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