2-2-1. الگوریتم‌های خوشه‌بندی پایه 9

 

2-2-1-1. الگوریتم‌های سلسله مراتبی 10

 

2-2-1-1-1. تعاریف و نماد‌ها 11

 

2-2-1-1-2. الگوریتم پیوندی منفرد 13

 

2-2-1-1-3. الگوریتم پیوندی کامل 13

 

2-2-1-1-4. الگوریتم پیوندی میانگین 14

 

2-2-1-1-5. الگوریتم پیوندی بخشی 15

 

2-2-1-2. الگوریتم‌های افرازبندی 15

 

2-2-1-2-1. الگوریتم K-means 16

 

2-2-1-2-2. الگوریتم FCM 17

 

2-2-1-2-3. الگوریتم طیفی 19

 

2-2-1-2-3-1. الگوریتم برش نرمال 20

 

2-2-1-2-3-2.  الگوریتم NJW 21

 

2-2-1-2-4. الگوریتم خوشه‌بندی کاهشی 22

 

2-2-1-2-5. الگوریتم خوشه‌بندی Median K-Flat 23

 

2-2-1-2-6. الگوریتم خوشه‌بندی مخلوط گوسی 25

 

2-2-2. معیارهای ارزیابی 27

 

2-2-2-1. معیار SSE 28

 

2-2-2-2. معیار اطلاعات متقابل نرمال شده 30

 

2-2-2-3. معیار APMM 32

 

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. روش CSPA 46

 

2-۳-2-2-2. روش HGPA 47

 

2-۳-2-2-3. روش MCLA 48

 

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. راهكار ارزیابی خوشهی MAX 69

 

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