Кластеризація K-Means: Центроїди, Збіжність та k-means++

Два кроки, повторювані до фіксованої точки

Алгоритм K-means розділяє n точок на k кластерів, кожен з яких представлений єдиним центром (центроїдом). Виходячи з k початкових центроїдів, алгоритм Ллойда (Stuart Lloyd, 1957, опубліковано 1982) чергує два кроки до тих пір, поки щось не зміниться: призначає кожну точку найближчому центром, розділяючи площину на діаграму Вороного, та потім переміщує кожен центр у середнє положення точок, які йому приписані. Обидва кроки гарантовано лише зменшують або підтримують стабільним об'єкт оптимізації, тому процес гарантовано застигає.

Що саме мінімізується

Мета полягає у зменшенні внутрішньо-кластерної суми квадратів (inertia), також відомої як сума квадратів відстаней до центроїдів. Для кожного об’єкту обчислюється квадрат відстані від точки до її призначеного центроїда, і ці значення підсумовуються для всіх об'єктів. Призначення точок, з фіксованими центроїдами, є доведеним способом мінімізації inertia. Оновлення положення центроїдів, з фіксованими призначеннями, полягає у встановленні кожного центроїда як арифметичне середнє значення його точок, що також є доведеним способом мінімізації суми квадратів відстаней до цього кластеру. Постійне чергування двох точних мінімізацій одного й того ж об’єкту пояснює, чому цикл не може збільшувати inertia і зрештою припиняється.

while (assignments changed) {
  for (const p of points)                          // assignment step
    p.cluster = argmin_k( dist2(p, centroid[k]) );
  for (let k = 0; k < K; k++)                       // update step
    centroid[k] = mean(points where p.cluster === k);
}

Лише локальний мінімум, і чому важливе початкове значення

Мінімізація інерції точно над усіма можливими поділами є NP-складною, тому алгоритм Лайдля гарантує лише локальний мінімум – результат, до якого він збігається, значною мірою залежить від того, звідки почалися центроїди. Два поганих початкових центроїда можуть назавжди розділити те, що мало б бути одним кластером, або об'єднати два кластери, які мали б залишатися окремими, оскільки в циклі немає механізму, який би переміщував центроїд через порожню область після того, як призначення були зафіксовані. Стандартне рішення – запустити весь алгоритм кілька разів з різних випадкових стартових значень і зберегти той, що має найнижчу кінцеву іннерцію.

k-means++: зародження, яке уникне найгірших стартів

Arthur і Vassilvitskii в своїй роботі k-means++ (2007) покращили шанси на хороший початок без зміни основного циклу. Виберіть перший центральний елемент випадково з даних. Для кожного наступного центрального елемента виберіть точку з ймовірністю, пропорційною квадрату відстані до найближчого вже обраного центрального елементу – точки, далекі від існуючих центральних елементів, набагато частіше обираються, що поширює початкові центральні елементи по всьому об’єкту замість того, щоб збирати їх у купі. Це зародження само по собі доводиться на O(log k) очікуваного співвідношення приблизності відносно істинного оптимуму, а на практиці воно помітно зменшує кількість ітерацій для збіжності та ймовірність потрапляння в поганий локальний мінімум.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте K-Means Clustering і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.