DBSCAN

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

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

Популярное продолжение HDBSCAN* было первоначально опубликовано Рикардо Дж. Кампелло, Дэвидом Мулави и Йоргом Сандером в 2013 году. ^[6] затем расширен с Артуром Зимеком в 2015 году. ^[7] Он пересматривает некоторые первоначальные решения, такие как пограничные точки, и дает иерархический, а не однородный результат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

DBSCAN(DB, distFunc, eps, minPts) {
    C := 0                                                  /* Cluster counter */
    for each point P in database DB {
        if label(P) ≠ undefined then continue               /* Previously processed in inner loop */
        Neighbors N := RangeQuery(DB, distFunc, P, eps)     /* Find neighbors */
        if |N| < minPts then {                              /* Density check */
            label(P) := Noise                               /* Label as Noise */
            continue
        }
        C := C + 1                                          /* next cluster label */
        label(P) := C                                       /* Label initial point */
        SeedSet S := N \ {P}                                /* Neighbors to expand */
        for each point Q in S {                             /* Process every seed point Q */
            if label(Q) = Noise then label(Q) := C          /* Change Noise to border point */
            if label(Q) ≠ undefined then continue           /* Previously processed (e.g., border point) */
            label(Q) := C                                   /* Label neighbor */
            Neighbors N := RangeQuery(DB, distFunc, Q, eps) /* Find neighbors */
            if |N| ≥ minPts then {                          /* Density check (if Q is a core point) */
                S := S ∪ N                                  /* Add new neighbors to seed set */
            }
        }
    }
}

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

RangeQuery(DB, distFunc, Q, eps) {
    Neighbors N := empty list
    for each point P in database DB {                      /* Scan all points in the database */
        if distFunc(Q, P) ≤ eps then {                     /* Compute distance and check epsilon */
            N := N ∪ {P}                                   /* Add to result */
        }
    }
    return N
}

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

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

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

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

Критерий оптимизации [ править ]

DBSCAN оптимизирует следующую функцию потерь: ^[10] Для любой возможной кластеризации $C=\{C_{1},\ldots ,C_{l}\}$ из множества всех кластеризаций ${\mathcal {C}}$ , он минимизирует количество кластеров при условии, что каждая пара точек в кластере достижима по плотности, что соответствует двум исходным свойствам «максимальность» и «связность» кластера: ^[1]

\min _{C\subset {\mathcal {C}},~d_{db}(p,q)\leq \varepsilon ~\forall p,q\in C_{i}~\forall C_{i}\in C}|C|

где $d_{db}(p,q)$ дает самый маленький $\varepsilon$ такие, что две точки $p$ и $q$ плотносвязны.

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

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

DBSCAN может находить нелинейно разделимые кластеры. Этот набор данных не может быть адекватно кластеризован с помощью k-средних или EM-кластеризации гауссовой смеси.

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

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

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

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

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

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

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

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

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

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

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

Спектральная реализация DBSCAN связана со спектральной кластеризацией в тривиальном случае определения компонентов связного графа — оптимальных кластеров без разрезанных ребер. ^[12] Однако это может потребовать больших вычислительных ресурсов, вплоть до $O(n^{3})$ . Кроме того, необходимо выбрать количество собственных векторов для вычисления. По соображениям производительности исходный алгоритм DBSCAN остается предпочтительнее его спектральной реализации.

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

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

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

Наличие [ править ]

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

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

Примечания [ править ]

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

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

^ Jump up to: Перейти обратно: ^а ^б ^с ^д Эстер, Мартин ; Кригель, Ханс-Петер ; Сандер, Йорг; Сюй, Сяовэй (1996). Симудис, Евангелос; Хан, Цзявэй; Файяд, Усама М. (ред.). Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом (PDF) . Материалы Второй Международной конференции по обнаружению знаний и интеллектуальному анализу данных (KDD-96). АААИ Пресс . стр. 226–231. CiteSeerX 10.1.1.121.9220 . ISBN 1-57735-004-9 .
^ «Microsoft Academic Search: статьи» . Архивировано из оригинала 21 апреля 2010 года . Проверено 18 апреля 2010 г. Наиболее цитируемые статьи по интеллектуальному анализу данных согласно академическому поиску Microsoft; DBSCAN находится на 24 месте.
^ «Премия SIGKDD «Испытание временем 2014»» . АСМ СИГКДД. 18 августа 2014 г. Проверено 27 июля 2016 г.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Шуберт, Эрих; Сандер, Йорг; Эстер, Мартин; Кригель, Ганс Петер ; Сюй, Сяовэй (июль 2017 г.). «Возвращение к DBSCAN, еще раз: почему и как вам следует (все еще) использовать DBSCAN» . АКМ Транс. Система баз данных . 42 (3): 19:1–19:21. дои : 10.1145/3068335 . ISSN 0362-5915 . S2CID 5156876 .
^ «ТОДС Дом» . tods.acm.org . Ассоциация вычислительной техники . Проверено 16 июля 2020 г.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Кампелло, Рикардо Дж.Г.Б.; Мулави, Давуд; Сандер, Йорг (2013). Пей, Цзянь; Ценг, Винсент С.; Цао, Лунбин; Мотода, Хироши (ред.). Кластеризация на основе плотности на основе оценок иерархической плотности . Достижения в области обнаружения знаний и интеллектуального анализа данных. Том. 7819. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 160–172. дои : 10.1007/978-3-642-37456-2_14 . ISBN 978-3-642-37455-5 . Проверено 18 августа 2023 г.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Кампелло, Рикардо Дж.Г.Б.; Мулави, Давуд; Зимек, Артур ; Сандер, Йорг (2015). «Оценки иерархической плотности для кластеризации данных, визуализации и обнаружения выбросов». Транзакции ACM по извлечению знаний из данных . 10 (1): 1–51. дои : 10.1145/2733381 . ISSN 1556-4681 . S2CID 2887636 .
^ Jump up to: Перейти обратно: ^а ^б Линг, РФ (1 января 1972 г.). «К теории и построению k-кластеров» . Компьютерный журнал . 15 (4): 326–332. дои : 10.1093/comjnl/15.4.326 . ISSN 0010-4620 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Сандер, Йорг; Эстер, Мартин; Кригель, Ханс-Петер ; Сюй, Сяовэй (1998). «Кластеризация на основе плотности в пространственных базах данных: алгоритм GDBSCAN и его приложения». Интеллектуальный анализ данных и обнаружение знаний . 2 (2). Берлин: Springer-Verlag : 169–194. Бибкод : 1998DMKD....2..169S . дои : 10.1023/А:1009745219419 . S2CID 445002 .
^ Пиво, Анна; Драганов, Андрей; Хохма, Эллен; Ян, Филипп; Фрей, Кристиан ММ; Согласие, Ира (6 августа 2023 г.). «Соединение точек: расстояние между плотностью и связностью объединяет DBSCAN, k-центр и спектральную кластеризацию» . Материалы 29-й конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . АКМ. стр. 80–92. дои : 10.1145/3580305.3599283 . ISBN 9798400701030 . S2CID 260499476 .
^ Кригель, Ханс-Петер ; Крегер, Пер; Сандер, Йорг; Зимек, Артур (2011). «Кластеризация на основе плотности» . WIREs Интеллектуальный анализ данных и обнаружение знаний . 1 (3): 231–240. дои : 10.1002/widm.30 . S2CID 36920706 . Архивировано из оригинала 17 ноября 2016 г. Проверено 12 декабря 2011 г.
^ Шуберт, Эрих; Гесс, Сибилла; Морик, Катарина (2018). Связь DBSCAN с матричной факторизацией и спектральной кластеризацией (PDF) . Обучение, знания, данные, аналитика (LWDA). стр. 330–334 – через CEUR-WS.org.
^ Сандер, Йорг (1998). Обобщенная кластеризация на основе плотности для интеллектуального анализа пространственных данных . Мюнхен: Герберт Утц Верлаг. ISBN 3-89675-469-6 .
^ Кампелло, RJGB; Мулави, Д.; Зимек, А. ; Сандер, Дж. (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-9] Jump up to: Перейти обратно: ^а ^б Хотя minPts интуитивно представляет собой минимальный размер кластера, в некоторых случаях DBSCAN может создавать кластеры меньшего размера. ^[4] Кластер DBSCAN состоит как минимум из одной базовой точки . ^[4] Поскольку другие точки могут быть граничными точками для более чем одного кластера, нет гарантии, что хотя бы точки minPts включены в каждый кластер.

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

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

[3] «Премия SIGKDD «Испытание временем 2014»» . АСМ СИГКДД. 18 августа 2014 г. Проверено 27 июля 2016 г.

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

[5] «ТОДС Дом» . tods.acm.org . Ассоциация вычислительной техники . Проверено 16 июля 2020 г.

[hdbscan1-6] Jump up to: Перейти обратно: ^а ^б ^с ^д Кампелло, Рикардо Дж.Г.Б.; Мулави, Давуд; Сандер, Йорг (2013). Пей, Цзянь; Ценг, Винсент С.; Цао, Лунбин; Мотода, Хироши (ред.). Кластеризация на основе плотности на основе оценок иерархической плотности . Достижения в области обнаружения знаний и интеллектуального анализа данных. Том. 7819. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 160–172. дои : 10.1007/978-3-642-37456-2_14 . ISBN 978-3-642-37455-5 . Проверено 18 августа 2023 г.

[hdbscan2-7] Jump up to: Перейти обратно: ^а ^б ^с ^д Кампелло, Рикардо Дж.Г.Б.; Мулави, Давуд; Зимек, Артур ; Сандер, Йорг (2015). «Оценки иерархической плотности для кластеризации данных, визуализации и обнаружения выбросов». Транзакции ACM по извлечению знаний из данных . 10 (1): 1–51. дои : 10.1145/2733381 . ISSN 1556-4681 . S2CID 2887636 .

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

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

[11] Пиво, Анна; Драганов, Андрей; Хохма, Эллен; Ян, Филипп; Фрей, Кристиан ММ; Согласие, Ира (6 августа 2023 г.). «Соединение точек: расстояние между плотностью и связностью объединяет DBSCAN, k-центр и спектральную кластеризацию» . Материалы 29-й конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . АКМ. стр. 80–92. дои : 10.1145/3580305.3599283 . ISBN 9798400701030 . S2CID 260499476 .

[WIREs-12] Кригель, Ханс-Петер ; Крегер, Пер; Сандер, Йорг; Зимек, Артур (2011). «Кластеризация на основе плотности» . WIREs Интеллектуальный анализ данных и обнаружение знаний . 1 (3): 231–240. дои : 10.1002/widm.30 . S2CID 36920706 . Архивировано из оригинала 17 ноября 2016 г. Проверено 12 декабря 2011 г.

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[а]

[9]

[10]

[11]

[12]

[13]

[14]

[15]