Участник:Артем Карпухин/Алгоритм 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_m\} [/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]m [/math] — количество объектов в базе транзакций, [math]k [/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]

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

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] - коэффициент отталкивания - входной параметр

/* Часть 1 - Инициализация */
algorithm clope([math]t, C, r[/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) \gt  maxCost [/math] then //если для транзакции найден кластер с большей ценой добавления, сохраняем эту информацию
       maxCost := [math]AddCost(C_j, t_i)[/math];
       bestChoice := [math]j[/math];
    fi
  end
  move transaction [math]t_i[/math] to cluster [math]C_bestChoice[/math]; //добавляем транзакцию в найденный кластер с наибольшей ценой добавления
   
  put t in an existing cluster or a new cluster C~ that maximize profit;
write (t, i) back to database;
/* Phrase 2 - Iteration */
repeat
rewind the database file;
moved = false;
while not end of the database file
read (t, i);
move t to an existing cluster or new cluster Cj that maximize profit;
ifCj* Cj then
write (t,j);
moved = true;
until not moved;

3 Литература

<references \>