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

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

2016-12-21T07:24:17Z

Андрей Туманов:

{{Assignment}}
Основные авторы описания: [[Участник:Андрей_Туманов|А.Л.Туманов]] ([[#Общее описание алгоритма|1.1]], [[#Математическое описание алгоритма|1.2]], [[#Вычислительное ядро алгоритма|1.3]], [[#Макроструктура алгоритма|1.4]], [[#Схема реализации последовательного алгоритма|1.5]], [[#Входные и выходные данные алгоритма|1.9]]), [[Участник:Boltonidze|А.В.Александров]] ([[#Последовательная сложность алгоритма|1.6]], [[#Информационный граф|1.7]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Свойства алгоритма|1.10]] [[#Существующие реализации алгоритма|2.7]])

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE<ref>Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.</ref>) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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> имеет следующие характеристики:
[[Файл:ExampleCLOPE.jpg|500px|thumb|right]]
<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> <ref>Нейский И.М. Классификация и сравнение методов кластеризации.</ref>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным. <ref>Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope</ref>

'''Схема реализации на псевдокоде:'''

Входные параметры:

* <math>t</math> - транзакции

* <math>r</math> - коэффициент отталкивания

Выходной параметр:

* <math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

=== Информационный граф ===
На этапе инициализации при обработке каждой транзакции количество кластеров может как увеличиться, так и остаться неизменным. Это показано пунктирными линиями:
[[Файл:init_clope.png|600px|center|Инициализация]]
На этапе итерации функции DeltaAdd/DeltaRemove могут считать параллельно для каждой транзакции
[[Файл:iter_clope.png ‎|600px|center|Итерации]]

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

Вычисление стоимости добавления/удаления транзакции, которые выполняются функциями DeltaAdd/DeltaRemove, происходит независимо для всех <math>k</math> кластеров. Поэтому все вычисления можно производить параллельно. Таким образом сложность алгоритма с <math>O(n*k*m)</math> понижается до <math>O(n*m)</math>.

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

'''Входные данные:'''

<math>n</math> транзакций длины <math>m</math> и коэффициент отталкивания <math>r</math>

'''Выходные данные:'''

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины <math>n</math>)

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

* Соотношение последовательной и параллельной сложности алгоритма определяется количеством кластеров: <math>\dfrac{O(n*k*m)}{O(n*m)} = k</math>
* [[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна <math>\dfrac{nk(m+8) + m + 2}{nm + n + 1} \cong k</math>
* Алгоритм не является [[глоссарий#Устойчивость|''устойчивым'']], так как результат работы зависит от порядка чтения транзакций и от текущего набора транзакций в кластере.
* Выполняется свойство сбалансированности операций между параллельными ветвями алгоритма, так как для каждой транзакции выполняются функции DeltaAdd/DeltaRemove, считающие стоимость добавления/удаления транзакции.
* Свойство [[глоссарий#Детерминированность|''детерминированности алгоритмов'']] не выполняется, так как результат алгоритма зависит от порядка прохождения транзакций. Но если рассматривать транзакции как нумерованный список, то результат будет определен однозначно от запуска к запуску. Однако существует расширение алгоритма, обеспечивающее свойство детерминированности. <ref>Li, Y., Le, J., Wang, M. Improving CLOPE’s Profit Value and Stability with an Optimized Agglomerative Approach. Algorithms 2015, 8, 380-394.</ref>.
* Так как алгоритм предназначен для кластеризации категориальных данных, то он практически неприменим для числовой кластеризации.
* Быстро работает даже для большого количества данных, обеспечивая при этом хорошее качество кластеризации
* Имеет простую реализацию

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===
Проверка масштабируемости производилась с использованием стандарта MPI на суперкомпьютере "Ломоносов" с числом процессоров: 1,8,16,32,64.
Результаты проверки масштабируемости приведены ниже на графике
[[file:maschtab_clope.png||700px|График масштабируемости]]

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

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

=== Существующие реализации алгоритма ===
* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java
Также существуют пользовательские реализации алгоритма:
* https://github.com/infozor/php_mysql_clustering_clope - реализация алгоритма на PHP
* https://github.com/Tolsi/scala-clope - реализация алгоритма Scala

= Литература =

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

2016-12-20T23:45:11Z

Андрей Туманов: /* Масштабируемость алгоритма и его реализации */

Основные авторы описания: [[Участник:Андрей_Туманов|А.Л.Туманов]] ([[#Общее описание алгоритма|1.1]], [[#Математическое описание алгоритма|1.2]], [[#Вычислительное ядро алгоритма|1.3]], [[#Макроструктура алгоритма|1.4]], [[#Схема реализации последовательного алгоритма|1.5]], [[#Входные и выходные данные алгоритма|1.9]]), [[Участник:Boltonidze|А.В.Александров]] ([[#Последовательная сложность алгоритма|1.6]], [[#Информационный граф|1.7]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Свойства алгоритма|1.10]] [[#Существующие реализации алгоритма|2.7]])

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE<ref>Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.</ref>) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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> имеет следующие характеристики:
[[Файл:ExampleCLOPE.jpg|500px|thumb|right]]
<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> <ref>Нейский И.М. Классификация и сравнение методов кластеризации.</ref>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным. <ref>Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope</ref>

'''Схема реализации на псевдокоде:'''

Входные параметры:

* <math>t</math> - транзакции

* <math>r</math> - коэффициент отталкивания

Выходной параметр:

* <math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

=== Информационный граф ===
На этапе инициализации при обработке каждой транзакции количество кластеров может как увеличиться, так и остаться неизменным. Это показано пунктирными линиями:
[[Файл:init_clope.png|600px|center|Инициализация]]
На этапе итерации функции DeltaAdd/DeltaRemove могут считать параллельно для каждой транзакции
[[Файл:iter_clope.png ‎|600px|center|Итерации]]

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

Вычисление стоимости добавления/удаления транзакции, которые выполняются функциями DeltaAdd/DeltaRemove, происходит независимо для всех <math>k</math> кластеров. Поэтому все вычисления можно производить параллельно. Таким образом сложность алгоритма с <math>O(n*k*m)</math> понижается до <math>O(n*m)</math>.

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

'''Входные данные:'''

<math>n</math> транзакций длины <math>m</math> и коэффициент отталкивания <math>r</math>

'''Выходные данные:'''

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины <math>n</math>)

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

* Соотношение последовательной и параллельной сложности алгоритма определяется количеством кластеров: <math>\dfrac{O(n*k*m)}{O(n*m)} = k</math>
* [[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна <math>\dfrac{nk(m+8) + m + 2}{nm + n + 1} \cong k</math>
* Алгоритм не является [[глоссарий#Устойчивость|''устойчивым'']], так как результат работы зависит от порядка чтения транзакций и от текущего набора транзакций в кластере.
* Выполняется свойство сбалансированности операций между параллельными ветвями алгоритма, так как для каждой транзакции выполняются функции DeltaAdd/DeltaRemove, считающие стоимость добавления/удаления транзакции.
* Свойство [[глоссарий#Детерминированность|''детерминированности алгоритмов'']] не выполняется, так как результат алгоритма зависит от порядка прохождения транзакций. Но если рассматривать транзакции как нумерованный список, то результат будет определен однозначно от запуска к запуску. Однако существует расширение алгоритма, обеспечивающее свойство детерминированности. <ref>Li, Y., Le, J., Wang, M. Improving CLOPE’s Profit Value and Stability with an Optimized Agglomerative Approach. Algorithms 2015, 8, 380-394.</ref>.
* Так как алгоритм предназначен для кластеризации категориальных данных, то он практически неприменим для числовой кластеризации.
* Быстро работает даже для большого количества данных, обеспечивая при этом хорошее качество кластеризации
* Имеет простую реализацию

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===
Проверка масштабируемости производилась с использованием стандарта MPI на суперкомпьютере "Ломоносов" с числом процессоров: 1,8,16,32,64.
Результаты проверки масштабируемости приведены ниже на графике
[[file:maschtab_clope.png||700px|График масштабируемости]]

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

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

=== Существующие реализации алгоритма ===
* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java
Также существуют пользовательские реализации алгоритма:
* https://github.com/infozor/php_mysql_clustering_clope - реализация алгоритма на PHP
* https://github.com/Tolsi/scala-clope - реализация алгоритма Scala

= Литература =

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

2016-12-20T22:08:09Z

Андрей Туманов: /* Информационный граф */

Основные авторы описания: [[Участник:Андрей_Туманов|А.Л.Туманов]] ([[#Общее описание алгоритма|1.1]], [[#Математическое описание алгоритма|1.2]], [[#Вычислительное ядро алгоритма|1.3]], [[#Макроструктура алгоритма|1.4]], [[#Схема реализации последовательного алгоритма|1.5]], [[#Входные и выходные данные алгоритма|1.9]]), [[Участник:Boltonidze|А.В.Александров]] ([[#Последовательная сложность алгоритма|1.6]], [[#Информационный граф|1.7]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Свойства алгоритма|1.10]] [[#Существующие реализации алгоритма|2.7]])

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE<ref>Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.</ref>) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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> имеет следующие характеристики:
[[Файл:ExampleCLOPE.jpg|500px|thumb|right]]
<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> <ref>Нейский И.М. Классификация и сравнение методов кластеризации.</ref>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным. <ref>Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope</ref>

'''Схема реализации на псевдокоде:'''

Входные параметры:

* <math>t</math> - транзакции

* <math>r</math> - коэффициент отталкивания

Выходной параметр:

* <math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

=== Информационный граф ===
На этапе инициализации при обработке каждой транзакции количество кластеров может как увеличиться, так и остаться неизменным. Это показано пунктирными линиями:
[[Файл:init_clope.png|600px|center|Инициализация]]
На этапе итерации функции DeltaAdd/DeltaRemove могут считать параллельно для каждой транзакции
[[Файл:iter_clope.png ‎|600px|center|Итерации]]

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

Вычисление стоимости добавления/удаления транзакции, которые выполняются функциями DeltaAdd/DeltaRemove, происходит независимо для всех <math>k</math> кластеров. Поэтому все вычисления можно производить параллельно. Таким образом сложность алгоритма с <math>O(n*k*m)</math> понижается до <math>O(n*m)</math>.

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

'''Входные данные:'''

<math>n</math> транзакций длины <math>m</math> и коэффициент отталкивания <math>r</math>

'''Выходные данные:'''

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины <math>n</math>)

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

* Соотношение последовательной и параллельной сложности алгоритма определяется количеством кластеров: <math>\dfrac{O(n*k*m)}{O(n*m)} = k</math>
* [[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна <math>\dfrac{nk(m+8) + m + 2}{nm + n + 1} \cong k</math>
* Алгоритм не является [[глоссарий#Устойчивость|''устойчивым'']], так как результат работы зависит от порядка чтения транзакций и от текущего набора транзакций в кластере.
* Выполняется свойство сбалансированности операций между параллельными ветвями алгоритма, так как для каждой транзакции выполняются функции DeltaAdd/DeltaRemove, считающие стоимость добавления/удаления транзакции.
* Свойство [[глоссарий#Детерминированность|''детерминированности алгоритмов'']] не выполняется, так как результат алгоритма зависит от порядка прохождения транзакций. Но если рассматривать транзакции как нумерованный список, то результат будет определен однозначно от запуска к запуску. Однако существует расширение алгоритма, обеспечивающее свойство детерминированности. <ref>Li, Y., Le, J., Wang, M. Improving CLOPE’s Profit Value and Stability with an Optimized Agglomerative Approach. Algorithms 2015, 8, 380-394.</ref>.
* Так как алгоритм предназначен для кластеризации категориальных данных, то он практически неприменим для числовой кластеризации.
* Быстро работает даже для большого количества данных, обеспечивая при этом хорошее качество кластеризации
* Имеет простую реализацию

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

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

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

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

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

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

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

=== Существующие реализации алгоритма ===
* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java
Также существуют пользовательские реализации алгоритма:
* https://github.com/infozor/php_mysql_clustering_clope - реализация алгоритма на PHP
* https://github.com/Tolsi/scala-clope - реализация алгоритма Scala

= Литература =

Обсуждение участника:Lineprinter

2016-11-07T21:23:36Z

Андрей Туманов: /* Перенос */

== Перенос ==
Статья: [[Участник:Бобцов Борис/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]]
Выполняет: [[Участник:Бобцов Борис| Бобцов Борис]]

Статья: [[Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]]
Выполняют: [[Участник:Greno4ka| Устинов Григорий ]] и [[ Лиджиев Данир ]]

Статья: [[Кластеризация сетями Кохонена]]
Выполняют: [[Участник:Kravtsovkirill| Кравцов Кирилл]] и [[Участник:Emaksimov| Максимов Егор]]

Статья: [[Нахождение собственных чисел квадратной матрицы методом QR разложения (2)]]
Выполняют: Баев Олег и Шевелев Александр

Статья: [[Стабилизированный метод биспоряженных градиентов (BiCGSTAB)]]
Выполняют: Гаврилов Алексей и Новиков Александр

Статья: [[Участники: Бобошко А., Юмакаева А./Решение начальной задачи Коши для системы ОДУ методом Рунге-Кутта 4-го порядка]];
Выполняют: Бобошко Алексей и Юмакаева Алина

Статья: [[Алгоритм кластеризации, основанный на сетях Кохоннена]];
Выполняют: Логвиненко Александра и Адиев Тохтар

Статья: [[Ортогонализация Грама-Шмидта]];
Выполняют: [[Участник:KibAndrey| Кибанов Андрей]] и Аджиева Татьяна

Статья: [[Самоорганизующиеся карты Кохонена]];
Выполняет: [[Участник:Anton goy| Гой Антон]]

Статья:[[ЕМ-алгоритм_(Тематическое_моделирование)]];
Выполняют: Мурат Апишев и Андрей Заночкин

Статья:[[Алгоритм_Ланцоша_с_полной_переортогонализацией]];
Выполняет:[[Участник:Sfedotov| Федотов С.А.]]

Статья: [[Алгоритм_k-средних]]
Выполняют: [[Участник:Error2407|Богомазов Евгений]], [[Участник:Илья_Егоров|Егоров Илья]]

Статья: [[Алгоритм k-means]]
Выполняют: [[Участник:Бротиковская Данута|Данута Бротиковская]] и [[Участник:DennZo1993|Денис Зобнин]]

Статья: [[Partitioning Around Medoids (Алгоритм)]]
Выполняют: [[Участник:Denemmy| Галеев Данил]] и [[Участник:Ivan.Z| Запутляев Иван]]

Статья: [[Нечеткий_алгоритм_С_средних]]
Выполняют: [[Участник:Demon smd|Д.А.Гуськов]], [[Участник:marina abramenkova|М.А.Абраменкова]]

Статья: [[Решение_задачи_Коши_для_системы_ОДУ_методом_Рунге-Кутты_4_порядка]];
Выполняют: [[Участник:Алимов_Дамир_Алиевич|Алимов Дамир]] и [[Участник:Anlesnichiy|Антон Лесничий]]

Статья: [[Строгий_алгоритм_С_средних_(Hard_C-Means,_HCM)]];
Выполняют: [[Участник:Светлана_Лукьяненко|Лукьяненко Светлана]] и [[Участник:Юрий_Комаров|Комаров Юрий]]

Статья: [[Алгоритм кластеризации, основанный на минимальном остовном дереве]];
Выполняет: [[Участник:Astandrik | Стандрик Антон Сергеевич]]

Статья: [[Умножение разреженной матрицы на вектор]];
Выполняет: [[Участник:Lexaloris | Новоселов Алексей]], Выполняет: [[Участник:kochet|П.А. Кочетков]]

Статья: [[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(3)|Нахождение собственных чисел квадратной матрицы методом QR разложения (3)]];
Выполняют: [[Участник:Смирнова_Александра|Смирнова А.С.]], [[Участник:Александра_Киямова|Киямова А.]]

Статья: [[Метод_Якоби_вычисления_сингулярных_чисел_и_векторов]];
Выполняют: [[Участница:Почернина_Елена| Почернина Елена]] и [[Участница:Светлана|Костюкова Светлана]]

Статья: [[Метод_Ньютона_для_решения_систем_нелинейных_уравнений(2)]];
Выполняют: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений]];
Выполняют: [[Участник:Cookie|Шатков С.А.]], [[Участница:JuliaA|Антохина Ю.А.]]

Статья: [[Быстрое_преобразование_Фурье_(FFT)|Быстрое преобразование Фурье (FFT)]];
Выполняют: [[Участник:Victoria_Stepanischeva|Степанищева Виктория]] и [[Участник:Igor_Munkin|Мунькин Игорь]]

Статья: [[Быстрое_дискретное_преобразование_Фурье|Быстрое_дискретное_преобразование_Фурье]];
Выполняют: [[Участник:ivanov.kir.m | К.М.Иванов]], [[Участник:Pumpkin | А.C.Сапин]]

Статья:[[Алгоритм_k_средних]]
Выполняют: [[Участник:Parkhomenko|Пархоменко Павел]], [[Участник:ivan.mashonskiy|Машонский Иван]]

Статья:[[EM-алгоритм_кластеризации]]
Выполняет: [[Участник:Noite|Зинченко Дмитрий]]

Статья:[[Алгоритм_k_means]]
Выполняют: [[Участник:IanaV| Валуйская Яна]], [[Участник:GlotovES| Глотов Евгений]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы ЗП |Метод Якоби вычисления собственных значений симметричной матрицы ЗП]];
Выполняют: [[Участник:Зиновьев Владимир|Зиновьев В.С.]], [[Участник:Пронин Андрей|Пронин А.М.]]

Статья:[[Алгоритм_кластеризации,_основанный_на_минимальном_покрывающем_дереве]]
Выполняет: [[Участник:Kanast74|Дмитриева Анастасия]]

Статья:[[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(4)]]
Выполняют: [[Участник:F-morozov|Морозов Ф. В.]], [[Участник:Nataliya|Пащенко Н. Ф.]]

Статья:[[Хранение_ненулевых_элементов_разреженных_матриц._Умножение_разреженной_матрицы_на_вектор]];
Выполняют: [[Участник:Trrufina|Третьякова Р.М.]] и [[Участник:Екатерина_Буторина|Буторина Е.В.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений2]];
Выполняет: [[Участник:Лукьянова Анна|Лукьянова А.Я.]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы]];
Выполняют: [[Участник: Galkina|Галкина А.С.]], [[Участник: Игорь|Плахов И.А.]]

Статья: [[Метод рекурсивной координатной бисекции]];
Выполняют: [[Участник: Obirvalger|Гордеев Михаил]], [[Участник: KolmakovEA|Колмаков Евгений]]

Статья: [[Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок)]];
Выполняют: [[Участник: Эльвира Ахиярова|Ахиярова Эльвира]]

Статья: [[Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор]];
Выполняют: [[Участник: Janyell|Сычева Евгения]], [[Участник: Ahahalin|Хахалин Анатолий]]

Статья: [[Построение матрицы Адамара произвольного размера]];
Выполняют: [[Участник: Бугаков Юрий|Бугаков Юрий]], Кужамалиев Ернур

Статья: [[Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки (1)]]
Выполняют: [[Участница:Sannikovats| Санникова Татьяна Сергеевна]], [[Участник:Plukshin| Лукшин Петр Андреевич]]

Статья: [[Алгоритм кластеризации, основанный на построении каркаса]];
Выполняют: [[Участник:SenderovichNikita| Сендерович Никита]]

Статья: [[Алгоритм кластеризации, основанный на максимизации ожидания]];
Выполняют: Готман Мария, Лукашкина Юлия

Статья: [[Partitioning_Around_Medoids_(PAM)]]
Выполняют: [[Участник:Avasilenko|А.Э.Василенко]], [[Участник:Anastasia|А.В.Тузикова]]

Статья: [[Нечеткий алгоритм С-средних (Fuzzy C-means)]]
Выполняют: [[Участник:Nikmedoed|Н.А. Муромцев]], [[Участник:illusive_mike|М.С. Дворецкий]]

Статья: [[Нечеткий алгоритм C средних]]
Выполняют: [[Участник:Gkhazeeva|Гелана Хазеева]], [[Участник:Yushin|Павел Юшин]]

Статья: [[Плотностный алгоритм кластеризации DBSCAN]]
Выполняют: [[Участник:Elena777mc|Малахова Е.С.]], [[Участник:Жаннат_Сагиолданова|Сагиолданова Ж.]]

Статья: [[Кластеризация Partitioning Around Medoids (PAM)]]
Выполняют:[[ Участник:Тодуа Антон| Тодуа Антон]], [[Участник:Гусева Юлия| Гусева Юлия]]

Статья: [[Участник:Бугаков Юрий (613 группа), Кужамалиев Ернур (601 группа)/Построение матрицы Адамара произвольной размерности]]
Выполняют:[[ Участник:Бугаков Юрий| Бугаков Юрий]], [[Участник:Кужамалиев Ернур| Кужамалиев Ернур]]

Статья: [[Участник:Nikita/Построение_матрицы_Адамара|Построение матрицы Адамара]]
Выполняют: [[Участник:Nikita|Иванов Никита]], [[Участник:Tsyganov Nikita|Цыганов Никита]]

Статья: [[Метод Ньютона для решения систем нелинейных уравнений]]
Выполняют: [[Участник:Александр Чернышев|Александр Чернышев]], [[Участник:Захаров Никита|Захаров Никита]]

Статья: [[BIRCH|Сбалансированный итеративный алгоритм редукции и кластеризации с использованием иерархий
(BIRCH)]]
Выполняют: [[Участник:Светлана Морозова|Морозова Светлана]], [[Участник:Smirnov.maxim|Смирнов Максим]]

Статья: [[Плотностный_алгоритм_кластеризации|Плотностный_алгоритм_кластеризации]], Выполняют: [[Участник:Ramon93i7|Шемякин Роман]], [[Участник:Dadrik|Вашуров Илья]]

Статья: [[Алгоритм CLOPE кластеризации категориальных данных]].
Выполняют: [[Участник:Артем_Карпухин|Карпухин Артем]], [[Участник:Артем_Желтков|Желтков Артем]].

Статья: [[Участник:Борис/Алгоритм_Рунге-Кутты]]
Выполняет: [[Участник:Борис| Савков Борис]] и Степанов Евгений.

Статья: [[Алгоритм_кластеризации_категориальных_данных_CLOPE]].
Выполняют: [[Участник:Андрей_Туманов|А.Л.Туманов]], [[Участник:Александр_Александров|А.В.Александров]].

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

2016-11-07T21:21:48Z

Андрей Туманов:

{{Assignment}}

Основные авторы описания: [[Участник:Андрей_Туманов|А.Л.Туманов]] ([[#Общее описание алгоритма|1.1]], [[#Математическое описание алгоритма|1.2]], [[#Вычислительное ядро алгоритма|1.3]], [[#Макроструктура алгоритма|1.4]], [[#Схема реализации последовательного алгоритма|1.5]], [[#Входные и выходные данные алгоритма|1.9]]), [[Участник:Александр_Александров|А.В.Александров]] ([[#Последовательная сложность алгоритма|1.6]], [[#Информационный граф|1.7]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Свойства алгоритма|1.10]] [[#Существующие реализации алгоритма|2.7]])

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE<ref>Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.</ref>) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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> имеет следующие характеристики:
[[Файл:ExampleCLOPE.jpg|500px|thumb|right]]
<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> <ref>Нейский И.М. Классификация и сравнение методов кластеризации.</ref>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным. <ref>Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope</ref>

'''Схема реализации на псевдокоде:'''

Входные параметры:

* <math>t</math> - транзакции

* <math>r</math> - коэффициент отталкивания

Выходной параметр:

* <math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

=== Информационный граф ===
На этапе инициализации при обработке каждой транзакции количество кластеров может как увеличиться, так и остаться неизменным. Это показано пунктирными линиями:
[[Файл:InitCLOPE.jpg|400px|center|Инициализация]]
На этапе итерации функции DeltaAdd/DeltaRemove могут считать параллельно для каждой транзакции
[[Файл:IterCLOPE.jpg ‎|400px|center|Итерации]]

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

Вычисление стоимости добавления/удаления транзакции, которые выполняются функциями DeltaAdd/DeltaRemove, происходит независимо для всех <math>k</math> кластеров. Поэтому все вычисления можно производить параллельно. Таким образом сложность алгоритма с <math>O(n*k*m)</math> понижается до <math>O(n*m)</math>.

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

'''Входные данные:'''

<math>n</math> транзакций длины <math>m</math> и коэффициент отталкивания <math>r</math>

'''Выходные данные:'''

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины <math>n</math>)

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

* Соотношение последовательной и параллельной сложности алгоритма определяется количеством кластеров: <math>\dfrac{O(n*k*m)}{O(n*m)} = k</math>
* [[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна <math>\dfrac{nk(m+8) + m + 2}{nm + n + 1} \cong k</math>
* Алгоритм не является [[глоссарий#Устойчивость|''устойчивым'']], так как результат работы зависит от порядка чтения транзакций и от текущего набора транзакций в кластере.
* Выполняется свойство сбалансированности операций между параллельными ветвями алгоритма, так как для каждой транзакции выполняются функции DeltaAdd/DeltaRemove, считающие стоимость добавления/удаления транзакции.
* Свойство [[глоссарий#Детерминированность|''детерминированности алгоритмов'']] не выполняется, так как результат алгоритма зависит от порядка прохождения транзакций. Но если рассматривать транзакции как нумерованный список, то результат будет определен однозначно от запуска к запуску. Однако существует расширение алгоритма, обеспечивающее свойство детерминированности. <ref>Li, Y., Le, J., Wang, M. Improving CLOPE’s Profit Value and Stability with an Optimized Agglomerative Approach. Algorithms 2015, 8, 380-394.</ref>.
* Так как алгоритм предназначен для кластеризации категориальных данных, то он практически неприменим для числовой кластеризации.
* Быстро работает даже для большого количества данных, обеспечивая при этом хорошее качество кластеризации
* Имеет простую реализацию

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

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

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

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

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

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

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

=== Существующие реализации алгоритма ===
* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java
Также существуют пользовательские реализации алгоритма:
* https://github.com/infozor/php_mysql_clustering_clope - реализация алгоритма на PHP
* https://github.com/Tolsi/scala-clope - реализация алгоритма Scala

= Литература =

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

2016-11-07T20:55:25Z

Андрей Туманов:

Основные авторы описания: [[Участник:Андрей_Туманов|А.Л.Туманов]] ([[#Общее описание алгоритма|1.1]], [[#Математическое описание алгоритма|1.2]], [[#Вычислительное ядро алгоритма|1.3]], [[#Макроструктура алгоритма|1.4]], [[#Схема реализации последовательного алгоритма|1.5]], [[#Входные и выходные данные алгоритма|1.9]]), [[Участник:Александр_Александров|А.В.Александров]] ([[#Последовательная сложность алгоритма|1.6]], [[#Информационный граф|1.7]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Свойства алгоритма|1.10]] [[#Существующие реализации алгоритма|2.7]])

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE<ref>Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.</ref>) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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> имеет следующие характеристики:
[[Файл:ExampleCLOPE.jpg|500px|thumb|right]]
<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> <ref>Нейский И.М. Классификация и сравнение методов кластеризации.</ref>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным. <ref>Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope</ref>

'''Схема реализации на псевдокоде:'''

Входные параметры:

* <math>t</math> - транзакции

* <math>r</math> - коэффициент отталкивания

Выходной параметр:

* <math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

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

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

Вычисление стоимости добавления/удаления транзакции, которые выполняются функциями DeltaAdd/DeltaRemove, происходит независимо для всех <math>k</math> кластеров. Поэтому все вычисления можно производить параллельно. Таким образом сложность алгоритма с <math>O(n*k*m)</math> понижается до <math>O(n*m)</math>.

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

'''Входные данные:'''

<math>n</math> транзакций длины <math>m</math> и коэффициент отталкивания <math>r</math>

'''Выходные данные:'''

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины <math>n</math>)

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

* Соотношение последовательной и параллельной сложности алгоритма определяется количеством кластеров: <math>\dfrac{O(n*k*m)}{O(n*m)} = k</math>
* [[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна <math>\dfrac{nk(m+8) + m + 2}{nm + n + 1} \cong k</math>
* Алгоритм не является [[глоссарий#Устойчивость|''устойчивым'']], так как результат работы зависит от порядка чтения транзакций и от текущего набора транзакций в кластере.
* Выполняется свойство сбалансированности операций между параллельными ветвями алгоритма, так как для каждой транзакции выполняются функции DeltaAdd/DeltaRemove, считающие стоимость добавления/удаления транзакции.
* Свойство [[глоссарий#Детерминированность|''детерминированности алгоритмов'']] не выполняется, так как результат алгоритма зависит от порядка прохождения транзакций. Но если рассматривать транзакции как нумерованный список, то результат будет определен однозначно от запуска к запуску. Однако существует расширение алгоритма, обеспечивающее свойство детерминированности. <ref>Li, Y., Le, J., Wang, M. Improving CLOPE’s Profit Value and Stability with an Optimized Agglomerative Approach. Algorithms 2015, 8, 380-394.</ref>.

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

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

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

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

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

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

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

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

* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java

= Литература =

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

2016-11-07T20:47:14Z

Андрей Туманов: /* Литература */

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE<ref>Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.</ref>) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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> имеет следующие характеристики:
[[Файл:ExampleCLOPE.jpg|500px|thumb|right]]
<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> <ref>Нейский И.М. Классификация и сравнение методов кластеризации.</ref>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным. <ref>Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope</ref>

'''Схема реализации на псевдокоде:'''

Входные параметры:

* <math>t</math> - транзакции

* <math>r</math> - коэффициент отталкивания

Выходной параметр:

* <math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

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

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

Вычисление стоимости добавления/удаления транзакции, которые выполняются функциями DeltaAdd/DeltaRemove, происходит независимо для всех <math>k</math> кластеров. Поэтому все вычисления можно производить параллельно. Таким образом сложность алгоритма с <math>O(n*k*m)</math> понижается до <math>O(n*m)</math>.

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

'''Входные данные:'''

<math>n</math> транзакций длины <math>m</math> и коэффициент отталкивания <math>r</math>

'''Выходные данные:'''

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины <math>n</math>)

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

* Соотношение последовательной и параллельной сложности алгоритма определяется количеством кластеров: <math>\dfrac{O(n*k*m)}{O(n*m)} = k</math>
* [[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна <math>\dfrac{nk(m+8) + m + 2}{nm + n + 1} \cong k</math>
* Алгоритм не является [[глоссарий#Устойчивость|''устойчивым'']], так как результат работы зависит от порядка чтения транзакций и от текущего набора транзакций в кластере.
* Выполняется свойство сбалансированности операций между параллельными ветвями алгоритма, так как для каждой транзакции выполняются функции DeltaAdd/DeltaRemove, считающие стоимость добавления/удаления транзакции.
* Свойство [[глоссарий#Детерминированность|''детерминированности алгоритмов'']] не выполняется, так как результат алгоритма зависит от порядка прохождения транзакций. Но если рассматривать транзакции как нумерованный список, то результат будет определен однозначно от запуска к запуску. Однако существует расширение алгоритма, обеспечивающее свойство детерминированности. <ref>Li, Y., Le, J., Wang, M. Improving CLOPE’s Profit Value and Stability with an Optimized Agglomerative Approach. Algorithms 2015, 8, 380-394.</ref>.

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

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

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

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

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

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

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

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

* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java

= Литература =

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

2016-11-07T20:47:02Z

Андрей Туманов: /* Схема реализации последовательного алгоритма */

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

2016-11-07T20:46:11Z

Андрей Туманов: /* Математическое описание алгоритма */

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE<ref>Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.</ref>) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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> имеет следующие характеристики:
[[Файл:ExampleCLOPE.jpg|500px|thumb|right]]
<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> <ref>Нейский И.М. Классификация и сравнение методов кластеризации.</ref>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным.

'''Схема реализации на псевдокоде:'''

Входные параметры:

* <math>t</math> - транзакции

* <math>r</math> - коэффициент отталкивания

Выходной параметр:

* <math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

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

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

Вычисление стоимости добавления/удаления транзакции, которые выполняются функциями DeltaAdd/DeltaRemove, происходит независимо для всех <math>k</math> кластеров. Поэтому все вычисления можно производить параллельно. Таким образом сложность алгоритма с <math>O(n*k*m)</math> понижается до <math>O(n*m)</math>.

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

'''Входные данные:'''

<math>n</math> транзакций длины <math>m</math> и коэффициент отталкивания <math>r</math>

'''Выходные данные:'''

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины <math>n</math>)

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

* Соотношение последовательной и параллельной сложности алгоритма определяется количеством кластеров: <math>\dfrac{O(n*k*m)}{O(n*m)} = k</math>
* [[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна <math>\dfrac{nk(m+8) + m + 2}{nm + n + 1} \cong k</math>
* Алгоритм не является [[глоссарий#Устойчивость|''устойчивым'']], так как результат работы зависит от порядка чтения транзакций и от текущего набора транзакций в кластере.
* Выполняется свойство сбалансированности операций между параллельными ветвями алгоритма, так как для каждой транзакции выполняются функции DeltaAdd/DeltaRemove, считающие стоимость добавления/удаления транзакции.
* Свойство [[глоссарий#Детерминированность|''детерминированности алгоритмов'']] не выполняется, так как результат алгоритма зависит от порядка прохождения транзакций. Но если рассматривать транзакции как нумерованный список, то результат будет определен однозначно от запуска к запуску. Однако существует расширение алгоритма, обеспечивающее свойство детерминированности. <ref>Li, Y., Le, J., Wang, M. Improving CLOPE’s Profit Value and Stability with an Optimized Agglomerative Approach. Algorithms 2015, 8, 380-394.</ref>.

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

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

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

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

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

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

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

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

* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java

= Литература =
[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm

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

2016-11-01T21:16:15Z

Андрей Туманов: /* Ресурс параллелизма алгоритма */

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным.

'''Схема реализации на псевдокоде:'''

Входные параметры:

-<math>t</math> - транзакции

-<math>r</math> - коэффициент отталкивания

Выходной параметр:

-<math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

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

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

Вычисление стоимости добавления/удаления транзакции, которые выполняются функциями DeltaAdd/DeltaRemove, происходит независимо для всех <math>k</math> кластеров. Поэтому все вычисления можно производить параллельно. Таким образом сложность алгоритма с <math>O(n*k*m)</math> понижается до <math>O(n*m)</math>.

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

'''Входные данные:'''

<math>n</math> транзакций длины <math>m</math> и коэффициент отталкивания <math>r</math>

'''Выходные данные:'''

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины <math>n</math>)

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

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

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

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

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

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

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

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

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

* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java

= Литература =
[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm

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

2016-11-01T21:06:28Z

Андрей Туманов: /* Входные и выходные данные алгоритма */

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным.

'''Схема реализации на псевдокоде:'''

Входные параметры:

-<math>t</math> - транзакции

-<math>r</math> - коэффициент отталкивания

Выходной параметр:

-<math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

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

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

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

'''Входные данные:'''

<math>n</math> транзакций длины <math>m</math> и коэффициент отталкивания <math>r</math>

'''Выходные данные:'''

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины <math>n</math>)

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

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

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

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

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

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

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

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

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

* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java

= Литература =
[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm

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

2016-11-01T20:59:39Z

Андрей Туманов: /* Схема реализации последовательного алгоритма */

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным.

'''Схема реализации на псевдокоде:'''

Входные параметры:

-<math>t</math> - транзакции

-<math>r</math> - коэффициент отталкивания

Выходной параметр:

-<math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

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

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

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

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

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

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

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

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

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

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

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

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

* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java

= Литература =
[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm

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

2016-11-01T20:55:54Z

Андрей Туманов: /* Последовательная сложность алгоритма */

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным.

'''Схема реализации на псевдокоде:'''

Входные параметры:

-<math>t</math> - транзакции

-<math>r</math> - коэффициент отталкивания

Входной параметр:

-<math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

В соответствии с ранее введенным обозначением <math>n</math> - количество транзакций, <math>m</math> - длина транзакции(максимальная), <math>k</math> - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

Операции выполняются для всех транзаций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>n*k*(m+8)</math> операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна <math>O(n*k*m)</math>.

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

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

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

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

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

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

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

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

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

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

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

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

* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java

= Литература =
[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm

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

2016-10-30T22:09:03Z

Андрей Туманов: /* Существующие реализации алгоритма */

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным.

'''Схема реализации на псевдокоде:'''

Входные параметры:

-<math>t</math> - транзакции

-<math>r</math> - коэффициент отталкивания

Входной параметр:

-<math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

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

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

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

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

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

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

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

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

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

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

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

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

* http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java

= Литература =
[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm

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

2016-10-30T22:02:36Z

Андрей Туманов: /* Вычислительное ядро алгоритма */

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации стоимости добавления и удаления транзакции из кластера:

*вычисление нового размера кластера <math>S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid </math>, где <math>\mid(t_n)\mid</math> - длина транзакции

*вычисление новой ширины кластера <math>W_{new}(C_i)=\mid D(C_i \cup t_n)|</math>

*вычисление стоимости <math>\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}</math>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным.

'''Схема реализации на псевдокоде:'''

Входные параметры:

-<math>t</math> - транзакции

-<math>r</math> - коэффициент отталкивания

Входной параметр:

-<math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

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

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

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

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

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

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

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

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

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

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

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

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

= Литература =
[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm

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

2016-10-30T21:48:12Z

Андрей Туманов: /* Схема реализации последовательного алгоритма */

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

=== Общее описание алгоритма ===
Алгоритм CLOPE (Clustering with sLOPE) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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>.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит в вычислении на каждой итерации функции стоимости:

<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>

=== Макроструктура алгоритма ===
Алгоритм состоит из следующих этапов:

1. '''Инициализация'''. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. '''Итерация'''. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным.

'''Схема реализации на псевдокоде:'''

Входные параметры:

-<math>t</math> - транзакции

-<math>r</math> - коэффициент отталкивания

Входной параметр:

-<math>C</math> кластеры, в начале алгоритма - пустое множество

'''Инициализация:'''
'''for''' t_i in t:
max = 0
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) > max:
max = DeltaAdd(C_j,t_i,r)
C_best = C_j
'''put''' t_i in C_best

'''Итерации:'''
move = True
'''while''' move == True:
move = False
'''for''' t_i in t:
max = 0
C_now = t_i.cluster
removeCost = DeltaRemove(C_now,t_i,r)
'''for''' C_j in C:
'''if''' DeltaAdd(C_j,t_i,r) + removeCost > max:
max = DeltaAdd(C_j,t_i,r) + removeCost
C_best = C_j
if max > 0
'''del''' t_i from C_now
'''put''' t_i in C_best
move = True

Вспомогательная функция '''DeltaAdd''':
'''function''' DeltaAdd(C,t,r)
S_new=C.size + t.itemCount
W_new=C.wigth
'''for''' item in t_i:
'''if''' C_j.occ(item) = 0
''W_new = W_new + 1
'''return''' S_new * (C.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

Вспомогательная функция '''DeltaRemove''':
'''function''' DeltaRemove(C,t,r)
S_new=C.size - t.itemCount
W_new=C.wigth
'''for''' item in t:
'''if''' C_j.occ(item) = 1
''W_new = W_new - 1
'''return''' S_new * (C.count-1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

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

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

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

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

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

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

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

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

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

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

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

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

= Литература =
[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm

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

2016-10-30T21:26:21Z

Андрей Туманов: /* Схема реализации последовательного алгоритма */

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

2016-10-30T19:52:52Z

Андрей Туманов: /* Схема реализации последовательного алгоритма */

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

2016-10-30T18:36:14Z

Андрей Туманов: /* Макроструктура алгоритма */

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

2016-10-24T21:42:01Z

Андрей Туманов: /* Вычислительное ядро алгоритма */

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

2016-10-24T21:29:31Z

Андрей Туманов: /* Литература */

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

2016-10-24T21:28:41Z

Андрей Туманов: /* Общее описание алгоритма */

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

2016-10-24T21:14:06Z

Андрей Туманов: /* Литература */

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

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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>.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

= Литература =
[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

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

2016-10-24T20:34:20Z

Андрей Туманов: /* Математическое описание алгоритма */

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

2016-10-24T20:33:22Z

Андрей Туманов: /* Математическое описание алгоритма */

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

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

=== Математическое описание алгоритма ===
Пусть имеется база транзакций <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>.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

= Литература =
[1]

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

2016-10-23T19:40:49Z

Андрей Туманов:

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

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

=== Математическое описание алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

= Литература =
[1]

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

2016-10-23T19:22:56Z

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

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

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

== Математическое описание алгоритма ==

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

= Литература =
[1]