بخشی از مقاله
خلاصه
خوشهبندی یک تکنیک یادگیری بدون ناظر است که به منظور گروهبندی دادههای بدون برچسب به گروههایی از دادهها مورد استفاده قرار میگیرد. خوشهبندی دادهها بر اساس شباهتها و تفاوتهای میان دادهها انجام میشود. این گروهبندی به گونهای است که نمونههای موجود در یک خوشه بیشترین شباهت را با یکدیگر دارند و دادههایی که در گروههای مختلف قرار میگیرند کمترین شباهت را با هم دارند. در این مقاله 3 تکنیک خوشهبندی با ترکیب الگوریتمهای تکاملی ژنتیک و آشوب ، بهینهسازی انبوه ذرات و آشوب ، رقابت استعماری و آشوب با هدف ارائه الگوریتمی کارا و با دقت بالا برای خوشه بندی داده ها پیشنهاد شده است. نتایج حاصل از اجرای الگوریتم بر روی 10 مجموعه داده معروف بیانگر دقت الگوریتمهای پیشنهادی است.
کلمات کلیدی: خوشه بندی، الگوریتم رقابت استعماری، الگوریتم بهینه سازی نبوه ذرات، الگوریتم ژنتیک
.1 مقدمه
خوشهبندی از افرازبندی یک گروه متنوع به تعداد زیرگروه مشابه یا گروهبندی مجموعهای از اشیاء به کلاسی از اشیاء مشابه به وجود میآید، در هر خوشه باید دادههایی شبیه به هم قرار گیرند و کمترین شباهت را با دادههای موجود در دیگر خوشهها دارا باشند. روشهای مختلف خوشهبندی با توجه به رویکردی که برای گروهبندی دادهها از آن استفاده میکنند، به انواع مختلفی تقسیم میشوند که از آن میان میتوان به روشهای مبتنی بر افراز دادهها، روشهای سلسه مراتبی، روش-های شبکهای، روشهای مبتنی بر تراکم و روشهای مبتنی بر مدل اشاره نمود .[2-1] در این مقاله روی خوشهبندی افرازی متمرکز میشویم. معروفترین الگوریتمهای خوشهبندی افرازی، الگوریتمهای خوشهبندی مرکز محور هستند که در میان آنها به الگوریتم k-means میتوان اشاره کرد. با توجه به سادگی و کارایی، الگوریتم k-means در سالهای گذشته مورد توجه قرار گرفته است.
با این حال، از کاستیهای آن میتوان به موارد زیر اشاره کرد: الگوریتم به انتخاب نقاط اولیه حساس است و به راحتی در مینیمم محلی گرفتار میشود .[14] به منظور غلبه بر این مشکل الگوریتمهای خوشهبندی اکتشافی معرفی شدهاند.برای مثال Koa و همکارانش با ترکیب دو الگوریتم ژنتیک و PSO روشی را ابداع نموده که در آن از عملگر جهش و تقاطع برای ژنتیک بهره گرفتهاند، این روش توانست مشکلات توابع پیوسته را رفع نماید. همچنین در یافتن جواب بهینهسراسری و سبب همگرایی تغییرات چشمگیری حاصل شده است .[3] یکی دیگر از روشهای جدید برای مسائل دادهکاوی، ترکیب الگوریتم PSO تطبیقی فازی با دو الگوریتم کلونی مورچه و k-means میباشد. این روش توسط نیکنام و همکارانش در سال 2010 مطرح گردید.
نتایج حاصله از این تکنیک در راستای بهبود عملکرد خوشهبندی اطلاعات بسیار جالب توجه میباشد از مزیت کلونی مورچگان، توانایی پیشبینی تعداد خوشهها را میتوان ذکر نمود و اینکه نتایج حاصله برتری کیفیت عملکرد ارزیابی را تضمین مینماید .[4] در سال 2015، Zheng و همکارانش روشی مبتنی بر ترکیب الگوریتم کلونی مورچگان و آشوب ارائه نمودهاند. این الگوریتم بر پایه زندگی اجتماعی مورچهها بنا شده است که در حوزه هوش مصنوعی میباشد. در این الگوریتم از آشوب برای تعیین مسیر مورچه ها استفاده شده است و برای خوشهبندی تصاویر ار این الگوریتم بهره گرفته شده است .[5] بهمنی فیروزی و همکارانش در سال 2010 یک الگوریتم تکاملی ترکیبی براساس ترکیب PSO، SA و K-means برای یافتن راه حل بهینه ارائه کردهاند .[6]
یک الگوریتم خوشهبندی از ترکیب الگوریتم رقابت کشورهای استعماری، آبکاری فولاد و k-means در سال 2012 نیکنام و همکارانش برای مساله خوشه-بندی ارائه کردهاند. عملکرد این الگوریتم که K-MICA ترکیبی نام دارد در مقایسه با الگوریتمهای k-means، رقابت استعماری، K-MICA و MICA-K قابل ملاحظه میباشد Chuang .[7] و همکارانش در سال 2011 الگوریتمی از ترکیب آشوب و الگوریتم PSO پیشنهاد دادهاند که در این الگوریتم ابتدا از فرمول لجستیک برای تولید جمعیت اولیه استفاده شده است و یک استراتژی جدیدی با عنوان استراتژی تسریع که شبیه k-means است را اعمال کردهاند .[8]
پورسیاه ناوی و همکارانش در سال 2014 الگوریتم PSO را با تابع برازندگی cmeans فازی کارآمدتر کردهاند و سپس برای تولید جمعیت اولیه الگوریتم را با آشوب ترکیب کردهاند و در نهایت برای رفع مشکل همگرایی زودرس یک جهش و تابع برازندگی مبتنی بر وزن اینرسی پیشنهاد کردهاند Chuang .[9] و همکارانش در سال 2012 در مقالهای با عنوان بهینه-سازی انبوه ذرات برای خوشهبندی روشی جدید برای خوشهبندی دادهها معرفی کردهاند. یک الگوریتم PSO مبتنی بر الگوی آشوبگونه گوسین ارایه دادهاند. در این الگوریتم از الگوی گوسین برای جمعیت اولیه و به روز رسانی سرعت و موقعیت ذرات استفاده شده است Wan .[10]
و همکارانش در سال 2012 مقالهای با عنوان ازدحام مورچههای آشوبگونه روشی نوین برای خوشهبندی دادهها ارائه کردهاند. الگوریتم یشنهادی برای دستیابی به خوشه-بندی بهینه براساس کمینه کردن تابع هدف عمل میکند. این الگوریتم سه نتیجه دست مییابد: یافتن راهحل بهینه سراسری مساله، عدم حساسیت خوشهها به اندازه مجموعه و حجم دادهها و برای مجموعه دادههای چند بعدی مناسب است .[11] در سال 2015 Maheshwar و همکارانش یک الگوریتم ترکیبی از الگوریتمهای ژنتیک و کرم شبتاب برای مساله خوشهبندی ارائه کرده-اند، در روش پیشنهادی الگوریتم کرم شبتاب برای انتخاب جمعیت اولیه از الگوریتم ژنتیک کمک میگیرد.[12]
الگوریتمهای تکاملی از مکانیزمها و عملیات ابتدایی برای حل مساله استفاده میکنند و در طی یک سری از تکرارها به راه حل مناسب مسئله میرسند. این الگوریتمها غالباً از یک جمعیت حاوی راهحلهای تصادفی شروع میکنند و در طی هر مرحله تکرار، سعی در بهتر کردن مجموعه راهحلها دارند .[13] لذا با بهرهگیری از ترکیب تئوری آشوب و الگوریتمهای تکاملی بهعنوان روشهای بهینهسازی نوین، این محدودیت مرتفع میشود. قابل توجه است که نسخههای اصلی الگوریتم-های تکاملی به تنهایی در رفع این مشکل کارساز نبوده است. تئوری آشوب مطالعه رفتار سیستمهای دینامیکی است که به انتخابهای اولیه حساسیت بالایی دارند و تفاوتهای کوچک در انتخابهای اولیه - مثل خطای گرد گردن در محاسبات ریاضی - باعث واگرایی نتایج حاصل از سیستمهای آشوبی میشود و در نتیجه پیشبینیهای بلند مدت را غیرممکن می-کند.
بنابراین از ایده دنبالههای آشوبی، شبه تصادفی بودن جمعیت اولیه، برای بهبود عملکرد الگوریتم استفاده میشود تا احتمال همگرایی به نقاط بهینه محلی کاهش یابد. هدف مقاله این است که با بررسی الگوریتمهای موجود در زمینه خوشهبندی، راهکاری برای ایجاد تغییرات در الگوریتمهای موجود برای بالا بردن سرعت همگرایی و بهبود کیفیت خوشه-بندی ارائه گردد بهگونهای که محدودیت های موجود از جمله کارایی برای پایگاه دادههای با حجم بالا، کشف خوشهها با اشکال مختلف، عدم حساسیت به ترتیب دادههای ورودی، قابلیت تفسیر و استفاده را پوشش دهد.در ادامه، مقاله به این صورت سازمان یافته است: در بخش 2 مساله تحلیل خوشهای معرفی شده است. در بخش 3 الگوریتم پیشنهادی شرح داده خواهد شد. در بخش 4 روشهای اعتبارسنجی خوشهها معرفی شدهاند. در بخش 5 نتایج خوشه بندی با الگوریتمهای تکاملی آشوبگونه نشان داده شده است. در نهایت بخش 6 شامل خلاصه و نتیجه است.
.2 تحلیل خوشه ای
همانطور که قبلا اشاره شد، در این مقاله بحث اصلی در رابطه با خوشهبندی افرازی است. در یک خوشهبندی افرازی، مجموعهای از شی را به خوشه افراز خواهیم کرد. الگوریتم k-means یکی از روشهای خوشهبندی افرازی است. این روش علیرغم سادگی آن یک روش پایه برای بسیاری از روشهای خوشهبندی دیگر محسوب میشود.[14] تابع هدف الگوریتم، از فرمول زیر محاسبه میشود که معیار خوبی برای شرط پایانی است:
در فرمول - 1 - معیار فاصله بین نقاط و مرکز خوشه j ام است. گامهای اصلی الگوریتم k-means به شرح زیر است:
1.درابتدا k نقطه از بین شیء به تصادف به عنوان مراکز خوشهها انتخاب میشوند.
2.سپس، فاصله بین همه اشیاء با مراکز همه خوشهها با استفاده از فرمول 1 محاسبه میگردد. هر نمونه داده به خوشهای که مرکز آن کمترین فاصله تا آن داده را داراست، نسبت داده میشود.
3.پس از انتصاب تمام دادهها به یکی از خوشهها برای هر خوشه یک نقطه جدید به عنوان مرکز محاسبه میشود. - میانگین نقاط متعلق به هر خوشه -
4.تا زمانی که تغییری در مراکز خوشهها حاصل نشده است مراحل 2 و 3 تکرار میشود.
الگوریتم k-means پیچیدگی زمانی خطی دارد، اما به انتخاب نقاط اولیه حساس است و به سادگی در بهینه محلی گرفتار میشود.
.3 الگوریتم پیشنهادی
در روش های پیشنهادی از مزایای تئوری آشوب و الگوریتمهای PSO، ICA و GA بهره گرفته خواهد شد؛ به طوری که معایب الگوریتمها پوشش داده خواهد شد. در واقع هدف ارائه راهکاری است که توسط آن دادهها را با حداقل خطا خوشه-بندی نمود. زمانی خوشهبندی ایدهآل میسر میگردد و هدف نهایی برآورده خواهد شد؛ که حداقل شباهت بین دادههای موجود در دستههای مجزا، همچنین حداکثر شباهت بین دادههای موجود در یک دسته برقرار باشد. در این راستا، روش k-means علیرغم معایبش - وابستگی به شرایط اولیه، همگرایی به نقاط بهینه محلی - ، به دلیل سادگی و سهولت شبیهسازی آن بسیار کاربرد دارد.جهت مرتفع نمودن این معایب، در تحقیقات اخیر ایدههای متفاوتی بیان گردیده است که تا حد قابل قبولی کارساز بوده است. در ادامه ترکیبی از الگوریتمهای تکاملی و پدیده آشوب ارائه شده است.فرمول آشوب استفاده شده در روشهای پیشنهادی در به صورت زیر است :[15]
