Что такое HDBSCAN: кластеры разной плотности и шум

Что такое HDBSCAN: кластеры разной плотности и шум — это алгоритм кластеризации, который строит иерархию по плотности, находит группы с разной плотностью и оставляет выбросы отдельными точками с меткой −1. Авторы библиотеки описывают его как DBSCAN, выполненный при меняющихся значениях epsilon с последующей интеграцией результатов по устойчивости.

Кластеры по плотности и точки-шум

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

Практический результат для читателя: часть объектов получает метку −1. Это решение алгоритма о том, что точка не принадлежит ни одной устойчивой группе. В библиотеке scikit-learn-contrib такие объекты помечаются −1, а в sklearn к ним добавляются −2 для строк с бесконечными элементами и −3 для строк с пропусками. Метка −1 означает шум, и это полноценный результат работы, который стоит показывать в отчёте отдельной строкой.

Кластеры разной плотности — вторая часть задачи. DBSCAN с одним радиусом находит группы сопоставимой плотности. HDBSCAN работает с иерархией уровней и потому выделяет и плотное ядро, и более рыхлое облако рядом. Авторы библиотеки прямо указывают, что это позволяет находить кластеры переменной плотности и делает результат устойчивее к выбору параметров.

Номера кластеров произвольны: группа 0 в одном запуске и группа 0 в другом — разные объекты. Сравнивать прогоны по номерам нельзя, сравнивать нужно по составу точек.

Расстояние взаимной достижимости и дерево

Механика HDBSCAN разложена в документации проекта на пять шагов: преобразование пространства по плотности, построение минимального остовного дерева взвешенного графа, построение иерархии связных компонент, сжатие иерархии по минимальному размеру кластера и извлечение устойчивых кластеров. Разберём первые два.

Оценка плотности берётся через расстояние до k-го ближайшего соседа. Документация называет эту величину core distance — расстояние до ядра. Точка в плотной области имеет малое core distance, точка на периферии — большое. Дальше вводится новое расстояние между точками, mutual reachability distance, расстояние взаимной достижимости. Оно равно максимуму из трёх величин: исходного расстояния между точками и двух core distance. Формулировка из документации: плотные точки остаются на прежнем расстоянии друг от друга, а разреженные отталкиваются минимум на своё core distance. Это и есть «понижение уровня моря»: разреженные точки разъезжаются, плотные остаются на месте.

Важная деталь: результат зависит от выбора k. Документация отмечает, что большие значения k относят больше точек к «морю». В примере из документации используется k, равное пяти, и окружность core distance проводится через шестого соседа с учётом самой точки.

Дальше строится минимальное остовное дерево графа, где вершины — точки, а вес ребра — расстояние взаимной достижимости. Дерево даёт минимальный набор рёбер, разрыв любого из которых рассоединяет компоненты. Документация подчёркивает: это дерево строится именно по mutual reachability distance, и оно отличается от дерева по чистому расстоянию. Затем рёбра сортируются по возрастанию, и последовательное слияние компонент даёт дендрограмму — иерархию связных компонент.

Здесь заканчивается robust single linkage. Дальше начинается собственно HDBSCAN: горизонтальный разрез дендрограммы соответствовал бы DBSCAN с одним уровнем плотности, а нужен выбор кластеров на разных уровнях. Каждый шаг описывает операцию над расстояниями. Для выбранной реализации проверьте, какие промежуточные структуры доступны после обучения и какие настройки нужны для их сохранения.

min_cluster_size и min_samples: что за что отвечает

Документация по выбору параметров называет min_cluster_size главным параметром, влияющим на результат кластеризации. Этот параметр задаёт минимальный размер группы, которую алгоритм готов признать кластером. При сжатии иерархии каждое разбиение проверяется: если отделившаяся часть меньше min_cluster_size, она считается точками, «выпавшими» из родительского кластера, и родитель сохраняет свою идентичность. Если обе части не меньше порога, разбиение признаётся настоящим и остаётся в дереве.

min_samples управляет консервативностью оценки плотности. Документация формулирует прямо: чем больше значение min_samples, тем консервативнее кластеризация, тем больше точек объявляется шумом, а кластеры ограничиваются всё более плотными областями. Этот параметр связан с k в оценке core distance.

Эти тенденции помогают выбрать направление проверки. Меняйте параметры по одному, затем изучайте состав меток и число получившихся групп; заранее гарантировать точное число кластеров нельзя.

Документация отдельно предостерегает от правки параметра alpha: он относится к коду RobustSingleLinkage и переходит в HDBSCAN естественным образом, поэтому трогать его в обычной работе не рекомендуется. Параметр cluster_selection_method со значением leaf выбирает листовые узлы дерева и даёт много мелких однородных кластеров — такой выбор стоит соотносить с задачей сегментации и требуемой детализацией.

Учебный набор из 11 точек и код на sklearn

Ниже полный учебный пример на sklearn.cluster.HDBSCAN. Набор двумерный: две плотные группы по пять точек и одиночная точка [8, 8]. Численные метки и число кластеров заранее не объявляются — их выдаёт модель. Программа не запускалась редакцией, это учебный вход для самостоятельного прогона.

# Учебный пример именно sklearn.cluster.HDBSCAN.
# Редакция не запускала модель; численные метки заранее не объявлены.
import numpy as np
from sklearn.cluster import HDBSCAN

X = np.array([[0, 0], [0, .1], [.1, 0], [.1, .1], [.05, .05],
              [3, 3], [3, 3.1], [3.1, 3], [3.1, 3.1], [3.05, 3.05],
              [8, 8]])
model = HDBSCAN(min_cluster_size=3, min_samples=2).fit(X)
assert len(model.labels_) == len(model.probabilities_) == len(X)
for point, label, strength in zip(X, model.labels_, model.probabilities_):
    print(point.tolist(), int(label), float(strength))
    if label == -1:
        assert strength == 0
print("Количество нешумовых групп:", len(set(model.labels_) - {-1}))

Порядок работы: подготовить массив, создать объект HDBSCAN с выбранными параметрами, вызвать fit, прочитать labels_ и probabilities_. Инвариант, который проверяет код: длина labels_ и probabilities_ равна числу точек. Для точки с меткой −1 membership strength равна нулю. Проверьте метку одиночной точки [8, 8] после запуска: её принадлежность зависит от полученной иерархии и выбранных параметров. Число нешумовых групп печатается отдельно, потому что номера кластеров произвольны и судить по максимальной метке о количестве групп можно только с оговоркой.

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

labels_ и probabilities_: что они значат

labels_ — массив целых чисел, по одному на объект. Объекты одного кластера получают одинаковое число, номера начинаются с нуля и растут. Документация библиотеки scikit-learn-contrib поясняет: количество кластеров определяется по наибольшей метке, а шум получает −1. Номера произвольны и не несут смысла порядка.

probabilities_ — сила принадлежности кластеру. Документация scikit-learn описывает её как силу, с которой каждый образец является членом назначенного ему кластера. Значение 1.0 означает точку в сердцевине кластера, 0.0 — точку, не входящую в кластер; все шумовые точки получают 0.0. Это не калиброванная вероятность правильного ответа и не вероятность истинного класса. Эта мера описывает силу принадлежности точки выбранному кластеру; её можно использовать как вес при анализе, учитывая смысл показателя.

Практический приём: отсортировать точки по возрастанию probabilities_ и посмотреть на нижние 10–20 процентов. Часто там оказываются объекты на границе между группами — именно они дают наибольшую неопределённость при разметке. Точки с меткой −1 и нулевой силой — кандидаты на отдельный разбор: опечатки, редкие случаи, аномалии.

Ещё одно различие между реализациями. В scikit-learn-contrib объект кластера получает persistence score — оценку устойчивости кластера по диапазону масштабов расстояний в данных. Это относительная мера силы кластера, полезная при сравнении групп между собой внутри одного прогона.

Разница учёта самой точки в min_samples

Параметр min_samples в двух реализациях считается по-разному, и это меняет результат при одинаковом числе в коде. Документация scikit-learn указывает: в sklearn параметр min_samples включает саму точку, тогда как реализация в scikit-learn-contrib/hdbscan её не включает. Значит, min_samples=2 в sklearn и min_samples=2 в contrib описывают разные окрестности, и переносить значение между библиотеками без пересчёта нельзя.

Та же логика касается API прогнозирования. Библиотека scikit-learn-contrib предоставляет approximate_predict и кэширование через prediction_data для разметки новых точек. В sklearn такого метода в разбираемом примере нет, и приписывать ему эту возможность не стоит. cuML от NVIDIA идёт дальше в ограничениях: документация cuML сообщает, что случай k = 1 не поддерживается, а из метрик допускается только euclidean. Кэширование prediction_data в cuML служит для предсказания меток и векторов принадлежности для новых точек.

Отсюда рабочее правило: выберите одну библиотеку под задачу и держите параметры и способ предсказания внутри неё. При переходе между sklearn, scikit-learn-contrib и cuML пересматривайте min_samples, метрику и способ разметки новых объектов заново.

Метрика, масштабирование и оценка числа кластеров

Метрика задаёт смысл расстояния, а значит и смысл плотности. Документация scikit-learn-contrib перечисляет широкий набор метрик, включая euclidean, manhattan, chebyshev, hamming, jaccard, mahalanobis и другие. Отдельно поддерживается метрика precomputed: если у вас есть только матрица попарных расстояний, кластеризатор принимает её напрямую. Пропущенные расстояния обозначаются numpy.inf, и алгоритм игнорирует такие пары, пока между точками существует путь из определённых расстояний. Входная матрица обязана содержать числовые данные.

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

Оценка числа кластеров требует осторожности. Номера кластеров произвольны, поэтому число групп считается как количество уникальных нешумовых меток. Меняйте min_cluster_size и min_samples по одному, фиксируйте состав меток и долю шума. Устойчивый результат — тот, где группы сохраняются при небольших сдвигах параметров. Документация scikit-learn-contrib описывает HDBSCAN как инструмент разведочного анализа, который возвращает осмысленные кластеры, если они есть в данных. Формулировка «если они есть» здесь ключевая: алгоритм может вернуть один кластер или объявить всё шумом, и это тоже информация о данных.

Частые вопросы

Чем HDBSCAN отличается от DBSCAN?
DBSCAN работает с одним радиусом epsilon и находит группы сопоставимой плотности. HDBSCAN выполняет DBSCAN при меняющихся значениях epsilon и интегрирует результаты по устойчивости, поэтому находит кластеры переменной плотности и меньше зависит от выбора параметров. Документация scikit-learn-contrib описывает это как основное преимущество.

Что означает метка −1 в labels_?
Это шум: точка не вошла ни в один выбранный кластер. В sklearn дополнительно используются −2 для строк с бесконечными элементами и −3 для строк с пропусками. Шум стоит показывать в отчёте отдельной категорией и учитывать его долю при анализе.

probabilities_ — это вероятность правильного класса?
Нет. Это сила принадлежности назначенному кластеру, внутренняя мера алгоритма. Значение 1.0 означает точку в сердцевине кластера, 0.0 — шумовую точку. Калиброванной вероятностью истинного класса эта величина не является.

Почему одинаковые min_samples дают разный результат в sklearn и contrib?
В sklearn параметр включает саму точку, в scikit-learn-contrib/hdbscan — не включает. Одинаковое число описывает разные окрестности, поэтому при переносе кода значение нужно пересчитывать.

Как выбрать min_cluster_size?
Отталкивайтесь от минимального размера группы, который имеет смысл в задаче. Документация называет этот параметр главным. Меняйте его по одному шагу и следите за долей шума и устойчивостью состава групп.