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

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

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

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

3 Литература

<references \>