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

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

پایان نامه مقطع ارشد فناوری اطلاعات

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

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

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

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

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

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

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

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

استاد مشاور:

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

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

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

فهرست مطالب:

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

قیمت : 14700 تومان

 

***

—-

:       

****         info@elmyar.net

 

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

 
 

مطالب مشابه را هم ببینید

 

فایل مورد نظر خودتان را پیدا نکردید ؟ نگران نباشید . این صفحه را نبندید ! سایت ما حاوی حجم عظیمی از پایان نامه های دانشگاهی است. مطالب مشابه را هم ببینید. برای یافتن فایل مورد نظر کافیست از قسمت جستجو استفاده کنید. یا از منوی بالای سایت رشته مورد نظر خود را انتخاب کنید و همه فایل های رشته خودتان را ببینید