یکی از پر کاربرد ترین و ساده ترین الگوریتم های دسته بندی بدون نظارت، خوشه بندی k- میانگین (k-mean clustering) می باشد. با توجه به توضیحات داده شده در آشنایی با الگوریتم knn (نزدیک ترین همسایه) با مفهوم محاسبه فاصله در داده های آموزشی آشنا شده ایم.
این روش خوشه بندی به دو روش مطرح می شود
- تعداد دسته های داده مشخص است
- تعداد دسته های داده نامشخص است
می توان به الگوریتم خوشهبندی k-میانگین به چشم یک مساله بهینهسازی نگاه کرد. که هدف از خوشهبندی داده ها کمینهسازی یا بیشینهسازی تابع هدف مشخصی می باشد.در صورتی که تابع هدف میزان فاصله (Distance Measure) بین داده ها باشد، مساله کمینهسازی خواهد بود و در حالتی که هدف یافتن شباهت (Dissimilarity Function) داده ها باشد، مساله بیشینه سازی خواهد بود.
در مثال آموزشی پیش رو هدف به دست آوردن کمینه فاصله بین داده ها و شاخص (میانگین) هر گروه می باشد. مسلما در این حالت تعداد گروه ها مشخص خواهد بود.
مراحل اجرای الگوریتم:
با فرض داشتن دو دسته داده (k=2) به صورت زیر مراحل زیر را دنبال می کنیم :
- k مرکز خوشه (در اینجا داده ها دو بعدی می باشد [x0,y0]) به صورت تصادفی انتخاب می کنیم.
2. با محاسبه فاصله همه داده ها از مراکز دو خوشه، می توانیم آنها را به خوشه یک یا دو اختصاص دهیم (داده به آن خوشه ای اختصاص میابد که کمترین فاصله را از مرکز آن خوشه داشته باشد)
3. محاسبه میانگین داده های هر خوشه و تعیین مرکز خوشه جدید.
4. پس از هر بار انجام این سه مرحله باید مجموع فاصله های درون خوشه ای است محاسبه شود و با مرحله قبلی مقایسه گردد. (آشنایی با توابع فاصله دیگر اینجا مطالعه کنید)
اگر رنج تغییرات از مقدار آستانه کمتر شود یعنی عملیات خوشه بندی با دقت کافی انجام شده است. بنابراین الگوریتم خاتمه می یابد. در غیر اینصورت باید عملیات از مرحله دوم از سر گرفته شود.
5. نتیجه نهایی به صورت زیر خواهد بود. داده ها در این حالت به دو دسته متفاوت تقسیم شده اند.
کد متلب خوشه بندی 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 نشان داده شده است.
