聚类(一):DBSCAN算法实现(r语言)

  • Some points
  • 算法流程
  • R语言实现
  • 选择最优的Eps值
  • 自定义距离公式
  • DBSCAN优缺点

DBSCAN(Density-BasedSpatial Clustering of Applications with Noise),一种基于密度的聚类方法,即找到被低密度区域分离的稠密区域,要求聚类空间中的一定区域内所包含对象(点或其他空间对象)的数目不小于某一给定阈值。

  • Some points

一、两个参数。

1,距离参数(Eps)

2,邻域内点最少个数(MinPts)

二、根据基于中心的密度进行点分类。

密度的基于中心的方法使得点分为三类:

1, 核心点。稠密区域内部的点。该点以Eps为半径的区域内点的个数不少于MinPts(包括自身)。

2, 边界点。稠密区边缘上的点,不是核心点,但在某个或多个核心点邻域内。

3, 噪声点。稀疏区域中的点,既非核心点也非边界点。

4, 密度可达。如果点p在核心点q的Eps邻域内,则称p是从q出发可以直接密度可达。如果存在点链p1,p2, …, pn,p1=q,pn=p,pi+1是从pi直接密度可达,则称点p是从q关于r和M密度可达的,密度可达是单向的。

  • 算法流程

从某点出发,将密度可达的点聚为一类,不断进行区域扩张,直至所有点都被访问。

  • R语言实现

在R中实现DBSCAN聚类,可以使用fpc包中的dbscan()函数。在下面的例子中,我们使用factoextra包中的数据集multishapes进行演示。

如下可查看聚类后的结果:

具体每个样本点的分类结果,可用db$cluster查看,其中0表示噪声点,如下随机显示50个点的分类结果:

  • 选择最优的Eps值

方法为计算每个点到其最近邻的k个点的平均距离。k的取值根据MinPts由用户指定。R语言中,使用dbscan包中的kNNdistplot()函数进行计算。

由图可知,拐点处基本在0.15左右,因此可以认为最优Eps值在0.15左右。

  • 自定义距离公式

dbscan()函数中计算距离公式为欧式距离,在一些特定的场合无法使用,比如要计算地图上两点的距离,就要应用特定的计算地图上两点的距离公式。

R里面的很多函数都是开源的,因此,直接运行fpc::dbscan可以看到此函数的原程序。我们用geosphere包中的distm()函数对原程序中的距离计算公式进行修改,实现地图上两点距离的计算。

将原程序中的distcomb函数改为如下形式:

将修改过的dbscan函数重新命名为disdbscan,重新将数据进行聚类:

  • DBSCAN优缺点

优点

(1)聚类速度快,且能够有效处理噪声点。

(2)能发现任意形状的空间聚类。

(3)聚类结果几乎不依赖于点遍历顺序。

(4)不需要输入要划分的聚类个数。

缺点

(1)当数据量增大时,要求较大的内存支持I/O消耗也很大;

(2)当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差。


机器学习养成记

原文发布于微信公众号 - 机器学习养成记(chenchenwings)

原文发表时间:2017-07-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

TensorFlow 自动句子语义编码,谷歌开源机器学习模型 Skip-Thoughts

【新智元导读】谷歌今天开源一个句子编码器模型 Skip-Thoughts,在 TensorFlow 上实现,学习将输入的句子编码成固定维度的向量表示,可以用于语...

42230
来自专栏人工智能LeadAI

理工男的文科梦 —— LSTM深度学习写春联

笔者作为一名根正苗红的理工男,内心却常常有很多文艺青年才会有的想法,例如写首诗、做首词,甚至包括春节写副对联,空有一番愿望却胸无点墨。随着对机器学习和深度学习的...

51440
来自专栏鹅厂优文

AI从入门到放弃:CNN的导火索,用MLP做图像分类识别?

图片标题会显示Accuracy(准确度),准确度的计算公式是: 识别正确图片数/图片总数。

56690
来自专栏专知

【干货】Batch Normalization: 如何更快地训练深度神经网络

【导读】本文是谷歌机器学习工程师 Chris Rawles 撰写的一篇技术博文,探讨了如何在 TensorFlow 和 tf.keras 上利用 Batch N...

4.8K80

如何在Python中规范化和标准化时间序列数据

如果您的时间序列数据具有连续的尺度或分布,则在某些机器学习算法将获得更好的性能。

59190
来自专栏老秦求学

[Deep-Learning-with-Python] Keras高级概念

目前为止,介绍的神经网络模型都是通过Sequential模型来实现的。Sequential模型假设神经网络模型只有一个输入一个输出,而且模型的网络层是线性堆叠在...

17110
来自专栏机器之心

教程 | 如何判断LSTM模型中的过拟合与欠拟合

选自MachineLearningMastery 作者:Jason Brownlee 机器之心编译 参与:Nurhachu Null、路雪 判断长短期记忆模型在...

1.5K100
来自专栏深度学习自然语言处理

基于汉语短文本对话的立场检测系统理论与实践

汉语短文本对话立场检测的主要任务就是通过以对话的一个人的立场为主要立场,而判断另一个人针对该人的回话的立场。立场包括支持,反对,中立三种立场。基于对话的立场检测...

17310
来自专栏null的专栏

简单易学的机器学习算法——基于密度的聚类算法DBSCAN

一、基于密度的聚类算法的概述     最近在Science上的一篇基于密度的聚类算法《Clustering by fast search and find of...

39540
来自专栏机器学习原理

机器学习篇(2)——最小二乘法概念最小二乘法

前言:主要介绍了从最小二乘法到 概念 顾名思义,线性模型就是可以用线性组合进行预测的函数,如图: ? image.png 公式如下: ? i...

64650

扫码关注云+社区

领取腾讯云代金券