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

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

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

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

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

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

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

Дано:

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

Требуется:

Разделить множество наблюдений [math]\displaystyle{ X }[/math] на [math]\displaystyle{ k }[/math] кластеров [math]\displaystyle{ S_1,S_2,...,S_k: }[/math]

• [math]\displaystyle{ S_i ∩ S_j = ∅, i ≠ j }[/math]
• [math]\displaystyle{ \bigcup_{i=1}^{k}S_i = X }[/math]

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

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

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

Алгоритм:

Инициализация: [math]\displaystyle{ }[/math]

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

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

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

Шаг [math]\displaystyle{ 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 }[/math]

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

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

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

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