الگوریتم k-میانگین

سه تا نونوایی

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

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

اگه این رو اون‌قدر تکرار کنیم که دیگه هیچ‌کی نونواییش رو عوض نکنه، محله خودبه‌خود به سه تا خوشه تقسیم شده. این دقیقا k-میانگین هست؛ اینجا k برابر ۳.

دو قدم، تکرار

بیایم با عدد ببینیم. یه خیابون داریم با شش تا خونه، شماره‌ی ۱، ۲، ۳، ۸، ۹ و ۱۰. دو تا نونوایی می‌خوایم (k برابر ۲)، و بدشانسی آوردیم: اول کار یکی جلوی خونه‌ی ۱ هست و یکی جلوی خونه‌ی ۲.

1. دور ۱، قدم اول: خونه‌ی ۱ می‌ره نونوایی ۱. بقیه همه به نونوایی ۲ نزدیک‌ترن.
2. دور ۱، قدم دوم: نونوایی ۲ می‌ره وسط مشتری‌هاش: میانگین ۲، ۳، ۸، ۹ و ۱۰ می‌شه ۶٫۴.
3. دور ۲، قدم اول: حالا خونه‌ی ۲ و ۳ به نونوایی ۱ نزدیک‌ترن تا به ۶٫۴. پس جابه‌جا می‌شن.
4. دور ۲، قدم دوم: نونوایی‌ها می‌رن وسط: میانگین ۱ و ۲ و ۳ می‌شه ۲، و میانگین ۸ و ۹ و ۱۰ می‌شه ۹.
5. دور ۳: هیچ خونه‌ای عوض نمی‌شه. تموم شد: دو تا خوشه داریم.

کِی تموم می‌شه؟

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

عددی که هی کم می‌شه بالاخره یه جا می‌ایسته. پس k-میانگین همیشه تموم می‌شه: وقتی گروه‌ها دیگه عوض نشن. ولی تموم شدن یعنی بهترین جواب نیست؛ این رو قسمت بعد می‌بینیم.

شروع بد

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

توی شروع بد، دو تا مرکز افتادن توی خوشه‌ی پایینی و نصفش کردن، و یه مرکز مجبوره دو تا خوشه‌ی بالا رو با هم نگه داره. الگوریتم هم دیگه راهی برای بیرون اومدن نداره؛ تموم می‌شه، ولی با جواب بد.

راهش ساده‌ست: چون k-میانگین سریعه، چند بار با شروع‌های مختلف اجراش می‌کنن و جوابی رو برمی‌دارن که اون عدد جمع فاصله‌هاش کمتره. یه روش شروع زرنگ‌تر هم هست به اسم k-means++ که معمولا شروع خوبی می‌ده.

k چند باشه؟

k رو ما باید بدیم؛ الگوریتم خودش نمی‌فهمه چند تا خوشه هست. یه راه معروف: برای k‌های مختلف اجراش کنیم و جمع فاصله‌ها رو بکشیم:

هر چی k بیشتر، جمع فاصله‌ها کمتر؛ اگه هر نقطه یه خوشه باشه، صفر می‌شه! پس دنبال کمترین نیستیم. دنبال جایی هستیم که نمودار یهو صاف می‌شه، مثل آرنج دست. اینجا k برابر ۳. به این می‌گن روش آرنج.

ولی راستش «آرنج» دقیق تعریف نشده و همیشه هم معلوم نیست. برای همین معمولا کنارش به این هم نگاه می‌کنن که با هر k، خوشه‌ها چقدر به درد کار بعدی می‌خورن.

کجا جواب نمی‌ده

k-میانگین هر خوشه رو یه مرکز و دورش می‌بینه. پس خوشه‌های گرد و هم‌اندازه رو دوست داره. اگه شکل خوشه‌ها چیز دیگه‌ای باشه چی؟

اینجا دو تا خوشه‌ی واقعی داریم: یه حلقه و یه گروه وسطش. ولی k-میانگین با k برابر ۲، صاف از وسط نصفش کرده؛ چون هیچ مرکزی نمی‌تونه یه حلقه رو نشون بده. برای این جور شکل‌ها، روش‌هایی که دنبال پرپشتی هستن بهترن.

یه کم تاریخ هم بد نیست: ایده‌اش سال ۱۹۵۶ مطرح شد، الگوریتمی که امروز استفاده می‌شه سال ۱۹۵۷ برای فشرده کردن سیگنال ساخته شد، و اسم k-means سال ۱۹۶۷ روش گذاشته شد.

درس بعد یه کار دیگه‌ی بی‌نظارت: ساده کردن داده‌ای که ستون‌های خیلی زیادی داره؛ کاهش ابعاد.