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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
← Предыдущая правка
Нет описания правки
 
(не показано 77 промежуточных версий 3 участников)
Строка 1: Строка 1:
{{Assignment|Teplov}}
{{algorithm
{{algorithm
| name              = Алгоритм устойчивой кластеризации с иcпользованием связей
| name              = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math>...</math>
| serial_complexity = <math>O(M^2 + M^2m_{nbr} + M^{2}logM)</math>
| pf_height        = <math>...</math>
| pf_height        = <math>O(MlogM)</math>
| pf_width          = <math>...</math>
| pf_width          = <math>O(M^2)</math>
| input_data        = <math>...</math>
| input_data        = <math>M \times N</math>
| output_data      = <math>...</math>
| output_data      = <math>M</math>
}}
}}


Строка 14: Строка 16:
=== Общее описание алгоритма ===
=== Общее описание алгоритма ===


Кластеризация (кластерный анализ) — задача разбиения заданной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Каждый объект из выборки характеризуется рядом признаков, которые могут быть вещественными, целочисленными, категорийными (то есть принимающими значения из какого-либо множества) и другими. Множество значений, которые может принимать признак, называется доменом этого признака. Так, например, у объекта '''кошка''' может быть категорийный признак '''порода''', доменом которого является множество '''[персидская, бенгальская, сфинкс, мейн-кун, ...]'''.
Кластеризация (кластерный анализ) — задача разбиения заданной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Каждый объект из выборки характеризуется рядом признаков, которые могут быть вещественными, целочисленными, категорийными (то есть принимающими значения из какого-либо конечного множества), бинарными (принимающими только два значения, обычно <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) <ref>Sudipto Guha, Rajeev Rastogi, Kyuseok Shim ROCK: A robust clustering algorithm for categorical attributes. 2000. Information Systems. Vol 25, Issue 5, Pages 345-366</ref> для кластеризации объектов с категорийными признаками.


Алгоритм устойчивой кластеризации с использованием связей предназначен для работы с объектами типа "транзакция" ("покупательская корзина"). Транзакция представляет собой множество товаров, приобретенных покупателем у поставщика. Каждому товару, который есть в наличии у поставщика, в транзакции соответствует отдельный признак, который принимает значение '''true''', если товар присутствует в транзакции, и '''false''', если товар в транзакции отсутствует.
'''Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK)''' был предложен в 2000 году Sudipto Guha (Stanford University), Rajeev Rastogi (Bell Laboratories) и Kyuseok Shim (Bell Laboratories) <ref>Sudipto Guha, Rajeev Rastogi, Kyuseok Shim ROCK: A robust clustering algorithm for categorical attributes. 2000. Information Systems. Vol 25, Issue 5, Pages 345-366</ref> для кластеризации объектов с бинарными признаками. При этом алгоритм особенно эффективен, если у каждого объекта лишь небольшое количество признаков имеет значение <math>true</math>.


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


В ходе кластеризации <math>M</math> имеющихся транзакций <math>P=\{p_1,...,p_M\}</math> должны быть разделены на <math>K</math> непересекающихся подмножеств (кластеров) <math>C_1, ..., C_K</math> таким образом, чтобы полученные кластеры максимизировали некоторую критериальную функцию <math>E(C_1, ..., C_K)</math>.
В ходе кластеризации <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>\theta</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>sim(p_1,p_2)<\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>sim(p_1,p_2)=\frac{N(p_1 \cap p_2)}{N(p_1 \cup p_2)}</math>
Формулы метода:
:<math>
neighbour(p_1,p_2)=(sim(p_1,p_2)>\theta)
</math>
<br>
:<math>
sim(p_1,p_2)=\frac{N(p_1 \cap p_2)}{N(p_1 \cup p_2)}
</math>
<br>
:<math>
link(p_1,p_2)=N \Big( \{ p \in P | sim(p_1,p) < \theta \} \cap \{ p \in P | sim(p_2,p) < \theta \} \Big)
</math>
<br>
:<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>
<br>
:<math>
f(\theta)=\frac {1-\theta}{1+\theta}
</math>
<br>
:<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>


'''Количеством связей''' между двумя транзакциями будем называть количество общих соседей этих транзакций, то есть
=== Вычислительное ядро алгоритма ===


<math>link(p_1,p_2)=N \Big( \{ p \in P | sim(p_1,p) < \theta \} \cap \{ p \in P | sim(p_2,p) < \theta \} \Big)</math>
Вычислительное ядро алгоритма можно разделить на два основных этапа:


В качестве критериальной функции используется функция вида
# Вычисление количества связей между каждой парой объектов (<math>\frac {M \times M} {2}</math> вычислений количества связей)
# Последовательные объединения пар наиболее подходящих кластеров (<math>M-K</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>N(C_i)^{1+2f(\theta)}</math> имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция <math>f(\theta)</math> имеет вид
=== Макроструктура алгоритма ===


<math>f(\theta)=\frac {1-\theta}{1+\theta}</math>
На макроуровне можно выделить следующие шаги алгоритма:


Для того, чтобы сформировать кластеры, удовлетворяющие поставленному условию, необходимо последовательно объединять среди имеющихся кластеров такие пары кластеров, для которых метрика
'''Шаг 1:''' вычисление соседних объектов.


<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>
'''Шаг 2:''' вычисление количества связей между всеми объектами.


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


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


Вычислительное ядро алгоритма можно разделить на два основных этапа:
'''Шаг 5 (повторяется то тех пор, пока количество кластеров не достигнет желаемого)'''


# Вычисление количества связей между каждой парой транзакций (<math>\frac {M \times M} {2}</math> вычислений количества связей)
'''Шаг 5.1:''' объединение двух кластеров с наилучшим goodness
 
# Последовательные объединения пар наиболее подходящих кластеров (<math>M-K</math> поисков пар и объединений).
 
Подробнее оба этапа будут описаны ниже.
 
=== Макроструктура алгоритма ===


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


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


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


<source lang="pascal">
<source lang="pascal">
procedure compute_links(P)
procedure compute_links(P)
begin
begin
   compute nbrlist[i] for every p[i] in P
   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


   link[i, j] = 0
   links[i, j] = 0
   for i := 1 to n do
   for each p[i], p[j] in P do
  begin
     for p[k] in P do
     N := nbrlist[i]
       if is_neighbour[i, k] && is_neighbour[j, k]
    for j := 1 to |N| − 1 do
         links[i, j] = links[i, j] + 1
       for l := j + 1 to |N| do
         link[N[j], N[l]] := link[N[j], N[l]] + 1
  end
end
end


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


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


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


     for each x ∈ q[u] ∪ q[v] do
     for each x in (q[u] or q[v]) do
     begin
     begin
      link[x, w] := link[x, u] + link[x, v]
       delete(q[x], u);
       delete(q[x], u);
       delete(q[x], v)
       delete(q[x], v)
       insert(q[x], w, g(x, w))
       insert(q[x], w, goodness(x, w))
       insert(q[w], x, g(x, w))
       insert(q[w], x, goodness(x, w))
       update(Q, x, q[x])
       update(Q, x, q[x])
     end
     end
Строка 115: Строка 135:
=== Последовательная сложность алгоритма ===
=== Последовательная сложность алгоритма ===


и тут
Рассмотрим сложности шагов алгоритма из раздела 1.4.
 
'''Шаг 1:''' выполняется с помощью двух вложенных циклов и содержит <math>O(M^2)</math> операций
 
'''Шаг 2:''' задача сводится к умножению полученной на предыдущем шаге матрицы соседства на саму себя. Это действие быть выполнено с помощью наивного метода за <math>O(M^3)</math> операций. С помощью алгоритма Копперсмита — Винограда это можно сделать за <math>O(M^{2.37})</math> операций.<ref>Donald Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proc. of the 19th Annual ACM Symposium on Theory of Computing. 1987.</ref> В случае, если среднее количество соседей каждого объекта значительно меньше общего количества объектов, связи могут быть вычислены за <math>O(M^2m_{nbr})</math>, где <math>m_{nbr}</math> - среднее количество соседей объекта.
 
'''Шаг 3:''' имеет сложность <math>O(M)</math>.<ref>Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to
Algorithms. The MIT Press, Massachusetts, 1990.</ref>
 
'''Шаг 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>.


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


и тут
''Информационный граф перемножения плотных матриц с подробным описанием представлен в статье [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)|перемножение плотных матриц]]''
 
Ниже представлен информационный граф наиболее интересного для рассмотрения этапа алгоритма устойчивой кластеризации с использованием связей - тела цикла (полупрозрачным показана следующая итерация цикла) при <math>n=5</math>.
 
[[file:rock-graph.png|thumb|center|1000px|Рисунок 1. Граф тела цикла; merge - объединение кластеров, insert - вставка goodness с новым кластером в упорядоченные списки соответствующих кластеров.]]


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


и тут
'''Шаг 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>.


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


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


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


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


== Программная реализация алгоритма ==
== Программная реализация алгоритма ==
Строка 137: Строка 200:
=== Особенности реализации последовательного алгоритма ===
=== Особенности реализации последовательного алгоритма ===


и тут
=== Локальность данных и вычислений ===
 
=== Возможные способы и особенности параллельной реализации алгоритма ===


=== Локальность данных и вычислений ===
=== Масштабируемость алгоритма и его реализации ===
 
Проведём исследование масштабируемости параллельной реализации алгоритма устройчивой кластеризации с использованием связей, выполненной с использованием OpenMP. Исследование проводилось на персональном компьютере HP Pavilion dv6 (процессор Intel Core i7 3610QM 2300 МГц, 8 логических ядер).
 
Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:
 
* число нитей [1 : 8] с шагом 1;
* количество точек [500 : 1500] с шагом 100.


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


=== Возможные способы и особенности параллельной реализации алгоритма ===
[[file:ROCK results 2.png|thumb|center|700px|Рисунок 2. Параллельная реализация алгоритма устойчивой кластеризации с использованием связей. Изменение времени выполнения кластеризации в зависимости от количества точек и от количества параллельных нитей.]]


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


=== Масштабируемость алгоритма и его реализации ===
{|border="1"
|
| 500 объектов
| 1000 объектов
| 1500 объектов
|-
| 1 нить
| 7.930 с
| 63.308 с
| 214.692 с
|-
| 4 нити
| 4.815 с
| 37.275 с
| 126.502 с
|-
| 8 нитей
| 5.312 с
| 39.986 с
| 135.251 с
|}


и тут
Реализация алгоритма была выполнена автором статьи.<ref>https://gitlab.com/viktorrulev/superprak-1/tree/master</ref>


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


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


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


нету :(
Алгоритм устойчивой кластеризации с иcпользованием связей реализован в пакете CBA языка R.<ref>https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/RockCluster</ref>


== Литература ==
== Литература ==


<references \>
<references \>

Текущая версия от 13:06, 3 февраля 2017

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



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


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

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

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

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

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

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

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

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

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

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

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

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


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


[math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ f(\theta)=\frac {1-\theta}{1+\theta} }[/math]


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

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

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

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

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

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

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

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

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

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

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

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

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

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.4.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проведём исследование масштабируемости параллельной реализации алгоритма устройчивой кластеризации с использованием связей, выполненной с использованием 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]

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

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

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

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

Литература

<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
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Участник:Viktorrulev/Алгоритм_устойчивой_кластеризации_с_иcпользованием_связей&oldid=22068