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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 7 промежуточных версий этого же участника)
Строка 1: Строка 1:
Данный документ содержит описание схемы, по которой предлагается описывать свойства и структуру каждого алгоритма. Описание состоит из двух частей. В [[#ЧАСТЬ. Свойства и структура алгоритмов|первой части]] описываются собственно алгоритмы и их свойства, а [[#ЧАСТЬ. Программная реализация алгоритмов|вторая]] посвящена описанию особенностей их программной реализации с учетом конкретных программно-аппаратных платформ. Такое деление на части сделано для того, чтобы машинно-независимые свойства алгоритмов, которые определяют качество их реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ.  
+
== Свойства и структура алгоритмов ==
 +
 
 +
=== Общее описание алгоритма ===
 +
'''''k-means++'''''<ref>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.</ref> — улучшенная версия алгоритма кластеризации k-means. Суть улучшения заключается в нахождении более «хороших» начальных значений центроидов кластеров. Задача k-means состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, т.е. сумму квадратов расстояний от каждой кластеризуемой точки данных до ее центроида кластера (центра, который находится ближе всего к ней), то есть разбить <math>n</math> наблюдений на <math>k</math> кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения. Хотя найти точное решение задачи о k-средних для произвольных входных данных NP-сложно, <ref>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</ref> стандартный подход к нахождению приближенного решения широко используется и часто быстро находит разумные решения.
 +
 
 +
Однако алгоритм k-means имеет, по крайней мере, два основных теоретических недостатка:
 +
 
 +
# Было показано, что наихудшее время выполнения алгоритма является супер-полиномиальным по размеру входных данных.<ref>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.
 +
</ref>
 +
# Найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.
 +
 
 +
=== Математическое описание алгоритма ===
 +
'''Дано''':
 +
* набор из <math display=block>n</math> наблюдений <math display=block>X={x_1,x_2,...,x_n},x_i \in R^d, i=1,...,n;</math>
 +
* <math display=block>k</math> - требуемое число кластеров, <math display=block>k \in N, k \leq n.</math>
 +
*
 +
Требуется:
 +
 
 +
Разделить множество наблюдений <math display=block>X</math> на <math display=block>k</math> кластеров <math display=block>S_1,S_2,...,S_k:</math>
 +
 
 +
* <math display=block>S_i ∩ S_j = ∅, i ≠ j</math>
 +
* <math display=block>\bigcup_{i=1}^{k}S_i = X</math>
 +
*
 +
Действие алгоритма:
 +
 
 +
Алгоритм k-means++ разбивает набор <math display=block>X</math> на <math display=block>k</math> наборов <math display=block>S_1,S_2,...,S_k</math>, таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центроида(центр масс кластера). Введем обозначение, <math display=block>S={S_1,S_2,...,S_k}</math>. Тогда действие алгоритма k-means++ равносильно поиску:
  
Общая схема описания алгоритмов имеет следующий вид:
+
<math display=block>\arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{\mathbf{x} \in S_i} \rho(\mathbf{x}, \mathbf{\mu}_i )^2</math>,
 +
где <math display="block">{\mu_i} = \frac{1}{|S_i|}\sum_{\mathbf x \in S_i} \mathbf x, </math> – центры кластеров, <math display=block>i=1,...,k,\rho(x,μ_i)</math> – расстояние между <math>x</math> и <math>μ_i</math>
  
== Свойства и структура алгоритмов ==
+
'''Алгоритм:'''
Свойства алгоритмов никак не зависят от вычислительных систем, и с этой точки зрения данная часть AlgoWiki имеет безусловную собственную ценность. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах. Несмотря на то, что в данной части мы рассматриваем лишь машинно-независимые свойства алгоритмов, соображения, важные на этапе реализации, или же ссылки на соответствующие пункты [[#ЧАСТЬ. Программная реализация алгоритмов|части II AlgoWiki]], здесь также вполне уместны.
 
  
=== Общее описание алгоритма ===
+
'''''Инициализация:''''' <math></math>
В данном разделе представляется самый первый вариант описания тех задач (или классов задач), для решения которых предназначен алгоритм. В описании поясняются особенности как алгоритма, так и объектов, с которыми он работает. Если описание соответствует целому классу схожих по структуре алгоритмов, либо же посвящено описанию отдельного представителя некоторого класса, то это здесь указывается явно. Описываются базовые математические свойства и структура входных данных. При необходимости, в описании могут присутствовать формулы, а также даваться ссылки на описания других используемых алгоритмов. Данное описание должно быть достаточным для однозначного понимания сути решаемой задачи.
+
# Случайным образом выбрать первый центроид <math>\mu_1</math>  из точек данных.
 +
# Для каждой точки данных x вычислить ее расстояние <math>D(x)</math> от ближайшего, ранее выбранного центроида.
 +
# Выбрать следующий центроид из точек данных таким образом, чтобы вероятность выбора точки в качестве центроида была прямо пропорциональна квадрату ее расстоянию <math>D^2(x)</math> от ближайшего, ранее выбранного центроида: <math>\frac{D^2(x)}{\sum_{x}D^2(x)}</math>(т.е. точка, имеющая максимальное расстояние от ближайшего центроида, с наибольшей вероятностью будет выбрана следующей в качестве центроида)
 +
# Повторять шаги 2 и 3 до тех пор, пока не будут отобраны k центроидов: <math>\mu_i^{(0)} = \mu_i, \quad i=1,...,k</math>.
 +
Теперь, когда начальные центроиды выбраны, нужно использовать стандартную кластеризацию k-means:
  
=== Математическое описание алгоритма ===
+
1. <b>Распределение векторов по кластерам:</b>
Приводится математическое описание решаемой задачи в виде совокупности формул и соотношений, как это принято в книгах и учебниках. По возможности, используются общепринятые обозначения и способы записи. Должны быть явно определены все использованные обозначения и описаны свойства входных данных. Представленное описание должно быть достаточным для однозначного понимания постановки решаемой задачи для человека, знающего математику.
+
    <p><b>Шаг</b> <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></p>
 +
2.    <b>Пересчет центров кластеров:</b>
 +
    <p><b>Шаг </b> <math>t: \forall i=1,...,k:  \mu_i^{(t)} = \cfrac{1}{|S_i|}\sum_{x\in S_i}x</math></p>
 +
3.   <b>Проверка условия останова:</b>
 +
    <p></p>
 +
* '''если''' <math>\exists i\in \overline{1,k}: \mu_i^{(t)} \ne \mu_i^{(t-1)}</math> '''тогда'''
 +
** <math>t = t + 1</math>;
 +
** переход к шагу пересчета;
 +
* '''иначе:'''
 +
** '''останова'''
 +
  </li>
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Строка 50: Строка 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.