K-Means

K-Means — один из наиболее известных алгоритмов разбиения, восходящий к работам Дж. Маккуина и широко используемый в анализе данных. **Цель алгоритма:** Найти такое разбиение объектов на $K$ кластеров, чтобы минимизировать сумму квадратов расстояний от объектов до центров своих кластеров: $J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2$. **Итерационный процесс:** 1. выбираются начальные центроиды; 2. каждый объект относится к ближайшему центроиду; 3. центроиды пересчитываются как средние значения объектов своих кластеров; 4. шаги повторяются до стабилизации разбиения. **Предпосылки:** Метод хорошо работает, если кластеры компактны, примерно выпуклы и сравнимы по размеру. Признаки должны быть масштабированы, иначе переменные с большими числовыми диапазонами будут доминировать в евклидовом расстоянии. **Ограничения:** Нужно заранее задать $K$. Алгоритм чувствителен к выбросам и начальной инициализации, а также плохо выделяет кластеры сложной невыпуклой формы.