Участник:Артем Карпухин/Алгоритм 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(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 Макроструктура алгоритма

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

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

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

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

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

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

3 Литература

<references \>