K-means

K-means - EMоподобный метрический алгоритм кластеризации.

Интуиция

Обозначим за $\mu _{i}$ центр $i$-го кластера, а за $z_{j}$ - номер кластера, которому принадлежит объект под номером $j$. Количество кластеров предполагается известным.

Хочется решить задачу минимизации:

$\sum _{i}\rho (x_{i},\mu _{z_{i}})^{2}\to {\underset {z_{i},\mu _{c}}{\min }}$

Чё-то сложновато и мы ищем субоптимальное решение по сути методом покоординатного спуска.

Описание

Инициализировать $\mu _{i}$ можно случайно, но лучше и понятнее инициализировать случайными объектами из выборки. До сходимости повторяются два шага:

• для каждого объекта $x_{i}$ пересчитывается $z_{i}=\operatorname {\underset {z_{i}}{argmin}} \rho (x_{i},\mu _{z_{i}})$
• вычисляются новые средние $\mu _{i}$ внутри каждого кластера

Критерии остановки

• после очередной итерации $z_{i}$ не изменились (типичный вариант)
• центры кластеров за итерацию изменились незначительно
• фиксированное число итераций