контент

1. Резюме

2. Как работает DBSCAN?

3. Реализовать DBSCAN с помощью Python

4. Преимущества и недостатки

5. Эпилог

Сводка

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:

  1. Необходимо только установитьepsиminPts без предварительного определения количества кластеров, как в K-means.
  2. Возможность идентифицировать шумовые точки в данных.
  3. Возможность группировки с помощью связанных фигур. Как показано на рисунке ниже, DBSCAN может обрабатывать множество различных типов распределений, особенно первый случай двойных колец и второй случай верхних и нижних кривых.

Однако его недостатки также очевидны:

  1. Для определения eps и minPts требуется определенное понимание распределения данных, иначе можно будет только медленно пробовать результаты кластеризации.
  2. Поскольку глобальные значения eps и minPts фиксированы, плотность распределения данных не может сильно различаться.
  3. Вычисление евклидова расстояния между каждой точкой и другими точками приведет к огромной вычислительной нагрузке, что может привести к проклятию размерности. Вот результаты моих тестов на время вычислений, необходимое для различных размеров данных.

В приведенном выше коде реализации, поскольку каждая точка должна вычислять свое евклидово расстояние от других точек,временная сложность составляет O(n²). Как видно из диаграммы, затраченное время действительно увеличивается в геометрической прогрессии.

Эпилог

Таким образом, DBSCAN — это метод кластеризации с явными преимуществами и недостатками. Мы надеемся, что после прочтения этой статьи вы лучше поймете принципы, лежащие в основе DBSCAN, и сможете эффективно использовать его преимущества в будущих проектах или заданиях!