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

ASA в 13:09, 3 февраля 2017

2017-02-03T13:09:42Z

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

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

Андрей Туманов в 07:24, 21 декабря 2016

2016-12-21T07:24:17Z

← Предыдущая версия		Версия от 07:24, 21 декабря 2016
Строка 1:		Строка 1:

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

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

2016-12-20T23:45:11Z

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

← Предыдущая версия		Версия от 23:45, 20 декабря 2016
Строка 171:		Строка 171:

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

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

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

2016-12-20T22:08:09Z

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

← Предыдущая версия		Версия от 22:08, 20 декабря 2016
Строка 133:		Строка 133:
	=== Информационный граф ===		=== Информационный граф ===
	На этапе инициализации при обработке каждой транзакции количество кластеров может как увеличиться, так и остаться неизменным. Это показано пунктирными линиями:		На этапе инициализации при обработке каждой транзакции количество кластеров может как увеличиться, так и остаться неизменным. Это показано пунктирными линиями:
	[[Файл:~~InitCLOPE~~.~~jpg~~\|~~400px~~\|center\|Инициализация]]		[[Файл:init_clope.png\|600px\|center\|Инициализация]]
	На этапе итерации функции DeltaAdd/DeltaRemove могут считать параллельно для каждой транзакции		На этапе итерации функции DeltaAdd/DeltaRemove могут считать параллельно для каждой транзакции
	[[Файл:~~IterCLOPE~~.~~jpg~~ ‎\|~~400px~~\|center\|Итерации]]		[[Файл:iter_clope.png ‎\|600px\|center\|Итерации]]

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

ASA в 08:36, 9 ноября 2016

2016-11-09T08:36:52Z

← Предыдущая версия		Версия от 08:36, 9 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~

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

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

2016-11-09T00:06:10Z

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

← Предыдущая версия	Версия от 00:06, 9 ноября 2016
(нет различий)

Lineprinter в 00:05, 9 ноября 2016

2016-11-09T00:05:48Z

← Предыдущая версия		Версия от 00:05, 9 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment}}

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

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

Андрей Туманов в 21:21, 7 ноября 2016

2016-11-07T21:21:48Z

← Предыдущая версия		Версия от 21:21, 7 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}

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

Boltonidze: /* Свойства алгоритма */

2016-11-07T21:18:22Z

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

← Предыдущая версия		Версия от 21:18, 7 ноября 2016
Строка 158:		Строка 158:
	* Выполняется свойство сбалансированности операций между параллельными ветвями алгоритма, так как для каждой транзакции выполняются функции DeltaAdd/DeltaRemove, считающие стоимость добавления/удаления транзакции.		* Выполняется свойство сбалансированности операций между параллельными ветвями алгоритма, так как для каждой транзакции выполняются функции 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>.		* Свойство [[глоссарий#Детерминированность\|''детерминированности алгоритмов'']] не выполняется, так как результат алгоритма зависит от порядка прохождения транзакций. Но если рассматривать транзакции как нумерованный список, то результат будет определен однозначно от запуска к запуску. Однако существует расширение алгоритма, обеспечивающее свойство детерминированности. <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>.
			* Так как алгоритм предназначен для кластеризации категориальных данных, то он практически неприменим для числовой кластеризации.
			* Быстро работает даже для большого количества данных, обеспечивая при этом хорошее качество кластеризации
			* Имеет простую реализацию

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

Boltonidze: /* Существующие реализации алгоритма */

2016-11-07T21:14:01Z

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

← Предыдущая версия		Версия от 21:14, 7 ноября 2016
Строка 174:		Строка 174:

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

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

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