Алгоритм k-средних

Простейший алгоритм кластеризации (деления данных на относительно однородные группы — т. н. кластеры).

Алгоритм k-средних делит имеющиеся данные на заданное число групп (кластеров) .

Алгоритм стремится минимизировать сумму квадратов расстояний от точек кластеров до центров кластеров.

Описание алгоритма

Шаг 0

Задаётся число групп

Шаг 1

Случайно выбираются точек, которые назначаются начальными центрами масс кластеров:

Шаг 2

Проводится начальное разбиение на кластеры. Точка принадлежит тому кластеру, расстояние до центра масс которого будет наименьшим.

Шаг 3

Происходит вычисление нового центра масс каждого кластера. Затем все точки заново разбиваются на кластеры по тому же правилу, что и в шаге 2. Эта процедура завершается тогда, когда после очередного пересчёта текущий центр масс совпадает с предыдущим.

Недостатки алгоритма

1. Алгоритму необходимо указывать число кластеров. Самостоятельно он не может вычислить их оптимальное количество.
2. Результат работы алгоритма зависит от начального выбора центров масс. Два разных выбора почти всегда дадут два разных результата. Задача начального оптимального выбора начальных центров масс (в модификациях алгоритма k-средних) может быть значительно сложнее, чем сама процедура кластеризации. Это напоминает СимплексМетод?, в котором задача поиска базисного плана может быть сопоставима по сложности (а иногда и сложнее), чем сам обход вершин выпуклого многогранника.
3. Алгоритм не гарантирует глобального минимума, только локальный.

Модификации алгоритма

Все модификации алгоритма можно свести к следующим улучшениям:

1. Поиск начального оптимального выбора центров масс. Допустим, мы хотим выбрать начальные центры масс таким образом, чтобы сумма расстояний между точками была наимбольшей. Если у нас наблюдений и мы хотим разбить данные на кластера, то число возможных вариантов разбиения будет равно (числу сочетаний из по ): вариантов. Поэтому для выбора оптимального начального центра масс используют иные методы, например МетодГрадиентногоСпуска и его вероятностные (стохастические) модификации.
2. Изменение алгоритма, по которому считаеются расстояния (с обычного евклидового расстояния до, например, суммы средних по разнице координатов, т. н. «расстояние городских кварталов»).
3. Различные процедуры поиска оптимального числа кластеров (обычно такие процедуры опираются на вероятностные методы).