وزارت علوم، تحقیقات و فناوری

 

دانشگاه علوم و فنون مازندران

 

 

 

پایان نامه

 

مقطع كارشناسی ارشد

 

رشته : فناوری اطلاعات – مدیریت سیستم‌های اطلاعاتی

 

 

 

عنوان : خوشه‌بندی مبتنی بر انتخاب بر اساس نظریه خرد جمعی

 

استاد راهنما : جناب آقای دکتر بهروز مینایی

 

استاد مشاور : جناب آقای دکتر حسین علیزاده

 

 

 

تابستان 1392

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

چكیده

خوشه‌بندی وظیفه کاوش الگوهای پنهان در داده‌های بدون برچسب را بر عهده دارد. به خاطر پیچیدگی مسئله و ضعف روش‌های خوشه‌بندی پایه، امروزه روش‌های خوشه‌بندی ترکیبی مورد استفاده قرار می‌گیرند. به روشی از خوشه‌بندی ترکیبی که در آن از زیرمجموعه‌ای منتخب از نتایج اولیه برای ترکیب و ساخت نتیجه نهایی استفاده می‌شود خوشه‌بندی ترکیبی مبتنی بر انتخاب زیرمجموعه نتایج اولیه می‌گویند. در سال‌های اخیر تمرکز بر روی ارزیابی نتایج اولیه برای انتخاب خوشه در خوشه‌بندی ترکیبی مورد توجه محققین زیادی قرار گرفته است. اما پاسخ به بعضی از سؤالات در این زمینه همچنان با ابهامات زیادی روبروست. از طرفی دیگر، نظریه خرد جمعی که اولین بار توسط سورویکی منتشر شده است، نشان می‌دهد که قضاوت‌های جمعی و دموکراتیک از اعتبار بیشتری نسبت به آنچه که ما انتظار داشتیم برخوردار هستند. این نظریه چهار شرط پراکندگی، استقلال، عدم تمرکز و روش ترکیب مناسب آراء را برای هر جمعیت خردمند لازم و کافی می‌داند. هدف این تحقیق پیشنهاد فرآیندی جهت نگاشت و به‌کارگیری نظریه خرد جمعی در انتخاب زیرمجموعه مناسب در خوشه‌بندی ترکیبی مبتنی بر انتخاب می‌باشد. از این روی در این تحقیق ابتدا با استفاده از تعاریف مطرح‌شده در نظریه خرد جمعی باز تعریفی متناسب با خوشه‌بندی ترکیبی مبتنی بر انتخاب ارائه می‌شود و بر اساس آن دو روش برای ترکیب این دو مفهوم پیشنهاد می‌شود. در روش پیشنهادی اول الگوریتم‌های خوشه‌بندی اولیه غیر هم نام کاملاً مستقل فرض خواهند شد و برای ارزیابی استقلال الگوریتم‌های هم نام نیاز به آستانه‌گیری می‌باشد. در روش دوم، سعی شده است تا دو بخش از روش اول بهبود یابد. از این روی جهت مدل‌سازی الگوریتم‌ها و ارزیابی استقلال آن‌ها نسبت به هم یک روش مبتنی بر گراف کد الگوریتم ارائه می‌شود و میزان استقلال به دست آمده در این روش به عنوان وزنی برای ارزیابی پراکندگی در تشکیل جواب نهایی مورد استفاده قرار می‌گیرد. جهت بررسی ادعاهای این تحقیق در بخش ارزیابی دقت و اطلاعات متقابل نرمال شده‌ی روش‌های پیشنهادی بر روی داده‌ّهای استاندارد با روش‌های پایه، روش‌ ترکیب کامل و چند روش معروف خوشه‌بندی ترکیبی مبتنی بر انتخاب مقایسه می‌شوند که این مقایسه کاراریی بالای روش‌های پیشنهادی این تحقیق در اکثر موارد نسبت به سایر روش‌های مطرح شده را نشان می‌دهد. همچنین در بخش نتیجه‌گیری چندین روش توسعه جهت كارهای آتی‌ پیشنهاد می‌شود.

واژه‌های كلیدی: خوشه‌بندی ترکیبی، خرد جمعی، استقلال الگوریتم‌های خوشه‌بندی، پراکندگی نتایج خوشه‌بندی اولیه، عدم تمرکز در چهارچوب خوشه‌بندی ترکیبی

فهرست مطالب

فصل اول

1. مقدمه 2

1-1. خوشه‌بندی 2

1-2. خوشه‌بندی تركیبی 4

1-3. خرد جمعی 4

1-4. خوشه‌بندی مبتنی بر انتخاب بر اساس نظریه خرد جمعی 5

1-4-1- فرضیات تحقیق 6

فصل دوم

2. مروری بر ادبیات تحقیق 9

2-1. مقدمه 9

2-2. خوشه‌بندی 9

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