- К-средних
-
k-means (иногда называемый k-средних) - наиболее популярный метод кластеризации. Алгоритм представляет собой модификацию EM-алгоритма для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера:
где k - число кластеров, Si - полученные кластеры,
и μi - центры масс векторов
.
Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбраной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.
Как показали Д.Артур и С.Вассилвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна
.[1]
Содержание
Демонстрация алгоритма
Действие алгоритма в двумерном случае. Начальные точки выбраны случайно.
Исходные точки и случайно выбранные начальные точки.Точки, отнесённые к начальным центрам.Вычисление новых центров кластеров.Предыдущие шаги повторяются, пока алгоритм не сойдётся.Проблемы k-means
- непонятно, как выбирать исходные центры кластеров
- число кластеров надо знать заранее
Расширения и вариации
Ссылки
- ↑ David Arthur & Sergei Vassilvitskii (2006). "How Slow is the k-means Method?". Proceedings of the 2006 Symposium on Computational Geometry (SoCG).
-
Wikimedia Foundation. 2010.