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

ASA в 13:29, 19 декабря 2016

2016-12-19T13:29:46Z

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

Руслан в 09:50, 18 декабря 2016

2016-12-18T09:50:31Z

← Предыдущая версия		Версия от 09:50, 18 декабря 2016
Строка 18:		Строка 18:

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	Идея, положенная в основу алгоритма, заключается в том, что внутри каждого кластера наблюдается типичная плотность точек (объектов), которая заметно выше, чем плотность снаружи кластера, а также плотность в областях с шумом ниже плотности любого из кластеров. Ещё точнее, что для каждой точки кластера её соседство заданного радиуса должно содержать не менее некоторого числа точек, это число точек задаётся пороговым значением. Алгоритм DBSCAN для заданных значений параметров <math>\varepsilon</math> и MinPts исследует кластер следующим образом: сначала выбирает случайную точку, являющуюся ядровой, в качестве затравки, затем помещает в кластер саму затравку и все точки, плотно-достижимые из неё.		Идея, положенная в основу алгоритма, заключается в том, что внутри каждого кластера наблюдается типичная плотность точек (объектов), которая заметно выше, чем плотность снаружи кластера, а также плотность в областях с шумом ниже плотности любого из кластеров. Ещё точнее, что для каждой точки кластера её соседство заданного радиуса должно содержать не менее некоторого числа точек, это число точек задаётся пороговым значением. Алгоритм DBSCAN для заданных значений параметров <math>\varepsilon</math> и MinPts исследует кластер следующим образом: сначала выбирает случайную точку, являющуюся ядровой, в качестве затравки, затем помещает в кластер саму затравку и все точки, плотно-достижимые из неё. (Точка <math>p</math> плотно-достижима из точки <math>q</math> если <math> 1) p \in N_\varepsilon (q); \quad 2) \mid N_\varepsilon (q) \mid \ge MinPts.</math>)

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

	Алгоритм начинает работу с произвольной точки <math>x \in X</math> и возвращает <math>\varepsilon</math> -окрестность(строка 4). Если <math>\varepsilon</math>-окрестность содержит, как минимум minpts точек, процедура выдает новый кластер C. Алгоритм извлекает все точки в X, которые являются плотность достижима из x и добавляет их в кластер C(строки 8-17). Если в <math>\varepsilon</math>-окрестности x точек меньше, чем minpts, то x помечается как шум(строка 6). Однако, х все еще может быть добавлены в кластер, если она определится как пограничная точка во время изучения других основных точек(строки 16-17). Поиск точек в <math>\varepsilon</math>-окрестности(функция GETNEIGHBORS)известен, как запрос в диапазоне значений и получает все ~~плотностно~~ достижимые точки от главной точки(строки 8-17) известный как алгоритм наращивания областей. Заметим что кластер может быть определен однозначно, начиная с любой "ядровой" точки<ref> A. Zhou, S. Zhou, J. Cao, Y. Fan, and Y. Hu, “Approaches for scaling DBSCAN algorithm to large spatial databases,” Journal of computer science and technology, vol. 15, no. 6, pp. 509–526, 2000.</ref>.		Алгоритм начинает работу с произвольной точки <math>x \in X</math> и возвращает <math>\varepsilon</math> -окрестность(строка 4). Если <math>\varepsilon</math>-окрестность содержит, как минимум minpts точек, процедура выдает новый кластер C. Алгоритм извлекает все точки в <math>X</math>, которые являются плотность достижима из <math>x</math> и добавляет их в кластер C(строки 8-17). Если в <math>\varepsilon</math>-окрестности <math>x</math> точек меньше, чем minpts, то <math>x</math> помечается как шум(строка 6). Однако, <math>x</math> все еще может быть добавлены в кластер, если она определится как пограничная точка во время изучения других основных точек(строки 16-17). Поиск точек в <math>\varepsilon</math>-окрестности(функция GETNEIGHBORS)известен, как запрос в диапазоне значений и получает все плотно-достижимые точки от главной точки(строки 8-17) известный как алгоритм наращивания областей. Заметим что кластер может быть определен однозначно, начиная с любой "ядровой" точки<ref> A. Zhou, S. Zhou, J. Cao, Y. Fan, and Y. Hu, “Approaches for scaling DBSCAN algorithm to large spatial databases,” Journal of computer science and technology, vol. 15, no. 6, pp. 509–526, 2000.</ref>.


Строка 73:		Строка 73:
	== Информационный граф ==		== Информационный граф ==

	На рисунке 1 представлен информационный граф алгоритма кластеризации DBSCAN. На входе у нас множество точек <math>P_i</math> и мы пробегаем по всем непосещенным точкам. Далее мы, для каждой непосещенной точки, маркируем ее как посещенную и находим всех её <math>\varepsilon</math>-соседей(на графике это узел <math>G</math>). Добавляем точку к кластеру(узел <math>C</math>). Затем, пробегаем по всем ~~плотностно~~-достижимых точках(<math>P_j</math>) к нашей точке, и для каждой такой точки ищем <math>\varepsilon</math>-сосдей и добавляем их в кластер, если они ещё не принадлежат никакому кластеру.		На рисунке 1 представлен информационный граф алгоритма кластеризации DBSCAN. На входе у нас множество точек <math>P_i</math> и мы пробегаем по всем непосещенным точкам. Далее мы, для каждой непосещенной точки, маркируем ее как посещенную и находим всех её <math>\varepsilon</math>-соседей(на графике это узел <math>G</math>). Добавляем точку к кластеру(узел <math>C</math>). Затем, пробегаем по всем плотно-достижимых точках(<math>P_j</math>) к нашей точке, и для каждой такой точки ищем <math>\varepsilon</math>-сосдей и добавляем их в кластер, если они ещё не принадлежат никакому кластеру.

	[[file:Информационный_граф.png\|thumb\|center\|700px\|Рис.1 Граф алгоритма без отображения входных и выходных данных. <math>P_i</math> и <math>P_j</math> - точки данного множества, <math>G</math> - поиск <math>\varepsilon</math>-соседей, <math>C</math> - добавление элемента к кластеру.]]		[[file:Информационный_граф.png\|thumb\|center\|700px\|Рис.1 Граф алгоритма без отображения входных и выходных данных. <math>P_i</math> и <math>P_j</math> - точки данного множества, <math>G</math> - поиск <math>\varepsilon</math>-соседей, <math>C</math> - добавление элемента к кластеру.]]
Строка 155:		Строка 155:
	= Литература =		= Литература =

	* Ester, Martin, et al. "A density-based algorithm for discovering clusters in large spatial databases with noise." Kdd. Vol. 96. No. 34. 1996.		<references \>

	* Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.

	* Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.

	* Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.

Dexter в 15:56, 17 декабря 2016

2016-12-17T15:56:30Z

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

Sleo в 11:09, 1 декабря 2016

2016-12-01T11:09:11Z

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

	{{algorithm		{{algorithm
	\| name = Плотностный алгоритм кластеризации DBSCAN		\| name = Плотностный алгоритм кластеризации DBSCAN

Руслан в 08:59, 25 ноября 2016

2016-11-25T08:59:18Z

← Предыдущая версия		Версия от 08:59, 25 ноября 2016
Строка 124:		Строка 124:

	Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.		Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.

			[[file:DbscanPerfomance.png\|thumb\|center\|700px\|Рис.2 График масштабируемости]]


	При увеличении числа процессов наблюдается уменьшение эффективности на всей области рассматриваемых значений параметров. При этом с ростом числа процессов снижение эффективности замедляется.		При увеличении числа процессов наблюдается уменьшение эффективности на всей области рассматриваемых значений параметров. При этом с ростом числа процессов снижение эффективности замедляется.

Руслан в 17:48, 21 ноября 2016

2016-11-21T17:48:57Z

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

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

			Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.

			При увеличении числа процессов наблюдается уменьшение эффективности на всей области рассматриваемых значений параметров. При этом с ростом числа процессов снижение эффективности замедляется.

			При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.

			При одновременном увеличении количества процессов и размерности системы наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая.

			[https://github.com/ruslanmsk/parallel_dbscan Параллельная реализация на языке C++]

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

Руслан в 20:55, 15 ноября 2016

2016-11-15T20:55:46Z

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

	{{algorithm		{{algorithm
	\| name = Плотностный алгоритм кластеризации DBSCAN		\| name = Плотностный алгоритм кластеризации DBSCAN

Руслан в 20:52, 15 ноября 2016

2016-11-15T20:52:02Z

← Предыдущая версия		Версия от 20:52, 15 ноября 2016
Строка 1:		Строка 1:
			{{algorithm
			\| name = Плотностный алгоритм кластеризации DBSCAN
			\| serial_complexity = <math>O(n \log n)</math>
			\| pf_height = <math>O(\|X\| \log \|X\|)</math>
			\| pf_width = <math>O(m)</math>
			\| input_data = <math>n</math>
			\| output_data = <math>n</math>
			}}

			Основной автор описания: [[User:Руслан\|Кучеров Р.И.]]

	Алгоритм '''DBSCAN (Density Based Spatial Clustering of Applications with Noise)''' - плотностный алгоритм для кластеризации пространственных данных с присутствием шума), был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы. Большинство алгоритмов, производящих плоское разбиение, создают кластеры по форме близкие к сферическим, так как минимизируют расстояние до центра кластера. Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы.		Алгоритм '''DBSCAN (Density Based Spatial Clustering of Applications with Noise)''' - плотностный алгоритм для кластеризации пространственных данных с присутствием шума), был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы. Большинство алгоритмов, производящих плоское разбиение, создают кластеры по форме близкие к сферическим, так как минимизируют расстояние до центра кластера. Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы.
Строка 34:		Строка 43:
	== Схема реализации последовательного алгоритма ==		== Схема реализации последовательного алгоритма ==

	Алгоритм начинает работу с произвольной точки <math>x \in X</math> и возвращает <math>\varepsilon</math> -окрестность(строка 4). Если <math>\varepsilon</math>-окрестность содержит, как минимум minpts точек, процедура выдает новый кластер C. Алгоритм извлекает все точки в X, которые являются плотность достижима из x и добавляет их в кластер C(строки 8-17). Если в <math>\varepsilon</math>-окрестности x точек меньше, чем minpts, то x помечается как шум(строка 6). Однако, х все еще может быть добавлены в кластер, если она определится как пограничная точка во время изучения других основных точек(строки 16-17). Поиск точек в <math>\varepsilon</math>-окрестности(функция GETNEIGHBORS)известен, как запрос в диапазоне значений и получает все плотностно достижимые точки от главной точки(строки 8-17) известный как алгоритм наращивания областей. Заметим что кластер может быть определен однозначно, начиная с любой "ядровой" точки.		Алгоритм начинает работу с произвольной точки <math>x \in X</math> и возвращает <math>\varepsilon</math> -окрестность(строка 4). Если <math>\varepsilon</math>-окрестность содержит, как минимум minpts точек, процедура выдает новый кластер C. Алгоритм извлекает все точки в X, которые являются плотность достижима из x и добавляет их в кластер C(строки 8-17). Если в <math>\varepsilon</math>-окрестности x точек меньше, чем minpts, то x помечается как шум(строка 6). Однако, х все еще может быть добавлены в кластер, если она определится как пограничная точка во время изучения других основных точек(строки 16-17). Поиск точек в <math>\varepsilon</math>-окрестности(функция GETNEIGHBORS)известен, как запрос в диапазоне значений и получает все плотностно достижимые точки от главной точки(строки 8-17) известный как алгоритм наращивания областей. Заметим что кластер может быть определен однозначно, начиная с любой "ядровой" точки<ref> A. Zhou, S. Zhou, J. Cao, Y. Fan, and Y. Hu, “Approaches for scaling DBSCAN algorithm to large spatial databases,” Journal of computer science and technology, vol. 15, no. 6, pp. 509–526, 2000.</ref>.


Строка 58:		Строка 67:
	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==

	В общем случае алгоритм DBSCAN имеет квадратичную вычислительную сложность <math>O(n^2)</math>(где n это количество точек в X) из-за поиска <math>\varepsilon</math>-соседства. Но если использовать пространственную индексацию (например, использую k-мерное дерево~~[5]~~ или R-дерево) для поиска <math>\varepsilon</math>-соседства, сложность снижается до <math>O(n log n)</math>~~[6]~~.		В общем случае алгоритм DBSCAN имеет квадратичную вычислительную сложность <math>O(n^2)</math>(где n это количество точек в X) из-за поиска <math>\varepsilon</math>-соседства. Но если использовать пространственную индексацию (например, использую k-мерное дерево<ref>M. B. Kennel, “KDTREE 2: Fortran 95 and C++ software to efficiently search for near neighbors in a multi-dimensional Euclidean space,” 2004, institute for Nonlinear Science, University of California.</ref> или R-дерево) для поиска <math>\varepsilon</math>-соседства, сложность снижается до <math>O(n log n)</math><ref>J. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975.</ref>.

	== Информационный граф ==		== Информационный граф ==
Строка 94:		Строка 103:
	=== Недостатки алгоритма ===		=== Недостатки алгоритма ===

	* алгоритм не совсем детерминирован: пограничные точки, которые доступны из более чем одного кластера могут быть частью любого кластера, в зависимости от того, как происходит обработка данных. К счастью, эта ситуация не часто возникают, и мало влияет на результат кластеризации. На основных точках и точках "шума", алгоритм детерминирован. Есть DBSCAN~~[7]~~ который представляет собой вариант, который рассматривает пограничные пункты как шум, и таким образом достигается полностью детерминированный результат, а также более последовательной статистической интерпретации плотности соединенных компонентов.		* алгоритм не совсем детерминирован: пограничные точки, которые доступны из более чем одного кластера могут быть частью любого кластера, в зависимости от того, как происходит обработка данных. К счастью, эта ситуация не часто возникают, и мало влияет на результат кластеризации. На основных точках и точках "шума", алгоритм детерминирован. Есть DBSCAN<ref>Campello, R. J. G. B.; Moulavi, D.; Sander, J. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery in Databases, PAKDD 2013. Lecture Notes in Computer Science. p. 160.</ref> который представляет собой вариант, который рассматривает пограничные пункты как шум, и таким образом достигается полностью детерминированный результат, а также более последовательной статистической интерпретации плотности соединенных компонентов.

	* качество алогоритма зависит от меры, которую мы рассматриваем в пространстве. Наиболее распространенная мера использует евклидово расстояние.		* качество алогоритма зависит от меры, которую мы рассматриваем в пространстве. Наиболее распространенная мера использует евклидово расстояние.
Строка 138:		Строка 147:

	* Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.		* Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.

	* A. Zhou, S. Zhou, J. Cao, Y. Fan, and Y. Hu, “Approaches for scaling DBSCAN algorithm to large spatial databases,” Journal of computer science and technology, vol. 15, no. 6, pp. 509–526, 2000.

	*J. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975.

	*Campello, R. J. G. B.; Moulavi, D.; Sander, J. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery in Databases, PAKDD 2013. Lecture Notes in Computer Science. p. 160.

Sleo в 11:19, 27 октября 2016

2016-10-27T11:19:56Z

← Предыдущая версия		Версия от 11:19, 27 октября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~

	Алгоритм '''DBSCAN (Density Based Spatial Clustering of Applications with Noise)''' - плотностный алгоритм для кластеризации пространственных данных с присутствием шума), был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы. Большинство алгоритмов, производящих плоское разбиение, создают кластеры по форме близкие к сферическим, так как минимизируют расстояние до центра кластера. Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы.		Алгоритм '''DBSCAN (Density Based Spatial Clustering of Applications with Noise)''' - плотностный алгоритм для кластеризации пространственных данных с присутствием шума), был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы. Большинство алгоритмов, производящих плоское разбиение, создают кластеры по форме близкие к сферическим, так как минимизируют расстояние до центра кластера. Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы.

Руслан: Новая страница: «{{Assignment}} Алгоритм '''DBSCAN (Density Based Spatial Clustering of Applications with Noise)''' - плотностный алгоритм для кл…»

2016-10-15T20:04:13Z

Новая страница: «{{Assignment}} Алгоритм '''DBSCAN (Density Based Spatial Clustering of Applications with Noise)''' - плотностный алгоритм для кл…»

Новая страница

{{Assignment}}

Алгоритм '''DBSCAN (Density Based Spatial Clustering of Applications with Noise)''' - плотностный алгоритм для кластеризации пространственных данных с присутствием шума), был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы. Большинство алгоритмов, производящих плоское разбиение, создают кластеры по форме близкие к сферическим, так как минимизируют расстояние до центра кластера. Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы.

= ЧАСТЬ. Свойства и структура алгоритма =
Кластеризация – это процесс разбиения множества элементов на непересекающиеся кластеры, так, чтобы в каждом кластере все элементы были схожи в каком-то смысле, а объекты разных кластеров существенно отличались.

== Общее описание алгоритма ==
Идея, положенная в основу алгоритма, заключается в том, что внутри каждого кластера наблюдается типичная плотность точек (объектов), которая заметно выше, чем плотность снаружи кластера, а также плотность в областях с шумом ниже плотности любого из кластеров. Ещё точнее, что для каждой точки кластера её соседство заданного радиуса должно содержать не менее некоторого числа точек, это число точек задаётся пороговым значением. Алгоритм DBSCAN для заданных значений параметров <math>\varepsilon</math> и MinPts исследует кластер следующим образом: сначала выбирает случайную точку, являющуюся ядровой, в качестве затравки, затем помещает в кластер саму затравку и все точки, плотно-достижимые из неё.

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

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

Вычисляемые данные: разбиение объектов по кластерам. Количество кластеров зависит от исходных данных.

Для построения оценки плотности, на основе соседства точек вводятся понятия достижимости и связности. Под <math>\varepsilon</math> -соседями точки <math>x \in X</math> понимается множество точек, расстояние до которых не превышает <math>\varepsilon</math> , т. е. <math>N_\varepsilon (x) = \{y \in X | D(x, y) \le \varepsilon\}.</math> Тогда точка y достижима из точки <math>x</math>, если существует последовательность точек <math>x^{(1)}=x, x^{(2)},... , x^{(p-1)}, x^{(p)}=y</math>, для которой выполнено:

<math>\begin{align}
x^{(i+1)} \in N_\varepsilon (x^{(i)}), i=1,... ,p-1 \\
\mid N_\varepsilon (x^{(i)}) \mid \ge MinPts, i=1,... ,p-1
\end{align}</math>

Здесь значение <math>MinPts</math> задаётся пользователем и регулирует порог «шума». Согласно второму условию, у точек, находящихся внутри кластера, должно быть не менее <math>MinPts \ \varepsilon</math> -соседей. Такие точки называются «ядрами». Остальные точки разделяются на граничные (имеющие менее <math>MinPts \ \varepsilon</math> -cоседей, но достижимые из какого-либо «ядра») и шумовые. Две точки связны, если существует «ядро», из которого они обе достижимы. При такой постановке задачи, под кластером понимается максимальное связное подмножество множества X . Точки, не попавшие в какой-либо кластер (не принадлежащие <math>\varepsilon</math> -окрестности какого-либо «ядра»), относятся к классу «шум».

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

Вычислительное ядро последовательной версии зависти от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки. Из-за поиска <math>\varepsilon</math>-соседства алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если задействовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

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

Алгоритм DBSCAN использует пространственную структуру данных для определения соседних объектов. Это может быть R*-дерево или k-d дерево. Такие структуры данных позволяют найти все объекты в пределах определенного расстояния от текущего объекта. Также для построения этих деревьев нужно уметь находить расстояние между объектами <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>

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

Алгоритм начинает работу с произвольной точки <math>x \in X</math> и возвращает <math>\varepsilon</math> -окрестность(строка 4). Если <math>\varepsilon</math>-окрестность содержит, как минимум minpts точек, процедура выдает новый кластер C. Алгоритм извлекает все точки в X, которые являются плотность достижима из x и добавляет их в кластер C(строки 8-17). Если в <math>\varepsilon</math>-окрестности x точек меньше, чем minpts, то x помечается как шум(строка 6). Однако, х все еще может быть добавлены в кластер, если она определится как пограничная точка во время изучения других основных точек(строки 16-17). Поиск точек в <math>\varepsilon</math>-окрестности(функция GETNEIGHBORS)известен, как запрос в диапазоне значений и получает все плотностно достижимые точки от главной точки(строки 8-17) известный как алгоритм наращивания областей. Заметим что кластер может быть определен однозначно, начиная с любой "ядровой" точки.

1: procedure DBSCAN(X, eps, minpts)
2: for each unvisited point x ∈ X do
3: mark x as visited
4: N ← GETNEIGHBORS(x, eps)
5: if |N| < minpts then
6: mark x as noise
7: else
8: C ← {x}
9: for each point x' ∈ N do
10: N ← N \ x'
11: if x' is not visited then
12: mark x' as visited
13: N' ← GETNEIGHBORS(x', eps)
14: if |N'| ≥ minpts then
15: N ← N ∪ N'
16: if x' is not yet member of any cluster then
17: C ← C ∪ {x'}

== Последовательная сложность алгоритма ==

В общем случае алгоритм DBSCAN имеет квадратичную вычислительную сложность <math>O(n^2)</math>(где n это количество точек в X) из-за поиска <math>\varepsilon</math>-соседства. Но если использовать пространственную индексацию (например, использую k-мерное дерево[5] или R-дерево) для поиска <math>\varepsilon</math>-соседства, сложность снижается до <math>O(n log n)</math>[6].

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

На рисунке 1 представлен информационный граф алгоритма кластеризации DBSCAN. На входе у нас множество точек <math>P_i</math> и мы пробегаем по всем непосещенным точкам. Далее мы, для каждой непосещенной точки, маркируем ее как посещенную и находим всех её <math>\varepsilon</math>-соседей(на графике это узел <math>G</math>). Добавляем точку к кластеру(узел <math>C</math>). Затем, пробегаем по всем плотностно-достижимых точках(<math>P_j</math>) к нашей точке, и для каждой такой точки ищем <math>\varepsilon</math>-сосдей и добавляем их в кластер, если они ещё не принадлежат никакому кластеру.

[[file:Информационный_граф.png|thumb|center|700px|Рис.1 Граф алгоритма без отображения входных и выходных данных. <math>P_i</math> и <math>P_j</math> - точки данного множества, <math>G</math> - поиск <math>\varepsilon</math>-соседей, <math>C</math> - добавление элемента к кластеру.]]

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

Поиск <math>\varepsilon</math>-соседей требует вычисления n расстояний и выполнения n сравнений с <math>\varepsilon</math>. Эти операции для каждой пары точек независимы и могут быть выполнены параллельно. Таким образом, при наличии неограниченного числа процессоров сложность поиска составит O(1). Так как поиск выполняется для каждой точки ровно один раз, параллельная сложность всего алгоритма составит O(n).

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

Входные данные: набор точек x, пороговое расстояние <math>\varepsilon</math>, а также минимальное количество точек, необходимых для формирования кластера, minpts.

Выход: множество кластеров С.

Если указать маленькое значение <math>\varepsilon</math>, то все точки будут шумом. Если наоборот, сделать большое значение, то кластер не будет разбит, возьмет один кластер и включит в него все точки. Также, если взять minpts слишком большое или слишком маленькое, будет либо один кластер, либо все точки шумовые. Оптимальные значения находятся опытным путем.

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

=== Преимущества алгоритма ===
* не требует указать априори количество кластеров, в отличие от K-средства

* алгоритм может разбить на произвольной формы кластеры. Даже может выявить кластер находящийся внутри другого, но не пересекающийся с ним. Из-за параметра MinPts снижается так называемый эффект однолокальности(single-link)

* алгоритм имеет понятие "шума" и устойчив к выбросам

* алгоритм требует всего два параметра и в основном нечувствительны к упорядоченности изначально данных точек

* параметры MinPts и <math>\varepsilon</math> могут быть установлены, экспертами в какой-либо области, если данные хорошо изучены.

=== Недостатки алгоритма ===

* алгоритм не совсем детерминирован: пограничные точки, которые доступны из более чем одного кластера могут быть частью любого кластера, в зависимости от того, как происходит обработка данных. К счастью, эта ситуация не часто возникают, и мало влияет на результат кластеризации. На основных точках и точках "шума", алгоритм детерминирован. Есть DBSCAN[7] который представляет собой вариант, который рассматривает пограничные пункты как шум, и таким образом достигается полностью детерминированный результат, а также более последовательной статистической интерпретации плотности соединенных компонентов.

* качество алогоритма зависит от меры, которую мы рассматриваем в пространстве. Наиболее распространенная мера использует евклидово расстояние.

* если данные и масштаб не очень хорошо поняты, выбирание значимого расстояния порогового <math>\varepsilon</math> может быть затруднено.

* алгоритм не может кластеризовать данные хорошо с большими различиями в плотности

= ЧАСТЬ. Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

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

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

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

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

* Ester, Martin, et al. "A density-based algorithm for discovering clusters in large spatial databases with noise." Kdd. Vol. 96. No. 34. 1996.

* Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.

* Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.

* Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.

* A. Zhou, S. Zhou, J. Cao, Y. Fan, and Y. Hu, “Approaches for scaling DBSCAN algorithm to large spatial databases,” Journal of computer science and technology, vol. 15, no. 6, pp. 509–526, 2000.

*J. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975.

*Campello, R. J. G. B.; Moulavi, D.; Sander, J. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery in Databases, PAKDD 2013. Lecture Notes in Computer Science. p. 160.