机器学习——聚类——密度聚类法——DBSCAN

目录

• • • 理论部分
    • • 1.1 提出背景
      • 1.2 常见算法
      • 1.3 DBSCAN算法
      • 1.4 评估指标
    • 代码部分

理论部分

1.1 提出背景

与K-means算法基于距离聚类不同，DBSCAN算法是基于样本点密度进行聚类。基于距离的聚类方法只适用于凸型数据尤其是球状分布的数据，而难以处理非凸数据，而密度聚类法可以很好地解决这个问题，密度聚类法的基本思想是只要一个区域中的点的密度大过某个阀值，就把它加到与之相近的聚类中去。

1.2 常见算法

基于密度的聚类算法有很多，例如DBSCAN算法、OPTICS算法、DENCLUE算法、基于密度峰值的聚类方法等。本篇我们着重讲解DBSCAN。

1.3 DBSCAN算法

1.3.1 基本概念

设 X = [ x 1 , x 2 , ⋯   , x n ] X=[x^{1},x^{2},\cdots,x_{n}] X=[x1,x2,⋯,xn​]为样本集， ϵ \epsilon ϵ表示领域半径， M M M表示密度阈值，则有：

· ϵ \epsilon ϵ领域
N ϵ ( x ) = { y ∈ X ∣ d ( x , y ) < ϵ } N_{\epsilon}(x)=\{y\in X|d(x,y)<\epsilon\} Nϵ​(x)={y∈X∣d(x,y)<ϵ}
即表示以 x x x为中心， ϵ \epsilon ϵ为半径的圆内样本点的集合（包括自身）。

· ρ ( x ) \rho(x) ρ(x)密度

ρ ( x ) = ∣ N ϵ ( x ) ∣ \rho(x)=|N_{\epsilon}(x)| ρ(x)=∣Nϵ​(x)∣
x x x的密度定义为 x x x的 ϵ \epsilon ϵ领域内的样本点个数。

·核心点

令 x ∈ X x\in X x∈X,若 ρ ( x ) ≥ M \rho(x) \geq M ρ(x)≥M，则成 x x x为 X X X的核心点，记 X X X中所有核心点构成的集合为 X c X_{c} Xc​，所有非核心点构成的集合为 X n c X_{nc} Xnc​

PS:简单来说，核心点即为满足在 ϵ \epsilon ϵ领域内至少有密度阈值个样本点的点。

·边界点

若 x ∈ X n c x\in X_{nc} x∈Xnc​(即 x x x为非核心点),且 ∃ y ∈ X \exists y \in X ∃y∈X，满足：
y ∈ N ϵ ( x ) ∩ X c y \in N_{\epsilon}(x)\cap X_{c} y∈Nϵ​(x)∩Xc​
则称 x x x为边界点，令样本点中所有边界点构成的集合为 X b c X_{bc} Xbc​

PS：边界点可以理解为指那些落入核心点 ϵ \epsilon ϵ领域内的但不是核心点的样本点。

·噪声点

若样本点 x x x同时有：
x ∈ X , x ∉ X c a n d x ∉ X b d x\in X,x\notin X_{c} and x \notin X_{bd} x∈X,x∈/​Xc​andx∈/​Xbd​
则称 x x x为噪声点。

PS:噪声点可以理解为既不是核心点也不是边界点的样本点。即若某个样本点在其 ϵ \epsilon ϵ领域内不具有至少密度阈值个样本点，同时该样本点也不落在任何核心点的 ϵ \epsilon ϵ领域内，则称该样本点为噪声点。

如上图，蓝色样本点即为核心点，黑色样本为边界点，白色样本为噪声点。

·密度直达

对于样本点 x , y x,y x,y,若有：
x ∈ N ϵ ∣ ( y ) x\in N_{\epsilon|(y)} x∈Nϵ∣(y)​
ρ y = ∣ N ϵ ∣ ( y ) ∣ ≥ M \rho_{y}=|N_{\epsilon|(y)}|\geq M ρy​=∣Nϵ∣(y)​∣≥M
则称 x x x是由 y y y关于参数 ( ϵ , M ) (\epsilon,M) (ϵ,M)密度直达。

PS： x x x是由 y y y密度直达的等效为以下说法： y y y是核心点且 x x x处在 y y y的 ϵ \epsilon ϵ领域内。

·密度可达

对于样本点 x , y x,y x,y,如果存在一系列样本点 p 1 , p 2 , ⋯   , p n ( p 1 = x , p n = y ) p_{1},p_{2},\cdots ,p_{n}(p_{1}=x,p_{n}=y) p1​,p2​,⋯,pn​(p1​=x,pn​=y)，若 p i + 1 p_{i+1} pi+1​能够由 p i p_{i} pi​密度直达 ( i = 1 , 2 , 3 , ⋯   , n − 1 ) (i=1,2,3,\cdots ,n-1) (i=1,2,3,⋯,n−1)，则称 y y y 可由 x x x密度可达。

·密度相连

如果存在一个样本点 z z z，使得 x x x y y y均可由 z z z密度可达，则称 x x x y y y是密度相连的。

1.3.2 算法流程

该算法流程可大致描述如下：首先确定所有的核心点从而构成核心点集合（并将这些核心点标注为已访问）。而后每次选取一个核心点，并将由其可密度直达且尚未访问的点归为该核心点对应的类别中（同时将这些点标注为已访问），以此类推。

1.3.3 参数设置

若 ϵ \epsilon ϵ或者 M M M设置得非常小，则意味着没有点是核心样本，可能会导致所有点被标记为噪声
若 ϵ \epsilon ϵ或者 M M M设置得非常大，可能会导致所有点形成单个簇。

1.3.3 优点

1.不必提前设置聚类数。
2.对非凸型数据处理能力较强，可以对任意类内稠密，类间系数的样本集进行聚类。
3.对异常点敏感性较低，可以较为有效地排除异常点的干扰。
4.可优化性强，部分步骤可由数据结构中的相关算法进行优化。

1.3.4 缺点

1.需要设置 ϵ \epsilon ϵ和 M M M，而这往往是依靠人的直觉和经验的。
2.在大规模数据集上效率较低。

属于簇的点是实心，噪声点则显示为空心，核心样本点显示为较大的标记，而边界点则显示为较小的标记，上图即验证了 ϵ \epsilon ϵ和 M M M取值大小对结果的影响。

1.3.5 可视化结果展示

上图为DBSCAN算法对于非球形分布数据的聚类过程。

上图为DBSCAN聚类结果（左图）和K-means聚类结果（右图）的对比

不同的 ϵ \epsilon ϵ和 M M M设置也会导致不同的结果：

1.4 评估指标

这里仍然可以采用轮廓系数进行评估，关于轮廓系数的介绍可以见另一篇博客K均值聚类法介绍

代码部分

2.1 不使用sklearn实现

import matplotlib.pyplot as plt
import random
import numpy as np
import math
from sklearn import datasets
 
list_1 = []
list_2 = []
def loadDataSet(fileName, splitChar='\t'):
    dataSet = []
    with open(fileName) as fr:
        for line in fr.readlines():
            curline = line.strip().split(splitChar)
            fltline = list(map(float, curline))
            dataSet.append(fltline)
    return dataSet
 
# 计算两个点之间的欧式距离，参数为两个元组
def dist(t1, t2):
    dis = math.sqrt((np.power((t1[0]-t2[0]),2) + np.power((t1[1]-t2[1]),2)))
    # print("两点之间的距离为："+str(dis))
    return dis
 
# DBSCAN算法，参数为数据集，Eps为指定半径参数，MinPts为制定邻域密度阈值
def dbscan(Data, Eps, MinPts):
    num = len(Data)  # 点的个数
    # print("点的个数："+str(num))
    unvisited = [i for i in range(num)]  # 没有访问到的点的列表
    # print(unvisited)
    visited = []  # 已经访问的点的列表
    C = [-1 for i in range(num)]
    # C为输出结果，默认是一个长度为num的值全为-1的列表
    # 用k来标记不同的簇，k = -1表示噪声点
    k = -1
    # 如果还有没访问的点
    while len(unvisited) > 0:
        # 随机选择一个unvisited对象
        p = random.choice(unvisited)
        unvisited.remove(p)
        visited.append(p)
        # N为p的epsilon邻域中的对象的集合
        N = []
        for i in range(num):
            if (dist(Data[i], Data[p]) <= Eps):# and (i!=p):
                N.append(i)
        # 如果p的epsilon邻域中的对象数大于指定阈值，说明p是一个核心对象
        if len(N) >= MinPts:
            k = k+1
            # print(k)
            C[p] = k
            # 对于p的epsilon邻域中的每个对象pi
            for pi in N:
                if pi in unvisited:
                    unvisited.remove(pi)
                    visited.append(pi)
                    # 找到pi的邻域中的核心对象，将这些对象放入N中
                    # M是位于pi的邻域中的点的列表
                    M = []
                    for j in range(num):
                        if (dist(Data[j], Data[pi])<=Eps): #and (j!=pi):
                            M.append(j)
                    if len(M)>=MinPts:
                        for t in M:
                            if t not in N:
                                N.append(t)
                # 若pi不属于任何簇，C[pi] == -1说明C中第pi个值没有改动
                if C[pi] == -1:
                    C[pi] = k
        # 剩余点既不是核心点也不是边界点
        else:
            C[p] = -1
 
    return C
 
dataSet = loadDataSet(r'D:\Deeplearning\788points.txt', splitChar=',')
C = dbscan(dataSet, 2, 14)
print(C)
x = []
y = []
for data in dataSet:
    x.append(data[0])
    y.append(data[1])
plt.figure(figsize=(8, 6), dpi=80)
plt.scatter(x,y, c=C, marker='o')
plt.show()

结果如下：

2.2 使用sklearn实现

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
%matplotlib inline
X1, y1=datasets.make_circles(n_samples=5000, factor=.6,
                                      noise=.05)
X2, y2 = datasets.make_blobs(n_samples=1000, n_features=2, centers=[[1.2,1.2]], cluster_std=[[.1]],
               random_state=9)

X = np.concatenate((X1, X2))
plt.scatter(X[:, 0], X[:, 1], marker='o')
plt.show()
y_pred = DBSCAN(eps = 0.1, min_samples = 10).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

结果如下：

未经允许，请勿转载

欢迎交流