بخشی از مقاله
چکیده
خوشه بندی اطلاعات به معنی افراز کردن دادهها در خوشه های شبیه به هم است؛ به طوری که داده های هر خوشه حداکثر مشابهت را با همدیگر و حداکثر عدم شباهت را با داده های خوشه های دیگر داشته باشند. در اینجا یک چارچوب جدید برای بهبود کارایی خوشه بندی ترکیبی پیشنهاد شده است که مبتنی بر استفاده از زیرمجموعهای از خوشه های اولیه میباشند. انتخاب این زیرمجموعه نقش حیاتی در کارایی اجماع دارد. این انتخاب به کمک دو روش هوشمند انجام می گیرد. ایده های اصلی در روش های پیشنهادی برای انتخاب زیرمجموعهای از خوشه ها، استفاده از خوشه های پایدار به کمک الگوریتم های جستجوی هوشمند میباشند. برای اعتبارسنجی خوشه ها، از معیار stability مبتنی بر اطلاعات متقابل استفاده شده است. در آخر نیز خوشه های انتخاب شده را به کمک چندین روش ترکیب نهایی با هم جمع می کنیم. نتایج تجربی روی چندین دیتاست استاندارد نشان میدهد که روش های پیشنهادی میتوانند به طور موثری همچنین روش ترکیب کامل را بهبود دهند. کلمات کلیدی: خوشه بندی ترکیبی، اعتبارسنجی خوشه، شبیه سازی برودتی، GA
مقدمه
خوشه بندی دادهها به معنی جداکردن دادهها از یکدیگر و قرار دادن آنها در گروه های شبیه به هم است. به این صورت که داده های شبیه به هم باید در یک گروه قرار بگیرند و با داده های گروه های دیگر حداکثر تفاوت را دارا باشند [1] و . [2] فرآیند خوشهبندی سعی دارد که یک دیتاست را به چندین خوشه تقسیم نماید بطوریکه داده-های قرار گرفته در یک خوشه با یکدیگر شبیه بوده و با دادههای خوشههای دیگر متفاوت باشند. در حال حاضر روشهای متعددی برای خوشهبندی دادهها وجود دارد که بر اساس نوع دادهها، شکل خوشهها، فاصله دادهها و غیره عمل خوشهبندی را انجام میدهند.GA
روش ژنتیک1 رهیافتی است که تکامل طبیعی موجودات را الگو قرار میدهد .[4] این روش تقلیدی از فرایند تکامل با استفاده از روشهای کامپیوتری است. اساسیترین اصل تکامل، وراثت است. هر نسل، خصوصیات نسل قبلی را به ارث میبرد و به نسل بعد انتقال میدهد. این انتقال خصوصیات از نسلی به نسل بعد توسط ژنها صورت می-گیرد. جهانی که در آن زندگی میکنیم دائمًا در حال تغییر است. برای بقا در این سیستم پویا ، افراد باید توانایی داشته باشند که خود را با محیط، سازگار کنند. الگوریتمهای تکاملی به کار رفته در این مقاله، یکی GA و دیگری شبیه سازی برودتی بوده است. پارامترهای GA شامل اندازهی جمعیت 1000، تعداد نسلهای 500 و طول کروموزوم برابر با 120 برابر تعداد خوشه های واقعی به علاوه 180 میباشد. همچنین از احتمال جهش 0/01 عملگر تقطیع یکنواخت و عملگر انتخاب مرتب سازی استفاده شده است.
اعتبارسنجی خوشه
در این مرحله خوشه های به دست آمده مورد اعتبارسنجی قرار میگیرند تا کارایی هر خوشه مشخص شود. از آن جایی که میزان برازندگی2 یک خوشه در میان کل نقاط داده معنیدار است، تابع برازندگی خوشه یعنی gj - Ci,D - علاوه بر پارامتر اول خود یعنی خوشه Ci به دیتاست D نیز وابسته است. برای اعتبارسنجی خوشه از معیارهای stability مختلفی استفاده شده است. اگر چه همه روش های پیشنهادی برای اعتبارسنجی خوشه مبتنی بر NMI هستند، هر کدام از این روشها یکی از معایب آن را جبران میکند. یک روش اعتبارسنجی خوشه به طور کامل در این بخش شرح داده شده است. [25]
دیتاستها
روش پیشنهادی بر روی 10 دیتاست استاندارد نرمال شده مورد آزمایش قرار گرفته است. برای انجام آزمایشها سعی شده است تا دیتاستها از لحاظ تعداد کلاسها، تعداد ویژگیها و همچنین تعداد دادهها از حداکثر تنوع برخوردار باشند تا نتایج آزمایش ها تا حد ممکن دارای استحکام و قابل تعمیم باشد.
نتایج آزمایشها
در این بخش نتایج به کارگیری روش پیشنهادی روی دیتاست های مختلف و پارامترهای مورد استفاده گزارش شده است. روش پیشنهادی در محیط MATLAB - ver 7.1 - پیادهسازی و مورد آزمایش قرار گرفته است. نتایج آزمایشها روی میانگین 10 بار اجرای مستقل برنامه گزارش شده است. عملکرد روش های مختلف خوشه بندی با سه معیار Accuracy، NMI و F-Measure محاسبه شده است. در تمامی روش های مورد استفاده از روش K-means به عنوان روش پایه استفاده شده است. تعداد خوشه بندی های اولیه تولید شده نیز در تمام روشها ثابت و برابر با 120 است. در واقع این تعداد با دستکاری پارامتر k از روش K-means به دست آمده است. به این صورت که چهار گروه 30 تایی از خوشه بندی های اولیه، با در نظر گرفتن تعداد خوشه های مورد استفاده توسط این روش با اندازه های k، k+1، k+2 و k+3 حاصل شده است. همچنین، برای ایجاد تنوع بیشتر در خوشه بندی های اولیه از دادهبرداری بدون جاگذاری با نرخ %50 استفاده شده است. همچنین، برای ساختن افراز نهایی از روش اتصال منفرد[15] 3 بر روی ماتریس همبستگی، روش [18] Fuzzy K-means و روشهای مبتنی بر گراف HGPA، MCLA و [3] CSPA استفاده شده است.
اعمال الگوریتمهای تکاملی برای انتخاب خوشه ها
در عمل اعمال الگوریتم متاهیوریستیک برای انتخاب خوشه ها، دو مجموعهی خوشه های پایدار و خوشه های غیر پایدار به دست می آید. نتایج اجماع کامل و اجماعی که خوشه های را با استفاده از الگوریتم متاهیوریستیک انتخاب میکند بر حسب NMI و F-Measure و Accuracy بر روی دیتاستهای گوناگون آمده است. چنانچه مشاهده میگردد نتایج نه تنها کاهش نداشته، بلکه در اغلب موارد بهبود نیز یافته است. برای سهولت در تحلیل، میانگین نتایج بر روی 10 دیتاست در شکلهای زیرآورده شده است.
