بهبود الگوریتم خوشه بندی K-means با استفاده از الگوریتم پیشنهادی فاخته توسعه یافته

امروزه، خوشه بندی نقش مهمی را در اغلب زمینه های تحقیقاتی مانند مهندسی، پزشکی، زیست شناسی، داده کاوری و ... ایفا می نماید. یکی از الگوریتم های معروف خوشه بندی، الگوریتم k-means می باشد، این الگوریتم در کنار مزایایی چون سرعت بالا و سهولت پیاده سازی، در دام بهینه محلی قرار گرفته و همواره جواب بهینه مساله را تولید نمی کند. به همین دلیل ما در این مقاله سعی نموده ایم با تعیین مراکز بهینه اولیه خوشه ها برای الگوریتم k-means، با استفاده از الگوریتم پیشنهادی فاخته توسعه یافته، تا درصد بالایی نتایج خوشه بندی را از بهینه محلی خارج نموده و به بهینه سراسری نزدیک نماییم. الگوریتم پیشنهادی، توسعه یافته الگو.ریتم فاخته کلاسیک می باشد که ما در روش پیشنهادی خود، تعدادی از عملگراهای آن را هدفمند و متنوع نموده ایم. بطور نمونه جهت افزایش سرعت همگرایی الگوریتم پیشنهادی، سعی نموده ایم جمعیت اولیه با پراکندگی بیشتر در فضای مساله، با استفاده از توالی آشوب تولید نماییم. همچنین جهت افزایش دقت و سرعت همگرایی الگوریتم، روال تعیین تعداد تخم برای هر فاخته موجود در جمعیت، مبتنی بر میزان شایستگی آن فاخته می باشد، در بهبودی دیگر جهت افزایش پوشش سراسری در فضای مساله، دسته های فاخته ایجاد شده حاصل از مرحله خوشه بندی فاخته ها را با درجه انحراف متفاوت در محیط به سمت فاخته بهینه سراسری مهاجرت خواهیم داد. سپس به منظور اعتبارسنجی، روش پیشنهادی بر روی چندین مجموعه داده استاندارد از سایت UCI مورد ارزیابی قرار گرفته است و نتایج حاصل با الگوریتم های چاله سیاه، الگوریتم مبنتی بر تئوری انبساط- انقباض، الگوریتم جستجوی فاخته (یانگ)، الگوریتم بهینه سازی فاخته (رجبیون) و الگوریتم k-means از لحاظ شاخص های، دقت، سرعت همگرایی و پایداری جواب ها مقایسه شده است. بررسی نتایج نشان می دهد، الگوریتم جدید ما قادر است جواب بهینه نهایی را با دقت، پایداری و سرعت همگرایی بالا در مقایسه با الگوریتم های دیگر تولید نماید.

Keywords:

خوشه بندی , داده کاوی , الگوریتم k-means , الگوریتم فاخته توسعه یافته