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

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

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

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

Шаг 0

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

Шаг 1

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

Шаг 2

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

Шаг 3

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

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

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

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