بخشی از مقاله
چکیده
خوشهبندی یکی از مسائل مهم در زمینه یادگیری ماشین، داده کاوی و الگوشناسی است. در واقع خوشهبندی دادهها را به دستههایی که از نظر پارامترهای مورد علاقه، شباهت بیشتری به یکدیگر دارند، تقسیم میکند. الگوریتم K-means یکی از روشهای رایج خوشهبندی می باشدکه علیرغم مزایای بسیار از جمله سرعت بالا در دام بهینه محلی قرار گرفته و حساس به مقادیر اولیه میباشد و همیشه جواب بهینه مسئله را تولید نمینماید. روش خوشهبندی K-harmonic means، مسئله حساس بودن به مقدار اولیه را پوشش میدهد اما مشکل گرفتار شدن در دام بهینه محلی همچنان این الگوریتم را تهدید میکند. در این مقاله سعی شده است که یک الگوریتم جدید - APKHM - برای بهبود خوشهبندی دادهها با استفاده از روش فرا ابتکاری ABC و PSO پیادهسازی شود. الگوریتم کولونی زنبور - ABC - از جمله رویکردهای فرا اکتشافی مبتنی بر جمعیت میباشد که یک تکنیک بهینه سازی احتمالی است که راهحل مناسبی برای غلبه بر مشکل ذکر شده است .الگوریتم HABC-PSO با مجموعه دادههای مختلف تست و نتایج آن با الگوریتمهای KHM، PSOKHM و GSAKHM مقایسه شده است. نتایج شبیهسازی نشان میدهد که الگوریتم جدید قادر است با دقت بالایی جواب بهینه را تولید نماید.
کلید واژه- خوشه بندی داده، کولونی زنبور عسل، بهینهسازی توده ذرات
-1 مقدمه
خوشهبندی دارای ویژگی هایی است که بر اساس آن می توان یک مجموعه داده را به بخشهایی - خوشههایی - تقسیم کرد بطوریکه عناصر هر بخش بیشترین شباهت را با هم و کمترین شباهت را با اعضای دیگر بخش ها داشته باشد. به دلیل اهمیت بالای این موضوع، در سال های اخیر پژوهش های زیادی در این زمینه صورت گرفته است که در بیشتر آنها سعی شده است زمان پردازش و پارامتر انحراف معیار توسط الگوریتمهای مختلف پیشبینی و کاسته شوند. محاسبه و بدست آوردن این زمانها میتواند کارایی الگوریتمهای خوشهبندی ارائه شده را به طور چشمگیری افزایش دهد. الگوریتم K-means یکی از روشهای معروف خوشهبندی محسوب میگردد که به سادگی قابل پیادهسازی می باشد.
متاسفانه نسخه اصل آن دارای محدودیتهایی از جمله وابستگی به مقادیر اولیه و همگرایی به پاسخ بهینه محلی میباشد. هدف اصلی خوشهبندی K-means این است که مجموع عدم تشابه بین تمام اشیاء یک خوشه از مراکز خوشههای متناظرشان کمترین باشد .[4-1] الگوریتمK-harmonic means - KHM - الگوریتمی است که در سال2002 پیشنهاد شد و هدف از آن این بود که میانگین هارمونیک تمامی نقاط موجود در یک مجموعه داده را تا مراکز خوشهها کمترین کند. الگوریتم KHM به حل مشکل مقداردهی اولیه در الگوریتم K-means می پردازد اما همچنان مشکل گرفتار شدن در دام بهینه محلی آن را تهدید می کند. بنابراین به هدف دستیابی به الگوریتم خوشهبندی بهتر، باید به دنبال راهحلی برای غلبه بر مشکل افتادن در دام بهینه محلی باشیم .[6 ,5 ,2]
با این حال، KM و KHM هر دو به راحتی در بهینه محلی اجرا میشوند. برای حل این مشکل، تعدادی از الگوریتمهای خوشهبندی اکتشافی معرفی شدند. بهینهسازی گروهی ذرات - PSO - یک تکنیک بهینهسازی مبتنی بر جمعیت میباشد که از رفتار گروهی پرندگان و ماهی ها الهام گرفته شده است. از این الگوریتم میتوان به عنوان روشی برای کمک به الگوریتم KHM جهت فرار از گرفتار شدن در دام بهینه محلی استفاده کرد که الگوریتم خوشهبندی ترکیبی PSOKHM سعی میکند از مزایای هر دو روش جهت بهبود عمل خوشهبندی بهره ببرد .[2] الگوریتم جستجوی گرانشی - GSA - ، با الهام از مفاهیم جرم و نیروی جاذبه و با شبیه سازی قوانین موجود در طبیعت ارایه شده است.
الگوریتم GSAKHM سال 2011 برای بهبود خوشهبندی معرفی گردید تا با استفاده از مزایای الگوریتم GSA و با ترکیب الگوریتم KHM در جهت بهبود خوشهبندی بهره ببرد .[8 ,7] در این مقاله کارایی الگوریتم مربوطه را بر روی چندین مجموعه داده استاندارد از پایگاه داده های - UCI - و با چندین الگوریتم مطرح شده در خوشهبندی دادهها مقایسه گردیده است.بقیه مقاله به شرح زیر سازماندهی شده است: در بخش 2، ما در مورد الگوریتم خوشهبندی K-harmonic بحث کردیم. بخش 3، الگوریتم استاندارد ABC معرفی میکنیم. بخش 4 در مورد الگوریتم PSO بحث میکنیم. بخش 5 ترکیب الگوریتمهای ABC و PSO را برای حل مسئله خوشهبندی معرفی میکنیم. بخش 6 آزمایشات بدست آمده از الگوریتم را که نشان میدهد عملکرد الگوریتم ترکیبی ما بهتر از الگوریتمهای معرفی شده است را ارائه میکنیم.
-2 الگوریتم خوشهبندی K-harmonic means
خوشهبندی KM یک روش ساده و سریع است که به دلیل پیادهسازیآسان و تعداد تکرار کم، عموماً مورد استفاده قرار میگیرد. الگوریتم KM در تلاش برای یافتن مراکز خوشههای c1, c2 ,...,c3 به گونهای عمل می کند که مجموع مربعاتفاصلهای هر نقطه xi تا نزدیکترین مرکز خوشه c j کمترین شود. وابستگی کارایی KM روی مقداردهی اولیه مراکز، یک مشکل اصلی این الگوریتم میباشد. در این الگوریتم ارتباط قویای بین نقاط داده و نزدیکترین مراکز خوشه برقرار شده و باعث میشود مراکز خوشهها از محدودهی تراکم محلی دادهها خارج نشوند. روش - K-harmonic means - KHM این مشکل عمده را از طریق جایگزینی کمترین فاصله یک نقطه از مرکز که در KM استفاده میشود با میانگین هارمونیک فاصله هر نقطه تا تمامی مراکز برطرف می کند. میانگین هارمونیک یک امتیاز مناسبی را به هر نقطهی داده بر اساس نزدیکی آن به هر مرکز میدهد که این امر را به عنوان یک ویژگی میانگین هارمونیک در نظر میگیرند.
نمادهای زیر برای فرمولبندی الگوریتم KHM استفاده می شود:
دادهای که باید خوشهبندی شود.مجموعه مراکز خوشهها تابع عضویتی که سهم دادهی xi ، را که متعلق به مرکز c j است، تعریف میکند. : w xi تابع وزنی که میزان تاثیرداده را در محاسبهی مجدد پارامترهای مرکز درتکرار بعدی تعریف می کند.الگوریتم پایه برای خوشهبندی KHM به صورت زیر میباشد:page8
- 1 مقداردهی اولیه الگوریتم با مراکز حدسی - C انتخاب تصادفی مراکز - .
- 2 محاسبه مقدار تابع هدف به صورت زیر است:که p یک پارامتر ورودی با مقدار 2p میباشد.
- 3 برای هر دادهxi ، تابع عضویت xi m c j به ازای هر مرکزc j به صورت زیر محاسبه میشود:
- 4 برای هر دادهxi ، وزنw xi مربوط به آن به صورت زیر محاسبه میشود:
- 5 برای هر مرکز c j ، فاصله آن از تمامی نقاط xi بر طبق توابع عضویت و وزنهایشان به صورت زیر محاسبه مجدد میشود:
- 6 گام های 2 تا 5 را به ازای تعداد تکرار از پیش تعریف شدهای انجام می دهیم یا تا زمانی که KHM - X,C - به اندازه قابل توجهای تغییر نکند.
- 7 نقطه xi را به کلاستر j با بزرگترین m c j xi تخصیص میدهیم.
این الگوریتم نشان می دهد که KHMضرورتاً به مقداردهی اولیه مراکز حساس نمیباشد ولی تمایل به همگرا شدن به بهینه محلی در آن وجود دارد .[9 ,6 ,2]
-3 الگوریتم کلونی زنبور عسل
الگوریتم کلونی زنبور عسل - ABC - از جمله رویکرهای فرا اکتشافی مبتنی بر جمعیت میباشد که توسط کارابوگا - Karaboga - و همکارانش ارائه شده است .[10] الگوریتم ABC رفتار هوشمندانه دسته های زنبور عسل را در یافتن مزارع گل - برای یافتن غذا - شبیه سازی میکند که یک الگوریتم قدرتمند و کارا و در عین حال ساده می باشد. در الگوریتم کلونیهای
