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

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === Данный алгоритм предна…»)
 
Строка 1: Строка 1:
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных
+
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>
+
Пусть имеется база транзакций <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>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.
 +
 
 +
=== Информационный граф алгоритма ===
 +
=== Ресурс параллелизма алгоритма ===
 +
=== Входные и выходные данные алгоритма ===
 +
=== Свойства алгоритма ===
 +
 
 +
== Программная реализация алгоритма ==
 +
=== Особенности реализации последовательного алгоритма ===
 +
=== Локальность данных и вычислений ===
 +
=== Возможные способы и особенности параллельной реализации алгоритма ===
 +
=== Масштабируемость алгоритма и его реализации ===
 +
=== Динамические характеристики и эффективность реализации алгоритма ===
 +
=== Выводы для классов архитектур ===
 +
=== Существующие реализации алгоритма ===

Версия 23:37, 15 октября 2016

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 Информационный граф алгоритма

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

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

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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