نحوه کار الگوریتم K-Means

خوشه‌ بندی k-means چگونه نقاط داده را جدا می‌کند؟ قدم اول بررسی داده خوشه‌ بندی نشده (Unclustered) بر روی نمودار پراکندگی و انتخاب دستی نقاط مرکزی (Centroids) برای هرکدام از خوشه‌ها است که در ادامه این نقاط مرکزی برای هر خوشه یک epicenter ایجاد می‌کنند.   در ابتدا می‌توان نقاط مرکزی را تصادفی انتخاب کرد که به آن معنی است که می‌توانید هر نقطه داده‌ای بر روی نمودار پراکندگی را کاندید کنید تا به‌عنوان نقطه مرکزی عمل کند. بااین‌حال، با انتخاب نقاط مرکزی پراکنده در سطح نمودار پراکندگی و نه در نزدیکی یکدیگر می‌توانید در زمان صرفه‌جویی کنید. به بیان دیگر، با حدس اینکه نقطه مرکزی برای هر خوشه کجا می‌تواند قرار بگیرد، شروع کنید. پس از آن نقاط داده باقی‌مانده بر روی نمودار پراکندگی به نزدیک‌ترین نقطه مرکزی که توسط فاصله اقلیدسی (Euclidean Distance) محاسبه می‌شود، تعلق می‌گیرد. محاسبه فاصله اقلیدسی را در زیر مشاهده می‌کنید.

هر نقطه داده تنها می‌تواند به یک خوشه تعلق بگیرد و خوشه‌ها گسسته خواهند بود پس هیچ‌گونه هم‌پوشانی بین خوشه‌ها وجود ندارد و در هیچ حالتی هیچ خوشه‌ای داخل خوشه دیگر جای نمی‌گیرد. همچنین، تمام نقاط داده حتی نقاط پرت، بدون توجه به اینکه شکل نهایی خوشه را چطور تحت‌تأثیر قرار می‌دهند به یک نقطه مرکزی تعلق می‌گیرند. بااین‌حال، به علت نیروی آماری (Statistical Force) که تمام نقاط داده نزدیک به هم را به یک نقطه مرکزی می‌کشاند، خوشه‌ها معمولاً شکلی بیضوی یا کروی می‌شوند. مثالی از یک خوشه بیضی در زیر مشاهده می‌شود.

پس از آنکه تمام نقاط داده به یک نقطه مرکزی اختصاص داده شدند، قدم بعدی، جمع تمامی مقادیر نقاط داده برای هر خوشه و میانگین‌گیری است – محاسبه میانگین مقادیر x و y تمام نقاط داده در هر خوشه. سپس از مقدار میانگین تمام نقاط داده در خوشه و مقادیر x و y آن، برای به‌روزرسانی مختصات نقطه مرکزی استفاده می‌کنید که به‌احتمال زیاد باعث جابه‌جایی محل فعلی نقطه مرکزی می‌شود. بااین‌وجود، تعداد کل خوشه‌ها، تغییری نخواهد کرد. خوشه‌های جدیدی نمی‌سازید، صرفاً محل آن‌ها را بر روی نمودار پراکندگی را به‌روزرسانی می‌کنید. اگر هر نقطه داده‌ای بر روی نمودار پراکندگی، با تغییر نقاط مرکزی، خوشه خود را تغییر بدهد، قدم قبلی دوباره تکرار می‌شود. این به معنای محاسبه دوباره متوسط میانگین مقادیر خوشه و به‌روزرسانی مقادیر x و y هر نقطه مرکزی است. هدف از این کار اعمال تغییرات میانگین مختصات نقاط داده روی هر خوشه است. زمانی که به مرحله‌ای برسید که پس از به‌روزرسانی مختصات نقطه مرکزی، نقاط داده خوشه‌های خود را تغییر نمی‌دهند، الگوریتم کامل می‌شود و مجموعه نهایی خوشه‌های خود را خواهید داشت. فرایند الگوریتمی کلی در زیر تشریح شده است. چند نقطه داده بر روی نمودار پراکندگی رسم شده‌اند.

دو نقطه داده به‌عنوان نقاط مرکزی کاندید شده‌اند.

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

مختصات نقطه مرکزی برای هر خوشه به‌روزرسانی شده تا نشان‌دهنده مقدار میانگین هر خوشه باشد. ازآنجایی‌که یک نقطه داده از خوشه راستی به خوشه چپی تغییر داشته است، نقطه مرکزی هر دو خوشه دوباره محاسبه می‌شوند.

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

در خوشه بندی k-means مقدار k چند باشد؟

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

بهینه‌سازی k در خوشه بندی k-means

به‌منظور بهینه‌سازی k، نمودار scree (شکل زیر) کمک‌کننده است. نمودار scree درجه پراکندگی (واریانس) در داخل یک خوشه را با افزایش تعداد کل خوشه‌ها نشان می‌دهد. یک مفهوم معروف در نمودارهای scree، “بازو (Elbow)” است که نشانگر پیچ‌های موجود در منحنی نمودار می‌باشد.

نمودار scree مجموع مربع خطا (SSE: Sum of squared error) برای ترکیب‌های مختلف از خوشه‌ها را مقایسه می‌کند. SSE به شکل مجموع مربع فاصله بین نقطه مرکزی و دیگر همسایگان داخل یک خوشه محاسبه می‌شود. نکته کلیدی این است که با افزایش تعداد خوشه‌ها، مقدار SEE کاهش می‌یابد.

تعداد بهینه خوشه‌ها در الگوریتم k-means

حالا یک سؤال مهم مطرح می‌شود که تعداد بهینه خوشه‌ها چیست؟ برای پاسخ به این سؤال بهتر است به سراغ نمودار رفته و به دنبال جایی در سمت چپ باشید که SSE به طور چشمگیری کاهش پیدا کرده باشد، اما از سمت راست، شاهد تغییرات ناچیز باشیم به صورتی که تقریباً منحنی به حالت ثابت رسیده باشد. برای مثال در شکل 10، مقدار SSE برای شش خوشه یا بیشتر، تغییرات اندکی می‌کند که باعث ساخت خوشه‌های کوچکی می‌شود که تمایز بین آن‌ها دشوار می‌شود. در این نمودار scree، دو یا سه خوشه به نظر گزینه ایده‌آلی است. در سمت چپ وقتی تعداد خوشه‌ها 2 باشد شاهد جهشی (Kink) بزرگ هستیم که می‌تواند یک نقطه مناسب برای drop-off باشد. در این حالت و با حرکت به سمت راست همچنان تغییرات کوچکی در مقدار SSE مشاهده می‌شود. این باعث اطمینان می‌شود که این دو خوشه متمایز هستند و بر روی دسته‌بندی داده تأثیر دارند.