Реализация алгоритма DBSCAN для поиска основных образцов
DBSCAN - сокращение от Пространственная кластеризация приложений с шумом на основе плотности - это алгоритм кластеризации на основе плотности. Кластеры формируются по параметрам плотности.
Плотность в терминах DBSCAN означает количество точек, расположенных в данной области. Чем ближе точки друг к другу, тем больше будет плотность.
Алгоритм DBSCAN принимает 2 параметра; ε - эпсилон, который представляет собой радиус основных точек и минимальное количество точек данных в кластере.
На диаграмме ниже, взятой из Википедии, минимальные точки выбраны как 4, minPts = 4.
Точка A и все другие красные точки называются основными точками, потому что они заключают в свой круг как минимум 4 точки. Точки B и C являются граничными точками, они не являются основными, потому что они не охватывают минимальное количество 4 точек. Точка N - это шумовая точка.
Алгоритм DBSCAN можно разделить на следующие основные этапы:
- Нахождение количества точек в охвате ε точки и определение основных точек.
- Нахождение компонентов связности основных точек в окрестности.
- Присвоение каждой граничной точки соседнему кластеру основной точки, если точка находится поблизости, в противном случае назначьте ее шуму.
Точки, которые находятся в плотной области, называются образцами керна. В следующем примере кода мы будем использовать DBSCAN Sklearn для поиска основных образцов самогенерируемых данных.
Код
В этом сегменте статьи мы пройдемся по коду, чтобы найти образцы ядра с высокой плотностью и расширить из них кластеры.
Импорт библиотек и модулей
Прежде всего, давайте импортируем соответствующие библиотеки и модули. Мы импортируем NumPy, метрики Sklearn, алгоритм DBSCAN из Sklearn, функцию make_blobs, которая позволяет нам генерировать капли точек с гауссовым распределением и StandardScaler, который используется для стандартизации функций.
import numpy as np from sklearn.cluster import DBSCAN from sklearn import metrics from sklearn.datasets import make_blobs from sklearn.preprocessing import StandardScaler
Создание образцов данных
Затем мы сгенерируем образцы данных, сначала создав центры, а затем сгенерируя капли с помощью функции make_blobs и стандартизировав наши функции.
У нас будет 3 центра со следующими координатами: (1, 1), (-1, -1) и (1, -1).
centers = [[1, 1], [-1, -1], [1, -1]]
Используя функцию make_blobs, мы сгенерируем капли с общим количеством точек 750, поровну разделенных между кластерами, с центрами, заданными центральным массивом, и стандартным отклонением 0,4.
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4,
random_state=0)
В результате получатся массивы NumPy: X и labels_true.
Затем мы применим стандартизацию функций с помощью StandardScaler () на X. Это позволит стандартизировать функции, удалив среднее значение и масштабируя его до единичной дисперсии.
X = StandardScaler().fit_transform(X)
Вычисление DBSCAN
После того, как мы создали и стандартизировали наши данные, мы развернем алгоритм DBSCAN из Sklearn со значением epsilon = 0,3 и 10 как минимальное количество образцов в кластере.
db = DBSCAN(eps=0.3, min_samples=10).fit(X)
Затем мы определим массив core_sample_mask, имеющий те же размеры, что и метки. core_sample_mask будет массивом из 750 элементов с нулями (False).
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
После подгонки модели DBSCAN к данным мы вычислим core_samples_mask.
core_samples_mask[db.core_sample_indices_] = True
Затем мы сохраним значения меток всех точек данных в массиве меток.
labels = db.labels_
В массиве меток всего 4 значения: 0, 1, 2 и -1. Значения 0,1 и 2 относятся к трем кластерам, состоящим из данных, тогда как -1 - это метка, присвоенная тем точкам данных, основные точки выборки которых не совпадают с таковыми в массиве центров.
Количество кластеров и шум
Теперь напечатаем количество сформированных кластеров, игнорируя точки данных шума, а также общее количество выбросов:
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
n_noise_ = list(labels).count(-1)
print('Estimated number of clusters: %d' % n_clusters_)
print('Estimated number of noise points: %d' % n_noise_)
У нас есть 3 кластера и 18 выбросов / шум:
Построение кластеров
Наконец, давайте построим сгруппированные результаты. Мы будем использовать matplotlib для построения кластеров.
import matplotlib.pyplot as plt
unique_labels = set(labels)
colors = [plt.cm.Spectral(each)
for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
if k == -1:
# Black used for noise.
col = [0, 0, 0, 1]
class_member_mask = (labels == k)
xy = X[class_member_mask & core_samples_mask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
markeredgecolor='k', markersize=14)
xy = X[class_member_mask & ~core_samples_mask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
markeredgecolor='k', markersize=6)
plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()
Как видно на рисунке выше, точки данных, сгенерированные с помощью выборочных данных, сгруппированы вместе в 3 основных тела.
Все точки, выходящие за пределы кластеров, являются выбросами / шумом и, таким образом, окрашены в черный цвет.
Вывод
В этой статье мы использовали алгоритм DBSCAN компании Sklearn, который представляет собой неконтролируемый алгоритм кластеризации для самогенерируемых выборочных данных. Алгоритм кластеризации DBSCAN смог сгруппировать вместе точки данных на основе радиуса и минимальных точек в радиусе, которые мы указали в качестве входных данных через код.
Алгоритм DBSCAN имеет ряд применений. Он используется в маркетинговых исследованиях для распознавания закономерностей, анализа данных и обработки изображений. Это весьма полезно для отделения кластеров с высокой плотностью от кластеров с низкой плотностью в наборе данных и устойчивых с обнаружением выбросов.
Надеюсь, вам понравилось читать статью! 😃
Вы до сих пор использовали DBSCAN в каком-либо проекте?
