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

Алгоритм устойчивой кластеризации с иcпользованием связей
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ ... }[/math]
Объём входных данных	[math]\displaystyle{ ... }[/math]
Объём выходных данных	[math]\displaystyle{ ... }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ ... }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ ... }[/math]

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

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

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

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

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

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

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

В ходе кластеризации [math]\displaystyle{ M }[/math] имеющихся транзакций [math]\displaystyle{ P=\{p_1,...,p_M\} }[/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{ \theta }[/math], то есть

[math]\displaystyle{ neighbour(p_1,p_2)=[sim(p_1,p_2)\lt \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{ N(C_i)^{1+2f(\theta)} }[/math] имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция [math]\displaystyle{ f(\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] вычислений количества связей)

1. Последовательные объединения пар наиболее подходящих кластеров ([math]\displaystyle{ M-K }[/math] поисков пар и объединений).

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

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

procedure compute_links(P)
begin
  compute nbrlist[i] for every p[i] in P

  link[i, j] = 0
  for i := 1 to n do
  begin
    N := nbrlist[i]
    for j := 1 to |N| − 1 do
      for l := j + 1 to |N| do
        link[N[j], N[l]] := link[N[j], N[l]] + 1
  end
end

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

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

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

    for each x ∈ q[u] ∪ q[v] do
    begin
      link[x, w] := link[x, u] + link[x, v]
      delete(q[x], u);
      delete(q[x], v)
      insert(q[x], w, g(x, w))
      insert(q[w], x, g(x, w))
      update(Q, x, q[x])
    end

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

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

нету :(

Литература

<references \>