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

1. Картинка: http://rextester.com/OBB28239

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

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

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

Алгоритм гарантирует только локальный, но не глобальный оптимум.

Алгоритм является частным случаем АлгоритмEM?.

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

Шаг 0

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

Шаг 1

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

Шаг 2

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

Шаг 3

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

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

1. Алгоритму необходимо указывать число кластеров. Самостоятельно он не может вычислить их оптимальное количество.
2. Алгоритм неустойчив:

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

1. Алгоритм не гарантирует глобального минимума, только локальный. Подобные алгоритмы называются «жадными».

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

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

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