Как эффективно использовать DBSCAN

Полное руководство по эффективному использованию самого цитируемого алгоритма кластеризации

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

Прежде чем мы начнем, убедитесь, что эти пакеты у вас под рукой.

numpy
sklearn
matplotlib # for visualization
seabron # for pretty visualizations
kneed # for our computations

Бегущий пример

Давайте сначала создадим набор данных, который может реплицировать подходящий набор точек данных для нашего анализа. Python очень щедрый со своим набором библиотек. Для генерации данных мы будем использовать функцию make blobs библиотеки sci-kit learn.

from sklearn.datasets import make_blobs
import seaborn as sns
import matplotlib.pyplot as plt
import numpy as np
centers = [[1, 0.5], [2, 2], [1, -1]]
stds = [0.1, 0.4, 0.3]
X, labels_true = make_blobs(n_samples=1000, centers=centers, cluster_std=stds, random_state=0)
fig = plt.figure(figsize=(10, 10))
sns.scatterplot(X[:,0], X[:,1], hue=["cluster-{}".format(x) for x in labels_true])

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

DBSCAN и его параметры

DBSCAN имеет несколько параметров, два из которых имеют решающее значение. Первый - это параметр eps, а второй - min_points (min_samples). Последний относится к количеству соседних точек, необходимых для того, чтобы точка считалась плотной областью или действительным кластером. Обычно мы устанавливаем это значение, которое имеет смысл для набора данных и количества измерений, присутствующих в данных. Это определит количество выявленных выбросов. Однако этот параметр не так важен, как eps.

Параметр эпсилон DBSCAN

Самый важный параметр DBSCAN можно обозначить как eps. Это самое дальнее расстояние, на котором точка выбирает своих соседей. Таким образом, интуитивно это решит, сколько соседей обнаружит точка. Хотя для min_points / min_samples мы можем указать значение по умолчанию, мы не можем этого сделать для eps. Это будет зависеть от распределения самих данных. Давайте выполним DBSCAN с некоторыми предполагаемыми значениями для нашего набора данных. Код и визуализация (на рисунке 2) будут такими, как показано ниже.

db = DBSCAN(eps=0.5, min_samples=10).fit(X)
labels = db.labels_
fig = plt.figure(figsize=(10, 10))
sns.scatterplot(X[:,0], X[:,1], hue=["cluster-{}".format(x) for x in labels])

Настройка параметра EPS

Из нашего последнего рисунка ясно видно, что два кластера были объединены. Это плохо. Такие ситуации могут уменьшить отзыв в реальном приложении кластеризации. Давайте попробуем изменить eps и снова кластеризовать. Код и визуализация (на рисунке 3) будут выглядеть, как показано ниже.

import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
fig = plt.figure(figsize=(20, 10))
fig.subplots_adjust(hspace=.5, wspace=.2)
i = 1
for x in range(10, 0, -1):
    eps = 1/(11-x)
    db = DBSCAN(eps=eps, min_samples=10).fit(X)
    core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
    core_samples_mask[db.core_sample_indices_] = True
    labels = db.labels_
    
    print(eps)
    ax = fig.add_subplot(2, 5, i)
    ax.text(1, 4, "eps = {}".format(round(eps, 1)), fontsize=25, ha="center")
    sns.scatterplot(X[:,0], X[:,1], hue=["cluster-{}".format(x) for x in labels])
    
    i += 1

Мы видим, что мы достигли оптимального значения между eps = 0,1 и eps = 0,3. Значения eps, меньшие этого значения, содержат слишком много шума или выбросов (показаны зеленым цветом). Обратите внимание, что на изображении я уменьшаю eps, увеличивая знаменатель в коде с 10 до 1. Как мы можем сделать это автоматически?

Систематический метод настройки значения eps

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

from sklearn.neighbors import NearestNeighbors
nearest_neighbors = NearestNeighbors(n_neighbors=11)
neighbors = nearest_neighbors.fit(X)
distances, indices = neighbors.kneighbors(X)
distances = np.sort(distances[:,10], axis=0)
fig = plt.figure(figsize=(5, 5))
plt.plot(distances)
plt.xlabel("Points")
plt.ylabel("Distance")
plt.savefig("Distance_curve.png", dpi=300)

from kneed import KneeLocator
i = np.arange(len(distances))
knee = KneeLocator(i, distances, S=1, curve='convex', direction='increasing', interp_method='polynomial')
fig = plt.figure(figsize=(5, 5))
knee.plot_knee()
plt.xlabel("Points")
plt.ylabel("Distance")

print(distances[knee.knee])