DBSCAN算法简介
DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。 该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。
DBSCAN算法原理
DBSCAN参数
1）eps： DBSCAN算法参数，即我们的𝜖-邻域的距离阈值，和样本距离超过𝜖的样本点不在𝜖-邻域内。默认值是0.5.一般需要通过在多组值里面选择一个合适的阈值。eps过大，则更多的点会落在核心对象的𝜖-邻域，此时我们的类别数可能会减少， 本来不应该是一类的样本也会被划为一类。反之则类别数可能会增大，本来是一类的样本却被划分开。
2）min_samples： DBSCAN算法参数，即样本点要成为核心对象所需要的𝜖-邻域的样本数阈值。默认值是5. 一般需要通过在多组值里面选择一个合适的阈值。通常和eps一起调参。在eps一定的情况下，min_samples过大，则核心对象会过少，此时簇内部分本来是一类的样本可能会被标为噪音点，类别数也会变多。反之min_samples过小的话，则会产生大量的核心对象，可能会导致类别数过少。
3）metric：最近邻距离度量参数。
4）algorithm：最近邻搜索算法参数，算法一共有三种，第一种是蛮力实现，第二种是KD树实现，第三种是球树实现。这三种方法在K近邻法(KNN)原理小结中都有讲述，如果不熟悉可以去复习下。对于这个参数，一共有4种可选输入，‘brute’对应第一种蛮力实现，‘kd_tree’对应第二种KD树实现，‘ball_tree’对应第三种的球树实现， ‘auto’则会在上面三种算法中做权衡，选择一个拟合最好的最优算法。需要注意的是，如果输入样本特征是稀疏的时候，无论我们选择哪种算法，最后scikit-learn都会去用蛮力实现‘brute’。个人的经验，一般情况使用默认的 ‘auto’就够了。 如果数据量很大或者特征也很多，用"auto"建树时间可能会很长，效率不高，建议选择KD树实现‘kd_tree’，此时如果发现‘kd_tree’速度比较慢或者已经知道样本分布不是很均匀时，可以尝试用‘ball_tree’。而如果输入样本是稀疏的，无论你选择哪个算法最后实际运行的都是‘brute’。
5）leaf_size：最近邻搜索算法参数，为使用KD树或者球树时， 停止建子树的叶子节点数量的阈值。这个值越小，则生成的KD树或者球树就越大，层数越深，建树时间越长，反之，则生成的KD树或者球树会小，层数较浅，建树时间较短。默认是30. 因为这个值一般只影响算法的运行速度和使用内存大小，因此一般情况下可以不管它。
6） p: 最近邻距离度量参数。只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择，p=1为曼哈顿距离， p=2为欧式距离。如果使用默认的欧式距离不需要管这个参数。
待聚类点分为三类：
1）核心点：如果一个对象在其半径 eps 内含有超过 MinPts 数目的点，则该对象为核心点。（如下图点A）
2）边界点：如果一个对象在其半径 eps 内含有点的数量小于 MinPts，但是该对象落在核心点的邻域内，则该对象为边界点。（如下图点B、C）
3）噪音点：如果一个对象既不是核心点也不是边界点，则该对象为噪音点。（如下图点N）
算法流程
1）DBSCAN通过检查数据集中每个点的r邻域来搜索簇，如果点p的r邻域包含多于MinPts个点，则创建一个以p为核心对象的簇；
2）DBSCAN迭代的聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并；
3）当没有新的带你添加到任何簇时，迭代过程结束。
DBSCAN算法python代码实现
# Author:Sunshine丶天
from sklearn import datasets
import numpy as np
import random
import matplotlib.pyplot as plt
def findNeighbor(j, X, eps):
N = []
for p in range(X.shape[0]): # 找到所有领域内对象
temp = np.sqrt(np.sum(np.square(X[j] - X[p]))) # 欧氏距离
if (temp <= eps):
N.append(p)
return N
def dbscan(X, eps, min_Pts):
k = -1
NeighborPts = [] # array,某点领域内的对象
Ner_NeighborPts = []
fil = [] # 初始时已访问对象列表为空
gama = [x for x in range(len(X))] # 初始时将所有点标记为未访问
cluster = [-1 for y in range(len(X))]
while len(gama) > 0:
j = random.choice(gama)
gama.remove(j) # 未访问列表中移除
fil.append(j) # 添加入访问列表
NeighborPts = findNeighbor(j, X, eps)
if len(NeighborPts) < min_Pts:
cluster[j] = -1 # 标记为噪声点
else:
k = k + 1
cluster[j] = k
for i in NeighborPts:
if i not in fil:
gama.remove(i)
fil.append(i)
Ner_NeighborPts = findNeighbor(i, X, eps)
if len(Ner_NeighborPts) >= min_Pts:
for a in Ner_NeighborPts:
if a not in NeighborPts:
NeighborPts.append(a)
if (cluster[i] == -1):
cluster[i] = k
return cluster
X1, y1 = datasets.make_circles(n_samples=2000, factor=.6, noise=.05)
X2, y2 = datasets.make_blobs(n_samples=500, n_features=2, centers=[[1.2, 1.2]], cluster_std=[[.1]],
random_state=666)
X = np.concatenate((X1, X2))
eps = 0.1
min_Pts = 10
cluster = dbscan(X, eps, min_Pts)
plt.figure(figsize=(12, 9), dpi=80)
plt.scatter(X[:, 0], X[:, 1], c=cluster)
plt.show()
DBSCAN算法sklearn实现
from sklearn.cluster import DBSCAN
from sklearn import datasets
import numpy as np
import matplotlib.pyplot as plt
X1, y1 = datasets.make_circles(n_samples=2000, factor=.6, noise=.05)
X2, y2 = datasets.make_blobs(n_samples=500, n_features=2, centers=[[1.2, 1.2]], cluster_std=[[.1]],
random_state=666)
X = np.concatenate((X1, X2))
eps = 0.1
min_Pts = 10
y_pred = DBSCAN(eps=eps, min_samples=min_Pts, metric='euclidean', metric_params=None, algorithm='auto').fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()
DBSCAN算法优缺点
优点：
（1）聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类；
（2）与K-MEANS比较起来，不需要输入要划分的聚类个数；
（3）聚类簇的形状没有偏倚；
（4）可以在需要时输入过滤噪声的参数。
缺点：
（1）当数据量增大时，要求较大的内存支持I/O消耗也很大，聚类收敛时间较长，此时可以对搜索最近邻时建立的 KD 树或者球树进行规模限制来进行改进；
（2）当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差，因为这种情况下参数min_samples和eps选取困难；
（3）算法聚类效果依赖与距离公式选取，实际应用中常用欧式距离，对于高维数据，存在“维数灾难”。
