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

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

2016-11-29T14:27:20Z

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

	Основные авторы описания: <br>		Основные авторы описания: <br>
	[[Участник:JuliaA\|Ю.А. Антохина]], разделы [[#Общее описание алгоритма\|1.1]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Ресурс параллелизма алгоритма\|1.8]] - [[#Свойства алгоритма\|1.10]], [[#Существующие реализации алгоритма\|2.7]]<br>		[[Участник:JuliaA\|Ю.А. Антохина]], разделы [[#Общее описание алгоритма\|1.1]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Ресурс параллелизма алгоритма\|1.8]] - [[#Свойства алгоритма\|1.10]], [[#Существующие реализации алгоритма\|2.7]]<br>

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

2016-11-29T14:21:53Z

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

	Основные авторы описания: <br>		Основные авторы описания: <br>
	[[Участник:JuliaA\|Ю.А. Антохина]], разделы [[#Общее описание алгоритма\|1.1]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Ресурс параллелизма алгоритма\|1.8]] - [[#Свойства алгоритма\|1.10]], [[#Существующие реализации алгоритма\|2.7]]<br>		[[Участник:JuliaA\|Ю.А. Антохина]], разделы [[#Общее описание алгоритма\|1.1]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Ресурс параллелизма алгоритма\|1.8]] - [[#Свойства алгоритма\|1.10]], [[#Существующие реализации алгоритма\|2.7]]<br>

Coctic в 13:47, 16 ноября 2016

2016-11-16T13:47:25Z

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

	Основные авторы описания: <br>		Основные авторы описания: <br>
	[[Участник:JuliaA\|Ю.А. Антохина]], разделы [[#Общее описание алгоритма\|1.1]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Ресурс параллелизма алгоритма\|1.8]] - [[#Свойства алгоритма\|1.10]], [[#Существующие реализации алгоритма\|2.7]]<br>		[[Участник:JuliaA\|Ю.А. Антохина]], разделы [[#Общее описание алгоритма\|1.1]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Ресурс параллелизма алгоритма\|1.8]] - [[#Свойства алгоритма\|1.10]], [[#Существующие реализации алгоритма\|2.7]]<br>

Cookie в 20:18, 15 ноября 2016

2016-11-15T20:18:54Z

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

	Основные авторы описания: <br>		Основные авторы описания: <br>
	[[Участник:JuliaA\|Ю.А. Антохина]], разделы [[#Общее описание алгоритма\|1.1]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Ресурс параллелизма алгоритма\|1.8]] - [[#Свойства алгоритма\|1.10]], [[#Существующие реализации алгоритма\|2.7]]<br>		[[Участник:JuliaA\|Ю.А. Антохина]], разделы [[#Общее описание алгоритма\|1.1]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Ресурс параллелизма алгоритма\|1.8]] - [[#Свойства алгоритма\|1.10]], [[#Существующие реализации алгоритма\|2.7]]<br>

Cookie: /* Входные и выходные данные алгоритма */

2016-11-15T20:13:56Z

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

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

	Параметр <math>\gamma</math> задаёт какая часть от <math>m</math> точек будет использована при случайной выборке точек на шаге "Инициализация".		Параметр <math>\gamma</math> задаёт какая часть от <math>m</math> точек будет использована при случайной выборке точек на шаге "Инициализация". Слишком малое значение <math>\gamma</math> может привести к объединению удалённых кластеров (если ни одна из точек предполагаемого кластера не была выбрана, они были присоединены к другому кластеру на этапе присваивания), а также к разделению кластеров на части (так как конечное количество кластеров фиксировано, а некоторые кластеры могут не набрать достаточное количество мест в выборке, чтобы их кластер сформировался). С другой стороны, скорость вычислений зависит от величины выборки: увеличение выборки при фиксированном числе кластеров <math>h</math> приведёт к дополнительным шагам на этапе кластеризации, а также к дополнительным вычислениям при нахождении кластеров, "наиболее подходящих" для объединения на каждом шаге. Кроме того, увеличение выборки приводит к уменьшению числа оставшихся точек, присвоение которых не входит в [[#Вычислительное ядро алгоритма\|Вычислительное ядро алгоритма]].

	'''Объём входных данных:''' <math>m\times n + 4</math>		'''Объём входных данных:''' <math>m\times n + 4</math>

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

2016-11-15T19:53:00Z

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

← Предыдущая версия		Версия от 19:53, 15 ноября 2016
Строка 28:		Строка 28:
	Выбранные точки сдвигаются на следующем шаге на <math>\alpha</math> к центроиду кластера. Алгоритм становится основанным на методе поиска центроида при <math>\alpha = 1</math>, и основанным на всех точках кластера при <math>\alpha = 0</math>.		Выбранные точки сдвигаются на следующем шаге на <math>\alpha</math> к центроиду кластера. Алгоритм становится основанным на методе поиска центроида при <math>\alpha = 1</math>, и основанным на всех точках кластера при <math>\alpha = 0</math>.

	[[Файл:Exampleofalgorithmparametrs1.png\|~~400px~~\|thumb\|center\|Пример работы алгоритма для разных параметров <math>\alpha</math> [1].]]		[[Файл:Exampleofalgorithmparametrs1.png\|600px\|thumb\|center\|Пример работы алгоритма для разных параметров <math>\alpha</math> [1].]]

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

Cookie: /* Входные и выходные данные алгоритма */

2016-11-15T19:52:30Z

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

← Предыдущая версия		Версия от 19:52, 15 ноября 2016
Строка 205:		Строка 205:
	'''Объём входных данных:''' <math>m\times n + 4</math>		'''Объём входных данных:''' <math>m\times n + 4</math>

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

	[[Файл:Exampleofalgorithmparameters2.png\|400px\|thumb\|center\|Пример работы алгоритма для разных параметров <math>c</math>.]]		[[Файл:Exampleofalgorithmparameters2.png\|400px\|thumb\|center\|Пример работы алгоритма для разных параметров <math>c</math>.]]

Cookie: /* Информационный граф */

2016-11-15T19:03:28Z

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

← Предыдущая версия		Версия от 19:03, 15 ноября 2016
Строка 157:		Строка 157:
	'''Шаг "Присваивание"'''		'''Шаг "Присваивание"'''

	Вычисление расстояний до точек представителей можно выполнять независимо между собой.		Вычисление расстояний до точек-представителей можно выполнять независимо между собой.

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

2016-11-15T19:02:44Z

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

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

	Пусть дана матрица <math>x \in R^{m\times n}</math>, количество кластеров <math>h</math>, число точек представителей <math>c</math>, параметр <math>\alpha</math>, параметр <math>\gamma</math>. Каждая строка матрицы представляет собой точку в <math>n</math> - мерном пространстве.		Пусть дана матрица <math>x \in R^{m\times n}</math>, количество кластеров <math>h</math>, число точек-представителей <math>c</math>, параметр <math>\alpha</math>, параметр <math>\gamma</math>. Каждая строка матрицы представляет собой точку в <math>n</math> - мерном пространстве.

	m число точек для кластеризации, n размерность.		m число точек для кластеризации, n размерность.

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

2016-11-15T19:01:50Z

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

← Предыдущая версия		Версия от 19:01, 15 ноября 2016
Строка 13:		Строка 13:
	Результат кластеризации зависит от того, как будут представлены кластеры. Например, средним всех точек кластера, или всеми точками кластера. Применение среднего возможно только в евклидовом пространстве. А использование всех точек неустойчиво к случайным выбросам. В CURE используется другой метод: для каждого кластера выбираются точки-представители. Выбирается постоянное число точек, которые будут представлять каждый кластер. Кластеры с наиболее похожими наборами репрезентативных точек объединяются на каждом шаге алгоритма.		Результат кластеризации зависит от того, как будут представлены кластеры. Например, средним всех точек кластера, или всеми точками кластера. Применение среднего возможно только в евклидовом пространстве. А использование всех точек неустойчиво к случайным выбросам. В CURE используется другой метод: для каждого кластера выбираются точки-представители. Выбирается постоянное число точек, которые будут представлять каждый кластер. Кластеры с наиболее похожими наборами репрезентативных точек объединяются на каждом шаге алгоритма.

	За счет использования точек представителей алгоритм CURE устойчив к выбросам и может выделять кластеры сложной формы и различных размеров.		За счет использования точек-представителей алгоритм CURE устойчив к выбросам и может выделять кластеры сложной формы и различных размеров.

	Описание шагов		Описание шагов
Строка 20:		Строка 20:
	Дальше работаем с кластерами.		Дальше работаем с кластерами.

	'''Шаг 2'''. Для каждого кластера выбираем <math>c</math> точек представителей, максимально удаленных друг от друга. Чисто <math>c</math> остается постоянным.		'''Шаг 2'''. Для каждого кластера выбираем <math>c</math> точек-представителей, максимально удаленных друг от друга. Чисто <math>c</math> остается постоянным.

	'''Шаг 3'''. Объединяем кластеры с наиболее похожими наборами точек представителей.		'''Шаг 3'''. Объединяем кластеры с наиболее похожими наборами точек-представителей.
	Если не достигнуто нужное число кластеров, то перейти на шаг 2.		Если не достигнуто нужное число кластеров, то перейти на шаг 2.
	Чтобы при объединении кластеров не выбирать каждый раз c точек представителей из всех точек, мы выбираем их только из <math>2c</math> точек объединенных кластеров.		Чтобы при объединении кластеров не выбирать каждый раз c точек-представителей из всех точек, мы выбираем их только из <math>2c</math> точек объединенных кластеров.

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