Cybernetics Wiki
Advertisement

k-means (иногда называемый k-средних) - наиболее популярный метод кластеризации. Алгоритм представляет собой модификацию EM-алгоритма для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера:

где - число кластеров, - полученные кластеры, и - центры масс векторов .

Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбраной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.

Как показали Д.Артур и С.Вассилвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна .[1]

Демонстрация алгоритма[]

Действие алгоритма в двумерном случае. Начальные точки выбраны случайно.

Файл:K Means Example Step 1.svg

Исходные точки и случайно выбранные начальные точки.

Файл:K Means Example Step 2.svg

Точки, отнесённые к начальным центрам. Разбиение на плоскости — диаграмма Вороного относительно начальных центров.

Файл:K Means Example Step 3.svg

Вычисление новых центров кластеров (Ищется центр масс).

Файл:K Means Example Step 4.svg

Предыдущие шаги повторяются, пока алгоритм не сойдётся.

Проблемы k-means[]

  • непонятно, как выбирать исходные центры кластеров
  • число кластеров надо знать заранее

Расширения и вариации[]

Ссылки[]

  1. David Arthur & Sergei Vassilvitskii (2006). "How Slow is the k-means Method?". Proceedings of the 2006 Symposium on Computational Geometry (SoCG). 



Advertisement