基于Matlab应用DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)
一、算法原理
Matlab中的统计与机器学习工具箱(The Statistics and Machine Learning Toolbox™)中开发了函数dbscan。DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一种典型的基于密度的聚类算法,能够将足够高密度的区域划分成簇,并能在具有噪声的空间数据库中发现任意形状的簇。它是基于一组“邻域”参数来刻画样本分布的紧密程度。
要将一个点分配给一个簇,它必须满足这样的条件:它的邻域(epsilon)包含至少最小数量的邻域(minpts)点。或者,这个点可以在另一个点的邻域内满足minpts条件。DBSCAN算法识别了三种点:
- 核心点——簇中的一个点,在它的邻域中至少有minpts个点
- 边界点-簇中的一个点,它的邻域中点的个数小于minpts
- 噪声点-不属于任何簇的离群值
DBSCAN可以使用广泛的距离度量方法,您可以为特定的应用背景定义自定义距离度量(不同特征)。距离度量的选择决定了邻域的形状。
对于指定的epsilon邻域epsilon值和核心点所需的最小邻域点数目minpts,dbscan函数实现功能的流程如下:
- 从输入数据集X中,选择第一个未标记的观测值x1作为当前点,并将第一个聚类标签C初始化为1。
- 找出在当前点的邻域内的点的集合。这些点是相邻点。如果邻居的数量小于minpts,则将当前点标记为噪声点(或异常值)。转步骤4。否则,将当前点标记为属于簇C的核心点。
- 遍历每个邻居节点(新的当前点)并重复步骤2,直到没有发现可以标记为属于当前簇C的新邻居节点。
- 选择X中的下一个未标记的点作为当前点,并将聚类计数增加1。
- 重复步骤2-4,直到标记X中的所有点。
这个例子展示了如何为dbscan的epsilon和minpts参数选择值。数据集是激光雷达扫描,存储为3-D点的集合,其中包含车辆周围物体的坐标。
加载、预处理和可视化数据集
加载物标的x, y, z坐标。
load('lidar_subset.mat')
X = lidar_subset;
为了突出车辆周围的环境,将感兴趣的区域设置为跨越车辆左右20米,车辆前后20米,以及路面以上的区域。
xBound = 20; % in meters
yBound = 20; % in meters
zLowerBound = 0; % in meters
裁剪数据以只包含指定区域内的点。
indices = X(:,1) <= xBound & X(:,1) >= -xBound ...
& X(:,2) <= yBound & X(:,2) >= -yBound ...
& X(:,3) > zLowerBound;
X = X(indices,:);
将数据可视化为二维散点图。突出车辆周围区域。
scatter(X(:,1),X(:,2),'.');
annotation('ellipse',[0.48 0.48 .1 .1],'Color','red')
点集的中心(红色圆圈)包含车辆的顶和引擎盖。所有其他点都是障碍。
选择minpts值
要为minpts值选择一个值,请考虑一个大于或等于1加上输入数据[1]的维数的值。例如,对于n × p矩阵X,设置'minpts'的值大于或等于p+1。
对于给定的数据集,指定一个大于或等于4的minpts值,特别是值50。
minpts = 50; % 核心点邻居节点的最小数值
选择邻域范围
估计邻域范围的一种方法是为输入数据X生成k-distance图。对于X中的每个点,找到到第k个最近点的距离,并根据这个距离绘制排序点。图中有一个变化较大的区域。与该区域对应的距离通常是邻域范围的一个很好的选择,因为它是点开始逐渐消失到异常值(噪声)区域的区域。
在绘制k-距离图之前,首先找到X中观测值的最小成对距离,按升序排列。
kD = pdist2(X,X,'euc','Smallest',minpts); % The minpts smallest pairwise distances
画出k-距离图。
plot(sort(kD(end,:)));
title('k-distance graph')
xlabel('Points sorted with 50th nearest distances')
ylabel('50th nearest distances')
Grid
拐点大概在2;因此,将ε的值设为2。
使用dbscan进行聚类
基于前面步骤中确定的minpts和epsilon值使用dbscan。
labels = dbscan(X,epsilon,minpts);
将聚类可视化,并对图进行注释以突出特定的聚类。
gscatter(X(:,1),X(:,2),labels);
title('epsilon = 2 and minpts = 50')
grid
annotation('ellipse',[0.54 0.41 .07 .07],'Color','red')
annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue')
annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')
Dbscan识别了11个簇和一组噪声点。该算法还将位于点集中心的车辆识别为一个不同的簇。
Dbscan识别一些不同的簇,例如黑色圈出的簇(并以(- 6,18)为中心)和蓝色圈出的簇(并以(2.5,18)为中心)。该函数还将以(3,-4)为中心圈出的一组点指定为同一类(第7组),即图中东南象限的一组点。我们的期望是这些组应该位于单独的簇中。
使用较小的值来分割较大的簇,并进一步划分点。
epsilon2 = 1;
labels2 = dbscan(X,epsilon2,minpts);
将聚类可视化,并对图进行注释以突出特定的聚类。
gscatter(X(:,1),X(:,2),labels2);
title('epsilon = 1 and minpts = 50')
grid
annotation('ellipse',[0.54 0.41 .07 .07],'Color','red')
annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue')
annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')
通过使用较小的epsilon值,dbscan能够将红色圈出的点组分配到一个不同的簇(组13)。然而,dbscan之前正确识别的一些簇现在在簇点和离群点之间分裂。例如,参见聚类组2(黑色圈出)和聚类组3(蓝色圈出)。正确的值在1和2之间。
使用epsilon值1.55对数据进行聚类。
epsilon3 = 1.55;
labels3 = dbscan(X,epsilon3,minpts);
将聚类可视化,并对图进行注释以突出特定的聚类。
gscatter(X(:,1),X(:,2),labels3);
title('epsilon = 1.55 and minpts = 50')
grid
annotation('ellipse',[0.54 0.41 .07 .07],'Color','red')
annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue')
annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')
当epsilon设置为1.55时,Dbscan可以更好地识别聚类。例如,该函数识别红、黑、蓝圈出的不同簇(分别以(3,-4)、(-6,18)和(2.5,18)为中心)。