原理
DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。
通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。
一些概念
x1是核心对象，x2由x1密度直达，x3由x1密度可达，x3与x4密度相连
伪码
python代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
from sklearn import datasets import numpy as np import random import matplotlib.pyplot as plt import time import copy def find_neighbor(j, x, eps): N = list() for i in range(x.shape[0]): temp = np.sqrt(np.sum(np.square(x[j]-x[i]))) # 计算欧式距离 if temp <= eps: N.append(i) return set(N) def DBSCAN(X, eps, min_Pts): k = -1 neighbor_list = [] # 用来保存每个数据的邻域 omega_list = [] # 核心对象集合 gama = set([x for x in range(len(X))]) # 初始时将所有点标记为未访问 cluster = [-1 for _ in range(len(X))] # 聚类 for i in range(len(X)): neighbor_list.append(find_neighbor(i, X, eps)) if len(neighbor_list[-1]) >= min_Pts: omega_list.append(i) # 将样本加入核心对象集合 omega_list = set(omega_list) # 转化为集合便于操作 while len(omega_list) > 0: gama_old = copy.deepcopy(gama) j = random.choice(list(omega_list)) # 随机选取一个核心对象 k = k + 1 Q = list() Q.append(j) gama.remove(j) while len(Q) > 0: q = Q[0] Q.remove(q) if len(neighbor_list[q]) >= min_Pts: delta = neighbor_list[q] & gama deltalist = list(delta) for i in range(len(delta)): Q.append(deltalist[i]) gama = gama - delta Ck = gama_old - gama Cklist = list(Ck) for i in range(len(Ck)): cluster[Cklist[i]] = k omega_list = omega_list - Ck return cluster X1, y1 = datasets.make_circles(n_samples=2000, factor=.6, noise=.02) X2, y2 = datasets.make_blobs(n_samples=400, n_features=2, centers=[[1.2, 1.2]], cluster_std=[[.1]], random_state=9) X = np.concatenate((X1, X2)) eps = 0.08 min_Pts = 10 begin = time.time() C = DBSCAN(X, eps, min_Pts) end = time.time() plt.figure() plt.scatter(X[:, 0], X[:, 1], c=C) plt.show() |
效果
选用iris鸢尾花数据集更改
|
1 2 |
from sklearn.datasets import load_iris X = load_iris().data |
缺点
参数敏感Eps , MinPts ,若选取不当 ,会造成聚类质量下降。
