Skip to content
بازگشت به نتایج جست‌وجو

خوشه‌بندی K-means

معرفی‌شده توسط
MacQueen, J. B.; Lloyd, S. P.
سال
1967 (formalized 1982)
نوع
Partitional clustering
خانواده
Machine learning

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

K-means یک الگوریتم کلاسیک خوشه‌بندی تقسیمی بدون نظارت است که با تخصیص تکراری هر مشاهده به نزدیک‌ترین مرکز (centroid) و به‌روزرسانی مراکز به عنوان میانگین نقاط تخصیص‌یافته به آن‌ها، یک مجموعه داده را به K گروه غیرهمپوشان تقسیم می‌کند. این الگوریتم یکی از پرکاربردترین ابزارهای اکتشافی در یادگیری ماشین و تحلیل داده است.

شهود پشت روش

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

تاریخ

ایده K-means به طور مستقل توسط مک‌کویین در سال 1967 معرفی شد که نام آن را ابداع کرد و توسط استوارت لوید در آزمایشگاه‌های بل در دهه 1950 به عنوان یک الگوریتم تکراری کارآمد رسمی شد (منتشر شده در 1982). بهبود مقداردهی اولیه k-means++ توسط آرتور و واسیلویتسکی در سال 2007 مشکل حساسیت به مینیمم محلی را برطرف کرد. امروزه K-means همچنان یک روش اصلی یادگیری بدون نظارت است که در تقریباً تمام برنامه‌های درسی علم داده تدریس می‌شود.

چه زمانی استفاده شود

K-means برای خوشه‌بندی اکتشافی مجموعه داده‌های بزرگ و کاملاً عددی مناسب است، زمانی که به پارتیشن‌بندی سریع و مقیاس‌پذیر نیاز دارید و با مشخص کردن K از قبل یا جستجوی آن با روش آرنج یا سیلوئت راحت هستید. این الگوریتم برای تقسیم‌بندی مشتریان، فشرده‌سازی تصویر، گروه‌بندی موضوعی اسناد و پیش‌پردازش قبل از یادگیری نظارت‌شده به خوبی عمل می‌کند. از آن در مواردی که خوشه‌ها غیر کروی هستند، اندازه‌ها یا چگالی‌های متفاوتی دارند، ویژگی‌ها دسته‌ای یا ترتیبی هستند (به جای آن از k-modes یا k-prototypes استفاده کنید)، تعداد خوشه‌ها کاملاً نامشخص است و آزمایش‌های K متغیر امکان‌پذیر نیست، یا داده‌ها حاوی نقاط پرت زیادی هستند (به جای آن از DBSCAN یا انواع مقاوم استفاده کنید) اجتناب کنید.

محدودیت‌ها و ملاحظات

  • نیاز به مشخص کردن K از قبل دارد؛ انتخاب نادرست K خوشه‌های بی‌معنی تولید می‌کند.
  • خوشه‌های کروی و با اندازه مشابه را فرض می‌کند؛ خوشه‌های کشیده، نامنظم یا با مقیاس متفاوت به اشتباه تقسیم یا ادغام می‌شوند.
  • به نقاط پرت حساس است: یک نقطه پرت می‌تواند یک مرکز را از توده اصلی خوشه دور کند.
  • فقط با ویژگی‌های عددی پیوسته کار می‌کند؛ داده‌های دسته‌ای نیاز به الگوریتم متفاوتی دارند (k-modes).
  • به یک مینیمم محلی همگرا می‌شود؛ نتایج ممکن است در اجراهای مختلف با بذرهای تصادفی متفاوت باشند مگر اینکه از k-means++ یا چندین راه‌اندازی مجدد استفاده شود.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • سریع و مقیاس‌پذیر: O(nKdi) در هر تکرار، در عمل روی میلیون‌ها مشاهده با K و ابعاد متوسط قابل استفاده است.
  • پیاده‌سازی ساده، در دسترس بودن در تمام چارچوب‌های اصلی یادگیری ماشین، و توضیح آسان برای مخاطبان غیر فنی.
  • روی خوشه‌های بزرگ، به خوبی جدا شده، تقریباً کروی و با اندازه مشابه به خوبی عمل می‌کند.
  • مقداردهی اولیه k-means++ حساسیت به شرایط اولیه را در مقایسه با مقداردهی اولیه تصادفی به طور قابل توجهی کاهش می‌دهد.
  • قطعی در یک بذر تصادفی ثابت، نتایج را قابل تکرار می‌سازد.

کاربردها

  • تقسیم‌بندی مشتریان برای بازاریابی و شخصی‌سازی بر اساس ویژگی‌های رفتاری یا جمعیتی.
  • فشرده‌سازی تصویر با کوانتیزه کردن رنگ پیکسل‌ها به K مقدار نماینده (کوانتیزاسیون رنگ).
  • خوشه‌بندی اسناد و متون به عنوان مرحله‌ای در خطوط لوله مدل‌سازی موضوع پس از برداری‌سازی.
  • پیش‌پردازش تشخیص ناهنجاری: نقاط دور از هر مرکز، نقاط پرت بالقوه هستند.
  • مرحله مقداردهی اولیه برای الگوریتم‌های پیچیده‌تر مانند مدل‌های مخلوط گاوسی یا خوشه‌بندی سلسله‌مراتبی.
  • تحلیل بیان ژن برای گروه‌بندی ژن‌ها یا نمونه‌ها با پروفایل‌های بیان مشابه.

چگونه کار می‌کند

چگونه کار می‌کند

1

K مرکز خوشه در فضای ویژگی قرار داده می‌شوند، یا با انتخاب تصادفی K نقطه داده (Forgy) یا با استراتژی هوشمندانه‌تر k-means++ که مراکز اولیه را پخش می‌کند تا احتمال مینیمم‌های محلی ضعیف را کاهش دهد. انتخاب مقداردهی اولیه مهم است: k-means++ معمولاً همگرایی سریع‌تر و راه‌حل‌های نهایی بهتری را به دست می‌دهد.

2

هر مشاهده به خوشه‌ای تخصیص داده می‌شود که مرکز آن بر اساس فاصله اقلیدسی نزدیک‌ترین است. این تخصیص سخت، K پارتیشن غیرهمپوشان از داده‌ها ایجاد می‌کند. به طور رسمی، هر نقطه x_i به خوشه c_i = argmin_k ||x_i - mu_k||^2 تخصیص داده می‌شود.

فرمول
c_i = \arg\min_k \|x_i - \mu_k\|^2
3

هر مرکز به عنوان میانگین حسابی تمام نقاطی که در حال حاضر به آن خوشه تخصیص داده شده‌اند، مجدداً محاسبه می‌شود: mu_k = (1/|C_k|) ضربدر مجموع تمام x_i در C_k. این مرحله تضمین می‌کند که مرکز جدید با توجه به تخصیص فعلی، WCSS را در هر خوشه به حداقل می‌رساند.

فرمول
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
4

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

5

کیفیت راه‌حل با WCSS کل (اینرسی) J = مجموع روی خوشه‌ها از مجموع روی نقاط تخصیص‌یافته از ||x_i - mu_k||^2 ارزیابی می‌شود. انتخاب K یک مسئله جداگانه است که با روش آرنج (elbow method)، امتیازات سیلوئت (silhouette scores) یا آماره‌های گپ (gap statistics) به آن پرداخته می‌شود، زیرا خود الگوریتم نیاز دارد که K از قبل مشخص شود.

فرمول
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2

دام‌های رایج

  • فراموش کردن استانداردسازی ویژگی‌ها قبل از خوشه‌بندی — متغیرهایی در مقیاس‌های بزرگ بر محاسبات فاصله غالب خواهند شد.
  • انتخاب K با بررسی صرف WCSS درون نمونه بدون نمودار آرنج یا اعتبارسنجی سیلوئت، منجر به انتخاب K بسیار کوچک یا بزرگ می‌شود.
  • اجرای تنها یک مقداردهی اولیه و پذیرش اولین نتیجه بدون راه‌اندازی مجدد متعدد برای محافظت در برابر مینیمم‌های محلی ضعیف.
  • گنجاندن متغیرهای دسته‌ای یا ترتیبی در ماتریس ویژگی بدون رمزگذاری مناسب یا تغییر به k-modes.
  • رفتار دادن به برچسب‌های خوشه به عنوان هویت‌های گروهی معنادار بدون اعتبارسنجی خارجی، به ویژه زمانی که خوشه‌ها به خوبی جدا نشده‌اند.

پرسش‌های متداول

چگونه تعداد مناسب خوشه‌ها K را انتخاب کنم؟

K-means را برای طیفی از مقادیر K اجرا کنید، مجموع مربعات درون خوشه‌ای را در برابر K رسم کنید و به دنبال 'آرنج' باشید که در آن نرخ کاهش به شدت کند می‌شود. این را با امتیازات سیلوئت که اندازه‌گیری می‌کنند هر نقطه چقدر به خوشه خود در مقابل خوشه‌های همسایه شبیه است، تکمیل کنید؛ میانگین سیلوئت بالاتر نشان‌دهنده خوشه‌های خوش‌تعریف‌تر است.

چرا در هر اجرا نتایج متفاوتی می‌گیرم؟

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

آیا K-means با داده‌های دسته‌ای کار می‌کند؟

خیر. K-means به فاصله اقلیدسی و میانگین مراکز متکی است که برای متغیرهای دسته‌ای تعریف نشده‌اند. برای داده‌های کاملاً دسته‌ای از k-modes استفاده کنید؛ برای داده‌های ترکیبی عددی و دسته‌ای از k-prototypes استفاده کنید.

چه زمانی باید DBSCAN یا GMM را به K-means ترجیح دهم؟

زمانی از DBSCAN استفاده کنید که خوشه‌ها شکل‌های نامنظمی دارند یا به تشخیص خودکار نقاط پرت بدون نیاز به مشخص کردن K نیاز دارید. زمانی از مدل‌های مخلوط گاوسی (GMM) استفاده کنید که تخصیص‌های خوشه‌ای نرم (احتمالاتی) یا خوشه‌هایی با اندازه‌ها و جهت‌گیری‌های متفاوت را می‌خواهید، اما با هزینه پیچیدگی محاسباتی بالاتر.

آیا نیاز به مقیاس‌بندی ویژگی‌هایم دارم؟

بله، تقریباً همیشه. K-means از فاصله اقلیدسی استفاده می‌کند، بنابراین ویژگی‌هایی با دامنه‌های عددی بزرگ بر خوشه‌بندی غالب خواهند شد. قبل از برازش K-means، استانداردسازی z-score یا مقیاس‌بندی min-max را اعمال کنید، مگر اینکه همه ویژگی‌ها از قبل در مقیاس یکسانی باشند.

روش‌های مرتبط

منابع

  1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    باز کردن مرجع DOI
    کپی شد.
  2. MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.

    باز کردن مرجع انتشار
    کپی شد.