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

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

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

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

Математическое описание алгоритма

Пусть имеется база транзакций [math]\displaystyle{ D }[/math], которая состоит из множества транзакций [math]\displaystyle{ \{t_1,t_2,...,t_n\} }[/math]. При этом каждая транзакция - набор объектов [math]\displaystyle{ \{i_1,...,i_m\} }[/math].

Множество кластеров [math]\displaystyle{ \{C_1,...,C_k\} }[/math] - это разбиение множества транзакций [math]\displaystyle{ \{t_1,...t_n\} }[/math], при котором

1. [math]\displaystyle{ C_1 \cup \ldots \cup C_k = \{t_1,...,t_n\} }[/math]
2. [math]\displaystyle{ C_i }[/math] [math]\displaystyle{ \ne }[/math] [math]\displaystyle{ \empty }[/math] [math]\displaystyle{ \land }[/math] [math]\displaystyle{ C_i }[/math] [math]\displaystyle{ \cap }[/math] [math]\displaystyle{ C_j= \empty }[/math], для [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ \le }[/math] [math]\displaystyle{ i }[/math], [math]\displaystyle{ j }[/math] [math]\displaystyle{ \le }[/math] [math]\displaystyle{ k }[/math].

Для каждого кластера [math]\displaystyle{ C }[/math] определяются следующие характеристики :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• вычисление стоимости [math]\displaystyle{ \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]

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

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

Литература

<references \>