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
فصل سوم
- روش تحقیق 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
فصل چهارم
- پیاده سازی و تحلیل نتایج 116
4-1. مقدمه 116
4-2. مجموعه داده 116
4-3. مدل سازی الگوریتم ها به زبان استقلال الگوریتم 118
4-4. ابزار تحلیلگر کد استقلال الگوریتم 128
4-5. نتایج آزمایش ها 130
فصل پنجم
- جمع بندی و کار های آینده 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
[چهارشنبه 1399-10-17] [ 07:31:00 ق.ظ ]
|