Версия 23:33, 24 октября 2016

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритма
3 Литература

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

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

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 \cup \dots \cup C_k=\{t_1,...,t_n\}[/math] и [math]C_i \ne \empty[/math] и [math]C_i \cap C_j = \empty [/math], для [math]i \ge 1, k \ge j[/math]. Каждый элемент [math]C_i[/math] называется кластером, а [math]n, m, k[/math] – количество транзакций, количество объектов в базе транзакций и число кластеров соответственно.

Каждый кластер [math]C[/math] имеет следующие характеристики:

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

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

[math]S(C)= \sum_{i \in D(C)} Occ(i,C)= \sum_{t_i \in C} \mid t_i \mid , [/math]

[math]W(C)= \mid D(C) \mid ,H(C)=S(C)/W(C) [/math]

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

[math] Profit(C) = \frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid } = \frac{\sum^{k}_{i=1} \frac{S(C_i)}{W(C_i)^r} \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid } [/math]

[math]\mid C_i \mid[/math]количество объектов в [math]i[/math]-ом кластере, [math]k[/math] – количество кластеров, [math]r[/math] – коэффициент отталкивания [math](0 \lt r \le 1)[/math]

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

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

для заданных [math]D[/math] и [math]r[/math] найти разбиение [math]C[/math] такое, что: [math]Profit(C) \longrightarrow max [/math].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература

[1]

@@ Строка 5: / Строка 5: @@
 === Математическое описание алгоритма ===
+Пусть имеется база транзакций <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 \cup \dots \cup C_k=\{t_1,...,t_n\}</math> и <math>C_i \ne \empty</math> и <math>C_i \cap C_j = \empty </math>, для <math>i \ge 1, k \ge j</math>. Каждый элемент <math>C_i</math> называется кластером, а <math>n, m, k</math> – количество транзакций, количество объектов в базе транзакций и число кластеров соответственно.
+Каждый кластер <math>C</math> имеет следующие характеристики:
+<math>D(C)</math> – множество уникальных объектов;
+<math>Occ(i,C)</math> – количество вхождений (частота) объекта <math>i</math> в кластер <math>C</math>;
+<math>S(C)= \sum_{i \in D(C)} Occ(i,C)= \sum_{t_i \in C}  \mid t_i  \mid , </math>
+<math>W(C)=  \mid D(C) \mid ,H(C)=S(C)/W(C) </math>
+Функция стоимости:
+<math> Profit(C) = \frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid } = \frac{\sum^{k}_{i=1} \frac{S(C_i)}{W(C_i)^r} \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid }  </math>
+<math>\mid C_i \mid</math>количество объектов в <math>i</math>-ом кластере, <math>k</math> – количество кластеров, <math>r</math> – коэффициент отталкивания <math>(0 < r \le 1)</math>
+С помощью параметра <math>r</math> регулируется уровень сходства транзакций внутри кластера, и, как
+следствие, финальное количество кластеров. Этот коэффициент подбирается пользователем. Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.
+Постановка задачи кластеризации алгоритмом CLOPE выглядит следующим образом:
+для заданных <math>D</math> и <math>r</math> найти разбиение <math>C</math> такое, что:
+<math>Profit(C) \longrightarrow max </math>.
 === Вычислительное ядро алгоритма ===

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