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

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

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

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

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

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

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

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)………………………………….

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

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

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

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

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

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

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

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

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

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

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

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

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

چکیده:

خوشه بندی فازی و ترکیبی از موضوعات قابل توجه در داده کاوی محسوب می شوند .اگر چه در سالهای اخیر الگوریتم های خوشه بندی فازی به سرعت در حال رشد هستند ،اما تکنیک های خوشه بندی ترکیبی فازی رشد چندانی نکرده اند و اکثر آنها از طریق تبدیل توابع ترکیب به نسخه فازی تبدیل شده اند .در این پایان نامه یک الگوریتم خوشه بندی فازی مبتنی بر گراف ارائه شده است. رویکرد پیشنهادی از ماتریس های عضویت حاصل از افراز های فازی که از الگوریتم های مختلف فازی نتیجه شده ،بهره گرفته است و سپس ماتریس های همبستگی فازی را برای هر الگوریتم ایجاد می کند که هریک از عناصر آن بیانگر میزان همبستگی و اشتراک بین نمونه ها ی متناظر می باشد. سرانجام همه­ی این ماتریس ها در ماتریس استحکام ترکیب شده ودر نهایت نتیجه ی نهایی توسط فرایند کاهشی تکراری مبتنی بر گراف بدست می آید .تکرارهای این الگوریتم تا زمانیکه به تعداد خوشه ی تعیین شده در ابتدای فرایند دست یابیم ادامه می یابد.همچنین تعدادی مجموعه داده ی فرضی و مجموعه داده استاندارد Iris به منظور ارزیابی روش پیشنهادی استفاده شده است .رویکرد پیشنهادی نشان داد که نسبت به الگوریتم های پایه همچون Kmeans ،FCM وSpectral کاراتر بوده و در مقایسه با روشهای خوشه بندی ترکیبی مختلف، رویکرد پیشنهادی حاوی نتایج قابل اطمینان و نرخ خطای کمتری است.

فصل اول: مقدمه و کلیات تحقیق

1-1- مقدمه ای بر داده کاوی

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

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

داده کاوی، پایگاه ها و مجموعه های حجیم داده ها را در پی کشف واستخراج دانش، مورد تحلیل و کند و کاوهای ماشینی (و نیمه ماشینی) قرار می دهد. این گونه مطالعات و کاوش ها را به واقع می توان همان امتداد و استمرار دانش کهن و همه جا گیر آمار دانست. تفاوت عمده در مقیاس، وسعت و گوناگونی زمینه ها و کاربردها، و نیز ابعاد و اندازه های داده های امروزین است که شیوه های ماشینی مربوط به یادگیری، مدل سازی، و آموزش را طلب می نماید. [4]

اصلی ترین دلیلی که باعث شد داده کاوی کانون توجهات در صنعت اطلاعات قرار بگیرد، مساله در دسترس بودن حجم وسیعی از داده ها و نیاز شدید به اینکه از این داده ها اطلاعات و دانش سودمند استخراج کنیم. اطلاعات و دانش بدست آمده در کاربردهای وسیعی از مدیریت کسب و کار وکنترل تولید و تحلیل بازار تا طراحی مهندسی و تحقیقات علمی مورد استفاده قرار می گیرد.

داده کاوی را می توان حاصل سیر تکاملی طبیعی تکنولوژی اطلاعات دانست، که این سیر تکاملی ناشی از یک سیر تکاملی در صنعت پایگاه داده می باشد، نظیر عملیات: جمع آوری داده ها وایجاد پایگاه داده، مدیریت داده و تحلیل و فهم داده ها. تکامل تکنولوژی پایگاه داده و استفاده فراوان آن در کاربردهای مختلف سبب جمع آوری حجم داده فراوان شده است .این داده های فراوان باعث ایجاد نیاز برای ابزارهای قدرتمند برای تحلیل داده ها گشته، زیرا در حال حاضر به لحاظ داده ثروتمند هستیم ولی دچار کمبود اطلاعات می باشیم .شکاف موجود بین داده ها و اطلاعات سبب ایجاد نیاز برای ابزارهای داده کاوی شده است تا داده های بی ارزش را به دانشی ارزشمند تبدیل کنیم.

به طور ساده داده کاوی به معنای استخراج یا “معدن کاری ” دانش از مقدار زیادی داده خام است. البته این نامگذاری برای این فرآیند تا حدی نامناسب است، زیرا به طور مثال عملیات معدن کاری برای استخراج طلا از صخره و ماسه را طلا کاوی می نامیم، نه ماسه کاوی یا صخره کاوی، بنابراین بهتر بود به این فرآیند نامی شبیه به “استخراج دانش از داده” می دادیم که متاسفانه بسیارطولانی است.

دانش کاوی” به عنوان یک عبارت کوتاهتر به عنوان جایگزین، نمی تواند بیانگر تاکید واهمیت بر معدن کاری مقدار زیاد داده باشد. معدن کاری عبارتی است که بلافاصله انسان را به یاد فرآیندی می اندازد که به دنبال یافتن مجموعه کوچکی از قطعات ارزشمند از حجم بسیار زیادی از مواد خام هستیم، با توجه به مطالب عنوان شده، با اینکه این فرآیند تا حدی دارای نامگذاری ناقص است ولی این نامگذاری یعنی داده کاوی بسیار عمومیت پیدا کرده است. البته اسامی دیگری نیز برای این فرآیند پیشنهاد شده که بعضا بسیاری متفاوت با واژه داده کاوی است، نظیر: استخراج دانش از پایگاه داده، استخراج دانش ، آنالیز داده / الگو،باستان شناسیداده ، و لایروبی داده ها. بسیاری از مردم داده کاوی را هم ارز با واژگانی نظیر کشف دانش در پایگاه داده می دانند[5].

کشف دانش دارای مراحل تکراری زیر است:

۱‐ پاکسازی داده ها (از بین بردن نویز و ناسازگاری داده ها)

۲‐ یکپارچه سازی داده ها (چندین منبع داده ترکیب می شوند)