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

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

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

چکیده

هدف از خوشهبندي فازي استخراج مدلهاي فازي از دادههاست. کاربردهاي متعدد خوشهبندي فازي در تحلیل دادهها و تشخیص الگو و نیز زمینه هاي پژوهشی موجود در این زمینه از جمله استفاده از آن در حل مسائل مسیریابی، تخصیص و زمانبندي نیاز به مطالعه الگوریتمهاي موجود و بهبود و اصلاح آنها را آشکارتر مینماید.

در این مقاله، پس از مرور اجمالی مفاهیم پایه اي خوشهبندي فازي، شامل مبحث خوشهبندي، نظریه مجموعههاي فازي و نهایتاً تعاریف پایهاي خوشهبندي فازي، به معرفی الگوریتمهاي اصلی و سپس الگوریتمهاي رایج که صورتهاي تغییریافتهي الگوریتمهاي اصلی هستند پرداخته شده و در بخش نهایی مروري اجمالی بر مقالات 10 سال اخیر(2000 الی (2009 ارائه شده است. هدف از این تحقیق ارائه یک دستهبندي براي الگوریتمهاي معرفی شده در زمینه خوشه بندي فازي است.

کلمات کلیدي
خوشهبندي، نظریه مجموعههاي فازي، خوشهبندي فازي.

١

.1 مقدمه

خوشهبندي از ابزارهاي متداول داده کاوي بوده که به استخراج دسته هایی با حداکثر شباهت بین عناصر داخل دسته و حداقل شباهت با عناصر سایر دستهها میپردازد. این تشابه یا عدم تشابه براساس معیارهاي اندازهگیري فاصله تعریف میشود. در واقع خوشهبندي یک کلاسبندي بدون نظارت است که در آن کلاسها از پیش تعریف نشدهاند. هدف از انجام خوشهبندي ارائه چشم انداز مناسبی از اتفاقات در حال وقوع در پایگاه داده ها به مصرف کنندة نهایی اطلاعات میباشد. کاربرد دیگر خوشهبندي را می توان در تعیین دادههایی که با سایر دادهها تفاوت چشمگیر دارند عنوان نمود.

در خوشهبندي کلاسیک، هر نمونه ورودي متعلق به یک و فقط یک خوشه است و نمی تواند عضو دو خوشه و یا بیشتر باشد. به عبـارتی خوشـههـا همپوشانی ندارند در حالیکه در خوشهبندي فازي یک نمونه میتواند متعلق به بیش از یک خوشه باشد. خوشهبندي فازي به کشف مـدلهـاي فـازي از دادهها میپردازد. این مقاله به بررسی الگوریتمهایی که هدفشان استخراج خوشههاي فازي از دادههاي قطعی است، میپردازد. یکی از اولـین روشهـاي خوشهبندي ﻓﺎزي که بر مبناي تابع هدف و استفاده از فاصله اقلیدسی بنا شده بود در سال 1974 توسط دان3 ارایه و سپس توسط بزدك4 تعمـیم داده شد. پس از آن یانگ5 یک بررسی اجمالی روي روشهاي خوشه بندي فازي انجام داد. سپس گوستافسون و کسل6 در سال 1979 الگوریتم خوشهبندي فازي با استفاده از ماتریس کوواریانس فازي را ارائه نمودند. تلفیق رویکرد امکان در خوشهبندي فازي نخستین بار توسط کیم و ﻛﺮﻳﺸﻨﺎﭘﻮرام7 در سـال

1993 صورت گرفت. پس از آن نیز اصلاحات و بهبودهاي بسیاري روي الگوریتمهاي ارائه شده صورت گرفتهاند که در این تحقیـق ﺑـﻪ برخـی از آنهـا خواهیم پرداخت. طبق دستهبندي صورت گرفته در این مقاله، الگوریتمهاي پایـهاي در زمینـه خوشـهبنـدي فـازي محـدود بـه Fuzzy C-Means8 و Possibilistic C-Means شد که از Hard C-Means که در ادبیات موضوع با عنوان الگوریتم k-Means معرفی شده است استخراج شده انـد. همـه الگوریتمهاي ارائه شده در این ﺑﺨﺶ مبتنی بر تابع هدف هستند که خوب بودن9 خوشهبندي را میسنجند.

.2 مفاهیم پایهاي

براي درك بهتر الگوریتم هاي خوشهبندي فازي آشنایی با مفاهیم پایهاي این مبحث ضروري به نظر میرسد. در این بخش به توضیحی مختصر در مورد مباحث خوشهبندي، نظریه مجموعههاي فازي و خوشه بندي فازي میپردازیم.

.1,2 خوشهبندي

هدف از خوشهبندي، تقسیمبندي دادههاي موجود به چند گروه بهقسمی است که دادههاي گروههاي مختلف حداکثر تفاوت ممکن را از هم داشـته باشند و دادههاي موجود در یک گروه بسیار به هم شبیه باشند. خوشه بندي با کلاسبندي تفاوت دارد و این تفاوت بـه برچـسب دار بـودن و نبـودن دستهها مربوط میشود. در خوشهبندي دسته ها از پیش معین نیستند.

دسته بنديهاي متفاوتی براي روشهاي خوشه بندي وجود دارد که رویکرد زیر جامع ترین دستهبندي این روشهاست:
• روشهاي افرازبندي
• روشهاي سلسله مراتبی
• روشهاي مبتنی بر چگالی
• روشهاي مبتنی بر شبکههاي مشبک
• روشهاي مبتنی بر مدل

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

.2,2 نظریه مجموعههاي فازي

نظریه مجموعههاي فازي براي اولین بار توسط پروفسور لطفیزاده در سال 1964 با هدف مدلسازي ابهامات و عدم قطعیت رویدادها مطرح گردید.

این نظریه عدم قطعیت غیراحتمالی را پشتیبانی میکند و به دنبال ارائه قالبی براي نمایش و مدیریت دانش مبهم و عدم قطعی است. در نظریه مجموعههاي فازي مرز قطعی و مشخصی براي مجموعه ها وجود ندارد و مانند مجموعههاي دقیق نمیتوان تابع مشخصه با برد صفر و یک تعریف نمود.

٢

عناصر میتوانند با درجات عضویت متفاوت به مجموعههاي مختلف تعلق داشته باشند. در نظریه مجموعههاي کلاسیک یک عنصر یا به مجموعهاي تعلق دارد یا اینکه در مجموعه مکمل آن عضویت دارد و هیچ عضویتی به مجموعه نامبرده ندارد در حالیکه با رویکرد فازي در نظریه مجموعهها یک عضو هم میتواند در مجموعه باشد و هم در مکمل آن.

.3,2 خوشهبندي فازي

خوشهبندي فازي را میتوان بخشی از تحلیل داده فازي دانست که داراي دو بخش است: یکی تحلیل دادههاي فازي و دیگري تحلیل داده هاي قطعی با استفاده از تکنیکهاي فازي. در این مطالعه به تحلیل دوم محدود خواهیم بود.

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

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

خوشهبندي فازي به کشف مدلهاي فازي از دادهها می پردازد. این مقاله به بررسی الگوریتم هایی که هدفشان استخراج خوشههاي فازي از داده هاي قطعی است، پرداخته است. یکی از اولین روشهاي خوشهبندي فازي که بر مبناي تابع هدف و استفاده از فاصله اقلیدسی بنا شده بود در سال 1974

توسط دان ارایه و سپس توسط بزدك تعمیم داده شد. پس از آن یانگ یک بررسی اجمالی روي روشهاي خوشه بندي فازي انجام داد. سپس گوستافسون و کسل در سال 1979 الگوریتم خوشهبندي فازي با استفاده از ماتریس کوواریانس فازي را ارائه نمودند. تلفیق رویکرد امکان در خوشهبندي فازي نخستین بار توسط کیم و کریشناپورام در سال 1993 صورت گرفت. پس از آن نیز اصلاحات و بهبودهاي بسیاري روي الگوریتمهاي ارائه شده صورت گرفتهاند که در این تحقیق به برخی از آنها خواهیم پرداخت.
طبق دستهبندي صورت گرفته در این مقاله، الگوریتم هاي پایهاي در زمینه خوشهبندي فازي محدود به Fuzzy C-Means و Possibilistic C-Means شد که از Hard C-Means که در ادبیات موضوع با عنوان الگوریتم k-Means معرفی شده است استخراج شده اند و در ادامه توضیح کاملتري از آنها ارائه خواهد شد. همه الگوریتمهاي ارائه شده در این بخش مبتنی بر تابع هدف هستند که خوب بودن خوشهبندي را میسنجند.

.1,3 الگوریتم Fuzzy C-Means

نخستین نسخه این الگوریتم10 در سال 1973 توسط دودا و ﻫﺎرت11 ارائه شد که یک خوشهبندي دقیـق انجـام مـیداد.[4] از آنجـاییکـه برخـی دادهها به خوشههاي متعدد وابستگی داشتند، امکان قرار دادن آنها در یک خوشه وجود نداشت، بر اساس همین ایده دان نسخه فازي الگوریتم را ارائه نمود.[5] الگوریتم بارها مورد بازبینی قرار گرفت تا در نهایت ارائه نسخه نهایی الگوریتم و نیز معرفی m بـه عنـوان fuzzifier توسـط بـزدك صـورت گرفت.[6]

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

مشکلی که در ارتباط با این الگوریتم مطرح است این است که الگوریتم نمیتواند خوشههایی با اشکال و اندازهها و چگالیهاي متفـاوت شناسـایی کند. براي شناسایی اشکال دیگر بهجاي ماتریس همانی در تعیین فاصله میتوان از ماتریسهاي دیگر بهره جست. مانند ماتریس قطري براي تـشخیص خوشههاي بیضوي. از مزایاي این الگوریتم، سهولت آن است که منجر به کاهش زمان محاسباتی میشود. در عمل با تکرارهاي کمی میتـوان بـه حلـی تقریباً نهایی رسید.

.2,3 الگوریتم Possibilistic C-Means

مشخصه نسبی بودن درجه عضویت احتمالی با وجود مناسب بودن در اکثر مواقع، گاه میتواند ایجاد مشکلاتی نماید.[7] به عنوان نمونهاي از این دسته مشکلات میتوان به مورد ذیل اشاره نمود.

شکل :1 ایراد وارد بر ٣درجه عضویت احتمالی

نقطه x1 از هر دو خوشه به یک فاصله است لذا درجه عضویتش به هر دو خوشه 0,5 است، این منطقی است، ولی مشکل وقتی پیش میآید که همان درجه تعلقات به x2 هم نسبت داده میشود. در حالیکه فاصله این دو نقطه از خوشهها به یک اندازه نیست. دلیل این موضوع نرمالسازي و لزوم برابر یک بودن مجموع درجات عضویت یک نقطه در خوشههاي مختلف است. نرمال کردن درجات عضویت میتواند منجر به اثرات نامطلوب در ارائه دادههاي پرت و دور از مرکز شود. اگر شرط نرمالسازي را در الگوریتم FCM آزاد کنیم، این اثرات نامطلوب هم کمتر خواهند شد. این رویکرد امکان نام دارد10]،9،.[8 تابع هدف نیز کهقبلاً فقط مربع فواصل را حداقل مینمود با رویکرد امکان چندان موافق به نظر نمیرسد. با حذف شرط نرمالسازي با اخذ درجات عضویت صفر براي همه نقاط در هر خوشهاي حداقل تابع هدف حاصل میشود و البته این معقول نیست که همه خوشهها خالی باشند.

پس بایستی جریمه اي در نظر گرفته شود تا درجات عضویت از صفر دور شوند.[10]

.4 الگوریتمهاي حاصل از تغییر در تابع فاصله

در هردو الگوریتم پایهاي عنوان شده در بخش قبل، فاصله ﺑﻴﻦ دادهها13 و مراکز خوشه ها با متر اقلیدسی اندازه گرفته میشـد. بـا ایـن متـر فقـط میتوان به شناسایی خوشههاي کروي پرداخت. با تغییر متر مورد بحث، صورتهاي مختلفی براي حل مشکل تشخیص اشکال متفاوت ارائه شـده اسـت که در اینبخش چند نمونه بیان شده که شامل الگـوریتم Gustafson-Kessel، Fuzzy shell clustering و Kernel based algorithm مـیباشـد.

البته الگوریتم کلیتري نیز به نام Fuzzy relational clustering معرفی شده است که ورودياش یک ماتریس فاصله است.[11]

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

با جایگزین کردن فاصله اقلیدسی با متر دیگري14 (که توسط یک ماتریس متقارن، ﻣﻌﻴﻦ و مثبت ایجاد شـده) در الگـوریتم FCM مـیتـوان بـه شناسایی خوشههاي بیضوي نیز دست یافت. این پیشنهاد توسط گوستافسون و کسل در سال 1979 ارائه شد. [12]
در مقایسه با FCM در این روش هر خوشه علاوه بر مرکز خوشه توسط یک ماتریس متقارن، معین و مثبت مشخص میشود. این مـاتریس بـراي هر خوشه یک نرم ایجاد میکند. باید این موضوع را هم در نظر گرفت که با انتخاب دلخواه و اختیاري ماتریسها، فاصلهها مـیتواننـد بـه طـور دلخـواه کوچک شوند. براي اجتناب از حداقل سازي تابع هدف با ماتریس هاي با وروديهايتقریباً صفر، نیاز به مقداري ثابـت بـراي خوشـه هـا بـا ماتریـسی بـا دترمینان یک داریم. بنابراین حالا فقط شکل خوشهها متغیر است نه اندازههایشان. اما گوستافسون و کسل اشکال متفاوت براي خوشهها را نیـز مقـدور ساختند بدین ترتیب که یک مقدار ثابت e براي هر ماتریس A معرفی کردند و در حالت کلی بایستی .det(A)=e اگرچه انتخاب ثابتها نیز نیاز به یک دانش پیشین در مورد خوشهها دارد. اشکال بیضوي حاصل از GK در مورد مثالهاي یکسان با FCM که اشکال کروي حاصـل مـیشـد، خوشـهبنـدي بهتري حاصل میکند، البته موضوع تجمع نقاط در مراکز خوشهها در مورد خوشهبندي امکانی با GK نیز به صورت مسئله باقی میماند. اگر دادهها بـا رویکرد امکان خوشهبندي شوند، فاکتورهاي توسعه براي خوشهها میتوانند براي تشخیص اشکال در تصاویر مورد استفاده قرار گیرند. موقعیت و جهـت را از مرکز خوشه و ماتریس میتوان بدست آورد. کیفیت نتیجه حاصل از این روش به شدت وابسته به دادههاي در دسترس است. در مقایسه بـا FCM

هزینههاي محاسباتی GK بسیار بیشتر است. یک روش پیشنهادي مؤثر در کاهش گامهاي تکرار و افزایش سرعت همگرایی، آغاز الگوریتم GK با نتایج حاصل از یک اجراي FCM میباشد.

.2,4 الگوریتم Fuzzy shell clustering

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

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

از الگوریتمهاي این دسته میتوان به16FCV اشاره نمود که براي تعیین خطوط، صفحات و ابرصفحات توسعه یافته اسـت. الگـوریتم17AFCE کـه صورت تغییر یافته FCM وPCM است و اجزاي متمایز خط را 18 به خوشههاي مختلف تخصیص میدهد. ترازهاي دایرهاي19 را میتوان بـا اسـتفاده از Fuzzy C-Shells وFuzzy C-Spherical Shells یافت. این دسته الگوریتمها نمونههاي با ذات متفاوت از سایر دادهها را بیرون میکشند و نیـاز بـه جایگزینی متر اقلیدسی با متر اصلاح شدهاي براي اندازهگیري فاصله بین دادهها و نمونههـا دارنـد. الگـوریتم 20FCQS قـادر بـه تـشخیص سـهمیهـا،

٤

هذلولیها و خوشههاي خطی است. همچنین تکنیکهاي دیگري21 از shell clustering براي ساختارهاي ناهموار مانند مثلثها و سایر چند ضـلعیهـا توسعه یافتهاند14]،.[ 1

.3,4 الگوریتم هاي خوشه بندي فازي مبتنی بر هسته

این دسته از الگوریتمها، تابع فاصله را براي کاربرد در دادههاي غیر برداري22 مانند دنبالهها، درختها یا گرافها بدون نیاز به تغییر کامل در خـود الگوریتم ها، اصلاح میکنند .[15, 16] درحالت کلی روشهاي مبتنی بر هسته مستقل از طبیعت داده و بدون نیاز به تطابق داده بکار بسته مـیشـوند.
اصول اولیه و تعاریف و مفاهیم پایهاي این روشها در [15] ارائه شده است.

بکار بستن قالب هسته براي خوشهبندي فازي استفاده از سـایر فاصـلههـا را ممکـن سـاخته اسـت. در بخـش قبـل دیـدیم کـه در fuzzy shell clustering هم مترهاي دیگري مورد استفاده قرار گرفت اما تفاوتی که وجود دارد این است که درآنها هدف استخراج نمونههـایی اسـت کـه از سـایر دادهها متفاوتند لذا به اصلاح فاصله بین آنها میپردازد. این در حالیست که در رویکرد هسته شـباهت بـین جفـت دادههـا محاسـبه مـیشـود و مراکـز خوشهها را در برنمیگیرد. رویکرد هسته مستقل از ذات داده میتواند به کار برده شود در حالیکه الگوریتمهاي fuzzy shell clustering باید مخـتص نوع نمونه باشد. روشهاي مبتنی بر هسته Prototype-Based نیستند.[17] بهکاربستن این روشها نیاز به انتخاب هسته و پارامترهاي آن دارد که کار دشواري است و مشابه مسأله انتخاب مشخصه23 و نماینده دادهها در روشهاي دیگر میباشد.

.5 الگوریتمهاي حاصل از تغییر در تابع هدف

در این بخش به بررسی الگوریتمهایی میﭘﺮدازﻳﻢ که به تغییرات اساسیتري در تابع هدف میپردازند و به دنبال بهبود نتایج خوشه بندي در مـوارد خاص هستند مانند حالتی که دادههاي پراکنده24 داریم. در ادامه به برخی از اشکال25 میپردازیم.

دسته اول از الگوریتمهایی که در این بخش به آنها اشاره خواهد شد آنهایی هستند که هدفشان به طور صریح مواجهه با دادههاي پراکنده است. دسته دیگر به مطالعه و اصلاح fuzzifier میپردازد. گروهی به معرفی اصطلاحات جدید در تابع هدف براي بهینهسازي تعداد خوشهها (به جاي داشتن آن به طور قطعی در ابتداي فرآیند) میپردازد نهایتاًو به ارائه بهبودهایی در PCM اشاره خواهد شد. البته حد و مرزي بین این دستهها وجـود نـدارد و تأثیرات متقابل میان آنها انکارناپذیر است.
Noise Handling Variants .1,5

هدف از ارائه این دسته، تعریف الگوریتمهاي خوشهبندي فازي قوي26 تري است که نتایج آن بستگی به حضور دادههاي پراکنده یا دور از مرکز در مجموعه دادهها ندارد. در این دسته سه روﻳﻜﺮد وجود دارد: اول noise clustering که به معرفی یک خوشه معین به نام خوشـه noise بـراي نمـایش دادههاي پرت میپردازد. دومین روش مبتنی بر استفاده از تخمین زنندههاي توانمند27 است و سومی اثر دادههاي پرت را با تعریف وزن کاهش میدهد.

رویکرد نخست براي اولین بار در[18] پیشنهاد و سپس در 20]،[19 توسعه یافت. رویکرد دوم در [21] و رویکرد سوم در [22] ارائه شـدند کـه رویکـرد آخر به هر داده وزنی اختصاص میدهد تا بتواند اثرات آنرا بر پارامترهاي خوشه کنترل کند.

Fuzzifier Variants .2,5

کلاس دیگري از اشکال FCM مبتنی بر مطالعه fuzzifier هستند. این توان براي اینکه درجات عضویت به جاي اتخـاذ دو مقـدار 1}،{0 در بـازه
1]،[0 مقدار بگیرند معرفی شد.[23, 24, 25, 26]

Cluster Number Determination Variants .3,5

الگوریتمهاي خوشهبندي افرازي به دنبال افراز فازي بهینه دادهها به c خوشه هستند که c ورودي الگوریتم است. در اغلب موارد دادهکاوي واقعی، این پارامتر از پیش مشخص نیست و باید تعیین شود. از این دسته مطالعات میتوان به 30]،29،28،[27 اشاره نمود.

.4,5 صورتهاي دیگر Possibilistic C-Means

از آنجاییکه PCM ممکن است منجر به نتایجی شود که رضایتبخش نباشد ( مانند پدیده خوشه هاي منطبق که دلیل آن تابع هدف بهینه شـده است که حداقل سرتاسري آن وقتی به دست میآید که همه خوشهها یکسان باشند) می توان آن را با اصلاح تـابع هـدف بهبـود بخـشید. در ادامـه بـه اختصار دو صورت اصلاح شده از PCM ، اولی مبتنی بر الحاق یک اصطلاح جریمه در تابع هدف و دومی ترکیب PCM وFCM ، ارائه میشود:

.1,4,5 دافعه خوشهاي

براي جلوگیري از ادغام خوشهاي، 32]،[31 پیشنهاد شمول عبارتی دادند که بیانگر دفع بین خوشهها باشد و به این ترتیـب خوشـه هـا مجبـور بـه تمایز باشند.

٥

.2,4,5 صور تغییر یافته PCM، مبتنی بر ترکیب FCM وPCM

در مقالات 34]،[33، رویکرد دیگري براي غلبه بر مشکل موجود در PCM ارائه شده است. رویکرد جدید هر دو درجـه امکـان و عـضویت را بـراي انجام خوشهبندي ضروري میانگارد. درجه امکان به کاهش اثر دادههاي دور از مرکز میانجامد در حالیکه درجه عضویت براي تخـصیص نقـاط ضـروري است. طبق [35] یک خوشهبندي خوب هم نیاز به مشخصه افراز بندي FCM و هم مشخصه تواناي جستجوي مدPCM 28 دارد.

.6 مروري بر مقالات سالهاي اخیر

همانگونه که در بخشهاي قبل عنوان شد، در دو دهه اخیر اصلاحات و بهبودهاي متعددي در الگوریتمهاي موجود در زمینه خوشهبنـدي فـازي صورت گرفته است و همچنین الگوریتمهاي جدیدي مبتنی بر الگوریتمهاي اصلی و یا از ترکیب این الگـوریتمهـا بـا سـایر الگـوریتمهـا (شـامل سـایر الگوریتمهاي خوشهبندي فازي و یا الگوریتمهاي دیگر مانند الگوریتمهاي تکاملی و...) ارائه شده است. بخشی از ادبیات موضـوع در بخـش قبـل و بـراي دستهبندي کلی مطالب عنوان شد و بخشی دیگر که از مطالعه مقالات سالهاي اخیر حاصل شده است در ادامه ارائه خواهد شد.

مقالات را میتوان در حالت کلی به دو دسته کاربردي و الگوریتمی تقسیمبندي نمود. این تقسیمبنـدي از آنجـایی ناشـی شـده اسـت کـه برخـی مقالاتصرفاً به استفاده از الگوریتمی در زمینهاي خاص پرداختهاند. در بررسی اجمالی مقالات کاربردي به یک دستهبندي کلی از این مقالات میرسیم که به صورت زیر میتوان به عنوان آن پرداخت:

9 مقالاتی که هدف اصلی آنها تعیین دادههاي دور از مرکز یا به عبارتی دادههاي پرت است.
9 مقالاتی کهصرفاً با هدف استخراج دستههایی مشابه از الگوریتمهاي خوشهبندي استفاده میکنند. این حالت میتواند پیش نیازي براي کلاسبندي در نظر گرفته شود.

براي مقالات الگوریتمی نیز سه کلاس در نظر گرفته شد:
کلاس :1 مقالاتی که به صورت ترکیب الگوریتمهاي خوشهبندي فازي با سایر الگوریتمها (شـامل سـایر الگـوریتمهـاي خوشـهبنـدي فـازي و یـا الگوریتمهاي دیگر مانند الگوریتمهاي تکاملی و...) هستند،

کلاس :2 مقالاتی که به بررسی تعداد بهینه خوشهها (اعتبار سنجی) میپردازند، کلاس :3 مقالاتی که به اصلاح یا بهبود یکی از مقالات موجود میپردازند.

مقالات کلاس 1 ، %58 کل مقالات بررسی شده سالهاي 2000 الی 2009، مقالات کلاس 2 که به بررسی تعداد بهینه خوشههـا (اعتبـار سـنجی)
میپردازند، %11 کل مقالات و مقالاتی که به اصلاح یا بهبود مقالات موجود میپردازند، %25 از کل مقالات مورد مطالعه را تـشکیل مـی دهنـد. در ایـن بین %6 مقالات، متعلق به هر دو دسته ترکیبی و بهبود یا اصلاح الگوریتمهاي موجود هستند.

خلاصهاي از مقالات الگوریتمی و کاربردي در پیوست 1 و 2 ارائه شدهاست.

.7 نتیجه گیري

خوشهبندي فازي از تلفیق رویکرد فازي در بحث خوشهبندي براي کاربرديتر نمودن آن و انطباق بیشتر با دنیاي واقعی حاصل شده است. در این مقاله به مروري بر الگوریتمهاي متداول خوشه بندي و به نوعی به خوشه بندي این الگوریتمها پرداختهایم. الگوریتمهاي رایج و کاربرديتر در جدول شماره 1 خلاصه شدهاند. آنچه در این تحقیق آمده است تکنیکهایی است که براي کشف مدلهاي فازي از داده هاي قطعی بهکار میرود و در کارهاي آتی میتوان بهمطالعه تکنیکهایی که براي دادههاي فازي توسعه یافتهاند، اقدام نمود. استفاده از روشهاي متاهیوریستیک براي بهبود نتایج خوشهبندي فازي نیز میتواند در لیست کارهاي آتی قرار گیرد.