بخشی از مقاله
چکیده -در سالهای اخیر یک خوشه بند مقاوم با عنوان الگوریتم -Cمیانگین مرتب شده فازی - - FCOM ارائه شده است که عملکرد آن در صورت وجود نویز و داده پرت کاهش نخواهد یافت. هر چند این خوشه بند نیز مانند FCM نیازمند مقدار دهی اولیه مناسب مراکز خوشهها است که در غیر این صورت دچار واگرایی و یا کاهش سرعت همگرایی خواهد شد. در این مقاله به پیشنهاد یک خوشه بند جدید خواهیم پرداخت که از تلفیق خوشه بند FCOM و الگوریتم PSO وفقی تشکیل شده است.
در روش پیشنهادی برای هر خوشه، به جای یک مرکز، چندین مرکز تصادفی در نظر گرفته میشود که به این دلیل حساسیت آن در مقابل مقداردهی اولیه نامناسب مراکز خوشه ها کاهش خواهد یافت. همچنین بروز رسانی ماتریس تعلق دادهها به خوشهها با استفاده از PSO و FCOM انجام خواهد گرفت که باعث افزایش سرعت همگرایی و جلوگیری از واگرایی خواهد شد. جهت ارزیابی عملکرد، روش پیشنهادی و تعدادی خوشه بند پیشنهادی بر روی چند پایگاه داده شبیه سازی شده و واقعی اعمال شدهاند که نتیجه این آزمایشات، نشان دهنده قدرت روش پیشنهادی از نظر سرعت همگرایی و مقاومت آن در مقابل نویز و داده پرت است.
-1 مقدمه
خوشه بندی1 به معنای تقسیم داده ها به گروه هایی از اشیا مشابه است .[2 ,1] هر گروه، خوشه2 نام دارد که شامل اشیایی است که بین آنها شباهت - شباهتهایی - وجود دارد و از طرفی عدم شباهت هایی بین اعضای یک خوشه و خوشههای دیگر دیده میشود. باید توجه شود که خوشهبندی یک الگوریتم نیست، بلکه مسئلهای کلی است که میتواند توسط الگوریتم های مختلف که نگاههای گوناگونی نسبت به تعریف یک خوشه دارند حل شود. از معمول ترین این نگاه ها میتوان به فاصله کم3، مناطق متراکم و توزیع های آماری مشابه اشاره کرد .[3]
معروفترین روش از نگاه فاصله کم، خوشه بند BCمیانگین فازی4 - FCM - است. FCM در کاربردهای بسیاری مورد استفاده قرار گرفته است [4] که از آن جمله میتوان به روانشناسی و سایر علوم اجتماعی [5]، پزشکی [6]، بازیابی اطﻻعات [7] و استخراج داده [8] اشاره کرد. اگرچه که FCM بسیار مورد توجه و استفاده قرار گرفته است اما این خوشه بند از مشکلاتی نظیر حساسیت به مقدار دهی اولیه، نویز و داده پرت و همچنین همگرایی کند به ازاء برخی از پایگاه های داده رنج میبرد .[9]
در مقاله [10] با استفاده از تکنیک وزندهی به داده و بکاربردن معیارهای مقاوم در برابر نویز ،یک خوشهبند مقاوم با عنوان -cمیانگین مرتب شده فازی - FCOM - 5 ارائه شده است، هر چند که این خوشهبند در مقابل نویز مقاوم شده است اما هنوز از مشکلاتی نظیر حساسیت به مقدار دهی اولیه و همگرایی کند رنج میبرد. برای غلبه بر این دو مشکل متداول ترین راه حل ترکیب خوشه بند FCOM با الگوریتم های تکاملی مختلف است. در میان الگوریتم های تکاملی، الگوریتم بهینه سازی توده ذرات6 - PSO - بیش از سایر الگوریتم های تکاملی مورد استفاده قرار گرفته است. دلیل این انتخاب، قابلیت های اکتشاف و استخراج PSO است که همگرایی آن به جواب بهینه را تسریع میبخشد .[11]
در مقاله [12] به معرفی یک نوع توسعه یافته از الگوریتم FCM با نام FC-PFC پرداخته است که در آن بجای استفاده از مجموعه های فازی متداول از مجموعه فازی تصویر استفاده شده است. در این مقاله جهت تعیین تعداد خوشهها ی مناسب، از رویکرد هرس و جهت تکامل جوابها از الگوریتم PSO متداول استفاده شده است. در مقاله [13] از یک نوع خاص از الگوریتم PSO با عنوان خوشهبندی توده ذرات استفاده شده است. در این روش هر ذره مرکز یک خوشه را نشان میدهد که با استفاده از روابط PSO بروزرسانی میشود.
سپس از میان این جوابها، N تا از بهترین آنها به صورت تصادفی و با توجه با ارزیابیشان انتخاب شده و برای تعیین مراکز نهایی با یکدیگر تلفیق میشوند. در مقاله [14] از تلفیق دو الگوریتم FCM و FPSO جهت بروزرسانی ماتریس عضویت استفاده شده است. در این روش ابتدا الگوریتم FPSO برای یافتن ماتریسهای تعلق مناسب به صورت تکراری اجرا میشود تا به تکامل برسد. سپس جواب های پیدا شده، در اختیار الگوریتم FCM قرار میگیرد.
این روند تا زمانی ادامه پیدا میکند که تابع هدف به اندازه از پیش تعیین شده کاهش یابد و یا تعداد تکرار ها به تعداد از پیش تعیین شده برسند. در مقاله [15] روش مقاله [14] بهبود یافته است به طوری که به جای استفاده از الگوریتم PSO متداول، از نوع تطبیقی بهبود یافته - IDPSO - استفاده شده است که نسبت به PSO از سرعت همگرایی بیشتری برخوردار است .[11] در مقاله [16] جهت یافتن ماتریس تعلق دادهها از تلفیق الگوریتم های PSO و تکامل تفاضلی - DE - استفاده شده است.
دلیل این تلفیق ایجاد سرعت بالای همگرایی در یافتن جواب بهینه مسئله می-باشد .[17] در مقاله [18] بر خلاف روشهای قبلی روشی ارائه شده است که با استفاده از نوع Focal الگوریتم PSO مستقیما به تخمین مکان مراکز خوشه ها می پردازد. دلیل استفاده از این الگوریتم، غلبه بر مشکل پیچیدگی زمانی PSO معمولی در مواجه با ذرههای چند بعدی میباشد. در این مقاله هدف ارائه یک خوشه بند مبتنی بر ایده فازی است به طوری که بر خلاف خوشهبند ارائه شده تا کنون در این حوزه، از مشکلاتی نظیر واگرایی و حساسیت به وجود نویز و داده پرت در دادهها رنج نمیبرد. برای ارائه چنین خوشه بندی از تلقیق دو روش استفاده شده است. روش اول وزندهی به داده ها جهت مقابله با داده پرت و استفاده از معیارهای فاصله مقاوم در برابر نویز است.
در روش دوم نیز از الگوریتم تکاملی PSO تطبیقی جهت کمینه سازی تابع هدف خوشهبندی و یافتن جواب بهینه استفاده شده است. علت انتخاب PSO تطبیقی، قدرت این الگوریتم در جستجوی تصادفی فضای مسئله و داشتن خصوصیاتی نظیر اکتشاف و استخراج است که سرعت همگرایی را تسریع میکنند. در ادامه این مقاله ابتدا به بیان برخی از مفاهیم پایه نظیر خوشهبند FCOM و الگوریتم تکاملی PSO خواهیم پرداخت. سپس به معرفی روش پیشنهادی می پردازیم. در بخش چهارم جهت تاکید بر موثر بودن روش پیشنهادی، مقایساتی ب ین این روش با سایر روشهای مشابه از جمله PCM، - 3&0 و FCOM انجام خواهیم داد. این مقایسات بر روی پایگاه داده های مصنوعی و همچینن پایگاه داده های واقعی برگرفته شده از UCI صورت خواهد گرفت. در انتها نیز نتیجه گیری و ارائه پیشنهاداتی برای تحقیقات آینده ارائه شده است.
-2 مفاهیم اولیه
در این بخش ابتدا به معرفی خوشه بند FCOM خواهیم پرداخت و در ادامه به مرور الگوریتم PSO و نوع تطبیقی آن می-پردازیم.
1-2 خوشه بند FCOM
همانطور که در قسمت قبل بیان شد، FCM از معیار شباهت اقلیدسی میان دادهها و مراکز خوشه استفاده میکند. اگرچه که این معیار ساده و از نظر حجم محاسبات، مقرون به صرفه است اما در مقابل نویز و داده پرت مقاومتی ندارد. برای ایجاد مقاومت در مقابل نویز و داده پرت، روشی با عنوان خوشه بند -Cمیانگین مرتب شده فازی - FCOM - در مقاله [10] معرفی شده است، که در آن به جای استفاده از معیار فاصله اقلیدسی، از معیار های فاصلهای استفاده میشود که تا حدی در مقابل نویز مقاوم هستند .
