Участник:Лукьянова Анна/Алгоритм кластеризации с использованием представлений2 - История изменений

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

2016-11-29T14:27:04Z

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

	Основные авторы описания: [[U:Лукьянова Анна\|А.Я. Лукьянова]]		Основные авторы описания: [[U:Лукьянова Анна\|А.Я. Лукьянова]]

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

2016-11-29T14:26:28Z

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

	Основные авторы описания: [[U:Лукьянова Анна\|А.Я. Лукьянова]]		Основные авторы описания: [[U:Лукьянова Анна\|А.Я. Лукьянова]]

IgorS в 11:00, 16 ноября 2016

2016-11-16T11:00:21Z

← Предыдущая версия		Версия от 11:00, 16 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment\|IgorS}}~~

	Основные авторы описания: [[U:Лукьянова Анна\|А.Я. Лукьянова]]		Основные авторы описания: [[U:Лукьянова Анна\|А.Я. Лукьянова]]

Лукьянова Анна: /* Масштабируемость алгоритма и его реализации */

2016-11-15T19:41:54Z

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

← Предыдущая версия		Версия от 19:41, 15 ноября 2016
Строка 212:		Строка 212:

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

			будет..

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

Лукьянова Анна: /* CURE */

2016-11-15T18:54:06Z

CURE

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

	''Назначение'': кластеризация очень больших наборов числовых данных.		''Назначение'': кластеризация очень больших наборов числовых данных.

	~~''Ограничения'': эффективен для данных низкой размерности, работает только на числовых данных.~~

	''Достоинства'':		''Достоинства'':

Лукьянова Анна: /* Входные и выходные данные алгоритма */

2016-11-15T13:42:59Z

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

← Предыдущая версия		Версия от 13:42, 15 ноября 2016
Строка 170:		Строка 170:
	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==

	'''Входные данные:''' набор данных <math> S </math> , количество кластеров <math>k</math>, число точек представителей <math>c</math>, параметр <math>\alpha</math>, параметр <math>~~\gamma~~</math>, <math>m</math> число ~~точек для кластеризации~~, <math>n</math> размерность.		'''Входные данные:''' набор данных <math> S </math> , количество кластеров <math>k</math>, число точек представителей <math>c</math>, параметр <math>\alpha</math>, параметр <math>q</math>, <math>p</math> число разбиений выборки, <math>n</math> размерность.

	Параметр <math>\alpha</math> для сжатия точек представления к центру кластера. В оригинальной статье авторы показывают что <math>\alpha</math> от <math>0.2</math> до <math>0.7</math> помогает хорошо выявлять несферические кластеры и подавлять редкие выбросы.		Параметр <math>\alpha</math> для сжатия точек представления к центру кластера.

	~~[[Файл~~:~~Factor_a.png\|400px\|thumb\|center\| Рисунок 2: Чувствительность алгоритма к параметру~~ <math>~~\alpha~~ </math>~~.]]~~		'''Выходные данные:''' требуемое количество <math> k </math> крастеров

	Параметр <math>\gamma</math> задаёт какая часть от <math>m</math> точек будет использована при случайной выборке точек на шаге 2.		===Оптимальный выбор параметров для алгоритма===

	Число точек представителей выбирается в зависимости от данных. Если возможно появление кластеров сложной формы, то точек должно быть больше, чтобы выявить их форму. В оригинальной статье авторы показывают что уже при <math>c</math> ~~равном <math>10</math> достигается неплохая эффективность.~~		*размер случайной выборки <math> S </math> (''а'')

	~~[[Файл:Param_c.png\|400px\|thumb\|center\| Рисунок 4: Результат работы алгоритка~~ в ~~зависимости~~ от ~~количесва представлений <math>c</math>~~.]]		При запуске CURE со случайными размерами выборки в пределах от 500 до 5000 видно, что при размерах до 2000 были найдены кластеры низкого качества, начиная с 2500 точек и выше (2,5% от установленного размера данных), CURE всегда правильно определяет кластеры.

	~~Из рисунка видно,~~ что при ~~меньших значениях~~ <math>c</math> ~~качество работы алгоритма ухудшается~~		*число точек представителей <math> c </math> (''b'')
			В оригинальной статье авторы показывают что уже при <math> c </math> равном <math>10</math> достигается неплохая эффективность.

	'''~~Выходные данные:~~''' ~~требуемое количество~~ <math> k </math> ~~крастеров~~		*число разбиений выборки <math> p </math> ('''c''')
			<math> p </math> должно быть выбрано таким, что <math> \frac{s}{pq} </math> > <math> k </math>

			*размерность (''d'')
			CURE хорошо себя чувствует при больших размерностях

			*сжимающий фактор <math>\alpha</math>
			В оригинальной статье авторы показывают что <math>\alpha</math> от 0.2 до 0.7 помогает хорошо выявлять несферические кластеры и подавлять редкие выбросы.

			[[Файл:4pic.png\|800px\|thumb\|center\| Рисунок 5: Влияние параметров <math> S </math>, <math> c </math>, <math> p </math> и размерности на работу алгоритма.]]

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

Лукьянова Анна: /* Математическое описание алгоритма */

2016-11-15T13:15:22Z

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

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

	Прежде всего, алгоритм использует случайное разбиение выборки из <math> n </math> элементов на <math> p </math> частей, которые могут поместиться в память отдельной машины кластера. Затем во время первого прохода алгоритм уменьшает число кластеров в каждой подвыборке до <math> \frac{n}{pq} </math>, где <math> q \geq 1 </math> – некоторая константа (происходит объединение ближайших кластеров). Для определения расстояния между кластерами используются «манхеттенская», «евклидова» метрики или похожие на них функции.		Прежде всего, алгоритм использует случайное разбиение выборки из <math> s </math> элементов на <math> p </math> частей, которые могут поместиться в память отдельной машины кластера. Затем во время первого прохода алгоритм уменьшает число кластеров в каждой подвыборке до <math> \frac{s}{pq} </math>, где <math> q \geq 1 </math> – некоторая константа (происходит объединение ближайших кластеров). Для определения расстояния между кластерами используются «манхеттенская», «евклидова» метрики или похожие на них функции.

	''Метрика Евклида:'' <math>\rho(p,k) = \sqrt{\sum_{i=1}^n (p_{i} - k_{i})^2}</math>		''Метрика Евклида:'' <math>\rho(p,k) = \sqrt{\sum_{i=1}^n (p_{i} - k_{i})^2}</math>

Лукьянова Анна: /* Информационный граф */

2016-11-15T12:24:50Z

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

← Предыдущая версия		Версия от 12:24, 15 ноября 2016
Строка 162:		Строка 162:
	В начале работы алгоритма все объекты являются отдельными кластерами. На первом шаге наиболее похожие объекты объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер.		В начале работы алгоритма все объекты являются отдельными кластерами. На первом шаге наиболее похожие объекты объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер.

	[[Файл:Metod.png\|400px\|thumb\|center\| Рисунок 3: Дендрограмма агломеративных методов]]		[[Файл:Metod.png\|400px\|thumb\|center\| Рисунок 4: Дендрограмма агломеративных методов]]

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

Лукьянова Анна: /* Математическое описание алгоритма */

2016-11-15T12:24:27Z

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

← Предыдущая версия		Версия от 12:24, 15 ноября 2016
Строка 101:		Строка 101:
	Число точек представителей выбирается в зависимости от данных. Если возможно появление кластеров сложной формы, то точек должно быть больше, чтобы выявить их форму. В оригинальной статье авторы показывают что уже при <math>c</math> равном <math>10</math> достигается неплохая эффективность.		Число точек представителей выбирается в зависимости от данных. Если возможно появление кластеров сложной формы, то точек должно быть больше, чтобы выявить их форму. В оригинальной статье авторы показывают что уже при <math>c</math> равном <math>10</math> достигается неплохая эффективность.

	[[Файл:Param_c.png\|400px\|thumb\|center\| Рисунок 4: Результат работы алгоритка в зависимости от количесва представлений <math>c</math>.]]		[[Файл:Param_c.png\|400px\|thumb\|center\| Рисунок 2: Результат работы алгоритка в зависимости от количесва представлений <math>c</math>.]]

	Из рисунка видно, что при меньших значениях <math>c</math> качество работы алгоритма ухудшается		Из рисунка видно, что при меньших значениях <math>c</math> качество работы алгоритма ухудшается
Строка 107:		Строка 107:
	Выбранные точки сдвигаются на <math>\alpha</math> к центроиду кластера. Алгоритм становится основанным на методе поиска центроида при <math>\alpha = 1</math>, и основанным на всех точках кластера при <math>\alpha = 0</math>.		Выбранные точки сдвигаются на <math>\alpha</math> к центроиду кластера. Алгоритм становится основанным на методе поиска центроида при <math>\alpha = 1</math>, и основанным на всех точках кластера при <math>\alpha = 0</math>.

	[[Файл:Factor_a.png\|400px\|thumb\|center\| Рисунок 2: Чувствительность алгоритма к параметру <math>\alpha </math>.]]		[[Файл:Factor_a.png\|400px\|thumb\|center\| Рисунок 3: Чувствительность алгоритма к параметру <math>\alpha </math>.]]

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

Лукьянова Анна: /* Математическое описание алгоритма */

2016-11-15T12:24:01Z

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

@@ Строка 89: / Строка 89: @@
 == Математическое описание алгоритма ==
-Прежде всего, алгоритм использует случайное разбиение выборки из <math> n </math> элементов на <math> p </math> частей, которые могут поместиться в память отдельной машины кластера. Затем во время первого прохода алгоритм уменьшает число кластеров в каждой подвыборке до <math> \frac{n}{pq} </math>, где <math> q \geq 1 </math> – некоторая константа. Для последующего шага на вход кластеризации подаются только представительные точки <math>c</math>  кластеров, полученных на предыдущем этапе. В ходе второго прохода алгоритма кластеризации остаются представительные точки для заданного количества кластеров. Алгоритм использует представительные точки, как метки, задающие форму и размер кластера.
+Прежде всего, алгоритм использует случайное разбиение выборки из <math> n </math> элементов на <math> p </math> частей, которые могут поместиться в память отдельной машины кластера. Затем во время первого прохода алгоритм уменьшает число кластеров в каждой подвыборке до <math> \frac{n}{pq} </math>, где <math> q \geq 1 </math> – некоторая константа (происходит объединение ближайших кластеров). Для определения расстояния между кластерами используются «манхеттенская», «евклидова» метрики или похожие на них функции.
 == Вычислительное ядро алгоритма ==