K-Means++: Чому насіння краще, ніж випадковість

Алгоритм Ллойда, у чотирьох рядках

K-Means++ розділяє n точок на k кластерів шляхом чергування двох кроків до тих пір, поки нічого не змінюється: призначає кожній точці найближчий центроїд, а потім переміщує кожен центроїд у середнє положення точок, призначених йому. Цей цикл є алгоритмом Ллойда, і кожен повний прохід доведено, що ніколи не збільшує об'єктиву, який він мінімізує – сума квадратів в межах кластерів (інерція):

J = sum over clusters c, sum over points x in c of ||x - mean(c)||^2 призначення: кожне x -> argmin_c ||x - centroid_c||^2 (перемага найближчий центроїд) оновлення: centroid_c Геометрично, фіксуючи центроїди та призначаючи кожну точку її найближчій, викарбовується площина у діаграму Ворноя – межа між областями двох кластерів є точно перпендикулярною бісектрисою їхніх центроїдів, оскільки це набір точок рівновіддалених від обох. K-Means, на кожному ітерації, обчислює діаграму Ворноя та потім розслабляє її до своїх власних центрів маси.

J = sum over clusters c, sum over points x in c  of  ||x - mean(c)||^2

assign  : each x -> argmin_c ||x - centroid_c||^2   (nearest centroid wins)
update  : centroid_c <- mean of all x currently assigned to c
repeat until assignments stop changing

Чому ініціалізація – це все

Алгоритм Ллойда гарантовано збігається лише до локального мінімума J, і яка саме локальна мінімальна точка буде досягнута залежить майже повністю від того, де починаються центроїди. Якщо два початкові центроїди розміщені в одному справжньому кластері, вони часто залишаться заплутаними там назавжди, розділяючи один реальний кластер навпіл і об'єднуючи два інших – оновлювальний крок може лише переміщати межі, він не може перемістити центроїд через порожній простір до кластера, в якому немає центроїда поруч. Просте випадкове ініціалізування (вибір k випадкових точок як центроідів) дешеве, але часто призводить до цієї проблеми.

K-Means++: розсіювання насіння для кращого результату

K-Means++ (Arthur & Vassilvitskii, 2007) вирішує цю проблему за допомогою зваженого випадкового підбору центроїдів, який виконується один раз перед початком алгоритму Ллойда:

1. виберіть перший центроїд випадково з даних 2. для кожного решти точок x обчисліть D(x) = відстань до обраного центроїда 3. випадковим чином виберіть наступний центроїд із ймовірністю, пропорційною D(x)^2 4. повторіть кроки 2-3 до тих пір, поки не буде вибрано k центроїдів 5. запустіть звичайний алгоритм Ллойда з цих насіння Піднесення відстані до квадрату перед вагуванням є свідомим рішенням: точки, далекі від усіх існуючих центроїдів, стають набагато більш ймовірними кандидатами на вибір, активно розсіюючи насіння по різних кластерах замість їхнього з'єднання, але при цьому залишається невелика ймовірність вибору близької точки, щоб підбір насіння не був безповолітно зірваний окремим викидом. Гарантія, що надається цим: підбір центроїдів K-Means++ забезпечує очікуване співвідношення апроксимації O(log k) відносно оптимального кластеризації, математичний прецедент, якого не існує у випадковому підборі. На практиці він також збігається значно менше ітерацій алгоритму Ллойда, оскільки насіння вже розташовані близько до хороших кінцевих положень.

1. pick the first centroid uniformly at random from the data
2. for each remaining point x, compute D(x) = distance to the nearest chosen centroid
3. pick the next centroid at random, with probability proportional to D(x)^2
4. repeat step 2-3 until k centroids are chosen
5. run ordinary Lloyd's algorithm from these seeds

Визначення оптимального значення k: метод ‘зап’ятого’ та оцінка силуетом

У алгоритмі нічого не вказує на правильну кількість кластерів – k є гіперпараметром, який ви визначаєте. Зазвичай використовують два методи діагностики: метод ‘зап’ятого’ (elbow method) будує графік інваріантної суми J у залежності від k і шукає точку, де додавання наступного кластера не дає значної користі (інваріантність завжди зменшується зі збільшенням k, досягаючи нуля, коли k = n, тому корисний сигнал – це точка зменшення швидкості зниження, а не мінімум). Оцінка силуетом (silhouette score) оцінює кожен об’єкт за тим, наскільки ближче він до свого власного кластера, ніж до найближчого іншого, в середньому по всіх об’єктах, і заохочує значення k, яке дає щільні, добре відокремлені кластери, а не просто низьку загальну дисперсію.

Де шукають слабини K-Means

K-Means неявно припускає, що кластери приблизно сферичні та мають схожий розмір, оскільки мінімізує квадратичну відстань Евкліда до одного центру границі на кластер – та сама припущення, закладена в суміш рівних, ізотропних Гаусових розподілів. Якщо подати йому класичні набори даних із двох півмісяців або концентричних кілець, він помітно зазнає невдачі: пряма межа поділу не може відокремити два переплетені півмісяці чи два вкладені кола, незалежно від того, як рухаються центри границі, оскільки жодне розташування центрів границі не утворює цих форм випуклих Воронових клітин. Методи на основі щільності (DBSCAN) або спектрального кластеризації обробляють ці форми; K-Means залишається популярним, оскільки він має часову складність O(n*k*i) на запуск (i = ітерацій), що легко паралелізується та достатньо хороший, коли кластери насправді мають вигляд неправильних тіснів, як бульбашки.

Frequently asked questions

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

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