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

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

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

Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.

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

Пусть имеется база транзакций [math]D[/math], которая состоит из множества транзакций [math]\{t_1, ..., t_n\}[/math]. Каждая из транзакций суть набор объектов [math]\{i_1, ..., i_n\}[/math]. Множество кластеров [math]\{C_1, ..., C_m\}[/math] есть разбиение множества транзакций таким образом, что [math]C_1 \oplus ... \oplus C_m = D[/math]. У каждого кластера есть следующие характеристики:

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

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

3. [math]S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}[/math] - площадь кластера

4. [math]W(C) = |D(C)|[/math] - ширина кластера,

5. [math]H(C) = S(C) / W(C)[/math] - высота кластера.

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

[math]Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}[/math],

где [math]r, 0 \lt r \leq 1[/math] - коэффициент отталкивания.

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

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

[math] Profit(C, r) \to max [/math]

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

Вычислительным ядром алгоритма является оптимизация функции стоимости.

[math] Profit(C, r) \to max [/math]

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

Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

1.5 Схема реализации последовательного алгоритма

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

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер [math]C_i[/math], который дает максимум [math]Profit(C,r)[/math];

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер [math]C_j[/math], который максимизирует [math]Profit(C,r)[/math];

2.3.3 если [math]C_i \neq C_j[/math] тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

1.6 Последовательная сложность алгоритма

Пусть средняя длина транзакции равна [math]A[/math], общее число транзакций [math]N[/math], максимально возможное число кластеров [math]K[/math]. Временная сложность одной итерации равна [math]O(N*K*A)[/math], показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

1.7 Информационный граф алгоритма

Здесь вершина Read - чтение транзакции из таблицы, PutIntoCluster - положить t в существующий либо в новый кластер, который дает максимум Profit(C,r), WriteIfINotEqualsJ соответствует шагам 2.3.3 и 2.3.3.1 пункта 1.5.

1.8 Ресурс параллелизма алгоритма

Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

1.9 Входные и выходные данные алгоритма

Входные данные - таблица транзакций [math]D = \{t_1, ..., t_n\}[/math]. Выходные данные - множество кластеров [math]\{C_1, ... , C_k\}[/math]

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

Соотношение последовательной и параллельной сложностей является квадратичным при том, что вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных является линейной.

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

Алгоритм CLOPE имеет множество приложений в базах данных, в частности для MySQL: https://github.com/infozor/php_mysql_clustering_clope

Также есть реализация на языке Go: https://github.com/realb0t/go-clope