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

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

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

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

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

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

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

Дано:

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

Требуется:

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

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

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

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

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

Алгоритм:

Инициализация: [math][/math]

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

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

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

Шаг [math]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]t: \forall i=1,...,k: \mu_i^{(t)} = \cfrac{1}{|S_i|}\sum_{x\in S_i}x[/math]

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

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