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

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

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

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

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

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

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

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

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

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

где [math]\boldsymbol\mu_i[/math] - центр кластера [math]G_i[/math]

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

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

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

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

3 Литература

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