الگوریتم K-Means محبوب ترین و پرکاربردترین الگوریتم برای گروه بندی خودکار داده ها در زیر مجموعه های منسجم (اعضای آن به هم مربوط هستند) است.
متغیرهای اصلی ما عبارتند از:
توجه داشته باشید که ما از عبارت $x ^ 0 = 1$ استفاده نخواهیم کرد.
الگوریتم:
Randomly initialize K cluster centroids mu(1), mu(2), ..., mu(K)
Repeat:
for i = 1 to m:
c(i):= index (from 1 to K) of cluster centroid closest to x(i)
for k = 1 to K:
mu(k):= average (mean) of points assigned to cluster k
حلقه for اول مرحله تخصیص خوشه یعنی مرحله ۲ است، یک بردار به اسم $c$ می‌سازیم که $c^{(i)}$ نمایانگر مرکزی است که به نمونه $x ^ {(i)}$ منتسب شده است.
ما می‌توانیم مرحله تخصیص خوشه را به ریاضی بنویسیم: $$ c^{(i)} = argmin _ k \begin{Vmatrix} x^{(i)} - \mu _ k \end{Vmatrix} ^2 $$
یعنی هر $c^{(i)}$ حاوی ایندکس مرکزی است که حداقل فاصله را تا $x^{(i)}$ دارد.
طبق قرارداد، ما سمت راست معادله را به توان ۲ می‌رسانیم، که باعث می‌شود بار محاسباتی کاهش پیدا کند.
بدون توان ۲: $$ \begin{Vmatrix} x^{(i)} - \mu _ k \end{Vmatrix} = \begin{Vmatrix} \sqrt{ (x^{(i) _ 1 - \mu _ {1 (k)}})^2 + (x^{(i) _ 2 - \mu _ {2 (k)}})^2 + (x^{(i) _ 3 - \mu _ {3 (k)}})^2 + … } \end{Vmatrix} $$
با توان ۲: $$ \begin{Vmatrix} x^{(i)} - \mu _ k \end{Vmatrix} ^2 = \begin{Vmatrix} (x^{(i) _ 1 - \mu _ {1 (k)}})^2 + (x^{(i) _ 2 - \mu _ {2 (k)}})^2 + (x^{(i) _ 3 - \mu _ {3 (k)}})^2 + … \end{Vmatrix} $$
بنابراین هدف از قرارداد توان ۲ محاسبه کمتر و دقیق تر است.
حلقه for دوم همان مرحله ۳ است، جایی که هر مرکز را به میانگین گروه خود منتقل می‌کنیم.
به صورت رسمی تر ، معادله برای این حلقه به شرح زیر است:
$$ \mu _k = \frac{1}{n} [ x^{(k _ 1)} + x^{(k _ 2)} + … + x^{(k _ n)}] \in \mathbb{R} ^ n $$
به طوری که هر کدام از $x^{(k _ 1)} + x^{(k _ 2)} + … + x^{(k _ n)}$ ها نمونه های آموزشی اختصاص داده شده به گروه $\mu _k$ هستند.
اگر یک مرکز خوشه ای دارید که 0 امتیاز به آن اختصاص داده شده است، می توانید آن مرکز را به طور تصادفی مجدداً در یک نقطه جدید تنظیم کنید. شما همچنین می توانید آن گروه خوشه را به سادگی از بین ببرید.
بعد از تعدادی تکرار الگوریتم به همگرایی خواهید رسید، به طوری که تکرار های جدید تاثیری بر خوشه ها نمی‌گذارند!
نکته ای در مورد خوشه های جدا نشده:
برخی از مجموعه های داده هیچ جدایی داخلی و ساختار طبیعی ندارند. K-mean هنوز هم می تواند داده های شما را به K زیر مجموعه تقسیم کند، بنابراین در این حالت نیز همچنان می‌تواند مفید باشد.