DBSCAN и плотностная кластеризация

Представьте карту ночного города из космоса: яркие пятна населённых пунктов, тёмные провалы лесов и полей, и отдельные огоньки - одинокие дома. Вы сразу видите города, потому что фонари расположены плотно. K-Means попытался бы нарисовать круги вокруг «центров», и деревня рядом с мегаполисом попала бы в один кластер с ним. А одинокий маяк на острове - тоже куда-нибудь прикрепился бы. Алгоритм DBSCAN думает иначе: кластер - это область, где точки расположены плотно, а то, что далеко от всех - это шум. Никаких центров, никаких сфер, никакого заранее заданного числа кластеров.

• **Геолокационная аналитика:** Uber и Lyft используют плотностную кластеризацию для определения «горячих зон» спроса на такси - области города, где запросы группируются плотно, а одиночные вызовы из пригорода корректно идентифицируются как выбросы
• **Обнаружение аномалий в кибербезопасности:** DBSCAN анализирует сетевой трафик, группируя нормальные паттерны в кластеры и автоматически помечая аномальные запросы (DDoS-атаки, сканирование портов) как noise - без необходимости заранее описывать, как выглядит атака
• **Анализ экспрессии генов:** HDBSCAN кластеризует гены по паттернам активности, находя группы ко-экспрессируемых генов произвольной формы и разной плотности - от крупных регуляторных сетей до редких подтипов клеток

Статья с KDD, прекрасно выдержавшая проверку временем

DBSCAN был представлен в 1996 году Мартином Эстером, Хансом-Петером Кригелем, Йоргом Сандером и Сяовэем Сюем на конференции KDD в статье «A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise». Мотивация была практической: пространственные базы данных той эпохи, полные спутниковых снимков и географических точек, совсем не вписывались в предположения K-Means, ведь реальная география порождает кластеры неправильной формы, окружённые шумом. Авторы переосмыслили кластер как область высокой плотности точек, а не шар вокруг центра, и одного этого сдвига хватило, чтобы метод находил полумесяцы, кольца и цепочки, попутно автоматически отмечая выбросы. Идея оказалась настолько живучей, что в 2014 году та же статья получила премию SIGKDD Test of Time Award, признавшую почти два десятилетия непрерывного влияния, а сам DBSCAN остаётся одним из самых цитируемых алгоритмов кластеризации.

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

• K-Means Clustering

Epsilon-окрестность и плотность

K-Means разбивает пространство на сферические области вокруг центроидов. Но что делать, если кластеры имеют форму полумесяцев, колец или цепочек? K-Means здесь бессилен. **DBSCAN (Density-Based Spatial Clustering of Applications with Noise)** - алгоритм 1996 года от Мартина Эстера и коллег - подходит к проблеме принципиально иначе: кластер - это не сфера вокруг центра, а **область высокой плотности**, отделённая от других областей зонами низкой плотности.

Центральное понятие DBSCAN - **eps-окрестность** (epsilon-neighbourhood). Для каждой точки p это множество всех точек, расстояние до которых не превышает eps: N_eps(p) = {q : dist(p, q) <= eps}. Проще говоря, eps - это **радиус круга** (в 2D) или сферы (в 3D), который мы рисуем вокруг каждой точки. Все точки, попавшие внутрь - соседи.

На основе eps-окрестности DBSCAN классифицирует каждую точку в одну из трёх категорий. **Core point (ядровая точка)** - точка, у которой в eps-окрестности находится не менее min_samples соседей. Это «сердце» кластера: вокруг неё достаточно плотно. **Border point (граничная точка)** - точка, у которой соседей меньше min_samples, но она сама лежит в eps-окрестности хотя бы одной core point. Она на «границе» кластера. **Noise point (шум/выброс)** - точка, которая не является ни core, ни border. Она далеко от всех плотных областей.

Алгоритм DBSCAN работает через **density-reachability** (достижимость по плотности). Точка q достижима из p, если существует цепочка core points от p до q, где каждая следующая точка лежит в eps-окрестности предыдущей. Алгоритм: 1. выбрать непосещённую точку 2. если она core - создать новый кластер и рекурсивно добавить все density-reachable точки 3. если она не core и не достижима ни из одной core - пометить как noise 4. повторить для всех непосещённых точек.

Параметр min_samples и подбор eps

DBSCAN принимает два параметра: **eps** (радиус окрестности) и **min_samples** (минимальное число точек для core point). Качество кластеризации критически зависит от их выбора. Плохие параметры - и алгоритм либо объединит все данные в один кластер, либо объявит все точки шумом. Но в отличие от K-Means, где нужно угадать число кластеров k, у DBSCAN есть **систематические методы** подбора параметров.

Начнём с **min_samples**. Эмпирическое правило: **min_samples >= D + 1**, где D - размерность данных. Для 2D-данных: min_samples >= 3. Для высокоразмерных данных (например, 50 признаков): min_samples >= 51. На практике часто берут **min_samples = 2 * D** как отправную точку. Увеличение min_samples делает алгоритм строже: меньше core points, больше шума, более «чистые» кластеры. Уменьшение - более мягкие кластеры, меньше шума.

**Практические рекомендации по min_samples:** - **min_samples = 2** - минимум (совпадает с иерархической кластеризацией single-linkage) - **min_samples = 5** - хорошая отправная точка для большинства 2D задач - **min_samples = 2 * D** - для высокоразмерных данных - **Большие датасеты** (100k+ точек) - увеличить min_samples, иначе будет слишком много мелких кластеров - **Зашумлённые данные** - увеличить min_samples для фильтрации шума

Теперь **eps** - более сложный параметр. Самый популярный метод его подбора - **k-distance plot** (график k-расстояний). Идея: для каждой точки вычислить расстояние до k-го ближайшего соседа (k = min_samples), отсортировать эти расстояния по убыванию и построить график. На графике будет характерный **«излом» (knee/elbow)** - точка, где расстояния резко возрастают. Значение eps берётся в этой точке: ниже излома - плотные кластеры, выше - шум.

**Главная ловушка:** eps задаёт **единый радиус** для всего датасета. Если кластеры имеют разную плотность - один кластер плотный (точки близко), другой разреженный (точки далеко) - один eps не справится. Маленький eps найдёт плотный кластер, но разобьёт разреженный. Большой eps объединит разреженный, но склеит плотные. Это фундаментальное ограничение DBSCAN, которое решает HDBSCAN.

Обнаружение выбросов и произвольная форма кластеров

Одно из главных преимуществ DBSCAN - **автоматическое обнаружение выбросов** (outlier detection). В K-Means каждая точка обязательно принадлежит какому-то кластеру, даже если она аномальная и далеко от всех. DBSCAN же присваивает таким точкам метку **-1 (noise)**, говоря: эта точка не вписывается ни в один кластер. Это делает DBSCAN одним из самых простых и эффективных методов обнаружения аномалий.

Второе ключевое преимущество - **кластеры произвольной формы**. K-Means работает с «шарообразными» (convex) кластерами, потому что каждая точка присваивается ближайшему центроиду. DBSCAN же строит кластеры через density-reachability - цепочку плотных точек. Это позволяет находить полумесяцы, кольца, змейки, любые нелинейные формы. Если два региона соединены тонким «мостиком» плотных точек - DBSCAN объединит их в один кластер.

Ещё одно преимущество: DBSCAN **не требует указания количества кластеров** заранее. K-Means нужен параметр k, и если вы ошиблись - результат будет некорректным. DBSCAN сам определяет число кластеров на основе структуры плотности данных. Если в данных 3 плотных области - будет 3 кластера. Если 10 - будет 10. Это особенно ценно в задачах, где количество групп заранее неизвестно: сегментация клиентов, анализ социальных сетей, географическая кластеризация.

**Когда DBSCAN лучше K-Means:** - Кластеры имеют нелинейную/произвольную форму - Количество кластеров заранее неизвестно - В данных есть выбросы, которые нужно обнаружить - Кластеры примерно одинаковой плотности **Когда K-Means лучше DBSCAN:** - Кластеры примерно сферические (выпуклые) - Кластеры разной плотности (DBSCAN борется с этим) - Нужен быстрый результат на очень больших данных (K-Means - O(nk), DBSCAN - O(n^2) без индексов) - Данные высокоразмерные (в высоких размерностях понятие плотности размывается - curse of dimensionality)

HDBSCAN и сравнение методов кластеризации

Мы видели главное ограничение DBSCAN: **один eps для всего датасета**. Представьте город: в центре - плотная застройка (точки близко), на окраинах - разреженные посёлки (точки далеко). Маленький eps найдёт центр, но посёлки рассыплются на шум. Большой eps объединит посёлки, но центр склеится в один кластер. **HDBSCAN (Hierarchical DBSCAN)** решает эту проблему, позволяя каждому кластеру иметь **свою локальную плотность**.

HDBSCAN работает в несколько шагов. Сначала для каждой точки вычисляется **core distance** - расстояние до k-го ближайшего соседа (k = min_cluster_size). Затем строится **mutual reachability distance**: для пары точек (a, b) это max(core_dist(a), core_dist(b), dist(a, b)). Идея: в плотных областях mutual reachability distance ~ реальному расстоянию, а в разреженных - оно увеличивается, «штрафуя» разреженные точки.

На основе mutual reachability distances строится **минимальное остовное дерево (MST)**. Затем HDBSCAN последовательно «отрезает» самые длинные рёбра, формируя иерархию кластеров (дендрограмму). Наконец, алгоритм выбирает **наиболее стабильные кластеры** из этой иерархии - те, которые существуют долго (при разных уровнях среза). Параметр **min_cluster_size** - единственный важный параметр: минимальное число точек, которое может считаться кластером.

**DBSCAN и HDBSCAN чувствительны к масштабу признаков.** Если один признак в диапазоне [0, 1], а другой - [0, 10000], eps-окрестность будет определяться почти исключительно вторым признаком. **Всегда** нормализуйте данные (StandardScaler или MinMaxScaler) перед применением любого плотностного метода.

Ключевые идеи

• **DBSCAN** строит кластеры по плотности: core points (>= min_samples соседей в eps-окрестности), border points (рядом с core) и noise (далеко от всех) - три категории вместо принудительного присвоения к ближайшему центроиду
• **Подбор параметров:** min_samples >= 2*D как отправная точка, eps - через k-distance plot (ищем излом); маленький eps = много шума, большой = один кластер
• **Преимущества DBSCAN:** произвольная форма кластеров (полумесяцы, кольца), автоматическое определение числа кластеров и обнаружение выбросов (label=-1), но один eps не справляется с кластерами разной плотности
• **HDBSCAN** решает проблему разной плотности через адаптивный подход: mutual reachability distance + иерархия - каждый кластер получает свою локальную плотность, как карта ночного города из космоса, где и мегаполис, и деревня распознаются как отдельные населённые пункты

Связанные темы

Плотностная кластеризация - один из подходов к unsupervised learning. Она связана с другими методами кластеризации и анализа данных:

• K-Means кластеризация — Базовый метод кластеризации на основе центроидов - DBSCAN решает его ограничения с нелинейными формами и выбросами
• Иерархическая кластеризация — HDBSCAN объединяет идеи иерархической кластеризации (дендрограмма) с плотностным подходом DBSCAN
• PCA и снижение размерности — В высокоразмерных данных DBSCAN теряет эффективность - PCA снижает размерность перед кластеризацией, сохраняя структуру плотности
• Обнаружение аномалий — Noise points в DBSCAN - простейший метод обнаружения аномалий, но специализированные методы (Isolation Forest, LOF) работают точнее

Вопросы для размышления

• DBSCAN использует евклидово расстояние для вычисления eps-окрестности. Как бы изменился результат, если заменить метрику на Manhattan distance или косинусное расстояние? Для каких данных какая метрика подойдёт лучше?
• Если DBSCAN хорошо обнаруживает выбросы (noise), можно ли использовать его как полноценный anomaly detector вместо специализированных алгоритмов (Isolation Forest, LOF)? В чём могут быть ограничения такого подхода?
• HDBSCAN решает проблему разной плотности, но добавляет сложность (MST, иерархия, stability). Когда стоит потратить время на HDBSCAN, а когда достаточно простого DBSCAN с подобранным eps?

Связанные уроки

• ml-16-clustering-kmeans — DBSCAN заменяет центроидную кластеризацию понятием плотности
• ml-17-hierarchical-clustering — Другое семейство кластеризации без заранее фиксированного K
• ml-20-anomaly-detection — Точки-шум становятся естественными кандидатами в выбросы
• prob-10-continuous — Оценка плотности лежит в основе идеи DBSCAN
• ds-02 — Запросы по окрестности опираются на пространственные индексы
• alg-13-dfs