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

Эта работа ждет рассмотрения преподавателем Дата последней правки страницы: 26.10.2016 Авторы этой статьи считают, что задание выполнено.

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

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

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

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

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

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

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

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

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

Будет называть две транзакции $p_1$ и $p_2$ соседями, если мера сходства этих транзакций больше некоторого заранее заданного порогового значения $\theta$, то есть

$neighbour(p_1,p_2)=(sim(p_1,p_2)\gt \theta)$

В качестве меры сходства в алгоритме устойчивой кластеризации с использованием связей используется основанная на коэффициенте Жаккара мера сходства

$sim(p_1,p_2)=\frac{N(p_1 \cap p_2)}{N(p_1 \cup p_2)}$

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

$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)$

В качестве критериальной функции используется функция вида

$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)}}$

Здесь $N(C_i)^{1+2f(\theta)}$ имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция $f(\theta)$ имеет вид

$f(\theta)=\frac {1-\theta}{1+\theta}$

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

$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)}}$

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

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма можно разделить на два основных этапа:

1. Вычисление количества связей между каждой парой транзакций ($\frac {M \times M} {2}$ вычислений количества связей)
2. Последовательные объединения пар наиболее подходящих кластеров ($M-K$ поисков пар и объединений)

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

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: выполняется с помощью двух вложенных циклов и содержит $O(M^2)$ операций

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

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

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

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

Таким образом, общую последовательную сложность алгоритма можно оценить, как $O(M^2 + M^{2.37} + M^{2}logM)$ или $O(M^2 + M^2m_{nbr} + M^{2}logM)$.

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

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

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

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

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

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

Шаг 2: высота ЯПФ равна $O(M)$, а ширина - $O(M^2)$ (см. перемножение плотных матриц)

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

Шаг 4: аналогично шагу 3.

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

Таким образом, высота ЯПФ зависит от размерности задачи линейно, а ширина ЯПФ - квадратично.

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

Входные данные: информация об $M$ транзакциях, каждая их которых имеет $N$ бинарных атрибутов.

Объём входных данных: $M \times N$ бинарных переменных. В силу того, что обычно в большинстве случаев лишь небольшое количество атрибутов транзакции имеет значение "1", каждую транзакцию можно хранить в виде списка номеров атрибутов, значения которых равны "1".

Выходные данные: $K$ кластеров.

Объём выходных данных: $M$ индексов транзакций, распределенных в $K$ списков.

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

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

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

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

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

3 Литература

<references \>