Алговики - Вклад [ru]

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

2017-02-02T18:10:34Z

Ilya365365: /* Свойства и структура алгоритма CLOPE */

== Свойства и структура алгоритма CLOPE ==
=== Общее описание алгоритма CLOPE ===

Алгоритм CLOPE решает задачу кластеризации категориальных транзакционных данных. Алгоритм основан на эвристическом методе повышения близости транзакций в кластерах при помощи оптимизации параметров кластерной гистограммы. Авторы (Yiling Yang Xudong Guan Jinyuan You )<ref>Y. Yang, X. Guan J. You. CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data. http://www.inf.ufrgs.br/~alvares/CMP259DCBD/clope.pdf</ref> предложили эффективный, масштабируемый алгоритм, не требующий хранения обучающей выборки в оперативной памяти.

Здесь и далее под категориальными данными понимаются качественные характеристики объектов, измеренные в шкале наименований, то есть при сравнении категориальных данных указывается только, одинаковы или нет объекты относительно данного признака.

Под термином транзакция понимается произвольный набор объектов, например, список ключевых слов статьи, товары, купленные в супермаркете, множество симптомов пациента, характерные фрагменты изображения и так далее. Задача кластеризации транзакционных данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, а отличающиеся друг от друга – в разных кластерах.

В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы. Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:

1: {{ab, abc, acd}, {de, def}}

2: {{ab, abc}, {acd, de, def}}.

Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину <math>W(c_i)</math> (количество уникальных объектов кластера), общее число объектов в кластере <math>S(C_i)</math> и высоту <math>H(C_i) = \frac{S(C_i)}{W(C_i)}</math>. Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.

[[Файл:Clope split.png|border|Гистограммы разбиений]]

Очевидно, что чем меньше ширина и чем больше высота кластера, тем больше сходство в ходящих в него транзакций. Авторы алгоритма формализовали эту идею, введя следующий функционал: <math> Profit(C)=\frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {M} </math>

Здесь <math>k</math> - количество кластеров, <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>, M - число транзакций в выборке, <math>G(C_i) = \frac{S(C_i)}{W^r(C_i)}</math>, <math>r</math> - коэффициент отталкивания. Чем больше <math>r</math>, тем больше кластеров будет сгенерировано.
=== Математическое описание алгоритма CLOPE ===
====Постановка задачи ====
Даны конечное множество объектов <math>O = \{o_1, \dots, o_N\}</math>, выборка транзакций <math>D = \{t_1, \dots, t_M\}</math> и <math>r</math> - коэффициент отталкивания.
Транзакция - вектор произвольной длины, каждая компонента которого является объектом из <math>O</math>.
Требуется найти кластеризацию <math>C</math> - конечное покрытие <math>D</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} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {M} </math>

====Оптимизация функционала====
Авторы алгоритма CLOPE предложили жадную стратегию оптимизации <math>Profit</math>.

Введём функции <math>Delete(C_i, t_j, r)</math>, вычисляющую изменение функции <math>Profit(C)</math> при удалении транзакции <math>t_j</math> из кластера <math>C_i</math>; <math>Add(C_i, t_j, r)</math>, вычисляющую изменение функции <math>Profit(C)</math> при добавлении транзакции <math>t_j</math> в кластер <math>C_i</math>; <math>DeltaAdd(C_i, t_j, r)</math>, вычисляющую изменение функции <math>Profit(C)</math> при перемещении транзакции <math>t_j</math> из кластера <math>C_l</math> в кластер <math>C_i</math>. Ширину <math>W</math> пустого кластера примем равной 1.

<math>Delete(C_i, t_j, r) = G(\{C_i \backslash t_j\})\times\mid C_i \backslash \{t_j\}\mid - G(C_i)\times\mid C_i\mid </math>
 =  <math> \frac {S(C_i) - size(t_j)}{{W(C_i \backslash \{t_j\})}^r} \times (\mid C_i \mid - 1) - \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid </math>

<math>Add(C_i, t_j, r) = G(C_i \cup \{t_j\}) \times \mid C_i \cup \{t_j\} \mid - G(C_i)\times\mid C_i\mid</math>  =  <math> \frac {S(C_i) + size(t_j)}{{W(C_i \cup \{t_j\})}^r} \times (\mid C_i \mid + 1) - \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid </math>

<math>DeltaAdd(C_i, t_j, r) = Add(C_i, t_j, r) + Delete(C_l, t_j, r)</math>, где <math>C_l</math> - кластер, к которому отнесена <math>t_j</math>

На этапе инициализации алгоритма выполняется проход по выборке, во время которого каждая транзакция помещается в существующий или пустой кластер таким образом, чтобы максимизировать <math>Profit(C)</math>.
Далее происходят уточняющие проходы по выборке. Во время уточняющего прохода каждая транзакция перемещается в существующий или пустой кластер таким образом, чтобы максимизировать <math>Profit(C)</math>. Если во время уточняющего прохода не было перемещено ни одной транзакции, алгоритм останавливается.

Авторы CLOPE доказали следующую '''теорему''':

Если <math>C_i = argmax_{C_k \in C}DeltaAdd(C_k,t, r)</math>, то перемещение <math>t</math> в кластер <math>C_i</math> даст наибольший прирост функции <math>Profit(C)</math>.

'''Доказательство''': Рассмотрим некоторую кластеризацию <math>C</math> и кластеризацию <math>C^{new}</math>, полученную из <math>C</math> перемещением <math>t</math> в кластер <math>C_i</math>.
Тогда <math>Profit(C^{new}) - Profit(C) = \frac{Add(C_i, t, r) + Delete(C_l, t, r)}{M} </math>
 =  <math>\frac{DeltaAdd(C_i, t, r)}{M};</math>

<math>max_{C_k \in C} Profit(C^{new}) - Profit(C) </math>  =  <math> max_{C_k \in C} \frac{DeltaAdd(C_k, t, r)}{M} </math>  =  <math> max_{C_k \in C} DeltaAdd(C_k,t, r)</math>

'''Следствие 1''': Алгоритм CLOPE сходится при любых <math>O</math>, <math>D</math> и <math>r</math>.

'''Доказательство следствия 1''': Так как <math>DeltaAdd(C_l, t, r) = 0 </math> (<math>C_l</math> - кластер, к которому отнесена <math>t</math>), любое перемещение транзакции увеличивает <math>Profit(C)</math>, следовательно, алгоритм CLOPE сходится при любых <math>O</math>, <math>D</math> и <math>r</math>.
=== Вычислительное ядро ===
Из доказанных выше утверждений следует, что для нахождения оптимального разбиения не нужно вычислять функцию <math>Profit(C)</math>. Достаточно уметь эффективно вычислять функцию
<math>DeltaAdd(C_i, t_j, r) = \frac {S(C_l) - size(t_j)}{{W(C_l \backslash \{t_j\})}^r} \times (\mid C_l \mid - 1) - \frac {S(C_l)}{{W(C_l)}^r} \times \mid C_l \mid </math>  +  <math> \frac {S(C_i) + size(t_j)}{{W(C_i \cup \{t_j\})}^r} \times (\mid C_i \mid + 1) - \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid
</math>

Вычислительным ядром алгоритма являются функции <math>Delete</math> и <math>Add</math>

Самая сложная операция при реализации вычислительного ядра - вычисление ширины кластера. Так как для большинства известных задач кластеризации транзакционных данных средняя длина транзакции <math>A = \frac{\sum_{i = 1}^{M}t_i}{M} << \mid O \mid</math>, авторы алгоритма рекомендуют хранить информацию об объектах кластера в ассоциативном массиве (словаре), ключом которого является номер объекта, а данными - число вхождений соответствующего объекта в кластер. При реализации словаря авторы CLOPE рекомендуют использовать хэш-таблицу.
Таким образом при добавлении или удалении транзакции <math>t</math> требуется <math>size(t)</math> раз обратиться к соответствующему словарю для поиска элементов и, в худшем случае, добавить или удалить <math>size(t)</math> элементов. Эффективная реализация ассоциативного массива является важнейшей и самой частью реализации алгоритма CLOPE.
=== Макроструктура алгоритма ===
====Класс Transaction====
Класс Transaction - структура данных, описывающая транзакцию. Содержит следующие поля:
* size - количество объектов в транзакции
* objects - массив с номерами объектов
* id - уникальный номер транзакции. Равен 0, если транзакция не отнесена к какому-либо кластеру
* cluster_id - номер кластера, в котором находится транзакция.
Класс Transaction имеет метод add(Cluster)
add(Cluster):
cluster_id = Cluster.id;

====Класс Cluster====
Класс Cluster - структура данных, описывающая кластер. Содержит следующие поля:
*repultion - коэффициент отталкиваня r. Входной параметр CLOPE.
*transaction_map - хэш-таблица, хранящая номера входящих в кластер транзакций
*object_map - словарь, хранящий количество вхождений объектов.
*transaction_quantity - число транзакций, входящих в кластер
*power - число объектов в кластере
*width - ширина кластера (число уникальных объектов)
*profit_summand - вклад кластера в функционал profit
*id - уникальный номер кластера
Класс Cluster содержит следующие методы:
* calculate_profit_summand(power, width, transaction_quantity) вычисляет вклад кластера с заданными параметрами в функционал Profit
calculate_profit_summand(power, width, transaction_quantity)
'''return''' power * transaction_quantity / width^self.repultion;
* estimate_profit_summand_after_addition(transaction) - оценивает вклад кластера в функционал Profit после добавления транзакции
estimate_profit_summand_after_addition(transaction)
new_width = width;
'''for each''' object '''in''' transaction:
if (self.object_map.get(object) == NULL):
new_width += 1;
new_profit = calculate_profit_summand(self.power + transaction.size,
new_width,
transaction_quantity + 1);
'''return''' new_profit;

* estimate_profit_summand_after_dellition(transaction) - оценивает вклад кластера в функционал Profit после удаления транзакции
estimate_profit_summand_after_dellition(transaction)
new_width = width;
'''for each''' object '''in''' transaction:
if (self.object_map.get(object) == 1) new_width -= 1;
new_profit = calculate_profit_summand(self.power - transaction.size,
new_width,
transaction_quantity - 1);
'''return''' new_profit;
* add_transaction(transaction) - добавление транзакции
add_transaction(transaction)
self.transaction_map.push(transaction.id);
self.power += transaction.size;
self.transaction_quantity += 1;
'''for each''' object '''in''' transaction.objects:
'''if''' (self.object_map.get(object) == NULL):
self.object_map.push((object,1));
'''else:'''
self.object_map[object] += 1;
self.width = self.object_map.size();
self.profit_summand = calculate_profit_summand(self.power,
self.width,
self.transaction_quantity);
* delete_transaction(transaction) - удаление транзакции
delete_transaction(transaction)
self.transaction_map.pop(transaction.id);
self.power -= transaction.size;
self.transaction_quantity -= 1;
'''for each''' object '''in''' transaction.objects:
'''if''' (self.object_map.get(object) == 1):
self.object_map.pop((object,1));
'''else:'''
self.object_map[object] -= 1;
self.width = self.object_map.size();
self.profit_summand = calculate_profit_summand(self.power,
self.width,
self.transaction_quantity);
Также класс Cluster содержит два конструктора:
* Cluster(id) - конструктор, создающий пустой кластер.
* Cluster(id, transaction) - конструктор, создающий кластер с единственной транзакцией.
====Класс CLOPE====
Класс CLOPE структура данных, обеспечивающая работу алгоритма. Класс CLOPE содержит следующие поля:
* cluster_map - ассоциативный массив, содержащий информацию о кластерах. Ключ - номер кластера. Кластер с индексом 0 является пустым.
* cluster_quantity - переменная, хранящая количество кластеров
* sample_size - переменная хранящая, количество транзакций.
В классе CLOPE необходимо реализовать следующие методы:
* get_next_transaction() - получение следующей транзакции из файла. Если достигнут конец файла, считывается первая транзакция.
*get_best_move(transaction) - найти кластер, в который следует переместить транзакцию
get_best_move(transaction)
'''if''' transaction.cluster_id != 0 : //транзакция лежит в кластере
old_cluster = self.cluster_map[transaction.cluster_id];
delete_change = old_cluster.profit_summand -
old_cluster.estimate_profit_summand_after_dellition(transaction);
else: //инициализация
delete_change = 0;
=== Схема реализации последовательного алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма ===
=== Входные и выходные данные ===

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

2017-02-02T17:30:09Z

Ilya365365: /* Свойства и структура алгоритма CLOPE */

== Свойства и структура алгоритма CLOPE ==
=== Общее описание алгоритма CLOPE ===

Алгоритм CLOPE решает задачу кластеризации категориальных транзакционных данных. Алгоритм основан на эвристическом методе повышения близости транзакций в кластерах при помощи оптимизации параметров кластерной гистограммы. Авторы (Yiling Yang Xudong Guan Jinyuan You )<ref>Y. Yang, X. Guan J. You. CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data. http://www.inf.ufrgs.br/~alvares/CMP259DCBD/clope.pdf</ref> предложили эффективный, масштабируемый алгоритм, не требующий хранения обучающей выборки в оперативной памяти.

Здесь и далее под категориальными данными понимаются качественные характеристики объектов, измеренные в шкале наименований, то есть при сравнении категориальных данных указывается только, одинаковы или нет объекты относительно данного признака.

Под термином транзакция понимается произвольный набор объектов, например, список ключевых слов статьи, товары, купленные в супермаркете, множество симптомов пациента, характерные фрагменты изображения и так далее. Задача кластеризации транзакционных данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, а отличающиеся друг от друга – в разных кластерах.

В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы. Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:

1: {{ab, abc, acd}, {de, def}}

2: {{ab, abc}, {acd, de, def}}.

Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину <math>W(c_i)</math> (количество уникальных объектов кластера), общее число объектов в кластере <math>S(C_i)</math> и высоту <math>H(C_i) = \frac{S(C_i)}{W(C_i)}</math>. Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.

[[Файл:Clope split.png|border|Гистограммы разбиений]]

Очевидно, что чем меньше ширина и чем больше высота кластера, тем больше сходство в ходящих в него транзакций. Авторы алгоритма формализовали эту идею, введя следующий функционал: <math> Profit(C)=\frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {M} </math>

Здесь <math>k</math> - количество кластеров, <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>, M - число транзакций в выборке, <math>G(C_i) = \frac{S(C_i)}{W^r(C_i)}</math>, <math>r</math> - коэффициент отталкивания. Чем больше <math>r</math>, тем больше кластеров будет сгенерировано.
=== Математическое описание алгоритма CLOPE ===
====Постановка задачи ====
Даны конечное множество объектов <math>O = \{o_1, \dots, o_N\}</math>, выборка транзакций <math>D = \{t_1, \dots, t_M\}</math> и <math>r</math> - коэффициент отталкивания.
Транзакция - вектор произвольной длины, каждая компонента которого является объектом из <math>O</math>.
Требуется найти кластеризацию <math>C</math> - конечное покрытие <math>D</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} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {M} </math>

====Оптимизация функционала====
Авторы алгоритма CLOPE предложили жадную стратегию оптимизации <math>Profit</math>.

Введём функции <math>Delete(C_i, t_j, r)</math>, вычисляющую изменение функции <math>Profit(C)</math> при удалении транзакции <math>t_j</math> из кластера <math>C_i</math>; <math>Add(C_i, t_j, r)</math>, вычисляющую изменение функции <math>Profit(C)</math> при добавлении транзакции <math>t_j</math> в кластер <math>C_i</math>; <math>DeltaAdd(C_i, t_j, r)</math>, вычисляющую изменение функции <math>Profit(C)</math> при перемещении транзакции <math>t_j</math> из кластера <math>C_l</math> в кластер <math>C_i</math>. Ширину <math>W</math> пустого кластера примем равной 1.

<math>Delete(C_i, t_j, r) = G(\{C_i \backslash t_j\})\times\mid C_i \backslash \{t_j\}\mid - G(C_i)\times\mid C_i\mid </math>
 =  <math> \frac {S(C_i) - size(t_j)}{{W(C_i \backslash \{t_j\})}^r} \times (\mid C_i \mid - 1) - \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid </math>

<math>Add(C_i, t_j, r) = G(C_i \cup \{t_j\}) \times \mid C_i \cup \{t_j\} \mid - G(C_i)\times\mid C_i\mid</math>  =  <math> \frac {S(C_i) + size(t_j)}{{W(C_i \cup \{t_j\})}^r} \times (\mid C_i \mid + 1) - \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid </math>

<math>DeltaAdd(C_i, t_j, r) = Add(C_i, t_j, r) + Delete(C_l, t_j, r)</math>, где <math>C_l</math> - кластер, к которому отнесена <math>t_j</math>

На этапе инициализации алгоритма выполняется проход по выборке, во время которого каждая транзакция помещается в существующий или пустой кластер таким образом, чтобы максимизировать <math>Profit(C)</math>.
Далее происходят уточняющие проходы по выборке. Во время уточняющего прохода каждая транзакция перемещается в существующий или пустой кластер таким образом, чтобы максимизировать <math>Profit(C)</math>. Если во время уточняющего прохода не было перемещено ни одной транзакции, алгоритм останавливается.

Авторы CLOPE доказали следующую '''теорему''':

Если <math>C_i = argmax_{C_k \in C}DeltaAdd(C_k,t, r)</math>, то перемещение <math>t</math> в кластер <math>C_i</math> даст наибольший прирост функции <math>Profit(C)</math>.

'''Доказательство''': Рассмотрим некоторую кластеризацию <math>C</math> и кластеризацию <math>C^{new}</math>, полученную из <math>C</math> перемещением <math>t</math> в кластер <math>C_i</math>.
Тогда <math>Profit(C^{new}) - Profit(C) = \frac{Add(C_i, t, r) + Delete(C_l, t, r)}{M} </math>
 =  <math>\frac{DeltaAdd(C_i, t, r)}{M};</math>

<math>max_{C_k \in C} Profit(C^{new}) - Profit(C) </math>  =  <math> max_{C_k \in C} \frac{DeltaAdd(C_k, t, r)}{M} </math>  =  <math> max_{C_k \in C} DeltaAdd(C_k,t, r)</math>

'''Следствие 1''': Алгоритм CLOPE сходится при любых <math>O</math>, <math>D</math> и <math>r</math>.

'''Доказательство следствия 1''': Так как <math>DeltaAdd(C_l, t, r) = 0 </math> (<math>C_l</math> - кластер, к которому отнесена <math>t</math>), любое перемещение транзакции увеличивает <math>Profit(C)</math>, следовательно, алгоритм CLOPE сходится при любых <math>O</math>, <math>D</math> и <math>r</math>.
=== Вычислительное ядро ===
Из доказанных выше утверждений следует, что для нахождения оптимального разбиения не нужно вычислять функцию <math>Profit(C)</math>. Достаточно уметь эффективно вычислять функцию
<math>DeltaAdd(C_i, t_j, r) = \frac {S(C_l) - size(t_j)}{{W(C_l \backslash \{t_j\})}^r} \times (\mid C_l \mid - 1) - \frac {S(C_l)}{{W(C_l)}^r} \times \mid C_l \mid </math>  +  <math> \frac {S(C_i) + size(t_j)}{{W(C_i \cup \{t_j\})}^r} \times (\mid C_i \mid + 1) - \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid
</math>

Вычислительным ядром алгоритма являются функции <math>Delete</math> и <math>Add</math>

Самая сложная операция при реализации вычислительного ядра - вычисление ширины кластера. Так как для большинства известных задач кластеризации транзакционных данных средняя длина транзакции <math>A = \frac{\sum_{i = 1}^{M}t_i}{M} << \mid O \mid</math>, авторы алгоритма рекомендуют хранить информацию об объектах кластера в ассоциативном массиве (словаре), ключом которого является номер объекта, а данными - число вхождений соответствующего объекта в кластер. При реализации словаря авторы CLOPE рекомендуют использовать хэш-таблицу.
Таким образом при добавлении или удалении транзакции <math>t</math> требуется <math>size(t)</math> раз обратиться к соответствующему словарю для поиска элементов и, в худшем случае, добавить или удалить <math>size(t)</math> элементов. Эффективная реализация ассоциативного массива является важнейшей и самой частью реализации алгоритма CLOPE.
=== Макроструктура алгоритма ===
====Класс Transaction====
Класс Transaction - структура данных, описывающая транзакцию. Содержит следующие поля:
* size - количество объектов в транзакции
* objects - массив с номерами объектов
* id - уникальный номер транзакции
====Класс Cluster====
Класс Cluster - структура данных, описывающая кластер. Содержит следующие поля:
*repultion - коэффициент отталкиваня r. Входной параметр CLOPE.
*transaction_map - хэш-таблица, хранящая номера входящих в кластер транзакций
*object_map - словарь, хранящий количество вхождений объектов.
*transaction_quantity - число транзакций, входящих в кластер
*power - число объектов в кластере
*width - ширина кластера (число уникальных объектов)
*profit_summand - вклад кластера в функцию profit
Класс Cluster содержит следующие методы:
* calculate_profit_summand(power, width, transaction_quantity) вычисляет вклад кластера с заданными параметрами в функцию profit
calculate_profit_summand(power, width, transaction_quantity)
'''return''' power * transaction_quantity / width^self.repultion
* estimate_width_after_addition(transaction) - оценивает ширину кластера, после добавления транзакции в кластер
estimate_width_after_addition(transaction)
new_width = width;
'''for each''' object '''in''' transaction:
if (self.object_map.get(object) == NULL) new_width += 1;
'''return''' new_width;

* estimate_width_after_delition(transaction) - оценивает ширину кластера, после удаления транзакции из кластера
estimate_width_after_deliton(transaction)
new_width = width;
'''for each''' object '''in''' transaction:
'''if''' (object_map.get(object) == 1):
new_width -= 1;
'''return''' new_width;
* add_transaction(transaction) - добавление транзакции
add_transaction(transaction)
self.transaction_map.push(transaction.id)
self.power += transaction.size
self.transaction_quantity += 1
'''for each''' object '''in''' transaction.objects:
'''if''' (self.object_map.get(object) == NULL):
self.object_map.push((object,1));
'''else:'''
self.object_map[object] += 1;
self.width = self.object_map.size();
self.profit_summand = calculate_profit_summand(self.power,
self.width,
self.transaction_quantity)
* delete_transaction(transaction) - удаление транзакции
delete_transaction(transaction)
self.transaction_map.pop(transaction.id)
self.power -= transaction.size
self.transaction_quantity -= 1
'''for each''' object '''in''' transaction.objects:
'''if''' (self.object_map.get(object) == 1):
self.object_map.pop((object,1));
'''else:'''
self.object_map[object] -= 1;
self.width = self.object_map.size();
self.profit_summand = calculate_profit_summand(self.power,
self.width,
self.transaction_quantity)

=== Схема реализации последовательного алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма ===
=== Входные и выходные данные ===

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

2017-02-02T12:49:41Z

Ilya365365: /* Свойства и структура алгоритма CLOPE */

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

2017-01-31T18:00:54Z

Ilya365365:

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

2017-01-31T17:59:08Z

Ilya365365:

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

2017-01-31T17:55:39Z

Ilya365365: /* Свойства и структура алгоритма CLOPE */

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

2017-01-31T17:14:08Z

Ilya365365: /* Свойства и структура алгоритма CLOPE */

== Свойства и структура алгоритма CLOPE ==
=== Общее описание алгоритма CLOPE ===

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

Алгоритм CLOPE работает с транзакциями. Под термином транзакция понимается произвольный набор объектов, например, список ключевых слов статьи, товары, купленные в супермаркете, множество симптомов пациента, характерные фрагменты изображения и так далее. Задача кластеризации транзакционных данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, а отличающиеся друг от друга – в разных кластерах.

В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы.Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:

1: {{ab, abc, acd}, {de, def}}

2: {{ab, abc}, {acd, de, def}}.

Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину W (количество уникальных объектов кластера) и высоту H (отношение общего числа объектов и ширины). Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.
[[Файл:Clope split.png|border|Гистограммы разбиений]]

Лучшим признаётся разбиение, при котором достигается минимум функции <math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>  =  <math>\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>r</math> - коэффициент отталкивания, <math>k</math> - количество кластеров, <math>S(C_i)</math> - число объектов в кластере <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>, <math>H(C_i)</math> и <math>W(c_i)</math> - высота и ширина <math>C_i</math> соответственно.
=== Математическое описание алгоритма CLOPE ===
=== Вычислительное ядро ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма ===
=== Входные и выходные данные ===

Файл:CLOPEdefs.png

2017-01-20T11:30:31Z

Ilya365365:

Файл:TransactionBaseD.png

2017-01-20T10:34:35Z

Ilya365365:

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

2017-01-20T06:47:11Z

Ilya365365:

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

Алгоритм CLOPE работает с транзакциями. Под термином транзакция понимается произвольный набор объектов, например, список ключевых слов статьи, товары, купленные в супермаркете, множество симптомов пациента, характерные фрагменты изображения и так далее. Задача кластеризации транзакционных данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, а отличающиеся друг от друга – в разных кластерах.

В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы.Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:

1: {{ab, abc, acd}, {de, def}}

2: {{ab, abc}, {acd, de, def}}.

Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину W (количество уникальных объектов кластера) и высоту H (отношение общего числа объектов и ширины). Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.
[[Файл:Clope split.png|border|Гистограммы разбиений]]

Лучшим признаётся разбиение, у которого сумма H/W, взвешенная с количеством транзакций в каждом кластере, минимальна.
=== Математическое описание алгоритма CLOPE ===
=== Вычислительное ядро ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма ===
=== Входные и выходные данные ===

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

2017-01-20T06:34:17Z

Ilya365365: Новая страница: «== Свойства и структура алгоритма CLOPE == === Общее описание алгоритма CLOPE === Алгоритм CLOPE реша…»

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

Алгоритм CLOPE работает с транзакциями. Под термином транзакция понимается произвольный набор объектов, например, список ключевых слов статьи, товары, купленные в супермаркете, множество симптомов пациента, характерные фрагменты изображения и так далее. Задача кластеризации транзакционных данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, а отличающиеся друг от друга – в разных кластерах.

В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы.Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:

1: {{ab, abc, acd}, {de, def}}

2: {{ab, abc}, {acd, de, def}}.

Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину W (количество уникальных объектов кластера) и высоту H (отношение общего числа объектов и ширины). Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.
[[Файл:Clope split.png|border|Гистограммы разбиений]]

Лучшим признаётся разбиение, у которого
=== Математическое описание алгоритма CLOPE ===
=== Вычислительное ядро ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма ===
=== Входные и выходные данные ===