Участник:Elena777mc/Плотностный алгоритм кластеризации DBSCAN - История изменений

ASA в 11:56, 3 декабря 2016

2016-12-03T11:56:48Z

← Предыдущая версия		Версия от 11:56, 3 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|~~Преподаватель 1~~\|Dexter}}		{{Assignment\|Sleo\|Dexter}}
	~~{{Assignment\|Sleo~~}}

	{{algorithm		{{algorithm

Dexter в 14:59, 28 ноября 2016

2016-11-28T14:59:16Z

← Предыдущая версия		Версия от 14:59, 28 ноября 2016
Строка 1:		Строка 1:
	{{Assignment\|Преподаватель 1\|Dexter}}		{{Assignment\|Преподаватель 1\|Dexter}}
	{Assignment\|Sleo}}		{{Assignment\|Sleo}}

	{{algorithm		{{algorithm

Dexter в 14:57, 28 ноября 2016

2016-11-28T14:57:52Z

← Предыдущая версия		Версия от 14:57, 28 ноября 2016
Строка 1:		Строка 1:
	{{Assignment\|Sleo}}		{{Assignment\|Преподаватель 1\|Dexter}}
			{Assignment\|Sleo}}

	{{algorithm		{{algorithm

ASA в 11:52, 25 ноября 2016

2016-11-25T11:52:43Z

← Предыдущая версия		Версия от 11:52, 25 ноября 2016
Строка 1:		Строка 1:
	{{Assignment\|Sleo}}		{{Assignment\|Sleo}}
	~~{{Assignment}}~~
	{{algorithm		{{algorithm
	\| name = Плотностный алгоритм кластеризации DBSCAN		\| name = Плотностный алгоритм кластеризации DBSCAN

Elena777mc: /* Схема реализации последовательного алгоритма */

2016-11-20T18:38:24Z

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

← Предыдущая версия		Версия от 18:38, 20 ноября 2016
Строка 67:		Строка 67:
	call function <math>expand\_cluster</math> to construct a cluster wrt. <math>\varepsilon</math> and <math>MinPts</math> containing <math>x</math>		call function <math>expand\_cluster</math> to construct a cluster wrt. <math>\varepsilon</math> and <math>MinPts</math> containing <math>x</math>

	// ~~Вспомогательная функция~~, которая строит кластер на основе одной точки		// Функция, которая строит кластер на основе одной точки
	<math>FUNCTION\ expand\_cluster(x,X,\varepsilon, MinPts):</math>		<math>FUNCTION\ expand\_cluster(x,X,\varepsilon, MinPts):</math>
	<math>retrive\_\varepsilon neighborhood(x, \varepsilon)</math>;		<math>retrive\_\varepsilon neighborhood(x, \varepsilon)</math>;
Строка 84:		Строка 84:
	<math>RETURN</math>		<math>RETURN</math>

	// ~~Вспомогательная функция~~, для определения <math>\varepsilon</math>-соседей для объекта		// Функция, для определения <math>\varepsilon</math>-соседей для объекта
	<math>FUNCTION\ retrive\_\varepsilon neighborhood(x, \varepsilon)</math> //функция возвращает соседей на основе пространственной структуры данных		<math>FUNCTION\ retrive\_\varepsilon neighborhood(x, \varepsilon)</math> //функция возвращает соседей на основе пространственной структуры данных
	return <math>\{ x' \ \| \ \forall x' \in X: \rho(x, x') < \varepsilon \}</math>		return <math>\{ x' \ \| \ \forall x' \in X: \rho(x, x') < \varepsilon \}</math>

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

2016-11-20T18:35:29Z

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

← Предыдущая версия		Версия от 18:35, 20 ноября 2016
Строка 95:		Строка 95:
	[[File:Dbscan_schema.jpg\|1000px\|thumb\|center\|Рис.1. Общая информационная структура алгоритма]]		[[File:Dbscan_schema.jpg\|1000px\|thumb\|center\|Рис.1. Общая информационная структура алгоритма]]
	Разбиение данных происходит с помощью пространственной структуры данных (R*-дерево, kd-дерево), которая разбивает все множество объектов <math>X</math> на <math>m</math> частей: <math>X_1,X_2,...,X_m</math>.		Разбиение данных происходит с помощью пространственной структуры данных (R*-дерево, kd-дерево), которая разбивает все множество объектов <math>X</math> на <math>m</math> частей: <math>X_1,X_2,...,X_m</math>.
	[[File:dbscan_clusters_partitions.png\|500px\|thumb\|center\|Рис.2. Пример разбиения объектов на части на основе пространственной структуры<ref>https://github.com/bwoneill/pypardis/blob/master/plots/median_search_split/clusters_partitions.png</ref>]]
	На каждой части объектов применяется алгоритм PDBSCAN. PDBSCAN - это последовательный алгоритм DBSCAN, применяемый только к одной части объектов, и для каждой из этих частей он определяет кандидатов на слияние. PDBSCAN использует пространственную структуру, которая распределяется вместе с данными.		На каждой части объектов применяется алгоритм PDBSCAN. PDBSCAN - это последовательный алгоритм DBSCAN, применяемый только к одной части объектов, и для каждой из этих частей он определяет кандидатов на слияние. PDBSCAN использует пространственную структуру, которая распределяется вместе с данными.
	Если для ядрового объекта части <math>X_i</math> в <math>\varepsilon</math>-окрестности находится объект из другой части <math>X_j</math>, то такие объекты становятся кандидатами на слияние.		Если для ядрового объекта части <math>X_i</math> в <math>\varepsilon</math>-окрестности находится объект из другой части <math>X_j</math>, то такие объекты становятся кандидатами на слияние.

	Само слияние осуществляется следующим образом: для каждой пары кандидатов на слияние, объединяем кластеры, соответствующие этим кандидатам в один общий кластер.		Само слияние осуществляется следующим образом: для каждой пары кандидатов на слияние, объединяем кластеры, соответствующие этим кандидатам в один общий кластер.

			[[File:dbscan_clusters_partitions.png\|500px\|thumb\|center\|Рис.2. Пример разбиения объектов на части на основе пространственной структуры. Каждый прямоугольник соответствует части данных, каждая из которых подается на вход алгоритму PDBSCAN <ref>https://github.com/bwoneill/pypardis/blob/master/plots/median_search_split/clusters_partitions.png</ref>]]

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

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

2016-11-20T18:32:07Z

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

← Предыдущая версия		Версия от 18:32, 20 ноября 2016
Строка 96:		Строка 96:
	Разбиение данных происходит с помощью пространственной структуры данных (R*-дерево, kd-дерево), которая разбивает все множество объектов <math>X</math> на <math>m</math> частей: <math>X_1,X_2,...,X_m</math>.		Разбиение данных происходит с помощью пространственной структуры данных (R*-дерево, kd-дерево), которая разбивает все множество объектов <math>X</math> на <math>m</math> частей: <math>X_1,X_2,...,X_m</math>.
	[[File:dbscan_clusters_partitions.png\|500px\|thumb\|center\|Рис.2. Пример разбиения объектов на части на основе пространственной структуры<ref>https://github.com/bwoneill/pypardis/blob/master/plots/median_search_split/clusters_partitions.png</ref>]]		[[File:dbscan_clusters_partitions.png\|500px\|thumb\|center\|Рис.2. Пример разбиения объектов на части на основе пространственной структуры<ref>https://github.com/bwoneill/pypardis/blob/master/plots/median_search_split/clusters_partitions.png</ref>]]
	На каждой части объектов применяется алгоритм PDBSCAN (каждая часть использует пространственную структуру данных, которая распределяется вместе с каждой частью данных). ~~Данный~~ алгоритм ~~отличается от общего алгоритма~~ DBSCAN ~~тем~~, ~~что применяется~~ к части объектов и для каждой из этих частей определяет кандидатов на слияние. Если для ядрового объекта части <math>X_i</math> в <math>\varepsilon</math>-окрестности находится объект из другой части <math>X_j</math>, то такие объекты становятся кандидатами на слияние.		На каждой части объектов применяется алгоритм PDBSCAN. PDBSCAN - это последовательный алгоритм DBSCAN, применяемый только к одной части объектов, и для каждой из этих частей он определяет кандидатов на слияние. PDBSCAN использует пространственную структуру, которая распределяется вместе с данными.
			Если для ядрового объекта части <math>X_i</math> в <math>\varepsilon</math>-окрестности находится объект из другой части <math>X_j</math>, то такие объекты становятся кандидатами на слияние.

	Само слияние осуществляется следующим образом: для каждой пары кандидатов на слияние, объединяем кластеры, соответствующие этим кандидатам в один общий кластер.		Само слияние осуществляется следующим образом: для каждой пары кандидатов на слияние, объединяем кластеры, соответствующие этим кандидатам в один общий кластер.

Elena777mc: /* Схема реализации последовательного алгоритма */

2016-11-20T18:20:58Z

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

← Предыдущая версия		Версия от 18:20, 20 ноября 2016
Строка 70:		Строка 70:
	<math>FUNCTION\ expand\_cluster(x,X,\varepsilon, MinPts):</math>		<math>FUNCTION\ expand\_cluster(x,X,\varepsilon, MinPts):</math>
	<math>retrive\_\varepsilon neighborhood(x, \varepsilon)</math>;		<math>retrive\_\varepsilon neighborhood(x, \varepsilon)</math>;
	<math>IF \mid N_{\varepsilon}(x) \mid < MinPts</math> //т.е. <math>x</math> - не ~~ядровой объект~~		<math>IF \mid N_{\varepsilon}(x) \mid < MinPts</math> //т.е. <math>x</math> - объект, не являющийся ядром
	mark <math>x</math> as <math>noise</math> and <math>RETURN</math>;		mark <math>x</math> as <math>noise</math> and <math>RETURN</math>;
	<math>ELSE</math>//т.е. <math>x</math> - ~~ядровой~~ объект		<math>ELSE</math>//т.е. <math>x</math> - объект, являющийся ядром
	select a new cluster-id and mark all objects in <math>N_{\varepsilon}(x)</math> with this current <math>cluster-id</math>;		select a new cluster-id and mark all objects in <math>N_{\varepsilon}(x)</math> with this current <math>cluster-id</math>;
	push all objects from <math>N_{\varepsilon}(x)</math>\<math>(x)</math> onto the stack seeds;		push all objects from <math>N_{\varepsilon}(x)</math>\<math>(x)</math> onto the stack seeds;

Elena777mc: /* Макроструктура алгоритма */

2016-11-20T18:19:15Z

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

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

	== Макроструктура алгоритма ==		== Макроструктура алгоритма ==
	Алгоритм DBSCAN использует пространственную структуру данных для определения соседних объектов~~. Это может быть R*-дерево или kd-дерево~~. Такие структуры данных позволяют найти все объекты в пределах определенного расстояния от текущего объекта. Сложность построения таких структур <math>O(n \log n)</math>, и использование такой структуры не увеличит сложность всего алгоритма (если сложность самого алгоритма <math>O(n \log n)</math>). Также для построения таких деревьев нужно уметь находить расстояния между объектами <math>\rho(u,v)</math>, это расстояние можно вводить разными способами. Например, если <math>\rho(u,v)</math> - метрика в евклидовом пространстве, <math>u=(u_1,...,u_n)</math> и <math>(v_1,...,v_n)</math>, то расстояние вычисляется следующим образом: <math>\rho(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}</math>		Алгоритм DBSCAN использует пространственную структуру данных для определения соседних объектов. Такие структуры данных позволяют найти все объекты в пределах определенного расстояния от текущего объекта. Сложность построения таких структур <math>O(n \log n)</math>, и использование такой структуры не увеличит сложность всего алгоритма (если сложность самого алгоритма <math>O(n \log n)</math>). Также для построения таких деревьев нужно уметь находить расстояния между объектами <math>\rho(u,v)</math>, это расстояние можно вводить разными способами. Например, если <math>\rho(u,v)</math> - метрика в евклидовом пространстве, <math>u=(u_1,...,u_n)</math> и <math>(v_1,...,v_n)</math>, то расстояние вычисляется следующим образом: <math>\rho(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}</math>

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

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

2016-11-20T18:17:45Z

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

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

	[[File:~~dbscan_osn~~.png\|thumb\|right\|500px\| Рис. 1. Пример ядровых, граничных и шумовых точек алгоритма <ref>~~http~~://~~stats~~.~~stackexchange~~.~~com~~/~~questions~~/~~194734~~/~~dbscan~~-~~what~~-is-~~a-core-point~~</ref>]]		[[File:Dbscan_picture.png\|thumb\|right\|500px\| Рис. 1. Пример ядровых, граничных и шумовых точек алгоритма. Точка A - ядровая, точки B и С - граничные, N - шум. В данном примере MinPts = 4, Eps равен радиусу окружности <ref>https://upload.wikimedia.org/wikipedia/commons/thumb/a/af/DBSCAN-Illustration.svg/400px-DBSCAN-Illustration.svg.png</ref>]]

	Исходные данные: объекты, которые нужно кластеризовать, параметры <math>MinPts, \ \varepsilon</math> . Между объектами можно считать расстояния.		Исходные данные: объекты, которые нужно кластеризовать, параметры <math>MinPts, \ \varepsilon</math> . Между объектами можно считать расстояния.