Участник:Артем Карпухин/Алгоритм CLOPE кластеризации категориальных данных

Алгоритм CLOPE
Последовательный алгоритм
Последовательная сложность	[math]O(N*k*A)[/math]
Объём входных данных	[math]N*A[/math]
Объём выходных данных	[math]2N[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O( \log (N*k*A))[/math]
Ширина ярусно-параллельной формы	[math]O(N*k*A)[/math]

Основные авторы описания: А.В.Карпухин, А.А.Желтков

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

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

Алгоритм CLOPE (Clustering with sLOPE) — неиерархический итеративный метод кластерного анализа, предназначенный для обработки больших наборов категориальных данных. Алгоритм был предложен группой исследователей из Шанхайского университета (Yiling Yang, Xudong Guan, Jinyuan You) в статье "CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data" на конференции SIGKDD (Special Interest Group on Knowledge Discovery and Data Mining) в 2002 году.

Алгоритм CLOPE в изначальной формулировке является алгоритмом кластеризации транзакционных данных (под транзакцией понимается некоторый произвольный набор объектов конечной длины). Основной идеей данного метода является использование глобального критерия оптимизации на основе максимизации функции стоимости применительно к задачам кластеризации.

Во время выполнения алгоритма в оперативной памяти требуется хранить относительно малое количество информации о каждом кластере и производится минимальное число проходов по набору данных. При использовании метода CLOPE количество кластеров подбирается автоматически и зависит от коэффициента отталкивания — параметра, определяющего уровень сходства транзакций внутри кластера. Коэффициент отталкивания задается пользователем: чем больше данный параметр, тем ниже уровень сходства транзакций и, как следствие, большее количество кластеров будет создано.

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

Пусть имеется база транзакций [math]D[/math], состоящая из множества транзакций [math]\{t_{1},t_{2},...,t_{n}\}[/math]. Каждая транзакция есть набор объектов [math]\{i_1,...,i_A\} [/math].

Множество кластеров [math]\{C_1,...,C_k\} [/math] есть разбиение множества [math]\{t_1,...t_n\} [/math], такое, что [math]C_1 \cup \ldots \cup C_k = \{t_1,...,t_n\}[/math] и [math]C_i[/math] [math]\ne[/math] [math]\empty[/math] [math]\land[/math] [math]C_i[/math] [math]\cap[/math] [math]C_j= \empty[/math], для [math]1[/math] [math]\le[/math] [math]i[/math], [math] j[/math] [math] \le[/math] [math] k[/math].

Каждый элемент [math] C_i[/math] называется кластером , [math] n[/math] — количество транзакций, [math]A [/math] — длина транзакции, [math]k [/math] — число кластеров.

При этом задан параметр [math]r[/math] - коэффициент отталкивания.

Характеристики кластера [math]C_j [/math] :

[math]D(C_j)[/math] — множество уникальных объектов;

[math]Occ(i,C_j) [/math] — количество вхождений объекта [math] i[/math] в кластер [math] C_j[/math] ;

[math]S(C_j) = \sum_{i \in D(C_j)} Occ(i,C_j) = \sum _{t_i \in C_j} \mid t_i \mid [/math]

[math]W(C_j) [/math]  =  [math] \mid[/math] [math]D(C_j)[/math] [math]\mid[/math] — высота кластера;

[math]H(C_j)[/math] = [math]S(C_j)[/math] [math]/[/math] [math]W(C_j)[/math] — ширина кластера.

Формула для вычисления глобального критерия — функции стоимости текущей кластеризации [math]C = \{C_1, \ldots C_k\}[/math], обозначаемой, как [math] Profit(C)[/math] :

[math] Profit(C)=\frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} [/math]  =  [math]\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} [/math]

Для построения начального разбиения необходимо сделать первый проход по таблице. Для каждой транзакции кластер выбирается таким образом, чтобы функция [math] Profit(C)[/math] была максимальной. В последующие проходы пробуем переместить каждую транзакцию в другой кластер так, чтобы [math] Profit(C) \longrightarrow max[/math].

Если в текущая итерация не принесла изменений, то действие алгоритма заканчивается.

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

Вычислительное ядро алгоритма состоит в многократном вычислении цены добавления транзакции в кластер и вычислении цены удаления транзакции из кластера, которые выполняются на каждой итерации для каждой транзакции (всего они выполняются [math]N*(k-1)[/math] и [math]N[/math] раз соответственно на каждой итерации).

Оба описанных процедуры (вычисление цены добавления и удаления транзакции) включают в себя следующие операции:

• вычисление нового размера кластера [math]\overline{S}(C_i)=S(C_i) \pm length(t_n)[/math] после добавления/удаления транзакции (1 операция сложения/вычитания)
• определение новой ширины кластера [math]\overline{W}(C_i)=|D(C_i {\cup} t_n)|[/math] после добавления/удаления транзакции ([math]length(t_n)[/math] операций сравнения и инкремента/декремента)
• вычисление цены добавления/удаления транзакции — выражения [math]Cost^{\pm}(C_i, t_n) = \frac{\overline{S} (C_i) * (|C_i| \pm 1)}{\overline{W}(C_i)^r} - \frac{S(C_i) * |C_i|}{W(C_i)^r}[/math]   (2 операции умножения, 2 операции деления, 2 возведения в степень и 1 инкремент/декремент)

1.4 Макроструктура алгоритма

Алгоритм состоит из одной обязательной инициализирующей итерации и нескольких "уточняющих" итераций. По итогам каждой из итераций каждой транзакции приписывается какой-либо один кластер.

В свою очередь, инициализирующая итерация включает в себя вычисление цены добавления транзакции в каждый из кластеров для каждой транзакции (это действие описано в разделе Вычислительное ядро алгоритма).

"Уточняющие" итерации помимо этого содержат вычисление цены удаления транзакции из ее текущего кластера (аналогично вычислению цены добавления, см. раздел Вычислительное ядро алгоритма).

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

В начале алгоритма происходит инициализация - по порядку перебираются все транзакции, и для каждой из них происходит вычисление цены ее добавления (это действие описано в разделе Вычислительное ядро алгоритма) в существующие кластеры или же в новый, изначально пустой, кластер.

Исходя из вычисленных значений, каждой транзакции назначается кластер (какой-либо из уже существующих или новый) - выбирается кластер (при необходимости создается новый), для которого было получено максимальное значение цены добавления данной транзакции. Таким образом происходит начальное распределение транзакций по кластерам (инициализация кластеризации).

Далее могут быть выполнены "уточняющие" итерации, на каждой из которых производится попытка улучшить существующее распределение. В рамках каждой итерации снова производится перебор всех транзакций, и для каждой из них вычисляется цена удаления транзакции из ее текущего кластера (аналогично вычислению цены добавления, см. раздел Вычислительное ядро алгоритма), а также происходят вычисления цены добавления транзакции в другие существующие кластеры или в новый кластер. На основании вычисленных значений, принимается решение о перемещении транзакции в другой кластер (а если это должен быть новый кластер, то и о создании нового кластера) или же о том, что данная транзакция остается в текущем кластере. Как и при инициализации, делается таким образом, чтобы суммарная цена за удаление из текущего кластера и добавление в другой кластер была наибольшей (если для всех перемещений суммарная стоимость отрицательна, то транзакция остается на месте).

Алгоритм заканчивается, если за итерацию не было произведено ни одного перемещения (это означает, что была получена устойчивая кластеризация, которую больше нельзя улучшить при помощи данного метода).

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

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

• [math]t[/math] - набор транзакций - входной параметр
• [math]C[/math] - множество кластеров (изначально пустое) - выходной параметр
• [math]r[/math] - коэффициент отталкивания - входной параметр

algorithm clope([math]t, C, r[/math])

/* Часть 1 - Инициализация */

  add empty cluster to [math]C[/math]; /* добавляем начальный пустой кластер в множество кластеров (соответствует варианту добавления транзакции в новый, еще не существующий кластер)*/

  for each transaction [math]t_i[/math] in [math]t[/math] do /* сканируем каждую транзакцию */
    maxCost := 0;

     for each cluster [math]C_j[/math] in [math]C[/math] do  /* проходим по всем кластерам из множества (включая специально созданный пустой) */

      if [math]AddCost(C_j, t_i, r)[/math] > maxCost then /* если для транзакции найден кластер с большей ценой добавления, сохраняем эту информацию */
         maxCost := [math]AddCost(C_j, t_i, r)[/math];
         bestChoice := [math]j[/math];
      end if

    end for

    if cluster [math]C_{bestChoice}[/math] is empty then /* если наилучший выбор - это зарезервированный пустой кластер, то необходимо создать новый пустой кластер, чтобы для следующих транзакций также был вариант добавления в новый кластер */
      add empty cluster to [math]C[/math];
    end if

    move transaction [math]t_i[/math] to cluster [math]C_{bestChoice}[/math]; /* добавляем транзакцию в найденный кластер с наибольшей ценой добавления */
  end for

/* Часть 2 - Уточняющие итерации */
  repeat
    moved := false;

    for each transaction [math]t_i[/math] in [math]t[/math] do /* сканируем каждую транзакцию */
      maxCost := 0;
      act := cluster([math]t_i[/math]); /* определяем кластер, в котором в данный момент находится транзакция */
      remCost := [math]RemoveCost(C_{act}, t_i, r)[/math]; /* вычисляем стоимость удаления транзакции из кластера */

      for each cluster [math]C_j[/math] in [math]C[/math] except [math]C_{act}[/math] do  /* проходим по всем кластерам из множества (включая специально созданный пустой), кроме того, что содержит данную транзакцию */

        if [math]AddCost(C_j, t_i, r)[/math] + remCost > maxCost  then /* если для транзакции найден кластер с большей ценой перемещения, сохраняем эту информацию */
          maxCost := [math]AddCost(C_j, t_i, r)[/math] + remCost;
          bestChoice := [math]j[/math];
        end if

      end for

      if maxCost > 0 then /* если нашлись выгодные перемещения (суммарная стоимость удаления и добавления больше нуля) */

        if cluster [math]C_{bestChoice}[/math] is empty then /* если наилучший выбор - это зарезервированный пустой кластер, то необходимо создать новый пустой кластер, чтобы для следующих транзакций также был вариант добавления в новый кластер */
          add empty cluster to [math]C[/math];
        end if 

        move transaction [math]t_i[/math] from cluster [math]C_{act}[/math] to cluster [math]C_{bestChoice}[/math]; /* перемещаем транзакцию из ее текущего кластера в найденный кластер с наибольшей ценой перемещения */
        moved := true; /* фиксируем факт перемещения */
      end if

    end for

  until moved = false

end algorithm

Описание функции AddCost:

function [math]AddCost(C_j, t_i, r[/math])
  S := [math]C_j[/math].size; /* текущий размер кластера */
  N := [math]C_j[/math].count; /* количество транзакций в кластере */
  W := [math]W(C_j)[/math].width; /* текущая ширина кластера (количество уникальных элементов) */
  Snew := S + [math]t_i[/math].length;
  Nnew := N + 1;
  Wnew  := W;
  
  for each item [math]O_k[/math] in [math]t_i[/math] /* проходим по всем объектам, содержащимся в транзакции */

    if [math]C_j.Occ(O_k[/math]) = 0 then /* если объекта из транзакции еще нет в кластере, то новая ширина будет больше на единицу */
      Wnew := Wnew + 1; 
    end if
   
  end for
  
  return (Snew * Nnew) / (Wnew ^ r) - (S * N) / (W ^ r);

end function

Описание функции RemoveCost:

function [math]RemoveCost(C_j, t_i, r[/math])
  S := [math]C_j[/math].size; /* текущий размер кластера */
  N := [math]C_j[/math].count; /* количество транзакций в кластере */
  W := [math]W(C_j)[/math].width; /* текущая ширина кластера (количество уникальных элементов) */
  Snew := S - [math]t_i[/math].length;
  Nnew := N - 1;
  Wnew  := W;
  
  for each item [math]O_k[/math] in [math]t_i[/math] /* проходим по всем объектам, содержащимся в транзакции */

    if [math]C_j.Occ(O_k[/math]) = 1 then /* если объект из транзакции в кластере присутствует только в одном экземпляре, то новая ширина будет меньше на единицу */
      Wnew := Wnew - 1; 
    end if
   
  end for
  
  return (Snew * Nnew) / (Wnew ^ r) - (S * N) / (W ^ r);

end function

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

Сложность алгоритма пропорционально количеству итераций, которое может быть жестко зафиксировано пользователем (когда требуется конкретное количество "уточняющих" итераций) или же быть изначально не определено (пока не получится устойчивая кластеризация, см. раздел Схема реализации последовательного алгоритма.

На каждой итерации в соответствии с описанием вычислительного ядра алгоритма для каждой сканируемой транзакции при каждом вызове функций AddCost или RemoveCost выполняется:

• 1 операция сложения (или вычитания)
• Не более, чем A операций инкремента или декремента (A — максимальная длина транзакции)
• 2 операции деления, 2 операции возведения в степень и 1 операция инкремента или декремента

Таким образом, всего при вызове функций AddCost или RemoveCost выполняется не более, чем [math]A + 6[/math] операций.

С учетом того, что в пределах итерации для каждой транзакции эти функции выполняются суммарно k раз (k - количество кластеров), а количество транзакций есть N, то получаем [math] N*k*(A+6) [/math] на каждой итерации.

Кроме того следует учесть, что при добавлении/перемещении транзакции на кластер возникает необходимости пересчета и обновления его характеристик (размера, ширины и количества транзакций). Пересчет характеристик кластера после добавления/удаления одной транзакции состоит из:

• вычисления нового размера — 1 операция сложения или вычитания
• вычисления новой ширины — не более, чем A операций инкремента или декремента (A — максимальная длина транзакции)
• вычисления нового количества транзакций — 1 операция инкремента или декремента

Итого получается не более, чем [math]A + 2[/math] операции.

На инициализирующей итерации, происходит ровно N добавлений транзакций, что означает выполнение не более, чем [math] N*(A+2) [/math] операций. На уточняющих итерациях происходит не более N перемещений транзакций, значит, количество операций, затрачиваемых на пересчет характеристик кластера, составляет не более [math] 2*N*(A+2) [/math] операций.

В конечном итоге, общее количество операций по вызову функций AddCost/RemoveCost и обновлению характеристик кластера составляет не более

• [math] N*k*(A+6) + N*(A+2) [/math] для инициализирующей итерации
• [math] N*k*(A+6) + 2*N*(A+2) [/math] для "уточняющих" итераций

Из этого вытекает, что для данного алгоритма справедлива асимптотическая оценка сложности [math]O(N*k*A)[/math].

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

Входные данные:

• набор из [math]N[/math] транзакций длины не более [math]A[/math].

Объем входных данных:

• [math]N * A[/math] символов, строк или чисел (зависит от того, в каком виде представляются категории).

Выходные данные:

• распределение исходного набора транзакций по кластерам.

Объем выходных данных:

• [math]N[/math] положительных целых чисел - номера кластеров, соответствующих каждой из транзакций.

3 Литература

<references \>