Алгоритм k средних (k-means)

Основные авторы статьи (разделы 1, 2.4.1, 2.6-2.7, 3): Д.Бротиковская и Д.Зобнин
Авторы отдельных разделов: Я.А.Валуйская и Е.С.Глотов (раздел 2.4.2), П.А.Пархоменко и И.Д.Машонский (раздел 2.4.3), И.Егоров и Е.Богомазов (раздел 2.4.4)

Алгоритм [math]k[/math] средних (k-means)
Последовательный алгоритм
Последовательная сложность	[math]O(ikdn)[/math]
Объём входных данных	[math] dn [/math]
Объём выходных данных	[math] n [/math]

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

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

Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Этот алгоритм является неиерархическим, итерационным методом кластеризации, он получил большую популярность благодаря своей простоте, наглядности реализации и достаточно высокому качеству работы. Был изобретен в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом. Особую популярность приобрел после публикации работы МакКуина в 1967.

Алгоритм представляет собой версию EM-алгоритма, применяемого также для разделения смеси гауссиан. Основная идея алгоритма k-means заключается в том, что данные произвольно разбиваются на кластеры, после чего итеративно перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике.

Цель алгоритма заключается в разделении [math]n[/math] наблюдений на [math]k[/math] кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.

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

Дано:

• набор из [math]n[/math] наблюдений [math]X=\{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\}, \mathbf{x}_i \in \mathbb{R}^d, \ i=1,...,n[/math];
• [math]k[/math] - требуемое число кластеров, [math]k \in \mathbb{N}, \ k \leq n[/math].

Требуется:

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

• [math]S_i \cap S_j= \varnothing, \quad i \ne 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](1)[/math]

где [math]\mathbf{\mu}_i[/math] – центры кластеров, [math]i=1,...,k, \quad \rho(\mathbf{x}, \mathbf{\mu}_i)[/math] – функция расстояния между [math]\mathbf{x}[/math] и [math]\mu_i[/math]

Шаги алгоритма:

1. Начальный шаг: инициализация кластеров

   Выбирается произвольное множество точек [math]\mu_i, \ i=1,...,k,[/math] рассматриваемых как начальные центры кластеров: [math]\mu_i^{(0)} = \mu_i, \quad i=1,...,k[/math]

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

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

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

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

4. Проверка условия останова:
   • if [math]\exists i\in \overline{1,k}: \mu_i^{(t)} \ne \mu_i^{(t-1)}[/math] then
     • [math]t = t + 1[/math];
     • goto 2;
   • else
     • stop

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

Вычислительным ядром являются шаги 2 и 3 приведенного выше алгоритма: распределение векторов по кластерам и пересчет центров кластеров.

Распределение векторов по кластерам предполагает вычисление расстояний между каждым вектором [math]\mathbf{x}_i \in X, \ i= 1,...,n[/math] и центрами кластера [math]\mathbf{\mu}_j, \ j= 1,...,k[/math]. Таким образом, данный шаг предполагает [math]kn[/math] вычислений расстояний между [math]d[/math]-мерными векторами.

Пересчет центров кластеров предполагает [math]k[/math] вычислений центров масс [math]\mathbf{\mu}_i[/math] множеств [math]S_i, \ i=1,...,k,[/math] представленных выражением в шаге 3 представленного выше алгоритма.

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

Инициализация центров масс [math]\mu_1, ..., \mu_k[/math].

Наиболее распространенными являются следующие стратегии:

• Метод Forgy
  В качестве начальных значений [math]\mu_1, ..., \mu_k[/math] берутся случайно выбранные векторы.
• Метод случайно разделения (Random Partitioning)
  Для каждого вектора [math]\mathbf{x}_i \in X, \ i=1,...,n,[/math] выбирается случайным образом кластер [math]S_1, ..., S_k[/math], после чего для каждого полученного кластера вычисляются значения [math]\mu_1, ..., \mu_k[/math].

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

Для этого шага алгоритма между векторами [math]\mathbf{x}_i \in X, \ i=1,...,n,[/math] и центрами кластеров [math]\mu_1,...,\mu_k[/math] вычисляются расстояния по формуле (как правило, используется Евлидово расстояние):

[math] \mathbf{v}_1, \mathbf{v}_2 \in \mathbb{R}^d, \quad \rho(\mathbf{v}_1, \mathbf{v}_2) = \lVert \mathbf{v}_1- \mathbf{v}_2 \rVert= \sqrt{\sum_{i=1}^{d}(\mathbf{v}_{1,i} - \mathbf{v}_{2,i})^2}[/math]

[math](2)[/math]

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

Для этого шага алгоритма производится пересчет центров кластера по формуле вычисления центра масс:

[math] \mu = \cfrac{1}{|S|}\sum_{\mathbf{x}\in S}\mathbf{x}[/math]

[math](3)[/math]

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

1. Инициализировать центры кластеров [math]\mathbf{\mu}_i^{(1)}, \ i=1,...,k[/math]
2. [math]t \leftarrow 1[/math]
3. Распределение по кластерам
[math]\quad S_i^{(t)}=\{\mathbf{x}_p: \lVert\mathbf{x}_p-\mathbf{\mu}_i^{(t)}\rVert^2 \leq \lVert\mathbf{x}_p-\mathbf{\mu}_j^{(t)}\rVert^2 \quad \forall j=1,...,k\},[/math]
[math]\quad[/math]где каждый вектор [math]\mathbf{x}_p[/math] соотносится единственному кластеру [math]S^{(t)}[/math]
4. Обновление центров кластеров
[math]\quad \mathbf{\mu}_i^{(t+1)} = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf{x}_j \in S^{(t)}_i} \mathbf{x}_j [/math]
5. if [math]\exists i \in \overline{1,k}: \mathbf{\mu}_i^{(t+1)} \ne \mathbf{\mu}_i^{(t)}[/math] then
[math]\quad t = t + 1[/math];
[math]\quad[/math]goto 3;
[math]~~~[/math]else
[math]\quad[/math]stop

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

Обозначим [math]\Theta_{\rm centroid}^{d, m}[/math] временную сложность вычисления центорида кластера, число элементов которого равна [math]m[/math], в d-мерном пространстве.

Аналогично [math]\Theta_{\rm distance}^d[/math] – временная сложность вычисления расстояния между двумя d-мерными векторами.

Сложность шага инициализации [math]k[/math] кластеров мощности [math]m[/math] в d-мерном пространстве – [math]\Theta_{\rm init}^{k, d, m}[/math]

• Стратерия Forgy: вычисления не требуются, [math]\Theta_{\rm init}^{k, d, m} = 0[/math]
• Стратегия случайного разбиения: вычисление центров [math]k[/math] кластеров, [math]\Theta_{\rm init}^{k, d, m} = k \cdot \Theta_{\rm centroid}^{d, m}, m \le n[/math]

Cложность шага распределения d мерных векторов по [math]k[/math] кластерам – [math]\Theta_{\rm distribute}^{k, d}[/math]

На этом шаге для каждого вектора [math]\mathbf{x}_i \in X, \ i=1,...,n,[/math] вычисляется [math]k[/math] расстояний до центров кластеров [math]\mathbf{\mu}_1, ...\mathbf{\mu}_k[/math]

[math]\Theta_{\rm distribute}^{k, d} = n \cdot k \cdot \Theta_{\rm distance}^d[/math]

Сложность шага пересчета центров [math]k[/math] кластеров размера [math]m[/math] в d-мерном пространстве – [math]\Theta_{\rm recenter}^{k, d, m}[/math]

На этом шаге вычисляется [math]k[/math] центров кластеров [math]\mathbf{\mu}_1, ...\mathbf{\mu}_k[/math]

[math]\Theta_{\rm recenter}^{k, d, m} = k \cdot \Theta_{\rm centroid}^{d, m}[/math]

Рассчитаем [math]\Theta_{\rm centroid}^{d, m}[/math] для кластера, число элементов которого равно [math]m[/math]

[math]\Theta_{\rm centroid}^{d, m}[/math] = [math]m \cdot d[/math] сложений + [math]d[/math] делений

Рассчитаем [math]\Theta_{\rm distance}^d[/math] в соответствие с формулой [math](2)[/math]

[math]\Theta_{\rm distance}^d[/math] = [math]d[/math] вычитаний + [math]d[/math] умножений + [math](d-1)[/math] сложение

Предположим, что алгоритм сошелся за [math]i[/math] итераций, тогда временная сложность алгоритма [math]\Theta_{\rm k-means}^{d, n}[/math]

[math]\Theta_{\rm k-means}^{d, n} \le \Theta_{\rm init}^{k, d, n} + i(\Theta_{\rm distribute}^{k, d} + \Theta_{\rm recenter}^{k, d, n})[/math]

Операции сложения/вычитания:

[math]\Theta_{\rm k-means}^{d, n} \le knd+ i(kn(2d-1) + knd) = knd+ i(kn(3d-1)) \thicksim O(ikdn)[/math]

Операции умножения/деления:

[math]\Theta_{\rm k-means}^{d, n} \le kd + i(knd + kd) = kd + ikd(n+1) \thicksim O(ikdn) [/math]

Получаем, что временная сложность алгоритма k-means кластеризации [math]n[/math] d-мерных векторов на [math]k[/math] кластеров за [math]i[/math] итераций:

[math] \Theta_{\rm k-means}^{d, n} \thicksim O(ikdn) [/math]

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

Рассмотрим информационный граф алгоритма. Алгоритм k-means начинается с этапа инициализации, после которого следуют итерации, на каждой из которых выполняется два последовательных шага (см. "Схема реализации последовательного алгоритма"):

• распределение векторов по кластерам
• перерасчет центров кластеров

Поскольку основная часть вычислений приходится на шаги итераций, распишем информационные графы данных шагов.

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

Информационный граф шага распределения векторов по кластерам представлен на рисунке 1. Исходами данного графа является исходные векторы [math]\mathbf{x}_1, ..., \mathbf{x}_n[/math], а также центры кластеров [math]\mathbf{\mu}_1, ... \mathbf{\mu}_k[/math], вычисленные ранее (на шаге инициализации, если рассматривается первая итерация алгоритма, или на шаге пересчета центров кластеров предыдущей итерации в противном случае). Каждая пара векторов данных [math]\mathbf{x}_i, \ i=1,...,n,[/math] и центров кластера [math]\mathbf{\mu}_j, \ j=1,...,k[/math] : ([math]\mathbf{x}_i[/math], [math]\mathbf{\mu}_j[/math]) подаются на независимые узлы "d" вычисления расстояния между векторами (более подробная схема вычисления расстояния представлена далее, рисунок 2). Далее узлы вычисления расстояния "d", соответствующие одному и тому же исходному вектору [math]\mathbf{x}_i[/math] передаются на один узел "m", где далее происходит вычисление новой метки кластера для каждого вектора [math]\mathbf{x}_i[/math] (берется кластер с минимальным результатом вычисления расстояния). На выходе графа выдаются метки кластеров , [math]L_1, ..., L_n[/math], такие что [math]\forall \mathbf{x}_i, \ i=1,...,n, \ \mathbf{x}_i \in S_j \Leftrightarrow L_i = j[/math].

Рис. 1. Схема распределения векторов по кластерам. d – вычисление расстояния между векторами; m – вычисление минимума.

Вычисление расстояния между векторами

Подробная схема вычисления расстояния между векторами [math]\mathbf{x}_i, \mathbf{\mu}_j[/math] представлена на рисунке 2. Как показано на графе, узел вычисления расстояния между векторами "d" состоит из шага взятия разности между векторами (узел "[math]-[/math]") и взятия нормы получившегося вектора разности (узел "[math]||\cdot||^2[/math]"). Более подробно, вычисление расстояния между векторами [math]\mathbf{x}_i = {x_{i1,}, ...,{x_{in}}}, \mathbf{\mu}_j = {\mu_{j1}, ...,\mu_{jn}}[/math] может быть представлено как вычисление разности между каждой парой компонент [math](x_{iz}, \mu_{jz}), \ z=1,...,d[/math] (узел "[math]-[/math]"), далее возведение в квадрат для каждого узла "[math]-[/math]" (узел "[math]()^2[/math]") и суммирования выходов всех узлов "[math]()^2[/math]" (узел "[math]+[/math]").

Рис. 2. Схема вычисления расстояния между вектором и центром кластера.

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

Информационный граф шага пересчета центров кластеров представлен на рисунке 3. Исходами данного графа является исходные векторы [math]\mathbf{x}_1, ..., \mathbf{x}_n[/math], а также им соответствующие метки кластера, [math]L_1, ..., L_n[/math], такие что [math]\forall x_i, \ i=1,...,n, \ \mathbf{x}_i \in S_j \Leftrightarrow L_i = j[/math], вычисленные на этапе распределения векторов по кластерам. Все векторы [math]\mathbf{x}_1, ..., \mathbf{x}_n[/math] подаются в узлы [math]+_1, ...+_k[/math], каждый узел [math]+_m, \ m = 1,...,k,[/math] соответствует операции сложения векторов кластера с номером [math]m[/math]. Метки кластера [math]L_1, ..., L_n[/math] также совместно передаются на узлы [math]S_m, \ m=1,...,k[/math], на каждом из которых вычисляется количество векторов в соответствующем кластере (количество меток с соответствующим значением). Далее каждая пара выходов узлов [math]+_m[/math] и [math]S_m[/math] подается на узел "[math]/[/math]", где производится деление суммы векторов кластера на количество элементов в нем. Значения, вычисленные на узлах "[math]/[/math]", присваиваются новым центрам кластеров (выходные значения графа).

Рис. 3. Схема пересчета центров кластеров

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

Работа алгоритма состоит из [math]i[/math] итераций, в каждой из которых происходит распределение [math]d[/math]-мерных векторов по [math]k[/math] кластерам, а также пересчет центров кластеров в [math]d[/math]-мерном пространстве. В шаге распределения [math]d[/math]-мерных векторов по [math]k[/math] кластерам расстояния между вектором и центрами кластеров вычисляются независимо (отсутствуют информационные зависимости). Центры масс кластеров также пересчитываются независимо друг от друга. Таким образом, имеет место массовый параллелизм. Вычислим параллельную сложность [math]\Psi_*[/math] каждого из шагов, а также параллельную сложность всего алгоритма, [math]\Psi_{\rm k-means}[/math]. Будем исходить из предположения, что может быть использовано любое необходимое число потоков.

Распределение [math]d[/math]-мерных векторов по [math]k[/math] кластерам

Поскольку на данном шаге для каждой пары векторов [math]\mathbf{x}_i, \ i=1,...,n[/math] и [math]\mathbf{\mu}_j, \ j=1,...,k,[/math] операции вычисления расстояния не зависят друг от друга, они могут выполняться параллельно. Тогда, разделив все вычисление расстояний на [math]n[/math] потоков, получим, что в каждом потоке будет выполняться только одна операция вычисления расстояния между векторами размерности [math]d[/math]. При этом каждому вычислительному потоку передаются координаты центров всех кластеров [math]\mathbf{\mu}_1, ..., \mathbf{\mu}_k[/math]. Таким образом, параллельная сложность данного шага определяется сложностью параллельной операции вычисления расстояния между [math]d[/math]-мерными векторами, [math]\Psi_{\rm distance}^d[/math] и сложностью определения наиболее близкого кластера (паралельное взятие минимума по расстояниям), [math]\Psi_{\rm min}^k[/math]. Для оценки [math]\Psi_{\rm distance}^d[/math] воспользуемся параллельной реализацией нахождения частичной суммы элементов массива путем сдваивания. Аналогично, [math]\Psi_{\rm min}^k = log(k)[/math]. В результате, [math]\Psi_{\rm distance}^d = O(\log(d))[/math]. Таким образом:

[math]\Psi_{\rm distribute}^{k, d} = \Psi_{\rm distance}^d + \Psi_{\rm min}^k = O(log(d))+O(log(k)) = O(log(kd))[/math]

Пересчет центров кластеров в d-мерном пространстве

Поскольку на данном шаге для каждого из [math]k[/math] кластеров центр масс может быть вычислен независимо, данные операции могут быть выполнены в отдельных потоках. Таким образом, параллельная сложность данного шага, [math]\Psi_{\rm recenter}^{k, d}[/math], будет определяться параллельной сложностью вычисления одного центра масс кластера размера [math]m[/math], [math]\Psi_{\rm recenter}^{k, d}[/math], а так как [math]m \le n \Rightarrow \Psi_{\rm recenter}^{d, m} \le \Psi_{\rm recenter}^{d, n}[/math]. Сложность вычисления центра масс кластера [math]d[/math]-мерных векторов размера n аналогично предыдущим вычислениям равна [math]O(log(n))[/math]. Тогда:

[math]\Psi_{\rm recenter}^{k, d} \le \Psi_{\rm recenter}^{d, n} = O(log(n))[/math]

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

На каждой итерации необходимо обновление центров кластеров, которые будут использованы на следующей итерации. Таким образом, итерационный процесс выполняется последовательно. Тогда, поскольку сложность каждой итерации определяется [math]\Psi_{\rm distribute}^{k, d}[/math] и [math]\Psi_{\rm recenter}[/math], сложность всего алгоритма, [math]\Psi_{\rm k-means}[/math] в предположении, что было сделано [math]i[/math] операций определяется выражением

[math]\Psi_{\rm k-means} \approx i \cdot (\Psi_{\rm distribute}^{k, d} + \Psi_{\rm recenter}^{k, d}) \le i \cdot O(log(kdn))[/math]

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

Входные данные

• Матрица из [math]n \cdot d[/math] элементов [math]x_{i, j} \in \mathbb{R}, \ i=1,...,n, \ j=1,...,d,[/math] – координат векторов (наблюдений).
• Целое положительное число [math]k, \ k \le n[/math] – количество кластеров.

Объем входных данных
[math]1[/math] целое число + [math]n \cdot d[/math] вещественных чисел (при условии, что координаты – вещественные числа).

Выходные данные
[math]n[/math] целых положительных чисел [math]L_1, ..., L_n[/math]– номера кластеров, соотвествующие каждому вектору (при условии, что нумерация кластеров начинается с [math]1[/math]).

Объем выходных данных
[math]n[/math] целых положительных чисел.

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

Вычислительная мощность

Вычислительная мощность алгоритма k-means равна [math]\frac{ikdn}{nd} = ki [/math], где [math]k[/math] – число кластеров, [math]i[/math] – число итераций алгоритма.

Детерминированность и Устойчивость

Алгоритм k-means является итерационным. Количество итераций алгоритма в общем случае не фиксируется и зависит от начального расположения объектов в пространстве, параметра [math]k[/math], а также от начального приближения центров кластеров, [math]\mu_1, ..., \mu_k[/math]. В результате этого может варьироваться результат работы алгоритма. При неудачном выборе начальных параметров итерационный процесс может сойтись к локальному оптимуму. По этим причинам алгоритм не является ни детермирированным, ни устойчивым.

Соотношение последовательной и параллельной сложности алгоритма

[math]\frac{\Theta_{\rm k-means}}{\Psi_{\rm k-means}} = \frac{O(ikdn)}{O(i \cdot log(kdn))}[/math]

Сильные стороны алгоритма:

• Сравнительно высокая эффективность при простоте реализации
• Высокое качество кластеризации
• Возможность распараллеливания
• Существование множества модификаций

Недостатки алгоритма:

• Количество кластеров является параметром алгоритма

• Чувствительность к начальным условиям

  Инициализация центров кластеров в значительной степени влияет на результат кластеризации.

• Чувствительность к выбросам и шумам

  Выбросы, далекие от центров настоящих кластеров, все равно учитываются при вычислении их центров.

• Возможность сходимости к локальному оптимуму

  Итеративный подход не дает гарантии сходимости к оптимальному решению.

• Использование понятия "среднего"

  Алгоритм неприменим к данным, для которых не определено понятие "среднего", например, категориальным данным.

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

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

В настоящем разделе проведено исследование масштабируемости различных параллельных реализации алгоритма [math]k[/math] средних согласно методике AlgoWiki.

2.4.1 Реализация 1

Исследование масштабируемости параллельной реализации алгоритма k-means проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. Алгоритм реализован на языке C с использованием средств MPI. Для исследования масштабируемости проводилось множество запусков программы с разным значением параметра (количество векторов для кластеризации), а также с различным числом процессоров. Фиксировались результаты запусков – время работы [math]t[/math] и количество произведенных итераций алгоритма [math]i[/math].

Параметры запусков для экспериментальной оценки:

• Значения количества векторов [math]n[/math]: 20'000, 30'000, 50'000, 100'000, 200'000, 300'000, 500'000, 700'000, 1'000'000, 1'500'000, 2'000'000.
• Значения количества процессоров [math]p[/math]: 1, 8, 16, 32, 64, 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448, 480, 512.
• Значение количества кластеров [math]k[/math]: 100.
• Значение размерности векторов [math]d[/math]: 10.

Для проведения экспериментов были сгенерированы нормально распределенные псевдослучайные данные (с использованием Python библиотеки scikit-learn):

from sklearn.datasets import make_classification
X1, Y1 = make_classification(n_features=10, n_redundant=2, n_informative=8,
                             n_clusters_per_class=1, n_classes=100,
                             n_samples=2000000)

Для заданной конфигурации эксперимента ([math]n, d, p, k[/math]) и полученных результатов ([math]t, i[/math]) производительность и эффективность реализации расчитывались по формулам:

• [math]{\rm Performance} = \frac{N_{\rm k-means}^{d, n}}{t}\ \ ({\rm FLOPS}),[/math]

где [math]N_{\rm k-means}^{d, n}[/math] – точное число операций с плавающей точкой (операции с памятью, а также целочисленные операции не учитывались), вычисленное в соответствие с разделом "Последовательная сложность алгоритма";

• [math]{\rm Efficiency} = \frac{100 \cdot {\rm Performance}}{{\rm Performance}_{\rm Peak}^{p}}\ \ (\%),[/math]

где [math]{\rm Performance}_{\rm Peak}^{p}[/math] – пиковая производительность суперкомпьютера при [math]p[/math] процессорах, вычисленная согласно спецификациям Intel^® XEON^® X5670.

Графики зависимости производительности и эффективности параллельной реализации k-means от числа векторов для кластеризации ([math]n[/math]) и числа процессоров ([math]p[/math]) представлены на рисунках 4 и 5, соответственно.

Рис. 4. Параллельная реализация k-means. График зависимости производительности реализации алгоритма от числа векторов для кластеризации ([math]n[/math]) и числа процессоров ([math]p[/math]).

Рис. 5. Параллельная реализация k-means. График зависимости эффективности реализации алгоритма от числа векторов для кластеризации ([math]n[/math]) и числа процессоров ([math]p[/math]).

В результате экспериментальной оценки были получены следующие оценки эффективности реализации:

• Минимальное значение: 0.000409 % достигается при [math]n=20'000, p=480[/math]
• Максимальное значение: 0.741119 % достигается при [math]n=300'000, p=1[/math]

Оценки масштабируемости реализации алгоритма k-means:

• По числу процессоров: -0.002683 – эффективность убывает с ростом числа процессоров. Данный результат вызван ростом накладных расходов для обеспечения параллельного выполнения алгоритма.
• По размеру задачи: 0.002779 – эффективность растет с ростом числа векторов. Данный результат вызван тем, что при увеличении размера задачи, количество вычислений растет по сравнению с временем, затрачиваемым на пересылку данных.
• Общая оценка: -0.000058 – можно сделать вывод, что в целом эффективность реализации незначительно уменьшается с ростом размера задачи и числа процессоров.

Использованная параллельная реализация алгоритма k-means

2.4.2 Реализация 2

Исследование также проводилось на суперкомпьютере "Ломоносов".

Набор данных для тестирования состоял из 946000 векторов размерности 2 (координаты на сфере)

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

• число процессов (виртуальных ядер) [8 : 512];
• число кластеров [128 : 384].

В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:

• минимальная эффективность реализации [math]2,47%[/math] достигается при делении исходных данных на 128 кластеров с использованием 512 процессов;
• максимальная эффективность реализации [math]7,13%[/math] достигается при делении исходных данных на 352 кластера с использованием 8 процессов.

На рисунках 6 и 7, соответственно, представлены графики зависимости производительности и эффективности параллельной реализации k-means от числа кластеров и числа процессов.

Рис. 6. График зависимости производительности параллельной реализации алгоритма от числа кластеров и числа процессов.

По рис. 6 можно отметить практически полное отсутствие роста производительности с увеличением числа процессов от 256 до 512 при минимальном размере задачи. Это связано с быстрым ростом накладных расходов по отношению к крайне низкому объёму вычислений. При росте размерности задачи данный эффект пропадает, и при одновременном пропорциональном увеличении числа кластеров и числа процессов рост производительности становится близким к линейному.

Рис. 7. График зависимости эффективности параллельной реализации алгоритма от числа кластеров и числа процессов.

Исследовалась параллельная реализация алгоритма k-means на MPI.

Были получены следующие оценки масштабируемости реализации алгоритма k-means:

• По числу процессов: [math]-0.02209[/math]. Следовательно, с ростом числа процессов эффективность уменьшается. На рис. 7 можно наблюдать плавное и равномерное снижение производительности по мере увеличения числа процессов при неизменном числе кластеров, что свидетельствует об относительно невысоком росте накладных расходов на передачу данных между процессами и преобладании объёма вычислений над объёмом пересылок данных по сети.
• По размеру задачи: [math]0.01252[/math]. Следовательно, с ростом размера задачи (числа кластеров) эффективность увеличивается. При этом объём пересылок данных по сети пропорционален [math](n + k) \cdot p[/math] (где [math]k[/math] - число кластеров, [math]n[/math] - число входных векторов, [math]p[/math] - число процессов) таким образом, поскольку [math]k \lt \lt n[/math], рост накладных расходов с ростом числа кластеров при неизменном числе процессов и входных векторов представляет собой незначительную величину.
• Общая оценка: [math]-0.00081[/math]. Таким образом, с ростом и размера задачи, и числа процессов эффективность уменьшается. Это связано с тем, что отношение объёма вычислений к объёму передаваемых данных изменяется пропорционально [math]{kn \over (n + k) \cdot p} \thicksim {k \over p}[/math], что представляет собой невысокий коэффициент, но при этом позволяет параллельной реализации не деградировать до нулевой эффективности при значительном увеличении числа процессов.

2.4.3 Реализация 3

Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара. Исследование происходило на суперкомпьютере Jaguar - Cray XT5. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.

Реализация алгоритма была выполнена на языке программирования C с использованием MPI.

Объем данных составлял 84 ГБ, количество объектов (d-мерных векторов) n равнялось 1,024,767,667, размерность векторов [math]d[/math] равнялась 22, количество кластеров [math]k[/math] равнялось 1000.

На рис. 8 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.

Рис. 8. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (из работы: Kumar etc. 2011).

Также было произведено самостоятельное исследование масштабируемости алгоритма k-means. Исследование производилось на суперкомпьютере "Blue Gene/P".

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

• число процессоров [1, 2, 4, 8, 16, 32, 64, 128, 256, 512];
• количество объектов [5000, 10000, 25000, 50000].

Был использован набор данных Dataset for Sensorless Drive Diagnosis Data Set из репозитория Machine learning repository.

Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.

Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI. Код можно найти здесь: https://github.com/serban/kmeans. Данная реализация предоставляет возможность распараллеливать решение задачи с помощью технологий MPI, OpenMP И CUDA. Для запуска MPI-версии программы использовалась цель "mpi_main" Makefile.

На рис. 9 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.

Рис. 9. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.

На рис. 10 показана эта же зависимость, только в трехмерном пространстве. По аналогии с рис. 9, были использованы логарифмические оси. Как и в случае двумерного рисунка, можно видеть близкое к линейному увеличение времени работы программы.

Рис. 10. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.

2.4.4 Реализация 4

Исследование масштабируемости данной параллельной реализации алгоритма k-средних также проводилось на суперкомпьютере "Ломоносов". Параллельная реализация была написана самостоятельно на языке C, ссылка на реализацию. Так как на каждой итерации число действий на единицу данных не велико и данные должны быть собраны вместе при перерасчете центроидов, было решено для ускорения вычислений воспользоваться только OpenMP без использовании MPI.

Код собирался под gcc c опцией -fopenmp. Код считался на одном процессоре, технология hyperthreading не использовалась.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

• число процессоров [1 : 16] с увеличением в 2 раза;
• размер данных [100000 : 1600000] с увеличением в 2 раза.

В результате проведённых экспериментов были получены следующие данные:

• Максимальная эффективность в точке достигается при переходе от 1 потока на 4 при минимальном размере данных, она равна [math]87,5%[/math].
• Усредненная максимальная эффективность достигается при переходе с одного потока на два. Среднее время вычислений на всех рассмотренных потока снижается с 16,33 до 11.87 секунд, поэтому формально эффективность [math]= 16.33 / 11.87 / 2 \approx 68,4\%[/math]
• Минимальная эффективность в точке достигается при переходе от 1 потока на 16 при размере данных 800000, она равна [math]11,1\%[/math].
• Усредненная минимальная эффективность наблюдается при переходе с одного на максимальное рассматриваемое в эксперименте число потоков, равное 16. Время вычисления изменяется с 16,33 до 7,6 секунд, поэтому формально эффективность [math] = 16.33 / 7.6 / 16 \approx 14,9\%[/math]

Ниже приведены графики зависимости вычислительного времени алгоритма и его эффективности от изменяемых параметров запуска — размера данных и числа процессоров:

Рис. 11. Параллельная реализация алгоритма k-средних. Изменение вычислительного времени алгоритма в зависимости от числа процессоров и размера исходных данных.

Здесь видно, что время выполнения операций алгоритма плавно убывает по каждому из параметров, причем скорость убывания по параметру числа процессоров выше, чем в зависимости от размерности задачи.

Рис. 12. Параллельная реализация алгоритма k-средних. Изменение эффективности алгоритма в зависимости от числа процессоров и размера исходных данных.

Здесь построена эффективность перехода от последовательной реализации к параллельной. Рассчитывается она по формуле Время вычисления на 1 потоке / Время вычисления на [math]T[/math] потоках / [math]T[/math], где [math]T[/math] — это число потоков. При вычислении на 1 процессоре она равна 100 \% в силу используемой формулы, что и отражено на графике.

Проведем оценки масштабируемости:

По числу процессов — при увеличении числа процессов эффективность уменьшается на всей области рассматриваемых значений, причем темп убывания замедляется с ростом числа процессов.

По размеру задачи — при увеличении размера задачи эффективность вычислений вначале кратковременно возрастает, но затем начинает относительно равномерно убывать на всей рассматриваемой области.

По размеру задачи — при увеличении размера задачи эффективность вычислений в общем случае постепенно убывает. На малых данных она выходит на пик мощности, являющийся максимумом эффективности в исследуемых условиях, но затем возвращается к процессу убывания.

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

В однопоточном режиме на наборах данных, представляющих практический интерес (порядка нескольких десятков тысяч векторов и выше), время работы алгоритма неприемлемо велико. Благодаря свойству массового параллелизма должно наблюдаться значительное ускорение алгоритма на многоядерных архитектурах (Intel Xeon), а также на графических процессорах, даже на мобильных вычислительных системах (ноутбуках), оснащенных видеокартой. Алгоритм k-means также будет демонстрировать значительное ускорение на сверхмощных вычислительных комплексах (суперкомпьютерах, системах облачных вычислений).

На сегодняшний день существует множество реализаций алгоритма k-means, в частности, направленных на оптимизацию параллельной работы на различных архитектурах. Предлагается множество адаптаций алгоритма под конкретные архитектуры. Например, авторы работы производят перерасчет центров кластеров на этапе распределения векторов по кластерам.

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

2.7.1 Открытое программное обеспечение

1. CrimeStat
Программное обеспечение, созданное для операционных систем Windows, предоставляющее инструменты статистического и пространственного анализа для решения задачи картирования преступности.
2. Julia
Высокоуровневый высокопроизводительный свободный язык программирования с динамической типизацией, созданный для математических вычислений, содержит реализацию k-means.
3. Mahout
Apache Mahout - Java библиотека для работы с алгоритмами машинного обучения с использованием MapReduce. Содержит реализацию k-means.
4. Octave
Написанная на C++ свободная система для математических вычислений, использующая совместимый с MATLAB язык высокого уровня, содержит реализацию k-means.
5. Spark
Распределенная реализация k-means содержится в библиотеке Mlib для работы с алгоритмами машинного обучения, взаимодействующая с Python библиотекой NumPy и библиотека R.
6. Torch
MATLAB-подобная библиотека для языка программирования Lua с открытым исходным кодом, предоставляет большое количество алгоритмов для глубинного обучения и научных расчётов. Ядро написано на Си, прикладная часть выполняется на LuaJIT, поддерживается распараллеливание вычислений средствами CUDA и OpenMP. Существуют реализации k-means.
7. Weka
Cвободное программное обеспечение для анализа данных, написанное на Java. Содержит k-means и x-means.
8. Accord.NET
C# реализация алгоритмов k-means, k-means++, k-modes.
9. OpenCV
Написанная на С++ библиотека, направленная в основном на решение задач компьютерного зрения. Содержит реализацию k-means.
10. MLPACK
Масштабируемая С++ библиотека для работы с алгоритмами машинного обучения, содержит реализацию k-means.
11. SciPy
Библиотека Python, содержит множество реализаций k-means.
12. scikit-learn
Библиотека Python, содержит множество реализаций k-means.
13. R
Язык программирования для статистической обработки данных и работы с графикой, а также свободная программная среда вычислений с открытым исходным кодом в рамках проекта GNU, содержит три реализации k-means.
14. ELKI
Java фреймворк, содержащий реализацию k-means, а также множество других алгоритмов кластеризации.

2.7.2 Проприетарное программное обеспечение

1. Ayasdi
2. Stata
3. Mathematica
4. MATLAB
5. SAS
6. RapidMiner
7. SAP HANA