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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показаны 44 промежуточные версии 3 участников)
Строка 1: Строка 1:
 +
{{Assignment|Teplov}}
 +
 
{{algorithm
 
{{algorithm
 
| name              = Алгоритм устойчивой кластеризации с иcпользованием связей
 
| name              = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math>O(M^2 + M^{2.37} + M^{2}logM)</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>M \times N</math>
 
| input_data        = <math>M \times N</math>
 
| output_data      = <math>M</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>N</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>neighbour(p_1,p_2)=(sim(p_1,p_2)>\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) < \theta \} \cap \{ p \in P | sim(p_2,p) < \theta \} \Big)</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>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>goodness(C_i,C_j)</math> достигает максимального значения среди всех пар кластеров. На начальном этапе каждый объект считается отдельным кластером.
  
Здесь <math>N(C_i)^{1+2f(\theta)}</math> имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция <math>f(\theta)</math> имеет вид
+
Формулы метода:
 
+
:<math>
<math>f(\theta)=\frac {1-\theta}{1+\theta}</math>
+
neighbour(p_1,p_2)=(sim(p_1,p_2)>\theta)
 
+
</math>
Для того, чтобы сформировать кластеры, удовлетворяющие поставленному условию, необходимо последовательно объединять среди имеющихся кластеров такие пары кластеров, для которых метрика
+
<br>
 
+
:<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>
+
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>
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Строка 54: Строка 59:
 
Вычислительное ядро алгоритма можно разделить на два основных этапа:
 
Вычислительное ядро алгоритма можно разделить на два основных этапа:
  
# Вычисление количества связей между каждой парой транзакций (<math>\frac {M \times M} {2}</math> вычислений количества связей)
+
# Вычисление количества связей между каждой парой объектов (<math>\frac {M \times M} {2}</math> вычислений количества связей)
 
# Последовательные объединения пар наиболее подходящих кластеров (<math>M-K</math> поисков пар и объединений)
 
# Последовательные объединения пар наиболее подходящих кластеров (<math>M-K</math> поисков пар и объединений)
  
Строка 63: Строка 68:
 
На макроуровне можно выделить следующие шаги алгоритма:
 
На макроуровне можно выделить следующие шаги алгоритма:
  
'''Шаг 1:''' вычисление соседних транзакций.
+
'''Шаг 1:''' вычисление соседних объектов.
  
'''Шаг 2:''' вычисление количества связей между всеми транзакциями.
+
'''Шаг 2:''' вычисление количества связей между всеми объектами.
  
 
'''Шаг 3:''' построение для каждого кластера упорядоченного списка значений метрики goodness со всеми остальными кластерами
 
'''Шаг 3:''' построение для каждого кластера упорядоченного списка значений метрики goodness со всеми остальными кластерами
Строка 79: Строка 84:
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
  
Схема реализации последовательного алгоритма выглядит следующим образом:
+
Ниже приведен псевдокод схемы реализации последовательного алгоритма:
  
 
<source lang="pascal">
 
<source lang="pascal">
Строка 134: Строка 139:
 
'''Шаг 1:''' выполняется с помощью двух вложенных циклов и содержит <math>O(M^2)</math> операций
 
'''Шаг 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> - среднее количество соседей транзакции.
+
'''Шаг 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
 
'''Шаг 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>
 
Algorithms. The MIT Press, Massachusetts, 1990.</ref>
  
'''Шаг 4:''' имеет такую же вычислительную сложность, как и предыдущий шаг.
+
'''Шаг 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>.
 
'''Шаг 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>O(M^2 + M^{2.37} + M^{2}logM)</math>
 +
 
 +
или в случае небольшого количества соседних объектов для каждого объекта выборки, как
 +
 
 +
:<math>O(M^2 + M^2m_{nbr} + M^{2}logM)</math>.
  
 
=== Информационный граф ===
 
=== Информационный граф ===
  
(to do)
+
''Информационный граф перемножения плотных матриц с подробным описанием представлен в статье [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)|перемножение плотных матриц]]''
 +
 
 +
Ниже представлен информационный граф наиболее интересного для рассмотрения этапа алгоритма устойчивой кластеризации с использованием связей - тела цикла (полупрозрачным показана следующая итерация цикла) при <math>n=5</math>.
 +
 
 +
[[file:rock-graph.png|thumb|center|1000px|Рисунок 1. Граф тела цикла; merge - объединение кластеров, insert - вставка goodness с новым кластером в упорядоченные списки соответствующих кластеров.]]
  
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
  
'''Шаг 1:''' каждая итерация цикла может быть выполнена независимо от всех остальных. Таким образом, в этом случае ширина ЯПФ равна <math>M \times M</math>, а высота - <math>1</math>.
+
'''Шаг 1:''' каждая итерация цикла может быть выполнена независимо от всех остальных. Таким образом, в этом случае ширина ЯПФ равна <math>O(M^2)</math>, а высота - <math>O(1)</math>.
  
'''Шаг 2:''' высота ЯПФ равна <math>M</math>, а ширина - <math>M^2</math> (''см. [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)|перемножение плотных матриц]]'')
+
'''Шаг 2:''' при использовании алгоритма наивного перемножения плотных матриц высота ЯПФ равна <math>O(M)</math>, а ширина - <math>O(M^2)</math> (''см. [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)|перемножение плотных матриц]]'')
  
 
'''Шаг 3:''' имеет небольшую асимптотическую сложность, может быть выполнен последовательно.
 
'''Шаг 3:''' имеет небольшую асимптотическую сложность, может быть выполнен последовательно.
  
'''Шаг 4:''' аналогично шагу 3.
+
'''Шаг 4:''' имеет небольшую асимптотическую сложность, может быть выполнен последовательно.
  
'''Шаг 5:''' каждая итерация цикла может быть выполнена только после полного завершения предыдущей, следовательно высота ЯПФ равна <math>M</math>. Внутри каждой отдельной итерации все вставки могут быть выполнены независимо друг от друга, следовательно ширина ЯПФ в этом случае равна <math>logM</math>.
+
'''Шаг 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</math> объектах, каждая их которых имеет <math>N</math> бинарных атрибутов.
  
'''Объём входных данных''': <math>M \times N</math> бинарных переменных. В силу того, что обычно в большинстве случаев лишь небольшое количество атрибутов транзакции имеет значение "1", каждую транзакцию можно хранить в виде списка номеров атрибутов, значения которых равны "1".
+
'''Объём входных данных''': <math>M \times N</math> бинарных переменных. В силу того, что обычно в большинстве случаев лишь небольшое количество атрибутов объекта имеет значение "true", каждый объект можно хранить в виде списка номеров атрибутов, значения которых равны "true".
  
 
'''Выходные данные''': <math>K</math> кластеров.
 
'''Выходные данные''': <math>K</math> кластеров.
  
'''Объём выходных данных''': <math>M</math> индексов транзакций, распределенных в <math>K</math> списков.
+
'''Объём выходных данных''': <math>M</math> индексов объектов, распределенных в <math>K</math> списков.
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
  
(to do)
+
Вычислительная сложность последовательного алгоритма в общем случае равна <math>O(M^{2.37})</math>, а в случае небольшого количества соседних объектов у каждого объекта сложность равна <math>O(M^{2})</math>.
 +
 
 +
Вычислительная мощность алгоритма (соотношение количества операций к объему входных и выходных данных) в общем случае равна O(M^{1.37}), в а случае небольшого количества соседних объектов (то есть в том случае, для которого и разрабатывался алгоритм) вычислительная мощность линейна.
 +
 
 +
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как показано выше, является квадратичным.
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
Строка 181: Строка 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 \>

Текущая версия на 16:06, 3 февраля 2017

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



Алгоритм устойчивой кластеризации с и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