主要内容

DBSCAN

DBSCAN简介

基于密度的噪声应用程序空间聚类(DBSCAN)识别数据中任意形状的集群和噪声(异常值)。统计和机器学习工具箱™功能dbscan对输入数据矩阵或观察值之间的成对距离执行聚类。dbscan返回聚类索引和指示核心点(聚类内的点)观测值的向量。不像k-means聚类，DBSCAN算法不需要预先知道聚类的数量，而且聚类不一定是球形的。DBSCAN对于基于密度的离群值检测也很有用，因为它可以识别不属于任何集群的点。

要将一个点分配给一个聚类，它必须满足这样的条件，即它的邻域(ε)包含至少最小数目的邻居(minpts)．或者，这个点可以在另一个点的邻域内满足ε而且minpts条件。DBSCAN算法识别了三种点:

  • 核心点-集群中至少有minpts它的邻域

  • 边界点-集群中小于的点minpts它的邻域

  • 噪声点-不属于任何集群的离群值

DBSCAN可以使用广泛的距离度量，您可以为您的特定应用程序定义自定义距离度量。距离度量的选择决定了邻域的形状。

算法描述

对于指定的邻域值ε以及最小的邻居数minpts需要一个核心点，dbscan函数实现DBSCAN如下:

  1. 从输入数据集中X，选择第一个未标记的观测值x1作为当前点，并初始化第一个集群标签C为1。

  2. 在邻域内找到点的集合ε当前点的。这些点是相邻点。

    1. 如果邻居数小于minpts，然后将当前点标记为噪声点(或异常值)。转步骤4。

      请注意

      dbscan是否可以将噪声点重新分配给集群，如果噪声点后来满足ε而且minpts从另一个点X．这个重新分配点的过程发生在集群的边界点上。

    2. 否则，将当前点标记为属于集群的核心点C．

  3. 遍历每个邻居(新的当前点)并重复步骤2，直到没有发现可以标记为属于当前集群的新邻居C．

  4. 选择中下一个未标记的点X作为当前点，并将集群计数增加1。

  5. 重复步骤2-4，直到所有指向X已经标记出来。

确定DBSCAN参数的值

打开实时脚本

属性的值ε而且minpts的参数dbscan．数据集是激光雷达扫描，存储为3-D点的集合，其中包含车辆周围物体的坐标。

加载、预处理和可视化数据集。

加载X y z物体的坐标。

负载(“lidar_subset.mat”) X = lidar_子集;

为了突出车辆周围的环境，将感兴趣的区域设置为跨越车辆左右20米，车辆前后20米，以及路面以上的区域。

xBound = 20;米%yBound = 20;米%zLowerBound = 0;米%

裁剪数据以只包含指定区域内的点。

指数= X(:，1) <= xBound & X(:，1) >= -xBound.．.& X(:，2) <= yBound & X(:，2) >= -yBound.．.& X(:，3) > zLowerBound;X = X(指数，:);

将数据可视化为二维散点图。注释情节以突出车辆。

散射(X (: 1) X (:, 2),“。”）;注释(“椭圆”，[0.48 0.48 0.1 .1]，“颜色”，“红色”）

图中包含一个轴对象。坐标轴对象包含一个散点类型的对象。

点集的中心(红色圆圈)包含车辆的屋顶和引擎盖。所有其他点都是障碍。

为minpts．

为选择一个值minpts，考虑一个大于或等于1加上输入数据[1]的维数的值。例如，对于一个n——- - - - - -p矩阵X，设置的值“minpts”大于或等于p＋1．

对于给定的数据集，指定aminpts大于或等于4的值，特别是值50。

薄荷= 50;一个核心点的最小邻居数

为ε．

一种估算值的策略ε就是生成一个k-distance图用于输入数据X．对于中的每一点X，求到的距离k最近的点，然后根据这个距离画出排序的点。图中有一个膝盖。与膝盖对应的距离一般是比较好的选择ε，因为它是点开始逐渐减少到异常值(噪声)区域[1]的区域。

在绘制k-distance图，首先找到minpts观测的最小成对距离X，按升序排列。

kD = pdist2(X,X，“euc”，“最小”, minpts);

画出k——远程图。

情节(排序(kD(最终,:)));标题(“英里的距离图”)包含(按第50个最近距离排序的点) ylabel (“第50个最近距离”网格)

图中包含一个轴对象。标题为k-distance graph的axes对象包含一个line类型的对象。

膝盖大概在2;因此，设置的值ε2。

= 2;

集群使用dbscan．

使用dbscan价值观是minpts而且ε在前面的步骤中确定的。

标签= dbscan(X,epsilon,minpts);

可视化集群，并注释该图以突出显示特定的集群。

numGroups =长度(唯一的(标签));gscatter (X (: 1) X(:, 2),标签,hsv (numGroups));标题('epsilon = 2 and minpts = 50')网格注释(“椭圆”，[0.54 0.41 .07 .07]，“颜色”，“红色”)注释(“椭圆”，[0.53 0.85 .07 .07]，“颜色”，“蓝”)注释(“椭圆”，[0.39 0.85 .07 .07]，“颜色”，“黑”）

图中包含一个轴对象。标题为epsilon = 2和minpts = 50的axes对象包含12个line类型的对象。这些对象分别代表-1、1、2、3、4、5、6、7、8、9、10、11。

dbscan标识11个集群和一组噪声点。该算法还将位于点集中心的车辆识别为一个不同的集群。

dbscan标识一些不同的集群，例如黑色圈出的集群(以(- 6,18)为中心)和蓝色圈出的集群(以(2.5,18)为中心)。该函数还分配了一组用红色圈出的点(并以(3、4))到与图东南象限的点组相同的聚类(组7)。我们期望这些组应该在单独的集群中。

使用较小的值ε拆分大型集群并进一步划分点。

2 = 1;labels2 = dbscan(X,epsilon2，薄荷);

可视化集群，并注释该图以突出显示特定的集群。

numGroups2 =长度(唯一的(labels2));gscatter (X (: 1) X (:, 2), labels2, hsv (numGroups2));标题('epsilon = 1 and minpts = 50')网格注释(“椭圆”，[0.54 0.41 .07 .07]，“颜色”，“红色”)注释(“椭圆”，[0.53 0.85 .07 .07]，“颜色”，“蓝”)注释(“椭圆”，[0.39 0.85 .07 .07]，“颜色”，“黑”）

图中包含一个轴对象。标题为epsilon = 1和minpts = 50的axes对象包含17个line类型的对象。这些对象分别代表-1、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16。

通过使用一个较小的值，dbscan能够将红圈的点组分配到不同的聚类(组13)。然而，一些集群认为dbscan以前正确识别的数据现在被划分为聚类点和异常值。例如，请参见集群组2(黑色圈出的部分)和集群组3(蓝色圈出的部分)。正确的εValue在1和2之间。

使用一个ε的价值1.55对数据进行聚类。

Epsilon3 = 1.55;labels3 = dbscan(X,epsilon3，薄荷);

可视化集群，并注释该图以突出显示特定的集群。

numGroups3 =长度(唯一的(labels3));gscatter (X (: 1) X (:, 2), labels3, hsv (numGroups3));标题('epsilon = 1.55 and minpts = 50')网格注释(“椭圆”，[0.54 0.41 .07 .07]，“颜色”，“红色”)注释(“椭圆”，[0.53 0.85 .07 .07]，“颜色”，“蓝”)注释(“椭圆”，[0.39 0.85 .07 .07]，“颜色”，“黑”）

图中包含一个轴对象。标题为epsilon = 1.55和minpts = 50的axes对象包含16个line类型的对象。这些对象分别代表-1、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15。

dbscan什么时候能更好地识别集群ε设置为1.55．例如，该函数标识用红色、黑色和蓝色圈出的不同簇(中心围绕(3、4)、(- 6,18)和(2.5,18)。

参考文献

酯，M.， h . p。Kriegel, J. Sander, X. Xiaowei。“一种基于密度的算法，用于在有噪声的大型空间数据库中发现集群。”在第二届数据库和数据挖掘中的知识发现国际会议论文集, 226 - 231。波特兰:AAAI出版社，1996年。

相关的话题

Baidu
map