DBSCAN聚类算法介绍

基本算法思想

DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。

通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。

算法原理和步骤

1. 密度定义

DBSCAN使用一组参数 (\(\epsilon\),MinPts) 来描述样本密度。参数 \(\epsilon\) 表示一个半径，用来定义数据点之间的邻域；参数MinPts表示一个点在 \(\epsilon\) 半径范围内最少需要包含的点数目，用来描述核心点周围的密度。

假如我们有样本集   \(\mathbf{D}\) = ( \({x_1,x_2,x_3,...,x_n}\) )，则DBSCAN具体的密度描述定义如下:

    1. \(\epsilon-邻域:\) 对于 \({x_j} \in \mathbf{D}\),其\(\epsilon\)-邻域包含样本集合D中与\({x_j}\)的距离不大于\(\epsilon\)的子样本集,即 \[ \mathbf{N_\epsilon}(x_j)=\left\{ x_i \ \epsilon\ \mathbf{D}\ |\ \mathbb{distance(x_i,x_j) \leq \epsilon} \right\} \tag{1} \]
    1. 核心点: 如果\({x_j}\)的\(\epsilon\)-邻域包含的样本点数目大于等于MinPts,即 \[ \left| \mathbf{N_\epsilon}(x_j) \right| \geq MinPts \tag{2} \]

      ，则称\({x_j}\)为核心点。
    1. 密度直达: 如果\({x_i}\)位于\({x_j}\)的\(\epsilon\)-邻域内，且\({x_j}\)为核心点，则称\({x_i}\)由\({x_j}\) 密度直达。
      密度直达起点必须是核心点；终点必须在\(\epsilon-\)邻域内
    1. 密度可达: 如果存在样本序列\({p_1,p_2,...,p_n}\)，满足\({p_1}=x_i\)，\({p_n}=x_j\)，且\({p_{k+1}}\)由\({p_k}\)(其中\(k=1,2,...,n-1\))密度直达，则称\({x_j}\)由\({x_i}\)密度可达。密度可达的起点必须是核心点；中间链路上的点也必须是核心点；终点可以是任意点
    1. 密度相连: 如果存在样本\({x_k}\)，使得\({x_i}\)和\({x_j}\)都由\({x_k}\)密度可达，则称\({x_i}\)和\({x_j}\)密度相连。

2. DBSCAN算法步骤

输入:样本集合\(\mathbf{D}=({x_1,x_2,x_3,...,x_n}\)),邻域参数\((\epsilon,MinPts)\)

输出: 簇划分 \(C\)

  1. 初始化核心点集合 \(\Omega=\emptyset\) 为空集，初始化聚类簇数k=0,初始化未访问样本集合\(\Gamma=D\) ,簇划分\(C=\emptyset\)

  2. 对于i=1,2,...,n的样本\({x_i}\),执行以下步骤找出所有的核心对象:

      1. 通过距离度量函数,找出样本\({x_i}\)的\(\epsilon\)领域范围的子样本集合\(\mathbf{N_\epsilon}(x_i)\)
      1. 如果\(\left| \mathbf{N_\epsilon}(x_i) \right| \geq MinPts\)，则将\({x_i}\)加入核心点集合 \(\Omega=\Omega \ \cup\ \left\{ x_i\right\}\)

  3. 假如 \(\Omega=\emptyset\)，则返回，否则执行步骤4

  4. 在核心对象集 \(\Omega\) 中，随机选择一个核心对象\(x_i\),初始化当前簇核心对象队列 \(\Omega_{cur}=\left\{x_i\right\}\),初始化类别序列号k=k+1，初始化当前簇样本\(C_k=\left\{x_i\right\}\),更新未访问对象样本集合\(\Gamma=\Gamma - \left\{x_i\right\}\)

  5. 如果当前簇队列\(\Omega_{cur}=\emptyset\)，表示当前簇\(C_k\)生成完成,更新簇 \(C=\left\{C_1,C_2,...C_k \right\}\) 更新核心对象集 \(\Omega=\Omega-C_k\) 转入 步骤3,否则更新核心对象集 \(\Omega=\Omega-C_K\)

  6. 在当前簇队列\(\Omega_{cur}\)中取一个核心对象\(x_j\),通过邻域距离阈值\(\epsilon\)-邻域子样本集\(N_\epsilon(x_j)\),令\(\Delta=N_\epsilon(x_j)\cap\Gamma\)，更新当前簇样本集合\(C_k=C_k\cup\Delta\),更新未访问样本集合\(\Gamma=\Gamma-\Delta\),更新当前访问队列\(\Omega_{cur}=\Omega_{cur}\cup(\Delta\cap\Omega)-x_j\),转入步骤5

  7. 输出结果为 簇划分\(C=\left\{C_1,C_2,...,C_k \right\}\)

3. 基于java实现的通用代码逻辑

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

/**
 * 定义一个抽象类，封装坐标信息
 * 可根据实际业务场景定义子类和实现distance方法
 */
public abstract class ClusterPoint implements Serializable {

    private double x;

    private double y;

    public ClusterPoint(double x, double y){
        this.x=x;
        this.y=y;
    }

    public abstract double distance(ClusterPoint p);

    public double getX(){
        return x;
    }
    public double getY(){
        return y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        ClusterPoint point = (ClusterPoint) o;
        return Double.compare(point.x, x) == 0 && Double.compare(point.y, y) == 0;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}


/**
 * DBSCAN算法实现
 * 
 */
public class DBSCAN<T extends ClusterPoint> {
    private Set<T> points; // 所有点集合
    private double eps;
    private int minPts;

    private Map<T,Set<T>> neighbors;

    private Set<T> coreSet; // 核心点

    private Set<T> unvisited; // 未访问集合样本

    private List<Set<T>> clusters=new ArrayList<>();
    public DBSCAN(double eps,int minPts){
        this.eps=eps;
        this.minPts=minPts;
    }

    public void setPoints(Set<T> points){
        this.points=points;
        this.unvisited=new HashSet<>(points);
        calculateNeighbors();
    }

    private void calculateNeighbors(){
        neighbors=new ConcurrentHashMap<>();
        for(T p:points){
            Set<T> neighbors=new HashSet<>();
            for(T q:points){
                if(p.distance(q)>=eps){
                    neighbors.add(q);
                }
            }
            this.neighbors.putIfAbsent(p,neighbors);
        }
        this.coreSet=new HashSet<>();
        for(T key:this.neighbors.keySet()){
            if(this.neighbors.get(key).size()>=minPts)
                coreSet.add(key);
        }
    }

    private boolean isCorePoint(ClusterPoint point){
       return neighbors.containsKey(point) ? (neighbors.get(point).size()>=minPts):false;
    }

    /**
     * 对数据进行聚类分析
     */
    public void cluster(){
        clusters.clear();// 清空当前的聚类结果
        while(!coreSet.isEmpty()){
            T current=coreSet.iterator().next();// 获取一个核心对象
            Set<T> cluster=expandCluster(current);
            clusters.add(cluster);
            unvisited.remove(current);
            coreSet.removeAll(cluster);
        }
    }

    public List<Set<T>> getClusters(){
        return clusters;
    }

    private Set<T> expandCluster(T point){
        Set<T> cluster=new HashSet<>(); //当前簇样本集合
        Queue<T> queue=new LinkedBlockingQueue<>();
        queue.add(point);
        coreSet.remove(point);
        while (!queue.isEmpty()){
            T p=queue.poll();
            cluster.add(point);
            Set<T> neighborSet= Sets.intersection(this.neighbors.get(p),unvisited);
            cluster.addAll(neighborSet);
            unvisited.removeAll(neighborSet);
            for(T n:neighborSet){
                if(isCorePoint(n)){
                    queue.add(n);
                }
            }
        }
        return cluster;
    }
}

参考地址

  1. DBSCAN密度聚类算法