参考来源：公众号：我的学城：一文掌握DBSCAN聚类。

认识DBSCAN

DBSCAN全称Density-Based Spatial Clustering of Applications with Noise，翻译过来就是基于密度的噪声应用空间聚类。

一句话形容就是，DBSCAN基于密度，它可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。

DBSCAN算法基于点的密度而不是点之间的距离，此外它也不要求我们指定集群的数量，不仅有效避免了异常值，并且在任意形状和大小的集群上都具有非常好的聚类效果。

 

实现原理

DBSCAN是如何实现的呢?

1、概念

在具体讲实现步骤前，我们需要了解几个概念。

第一个是算法参数：半径（epsilon）、最小点数目（minpts）

（1）epsilon：计算的最大半径（epsilon ）。如果数据点的相互距离小于或等于指定的epsilon，那么它们在同一邻域。换句话说，它是DBSCAN用来确定两个点是否相似和属于同一类的距离。更大的epsilon将产生更大的簇（包含更多的数据点），更小的epsilon将构建更小的簇。

（2）最小点(minpts)：在一个邻域内，点的最小数量。这些点被认为是一个簇。这里要特别注意，初始点包含在minpts中。一个较低的minpts帮助算法建立更多的集群与更多的噪声或离群值。较高的minpts将确保更健壮的集群，但如果集群太大，较小的集群将被合并到较大的集群中。

第二个是点类型：核心点、边界点、噪声点。

 

 

DBSCAN会先判断点的类型，根据一定规则把点分为核心点、边界点、噪声点。

（1）核心点：以该点为圆心，如果给定半径epsilon内含有大于等于minpts数目的点，那么该点就是核心点。

（2）边界点：以该点为圆心，如果给定半径epsilon内含有不超过minpts数目的点，并且落在核心点的epsilon半径内。

（3）噪声点：不是核心点也不是边界点的点。

第三个是点关系：密度直达、密度可达、密度相连、非密度相连。

 

 

密度直达：如果P为核心点，Q在P的邻域内，那么称P到Q密度直达。反之不一定成立，即此时不能说Q到P密度直达，除非Q也是核心点，即密度直达不满足对称性。

如上图左，4为核心点，1在4的邻域内，那么4到1密度直达。

密度可达：如果存在核心点P2,P3,……,Pn,并且P1到P2密度直达，P2到P3密度直达，……,Pn-1到Pn密度直达，Pn到Q密度直达，则P1到Q密度可达。密度可达也不具备对称性。

如上图中，4、5为核心点，1在4的邻域内，4到1密度直达。那么5到1密度可达。

密度相连：如果存在核心点S，使得S到P和Q都密度可达，则P和Q密度相连。密度相连具有对称性，如果P和Q密度相连，那么Q和P也一定密度相连。密度相连的连个点属于同一聚类簇。

如上图右，4、5为核心点，1在4的邻域内，6在5邻域内，5到1密度可达，5到6密度直达，所以6和1之间密度相连。

非密度相连：如果两个点不属于密度相连关系，则两个点非密度相连。非密度相连的两个点属于不同的聚类簇，或者其中存在噪声点。如上图右，8与其它点都非密度相连。

三者的定义

 

 

2、 实现步骤

基本概念搞懂后，我们来看看DBSCAN算法的具体步骤。

第一步，寻找核心点形成临时的聚类簇。扫描全部样本点，如果某个样本点的半径范围内（epsilon）点的数目>=minpts，则界定为核心点，放入核心点集合，并将其密度直达的点形成对应的临时聚类簇。

 

如上图，对每一个点执行点计算（假设minpts=5），如果该点邻域内的点数量大于等于5个，则为核心点，并记录核心点及其邻域内的点。如果该点邻域内的点数量小于5个，且位于核心点邻域内，则为边界点。其余为噪声点。三种点分别用红色、蓝色和绿色表示。

 

如上图，扫描结束后，记录临时聚类簇与核心点。

第二步，合并临时聚类簇得到聚类簇。以任意一个核心点出发，找出其密度可达的样本生成聚类簇，直到所有核心对象均被访问过为止。

如上图，循环核心点集合CP中的所有点，直至核心点内所有点都被循环。每次迭代时，判断簇间是否密度可达，可达则生成聚类簇。当然，刚才演示非常简单，可以从https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/看看多点的演示。

3、如何确定最优的Epsilon与minPts？

结合上面的介绍，我们发现，DBSCAN是直接给定了半径epsilon和minpts。也就是直接定义了最小密度，那么密度较小的簇最终会被忽略掉。所以，选择合适的epsilon和minpts非常关键。那如何确定最优的epsilon和minpts呢？

 

 DBSCAN聚类的簇的尺寸问题

      关于DBSCAN聚类的尺寸问题是本人在工作中了解到的相关信息。大致算法流程是：

前提条件是DBSCAN将一帧的原始数据（经过距离、速度和角度FFT之后得到的数据）经过处理后已经聚成了一个或多个簇。

1）根据原始数据中保存的一帧数据，先计算簇中x方向和y方向距离的据平均值，记为xcenter,ycenter，作为聚类尺寸的中心点。

2）然后初始化尺寸大小为xsize=0,ysize=0。

3）选择簇中的第一个点作为核心点，计算该点到中心点（xcenter,ycenter）的距离，记为temp_x,temp_y。然后将其与xsize,ysize进行比较。取最大值存为新的xsize,ysize。

4）之后依次比较簇中其他点到中心点（xcenter,ycenter）的距离，取其中最大的值作为新的xsize,ysize。从而作为DBSCAN聚类的簇的尺寸。

5）另外如果得到的xsize,ysize有一个是为0的，那么会将xsize,ysize等于一个固定的值。

 1 %detObj2D是存储的原始数据，clusterOriginator是选择的第一个核心点
 2 sumx = detObj2D(clusterOriginator,10);
 3 sumy = detObj2D(clusterOriginator,11);
 4 
 5 for ind = 1:length1
 6     
 7     member = neighStart(ind);
 8     sumx =sumx+ detObj2D(member,10);
 9     sumy =sumy+ detObj2D(member,11);
10     
11 end
12 
13 lengthInv = (1/(length1 + 1));%/取倒数   length是聚类的簇的点的个数
14 xCenter = sumx * lengthInv;%//取横坐标的平均值
15 yCenter = sumy * lengthInv;%//纵坐标的平均值
16 
17 xSize = 0;
18 ySize = 0;
19 
20 strongestPeakVal = detObj2D(clusterOriginator,4);
21 strongestMember = clusterOriginator;
22 
23 temp =  (detObj2D(clusterOriginator,10) - xCenter);
24 % //abs
25 if (temp > 0)
26     temp=temp;
27 else
28     temp=-temp;
29 end
30 %    //max
31 if (xSize > temp)
32     xSize=xSize;
33 else
34     xSize=temp;
35 end
36 temp =  (detObj2D(clusterOriginator,11) - yCenter);
37 %//abs
38 if (temp > 0)
39     temp=temp;
40 else
41     temp=-temp;
42 end
43 %         //max
44 if (ySize > temp)
45     ySize=ySize;
46 else
47     ySize=temp;
48 end
49 for ind = 1: length1%求取聚类的框的长和宽以及峰值，平均中心与每一个邻居点做对比，差值大的被选中
50     
51     member = neighStart(ind);       %簇中的数据对应的原始数据的下标
52     temp =  detObj2D(member,10) - xCenter;
53     % abs
54     if (temp > 0)
55         temp=temp;
56     else
57         temp=-temp;
58     end
59     %    max
60     if (xSize > temp)
61         xSize=xSize;
62     else
63         xSize=temp;
64     end
65     
66     temp = detObj2D(member,11) - yCenter;
67     %abs
68     if (temp > 0)
69         temp=temp;
70     else
71         temp=-temp;
72     end
73     %         max
74     if (ySize > temp)
75         ySize=ySize;
76     else
77         ySize=temp;
78     end
79 
80 end
81 
82 %If the size is absurd, due to the fact that the cluster has only  one point, put in a more reasonable number. 
83 if ((xSize == 0) || (ySize == 0))
84     
85     xSize = (3.0* rangeResolution * oneQFormat);
86     ySize = (3.0 * rangeResolution * oneQFormat);
87 end

 

 如有侵权，请联系删除。