主要内容

dbscan

基于密度的带噪声应用的空间聚类

折叠所有页面

语法

idx = dbscan(X,epsilon，薄荷)
idx = dbscan(X,epsilon,minpts，名称，值)
idx = dbscan(D,epsilon,minpts，'Distance'，'预计算')
[idx,corepts] = dbscan(___）

描述

例子

idx= dbscan (X，ε，minpts）在n——- - - - - -p数据矩阵X使用DBSCAN算法(参见算法)．dbscan基于邻域搜索半径的阈值对观测值(或点)进行聚类ε和最小数量的邻居minpts需要确定一个核心点。函数返回一个n-by-1向量(idx)，包含每个观测值的聚类指数。

例子

idx= dbscan (X，ε，minpts，名称,值）使用一个或多个名称-值对参数指定其他选项。例如，您可以指定“距离”、“闵可夫斯基”,“P”3在DBSCAN算法中使用指数为3的闵科夫斯基距离度量。

例子

idx= dbscan (D，ε，minpts，“距离”“预算”)返回预先计算的成对距离的聚类索引向量D之间的观察。D可以输出的pdist或pdist2的输出格式，或更一般的不相似向量或矩阵pdist或pdist2,分别。

例子

［idx，corepts= dbscan(___）还返回一个逻辑向量corepts包含了由dbscan，使用前面语法中的任何输入参数组合。

例子

全部折叠

打开实时脚本

使用DBSCAN和默认的欧几里得距离度量对2-D圆形数据集进行聚类。另外，比较使用DBSCAN和DBSCAN对数据集进行聚类的结果k-表示聚类与平方欧几里得距离度量。

生成包含两个噪声圆的合成数据。

rng (“默认”）%用于再现性%数据生成参数N = 300;%每个集群的大小R1 = 0.5;%第一个圆的半径R2 = 5;%第二圆半径= linspace(0,2*pi,N)';X1 = r1*[cos(theta)，sin(theta)]+ rand(N,1);X2 = r2*[cos(theta)，sin(theta)]+ rand(N,1);X = [x1; x2];%噪声二维圆形数据集

可视化数据集。

散射(X (: 1), (2):,)

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

该图显示数据集包含两个不同的集群。

对数据进行DBSCAN聚类。指定一个ε1和a的值minpts5的值。

idx = dbscan(X,1,5);默认的距离度量是欧氏距离

可视化集群。

gscatter (X (: 1) X (:, 2), idx);标题(使用欧几里得距离度量的DBSCAN）

图中包含一个轴对象。标题为DBSCAN Using Euclidean Distance Metric的axis对象包含2个类型为line的对象。这些物体表示1,2。

使用欧几里得距离度量，DBSCAN可以正确地识别数据集中的两个集群。

使用平方欧几里得距离度量执行DBSCAN聚类。指定一个ε1和a的值minpts5的值。

idx2 = dbscan(X,1,5，“距离”，“squaredeuclidean”）;

可视化集群。

gscatter (X (: 1) X (:, 2), idx2);标题(使用平方欧几里得距离度量的DBSCAN）

图中包含一个轴对象。标题为DBSCAN Using Squared Euclidean Distance Metric的axis对象包含2个类型为line的对象。这些物体表示1,2。

使用平方欧几里得距离度量，DBSCAN正确地识别了数据集中的两个集群。

执行k-表示使用平方欧氏距离度量的聚类。指定k= 2个集群。

kidx = kmeans(X,2);默认距离度量是欧几里得距离的平方

可视化集群。

gscatter (X (: 1) X (:, 2), kidx);标题(使用平方欧氏距离度规的K-Means）

图中包含一个轴对象。标题为K-Means的axis对象包含2个类型为line的对象。这些物体表示1,2。

使用平方欧几里得距离度规，k-表示聚类无法正确识别数据集中的两个聚类。

打开实时脚本

执行DBSCAN聚类，使用观测值之间的成对距离矩阵作为输入dbscan函数，并找到异常值和核心点的数量。数据集是激光雷达扫描，存储为3-D点的集合，其中包含车辆周围物体的坐标。

加载X y z物体的坐标。

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

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

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

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

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

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

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

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

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

预先计算一个成对距离的矩阵D在观察值之间使用pdist2函数。

D = pdist2(loc,loc);

使用对数据进行聚类dbscan用成对距离。指定一个ε2和a的值minpts值为50。

[idx, corepts] = dbscan(D,2,50，“距离”，“预算”）;

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

numGroups =长度(唯一的(idx));gscatter (loc (: 1), loc (:, 2), idx, hsv (numGroups));注释(“椭圆”，[0.54 0.41 .07 .07]，“颜色”，“红色”网格)

图中包含一个轴对象。axis对象包含12个line类型的对象。这些对象分别代表-1、1、2、3、4、5、6、7、8、9、10、11。

如散点图所示，dbscan识别11个集群，并将车辆放置在单独的集群中。

dbscan指定一组用红色圈出的点(并以(3、4))到与图东南象限的点组相同的聚类(组7)。我们期望这些组应该在单独的集群中。您可以尝试使用较小的值ε拆分大型集群并进一步划分点。

该函数还标识了一些异常值(anidx的价值1)。求出点的个数dbscan标识为异常值。

求和(idx == -1)
Ans = 412

dbscan从19,070个观测值中识别出412个异常值。

求出点的个数dbscan标识为核心点。一个corepts的价值1表示核心点。

Sum (corepts == 1)
Ans = 18446

dbscan确定18,446个观察结果为核心点。

看到确定DBSCAN参数的值这是一个更广泛的例子。

输入参数

全部折叠

的输入数据n——- - - - - -p数字矩阵。一排排的X对应观测值(或点)，列对应变量。

数据类型:单|双

的输出，指定为数值行向量的观测值之间的成对距离pdist，数值方阵的输出pdist2、逻辑行向量或逻辑方阵。D也可以是更一般的不相似向量或矩阵，符合的输出格式pdist或pdist2,分别。

对于上述规范，下表描述了用于D可以取，给定一个输入矩阵X有n观察(行)和p维度(列)。

规范 格式
数字行向量(的输出pdist (X)）

  • 长度的行向量n（n- 1) / 2，对应于中的观测值对X

  • 按顺序排列的距离(2,1)，(3,1)，…, (n，1)，(3,2)，…, (n, 2),…, (n，n- 1))
数字方阵(输出pdist2 (X, X)）

  • 一个n——- - - - - -n矩阵,D (i, j)观测值之间的距离是多少我和j在X

  • 对角线元素为零的对称矩阵
逻辑行向量

  • 长度的行向量n（n- 1) / 2，对应于中的观测值对X

  • 一种逻辑行向量，其元素指示距离小于或等于ε

  • 的元素D按顺序排列(2,1)，(3,1)，…, (n，1)，(3,2)，…, (n, 2),…, (n，n- 1))
逻辑方阵

  • 一个n——- - - - - -n矩阵,D (i, j)表示观测值之间的距离我和j在X小于等于ε

请注意

如果D逻辑上是向量还是矩阵，那么值是多少ε必须是空的;例如,dbscan (D[] 5,“距离”,“预计”)．

数据类型:单|双|逻辑

点的Epsilon邻域，指定为一个数值标量，用于定义围绕该点的邻域搜索半径。如果一点的邻域包含至少minpts邻居,然后dbscan将该点标识为核心点。

的价值ε必须为空(［］)当D是逻辑向量或矩阵。

例子:dbscan (X, 2.5, 10)

例子:dbscan (D[] 5,“距离”,“预计”)，表示逻辑矩阵或向量D

数据类型:单|双

一个核心点所需的最小邻居数，以正整数指定。簇中核心点的邻域必须至少包含minpts邻域，而边界点的ε邻域可以包含的邻域小于minpts．

例子:dbscan (X, 2.5, 5)

数据类型:单|双

名称-值参数

指定可选参数对为Name1 = Value1,…,以=家,在那里的名字参数名称和价值对应的值。名称-值参数必须出现在其他参数之后，但对的顺序无关紧要。

在R2021a之前，使用逗号分隔每个名称和值，并将其括起来的名字在报价。

例子:dbscan (2.5 D, 5‘距离’,“预算”)指定DBSCAN集群使用预计算的成对距离矩阵D的邻域2.5的最小值5邻居。

距离度量，指定为逗号分隔的对，由“距离”和字符向量、字符串标量或函数句柄，如本表所述。

价值 描述
“预算”

预先计算的距离。如果第一个输入为，则必须指定此选项dbscan是成对距离的向量还是矩阵D．
“欧几里得”

欧氏距离(默认值)
“squaredeuclidean”

欧式距离的平方。(此选项仅为提高效率而提供。它不满足三角形不等式。)
“seuclidean”

标准化欧氏距离。观测值之间的每个坐标差都通过除以相应的标准偏差元素来缩放，S = std(X，'omitnan')．使用规模为指定另一个值年代．
“mahalanobis”

的样本协方差的马氏距离X，C = cov(X，'omitrows')．使用浸为指定另一个值C，其中矩阵C是对称且正定的。
“cityblock”

城市街区距离
闵可夫斯基的

闵可夫斯基距离。默认指数为2。使用P要指定不同的指数，其中P为正标量值。
“chebychev”

切比雪夫距离(最大坐标差)
的余弦

1减去点间夹角的余弦(作为向量处理)
“相关”

1减去点之间的样本相关性(作为值序列处理)
“汉明”

汉明距离，也就是不同坐标的百分比
“jaccard”

1减去杰卡德系数，也就是非零坐标的百分比
“枪兵”

1减去观测值之间的样本斯皮尔曼秩相关(作为值序列处理)
@distfun

自定义距离函数句柄。距离函数有这样的形式

函数D2 = distfun(ZI,ZJ)距离计算%.．.
在哪里

  • 子是一个1——- - - - - -n包含单个观测值的向量。

  • ZJ是一个平方米——- - - - - -n包含多个观测值的矩阵。distfun必须接受一个矩阵ZJ用任意数量的观测值。

  • D2是一个平方米——- - - - - -1距离向量，和D2 (k)观测值之间的距离是多少子和ZJ (k,:)．

如果数据不是稀疏的，通常可以通过使用内置距离而不是函数句柄来更快地计算距离。

有关定义，请参见距离度量．

当你使用“seuclidean”，闵可夫斯基的,或“mahalanobis”距离度量时，可以指定附加的名称-值对参数“规模”，“P”,或“浸”，分别控制距离度量。

例子:dbscan (X 2.5 5,“距离”,“闵可夫斯基”,“P”,3)的邻域2.5，最小为5的指数，并使用闵可夫斯基距离度量3.执行聚类算法时。

闵可夫斯基距离度量的指数，指定为逗号分隔的对，由“P”一个正标量。

这个论点只有在以下情况下才成立“距离”是闵可夫斯基的．

例子:“P”3

数据类型:单|双

马氏距离度量的协方差矩阵，指定为逗号分隔的对，由“浸”一个对称的，正定的，数值矩阵。

这个论点只有在以下情况下才成立“距离”是“mahalanobis”．

数据类型:单|双

标准化欧几里得距离度量的比例因子，指定为逗号分隔的对，由“规模”和一个正数值向量。

的每个维度(列)X有相应的值在“规模”；因此,“规模”长度p的列数X)．对于的每个维度X，dbscan中使用相应的值“规模”标准化之间的差异X还有一个查询点。

这个论点只有在以下情况下才成立“距离”是“seuclidean”．

数据类型:单|双

输出参数

全部折叠

群集索引，作为数值列向量返回。idx有n行，每一行idx中对应观测值的聚类分配X．下标等于1指示一个异常值(或噪声点)。

请注意

使用DBSCAN算法的聚类分配依赖于观测的顺序。因此，洗牌的行X可以为观测结果分配不同的聚类。详情请参见算法．

数据类型:双

用于核心点的指示器，返回为n——- - - - - -1逻辑向量，表示所识别的核心点的指数dbscan．值为1在任何一行corepts表示在X是一个核心点。否则,corepts值为0对应于不是核心点的观测值的行。

数据类型:逻辑

更多关于

全部折叠

核心要点

集群中的核心点是具有至少最小数量的邻居(minpts)在它们的邻域(ε)．每个集群至少包含一个核心点。

边界点

集群中的边界点是指小于核心点所要求的最小邻居数的点(minpts)在它们的邻域(ε)．通常，边界点的邻域包含的点明显少于核心点的邻域。

噪声点

噪声点是不属于任何聚类的异常值。

提示

  • 用于提高迭代多个值时的速度ε，考虑通过D作为的输入dbscan．这种方法可以防止函数必须在迭代的每个点上计算距离。

  • 如果你使用pdist2预先执行D，不指定“最小”或“最大”的名称-值对参数pdist2对…的列进行选择或排序D．选择少于n距离会导致错误，因为dbscan预计D是一个方阵。的每一列的距离排序D导致了在诠释上的失落D并且在使用时会给出无意义的结果dbscan函数。

  • 为了有效地使用内存，可以考虑传入D作为一个逻辑矩阵，而不是一个数字矩阵dbscan当D很大。默认为MATLAB®使用8字节(64位)将每个值存储在数值矩阵中，使用1字节(8位)将每个值存储在逻辑矩阵中。

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

  • 选择值的一种可能策略ε就是生成一个k-距离图X．对于中的每一点X，求到的距离k最近的点，然后根据这个距离画出排序的点。通常，图中包含一个膝盖。与膝盖对应的距离通常是一个很好的选择ε，因为它是点开始逐渐减少到异常值(噪声)区域[1]的区域。

算法

  • DBSCAN是一种基于密度的聚类算法，用于发现数据中的聚类和噪声。算法识别出三种点:核心点、边界点和噪声点[1]。对于指定的值ε和minpts,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可以识别属于彼此靠近的两个集群的边界点。在这种情况下，算法将边界点分配给第一个发现的聚类。因此，第二个集群仍然是一个有效的集群，但它可以小于minpts观察。

参考文献

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

版本历史

在R2019a中引入

另请参阅

|||||

主题