نوشته سوم: کارایی متلب: الگوریتم خوشه‌بندی کا-مینز

من در بخش‌های قبل از الگوریتم خوشه‌بندی کا-مینز در محیط یک سری چیا گفتم، در اینجا آن را ساده‌تر می‌گم

کا-مینز  ساده‌ترین و گسترده‌ استفاده‌ترین الگوریتم خوشه‌بندی است. توصیفات جزئی این الگوریتم را می‌توانید از این نوشتار بیابید.

تعین مجموعه نقاط اولیه کا مین، این الگوریتم با جا به جا شدن میان دو گام تا زمانی که پوشش برسد جا به جا میشه

۱) گام ارزیابی، ارزیابی هر نقطه نمونه با اندازه‌گیری نزدیکی فاصله آن به خوشه

۲) گام به روز رسانی: محاسبه مین‌های جدید برای قرار دادن آنها به عنوان مراکز نقاط جدید در خوشه

این الگوریتم فرض می‌کند زمانی که تغییر در تابع ارزیابی حاصل نشد، پوشش حاصل شده است.

یک تابع خود ساخته شده کا-مینز در متلب وجود دارد، مجددا، آن بسیار کارا است. پیاده‌سازی آن در متلب بسیار ساده است. یک چیزهایی مثل پایین:

while !converged   for each point     assign label   end   for each cluster     compute mean   end end

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

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

[~,label] = min(sqDistance(M,X),[],1);

جایی که اِم ماتریس مین و ایکس ماتریس نمونه است. تابع sqDistance  یک تابع یک خطی است

function D = sqDistance(X, Y)
 D = bsxfun(@plus,dot(X,X,1)',dot(Y,Y,1))-2*(X'*Y);

برای هدف ما (یافتن نزدیکترین همسایه)، ما نیاز به محاسبه ضرب داخلی برای نقاط نمونه‌ در هنگام محاسبه ارزیابی نداریم. ما می‌توانیم آن را پیش محاسبه کنیم. کمی تحلیل بیشتر، ما می‌توانیم ببینیم که حتی در کل به محاسبه آن نیاز نداریم، چون روی رتبه بندی تاثیر نمی‌گذارد. بنابراین می‌توانیم گام ارزیابی را به صورت زیر بنویسیم:

[~,label] = max(bsxfun(@minus,m'*X,dot(m,m,1)'/2),[],1);
 فعلا این را بیشتر ادامه نمی‌دهم، چون این پیشرفته است. و باید اول از همه بدانیم این الگوریتم چطور در متلب کار می‌کنه و بعد بریم کاراش کنیم. پس این را می‌سپاریم به بعدها

دیدگاه‌تان را بنویسید: