شکل ۳-۵ استفاده از echolocation برای پیدا کردن شکار توسط یک خفاش ………………………………………. ۵۲

شکل۳-۶ شبه کد الگوریتم خفاش ………………………………………………………………………………………………………………….. ۵۳
شکل۳-۷ تابع موج ضربه‌ای مورلت ………………………………………………………………………………………………………………… ۵۶
شکل ۳-۸ الف) نماش سه بعدی تابع Rosenbrock ب) نمایش contour تابع Rosenbrock …………. 61
شکل ۳-۹ الف) نماش سه بعدی تابع Schewefel ب) نمایش contour تابعel Schewef ………………… 62
شکل ۳-۱۰ الف) نماش سه بعدی تابع Rastragin ب) نمایش contour تابع Rastragin …………………….63
شکل۳-۱۱ الف) نماش سه بعدی تابع Ackley ب) نمایش contour تابع Ackley …………………………….. ۶۴
شکل۳-۱۲ الف) نماش سه بعدی تابع Greiwank ب) نمایش contour تابع Greiwank …………………. 65
شکل ۴‑۱نمونه های گلهای زنبق از مجموعه دادهIris ………………………………………………………………………………… ۷۲
فصل اول : مقدمه
مقدمه
داده و الگو یکی از شاخص­ های بسیار مهم در دنیای اطلاعات هستند و خوشه­بندی یکی از بهترین روش­هایی است که برای کار با داده ­ها ارائه شده است. قابلیت آن در ورود به فضای داده و تشخیص ساختار آن­ها باعث گردیده که خوشه بندی یکی از ایده­آل­ترین مکانیزم­ ها برای کار با دنیای عظیم داده ­ها باشد.
در خوشه­بندی، نمونه­ها به دسته­هایی تقسیم می­شوند که از قبل معلوم نیستند. بنابراین، خوشه­بندی یک روش یادگیری است که بدون دانش پیشین و مشاهده نمونه­های از قبل تعریف شده­، داده ­ها را به صورت خود مختار و مستقل دسته بندی می­ کند.
خوشه بندی در واقع یافتن ساختار در مجموعه داده­هایی است که طبقه بندی نشده­اند. به بیان دیگر خوشه­بندی قرار­دادن داده ­ها در گرو­ه­هایی است که اعضای هر گروه از زاویه­ی خاصی به هم شباهت دارند. در نتیجه شباهت بین داده ­های درون هر خوشه حداکثر و شباهت بین داده ­های درون خوشه­های متفاوت حداقل می­باشد. معیار شباهت در اینجا، فاصله بوده یعنی نمونه­هایی که به یکدیگر نزدیک­ترهستند، در یک خوشه قرار می­گیرند. لذا محاسبه­ی فاصله­ی بین دو داده در خوشه­بندی بسیار مهم می­باشد؛ زیرا کیفیت نتایج نهایی را دستخوش تغییر قرار خواهد داد.
فاصله که همان معرف عدم تجانس است حرکت در فضای داده ­ها را میسر می­سازد و سبب ایجاد خوشه ­ها می­گردد. با محاسبه­ی فاصله­ی بین دو داده، می­توان فهمید که چقدر این دو داده به هم نزدیک هستند و در یک خوشه قرار می گیرند یا نه؟ توابع ریاضی مختلفی برای محاسبه­ی فاصله وجود دارند؛ فاصله اقلیدسی، فاصله همینگ و ….
۱-۱-بیان مسأله
خوشه­بندی یافتن ساختار، درون مجموعه ­ای از داده ­های بدون برچسب است و می­توان آن را به عنوان مهم­ترین مسأله در یادگیری بدون نظارت در نظر گرفت. ایده­ خوشه­بندی اولین بار در دهه­ ۱۹۳۵ مطرح شد و امروزه با پیشرفت­ها و جهش­های عظیمی که در آن به ­وجود آمده در کاربردها و جنبه­ های مختلفی حضور یافته است. یک جستجوی ساده در وب یا حتی در پایگاه داده یک کتابخانه، کاربرد شگفت انگیز آن را برای ما آشکار می­سازد. الگوریتم­های خوشه­بندی در زمینه ­های مختلفی کاربرد دارد که به عنوان نمونه می­توان موارد زیر را برشمرد:

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

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

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

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

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

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

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

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

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

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

با توجه به کاربرد روزافزون خوشه­بندی، امروزه شاهد ارائه­ روش­های جدید و کارآمدتری هستیم که هر یک برای کاربردی خاص ارائه می­ شود. ولی با همه این تلاش­ها هنوز خوشه­بندی در بسیاری از علوم آن­چنان که باید مورد استفاده قرار نگرفته است و قابلیت گسترش بسیار زیادی برای آن وجود دارد.
۱-۲-پیشینه تحقیق
ما در جها­نی پر از داده زندگی می­کنیم و هر روز با حجم وسیعی از ذخیره یا نمایش اطلاعات روبه­رو هستیم. یکی از روش­های حیاتی کنترل و مدیریت این داده ­ها، خوشه­بندی می­باشـد. در این روش داده­هایی که دارای خواص مشابه می­باشند، درون یک دسته یا یک خوشه قرار می­گیرند. اولین بار ایده­ خوشه­بندی در دهه­ ۱۹۳۵ ارائه شد و امروزه با پیشرفت­ها و جهش­های عظیمی که در آن پدید آمده مورد توجه بسیاری از محققــان قرار گرفته است. لذا در کاربردها و جنبه­ های مختلفی حضور یافته و روش­های مختلفی برای بهره ­برداری از آن مطرح گردیده است [۱]. از یک نظر، الگوریــتم­های خوشه بندی می تواند در دو دسته کلی تقسیم ­بندی شوند: خوشه بندی سخت و خوشه بندی فازی. در خوشه­بندی سخت یک داده به یک و فقط یک خوشه تعلق می­گیرد، درحالی­که در خوشه­بندی فازی یک داده ممکن است بطور هم­زمان به دو خوشه یا بیشتر تعلق داشته باشد [۲]، [۳]، [۴]. الگوریتم Fuzzy c-means یکی از روش­های معروف خوشه­بندی فازی محسوب می­گردد که به سادگی قابل پیاده­سازی می­باشد. متأسفانه نسخه­ اصل آن دارای محدودیت­هایی از جمله وابستگی به مقادیر اولیه و همگرایی به پاسخ بهینه محلی می­باشد [۵]، [۶]. در الگوریتم ژنتیک این محدودیت­ها از بین رفته است. در عین حال با ترکیب این دو الگوریتم نتایج قابل توجهی حاصل شده است که سرعت همگرایی آن نیز به مراتب از نمونه­های قبل بیشتر گردیده است [۷]. Kao و همکارانش با ترکیب دو الگوریتم ژنتیک و PSO روشی را ابداع نمود که در آن از عملگر جهش و تقاطع برای ژنتیک بهره گرفته است. این روش توانست مشکلات مختلف توابع پیوسته را رفع نماید. هم­چنین در یافتن جواب بهینه­ سراسری و نسبت همگرایی تغییرات چشمگیری حاصل شده است [۸]. با بهره گرفتن از ترکیب الگوریتم ژنتیک و روش فازی، روشی توسط عسگریان در سال ۱۳۸۶ مطرح شد. در این روش مشکل وابستگی به تعداد اولیه خوشه ­ها ­و مکان اولیه مراکز آن­ها مرتفع و با عدم توانایی خوشه­بندی داده­هایی که فاصله­ی آنها از مراکز چند خوشه به یک اندازه می­باشد؛ مقابله گردید. از مزایای دیگر این ترکیب کاهش پیچیدگی محاسبات می­باشد [۹]. یکی دیگر از روش­های ترکیبی که در مسائل داده ­کاوی کاربرد دارد استفاده از ترکیب Fuzzy c-means و PSO می­باشد که توانست مشکل همگرایی به بهینه­ محلی و سرعت همگرایی را بهبود بخشد [۱۰] ،[۱۱]. از دیگر روش­های ترکیبی جدید ترکیب الگوریتمFCM و الگوریتم مِمتیک فازی است. در راستای بهبود عملکرد خوشه­بندی، نتایج حاصل از این تکنیک نشان می­دهد که جواب­های بهتری داشته و پایداری آن نیز بالاتر می­باشد [۱۲]. ترکیب FCM و SA نمونه ­ای دیگر از روش­های ترکیبی است که در تشخیص سرطان استفاده می­ شود [۱۳]،[۱۴]،[۱۵]،[۱۶]. در راستای تلاش­ های ذکر شده، در این پایان نامه سعی بر آن است تا با بهره گرفتن از ترکیب الگوریتمFCM و الگوریتم خفاش از مزایای دو الگوریتم در حل مسائل خوشه­بندی بهره گرفته شود.
۱-۳-هدف تحقیق
هدف در این تحقیق این است که با بررسی الگوریتم­های موجود در زمینه خوشه­بندی، الگوریتمی ارائه گردد که تا حد قابل قبولی بتواند محدودیت­های موجود را پوشش دهد. برخی از محدودیت­های موجود را می­توان به شرح ذیل برشمرد:
کارایی برای پایگاه داده ­ها با حجم بالا
کشف خوشه ­ها با اشکال مختلف
عدم حساسیت به ترتیب داده ­های ورودی
قابلیت تفسیر و استفاده
۱-۴-اهمیت تحقیق
همزمان با افزایش سیستم­های پایگاه داده و ابزار­های متعدد برای ذخیره­ی حجم بالای داده ­ها نیاز به روش­های خودکار برای کشف دانش از درون داده ­ها کاملاً احساس می­شد. علاوه بر آن به دلیل هزینه­ بالای نیروی انسانی و مادی جهت انجام عملیات روی حجم انبوه داده ­ها ارائه روشهایی با کمترین دخالت کاربر ضروری بود. استخراج اطلاعات مناسب از میان انبوه داده‏ها و تبدیل آنها به دانش مورد نیاز سازمان­ها - به­ ویژه در تصمیم‌گیری‏های سازمانی - نیازمند استفاده از روش‏های نوین در این حوزه بود. داده ­کاوی^[۸] یکی از این ابزارهاست که به کشف دانش از پایگاه داده ­ها کمک می‏کند. می­توان گفت داده ­کاوی استخراج اطلاعـات معتبر، قابل فهم و قابل اعتماد از پایگاه داده ­های بسیار بزرگ است که به کشـف الگوهای پنهان و روابط مطمئن بین داده ­ها و استفاده از آن در تصمیم ­گیری کمک می­نماید. در حقیقت شناخت و دست­و­پنجه نرم کردن با داده ­ها یکی از اهداف مهم در داده ­کاوی است.
این فرایند از اواخر دهه ۹۰ مطرح شد و از سال ۱۹۹۵ به صورت جدی وارد مباحث آماری گشت و در حال حاضر جزء مهم­ترین ابزار بهره ­برداری مؤثر از انبوه داده ­ها می­باشد و اهمیت وجود آن هر روز افزایش می­یابد. به عبارت دیگر داده ­کاوی­­، علمی نسـبتاً جدید است که از انجام تحقیـقات در رشته­ های آمار، یادگیری ماشین و علوم کامپیوتر مخصوصاً مدیـریت پایگاه داده ­ها شکل گرفته است.
داده کاوی در سه حوزه مستقل از علوم مورد استفاده قرار می­گیرد:
آمار کلاسیک و الگوهای آماری
هوش مصنوعی
یادگیری خودکار و شبکه های عصبی