همانطور که قبلا ذکر شد، بسیاری از الگوریتم‌های خوشه‌بندی به مجموعه داده‌های مورد استفاده در یادگیری ماشین، که اغلب میلیون‌ها مثال دارند، مقیاس نمی‌شوند. برای مثال، الگوریتم‌های خوشه‌بندی سلسله مراتبی تجمعی یا تقسیمی به تمام جفت‌های نقطه نگاه می‌کنند و به ترتیب دارای پیچیدگی‌های \(O(n^2 log(n))\) و \(O(n^2)\)هستند.
این دوره روی k-means تمرکز دارد زیرا به صورت \(O(nk)\)مقیاس می شود، که در آن \(k\)تعداد خوشه های انتخاب شده توسط کاربر است. این الگوریتم با به حداقل رساندن فاصله بین هر نقطه و مرکز خوشه آن، نقاط را در خوشه های\(k\) گروه بندی می کند (شکل 1 را ببینید).
در نتیجه، k-means به طور موثر داده‌ها را به‌صورتی که از تعدادی توزیع تقریباً دایره‌ای تشکیل شده‌اند، رفتار می‌کند و سعی می‌کند خوشه‌های مربوط به این توزیع‌ها را بیابد. اما داده‌های دنیای واقعی حاوی مقادیر پرت و خوشه‌های مبتنی بر چگالی هستند و ممکن است با مفروضات اساسی k-means مطابقت نداشته باشند.
k-means الگوریتم خوشه بندی
الگوریتم این مراحل را دنبال می کند:
یک حدس اولیه برای \(k\)ارائه کنید که بعداً قابل تجدید نظر است. برای این مثال، \(k = 3\)انتخاب می کنیم.
به طور تصادفی \(k\) centroids را انتخاب کنید.
شکل 1: k-means در مقدار دهی اولیه. برای به دست آوردن خوشه های اولیه \(k\) هر نقطه را به نزدیکترین مرکز اختصاص دهید.
شکل 2: خوشه های اولیه. برای هر خوشه، یک مرکز جدید را با گرفتن موقعیت میانگین تمام نقاط خوشه محاسبه کنید. فلش های شکل 4 تغییر موقعیت های مرکز را نشان می دهد.
شکل 3: مرکزهای محاسبه شده مجدد. هر نقطه را به نزدیکترین مرکز جدید اختصاص دهید.
شکل 4: خوشه ها پس از تخصیص مجدد. مراحل 4 و 5 را تکرار کنید، مرکزها و عضویت در خوشه را دوباره محاسبه کنید، تا زمانی که نقاط دیگر خوشه را تغییر ندهند. در مورد مجموعه داده های بزرگ، می توانید الگوریتم را قبل از همگرایی بر اساس معیارهای دیگر متوقف کنید.
از آنجایی که موقعیت‌های مرکز در ابتدا به صورت تصادفی انتخاب می‌شوند، k-means می‌تواند نتایج بسیار متفاوتی را در اجراهای متوالی نشان دهد. برای حل این مشکل، k-means را چندین بار اجرا کنید و نتیجه را با بهترین معیارهای کیفیت انتخاب کنید. (ما بعداً در این دوره معیارهای کیفیت را شرح خواهیم داد.) برای انتخاب موقعیت های اولیه بهتر به یک نسخه پیشرفته از k-means نیاز دارید.
اگرچه درک عمیق ریاضیات ضروری نیست، اما برای کسانی که کنجکاو هستند، k-means مورد خاصی از الگوریتم حداکثرسازی انتظارات است. یادداشت های سخنرانی در مورد موضوع را از UPenn ببینید.