Основанная на плотности пространственная кластеризация для приложений с шумами (DBSCAN)

Основанная на плотности пространственная кластеризация для приложений с шумами (DBSCAN) by Лена Капаца Nov. 7, 2021 Продвинуто

Основанная на плотности пространственная кластеризация для приложений с шумами (DBSCAN) – это метод Обучения без учителя (Unsupervised Learning), при котором группируем точки Наблюдений (Observation) на основе определенных характеристик в Кластеры (Cluster) произвольной формы:

Очевидное преимущество DBSCAN (справа) перед K-Means в случае необычной формы кластера

На изображении выше есть точки данных, расположенные в виде концентрических кругов. Мы видим три различных плотных кластера в виде концентрических кругов с некоторым Шумом (Noise). Мы запустили Метод K-средних (K-Means) и получили четыре кластера. Данные содержат шум, поэтому и выделили четвертую группу наблюдений, обозначенную фиолетовым цветом. К сожалению, методу не удалось корректно сгруппировать точки. Кроме того, он не смог должным образом обнаружить шум. Теперь давайте посмотрим на результаты кластеризации DBSCAN.

DBSCAN не только может правильно выделить кластеры сложной формы, но также отлично обнаруживает шум. Метод создан Мартином Эстером и коллегами в 1996 году. Это алгоритм, основанный на плотности, который работает с предположением, что кластеры представляют собой плотные области в пространстве, разделенные "пустующими" областями.

Он собирает "плотно сгруппированные» точки данных в один кластер. Самая интересная особенность кластеризации DBSCAN заключается в том, что она устойчива к Выбросам (Outlier). Также не требуется указывать количество кластеров заранее.

DBSCAN требует только два параметра: epsilon (радиус круга, который должен быть создан вокруг каждой точки данных для проверки плотности) и minPoints (минимальное количество точек данных, необходимых внутри этого круга для того, чтобы эта точка данных была классифицирована как базовая).

Здесь у нас есть некоторые точки данных, представленные серым цветом:

Давайте посмотрим, как DBSCAN кластеризует эти точки данных.

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

Точка данных является центральной, если круг вокруг нее не менее minPoints точек. Если количество точек меньше minPoints, то оно классифицируется как граничная точка, а если нет других точек в пределах эпсилон-радиуса, то точка рассматривается как шум.

Все точки данных с как минимум 3 точками в круге считаются основными точками и обозначены красным цветом. Все точки данных с менее чем 3, но более чем 1 точкой в круге, включая ее саму, считаются граничными точками. Они представлены желтым цветом. Наконец, точки данных, внутри круга которых нет другой точки, считаются шумом (фиолетовый цвет).

Для определения местоположения точек данных в пространстве DBSCAN использует Евклидово расстояние (Euclidean Distance), хотя можно использовать и другие методы. Ему необходимо просканировать весь набор данных один раз, тогда как в других алгоритмах нам приходится делать это несколько раз.

Доступность и cвязность

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

Точки X и Y плотностно достижимые (Density Reachable) для точки O
Точки X и Y плотностно связаны (Density Connected) друг с другом
Точки O и A напрямую плотностно достижимы (Directly Density Reachable) друг другу

Выбор параметров в кластеризации DBSCAN

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

Значение minPoints должно быть как минимум на единицу больше, чем количество Признаков (Feature) в наборе данных. Нет смысла принимать minPoints за 1, потому что это приведет к тому, что каждая точка будет отдельным кластером. Следовательно, его значение должно быть не менее 3.

DBSCAN: Scikit-learn

Давайте посмотрим, как метод реализован в SkLearn. Для начала импортируем необходимые библиотеки:

import numpy as np
import pandas as pd
import math

import matplotlib
import matplotlib.pyplot as plt

import sklearn
from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors

Здесь я создаю набор данных только с двумя признаками, чтобы мы могли легко его визуализировать. Для создания Датасета (Dataset) я создал функцию PointsInCircum, которая принимает радиус и количество точек данных в качестве аргументов и возвращает массив точек данных, который при нанесении на график образует круг:

np.random.seed(42)

# Функция, позволяющая создать кластеры в форме окружности 
def PointsInCircum(r, n = 100): return [(math.cos(2 * math.pi / n * x) * r + np.random.normal(-30, 30), math.sin(2 * math.pi/ n * x) * r + np.random.normal(-30, 30)) for x in range(1, n + 1)]

Одного круга недостаточно, чтобы увидеть способность DBSCAN к кластеризации. Поэтому создадим три концентрических круга разного радиуса. Кроме того, добавим шума, чтобы видеть, как метод с ним справляется:

# Создадим датафрейм в форме кругов
df = pd.DataFrame(PointsInCircum(500, 1000))
df = df.append(PointsInCircum(300, 700))
df = df.append(PointsInCircum(100, 300))

# Добавим шум
df = df.append([(np.random.randint(-600, 600), np.random.randint(-600, 600)) for i in range(300)])

Давайте построим эти точки данных и посмотрим, как они выглядят в пространстве функций. Здесь я использую диаграмму рассеяния для построения этих точек данных. Используйте следующий синтаксис:

plt.figure(figsize = (10, 10))
plt.scatter(df[0], df[1], s = 15, color = 'grey')
plt.title('Датасет', fontsize = 20)
plt.xlabel('Признак 1', fontsize = 14)
plt.ylabel('Признак 2', fontsize = 14)
plt.show()

Пришло время внедрить DBSCAN и убедиться в его мощи. Давайте сначала запустим его без какой-либо оптимизации параметров и посмотрим на результаты.

# Инициализируем метод
dbscan = DBSCAN()
dbscan.fit(df[[0, 1]])

DBSCAN(algorithm='auto', eps=0.5, leaf_size=30, metric='euclidean',
       metric_params=None, min_samples=5, n_jobs=None, p=None)

Epsilon равен 0,5, а min_samples (minPoints) – 5. Давайте визуализируем результаты этой модели:

df['DBSCAN_labels'] = dbscan.labels_ 

# Отобразим точки на графике
plt.figure(figsize = (10, 10))
plt.scatter(df[0], df[1], c = df['DBSCAN_labels'], cmap = matplotlib.colors.ListedColormap(colors), s = 15)
plt.title('DBSCAN', fontsize = 20)
plt.xlabel('Признак 1', fontsize = 14)
plt.ylabel('Признак 2', fontsize = 14)
plt.show()

Все точки данных теперь фиолетового цвета, что означает, что они рассматриваются как шум:

Это потому, что значение epsilon очень мало, и мы не оптимизировали параметры. Следовательно, нам нужно найти значение epsilon и minPoints, а затем снова обучить нашу модель.

Для эпсилона я использую график K-расстояний – дистанций между точкой и ближайшей к ней точкой данных для всех точек в наборе:

neigh = NearestNeighbors(n_neighbors = 2)
nbrs = neigh.fit(df[[0, 1]])
distances, indices = nbrs.kneighbors(df[[0, 1]])

# Отобразим график расстояний между точками
distances = np.sort(distances, axis = 0)
distances = distances[:, 1]
plt.figure(figsize = (20, 10))
plt.plot(distances)
plt.title('K-distance Graph', fontsize = 20)
plt.xlabel('Data Points sorted by distance', fontsize = 14)
plt.ylabel('Epsilon', fontsize = 14)
plt.show()

Построим наш график K-расстояний и найдем значение эпсилон:

Оптимальное значение эпсилон находится в точке максимальной кривизны на графике K-расстояний, которая в данном случае равна 30. Узнаем значение minPoints. На этот раз попробуем значение 6:

dbscan_opt = DBSCAN(eps = 30, min_samples = 6)
dbscan_opt.fit(df[[0, 1]])

DBSCAN(algorithm='auto', eps=30, leaf_size=30, metric='euclidean',
       metric_params=None, min_samples=6, n_jobs=None, p=None)

Самое удивительное в DBSCAN – это его способность отделять шум.

df['DBSCAN_opt_labels'] = dbscan_opt.labels_
df['DBSCAN_opt_labels'].value_counts()

DBSCAN сгруппировал точки данных в три кластера, а также обнаружил шум в наборе данных, представленном фиолетовым цветом. Здесь 0, 1 и 2 – три разных кластера, а -1 – это шум.

0    1030
 1     730
 2     318
-1     222
Name: DBSCAN_opt_labels, dtype: int64

Давайте построим график результатов и посмотрим, что у нас получится:

# Обозначим кластеры разными цветами
colors = ['purple', 'red', 'blue', 'green']
plt.figure(figsize = (10, 10))
plt.scatter(df[0], df[1], c = df['DBSCAN_opt_labels'], cmap = matplotlib.colors.ListedColormap(colors), s = 15)
plt.title('DBSCAN Clustering', fontsize = 20)
plt.xlabel('Feature 1',fontsize=14)
plt.ylabel('Feature 2',fontsize=14)
plt.show()

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

Кроме того, по мере увеличения размера данных этому Алгоритму (Algorithm) становится трудно создавать кластеры, и он становится жертвой Проклятия размерности (Curse of Dimensionality).

Ноутбук, не требующий дополнительной настройки на момент написания статьи, можно скачать здесь.

Автор оригинальной статьи: Abhishek Sharma