IT学习站-137zw.com

作者: 却写杂布计
查看: 59|回复: 0

more +资源更新Forums

more +随机图赏Gallery

微专业 - Java高级开发工程师(完整版)微专业 - Java高级开发工程师(完整版)
画画教程 SAI零基础合集(11套)202G  完整版课程分享画画教程 SAI零基础合集(11套)202G 完整版课程分享
喜马拉雅付费专辑 华语辩论冠军的思辩表达课 分享下载喜马拉雅付费专辑 华语辩论冠军的思辩表达课 分享下载
价值1169元 建设项目目标成本编制与投资收益测算 课程价值1169元 建设项目目标成本编制与投资收益测算 课程
医学生必备图谱及教材 蓝色生死恋全集奈特图谱十二本+黄...医学生必备图谱及教材 蓝色生死恋全集奈特图谱十二本+黄...
手把手教你招投标从入门到独立完成标书 完整版课程手把手教你招投标从入门到独立完成标书 完整版课程

聚类——密度聚类DBSCAN

聚类——密度聚类DBSCAN

[复制链接]
却写杂布计 | 显示全部楼层 发表于: 2019-11-14 11:40:03
却写杂布计 发表于: 2019-11-14 11:40:03 | 显示全部楼层 |阅读模式
查看: 59|回复: 0
Clustering 聚类

密度聚类——DBSCAN

  前面我们已经介绍了两种聚类算法:k-means和谱聚类。今天,我们来介绍一种基于密度的聚类算法——DBSCAN,它是最经典的密度聚类算法,是很多算法的基础,拥有很多聚类算法不具有的优势。今天,小编就带你理解密度聚类算法DBSCAN的实质。

DBSCAN


基础概念

    作为最经典的密度聚类算法,DBSCAN使用一组关于“邻域”概念的参数来描述样本分布的紧密程度,将具有足够密度的区域划分成簇,且能在有噪声的条件下发现任意形状的簇。在学习具体算法前,我们先定义几个相关的概念:

  • 邻域:对于任意给定样本x和距离ε,x的ε邻域是指到x距离不超过ε的样本的集合;
  • 核心对象:若样本x的ε邻域内至少包含minPts个样本,则x是一个核心对象;
  • 密度直达:若样本b在a的ε邻域内,且a是核心对象,则称样本b由样本x密度直达;
  • 密度可达:对于样本a,b,如果存在样例p1,p2,...,pn,其中,p1=a,pn=b,且序列中每一个样本都与它的前一个样本密度直达,则称样本a与b密度可达;
  • 密度相连:对于样本a和b,若存在样本k使得a与k密度可达,且k与b密度可达,则a与b密度相连。

光看文字是不是绕晕了?下面我们用一个图来简单表示上面的密度关系:
聚类——密度聚类DBSCAN  技术博客 9pgeGBkF_se53

当minPts=3时,虚线圈表示ε邻域,则从图中我们可以观察到:

  • x1是核心对象;
  • x2由x1密度直达;
  • x3由x1密度可达;
  • x3与x4密度相连。
为什么要定义这些看上去差不多又容易把人绕晕的概念呢?其实ε邻域使用(ε,minpts)这两个关键的参数来描述邻域样本分布的紧密程度,规定了在一定邻域阈值内样本的个数(这不就是密度嘛)。那有了这些概念,如何根据密度进行聚类呢?
DBSCAN聚类思想

  DBSCAN聚类的原理很简单:由密度可达关系导出最大密度相连的样本集合(聚类)。这样的一个集合中有一个或多个核心对象,如果只有一个核心对象,则簇中其他非核心对象都在这个核心对象的ε邻域内;如果是多个核心对象,那么任意一个核心对象的ε邻域内一定包含另一个核心对象(否则无法密度可达)。这些核心对象以及包含在它ε邻域内的所有样本构成一个类。
  那么,如何找到这样一个样本集合呢?一开始任意选择一个没有被标记的核心对象,找到它的所有密度可达对象,即一个簇,这些核心对象以及它们ε邻域内的点被标记为同一个类;然后再找一个未标记过的核心对象,重复上边的步骤,直到所有核心对象都被标记为止。
  算法的思想很简单,但是我们必须考虑一些细节问题才能产出一个好的聚类结果:

  • 首先对于一些不存在任何核心对象邻域内的点,再DBSCAN中我们将其标记为离群点(异常);
  • 第二个是距离度量,如欧式距离,在我们要确定ε邻域内的点时,必须要计算样本点到所有点之间的距离,对于样本数较少的场景,还可以应付,如果数据量特别大,一般采用KD树或者球树来快速搜索最近邻,不熟悉这两种方法的同学可以找相关文献看看,这里不再赘述;
  • 第三个问题是如果存在样本到两个核心对象的距离都小于ε,但这两个核心对象不属于同一个类,那么该样本属于哪一个类呢?一般DBSCAN采用先来后到的方法,样本将被标记成先聚成的类。
DBSCAN算法流程

聚类——密度聚类DBSCAN  技术博客 eApHwHEJ_SC4N

DBSCAN算法小结

      之前我们学过了kmeans算法,用户需要给出聚类的个数k,然而我们往往对k的大小无法确定。DBSCAN算法最大的优势就是无需给定聚类个数k,且能够发现任意形状的聚类,且在聚类过程中能自动识别出离群点。那么,我们在什么时候使用DBSCAN算法来聚类呢?一般来说,如果数据集比较稠密且形状非凸,用密度聚类的方法效果要好一些。
DBSCAN算法优点:

  • 不需要事先指定聚类个数,且可以发现任意形状的聚类;
  • 对异常点不敏感,在聚类过程中能自动识别出异常点;
  • 聚类结果不依赖于节点的遍历顺序;
DBSCAN缺点:

  • 对于密度不均匀,聚类间分布差异大的数据集,聚类质量变差;
  • 样本集较大时,算法收敛时间较长;
  • 调参较复杂,要同时考虑两个参数;

小结:

基于密度的聚类算法是广为使用的算法,特别是对于任意形状聚类以及存在异常点的场景。上面我们也提到了DBSCAN算法的缺点,但是其实很多研究者已经在DBSCAN的基础上做出了改进,实现了多密度的聚类,针对海量数据的场景,提出了micro-cluster的结构来表征距离近的一小部分点,减少存储压力和计算压力...还有很多先进的密度聚类算法及其应用,相信看完这篇文章再去读相关的论文会比较轻松。

聚类——密度聚类DBSCAN  技术博客

扫码关注

获取有趣的算法知识

聚类——密度聚类DBSCAN  技术博客 D96dShcj_IZqC

聚类——密度聚类DBSCAN  技术博客



来源:http://www.137zw.com
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
137zw.com IT学习站致力于免费提供精品的java技术教程和python技术教程,CCNA书籍/资料/CCNP书籍/资料教程/CCIE书籍/资料/H3C学习/认证/一级建造师考试/微软学习/认证/包括基础教程和高级实战教程,同时也提供分享网站源码下载和互联网相关一系列的技术教程,我们想做的就是让知识分享更有价值!(IT学习站官方唯一域名地址:www.137zw.com 请谨防假冒网站!)本站所有资源全部收集于互联网或网友自行分享,分享目的仅供大家学习与参考,如无意中侵犯您的合法权益,请联系本站管理员进行删除处理!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

浙ICP备19022368号-1|Archiver|手机版|IT学习站-137zw.com

GMT+8, 2020-7-4 09:57 , Processed in 0.265288 second(s), 33 queries .

快速回复 返回顶部 返回列表