专栏首页Python与算法之美20分钟学会DBSCAN聚类算法

20分钟学会DBSCAN聚类算法

DBSCAN是一种非常著名的基于密度的聚类算法。其英文全称是 Density-Based Spatial Clustering of Applications with Noise,意即:一种基于密度,对噪声鲁棒的空间聚类算法。直观效果上看,DBSCAN算法可以找到样本点的全部密集区域,并把这些密集区域当做一个一个的聚类簇。

DBSCAN算法具有以下特点:

  • 基于密度,对远离密度核心的噪声点鲁棒
  • 无需知道聚类簇的数量
  • 可以发现任意形状的聚类簇

DBSCAN通常适合于对较低维度数据进行聚类分析。

公众号后台回复关键字:"源码",获取本文全部代码和对应插图PPT。

一,基本概念

DBSCAN的基本概念可以用1,2,3,4来总结。

1个核心思想:基于密度。

直观效果上看,DBSCAN算法可以找到样本点的全部密集区域,并把这些密集区域当做一个一个的聚类簇。

2个算法参数:邻域半径R和最少点数目minpoints。

这两个算法参数实际可以刻画什么叫密集——当邻域半径R内的点的个数大于最少点数目minpoints时,就是密集。

3种点的类别:核心点,边界点和噪声点。

邻域半径R内样本点的数量大于等于minpoints的点叫做核心点。不属于核心点但在某个核心点的邻域内的点叫做边界点。既不是核心点也不是边界点的是噪声点。

4种点的关系:密度直达,密度可达,密度相连,非密度相连。

如果P为核心点,Q在P的R邻域内,那么称P到Q密度直达。任何核心点到其自身密度直达,密度直达不具有对称性,如果P到Q密度直达,那么Q到P不一定密度直达。

如果存在核心点P2,P3,……,Pn,且P1到P2密度直达,P2到P3密度直达,……,P(n-1)到Pn密度直达,Pn到Q密度直达,则P1到Q密度可达。密度可达也不具有对称性。

如果存在核心点S,使得S到P和Q都密度可达,则P和Q密度相连。密度相连具有对称性,如果P和Q密度相连,那么Q和P也一定密度相连。密度相连的两个点属于同一个聚类簇。

如果两个点不属于密度相连关系,则两个点非密度相连。非密度相连的两个点属于不同的聚类簇,或者其中存在噪声点。

二,DBSCAN算法步骤

DBSCAN的算法步骤分成两步。

1,寻找核心点形成临时聚类簇。

扫描全部样本点,如果某个样本点R半径范围内点数目>=MinPoints,则将其纳入核心点列表,并将其密度直达的点形成对应的临时聚类簇。

2,合并临时聚类簇得到聚类簇。

对于每一个临时聚类簇,检查其中的点是否为核心点,如果是,将该点对应的临时聚类簇和当前临时聚类簇合并,得到新的临时聚类簇。

重复此操作,直到当前临时聚类簇中的每一个点要么不在核心点列表,要么其密度直达的点都已经在该临时聚类簇,该临时聚类簇升级成为聚类簇。

继续对剩余的临时聚类簇进行相同的合并操作,直到全部临时聚类簇被处理。

三,DBSCAN使用范例

1,生成样本点

import numpy as np
import pandas as pd
from sklearn import datasets
%matplotlib inline

X,_ = datasets.make_moons(500,noise = 0.1,random_state=1)
df = pd.DataFrame(X,columns = ['feature1','feature2'])

df.plot.scatter('feature1','feature2', s = 100,alpha = 0.6, title = 'dataset by make_moon')

2,调用dbscan接口完成聚类

from sklearn.cluster import dbscan

# eps为邻域半径,min_samples为最少点数目
core_samples,cluster_ids = dbscan(X, eps = 0.2, min_samples=20) 
# cluster_ids中-1表示对应的点为噪声点

df = pd.DataFrame(np.c_[X,cluster_ids],columns = ['feature1','feature2','cluster_id'])
df['cluster_id'] = df['cluster_id'].astype('i2')

df.plot.scatter('feature1','feature2', s = 100,
    c = list(df['cluster_id']),cmap = 'rainbow',colorbar = False,
    alpha = 0.6,title = 'DBSCAN cluster result')

本文分享自微信公众号 - Python与算法之美(Python_Ai_Road),作者:梁云1991

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-27

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 6, 元组tuple和集合set

    11,a = 2; b = 3; 如何利用 tuple为多个变量赋值的特性用一条语句互换 a 和 b 的值?(回复关键字 python11 查看参考答案)

    lyhue1991
  • 30分钟学会PCA主成分分析

    PCA主成分分析算法(Principal Components Analysis)是一种最常用的降维算法。能够以较低的信息损失(以样本间分布方差衡量)减少特征数...

    lyhue1991
  • 张量的数学运算

    Pytorch提供的方法比numpy更全面,运算速度更快,如果需要的话,还可以使用GPU进行加速。

    lyhue1991
  • 【无监督学习】DBSCAN聚类算法原理介绍,以及代码实现

    主要包括:K-means、DBSCAN、Density Peaks聚类(局部密度聚类)、层次聚类、谱聚类。

    IT派
  • 深入浅出——基于密度的聚类方法

    作者 祝烨 编辑 (没脸) “The observation of and the search forsimilarities an...

    机器学习算法工程师
  • Laravel 5.0 发布, 海量新特性!!

    译注: 期待 Laravel 5.0 已经很久很久了, 之前跳票说要到今年一月份发布. 从一月份就一直在刷新官网和博客, 始终没有更新的消息, 前几天终于看到官...

    小李刀刀
  • 接口自动化测试:快速敏捷迭代的业务类产品适合做接口自动化测试

    当前互联网产品迭代速度越来越快,现在很多业务类产品一周发两个版本,甚至更多。每次发版之前都需要对所有功能进行回归测试,在人力资源有限的情况下,做自动化测试很有必...

    小老鼠
  • Love beautiful code? We do too.

    Laravel是一个有着美好前景的年轻框架,它的社区充满着活力,同时提供了完整而清晰的文档,而且为快速、安全地开发现代应用提供了必要的功能。

    貟王軍
  • Laravel 7 正式发布,一起来看看有哪些重要更新吧

    Laravel 7 版本于 2020 年 3 月 3 日正式发布,本次版本更新包含了很多新特性:

    学院君
  • [PHP] Laravel框架介绍、安装及配置

    Laravel是一套简洁、优雅的PHP Web开发框架(PHP Web Framework)。它可以让你从面条一样杂乱的代码中解脱出来;它可以帮你构建一个完美的...

    泰坦HW

扫码关注云+社区

领取腾讯云代金券