وبلاگ

۳-۴- خلاصه فصل
در این فصل جزئیات مختلف راهکار پیشنهادی بیان گردید. همانطور که در فصل قبل توضیح داده شد الگوریتم IVC دارای معایبی نظیر عدم تشخیص تناظر بین خوشه‏ها، یکسان در نظر گرفتن رأی خوشه‏بندی‏های اولیه می‏باشد. ما در راهکار پیشنهادی برای هر یک از مسائل راه‏حلی ارائه نمودیم.

جهت تشخیص نظیر به نظیر بودن خوشه‏ها در خوشه‏بندی‏های مختلف، یک خوشه‏بندی را به عنوان خوشه‏بندی مرجع در نظر گرفته و با بهره گرفتن از الگوریتم تشخیص نظیر به نظیر بودن مشخص می‏گردد که هر یک از خوشه‏های یک خوشه‏بندی متناسب کدام خوشه در خوشه‏بندی مرجع می‏باشند. سپس با بهره گرفتن از شاخص DB هر یک از خوشه‏بندی‏ها وزن‏دار می‏گردند. ترکیب خوشه‏بندی‏ها و تولید یک خوشه‏بندی نهایی نیز با بهره گرفتن از الگوریتم خوشه‏بندی توافقی وزنی انجام می‎شود.
اجتماع خوشه‏بندی‏ها با بهره گرفتن از خوشه‏بندی زیر مجموعه‏هایی از صفات خاصه تشکیل می‏گردد. در حالتی که خوشه‏بندی‏ها بر روی داده‏های توزیع شده ناهمگن ایجاد گردند می‏توان انتظار داشت که یک یا چند خوشه‏بندی (با توجه به صفات خاصه‏ای که دارا می‏باشند) از کیفیت پایین‏تری نسبت به دیگر خوشه‏بندی‏ها برخوردار باشند. از اینرو، روش پیشنهادی که بر اساس وزن تخصیص یافته به هر خوشه‏بندی عمل می‏کند می‏تواند کارایی بالاتری نسبت به دیگر روش‏های خوشه‏بندی توافقی داشته باشد که به طور معمول اجازه‏ی تأثیرگذاری برابری را به خوشه‏بندی‏های اولیه می‏دهند.
فصل چهارم
پیاده‎سازی راهکار پیشنهادی و نتایج ارزیابی آن
۴-۱- مقدمه
در این فصل نتایج بدست آمده در ارزیابی الگوریتم پیشنهادی جهت انجام خوشه‏بندی توافقی بر روی داده‏های توزیع شده ناهمگن، ارائه می‏گردد. ابتدا ۴ معیار که در این ارزیابی مورد استفاده قرار گرفته‏اند شامل معیار دقت،DB ، Rand و میانگین اطلاعات دوجانبه نرمال سازی شده (ANMI)، بررسی می‏شوند. پس از آن جزئیات لازم در مورد مجموعه‏های داده‏ای استفاده شده در آزمایشات و شرایط مختلف خوشه‏بندی آنها بیان می‏گردد. در نهایت نیز نتایج بدست آمده در ارزیابی‏ها در مقایسه با ۴ الگوریتم دیگر (IVC، CSPA، HGPA و MCLA)، ارائه شده و مورد تحلیل قرار می‏گیرند.
۴-۲- معیارهای ارزیابی
در این بخش به بررسی معیارهای استفاده شده جهت ارزیابی نتایج در این پایان نامه می‏پردازیم. همانطور که در فصل قبل اشاره گردید، معیارهای ارزیابی خوشه‏بندی به دو گروه معیارهای داخلی و معیارهای خارجی تقسیم می‏شوند. ما از سه معیار داخلی جهت ارزیابی نتایج بدست آمده از خوشه‏بندی توافقی بر روی داده‏های توزیع شده ناهمگن و یک معیار خارجی جهت بررسی میزان توافق نتیجه‏ی بدست آمده با اجتماع خوشه‏بندی‏ها، استفاده می‏نماییم.
معیار‏های داخلی استفاده شده در این ارزیابی شامل معیارهای دقت، شاخص Davies-Bouldin و Rand می‏باشند. هر یک از این معیار‏ها، اطلاعاتی در مورد خوشه‏بندی تولید شده توسط راهکار پیشنهادی ارائه می‏دهند که می‏تواند نشان‏دهنده‏ی کیفیت خوشه‏بندی نیز باشد. البته لازم به ذکر است که شاخص Rand در فصل ۳ به عنوان یک معیار خارجی معرفی شد، اما در ارزیابی‏ها از نوع تغییر یافته‏ای استفاده شده است که قابلیت ارزیابی یک خوشه‏بندی را دارا
می‏باشد. تنها معیار خارجی استفاده شده در این ارزیابی‏ها معیار ANMI می‏باشد که جزئیات محاسبه‏ی این معیار نیز در فصل ۳ ارائه گردید. این معیار میانگین میزان توافق خوشه‏بندی نهایی را با اجتماع خوشه‏بندی‏ها نشان می‏دهد. در ادامه به معرفی هر یک از معیارهای ذکر شده و ارائه‏ جزئیات لازم جهت محاسبه‏ی آنها می‏پردازیم.
لازم به ذکر است که هیچ یک از معیارهایی که تاکنون در مقالات به عنوان معیارهای ارزیابی خوشه‏بندی‏ها معرفی شده‏اند، به تنهایی نمی‏توانند با قطعیت بهتر بودن یک الگوریتم خوشه‏بندی خاص را نسبت به سایر الگوریتم‏ها در تمامی شرایط نشان دهند. از اینرو، استفاده از معیارهای ارزیابی گوناگون می‏تواند امکان بررسی نتیجه‏ی خوشه‏بندی را از جنبه‏ه ای مختلف بوجود آورد.
۴-۲-۱- معیار دقت
معیار دقت یکی از متداول‏ترین معیارهای ارزیابی خوشه‏بندی می‏باشد. معیار دقت [۷۶] بر روی بیشترین تعداد اشیاء داده‏ای از یک کلاس داده در هر خوشه متمرکز می‏شود. در برخی مقالات نظیر [۷۶] این معیار با نام معیار خلوص^[۱۵۳] نیز مطرح شده است. روابط (۴-۱) و (۴-۲) نحوه‏ی محاسبه این معیار را نشان می‏دهند.

در روابطه (۴-۱) و (۴-۲)، π خوشه‏بندی‏ای بر روی N داده با K خوشه به صورت π={C₁, C₂, …, C_K} می‎باشد. مجموعه داده‏ای دارای تعدادی برچسب کلاس است و هر یک از داده‏ها دارای یکی از این برچسب‏ها می‏باشند. هر کدام از این برچسب‏ها نیز با L_j نشان داده می‏شوند.
معیار دقت یا خلوص، دقت الگوریتم خوشه‏بندی را در گروه‏بندی اشیاء داده با توجه به کلاس واقعی آنها نشان می‏دهد. به عنوان مثال اگر مجموعه داده‏ای دارای سه گروه باشد و الگوریتم خوشه‏بندی نیز اشیاء داده را در سه خوشه قرار داده و هر خوشه تنها شامل اشیاء داده‏ای از یک گروه خاص باشد، این خوشه‏بندی دارای دقت ۱۰۰% خواهد بود. لازم به ذکر است که جابه‏جایی اشیاء داده بین خوشه‏ها به همان میزان می‏تواند سبب کاهش دقت خوشه‏بندی گردد.
نتیجه‏ی ارزیابی معیار دقت، عددی بین صفر و یک است. مقدار یک زمانی بدست می‏آید که هر خوشه تنها شامل داده‏های از یک کلاس مشخص باشد. به عنوان مثال، شکل ۴-۱ نتیجه‏ی خوشه‏بندی بر روی ۱۷ شئ داده با ۳ کلاس را نشان می‏دهد. تعداد بیشینه‏ی کلاس‏ها در هر خوشه عبارتست از: ×، ۵ (خوشه‏ ۱)، o، ۴ (خوشه ۲) و ◊، ۳ (خوشه ۳). با توجه به شکل و روابط (۴-۱) و (۴-۲)، دقت خوشه‏بندی انجام شده به صورت ۰٫۷۱(۳+۴+۵)×(۱۷/۱) محاسبه می‏گردد. البته ذکر این نکته نیز ضروری است که این معیار از برچسب کلاس جهت انجام ارزیابی استفاده می‏کند اما از این برچسب‏ها در زمان انجام خوشه‏بندی هیچ استفاده‏ای نمی‏شود.

خوشه ۱
خوشه ۲
خوشه ۳
شکل ۴-۱ خوشه‏بندی ۱۷ شئ داده با سه کلاس [۷۵]
۴-۲-۲- شاخص Davies-Bouldin
همانطور که در فصل ۳ مطرح گردید شاخص DB میزان فشردگی و تفکیک شدگی خوشه‏ها را نشان می‏دهد. هر چه مقدار این شاخص کوچکتر باشد خوشه‏بندی‏ای با خوشه‏های فشرده‏تر و تفکیک شده‏تری در اختیار خواهیم داشت. جزئیات محاسبه‏ی شاخص DB در بخش ۳-۲-۲ آورده شد، بنابراین از تکرار آن در این بخش خودداری می‏کنیم. در این پایان نامه از شاخص DB، هم برای وزن‏دار نمودن خوشه‏بندی‏های اولیه و هم برای ارزیابی نتایج بدست آمده استفاده می‏گردد.
۴-۲-۳- شاخص Rand
معیار یا شاخص Rand میزان شباهت بین دو خوشه‏بندی را اندازه‏گیری می‏کند. مقدار این شاخص عددی بین صفر و یک می‏باشد، صفر نشان‏دهنده‏ی این است که دو خوشه‏بندی هیچ شباهتی در تصمیم‏ گیری‏هایشان با یکدیگر ندارند و یک نشان‏دهنده‏ی این است که دو خوشه‏بندی به طور کامل مشابه یکدیگرند. اما از معیار Rand در این پایان نامه به عنوان معیاری جهت اندازه‏گیری نرخ تصمیمات صحیح اتخاذ شده در خوشه‏بندی استفاده می‏گردد (یعنی به صورت یک معیار داخلی). از اینرو، مقدار صفر نشان‏دهنده‏ی این است که هیچ تصمیم صحیحی در خوشه‏بندی اتخاذ نشده است و یک نیز نشان‏دهنده‏ی این است که تصمیمات اتخاذ شده در خوشه‏بندی به طور کامل صحیح می‏باشد. نحوه‏ی محاسبه شاخص Rand در رابطه‏ (۴-۳) آورده شده است.