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