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

Алгоритм k средних Автор статьи: Синдеева Мария, группа 416

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

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

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

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

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

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

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

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

[math]\displaystyle{ 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]\displaystyle{ \boldsymbol\mu_i }[/math] - центр кластера [math]\displaystyle{ G_i }[/math]

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

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

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

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

Литература

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