Участник:Ruslanlazovskiy/CHAMELEON - История изменений

Hromovalexander: Отмена правки 21740, сделанной участником Hromovalexander (обс.)

2017-01-25T12:19:57Z

Отмена правки 21740, сделанной участником Hromovalexander (обс.)

@@ Строка 147: / Строка 147: @@
 ===Возможные способы и особенности параллельной реализации алгоритма===
 ===Масштабируемость алгоритма и его реализации===
 ===Динамические характеристики и эффективность реализации алгоритма===
 ===Выводы для классов архитектур===
 ===Существующие реализации алгоритма===
 ==Литература==

Hromovalexander: /* Программная реализация алгоритма */

2017-01-25T12:19:25Z

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

@@ Строка 147: / Строка 147: @@
 ===Возможные способы и особенности параллельной реализации алгоритма===
 ===Масштабируемость алгоритма и его реализации===
 ===Динамические характеристики и эффективность реализации алгоритма===
 ===Выводы для классов архитектур===
 ===Существующие реализации алгоритма===
 ==Литература==

Kronberg в 14:29, 29 ноября 2016

2016-11-29T14:29:53Z

← Предыдущая версия		Версия от 14:29, 29 ноября 2016
Строка 1:		Строка 1:
	{{Assignment\|Algoman}}		{{Assignment\|Algoman\|Kronberg}}

	{{algorithm		{{algorithm

Ruslanlazovskiy в 10:10, 29 ноября 2016

2016-11-29T10:10:21Z

← Предыдущая версия		Версия от 10:10, 29 ноября 2016
Строка 11:		Строка 11:

	Авторы статьи:		Авторы статьи:
	[https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ruslanlazovskiy\|<b>Лазовский Р. А.</b>] (разделы 1.1 - 1.4 , 1.7 , 1.8),		[https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ruslanlazovskiy <b>Лазовский Р. А.</b>] (разделы 1.1 - 1.4 , 1.7 , 1.8),
	[https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%9C%D1%83%D1%81%D1%82%D0%B0%D1%84%D0%B0%D0%B5%D0%B2_%D0%AD%D0%BB%D1%8C%D0%B2%D0%B8%D0%BD_%D0%AD%D0%BB%D1%8C%D0%BC%D0%B0%D0%BD%D0%BE%D0%B2%D0%B8%D1%87 <b>Мустафаев Э. Э.</b>] (разделы 1.5 , 1.6 , 1.9 , 1.10 , 2.2)		[https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%9C%D1%83%D1%81%D1%82%D0%B0%D1%84%D0%B0%D0%B5%D0%B2_%D0%AD%D0%BB%D1%8C%D0%B2%D0%B8%D0%BD_%D0%AD%D0%BB%D1%8C%D0%BC%D0%B0%D0%BD%D0%BE%D0%B2%D0%B8%D1%87 <b>Мустафаев Э. Э.</b>] (разделы 1.5 , 1.6 , 1.9 , 1.10 , 2.2)

Ruslanlazovskiy в 10:10, 29 ноября 2016

2016-11-29T10:10:02Z

← Предыдущая версия		Версия от 10:10, 29 ноября 2016
Строка 12:		Строка 12:
	Авторы статьи:		Авторы статьи:
	[https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ruslanlazovskiy\|<b>Лазовский Р. А.</b>] (разделы 1.1 - 1.4 , 1.7 , 1.8),		[https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ruslanlazovskiy\|<b>Лазовский Р. А.</b>] (разделы 1.1 - 1.4 , 1.7 , 1.8),
	[https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%9C%D1%83%D1%81%D1%82%D0%B0%D1%84%D0%B0%D0%B5%D0%B2_%D0%AD%D0%BB%D1%8C%D0%B2%D0%B8%D0%BD_%D0%AD%D0%BB%D1%8C%D0%BC%D0%B0%D0%BD%D0%BE%D0%B2%D0%B8%D1%87\|<b>Мустафаев Э. Э.</b>] (разделы 1.5 , 1.6 , 1.9 , 1.10 , 2.2)		[https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%9C%D1%83%D1%81%D1%82%D0%B0%D1%84%D0%B0%D0%B5%D0%B2_%D0%AD%D0%BB%D1%8C%D0%B2%D0%B8%D0%BD_%D0%AD%D0%BB%D1%8C%D0%BC%D0%B0%D0%BD%D0%BE%D0%B2%D0%B8%D1%87 <b>Мустафаев Э. Э.</b>] (разделы 1.5 , 1.6 , 1.9 , 1.10 , 2.2)

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

Ruslanlazovskiy: /* Математическое описание алгоритма */

2016-11-28T15:16:00Z

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

← Предыдущая версия		Версия от 15:16, 28 ноября 2016
Строка 22:		Строка 22:
	===Математическое описание алгоритма===		===Математическое описание алгоритма===

	<b>Исходные данные:</b> Первоначально исходными данными алгоритма являются <math>n</math> векторов длины <math>p</math>, каждый из которых соответствует одному объекту. На основании значений элементов этих векторов строится матрица смежности размера <math>n * n</math> ( возможно сокращение требуемого объема памяти до <math>(n*(n - 1))/ 2</math> в соответствии с выбранной метрикой. К исходным данным также относится набор параметров. Это <math>k</math> - количество ближайших соседей на первом этапе алгоритма, <math>q</math> - отношение количества вершин в наибольшем подграфе по отношению к общему числу объектов на втором этапе алгоритма, а также параметры <math>T_{RI}, T_{RI}</math> - пороговые значения, после которых прекращается агломеративная кластеризация на третьем этапе. Следует особо отметить, что число получаемых в итоге кластеров заранее не известно, хотя на него и можно повлиять изменением значений перечисленных параметров.		<b>Исходные данные:</b> Первоначально исходными данными алгоритма являются <math>n</math> векторов длины <math>p</math>, каждый из которых соответствует одному объекту. На основании значений элементов этих векторов строится матрица смежности размера <math>n * n</math>, возможно сокращение требуемого объема памяти до <math>(n*(n - 1))/ 2</math> в соответствии с выбранной метрикой. К исходным данным также относится набор параметров. Это <math>k</math> - количество ближайших соседей на первом этапе алгоритма, <math>q</math> - отношение количества вершин в наибольшем подграфе по отношению к общему числу объектов на втором этапе алгоритма, а также параметры <math>T_{RI}, T_{RI}</math> - пороговые значения, после которых прекращается агломеративная кластеризация на третьем этапе. Следует особо отметить, что число получаемых в итоге кластеров заранее не известно, хотя на него и можно повлиять изменением значений перечисленных параметров.

	<b>Первый этап алгоритма:</b> На первом этапе на основании матрицы смежности строится граф <math>G = (V, E)</math> <math>k</math> ближайших соседей, где <math>V</math> - множество вершин графа (т.е. объекты), а <math>E</math> - множество ребер графа (т.е. построенные связи между ближайшими соседями). Указанный граф не обязательно является связным.		<b>Первый этап алгоритма:</b> На первом этапе на основании матрицы смежности строится граф <math>G = (V, E)</math> <math>k</math> ближайших соседей, где <math>V</math> - множество вершин графа (т.е. объекты), а <math>E</math> - множество ребер графа (т.е. построенные связи между ближайшими соседями). Указанный граф не обязательно является связным.

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

2016-11-28T15:13:52Z

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

← Предыдущая версия		Версия от 15:13, 28 ноября 2016
Строка 152:		Строка 152:
	В силу вышескасновного основное внимание будет уделено исследованию масштабируемости алгоритма по размеру задачи, в пределах одного узла. Далее приводятся графики производительности в Гфлопс для различных размеров задачи. Эффективность работы алгоритма убывает на всей рассматриваемой области. Темпы убывания эффективности снижаются с ростом размера задачи.		В силу вышескасновного основное внимание будет уделено исследованию масштабируемости алгоритма по размеру задачи, в пределах одного узла. Далее приводятся графики производительности в Гфлопс для различных размеров задачи. Эффективность работы алгоритма убывает на всей рассматриваемой области. Темпы убывания эффективности снижаются с ростом размера задачи.

	Для исследования такой масштабируемости вширь использовалась референсная последовательная реализация алгоритма (м. раздел "Существующие реализации"). Соответствующая программа запускалась на системе BG/P на одном вычислительном узле. Характеристики вычислительного узла, а также микропроцессорного ядра - элемента такого узла, приводятся в <ref>http://hpc.cmc.msu.ru/bgp</ref> Таким образом, удостоверенными экспериментальными данными являются только значения, полученные для случая 1 процесса. Значения для случаев 2 и 4 процессов являются ОЦЕНОЧНЫМИ и выводятся из результатов работы модифицированной версии алгоритма, исследуемой в <ref name = "exp">Parallel Algorithm for the Chameleon Clustering Algorithm using Dynamic Modeling. Rajnish Dashora, Harsh Bajaj, Akshat Dube, Geetha Mary .A. VIT University,Vellore. International Journal of Computer Applications (0975 – 8887) Volume 79 – No8, October 2013 </ref>. К сожалению, указанной реализации авторы не предоставляют.		Для исследования такой масштабируемости вширь использовалась референсная последовательная реализация алгоритма (cм. раздел "Существующие реализации"). Соответствующая программа запускалась на системе BG/P на одном вычислительном узле. Характеристики вычислительного узла, а также микропроцессорного ядра - элемента такого узла, приводятся в <ref>http://hpc.cmc.msu.ru/bgp</ref> Таким образом, удостоверенными экспериментальными данными являются только значения, полученные для случая 1 процесса. Значения для случаев 2 и 4 процессов являются ОЦЕНОЧНЫМИ и выводятся из результатов работы модифицированной версии алгоритма, исследуемой в <ref name = "exp">Parallel Algorithm for the Chameleon Clustering Algorithm using Dynamic Modeling. Rajnish Dashora, Harsh Bajaj, Akshat Dube, Geetha Mary .A. VIT University,Vellore. International Journal of Computer Applications (0975 – 8887) Volume 79 – No8, October 2013 </ref>. К сожалению, указанной реализации авторы не предоставляют.

Ruslanlazovskiy в 15:13, 28 ноября 2016

2016-11-28T15:13:28Z

Kronberg: /* Общее описание алгоритма */

2016-11-28T08:37:35Z

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

← Предыдущая версия		Версия от 08:37, 28 ноября 2016
Строка 16:		Строка 16:
	==Свойства и структура алгоритма==		==Свойства и структура алгоритма==
	===Общее описание алгоритма===		===Общее описание алгоритма===
	CHAMELEON – алгоритм динамической иерархической кластеризации графа, то есть процесса разбиения графа на несколько подграфов-кластеров таким образом, что данные внутри одного кластера имеют максимально схожи, а данные в разных кластерах — максимально различны. В классических алгоритмах кластеризации схожесть объектов определяется с помощью некоторой метрики (простейший пример - евклидова метрика). Не следует путать задачу кластеризации с задачей классификации - в последней характеристики объекта, необходимые для попадания в тот или иной класс, известны заранее, в рассматриваемой же задаче они становятся известны в процессе решения. Первоначально алгоритм был описан в статье<ref>CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling. George Karypis, Eui-Hong Han, Vipin Kumar. IEEE Computer 32(8): 68-75, 1999</ref>.		CHAMELEON – алгоритм динамической иерархической кластеризации графа, то есть процесса разбиения графа на несколько подграфов-кластеров таким образом, что данные внутри одного кластера имеют максимально схожи, а данные в разных кластерах — максимально различны. В классических алгоритмах кластеризации схожесть объектов определяется с помощью некоторой метрики (простейший пример — евклидова метрика). Не следует путать задачу кластеризации с задачей классификации: в последней характеристики объекта, необходимые для попадания в тот или иной класс, известны заранее, в рассматриваемой же задаче они становятся известны в процессе решения. Первоначально алгоритм был описан в статье<ref>CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling. George Karypis, Eui-Hong Han, Vipin Kumar. IEEE Computer 32(8): 68-75, 1999</ref>.

	Алгоритм CHAMELEON работает в 3 этапа. На первом этапе исходное множество объектов организуется в граф по принципу k ближайших соседей. На втором этапе этого граф разбивается на достаточно малые подграфы-кластеры. На третьем этапе происходит агломеративная иерархическая кластеризация полученных подграфов в соответствии с одной из выбранных метрик ( возможные метрики будут подробно описаны далее ). Число получаемых в итоге кластеров в явном виде не задаётся.		Алгоритм CHAMELEON работает в 3 этапа. На первом этапе исходное множество объектов организуется в граф по принципу k ближайших соседей. На втором этапе этого граф разбивается на достаточно малые подграфы-кластеры. На третьем этапе происходит агломеративная иерархическая кластеризация полученных подграфов в соответствии с одной из выбранных метрик (возможные метрики будут подробно описаны далее). Число получаемых в итоге кластеров в явном виде не задаётся.

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

Kronberg: /* Общее описание алгоритма */

2016-11-28T08:36:34Z

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

← Предыдущая версия		Версия от 08:36, 28 ноября 2016
Строка 16:		Строка 16:
	==Свойства и структура алгоритма==		==Свойства и структура алгоритма==
	===Общее описание алгоритма===		===Общее описание алгоритма===
	CHAMELEON – алгоритм динамической иерархической кластеризации графа, то есть процесса разбиения графа на несколько подграфов-кластеров таким образом, что данные внутри одного кластера имеют максимально схожи, а данные в разных кластерах — максимально различны. В классических алгоритмах кластеризации схожесть объектов определяется с помощью некоторой метрики ( простейший пример - евклидова метрика ). Не следует путать задачу кластеризации с задачей классификации - в последней характеристики объекта, необходимые для попадания в тот или иной класс, известны заранее, в рассматриваемой же задаче они становятся известны в процессе решения. Первоначально алгоритм был описан в статье<ref>CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling. George Karypis, Eui-Hong Han, Vipin Kumar. IEEE Computer 32(8): 68-75, 1999</ref>.		CHAMELEON – алгоритм динамической иерархической кластеризации графа, то есть процесса разбиения графа на несколько подграфов-кластеров таким образом, что данные внутри одного кластера имеют максимально схожи, а данные в разных кластерах — максимально различны. В классических алгоритмах кластеризации схожесть объектов определяется с помощью некоторой метрики (простейший пример - евклидова метрика). Не следует путать задачу кластеризации с задачей классификации - в последней характеристики объекта, необходимые для попадания в тот или иной класс, известны заранее, в рассматриваемой же задаче они становятся известны в процессе решения. Первоначально алгоритм был описан в статье<ref>CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling. George Karypis, Eui-Hong Han, Vipin Kumar. IEEE Computer 32(8): 68-75, 1999</ref>.

	Алгоритм CHAMELEON работает в 3 этапа. На первом этапе исходное множество объектов организуется в граф по принципу k ближайших соседей. На втором этапе этого граф разбивается на достаточно малые подграфы-кластеры. На третьем этапе происходит агломеративная иерархическая кластеризация полученных подграфов в соответствии с одной из выбранных метрик ( возможные метрики будут подробно описаны далее ). Число получаемых в итоге кластеров в явном виде не задаётся.		Алгоритм CHAMELEON работает в 3 этапа. На первом этапе исходное множество объектов организуется в граф по принципу k ближайших соседей. На втором этапе этого граф разбивается на достаточно малые подграфы-кластеры. На третьем этапе происходит агломеративная иерархическая кластеризация полученных подграфов в соответствии с одной из выбранных метрик ( возможные метрики будут подробно описаны далее ). Число получаемых в итоге кластеров в явном виде не задаётся.