Участник:Msindeeva/Алгоритм k средних

1 Свойства и структура алгоритма

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

Алгоритм k средних - это алгоритм кластерного анализа, используемый в дата майнинге. Цель алгоритма - разделить $n$ наблюдений на $k$ кластеров, в которых каждое наблюдение принадлежит к кластеру с ближайшим центром, который служит прототипом всего кластера. Эта задача является NP-сложной, но существуют эффективные эвристические алгоритмы, быстро сходящиеся к локальному минимуму.

Алгоритм k средних является наиболее популярным метод кластеризации. Он был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом.

1.2 Математическое описание алгоритма

Входные параметры: $n$ наблюдений (векторов) $(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)$, $k$ - число кластеров.

Также входным параметром можно считать метрику для векторов, например евклидово расстояние $d(x, y) = \sum_{i = 1}^{l} (x_i - y_i )^2$ - одна из самых популярных используемых метрик.

Формально нам необходимо найти такое разделение $(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)$ на подмножества $G = (G_1, .. G_k)$, так чтобы минимизировать сумму квадратов расстояний до их центров, или суммарное квадратичное отклонение:

$F = \underset{\mathbf{G}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x \in G_i} d(\mathbf x, \boldsymbol\mu_i)^2,$

где $\boldsymbol\mu_i$ - центр кластера $G_i$

Алгоритм работает итерационно, каждая итерация алгоритма представляет собой следующее:

• Пересчитать центр масс для каждого кластера, полученного на предыдущем шаге: $\boldsymbol \mu_i = \frac{\sum_{\mathbf x_i \in G_i}\mathbf x_i}{|G_i|}, i = 1, 2, .. k$
• Переразбить векторы на кластеры в соответствии с расстоянием до новых посчитанных центров: $z_i = \underset{\mathbf{j}} {\operatorname{arg\,min}} \{d(\mathbf x_i, \boldsymbol \mu_j)\}, i = 1, 2, .. n$

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

Такой алгоритм сходится при любом начальном приближении разбиения на кластеры, поэтому в качестве нулевого шаге часто выбирают $k$ случайных векторов среди $(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)$.

3 Литература

• MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations"
• MacKay, David (2003). "An Example Inference Task: Clustering"