چكیده

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

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

فهرست مطالب

فصل اول

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

فصل سوم

شکل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]، یادگیری ماشین[2] به تنظیم و اکتشاف شیوه‌ها و الگوریتم‌هایی می‌پردازد که بر اساس آن‌ ها رایانه‌ها و سامانه‌های اطلاعاتی توانایی تعلم و یادگیری پیدا می‌کنند. طیف پژوهش‌هایی که در مورد یادگیری ماشینی صورت می‌گیرد گسترده ‌است. در سوی نظر‌ی آن پژوهش‌گران بر آن‌اند که روش‌های یادگیری تازه‌ای به وجود بیاورند و امکان‌پذیری و کیفیت یادگیری را برای روش‌هایشان مطالعه کنند و در سوی دیگر عده‌ای از پژوهش‌گران سعی می‌کنند روش‌های یادگیری ماشینی را بر مسائل تازه‌ای اعمال کنند. البته این طیف گسسته نیست و پژوهش‌های انجام‌شده دارای مؤلفه‌هایی از هر دو رو‌یكرد هستند. امروزه، داده‌كاوی[3] به عنوان یک ابزار قوی برای تولید اطلاعات و دانش از داده‌های خام، در یادگیری ماشین شناخته‌شده و همچنان با سرعت در حال رشد و تكامل است. به طور كلی می‌توان تکنیک‌های داده‌كاوی را به دو دسته بانظارت[4] و بدون نظارت[5] تقسیم كرد [29, 46].

در روش بانظارت ما ورودی (داده یادگیری[6]) و خروجی (كلاس[7] داده) یک مجموعه داده را به الگوریتم هوشمند می‌دهیم تا آن الگوی[8] بین ورودی و خروجی را تشخیص دهد در این روش خروجی كار ما مدلی[9] است كه می‌تواند برای ورودی‌های جدید خروجی درست را پیش‌بینی[10] كند. روش‌های طبقه‌بندی[11] و قوانین انجمنی[12] از این جمله تكنیك‌ها می‌باشد. روش‌های با نظارت كاربرد فراوانی دارند اما مشكل عمده این روش‌ها این است كه همواره باید داده‌ای برای یادگیری وجود داشته باشد كه در آن به ازای ورودی مشخص خروجی درست آن مشخص شده باشد. حال آنكه اگر در زمینه‌ای خاص داده‌ای با این فرمت وجود نداشته باشد این روش‌ها قادر به حل این‌گونه مسائل نخواهند بود [29, 68]. در روش بدون نظارت برخلاف یادگیری بانظارت هدف ارتباط ورودی و خروجی نیست، بلکه تنها دسته‌بندی ورودی‌ها است. این نوع یادگیری بسیار مهم است چون  خیلی از مسائل (همانند دنیای ربات‌ها) پر از ورودی‌هایی است که هیچ برچسبی[13] (كلاس) به آن‌ ها اختصاص داده نشده است اما به وضوح جزئی از یک دسته هستند [46, 68]. خوشه‌بندی[14] شاخص‌ترین روش در داده‌كاوی جهت حل مسائل به صورت بدون ناظر است. ایده اصلی خوشه‌بندی  اطلاعات، جدا کردن نمونه‌ها از یكدیگر و قرار دادن آن‌ ها در گروه‌های شبیه به هم می‌باشد. به این معنی كه نمونه‌های شبیه به هم باید در یک گروه قرار بگیرند و با نمونه‌های گروه‌های دیگر حداكثر متفاوت را دارا باشند [20, 26]. دلایل اصلی برای اهمیت خوشه‌بندی عبارت‌اند از:

اول، جمع‌ آوری و برچسب‌گذاری یک مجموعه بزرگ از الگوهای نمونه می‌تواند بسیار پركاربرد و باارزش باشد.