فهرست

خوشه بندی چیست؟2

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

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

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

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

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

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

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

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

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

مراجع:22

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

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

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

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

شکل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 را در نظر بگیرید:

[1] Clustering

[2] Cluster

[3] Distance-based Clustering

[4] Classification

[5] Uncertainty