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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 134: Строка 134:
 
'''Шаг 1:''' выполняется с помощью двух вложенных циклов и содержит <math>O(M^2)</math> операций
 
'''Шаг 1:''' выполняется с помощью двух вложенных циклов и содержит <math>O(M^2)</math> операций
  
'''Шаг 2:''' задача сводится к умножению полученной на предыдущем шаге матрицы соседства на саму себя. Это действие быть выполнено с помощью наивного метода за <math>O(M^3)</math> операций. Наилучший асимптотически метод возведения матрицы в квадрат под авторством Coppersfield и Winograd выполняет это действие за <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>
+
'''Шаг 2:''' задача сводится к умножению полученной на предыдущем шаге матрицы соседства на саму себя. Это действие быть выполнено с помощью наивного метода за <math>O(M^3)</math> операций. Наилучший асимптотически метод возведения матрицы в квадрат под авторством Coppersfield и Winograd выполняет это действие за <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>
  
 
'''Шаг 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

Версия 00:33, 16 октября 2016


Алгоритм устойчивой кластеризации с иcпользованием связей
Последовательный алгоритм
Последовательная сложность [math]...[/math]
Объём входных данных [math]...[/math]
Объём выходных данных [math]...[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]...[/math]
Ширина ярусно-параллельной формы [math]...[/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]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)\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]N(C_i)^{1+2f(\theta)}[/math] имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция [math]f(\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] операций. Наилучший асимптотически метод возведения матрицы в квадрат под авторством Coppersfield и Winograd выполняет это действие за [math]O(M^{2.37})[/math] операций.[2]

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

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

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

Таким образом, общую последовательную сложность алгоритма можно оценить, как [math]O(M^2) + O(M^{2.37}) + O(M^{2}log(M))[/math]

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

(to do)

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

(to do)

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 Свойства алгоритма

(to do)

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

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

нету :(

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.