بخشی از مقاله
چکیده
در این مقاله روشهای پیشنهادی بر روی 11 مجموعه داده استاندارد مورد آزمایش قرار گرفته است. این مجموعه دادها از لحاظ تعداد کلاس، تعداد ویژگی ها و همچنین تعداد نمونهها دارای حداکثر تنوع می باشند. علت انجام این کار این بود می خواهیم خروجی مطلوب تری را به دست آوردیم. برای ارزیابی پروژه از سه تابع مهم Nmi، Fm، Error و Ar استفاده شده است. این چهار تابع به عنوان معیار کارایی روش خوشه بندی مورد استفاده قرار گرفته شده اند. نرخ نمونه برداری 30 درصد بوده است که از روش نمونه برداری بدون جایگزینی استفاده شده است. برای اجرای هر نمونه Dataset برنامه 30 بار اجرا شده است و برای هر مجموعه داده، میانگین و انحراف معیار اندازه گیری شده است.
کلمات کلیدی: الگوریتم PSO، GA، K-means
مقدمه
به عنوان یکی از شاخههای وسیع و پرکاربرد هوش مصنوعی، یادگیری ماشین - - Machine learning به تنظیم و اکتشاف شیوهها و الگوریتمهایی میپردازد که بر اساس آنها رایانهها و سامانها توانایی تعلٌم و یادگیری پیدا میکنند. هدف یادگیری ماشین این است که کامپیوتر - در کلیترین مفهوم آن - بتواند به تدریج و با افزایش دادهها کارایی بهتری در انجام وظیفه مورد نظر پیدا کند. گستره این وظیفه میتواند از تشخیص خودکار چهره با دیدن چند نمونه از چهره مورد نظر تا فراگیری شیوه گامبرداری روباتهای دوپا با دریافت سیگنال پاداش و تنبیه باشد.
طیف پژوهش هایی که در یادگیری ماشینی میشود گستردهاست. در سوی نظری آن پژوهشگران بر آن هستند که روشهای یادگیری تازهای به وجود بیاورند و امکانپذیری و کیفیت یادگیری را برای روشهای خود مطالعه کنند و در سوی دیگر عده ای از پژوهش گران سعی میکنند روشهای یادگیری ماشینی را بر مسایل تازهای اعمال کنند. البته این طیف گسسته نیست و پژوهشهای انجامشده دارای مولفههایی از هر دو رویکرد هستند.
مسأله بهینه سازی شده
در مسأله بهینه سازی هدف این است که فاصله بین دادهها و مراکز خوشهها به کمترین مقدار ممکن کاهش پیدا کند. در واقع اگر بخواهیم مسأله خوشه بندی را بیان کنیم، آن را بصورت یک مسأله بینه سازی بیان می کنیم. مسأله بهینه سازی یک مسأله خیلی عمومی است.[5]
خوشه بندی ترکیبی
در حقیقت خوشه بندی ترکیبی، خوشه بندی است که تابع هدف فقط یک تابع هدف نیست و همچنین ممکن است از چند خوشه بندی گوناگون تشکیل شده باشد. در واقع هدف اصلی خوشهبندی ترکیبی1 جستجوی بهترین خوشهها با استفاده از ترکیب نتایج الگوریتمهای دیگر است 8]و.[27 اگر ما تابع هدفمان را متفاوت در نظر بگیریم یعنی اگر ما بیایم یک اجماع و یا جمعی از خوشه بندی را بسازیم ما دیگر می توانیم یک تابع هدف را در نظر نگیریم و چندین تابع هدف گوناگون را در نظر بگیریم. علت این کار این است که می خواهیم از آن مشکل تابع یک هدفه خارج شویم. به طور طبیعی اگر ما یک خوشه بندی و یک تابع هدف داشته باشیم، فقط همان تابع هدف را برای ما بهینه می کند. اما اگر به جای آن، چندین خوشه بندی که هر کدام یک تابع هدفی را بهینه می کنند را با هم ترکیب کنیم به شرط اینکه آن ترکیب متناسب انجام شود می توانیم ادعا کنیم که خوشه بندی ترکیبی ما چند تابع هدف را بهینه می کند.
الگوریتم ژنتیک
الگوریتم ژنتیک2 رهیافتی است که تکامل طبیعی موجودات را الگو قرار میدهد .[5] الگوریتم ژنتیک - GA - یکی از زیر مجموعههای محاسبات تکامل یافته می باشد که رابطه مستقیمی با بحث هوش مصنوعی دارد. محدوده کاری الگوریتم ژنتیک بسیار وسیع می باشد. با پیشرفت روز افزون علوم و تکنولوژی، استفاده از این الگوریتم در روش های بهینه سازی مسائل مهندسی روز به روز گسترش یافته است. همچنین الگوریتم ژنتیک یک روش بهینهسازی الهام گرفته از طبیعت جاندار - موجودات زنده - است که میتوان در طبقهبندیها، از آن به عنوان یک روش عددی، جستجوی مستقیم و تصادفی یاد کرد. این الگوریتم، الگوریتمی مبتنی بر تکرار است. الگوریتم ژنتیک برای به دست آوردن بهترین نتیجه بر روی یک سری از دادهها اعمال می شود در هر مرحله - نسل - به کمک فرایند انتخابی مناسب و با کمک عملگر های ژنتیک تفریب های از جواب نهایی به دست می آورد.
الگوریتم PSO
الگوریتم 3 PSO یک الگوریتم جستجوی اجتماعی است که از روی رفتار اجتماعی دسته های پرندگان مدل شده است. در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز هم زمان پرندگان و تغییر ناگهانی مسیر آن ها و تغییر شکل بهینهی دسته به کار گرفته شد. در PSO، ذرات4 در فضای جستجو جاری میشوند. تغییر مکان ذرات در فضای جستجو تحت تأثیر تجربه و دانش خودشان و همسایگانشان است. بنابراین موقعیت دیگر توده5 ذرات روی چگونگی جستجوی یک ذره اثر میگذارد. نتیجهی مدلسازی این رفتار اجتماعی فرایند جستجویی است که ذرات به سمت نواحی موفق میل میکنند.
انتخاب زیر مجموعه ای از مجموعه دادههای اصلی
در روش پیشنهادی
همانطور که گفته شد انتخاب زیر مجموعه ای از نمونهها به جای کل نمونهها دو مزیت دارد: -1کاهش میزان محاسبات -2 افزایش پراکندگی. در این گزارش برای انتخاب زیر مجموعه ای از دادهها نمونهها و یا دادههایی که در مرز تصمیم گیری خوشهها قرار دارند شانس بیشتر برای انتخاب شدن دارند. روش کار بدین صورت است که ابتدا الگوریتم k-Means را بر روی کل داده ها اجرا می کنیم، سپس نتیجه حاصل را با نتیجه به دست آمده از خوشه بندی ترکیبی اولیه مقایسه می کنیم. سپس برای انتخاب هر کدام را نمونهها در زیر پس از اینکه خوشه بندیهای اولیه به دست آمدند برای مجموعه انتخابی را به صورت فرمول 1 تغییر می دهیم. دست یابی به نتیجه نهایی باید از خوشه بندی ترکیبی استفاده کرد.
