DBSCAN - DBSCAN

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

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

История

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

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

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

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

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

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

minPts = 4

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

ε

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

Абстрактный алгоритм

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

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

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

Сложность

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

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

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

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

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

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

Расширения

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

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

Доступность

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

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

Примечания

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