الگوریتم K-Means

خوشه‌بندی داده‌ها رو بر اساس شباهتی که دارن، به طوری که داده‌های هر خوشه دارای بیشترین شباهت به هم و کم‌ترین شباهت به داده‌های خوشه‌های دیگه هستن، در یک خوشه قرار میده. الگوریتم K-Means یکی از الگوریتم‌های مورد استفاده در داده کاوی و یادگیری ماشینی هست که برای خوشه‌بندی(Clustering) یا دسته‌بندی بدون نظارت از اون استفاده میشه. KMeans  یکی از ساده‌ترین الگوریتمِ های خوشه‌بندی باشد. این الگوریتم از دسته الگوریتم‌هایی است که بایستی تعداد خوشه‌ها(گروه ها) را از قبل به او گفته باشیم. در ادامه نحوه کار این الگوریتم توضیح داده خواهد شد.

  

1-    باید تعداد خوشه‌هایی که مد نظر داریم رو مشخص کنیم.

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

3-    حال فاصله‌ی هر کدام از نمونه‌ها را با این دو نقطه حساب می‌کنیم. برای این کار می‌توانیم از فاصله منهتن(Manhatan) استفاده کنیم.

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

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

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

7-    الگوریتمْ وقتی به این حالت رسید که در چند دورِ متوالی تغییری در خوشه‌ی نمونه‌ها به وجود نیامد، یعنی الگوریتمْ دیگر نمی‌تواند زیاد تغییر کند و این حالتِ پایانی برای خوشه‌هاست. البته می‌توان شرطی دیگر نیز برای پایان الگوریتم در نظر گرفت. برای مثال الگوریتمْ حداکثر در nدورِ متوالی می‌تواند عملیات را انجام دهد و دورِ nام آخرین دورِ الگوریتم خواهد بود و الگوریتم دیگر بیشتر از آن پیشروی نخواهد کرد. به طور کل در الگوریتم‌های مبتنی بر دور(Iterative Algorithms) می‌توان تعدادِ دورها را محدود کرد تا الگوریتمْ بی‌نهایت دور نداشته باشد.

همچنین در گیف زیر فرایند  الگوریتم K-Means را می توانید مشاهده کنید:

مرتبه پیچیدگی الگوریتم K-means
الگوریتم K-means دارای مرتبه ی زمانیO(I*K*n)  است ، که در آن I تعداد تکرارها، K تعداد خوشه ها و n تعداد نمونه ها است.