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

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

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], при котором

1. [math]C_1 \cup \ldots \cup C_k = \{t_1,...,t_n\}[/math]
2. [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[/math] определяются следующие характеристики :

[math]D(C)[/math] — множество уникальных объектов в данном кластере [math] C[/math],

[math]Occ(i,C) [/math] — количество вхождений объекта [math] i[/math] в кластер [math] C[/math] ,

[math]S(C) = \sum_{i \in D(C)} Occ(i,C) = \sum _{t_i \in C} \mid t_i \mid [/math]; — количество всех объектов в кластере [math] C[/math],

[math]W(C) [/math]  =  [math] \mid[/math] [math]D(C)[/math] [math]\mid[/math] — ширина кластера,

[math]H(C)[/math]  =  [math] \frac{S(C)}{W(C)}[/math] — высота кластера.

Функция стоимости:

[math] Profit(C) = \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]\mid C_i \mid[/math] - количество объектов в [math]i[/math]-ом кластере, [math]k[/math] – общее количество кластеров. Коэффициент отталкивания [math]r[/math] регулирует уровень похожести среди транзакций одного кластера. Чем больше [math]r[/math], тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Таким образом задача кластеризации алгоритмом CLOPE состоит в том, чтобы для заданных множества [math]D[/math] и коэффициента отталкивания [math]r[/math] найти такое разбиение [math]C[/math], для которого значение функции цены максимально.

Постановка задачи кластеризации алгоритмом CLOPE выглядит следующим образом:

для заданных [math]D[/math] и [math]r[/math] найти разбиение [math]C[/math] такое, что: [math]Profit(C) \longrightarrow max [/math].

1.3 Вычислительное ядро алгоритма

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

• [math]S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid [/math],

• [math]W_{new}(C_i)=\mid D(C_i \cup t_n)|[/math]

• вычисление стоимости [math]\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}[/math]

1.4 Макроструктура алгоритма

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

3 Литература

<references \>