1-8-2 روشهای سلسله مراتبی……………………………………………………………………..12

 

1-8-2-1 خوشه‌بندی با روش Single-Link…………………………………………………….14

 

1-8-2-2 خوشه‌بندی با روش Complete-Link……………………………………………….15

 

1-8-2-3 خوشه‌بندی با روش Average-Link…………………………………………………16

 

1-8-2-4 دیگر روشهای خوشه بندی سلسله مراتبی…………………………………..16

 

1-8-3 روش مبتنی برچگالی………………………………………………………………………..18

 

1-8-3-1 الگوریتم خوشه‌بندی براساس چگالی DBSCAN……………………………21

 

1-8-3-2 الگوریتم سلسله مراتبی خوشه‌بندی براساس چگالی OPTICS …….22

 

1-8-4 روشهای مبتنی بر شبکه های مشبک (Grid based)……………………………..23

 

1-8-5 روشهای مبتنی بر مدل………………………………………………………………………..23

 

1-8-6 روش های فازی………………………………………………………………………………..23

 

1-9 هدف خوشه بندی ……………………………………………………………………………………..23

 

1-10 اندازه­گیری کیفیت خوشه­بندی……………………………………………………………………25

 

1-11 بررسی تکنیکهای اندازه‌گیری اعتبار خوشه‌ها……………………………………………….25

 

1-12 شاخصهای اعتبارسنجی…………………………………………………………………………….27

 

1-12-1 شاخص دون (Dunn Index)……………………………………………………………28

 

1-12-2 شاخص دیویس بولدین (Davies Bouldin Index)…………………………….28

 

1-12-3 شاخص‌های  اعتبارسنجی ریشة میانگین مربع انحراف از معیار (RMSSDT) و ریشة R (RS)…………………………………………………………………………………………….30

 

1-12-4 شاخص اعتبار‌سنجی SD………………………………………………………………..31

 

1-12-5 شاخص اعتبارسنجی S_Dbw………………………………………………………..32

 

1-12-6 آزمایش ومقایسه کارایی شاخص‌های اعتبار سنجی……………………………..33

 

1-13 خوشه‌بندی ترکیبی………………………………………………………………………………….37

 

1-13-1 ایجاد پراکندگی در خوشه‌بندی ترکیبی……………………………………………..37

 

1-13-2 تابع توافقی ………………………………………………………………………………….39

 

1-13-3 مشکلات پیش روی خوشه‌بندی ترکیبی……………………………………………40

 

 

 

فصل دوم – ادبیات و پیشینه تحقیق                                                         42

 

2-1 مقدمه……………………………………………………………………………………………………..43

 

2-2 خوشه بندی فازی …………………………………………………………………………………..43

 

2-3 الگوریتم خوشه بندی c میانگین (Fuzzy c-mean)………………………………….45

 

2-4 الگوریتم PFCM………………………………………………………………………………………….49

 

 

2-5 الگوریتم AFCM………………………………………………………………………….51

 

 

2-6 الگوریتم FPCM…………………………………………………………………………..52

 

2-7 الگوریتم خوشه بندی c میانگین برای داده های نویزی………………………………..53

 

2-8 الگوریتم KFCM……………………………………………………………………………………54

 

2-9 توابع ارزیابی خوشه ………………………………………………………………………………56

 

2-9-1 تابع ارزیابی ضریب افراز……………………………………………………………….57

 

2-9-2 تابع ارزیابی آنتروپی افراز………………………………………………………………57

 

2-9-3 تابع Fukuyama and Sugeno………………………………………………………………..58

 

2-9-4 تابع  Beni Xie and ……………………………………………………………………………….59

 

2-9-5 تابع N.Zahid………………………………………………………………………………………….59

 

2-9-6  تابع M.Ramze Rezaee……………………………………………………………………….60

 

2-10 خوشه‌بندی ترکیبی……………………………………………………………………………62

 

 

 

فصل سوم – روش تحقیق                                                                 68

 

3-1 مقدمه ……………………………………………………………………………………………….69

 

3-2 فرضیات روش پیشنهادی……………………………………………………………………..70

 

3-3 شرح مفصلی از روش پیشنهادی……………………………………………………………72

 

3-4 شرح الگوریتم…………………………………………………………………………………….83

 

 

 

فصل چهارم – محاسبات و یافته های تحقیق                                          85

 

 

4-1 مقدمه……………………………………………………………………………………………….86

 

4-2 نتایج خوشه بندی به روش پیشنهادی…………………………………………………..86

 

4-3 مقایسه ای با الگوریتم های خوشه بندی پایه ………………………………………..87

 

4-4 مقایسه با روش های خوشه بندی ترکیبی …………………………………………….90

 

 

 

فصل پنجم – نتیجه گیری و پیشنهادات                                                    92

 

5-1 جمع بندی…………………………………………………………………………………………….93

 

5-2 پیشنهادات…………………………………………………………………………………………….95

 

 

 

پیوست                                                                                      96

 

منابع و مآخذ                                                                              100

 

 

 

 

 

فهرست جداول

 

ـــــــــــــــــــــــــــــــــــــــــ

 

عنوان                                                                                             صفحه

 

 

 

جدول 1-1: مجموعة علائم بکار رفته در این بخش…………………………………………………….27

 

جدول2-1 : معیارهای تشابه بر اساس توابع فاصله مختلف…………………………………………..49

 

جدول 4-1 میزان نرخ خطای روش های مختلف توسط مقایسه ی نتایج با برچسب حقیقی مجموعه داده های استاندارد Iris ، Wine و Glass………………………………………………………………………….91

 

 

 

 

 

 

 

 

 

فهرست تصاویر و نمودار

 

ـــــــــــــــــــــــــــــــــــــــــ

 

عنوان                                                                                             صفحه

 

 

 

شکل1-1 : نمونه‌ای از اعمال خوشه‌بندی با استفاده از معیار فاصله(Distance)……………………5

 

شکل1-2 : a) در طبقه‌بندی با استفاده یک سری اطلاعات اولیه داده‌ها به دسته‌های معلومی نسبت داده‌ می‌شوند. b) در خوشه‌بندی داده‌ها با توجه به الگوریتم انتخاب شده به خوشه‌هایی نسبت داده‌ می‌شوند ………………………………………………………………………………………………… 6

 

شکل1-3 : تفاوت بین روشهای بالا به پایین با روشهای پایین به بالا ……………………………..14

 

شکل1-4 :  شباهت بین دو خوشه در روش Single-Link برابر است با کمترین فاصلة بین داده‌های دو خوشه………………………………………………………………………………………………….. 15

 

شکل1-5 : شباهت بین دو خوشه در روش Complete-Link برابر است با بیشترین فاصلة بین داده‌های دو خوشه………………………………………………………………………………………………….. 15

 

شکل1-6 : شباهت بین دو خوشه در روش Average-Link برابر است با میانگین فاصلة بین داده‌های دو خوشه………………………………………………………………………………………………….. 16

 

شکل1-7 :  شباهت بین دو خوشه در روش Group Average Link برابر است با فاصله بین میانگین نقاط دو خوشه …………………………………………………………………………………………. 17

 

شکل1-8 : یک همسایگی برای P دارای چگالی نقاط 5……………………………………………….19

 

شکل 1-9 : p در دسترسِ مستقیمِ چگالیِ q قرار دارد…………………………………………………..20

 

شکل 1-10 : p در دسترسِ چگالیِ q قرار دارد……………………………………………………………20

 

شکل 1-11 : p متصلِ چگالیِ q است………………………………………………………………………..20

 

شکل1-12 : خوشه‌بندی بر اساس چگالی………………………………………………………………….21

 

شکل 1-13 : در روش سلسله مراتبی خوشه‌بندی براساس چگالی OPTICS از ترکیب خوشه‌های با چگالی زیاد و کوچک خوشه‌های بزرگتری حاصل می‌شود…………………………22

 

شکل1-14: مجموعه داده‌های بکار رفته برای مقایسة کارایی شاخص‌های اعتبارسنجی خوشه‌ها…………………………………………………………………………………………………………………34

 

شکل1-15 : مقادیر مربوط به شاخص‌های اعتبار بر روی نتایج حاصل از خوشه‌بندی داده‌ها کاملا مجزا ……………………………………………………………………………………………………………..34

 

شکل 1-16 : مقادیر مربوط به شاخص‌های اعتبار بر روی نتایج حاصل از خوشه‌بندی داده‌ها حلقوی…………………………………………………………………………………………………………………..35

 

شکل1-17 : دو حالت خوشه‌بندی درست و نادرست داده‌های با شکل دلخواه ……………….36

 

شکل 1-18 : مقادیر مربوط به شاخص‌های اعتبار بر روی نتایج حاصل از خوشه‌بندی داده‌ها با شکل دلخواه ……………………………………………………………………………………………………… 36

 

شکل1-19 طبقه بندی روشهای ایجاد پراکندگی در خوشه‌بندی ترکیبی………………………….39

 

شکل1-20 طبقه بندی توابع توافقی در خوشه بندی ترکیبی…………………………………………..40

 

شکل 2-1: مجموعه داده پروانه ای…………………………………………………………………………….45

 

شکل 2-2 : توزیع یک بعدی نمونه ها……………………………………………………………………….47

 

شکل 2-3 : خوشه بندی کلاسیک نمونه های ورودی………………………………………………….48

 

شکل2-4 : خوشه بندی فازی نمونه ها………………………………………………………………………48

 

شکل 3-1 فرایند کلی خوشه بندی ترکیبی فازی…………………………………………………………70

 

شکل 3-2 مجموعه داده فرضی………………………………………………………………………………..77

 

شکل 3-3 ماتریس های همبستگی فازی متناظر با ماتریس های عضویت مربوطه…………..79

 

شکل 3-4 ماتریس استحکام حاصل از ماتریس های همبستگی فازی مرحله 2………………80

 

شکل 3-5 ماتریس های استحکام حاصل از اجرای الگوریتم روش پیشنهادی در سه تکرار متوالی…………………………………………………………………………………………………………………..81

 

شکل 3-6 گراف متناظر با تکرار اول از الگوریتم پیشنهادی ………………………………………..81

 

شکل 3-7 گراف متناظر با تکرار دوم از الگوریتم پیشنهادی ………………………………………..82

 

شکل 3-8 گراف متناظر با تکرار سوم از الگوریتم پیشنهادی………………………………………..82

 

شکل4-1 نتیجه ی خوشه بندی به روش پیشنهادی a)نحوه توزیع خوشه ها تا رسیدن به تعداد خوشه تعیین شده b)نمایش داده ها و خوشه بندی نهایی ……………………………………87

 

شکل 4-2 اعمال الگوریتم kmeans بر روی مجموعه داده نمونه …………………………………..88

 

شکل 4-3 اعمال الگوریتم FCM بر روی مجموعه داده نمونه……………………………………….88

 

شکل 4-4  اعمال الگوریتم پیشنهادی بر روی مجموعه داده نمونه ……………………………….88

 

شکل 4-5  اعمال الگوریتم پیشنهادی بر روی مجموعه داده نمونه ی دیگر …………………..89

 

شکل 4-6مقایسه ای میان روش spectral و روش پیشنهادی a,b,c )خوشه بندی به روش spectral . d,e,f)خوشه بندی به روش پیشنهادی ……………………………………………………….90

 

 

 

مقدمه ای بر داده‌کاوی

 

 

 

در دو دهه قبل توانایی های فنی بشر در تولید و جمع آوری داده ها به سرعت افزایش یافته است . عواملی نظیر به خدمت­گرفتن کامپیوتر در کسب و کار، علوم ، خدمات دولتی و پیشرفت در وسائل جمع­آوری داده، از اسکن کردن متون و تصاویر تا سیستمهای سنجش از دور ماهواره ای، در این تغییرات نقش مهمی دارند. بطور کلی استفاده همگانی از وب و اینترنت به عنوان یک سیستم اطلاع رسانی جهانی ما را با حجم وحشتناکی ازداده و اطلاعات مواجه می‌کند. این رشد انفجاری در داده های ذخیره شده، نیاز مبرمی برای تکنولوژی های جدید و ابزارهای خودکاری ایجاد کرده که به صورت هوشمند به انسان یاری رسانند تا این حجم زیاد داده را به اطلاعات و دانش تبدیل کند.

 

داده کاوی به عنوان یک راه حل برای این مسائل مطرح می باشد. در یک تعریف غیر رسمی داده کاوی فرآیندی است، خودکار برای استخراج الگوهایی که دانش را بازنمایی می کنند، که این دانش به صورت ضمنی در پایگاه داده های عظیم، انباره داده و دیگر مخازن بزرگ اطلاعات، ذخیره شده است.