K-Means یکی از معروفترین الگوریتمهای یادگیری بدون نظارت (Unsupervised Learning) است. برخلاف الگوریتمهای طبقهبندی، دادههای ورودی در K-Means لزوماً برچسب ندارند. هدف این است که نمونههای مشابه به صورت خودکار در گروههایی به نام Cluster قرار بگیرند.
اگر اطلاعات هزاران مشتری را داشته باشیم ولی ندانیم هر مشتری متعلق به چه گروهی است، K-Means میتواند بر اساس ویژگیهایی مانند میزان خرید، تعداد سفارش، فعالیت و رفتار مشتری، گروههای طبیعی موجود در داده را پیدا کند.
ایده اصلی K-Means
فرض کنید میخواهیم دادهها را به K = 3 گروه تقسیم کنیم.
الگوریتم سه نقطه را به عنوان مرکز اولیه خوشهها در نظر میگیرد. سپس هر داده به نزدیکترین مرکز اختصاص داده میشود. بعد از آن مرکز هر خوشه دوباره با استفاده از میانگین نقاط آن خوشه محاسبه میشود.
این فرایند چند بار تکرار میشود تا مراکز تقریباً دیگر تغییر نکنند.
مراحل الگوریتم
فرایند استاندارد K-Means را میتوان چنین خلاصه کرد:
- مقدار K را مشخص کنید.
- K مرکز اولیه یا Centroid انتخاب کنید.
- فاصله هر نقطه تا تمام Centroidها را محاسبه کنید.
- هر نقطه را به نزدیکترین خوشه اختصاص دهید.
- Centroid هر خوشه را با میانگین نقاط آن دوباره محاسبه کنید.
- مراحل تخصیص و محاسبه مرکز را تا رسیدن به همگرایی تکرار کنید.
Centroid چیست؟
Centroid مرکز میانگین یک خوشه است.
اگر یک خوشه شامل سه نقطه باشد:
(2, 4)
(4, 6)
(6, 8)
مرکز آن برابر است با:
((2+4+6)/3, (4+6+8)/3) = (4, 6)
این نقطه لزوماً یکی از دادههای واقعی نیست؛ بلکه میانگین موقعیت اعضای خوشه است.
فاصله اقلیدسی
برای تعیین نزدیکترین Centroid معمولاً از Euclidean Distance استفاده میشود:
d = sqrt((x2 - x1)^2 + (y2 - y1)^2)
هر داده به Centroidای اختصاص داده میشود که کمترین فاصله را با آن داشته باشد.
یک مثال ساده
فرض کنید این نقاط را داریم:
(1, 1)(1, 2)(2, 1)(8, 8)(8, 9)(9, 8)
اگر K = 2 باشد، انتظار داریم الگوریتم دو گروه طبیعی ایجاد کند:
Cluster 1:
(1,1), (1,2), (2,1)
Cluster 2:
(8,8), (8,9), (9,8)
Centroidها به تدریج به مرکز این دو گروه حرکت میکنند.
چگونه K را انتخاب کنیم؟
یکی از مهمترین پرسشها این است که تعداد خوشهها را چگونه تعیین کنیم.
Elbow Method
در روش Elbow، Kهای مختلف آزمایش میشوند و میزان خطای درون خوشهای مانند Within-Cluster Sum of Squares بررسی میشود.
با افزایش K خطا کاهش پیدا میکند، اما از نقطهای به بعد کاهش خطا بسیار کمتر میشود. این نقطه شبیه «آرنج» نمودار است و میتواند انتخاب مناسبی برای K باشد.
Silhouette Score
Silhouette Score بررسی میکند که هر نمونه چقدر به خوشه خودش نزدیک و از خوشههای دیگر دور است.
این معیار نیز میتواند در انتخاب K کمک کند.
چرا Feature Scaling مهم است؟
K-Means نیز مانند KNN بر فاصله تکیه میکند.
اگر یک ویژگی بین 0 تا 10 و ویژگی دیگر بین 0 تا 1,000,000 باشد، ویژگی دوم فاصله را تحت سلطه خود قرار میدهد.
به همین دلیل Standardization یا Min-Max Scaling معمولاً قبل از K-Means اهمیت زیادی دارد.
مقداردهی اولیه Centroidها
نتیجه K-Means میتواند به مراکز اولیه حساس باشد.
اگر مراکز اولیه نامناسب انتخاب شوند، الگوریتم ممکن است به یک جواب محلی ضعیف برسد.
یکی از روشهای شناختهشده برای بهبود مقداردهی اولیه، K-Means++ است که سعی میکند Centroidهای اولیه را با فاصله مناسبتری انتخاب کند.
در پیادهسازی JavaScript موجود در فایل پروژه، مراکز اولیه از اولین K نقطه داده انتخاب میشوند. این روش برای آموزش ساده است، اما در کاربردهای واقعی معمولاً انتخاب هوشمندانهتر یا چند بار اجرای الگوریتم توصیه میشود.
همگرایی یعنی چه؟
بعد از هر مرحله، نقاط ممکن است خوشه خود را تغییر دهند و Centroidها نیز جابهجا شوند.
وقتی تخصیص نقاط دیگر تغییر نکند یا حرکت Centroidها بسیار کوچک شود، میگوییم الگوریتم Converge کرده است.
کاربردهای واقعی K-Means
Customer Segmentation
میتوان مشتریان را بر اساس رفتار خرید، تعداد سفارش، ارزش مالی یا میزان تعامل خوشهبندی کرد.
تقسیمبندی کاربران محصول
کاربران یک اپلیکیشن را میتوان بر اساس الگوهای استفاده به گروههای مختلف تقسیم کرد.
تحلیل دادههای بازاریابی
K-Means برای کشف گروههای رفتاری در کمپینهای بازاریابی مفید است.
فشردهسازی تصویر
یکی از کاربردهای آموزشی جالب، کاهش تعداد رنگهای تصویر با خوشهبندی رنگهای مشابه است.
تحلیل اولیه داده
در Exploratory Data Analysis میتوان از K-Means برای کشف ساختار تقریبی داده استفاده کرد.
مزایای K-Means
- ساده و قابل فهم
- نسبتاً سریع در بسیاری از دادهها
- مناسب برای کشف ساختارهای اولیه
- قابل استفاده در حجم نسبتاً زیاد داده
- کاربردی برای Segmentation
محدودیتهای K-Means
باید K را از قبل مشخص کنیم
الگوریتم به صورت خودکار نمیداند چند خوشه وجود دارد.
حساسیت به Outlier
نقاط دورافتاده میتوانند Centroid را جابهجا کنند.
فرض خوشههای نسبتاً فشرده
K-Means برای خوشههایی که تقریباً گرد و قابل تفکیک با فاصله اقلیدسی هستند مناسبتر است.
حساسیت به مقداردهی اولیه
Centroidهای اولیه میتوانند روی نتیجه نهایی اثر بگذارند.
ویژگیهای دستهای
K-Means به شکل اصلی برای دادههای عددی و مفهوم میانگین طراحی شده است و برای دادههای صرفاً دستهای انتخاب طبیعیای نیست.
ساختار پیادهسازی
منطق ساده الگوریتم چنین است:
choose K centroids
repeat:
assign every point to nearest centroid
recompute each centroid as cluster mean
until assignments stop changing
پیادهسازی موجود در پروژه نیز یک ماتریس فاصله ایجاد میکند، کلاس نزدیکترین خوشه را برای هر نقطه تعیین میکند، سپس میانگین ابعاد اعضای هر خوشه را برای ساخت Centroid جدید محاسبه میکند و این روند را تا ثابت شدن تخصیصها ادامه میدهد.
K-Means و KNN چه تفاوتی دارند؟
با وجود شباهت اسمی، این دو الگوریتم هدف متفاوتی دارند.
KNN معمولاً Supervised است و از دادههای برچسبدار برای پیشبینی کلاس نمونه جدید استفاده میکند.
K-Means Unsupervised است و تلاش میکند بدون داشتن Label، ساختار و خوشههای موجود در داده را کشف کند.
جمعبندی
K-Means یک الگوریتم بنیادی برای درک مفهوم Clustering است. الگوریتم با تخصیص نقاط به نزدیکترین Centroid و محاسبه دوباره مرکز خوشهها به تدریج گروههای داده را پیدا میکند.
برای استفاده صحیح باید به انتخاب K، Scaling، مقداردهی اولیه، Outlierها و شکل واقعی خوشهها توجه کرد. برای مسائلی مانند Customer Segmentation و کشف گروههای رفتاری، K-Means همچنان یکی از بهترین الگوریتمها برای شروع تحلیل است.