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

Egorovatonya в 08:37, 6 февраля 2017

2017-02-06T08:37:21Z

← Предыдущая версия		Версия от 08:37, 6 февраля 2017
Строка 109:		Строка 109:
	Сложность алгоритма равна <math>O(nkm)</math>.		Сложность алгоритма равна <math>O(nkm)</math>.
	=== Информационный граф ===		=== Информационный граф ===

			На этапе итерации для любой транзакции функции стоимости удаления и добавления могут работать параллельно для каждого кластера.
			[[Файл:iter.png ‎\|600px\|center\|Итерации]]


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

Egorovatonya в 07:17, 6 февраля 2017

2017-02-06T07:17:14Z

← Предыдущая версия		Версия от 07:17, 6 февраля 2017
Строка 5:		Строка 5:

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
			[[Файл:clope.png\|500px\|thumb\|right\|Разбиение набора транзакций на два кластера.]]

	Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1,t_2,...,t_n\}</math>. При этом каждая транзакция - набор объектов <math>\{i_1,...,i_m\} </math>.		Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1,t_2,...,t_n\}</math>. При этом каждая транзакция - набор объектов <math>\{i_1,...,i_m\} </math>.

Egorovatonya в 01:45, 6 февраля 2017

2017-02-06T01:45:13Z

← Предыдущая версия		Версия от 01:45, 6 февраля 2017
Строка 128:		Строка 128:
	* Количество кластеров определяет отношение последовательной и параллельной сложности алгоритма : <math>\dfrac{O(nmk)}{O(n*m)} = k</math>		* Количество кластеров определяет отношение последовательной и параллельной сложности алгоритма : <math>\dfrac{O(nmk)}{O(n*m)} = k</math>
	* Быстро работает для большого количества категориальных данных, так как в оперативной памяти необходимо хранить небольшое количество информации по каждому кластеру и требуется минимальное число сканирований набора транзакций. <ref>Н. Паклин. «Кластеризация категорийных данных: масштабируемый алгоритм CLOPE». Электронное издание. http://www.basegroup.ru/clusterization/clope.htm </ref>		* Быстро работает для большого количества категориальных данных, так как в оперативной памяти необходимо хранить небольшое количество информации по каждому кластеру и требуется минимальное число сканирований набора транзакций. <ref>Н. Паклин. «Кластеризация категорийных данных: масштабируемый алгоритм CLOPE». Электронное издание. http://www.basegroup.ru/clusterization/clope.htm </ref>
			Вычислительная мощность операций алгоритма: <math>\frac{O(NkA)}{NA + N + 1} = O(k)</math>.
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==

Egorovatonya в 01:42, 6 февраля 2017

2017-02-06T01:42:28Z

← Предыдущая версия		Версия от 01:42, 6 февраля 2017
Строка 33:		Строка 33:

	Таким образом задача кластеризации алгоритмом CLOPE состоит в том, чтобы для заданных множества <math>D</math> и коэффициента отталкивания <math>r</math> найти такое разбиение <math>C</math>, для которого значение функции цены максимально.		Таким образом задача кластеризации алгоритмом CLOPE состоит в том, чтобы для заданных множества <math>D</math> и коэффициента отталкивания <math>r</math> найти такое разбиение <math>C</math>, для которого значение функции цены максимально.


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

	для заданных <math>D</math> и <math>r</math> найти разбиение <math>C</math> такое, что:		для заданных <math>D</math> и <math>r</math> найти разбиение <math>C</math> такое, что:
	<math>Profit(C) \longrightarrow max </math>.		<math>Profit(C) \longrightarrow max </math>.<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>

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
Строка 128:		Строка 127:
	Если множество транзакций представить в виде пронумерованного списка, то результат будет однозначным.		Если множество транзакций представить в виде пронумерованного списка, то результат будет однозначным.
	* Количество кластеров определяет отношение последовательной и параллельной сложности алгоритма : <math>\dfrac{O(nmk)}{O(n*m)} = k</math>		* Количество кластеров определяет отношение последовательной и параллельной сложности алгоритма : <math>\dfrac{O(nmk)}{O(n*m)} = k</math>
	* Быстро работает для большого количества данных		* Быстро работает для большого количества категориальных данных, так как в оперативной памяти необходимо хранить небольшое количество информации по каждому кластеру и требуется минимальное число сканирований набора транзакций. <ref>Н. Паклин. «Кластеризация категорийных данных: масштабируемый алгоритм CLOPE». Электронное издание. http://www.basegroup.ru/clusterization/clope.htm </ref>

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
Строка 153:		Строка 152:

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

	<references \>		<references \>

Egorovatonya в 01:09, 6 февраля 2017

2017-02-06T01:09:37Z

← Предыдущая версия		Версия от 01:09, 6 февраля 2017
Строка 61:		Строка 61:

	==== Описание реализации алгоритма на псевдокоде ====		==== Описание реализации алгоритма на псевдокоде ====
			Вход:
			<math>t</math> - транзакции,
			<math>r</math> - коэффициент отталкивания

			Выход:
			<math>C</math> - множество кластеров

			'''инициализация:'''
			'''while ''' не конец '''do'''
			'''read''' следующую транзакцию <math>t</math>
			определить существующий кластер или пустой <math>C_j</math>, который дает максимум функции стоимости <math>Profit</math>
			'''write''' транзакцию в кластер <math>C_j</math>
			'''end while'''

			'''итерация''':
			'''repeat'''
			в начало таблицы транзакций
			change = false
			'''while''' не конец таблицы '''do'''
			'''read''' следующую транзакцию <math>t_i</math> из таблицы
			sum_max = 0
			'''for''' для каждого кластера <math>C_j</math>
			вычислить сумму <math>Sum</math> стоимости удаления из кластера <math>C_i</math> и добавления транзакции к <math>C_j</math>(j<>i)
			'''if''' Sum > sum_max '''then'''
			sum_max = Sum
			запомнить номер кластера <math>l</math>
			'''end if'''
			'''end for'''
			'''if''' sum_max>0
			change = true
			'''write''' транзакцию <math>t_i</math> в кластер <math>C_l</math>, который максимизирует функцию цены
			'''end if'''
			'''end while'''
			'''until''' not change
			'''delete''' все пустые кластеры

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

Egorovatonya в 18:43, 5 февраля 2017

2017-02-05T18:43:34Z

← Предыдущая версия		Версия от 18:43, 5 февраля 2017
Строка 89:		Строка 89:

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

			* Алгоритм не устойчив, так как результат его работы зависит от порядка считывания транзакций и текущего набора кластеров.
			* Алгоритм не детерминирован , так как результат алгоритма зависит от порядка считывания транзакций.
			Если множество транзакций представить в виде пронумерованного списка, то результат будет однозначным.
			* Количество кластеров определяет отношение последовательной и параллельной сложности алгоритма : <math>\dfrac{O(nmk)}{O(n*m)} = k</math>
			* Быстро работает для большого количества данных

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

Egorovatonya: и

2017-02-05T16:32:19Z

← Предыдущая версия		Версия от 16:32, 5 февраля 2017
Строка 47:		Строка 47:
	*<math>W_{new}(C_i)=\mid D(C_i \cup t_n)\|</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>		*вычисление стоимости добавления(удаления)<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>

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

			<ol>
			<li>Инициализация. Последовательно для каждой транзакции считается цена добавления ко всем существующим или новому пустому кластерам. В результате, транзакция занимает место в том кластере, для которого цена добавления максимальна(если это пустой кластер, то необходимо его создать). В конечном итоге все транзакции будут находиться в кластерах.</li>
			<li>Итерации. Этот этап нужен для возможного улучшения результата, полученного на первом шаге. При этом для каждой транзакции вычисляется стоимость удаления из кластера, в котором она находится, и цена добавления в каждый существующий или пустой кластер. Необходимо посчитать и найти максимальную суммарную стоимость удаления и добавления транзакции к каждому кластеру. Если максимальная стоимость положительная, то данная транзакция перемещается в этот кластер. Это выполняется для каждой транзакции.
			Итерация повторяется до тех пор, пока результат улучшается. Как только за итерацию ничего не меняется, алгоритм заканчивает работу. </li>
			</ol>

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


	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===
			Пусть <math>n</math> - количество транзакций, <math>m</math> - максимальное количество объектов транзакции, <math>k</math> - количество кластеров.

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

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

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

			Сложность алгоритма равна <math>O(nkm)</math>.
	=== Информационный граф ===		=== Информационный граф ===

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

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

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

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

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

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

	=== Свойства алгоритма ===		=== Свойства алгоритма ===
Строка 82:		Строка 105:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
			Первое описание данного алгоритма появилось совсем недавно, этим можно объяснить небольшое количество его реализаций.
			* 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


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

	<references \>		<references \>

Egorovatonya в 18:55, 4 февраля 2017

2017-02-04T18:55:21Z

@@ Строка 1: / Строка 1: @@
 == Свойства и структура алгоритма ==
 === Общее описание алгоритма ===
 === Математическое описание алгоритма ===
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===
 === Схема реализации последовательного алгоритма ===
 ==== Описание реализации алгоритма на псевдокоде ====

Egorovatonya в 21:35, 31 января 2017

2017-01-31T21:35:54Z

← Предыдущая версия		Версия от 21:35, 31 января 2017
Строка 7:		Строка 7:
	\| output_data = <math>N</math>		\| output_data = <math>N</math>
	}}		}}

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

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

			=== Математическое описание алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

			<references \>

Egorovatonya: Новая страница: «{{algorithm | name = Алгоритм CLOPE | serial_complexity = $O(NkA)$ | pf_height = $O(N*A)$ | pf_width…»

2017-01-31T21:33:49Z

Новая страница: «{{algorithm | name = Алгоритм CLOPE | serial_complexity = <math>O(N*k*A)</math> | pf_height = <math>O(N*A)</math> | pf_width…»

Новая страница

{{algorithm
| name = Алгоритм CLOPE
| serial_complexity = <math>O(N*k*A)</math>
| pf_height = <math>O(N*A)</math>
| pf_width = <math>O(N*k*A)</math>
| input_data = <math>N*A + 1</math>
| output_data = <math>N</math>
}}