خوشه بندی k-means چیست؟

همانطور که قبلا ذکر شد، بسیاری از الگوریتم‌های خوشه‌بندی به مجموعه داده‌های مورد استفاده در یادگیری ماشین، که اغلب میلیون‌ها مثال دارند، مقیاس نمی‌شوند. برای مثال، الگوریتم‌های خوشه‌بندی سلسله مراتبی تجمعی یا تقسیمی به همه جفت‌های نقطه نگاه می‌کنند و دارای پیچیدگی‌های $O(n^2 log(n))$ و $O(n^2)$به ترتیب.

این دوره بر روی k-means تمرکز دارد زیرا به صورت مقیاس بندی می شود $O(nk)$، کجا $k$تعداد خوشه های انتخاب شده توسط کاربر است. این الگوریتم نقاط را به گروه بندی می کند$k$ با به حداقل رساندن فواصل بین هر نقطه و مرکز خوشه آن خوشه می شود (شکل 1 را ببینید).

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

k-means الگوریتم خوشه بندی

الگوریتم این مراحل را دنبال می کند:

1. یک حدس اولیه برای آن ارائه دهید $k$، که می تواند بعداً تجدید نظر شود. برای این مثال، ما انتخاب می کنیم $k = 3$.

2. به صورت تصادفی انتخاب کنید $k$ مرکز

   

   شکل 1: k-means در مقدار دهی اولیه.

3. هر نقطه را به نزدیکترین مرکز برای بدست آوردن اختصاص دهید $k$ خوشه های اولیه

   

   شکل 2: خوشه های اولیه.

4. برای هر خوشه، یک مرکز جدید را با گرفتن موقعیت میانگین تمام نقاط خوشه محاسبه کنید. فلش های شکل 4 تغییر موقعیت های مرکز را نشان می دهد.

   

   شکل 3: مرکزهای محاسبه شده مجدد.

5. هر نقطه را به نزدیکترین مرکز جدید اختصاص دهید.

   

   شکل 4: خوشه ها پس از تخصیص مجدد.

6. مراحل 4 و 5 را تکرار کنید، مرکزها و عضویت در خوشه را دوباره محاسبه کنید، تا زمانی که نقاط دیگر خوشه را تغییر ندهند. در مورد مجموعه داده های بزرگ، می توانید الگوریتم را قبل از همگرایی بر اساس معیارهای دیگر متوقف کنید.

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

اگرچه درک عمیق ریاضیات ضروری نیست، اما برای کسانی که کنجکاو هستند، k-means مورد خاصی از الگوریتم حداکثرسازی انتظارات است. یادداشت های سخنرانی در مورد موضوع را از UPenn ببینید.