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

word قابل ویرایش
13 صفحه
دسته : اطلاعیه ها
8700 تومان

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

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

 

چکیده

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

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

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

 

١

.۱ مقدمه

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

در خوشهبندی کلاسیک، هر نمونه ورودی متعلق به یک و فقط یک خوشه است و نمی تواند عضو دو خوشه و یا بیشتر باشد. به عبـارتی خوشـههـا همپوشانی ندارند در حالیکه در خوشهبندی فازی یک نمونه میتواند متعلق به بیش از یک خوشه باشد. خوشهبندی فازی به کشف مـدلهـای فـازی از دادهها میپردازد. این مقاله به بررسی الگوریتمهایی که هدفشان استخراج خوشههای فازی از دادههای قطعی است، میپردازد. یکی از اولـین روشهـای خوشهبندی ﻓﺎزی که بر مبنای تابع هدف و استفاده از فاصله اقلیدسی بنا شده بود در سال ۱۹۷۴ توسط دان۳ ارایه و سپس توسط بزدک۴ تعمـیم داده شد. پس از آن یانگ۵ یک بررسی اجمالی روی روشهای خوشه بندی فازی انجام داد. سپس گوستافسون و کسل۶ در سال ۱۹۷۹ الگوریتم خوشهبندی فازی با استفاده از ماتریس کوواریانس فازی را ارائه نمودند. تلفیق رویکرد امکان در خوشهبندی فازی نخستین بار توسط کیم و ﻛﺮﻳﺸﻨﺎﭘﻮرام۷ در سـال

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

.۲ مفاهیم پایهای

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

.۱,۲ خوشهبندی

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

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

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

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

نظریه مجموعههای فازی برای اولین بار توسط پروفسور لطفیزاده در سال ۱۹۶۴ با هدف مدلسازی ابهامات و عدم قطعیت رویدادها مطرح گردید.

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

٢

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

.۳,۲ خوشهبندی فازی

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

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

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

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

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

.۱,۳ الگوریتم Fuzzy C-Means

نخستین نسخه این الگوریتم۱۰ در سال ۱۹۷۳ توسط دودا و ﻫﺎرت۱۱ ارائه شد که یک خوشهبندی دقیـق انجـام مـیداد.[۴] از آنجـاییکـه برخـی دادهها به خوشههای متعدد وابستگی داشتند، امکان قرار دادن آنها در یک خوشه وجود نداشت، بر اساس همین ایده دان نسخه فازی الگوریتم را ارائه نمود.[۵] الگوریتم بارها مورد بازبینی قرار گرفت تا در نهایت ارائه نسخه نهایی الگوریتم و نیز معرفی m بـه عنـوان fuzzifier توسـط بـزدک صـورت گرفت.[۶]

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

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

.۲,۳ الگوریتم Possibilistic C-Means

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

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

نقطه x1 از هر دو خوشه به یک فاصله است لذا درجه عضویتش به هر دو خوشه ۰,۵ است، این منطقی است، ولی مشکل وقتی پیش میآید که همان درجه تعلقات به x2 هم نسبت داده میشود. در حالیکه فاصله این دو نقطه از خوشهها به یک اندازه نیست. دلیل این موضوع نرمالسازی و لزوم برابر یک بودن مجموع درجات عضویت یک نقطه در خوشههای مختلف است. نرمال کردن درجات عضویت میتواند منجر به اثرات نامطلوب در ارائه دادههای پرت و دور از مرکز شود. اگر شرط نرمالسازی را در الگوریتم FCM آزاد کنیم، این اثرات نامطلوب هم کمتر خواهند شد. این رویکرد امکان نام دارد۱۰]،۹،.[۸ تابع هدف نیز کهقبلاً فقط مربع فواصل را حداقل مینمود با رویکرد امکان چندان موافق به نظر نمیرسد. با حذف شرط نرمالسازی با اخذ درجات عضویت صفر برای همه نقاط در هر خوشهای حداقل تابع هدف حاصل میشود و البته این معقول نیست که همه خوشهها خالی باشند.

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

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

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

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

.۱,۴ الگوریتم Gustafson-Kessel

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

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

.۲,۴ الگوریتم Fuzzy shell clustering

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

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

از الگوریتمهای این دسته میتوان به۱۶FCV اشاره نمود که برای تعیین خطوط، صفحات و ابرصفحات توسعه یافته اسـت. الگـوریتم۱۷AFCE کـه صورت تغییر یافته FCM وPCM است و اجزای متمایز خط را ۱۸ به خوشههای مختلف تخصیص میدهد. ترازهای دایرهای۱۹ را میتوان بـا اسـتفاده از Fuzzy C-Shells وFuzzy C-Spherical Shells یافت. این دسته الگوریتمها نمونههای با ذات متفاوت از سایر دادهها را بیرون میکشند و نیـاز بـه جایگزینی متر اقلیدسی با متر اصلاح شدهای برای اندازهگیری فاصله بین دادهها و نمونههـا دارنـد. الگـوریتم ۲۰FCQS قـادر بـه تـشخیص سـهمیهـا،

۴

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

.۳,۴ الگوریتم های خوشه بندی فازی مبتنی بر هسته

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

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

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

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

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

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

رویکرد نخست برای اولین بار در[۱۸] پیشنهاد و سپس در ۲۰]،[۱۹ توسعه یافت. رویکرد دوم در [۲۱] و رویکرد سوم در [۲۲] ارائه شـدند کـه رویکـرد آخر به هر داده وزنی اختصاص میدهد تا بتواند اثرات آنرا بر پارامترهای خوشه کنترل کند.

Fuzzifier Variants .2,5

کلاس دیگری از اشکال FCM مبتنی بر مطالعه fuzzifier هستند. این توان برای اینکه درجات عضویت به جای اتخـاذ دو مقـدار ۱}،{۰ در بـازه
۱]،[۰ مقدار بگیرند معرفی شد.[۲۳, ۲۴, ۲۵, ۲۶]

Cluster Number Determination Variants .3,5

الگوریتمهای خوشهبندی افرازی به دنبال افراز فازی بهینه دادهها به c خوشه هستند که c ورودی الگوریتم است. در اغلب موارد دادهکاوی واقعی، این پارامتر از پیش مشخص نیست و باید تعیین شود. از این دسته مطالعات میتوان به ۳۰]،۲۹،۲۸،[۲۷ اشاره نمود.

.۴,۵ صورتهای دیگر Possibilistic C-Means

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

.۱,۴,۵ دافعه خوشهای

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

۵

.۲,۴,۵ صور تغییر یافته PCM، مبتنی بر ترکیب FCM وPCM

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

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

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

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

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

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

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

مقالات کلاس ۱ ، %۵۸ کل مقالات بررسی شده سالهای ۲۰۰۰ الی ۲۰۰۹، مقالات کلاس ۲ که به بررسی تعداد بهینه خوشههـا (اعتبـار سـنجی)
میپردازند، %۱۱ کل مقالات و مقالاتی که به اصلاح یا بهبود مقالات موجود میپردازند، %۲۵ از کل مقالات مورد مطالعه را تـشکیل مـی دهنـد. در ایـن بین %۶ مقالات، متعلق به هر دو دسته ترکیبی و بهبود یا اصلاح الگوریتمهای موجود هستند.

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

.۷ نتیجه گیری

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

این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید
wordقابل ویرایش - قیمت 8700 تومان در 13 صفحه
سایر مقالات موجود در این موضوع
دیدگاه خود را مطرح فرمایید . وظیفه ماست که به سوالات شما پاسخ دهیم

پاسخ دیدگاه شما ایمیل خواهد شد