контент
Сводка
DBSCAN
(Dплотность-bпредполагает sчастичное cотображение aприложений с nnoise) – это метод кластеризации, использующий плотность данных. Он способен идентифицировать кластеры различной формы и отделять шум от данных. Подобно K-means
, это широко используемый метод кластеризации в машинном обучении. Давайте подробнее рассмотрим, как работает DBSCAN
!
Как работает DBSCAN?
Ранее мы упоминали, что DBSCAN
— это метод, основанный на плотности. Но как определить плотность тысяч точек данных? Во-первых, нам нужно определить два гиперпараметра: радиус для определения плотности (eps
) и минимальное количество точек (minPts
). Затем для каждой точки данных мы рассматриваем круг с точкой в качестве центра и eps
в качестве радиуса. Если количество точек данных внутри круга не менее minPts
, считается, что точка находится в регионе высокой плотности (ядре).
Например, на приведенной ниже диаграмме Условие 1 и Условие 2 отличаются только значением minPts
. На левом изображении количество точек внутри круга меньше minPts
, поэтому красная точка не является основной точкой. На правом изображении количество точек внутри круга больше, чем minPts
, поэтому красная точка является основной точкой.
Если в круге есть только одна точка, мы пометим эту точку как шум, как показано желтой точкой на рисунке ниже.
Точки с числом соседних точек больше 1, но меньше minPts помечаются как граничные точки.
После определения основных точек все точки внутри круга можно пометить как один и тот же кластер. Затем выбирается следующая точка, и описанный выше процесс повторяется до тех пор, пока все точки не будут помечены. Это цикл, и он продолжается до тех пор, пока все точки не будут помечены.
На следующем gif-файле показан процесс маркировки, аналогичный распространению вируса.
Реализовать DBSCAN с помощью Python
Зная изложенный выше принцип DBSCAN
, мы можем попробовать реализовать его самостоятельно, используя Python.
Эта программа имеет два основных пункта. Во-первых, нужно использовать функцию findNeighbor
для поиска других точек вокруг заданной точки. 11-я строка использует математическую функцию в numpy
для реализации формулы евклидова расстояния. Если рассчитанное евклидово расстояние меньше установленного нами значения eps
, точка добавляется к Neighbor list
.
Второй ключевой момент — это код с строк с 32 по 45. Здесь, когда основная точка найдена, мы продолжаем проверять ее Neighbor list
и отмечаем все точки вNeighbor list
как имеющие одинаковую кластеризацию..
Наконец, мы используем matplotlib
для отображения результатов кластеризации в виде графика. Вот результат кластеризации! Вы можете видеть, что оба круга были сгруппированы правильно, а окружающие шумовые точки также были отмечены.
Преимущества и недостатки
После приведенного выше введения вы должны были осознать многие Преимущества DBSCAN
:
- Необходимо только установить
eps
иminPts
без предварительного определения количества кластеров, как вK-means
. - Возможность идентифицировать шумовые точки в данных.
- Возможность группировки с помощью связанных фигур. Как показано на рисунке ниже,
DBSCAN
может обрабатывать множество различных типов распределений, особенно первый случай двойных колец и второй случай верхних и нижних кривых.
Однако его недостатки также очевидны:
- Для определения
eps
иminPts
требуется определенное понимание распределения данных, иначе можно будет только медленно пробовать результаты кластеризации. - Поскольку глобальные значения
eps
иminPts
фиксированы, плотность распределения данных не может сильно различаться. - Вычисление евклидова расстояния между каждой точкой и другими точками приведет к огромной вычислительной нагрузке, что может привести к проклятию размерности. Вот результаты моих тестов на время вычислений, необходимое для различных размеров данных.
В приведенном выше коде реализации, поскольку каждая точка должна вычислять свое евклидово расстояние от других точек,временная сложность составляет O(n²). Как видно из диаграммы, затраченное время действительно увеличивается в геометрической прогрессии.
Эпилог
Таким образом, DBSCAN
— это метод кластеризации с явными преимуществами и недостатками. Мы надеемся, что после прочтения этой статьи вы лучше поймете принципы, лежащие в основе DBSCAN
, и сможете эффективно использовать его преимущества в будущих проектах или заданиях!