K-середніх розбиває точки на k кластерів, мінімізуючи сумарну квадратичну відстань від кожної точки до центру її кластера. Алгоритм Ллойда чергує два дешевих кроки, доки нічого не змінюється.

Два кроки

• Призначення: прикріпити кожну точку до найближчого центроїда. Це розбиває площину на комірки Вороного.
• Оновлення: перемістити кожен центроїд до середнього призначених йому точок.

Повторюйте. Кожен крок може лише знизити цільову функцію, тож інерція (внутрішньокластерна сума квадратів похибок) ніколи не зростає, і процес збігається.

Інерція

інерція = Σ‖xᵢ − μ_c(i)‖² — сума по всіх точках квадрата відстані до призначеного центроїда μ. Спостерігайте, як вона падає з кожною ітерацією.

Ініціалізація k-means++

Випадкові початкові центроїди можуть дати поганий локальний оптимум. k-means++ обирає перший центр випадково, а кожен наступний — з імовірністю, пропорційною квадрату відстані до найближчого наявного центру, розкидаючи насіння та даючи значно кращі й стабільніші результати.

Обмеження

K-середніх припускає приблизно сферичні кластери схожого розміру і вимагає заздалегідь зафіксувати k. Воно погано справляється з видовженими чи вкладеними формами (спробуйте набір Місяці) — саме там виграють методи за густиною, як-от DBSCAN.