Уровень алгоритма

Участник:Viktorrulev/Алгоритм устойчивой кластеризации с иcпользованием связей

Материал из Алговики
Перейти к навигации Перейти к поиску
Symbol wait.svgЭта работа прошла предварительную проверку
Дата последней правки страницы:
16.12.2016
Данная работа соответствует формальным критериям.
Проверено Teplov.


Symbol wait.svgЭта работа ждет рассмотрения преподавателем
Дата последней правки страницы:
16.12.2016
Авторы этой статьи считают, что задание выполнено.



Алгоритм устойчивой кластеризации с иcпользованием связей
Последовательный алгоритм
Последовательная сложность [math]O(M^2 + M^2m_{nbr} + M^{2}logM)[/math]
Объём входных данных [math]M \times N[/math]
Объём выходных данных [math]M[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O(MlogM)[/math]
Ширина ярусно-параллельной формы [math]O(M^2)[/math]


Автор описания: В.А. Рулев.

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

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

Кластеризация (кластерный анализ) — задача разбиения заданной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Каждый объект из выборки характеризуется рядом признаков, которые могут быть вещественными, целочисленными, категорийными (то есть принимающими значения из какого-либо конечного множества), бинарными (принимающими только два значения, обычно [math]true[/math] или [math]false[/math]).

Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK) был предложен в 2000 году Sudipto Guha (Stanford University), Rajeev Rastogi (Bell Laboratories) и Kyuseok Shim (Bell Laboratories) [1] для кластеризации объектов с бинарными признаками. При этом алгоритм особенно эффективен, если у каждого объекта лишь небольшое количество признаков имеет значение [math]true[/math].

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

В ходе кластеризации [math]M[/math] имеющихся объектов [math]P=\{p_1,...,p_M\}[/math] (каждый объект имеет [math]N[/math] признаков) должны быть разделены на [math]K[/math] непересекающихся подмножеств (кластеров) [math]C_1, ..., C_K[/math] таким образом, чтобы полученные кластеры максимизировали некоторую критериальную функцию [math]E(C_1, ..., C_K)[/math].

Будет называть два объекта [math]p_1[/math] и [math]p_2[/math] соседями, если мера сходства [math]neighbour(p_1,p_2)[/math] этих объектов больше некоторого заранее заданного порогового значения [math]\theta[/math] В качестве меры сходства в алгоритме устойчивой кластеризации с использованием связей используется основанная на коэффициенте Жаккара мера сходства [math]sim(p_1,p_2)[/math]. В ней [math]N(C_i)^{1+2f(\theta)}[/math] имеет смысл ожидаемого (среднего) количества связей внутри одного кластера.

Количеством связей [math]link(p_1,p_2)[/math] между двумя объектами [math]p_1[/math] и [math]p_2[/math] будем называть количество общих соседей этих объектов.

Для того, чтобы сформировать кластеры, удовлетворяющие поставленному условию, необходимо последовательно объединять среди имеющихся кластеров такие пары кластеров, для которых метрика [math]goodness(C_i,C_j)[/math] достигает максимального значения среди всех пар кластеров. На начальном этапе каждый объект считается отдельным кластером.

Формулы метода:

[math] neighbour(p_1,p_2)=(sim(p_1,p_2)\gt \theta) [/math]


[math] sim(p_1,p_2)=\frac{N(p_1 \cap p_2)}{N(p_1 \cup p_2)} [/math]


[math] link(p_1,p_2)=N \Big( \{ p \in P | sim(p_1,p) \lt \theta \} \cap \{ p \in P | sim(p_2,p) \lt \theta \} \Big) [/math]


[math] E(C_1,...,C_K)=\sum_{i=1}^{K}N(C_i) \ast \sum_{p_q,p_r \in C_i}\frac{link(p_q,p_r)}{N(C_i)^{1+2f(\theta)}} [/math]


[math] f(\theta)=\frac {1-\theta}{1+\theta} [/math]


[math] goodness(C_i,C_j)=\frac {\sum_{p_r \in C_i, p_q \in C_j}{link(p_r,p_q)}} {(N(C_i) + N(C_j))^{1+2f(\theta)} - N(C_i)^{1+2f(\theta)} - N(C_j)^{1+2f(\theta)}} [/math]

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

Вычислительное ядро алгоритма можно разделить на два основных этапа:

  1. Вычисление количества связей между каждой парой объектов ([math]\frac {M \times M} {2}[/math] вычислений количества связей)
  2. Последовательные объединения пар наиболее подходящих кластеров ([math]M-K[/math] поисков пар и объединений)

Подробнее оба этапа будут описаны ниже.

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

На макроуровне можно выделить следующие шаги алгоритма:

Шаг 1: вычисление соседних объектов.

Шаг 2: вычисление количества связей между всеми объектами.

Шаг 3: построение для каждого кластера упорядоченного списка значений метрики goodness со всеми остальными кластерами

Шаг 4: построение общего упорядоченного списка значений метрики goodness

Шаг 5 (повторяется то тех пор, пока количество кластеров не достигнет желаемого)

Шаг 5.1: объединение двух кластеров с наилучшим goodness

Шаг 5.2: обновление списков кластеров

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

Ниже приведен псевдокод схемы реализации последовательного алгоритма:

procedure compute_links(P)
begin
  for each p[i], p[j] in P do
    if sim(p[i], p[j]) > theta
      is_neighbour[i, j] = true
    else
      is_neighbour[i, j] = false

  links[i, j] = 0
  for each p[i], p[j] in P do
    for p[k] in P do
      if is_neighbour[i, k] && is_neighbour[j, k]
        links[i, j] = links[i, j] + 1
end

procedure cluster(P, k)
begin
  links := compute_links(P)

  for each p in P do
    q[p] := build_local_list(links, p)
  Q := build global_list(P, q)

  while size(Q) > k do
  begin
    u := extract_max(Q)
    v := extract_max(q[u])
    w := merge(u, v)
    delete(Q, v)

    for each x in (q[u] or q[v]) do
    begin
      delete(q[x], u);
      delete(q[x], v)
      insert(q[x], w, goodness(x, w))
      insert(q[w], x, goodness(x, w))
      update(Q, x, q[x])
    end

    insert(Q, w, q[w])
    deallocate(q[u])
    deallocate(q[v])
  end
end

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

Рассмотрим сложности шагов алгоритма из раздела 1.4.

Шаг 1: выполняется с помощью двух вложенных циклов и содержит [math]O(M^2)[/math] операций

Шаг 2: задача сводится к умножению полученной на предыдущем шаге матрицы соседства на саму себя. Это действие быть выполнено с помощью наивного метода за [math]O(M^3)[/math] операций. С помощью алгоритма Копперсмита — Винограда это можно сделать за [math]O(M^{2.37})[/math] операций.[2] В случае, если среднее количество соседей каждого объекта значительно меньше общего количества объектов, связи могут быть вычислены за [math]O(M^2m_{nbr})[/math], где [math]m_{nbr}[/math] - среднее количество соседей объекта.

Шаг 3: имеет сложность [math]O(M)[/math].[3]

Шаг 4: имеет сложность [math]O(M)[/math].

Шаг 5: вычислительная сложность каждой итерации цикла составляет [math]O(MlogM)[/math], так как в худшем случае в ходе итерации выполняется [math]M[/math] вставок элемента в упорядоченный список. Желаемое количество кластеров [math]K[/math] мало по сравнению с [math]M[/math], следовательно можно считать, что нужно выполнить [math]M[/math] итераций цикла. Таким образом, общая вычислительная сложность цикла равна [math]O(M^{2}logM)[/math].

Таким образом, общую последовательную сложность алгоритма в общем случае можно оценить, как

[math]O(M^2 + M^{2.37} + M^{2}logM)[/math]

или в случае небольшого количества соседних объектов для каждого объекта выборки, как

[math]O(M^2 + M^2m_{nbr} + M^{2}logM)[/math].

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

Информационный граф перемножения плотных матриц с подробным описанием представлен в статье перемножение плотных матриц

Ниже представлен информационный граф наиболее интересного для рассмотрения этапа алгоритма устойчивой кластеризации с использованием связей - тела цикла (полупрозрачным показана следующая итерация цикла) при [math]n=5[/math].

Рисунок 1. Граф тела цикла; merge - объединение кластеров, insert - вставка goodness с новым кластером в упорядоченные списки соответствующих кластеров.

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

Шаг 1: каждая итерация цикла может быть выполнена независимо от всех остальных. Таким образом, в этом случае ширина ЯПФ равна [math]O(M^2)[/math], а высота - [math]O(1)[/math].

Шаг 2: при использовании алгоритма наивного перемножения плотных матриц высота ЯПФ равна [math]O(M)[/math], а ширина - [math]O(M^2)[/math] (см. перемножение плотных матриц)

Шаг 3: имеет небольшую асимптотическую сложность, может быть выполнен последовательно.

Шаг 4: имеет небольшую асимптотическую сложность, может быть выполнен последовательно.

Шаг 5: каждая итерация цикла может быть выполнена только после полного завершения предыдущей, а внутри каждой отдельной итерации все вставки могут быть выполнены независимо друг от друга. Следовательно ширина ЯПФ в этом случае равна [math]O(M)[/math], а высота ЯПФ равна [math]O(MlogM)[/math].

Таким образом, высота ЯПФ зависит от размерности задачи как [math]O(MlogM)[/math], а ширина ЯПФ - как [math]O(M^2)[/math].

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

Входные данные: информация об [math]M[/math] объектах, каждая их которых имеет [math]N[/math] бинарных атрибутов.

Объём входных данных: [math]M \times N[/math] бинарных переменных. В силу того, что обычно в большинстве случаев лишь небольшое количество атрибутов объекта имеет значение "true", каждый объект можно хранить в виде списка номеров атрибутов, значения которых равны "true".

Выходные данные: [math]K[/math] кластеров.

Объём выходных данных: [math]M[/math] индексов объектов, распределенных в [math]K[/math] списков.

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

Вычислительная сложность последовательного алгоритма в общем случае равна [math]O(M^{2.37})[/math], а в случае небольшого количества соседних объектов у каждого объекта сложность равна [math]O(M^{2})[/math].

Вычислительная мощность алгоритма (соотношение количества операций к объему входных и выходных данных) в общем случае равна O(M^{1.37}), в а случае небольшого количества соседних объектов (то есть в том случае, для которого и разрабатывался алгоритм) вычислительная мощность линейна.

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

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

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

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

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

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

Проведём исследование масштабируемости параллельной реализации алгоритма устройчивой кластеризации с использованием связей, выполненной с использованием OpenMP. Исследование проводилось на персональном компьютере HP Pavilion dv6 (процессор Intel Core i7 3610QM 2300 МГц, 8 логических ядер).

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

  • число нитей [1 : 8] с шагом 1;
  • количество точек [500 : 1500] с шагом 100.

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

Рисунок 2. Параллельная реализация алгоритма устойчивой кластеризации с использованием связей. Изменение времени выполнения кластеризации в зависимости от количества точек и от количества параллельных нитей.

Время выполнения кластеризации:

500 объектов 1000 объектов 1500 объектов
1 нить 7.930 с 63.308 с 214.692 с
4 нити 4.815 с 37.275 с 126.502 с
8 нитей 5.312 с 39.986 с 135.251 с

Реализация алгоритма была выполнена автором статьи.[4]

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

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

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

Алгоритм устойчивой кластеризации с иcпользованием связей реализован в пакете CBA языка R.[5]

3 Литература

<references \>

  1. Sudipto Guha, Rajeev Rastogi, Kyuseok Shim ROCK: A robust clustering algorithm for categorical attributes. 2000. Information Systems. Vol 25, Issue 5, Pages 345-366
  2. Donald Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proc. of the 19th Annual ACM Symposium on Theory of Computing. 1987.
  3. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. The MIT Press, Massachusetts, 1990.
  4. https://gitlab.com/viktorrulev/superprak-1/tree/master
  5. https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/RockCluster