Участник:Mansur/Алгоритм K-means++

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

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

k-means++ — улучшенная версия алгоритма кластеризации k-means. Суть улучшения заключается в нахождении более «хороших» начальных значений центроидов кластеров. Задача k-means состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, т.е. сумму квадратов расстояний от каждой кластеризуемой точки данных до ее центроида кластера (центра, который находится ближе всего к ней), то есть разбить n наблюдений на k кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения. Хотя найти точное решение задачи о k-средних для произвольных входных данных NP-сложно, стандартный подход к нахождению приближенного решения широко используется и часто быстро находит разумные решения.

Однако алгоритм k-means имеет, по крайней мере, два основных теоретических недостатка:

1. Было показано, что наихудшее время выполнения алгоритма является супер-полиномиальным по размеру входных данных.
2. Найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.

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

Дано:

• набор из $n$ наблюдений $X={x_1,x_2,...,x_n},x_i \in R^d, i=1,...,n;$
• $k$ - требуемое число кластеров, $k \in N, k \leq n.$

Требуется:

Разделить множество наблюдений $X$ на $k$ кластеров $S_1,S_2,...,S_k:$

• $S_i ∩ S_j = ∅, i ≠ j$
• $\bigcup_{i=1}^{k}S_i = X$

Действие алгоритма:

Алгоритм k-means++ разбивает набор $X$ на $k$ наборов $S_1,S_2,...,S_k$, таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центроида(центр масс кластера). Введем обозначение, $S={S_1,S_2,...,S_k}$. Тогда действие алгоритма k-means++ равносильно поиску:

$\arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{\mathbf{x} \in S_i} \rho(\mathbf{x}, \mathbf{\mu}_i )^2$, где ${\mu_i} = \frac{1}{|S_i|}\sum_{\mathbf x \in S_i} \mathbf x,$ – центры кластеров, $i=1,...,k,\rho(x,μ_i)$ – расстояние между $x$ и $μ_i$

Алгоритм:

Инициализация:

1. Случайным образом выбрать первый центроид $\mu_1$ из точек данных.
2. Для каждой точки данных x вычислить ее расстояние $D(x)$ от ближайшего, ранее выбранного центроида.
3. Выбрать следующий центроид из точек данных таким образом, чтобы вероятность выбора точки в качестве центроида была прямо пропорциональна квадрату ее расстоянию $D^2(x)$ от ближайшего, ранее выбранного центроида: $\frac{D^2(x)}{\sum_{x}D^2(x)}$(т.е. точка, имеющая максимальное расстояние от ближайшего центроида, с наибольшей вероятностью будет выбрана следующей в качестве центроида)
4. Повторять шаги 2 и 3 до тех пор, пока не будут отобраны k центроидов: $\mu_i^{(0)} = \mu_i, \quad i=1,...,k$.

Теперь, когда начальные центроиды выбраны, нужно использовать стандартную кластеризацию k-means:

1. Распределение векторов по кластерам:

Шаг $t: \forall \mathbf{x}_i \in X, \ i=1,...,n: j=\arg\min_{k}\rho(\mathbf{x}_i,\mathbf{\mu}_k^{(t-1)})^2 \Longrightarrow \mathbf{x}_i \in S_j$

2. Пересчет центров кластеров:

Шаг $t: \forall i=1,...,k: \mu_i^{(t)} = \cfrac{1}{|S_i|}\sum_{x\in S_i}x$

3. Проверка условия останова:

• если $\exists i\in \overline{1,k}: \mu_i^{(t)} \ne \mu_i^{(t-1)}$ тогда
  • $t = t + 1$;
  • переход к шагу пересчета;
• иначе:
  • останова

3 Литература

Arthur, D.; Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding" (PDF). Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035.