K-means (К-средних) — это самый популярный алгоритм кластеризации. Название происходит от того, что мы делим данные на K групп, и каждая группа представлена своим средним значением (центром).
Как работает алгоритм (простыми словами):
Представьте, что вы организуете детей на детской площадке. Вам нужно разделить их на 3 группы для игры.
1) Выбираем трёх случайных детей как "капитанов команд"
Это наши начальные центры кластеров
2) Каждый ребёнок идёт к ближайшему капитану
Это назначение точек к кластерам
3) Капитаны перемещаются в центр своей группы
Это пересчёт центров кластеров
4) Повторяем шаги 2-3, пока группы не стабилизируются
Это итерации алгоритма
Математическая формулировка:
Алгоритм
Вход: набор точек X = {x₁, x₂, ..., xₙ}, количество кластеров k
1. Инициализация: случайно выбираем k точек как начальные центры C = {c₁, c₂, ..., cₖ}
Число кластеров, которые мы хотим распознать, это и есть
k в K-means.
Примечание:
Если начальные центры выбрать неудачно (слишком близко), алгоритм может сойтись неправильно. Поэтому центры берут равномерно среди точек, чтобы они покрывали всё пространство.
2. Повторяем до сходимости:
а) Назначение: для каждой точки xᵢ найти ближайший центр cⱼ
Точка xᵢ принадлежит кластеру j, если d(xᵢ, cⱼ) минимально
б) Обновление: пересчитать центры как среднее арифметическое точек кластера
cⱼ = (1/|Sⱼ|) × Σ(x для всех x ∈ Sⱼ)
где Sⱼ — множество точек в кластере j
3.
Выход: финальные кластеры и их центры