Участник:Kirillov\Графо-ориентированный алгоритм кластеризации CHAMELEON - История изменений

Kirillov в 20:23, 15 октября 2016

2016-10-15T20:23:39Z

← Предыдущая версия		Версия от 20:23, 15 октября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~

	Авторы: Кириллов Валентин Владимирович, Холопкин Степан Андреевич		Авторы: Кириллов Валентин Владимирович, Холопкин Степан Андреевич

Kirillov в 20:10, 15 октября 2016

2016-10-15T20:10:28Z

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

	Авторы: Кириллов Валентин Владимирович, Холопкин Степан Андреевич		Авторы: Кириллов Валентин Владимирович, Холопкин Степан Андреевич

Строка 4:		Строка 6:
	\| name = Графо-ориентированный алгоритм кластеризации CHAMELEON		\| name = Графо-ориентированный алгоритм кластеризации CHAMELEON
	\| serial_complexity = <math>O(n^2+nm+n log n + m^2 log(m))</math>		\| serial_complexity = <math>O(n^2+nm+n log n + m^2 log(m))</math>
	\| pf_height = <math>O(n)</math>		\| pf_height = <math>O(log(n))</math>
	\| pf_width = <math>O(n^2)</math>		\| pf_width = <math>O(n)</math>
	\| input_data = <math>n</math>		\| input_data = <math>n</math>
	\| output_data = <math>n</math>		\| output_data = <math>n</math>
	}}		}}



	= ЧАСТЬ. Свойства и структура алгоритмов =		= ЧАСТЬ. Свойства и структура алгоритмов =
Строка 186:		Строка 186:
	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	Как видно из графа алгоритма, операции слияния, находящиеся на одной итерации-плоскости главного цикла, не зависят друг от друга, и, следовательно, могут быть выполнены параллельно. Исходя из этого, предлагается следующая схема выполнения параллельного выполнения: каждая операция слияния на одной итерации главного цикла вызывается асинхронно, а в конце одной итерации главного цикла происходит ожидание окончания работы всех операций и подготовка к следующей итерации.		Как видно из графа алгоритма, операции слияния, находящиеся на одной итерации-плоскости главного цикла, не зависят друг от друга, и, следовательно, могут быть выполнены параллельно. Исходя из этого, предлагается следующая схема выполнения параллельного выполнения: каждая операция слияния на одной итерации главного цикла вызывается асинхронно, а в конце одной итерации главного цикла происходит ожидание окончания работы всех операций и подготовка к следующей итерации.

			Стоит заметить, что создание числа параллельных потоков, равного текущему количеству кластеров, вряд ли можно считать реальной задачей. Поэтому будем считать, что каждый параллельный поток вычисляет ровно один столбец матрицы-плоскости информационного графа, что означает, что параллельная сложность выполнения одной итерации алгоритма равна <math>O(n)</math>. Высота полученного графа (то есть, число позиций по вертикальной оси) будет равна <math>O(log(n))</math>, так как на каждом шаге цикла число кластеров уменьшается в среднем в 2 раза.

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

Kirillov в 20:04, 15 октября 2016

2016-10-15T20:04:54Z

← Предыдущая версия		Версия от 20:04, 15 октября 2016
Строка 1:		Строка 1:
			Авторы: Кириллов Валентин Владимирович, Холопкин Степан Андреевич

			{{algorithm
			\| name = Графо-ориентированный алгоритм кластеризации CHAMELEON
			\| serial_complexity = <math>O(n^2+nm+n log n + m^2 log(m))</math>
			\| pf_height = <math>O(n)</math>
			\| pf_width = <math>O(n^2)</math>
			\| input_data = <math>n</math>
			\| output_data = <math>n</math>
			}}



	= ЧАСТЬ. Свойства и структура алгоритмов =		= ЧАСТЬ. Свойства и структура алгоритмов =

Строка 18:		Строка 31:

	[[Файл:Scheme_algo.jpg]]		[[Файл:Scheme_algo.jpg]]

			На рисунке представлена схема работы алгоритма CHAMELEON.

	== Математическое описание алгоритма ==		== Математическое описание алгоритма ==
Строка 52:		Строка 67:
	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==
	Из математического описания алгоритма следует, что вычислительное ядро алгоритма сосредоточено в вычислении относительной взаимной связности и относительного взаимного сходства каждой пары кластеров на каждой итерации алгоритма.		Из математического описания алгоритма следует, что вычислительное ядро алгоритма сосредоточено в вычислении относительной взаимной связности и относительного взаимного сходства каждой пары кластеров на каждой итерации алгоритма.

			<math>RI(C_i, C_j) = \frac{\|EC(C_i,C_j)\|}{\frac{\|EC(C_i)\| + \|EC(C_j)\|}{2}}</math>

			<math>RC(C_i, C_j) = \frac{\bar{S}_{EC(C_i,C_j)}}{\frac{\|C_i\|}{\|C_i\|+\|C_j\|}\bar{S}_{EC(C_i)} + \frac{\|C_j\|}{\|C_i\|+\|C_j\|}\bar{S}_{EC(C_j)}}</math>

	== Макроструктура алгоритма ==		== Макроструктура алгоритма ==
Строка 159:		Строка 178:

	== Информационный граф ==		== Информационный граф ==
			Покажем информационный граф основной части алгоритма. Он представляет собой трехмерный набор точек-итераций главного цикла. Плоскость <math>(i,j)</math> являет собой последовательную проверку на слияние пары кластеров с номерами <math>i</math> и <math>j</math>. Ось <math>h</math> являет собой номер текущего набора кластеров, иначе говоря – номер итерации главного цикла. Операции слияния обозначены кружком с буквой “m” внутри.

			[[Файл:Scheme4.jpg]]

			Из графа алгоритма видно, что переходить к следующей итерации главного цикла можно лишь тогда, когда будет завершена предыдущая (дуги-зависимости идут от операций слияния строго вверх).

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

	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==
			Входные данные: массив <math>n</math> точек произвольной размерности.

			Выходные данные: <math>n</math> чисел <math>q_1, q_2, ..., q_n</math>, где <math>q_i</math> - целое число, соответствующее кластеру <math>i</math>-й точки.

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

			Детерминированность: Важной особенностью данного алгоритма является его недетерминированность. Несмотря на то, что первая часть первого этапа детерминирована, остальные две части выполняются итеративно и останавливаются по достижении заданной точности.


	= ЧАСТЬ. Программная реализация алгоритма =		= ЧАСТЬ. Программная реализация алгоритма =

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


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


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


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


	== ~~Динамические характеристики и эффективность~~ реализации алгоритма ==		== Существующие реализации алгоритма ==
			Существующая реализация алгоритма CHAMELEON есть в составе пакета CLUTO от авторов алгоритма. Подробнее можно посмотреть по ссылке [4].

			= Литература =
			[1] CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling George Karypis Eui-Hong (Sam) Han Vipin Kumar Department of Computer Science and Engineering University of Minnesota 4-192 EECS Bldg., 200 Union St. SE Minneapolis, MN 55455, USA Technical Report #99–007 {karypis,han,kumar}@cs.umn.edu

	~~== Выводы для классов архитектур ==~~		[2] International Journal of Computer Applications (0975 – 8887) Volume 79 – No8, October 2013 11 Parallel Algorithm for the Chameleon Clustering Algorithm using Dynamic Modeling

			[3] ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ КАЧЕСТВА КЛАСТЕРИЗАЦИИ РАЗНООБРАЗНЫХ НАБОРОВ ДАННЫХ С ПОМОЩЬЮ МОДИФИЦИРОВАННОГО АЛГОРИТМА ХАМЕЛЕОН © Т. Б. Шатовская, А. А. Заремская

	~~== Существующие реализации алгоритма ==~~		[4] [http://glaros.dtc.umn.edu/gkhome/views/cluto Data Clustering Software CLUTO - Software for Clustering High-Dimensional Datasets]

Kirillov в 19:21, 15 октября 2016

2016-10-15T19:21:02Z

Внесённые изменения

Kirillov в 18:05, 15 октября 2016

2016-10-15T18:05:08Z

← Предыдущая версия		Версия от 18:05, 15 октября 2016
Строка 2:		Строка 2:

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	~~Впервые~~ представлен George Karypis, Eui-Hong (Sam) Han, Vipin Kumar ~~в 1999 департамент компьютерных наук и инженерии, университет Миннесоты, США~~.		Алгоритм CHAMELEON первые представлен в 1999 департаментом компьютерных наук и инженерии, университет Миннесоты, США. Авторы George Karypis, Eui-Hong (Sam) Han, Vipin Kumar.
	Кластеризация – процесс разбиения множества данных по некоторому признаку на такие группы, что в пределах одной группы данные максимально схожи по данному признаку, а в разных группах данные максимально различны. Иерархические алгоритмы кластеризации строят не одно разбиение множества данных на кластеры, а систему вложенных разбиений. CHAMELEON является агломеративным методом (снизу вверх), когда после первого разбиения на мелкие кластеры пары близлежащих кластеров итеративно объединяются в общий кластер. На первом этапе CHAMELEON использует алгоритм разделения графа для получения набора относительно малых кластеров. На втором этапе, для объединения кластеров, полученных на первом этапе, в настоящие кластеры, используется иерархическая агломеративная кластеризация. Таким образом, алгоритм, фактически, является гибридным, построенным комбинацией графо-ориентированных и классических иерархических методов.		Кластеризация – процесс разбиения множества данных по некоторому признаку на такие группы, что в пределах одной группы данные максимально схожи по данному признаку, а в разных группах данные максимально различны. Иерархические алгоритмы кластеризации строят не одно разбиение множества данных на кластеры, а систему вложенных разбиений. CHAMELEON является агломеративным методом (снизу вверх), когда после первого разбиения на мелкие кластеры пары близлежащих кластеров итеративно объединяются в общий кластер. На первом этапе CHAMELEON использует алгоритм разделения графа для получения набора относительно малых кластеров. На втором этапе, для объединения кластеров, полученных на первом этапе, в настоящие кластеры, используется иерархическая агломеративная кластеризация. Таким образом, алгоритм, фактически, является гибридным, построенным комбинацией графо-ориентированных и классических иерархических методов.
	На первом этапе, согласно графо-ориентированному подходу, происходит построение графа на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары.		На первом этапе, согласно графо-ориентированному подходу, происходит построение графа на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары.

Kirillov в 18:03, 15 октября 2016

2016-10-15T18:03:14Z

← Предыдущая версия		Версия от 18:03, 15 октября 2016
Строка 2:		Строка 2:

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
			Впервые представлен George Karypis, Eui-Hong (Sam) Han, Vipin Kumar в 1999 департамент компьютерных наук и инженерии, университет Миннесоты, США.
			Кластеризация – процесс разбиения множества данных по некоторому признаку на такие группы, что в пределах одной группы данные максимально схожи по данному признаку, а в разных группах данные максимально различны. Иерархические алгоритмы кластеризации строят не одно разбиение множества данных на кластеры, а систему вложенных разбиений. CHAMELEON является агломеративным методом (снизу вверх), когда после первого разбиения на мелкие кластеры пары близлежащих кластеров итеративно объединяются в общий кластер. На первом этапе CHAMELEON использует алгоритм разделения графа для получения набора относительно малых кластеров. На втором этапе, для объединения кластеров, полученных на первом этапе, в настоящие кластеры, используется иерархическая агломеративная кластеризация. Таким образом, алгоритм, фактически, является гибридным, построенным комбинацией графо-ориентированных и классических иерархических методов.
			На первом этапе, согласно графо-ориентированному подходу, происходит построение графа на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары.

Kirillov: Kirillov переименовал страницу Участник:Kirillov в Участник:Kirillov\Графо-ориентированный алгоритм кластеризации CHAMELEON

2016-10-13T21:52:29Z

Kirillov переименовал страницу Участник:Kirillov в Участник:Kirillov\Графо-ориентированный алгоритм кластеризации CHAMELEON

← Предыдущая версия	Версия от 21:52, 13 октября 2016
(нет различий)

Kirillov: Новая страница: «= ЧАСТЬ. Свойства и структура алгоритмов = == Общее описание алгоритма == == Математическо…»

2016-10-13T20:30:12Z

Новая страница: «= ЧАСТЬ. Свойства и структура алгоритмов = == Общее описание алгоритма == == Математическо…»

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

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

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

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

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

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

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

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

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

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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