DBSCAN

Машинное обучение и интеллектуальный анализ данных
Часть серии по

Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Глоссарий искусственного интеллекта Глоссарий искусственного интеллекта
Статьи по Теме Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

Пространственная кластеризация приложений с шумом на основе плотности ( DBSCAN ) - это алгоритм кластеризации данных , предложенный Мартином Эстером , Хансом-Петером Кригелем , Йоргом Сандером и Сяовей Сюй в 1996 году. ^[1] Это непараметрический алгоритм кластеризации на основе плотности : учитывая набор точек в некотором пространстве, он группирует точки, которые плотно упакованы вместе (точки с множеством ближайших соседей ), отмечая как выбросы точки, которые лежат одни в регионах с низкой плотностью (ближайшие соседи которых находятся слишком далеко). DBSCAN - один из наиболее распространенных алгоритмов кластеризации, который также наиболее цитируется в научной литературе. ^[2]

В 2014 году алгоритм был удостоен награды «Проверка временем» (награда, присуждаемая алгоритмам, получившим значительное внимание в теории и практике) на ведущей конференции по интеллектуальному анализу данных ACM SIGKDD . ^[3] По состоянию на июль 2020 года ^{[Обновить]}, последующий документ «DBSCAN Revisited, Revisited: Почему и как вы должны (все еще) использовать DBSCAN» ^[4] появляется в списке 8 наиболее загружаемых статей престижного журнала ACM Transactions on Database. Системный журнал (TODS) . ^[5]

История [ править ]

В 1972 году Роберт Ф. Линг опубликовал тесно связанный алгоритм в «Теории и построении k-кластеров» ^[6] в The Computer Journal с оценочной сложностью выполнения O (n³). ^[6] DBSCAN имеет наихудший случай O (n²), а формулировка запроса диапазона DBSCAN, ориентированная на базу данных, позволяет ускорить индексирование. Алгоритмы немного отличаются в обработке пограничных точек.

Предварительный [ править ]

Рассмотрим набор точек в некотором пространстве для кластеризации. Пусть $ε$ - параметр, определяющий радиус окрестности относительно некоторой точки. Для целей кластеризации DBSCAN точки классифицируются как основные точки , ( плотность -) достижимые точки и выбросы следующим образом:

Точка $p$ является базовой, если хотя бы $minPts$ точек находятся на расстоянии $ε$ от нее (включая $p$ ).
Точка $д$ является непосредственно достижим из $р$ , если точка $д$ находится в пределах расстояния $е$ от основной точки $р$ . Говорят, что точки доступны только напрямую из основных точек.
Точка $д$ является достижимым из $р$ , если существует путь $р 1, ..., р п$ с $р 1 = р$ и $р п = д$ , где каждый $р я + 1$ находится непосредственно достижима из $р я$ . Обратите внимание, что это означает, что начальная точка и все точки на пути должны быть основными, за возможным исключением $q$ .
Все точки, недоступные из других точек, являются выбросами или точками шума .

Теперь, если $p$ является базовой точкой, то она образует кластер вместе со всеми точками (основными или неосновными), которые достижимы из него. Каждый кластер содержит по крайней мере одну точку ядра; Неосновные точки могут быть частью кластера, но они образуют его «край», поскольку их нельзя использовать для достижения большего количества точек.

На этой диаграмме

minPts = 4

. Точка A и другие красные точки являются основными, потому что область, окружающая эти точки в радиусе

ε,

содержит не менее 4 точек (включая саму точку). Поскольку все они доступны друг от друга, они образуют единый кластер. Точки B и C не являются базовыми точками, но достижимы из A (через другие базовые точки) и, следовательно, также принадлежат кластеру. Точка N - это шумовая точка, которая не является ни основной, ни напрямую достижимой.

Достижимость не является симметричным отношением: по определению, только основные точки могут достигать неосновных точек. Обратное неверно, поэтому неосновная точка может быть достижима, но из нее ничего не может быть достигнуто. Следовательно, необходимо дополнительное понятие связности, чтобы формально определить размер кластеров, обнаруженных DBSCAN. Две точки $p$ и $q$ связаны плотностью, если существует точка $o$ такая, что обе точки $p$ и $q$ достижимы из точки $o$ . Плотность связность является симметричной.

Тогда кластер удовлетворяет двум свойствам:

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

Алгоритм [ править ]

Исходный алгоритм на основе запросов [ править ]

DBSCAN требует двух параметров: ε (eps) и минимальное количество точек, необходимых для формирования плотной области ^[a] (minPts). Он начинается с произвольной начальной точки, которая еще не была посещена. Восстанавливается ε-окрестность этой точки, и если она содержит достаточно много точек, запускается кластер. В противном случае точка помечается как шум. Обратите внимание, что эта точка может позже быть найдена в ε-среде достаточного размера другой точки и, следовательно, быть сделана частью кластера.

Если точка оказывается плотной частью кластера, ее ε-окрестность также является частью этого кластера. Следовательно, все точки, найденные в ε-окрестности, добавляются, как и их собственная ε-окрестность, когда они также плотны. Этот процесс продолжается до тех пор, пока плотно связанный кластер не будет полностью найден. Затем извлекается и обрабатывается новая непосещенная точка, что приводит к обнаружению следующего кластера или шума.

DBSCAN может использоваться с любой функцией расстояния ^[1]^[4] (а также функциями подобия или другими предикатами). ^[7] Таким образом, функцию расстояния (dist) можно рассматривать как дополнительный параметр.

В псевдокоде алгоритм можно представить следующим образом: ^[4]

DBSCAN (DB, distFunc, eps, minPts) { C: = 0 / * Счетчик кластера * /  для каждой точки P в базе данных DB { если метка (P) ≠ undefined, то  продолжить  / * Ранее обработано во внутреннем цикле * / Соседи N: = RangeQuery (DB, distFunc, P, eps) / * Находим соседей * /  if | N | <minPts then { / * Проверка плотности * / label (P): = Noise / * Label as Noise * /  continue } C: = C + 1 / * следующая метка кластера * / label (P): = C / * Начальная точка метки * / SeedSet S: = N \ {P} / * Соседи для расширения * /  для каждой точки Q в S { / * Обработка каждой начальной точки Q * /  если метка (Q) = Шум, затем метка (Q): = C / * Измените шум на граничную точку * /  если метка (Q) ≠ undefined, то  продолжить  / * Ранее обработано (например, граница точка) * / label (Q): = C / * Обозначить соседа * / Nighbors N: = RangeQuery (DB, distFunc, Q, eps) / * Найти соседей * /  if | N | ≥ minPts, затем { / * Проверка плотности (если Q - центральная точка) * / S: = S ∪ N / * Добавление новых соседей в начальный набор * / } } }}

где RangeQuery может быть реализован с использованием индекса базы данных для повышения производительности или с помощью медленного линейного сканирования:

RangeQuery (DB, distFunc, Q, eps) { Соседи N: = пустой список для каждой точки P в базе данных DB { / * Сканировать все точки в базе данных * /  если distFunc (Q, P) ≤ eps, то { / * Вычислить расстояние и проверить эпсилон * / N: = N ∪ {P} / * Добавить в результат */ } } вернуть N}

Абстрактный алгоритм [ править ]

Алгоритм DBSCAN можно разделить на следующие шаги: ^[4]

Найдите точки в окрестности ε (eps) каждой точки и идентифицируйте основные точки с более чем minPts соседей.
Найти связные компоненты из ключевых точек на соседней графе, игнорируя все непрофильные точки.
Назначьте каждую неосновную точку соседнему кластеру, если кластер является соседом ε (eps), в противном случае назначьте ее шуму.

Наивная реализация этого требует сохранения окрестностей на шаге 1, что требует значительного объема памяти. Исходный алгоритм DBSCAN не требует этого, выполняя эти шаги для одной точки за раз.

Сложность [ править ]

DBSCAN посещает каждую точку базы данных, возможно, несколько раз (например, в качестве кандидатов в разные кластеры). Однако из практических соображений сложность времени в основном определяется количеством вызовов regionQuery. DBSCAN выполняет ровно один такой запрос для каждой точки, и если используется структура индексации, которая выполняет запрос соседства в $O (log n)$ , общая средняя сложность времени выполнения получается $O (n log n)$ (если параметр $ε$ выбран в осмысленный способ, т.е. такой, что в среднем только $O (log n)$ баллы возвращаются). Без использования структуры ускоряющегося индекса или вырожденных данных (например, всех точек на расстоянии меньше $ε$ ) сложность времени выполнения наихудшего случая остается $O (n ²)$ . Матрица расстояний размера $(n ²- n) / 2$ может быть материализована, чтобы избежать повторных вычислений расстояния, но для этого требуется $O (n ²)$ памяти, тогда как нематричной реализации DBSCAN требуется только $O (n)$ памяти.

DBSCAN может находить нелинейно разделимые кластеры. Этот набор данных не может быть адекватно кластеризован с помощью К-средних или ЭМ-кластеризации Gaussian Mixture.

Преимущества [ править ]

В DBSCAN не требуется указывать количество кластеров в данных априори, в отличие от k-средних .
DBSCAN может находить кластеры произвольной формы. Он даже может найти кластер, полностью окруженный (но не связанный) с другим кластером. За счет параметра MinPts снижается так называемый эффект одиночной связи (разные кластеры соединяются тонкой линией точек).
DBSCAN имеет понятие шума и устойчив к выбросам .
DBSCAN требует всего два параметра и по большей части нечувствителен к порядку точек в базе данных. (Однако точки, расположенные на краю двух разных кластеров, могут поменять членство в кластере, если порядок точек изменился, а назначение кластера уникально только с точностью до изоморфизма.)
DBSCAN разработан для использования с базами данных, которые могут ускорять запросы по регионам, например, с использованием дерева R * .
Параметры minPts и ε могут быть установлены экспертом в предметной области, если данные хорошо изучены.

Недостатки [ править ]

DBSCAN не является полностью детерминированным: пограничные точки, доступные из более чем одного кластера, могут быть частью любого кластера, в зависимости от порядка обработки данных. Для большинства наборов данных и доменов такая ситуация возникает нечасто и мало влияет на результат кластеризации: ^[4] DBSCAN детерминирован как по основным, так и по шумовым точкам. DBSCAN * ^[8] - это вариант, который рассматривает граничные точки как шум, и таким образом достигается полностью детерминированный результат, а также более последовательная статистическая интерпретация связанных с плотностью компонентов.
Качество DBSCAN зависит от меры расстояния, используемой в функции regionQuery (P, ε). Наиболее распространенная метрика расстояния - евклидово расстояние . Эта метрика может оказаться практически бесполезной из-за так называемого « проклятия размерности », особенно для данных большой размерности , что затрудняет поиск подходящего значения для ε. Однако этот эффект присутствует и в любом другом алгоритме, основанном на евклидовом расстоянии.
DBSCAN не может хорошо кластеризовать наборы данных с большими различиями в плотности, поскольку комбинация minPts-ε не может быть выбрана надлежащим образом для всех кластеров. ^[9]
Если данные и масштаб не совсем понятны, выбор значимого порогового значения расстояния ε может быть затруднительным.

См. Ниже раздел о расширениях для алгоритмических модификаций для решения этих проблем.

Оценка параметров [ править ]

У каждой задачи интеллектуального анализа данных есть проблема параметров. Каждый параметр определенным образом влияет на алгоритм. Для DBSCAN необходимы параметры ε и minPts . Параметры должны быть указаны пользователем. В идеале значение ε задается задачей, которую необходимо решить (например, физическое расстояние), и minPts тогда является желаемым минимальным размером кластера. ^[а]

MinPts : Как показывает практика, минимальное значение minPts может быть получено из количества измерений D в наборе данных, поскольку minPts ≥ D + 1. Низкое значение minPts = 1 не имеет смысла, поскольку тогда каждая точка на его Собственный уже будет кластер. ^{[ сомнительно - обсудить ]} При minPts ≤ 2 результат будет таким же, как и при иерархической кластеризации с метрикой одиночной связи, с разрезом дендрограммы на высоте ε. Следовательно, minPtsдолжно быть выбрано не менее 3. Однако большие значения обычно лучше для наборов данных с шумом и дают более значимые кластеры. Как правило, можно использовать minPts = 2 · dim ^[7], но может потребоваться выбрать большие значения для очень больших данных, для данных с шумом или для данных, содержащих много дубликатов. ^[4]
ε: значение для ε можно затем выбрать, используя график k-расстояний , построив расстояние до ближайшего соседа k = minPts -1, упорядоченное от наибольшего к наименьшему значению. ^[4] Хорошие значения ε находятся там, где этот график показывает «изгиб»: ^[1]^[7]^[4] если ε выбрано слишком маленьким, большая часть данных не будет кластеризована; тогда как при слишком высоком значении ε кластеры будут сливаться, и большинство объектов будут в одном кластере. Как правило, предпочтительны небольшие значения ε ^[4], и, как показывает практический опыт, только небольшая часть точек должна находиться на этом расстоянии друг от друга. В качестве альтернативы можно использовать график OPTICS для выбора ε,^[4], но тогда для кластеризации данных можно использовать сам алгоритм OPTICS.
Функция расстояния: выбор функции расстояния тесно связан с выбором ε и оказывает большое влияние на результаты. Как правило, необходимо сначала определить разумную меру сходства для набора данных, прежде чем можно будет выбрать параметр ε. Для этого параметра нет оценки, но функции расстояния должны быть выбраны надлежащим образом для набора данных. Например, для географических данных расстояние по дуге большого круга часто является хорошим выбором.

ОПТИКУ можно рассматривать как обобщение DBSCAN, в котором параметр ε заменяется максимальным значением, которое в основном влияет на производительность. Таким образом, MinPts становится минимальным размером кластера, который нужно найти. Хотя алгоритм намного проще параметризовать, чем DBSCAN, результаты немного сложнее использовать, поскольку он обычно дает иерархическую кластеризацию вместо простого разделения данных, которое производит DBSCAN.

Недавно один из первоначальных авторов DBSCAN пересмотрел DBSCAN и OPTICS и опубликовал усовершенствованную версию иерархического DBSCAN (HDBSCAN *) ^{[8], в} которой больше нет понятия пограничных точек. Вместо этого только основные точки образуют кластер.

Связь со спектральной кластеризацией [ править ]

DBSCAN можно рассматривать как специальный (эффективный) вариант спектральной кластеризации : соединенные компоненты соответствуют оптимальным спектральным кластерам (без обрезания краев - спектральная кластеризация пытается разделить данные с минимальным вырезом ); DBSCAN находит связанные компоненты на (асимметричном) графе достижимости. ^[10] Однако спектральная кластеризация может потребовать значительных вычислительных ресурсов (вплоть до без аппроксимации и дополнительных предположений), и необходимо выбрать количество кластеров. ${\ Displaystyle О (п ^ {3})}$ ${\ displaystyle k}$ как для числа выбираемых собственных векторов, так и для числа кластеров, которые необходимо создать с помощью k-средних при спектральном вложении. Таким образом, по соображениям производительности исходный алгоритм DBSCAN остается предпочтительным по сравнению со спектральной реализацией, и это соотношение пока представляет только теоретический интерес.

Расширения [ править ]

Обобщенный DBSCAN (GDBSCAN) ^[7]^[11] является обобщением тех же авторов для произвольных «соседних» и «плотных» предикатов. Параметры ε и minPts удаляются из исходного алгоритма и перемещаются в предикаты. Например, для данных многоугольника «соседство» может быть любым пересекающимся многоугольником, тогда как предикат плотности использует площади многоугольника, а не только количество объектов.

Были предложены различные расширения алгоритма DBSCAN, включая методы распараллеливания, оценки параметров и поддержки неопределенных данных. Основная идея была расширена до иерархической кластеризации с помощью алгоритма OPTICS . DBSCAN также используется как часть алгоритмов кластеризации подпространств, таких как PreDeCon и SUBCLU . HDBSCAN ^[8] - это иерархическая версия DBSCAN, которая также быстрее, чем OPTICS, из которой можно извлечь плоский раздел, состоящий из наиболее заметных кластеров, из иерархии. ^[12]

Доступность [ править ]

Было обнаружено, что разные реализации одного и того же алгоритма демонстрируют огромные различия в производительности: самая быстрая из тестовых данных завершается за 1,4 секунды, а самая медленная - за 13803 секунды. ^[13] Различия можно объяснить качеством реализации, различиями в языке и компиляторах, а также использованием индексов для ускорения.

Apache Commons Math содержит Java-реализацию алгоритма, работающего в квадратичном времени.
ELKI предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индекса для субквадратичной среды выполнения и поддерживает функции произвольного расстояния и произвольные типы данных, но она может уступать в производительности низкоуровневым оптимизированным (и специализированным) реализациям для небольших наборов данных.
mlpack включает реализацию DBSCAN, ускоренную с помощью методов поиска по двойному дереву.
PostGIS включает ST_ClusterDBSCAN - двухмерную реализацию DBSCAN, использующую индекс R-tree. Поддерживается любой тип геометрии, например Point, LineString, Polygon и т. Д.
R содержит реализации DBSCAN в пакетах dbscan и fpc . Оба пакета поддерживают произвольные функции расстояния через матрицы расстояний. Пакет fpc не имеет поддержки индекса (и, следовательно, имеет квадратичное время выполнения и сложность памяти) и работает довольно медленно из-за интерпретатора R. Пакет dbscan обеспечивает быструю реализацию C ++ с использованием деревьев kd (только для евклидова расстояния), а также включает реализации DBSCAN *, HDBSCAN *, OPTICS, OPTICSXi и других связанных методов.
scikit-learn включает Python-реализацию DBSCAN для произвольных метрик Минковского , которую можно ускорить с помощью деревьев kd и шаровых деревьев, но которая использует квадратичную память наихудшего случая. Вклад в scikit учиться обеспечивает реализацию алгоритма HDBSCAN *.
Библиотека pyclustering включает Python и C ++ реализацию DBSCAN только для евклидова расстояния, а также алгоритм OPTICS.
SPMF включает реализацию алгоритма DBSCAN с поддержкой дерева kd только для евклидова расстояния.
Weka содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает с квадратичным временем и линейной памятью.

Заметки [ править ]

^ a b Хотя minPts интуитивно является минимальным размером кластера, в некоторых случаях DBSCAN может создавать кластеры меньшего размера. ^[4] Кластер DBSCAN состоит как минимум из одной базовой точки . ^[4] Поскольку другие точки могут быть граничными точками для более чем одного кластера, нет гарантии, что хотя бы точки minPts включены в каждый кластер.

Ссылки [ править ]

^ a b c Эстер, Мартин; Кригель, Ханс-Петер ; Сандер, Йорг; Сюй, Сяовэй (1996). Симудис, Эвангелос; Хан, Цзявэй; Файяд, Усама М. (ред.). Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом . Труды Второй Международной конференции по открытию знаний и интеллектуальному анализу данных (KDD-96). AAAI Press . С. 226–231. CiteSeerX 10.1.1.121.9220 . ISBN 1-57735-004-9.
^ "Архивная копия" . Архивировано из оригинального 21 апреля 2010 года . Проверено 18 апреля 2010 .CS1 maint: заархивированная копия как заголовок ( ссылка )Наиболее цитируемые статьи по интеллектуальному анализу данных согласно академическому поиску Microsoft; DBSCAN находится на 24 месте.
^ "2014 SIGKDD Test of Time Award" . ACM SIGKDD. 2014-08-18 . Проверено 27 июля 2016 .
^ Б с д е е г ч я J K L Шуберта, Эрих; Сандер, Йорг; Эстер, Мартин; Кригель, Ганс Петер ; Сюй, Сяовэй (июль 2017 г.). «Возвращение к DBSCAN, повторение: почему и как (по-прежнему) следует использовать DBSCAN» . ACM Trans. База данных Syst . 42 (3): 19: 1–19: 21. DOI : 10.1145 / 3068335 . ISSN 0362-5915 . S2CID 5156876 .
^ "TODS Home" . tods.acm.org . Ассоциация вычислительной техники . Проверено 16 июля 2020 .
^ а б Линг, РФ (1972-01-01). «К теории и построению k-кластеров» . Компьютерный журнал . 15 (4): 326–332. DOI : 10.1093 / comjnl / 15.4.326 . ISSN 0010-4620 .
^ a b c d Сандер, Йорг; Эстер, Мартин; Кригель, Ханс-Петер ; Сюй, Сяовэй (1998). «Кластеризация на основе плотности в пространственных базах данных: алгоритм GDBSCAN и его приложения». Интеллектуальный анализ данных и обнаружение знаний . Берлин: Springer-Verlag . 2 (2): 169–194. DOI : 10,1023 / A: 1009745219419 . S2CID 445002 .
^ a b c Кампелло, Рикардо Дж.Б. Мулави, Давуд; Зимек, Артур ; Сандер, Йорг (2015). «Иерархические оценки плотности для кластеризации данных, визуализации и обнаружения выбросов». ACM-транзакции при обнаружении знаний из данных . 10 (1): 1–51. DOI : 10.1145 / 2733381 . ISSN 1556-4681 . S2CID 2887636 .
^ Кригель, Ганс-Петер ; Крегер, Пер; Сандер, Йорг; Зимек, Артур (2011). «Кластеризация на основе плотности» . WIREs Data Mining и Knowledge Discovery . 1 (3): 231–240. DOI : 10.1002 / widm.30 .
^ Шуберт, Эрих; Гесс, Сибилла; Морик, Катарина (2018). Связь DBSCAN с матричной факторизацией и спектральной кластеризацией (PDF) . Lernen, Wissen, Daten, Analysen (LWDA). С. 330–334 - через CEUR-WS.org.
^ Сандер, Йорг (1998). Обобщенная кластеризация на основе плотности для интеллектуального анализа пространственных данных . Мюнхен: Герберт Утц Верлаг. ISBN 3-89675-469-6.
^ Кампелло, RJGB; Moulavi, D .; Зимек, А .; Сандер, Дж. (2013). «Фреймворк для полууправляемого и неконтролируемого оптимального извлечения кластеров из иерархий». Интеллектуальный анализ данных и обнаружение знаний . 27 (3): 344. DOI : 10.1007 / s10618-013-0311-4 . S2CID 8144686 .
^ Кригель, Ганс-Петер ; Шуберт, Эрих; Зимек, Артур (2016). «(Черное) искусство оценки времени выполнения: сравниваем ли мы алгоритмы или реализации?». Знания и информационные системы . 52 (2): 341. DOI : 10.1007 / s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .

[minpts-7] Хотя minPts интуитивно является минимальным размером кластера, в некоторых случаях DBSCAN может создавать кластеры меньшего размера. ^[4] Кластер DBSCAN состоит как минимум из одной базовой точки . ^[4] Поскольку другие точки могут быть граничными точками для более чем одного кластера, нет гарантии, что хотя бы точки minPts включены в каждый кластер.

[dbscan-1] Эстер, Мартин; Кригель, Ханс-Петер ; Сандер, Йорг; Сюй, Сяовэй (1996). Симудис, Эвангелос; Хан, Цзявэй; Файяд, Усама М. (ред.). Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом . Труды Второй Международной конференции по открытию знаний и интеллектуальному анализу данных (KDD-96). AAAI Press . С. 226–231. CiteSeerX 10.1.1.121.9220 . ISBN 1-57735-004-9.

[2] "Архивная копия" . Архивировано из оригинального 21 апреля 2010 года . Проверено 18 апреля 2010 .CS1 maint: заархивированная копия как заголовок ( ссылка )Наиболее цитируемые статьи по интеллектуальному анализу данных согласно академическому поиску Microsoft; DBSCAN находится на 24 месте.

[3] "2014 SIGKDD Test of Time Award" . ACM SIGKDD. 2014-08-18 . Проверено 27 июля 2016 .

[tods-4] Б с д е е г ч я J K L Шуберта, Эрих; Сандер, Йорг; Эстер, Мартин; Кригель, Ганс Петер ; Сюй, Сяовэй (июль 2017 г.). «Возвращение к DBSCAN, повторение: почему и как (по-прежнему) следует использовать DBSCAN» . ACM Trans. База данных Syst . 42 (3): 19: 1–19: 21. DOI : 10.1145 / 3068335 . ISSN 0362-5915 . S2CID 5156876 .

[5] "TODS Home" . tods.acm.org . Ассоциация вычислительной техники . Проверено 16 июля 2020 .

[:1-6] а б Линг, РФ (1972-01-01). «К теории и построению k-кластеров» . Компьютерный журнал . 15 (4): 326–332. DOI : 10.1093 / comjnl / 15.4.326 . ISSN 0010-4620 .

[:0-8] Сандер, Йорг; Эстер, Мартин; Кригель, Ханс-Петер ; Сюй, Сяовэй (1998). «Кластеризация на основе плотности в пространственных базах данных: алгоритм GDBSCAN и его приложения». Интеллектуальный анализ данных и обнаружение знаний . Берлин: Springer-Verlag . 2 (2): 169–194. DOI : 10,1023 / A: 1009745219419 . S2CID 445002 .

[hdbscan1-9] Кампелло, Рикардо Дж.Б. Мулави, Давуд; Зимек, Артур ; Сандер, Йорг (2015). «Иерархические оценки плотности для кластеризации данных, визуализации и обнаружения выбросов». ACM-транзакции при обнаружении знаний из данных . 10 (1): 1–51. DOI : 10.1145 / 2733381 . ISSN 1556-4681 . S2CID 2887636 .

[WIREs-10] Кригель, Ганс-Петер ; Крегер, Пер; Сандер, Йорг; Зимек, Артур (2011). «Кластеризация на основе плотности» . WIREs Data Mining и Knowledge Discovery . 1 (3): 231–240. DOI : 10.1002 / widm.30 .

[11] Шуберт, Эрих; Гесс, Сибилла; Морик, Катарина (2018). Связь DBSCAN с матричной факторизацией и спектральной кластеризацией (PDF) . Lernen, Wissen, Daten, Analysen (LWDA). С. 330–334 - через CEUR-WS.org.

[12] Сандер, Йорг (1998). Обобщенная кластеризация на основе плотности для интеллектуального анализа пространственных данных . Мюнхен: Герберт Утц Верлаг. ISBN 3-89675-469-6.

[13] Кампелло, RJGB; Moulavi, D .; Зимек, А .; Сандер, Дж. (2013). «Фреймворк для полууправляемого и неконтролируемого оптимального извлечения кластеров из иерархий». Интеллектуальный анализ данных и обнаружение знаний . 27 (3): 344. DOI : 10.1007 / s10618-013-0311-4 . S2CID 8144686 .

[14] Кригель, Ганс-Петер ; Шуберт, Эрих; Зимек, Артур (2016). «(Черное) искусство оценки времени выполнения: сравниваем ли мы алгоритмы или реализации?». Знания и информационные системы . 52 (2): 341. DOI : 10.1007 / s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .