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

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

2016-12-03T11:57:16Z

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

	{{algorithm		{{algorithm

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

2016-11-28T14:58:14Z

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

Sleo в 23:25, 13 ноября 2016

2016-11-13T23:25:04Z

← Предыдущая версия		Версия от 23:25, 13 ноября 2016
Строка 1:		Строка 1:
			{{Assignment\|Sleo}}
	{{Assignment}}

	{{algorithm		{{algorithm

Elmon: Баг с блоком {{Assignment}} в конце статьи, переместил в начало

2016-11-11T18:06:05Z

Баг с блоком {{Assignment}} в конце статьи, переместил в начало

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

			{{Assignment}}

	{{algorithm		{{algorithm
Строка 164:		Строка 166:

	[[en:DBSCAN]]		[[en:DBSCAN]]
	~~{{Assignment}}~~

Elmon: Вернул на проверку

2016-11-01T21:14:29Z

Вернул на проверку

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

	[[en:DBSCAN]]		[[en:DBSCAN]]
			{{Assignment}}

Elmon: Переместил референс изображения так, чтобы его было лучше видно.

2016-11-01T21:10:51Z

Переместил референс изображения так, чтобы его было лучше видно.

← Предыдущая версия		Версия от 21:10, 1 ноября 2016
Строка 54:		Строка 54:
	* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.		* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

	[[File:DBSCAN-Illustration.svg\|thumb\|right\|400px\| Рис. 1<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>~~. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.~~]]		[[File:DBSCAN-Illustration.svg\|thumb\|right\|400px\| Рис. 1. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>]]

	=== Пошаговое описание алгоритма ===		=== Пошаговое описание алгоритма ===

Elmon: Добавлено описание ссылок на алгоритмы

2016-11-01T21:06:13Z

Добавлено описание ссылок на алгоритмы

← Предыдущая версия		Версия от 21:06, 1 ноября 2016
Строка 152:		Строка 152:
	== Существующие реализации алгоритма ==		== Существующие реализации алгоритма ==

	* [https://github.com/ContinuumIO/parallel_dbscan]		* [https://github.com/ContinuumIO/parallel_dbscan Параллельная реализация для Python на OpenMP/MPI]
	* [https://github.com/propanoid/DBSCAN]		* [https://github.com/propanoid/DBSCAN Параллельная реализация для C++ на Boost и OpenMP с использованием VP-дерева]
	* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary]		* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary Параллельная реализация для С++ на OpenMP с использованием системы непересекающихся множеств]
	* [https://github.com/bwoneill/pypardis]		* [https://github.com/bwoneill/pypardis Параллельная реализация для многомерных данных для Python на SciPy и NumPy ]
	* [https://github.com/mhahsler/dbscan]		* [https://github.com/mhahsler/dbscan Последовательная реализация для R на С++]

	= Литература =		= Литература =

Elmon: Добавена вычислительная мощность алгоритма

2016-11-01T20:53:48Z

Добавена вычислительная мощность алгоритма

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

	== Свойства алгоритма ==		== Свойства алгоритма ==
			Вычислительная мощность алгоритма (отношение числа операций к объему входных и выходных данных) является логарифмической.
	* Алгоритм может определять кластера произвольной формы;		* Алгоритм может определять кластера произвольной формы;
	* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;		* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;

Elmon: Добавлено описание информационного графа

2016-11-01T20:49:36Z

Добавлено описание информационного графа

← Предыдущая версия		Версия от 20:49, 1 ноября 2016
Строка 120:		Строка 120:
	Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.		Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

	[[File:DBSCAN algo graph.png\|thumb\|center\|800px\| Граф алгоритма DBSCAN]]		[[File:DBSCAN algo graph.png\|thumb\|center\|800px\|Рис. 2. Граф алгоритма DBSCAN с отображением входных данных. Element — входные данные, Neighbours — операция поиска соседей, Check — операция проверки условий, добавления вершины к кластеру и выбора новой, Out — результаты.]]

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

Elmon: Добавлены комментарии к схеме реализации последовательного алгоритма

2016-11-01T20:39:55Z

Добавлены комментарии к схеме реализации последовательного алгоритма

← Предыдущая версия		Версия от 20:39, 1 ноября 2016
Строка 82:		Строка 82:
	for <math>p</math> in <math>X</math>:		for <math>p</math> in <math>X</math>:
	if <math>p</math> is <math>visited</math>:		if <math>p</math> is <math>visited</math>:
			# Skipping already visited elements
	continue		continue
	mark <math>p</math> as <math>visited</math>		mark <math>p</math> as <math>visited</math>
			# [Core operation] Searching for neighbors
	<math>neighbours</math> = <math>\{ o \ \| \ \forall o \in X: D(p, o) \le \varepsilon \}</math>		<math>neighbours</math> = <math>\{ o \ \| \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
	if <math>\| neighbours \| \ge MinPts</math>:		if <math>\| neighbours \| \ge MinPts</math>:
			# Found new cluster
	<math>C = C + 1</math>		<math>C = C + 1</math>
	add <math>p</math> to cluster <math>C</math>		add <math>p</math> to cluster <math>C</math>
			# Looking for more neighbors, until none left
	for <math>q \in neighbours</math>:		for <math>q \in neighbours</math>:
	if <math>q</math> is not <math>visited</math>:		if <math>q</math> is not <math>visited</math>:
			# If element is visited, then either it was marked as part of other cluster, or as noise
	mark <math>q</math> as <math>visited</math>		mark <math>q</math> as <math>visited</math>
			# [Core operation] Searching for neighbors
	<math>q\_neighbours</math> = <math>\{ o \ \| \ \forall o \in X: D(q, o) \le \varepsilon \}</math>		<math>q\_neighbours</math> = <math>\{ o \ \| \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
	if <math>\| q\_neighbours \| \ge MinPts</math>:		if <math>\| q\_neighbours \| \ge MinPts</math>:
			# We can expand neighbors with new elements from element <math>q</math>
	<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>		<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
	if <math>q</math> has no cluster mark:		if <math>q</math> has no cluster mark:
			# If it's noise — mark as edge-element part of cluster
	mark <math>q</math> as part of cluster <math>C</math>		mark <math>q</math> as part of cluster <math>C</math>
	else:		else: