Кластеризація K-середніх: центроїди, комірки воронами, інерція

Розділяй на частини спочатку, питань не задавай взагалі

Алгоритм k-середніх є найпростішим і найбільш поширеним безперешкодним алгоритмом машинного навчання: враховуючи набір точок і вибране число кластерів k, він розділяє точки на k груп таким чином, щоб кожна точка була ближче до центру свого власного кластера (свого центроїда), ніж до будь-якого центру іншого кластера. Немає міток для навчання — алгоритм виявляє структуру лише на основі того, як розподілені точки в просторі.

Алгоритм чергує два простих кроки до тих пір, поки щось не зміниться, особливий випадок ширшої техніки, яка називається алгоритмом Ллойда: призначення — призначати кожну точку найближчому центроїду — та оновлення — переміщати кожен центроїд у середнє положення точок, які зараз призначені йому. Оскільки перепризначення точок ніколи не може збільшити загальну квадратичну відстань від точок до їх призначеного центроїда, і обчислення центроїдів як середніх положень може лише зменшити його, об'єктив гарантовано монотонно незростаючий на кожному кроці, тому цикл завжди завершується, а не коливається вічно.

1. pick k initial centroids
2. repeat until assignments stop changing:
     assign each point to its nearest centroid   (Voronoi partition)
     move each centroid to the mean of its assigned points
3. done — clusters are the final Voronoi regions

Що саме мінімізує K-means

Формальна мета – сума квадратів усередини кластерів (WCSS), також відома як інерція: загальна сурована євклідова відстань від кожної точки до центру її власного кластера, підсумована по всіх кластерах. Кожне ітерацію призначення-оновлення доводиться незростаючою з цієї величини, тому спостереження за падінням інерції, стабілізацією та зрештою рівномірністю є стандартним способом відстежування процесу збіжності – горизонтальна лінія інерції означає, що призначення більше не змінюється, і алгоритм досяг локального оптимуму WCSS.

Геометрично, фіксуючи центроїди та запитуючи «до якого центроїда ближче до кожної точки», це точно визначення діаграми Вороної: k центроїдів розділяють площину на k викривлених областей, кожна з яких є множиною точок, ближчих до цього центроїда, ніж до будь-якого іншого. K-means, у цьому сенсі, ітеративно переналаштовує діаграму Вороної до даних – переміщуючи кожну точку генерації в центр маси її власної комірки, а потім перераховує комірки для нових точок та повторює.

Локальні мініма та важливість початкової ініціалізації

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

Вибір k: метод ліпкого та оцінка силуета

K-means потребує задання значення k заздалегідь, і алгоритму немає способу повідомити вам про ‘правильне’ з нього. Інтерція зменшується зі зростанням k (більше кластерів можуть лише так само добре підходити до даних, а k рівне кількості точок призводить до того, що WCSS стає нульовим безперестанно), тому ви не можете просто вибрати k, який мінімізує WCSS. Метод ліпкого малює інтерію проти k і шукає точку, де швидкість зменшення різко згладжується – візуальний, відносно суб’єктивний евристичний метод на основі зниження прибутковості. Оцінка силуета є більш обґрунтованою: для кожної точки вона порівнює середню відстань до точок у її власному кластері з середньою відстанню до точок у найближчому іншому кластері, створюючи оцінку від -1 до 1, яка винагороджує щільні, добре відособлені кластери. Кількість k, яка максимізує середню оцінку силуета для всіх точок, є поширеним, більш кількісним вибором.

Frequently asked questions

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

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