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

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

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

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

Шаг 0

Выбирается число групп

Шаг 1

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

Шаг 2

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

Шаг 3

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

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

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

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

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

1. Поиск начального оптимального выбора центров масс.
2. Изменение алгоритма, по которому считаеются расстояния (с обычного евклидового расстояния до, например, суммы средних по разнице координатов, т. н. «расстояние городских кварталов»).
3. Различные процедуры поиска оптимального числа кластеров.