الگوریتم خوشه بندی KMeans

KMeans شاید ساده‌ترین الگوریتم خوشه‌ بندی هست که در بسیاری از مواقع  بهترین الگوریتم‌ های خوشه‌ بندی هست. این مورد از دسته الگوریتم‌هایی است که بایستی تعداد خوشه‌ها یا گروه‌ها را از قبل به او گفته باشیم. فرض کنید مانندِ درسِ شبکه های عصبی دو دسته داده داریم (اتوبوس و پراید) با این تفاوت که در یک مسئله‌ی خوشه‌ بندی، نمی‌دانیم که کدام پراید است کدام اتوبوس؟ و فقط یک سری داده با دو ویژگی (طول ماشین و ارتفاع ماشین) در اختیار داریم. اجازه دهید اینبار این دو دسته را بدون دانستنِ برچسبِ آن ها بر روی نمودار رسم کنیم  به صورت ساده، ما یک تعداد اتومبیل داریم که هر کدام ارتفاع و طولِ مشخصی را دارند. آن‌ها را به این گونه در دو بُعد در شکلِ زیر نشان می‌دهیم :

برای مثال، ماشین شماره‌ی ۴#، دارای  ارتفاع ۴ و طول ۹ است. در الگوریتم KMeans باید تعدادی نقطه در داخل فضا ایجاد کنیم. تعداد این نقطه ها باید به تعداد خوشه‌ هایی که می‌خواهیم در انتها به آن برسیم، باشد (مثلاً فرض کنید می‌خواهیم اطلاعات را به ۲ خوشه تقسیم‌ بندی کنیم، پس ۲ نقطه به صورت اتفاقی در فضای ۲ بُعدیِ شکلِ بالا رسم می‌کنیم). به شکل زیر را نگاه کنید:

الان ما دو نقطه‌ی سبز و قرمز را انتخاب کردیم و این دو نقطه را جایی در فضا (به صورت رندوم) قرار دادیم. حالا فاصله‌ ی هر کدام از نمونه‌ ها را با  دو نقطه حساب می‌کنیم. برای این کار قادر هستیم از فاصله منهتن ( manhatan ) استفاده کنیم . در واقع برای هر کدام از نمونه‌ها نسبت به دو نقطه‌ ی سبز و قرمز در هر بعد، مقایسه را انجام داده یعنی از هم کم (تفریق) می‌کنیم، سپس نتیجه‌ ی کم کردنِ هر کدام از بُعدها را با یکدیگر جمع میکنیم.

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

الان یک مرحله از الگوریتم را به اتمام رساندیم. یعنی یک دور از الگوریتم تمام شد و می‌توانیم همین جا هم الگوریتم را به اتمام برسانیم و نقاطی که سبز رنگ هستند را در خوشه‌ ی سبزها و نقاطی که قرمز رنگ شده‌ اند را در خوشه‌ی قرمز‌ها قرار دهیم. ولی الگوریتمِ KMeans را باید چندین بار تکرار کرد. ما هم همین کار را انجام می‌دهیم. برای شروع مرحله‌ ی بعد  باید نقطه‌ی سبز و قرمز را جا‌به‌جا کنیم و به جایی ببریم که میانگینِ نمونه‌های مختلف در خوشه‌ی مربوط به خودشان قرار دارد. مثلاً برای نقطه قرمز بایستی نقطه را به جایی ببریم که میانگینِ نمونه‌های قرمزِ دیگر (در مرحله‌ی قبلی) باشد. برای نقطه سبز هم همین طور. این کار را در شکل زیر انجام داده‌ایم:

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

دور دوم نیز به اتمام رسید و به نظر الگوریتم خوشه‌های خوبی را تشخیص داد. ولی صبر کنید یک دور دیگر نیز الگوریتم را ادامه دهیم. مانند شکل زیر دور سوم نیز انجام می‌شود. یعنی نقاطِ قرمز و سبز به مرکز خوشه‌ ی خود (در مرحله‌ی قبلی) می‌روند و  فاصله‌ی هر کدام از نمونه‌ها دوباره با نقاط قرمز و سبز (در محلِ جدید) محاسبه شده و هر کدام همرنگِ نزدیک‌ترین نقطه‌ی قرمز یا سبز می‌شود:

همان طور که می‌بینید در انتهای دور سوم، تغییری در خوشه‌ی هر کدام از نمونه‌ها رخ نداد. یعنی سبزها سبز ماندند و قرمزها، قرمز. این یکی از شروطی است که می‌تواند الگوریتم را خاتمه دهد. یعنی الگوریتم وقتی به این حالت رسید که در چند دور پشت سرهم تفاوتی در خوشه‌ی نمونه‌ها (در این‌جا ماشین‌ها) به وجود نیامد، به این معنی است که الگوریتم دیگر نمی‌تواند زیاد تغییر کند و این حالت پایانی برای خوشه‌ هاست. البته می‌توان شرطی دیگر نیز برای پایان الگوریتم در نظر گرفت. برای مثال الگوریتم حداکثر در ۲۰ دورِ متوالی می‌تواند عملیات را انجام دهد و دورِ ۲۰ام آخرین دور الگوریتم خواهد بود و الگوریتم، دیگر بیشتر از آن ادامه نخواهد یافت. به طور کل در الگوریتم‌های مبتنی بر تکرار (iterative algorithms) می‌توان تعداد تکرارها را محدود کرد تا الگوریتم بی‌نهایت تکرار نداشته باشد.

همان طور که دیدیم، این الگوریتم می‌تواند یک گروه‌بندی ذاتی برای داده‌ها بسازد، بدون اینکه برچسب داده‌ها یا نوع آن‌ها را بداند.

کاربردهای خوشه‌ بندی بسیار زیاد است. برای مثال فرض کنید می‌خواهید مشتریانِ خود را (که هر کدام دارای ویژگی‌های مختلفی هستند) به خوشه‌های متفاوتی تقسیم کنید و هر کدام از خوشه‌ها را به صورتِ جزئی مورد بررسی قرار دهید. ممکن است با مطالعه‌ی خوشه‌هایی از مشتریان به این نتیجه برسید که برخی از آن‌ها (که معمولاً در یک خوشه قرار می‌گیرند)، علیرغم خرید با توالیِ زیاد، در هر بار خرید پول کمتری خرج می‌کنند. با این تحلیل‌هایی که از خوشه‌بندی به دست می‌آید یک مدیرِ کسب و کار می‌تواند به تحلیل‌داده‌ها و سپس تصمیم‌گیریِ درست‌تری برسد.