Ініціалізація

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

Крок призначення

На цьому етапі кожна точка даних призначається до найближчого центроїда. Відстань зазвичай вимірюється за допомогою евклідової відстані, але можуть використовуватися й інші метрики відстані. Кожна точка даних потрапляє до кластера, який представляє найближчий центроїд.

Крок оновлення

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

Ітерація

Кроки 2 і 3 повторюються ітеративно. На кожній ітерації точки даних перепризначаються до кластерів на основі оновлених центроїдів, а потім центроїди перераховуються відповідно до нових призначень кластерів. Цей ітеративний процес триває до досягнення критерію зупинки.

Збіжність

Алгоритм зупиняється, коли виконується одна з наступних умов:

• Центроїди майже не змінюються: положення центроїдів стабілізуються, тобто в наступних ітераціях їх розташування змінюється мінімально;

• Призначення точок даних не змінюється: точки даних залишаються в тих самих кластерах, що свідчить про стабільність структури кластерів;

• Досягнуто максимальну кількість ітерацій: досягнуто заздалегідь визначену максимальну кількість ітерацій. Це запобігає нескінченному виконанню алгоритму.

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