Меня недавно попросили сделать молниеносный доклад об алгоритме кластеризации под названием HDBScan. HDBScan основан на алгоритме DBScan и, как и другие алгоритмы кластеризации, используется для группировки схожих данных вместе.
В ходе выступления я затронул три основные темы: преимущества HDBScan, реализация и принцип работы.
Преимущества
Обычный DBScan отлично справляется с кластеризацией данных различной формы, но не справляется с кластеризацией данных различной плотности. Вы можете убедиться в этом, зайдя в сообщение в блоге Нафтали Харриса о DBScan и поигравшись с диаграммой рассеяния столбцов плотности.
Ниже представлена копия диаграммы рассеяния столбцов плотности на участке Нафтали. Вы можете видеть, что есть один главный центральный кластер и шум слева и справа.
После экспериментов с параметрами, ниже показано, как работает DBScan. Он смог получить центральный кластер, но также произвел много мини-кластеров, которые не имеют особого смысла.
Ниже показано, как работает HDBScan. Мне удалось получить только один кластер, который я искал. К сожалению, ни один алгоритм не является идеальным, и он вносит некоторый шум в пурпурный кластер, но он был ближе к тому, что я искал, чем обычный DBScan.
Помимо того, что он лучше подходит для данных с разной плотностью, он также быстрее, чем обычный DBScan. Ниже приведен график нескольких алгоритмов кластеризации, DBScan - темно-синий, а HDBScan - темно-зеленый. При отметке 200 000 записей DBScan занимает примерно вдвое больше времени, чем HDBScan. По мере увеличения количества записей будет увеличиваться несоответствие между производительностью DBScan и HDBScans.
Реализация
HDScan - это отдельная библиотека от scikitlearn, поэтому вам придется либо установить ее, либо conda.
Оба алгоритма имеют параметр минимального количества выборок, который является порогом соседства, чтобы запись стала базовой точкой.
DBScan имеет параметр epsilon, который представляет собой радиус, в котором должны находиться эти соседи для формирования ядра. Вот реализация DBScan для графика выше DBSCAN (eps = 0,225, min_samples = 4).
HDBScan имеет параметр минимального размера кластера, который определяет размер кластера для его формирования. Это более интуитивно понятно, чем эпсилон, потому что вы, вероятно, имеете представление о том, насколько большими должны быть ваши кластеры, чтобы принимать по ним действенные решения. Вот реализация HDBScan для графика выше HDBSCAN (min_samples = 11, min_cluster_size = 10, allow_single_cluster = True).
Как это работает
Оба алгоритма начинают с нахождения основного расстояния до каждой точки, которое является расстоянием между этой точкой и ее самым дальним соседом, определяемым параметром минимальных выборок. Поскольку синяя точка попадает в радиус зеленой точки, зеленая точка может захватывать синюю точку как часть своего кластера. Однако красная точка не попадает в радиус зеленой точки и наоборот, поэтому ни одна точка не может захватить друг друга (хотя они могут быть связаны через другие точки).
Потенциальные кластеры могут образовывать дендограмму, а точка отсечения для DBScan на дендограмме - эпсилон.
HDBScan подходит к этому иначе, отбрасывая крошечные побеги и вместо этого сохраняя самые большие кластеры в соответствии с параметром минимального размера кластера. Это приводит к более сжатой дендограмме, как показано ниже.
HDBScan создан для реального сценария получения данных с разной плотностью, он относительно быстр и позволяет определять, какие кластеры важны для вас, в зависимости от их размера. В целом, HDBScan кажется отличным алгоритмом. Если вам нужна ссылка на мою презентацию для соответствующего видео выше, щелкните здесь.
Источники:
Документы: http://hdbscan.readthedocs.io/
Высокопроизводительная кластеризация с HDBSCAN: https://www.youtube.com/watch?v=AgPQ76RIi6A
Визуализация кластеризации DBScan: https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/
