Плотностная : кластеры — это связные области высокой плотности, остальное объявляется шумом.
Ключевые тезисы
- Параметры eps и min_samples задают, что считать плотной областью.
- Находит кластеры произвольной формы и не требует задавать их число.
- Плохо работает при сильно разной плотности кластеров — здесь помогает HDBSCAN.
Какую задачу решает
определяет кластер не через близость к центру, а через плотность: кластер — это связная область, где объекты стоят плотно, а разделяют такие области разрежённые промежутки. Отсюда два свойства, которых нет у : форма кластера может быть любой, а число кластеров алгоритм определяет сам.
Третье важное отличие — понятие шума. Объект, вокруг которого нет достаточной плотности, не приписывается ни к какому кластеру, а помечается выбросом. Для многих прикладных задач это не побочный эффект, а главный результат.
Постройте k-distance график: для каждого объекта найдите расстояние до его min_samples-го соседа, отсортируйте эти расстояния по возрастанию и нарисуйте. На графике обычно виден «локоть» — точка, после которой расстояния резко растут: это и есть граница между плотными областями и разрежёнными. Значение в локте берут за . Если локтя не видно вовсе, у данных нет выраженной плотностной структуры, и здесь мало что даст — какое ни возьми, получится либо один огромный кластер, либо сплошной шум.
Подробный разбор
- Ядровая точка: в её -окрестности не меньше
min_samplesобъектов. - Граничная: попадает в окрестность ядровой, но сама плотной окрестности не имеет.
- Шум: не относится ни к одному кластеру — и это полноценный результат, а не ошибка.
Кластеры получаются произвольной формы: спирали, кольца, вытянутые полосы — всё, что разрезал бы поперёк.
min_samples обычно берут около , где — размерность. Для eps строят график расстояний до -го соседа для всех точек, сортируют его и ищут «колено».
Главное ограничение — единая плотность для всего датасета. Если один кластер плотный, а другой разреженный, ни одно значение eps не подойдёт обоим; тогда берут HDBSCAN, который перебирает плотности иерархически.
Где применяется
- Шумовые точки — готовый результат: объекты, не принадлежащие ни одной плотной области.
- ГеоданныеСкопления событий на карте: ДТП, вызовы, точки интереса. Форма скоплений произвольна, и это .
- Кластеры сложной формыВытянутые, изогнутые, вложенные структуры, недоступные .
- Неизвестное число группКогда подсказать нечем и задавать его произвольно неправильно.
Плюсы, минусы и альтернативы
Плюсы
- Число кластеров определяется автоматически.
- Кластеры произвольной формы — не только сферические.
- Явно выделяет вместо того, чтобы приписывать их куда попало.
- Устойчив к выбросам: они не смещают ничего, в отличие от центроидов.
- Один понятный содержательный параметр — что считать плотным.
Минусы
- Плохо работает, если у кластеров разная плотность: один на всех не подходит.
- Подбор нетривиален и сильно влияет на результат.
- Разваливается в высокой размерности вместе с понятием расстояния.
- Не умеет назначать кластер новому объекту без пересчёта.
- Сложность до без пространственного индекса.
Брать, если
- Кластеры ожидаются произвольной формы.
- В данных есть шум, и его нужно отделить, а не распределить.
- Число кластеров неизвестно.
Не брать, если
- Плотность кластеров сильно различается — берите HDBSCAN.
- Размерность высокая и снизить её нечем.
- Нужно быстро назначать кластер новым объектам в проде.
Чем заменяют
Связанные темы
Плотностная кластеризация · Кластеризация и её оценка
HDBSCAN85%
HDBSCAN · Обучение без учителяИерархическая версия DBSCAN: перебирает плотности автоматически и находит кластеры разной плотности.
Spectral Clustering85%
Спектральная кластеризация · Обучение без учителяКластеризация через собственные векторы матрицы Лапласа графа сходства: находит невыпуклые и вложенные структуры.
Dimensionality Reduction85%
Снижение размерности · Обучение без учителяКомпактное представление данных, сохраняющее важную часть структуры.
Persistent Homology85%
Персистентные гомологии · Топологический анализ данныхЦентральный метод TDA: вместо одного порога ε рассматривается вся фильтрация, и отслеживается, когда топологические особенности рождаются и умирают.
Eigenvector85%
Собственный вектор · Математический справочникНаправление, сохраняющееся при линейном преобразовании с точностью до масштаба.
k-Means75%
k-средних · Классическое машинное обучениеРазбивает объекты на k кластеров, минимизируя суммарное расстояние до центроидов.
GMM75%
Смесь гауссиан · Классическое машинное обучениеВероятностная модель: данные порождаются смесью нормальных распределений, параметры оцениваются EM-алгоритмом.
Clustering75%
Кластеризация · Обучение без учителяРазбиение объектов на группы похожих без заранее известных меток.
Density Estimation75%
Оценка плотности · Обучение без учителяВосстановление распределения данных: где объекты встречаются часто, а где почти никогда.
Association Rules75%
Ассоциативные правила · Обучение без учителяПоиск закономерностей вида «если A, то B» в транзакционных данных.
Silhouette Score75%
Силуэт · МетрикиСравнивает среднее расстояние объекта до своего кластера и до ближайшего чужого.
Davies–Bouldin75%
Индекс Дэвиса — Болдина · МетрикиОтношение внутрикластерного разброса к расстоянию между кластерами; чем меньше, тем лучше.
Calinski–Harabasz75%
Индекс Калинского — Харабаша · МетрикиОтношение межкластерной дисперсии к внутрикластерной; чем больше, тем лучше разделение.
Mapper75%
Алгоритм Mapper · Топологический анализ данныхСтроит граф-скелет данных: проекция фильтрующей функцией, покрытие интервалами, локальная кластеризация и склейка.
Всё, что названо в описании, разобрано здесь же или в соседней теме — переходы под каждым определением.
(радиус)
Размер окрестности, в которой считаются соседи. Главный и самый капризный параметр.
Разбор ниже: Подбор eps и min_samplesmin_samples
Сколько соседей нужно, чтобы точка считалась внутренней. Определяет, что считать плотным.
Разбор ниже: Подбор eps и min_samplesЯдровые, граничные и шумовые точки
Три роли: внутренние точки образуют кластер, граничные к нему примыкают, шумовые остаются вне.
Разбор ниже: Ядровые точки, границы и шумПлотностная связность
Кластер — это всё, до чего можно дойти цепочкой внутренних точек. Отсюда произвольная форма.
Разбор ниже: Ядровые точки, границы и шумГлава «Классическое машинное обучение» последний раз правилась . Нашли ошибку — напишите.