الگوریتم K-Means چیست؟ راهنمای کامل خوشه‌بندی K-Means

الگوریتم K-Means یکی از معروف‌ترین الگوریتم‌های یادگیری بدون نظارت و یکی از پرکاربردترین روش‌های یادگیری ماشین برای حل مسائل خوشه‌بندی است. این الگوریتم تلاش می‌کند داده‌های بدون برچسب را بر اساس میزان شباهت آن‌ها به چند گروه یا Cluster تقسیم کند.

در K-Means، هر داده به خوشه‌ای اختصاص داده می‌شود که مرکز آن، یعنی Centroid، به داده موردنظر نزدیک‌تر است. الگوریتم سپس این مراکز را بارها به‌روزرسانی می‌کند تا به وضعیتی برسد که تخصیص داده‌ها و مراکز خوشه‌ها دیگر تغییر قابل‌توجهی نداشته باشند.

K-Means به دلیل سادگی، سرعت بالا و قابلیت استفاده روی مجموعه‌داده‌های نسبتاً بزرگ، در حوزه‌هایی مانند تقسیم‌بندی مشتریان، تحلیل بازار، پردازش تصویر، خوشه‌بندی اسناد و تحلیل داده‌های اکتشافی کاربرد زیادی دارد.

در این مقاله ابتدا مفهوم خوشه‌بندی را بررسی می‌کنیم، سپس نحوه عملکرد K-Means، انتخاب تعداد خوشه‌ها، تابع هدف، K-Means++، کاربردها، مزایا و محدودیت‌ها و در نهایت نحوه استفاده از آن در Python و Scikit-learn را توضیح می‌دهیم.

الگوریتم K-Means چیست؟

K-Means یک الگوریتم Unsupervised Learning است؛ یعنی برای آموزش آن به برچسب یا پاسخ صحیح از پیش تعیین‌شده نیاز نداریم. الگوریتم مجموعه‌ای از داده‌ها را دریافت می‌کند و تلاش می‌کند ساختارهای پنهان و گروه‌های مشابه موجود در داده را پیدا کند.

حرف K در نام الگوریتم نشان‌دهنده تعداد خوشه‌هایی است که می‌خواهیم ایجاد کنیم. برای مثال، اگر K برابر با 3 باشد، الگوریتم تلاش می‌کند داده‌ها را به سه خوشه تقسیم کند.

هدف اصلی K-Means این است که داده‌های داخل هر خوشه تا حد امکان به یکدیگر شبیه باشند و در عین حال خوشه‌های مختلف تا حد امکان از یکدیگر متمایز باشند.

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

K-Means چگونه کار می‌کند؟

فرآیند K-Means را می‌توان به چند مرحله اصلی تقسیم کرد. این مراحل به صورت تکراری اجرا می‌شوند تا الگوریتم به یک وضعیت پایدار یا همان Convergence برسد.

1. انتخاب تعداد خوشه‌ها

در ابتدا باید مقدار K را مشخص کنیم. این مقدار تعیین می‌کند که الگوریتم چند خوشه ایجاد کند.

برای مثال:

• K = 2 یعنی داده‌ها به دو خوشه تقسیم می‌شوند.
• K = 3 یعنی داده‌ها به سه خوشه تقسیم می‌شوند.
• K = 5 یعنی الگوریتم پنج خوشه ایجاد می‌کند.

یکی از چالش‌های مهم K-Means همین انتخاب مقدار مناسب K است. روش‌هایی مانند Elbow Method و Silhouette Score می‌توانند برای انتخاب مقدار مناسب کمک کنند.

2. انتخاب Centroidهای اولیه

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

انتخاب تصادفی مراکز می‌تواند باعث شود اجرای الگوریتم در هر بار نتیجه متفاوتی داشته باشد. به همین دلیل در پیاده‌سازی‌های مدرن معمولاً از روش K-Means++ برای انتخاب هوشمندانه‌تر مراکز اولیه استفاده می‌شود.

3. تخصیص داده‌ها به نزدیک‌ترین Centroid

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

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

4. محاسبه مجدد Centroidها

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

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

5. تکرار تا رسیدن به همگرایی

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

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

تابع هدف در الگوریتم K-Means چیست؟

K-Means فقط به دنبال تشکیل چند گروه تصادفی نیست؛ بلکه یک هدف ریاضی مشخص دارد. هدف اصلی الگوریتم این است که فاصله نقاط داده از مرکز خوشه خود را تا حد امکان کاهش دهد.

به طور مشخص، K-Means تلاش می‌کند مجموع فواصل مربع‌شده بین هر نقطه و Centroid مربوط به آن را کمینه کند. این مقدار در بسیاری از پیاده‌سازی‌ها با مفاهیمی مانند Inertia یا Within-Cluster Sum of Squares (WCSS) شناخته می‌شود.

Inertia چیست؟

در الگوریتم K-Means، Inertia معیاری برای اندازه‌گیری میزان پراکندگی داده‌ها درون خوشه‌هاست. هرچه داده‌ها به Centroid خوشه خود نزدیک‌تر باشند، مقدار Inertia کمتر خواهد بود.

بنابراین در حالت کلی، مقدار پایین‌تر Inertia نشان می‌دهد که نقاط داخل هر خوشه به مرکز آن نزدیک‌تر هستند؛ البته این معیار به تنهایی برای تعیین بهترین تعداد خوشه‌ها کافی نیست، زیرا با افزایش K معمولاً مقدار Inertia نیز کاهش پیدا می‌کند.

Within-Cluster Sum of Squares

WCSS مجموع فاصله‌های مربع‌شده بین نقاط هر خوشه و Centroid همان خوشه است. K-Means تلاش می‌کند این مقدار را کمینه کند.

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

چگونه مقدار K را انتخاب کنیم؟

انتخاب مقدار مناسب K یکی از مهم‌ترین مراحل استفاده از K-Means است. اگر K بیش از حد کوچک باشد، گروه‌های متفاوت ممکن است در یک خوشه قرار بگیرند و اگر بیش از حد بزرگ باشد، داده‌ها بیش از اندازه تقسیم می‌شوند.

Elbow Method

یکی از روش‌های رایج برای انتخاب K، Elbow Method یا روش آرنج است. در این روش الگوریتم K-Means را برای مقادیر مختلف K اجرا می‌کنیم و مقدار Inertia یا WCSS را برای هر مقدار ثبت می‌کنیم.

با افزایش تعداد خوشه‌ها، Inertia کاهش پیدا می‌کند. اما از یک نقطه به بعد، افزایش K باعث کاهش قابل‌توجه Inertia نمی‌شود. این نقطه معمولاً به شکل یک «آرنج» در نمودار دیده می‌شود و می‌تواند گزینه مناسبی برای K باشد.

Silhouette Score

روش دیگری برای ارزیابی کیفیت خوشه‌بندی، Silhouette Score است. این معیار بررسی می‌کند که هر داده تا چه اندازه به اعضای خوشه خودش نزدیک و از خوشه‌های دیگر دور است.

مقدار Silhouette Score معمولاً بین -1 و 1 قرار می‌گیرد. مقدار بالاتر، در شرایط مشابه، نشان‌دهنده جداسازی بهتر خوشه‌هاست.

در عمل بهتر است انتخاب K تنها بر اساس یک معیار انجام نشود و علاوه بر معیارهای عددی، ساختار داده و هدف مسئله نیز در نظر گرفته شود.

یک مثال ساده از الگوریتم K-Means

فرض کنید اطلاعات مشتریان یک فروشگاه را در اختیار داریم و برای هر مشتری دو ویژگی «میزان خرید» و «تعداد خرید» ثبت شده است. هدف ما این است که مشتریان را به سه گروه تقسیم کنیم.

در ابتدا K را برابر 3 قرار می‌دهیم. سپس سه Centroid اولیه انتخاب می‌شوند. هر مشتری به نزدیک‌ترین Centroid اختصاص پیدا می‌کند.

بعد از این مرحله، میانگین ویژگی‌های مشتریان هر گروه محاسبه شده و Centroidهای جدید ساخته می‌شوند. دوباره فاصله مشتریان تا مراکز جدید محاسبه شده و در صورت نیاز تخصیص آن‌ها تغییر می‌کند.

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

البته نام‌گذاری و تفسیر این گروه‌ها پس از اجرای الگوریتم و با توجه به ویژگی‌های هر خوشه انجام می‌شود؛ خود K-Means به صورت مستقیم نمی‌داند که یک خوشه «مشتری وفادار» است.

فاصله در K-Means چگونه محاسبه می‌شود؟

مفهوم فاصله نقش مهمی در K-Means دارد، زیرا الگوریتم برای تعیین نزدیک‌ترین Centroid باید فاصله میان داده و مراکز خوشه‌ها را محاسبه کند.

در پیاده‌سازی استاندارد K-Means معمولاً از فاصله اقلیدسی استفاده می‌شود. این فاصله، فاصله مستقیم میان دو نقطه در فضای ویژگی‌ها را اندازه‌گیری می‌کند.

با این حال، مفهوم فاصله به نوع داده و روش مورد استفاده بستگی دارد و انتخاب معیار نامناسب می‌تواند روی نتیجه خوشه‌بندی تأثیر بگذارد.

K-Means++ چیست؟

یکی از نقاط ضعف K-Means کلاسیک، وابستگی آن به انتخاب Centroidهای اولیه است. اگر مراکز اولیه نامناسب انتخاب شوند، الگوریتم ممکن است به یک جواب ضعیف برسد یا در یک کمینه محلی نامناسب قرار بگیرد.

K-Means++ روشی برای انتخاب بهتر Centroidهای اولیه است. این روش تلاش می‌کند مراکز اولیه را به گونه‌ای انتخاب کند که از یکدیگر فاصله مناسبی داشته باشند.

استفاده از K-Means++ معمولاً باعث می‌شود شروع الگوریتم مناسب‌تر و نتیجه آن پایدارتر باشد. به همین دلیل در بسیاری از پیاده‌سازی‌های عملی، از جمله Scikit-learn، K-Means++ به عنوان روش پیش‌فرض انتخاب مراکز اولیه استفاده می‌شود.

کاربردهای الگوریتم K-Means

K-Means به دلیل سادگی و سرعت بالا در طیف گسترده‌ای از مسائل داده‌کاوی و یادگیری ماشین استفاده می‌شود.

تقسیم‌بندی مشتریان

یکی از معروف‌ترین کاربردهای K-Means، Customer Segmentation است. کسب‌وکارها می‌توانند مشتریان را بر اساس ویژگی‌هایی مانند میزان خرید، تعداد تراکنش‌ها، میانگین مبلغ خرید یا رفتار کاربران به گروه‌های مختلف تقسیم کنند.

تقسیم‌بندی بازار

در بازاریابی می‌توان مشتریان یا بازار را به گروه‌هایی با رفتار و ویژگی‌های مشابه تقسیم کرد و برای هر گروه استراتژی متفاوتی در نظر گرفت.

خوشه‌بندی اسناد

K-Means می‌تواند برای گروه‌بندی اسناد، مقالات یا متون بر اساس ویژگی‌های استخراج‌شده از آن‌ها استفاده شود. برای مثال، اسناد مرتبط با موضوعات مشابه می‌توانند در یک خوشه قرار بگیرند.

پردازش تصویر

یکی دیگر از کاربردهای شناخته‌شده K-Means، پردازش تصویر و Image Segmentation است. برای مثال می‌توان پیکسل‌های تصویر را بر اساس ویژگی‌هایی مانند رنگ در گروه‌های مختلف قرار داد.

همچنین K-Means در برخی روش‌های کاهش تعداد رنگ‌ها و فشرده‌سازی تصویر نیز کاربرد دارد.

مزایای الگوریتم K-Means

• سادگی: مفهوم و پیاده‌سازی الگوریتم نسبتاً ساده است.
• سرعت بالا: در بسیاری از مسائل، K-Means نسبت به روش‌های پیچیده‌تر خوشه‌بندی سریع اجرا می‌شود.
• مقیاس‌پذیری مناسب: برای مجموعه‌داده‌های نسبتاً بزرگ نیز قابل استفاده است.
• پیاده‌سازی آسان: کتابخانه‌هایی مانند Scikit-learn استفاده از آن را بسیار ساده کرده‌اند.
• کاربردهای متنوع: در بازاریابی، پردازش تصویر، متن، تحلیل مشتریان و بسیاری حوزه‌های دیگر استفاده می‌شود.
• تفسیر نسبتاً ساده: بررسی Centroidها و ویژگی‌های هر خوشه می‌تواند به تفسیر نتایج کمک کند.

معایب و محدودیت‌های K-Means

با وجود کاربرد گسترده، K-Means برای همه مسائل خوشه‌بندی مناسب نیست و محدودیت‌های مهمی دارد.

• نیاز به تعیین K: تعداد خوشه‌ها باید از قبل مشخص شود.
• حساسیت به مقداردهی اولیه: انتخاب مراکز اولیه می‌تواند روی نتیجه اثر بگذارد.
• حساسیت به Outlier: نقاط پرت می‌توانند Centroidها را جابه‌جا کنند.
• وابستگی به مقیاس ویژگی‌ها: ویژگی‌هایی با مقیاس عددی بزرگ‌تر می‌توانند بیش از حد بر فاصله اثر بگذارند.
• مناسب نبودن برای برخی شکل‌های خوشه: K-Means برای خوشه‌های تقریباً کروی یا محدب عملکرد بهتری دارد.
• فرض ضمنی درباره ساختار خوشه‌ها: وقتی خوشه‌ها شکل‌های پیچیده، کشیده یا چگالی‌های بسیار متفاوت دارند، ممکن است نتیجه مناسبی حاصل نشود.

تأثیر مقیاس ویژگی‌ها بر K-Means

یکی از نکات بسیار مهم در استفاده از K-Means، Feature Scaling است. دلیل این موضوع آن است که K-Means بر اساس فاصله کار می‌کند.

فرض کنید دو ویژگی داریم: سن افراد بین 18 تا 70 و درآمد افراد بین 20,000 تا 200,000,000. در چنین شرایطی ویژگی درآمد به دلیل مقیاس عددی بسیار بزرگ‌تر می‌تواند اثر بسیار بیشتری روی محاسبه فاصله داشته باشد.

برای جلوگیری از این مشکل، معمولاً پیش از اجرای K-Means از روش‌هایی مانند Standardization یا Normalization استفاده می‌شود.

این مرحله می‌تواند تأثیر قابل‌توجهی بر نتیجه خوشه‌بندی داشته باشد و باید متناسب با ماهیت داده انجام شود.

K-Means در Python و Scikit-learn

کتابخانه Scikit-learn یکی از ساده‌ترین روش‌ها برای اجرای K-Means در Python را فراهم می‌کند. کلاس KMeans در ماژول sklearn.cluster برای این کار استفاده می‌شود.

یک نمونه ساده از اجرای K-Means به شکل زیر است:

from sklearn.cluster import KMeans

model = KMeans(
    n_clusters=3,
    random_state=42,
    n_init="auto"
)

model.fit(X)

labels = model.labels_
centers = model.cluster_centers_

در این مثال، مقدار n_clusters=3 مشخص می‌کند که می‌خواهیم داده‌ها به سه خوشه تقسیم شوند.

پس از آموزش مدل، ویژگی labels_ برچسب خوشه هر نمونه را مشخص می‌کند و cluster_centers_ مختصات Centroidهای نهایی را در اختیار ما قرار می‌دهد.

در پروژه‌های واقعی، بهتر است پیش از اجرای مدل، داده‌ها بررسی و پاک‌سازی شوند، ویژگی‌های مناسب انتخاب شوند و در صورت نیاز Scaling انجام شود. همچنین انتخاب K باید با روش‌هایی مانند Elbow Method یا Silhouette Score و با توجه به هدف کسب‌وکار ارزیابی شود.

تفاوت K-Means با Hierarchical Clustering و DBSCAN

K-Means تنها یکی از روش‌های خوشه‌بندی است. الگوریتم‌های دیگری مانند Hierarchical Clustering و DBSCAN نیز برای گروه‌بندی داده‌ها استفاده می‌شوند، اما رویکرد آن‌ها با K-Means متفاوت است.

به طور کلی، اگر داده‌ها ساختاری نسبتاً ساده داشته باشند و سرعت و سادگی اهمیت زیادی داشته باشد، K-Means می‌تواند گزینه مناسبی باشد. اگر ساختار سلسله‌مراتبی داده‌ها اهمیت داشته باشد، Hierarchical Clustering می‌تواند انتخاب بهتری باشد. همچنین برای داده‌هایی با خوشه‌های شکل‌نامنظم و وجود نقاط پرت، DBSCAN در بسیاری از موارد عملکرد مناسب‌تری دارد.

چه زمانی از K-Means استفاده نکنیم؟

K-Means الگوریتم قدرتمندی است، اما نباید بدون بررسی ساختار داده روی هر مسئله‌ای اجرا شود.

اگر خوشه‌های مورد انتظار شکل‌های بسیار پیچیده یا غیرکروی داشته باشند، K-Means ممکن است نتواند مرز مناسبی بین آن‌ها ایجاد کند. همچنین اگر داده‌ها دارای تعداد زیادی Outlier باشند، Centroidها ممکن است به سمت نقاط پرت کشیده شوند.

اگر ویژگی‌ها مقیاس‌های بسیار متفاوتی داشته باشند نیز اجرای مستقیم K-Means می‌تواند نتیجه گمراه‌کننده‌ای ایجاد کند. در چنین شرایطی باید ابتدا Scaling مناسب انجام شود.

همچنین اگر ندانیم تعداد خوشه‌های موردنظر تقریباً چه مقدار است، باید ابتدا ساختار داده را بررسی کنیم و از روش‌هایی مانند Elbow و Silhouette برای ارزیابی گزینه‌های مختلف استفاده کنیم.

جمع‌بندی الگوریتم K-Means

الگوریتم K-Means یکی از مهم‌ترین و پرکاربردترین الگوریتم‌های یادگیری بدون نظارت برای خوشه‌بندی داده‌هاست. این الگوریتم داده‌های بدون برچسب را به K گروه تقسیم می‌کند و تلاش می‌کند داده‌های داخل هر گروه به یکدیگر نزدیک و از داده‌های خوشه‌های دیگر متمایز باشند.

فرآیند K-Means بر پایه دو عملیات اصلی انجام می‌شود: ابتدا هر داده به نزدیک‌ترین Centroid اختصاص پیدا می‌کند و سپس Centroid هر خوشه با توجه به داده‌های اختصاص‌یافته دوباره محاسبه می‌شود. این مراحل به صورت تکراری ادامه پیدا می‌کنند تا الگوریتم به حالت پایدار برسد.

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

در نهایت، K-Means زمانی بیشترین کاربرد را دارد که هدف ما کشف گروه‌های نسبتاً همگن در داده‌ها باشد و ساختار داده با فرض‌های این الگوریتم سازگار باشد. استفاده صحیح از روش‌هایی مانند K-Means++، Elbow Method و Silhouette Score نیز می‌تواند به ساخت یک مدل خوشه‌بندی قابل‌اعتمادتر کمک کند.

سوالات متداول

الگوریتم K-Means چیست؟

K-Means یک الگوریتم یادگیری بدون نظارت است که داده‌های بدون برچسب را بر اساس شباهت به K خوشه تقسیم می‌کند. در این الگوریتم هر خوشه با یک Centroid نمایش داده می‌شود و داده‌ها به نزدیک‌ترین مرکز اختصاص پیدا می‌کنند.

آیا K-Means یک الگوریتم یادگیری بدون نظارت است؟

بله. K-Means به برچسب‌های از پیش تعیین‌شده نیاز ندارد و ساختار خوشه‌های موجود در داده را به صورت بدون نظارت کشف می‌کند.

حرف K در K-Means به چه معناست؟

K نشان‌دهنده تعداد خوشه‌هایی است که الگوریتم باید ایجاد کند. برای مثال، K=4 یعنی داده‌ها به چهار خوشه تقسیم می‌شوند.

چگونه بهترین مقدار K را انتخاب کنیم؟

روش‌هایی مانند Elbow Method و Silhouette Score برای بررسی مقدار مناسب K استفاده می‌شوند. با این حال، انتخاب نهایی باید با توجه به ساختار داده و هدف مسئله انجام شود.

K-Means++ چیست؟

K-Means++ روشی برای انتخاب بهتر Centroidهای اولیه است که با انتخاب مراکز اولیه مناسب‌تر، می‌تواند به بهبود شروع الگوریتم و کاهش احتمال رسیدن به جواب نامناسب کمک کند.

آیا K-Means به Scaling داده‌ها نیاز دارد؟

اگر ویژگی‌ها در مقیاس‌های متفاوت باشند، معمولاً انجام Feature Scaling اهمیت زیادی دارد؛ زیرا K-Means بر اساس فاصله کار می‌کند و ویژگی‌هایی با مقیاس بزرگ‌تر می‌توانند تأثیر نامتناسبی بر نتیجه داشته باشند.

مهم‌ترین کاربردهای K-Means چیست؟

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

تفاوت K-Means و DBSCAN چیست؟

K-Means داده‌ها را بر اساس فاصله از Centroidها گروه‌بندی می‌کند و معمولاً برای خوشه‌های نسبتاً کروی مناسب است. DBSCAN بر اساس چگالی داده‌ها کار می‌کند و می‌تواند خوشه‌های با شکل پیچیده‌تر و نقاط پرت را بهتر مدیریت کند.

منابع

• Towards Data Science
• JavaTpoint
• Scikit-learn Documentation