دانلود شبیه سازی مقاله بهینه سازی ازدحام ذرات آشفته برای خوشه بندی داده ها

خوشه بندی داده ها با PSO

تحلیل خوشه بندی، یک روش داده کاوی بسیار محبوب می باشد. در این فرآیند، گروه بندی یک مجموعه از اشیاء به چندین خوشه انجام می شود به گونه ای که اشیاء درون خوشه یکسان با همدیگر مشابه هستند، اما با اشیاء خوشه های دیگر، نامشابه می باشند. هنگامی که یک مجموعه از اشیاء با استفاده از الگوریتم خوشه بندی حاصل شدند، خوشه های حاصله را می توان برای آشکار سازی سازه ها یا ساختارهای ذاتی در داده ها مورد استفاده قرار داد. هدف تحلیل خوشه ای، دسته بندی خوشه ها به گروه هایی است که مقداری معنا در زمینه یک مسئله خاص دارند. به بیان دقیقتر، یک مجموعه الگو، که عموماً بوسیله بردارهای چند بعدی در یک فضای از پیش تعریف شده نشان داده می شوند، براساس شباهتشان درون خوشه ها وارد می شوند. اگر تعداد خوشه ها، K، از قبل معلوم باشد، خوشه بندی را می توان به صورت توزیع n شیء در یک فضای N بعدی بین K گروه، فرموله نمود، به نحوی که اشیاء درون یک گروه، از نظر ضوابط خاصی نسبت به گروه های دیگر، مشابه تر هستند. این شامل کمینه سازی تعدادی ضابطه بهینه سازی برونزاد می باشد.

الگوریتم های خوشه بندی بسیاری براساس روش های محاسبه تکاملی، می باشند، برای مثال، الگوریتم های ژنتیک؛ اما، بهینه سازی ازدحام ذرات بندرت برای حل مسئله خوشه بندی انتخاب می شود. فلوچارت معمول الگوریتم های ژنتیک با مقدار دهی یک مجموعه جواب های کاندید برای مسئله بهینه سازی شروع می شود. کاندیدها غالباً از طریق عملگرهای ژنتیک مانند انتخاب، تبادل ژنی و جهش ایجاد می شوند و به سمت یک جواب بهتر تکامل پیدا می کنند. بهینه سازی ازدحام ذرات (PSO) یک الگوریتم مبتنی بر جمعیت است. این نوع بهینه سازی، رفتار پرندگان در حال خوراک جویی یا ماهیان با حرکت دسته جمعی برای رسیدن به یک سیستم خود تکاملی را شبیه سازی و تقلید می کند. PSO به صورت خودکار به جستجوی جواب بهینه در فضای جستجو، با استفاده از فرآیند جستجوی غیراتفاقی، می پردازد.  بر اساس ماهیت متفاوت مسائل، یک تابع برازش، بهترین روش انجام این جستجو را مشخص و انتخاب می کند. این الگوریتم PSO سریعاً پرطرفدار شده است و در بسیاری از سیستم های قدرت الکتریکی، خوشه بندی داده ها، خوشه بندی دو شاخه ای داده های ریز آرایه، طراحی مهندسی و غیره، بکار گرفته شده است.

در این پروژه، از الگوریتم ACPSO برای خوشه بندی بردارهای داده ای برای شش مجموعه داده، استفاده کردیم. ACPSO از فواصل بین خوشه ای کمینه به عنوان یک معیار استفاده میکند و به دنبال مراکز خوشه داده ای مقاوم یا استوار در یک فضای اقلیدسی N بعدی می گردد. تحت همین معیار، PSO، NM-PSO، K-PSO و K-NM-PSO نیاز به تکرار بیشتری برای رسیدن به یک جواب بهینه جهانی نسبت به ACPSO دارد. الگوریتم K-means، تمایل به گیر افتادن در یک بهینه محلی، براساس انتخاب مراکز خوشه اولیه دارد. اگرچه روش معرفی شده از k-means و جستجوی محلی استفاده نمی کند، اما نتایج بدست آمده بهتر از نتایج دیگر الگوریتم های ترکیبی موجود در مقالات می باشند. نتایج تجربی نشان می دهند که ACPSO سریعتر از روش های دیگر، به نرخ خطای کمینه، دست می یابد، و بنابراین هزینه محاسباتی را کاهش می دهد. الگوریتم ACPSO ارائه شده در این پروژه را می توان هنگامی به کار گرفت که تعداد خوشه ها از قبل معلوم باشند و خوشه ها به وضوح تعریف شده باشند.

این شبیه سازی با استفاده از نرم افزار متلب (MATLAB) انجام شده و در ادامه نیز تعدادی از نتایج خروجی آن قرار داده شده است: