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

Вычисление расстояния между векторами
Подробная схема вычисления расстояния между векторами xi,μj представлена на рисунке 2. Как показано на графе, узел вычисления расстояния между векторами "d" состоит из шага взятия разности между векторами (узел "−") и взятия нормы получившегося вектора разности (узел "||⋅||2"). Более подробно, вычисление расстояния между векторами xi=xi1,,...,xin,μj=μj1,...,μjn может быть представлено как вычисление разности между каждой парой компонент (xiz,μjz), z=1,...,d (узел "−"), далее возведение в квадрат для каждого узла "−" (узел "()2") и суммирования выходов всех узлов "()2" (узел "+").

Рис. 2. Схема вычисления расстояния между вектором и центром кластера.
Пересчет центров кластеров
Информационный граф шага пересчета центров кластеров представлен на рисунке 3. Исходами данного графа является исходные векторы x1,...,xn, а также им соответствующие метки кластера, L1,...,Ln, такие что ∀xi, i=1,...,n, xi∈Sj⇔Li=j, вычисленные на этапе распределения векторов по кластерам. Все векторы x1,...,xn подаются в узлы +1,...+k, каждый узел +m, m=1,...,k, соответствует операции сложения векторов кластера с номером m. Метки кластера L1,...,Ln также совместно передаются на узлы Sm, m=1,...,k, на каждом из которых вычисляется количество векторов в соответствующем кластере (количество меток с соответствующим значением). Далее каждая пара выходов узлов +m и Sm подается на узел "/", где производится деление суммы векторов кластера на количество элементов в нем. Значения, вычисленные на узлах "/", присваиваются новым центрам кластеров (выходные значения графа).

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

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

Работа алгоритма состоит из i итераций, в каждой из которых происходит распределение d-мерных векторов по k кластерам, а также пересчет центров кластеров в d-мерном пространстве. В шаге распределения d-мерных векторов по k кластерам расстояния между вектором и центрами кластеров вычисляются независимо (отсутствуют информационные зависимости). Центры масс кластеров также пересчитываются независимо друг от друга. Таким образом, имеет место массовый параллелизм. Вычислим параллельную сложность Ψ∗ каждого из шагов, а также параллельную сложность всего алгоритма, Ψk−means. Будем исходить из предположения, что может быть использовано любое необходимое число потоков.