Участник:Артем Карпухин/Алгоритм 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 количество кластеров подбирается автоматически и зависит от коэффициента отталкивания - параметра, определяющего уровень сходства транзакций внутри кластера. Коэффициент отталкивания задается пользователем: чем больше данный параметр, тем ниже уровень сходства транзакций и, как следствие, большее количество кластеров будет создано.

https://basegroup.ru/community/articles/clope http://www.fundamental-research.ru/ru/article/view?id=33381 http://www.olap.ru/home.asp?artId=155 Задачи кластеризации больших массивов категорийных данных весьма актуальна для систем анализа данных.

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...C_k[/math]  =  [math]\{t_1,...,t_n\}[/math] и [math]C_i[/math] [math]\ne[/math] [math]\oslash[/math] [math]\land[/math] [math]C_i[/math] [math]\cap[/math]

[math]C_j[/math]  =  [math]\ne[/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 [/math] :

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

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

[math]S(C) [/math]  =  [math]\sum_i\inD(C)[/math];

3 Литература

<references \>