Архив метки: DBSCAN

Реализация алгоритма кластеризации шумных данных DBSCAN на python

Добавить комментарий

Самым известным алгоритмом кластеризации является k-means, с него начинаются все обучающие примеры по кластеризации. Но несмотря на простоту и скорость k-means, у него есть одна очень большая проблема — это наперед заданное количество кластеров. В реальном же мире чаще всего нам не известно на сколько групп следует разбить данные, более того часть данных могут быть вредными выбросами. DBSCAN отлично разбивает множество на оптимальное количество кластеров и не учитывает выбросы, неудивительно что в 2014ом году алгоритм получил метку «проверено временем» на одной из конференций по анализу данных.
Мы будет рассматривать реализация на основе библиотеки sklearn
* В алгоритма два входных параметра min_samples и eps. Если в заданной окрестности eps есть минимальное необходимое количество объектов min_samples, то данная окрестность будет считаться кластером.
* Если в заданной области нет необходимого количества объектов, то инициирующая эту область точка считается выбросом
Кластеры, найденные DBSCAN могут иметь любую форму, в отличии от алгоритма k-means (которые предполагают только выпуклую форму)

Ниже приведём простой пример кластеризации с помощью DBSCAN. 

from sklearn.datasets import load_iris
from sklearn.cluster import DBSCAN

iris = load_iris()
dbscan = DBSCAN(eps=0.5, min_samples=5)

dbscan.fit(iris.data)

# Готово! Распечатаем метки принадлежности к кластерам
print(dbscan.labels_)

Теперь давайте визуализируем полученный результат

from sklearn.decomposition import PCA
import matplotlib.pyplot as pl

pca = PCA(n_components=2).fit(iris.data)
pca_2d = pca.transform(iris.data)
for i in range(0, pca_2d.shape[0]):
    if dbscan.labels_[i] == 0:
        c1 = pl.scatter(pca_2d[i, 0], pca_2d[i, 1], c='r', marker='+')
    elif dbscan.labels_[i] == 1:
        c2 = pl.scatter(pca_2d[i, 0], pca_2d[i, 1], c='g', marker='o')
    elif dbscan.labels_[i] == -1:
        c3 = pl.scatter(pca_2d[i, 0], pca_2d[i, 1], c='b', marker='*')

pl.legend([c1, c2, c3], ['Cluster 1', 'Cluster 2', 'Noise'])
pl.title('DBSCAN finds 2 clusters and noise')
pl.show()

В результате получим вот такое разбиение по кластерам и шум
кластеризация dbscan