خوشه بندی k_mean

یکی از پر کاربرد ترین و ساده ترین الگوریتم های دسته بندی بدون نظارت، خوشه بندی k- میانگین (k-mean clustering) می باشد. با توجه به توضیحات داده شده در آشنایی با الگوریتم knn (نزدیک ترین همسایه) با مفهوم محاسبه فاصله در داده های آموزشی آشنا شده ایم.

این روش خوشه بندی به دو روش مطرح می شود

1. تعداد دسته های داده مشخص است
2. تعداد دسته های داده نامشخص است

می توان به الگوریتم خوشه‌بندی k-میانگین به چشم یک مساله بهینه‌سازی نگاه کرد. که هدف از خوشه‌بندی داده ها کمینه‌سازی یا بیشینه‌سازی تابع هدف مشخصی می باشد.در صورتی که تابع هدف میزان فاصله (Distance Measure) بین داده ها باشد، مساله کمینه‌سازی خواهد بود و در حالتی که هدف یافتن شباهت (Dissimilarity Function) داده ها باشد، مساله بیشینه سازی خواهد بود.

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

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

با فرض داشتن دو دسته داده (k=2) به صورت زیر مراحل زیر را دنبال می کنیم :

1. k مرکز خوشه (در اینجا داده ها دو بعدی می باشد [x0,y0]) به صورت تصادفی انتخاب می کنیم. (برای این مثال دو مرکز داده به تصادف انتخاب می شود)

2. با محاسبه فاصله همه داده ها از مراکز دو خوشه، می توانیم آنها را به خوشه یک یا دو اختصاص دهیم (داده به آن خوشه ای اختصاص میابد که کمترین فاصله را از مرکز آن خوشه داشته باشد به عنوان مثال شماره یک به کلاس سبز نزدیک تر است و شماره دو به کلاس آبی تعلق می پذیرد)

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

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

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

5. نتیجه نهایی به صورت زیر خواهد بود. داده ها در این حالت به دو دسته متفاوت تقسیم شده اند.

مزایای K-Means

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

معایب K-Means

• نیاز به تعیین k: تعداد خوشه‌ها باید از قبل مشخص شود.
• حساس به مقداردهی اولیه: نتیجه به انتخاب اولیه مراکز خوشه بستگی دارد.
• حساس به نویز و پرت‌ها: داده‌های پرت می‌توانند خوشه‌بندی را خراب کنند.
• نامناسب برای خوشه‌های غیرکروی: برای اشکال پیچیده کارایی ندارد.
• عدم پشتیبانی از داده‌های دسته‌ای: نیاز به پیش‌پردازش برای داده‌های غیرعددی.
• مشکل در ابعاد بالا: در داده‌های با ابعاد زیاد دقت کاهش می‌یابد.

کد متلب خوشه بندی k_mean

با توجه به تئوری توضیح داده شد، می توانید با حلقه تکرار for و if این الگوریتم را پیاده سازی کنید. (کد متلب پایه موجود می باشد) اما در متلب توابع از پیش تعریف شده ای وجود دارد که به راحتی می تواند کار کد نویسی شما را ساده تر کند.
به مثال زیر توجه کنید:

X = [randn(100,2)*0.75+ones(100,2);
    randn(100,2)*0.5-ones(100,2);
    randn(100,2)*0.75];

برای تولید سه دسته داده تست با واریانس و میانگین متفات از الگوی sigma*randn()+mean استفاده شده است. هر ستون ماتریس x بیانگر یک دسته داده می باشد.

[idx,C] = kmeans(X,3);

با استفاده از دستور kmean الگوریتم را برای 3 دسته داده اجرا می کنیم.برای رسم نتایج از کد های زیر استفاده شده است.

figure
gscatter(X(:,1),X(:,2),idx,'bgm')
hold on
plot(C(:,1),C(:,2),'kx')
legend('Cluster 1','Cluster 2','Cluster 3','Cluster Centroid')

داده ها و مراکز داده در شکل زیر پس از اعمال الگوریتم k_mean نشان داده شده است.