الگوريتم های خوشه بندی فازی

1ـ1ـ1ـ الگوريتم Fuzzy C-Means

نخستين نسخه اين الگوريتم[1] در سال 1973 توسط دودا و هارت[2] ارائه شد كه يك خوشه‌بندی دقيـق انجـام می‌داد (Al- Zoubi, A. Hudaib, A. Huneiti ، 2008). ازآنجایی‌که برخـي داده‌ها به خوشه‌های متعدد وابستگي داشتند، امكان قرار دادن آن‌ها در يك خوشه وجود نداشت، بر اساس همين ايده دان نسخه فازي الگوريتم را ارائه نمود (Celebi ، 2009). الگوريتم بارها مورد بازبيني قرار گرفت تا درنهایت ارائه نسخه نهايي الگوريتم و نيز معرفي m به‌عنوان fuzzifier توسـط بـزدك صـورت گرفت (Borodovsky and J. McIninch ، 1993).

الگوريتم حاصل ابرهاي كروي از نقاط را در يك فضاي p-بعدي شناسايي می‌کند. اين خوشه‌ها به‌طور مفروض تقريباً هم‌اندازه هستند. هر خوشه بـا مركزش نمايش داده می‌شود. اين نحوه نمايش خوشه‌ها، مدل يا نمونه[3] نيز ناميده می‌شود، زيرا اغلب به‌عنوان نماينـده همـه داده‌های تخـصيص داده شده به خوشه انگاشته می‌شود. به‌عنوان يك متر براي فاصله، فاصله اقليدسي بين يك نقطه و يك نمونه مورد استفاده قرار می‌گیرد. در انتخاب مركـز خوشه، همان‌گونه كه از اسم الگوريتم پيداست مقدار ميانگين مورد استفاده قرار می‌گیرد. براي محاسبه مركز خوشه مجموع درجات عضويت هر عنصر به توان m در خودش به حاصل‌ضرب توان m درجه عضویت‌ها تقسيم می‌شود. مشكلي كه در ارتباط با اين الگوريتم مطرح است اين است كه الگوريتم نمی‌تواند خوشه‌هایی با اشكال و اندازه‌ها و چگالی‌های متفـاوت شناسـايي كند. براي شناسايي اشكال ديگر به‌جای ماتريس هماني در تعيين فاصله می‌تواند از ماتریس‌های ديگر بهره جست. مانند ماتريس قطري براي تـشخيص خوشه‌های بيضوي. از مزاياي اين الگوريتم، سهولت آن است كه منجر به كاهش زمان محاسباتي می‌شود. در عمل با تكرارهاي كمي می‌تواند بـه راه حلـي تقريباً نهايي رسيد.

1ـ1ـ2ـ الگوریتم Possibilistic C-Means

مشخصه نسبي بودن درجه عضويت احتمالي باوجود مناسب بودن در اكثر مواقع، گاه می‌تواند مشكلاتي ايجاد نمايد (Wang, W. Qiu and R. H. Zamar ، 2007). به‌عنوان نمونه‌ای از اين دسته مشكلات می‌تواند به مورد ذيل اشاره نمود:

نقطه x₁ از هر دو خوشه به يك فاصله است لذا درجه عضويتش به هر دو خوشه 0,5 است، اين منطقي است، ولي مشكل وقتي پيش می‌آید كه همان درجه تعلقات به x₂ هم نسبت داده می‌شود. درحالی‌که فاصله اين دو نقطه از خوشه‌ها به يك اندازه نيست. دليل اين موضوع نرمال‌سازی و لزوم برابر يك بودن مجموع درجات عضويت يك نقطه در خوشه‌های مختلف است. نرمال كردن درجات عضويت می‌تواند منجر به اثرات نامطلوب در ارائه داده‌های پرت و دور از مركز شود. اگر شرط نرمال‌سازی را در الگوريتم FCM بکارببریم، اين اثرات نامطلوب هم كمتر خواهند شد. اين رويكرد امكان نام دارد [خلیلیان و همکاران، 2010؛ Oyelade, O. Oladipupo and I. Obagbuwa ، 1992]. تابع هدف نيز كه قبلاً فقط مربع فواصل را حداقل می‌نمود با رويكرد امكان چندان موافق به نظر نمی‌رسد. با حذف شرط نرمال‌سازی با اخذ درجات عضويت صفر براي همه نقاط در هر خوشه‌ای حداقل تابع هدف حاصل می‌شود و البته اين معقول نيست كه همه خوشه‌ها خالي بمانند. پس بايستي جریمه‌ای در نظر گرفته شود تا درجات عضويت از صفر دور شوند (Bezdek, J. Keller, R. Krishnapuram, and N. Pal 1992).

1ـ1ـ3ـ الگوریتم‌های حاصل از تغيير در تابع فاصله

در هردو الگوريتم پایه‌ای عنوان‌شده در بخش قبل، فاصله بين داده‌ها[4] و مراكز خوشه‌ها با متر اقليدسي اندازه گرفته می‌شد. بـا ايـن متـر فقـط  می­توان به شناسايي خوشه‌های كروي پرداخت. با تغيير متر موردبحث، صورت‌های مختلفي براي حل مشكل تشخيص اشكال متفاوت ارائه‌شده اسـت كه در این بخش چند نمونه بیان‌شده كه شامل الگـوريتم Fuzzy shell clustering،Gustafson-Kessel و Kernel based algorithm می‌باشد. البته الگوريتم کلی‌تری نيز به نام Fuzzy relational clustering معرفی‌شده است كه ورودی‌اش يك ماتريس فاصله است (کارابوگا و اُزتورک، 2010).

1ـ1ـ4ـ الگوریتم Gustafson-Kessel

با جايگزين كردن فاصله اقليدسي با متر ديگري[5] (كه توسط يك ماتريس متقارن، معين و مثبت ایجادشده) در الگـوريتم FCM می‌تواند بـه شناسايي خوشه‌های بيضوي نيز دست يافت. اين پيشنهاد توسط گوستافسون و كسل در سال 1979 ارائه شد (بِزدِک، 1981).

در مقايسه با FCM در اين روش هر خوشه علاوه بر مركز خوشه توسط يك ماتريس متقارن، معين و مثبت مشخص می‌شود. اين مـاتريس بـراي هر خوشه يك نرم ايجاد می‌کند. بايد اين موضوع را هم در نظر گرفت كه با انتخاب دلخواه و اختياري ماتریس‌ها، فاصله‌ها می‌توانند به‌طور دلخـواه كوچك شوند. براي اجتناب از حداقل سازي تابع هدف با ماتریس‌های با ورودی‌های تقريباً صفر، نياز به مقداري ثابـت بـراي خوشه‌ها بـا ماتريـسي بـا دترمينان يك داريم. بنابراين حالا فقط شكل خوشه‌ها متغير است نه اندازه‌هایشان. اما گوستافسون و كسل اشكال متفاوت براي خوشه‌ها را نيـز مقـدور ساختند بدين ترتيب كه يك مقدار ثابت e براي هر ماتريس A معرفي كردند و در حالت كلي بايستي det(A)=e. اگرچه انتخاب ثابت‌ها نيز نياز به يك دانش پيشين در مورد خوشه‌ها دارد. اشكال بيضوي حاصل از GK در مورد مثال‌های يكسان با FCM كه اشكال كروي حاصـل می‌شد، خوشه‌بندی بهتري حاصل می‌کند، البته موضوع تجمع نقاط در مراكز خوشه‌ها در مورد خوشه‌بندی امكاني با GK نيز به‌صورت مسئله باقي می‌ماند. اگر داده‌ها بـا رويكرد امكان خوشه‌بندی شوند، فاكتورهاي توسعه براي خوشه‌ها می‌توانند براي تشخيص اشكال در تصاوير مورد استفاده قرار گيرند. موقعيت و جهـت را از مركز خوشه و ماتريس می‌تواند به دست آورد. كيفيت نتيجه حاصل از اين روش به‌شدت وابسته به داده‌های در دسترس است. در مقايسه بـا FCM هزینه‌های محاسباتي GK بسيار بيشتر است. يك روش پيشنهادي مؤثر در كاهش گام‌های تكرار و افزايش سرعت همگرايي، آغاز الگوريتم GK با نتايج حاصل از يك اجراي FCM می‌باشد.

1ـ1ـ5ـ الگوریتم Fuzzy shell clustering

الگوریتم‌هایی كه پیش‌ازاین به ذكر آن‌ها پرداختيم مناسب براي خوشه‌های فشرده محدب بودند بـه همـين دليـل الگوریتم‌های خوشه‌بندی یکپارچه[6] نيز ناميده می‌شوند. اين الگوریتم‌ها در كاربردهاي تحليل داده  مناسب و مفيد می باشند. اما خوشه‌بندی فازي يك كاربرد ديگر هـم در زمينـه تشخيص و تحليل تصوير دارد كه نياز به الگوریتم‌های متفاوتي را آشكار می‌سازد.

صورت‌های مختلفي از FCM و PCM براي تعيين خطوط، دواير و بیضی‌ها روي مجموعه داده‌های متناظر با زيـرسـاختارهاي پيچيـده پیشنهادشده است كه الگوریتم‌های shell clustering ناميده می‌شوند [بِزدِک و همکاران، 1999]. متر مورد استفاده در اين الگوریتم‌ها در حالت عمومي به‌صورت زير اسـت كـه در آن p مركز و r شعاع است.

از الگوریتم‌های اين دسته می‌تواند به FCV[7] اشاره نمود كه براي تعيين خطوط، صفحات و ابرصفحات توسعه‌یافته اسـت. الگـوريتم AFCE[8] که صورت تغییریافته FCM و PCM است و اجزاي متمايز خط را[9] به خوشه‌های مختلف تخصيص می‌دهد. ترازهاي دايره­اي[10] را   می­توان بـا اسـتفاده از Fuzzy C-Shells و Fuzzy C-Spherical Shells يافت. اين دسته الگوریتم‌ها نمونه‌های با ذات متفاوت از ساير داده‌ها را بيرون می‌کشند و نيـاز به جایگزيني متر اقليدسي با متر اصلاح‌شده‌ای براي اندازه‌گیری فاصله بين داده‌ها و نمونه‌ها دارنـد. الگـوريتم FCQS[11] قـادر بـه تـشخيص سهمی‌ها، هذلولی‌ها و خوشه‌های خطي است. همچنين تکنیک‌های ديگري[12] از shell clustering براي ساختارهاي ناهموار مانند مثلث‌ها و ساير چندضلعی‌ها توسعه‌یافته‌اند. (Chen, Y. Song, H. Bai, C.-J. Lin, E ، 1999؛ Hochbaum, and D. Shmoys ، 1999).

جدول 1: مطرح‌ترین الگوریتم‌ها در خوشه‌بندی فازي

[1] Hard C-Means, ISODATA Algorithm

[2] Duda & Hart

[3] prototype

[4] data point

[5] Mahalanobis

[6] Solid clustering algorithms

[7] fuzzy c-varieties

[8] Adaptive Fuzzy C-Elliptotypes Algorithm

[9] disjoint line segments

[10] circle contours

[11] Fuzzy C-Quadric Shells

[12] Fuzzy C-Rectangular Shells, Fuzzy C-2 Rectangular Shells