:دانلود فایل متن کامل پایان نامه در سایت sabzfile.com

عنوان : رویکردی مبتنی برگراف به مقصود خوشه‌بندی ترکیبی افرازبندی‌های فازی

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

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

 

پایان نامه

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

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

عنوان/موضوع    :رویکردی مبتنی بر گراف به مقصود خوشه‌بندی ترکیبی افرازبندی‌های فازی

استا دراهنما:دکتر جواد وحیدی

استاد مشاور:دکتر بابک شیرازی

(پاییز 1391)

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

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

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

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

چکیده

 

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

 

کلمات کلیدی فارسی :خوشه بندی ترکیبی ، خوشه بندی فازی ، خوشه بندی ترکیبی فازی ، شاخص اعتبار خوشه ، ماتریس همبستگی فازی ، ماتریس استحکام ، الگوریتم مبتنی بر گراف

فهرست مطالب

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

عنوان                                                                                                  صفحه

فصل اول- مقدمه و کلیات پژوهش                                                              1

1-1 مقدمه ای بر داده‌کاوی…………………………………………………………………………………..2

1-2 تکنیکهای داده‌کاوی………………………………………………………………………………………4

1-3 مقدمه‌ای بر خوشه‌بندی…………………………………………………………………………………4

1-4 تفاوت خوشه­بندی و دسته­بندی……………………………………………………………………..5

1-5 یادگیری با نظارت پیش روی یادگیری بدون‌نظارت…………………………………………….6

1-6 کاربردهای خوشه‌بندی…………………………………………………………………………………6

1-7 تقسیم‌بندی روش‌های خوشه‌بندی از جنبه های گوناگون ………………………………..7

1-8 طبقه­بندی دیگری از روشهای اصلی خوشه­بندی……………………………………………..8

1-8-1 روش افرازبندی…………………………………………………………………………………8

1-8-1-1 روش خوشه‌بندی K-Means (C-Means یا C-Centeriod)……………9

1-8-1-2 الگوریتم خوشه‌بندی LBG…………………………………………………………………11

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

 

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

 

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

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

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

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

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

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

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

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

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

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

۳‐ انتخاب داده ها (داده های مرتبط با واکاوی از پایگاه داده بازیابی می شوند)

۴‐ تبدیل کردن داده ها(تبدیل داده ها به فرمی که مناسب برای داده کاوی باشد مثل اختصار سازی و همسانسازی)

۵ ‐داده کاوی (فرایند اصلی که روالهای هوشمند برای استخراج الگوها از داده ها به کار گرفته می شوند)

۶ ‐ارزیابی الگو (برای مشخص کردن الگوهای صحیح و مورد نظر به وسیله معیارهای اندازه گیری)

۷ ‐ارائه دانش (یعنی نمایش بصری، تکنیکهای بازنمایی دانش برای ارائه دانش کشف شده به کاربر بهره گیری می گردد)

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

تعداد صفحه : 123

قیمت : 14700 تومان

بلافاصله پس از پرداخت لینک دانلود فایل در اختیار شما قرار می گیرد

و در ضمن فایل خریداری شده به ایمیل شما ارسال می گردد.

پشتیبانی سایت :        ****       [email protected]

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

***  **** ***