روشی نوین جهت خوشه بندی داده مبتنی بر ترکیب الگوریتمهای بهینهسازی ژنتیک و کرم شبتاب
الموضوعات : سامانههای پردازشی و ارتباطی چندرسانهای هوشمند
مهسا افسردیر
1
(
دانشگاه آزاد اسلامی واحد علوم تحقیقات، دانشکده فنی مهندسی، گروه مهندسی کامپیوتر، تهران، ایران
)
منصوره افسردیر
2
(
دانشگاه آزاد اسلامی واحد دزفول، دانشکده فنی مهندسی، گروه مهندسی پزشکی دزفول، ایران
)
الکلمات المفتاحية: الگوریتم ژنتیکی کرم شب تاب, الگوریتم کرم شب تاب, الگوریتم ژنتیک, داده کاوی, خوشه بندی k-means,
ملخص المقالة :
یکی ازمسائل مهم دردادهکاوی خوشهبندی است که بدون هدف ازپیش تعیین شدهای دادهها را بر اساس شباهت درون خوشهها تقسیمبندی میکند. از روشهای متداول خوشهبندی الگوریتم k-means است که بادریافت ورودی، دادههارابه k خوشه تقسیمبندی میکند. یکی ازمعایب این روش حساسیت به شرایط اولیه است که منجربه کاهش دقت درخوشهبندی میشود. از روشهای بهبود عملکرد k-means میتوان استفاده ازالگوریتمهای فراابتکاری را نام برد. در این پژوهش به دو روش بهینهسازی ژنتیک و کرم شبتاب پرداخته شده است و الگوریتم جدیدی تحت عنوان الگوریتم ژنتیکی کرمشبتاب جهت بهینهسازی خوشهبندی k-means ارائه شده است. الگوریتم کرمشبتاب از الگوریتمهای هوش جمعی است که از ویژگی نورچشمک زن کرمشبتاب الهام گرفته است و الگوریتم ژنتیک نوعی از الگوریتمهای فراابتکاری است که از تکنیک-های زیستشناسی مانند وراثت و جهش استفاده میکند. در الگوریتم k-means برای اینکه مراکز خوشه به صورت تصادفی انتخاب می شوند، خوشهبندی دقت لازم را ندارد. با استفاده از الگوریتمهای فراابتکاری سعی در بدست آوردن مراکز دقیق خوشهها داشته و در نتیجه آن، خوشه-بندی صحیح میباشیم. در روش پیشنهادی، ابتدا الگوریتم k-means را روی دادههای ورودی اجراکرده و خوشهبندی انجام میشود. سپس مضربی از مراکز خوشه که دراین الگوریتم بدست آمده است را به عنوان حد پایین و حد بالای الگوریتم پیشنهادی استفاده میکنیم. جمعیت اولیه به صورت تصادفی بین حد پایین و حد بالا تولید میشود. در حلقه اصلی الگوریتم جمعیت را به دو دسته جمعیت مساوی تقسیم می نماییم، بر روی دسته اول الگوریتم ژنتیک را اجرا میکنیم، بر روی دسته دوم بر اساس الگوریتم کرمشبتاب موقعیتهای جدید را بدست میآوریم. حال جمعیت قبلی و جمعیت جدید بدست امده از الگوریتم ژنتیک و جمعیت جدید بدست امده از الگوریتم کرمشبتاب را تلفیق کرده وآنها را از خوب به بد مرتب میکنیم و به تعداد مورد نیاز از آنها را انتخاب و به ابتدای حلقه میرویم. این فرایند را تا برقراری شرط توقف ادامه میدهیم. درپایان الگوریتم k-means، الگوریتم کرم شبتاب، الگوریتم ژنتیک و الگوریتم پیشنهادی بر روی سه مجموعه داده اعمال شده و نتایج مورد مقایسه قرار گرفته است.نتایج شبیهسازی نشان میدهد که الگوریتم ژنتیکی کرمشبتاب عملکرد بهتری در مقایسه با سایر روشها داشته است.
_||_