فهرست

الگوریتم خوشه بندی c میانگین:7

الگوریتم خوشه بندی c میانگین برای داده های نویزی:10

الگوریتم خوشه بندی c میانگین با استفاده از نمونه های برچسب گذاری شده:11

الگوریتم خوشه بندی c میانگین مبتنی بر آنتروپی:12

الگوریتم خوشه بندی c میانگین مبتنی بر آنتروپی برای داده های نویزی:13

الگوریتم خوشه بندی c میانگین با استفاده از یادگیری وزن ویژگی ها:14

معیارهای کارایی:16

مراجع:22

محصولات مرتبط

خوشه بندی[1] چیست؟

خوشه بندی یکی از شاخه های یادگیری بدون نظارت می باشد و فرآیند خودکاری است که در طی آن، نمونه ها به دسته هایی که اعضای آن مشابه یکدیگر می باشند تقسیم می شوند که به این دسته ها خوشه[2] گفته میشود. بنابراین خوشه مجموعه ای از اشیاء می باشد که در آن اشیاء با یکدیگر مشابه بوده و با اشیاء موجود در خوشه های دیگر غیر مشابه می باشند. برای مشابه بودن می توان معیارهای مختلفی را در نظر گرفت مثلا می توان معیار فاصله را برای خوشه بندی مورد استفاده قرار داد و اشیائی را که به یکدیگر نزدیکتر هستند را بعنوان یک خوشه در نظر گرفت که به این نوع خوشه بندی، خوشه بندی مبتنی بر فاصله[3] نیز گفته می شود. بعنوان مثال در شکل 1 نمونه های ورودی در سمت چپ به چهار خوشه مشابه شکل سمت راست تقسیم می شوند. در این مثال هر یک از نمونه های ورودی به یکی از خوشه ها تعلق دارد و نمونه ای وجود ندارد که متعلق به بیش از یک خوشه باشد.

شکل1: خوشه بندی نمونه های ورودی

بعنوان یک مشال دیگر شکل 2 را در نظر بگیرید در این شکل هر یک از دایره های کوچک یک وسیله نقلیه (شیء) را نشان می دهد که با ویژگی های وزن و حداکثر سرعت مشخص شده اند. هر یک از بیضی ها یک خوشه می باشد و عبارت کنار هر بیضی برچسب آن خوشه را نشان می دهد. کل دستگاه مختصات که نمونه ها در آن نشان داده شده اند را فضای ویژگی می گویند.

feature space

object

feature

cluster

label

شکل2: خوشه بندی وسایل نقلیه

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

خوشه بندی با طبقه بندی[4] متفاوت است. در طبقه بندی نمونه های ورودی برچسب گذاری شده اند ولی در خوشه بندی نمونه های ورودی دارای بر چسب اولیه نمی باشند و در واقع با استفاده از روشهای خوشه بندی است که داده های مشابه مشخص و بطور ضمنی برچسب گذاری می شوند. در واقع می توان قبل از عملیات طبقه بندی داده ها یک خوشه بندی روی نمونه ها انجام داد و سپس مراکز خوشه های حاصل را محاسبه کرد و یک بر چسب به مراکز خوشه ها نسبت داد و سپس عملیات طبقه بندی را برای نمونه های ورودی جدید انجام داد.

هدف از خوشه بندی چیست؟

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

خوشه بندی فازی چیست؟

برای درک بهترخوشه بندی فازی و الگوریتمهای مختلف آن لازم است تا ابتدا با مفهوم مجموعه های فازی و تفاوت آنها با مجموعه های کلاسیک آشنا شویم. در مجموعه های کلاسیک یک عضو از مجموعه مرجع یا عضوی از مجموعه A است یا عضو مجموعه A نیست. مثلا مجموعه مرجع اعداد حقیقی را در نظر بگیرید. عدد 2.5 عضو مجموعه اعداد صحیح نمی باشد حال آنکه عدد 2 عضو این مجموعه است. به زبان دیگر تعلق عدد 2.5 به مجموعه اعداد صحیح 0 است و تعلق عدد 2 به این مجموعه 1 است. در واقع می توان برای هر مجموعه یک تابع تعلق تعریف کرد که مقدار این تابع تعلق برای اعضای مجموعه 1 می باشد و برای بقیه 0. در مجموعه های کلاسیک مقدار این تابع تعلق یا 0 است یا 1. حال مجموعه انسان های جوان و پیر را در نظر بگیرید. سوالی که در اینجا مطرح می شود این است که آیا فردی با سن 25 جزء این مجموعه است یا خیر؟ سن 30 چطور؟ 35؟ همانطور که حدس زدید نمی توان بطور قطع و یقین مرزی برای انسان های جوان و پیر در نظر گرفت. دلیل آن هم این است که اگر فرضا 35 جوان محسوب شود 36 نیز می تواند جوان باشد و همینطور 37 و 38 و غیره . در واقع در اینجا با مفهوم عدم قطعیت[5] مواجه هستیم. ما خودمان نیز از عدم قطعیت در زندگی روزمره بارها استفاده کرده ایم مثلا هوای سرد، آب داغ و غیره. در واقع تمامی مثالهای بالا مثالهایی از مجموعه های فازی می باشند. تفاوت اصلی مجموعه های فازی و مجموعه های کلاسیک در این است که تابع تعلق مجموعه های فازی دو مقداری نیست (0 یا 1) بلکه می تواند هر مقداری بین 0 تا 1 را اختیار کند. حال مجموعه انسانهای جوان و پیر را در نظر بگیرید اگر 25 سال را سن جوانی در نظر بگیریم می توانیم به 25 تعلق 1 بدهیم و مثلا به 30 تعلق 0.8 و به 35 تعلق 0.75 و به 90 تعلق 0.1 را بدهیم. اگر اعضای یک مجموعه فازی تنها دارای تابع تعلق 0 و 1 باشند این مجموعه فازی یک مجموعه کلاسیک خواهد بود. نکته جالب توجه این است که مثلا سن 50 می تواند با تعلق 0.5 عضو مجموعه جوان باشد و با تعلق 0.5 عضو مجموعه پیر یعنی یک عضو مجموعه مرجع می تواند با درجه های تعلق مختلف عضو مجموعه های فازی تعریف شده روی مجموعه مرجع باشد.

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

شکل3: مجموعه داده پروانه ای

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

بعنوان یک مثال دیگر شکل 4 را در نظر بگیرید. در این شکل نمونه هایی که با علامت بعلاوه مشخص شده اند به بیش از یک خوشه تعلق دارند.

شکل4: خوشه بندی فازی داده

الگوریتم خوشه بندی c میانگین:

مشابه اگوریتم c میانگین کلاسیک در این الگوریتم نیز تعداد خوشه ها (c) از قبل مشخص شده است. تابع هدفی که برای این الگوریتم تعریف شده است بصورت زیر می باشد:

در فرمول فوق m یک عدد حقیقی بزرگتر از 1 است که در اکثر موراد برای m عدد 2 انتخاب می شود. X_k نمونه k ام است و V_i نماینده یا مرکز خوشه i ام است. U_ikمیزان تعلق نمونه i ام در خوشه k ام را نشان می دهد. علامت ||*|| میزان تشابه (فاصله) نمونه با (از) مرکز خوشه می باشد که می توان از هر تابعی که بیانگر تشابه نمونه و مرکز خوشه باشد را استفاده کرد. از روی U_ikمی توان یک ماتریس U تعریف کرد که دارای c سطر و n ستون می باشد و مولفه های آن هر مقداری بین 0 تا 1 را می توانند اختیار کنند. اگر تمامی مولفه های ماتریس U بصورت 0 و یا 1 باشند الگوریتم مشابه c میانگین کلاسیک خواهد بود. با اینکه مولفه های ماتریس U می توانند هر مقداری بین 0 تا 1 را اختیار کنند اما مجموع مولفه های هر یک از ستونها باید برابر 1 باشد و داریم:

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

مراحل الگوریتم:

مقدار دهی اولیه برای c، m و U⁰. خوشه های اولیه حدس زده شوند.
مراکز خوشه ها محاسبه شوند (محاسبه v_iها).
محاسبه ماتریس تعلق از روی خوشه های محاسبه شده در 2.
اگر ||Ul+1-Ul||£e الگوریتم خاتمه می یابد و در غیر اینصورت برو به مرحله 2.

برای مشاهده عملکرد خوشه بندی فازی به مثال زیر توجه کنید. در شکل زیر یک توزیع یک بعدی از نمونه های ورودی را آورده شده است.

شکل5: توزیع یک بعدی نمونه ها

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

شکل6: خوشه بندی کلاسیک نمونه های ورودی

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

شکل7: خوشه بندی فازی نمونه ها

مشاهده می کنید که در این حالت منحنی تابع تعلق هموارتر است و مرز بین خوشه ها بطور قطع و یقین مشخص نشده است. بعنوان مثال نمونه ای که با رنگ قرمز مشخص شده است با درجه تعلق 0.2 به خوشه A و با درجه تعلق 0.8 به خوشه B نسبت داده شده است.

نقاط قوت الگوریتم c میانگین فازی:

همیشه همگرا می شود.
بدون نظارت بودن الگوریتم.

نقاط ضعف الگوریتم c میانگین فازی:

زمان محاسبات زیاد است.
حساس به حدسهای اولیه میباشد و ممکن در مینیمم های محلی متوقف شود.
حساس به نویز میباشد.

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

جدول1: معیارهای تشابه بر اساس توابع فاصله مختلف

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

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

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

تابع هدفی که برای این خوشه بندی تعریف شده بصورت زیر میباشد:

با مینیمم کردن تابع فوق نسبت به u_ik داریم:

δ عدد ثابتی است که برابر است با فاصله مرکز خوشه نویز با تمامی نمونه ها. از آنجا که جمله اضافه شده به تابع هدف به v_i بستگی ندارد برای محاسبه مقادیر v_i می توان از فرمول ارائه شده برای الگوریتم c میانگین استفاده کرد.

اگر نمونه k ام نویز باشد جمله دوم فرمول فوق بزرگ می شود و میزان تعلق این نمونه به خوشه ها کم می شود و در نتیج میزان تعلق این نمونه به خوشه نویز افزایش می یابد.

با پیدا کردن یک مقدار مناسب برای δ این الگوریتم نتایج بهتری نسبت به روش c میانگین اولیه خواهد داشت.

الگوریتم خوشه بندی c میانگین با استفاده از نمونه های برچسب گذاری شده:

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

بردار b نیز بدین صورت تعریف می شود که اگر نمونه k ام برچسب داشته باشد =1b_k و در غیر اینصورتb_k=0 است وl_ikمولفه های ماتریس L می باشند که درجه تعلق نمونه های برچسب دار را نشان می دهند. ضریب α برابر نسبت n به M در نظر گرفته می شود. مشابه قسمتهای قبل با مشتق گرفتن از تابع هدف می توان فرمول های بروز رسانی u_ik ها را محاسبه کرد و همچنین برای محاسبه مراکز خوشه ها از فرمول ارائه شده در الگوریتم c میانگین استاندارد استفاده می شود. مراحل الگوریتم نیز مشابه مراحل خوشه بندی c میانگین استاندارد می باشد. در این نوع خوشه بندی ها اگر M=n باشد الگوریتم خوشه بندی را با ناظر و اگر M<n باشد الگوریتم را با ناظر جزئی و اگر M=0 باشد الگوریتم خوشه بندی را بدون ناظر گویند.

الگوریتم خوشه بندی c میانگین مبتنی بر آنتروپی:

تابع هدفی که برای این روش در نظر گرفته شده است بصورت زیر میباشد:

که در فرمول فوق n>0 می باشد. جمله اول فرمول فوق، جمله اول تابه هدف الگوریتم c میانگین فازی می باشد البته با مقدار m=1. جمله دوم فرمول –n برابر تابع E(U) زیر است:

به تابع E(U) تابع آنتروپی فازی گفته می شود و این تابع می تواند مقادیری بین 0 تا 1/c را اختیار کند. اگر خوشه ها را مجموعه های فازی در نظر بگیریم تابع آنتروپی فازی عدم قطعیت در اینکه آیا x_k به یک خوشه خاص تعلق دارد یا خیر را می رساند.

با مینیمم کردن تابع هدف تعیین شده برای این روش خواهیم داشت:

برای خوشه بندی مبتنی بر آنتروپی چند تابع آنتروپی فازی دیگر نیز تعریف شده است. مثلا می توان بجای استفاده از خود u_ik ها از متوسط u_ik ها برای n نمونه استفاده کرد.

اگر P_i را بصورت زیر تعریف کنیم:

می توان تابع آنتروپی فازی را بصورت زیر تعریف کرد:

الگوریتم خوشه بندی c میانگین مبتنی بر آنتروپی برای داده های نویزی:

با استفاده از تعاریف قسمت مربوط به “الگوریتم c میانگین برای داده های نویزی” تابع هدف این قسمت بصورت زیر تعریف می شود:

با مینیمم کردن تابع فوق نسبت به U_ik داریم:

اگر نمونه ورودی نویز باشد جمله دوم فرمول فوق مقدار یزرگی می شود و میزان تعلق این نمونه به خوشه های اصلی کم شده و در عوض میزان تعلق نمونه به خوشه نویز زیاد می شود.

برای محاسبه v_i می توانیم از فرمول ارائه شده برای قسمت خوشه بندی مبتنی بر آنتروپی استفاده کنیم.

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

در این روش ابتدا با استفاده از روشهای یادگیری میزان تشابه بین نمونه ها محاسبه می شود و سپس از روی تشابهات نمونه ها تابع هدف جدیدی برای الگوریتم c میانگین فازی ارائه می شود. برای محاسبه میزان تشابه نمونه ها می توان معیارهای مختلفی در نظر گرفت مانند فاصله اقلیدوسی. یکی از روشهایی که در این زمینه ارائه شده روشی است که آقای Wang و همکارانش ارائه نموده اند. در این روش میزان تشابه نمونه i و نمونه j بصورت زیر تعریف شده است:

در فرمول فوق فاصله اقلیدوسی وزن دار نمونه i و نمونه j می باشد.β ضریبی مثبت است که برای قرار گرفتن میزان تشابه در فاصله [0 1] استفاده شده است.

مقدار βاز معادله زیر بدست می آید:

در فرمول فوق d_ij فاصله اقلیدوسی نمونه i و نمونه j می باشد که اگر فرض کنیم که نمونه ها دارای s بعد هستند خواهیم داشت:

همچنین برای فاصله اقلیدوسی وزن دار داریم:

در واقع قسمت یادگیری این الگوریتم همان پیدا کردن بردار وزن w=(w₁,w₂,…,w_s) می باشد. برای محاسبه بردار وزن لازم است تا یک معیار برای ارزیابی میزان تشابه نمونه ها ارائه شود. تابع ارزیابی که آقای Wang و همکارانش در نظر گرفته اند بصورت زیر می باشد:

در فرمول فوق p_ij میزان تشابه نمونه i و نمونه j بر مبنای فاصله اقلیدوسی می باشد.

معیارهای کارایی:

همانطور که قبلا اشاره شد یکی از مهمترین مسایل در خوشه بندی انتخاب تعداد خوشه های مناسب می باشد. تعداد خوشه ای مناسب می باشد که 1) نمونه های موجود در یک خوشه تا حد امکان شبیه به یکدیگر باشند و 2) نمونه های متعلق به خوشه های متفاوت تا حد امکان با یکدیگر نامتشابه باشند. عبارات فوق را بدین صورت نیز بیان می کنند که خوشه ها باید ماکزیمم فشردگی[6] باشند و تا حد امکان جدایی[7] آنها نیز زیاد باشد. اگر تنها معیار فشردگی مورد استفاده قرار گیرد در آنصورت هر داده می تواند به صورت یک خوشه در نظر گرفته شود چرا که هیچ خوشه ای فشرده تر از خوشه ای با یک داده نمی باشد. اگر تنها معیار جدایی در نظر گرفته شود در آنصورت بهترین خوشه بندی این می باشد که کل داده ها را یک خوشه بگیریم با این فرض که فاصله هر خوشه از خودش صفر است. بنابراین باید از ترکیب دو معیار فوق استفاده شود. برای مشخص کردن تعداد درست خوشه ها توابع ارزیابی[8] مختلفی تعریف شده است که می توان با استفاده از آنها تعداد خوشه ها را برای مسایل مختلف مشخص کرد.

تابع ارزیابی ضریب افراز[9]

انتخاب تعداد خوشه های مناسب با ماکزیمم کردن تابع فوق بدست می آید. یعنی برای تعداد خوشه های مختلف خوشه بندی را اجرا می کنند و با استفاده از ماتریس تعلق بدست آمده مقدار تابع فوق را محاسبه می کنند. تعداد خوشه هایی که به ازای آن این تابع بیشترین مقدار را داشته است بعنوان تعداد خوشه های مناسب برای آن مساله مورد استفاده قرار می گیرد. مقدار تابع فوق بین 1/c و 1 می باشد.

تابع ارزیابی آنتروپی افراز[10]

انتخاب تعداد خوشه های مناسب با مینیمم کردن تابع فوق بدست می آید. تعداد خوشه هایی که به ازای آن این تابع کمترین مقدار را داشته است بعنوان تعداد خوشه های مناسب برای آن مساله مورد استفاده قرار می گیرد. مقدار این تابع بین 0 تا log₂c می باشد. یک حالت دیگر از این تابع نیز تعریف شده است که به تابع ارزیابی آنتروپی نرمال شده معروف است. در این تابع مقدار تابع ارزیابی فوق را بر لگاریتم تعداد خوشه ها (c) تقسیم می کنند.

نکته قابل توجه در مورد این دو تابع این است که زمانی که PC برابر 1 باشد PE برابر 0 خواهد بود و در این حالت خوشه بندی معادل خوشه بندی کلاسیک است. اگر PC برابر 1/c باشد PE برابر log2c خواهد بود که در این حالت خوشه بندی در فازی ترین حالت خود خواهد بود. از طرف دیگر گفته شد که باید برای رسیدن به حالت خوشه بندی مطلوب PC ماکزیمم شود و PE می نیمم. بنابراین در خوشه بندی های فازی سعی می شود تا خوشه ها به خوشه های کلاسیک نزدیکتر باشند.

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

تابع Fukuyama and Sugeno

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

تابع Xie and Beni

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

تابع N.Zahid

آقای N.Zahid و همکارانش تابع ارزیابی دیگری را معرفی کرده اند که مبتنی بر معیارهای فشردگی و جدایی خوشه می باشد.

انحراف فازی[11] نمونه k ام از مرکز خوشه V_iبصورت زیر تعریف می شود:

تغییرات خوشه فازی U_iبصورت زیر تعریف شده است:

کاردینالیتی فازی خوشه U_i نیز بصورت زیر تعریف شده است:

با استفاده از تعاریف فوق میتوان میزان فشردگی خوشه فازی U_i را بصورت زیر تعریف کرد:

فشردگی کلی تمامی خوشه ها بصورت زیر تعریف شده است:

برای تعریف تابع ارزیابی لازم است تا معیار جدایی خوشه ها را نیز تعریف شود که آقای N.Zahid و همکارانش جدایی خوشه ها را بصورت زیر تعریف کرده اند:

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

انتخاب تعداد خوشه های مناسب با ماکزیمم کردن تابع فوق بدست می آید.

تابع M.Ramze Rezaee

آقای Ramze Rezaee و همکارانش تابع دیگری را برای ارزیابی الگوریتم خوشه بندی c میانگین ارائه داده اند. روش آنها مبتنی بر معیارهای جدایی و فشردگی خوشه ها می باشد که در ادامه روش مورد نظر آورده شده است.

فرض کنید که داده های ورودی p بعدی باشند و می خواهیم آنها را به c خوشه گروهبندی کنیم:

خوشه ها با v_i مشخص می شوند و میزان تعلق نمونه ها با خوشه ها نیز با ماتریس U نشان داده می شود. اگر واریانس نمونه های X را R^p (x)σدرنظر بگیریم برای p امین مولفه واریانس خواهیم داشت:

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

اگر تغییرات خوشه i ام را R^p (v_i)σ در نظر بگیریم برای p امین مولفه تغییرات خواهیم داشت:

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

همچنین یک تابع فاصله نیز بصورت زیر تعریف شده است:

که برای D_maxو D_min داریم:

که در واقع فرمول فوق ماکزیمم(می نیمم) فاصله بین مراکز خوشه ها را محاسبه می کند. از روی فرمول های فاصله و پراکندگی آقای Ramze Rezaee و همکارانش تابع ارزیابی را بصورت زیر تعریف کرده اند:

جمله اول فرمول فوق متوسط پراکندگی خوشه ها را نشان می دهد که هر چه این مقدار کوچک باشد نشان دهنده این است که خوشه ها فشرده تر هستند. اما همانطور که قبلا گفته شد این جمله بتنهایی نمی تواند معیار خوبی برای خوشه بندی باشد و باید جدایی خوشه ها نیز در نظر گرفته شود که این معیار توسط جمله دوم فرمول فوق محقق می شود. ضریب α نیز که برابر است با D(c_max) برای متعادل کردن دو جمله بکار گرفته شده است. الگوریتم پیدا کردن تعداد خوشه های بهینه بصورت زیر می باشد:

فرض کنید که تعداد خوشه های بهینه بین c_min و c_max باشد. تابع ارزیابی فوق را برای تمامی مقادیر بین c_min و c_max محاسبه و ذخیره می کنیم. مقدار c متناظر می نیمم مقادیر ذخیره شده تعداد خوشه های بیهنه خوشه بندی می باشد.

مراجع:

Tariq Rashid: “Clustering”
http://www.cs.bris.ac.uk/home/tr1690/documentation/fuzzy_clustering_initial_report/node11.html
Osmar R. Zaïane: “Principles of Knowledge Discovery in Databases – Chapter 8: Data Clustering”
http://www.cs.ualberta.ca/~zaiane/courses/cmput690/slides/Chapter8/index.html
Pier Luca Lanzi: “Ingegneria della Conoscenza e Sistemi Esperti – Lezione 2: Apprendimento non supervisionato”
http://www.elet.polimi.it/upload/lanzi/corsi/icse/2002/Lezione%202%20-%20Apprendimento%20non%20supervisionato.pdf
M. Halkidi, Y. Batistakis and M. Vazirgiannis, “On Clustering Validation Techniques“, Journal of Intelligent Systems, vol. 17:2/3, pp 107-145, 2001.
George E. Tsekouras and Haralambos Sarimveis, “A new approach for measuring the validity of the fuzzy c-means algorithm“, Advances in Engineering Software 35 (2004) 567–575.
N. Zahid, M. Limouri and A. Essaid, “A new cluster-validity for fuzzy clustering“, Pattern Recognition 32 (1999) 1089-1097.
M. Ramze Rezaee, B.P.F. Lelieveldt, J.H.C. Reiber, “A new cluster validity index for the fuzzy c-mean“, Pattern Recognition Letters 19 1998 237–246.
Bezdek, J.C., 1981. “Pattern Recognization with Fuzzy Objective Function Algorithms“. Plenum press, New York.
Bezdek JC. “Fuzzy mathematics in pattern classification“. PhD dissertation, Cornell University, Ithaca, NY; 1973.
S.L. Chiu, “Fuzzy model identification based on cluster estimation“, J. Intell. Fuzzy Systems 2 (1994) 267- 278.
J. Yao, M. Dash, S.T. Tan, H. Liu, “Entropy-based fuzzy clustering and fuzzy modeling“, Fuzzy Sets and Systems 113 (2000) 381_388.
Dat Tran and Michael Wagner, “Fuzzy Entropy Clustering“, University of Canberra, ATC 2601, Australia.
Xizhao Wang, Yadong Wang and Lijuan Wang, “Improving fuzzy c-means clustering based on feature-weight learning“, Pattern Recognition Letters 25 (2004) 1123–1132.
George E. Tsekouras and Haralambos Sarimveis, “A new approach for measuring the validity of the fuzzy c-means algorithm“, Advances in Engineering Software 35 (2004) 567–575.

[1] Clustering

[2] Cluster

[3] Distance-based Clustering

[4] Classification

[5] Uncertainty

[6] Compactness

[7] Separation

[8]Validation function

[9]Partition coefficient

[10]Partition entropy

[11] Fuzzy Deviation

لينك دانلود

دسته بندي فازي fuzzy clustering