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

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

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

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

Шаг 0

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

Шаг 1

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

Шаг 2

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

Шаг 3

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

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

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

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

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

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