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

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания. 
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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 < r \leq 1</math> - коэффициент отталкивания.

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

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

<math> Profit(C, r) \to max </math>

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

<math> Profit(C, r) \to max </math>

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

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <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.    удалить все пустые кластеры;

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

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

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

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

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
Алгоритм CLOPE имеет множество приложений в базах данных, в частности для MySQL: https://github.com/infozor/php_mysql_clustering_clope

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