…………………………………………………………………………………………………………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 مقایسه خواهد­گردید. توانایی بالا و مقاوم بودن این روش بر اساس نتایج مشهود خواهد بود.
<
strong>مقدمه
داده و الگو یکی از شاخص­های بسیار مهم در دنیای اطلاعات هستند و خوشه­بندی یکی از بهترین روش­هایی است که برای کار با داده­ها ارائه شده است. قابلیت آن در ورود به فضای داده و تشخیص ساختار آن­ها باعث گردیده که خوشه بندی یکی از ایده­آل­ترین مکانیزم­ها برای کار با دنیای عظیم داده­ها باشد.
در خوشه­بندی، نمونه­ها به دسته­هایی تقسیم می­شوند که از قبل معلوم نیستند. بنابراین، خوشه­بندی یک روش یادگیری است که بدون دانش پیشین و مشاهده نمونه­های از قبل تعریف شده­، داده­ها را به صورت خود مختار و مستقل دسته بندی می­کند.
خوشه بندی در واقع یافتن ساختار در مجموعه داده­هایی است که طبقه بندی نشده­اند. به بیان دیگر خوشه­بندی قرار­دادن داده­ها در گرو­ه­هایی است که اعضای هر گروه از زاویه­ی خاصی به هم شباهت دارند. در نتیجه شباهت بین داده­های درون هر خوشه حداکثر و شباهت بین داده­های درون خوشه­های متفاوت حداقل می­باشد. معیار شباهت در اینجا، فاصله بوده یعنی نمونه­هایی که به یکدیگر نزدیک­ترهستند، در یک خوشه قرار می­گیرند. لذا محاسبه­ی فاصله­ی بین دو داده در خوشه­بندی بسیار مهم می­باشد؛ زیرا کیفیت نتایج نهایی را دستخوش تغییر قرار خواهد داد.
فاصله که همان معرف عدم تجانس است حرکت در فضای داده­ها را میسر می­سازد و سبب ایجاد خوشه­ها می­گردد. با محاسبه­ی فاصله­ی بین دو داده، می­توان فهمید که چقدر این دو داده به هم نزدیک هستند و در یک خوشه قرار می گیرند یا نه؟ توابع ریاضی مختلفی برای محاسبه­ی فاصله وجود دارند؛ فاصله اقلیدسی، فاصله همینگ و ….
1-1-بیان مسأله
خوشه­بندی یافتن ساختار، درون مجموعه­ای از داده­های بدون برچسب است و می­توان آن را به عنوان مهم­ترین مسأله در یادگیری بدون نظارت در نظر گرفت. ایده­ی خوشه­بندی اولین بار در دهه­ی 1935 مطرح شد و امروزه با پیشرفت­ها و جهش­های عظیمی که در آن به­وجود آمده در کاربردها و جنبه­های مختلفی حضور یافته است. یک جستجوی ساده در وب یا حتی در پایگاه داده یک کتابخانه، کاربرد شگفت انگیز آن را برای ما آشکار می­سازد. الگوریتم­های خوشه­بندی در زمینه­های مختلفی کاربرد دارد که به عنوان نمونه می­توان موارد زیر را برشمرد:
· داده کاوی[1]: کشف اطلاعات و ساختار جدید از داده های موجود
· تشخیص گفتار[2]: در ساخت کتاب کد از بردارهای ویژگی، در تقسیم کردن گفتار بر حسب گویندگان آن یا فشرده سازی گفتار
· تقسیم بندی تصاویر[3]: تقسیم بندی تصاویر پزشکی یا ماهواره ای