پژوهش: پایان نامه ارشد مهندسی فناوری اطلاعات: رویکردی مبتنی بر گراف به منظور خوشه‌بندی ترکیبی افرازبندی‌های فازی

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

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

پايان نامه مقطع كارشناسي ارشد

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

عنوان/موضوع:

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

استاد راهنما:

دکتر جواد وحیدی

استاد مشاور:

دکتر بابک شیرازی

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

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

فهرست مطالب:

فصل اول- مقدمه و کلیات پژوهش……………………………………………………………………..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)………………………

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

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

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

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

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

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

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

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

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

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

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

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].

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

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

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

۳‐ انتخاب داده ها (داده هاي مرتبط با آناليز از پايگاه داده بازيابي مي شوند)

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

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

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

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

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

2-1- تکنیک های داده کاوی

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

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

متن کامل را می توانید دانلود نمائید

زیرا فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به گونه نمونه)

اما در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود می باشد

تعداد صفحه : 117

قیمت : چهارده هزار و هفتصد تومان