基于密度的聚类算法（1）——DBSCAN详解

article/2025/10/2 3:21:58

基于密度的聚类算法（1）——DBSCAN详解
基于密度的聚类算法（2）——OPTICS详解
基于密度的聚类算法（3）——DPC详解

1. DBSCAN简介
DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种典型的基于密度的空间聚类算法。和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

该算法利用基于密度的聚类的概念，即要求聚类空间中的一定区域内所包含对象（点或其他空间对象）的数目不小于某一给定阈值。DBSCAN算法的显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。但是当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差。

2. DBSCAN的优缺点
和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点，这点和BIRCH算法类似。

那么什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。
（1）DBSCAN的优点：
1） 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
2） 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
3） 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。
（2）DBSCAN的缺点：
1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
2） 如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
3） 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响

3. DBSCAN详细描述及参数含义
DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(ϵ, MinPts)用来描述邻域的样本分布紧密程度。其中，ϵ描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为ϵ的邻域中样本个数的阈值。
　　　　假设样本集是*D=(x1,x2,...,xm)*,则DBSCAN具体的密度描述如下：
　　　　1） ϵ-邻域：对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 这个子样本集的个数记为|Nϵ(xj)|　
　　　　2) 核心对象：对于任一样本xj∈D，如果其ϵ-邻域对应的Nϵ(xj)至少包含MinPts个样本，即如果|Nϵ(xj)|≥MinPts，则xj是核心对象。　
　　　　3）密度直达：如果xi位于xj的ϵ-邻域中，且xj是核心对象，则称xi由xj密度直达。注意反之不一定成立，即此时不能说xj由xi密度直达, 除非且xi也是核心对象。
　　　　4）密度可达：对于xi和xj,如果存在样本样本序列p1,p2,...,pT,满足p1=xi,pT=xj, 且pt+1由pt密度直达，则称xj由xi密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本p1,p2,...,pT−1均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。
　　　　5）密度相连：对于xi和xj,如果存在核心对象样本xk，使xi和xj均由xk密度可达，则称xi和xj密度相连。注意密度相连关系是满足对称性的。

从下图可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心对象，因为其ϵ-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的ϵ-邻域内所有的样本相互都是密度相连的。
在这里插入图片描述
4. DBSCAN思想
　　DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。
　　这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。
　　　　
　　那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。

这基本上就是DBSCAN算法的主要内容了，但是还有三个问题没有考虑：
　　1）一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。
　　2）距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。
　　3）第三种问题比较特殊，某些样本可能到两个核心对象的距离都小于ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法

5. DBSCAN算法步骤
下面是DBSCAN聚类算法的主要步骤
　　输入：样本集D=(x1,x2,...,xm)，邻域参数(ϵ,MinPts), 样本距离度量方式
　　输出： 簇划分C.　
　　
　　1）初始化核心对象集合Ω=∅, 初始化聚类簇数k=0，初始化未访问样本集合Γ = D, 簇划分C = ∅
　　2) 对于j=1,2,…m, 按下面的步骤找出所有的核心对象：
　　　 a) 通过距离度量方式，找到样本xj的ϵ-邻域子样本集Nϵ(xj)
　　　 b) 如果子样本集样本个数满足|Nϵ(xj)|≥MinPts， 将样本xj加入核心对象样本集合：Ω=Ω∪{xj}
　　3）如果核心对象集合Ω=∅，则算法结束，否则转入步骤4.
　　4）在核心对象集合Ω中，随机选择一个核心对象o，初始化当前簇核心对象队列Ωcur={o}, 初始化类别序号k=k+1，初始化当前簇样本集合Ck={o}, 更新未访问样本集合Γ=Γ−{o}
　　5）如果当前簇核心对象队列Ωcur=∅，则当前聚类簇Ck生成完毕, 更新簇划分C={C1,C2,...,Ck}, 更新核心对象集合Ω=Ω−Ck， 转入步骤3。否则更新核心对象集合Ω=Ω−Ck。
　　6）在当前簇核心对象队列Ωcur中取出一个核心对象o′,通过邻域距离阈值ϵ找出所有的ϵ-邻域子样本集Nϵ(o′)，令Δ=Nϵ(o′)∩Γ, 更新当前簇样本集合Ck=Ck∪Δ, 更新未访问样本集合Γ=Γ−Δ, 更新Ωcur=Ωcur∪(Δ∩Ω)−o′，转入步骤5.
　　输出结果为： 簇划分C={C1,C2,…,Ck}

6. DBSCAN算法在python scikit-learn实现
　　在scikit-learn中，DBSCAN算法类为sklearn.cluster.DBSCAN。要熟练的掌握用DBSCAN类来聚类，除了对DBSCAN本身的原理有较深的理解以外，还要对最近邻的思想有一定的理解。
　　DBSCAN重要参数也分为两类，一类是DBSCAN算法本身的参数，一类是最近邻度量的参数：
　　1）eps： DBSCAN算法参数，即我们的ϵ-邻域的距离阈值，和样本距离超过ϵ的样本点不在ϵ-邻域内。默认值是0.5.一般需要通过在多组值里面选择一个合适的阈值。eps过大，则更多的点会落在核心对象的ϵ-邻域，此时我们的类别数可能会减少， 本来不应该是一类的样本也会被划为一类。反之则类别数可能会增大，本来是一类的样本却被划分开。
　　2）min_samples： DBSCAN算法参数，即样本点要成为核心对象所需要的ϵ-邻域的样本数阈值。默认值是5. 一般需要通过在多组值里面选择一个合适的阈值。通常和eps一起调参。在eps一定的情况下，min_samples过大，则核心对象会过少，此时簇内部分本来是一类的样本可能会被标为噪音点，类别数也会变多。反之min_samples过小的话，则会产生大量的核心对象，可能会导致类别数过少。
　　3）metric：最近邻距离度量参数。可以使用的距离度量较多，一般来说DBSCAN使用默认的欧式距离（即p=2的闵可夫斯基距离）就可以满足我们的需求。可以使用的距离度量参数有：
　　　　a) 欧式距离 “euclidean”
　　　　b) 曼哈顿距离 “manhattan”
　　　　c) 切比雪夫距离“chebyshev”
　　　　d) 闵可夫斯基距离 “minkowski”
　　　　e) 带权重闵可夫斯基距离 “wminkowski”
　　　　f) 标准化欧式距离 “seuclidean”: 即对于各特征维度做了归一化以后的欧式距离。此时各样本特征维度的均值为0，方差为1.
　　　　g) 马氏距离“mahalanobis”：当样本分布独立时，马氏距离等同于欧式距离。
　还有一些其他不是实数的距离度量，一般在DBSCAN算法用不上，这里也就不列了。
　　
　　4）algorithm：最近邻搜索算法参数，算法一共有三种，第一种是蛮力实现，第二种是KD树实现，第三种是球树实现。对于这个参数，一共有4种可选输入，‘brute’对应第一种蛮力实现，‘kd_tree’对应第二种KD树实现，‘ball_tree’对应第三种的球树实现， ‘auto’则会在上面三种算法中做权衡，选择一个拟合最好的最优算法。需要注意的是，如果输入样本特征是稀疏的时候，无论我们选择哪种算法，最后scikit-learn都会去用蛮力实现‘brute’。个人的经验，一般情况使用默认的 ‘auto’就够了。 如果数据量很大或者特征也很多，用"auto"建树时间可能会很长，效率不高，建议选择KD树实现‘kd_tree’，此时如果发现‘kd_tree’速度比较慢或者已经知道样本分布不是很均匀时，可以尝试用‘ball_tree’。而如果输入样本是稀疏的，无论你选择哪个算法最后实际运行的都是‘brute’。
　　5）leaf_size：最近邻搜索算法参数，为使用KD树或者球树时， 停止建子树的叶子节点数量的阈值。这个值越小，则生成的KD树或者球树就越大，层数越深，建树时间越长，反之，则生成的KD树或者球树会小，层数较浅，建树时间较短。默认是30. 因为这个值一般只影响算法的运行速度和使用内存大小，因此一般情况下可以不管它。
　　6） p: 最近邻距离度量参数。只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择，p=1为曼哈顿距离， p=2为欧式距离。如果使用默认的欧式距离不需要管这个参数。
　　以上就是DBSCAN类的主要参数介绍，需要调参的两个参数eps和min_samples，这两个值的组合对最终的聚类效果有很大的影响。因此，DBSCAN聚类算法的结果对参数比较敏感，基于DBSCAN开发的OPTICS聚类算法则很好的解决了这个问题，后续会更新OPTICS算法的详解。

生成一组随机数据，为了体现DBSCAN在非凸数据的聚类优点，我们生成了三簇数据，两组是非凸的

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
%matplotlib inline
X1, y1=datasets.make_circles(n_samples=5000, factor=.6,noise=.05)
X2, y2 = datasets.make_blobs(n_samples=1000, n_features=2, centers=[[1.2,1.2]], cluster_std=[[.1]],random_state=9)X = np.concatenate((X1, X2))
plt.scatter(X[:, 0], X[:, 1], marker='o')
plt.show()

在这里插入图片描述

1）利用K-Means聚类，代码如下：

from sklearn.cluster import KMeans
y_pred = KMeans(n_clusters=3, random_state=9).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

在这里插入图片描述
2）使用DBSCAN，用默认参数，代码如下：

from sklearn.cluster import DBSCAN
y_pred = DBSCAN().fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

在这里插入图片描述
但是聚类结果是只有一类。。。

3）使用DBSCAN，调整两个重要参数：
从上图可以发现，类别数太少，因此需要增加类别数，可以通过减少ϵ-邻域的大小来实现，默认是0.5，减到0.1看看效果。代码如下：

y_pred = DBSCAN(eps = 0.1).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

在这里插入图片描述
可以看到聚类效果有了改进。继续调参增加类别，有两个方向都是可以的，一个是继续减少eps，另一个是增加min_samples。将min_samples从默认的5增加到10，代码如下：

y_pred = DBSCAN(eps = 0.1, min_samples = 10).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

在这里插入图片描述
此时的聚类效果基本是可以令人满意的。

7. 总结
DBSCAN需要调参的两个参数eps和min_samples，这两个值的组合对最终的聚类效果有很大的影响，即DBSCAN聚类算法的结果对参数比较敏感。
基于DBSCAN开发的OPTICS聚类算法，则很好的解决了这个问题，后续会更新OPTICS算法的详解与应用。
此外，DBSCAN的matlab函数也已更新在资源中，有需要的也可以评论或者留言找我要！！
https://download.csdn.net/download/weixin_50514171/85192429?spm=1001.2014.3001.5503


http://chatgpt.dhexx.cn/article/Q7wVKTKy.shtml

相关文章

聚类算法之DBSCAN

聚类算法之DBSCAN

DBSCAN聚类算法 1. DBSCAN算法基本概念 DBSCAN是一种典型的基于密度的聚类算法，基于一组邻域 ( ϵ , M i n P t s ) (\epsilon, MinPts) (ϵ,MinPts)来描述样本集的紧密程度。其中 ϵ \epsilon ϵ描述了某一样本的邻域距离阈值， M i n P t s MinPts Mi…
阅读更多...
char型和int型之间的类型转换

char型和int型之间的类型转换

char转换为int型数据 通过赋值方式将char类型变量转换为int型变量，变量值为char类型变量的ASCII码值 例如：int a ‘0’ 那么打印a的结果为48，如果想要得到正确的数字，需要减去ASCII码值。 int型转换为char型 char类型和int类…
阅读更多...
C++：char转换为int（char to int ）

C++：char转换为int（char to int ）

文章目录 1.通过ascii码&#xff1a;2.直接转换&#xff08;更简单&#xff0c;推荐&#xff09; 1.通过ascii码&#xff1a; char a 0; int ia (int)a; /* note that the int cast is not necessary -- int ia a would suffice */ cout<<ia<<endl;结果如下&a…
阅读更多...
c++ char[]与int之间的类型转换

c++ char[]与int之间的类型转换

char数组转int&#xff0c;int转char数组。 #include <cstdio> #include <iostream> #include <stdlib.h> using namespace std;int main(int argc , char *argv[]){int n 0; char str[110] "1234";//char[]转int n atoi(str);printf("%d…
阅读更多...
c/c++，char型数组转化为int类型

c/c++，char型数组转化为int类型

char型数组转int类型 这几天遇到需要将int等类型转换并保存在char数组中&#xff0c;同时还需要将char数组转换为int等类型进行显示。 1、int等类型转换并保存在char数组中 int为4字节&#xff0c;char为1字节&#xff0c;由长变短&#xff0c;容易发出截断&#xff0c;数据…
阅读更多...
【c++】int与char相互转换

【c++】int与char相互转换

1 通过ASCII码转换 首先先看一下ASCII表 其中数字字符对应的位置为&#xff1a;48 - 57。 需要记住的几个数值&#xff1a; 2 char ->int char 转 int 之前&#xff0c;先将运算式中的每个字符都转换成 ASCII 码值&#xff0c;再进行计算。 char c 0;int i1 c; …
阅读更多...
c++中int与char相互转换

c++中int与char相互转换

一、ASCII 表 了解 int 与 char 相互转换之前&#xff0c;先让我们看一下 ASCII 码表。 其中数字字符对应的位置为&#xff1a;48 - 57。 二、char 转 int char 转 int 之前&#xff0c;先将运算式中的每个字符都转换成 ASCII 码值&#xff0c;再进行计算。 以下代码为例&a…
阅读更多...
java中char类型转换成int类型的方法

java中char类型转换成int类型的方法

java中&#xff0c;需要对输入进行一些判断&#xff0c;比如需要输入的是数字&#xff0c;而用户输入了字符&#xff0c;那么就会报错&#xff0c;因此用char或者String类型接收输入的数据就不会报错&#xff0c;但是问题来了&#xff1a;如何让输入的char或者String类型变为数…
阅读更多...
C++ char转换为int（char to int ）

C++ char转换为int（char to int ）

1.通过ascii码&#xff1a; char a 0; int ia (int)a; /* note that the int cast is not necessary -- int ia a would suffice */ cout<<ia<<endl; 结果如下&#xff1a; 可以看出这种方法得到的其实是char对应的ascii码。 因为ascii码的数字&#xff08;…
阅读更多...
char 与 int之间的转换

char 与 int之间的转换

转载自&#xff1a; 1.首先char与int都分为signed与unsigned类型&#xff0c;默认情况下都是signed类型。 2.从长字节数据类型转换为短字节数据类型&#xff0c;会产生截断&#xff1a; 如从4字节的int类型转换成1个字节的char类型&#xff0c;则取int数据的最低的一个字节&…
阅读更多...
派生类的构造函数和析构函数

派生类的构造函数和析构函数

派生类的构造和析构函数 派生类的构造函数 在定义派生类时&#xff0c;派生类并没有把基类的构造函数和析构函数继承下来。因此&#xff0c;对继承的基类成员初始化的工作要由派生类的构造函数承担&#xff0c;同时基类的析构函数也要被派生类的析构函数来调用 1.派生类构造…
阅读更多...
C++构造函数和析构函数总结

C++构造函数和析构函数总结

构造函数&#xff1a; <1>作用&#xff1a;赋初值,初始化对象的数据成员,由编译器帮我们调用。 <2>特点&#xff1a;①函数名和类名一样。②没有返回值。③支持有参/无参。④可以重载。 <3>调用时机&#xff1a;在类的对象创建时刻,编译器帮我们调用构造函数…
阅读更多...
C++基础：构造函数与析构函数

C++基础：构造函数与析构函数

数据成员多为私有的&#xff0c;要对他们进行初始化&#xff0c;必须用一个公有函数来进行。同时这个函数应该在定义对象时自动执行一次。称为构造函数。 构造函数的用途&#xff1a;1&#xff09;创建对象&#xff1b;2&#xff09;初始化对象中的属性&#xff1b;3&#xff…
阅读更多...
类的构造函数和析构函数、默认构造函数

类的构造函数和析构函数、默认构造函数

前言 程序只能通过成员函数来访问数据成员&#xff0c;因此需要设计合适成员函数&#xff0c;才能成功地将对象初始化。 类构造函数专门用于构造新对象&#xff0c;将值赋给他们的数据成员&#xff0c;进行初始化。 构造函数名称与类名相同&#xff0c;没有返回值&#xff0…
阅读更多...
c++中的构造函数和析构函数

c++中的构造函数和析构函数

类和对象中&#xff0c;包括构造函数和析构函数&#xff0c;比较重要&#xff0c;通过学习总结一下&#xff0c;以便以后可以回顾&#xff01; 目录 构造函数 1.默认构造函数 2.有参构造函数 3.委托构造函数 4.复制(拷贝)构造函数 5.移动构造函数 左值引用与右值引用 析…
阅读更多...
C++类构造函数和析构函数

C++类构造函数和析构函数

11.3 类构造函数和析构函数 构造函数&#xff1a;是为了在定义对象时自动初始化其成员变量的值。 构造函数没有返回值&#xff0c;也没有被声明为void类型&#xff1b;因此&#xff0c;构造函数没有声明类型。 11.3.1 声明和定义一个构造函数 构造函数原型&#xff1a;在这…
阅读更多...
C++ 构造函数和析构函数可以是虚函数嘛？

C++ 构造函数和析构函数可以是虚函数嘛？

简单总结就是&#xff1a;构造函数不可以是虚函数&#xff0c;而析构函数可以且常常是虚函数。 构造函数不能是虚函数 1. 从vptr角度解释 虚函数的调用是通过虚函数表来查找的&#xff0c;而虚函数表由类的实例化对象的vptr指针(vptr可以参考C的虚函数表指针vptr)指向&#x…
阅读更多...
构造函数和析构函数顺序

构造函数和析构函数顺序

父子类 1、构造顺序&#xff1a; 创建一个子类对象&#xff0c;则父类、子类的构造方法都执行&#xff0c;且是 先父类 构造方法&#xff0c;再子类构造方法 派生类的构造顺序&#xff1a;先父类&#xff0c;后子类&#xff0c;因为子类很有可能会用到从父类继承来的成员 2、析…
阅读更多...
【C++】构造函数与析构函数

【C++】构造函数与析构函数

1. 概述 构造函数&#xff1a;用于初始化对象&#xff0c;没有返回值&#xff0c;函数名和类名相同&#xff0c;只有在对象初始化的时候才会被调用。构造函数的分类&#xff1a; 默认构造函数&#xff1a;是编译器自动生成&#xff0c;没有任何参数的构造函数。 有参构造函数&…
阅读更多...
何时调用构造函数和析构函数

何时调用构造函数和析构函数

何时调用构造函数和析构函数 构造函数的作用是保证每个对象的数据成员都有何时的初始值。 析构函数的作用是回收内存和资源&#xff0c;通常用于释放在构造函数或对象生命期内获取的资源。 一般我们都知道构造和析构的次序&#xff1a; 构造从类层次的最根处开始&#xff0c…
阅读更多...
推荐文章

Copyright @ 2022~2023