شبیه سازی مقاله خوشه بندی

شبیه سازی مقاله خوشه بندی

شبیه سازی مقاله خوشه بندی با عنوان :

 Clustering Analysis with Combination of Artificial Bee Colony Algorithm and k-Means Technique

سال چاپ: 2014

دانلود اصل مقاله 

روال کار مقاله:

یک الگوریتم جدید بنام KABC برای خوشه بندی ارائه شده است در این کار که از ترکیب الگوریتم Kmeans و الگوریتم ABC بدست امده است. الگوریتم Kmeans در بهینه های محلی گیر میکند و الگوریتم KABC برای رفع این مشکل ارائه شده است.

روال الگوریتم KABC بصورت زیر می باشد:

– مقدار دهی اولیه منابع غذا، یا ساخت تصادفی راه حل های اولیه  . در اینجا هر منبع غذا در واقع مراکز خوشه ها را  به ما خواهد داد.

– با الگوریتم Kmeans هر منبع غذایی را ارزیابی میکنیم .

– زنبور های کارگر را به سمت منابع غذا میفرستم

– حلقه تکرار الگوریتم شروع میشود که شامل مراحل زیر می باشد:

– تا زمان برقراری شرط پایان مراحل زیر را تکرار کن

• -هر زنبورکارگر یک منبع غذایی جدید در منبع غذایی خود تولید می کند و منبع بهتر را استخراج می کند.
• هر زنبور دیده ور یک منبع را وابسته به کیفیت راه حلش انتخاب می کند و یک منبع غذایی جدید رادر مکان منبع غذایی انتخاب شده تولید می کند و منبع بهتر را استخراج می کند.
• تعیین منبعی که باید متروک شود و تخصیص زنبورهای کارگر آن به عنوان دیده ور برای جستجوی منابع غذایی جدید.
• بخاطر سپردن بهترین منبع غذایی پیدا شده تا کنون.

تکرار مرحله های فوق تا زمانی که معیار توقف مقتضی شود.

در واقع میتوان گفت به این شکل عمل شده است که الگوریتم ABC استفاده شده را به این شکل تغییر داده ایم که هر راه حل نشان دهنده مراکز خوشه ها باشد و برای ارزیابی هر راه حل نیز از الگوریتم Kmeans استفاده کرده ایم.

در الگوریتم ارائه شده هر منبع غذایی یک مجموعه از مراکز خوشه را نمایش میدهد . بعنوان مثال اگر دیتا را بخواهیم در سه خوشه دسته بندی کنیم و دیتای ما نیز دارای 4 ویژگی باشد یک منبع غذایی بصورت یک بردار با 12 خانه نمایش داده میشود (3*4=12)  که 4 خانه اول ان نشان دهنده مرکز کلاستر اول، 4 خانه دوم ان نشان دهنده مرکز کلاستر دوم و 4 خانه سوم ان نیز نشان دهنده مراکز خوشه سوم می باشند

به این ترتیب جمعیت اولیه یا همان منابع غذا بصورت رندوم تولید میشوند.

برای ارزیابی هر منبع غذایی (هر راه حل) ، دیتای مورد نظر خود را با توجه به مراکز خوشه ای که ان راه حل به مامیدهد،با الگوریتم Kmeans ارزیابی میکنیم. یعنی مراکز خوشه ای را که راه حل به ما میدهد را بعنوان مراکز خوشه اولیه الگوریتم Kmeans در نظر میگیریم و الگوریتم Kmeans را اعمال میکنیم. در نهایت برای مشخص شدن دقت حاصل از خوشه بندی از معیار اعوجاج یا Distortion  استفاده میکنیم که این معیار بصورت زیر تعریف میشود:

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

برای ارزیابی روش پیشنهادی نیز از دیتاست های استاندارد موجود در مخزن UCI استفاده شده است و سه دیتاست با نام های IRIS و Wine و CMC مورد استفاده قرار گرفته اند که در ادامه هر سه را معرفی میکنیم

دیتاست IRIS : این دیتاست شامل 150 نمونه می باشد که هر نمونه نیز 4 ویژگی دارد و نمونه ها در سه کلاس دسته بندی شده اند.

دیتاست Wine : این دیتاست شامل 178 نمونه می باشد که هر نمونه نیز 13 ویژگی دارد و نمونه ها در سه کلاس دسته بندی شده اند.

دیتاست CMC : این دیتاست شامل 1473 نمونه می باشد که هر نمونه نیز 10 ویژگی دارد و نمونه ها در سه کلاس دسته بندی شده اند.

برای شبیه سازی نیز تنظیم پارامتر های الگوریتم بصورت زیر انجام شده است که اندازه جمعیت مساوی 10 و مقدار پارامتر Limit مساوی 100 و تعداد تکرار الگوریتم نیز مساوی 20 در نظر گرفته شده است

برای هر دیتاست به تعداد 100 بار الگوریتم را اجرا کرده ایم، ونتایج را در جدول ارائه کرده ایم که شامل بهترین نتیجه،بدترین نتیجه و میانگین نتایج می باشد.

جهت دریافت کد متلب مقاله فوق، و شبیه سازی انجام شده به همراه فایل توضیحات با ما تماس بگیرید. هزینه کار 100 هزارتومان می باشد.

09120563264