2-?. خوشه‌بندی ترکیبی33
2-?-1. ایجاد تنوع در خوشه‌بندی ترکیبی34
2-?-1-1. استفاده از الگوریتم‌های مختلف خوشه‌بندی ترکیبی35
2-?-1-2. تغییر پارامترهای اولیه خوشه‌بندی ترکیبی35
2-?-1-3. انتخاب یا تولید ویژگی‌های جدید36
2-?-1-4. انتخاب زیرمجموعه‌ای از مجموعه داده اصلی36
2-?-2. ترکیب نتایج با تابع توافقی37
2-?-2-1. روش مبتنی بر مدل مخلوط37
2-?-2-2. روش مبتنی بر ابر گراف44
2-?-2-2-1. روش CSPA46
2-?-2-2-2. روش HGPA47
2-?-2-2-3. روش MCLA48
2-?-2-3. روش‌های مبتنی بر ماتریس همبستگی50
2-?-2-3-1. الگوریتم‌های سلسله مراتبی تراکمی51
2-?-2-3-2. الگوریتم افرازبندی گراف با تکرار52
2-3-3. الگوریتم‌های خوشه‌بندی ترکیبی کامل56
2-4. خوشه‌بندی ترکیبی مبتنی بر انتخاب56
2-4-1. خوشه‌بندی ترکیبی مبتنی بر انتخاب فرن و لین57
2-4-1-1. تعریف معیار کیفیت در روش فرن و لین57
2-?-?-2. تعریف معیار پراکندگی در روش فرن و لین58
2-?-?-3. راهکار انتخاب خوشه‌ برای تشکیل نتیجه نهایی در روش فرن و لین58
2-4-2. الگوریتم هوشمند طبقه‌بندی مجموعه داده‌ها60
2-4-3. خوشه‌بندی ترکیبی طیفی مبتنی بر انتخاب بر اساس شباهت61
2-4-3-1. معیار ارزیابی در روش پیشنهادی ژیا61
2-4-3-2. انتخاب خوشه‌بندی بر اساس قانون نزدیک‌ترین همسایه در روش ژیا62
2-4-4. خوشه‌بندی ترکیبی انتخابی لی‌مین64
2-4-4-1. انتخاب افراز مرجع در روش لی‌مین64
2-4-4-2. راهکار انتخاب خوشه در روش‌ لی‌مین66
2-4-4-3. چهارچوب الگوریتم خوشه‌بندی انتخابی لی‌مین68
2-4-5. خوشه‌بندی بر اساس معیار MAX با استفاده از مجموعه‌ای از خوشه‌های یک افراز69
2-4-5-1. راهکار ارزیابی خوشهی MAX69
2-4-5-2. روش انباشت مدارک توسعهیافته70
2-4-6. خوشه‌بندی بر اساس معیار APMM با استفاده از مجموعه‌ای از خوشه‌های یک افراز70
2-5. روش بهترین افراز توافقی اعتبارسنجی شده72
2-6. استفاده از نظریه خرد جمعی در علوم رایانه73
فصل سوم
3. روش تحقیق76
3-1. مقدمه76
3-2. نظریه خرد جمعی77
3-2-1. شرایط جامعه خردمند78
3-2-1-1. تعریف معیار پراکندگی78
3-2-1-2. تعریف معیار استقلال79
3-2-1-3. تعریف معیار عدم تمرکز79
3-2-1-4. روش ترکیب مناسب80
3-2-2. اهمیت و رابطه استقلال و پراکندگی در خرد جمعی80
3-2-3. استثناءها در خرد جمعی82
3-3. خوشه‌بندی خردمند با استفاده از آستانه‌گیری82
3-3-1. روش ارزیابی پراکندگی نتایج84
3-3-2. روش ارزیابی استقلال الگوریتم‌ها85
3-3-3. عدم تمرکز در بخش‌های سازنده خوشه‌بندی ترکیبی88
3-3-4. مکانیزم ترکیب مناسب90
3-3-5. بررسی تأثیر مکانیزم بازخورد در کیفیت نتیجه نهایی90
3-3-6. شبه کد خوشه‌بندی خردمند با استفاده از آستانه‌گیری91
3-4. خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم93
3-4-1. بررسی مکانیزم حل مسائل توسط الگوریتم‌های خوشه‌بندی93
3-4-2. مدل‌سازی گراف استقلال الگوریتم95
3-4-2-1. زبان استقلال الگوریتم‌ خوشه‌بندی96
3-4-2-2. تبدیل کد به گراف استقلال الگوریتم99
3-4-?-?. ارزیابی گراف استقلال الگوریتم107
3-4-3. چهارچوب خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم110
3-4-3-1. ارزیابی استقلال الگوریتم110
3-4-3-2. روش انباشت مدارک وزن‌دار112
3-4-3-3. شبه کد خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم113
فصل چهارم
4. پیاده‌سازی و تحلیل نتایج116
4-1. مقدمه116
4-2. مجموعه داده‌116
4-3. مدل‌سازی الگوریتم‌ها به زبان استقلال الگوریتم‌118
4-4. ابزار تحلیلگر کد استقلال الگوریتم128
4-5. نتایج آزمایش‌ها130
فصل پنجم

5. جمع‌بندی و کار‌های آینده140
5-1. جمع‌بندی140
5-2. کار‌های آینده141
منابع و مآخذ142
فهرست جداول
فصل سوم
جدول3-1. نگاشت لغات لاتین در خوشه‌بندی ترکیبی به نظریه خرد جمعی …………………………………………………. 93
جدول3-2. یک نمونه از جدول نگاشت استاندارد کد …………………………………………………………………………………. 98
فصل چهارم
جدول4-1. مجموعه داده ………………………………………………………………………………………………………………………. 117
جدول4-2. لیست مجموعه الگوریتم‌های پایه ………………………………………………………………………………………….. 119
جدول4-3. جدول نگاشت استاندارد کد …………………………………………………………………………………………………. 120
جدول4-4. دقت نتایج این الگوریتم‌های خوشه‌بندی را نسبت به کلاس‌های واقعی داده ……………………………….. 130
جدول4-5. جدول مقایسه معیار اطلاعات متقابل نرمال‌ شده (NMI) نتایج آزمایش ………………………………………. 132
فهرست تصاویر و نمودار
فصل دوم
شکل 2-1. یک خوشه‌بندی سلسله مراتبی و درخت متناظر …………………………………………………………………………. 10
شکل 2-2. ماتریس مجاورت …………………………………………………………………………………………………………………… 11
شکل 2-3. رابطه دودویی و گراف آستانه ………………………………………………………………………………………………….. 12
شکل 2-4. گراف‌های آستانه برای ماتریس ………………………………………………………………………………………….. 12
شکل 2-5. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی منفرد …………………………………………………………… 13
شکل 2-6. دندوگرام پیوندی منفرد برای ماتریس………………………………………………………………………………….. 13
شکل 2-7. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی کامل ……………………………………………………………. 14

در این سایت فقط تکه هایی از این مطلب با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

شکل 2-8. دندوگرام پیوندی کامل برای ماتریس ………………………………………………………………………………….. 14
شکل 2-9. الگوریتم خوشه‌بندی افرازبندی………………………………………………………………………….. 16
شکل 2-10. الگوریتم فازی خوشه‌بندی ………………………………………………………………………………………… 18
شکل 2-11. خوشه‌بندی کاهشی ……………………………………………………………………………………………………………… 23
شکل 2-12. شبه‌کد الگوریتم MKF ………………………………………………………………………………………………………… 26
شکل2-13. (الف) مجموعه داده با تعداد 10 خوشه واقعی. (ب) منحنی ……………………………………………….. 29
شکل2-1?. (الف) مجموعه داده (ب) منحنی مربوطه …………………………………………………………………………. 29
شکل2-15. دو افراز اولیه با تعداد سه خوشه …………………………………………………………………………………………….. 31
شکل2-16. نمونه‌های اولیه در نتایج الگوریتم …………………………………………………………………….. 36
شکل 2-17. زیر شبه کد الگوریتم خوشه‌بندی ترکیبی توسط مدل مخلوط …………………………………………………….. 43
شکل 2-18. خوشه‌بندی ترکیبی ………………………………………………………………………………………………………………. 44
شکل 2-19. نمونه ماتریس، جهت تبدیل خوشه‌بندی به ابر گراف ……………………………………………………….. 45
شکل 2-20. ماتریس شباهت بر اساس خوشه برای مثال شکل (3-5) ………………………………………………………….. 46
شکل 2-21. الگوریتم افرازبندی ابر گراف ………………………………………………………………………………………………… 47
شکل 2-22. الگوریتم فرا خوشه‌بندی ……………………………………………………………………………………………………… 49
شکل2-23. الگوریتم خوشه‌بندی ترکیبی مبتنی بر ماتریس همبستگی ……………………………………………………………. 50
شکل2-24. الگوریتم افرازبندی با تکرار ……………………………………………………………………………………………………. 53
شکل2-25. نمایش گراف مجاورت در مراحل کاهش درجه ماتریس و شمارش آن ………………………………………… 54
شکل2-26. مثال روند تغییر توزیع تعداد خوشه …………………………………………………………………………………………. 55
شکل2-27. جریان کار عمومی برای پیاده‌سازی الگوریتم افرازبندی گراف …………………………………………………….. 55
شکل 2-28. گراف تابع در بازه بین صفر و یک ………………………………………………………………………………… 62
شکل 2-29. الگوریتم خوشه‌بندی ترکیبی طیفی مبتنی بر انتخاب بر اساس شباهت ………………………………………… 63
شکل 2-30. مثالی از ماتریس اتصال ………………………………………………………………………………………………………… 66
شکل 2-31. شبه کد خوشه‌بندی ترکیبی انتخابی لی‌مین ……………………………………………………………………………… 68
شکل 2-32. روش ارزیابی خوشهی یک افراز در روش MAX ……………………………………………………………………. 69
شکل 2-33. چهارچوب خوشهبندی ترکیبی مبتنی بر انتخاب با استفاده از مجموعه‌ای از خوشه‌های یک افراز …… 71
شکل 2-34. چهارچوب روش بهترین افراز توافقی اعتبارسنجی شده ……………………………………………………………. 72
فصل سوم
شکل3-1. چهارچوب الگوریتم خوشه‌بندی خردمند با استفاده از آستانه‌گیری ………………………………………………… 82
شکل3-?. محاسبه درجه استقلال دو خوشه‌بندی ……………………………………………………………………………………….. 86
شکل3-3. تأثیر عدم تمرکز بر روی پیچیدگی داده ……………………………………………………………………………………… 89
شکل3-3. تأثیر انتخاب افرازها در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر مقدار NMI ارزیابی‌شده …………………… 91
شکل3-4. شبه کد خوشه‌بندی خردمند با استفاده از آستانه‌گیری …………………………………………………………………… 92
شکل3-5. دسته‌بندی الگوریتم‌های خوشه‌بندی ………………………………………………………………………………………….. 94
شکل3-6. کد الگوریتم K-means به زبان استقلال الگوریتم‌ خوشه‌بندی ……………………………………………………….. 98
شکل3-7. تبدیل کد‌های شروع و پایان به گراف ………………………………………………………………………………………. 100
شکل3-8. تبدیل عملگر شرط ساده به گراف …………………………………………………………………………………………… 100
شکل3-9. تبدیل عملگر شرط کامل به گراف …………………………………………………………………………………………… 101
شکل3-10. تبدیل عملگر شرط تو در تو به گراف ……………………………………………………………………………………. 101
شکل3-11. تبدیل عملگر حلقه ساده به گراف …………………………………………………………………………………………. 102
شکل3-12. تبدیل عملگر حلقه با پرش به گراف ……………………………………………………………………………………… 102
شکل3-13. پیاده‌سازی شرط ساده بدون هیچ کد اضافی ……………………………………………………………………………. 103
شکل3-14. پیاده‌سازی شرط ساده با کدهای قبل و بعد آن ………………………………………………………………………… 103
شکل3-15. پیاده‌سازی شرط کامل …………………………………………………………………………………………………………. 104
شکل3-16. پیاده‌سازی شرط‌ تو در تو …………………………………………………………………………………………………….. 104
شکل3-17. پیاده‌سازی یک شرط کامل در یک شرط ساده ………………………………………………………………………… 105
شکل3-18. پیاده‌سازی یک شرط کامل در یک شرط کامل دیگر ………………………………………………………………… 105
شکل3-19. پیاده‌سازی حلقه ساده ………………………………………………………………………………………………………….. 106
شکل3-20. پیاده‌سازی یک حلقه ساده داخل حلقه‌ای دیگر ……………………………………………………………………….. 106
شکل3-21. پیاده‌سازی یک حلقه داخل یک شرط کامل ……………………………………………………………………………. 106
شکل3-22. پیاده‌سازی یک شرط کامل داخل یک حلقه ساده …………………………………………………………………….. 107
شکل3-23. ماتریس درجه وابستگی‌ کد ………………………………………………………………………………………………….. 108
شکل3-24. شبه کد مقایسه محتوای دو خانه از آرایه‌های استقلال الگوریتم …………………………………………………. 108
شکل3-25. چهارچوب خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم ……………………………………………… 110
شکل3-26. شبه کد خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم …………………………………………………… 113
فصل چهارم
شکل?-?. مجموعه داده Halfring ………………………………………………………………………………………………………….. 118
شکل4-2. الگوریتم K-means ……………………………………………………………………………………………………………….. 121
شکل4-3. الگوریتم FCM …………………………………………………………………………………………………………………….. 121
شکل4-4. الگوریتم Median K-Flats …………………………………………………………………………………………………….. 122
شکل4-5. الگوریتم Gaussian Mixture …………………………………………………………………………………………………. 122
شکل4-6. الگوریتم خوشه‌بندی Subtractive …………………………………………………………………………………………… 122
شکل4-7. الگوریتم پیوندی منفرد با استفاده از معیار فاصله اقلیدسی …………………………………………………………… 123
شکل4-8. الگوریتم پیوندی منفرد با استفاده از معیار فاصله Hamming ………………………………………………………. 123
شکل4-9. الگوریتم پیوندی منفرد با استفاده از معیار فاصله Cosine …………………………………………………………… 123
شکل4-10. الگوریتم پیوندی کامل با استفاده از معیار فاصله اقلیدسی …………………………………………………………. 124
شکل4-1?. الگوریتم پیوندی کامل با استفاده از معیار فاصله Hamming …………………………………………………….. 124
شکل4-1?. الگوریتم پیوندی کامل با استفاده از معیار فاصله Cosine ………………………………………………………….. 124
شکل4-1?. الگوریتم پیوندی میانگین با استفاده از معیار فاصله اقلیدسی ……………………………………………………… 124
شکل4-14. الگوریتم پیوندی میانگین با استفاده از معیار فاصله Hamming …………………………………………………. 125
شکل4-15. الگوریتم پیوندی میانگین با استفاده از معیار فاصله Cosine ……………………………………………………… 125
شکل4-16. الگوریتم پیوندی بخشی با استفاده از معیار فاصله اقلیدسی ………………………………………………………. 125
شکل4-17. الگوریتم پیوندی بخشی با استفاده از معیار فاصله Hamming …………………………………………………… 125
شکل4-18. الگوریتم پیوندی بخشی با استفاده از معیار فاصله Cosine ……………………………………………………….. 126
شکل4-19. طیفـی با استفاده از ماتریس شباهت نامتراکم ………………………………………………………………………….. 126
شکل4-20. طیفـی با استفاده از روش نیستروم با متعادل ساز …………………………………………………………………… 127
شکل4-21. طیفـی با استفاده از روش نیستروم بدون متعادل ساز ………………………………………………………………. 127
شکل4-22. نرم‌افزار تحلیل‌گر کد استقلال الگوریتم ………………………………………………………………………………….. 128
شکل4-23. ماتریس AIDM ………………………………………………………………………………………………………………….. 129
شکل4-24. میانگین دقت الگوریتم‌های خوشه‌بندی ………………………………………………………………………………….. 131
شکل4-25. رابطه میان آستانه استقلال و زمان اجرای الگوریتم در روش پیشنهادی اول …………………………………. 133
شکل4-26. رابطه میان آستانه پراکندگی و زمان اجرای الگوریتم در روش پیشنهادی اول ………………………………. 133
شکل4-27. رابطه میان آستانه استقلال و دقت نتیجه نهایی در روش پیشنهادی اول ………………………………………. 134
شکل4-28. رابطه میان آستانه پراکندگی و دقت نتیجه نهایی در روش پیشنهادی اول …………………………………….. 134
شکل4-29. رابطه میان آستانه عدم تمرکز و دقت نتیجه نهایی در روش پیشنهادی اول ………………………………….. 135
شکل4-30. رابطه میان آستانه پراکندگی و زمان اجرای الگوریتم در روش پیشنهادی دوم ………………………………. 135
شکل4-31. رابطه میان آستانه پراکندگی و دقت نتایج نهایی در روش پیشنهادی دوم …………………………………….. 136
شکل4-32. رابطه میان آستانه عدم تمرکز و دقت نتایج نهایی در روش پیشنهادی دوم ………………………………….. 137
شکل4-33. مقایسه زمان اجرای الگوریتم‌ ………………………………………………………………………………………………… 138
فصل اول
مقدمه
1. مقدمه
1-1. خوشه‌بندی
به عنوان یکی از شاخه‌های وسیع و پرکاربرد هوش مصنوعی1، یادگیری ماشین2 به تنظیم و اکتشاف شیوه‌ها و الگوریتم‌هایی می‌پردازد که بر اساس آن‌ها رایانه‌ها و سامانه‌های اطلاعاتی توانایی تعلم و یادگیری پیدا می‌کنند. طیف پژوهش‌هایی که در مورد یادگیری ماشینی صورت می‌گیرد گسترده ‌است. در سوی نظر‌ی آن پژوهش‌گران بر آن‌اند که روش‌های یادگیری تازه‌ای به وجود بیاورند و امکان‌پذیری و کیفیت یادگیری را برای روش‌هایشان مطالعه کنند و در سوی دیگر عده‌ای از پژوهش‌گران سعی می‌کنند روش‌های یادگیری ماشینی را بر مسائل تازه‌ای اعمال کنند. البته این طیف گسسته نیست و پژوهش‌های انجام‌شده دارای مؤلفه‌هایی از هر دو رو‌یکرد هستند. امروزه، داده‌کاوی3 به عنوان یک ابزار قوی برای تولید اطلاعات و دانش از داده‌های خام، در یادگیری ماشین شناخته‌شده و همچنان با سرعت در حال رشد و تکامل است. به طور کلی می‌توان تکنیک‌های داده‌کاوی را به دو دسته بانظارت4 و بدون نظارت5 تقسیم کرد [29, 46].
در روش بانظارت ما ورودی (داده یادگیری6) و خروجی (کلاس7 داده) یک مجموعه داده را به الگوریتم هوشمند می‌دهیم تا آن الگوی8 بین ورودی و خروجی را تشخیص دهد در این روش خروجی کار ما مدلی9 است که می‌تواند برای ورودی‌های جدید خروجی درست را پیش‌بینی10 کند. روش‌های طبقه‌بندی11 و قوانین انجمنی12 از این جمله تکنیک‌ها می‌باشد. روش‌های با نظارت کاربرد فراوانی دارند اما مشکل عمده این روش‌ها این است که همواره باید داده‌ای برای یادگیری وجود داشته باشد که در آن به ازای ورودی مشخص خروجی درست آن مشخص شده باشد. حال آنکه اگر در زمینه‌ای خاص داده‌ای با این فرمت وجود نداشته باشد این روش‌ها قادر به حل این‌گونه مسائل نخواهند بود [29, 68]. در روش بدون نظارت برخلاف یادگیری بانظارت هدف ارتباط ورودی و خروجی نیست، بلکه تنها دسته‌بندی ورودی‌ها است. این نوع یادگیری بسیار مهم است چون خیلی از مسائل (همانند دنیای ربات‌ها) پر از ورودی‌هایی است که هیچ برچسبی13 (کلاس) به آن‌ها اختصاص داده نشده است اما به وضوح جزئی از یک دسته هستند [46, 68]. خوشه‌بندی14 شاخص‌ترین روش در داده‌کاوی جهت حل مسائل به صورت بدون ناظر است. ایده اصلی خوشه‌بندی اطلاعات، جدا کردن نمونه‌ها از یکدیگر و قرار دادن آن‌ها در گروه‌های شبیه به هم می‌باشد. به این معنی که نمونه‌های شبیه به هم باید در یک گروه قرار بگیرند و با نمونه‌های گروه‌های دیگر حداکثر متفاوت را دارا باشند [20, 26]. دلایل اصلی برای اهمیت خوشه‌بندی عبارت‌اند از:
اول، جمع‌آوری و برچسب‌گذاری یک مجموعه بزرگ از الگوهای نمونه می‌تواند بسیار پرکاربرد و باارزش باشد.
دوم، می‌توانیم از روش‌های خوشه‌بندی برای پیدا کردن و استخراج ویژگی‌ها15 و الگوهای جدید استفاده کنیم. این کار می‌تواند کمک به سزایی در کشف دانش ضمنی16 داده‌ها انجام دهد.
سوم، با خوشه‌بندی می‌توانیم یک دید و بینشی از طبیعت و ساختار داده به دست آوریم که این می‌تواند برای ما باارزش باشد.
چهارم، خوشه‌بندی می‌تواند منجر به کشف زیر رده‌های17 مجزا یا شباهت‌های بین الگوها ممکن شود که به طور چشمگیری در روش طراحی طبقه‌بندی قابل استفاده باشد.
1-2. خوشه‌بندی ترکیبی
هر یک از الگوریتم‌های خوشه‌بندی، با توجه به اینکه بر روی جنبه‌های متفاوتی از داده‌ها تاکید می‌کند، داده‌ها را به صورت‌های متفاوتی خوشه‌بندی می‌نماید. به همین دلیل، نیازمند روش‌هایی هستیم که بتواند با استفاده از ترکیب این الگوریتم‌ها و گرفتن نقاط قوت هر یک، نتایج بهینه‌تری را تولید کند. در واقع هدف اصلی خوشه‌بندی ترکیبی18 جستجوی بهترین خوشه‌ها با استفاده از ترکیب نتایج الگوریتم‌های دیگر است [1, 8, 9, 54, 56]. به روشی از خوشه‌بندی ترکیبی که زیرمجموعه‌ی منتخب از نتایج اولیه برای ترکیب و ساخت نتایج نهایی استفاده می‌شود خوشه‌بندی ترکیبی مبتنی بر انتخاب19 زیرمجموعه نتایج اولیه می‌گویند. در این روش‌ها بر اساس معیاری توافقی مجموعه‌ای از مطلوب‌ترین نتایج اولیه را انتخاب کرده و فقط توسط آن‌ها نتیجه نهایی را ایجاد می‌کنیم [21]. معیارهای مختلفی جهت انتخاب مطلوب‌ترین روش پیشنهاد شده است که معیار اطلاعات متقابل نرمال شده20، روش ماکزیموم21 و 22APMM برخی از آن‌ها می‌باشند [8, 9, 21, 67]. دو مرحله مهم در خوشه‌بندی ترکیبی عبارت‌اند از:
اول، الگوریتم‌های ابتدایی خوشه‌بندی که خوشه‌بندی اولیه را انجام می‌دهد.
دوم، جمع‌بندی نتایج این الگوریتم‌های اولیه (پایه) برای به دست آوردن نتیجه نهایی.
1-3. خرد جمعی
نظریه خرد جمعی23 که اولین بار توسط سورویکی24 در سال 2004 در کتابی با همان عنوان منتشر شد، استنباطی از مسائل مطرح‌شده توسط گالتون25 و کندورست26 می‌باشد، و نشان می‌دهد که قضاوت‌های جمعی و دموکراتیک از اعتبار بیشتری نسبت به آنچه که ما انتظار داشتیم برخوردار است، ما تأثیرات این ایده را در حل مسائل سیاسی، اجتماعی در طی سال‌های اخیر شاهد هستیم. در ادبیات خرد جمعی هر جامعه‌ای را خردمند نمی‌گویند. از دیدگاه سورویکی خردمند بودن جامعه در شرایط چهارگانه پراکندگی27، استقلال28، عدم تمرکز29 و روش ترکیب مناسب30 است [55].
1-4. خوشه‌بندی مبتنی بر انتخاب بر اساس نظریه خرد جمعی
هدف از این تحقیق استفاده از نظریه خرد جمعی برای انتخاب زیرمجموعه‌ی مناسب در خوشه‌بندی ترکیبی می‌باشد. تعاریف سورویکی از خرد جمعی مطابق با مسائل اجتماعی است و در تعاریف آن عناصر سازنده تصمیمات رأی افراد می‌باشد. در این تحقیق ابتدا مبتنی بر تعاریف پایه سورویکی از خرد جمعی و ادبیات مطرح در خوشه‌بندی ترکیبی، تعریف پایه‌ای از ادبیات خرد جمعی در خوشه‌بندی ترکیبی ارائه می‌دهیم و بر اساس آن الگوریتم پیشنهادی خود را در جهت پیاده‌سازی خوشه‌بندی ترکیبی ارائه می‌دهیم [55]. شرایط چهارگانه خوشه‌بندی خردمند که متناسب با تعاریف سورویکی باز تعریف شده است به شرح زیر می‌باشد:
پراکندگی نتایج اولیه، هر الگوریتم خوشه‌بندی پایه باید به طور جداگانه و بدون واسطه به داده‌های مسئله دسترسی داشته و آن را تحلیل و خوشه‌بندی کند حتی اگر نتایج آن غلط باشد.
استقلال الگوریتم، روش تحلیل هر یک از خوشه‌بندی‌های پایه نباید تحت تأثیر روش‌های سایر خوشه‌بندی‌های پایه تعیین شود، این تأثیر می‌تواند در سطح نوع الگوریتم (گروه) یا پارامترهای اساسی یک الگوریتم خاص (افراد) باشد.
عدم تمرکز، ارتباط بین بخش‌های مختلف خوشه‌بندی خرد جمعی باید به گونه‌ای باشد تا بر روی عملکرد خوشه‌بندی پایه تأثیری ایجاد نکند تا از این طریق هر خوشه‌بندی پایه شانس این را داشته باشد تا با شخصی سازی و بر اساس دانش محلی خود بهترین نتیجه ممکن را آشکار سازد.
مکانیزم ترکیب مناسب، باید مکانیزمی وجود داشته باشد که بتوان توسط آن نتایج اولیه الگوریتم‌های پایه را با یکدیگر ترکیب کرده و به یک نتیجه نهایی (نظر جمعی) رسید.
در این تحقیق دو روش برای ترکیب خوشه‌بندی ترکیبی و خرد جمعی پیشنهاد شده است. با استفاده از تعاریف بالا الگوریتم روش اول مطرح خواهد شد که در آن، جهت رسیدن به نتیجه نهایی از آستانه‌گیری استفاده می‌شود. در این روش الگوریتم‌های خوشه‌بندی اولیه غیر هم نام کاملاً مستقل فرض خواهند شد و برای ارزیابی استقلال الگوریتم‌های هم نام نیاز به آستانه‌گیری می‌باشد. در روش دوم، سعی شده است تا دو بخش از روش اول بهبود یابد. از این روی جهت مدل‌سازی الگوریتم‌ها و ارزیابی استقلال آن‌ها نسبت به هم یک روش مبتنی بر گراف شبه کد ارائه می‌شود و میزان استقلال به دست آمده در این روش به عنوان وزنی برای ارزیابی پراکندگی در تشکیل جواب نهایی مورد استفاده قرار می‌گیرد. جهت ارزیابی، روش‌های پیشنهادی با روش‌های پایه، روش‌ ترکیب کامل و چند روش معروف ترکیب مبتنی بر انتخاب مقایسه خواهد شد. از این روی از چهارده داده استاندارد و یا مصنوعی که عموماً از سایت UCI [76] جمع‌آوری شده‌اند استفاده شده است. در انتخاب این داده‌ها سعی شده، داده‌هایی با مقیاس‌ کوچک، متوسط و بزرگ انتخاب شوند تا کارایی روش بدون در نظر گرفتن مقیاس داده ارزیابی شود. همچنین جهت اطمینان از صحت نتایج تمامی آزمایش‌های تجربی گزارش‌شده حداقل ده بار تکرار شده است.
1-4-1- فرضیات تحقیق
این تحقیق بر اساس فرضیات زیر اقدام به ارائه روشی جدید در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر اساس نظریه خرد جمعی می‌کند.
? ) در این تحقیق تمامی آستانه‌گیری‌ها بر اساس میزان صحت نتایج نهایی و مدت زمان اجرای الگوریتم به صورت تجربی انتخاب می‌شوند.
? ) در این تحقیق جهت ارزیابی عملکرد یک الگوریتم، نتایج اجرای آن را بر روی‌داده‌های استاندارد UCI در محیطی با شرایط و پارامترهای مشابه نسبت به سایر الگوریتم‌ها ارزیابی می‌کنیم که این داده‌ها الزاماً حجیم یا خیلی کوچک نیستند.
? ) جهت اطمینان از صحت نتایج آزمایش‌ها ارائه‌شده در این تحقیق، حداقل اجرای هر الگوریتم بر روی هر داده ده بار تکرار شده و نتیجه‌ی نهایی میانگین نتایج به دست آمده می‌باشد.
4 ) از آنجایی که روش مطرح‌شده در این تحقیق یک روش مکاشفه‌ای است سعی خواهد شد بیشتر با روش‌های مکاشفه‌ای مطرح در خوشه‌بندی ترکیبی مقایسه و نتایج آن مورد بررسی قرار گیرد.
در این فصل اهداف، مفاهیم و چالش‌های این تحقیق به صورت خلاصه ارائه شد. در ادامه این تحقیق، در فصل دوم، الگوریتم‌های خوشه‌بندی پایه و روش‌های خوشه‌بندی‌ ترکیبی مورد بررسی قرار می‌گیرد. همچنین به مرور روش‌های انتخاب خوشه31 و یا افراز32 در خوشه‌بندی ترکیبی مبتنی بر انتخاب خواهیم پرداخت. در فصل سوم، نظریه خرد جمعی و دو روش پیشنهادی خوشه‌بندی خردمند ارائه می‌شود. در فصل چهارم، به ارائه نتایج آزمایش‌های تجربی این تحقیق و ارزیابی آن‌ها می‌پردازیم و در فصل پنجم، به ارائه‌ی نتایج و کار‌های آتی خواهیم پرداخت.
فصل دوم
مروری بر ادبیات تحقیق
2. مروری بر ادبیات تحقیق
2-1. مقدمه
در این بخش، کارهای انجام‌شده در خوشه‌بندی و خوشه‌بندی ترکیبی را مورد مطالعه قرار می‌دهیم. ابتدا چند الگوریتم‌ پایه خوشه‌بندی معروف را معرفی خواهیم کرد. سپس چند روش کاربردی جهت ارزیابی خوشه، خوشه‌بندی و افرازبندی را مورد مطالعه قرار می‌دهیم. در ادامه به بررسی ادبیات خوشه‌بندی ترکیبی خواهیم پرداخت و روش‌های ترکیب متداول را بررسی خواهیم کرد. از روش‌های خوشه‌بندی ترکیبی، روش ترکیب کامل و چند روش معروف مبتنی بر انتخاب را به صورت مفصل شرح خواهیم داد.
2-2. خوشه‌بندی
در این بخش ابتدا انواع الگوریتم‌های خوشه‌بندی پایه را معرفی می‌کنیم و سپس برخی از آن‌ها را مورد مطالعه قرار می‌دهیم سپس برای ارزیابی نتایج به دست آمده چند متریک معرفی خواهیم کرد.
2-2-1. الگوریتم‌های خوشه‌بندی پایه
به طور کلی، الگوریتم‌های خوشه‌بندی را می‌توان به دو دسته کلی تقسیم کرد:
1- الگوریتم‌های سلسله مراتبی33
2- الگوریتم‌های افرازبندی34
الگوریتم‌های سلسله مراتبی، یک روال برای تبدیل یک ماتریس مجاورت به یک دنباله از افرازهای تو در تو، به صورت یک درخت است. در این روش‌ها، مستقیماً با داده‌ها سروکار داریم و از روابط بین آن‌ها برای به دست آوردن خوشه‌ها استفاده می‌کنیم. یکی از ویژگی‌های این روش قابلیت تعیین تعداد خوشه‌ها به صورت بهینه می‌باشد. در نقطه مقابل الگوریتم‌های سلسله مراتبی، الگوریتم‌های افرازبندی قرار دارند. هدف این الگوریتم‌ها، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. در این فصل تعدادی از متداول‌ترین الگوریتم‌های خوشه‌بندی، در دو دسته سلسله مراتبی و افرازبندی، مورد بررسی قرار می‌گیرند. از روش سلسله‌ مراتبی چهار الگوریتم‌ از سری الگوریتم‌های پیوندی35 را مورد بررسی قرار می‌دهیم. و از الگوریتم‌های افرازبندی K-means، FCM و الگوریتم طیفی را مورد بررسی خواهیم داد.
2-2-1-1. الگوریتم‌های سلسله مراتبی
همان‌گونه که در شکل 2-1 مشاهده می‌شود، روال الگوریتم‌های خوشه‌بندی سلسله مراتبی را می‌تواند به صورت یک دندوگرام36 نمایش داد. این نوع نمایش تصویری از خوشه‌بندی سلسله مراتبی، برای انسان، بیشتر از یک لیست از نمادها قابل‌درک است. در واقع دندوگرام، یک نوع خاص از ساختار درخت است که یک تصویر قابل‌فهم از خوشه‌بندی سلسله مراتبی را ارائه می‌کند. هر دندوگرام شامل چند لایه از گره‌هاست، به طوری که هر لایه یک خوشه را نمایش می‌دهد. خطوط متصل‌کننده گره‌ها، بیانگر خوشه‌هایی هستند که به صورت آشیانه‌ای37 داخل یکدیگر قرار دارند. برش افقی یک دندوگرام، یک خوشه‌بندی را تولید می‌کند [33]. شکل 2-1 یک مثال ساده از خوشه‌بندی و دندوگرام مربوطه را نشان می‌دهد.
شکل 2-1. یک خوشه‌بندی سلسله مراتبی و درخت متناظر
اگر الگوریتم‌های خوشه‌بندی سلسله مراتبی، دندوگرام را به صورت پایین به بالا بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تراکمی38 نامیده می‌شوند. همچنین، اگر آن‌ها دندوگرام را به صورت بالا به پایین بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تقسیم‌کننده39 نامیده می‌شوند [26]. مهم‌ترین روش‌های خوشه‌بندی سلسله مراتبی الگوریتم‌های سری پیوندی می‌باشد که در این بخش تعدادی از کاراترین آن‌ها مورد بررسی قرار خواهند گرفت که عبارت‌اند از:
1- الگوریتم پیوندی منفرد40
2- الگوریتم پیوندی کامل41
3- الگوریتم پیوندی میانگین42
4- الگوریتم پیوندی بخشی43
2-2-1-1-1. تعاریف و نماد‌ها
شکل 2-2. ماتریس مجاورت
قبل از معرفی این الگوریتم‌ها، در ابتدا نمادها و نحوه نمایش مسئله نمایش داده خواهد شد. فرض کنید که یک ماتریس مجاورت متقارن داریم. وارده در هر سمت قطر اصلی قرار دارد که شامل یک جای گشت اعداد صحیح بین 1 تا است. ما مجاورت‌ها را عدم شباهت در نظر می‌گیریم. به این معنی است که اشیاء 1 و 3 بیشتر از اشیاء 1 و 2 به هم شبیه‌اند. یک مثال از ماتریس مجاورت معمول برای است که در شکل 2-2 نشان داده شده است. یک گراف آستانه44، یک گراف غیر جهت‌دار و غیر وزن‌دار، روی گره، بدون حلقه بازگشت به خود45 یا چند لبه است. هر نود یک شیء را نمایش می‌دهد. یک گراف آستانه برای هر سطح عدم شباهت به این صورت تعریف می‌شود: اگر عدم شباهت اشیاء و از حد آستانه کوچک‌تر باشد، با واردکردن یک لبه بین نودهای ویک گراف آستانه تعریف می‌کنیم.
(2-1)if and only if
شکل 2-3 یک رابطه دودویی به دست آمده از ماتریس مربوط به شکل 2-2 را برای مقدار آستانه 5 نشان می‌دهد. نماد “*” در موقعیت ماتریس، نشان می‌دهد که جفت متعلق به رابطه دودویی می‌باشد. شکل 2-4، گراف‌های آستانه برای ماتریس را نمایش می‌دهد.
شکل 2-3. رابطه دودویی و گراف آستانه برای مقدار آستانه 5.
شکل 2-4. گراف‌های آستانه برای ماتریس
2-2-1-1-2. الگوریتم پیوندی منفرد
این الگوریتم روش کمینه و روش نزدیک‌ترین همسایه نیز نامیده می‌شود [26]. اگر و خوشه‌ها باشند، در روش پیوندی منفرد، فاصله آن‌ها برابر خواهد بود با:
(2-2)
که نشان‌دهنده فاصله (عدم شباهت) بین نقاط a و b در ماتریس مجاورت است. شکل 2-5 این الگوریتم را نمایش می‌دهد. شکل 2-6 دندوگرام حاصل از روش پیوندی منفرد را برای ماتریس ، را نشان می‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If the number of comonents (maximally connected subgraphs) in, is less than the number of clusters in the current clustering, redefiene the current clustering by naming each component of as a cluster.
Step 3. If consists of a single connected graph, stop. Else, setand go to step 2.شکل 2-5. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی منفرد
شکل 2-6. دندوگرام پیوندی منفرد برای ماتریس
2-2-1-1-3. الگوریتم پیوندی کامل
این الگوریتم روش بیشینه یا روش دورترین همسایه نیز نامیده می‌شود. الگوریتم پیوندی کامل می‌گوید که وقتی دو خوشه و شبیه به هم هستند که بیشینه روی تمام ها در و کوچک باشد. به عبارت دیگر، در این الگوریتم، برای یکی کردن دو خوشه، همه جفت‌ها در دو خوشه باید شبیه به هم باشند [26]. اگر و خوشه‌ها باشند، در روش پیوندی کامل، فاصله آن‌ها برابر خواهد بود با:
(2-3)
که نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و در ماتریس مجاورت است. شکل 2-7 این الگوریتم و شکل 2-8 دندوگرام حاصل از این روش را برای ماتریس ، را نشان می‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If two of the current clusters from a clique (maximally complete sub graph) in, redefine the current clustering by merging these two clusters into a single cluster.
Step 3. If, so that is the complete graph on the nodes, stop. Else, set and go to step 2.شکل 2-7. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی کامل
شکل 2-8. دندوگرام پیوندی کامل برای ماتریس
2-2-1-1-4. الگوریتم پیوندی میانگین
الگوریتم پیوندی منفرد اجازه می‌دهد تا خوشه‌ها به صورت دراز و نازک رشد کنند. این در شرایطی است که الگوریتم پیوندی کامل خوشه‌های فشرده‌تری تولید می‌کند. هر دو الگوریتم مستعد خطا با داده‌های خارج از محدوده46 هستند. الگوریتم خوشه‌بندی پیوندی میانگین، یک تعادلی بین مقادیر حدی الگوریتم‌های پیوندی منفرد و کامل است. الگوریتم پیوندی میانگین همچنین، روش جفت-گروه بدون وزن با استفاده از میانگین حسابی47 نامیده می‌شود. این الگوریتم، یکی از پرکاربردترین الگوریتم‌های خوشه‌بندی سلسله مراتبی می‌باشد [26]. اگر یک خوشه با تعداد تا عضو، و یک خوشه دیگر با تعداد تا عضو باشند، در روش پیوندی میانگین، فاصله آن‌ها برابر خواهد بود با:
(2-4)
که نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و در ماتریس مجاورت است.
2-2-1-1-5. الگوریتم پیوندی بخشی
روش پیوندی بخشی که از مربع مجموع خطا‌های (SSE) خوشه‌های یک افراز برای ارزیابی استفاده می‌کند، یکی دیگر از روش‌های سلسله مراتبی می‌باشد [60]. اگر یک خوشه با تعداد تا عضو، و یک خوشه دیگر با تعداد تا عضو باشند و نماد به معنای فاصله اقلیدسی و و مراکز خوشه‌های و باشد آنگاه در روش پیوندی بخشی، فاصله آن‌ها برابر خواهد بود با:
(2-5)
2-2-1-2. الگوریتم‌های افرازبندی
یک خاصیت مهم روش‌های خوشه‌بندی سلسله مراتبی، قابلیت نمایش دندوگرام است که تحلیل‌گر را قادر می‌سازد تا ببیند که چگونه اشیاء در سطوح متوالی مجاورت، در خوشه‌ها به هم پیوند می‌خورند یا تفکیک می‌شوند. همان طور که اشاره شد، هدف الگوریتم‌های افرازبندی، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. آن‌ها یک افراز منفرد از داده را تولید می‌کنند و سعی می‌کنند تا گروه‌های طبیعی حاضر در داده را کشف کنند. هر دو رویکرد خوشه‌بندی، دامنه‌های مناسب کاربرد خودشان را دارند. معمولاً روش‌های خوشه‌بندی سلسله مراتبی، نیاز به ماتریس مجاورت بین اشیاء دارند؛ درحالی‌که روش‌های افرازبندی، به داده‌ها در قالب ماتریس الگو نیاز دارند. نمایش رسمی مسئله خوشه‌بندی افرازبندی می‌تواند به صورت زیر باشد:
تعیین یک افراز از الگوها در گروه، یا خوشه، با داشتن الگو در یک فضای d-بعدی؛ به طوری که الگوها در یک خوشه بیش‌ترین شباهت را به هم داشته و با الگوهای خوشه‌های دیگر بیش‌ترین، تفاوت را داشته باشند. تعداد خوشه‌ها،، ممکن است که از قبل مشخص‌شده نباشد، اما در بسیاری از الگوریتم‌های خوشه‌بندی افرازبندی، تعداد خوشه‌ها باید از قبل معلوم باشند. در ادامه برخی از معروف‌ترین و پرکاربردترین الگوریتم‌های افرازبندی مورد بررسی قرار خواهند گرفت.
2-2-1-2-1. الگوریتم K-means
در الگوریتم مراکز خوشه‌ها بلافاصله بعد از اینکه یک نمونه به یک خوشه می‌پیوندد محاسبه می‌شوند. به طور معمول بیشتر روش‌های خوشه‌بندی ترکیبی از الگوریتم جهت خوشه‌بندی اولیه خود استفاده می‌کنند [37, 47, 57]. اما مطالعات اخیر نشان داده‌اند که با توجه به رفتار هر مجموعه داده، گاهی اوقات یک روش خوشه‌بندی خاص پیدا می‌شود که دقت بهتری از برای بعضی از مجموعه داده‌ها می‌دهد [1, 54]. اما الگوریتم به دلیل سادگی و توانایی مناسب در خوشه‌بندی همواره به عنوان انتخاب اول مطالعات خوشه‌بندی ترکیبی مورد مطالعه قرار گرفته است. در شکل 2-10 شبه کد الگوریتم را مشاهده می‌کنید:
1. Place K points into the space represented by the objects that are being clustered.
These points represent initial group centroids.
2. Assign each object to the group that has the closest centroid.
3. When all objects have been assigned, recalculate the positions of the K centroids.
4. Repeat Steps 2 and 3 until the centroids no longer move. This produces a separation
of the objects into groups from which the metric to be minimized can be calculatedشکل 2-9. الگوریتم خوشه‌بندی افرازبندی
مقادیر مراکز اولیه‌ی‌ متفاوت برای الگوریتم می‌تواند منجر به خوشه‌بندی‌های مختلفی شود. به خاطر اینکه این الگوریتم مبتنی بر مربع خطا است، می‌تواند به کمینه محلی همگرا شود، مخصوصاً برای خوشه‌هایی که به طور خیلی خوبی از هم تفکیک نمی‌شوند، این امر صادق است. نشان داده شده است که هیچ تضمینی برای همگرایی یک الگوریتم تکراری به یک بهینه سراسری نیست [33]. به طور خلاصه می‌توان ویژگی‌های الگوریتم را به صورت زیر برشمرد:
1- بر اساس فاصله اقلیدسی تمامی ویژگی‌ها می‌باشد.
2- منجر به تولید خوشه‌هایی به صورت دایره، کره و یا ابر کره می‌شود.
3- نسبت به روش‌های دیگر خوشه‌بندی، ساده و سریع است.
4- همگرایی آن به یک بهینه محلی اثبات شده است، اما تضمینی برای همگرایی به بهینه سراسری وجود ندارد.
5- نسبت به مقداردهی اولیه مراکز خوشه‌ها خیلی حساس است.


پاسخ دهید