DBSCAN (Пространственная кластеризация приложений с шумом на основе плотности) — это алгоритм кластеризации, который группирует точки, близкие друг к другу, на основе критерия плотности. В отличие от других моделей кластеризации, таких как K-средние, DBSCAN может идентифицировать кластеры произвольной формы и не требует предварительного указания количества кластеров. Он менее чувствителен к шуму и может работать с кластерами разной плотности.

Чтобы получить удовлетворительный результат при использовании алгоритма DBSCAN, предполагается, что разные кластеры в данных имеют относительно одинаковую плотность, где под плотностью мы подразумеваем количество точек, существующих в каждой окрестности N(x, ε), которая определена по радиусу ε и точке данных x. Это утверждение можно оптически проверить, наблюдая пример DBSCAN в середине изображения выше, где точки вокруг синего кластера, которые имеют несколько другую плотность, считаются частью оранжевого кластера.

Единственные параметры, необходимые для реализации DBSCAN:

  • MinPts = минимальное количество точек, которое должно быть в окрестности точки данных, чтобы точка данных считалась основной точкой кластера.
  • ε =радиус окрестностей (т. е. насколько большими должны быть наши «круги» вокруг центральной точки данных)

На основе этих параметров алгоритм DBSCAN делит точки данных на три категории:

  1. Основная точка.Точка данных этого типа имеет плотность ≥ MinPts. Это означает, что количество точек данных в N(x, ε) больше или равно MinPts.

Пример: MinPts = 4, ε = 3, тогда x является центральной точкой.

2. Пограничная точка. Плотность точки данных этого типа ‹ MinPts, но расстояние (y, cp) ≤ ε, где cp — основная точка. Это означает, что эти точки не имеют плотности, необходимой для того, чтобы быть основными точками, но они также не так далеко от основных точек, чтобы их можно было считать шумом.

Пример: MinPts = 4, ε = 3, тогда y является граничной точкой.

3. Точка шума: точка данных этого типа имеет плотность ‹ MinPts и расстояние (z, cp) ≥ ε. Это означает, что она не имеет плотности, необходимой для того, чтобы быть центральной точкой, и находится далеко от любой центральной точки.

Пример: MinPts = 4, ε = 3, тогда z — точка шума.

Итак, на основе этого процесса категоризации точек данных алгоритм DBSCAN работает следующим образом:

  1. Переберите каждую точку данных и классифицируйте ее по одной из этих трех категорий.
  2. Устранение всех шумовых точек
  3. Считайте, что все основные точки, которые расположены близко друг к другу, находятся в одном кластере (это означает, что если cp_1 и cp_2 являются основными точками и расстояние (cp_1, cp_2) ≤ ε, то считается, что cp_1 и cp_2 находятся в одном кластере.)
  4. Назначьте каждую граничную точку в кластере основных точек в зависимости от их расстояния (граничные точки, которые лежат точно посередине между двумя кластерами, должны быть решены отдельно, возможно, подбросьте монету; D)

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

Преимущества DBSCAN:

  • Идентифицирует кластеры произвольной формы.
  • Не требует указания количества кластеров.
  • Он имеет высокую эффективность на наборах данных малого и среднего размера.
  • Он обнаруживает выбросы и не включает их в кластеры.

Ограничения DBSCAN:

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

Ниже приведен пример реализации алгоритма DBSCAN на Python с использованием scikit-learn.