K-means

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

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

V = \sum_{i=1}^{k} \sum_{x_j \in S_i} (x_j - \mu_i)^2

где k - число кластеров, Si - полученные кластеры, i = 1, 2, \dots, k и μi - центры масс векторов x_j \in S_i.

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

Как показали Д.Артур и С.Вассилвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна 2^{\Omega(\sqrt{n})}.[1]

Содержание

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

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

Исходные точки и случайно выбранные начальные точки.
Точки, отнесённые к начальным центрам. Разбиение на плоскости — диаграмма Вороного относительно начальных центров.
Вычисление новых центров кластеров (Ищется центр масс).
Предыдущие шаги повторяются, пока алгоритм не сойдётся.

[править] Проблемы k-means

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

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

[править] Ссылки

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


Информатика Это незавершённая статья по информатике. Вы можете помочь проекту, исправив и дополнив её.
Формула Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её.
Источник — «http://ru.wikipedia.org/wiki/K-means»