الگوریتم خوشه بندی را اجرا کنید

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

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

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

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

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

برای خوشه‌بندی داده‌ها در خوشه‌های \(k\) ، k-means مراحل زیر را دنبال می‌کند:

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

گام یک

الگوریتم به طور تصادفی یک مرکز را برای هر خوشه انتخاب می کند. در مثال ما، یک \(k\) از 3 را انتخاب می کنیم و بنابراین الگوریتم به طور تصادفی 3 مرکز را انتخاب می کند.

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

گام دوم

الگوریتم هر نقطه را به نزدیکترین مرکز برای بدست آوردن خوشه های اولیه \(k\) اختصاص می دهد.

شکل 3: محاسبه مجدد سانتروئیدها.

مرحله سوم

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

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

مرحله چهارم

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

برای این دوره نیازی به درک ریاضیات پشت k-means نیست. با این حال، اگر کنجکاو هستید، برای اثبات ریاضی به زیر مراجعه کنید.

برای اثبات ریاضی روی نماد مثبت کلیک کنید

با توجه به مثال‌های \(n\) اختصاص داده شده به خوشه‌های \(k\) ، مجموع فاصله نمونه‌ها را تا مرکز آنها به حداقل برسانید. جایی که:

• \(A_{nk} = 1\) هنگامی که مثال \(k\) \(n\)داده می شود و در غیر این صورت 0
• \(\theta_k\) مرکز خوشه \(k\)

ما می خواهیم عبارت زیر را به حداقل برسانیم:$$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$موضوع:$$A_{nk} \in \{0,1\} \forall n,k$$و$$\sum^{K}_{k=1}A_{nk}=1 \forall n$$برای به حداقل رساندن عبارت با توجه به مرکز خوشه \(\theta_k\)، مشتق را با توجه به \(\theta_k\) it را به quate 23 و e ببرید.$$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$$$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$$$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$$$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$$$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$شمارنده مجموع تمام فواصل مثال-مرکز در خوشه است. مخرج تعداد نمونه های خوشه است. بنابراین، مرکز خوشه\(\theta_k\) میانگین فواصل مثال-مرکز در خوشه است. از این رو ثابت شد.

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

آزمایش: با استفاده از این شبیه ساز k-means از استنفورد، سعی کنید k-means را چندین بار اجرا کنید و ببینید آیا نتایج متفاوتی دریافت می کنید.

شرایط کلیدی:

• نقطه مرکزی