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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 208 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
{{algorithm
 
{{algorithm
 
| name              = Алгоритм CLOPE
 
| name              = Алгоритм CLOPE
−
| serial_complexity = <math>O(N*K*A)</math>
+
| serial_complexity = <math>O(N*k*A)</math>
−
| pf_height        = <math>O( \log (N*K*A))</math>
+
| pf_height        = <math>O(N*A)</math>
−
| pf_width          = <math>O(N*K*A)</math>
+
| pf_width          = <math>O(N*k*A)</math>
−
| input_data        = <math>N*A</math>
+
| input_data        = <math>N*A + 1</math>
−
| output_data      = <math>2N</math>
+
| output_data      = <math>N</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]])
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
−
Алгоритм '''CLOPE (Clustering with sLOPE)''' - неиерархический итеративный метод кластерного анализа, предназначенный для обработки больших наборов категориальных данных. Алгоритм был предложен группой исследователей из Шанхайского университета (Yiling Yang, Xudong Guan, Jinyuan You) в статье "''CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data''" <ref> Y.Yang, X.Guan J.You. CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data</ref> на конференции [http://www.kdd.org SIGKDD (Special Interest Group on Knowledge Discovery and Data Mining)] в 2002 году.
+
Алгоритм '''CLOPE (Clustering with sLOPE)''' — неиерархический итеративный метод кластерного анализа, предназначенный для обработки больших наборов категориальных данных. Алгоритм был предложен группой исследователей из Шанхайского университета (Yiling Yang, Xudong Guan, Jinyuan You) в статье "''CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data''" <ref> Y. Yang, X. Guan J. You. CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data. http://www.inf.ufrgs.br/~alvares/CMP259DCBD/clope.pdf</ref> на конференции [http://www.kdd.org SIGKDD (Special Interest Group on Knowledge Discovery and Data Mining)] в 2002 году.
  
 
Алгоритм CLOPE в изначальной формулировке является алгоритмом кластеризации транзакционных данных (под транзакцией понимается некоторый произвольный набор объектов конечной длины). Основной идеей данного метода является использование глобального критерия оптимизации на основе максимизации функции стоимости применительно к задачам кластеризации.
 
Алгоритм CLOPE в изначальной формулировке является алгоритмом кластеризации транзакционных данных (под транзакцией понимается некоторый произвольный набор объектов конечной длины). Основной идеей данного метода является использование глобального критерия оптимизации на основе максимизации функции стоимости применительно к задачам кластеризации.
  
−
Во время выполнения алгоритма в оперативной памяти требуется хранить относительно малое количество информации о каждом кластере и производится минимальное число проходов по набору данных. При использовании метода CLOPE количество кластеров подбирается автоматически и зависит от коэффициента отталкивания - параметра, определяющего уровень сходства транзакций внутри кластера. Коэффициент отталкивания задается пользователем: чем больше данный параметр, тем ниже уровень сходства транзакций и, как следствие, большее количество кластеров будет создано.
+
Во время выполнения алгоритма в оперативной памяти требуется хранить относительно малое количество информации о каждом кластере и производится минимальное число проходов по набору данных. При использовании метода CLOPE количество кластеров подбирается автоматически и зависит от коэффициента отталкивания — параметра, определяющего уровень сходства транзакций внутри кластера. Коэффициент отталкивания задается пользователем: чем больше данный параметр, тем ниже уровень сходства транзакций и, как следствие, большее количество кластеров будет создано.
  
−
https://basegroup.ru/community/articles/clope
+
=== Математическое описание алгоритма ===
−
http://www.fundamental-research.ru/ru/article/view?id=33381
+
Пусть имеется база транзакций <math>D</math>, состоящая из множества транзакций <math>\{t_{1},t_{2},...,t_{n}\}</math>. Каждая транзакция есть набор объектов <math>\{i_1,...,i_A\} </math>.
−
http://www.olap.ru/home.asp?artId=155
+
 
−
Задачи кластеризации больших массивов категорийных данных весьма актуальна для систем анализа данных.
+
Множество кластеров <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> 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> &nbsp; — общее количество объектов в кластере <math> C_j</math>;
−
Пусть имеется база транзакций <math>D</math>, состоящая из множества транзакций <math>\{t_{1},t_{2},...,t_{n}\}</math>. Каждая транзакция есть набор объектов <math>\{i_1,...,i_m\} </math>.  
+
 
 +
: <math>W(C_j) </math> &nbsp;=&nbsp; <math> \mid</math> <math>D(C_j)</math> <math>\mid</math> — '''ширина''' кластера;
 +
 
 +
: <math>H(C_j)</math> &nbsp;=&nbsp; <math>S(C_j)</math> <math>/</math> <math>W(C_j)</math> — '''высота''' кластера.
  
−
Множество кластеров <math>\{C_1,...,C_k\} </math> есть разбиение множества <math>\{t_1,...t_n\} </math>, такое, что <math>C_1...C_k</math> &nbsp;=&nbsp; <math>\{t_1,...,t_n\}</math> и <math>C_i</math> <math>\ne</math> <math>\oslash</math> <math>\land</math> <math>C_i</math> <math>\cap</math>
 
  
−
<math>C_j</math> &nbsp;=&nbsp; <math>\ne</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>m </math>  - количество объектов в базе транзакций, <math>k </math> - число кластеров.
+
Формула для вычисления глобального критерия — '''функции стоимости''' текущей кластеризации <math>C = \{C_1, \ldots C_k\}</math>, обозначаемой, как <math> Profit(C)</math> :
  
−
Характеристики кластера <math>C </math> :
+
<math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math> &nbsp;=&nbsp; <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>D(C) </math> - множество уникальных объектов;
+
Для построения начального распределения транзакций по кластерам необходимо сделать первый проход по таблице (фаза инициализации). Во время нее для каждой транзакции выбирается кластер таким образом, чтобы функция <math> Profit(C)</math> была максимальной.
  
−
<math>Occ(i,C) </math>  - количество вхождений объекта <math> i</math> в кластер <math> C</math> ;
+
Далее происходят "уточняющие" проходы (фаза итерации), где для каждой транзакции производится попытка перемещения в другой кластер так, чтобы <math> Profit(C) \longrightarrow max</math>.
  
−
<math>S(C) </math> &nbsp;=&nbsp; <math>\sum </math><math>_i</math> <math>\in</math> <math>D(C)</math>;
+
Если больше не существует перемещений транзакций, увеличивающих глобальную стоимость <math> Profit(C) </math>, то действие алгоритма заканчивается.
  
−
<math>Occ(i,C)</math> &nbsp;=&nbsp; <math>\sum</math>  
+
Разность между стоимостью кластеризации <math> Profit(C) </math> после перемещения транзакции <math> t_n </math> с кластера <math> C_i </math> на кластер <math> C_j </math> и стоимостью кластеризации непосредственно до этого перемещения называется '''ценой перемещения''' транзакции.
 +
Цена перемещения <math> t_n </math> с кластера <math> C_i </math> на кластер <math> C_j </math> складывается из двух величин:
 +
* <math>Cost^{-}(C_i, t_n) = \frac{(S(C_i) - lentgh(t_n))* (|C_i| - 1)}{W(C_i \setminus t_n)^r} - \frac{S(C_i) * |C_i|}{W(C_i)^r} </math> &nbsp; — '''цена удаления''' транзакции <math> t_n </math> из кластера <math> C_i </math>.
  
−
<math>W(C)</math> &nbsp;=&nbsp; <math>\mid</math> <math>D(C)</math> <math>\mid</math>
 
  
−
<math>H(C)</math> &nbsp;=&nbsp; <math>S(C)</math> <math>/</math> <math>W(C)</math>
+
* <math>Cost^{+}(C_j, t_n) = \frac{(S(C_j) + lentgh(t_n))* (|C_j| + 1)}{W(C_j \cup t_n)^r} - \frac{S(C_j) * |C_j|}{W(C_j)^r} </math> &nbsp; — '''цена добавления''' транзакции <math> t_n </math> на кластер <math> C_j </math>.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 +
Вычислительное ядро алгоритма состоит в многократном вычислении цены добавления транзакции в кластер и вычислении цены удаления транзакции из кластера, которые выполняются на каждой итерации для каждой транзакции (всего они выполняются <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 \begin{smallmatrix} \cup \\ \setminus \end{smallmatrix} 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> &nbsp; (2 операции умножения, 2 операции деления, 2 возведения в степень и 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''' (вычисляет <math>Cost^{+}(C_j, t_i)</math>):
 +
 +
'''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''' (вычисляет <math>Cost^{-}(C_j, t_i)</math>):
 +
 +
'''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'''
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
 +
Сложность алгоритма пропорционально количеству итераций, которое может быть жестко зафиксировано пользователем (когда требуется конкретное количество "уточняющих" итераций) или же быть изначально не определено (пока не получится устойчивая кластеризация, см. раздел [[#Схема реализации последовательного алгоритма|Схема реализации последовательного алгоритма]].
 +
 +
 +
На каждой итерации в соответствии с [[#Вычислительное ядро алгоритма|описанием вычислительного ядра алгоритма]] для каждой сканируемой транзакции  при каждом вызове функций 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 приводится общая схема алгоритма кластеризации CLOPE.
 +
Входными  данными для этого алгоритма является набор из <math>N</math> транзакций длины <math>A</math> и коэффициент отталкивания <math>r</math>.
 +
В начале алгоритма происходит выполнение шага '''Init''', во время которого производится изначальное распределение транзакций по кластерам (инициализирующая итерация). После начального распределения циклически выполняется шаг '''Iter''' ("уточняющие" итерации) до тех пор, пока не перестанут существовать перемещения транзакций, увеличивающие глобальную стоимость кластеризации. После этого выполнение алгоритма завершается, получается итоговая кластеризация.
 +
 +
[[file:CLOPE common scheme.png|thumb|center|800px|Рисунок 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>, аргументом которой является измененный кластер. Поэтому обработка следующей транзакции может быть начата только после окончания обработки предыдущей транзакции и добавления ее на какой-либо один кластер.
 +
 +
[[file:CLOPE init scheme.png|thumb|center|800px|Рисунок 2. Схема шага Init алгоритма CLOPE]]
 +
 +
Фаза итерации отличается от фазы инициализации лишь тем, что действие '''AC''' для данной фазы включает в себя еще и вычисление стоимости удаления транзакции с ее текущего кластера - значения функции <math>RemoveCost(C_j, t_i)</math>.
 +
 +
Поэтому Рис.2 подходит и для схематичного описания шага '''Iter''' из общей схемы.
  
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
 +
 +
Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих  кластеров.
 +
Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления  <math>Cost^{\pm}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>" подразумевается непосредственно стоимость добавления <math>Cost^{+}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>, если транзакция <math>t_i</math> в данный момент '''не находится''' на кластере <math>C_j</math>, а иначе, если транзакция <math>t_i</math> принадлежит кластеру <math>C_j</math> — то стоимость ее удаления <math>Cost^{-}(C_j, t_i) </math> с данного кластера.
 +
 +
 +
Для алгоритма CLOPE кластеризации категориальных данных имеет место '''конечный''' параллелизм.
 +
 +
В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент — вычисление обобщенной стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров — <math>Cost^{\pm}(C_j, t_i) </math>, при фиксированном значении <math>i</math>.
 +
 +
То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.
 +
 +
Однако при этом важно отметить, что для корректного распараллеливания (чтобы результат выполнения параллельной программы был эквивалентен результату последовательной) обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно — вычисления обобщенных стоимостей добавления транзакции <math>t_{i+1}</math> на существующие кластеры могут быть начаты только после завершения обработки транзакции <math>t_i</math> — т.е. после вычислений всех ее обобщенных стоимостей добавления на каждый из кластеров (стоимости ее удаления с текущего кластера (если итерация алгоритма — уточняющая) и стоимостей добавления на каждый из остальных кластеров) и возможного выполнения перемещения транзакции на новый кластер — потому как обобщенные стоимости добавления транзакции <math>t_{i+1}</math> на кластеры информационно зависят от результата распределения транзакции <math>t_i</math> на текущей итерации алгоритма.
 +
 +
Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> — данная оценка приводится в разделе [[#Последовательная сложность алгоритма|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.
 +
 +
С учетом требования к последовательной обработке транзакций на каждой итерации алгоритма приходим к выводу, что сложность параллельного алгоритма будет равна <math>O(N*A)</math>  (здесь <math>N</math> — количество транзакций).
  
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
 +
 +
'''Входные данные''':
 +
* набор из <math>N</math> транзакций длины не более <math>A</math> и коэффициент отталкивания <math>r</math>.
 +
 +
'''Объем входных данных''':
 +
* <math>N * A</math> символов, строк или чисел (зависит от того, в каком виде представляются категории) и <math>1</math> вещественное число..
 +
 +
'''Выходные данные''':
 +
* распределение исходного набора транзакций по кластерам.
 +
 +
'''Объем выходных данных''':
 +
* <math>N</math> положительных целых чисел - номера кластеров, соответствующих каждой из транзакций.
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
 +
 +
* Соотношение последовательной и параллельной сложности алгоритма: <math>\frac{O(N*k*A)}{O(N*A)} = k</math>.
 +
 +
* Вычислительная мощность операций алгоритма: <math>\frac{O(N*k*A)}{N*A + N + 1} = O(k)</math>.
 +
 +
* Устойчивость алгоритма: алгоритм '''не является''' устойчивым, поскольку результат его работы зависит от того, в каком порядке сканируются транзакции. Действительно, стоимость перемещения или добавления транзакции на кластер зависит от набора транзакций, уже находящегося на этом кластере. Значит, если поменять местами порядок чтения для двух транзакций, то для каждой из них будут получены значения цены добавления или суммарной цены перемещения, отличные от значений, полученных при сканировании в исходном порядке, и, соответственно, для них могут быть выбраны другие кластеры.
 +
 +
* Детерминированность алгоритма: алгоритм, вообще говоря, '''не является''' детерминированным, поскольку, как уже описано выше, результат работы зависит от порядка обхода транзакций. Однако, если рассматривать набор транзакций не как множество, а как нумерованный массив, для которого фиксирован порядок извлечения элементов, то результат работы алгоритма от запуска к запуску будет определен однозначно, поскольку в нем отсутствуют какие-либо рандомизации.
 +
 +
* Характерные особенности алгоритма:
 +
** Алгоритм предназначен для обработки категориальных данных, а значит практически неприменим к обработке наборов числовых данных. Данный метод &laquo;не понимает&raquo;, что, например, числа 3 и 4 являются близкими по значению, а числа 3 и 100 — нет. В ходе алгоритма они будут просто интерпретироваться, как разные категории.
 +
** Алгоритм достаточно прост в реализации и имеет высокую скорость работы, а также качество кластеризации.
 +
** Во время работы алгоритма в оперативной памяти хранится относительно небольшое количество информации по каждому кластеру и требуется минимальное число сканирований набора транзакций. Это позволяет применять его для кластеризации больших объемов категориальных данных <ref>Н. Паклин. «Кластеризация категорийных данных: масштабируемый алгоритм CLOPE». Электронное издание. https://basegroup.ru/community/articles/clope </ref>
 +
** Требования к памяти главным образом зависят от количества различных категорий в базе транзакций.
 +
** Количество кластеров зависит от параметра — коэффициента отталкивания — и подбирается автоматически. Это означает, что хоть количество кластеров и регулируется пользователем при помощи данного коэффициента, нельзя априорно получить число кластеров, которое будет в итоге создано, а значит, нельзя точно предсказать сложность алгоритма и объем выходных данных (т.к. они зависят от количества кластеров).
 +
** Динамическое создание кластеров в процессе выполнения алгоритма не позволяет эффективно распараллеливать оригинальную последовательную версию данного метода (особенно фазу инициализации) на большом числе процессов. Кроме того, вследствие этого невозможно подобрать оптимальное количество вычислительных ресурсов, чтобы они были максимально эффективно использованы.
 +
** Количество итераций алгоритма может быть искусственно жестко зафиксировано пользователем (в таком случае вероятно, что будет получена кластеризация с худшим качеством, чем возможно было получить) или же быть не определено (тогда качество кластеризации будет наилучшим, но будет информация о количестве итерации (и, соответственно, об общем времени выполнения) будет отсутствовать.
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
Строка 76: Строка 306:
  
 
=== Существующие реализации алгоритма ===
 
=== Существующие реализации алгоритма ===
 +
 +
Вследствие того, что алгоритм CLOPE был впервые изложен относительно недавно, на текущий момент для него нет большого количества известных библиотечных реализаций. Список известных пакетов, реализующих данный алгоритм:
 +
 +
* [http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html WEKA] - библиотека алгоритмов машинного обучения и анализа данных на языке Java.
 +
 +
Однако существует несколько реализаций от частных пользователей, размещенные ими в Git:
 +
* [https://github.com/realb0t/go-clope Go-CLOPE] - Golang-реализация алгоритма CLOPE пользователем '''realb0t'''.
 +
* [https://github.com/tnataly1990/clope CLOPE] - Java-реализация алгоритма CLOPE пользователем '''tnataly1990'''.
 +
* [https://github.com/infozor/php_mysql_clustering_clope 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''" <ref> D. Xiangwu, G. Tao, W. Mei. A Clustering Algorithm for Large-Scale Categorical Data and Its Parallel Implementation. http://crad.ict.ac.cn/EN/abstract/abstract3169.shtml</ref>.
 +
* Yuping Wang, Huiyun Wu, Jingmin Liang, Jiaguo Ou, Youfang Huang. "''A Clustering with Slope Algorithm based on MapReduce''" <ref>Y. Wang, H. Wu, J. Liang, J. Ou, Y. Huang. A Clustering with Slope Algorithm based on MapReduce. Journal of Digital Information Management. Jun2016, Vol. 14 Issue 3, p168-176.</ref>.
  
 
== Литература ==
 
== Литература ==
  
 
<references \>
 
<references \>

Текущая версия на 22:21, 9 февраля 2017


Алгоритм 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" [1] на конференции 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] 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] C_j[/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} H(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], то действие алгоритма заканчивается.

Разность между стоимостью кластеризации [math] Profit(C) [/math] после перемещения транзакции [math] t_n [/math] с кластера [math] C_i [/math] на кластер [math] C_j [/math] и стоимостью кластеризации непосредственно до этого перемещения называется ценой перемещения транзакции. Цена перемещения [math] t_n [/math] с кластера [math] C_i [/math] на кластер [math] C_j [/math] складывается из двух величин:

  • [math]Cost^{-}(C_i, t_n) = \frac{(S(C_i) - lentgh(t_n))* (|C_i| - 1)}{W(C_i \setminus t_n)^r} - \frac{S(C_i) * |C_i|}{W(C_i)^r} [/math]   — цена удаления транзакции [math] t_n [/math] из кластера [math] C_i [/math].


  • [math]Cost^{+}(C_j, t_n) = \frac{(S(C_j) + lentgh(t_n))* (|C_j| + 1)}{W(C_j \cup t_n)^r} - \frac{S(C_j) * |C_j|}{W(C_j)^r} [/math]   — цена добавления транзакции [math] t_n [/math] на кластер [math] C_j [/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 \begin{smallmatrix} \cup \\ \setminus \end{smallmatrix} 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 (вычисляет [math]Cost^{+}(C_j, t_i)[/math]): 

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 (вычисляет [math]Cost^{-}(C_j, t_i)[/math]): 

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 Ресурс параллелизма алгоритма

Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера [math]Cost^{-}(C_{C(t_i)}, t_i) [/math] совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры [math]Cost^{+}(C_j, t_i) [/math] — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции [math]Cost^{\pm}(C_j, t_i) [/math] вычисления стоимости добавления/удаления на каждый из существующих кластеров. Поэтому в данном разделе условимся, что под выражением "обобщенная стоимость (цена) добавления [math]Cost^{\pm}(C_j, t_i) [/math] транзакции [math]t_i[/math] на кластер [math]C_j[/math]" подразумевается непосредственно стоимость добавления [math]Cost^{+}(C_j, t_i) [/math] транзакции [math]t_i[/math] на кластер [math]C_j[/math], если транзакция [math]t_i[/math] в данный момент не находится на кластере [math]C_j[/math], а иначе, если транзакция [math]t_i[/math] принадлежит кластеру [math]C_j[/math] — то стоимость ее удаления [math]Cost^{-}(C_j, t_i) [/math] с данного кластера.


Для алгоритма CLOPE кластеризации категориальных данных имеет место конечный параллелизм.

В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент — вычисление обобщенной стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров — [math]Cost^{\pm}(C_j, t_i) [/math], при фиксированном значении [math]i[/math].

То есть, для [math]i[/math]-ой транзакции вычисление обобщенной цены добавления на [math]j[/math]-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на [math]k[/math]-й кластер. Поэтому эти операции при обработке текущей транзакции [math]t_i[/math] можно выполнять одновременно.

Однако при этом важно отметить, что для корректного распараллеливания (чтобы результат выполнения параллельной программы был эквивалентен результату последовательной) обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно — вычисления обобщенных стоимостей добавления транзакции [math]t_{i+1}[/math] на существующие кластеры могут быть начаты только после завершения обработки транзакции [math]t_i[/math] — т.е. после вычислений всех ее обобщенных стоимостей добавления на каждый из кластеров (стоимости ее удаления с текущего кластера (если итерация алгоритма — уточняющая) и стоимостей добавления на каждый из остальных кластеров) и возможного выполнения перемещения транзакции на новый кластер — потому как обобщенные стоимости добавления транзакции [math]t_{i+1}[/math] на кластеры информационно зависят от результата распределения транзакции [math]t_i[/math] на текущей итерации алгоритма.

Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров [math]k[/math], существующих на любой из итераций алгоритма, можно считать, что обработка одной транзакции на каждой итерации алгоритма выполняется за [math]O(A)[/math] операций (это соответствует сложности однократного вычисления [math]Cost^{\pm}(C_j, t_i) [/math] — данная оценка приводится в разделе Последовательная сложность алгоритма), где [math]A[/math] — максимальная длина транзакции.

С учетом требования к последовательной обработке транзакций на каждой итерации алгоритма приходим к выводу, что сложность параллельного алгоритма будет равна [math]O(N*A)[/math] (здесь [math]N[/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 Программная реализация алгоритма

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

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

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

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

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

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

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" [3].
  • Yuping Wang, Huiyun Wu, Jingmin Liang, Jiaguo Ou, Youfang Huang. "A Clustering with Slope Algorithm based on MapReduce" [4].

3 Литература

<references \>

  1. ↑ Y. Yang, X. Guan J. You. CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data. http://www.inf.ufrgs.br/~alvares/CMP259DCBD/clope.pdf
  2. ↑ Н. Паклин. «Кластеризация категорийных данных: масштабируемый алгоритм CLOPE». Электронное издание. https://basegroup.ru/community/articles/clope
  3. ↑ D. Xiangwu, G. Tao, W. Mei. A Clustering Algorithm for Large-Scale Categorical Data and Its Parallel Implementation. http://crad.ict.ac.cn/EN/abstract/abstract3169.shtml
  4. ↑ Y. Wang, H. Wu, J. Liang, J. Ou, Y. Huang. A Clustering with Slope Algorithm based on MapReduce. Journal of Digital Information Management. Jun2016, Vol. 14 Issue 3, p168-176.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Артем_Карпухин/Алгоритм_CLOPE_кластеризации_категориальных_данных&oldid=22490