DBSCAN - DBSCAN

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

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

История

В 1972 году Роберт Ф. Линг опубликовал тесно связанный алгоритм в «Теории и построении k-кластеров» в The Computer Journal с оценочной сложностью выполнения O (n³). 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 . Плотность связность является симметричной.

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

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

Алгоритм

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

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

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

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

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

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 можно разделить на следующие шаги:

  1. Найдите точки в окрестности ε (eps) каждой точки и идентифицируйте основные точки с более чем minPts соседей.
  2. Найти связные компоненты из ключевых точек на соседней графе, игнорируя все непрофильные точки.
  3. Назначьте каждую неосновную точку соседнему кластеру, если кластер является соседом ε (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.

Преимущества

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

Недостатки

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

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

Оценка параметров

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

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

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

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

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

DBSCAN можно рассматривать как специальный (эффективный) вариант спектральной кластеризации : соединенные компоненты соответствуют оптимальным спектральным кластерам (без обрезания краев - спектральная кластеризация пытается разделить данные с минимальным вырезом ); DBSCAN находит связанные компоненты на (асимметричном) графе достижимости. Однако спектральная кластеризация может потребовать значительных вычислительных ресурсов (вплоть до без аппроксимации и дополнительных предположений), и нужно выбрать количество кластеров как для количества собственных векторов, так и для количества кластеров, которые необходимо произвести с помощью k-средних при спектральном вложении. . Таким образом, по соображениям производительности исходный алгоритм DBSCAN остается предпочтительным по сравнению со спектральной реализацией, и это соотношение пока представляет только теоретический интерес.

Расширения

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

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

Доступность

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

  • 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, которая работает с квадратичным временем и линейной памятью.

Примечания

использованная литература