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

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

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

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

Во время работы алгоритм хранит в памяти небольшое количество информации по каждому кластеру и требует минимальное число сканирований набора данных. CLOPE автоматически подбирает количество кластеров, причем это регулируется одним единственным параметром - коэффициентом отталкивания [math] r [/math]. При этом он обеспечивает более высокую производительность и лучшее качество кластеризации в сравнении с многими иерархическими алгоритмами.

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 \dots \cup C_k=\{t_1,...,t_n\}[/math] и [math]C_i \ne \empty[/math] и [math]C_i \cap C_j = \empty [/math], для [math]i \ge 1, k \ge j[/math]. Каждый элемент [math]C_i[/math] называется кластером, а [math]n, m, k[/math] – количество транзакций, количество объектов в базе транзакций и число кластеров соответственно.

Каждый кластер [math]C[/math] имеет следующие характеристики:

[math]D(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]W(C)= \mid D(C) \mid ,H(C)=S(C)/W(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 } = \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](0 \lt r \le 1)[/math]

С помощью параметра [math]r[/math] регулируется уровень сходства транзакций внутри кластера, и, как следствие, финальное количество кластеров. Этот коэффициент подбирается пользователем. Чем больше [math]r[/math], тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

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

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

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

Вычислительное ядро алгоритма состоит в вычислении на каждой итерации функции стоимости:

[math] Profit(C) = \frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid } = \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]

3 Литература

[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm