دانلود پایان نامه ارشد: ارائه روشی جدید در خوشه بندی اطلاعات با استفاده ازترکیب الگوریتم خفاش و Fuzzy c- means

دانلود متن کامل پایان نامه مقطع کارشناسی ارشد رشته اتوماسیون و ابزار دقیق

عنوان : ارائه روشی جدید در خوشه بندی اطلاعات با استفاده ازترکیب الگوریتم خفاش و Fuzzy c- means

دانشگاه شیراز

دانشکده آموزشهای الکترونیکی

پایان نامه کارشناسی ارشد در رشته مهندسی اتوماسیون و ابزار دقیق

عنوان:

ارائه روشی جدید در خوشه بندی اطلاعات با استفاده ازترکیب الگوریتم خفاش و Fuzzy c- means

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

  دکتر طاهر نیکنام

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

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

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

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

فهرست مطالب:

1- فصل اول: مقدمه ……………………………………………………………………………………………………………………… 2

1-1- بیان مسأله ………………………………………………………………………………………………………………………… 3

1-2- پیشینه تحقیق ……………………………………………………………………………………………………………………. 4

1-3- هدف تحقیق ……………………………………………………………………………………………………………………….5

1-4- اهمیت تحقیق ………………………………………………………………………………………………………………………5

1-5- گفتارهای پایان نامه ………………………………………………………………………………………………………………8

2- فصل دوم: خوشه بندی بر مبنای الگوریتم Fuzzy c-means ………………………………………………………10

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

2-2- خوشه بندی اطلاعات …………………………………………………………………………………………………………11

2-2-1- تفاوت خوشه­بندی و طبفه­بندی ……………………………………………………………………………………..13

2-2-2-کاربردهای خوشه­بندی………………………………………………………………………………………………… 13

2-2-3- انواع خوشه­ها………………………………………………………………………………………………………………15

2-2-4- مراحل خوشه بندی ……………………………………………………………………………………………………..15

2-2-5- انواع روش های خوشه بندی …………………………………………………………………………………….. 18

2-2-6- خوشه بندی سلسله مراتبی ………………………………………………………………………………………… 18

2-2-6-1- خوشه بندی سلسله مراتبی تقسیم شونده ………………………………………………………………….19

2-2-6-2- خوشه بندی سلسله مراتبی متراکم شونده ………………………………………………………………. 1

2-2-7- خوشه بندی افراز­بندی یا پارتیشنی …………………………………………………………………………………22

2-2-7-1- الگوریتم k-means ……………………………………………………………………………………………..23

2-2-8- خوشه بندی همپوشانی………………………………………………………………………………………………….26

2-2-8-1- خوشه بندی فازی…………………………………………………………………………………………………..27

3- فصل سوم: بهینه سازی بر مبنای الگوریتم خفاش ………………………………………………………………………. 33

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

3-2- شرح مسئله بهینه سازی …………………………………………………………………………………………………… 35

3-3- روش های حل مسائل بهینه سازی ……………………………………………………………………………………. 39

3-3-1- الگوریتم بهینه­سازی توده ذرات …………………………………………………………………………………  43

3-3-2- الگوریتم جفت گیری زنبور عسل ………………………………………………………………………………. 45

3-3-3- الگوریتم مورچگان …………………………………………………………………………………………………… 46

3-3-4- الگوریتم الگوی جستجوی ممنوع ………………………………………………………………………………. 48

3-3-5-الگوریتم آبکاری فولاد ……………………………………………………………………………………………….. 49

3-3-6- الگوریتم خفاش ……………………………………………………………………………………………………….. 51

3-3-7-راه­حلهای پیشنهادی برای بهبود عملکرد الگوریتم خفاش ………………………………………………… 54

3-3-7-1-انتخاب جمعیت اولیه بر اساس قاعده نولید عدد متضاد ……………………………………………… 54

3-3-7-2-استراتژی جهش خود تطبیق …………………………………………………………………………………… 55

3-4- معیارهای مقایسه الگوریتمهای بهینه­سازی ………………………………………………………………………….. 58

3-4-1- کارایی…………………………………………………………………………………………………………………… 58

3-4-2- انحراف استاندارد……………………………………………………………………………………………………. 58

3-4-3- قابلیت اعتماد………………………………………………………………………………………………………….. 59

3-4-4- سرعت همگرایی…………………………………………………………………………………………………….. 59

3-5-تعریف مسایل عددی گوناگون……………………………………………………………………………………………. 60

3-5-1-تابع Rosenbrock…………………………………………………………………………………………………… 61

3-5-2- تابع Schewefel  ……………………………………………………………………………………………………..62

3-5-3- تابع Rastragin  ……………………………………………………………………………………………………….63

3-5-4- تابعAchley ……………………………………………………………………………………………………………..64

3-5-5- تابع Greiwank ………………………………………………………………………………………………………..65

4- فصل چهارم: الگوریتم پیشنهادی ………………………………………………………………………………………………..66

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

4-2- خوشه بندی اطلاعات به روش ترکیبی پیشنهادی ………………………………………………………………… 68

4-3- تنظیم پارامترهای الگوریتم پیشنهادی …………………………………………………………………………………. 71

4-4- بررسی نتایج حاصل از الگوریتم پیشنهادی و مقایسه آن با دیگر الگوریتم ها……………………………. 71

4-4-1- معرفی داده های استفاده شده و نتایج شبیه سازی مربوط به آن  …………………………………………..72

4-4-1-1- مجموعه داده Iris ……………………………………………………………………………………………… 72

4-4-1-2- مجموعه داده Wine ………………………………………………………………………………………….. 75

4-4-1-3- مجموعه داده CMC …………………………………………………………………………………………. 77

4-4-1-4- مجموعه داده Vowel ……………………………………………………………………………………….. 80

5- فصل پنجم: نتیجه گیری و پیشنهادات …………………………………………………………………………………………82

5-1- نتیجه …………………………………………………………………………………………………………………………….. 83

5-2- پیشنهاد کارهای آینده ………………………………………………………………………………………………………. 84

 

فهرست جدول­ها

جدول2‑1 مزایا و معایب الگوریتم k-means …………………………………………………………………………………………………26

جدول2‑2 معایب و محاسن الگوریتم c میانگین فازی …………………………………………………………………………………… 31

جدول2‑3 معیارهای تشابه بر اساس توابع فاصله مختلف………………………………………………………………………………….32

جدول3-1  توابع عددی مورد استفاده برای تست الگوریتم‌ها …………………………………………………………………………60

جدول4‑1 پارامترهای مربوط به الگوریتم های پیشنهادی ……………………………………………………………………………….71

جدول4‑2مراکز خوشه به دست آمده با اجرای الگوریتم FCM-BA روی مجموعه دادهIris  ………………….73

جدول4‑3پاسخ الگوریتم های موجود بر روی مجموعه دادهIris …………………………………………………………………….74

جدول4‑4 پاسخ الگوریتم FCM-BA بازاء مقادیر مختلف پارامترها بر روی مجموعه داده Iris ………………. 74

جدول4‑5 پاسخ الگوریتم های موجود بر روی مجموعه داده Wine………………………………………………………………75

جدول4‑6 مراکز خوشه به دست آمده بااجرای الگوریتم FCM-BA روی مجموعه داده Wine………………..76

جدول4‑7پاسخ الگوریتمFCM-BA   بازاء مقادیر مختلف پارامترها برروی مجموعه دادهWine …………….. 77

جدول 4‑8 مراکز خوشه به دست آمده با اجرای الگوریتم پیشنهادی روی مجموعه داده CMC ………………. 78

جدول 4‑9پاسخ الگوریتم های موجود بر روی مجموعه داده CMC ……………………………………………………………..79

جدول4‑10پاسخ الگوریتم   FCM-BAبازاء مقادیر مختلف پارامترها بر روی مجموعه داده CMC …………79

جدول 4‑11 مراکز خوشه به دست آمده با اجرای الگوریتم پیشنهادی روی مجموعه داده Vowel ……………80

جدول 4-12 پاسخ الگوریتم های موجود بر روی مجموعه داده Vowel ……………………………………………………….80

جدول 4‑13 پاسخ الگوریتمFCM-BA بازاء مقادیر مختلف پارامترهابرروی مجموعه داده Vowel ……….  81

 

فهرست شکل­ها

شکل 2‑1 تفاوت خوشه بندی و طبقه بندی …………………………………………………………………………………………………  12

شکل2-2 مراحل خوشه بندی ………………………………………………………………………………………………………………………..  17

شکل 2‑ 3 محاسبه فاصله در اتصال منفرد، اتصال میانگین و اتصال کامل …………………………………………………. 0 2

شکل 2-4 تفاوت بین روش متراکم شوتده و تقسیم کننده …………………………………………………………………………..  20

شکل2-5 مجموعه داده پروانه­ا­ی …………………………………………………………………………………………………………………….  27

شکل 2‑6 توزیع یک بعدی نمونه ها ………………………………………………………………………………………………………………  30

شکل 2‑7 خوشه بندی کلاسیک نمونه های ورودی ……………………………………………………………………………………… 30

شکل 2‑ 8 خوشه بندی فازی نمونه ها ………………………………………………………………………………………………………….  31

شکل 3‑1 دسته ­بندی­های متفاوت در مسایل بهینه ­سازی ………………………………………………………………………….  37

شکل 3‑2 روش­های حل مسایل بهینه ­سازی ………………………………………………………………………………………………..  40

شکل 3‑3  تقسیم بندی روش محاسباتی ………………………………………………………………………………………………………  41

شکل 3-4 آزمایش پل دوگانه …………………………………………………………………………………………………………………………  47

شکل 3-5 استفاده از echolocation برای پیدا کردن شکار توسط یک خفاش ……………………………………….  52

شکل3-6 شبه کد الگوریتم خفاش ………………………………………………………………………………………………………………….. 53

شکل3-7 تابع موج ضربه‌ای مورلت …………………………………………………………………………………………………………………  56

شکل 3-8 الف) نماش سه بعدی تابع Rosenbrock ب) نمایش contour تابع Rosenbrock ………….  61

شکل 3-9 الف) نماش سه بعدی تابع Schewefel ب) نمایش contour تابعel Schewef …………………  62

شکل 3-10 الف) نماش سه بعدی تابع Rastragin ب) نمایش contour تابع Rastragin …………………….63

شکل3-11 الف) نماش سه بعدی تابع Ackley ب) نمایش contour تابع Ackley ……………………………..  64

شکل3-12 الف) نماش سه بعدی تابع Greiwank ب) نمایش contour تابع Greiwank ………………….  65

شکل 4‑1نمونه های گلهای زنبق از مجموعه دادهIris …………………………………………………………………………………  72

چکیده

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

Fuzzy c-means نیز یک تکنیک خوشه­بندی فازی است که علی­رغم حساس بودن به مقدار دهی اولیه و همگرائی به نقاط بهیـــنه محلی ، به دلیل کارآمد بودن و پیاده سازی آسان، یکی از متداول­ترین روش­ها می­باشد. در این رساله جهت رفع مشکلات موجود از روش ترکیبی مبتنی بر الگوریتم خفاش و Fuzzy c-means بهره گرفته ­خواهد ­شد. به منظور اعتبارسنجی، روش پیشنهادی بر روی چندین داده متفاوت مشهور پیاده­سازی می­گردد و نتــایج با روش­های الگوریتم­ جستجوی ممنوع، مورچگان، اجتماع ذرات، آبکاری فولاد و k-means مقایسه خواهد­گردید. توانایی بالا و مقاوم بودن این روش بر اساس نتایج مشهود خواهد بود.

مقدمه

داده و الگو یکی از شاخص­های بسیار مهم در دنیای اطلاعات هستند و خوشه­بندی یکی از بهترین روش­هایی است که برای کار با داده­ها ارائه شده است. قابلیت آن در ورود به فضای داده و تشخیص ساختار آن­ها باعث گردیده که خوشه بندی یکی از ایده­آل­ترین مکانیزم­ها برای کار با دنیای عظیم داده­ها باشد.

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

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

فاصله که همان معرف عدم تجانس است حرکت در فضای داده­ها را میسر می­سازد و سبب ایجاد خوشه­ها می­گردد. با محاسبه­ی فاصله­ی بین دو داده، می­توان فهمید که چقدر این دو داده به هم نزدیک هستند و در یک خوشه قرار می گیرند یا نه؟ توابع ریاضی مختلفی برای محاسبه­ی فاصله وجود دارند؛ فاصله اقلیدسی، فاصله همینگ و ….

1-1-بیان مسأله

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

·        داده کاوی[1]: کشف اطلاعات و ساختار جدید از داده‌های موجود

·        تشخیص گفتار[2]: در ساخت کتاب کد از بردارهای ویژگی، در تقسیم کردن گفتار بر حسب گویندگان آن یا فشرده‌سازی گفتار

·        تقسیم‌بندی تصاویر[3]: تقسیم‌بندی تصاویر پزشکی یا ماهواره‌ای

·        وب (WWW): دسته‌بندی اسناد و یا دسته‌بندی سایت­ها و …

·        زیست‌‌‌شناسی[4]: دسته‌بندی حیوانات و گیاهان از روی ویژگی‌های آن­ها

·        برنامه ریزی شهری[5]: دسته‌بندی خانه‌ها بر اساس نوع و موقعیت جغرافیایی آن­ها

·         مطالعات زلزله‌نگاری[6]: تشخیص مناطق حادثه‌خیز بر اساس مشاهدات قبلی

·        کتابداری: دسته‌بندی کتاب­ها

·        بیمه: تشخیص افراد متقلب

·        بازاریابی[7]: دسته‌‌بندی مشتریان به دسته‌هایی بر حسب نیاز آن­ها از طریق مجموعه آخرین خرید‌های آنان.

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

 

تعداد صفحه : 104

قیمت : 14000تومان

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

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

پشتیبانی سایت :        09199970560        info@arshadha.ir

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

شماره کارت :  6037997263131360 بانک ملی به نام محمد علی رودسرابی

11

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

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