DBSCAN

Основанная на плотности пространственная кластеризация для приложений с шумами (англ. Density-based spatial clustering of applications with noise, DBSCAN) — это алгоритм кластеризации данных, который предложили Мартин Эстер, Ганс-Петер Кригель, Йёрг Сандер и Сюй Сяовэй в 1996. Это алгоритм кластеризации, основанной на плотности: если дан набор точек в некотором пространстве, алгоритм группирует вместе точки, которые тесно расположены (точки со многими близкими соседями), помечая как выбросы точки, которые находятся одиноко в областях с малой плотностью (ближайшие соседи которых лежат далеко). DBSCAN является одним из наиболее часто используемых алгоритмов кластеризации, и наиболее часто упоминается в научной литературе.

В 2014 алгоритм получил премию «проверено временем» (премия даётся алгоритмам, которые получили существенное внимание в теории и практике) на ведущей конференции по интеллектуальному анализу данных, KDD.

Ранние варианты

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

Подготовка

Рассмотрим набор точек в некотором пространстве, требующий кластеризации. Для выполнения кластеризации DBSCAN точки делятся на основные точки, прямо достижимые по плотности точки, достижимые точки и выбросы следующим образом:

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

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

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

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

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

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

Алгоритм

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

DBSCAN требует задания двух параметров: $\epsilon$ и минимального числа точек, которые должны образовывать плотную область (minPts). Алгоритм начинается с произвольной точки, которая ещё не просматривалась. Выбирается $\epsilon$-окрестность точки и, если она содержит достаточно много точек, образуется кластер, в противном случае точка помечается как шум. Заметим, что эта точка может быть позже найдена в $\epsilon$-окрестности другой точки и включена в какой-то кластер.

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

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

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

DBSCAN(DB, distFunc, eps, minPts) {
   C=0                                                  /* Счётчик кластеров */
   for each point P in database DB {
      if label(P) ≠ undefined then continue               /* Точка была просмотрена во внутреннем цикле */
      Neighbors N=RangeQuery(DB, distFunc, P, eps)      /* Находим соседей */
      if|N|< minPts then {                              /* Проверка плотности */
         label(P)=Noise                                 /* Помечаем как шум */
         continue
      }
      C=C + 1                                           /* следующая метка кластера */
      label(P)=C                                        /* Помечаем начальную точку */
      Seed set S=N \ {P}                                /* Соседи для расширения */
      for each point Q in S {                             /* Обрабатываем каждую зачаточную точку */
         if label(Q)=Noise then label(Q)=C            /* Заменяем метку Шум на Край */
         if label(Q) ≠ undefined then continue            /* Была просмотрена */
         label(Q)=C                                     /* Помечаем соседа */
         Neighbors N=RangeQuery(DB, distFunc, Q, eps)   /* Находим соседей */
         if|N|≥ minPts then {                           /* Проверяем плотность */
            S=S ∪ N                                     /* Добавляем соседей в набор зачаточных точек */
         }
      }
   }
}

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

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

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

Алгоритм DBSCAN может быть разложен на следующие шаги:

1. Находим точки в $\epsilon$ окрестности каждой точки и выделяем основные точки с более чем minPts соседями.
2. Находим связные компоненты основных точек на графе соседей, игнорируя все неосновные точки.
3. Назначаем каждую неосновную ближайшему кластеру, если кластер является $\epsilon$-соседним, в противном случае считаем точку шумом.

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

Сложность

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

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

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

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

Недостатки

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

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

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

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

• MinPts: Как показывает опыт, минимальное значение minPts может быть получено из размерности D набора данных как $minPts\geqslant D+1$. Низкое значение minPts=1 не имеет смысла, так как тогда любая точка будет кластером. Для $minPts\leqslant 2$ результат будет тем же самым, что и иерархическая кластеризация с метрикой единичного соединения с отсечением дендрограммы на высоте $\epsilon$. Поэтому minPts должен быть равным как минимум 3. Однако, для наборов данных с шумами бо́льшие значения обычно лучше, и дают более существенные кластеры. Опыт подсказывает, что может быть использовано значение $minPts=2\cdot dim$, но может оказаться необходимым выбор большего значения для больших наборов данных, для данных с шумом или для данных, содержащих много дубликатов.
• $\epsilon$: Значение $\epsilon$ может быть выбрано с помощью графа k-расстояний, вычерчивая расстояние к ($k=minPts-1$) ближайшему соседу в порядке от большего к меньшему. Хорошие значения $\epsilon$ те, где график имеет «изгиб» — если $\epsilon$ выбрана слишком малыми, большая часть данных не будет кластеризована, а для слишком больших значений $\epsilon$ кластеры будут сливаться и большинство объектов окажутся в одном кластере. Обычно малые значения $\epsilon$ предпочтительнее и опыт показывает, что только небольшая доля точек должна быть с этим расстоянием друг от друга. Альтернативно, может быть использован график OPTICS для выбора $\epsilon$, но тогда и сам алгоритм OPTICS может быть использован для кластеризации.
• Функция расстояния: Выбор функции расстояния сильно связан с выбором $\epsilon$ и имеет большое влияние на результаты. Обычно сначала необходимо определить обоснованные меры похожести набора данных, прежде чем выбирать параметр $\epsilon$. Нет оценок для этого параметра, но функции расстояния следует выбирать согласно набору данных. Например, для географических данных, расстояние по дуге большого круга часто будет хорошим выбором.

OPTICS можно рассматривать как обобщение DBSCAN, в котором параметр $\epsilon$ заменяется максимальным значением, наиболее воздействущим на эффективность. MinPts тогда становится минимальным размером кластера. Хотя алгоритм существенно проще в области выбора параметров, чем DBSCAN, его результаты труднее использовать, так как он обычно даёт иерархическую кластеризацию вместо простого разделения, которое даёт DBSCAN.

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

Расширения

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

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

Доступность

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

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