Основанная на плотности пространственная кластеризация для приложений с шумами (, DBSCAN) — это алгоритм кластеризации данных, который предложили Мартин Эстер, Ганс-Петер Кригель, Йёрг Сандер и Сюй Сяовэй в 1996. Это алгоритм кластеризации, основанной на плотности: если дан набор точек в некотором пространстве, алгоритм группирует вместе точки, которые тесно расположены (точки со многими ), помечая как выбросы точки, которые находятся одиноко в областях с малой плотностью (ближайшие соседи которых лежат далеко). DBSCAN является одним из наиболее часто используемых алгоритмов кластеризации, и наиболее часто упоминается в научной литературе.
В 2014 алгоритм получил премию «проверено временем» (премия даётся алгоритмам, которые получили существенное внимание в теории и практике) на ведущей конференции по интеллектуальному анализу данных, KDD.
Ранние варианты В 1972 Роберт Ф. Линг уже опубликовал статью с названием «Теория и построение k-кластеров» () в журнале со сходным алгоритмом с оценкой сложности вычисления . DBSCAN же имеет сложность в худшем случае , а позволяет ускорение по индексу. Алгоритмы отличаются в их обработке граничных точек.
Подготовка Рассмотрим набор точек в некотором пространстве, требующий кластеризации. Для выполнения кластеризации DBSCAN точки делятся на основные точки, прямо достижимые по плотности точки, достижимые точки и выбросы следующим образом:
Точка является основной точкой, если по меньшей мере точек находятся на расстоянии, не превосходящем ( является максимальным радиусом соседства от ), до неё (включая саму точку ). Говорят, что эти точки достижимы прямо из . Точка прямо достижима из , если точка находится на расстоянии, не большем , от основной точки . Точка достижима из , если имеется путь с и , где каждая точка достижима прямо из (все точки на пути должны быть основными, за исключением ). Все точки, не достижимые из основных точек, считаются выбросами.
Теперь, если является основной точкой, то она формирует кластер вместе со всеми точками (основными или неосновными), достижимые из этой точки. Каждый кластер содержит по меньшей мере одну основную точку. Неосновные точки могут быть частью кластера, но они формируют его «край», поскольку не могут быть использованы для достижения других точек.
Достижимость не является симметричным отношением, поскольку, по определению, никакая точка не может быть достигнута из неосновной точки, независимо от расстояния (так что неосновная точка может быть достижимой, но ничто не может быть достигнуто из неё). Поэтому дальнейшее понятие связности необходимо для формального определения области кластеров, найденных алгоритмом DBSCAN. Две точки и связаны по плотности, если имеется точка , такая что и , и достижимы из . Связность по плотности является симметричной.
Тогда кластер удовлетворяет двум свойствам: Все точки в кластере попарно связны по плотности. Если точка достижима по плотности из какой-то точки кластера, она также принадлежит кластеру.
Алгоритм
Оригинальный алгоритм, основанный на запросах DBSCAN требует задания двух параметров: и минимального числа точек, которые должны образовывать плотную областьВ то время как minPts, интуитивно, является минимальным размером кластера, в некоторых случаях DBSCAN может дать меньшие кластеры . Кластер DBSCAN состоит из по меньшей мере одной основной точки. Так как другие точки могут быть граничными точками более чем одного кластера, нет гарантии, что по меньшей мере minPts точек включаются в каждый кластер. (minPts). Алгоритм начинается с произвольной точки, которая ещё не просматривалась. Выбирается -окрестность точки и, если она содержит достаточно много точек, образуется кластер, в противном случае точка помечается как шум. Заметим, что эта точка может быть позже найдена в -окрестности другой точки и включена в какой-то кластер.
Если точка найдена как плотная точка кластера, её -окрестность также является частью этого кластера. Следовательно, все точки, найденные в -окрестности этой точки, добавляются к кластеру. Этот процесс продолжается, пока не будет найден связный по плотности кластер. Затем выбирается и обрабатывается новая непосещённая точка, что ведёт к обнаружению следующего кластера или шума.
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, ) { Neighbors=empty list for each point P in database DB { /* Scan all points in the database */ if then { /* Compute distance and check epsilon */ Neighbors=Neighbors ∪ {P} /* Add to result */
return Neighbors
Абстрактный алгоритм Алгоритм DBSCAN может быть разложен на следующие шаги:
Находим точки в окрестности каждой точки и выделяем основные точки с более чем minPts соседями. Находим связные компоненты основных точек на графе соседей, игнорируя все неосновные точки. Назначаем каждую неосновную ближайшему кластеру, если кластер является -соседним, в противном случае считаем точку шумом.
Наивная реализация алгоритма требует запоминания соседей на шаге 1, так что требует существенной памяти. Оригинальный алгоритм DBSCAN не требует этого за счёт того, что выполняет эти шаги для одной точки за раз.
Сложность DBSCAN посещает каждую точку базы данных, может быть несколько раз (например, как кандидаты в другие кластеры). По опыту эксплуатации, однако, временна́я сложность в основном регулируются числом запросов regionQuery. DBSCAN выполняет в точности один такой запрос для каждой точки и, если используется индексная структура, которая выполняет за время , получаем полную среднюю временну́ю сложность (если параметр выбирается осмысленно, то есть так, что в среднем возвращается только точек). Без использования ускоряющей индексной структуры или на вырожденных данных (например, когда все точки находятся на расстоянии меньше чем ), худшим случаем времени работы остаётся . Матрица расстояний размера может быть вычислена во избежание перевычисления расстояний, но это требует памяти , в то время как реализация DBSCAN без матрицы расстояний требует лишь памяти.
Преимущества DBSCAN не требует априорного указания числа кластеров в данных, в отличие от метода k-средних. DBSCAN может найти кластеры произвольной формы. Он может найти даже кластеры, полностью окружённые (но не связанные с) другими кластерами. Благодаря параметру MinPts уменьшается так называемый эффект одной связи (связь различных кластеров тонкой линией точек). DBSCAN имеет понятие шума и устойчив к выбросам. DBSCAN требует лишь двух параметров и большей частью нечувствителен к порядку точек в базе данных. (Однако точки, находящиеся на границе двух различных кластеров, могут оказаться в другом кластере, если изменить порядок точек, а назначение кластеров единственно с точностью до изоморфизма.) DBSCAN разработан для применения с базами данных, которые позволяют ускорить запросы в диапазоне значений, например, с помощью R*-дерева. Параметры minPts и могут быть установлены экспертами в рассматриваемой области, если данные хорошо интерпретируются.
Недостатки DBSCAN не полностью однозначен — краевые точки, которые могут быть достигнуты из более чем одного кластера, могут принадлежать любому из этих кластеров, что зависит от порядка просмотра точек. Для большинства наборов данных эти ситуации возникают редко и имеют малое влияние на результат кластеризации — основные точки и шум DBSCAN обрабатывает однозначно. DBSCAN* является вариантом, который трактует краевые точки как шум и тем самым достигается полностью однозначный результат, а также более согласованная статистическая интерпретация связных по плотности компонент. Качество DBSCAN зависит от измерения расстояния, используемого в функции regionQuery(P,ε). Наиболее часто используемой метрикой расстояний является евклидова метрика. Особенно для кластеризации эта метрика может оказаться почти бесполезной ввиду так называемого «проклятия размерности», что делает трудным делом нахождение подходящего значения . Этот эффект, однако, присутствует в любом другом алгоритме, основанном на евклидовом расстоянии. DBSCAN не может хорошо кластеризовать наборы данных с большой разницей в плотности, поскольку не удается выбрать приемлемую для всех кластеров комбинацию . Если данные и масштаб не вполне хорошо поняты, выбор осмысленного порога расстояния может оказаться трудным.
См. раздел ниже о расширениях для алгоритмических модификаций, имеющих дело с этими проблемами.
Оценка параметров Любая задача интеллектуальной обработки данных имеет проблему параметров. Любой параметр специфично влияет на алгоритм. Для алгоритма DBSCAN нужны параметры и minPts. Параметры должны быть определены пользователем. В идеале, значение определяется решаемой задачей (например, физические расстояния), а minPts определяет тогда минимальный желаемый размер кластера.
MinPts: Как показывает опыт, минимальное значение minPts может быть получено из размерности D набора данных как . Низкое значение minPts=1 не имеет смысла, так как тогда любая точка будет кластером. Для результат будет тем же самым, что и иерархическая кластеризация с метрикой единичного соединения с отсечением дендрограммы на высоте . Поэтому minPts должен быть равным как минимум 3. Однако, для наборов данных с шумами бо́льшие значения обычно лучше, и дают более существенные кластеры. Опыт подсказывает, что может быть использовано значение , но может оказаться необходимым выбор большего значения для больших наборов данных, для данных с шумом или для данных, содержащих много дубликатов. : Значение может быть выбрано с помощью графа k-расстояний, вычерчивая расстояние к () ближайшему соседу в порядке от большего к меньшему. Хорошие значения те, где график имеет «изгиб» — если выбрана слишком малыми, большая часть данных не будет кластеризована, а для слишком больших значений кластеры будут сливаться и большинство объектов окажутся в одном кластере. Обычно малые значения предпочтительнее и опыт показывает, что только небольшая доля точек должна быть с этим расстоянием друг от друга. Альтернативно, может быть использован график OPTICS для выбора , но тогда и сам алгоритм OPTICS может быть использован для кластеризации. Функция расстояния: Выбор функции расстояния сильно связан с выбором и имеет большое влияние на результаты. Обычно сначала необходимо определить обоснованные меры похожести набора данных, прежде чем выбирать параметр . Нет оценок для этого параметра, но функции расстояния следует выбирать согласно набору данных. Например, для географических данных, расстояние по дуге большого круга часто будет хорошим выбором.