Участник:Пискунов Константин/ Алгоритм кластеризации категориальных данных (Clustering with sLOPE, CLOPE)

Алгоритм CLOPE
Последовательный алгоритм
Последовательная сложность	[math]O(N*k*A)[/math]
Объём входных данных	[math]N*A+1[/math]
Объём выходных данных	[math]N[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(N*A)[/math]
Ширина ярусно-параллельной формы	[math]O(N*k*A)[/math]

Основные авторы описания: К.А.Пискунов

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

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

Задачи кластеризации больших массивов категорийных данных весьма актуальна для систем анализа данных. Категорийные данные встречаются в любых областях: производство, коммерция, маркетинг, медицина… Категорийные данные включают в себя и так называемые транзакционные данные: чеки в супермаркетах, логи посещений веб-ресурсов. Сюда же относится анализ и классификация текстовых документов (Text Mining).

Здесь и далее под категорийными данными понимаются качественные характеристики объектов, измеренные в шкале наименований. Напомним: при использовании шкалы наименований указывается только, одинаковы или нет объекты относительно измеряемого признака.

Алгоритм CLOPE. Предназначен для кластеризации огромных наборов категорийных данных. К достоинствам относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации. Во время работы алгоритм хранит в памяти небольшое количество информации по каждому кластеру и требует минимальное число сканирований набора данных. CLOPE автоматически подбирает количество кластеров, причем это регулируется одним единственным параметром коэффициентом отталкивания. CLOPE предложен в 2002 году группой китайских ученых . При этом он обеспечивает более высокую производительность и лучшее качество кластеризации в сравнении с многими иерархическими алгоритмами.

Алгоритм CLOPE является масштабируемым, поскольку способен работать в ограниченном объеме оперативной памяти компьютера. Во время работы в оперативной памяти хранится только текущая транзакция и небольшое количество информации по каждому кластеру, которая состоит из: количества транзакций N, числа уникальных объектов (или ширины кластера) W, простой хэш-таблицы для расчета Occ(i,C) и значения S площади кластера.

Качество кластеризации достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Он легко рассчитывается и интерпретируется. Во время работы алгоритм хранит в RAM небольшое количество информации по каждому кластеру и требует минимальное число сканирований набора данных. CLOPE автоматически подбирает количество кластеров, причем это регулируется одним единственным параметром – коэффициентом отталкивания.

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

Пусть имеется база транзакций [math]D[/math], состоящая из множества транзакций [math]\{t_{1},t_{2},...,t_{n}\}[/math]. Каждая транзакция есть набор объектов [math]\{i_1,...,i_A\} [/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]A [/math] — длина транзакции, [math]k [/math] — число кластеров.

При этом задан параметр [math]r[/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]

Для построения начального распределения транзакций по кластерам необходимо сделать первый проход по таблице (фаза инициализации). В время нее для каждой транзакции выбирается кластер таким образом, чтобы функция [math] Profit(C)[/math] была максимальной.

Далее происходят "уточняющие" проходы (фаза итерации), где для каждой транзакции производится попытка перемещения в другой кластер так, чтобы [math] Profit(C) \longrightarrow max[/math].

Если больше не существует перемещений транзакций, увеличивающих глобальную стоимость [math] Profit(C) [/math], то действие алгоритма заканчивается.

3 Литература

Wang, K., Xu, C.. Liu, B. Clustering transactions using large items. In Proc. CIKM’99, Kansas, Missouri, 1999.

Fasulo D. «An Analysis Of Recent Work on Clustering Algorithms». Department of Computer Science & Engineering.» / D. Fasulo// University of Washington,1999.