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

Algoman в 11:10, 16 ноября 2016

2016-11-16T11:10:04Z

← Предыдущая версия		Версия от 11:10, 16 ноября 2016
Строка 1:		Строка 1:
	Авторы: Кириллов Валентин Владимирович: 1.1, 1.3, 1.4, 1.7, 1.9, 1.10, 2.7;		Авторы: Кириллов Валентин Владимирович: 1.1, 1.3, 1.4, 1.7, 1.9, 1.10, 2.7;
	Холопкин Степан Андреевич: 1.2, 1.5, 1.6, 1.7, 1.8, 1.10		Холопкин Степан Андреевич: 1.2, 1.5, 1.6, 1.7, 1.8, 1.10

	~~{{Assignment}}~~

	{{algorithm		{{algorithm

Kirillov в 18:15, 14 ноября 2016

2016-11-14T18:15:10Z

← Предыдущая версия		Версия от 18:15, 14 ноября 2016
Строка 1:		Строка 1:
	Авторы: Кириллов Валентин Владимирович: 1.1, 1.3, 1.4, 1.7, 1.9, 1.10, 2.7;		Авторы: Кириллов Валентин Владимирович: 1.1, 1.3, 1.4, 1.7, 1.9, 1.10, 2.7;
	Холопкин Степан Андреевич: 1.2, 1.5, 1.6, 1.7, 1.8, 1.10		Холопкин Степан Андреевич: 1.2, 1.5, 1.6, 1.7, 1.8, 1.10

			{{Assignment}}

	{{algorithm		{{algorithm

Steve в 00:33, 1 ноября 2016

2016-11-01T00:33:21Z

← Предыдущая версия		Версия от 00:33, 1 ноября 2016
Строка 197:		Строка 197:

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

			Приближенно оценить вычислительную мощность алгоритма можно как отношение числа операций к объему входных данных:

			<math>\frac{n^2+nm+nlog(n)+m^2log(m)}{n+m} = n + \frac{nlog(n)}{n+m} + \frac{m^2log(m)}{n+m} < n + log(n) + mlog(m)</math>

			что являет собой сумму линейной, логарифмической и произведения линейной и логарифмической функций.

Kirillov в 09:45, 29 октября 2016

2016-10-29T09:45:22Z

← Предыдущая версия		Версия от 09:45, 29 октября 2016
Строка 1:		Строка 1:
	Авторы: Кириллов Валентин Владимирович: 1.1, 1.3, 1.4, 1.7, 1.9, 1.10, 2.7;		Авторы: Кириллов Валентин Владимирович: 1.1, 1.3, 1.4, 1.7, 1.9, 1.10, 2.7;
	Холопкин Степан Андреевич: 1.2, 1.5, 1.6, 1.7, 1.8		Холопкин Степан Андреевич: 1.2, 1.5, 1.6, 1.7, 1.8, 1.10

	{{algorithm		{{algorithm

Kirillov в 09:44, 29 октября 2016

2016-10-29T09:44:56Z

← Предыдущая версия		Версия от 09:44, 29 октября 2016
Строка 14:		Строка 14:

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	Алгоритм CHAMELEON первые представлен в 1999 департаментом компьютерных наук и инженерии, университет Миннесоты, США. Авторы George Karypis, Eui-Hong (Sam) Han, Vipin Kumar.		Алгоритм CHAMELEON первые представлен в 1999 департаментом компьютерных наук и инженерии, университет Миннесоты, США. Авторы George Karypis, Eui-Hong (Sam) Han, Vipin Kumar<ref>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 </ref> <ref> ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ КАЧЕСТВА КЛАСТЕРИЗАЦИИ РАЗНООБРАЗНЫХ НАБОРОВ ДАННЫХ С ПОМОЩЬЮ МОДИФИЦИРОВАННОГО АЛГОРИТМА ХАМЕЛЕОН © Т. Б. Шатовская, А. А. Заремская </ref>.

	Кластеризация – процесс разбиения множества данных по некоторому признаку на такие группы, что в пределах одной группы данные максимально схожи по данному признаку, а в разных группах данные максимально различны. Иерархические алгоритмы кластеризации строят не одно разбиение множества данных на кластеры, а систему вложенных разбиений. CHAMELEON является агломеративным методом (снизу вверх), когда после первого разбиения на мелкие кластеры пары близлежащих кластеров итеративно объединяются в общий кластер. На первом этапе CHAMELEON использует алгоритм разделения графа для получения набора относительно малых кластеров. На втором этапе, для объединения кластеров, полученных на первом этапе, в настоящие кластеры, используется иерархическая агломеративная кластеризация. Таким образом, алгоритм, фактически, является гибридным, построенным комбинацией графо-ориентированных и классических иерархических методов.		Кластеризация – процесс разбиения множества данных по некоторому признаку на такие группы, что в пределах одной группы данные максимально схожи по данному признаку, а в разных группах данные максимально различны. Иерархические алгоритмы кластеризации строят не одно разбиение множества данных на кластеры, а систему вложенных разбиений. CHAMELEON является агломеративным методом (снизу вверх), когда после первого разбиения на мелкие кластеры пары близлежащих кластеров итеративно объединяются в общий кластер. На первом этапе CHAMELEON использует алгоритм разделения графа для получения набора относительно малых кластеров. На втором этапе, для объединения кластеров, полученных на первом этапе, в настоящие кластеры, используется иерархическая агломеративная кластеризация. Таким образом, алгоритм, фактически, является гибридным, построенным комбинацией графо-ориентированных и классических иерархических методов.
Строка 21:		Строка 21:
	[[Файл:Cham1.jpg ]][[Файл:Cham2.jpg ]][[Файл:Cham3.jpg ]]		[[Файл:Cham1.jpg ]][[Файл:Cham2.jpg ]][[Файл:Cham3.jpg ]]

	На рисунке изображены: объекты в пространстве – слева, граф по принципу 1-го ближайшего соседа – в середине, граф по принципу 3-х ближайших соседей – справа (~~CHAMELEON: A Hierarchical~~ Clustering Algorithm ~~Using~~ Dynamic Modeling).		На рисунке изображены: объекты в пространстве – слева, граф по принципу 1-го ближайшего соседа – в середине, граф по принципу 3-х ближайших соседей – справа <ref> International Journal of Computer Applications (0975 – 8887) Volume 79 – No8, October 2013 11 Parallel Algorithm for the Chameleon Clustering Algorithm using Dynamic Modeling </ref>.

	Далее, алгоритм разделяет полученный граф на множество сравнительно малых подграфов. Разделение происходит последовательно. На каждом шаге выбирается подграф, содержащий наибольшее число вершин. Этот граф разделяется на два подграфа, так, что разделитель ребер графа минимален и каждый из получаемых подграфов содержит не менее некоторого процента вершин исходного графа. Процесс разделения останавливается, когда наибольший подграф содержит меньше некоторого заданного числа вершин. Полученное множество связных графов считается множеством начальных кластеров, на котором требуется провести последовательное иерархическое объединение.		Далее, алгоритм разделяет полученный граф на множество сравнительно малых подграфов. Разделение происходит последовательно. На каждом шаге выбирается подграф, содержащий наибольшее число вершин. Этот граф разделяется на два подграфа, так, что разделитель ребер графа минимален и каждый из получаемых подграфов содержит не менее некоторого процента вершин исходного графа. Процесс разделения останавливается, когда наибольший подграф содержит меньше некоторого заданного числа вершин. Полученное множество связных графов считается множеством начальных кластеров, на котором требуется провести последовательное иерархическое объединение.
Строка 214:		Строка 214:

	== Существующие реализации алгоритма ==		== Существующие реализации алгоритма ==
	Существующая реализация алгоритма CHAMELEON есть в составе пакета CLUTO от авторов алгоритма. ~~Подробнее можно посмотреть по ссылке [4~~].		Существующая реализация алгоритма CHAMELEON есть в составе пакета CLUTO от авторов алгоритма <ref> [http://glaros.dtc.umn.edu/gkhome/views/cluto Data Clustering Software CLUTO - Software for Clustering High-Dimensional Datasets]. </ref>.

	= Литература =		= Литература =
	[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~~		<references \>

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

	~~[4] [http://glaros.dtc.umn.edu/gkhome/views/cluto Data Clustering Software CLUTO - Software for Clustering High-Dimensional Datasets]~~

Kirillov в 09:32, 29 октября 2016

2016-10-29T09:32:31Z

← Предыдущая версия		Версия от 09:32, 29 октября 2016
Строка 1:		Строка 1:
	Авторы: Кириллов Валентин Владимирович: 1.1, 1.3, 1.4, 1.7, 1.9, 1.10, 2.7		Авторы: Кириллов Валентин Владимирович: 1.1, 1.3, 1.4, 1.7, 1.9, 1.10, 2.7;
	Холопкин Степан Андреевич: 1.2, 1.5, 1.6, 1.7, 1.8		Холопкин Степан Андреевич: 1.2, 1.5, 1.6, 1.7, 1.8

Kirillov в 09:32, 29 октября 2016

2016-10-29T09:32:12Z

← Предыдущая версия		Версия от 09:32, 29 октября 2016
Строка 1:		Строка 1:
	Авторы: Кириллов Валентин Владимирович, Холопкин Степан Андреевич		Авторы: Кириллов Валентин Владимирович: 1.1, 1.3, 1.4, 1.7, 1.9, 1.10, 2.7
			Холопкин Степан Андреевич: 1.2, 1.5, 1.6, 1.7, 1.8

	{{algorithm		{{algorithm

Kirillov в 21:18, 28 октября 2016

2016-10-28T21:18:17Z

← Предыдущая версия		Версия от 21:18, 28 октября 2016
Строка 199:		Строка 199:

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

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

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

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

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

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

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

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

Algoman в 16:04, 26 октября 2016

2016-10-26T16:04:02Z

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

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

Kirillov в 19:35, 25 октября 2016

2016-10-25T19:35:58Z

← Предыдущая версия		Версия от 19:35, 25 октября 2016
Строка 20:		Строка 20:

	На первом этапе, согласно графо-ориентированному подходу, происходит построение графа на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары.		На первом этапе, согласно графо-ориентированному подходу, происходит построение графа на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары.
	[[Файл:Cham1.jpg]][[Файл:Cham2.jpg]][[Файл:Cham3.jpg]]		[[Файл:Cham1.jpg ]][[Файл:Cham2.jpg ]][[Файл:Cham3.jpg ]]

	На рисунке изображены: объекты в пространстве – слева, граф по принципу 1-го ближайшего соседа – в середине, граф по принципу 3-х ближайших соседей – справа.		На рисунке изображены: объекты в пространстве – слева, граф по принципу 1-го ближайшего соседа – в середине, граф по принципу 3-х ближайших соседей – справа (CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling).

	Далее, алгоритм разделяет полученный граф на множество сравнительно малых подграфов. Разделение происходит последовательно. На каждом шаге выбирается подграф, содержащий наибольшее число вершин. Этот граф разделяется на два подграфа, так, что разделитель ребер графа минимален и каждый из получаемых подграфов содержит не менее некоторого процента вершин исходного графа. Процесс разделения останавливается, когда наибольший подграф содержит меньше некоторого заданного числа вершин. Полученное множество связных графов считается множеством начальных кластеров, на котором требуется провести последовательное иерархическое объединение.		Далее, алгоритм разделяет полученный граф на множество сравнительно малых подграфов. Разделение происходит последовательно. На каждом шаге выбирается подграф, содержащий наибольшее число вершин. Этот граф разделяется на два подграфа, так, что разделитель ребер графа минимален и каждый из получаемых подграфов содержит не менее некоторого процента вершин исходного графа. Процесс разделения останавливается, когда наибольший подграф содержит меньше некоторого заданного числа вершин. Полученное множество связных графов считается множеством начальных кластеров, на котором требуется провести последовательное иерархическое объединение.
Строка 30:		Строка 30:
	Относительная взаимная связность пары кластеров определяется абсолютной взаимной связностью кластеров, нормализованной с учетом внутренней связности каждого кластера (подграфа). Нормализация используется для того, чтобы исключить тенденцию к преимущественному объединению крупных кластеров, у которых, определенно, значение взаимной связности будет больше, вследствие их размера.		Относительная взаимная связность пары кластеров определяется абсолютной взаимной связностью кластеров, нормализованной с учетом внутренней связности каждого кластера (подграфа). Нормализация используется для того, чтобы исключить тенденцию к преимущественному объединению крупных кластеров, у которых, определенно, значение взаимной связности будет больше, вследствие их размера.

	[[Файл:Scheme_algo.jpg]]		[[Файл:Scheme_algo.jpg \| thumb \| center \| 1000px \| CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling]]

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