فهرست مطالب 1- فصل اول: مقدمه ....... 21-1- بیان مسأله ....... 31-2- پیشینه تحقیق ...... 41-3- هدف تحقیق ...........51-4- اهمیت تحقیق ........51-5- گفتارهای پایان نامه .............82- فصل دوم: خوشه بندی بر مبنای الگوریتم Fuzzy c-means ......102-1- مقدمه ..........112-2- خوشه بندی اطلاعات .........112-2-1- تفاوت خوشهب ندی و طبفه بندی ............132-2-2-کاربردهای خوشه بندی......... 132-2-3- انواع خوشه ها........152-2-4- مراحل خوشه بندی .........152-2-5- انواع روش های خوشه بندی .................................................................................................. 182-2-6- خوشه بندی سلسله مراتبی ...................................................................................................... 182-2-6-1- خوشه بندی سلسله مراتبی تقسیم شونده ............................................................................192-2-6-2- خوشه بندی سلسله مراتبی متراکم شونده ......................................................................... 19 عنوان صفحه 2-2-7- خوشه بندی افرازبندی یا پارتیشنی .............................................................................................222-2-7-1- الگوریتم k-means ...........................................................................................................232-2-8- خوشه بندی همپوشانی................................................................................................................262-2-8-1- خوشه بندی فازی.................................................................................................................273- فصل سوم: بهینه سازی بر مبنای الگوریتم خفاش .................................................................................. 333-1- مقدمه .............................................................................................................................................. 343-2- شرح مسئله بهینه سازی .................................................................................................................. 353-3- روش های حل مسائل بهینه سازی ................................................................................................. 393-3-1- الگوريتم بهینهسازی توده ذرات ............................................................................................. 433-3-2- الگوريتم جفت گیری زنبور عسل ........................................................................................... 453-3-3- الگوریتم مورچگان .................................................................................................................. 463-3-4- الگوریتم الگوي جستجوي ممنوع ........................................................................................... 48 3-3-5-الگوریتم آبکاری فولاد .............................................................................................................. 49 3-3-6- الگوریتم خفاش ....................................................................................................................... 513-3-7-راهحلهای پیشنهادی برای بهبود عملکرد الگوریتم خفاش ......................................................... 54 3-3-7-1-انتخاب جمعیت اولیه بر اساس قاعده نولید عدد متضاد ...................................................... 543-3-7-2-استراتژی جهش خود تطبیق ................................................................................................ 553-4- معیارهای مقایسه الگوریتمهای بهینهسازی ...................................................................................... 583-4-1- کارایی.................................................................................................................................... 583-4-2- انحراف استاندارد................................................................................................................... 583-4-3- قابلیت اعتماد.......................................................................................................................... 593-4-4- سرعت همگرایی.................................................................................................................... 59 عنوان صفحه 3-5-تعریف مسایل عددی گوناگون.......................................................................................................... 603-5-1-تابع Rosenbrock.................................................................................................................. 613-5-2- تابع Schewefel ....................................................................................................................623-5-3- تابع Rastragin ......................................................................................................................633-5-4- تابعAchley .............................................................................................................................643-5-5- تابع Greiwank .......................................................................................................................654- فصل چهارم: الگوریتم پیشنهادی ..............................................................................................................664-1- مقدمه .............................................................................................................................................. 674-2- خوشه بندی اطلاعات به روش ترکیبی پیشنهادی ........................................................................... 684-3- تنظیم پارامترهای الگوریتم پیشنهادی .............................................................................................. 714-4- بررسی نتایج حاصل از الگوریتم پیشنهادی و مقایسه آن با دیگر الگوریتم ها.................................. 714-4-1- معرفی داده های استفاده شده و نتایج شبیه سازی مربوط به آن..................................................724-4-1-1- مجموعه داده Iris ............................................................................................................ 724-4-1-2- مجموعه داده Wine ........................................................................................................ 754-4-1-3- مجموعه داده CMC ....................................................................................................... 774-4-1-4- مجموعه داده Vowel ..................................................................................................... 805- فصل پنجم: نتیجه گیری و پیشنهادات ......................................................................................................825-1- نتیجه ............................................................................................................................................... 835-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 تابعelSchewef..................... 62شکل 3-10 الف) نماش سه بعدی تابع Rastragin ب) نمایش contour تابع Rastragin .........................63شکل3-11 الف) نماش سه بعدی تابع Ackley ب) نمایش contour تابع Ackley................................... 64شکل3-12 الف) نماش سه بعدی تابع Greiwank ب) نمایش contour تابع Greiwank...................... 65شکل 4‑1نمونه های گلهای زنبق از مجموعه دادهIris ............................................................................................. 72فصل اول : مقدمهمقدمهداده و الگو یکی از شاخصهای بسیار مهم در دنیای اطلاعات هستند و خوشهبندی یکی از بهترین روشهایی است که برای کار با دادهها ارائهشده است. قابلیت آن در ورود به فضای داده و تشخیص ساختار آنها باعث گردیده که خوشه بندی یکی از ایدهآلترین مکانیزمها برای کار با دنیای عظیم دادهها باشد.در خوشهبندی، نمونهها به دستههایی تقسیم میشوند که از قبل معلوم نیستند. بنابراین، خوشهبندی یک روش یادگیری است که بدون دانش پیشین و مشاهده نمونههای از قبل تعریف شده، دادهها را به صورت خود مختار و مستقل دسته بندی میکند.خوشه بندی در واقع یافتن ساختار در مجموعه دادههایی است که طبقه بندی نشدهاند. به بیان دیگر خوشهبندی قراردادن دادهها در گروههایی است که اعضای هر گروه از زاویهی خاصی به هم شباهت دارند. در نتیجه شباهت بين دادههاي درون هر خوشه حداکثر و شباهت بين دادههاي درون خوشههاي متفاوت حداقل میباشد. معیار شباهت در اینجا، فاصله بوده یعنی نمونههایی که به یکدیگر نزدیکترهستند، در یک خوشه قرار میگیرند. لذا محاسبهی فاصلهی بین دو داده در خوشهبندی بسیار مهم میباشد؛ زیرا کیفیت نتایج نهایی را دستخوش تغییر قرار خواهد داد.فاصله که همان معرف عدم تجانس است حرکت در فضای دادهها را میسر میسازد و سبب ایجاد خوشهها میگردد. با محاسبهی فاصلهی بین دو داده، میتوان فهمید که چقدر این دو داده به هم نزدیک هستند و در یک خوشه قرار می گیرند یا نه؟ توابع ریاضی مختلفی برای محاسبهی فاصله وجود دارند؛ فاصله اقلیدسی، فاصله همینگ و .... 1-1-بیان مسألهخوشهبندي یافتن ساختار، درون مجموعهای از دادههای بدون برچسب است و میتوان آن را به عنوان مهمترین مسأله در یادگیری بدون نظارت در نظر گرفت. ایدهی خوشهبندی اولین بار در دههی 1935 مطرح شد و امروزه با پیشرفتها و جهشهای عظیمی که در آن بهوجود آمده در کاربردها و جنبههای مختلفی حضور یافته است. یک جستجوی ساده در وب یا حتی در پایگاه داده یک کتابخانه، کاربرد شگفت انگیز آن را برای ما آشکار میسازد. الگوریتمهای خوشهبندی در زمینههای مختلفی کاربرد دارد که به عنوان نمونه میتوان موارد زیر را برشمرد: