Участник:Mansur/Алгоритм K-means++: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(<math>n</math>)
 
Строка 89: Строка 89:
 
== Литература ==
 
== Литература ==
 
<references />
 
<references />
 
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.
 

Текущая версия на 23:53, 30 октября 2023

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

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

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

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

  1. Было показано, что наихудшее время выполнения алгоритма является супер-полиномиальным по размеру входных данных.[3]
  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];
    • переход к шагу пересчета;
  • иначе:
    • останова

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

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

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. 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.
  2. Drineas, P.; Frieze, A.; Kannan, R.; Vempala, S.; Vinay, V. (2004). "Clustering Large Graphs via the Singular Value Decomposition". Machine Learning. 56 (1–3): 9–33. doi:10.1023/B:MACH.0000033113.59016.96
  3. Arthur, D.; Vassilvitskii, S. (2006). "How slow is the k-means method?". Proceedings of the twenty-second annual symposium on Computational geometry. ACM New York, NY, USA. pp. 144–153.