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

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

Материал из Алговики
Перейти к навигации Перейти к поиску



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

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

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

Алгоритм устойчивой кластеризации с использованием связей предназначен для работы с объектами типа "транзакция" ("покупательская корзина"). Транзакция представляет собой множество товаров, приобретенных покупателем у поставщика. Каждому товару, который есть в наличии у поставщика, в транзакции соответствует отдельный признак, который принимает значение true, если товар присутствует в транзакции, и false, если товар в транзакции отсутствует.

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: имеет такую же вычислительную сложность, как и предыдущий шаг.

Шаг 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: аналогично шагу 3.

Шаг 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] бинарных переменных. В силу того, что обычно в большинстве случаев лишь небольшое количество атрибутов транзакции имеет значение "1", каждую транзакцию можно хранить в виде списка номеров атрибутов, значения которых равны "1".

Выходные данные: [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 Масштабируемость алгоритма и его реализации

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

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

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

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

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://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/RockCluster