ارایه یک الگوریتم ترکیبی برای خوشه بندی با استفاده از رویکرد فرا ابتکاری جستجوی ممنوعه

الگوریتم K-Meansیکی از روشهای رایج خوشه بندی می باشد که علیرغم مزایای بسیار از جمله سرعت بالا و سهولت پیاده سازی، در دام بهینه محلی قرار گرفته و همیشه جواب بهینه مساله را تولید نمی نماید. از سوی دیگر الگوریتمهای فراابتکاری مانند خوشه بندی کلونی مورچه ها و یا الگوریتم ژنتیک نیز که با منطق تصادفی و با تکرار اجرای الگوریتم، قادر به خوشه بندی داده ها با شکلهای پیچیده می باشد، لزوماً تولید جواب بهینه خوشه بندی را تضمین نمی نماید. در این مقاله جهت الگوریتمهایی که مراکز اولیه خوشه ها در آن به صورت تصادفی انتخاب می گردند، الگوریتم ترکیبی جدیدی با استفاده از روش فراابتکاری جستجوی ممنوعه طراحی و پیاده سازی شده است که می تواند سبب خروج از مینیمم محلی شده و بادرصد بالایی جواب بهینه مساله را تولید نماید. لگوریتم جدید K-Means+Tabu و Ant+Tabu با داده های مختلف تست و نتایج آن با سایر الگوریتمهای فراابتکاری نیز مقایسه شده است. بررسی نتایج نشان می دهد که الگوریتم جدید قادر است با دقت بالایی جواب بهینه را در مقایسه با نتایج حاصل از الگوریتمهای Ant Clustering و K-Means تولید نماید.

Keywords:

داده کاوی , خوشه بندی , جستجوی ممنوعه , بهینه سازی کلونی مورچه ها , الگوریتم K-Means مینیمم محلی