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

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

Основные авторы описания: А.В.Карпухин (1.1, 1.2, 1.4, 1.8, 1.9, 1.10), А.А.Желтков (1.3, 1.4, 1.5, 1.6, 1.7, 2.7)

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].

Если больше не существует перемещений транзакций, увеличивающих глобальную стоимость [math] Profit(C) [/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.7 Информационный граф

На Рис.1 приводится общая схема алгоритма кластеризации CLOPE. Входными данными для этого алгоритма является набор из [math]N[/math] транзакций длины [math]A[/math] и коэффициент отталкивания [math]r[/math]. В начале алгоритма происходит выполнение шага Init, во время которого производится изначальное распределение транзакций по кластерам (инициализирующая итерация). После начального распределения циклически выполняется шаг Iter ("уточняющие" итерации) до тех пор, пока не перестанут существовать перемещения транзакций, увеличивающие глобальную стоимость кластеризации. После этого выполнение алгоритма завершается, получается итоговая кластеризация.

Рисунок 1. Общая схема CLOPE

На Рис.2 представлена схема фазы Init на примере 2 входных транзакций [math]t_1, t_2[/math] и двух существующих кластеров [math]C_1, C_2[/math]. На рисунке также присутствует кластер [math]C_e[/math] - это специальный пустой кластер, который соответствует варианту "Поместить транзакцию на новый кластер" при обработке транзакции. Для этого кластера выполняются все те же вычисления, что и для остальных при сканировании каждой транзакции. Объект AC на схеме соответствует выполнению функции [math]AddCost(C_j, t_i)[/math] для вычисления цены добавления транзакции [math]t_i[/math] на кластер [math]C_j[/math]. Как видно, данное действие выполняется для всех возможных пар "кластер-транзакция".

После выполнения всех вычислений AC по одной транзакции, для этой транзакции выполняется действие Choose соответствующее определению максимального значения функции [math]AddCost[/math], вычисленного для данной транзакции и выбору исходя из этого кластера, на который она будет помещена. Заметим, что от результата действия Choose может зависеть каждый из кластеров (включая пустой), т.к. добавление транзакции на кластер изменяет его характеристики и, как следствие, значения функции [math]AddCost[/math], аргументом которой является измененный кластер. Поэтому обработка следующей транзакции может быть начата только после окончания обработки предыдущей транзакции и добавления ее на какой-либо один кластер.

Рисунок 2. Схема шага Init алгоритма CLOPE

Фаза итерации отличается от фазы инициализации лишь тем, что действие AC для данной фазы включает в себя еще и вычисление стоимости удаления транзакции с ее текущего кластера - значения функции [math]RemoveCost(C_j, t_i)[/math].

Поэтому Рис.2 подходит и для схематичного описания шага Iter из общей схемы.

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

Алгоритм CLOPE кластеризации категориальных данных имеет место массовой параллелизм, который возникает в тот момент, когда нужно для конкретной транзакции вычислить [math]Cost^{\pm}(C_i, t_n) [/math] — цену добавления/удаления транзакции. То есть для [math]i[/math]-ой транзакции вычисление цены на [math]i[/math]-ом кластере никак не зависит от вычисления цены для той же транзакции на [math]j[/math]-ом кластере. Поэтому эти операции можно выполнять одновременно. Количество транзакций алгоритма равно [math]N[/math], длина транзакции алгоритма — [math]A[/math], тогда сложность параллельного алгоритма будет равна [math]O(N*A)[/math].

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

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

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

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

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

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

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

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

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

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

• Соотношение последовательной и параллельной сложности алгоритма: [math]\frac{O(N*k*A)}{O(N*A)} = k[/math].

• Вычислительная мощность операций алгоритма: [math]\frac{O(N*k*A)}{N*A + N + 1} = O(k)[/math].

• Устойчивость алгоритма: алгоритм не является устойчивым, поскольку результат его работы зависит от того, в каком порядке сканируются транзакции. Действительно, стоимость перемещения или добавления транзакции на кластер зависит от набора транзакций, уже находящегося на этом кластере. Значит, если поменять местами порядок чтения для двух транзакций, то для каждой из них будут получены значения цены добавления или суммарной цены перемещения, отличные от значений, полученных при сканировании в исходном порядке, и, соответственно, для них могут быть выбраны другие кластеры.

• Детерминированность алгоритма: алгоритм, вообще говоря, не является детерминированным, поскольку, как уже описано выше, результат работы зависит от порядка обхода транзакций. Однако, если рассматривать набор транзакций не как множество, а как нумерованный массив, для которого фиксирован порядок извлечения элементов, то результат работы алгоритма от запуска к запуску будет определен однозначно, поскольку в нем отсутствуют какие-либо рандомизации.

• Характерные особенности алгоритма:
  • Алгоритм предназначен для обработки категориальных данных, а значит практически неприменим к обработке наборов числовых данных. Данный метод «не понимает», что, например, числа 3 и 4 являются близкими по значению, а числа 3 и 100 — нет. В ходе алгоритма они будут просто интерпретироваться, как разные категории.
  • Алгоритм достаточно прост в реализации и имеет высокую скорость работы, а также качество кластеризации.
  • Во время работы алгоритма в оперативной памяти хранится относительно небольшое количество информации по каждому кластеру и требуется минимальное число сканирований набора транзакций. Это позволяет применять его для кластеризации больших объемов категориальных данных
  • Требования к памяти главным образом зависят от количества различных категорий в базе транзакций.
  • Количество кластеров зависит от параметра — коэффициента отталкивания — и подбирается автоматически. Это означает, что хоть количество кластеров и регулируется пользователем при помощи данного коэффициента, нельзя априорно получить число кластеров, которое будет в итоге создано, а значит, нельзя точно предсказать сложность алгоритма и объем выходных данных (т.к. они зависят от количества кластеров).
  • Динамическое создание кластеров в процессе выполнения алгоритма не позволяет эффективно распараллеливать оригинальную последовательную версию данного метода (особенно фазу инициализации) на большом числе процессов. Кроме того, вследствие этого невозможно подобрать оптимальное количество вычислительных ресурсов, чтобы они были максимально эффективно использованы.
  • Количество итераций алгоритма может быть искусственно жестко зафиксировано пользователем (в таком случае вероятно, что будет получена кластеризация с худшим качеством, чем возможно было получить) или же быть не определено (тогда качество кластеризации будет наилучшим, но будет информация о количестве итерации (и, соответственно, об общем времени выполнения) будет отсутствовать.

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

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

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

• WEKA - библиотека алгоритмов машинного обучения и анализа данных на языке Java.

Однако существует несколько реализаций от частных пользователей, размещенные ими в Git:

• Go-CLOPE - Golang-реализация алгоритма CLOPE пользователем realb0t.
• CLOPE - Java-реализация алгоритма CLOPE пользователем tnataly1990.
• PHP-MySQL Clustering CLOPE - реализация алгоритма CLOPE пользователем infozor на PHP + MySQL.

Также интерес представляют следующие публикации, посвященные параллельной реализации данного алгоритма:

• Ding Xiangwu, Guo Tao, Wang Mei. "A Clustering Algorithm for Large-Scale Categorical Data and Its Parallel Implementation" .
• Yuping Wang, Huiyun Wu, Jingmin Liang, Jiaguo Ou, Youfang Huang. "A Clustering with Slope Algorithm based on MapReduce" .

3 Литература

<references \>