DBSCAN 🔍

Банк ежедневно обрабатывает миллионы транзакций, и подавляющее большинство из них — рутинные покупки, укладывающиеся в привычные паттерны конкретного клиента: примерно одна и та же сумма, примерно одно и то же время суток, примерно одни и те же категории магазинов. Такие транзакции образуют плотные скопления в пространстве признаков — тысячи похожих точек рядом друг с другом. А мошенническая транзакция обычно ведёт себя иначе: она нетипична, выбивается из привычного паттерна, стоит особняком. Если применить к этим данным k-means (урок 320) или иерархическую кластеризацию (урок 321), оба метода обязаны отнести абсолютно каждую точку к какому-то кластеру — мошенническая транзакция получит номер ближайшей группы «нормального» поведения и растворится среди легитимных операций, вместо того чтобы быть замеченной. DBSCAN устроен принципиально иначе: он способен сказать «эта точка не похожа ни на один плотный регион данных» и явно пометить её как шум, а не притворяться, что у неё есть подходящий кластер.

Название DBSCAN расшифровывается как Density-Based Spatial Clustering of Applications with Noise — «пространственная кластеризация приложений на основе плотности с шумом»; в тексте этого урока алгоритм всюду называется именно DBSCAN, как это принято и в русскоязычной литературе, и в документации sklearn.cluster.DBSCAN. Уже в названии зашита главная идея: кластеры определяются через плотность точек, а не через расстояние до центра или последовательное объединение по дереву, и шум — не досадная помеха, которую нужно куда-то пристроить, а полноправная, явно выделяемая категория.

В прошлых двух уроках ты разобрал два фундаментальных ограничения, с которыми регулярно сталкиваются на практике. K-means (урок 320) требует заранее знать число кластеров $k$ и минимизирует сумму квадратов расстояний до центроидов, из-за чего находит только компактные, примерно сферические кластеры сопоставимого размера — а на данных другой формы или при неизвестном $k$ начинает откровенно ошибаться. Иерархическая кластеризация (урок 321) решает проблему незнания $k$ — она строит дерево всех возможных разбиений и позволяет выбрать число кластеров уже после построения дендрограммы, — но по-прежнему в конце концов относит каждую точку к одной из ветвей дерева, не давая ей возможности остаться «ничьей». DBSCAN решает сразу обе эти проблемы за счёт другого взгляда на то, что вообще такое кластер: не заранее заданное число групп и не узел дерева, а связная область, где точек локально много.

Сегодняшний урок устроен так: сначала разберём историю алгоритма, затем — почему его вообще понадобилось изобретать, то есть конкретные ограничения k-means и иерархической кластеризации, которые DBSCAN снимает. После этого — два параметра, которыми управляется весь алгоритм ($\varepsilon$ и minPts), классификация точек на три типа (корневые, граничные и шумовые) с полным разбором на конкретном числовом датасете, и, наконец, сам алгоритм построения кластеров через связывание корневых точек. Каждый раздел содержит формальное определение и разобранные числовые примеры — их стоит проследить с карандашом в руках, а не просто прочитать.

История

DBSCAN предложили в 1996 году четверо исследователей из Мюнхенского университета имени Людвига и Максимилиана (Ludwig-Maximilians-Universität München): Мартин Эстер (Martin Ester), Ханс-Петер Кригель (Hans-Peter Kriegel), Йорг Сандер (Jörg Sander) и Сяовэй Сюй (Xiaowei Xu). Их статья «A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise» была представлена на конференции KDD-96 (Knowledge Discovery and Data Mining) — одной из ключевых конференций по анализу данных того времени.

Мотивация была вполне прикладной: команда работала с пространственными базами данных — географическими и картографическими данными, где нужно было находить регионы повышенной плотности объектов (например, скопления точек на карте) без двух вещей, которые в геопространственных задачах особенно неудобны. Во-первых, без необходимости заранее знать, сколько именно таких регионов существует — на карте города количество «районов повышенной плотности» магазинов или происшествий заранее неизвестно и может меняться от датасета к датасету. Во-вторых, без ограничения на форму этих регионов — реальные географические скопления редко бывают аккуратными кругами или эллипсами, а k-means того времени именно такую форму и предполагал.

Идея оказалась настолько удачной, что вышла далеко за пределы геопространственных задач и стала одним из самых цитируемых алгоритмов кластеризации в машинном обучении в целом. В 2014 году, спустя 18 лет после публикации, оригинальная статья получила премию SIGKDD «Проверка временем» (англ. SIGKDD Test of Time Award) — награду, которую присуждают за работы, показавшие долгосрочное фундаментальное влияние на область; DBSCAN оказался в числе первых лауреатов этой премии. Позже та же исследовательская группа развила идею дальше: в 1999 году появился OPTICS (англ. Ordering Points To Identify the Clustering Structure — «упорядочивание точек для выявления структуры кластеризации»), снимающий необходимость фиксировать единственное значение $\varepsilon$ заранее, а в 2013 году независимая команда (Кампелло, Мойзес, Сандер) предложила HDBSCAN — иерархическое расширение DBSCAN, о котором мы ещё вспомним в конце урока.

Ограничения k-means и иерархической кластеризации: зачем нужен DBSCAN

Интуиция

Представь, что тебе нужно найти на карте города скопления кафе. K-means подошёл бы к задаче так: «раздели все кафе города ровно на $k$ групп так, чтобы средняя удалённость кафе от центра своей группы была минимальной» — но при этом абсолютно каждое кафе, включая единственную случайную точку общепита на отшибе в промзоне, обязано попасть в одну из этих $k$ групп, а сами группы по построению получаются компактными и выпуклыми. Иерархическая кластеризация подошла бы иначе — «сначала объедини два ближайших кафе, потом ещё два ближайших (или ближайшую пару кластеров), и так далее, пока не останется одна большая группа», — и тебе не нужно знать $k$ заранее, но по-прежнему нужно в какой-то момент разрезать получившееся дерево на конечное число частей, и опять же каждое кафе окажется в какой-то части, сколь угодно от неё удалённое. DBSCAN подходит к задаче принципиально иначе: «найди районы, где кафе стоят достаточно плотно друг к другу, и объяви их кластерами; одинокое кафе в промзоне, вокруг которого пусто, — просто не входит ни в какой район» — никакого заранее заданного числа групп и никакой обязанности всех распределить.

Формула

От разбиения всей выборки — к связным областям высокой плотности. Классические методы кластеризации, которые ты уже разобрал, — k-means и иерархическая кластеризация — вычисляют разбиение всего множества точек $X=\{x_1,\dots,x_n\}$ на ровно $k$ непустых групп, минимизируя некоторый глобальный критерий (сумму квадратов расстояний до центроидов для k-means, суммарное расстояние объединения для linkage-функций иерархической кластеризации), и по построению обязаны отнести каждую без исключения точку выборки к одной из этих $k$ групп. DBSCAN определяет кластер иначе — не как часть разбиения на заданное число групп, а как максимальную связную область высокой плотности точек (формальное определение — в разделе про алгоритм построения кластеров), и явно допускает, что часть точек данных не принадлежит ни одному кластеру.

Разбор примеров

Пример 1 (k-means насильно присваивает выброс ближайшему центроиду). Возьмём пять транзакций типичного клиента с признаками (стандартизированная сумма, стандартизированное время суток): $(0{,}1;\,0{,}0)$, $(0{,}2;\,0{,}1)$, $(-0{,}1;\,0{,}2)$, $(0{,}0;\,-0{,}1)$, $(0{,}1;\,0{,}1)$ — все они укладываются в тесный диапазон около нуля. Шестая транзакция — потенциально мошенническая — имеет признаки $(8{,}0;\,7{,}0)$, то есть аномально большая сумма в нетипичное время. Запустим k-means с $k=1$ (одна «нормальная» группа): центроид сместится с примерно $(0{,}06;\,0{,}06)$ (среднее по пяти типичным точкам) до $(1{,}37;\,1{,}22)$ (среднее по всем шести точкам вместе с выбросом) — сама аномальная точка утягивает центр «нормального» кластера в свою сторону, а при $k=2$ будет вынуждена образовать отдельный кластер из одной точки только потому, что мы заранее указали два центроида, — но k-means не скажет тебе явно «это аномалия», он просто разложит все шесть точек по $k$ группам, какими бы ни были эти группы по смыслу.

Пример 2 (кластеры невыпуклой формы — k-means режет их поперёк). Представь данные, образующие два вложенных концентрических кольца: внешнее кольцо радиуса $\approx 5$ и внутреннее кольцо радиуса $\approx 1$, с общим центром в начале координат. Геометрический центроид (среднее по всем координатам) обоих колец при этом почти совпадает — он находится примерно в той же точке $(0,0)$, вокруг которой физически нет ни одной точки данных ни одного из колец. K-means с $k=2$, минимизируя расстояние до центроидов, неизбежно делит плоскость на две половины лучами из общего центра (что-то вроде «верхняя половина против нижней»), разрезая при этом каждое из двух колец пополам, а не выделяя внутреннее и внешнее кольцо как два целостных кластера. Дело не в неудачной инициализации центроидов — при любой инициализации оптимум минимизируемой k-means функции для этой геометрии физически не совпадает с «правильным» с точки зрения формы данных разбиением.

Пример 3 (иерархическая кластеризация: число кластеров всё ещё нужно указать при разрезании). Построим дендрограмму для датасета из десяти транзакций тем же способом, что в уроке 321. Дендрограмма честно покажет всю последовательность объединений — от отдельных точек до одного общего кластера, — но чтобы получить конкретное разбиение, дендрограмму всё равно нужно разрезать на определённой высоте, и эта высота выбирается человеком (визуально, по эвристике вроде наибольшего вертикального «разрыва» между уровнями объединения). Если аномальная транзакция значительно удалена от остальных, она объединится с ближайшим кластером на самом последнем, самом высоком уровне дендрограммы — и при разрезании на любое разумное число частей $k \ge 2$ окажется приписана к какой-то из этих частей, а не помечена отдельно как «эта точка вообще не вписывается в структуру данных». Получить её как самостоятельный «шум», а не как полноценный кластер или часть чужого кластера, средствами одной лишь иерархической кластеризации напрямую нельзя.

Почему это важно

Оба ограничения — обязательность заранее известного $k$ и обязательность отнесения каждой точки к какому-то кластеру — не мелкие технические неудобства, а следствия самого способа, которым k-means и иерархическая кластеризация определяют, что такое кластер: через глобальную оптимизацию расстояний до центроидов или через последовательное попарное объединение. DBSCAN меняет само определение кластера на локальное — «плотная связная область» — и именно из-за этой смены определения оба ограничения снимаются одновременно и естественным образом, а не патчем поверх старого алгоритма: число кластеров становится следствием структуры плотности данных, а не входным параметром, а шум становится законной третьей категорией точек наравне с «принадлежит кластеру A» и «принадлежит кластеру B».

Параметры ε и minPts

Интуиция

Всё поведение DBSCAN определяется всего двумя числами. Первое — радиус $\varepsilon$ (эпсилон): насколько далеко от точки стоит заглядывать в поисках соседей, своего рода «зона видимости» каждой точки. Второе — minPts: сколько точек должно оказаться в этой зоне видимости, чтобы место считалось «достаточно людным», плотным. Если в переполненном вагоне метро ты стоишь и можешь дотянуться рукой (радиус $\varepsilon$) до как минимум ещё четырёх человек (minPts), вокруг тебя точно людно; если в радиусе вытянутой руки — только пустое пространство, ты стоишь в разрежённой, не плотной зоне вагона. Оба параметра задаются вручную перед запуском алгоритма, и весь дальнейший результат — какие точки окажутся корневыми, какие кластеры образуются, сколько точек уйдёт в шум — целиком определяется этими двумя числами.

Формула

ε-окрестность точки. Для точки $p \in X$ и радиуса $\varepsilon > 0$ ε-окрестность определяется как множество всех точек выборки, находящихся от $p$ на расстоянии не больше $\varepsilon$ — включая саму точку $p$, поскольку расстояние от точки до самой себя равно нулю:

$$N_\varepsilon(p) = \{q \in X : d(p, q) \le \varepsilon\}$$

Точка $p$ считается корневой (core point), если её ε-окрестность содержит не менее minPts точек: $|N_\varepsilon(p)| \ge \text{minPts}$. Именно так это определили Эстер и соавторы в оригинальной статье 1996 года, и именно так считает параметр min_samples в sklearn.cluster.DBSCAN: он включает саму точку, поэтому корневой точке нужно ровно $\text{minPts}-1$ других соседей в радиусе $\varepsilon$, помимо неё самой.

Разбор примеров

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

Зафиксируем на первое время $\varepsilon = 1{,}5$, $\text{minPts}=4$ (то есть 3 других соседа плюс сама точка).

Пример 1 (ε слишком маленький — всё превращается в шум). Возьмём то же самое расположение точек, но радиус $\varepsilon = 0{,}5$. Минимальное расстояние между любыми двумя различными точками датасета равно $1$ (например, $d(T_1,T_2)=1$) — то есть меньше, чем удвоенный радиус $\varepsilon=0{,}5$ ни для одной пары точек не выполняется. Значит ε-окрестность любой точки содержит только её саму: $|N_{0{,}5}(p)|=1$ для всех десяти точек. При minPts$=4$ ни одна точка не набирает нужного числа соседей — корневых точек не остаётся вовсе, и все десять точек становятся шумом. Слишком маленький $\varepsilon$ делает DBSCAN бесполезным: он не видит вообще никакой плотности там, где она объективно есть.

Пример 2 (ε слишком большой — всё сливается в один кластер). Теперь возьмём $\varepsilon = 4{,}5$ при том же minPts$=4$. Расстояние от $T_6(4,4)$ до $T_4(1,1)$ равно $\sqrt{3^2+3^2}=\sqrt{18}\approx 4{,}2426 \le 4{,}5$, расстояние до $T_5(2;0{,}5)$ равно $\sqrt{2^2+3{,}5^2}=\sqrt{16{,}25}\approx 4{,}0311 \le 4{,}5$, а расстояние до всех четырёх точек группы B ($T_7$–$T_{10}$) — не больше $\sqrt{2^2+2^2}=\sqrt8\approx 2{,}8284 \le 4{,}5$. Значит при этом радиусе $N_{4{,}5}(T_6)$ содержит саму $T_6$ плюс $T_4$, $T_5$, $T_7$, $T_8$, $T_9$, $T_{10}$ — семь точек, что больше minPts$=4$, и бывшая «подозрительная одиночка» $T_6$ сама становится корневой точкой. А поскольку $T_6$ одновременно попадает в радиус группы A (через $T_4$, $T_5$) и группы B (через $T_7$–$T_{10}$), она напрямую связывает обе группы в одну общую цепочку плотностной достижимости. Результат: весь датасет из десяти точек, включая бывшую аномалию, сливается в один сплошной кластер, ни одной шумовой точки не остаётся — слишком большой $\varepsilon$ убивает саму идею отделять «плотное» от «редкого».

Пример 3 (minPts слишком большой относительно фактической плотности данных). Вернёмся к исходному $\varepsilon=1{,}5$, но поднимем minPts с $4$ до $6$. Максимальное число соседей (включая себя), которое вообще способна набрать любая точка этого датасета при $\varepsilon=1{,}5$, — пять (у точек $T_2$ и $T_4$ из группы A) и четыре (у всех точек группы B). И пять, и четыре меньше шести. Значит при minPts$=6$ ни одна точка датасета не удовлетворяет условию корневой — корневых точек не остаётся вовсе, и все десять точек становятся шумом, хотя визуально в данных отчётливо видны две плотные группы. Слишком большой minPts относительно реальной плотности данных так же разрушителен для результата, как и неудачно подобранный $\varepsilon$.

Почему это важно

Оба параметра — $\varepsilon$ и minPts — не независимы друг от друга, а работают только в паре: один и тот же $\varepsilon$ при разных minPts даёт совершенно разные результаты (примеры 1 и 3), и один и тот же minPts при разных $\varepsilon$ — тоже (примеры 1 и 2). DBSCAN не «сам угадывает» правильную плотность — он лишь честно применяет твоё определение плотности («столько-то точек в таком-то радиусе») к данным, и если это определение задано неудачно, результат окажется вырожденным в одну из двух крайностей: весь датасет в шуме или весь датасет в одном кластере. Именно поэтому подбор $\varepsilon$ и minPts — не формальность, а содержательная часть работы с DBSCAN, к которой мы вернёмся в разделе «Частые ошибки» и в «Лайфхаках».

Три типа точек: корневые, граничные, шумовые (core, border, noise)

Интуиция

Продолжим аналогию с переполненным вагоном метро. Если вокруг тебя достаточно людей в радиусе вытянутой руки — ты сам находишься в центре плотной толпы, это корневая (core) точка: с неё можно уверенно начинать говорить «здесь плотный кластер людей». Если рядом с тобой людей меньше, чем нужно для «настоящей толпы», но ты стоишь буквально впритык к кому-то, кто как раз в центре плотной толпы, — ты всё ещё часть этой толпы, просто с её края, это граничная (border) точка. А если ты стоишь в отдельном углу вагона, и никто из «людей в центре толпы» не может дотянуться до тебя рукой, — ты сам по себе, вне какой-либо группы, это шумовая (noise) точка.

Формула

Три типа точек DBSCAN (при фиксированных $\varepsilon$ и minPts).

— Корневая точка (core point): $|N_\varepsilon(p)| \ge \text{minPts}$ — в её собственной ε-окрестности достаточно точек, чтобы место считалось плотным.

— Граничная точка (border point): $|N_\varepsilon(p)| < \text{minPts}$ (сама точка не корневая), но существует хотя бы одна корневая точка $q$, для которой $p \in N_\varepsilon(q)$ — то есть $p$ напрямую плотностно достижима (directly density-reachable) из некоторой корневой точки.

— Шумовая точка (noise point): не корневая и не граничная — ни одна корневая точка не содержит $p$ в своей ε-окрестности.

Обрати внимание на асимметрию отношения «напрямую плотностно достижима»: то, что $q$ входит в окрестность корневой $p$, не гарантирует, что $p$ входит в окрестность $q$, если сама $q$ не корневая, — именно поэтому границы, а не корневые точки, определяются через принадлежность чужой окрестности, а не через собственную.

Разбор примеров

Пример 1 (полная классификация всех десяти точек датасета). Вернёмся к датасету из раздела про параметры с $\varepsilon=1{,}5$, $\text{minPts}=4$ и распишем ε-окрестность каждой точки по отдельности.

Для группы A: $d(T_1,T_2)=1$, $d(T_1,T_3)=1$, $d(T_1,T_4)=\sqrt2\approx1{,}4142$, $d(T_1,T_5)=\sqrt{4+0{,}25}\approx2{,}0616$; $d(T_2,T_3)=\sqrt2\approx1{,}4142$, $d(T_2,T_4)=1$, $d(T_2,T_5)=\sqrt{1+0{,}25}\approx1{,}1180$; $d(T_3,T_4)=1$, $d(T_3,T_5)\approx2{,}0616$; $d(T_4,T_5)\approx1{,}1180$.

Отсюда: $N_{1{,}5}(T_1)=\{T_1,T_2,T_3,T_4\}$ (четыре точки, $T_5$ дальше $1{,}5$) — корневая. $N_{1{,}5}(T_2)=\{T_2,T_1,T_3,T_4,T_5\}$ (пять точек, все расстояния $\le1{,}5$) — корневая. $N_{1{,}5}(T_3)=\{T_3,T_1,T_2,T_4\}$ (четыре точки) — корневая. $N_{1{,}5}(T_4)=\{T_4,T_1,T_2,T_3,T_5\}$ (пять точек) — корневая. А вот $N_{1{,}5}(T_5)=\{T_5,T_2,T_4\}$ — всего три точки, меньше minPts$=4$, значит $T_5$ сама не корневая; но она входит в окрестность корневых $T_2$ и $T_4$ (расстояние $\approx1{,}118\le1{,}5$ в обе стороны) — значит $T_5$ граничная.

Для группы B: наибольшее расстояние внутри четвёрки $T_7(6,6)$, $T_8(6,7)$, $T_9(7,6)$, $T_{10}(6{,}2;\,6{,}2)$ — это $d(T_8,T_9)=\sqrt{1^2+(-1)^2}=\sqrt2\approx1{,}4142\le1{,}5$, а остальные пары ещё ближе (например, $d(T_7,T_{10})=\sqrt{0{,}2^2+0{,}2^2}\approx0{,}2828$). Значит для любой из четырёх точек в её ε-окрестность попадают все четыре точки группы: $|N_{1{,}5}|=4\ge4$ — все четыре точки группы B корневые.

Наконец, $T_6(4,4)$: ближайшая точка группы A — $T_5$ на расстоянии $d(T_5,T_6)=\sqrt{2^2+3{,}5^2}\approx4{,}0311$, ближайшая точка группы B — $T_7$ на расстоянии $d(T_6,T_7)=\sqrt{2^2+2^2}\approx2{,}8284$. Оба расстояния больше $\varepsilon=1{,}5$, значит $N_{1{,}5}(T_6)=\{T_6\}$ — всего одна точка, меньше minPts, и она не входит в окрестность ни одной корневой точки. $T_6$ — шум.

Итог классификации: корневые — $T_1,T_2,T_3,T_4,T_7,T_8,T_9,T_{10}$; граничная — $T_5$; шумовая — $T_6$.

Пример 2 (почему граничная точка не расширяет кластер дальше себя). Представь гипотетическую одиннадцатую точку $T_{11}(3;\,0{,}5)$, находящуюся на расстоянии $d(T_5,T_{11})=1$ от граничной $T_5$, но на расстоянии больше $\varepsilon=1{,}5$ от любой корневой точки группы A (например, $d(T_2,T_{11})=\sqrt{2^2+0{,}5^2}\approx2{,}0616$). Хотя $T_{11}$ и близка к $T_5$, она не может присоединиться к кластеру через $T_5$, потому что $T_5$ сама не корневая, а в определении directly density-reachable роль «источника» цепочки могут играть только корневые точки. Формально: $T_{11}\notin N_\varepsilon(T_5)$ в смысле «$T_5$ распространяет кластер» не работает, поскольку сама $T_5$ не удовлетворяет условию $|N_\varepsilon(T_5)|\ge\text{minPts}$. На практике это означает, что граничные точки — своего рода тупиковые ветви кластера: они присоединяются к нему, но сами дальше цепочку плотности не продолжают.

Пример 3 (почему T6 — шум, а не третий крошечный кластер). Может показаться нелогичным, что одинокая точка $T_6$ помечается шумом, а не образует собственный «кластер из одной точки» — ведь она тоже реальные данные. Но по определению DBSCAN кластер строится вокруг хотя бы одной корневой точки, а корневой точка становится только тогда, когда вокруг неё достаточно плотно — то есть по определению кластер не может состоять из единственной изолированной точки при $\text{minPts}>1$. Это осознанное архитектурное решение, а не недостаток алгоритма: единичная удалённая точка данных статистически с гораздо большей вероятностью — случайный выброс или ошибка измерения (в контексте банка — потенциально мошенническая операция), чем полноценный, просто очень маленький кластер, и явная метка «шум» отражает именно эту неопределённость честнее, чем выдуманный кластер размера один.

Почему это важно

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

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

Интуиция

Представь, что кластер строится как надувающийся воздушный шар, который стартует с одной корневой точки и «перетекает» на всех её соседей. Если сосед сам оказывается корневым, шар продолжает раздуваться и через него — захватывает уже его соседей. Если сосед не корневой (то есть граничный), он присоединяется к шару, но раздувание дальше через него не продолжается — на этом конкретном направлении рост останавливается. Процесс повторяется, пока не останется ни одной новой точки, до которой можно дотянуться через цепочку корневых точек. Затем алгоритм берёт следующую ещё не посещённую точку и, если она корневая, надувает новый шар — новый кластер; если нет — либо она уже стала чьей-то границей, либо окончательно остаётся шумом.

Формула

Плотностная достижимость и кластер. Точка $q$ плотностно достижима (density-reachable) из точки $p$, если существует цепочка точек $p=p_1, p_2, \dots, p_m=q$, в которой каждая следующая точка входит в ε-окрестность предыдущей ($p_{i+1}\in N_\varepsilon(p_i)$) и каждая точка цепочки, кроме, возможно, последней, — корневая. Две точки $p$ и $q$ плотностно связаны (density-connected), если существует точка $o$, из которой плотностно достижимы обе. Кластер — это максимальное по включению множество взаимно плотностно связанных точек; всё, что не вошло ни в один кластер, помечается как шум.

Псевдокод (в духе оригинального алгоритма Эстера и соавторов):

DBSCAN(X, eps, minPts):
    пометить все точки как "не посещена"
    cluster_id = 0
    for p in X:
        if label(p) != "не посещена": continue
        neighbors = N_eps(p)
        if |neighbors| < minPts:
            label(p) = ШУМ
            continue
        cluster_id += 1
        label(p) = cluster_id
        seeds = neighbors \ {p}
        while seeds не пусто:
            q = seeds.pop()
            if label(q) == ШУМ:
                label(q) = cluster_id
            if label(q) != "не посещена":
                continue
            label(q) = cluster_id
            neighbors_q = N_eps(q)
            if |neighbors_q| >= minPts:
                seeds = seeds объединить с neighbors_q

Разбор примеров

Пример 1 (пошаговая трассировка расширения кластера A, начиная с $T_1$). Используем тот же датасет и $\varepsilon=1{,}5$, $\text{minPts}=4$, а порядок обхода — $T_1, T_2, \dots, T_{10}$. $T_1$ ещё не посещена, $N_{1{,}5}(T_1)=\{T_1,T_2,T_3,T_4\}$, четыре точки $\ge$ minPts — корневая, открываем кластер 1, seeds $=\{T_2,T_3,T_4\}$. Достаём $T_2$: не посещена, помечаем кластером 1; $T_2$ корневая ($N_{1{,}5}(T_2)=\{T_2,T_1,T_3,T_4,T_5\}$, пять точек), добавляем её соседей в seeds — новой оказывается только $T_5$, seeds теперь $\{T_3,T_4,T_5\}$. Достаём $T_3$: помечаем кластером 1, она тоже корневая, но все её соседи ($T_1,T_2,T_4$) уже размечены, новых точек не добавляется. Достаём $T_4$: помечаем кластером 1, корневая, соседи ($T_1,T_2,T_3,T_5$) уже размечены или уже в seeds. Достаём $T_5$: помечаем кластером 1; $N_{1{,}5}(T_5)=\{T_5,T_2,T_4\}$, три точки $<$ minPts — $T_5$ не корневая, значит она присоединяется к кластеру, но сама seeds не пополняет. Seeds опустели — кластер 1 завершён: $\{T_1,T_2,T_3,T_4,T_5\}$, в точности четыре корневых точки плюс одна граничная — то же самое разбиение, которое мы получили в предыдущем разделе прямым перебором.

Пример 2 (продолжение обхода — кластер B и шум). Следующая непосещённая точка по порядку — $T_6$: $N_{1{,}5}(T_6)=\{T_6\}$, одна точка $<$ minPts, помечаем шумом (временная метка — если позже она окажется в чьей-то ε-окрестности, метка сменится на номер кластера; в нашем случае этого не произойдёт). Далее $T_7$: не посещена, $N_{1{,}5}(T_7)=\{T_7,T_8,T_9,T_{10}\}$, четыре точки — корневая, открываем кластер 2, seeds $=\{T_8,T_9,T_{10}\}$. Все три точки при обработке тоже оказываются корневыми, но их соседи — те же самые четыре точки группы B, все уже размечены, новых узлов не добавляется. Кластер 2 завершается на составе $\{T_7,T_8,T_9,T_{10}\}$ — все четыре точки корневые, границ в этом кластере нет. Итоговый результат прохода по всему датасету: два кластера и одна точка шума ($T_6$) — полностью совпадает с классификацией из предыдущего раздела.

Пример 3 (порядок обхода не влияет на итоговые кластеры — с одной тонкой оговоркой про границы). Начнём обход не с $T_1$, а с $T_9$ (точка группы B). $N_{1{,}5}(T_9)=\{T_9,T_7,T_8,T_{10}\}$, корневая — открывается кластер 1 (просто с другим номером, чем раньше), и через seeds$=\{T_7,T_8,T_{10}\}$ последовательно захватываются все три оставшиеся точки группы B — итоговый состав кластера $\{T_7,T_8,T_9,T_{10}\}$ идентичен примеру 2, просто получен в другом порядке и под другим номером. То же самое для группы A и для $T_6$: какая бы точка ни обрабатывалась первой, набор корневых и граничных точек, а также сама принадлежность к тому или иному кластеру, не зависят от порядка обхода — они полностью определяются геометрией данных и параметрами $\varepsilon$, minPts. Единственная ситуация, где порядок теоретически может повлиять на результат, — это редкий пограничный случай, когда одна и та же граничная точка одновременно попадает в ε-окрестность корневых точек сразу двух разных кластеров: в исходном алгоритме Эстера такая точка присоединяется к тому кластеру, который обработан первым, то есть присвоение зависит от порядка обхода. Это единственная точка недетерминированности в классическом DBSCAN, и на неё стоит обращать внимание при интерпретации результатов на данных с сильно пересекающимися плотными зонами.

Почему это важно

Алгоритм построения кластеров — это буквальная процедурная реализация определения «кластер = максимальная связная область высокой плотности» из раздела про мотивацию DBSCAN: каждый шаг расширения через seeds — это в точности прослеживание цепочки плотностной достижимости, а завершение расширения на границе (пример 1, точка $T_5$) — это прямое следствие того, что граничные точки не могут сами быть источником дальнейшего распространения. Понимание этого механизма важно не только теоретически: именно из него следует, почему DBSCAN невосприимчив к «затравке» (в отличие от k-means, который чувствителен к случайной инициализации центроидов, урок 320) — результат кластеризации определяется геометрией данных и параметрами, а не порядком обработки точек, за единственным узким исключением редких неоднозначных границ.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Точка $p$ имеет в своей ε-окрестности (включая саму себя) 5 точек, $\text{minPts}=4$. Является ли $p$ корневой?

Задание 2: Точка $q$ сама не удовлетворяет условию корневой, но находится в ε-окрестности некоторой корневой точки $p$. Как классифицировать $q$?

Задание 3: Точка $r$ не корневая и не входит в ε-окрестность ни одной корневой точки. Как её классифицировать?

Задание 4 (машинное обучение): Верно ли, что DBSCAN, как и k-means, требует заранее задать число кластеров $k$?

Задание 5 (машинное обучение): Верно ли, что DBSCAN, как k-means и иерархическая кластеризация, обязательно относит каждую точку выборки к какому-то кластеру?

Задание 6: Даны точки $p(2,3)$, $q(5,7)$, $\varepsilon=5$. Входит ли $q$ в $N_\varepsilon(p)$?

Задание 7: $\text{minPts}=1$. Что произойдёт с определением корневой точки при таком выборе (с учётом того, что окрестность включает саму точку)?

Задание 8: В выводе dbscan.fit_predict(X) библиотеки sklearn метка одной из точек равна $-1$. Что это означает?

Задание 9 (машинное обучение): Почему для DBSCAN важна структура данных, ускоряющая поиск ближайших соседей (KD-дерево, Ball Tree), а не только сам алгоритм кластеризации?

Задание 10: Точка имеет в ε-окрестности ровно minPts точек, включая саму себя. Корневая она или нет?

Средние задания (11–20)

Задание 11: Даны $T_1(0,0)$, $T_2(1,0)$, $T_3(0,1)$, $T_4(1,1)$. Найти расстояния $d(T_1,T_2)$, $d(T_1,T_3)$, $d(T_1,T_4)$.

Задание 12: Используя расстояния из задания 11 и $\varepsilon=1{,}5$, найти $N_\varepsilon(T_1)$ среди $\{T_1,T_2,T_3,T_4\}$.

Задание 13: При $\text{minPts}=4$ является ли $T_1$ корневой по результату задания 12?

Задание 14: $T_5(2;\,0{,}5)$. Расстояния до $T_1,T_2,T_3,T_4$ равны примерно $2{,}0616$; $1{,}1180$; $2{,}0616$; $1{,}1180$. При $\varepsilon=1{,}5$, сколько точек входит в $N_\varepsilon(T_5)$, включая саму $T_5$?

Задание 15 (машинное обучение): Используя результат задания 14 и $\text{minPts}=4$, классифицируй $T_5$ (корневая / граничная / шум) с обоснованием.

Задание 16: $T_6(4,4)$. Ближайшая точка группы A — $T_5$ на расстоянии $\approx4{,}0311$, ближайшая точка группы B — $T_7$ на расстоянии $\approx2{,}8284$. При $\varepsilon=1{,}5$, $\text{minPts}=4$ классифицируй $T_6$.

Задание 17: $T_7(6,6)$, $T_8(6,7)$, $T_9(7,6)$, $T_{10}(6{,}2;\,6{,}2)$. Наибольшее расстояние внутри этой четвёрки — $d(T_8,T_9)=\sqrt2\approx1{,}4142$. При $\varepsilon=1{,}5$, $\text{minPts}=4$ сколько точек этой четвёрки — корневые?

Задание 18 (машинное обучение): Сколько кластеров и сколько шумовых точек находит DBSCAN на полном датасете $T_1$–$T_{10}$ при $\varepsilon=1{,}5$, $\text{minPts}=4$? Перечисли состав.

Задание 19: Если увеличить $\varepsilon$ с $1{,}5$ до $4{,}5$ (minPts$=4$ фиксирован), $T_6$ набирает в свою ε-окрестность $T_4$, $T_5$, $T_7$, $T_8$, $T_9$, $T_{10}$ (все на расстоянии $\le4{,}5$) плюс себя — семь точек. Что произойдёт с кластеризацией всего датасета?

Задание 20: Если вместо этого оставить $\varepsilon=1{,}5$, но поднять $\text{minPts}$ с $4$ до $6$, что произойдёт с корневыми точками $T_2$ и $T_4$ (у которых было по 5 соседей, включая себя)?

Продвинутые задания (21–30)

Задание 21 (машинное обучение): На датасете $T_1$–$T_{10}$ с $\varepsilon=0{,}5$ ($\text{minPts}=4$) минимальное расстояние между любыми двумя различными точками равно $1$. Что произойдёт с кластеризацией?

Задание 22: Проследи полное расширение кластера DBSCAN, начиная с $T_1$ (порядок обхода $T_1\to T_2\to T_3\to T_4\to T_5$). Опиши шаги очереди seeds.

Задание 23: Продолжи обход дальше по порядку $T_6, T_7,\dots$: как обрабатывается $T_6$, и что происходит при переходе к $T_7$?

Задание 24 (машинное обучение): Банк применяет DBSCAN к 10 000 транзакциям (два стандартизированных признака) и получает 3 кластера и 240 точек с меткой $-1$. Как разумно распорядиться этими 240 точками?

Задание 25: Датасет содержит густой кластер A (тысячи точек на малой площади) и разрежённый кластер B (точки расположены в 5 раз дальше друг от друга). Почему подобрать единый $\varepsilon$ для обоих кластеров может быть трудно?

Задание 26: Признаковое пространство имеет размерность $D=8$. По практическому правилу (minPts не меньше $D+1$, часто ориентир $2D$), в каком диапазоне разумно выбирать minPts?

Задание 27 (машинное обучение): Объясни разницу в поведении k-means и DBSCAN на датасете из двух концентрических колец с общим центром.

Задание 28: Дан отсортированный по возрастанию график k-distance (расстояние до 4-го ближайшего соседа, minPts$=4$) для 8 точек: $0{,}3$; $0{,}32$; $0{,}35$; $0{,}4$; $0{,}42$; $1{,}8$; $2{,}1$; $2{,}4$. Где находится "локоть" и какое значение $\varepsilon$ разумно выбрать?

Задание 29 (машинное обучение): Сравни, как k-means (урок 320), иерархическая кластеризация (урок 321) и DBSCAN поступят с одной и той же явной выбросной точкой, находящейся далеко от всех прочих данных.

Задание 30 (машинное обучение, синтез): Сформулируй одним связным ответом, чем DBSCAN принципиально отличается от k-means и иерархической кластеризации по трём осям: нужно ли заранее знать число кластеров, какую форму кластеров каждый метод способен находить и как каждый метод поступает с выбросами.

Частые ошибки

• Выбор $\varepsilon$ "на глаз" или по значению по умолчанию в библиотеке, без построения графика k-distance. Как показано в заданиях 21 и 28, слишком маленький $\varepsilon$ превращает весь датасет в шум, а слишком большой — сливает разные кластеры в один; оба исхода легко проверить заранее с помощью графика расстояний до $k$-го ближайшего соседа.

• Использование DBSCAN на признаках с разными масштабами без стандартизации. DBSCAN, как и k-means (урок 320) и иерархическая кластеризация (урок 321), опирается на евклидово (или иное метрическое) расстояние — признак с большим масштабом абсолютных значений будет доминировать при вычислении расстояний и полностью исказит само понятие "плотности".

• Слишком маленький minPts (в духе $\text{minPts}=1$–$2$), особенно на зашумлённых данных. Задание 7 показывает крайний случай $\text{minPts}=1$, при котором корневой становится буквально любая точка; при малых, но больших единицы значениях почти любая случайная пара близких точек начинает восприниматься как полноценный кластер, что резко повышает чувствительность к шуму вместо защиты от него.

• Ожидание, что DBSCAN одинаково хорошо справится с кластерами существенно разной плотности при одном фиксированном $\varepsilon$. Задание 25 показывает, что единый радиус физически не может одновременно подходить и плотному, и разрежённому кластеру; для таких случаев существуют расширения — OPTICS (1999) и HDBSCAN (2013).

• Смешение метки шума ($-1$ в sklearn) с обычным идентификатором кластера при дальнейшей агрегации результатов. Например, при усреднении координат "кластера $-1$" получится бессмысленное число — $-1$ не кластер, а явное указание "эта точка ни в один кластер не вошла", и перед любой групповой статистикой по номерам кластеров шумовые точки нужно исключать явно.

• Применение DBSCAN к данным очень высокой размерности без осторожности. С ростом числа признаков (проклятие размерности) евклидовы расстояния между почти всеми точками становятся похожими друг на друга, и понятие "плотной окрестности" радиуса $\varepsilon$ теряет содержательный смысл; часто помогает предварительное снижение размерности (урок 323, метод главных компонент).

Главное запомнить

• DBSCAN определяет кластер не как часть разбиения на $k$ групп, а как максимальную связную область высокой плотности точек.

• Всё поведение алгоритма определяется двумя параметрами: $\varepsilon$ (радиус ε-окрестности) и minPts (минимальное число точек в этой окрестности, включая саму точку, чтобы место считалось плотным).

• Три типа точек: корневая (core, $|N_\varepsilon(p)|\ge\text{minPts}$), граничная (border, сама не корневая, но соседствует с корневой), шумовая (noise, ни то ни другое).

• Кластер строится через плотностную достижимость — цепочку корневых точек, каждая следующая из которых лежит в ε-окрестности предыдущей; граничные точки присоединяются к кластеру, но сами цепочку не продолжают.

• В отличие от k-means (урок 320) и иерархической кластеризации (урок 321), DBSCAN не требует заранее знать число кластеров — оно определяется структурой плотности данных.

• DBSCAN находит кластеры произвольной формы, а не только выпуклые, потому что соединяет точки через локальные цепочки соседства, а не через расстояние до единого центроида.

• DBSCAN явно помечает часть точек как шум (метка $-1$ в sklearn.cluster.DBSCAN), а не насильно распределяет их по ближайшим кластерам — поэтому его часто применяют как готовый детектор аномалий: мошеннические транзакции, необычная сетевая активность.

• Слишком маленький $\varepsilon$ делает почти весь датасет шумом, слишком большой $\varepsilon$ сливает разные кластеры в один; оптимальный $\varepsilon$ обычно ищут по "локтю" на графике k-distance.

• minPts, слишком большой относительно фактической плотности данных, лишает датасет корневых точек вовсе; практический ориентир — не меньше размерности признакового пространства плюс один, часто около удвоенной размерности.

• DBSCAN плохо справляется с кластерами существенно разной плотности при одном фиксированном $\varepsilon$ — для таких случаев существуют более поздние алгоритмы OPTICS (1999) и HDBSCAN (2013).

Связь с темами курса

Этот урок напрямую продолжает блок кластеризации, начатый в уроке 320 (k-means): там ты разобрал минимизацию суммы квадратов расстояний до центроидов и главное следствие этого подхода — необходимость заранее знать $k$ и предположение о выпуклой, примерно сферической форме кластеров. DBSCAN снимает оба этих ограничения за счёт другого определения кластера — через локальную плотность, а не через глобальную оптимизацию расстояний до центра. С уроком 321 (иерархическая кластеризация) связь ещё более прямая: там число кластеров тоже не нужно знать заранее при построении дендрограммы, но оно неизбежно требуется при её разрезании на конечное число ветвей, и ни одна точка не может остаться "ничьей" — DBSCAN убирает и это последнее ограничение, явно допуская шум как самостоятельную категорию. Упомянутая в разделе про частые ошибки проблема "проклятия размерности" — прямой мостик к следующему уроку 323 про метод главных компонент (PCA): снижение размерности признакового пространства перед кластеризацией часто оказывается необходимым шагом именно потому, что в высокой размерности понятие ε-окрестности перестаёт быть содержательным.

Интересные факты

• Оригинальная статья Мартина Эстера, Ханса-Петера Кригеля, Йорга Сандера и Сяовэй Сюя была представлена на конференции KDD-96, а в 2014 году, спустя 18 лет, получила премию SIGKDD Test of Time Award — награду, присуждаемую за работы, показавшие долгосрочное фундаментальное влияние на область анализа данных.

• Алгоритм изначально разрабатывался для пространственных баз данных — географических и картографических данных, где было важно находить регионы повышенной плотности объектов произвольной формы (например, скопления городов на карте), а не абстрактные "кластеры" в общем смысле машинного обучения.

• Та же исследовательская группа (Анкерст, Бройниг, Кригель, Сандер) в 1999 году предложила OPTICS — алгоритм, убирающий необходимость фиксировать единственное значение $\varepsilon$ заранее и вместо этого строящий упорядоченную структуру достижимости сразу для целого диапазона значений $\varepsilon$.

• Более поздний алгоритм HDBSCAN (2013, Кампелло, Мойзес, Сандер) объединяет идею DBSCAN с иерархической кластеризацией (урок 321), позволяя находить кластеры существенно разной плотности без единственного фиксированного $\varepsilon$ — прямое развитие сразу двух методов этого блока курса.

Лайфхаки

• Подбирай $\varepsilon$ через график k-distance: отсортируй по возрастанию расстояния до $k$-го (равного minPts) ближайшего соседа для каждой точки и найди "локоть" — этот радиус обычно и есть разумный $\varepsilon$ (см. задание 28).

• Стандартизируй признаки (StandardScaler) перед DBSCAN, как и перед любым методом на основе евклидова расстояния — иначе один признак с большим масштабом абсолютных значений будет доминировать в понятии "плотности".

• Начинай подбор minPts с ориентира "не меньше размерности признакового пространства плюс один" (задание 26), а для заметно зашумлённых данных сразу бери значение заметно выше этого минимума — шум требует более строгого критерия плотности.

• Используй метку $-1$ в sklearn.cluster.DBSCAN напрямую как первый, по сути бесплатный слой детектора аномалий — прежде чем городить отдельную модель обнаружения выбросов, посмотри, что уже нашёл DBSCAN.

• Если в данных заметно различается плотность разных областей (задание 25), не трать время на бесконечный подбор единого $\varepsilon$ для DBSCAN — сразу попробуй HDBSCAN, который снимает именно это ограничение.

• Перед прогоном на больших датасетах убедись, что sklearn использует ускоренный поиск соседей (параметр algorithm='auto', 'ball_tree' или 'kd_tree'), а не полный перебор 'brute' — разница в скорости на больших $n$ может достигать порядков (задание 9).

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