DBSCAN聚类算法

这篇具有很好参考价值的文章主要介绍了DBSCAN聚类算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法简介

DBSCAN(density-based spatial clustering of applications with noise),即“具有噪声的基于密度的空间聚类应用”。它的原理是识别特征空间的“拥挤”区域中的点,在这些区域中许多点靠在一起,这些区域称为特征空间中的密集区域。密集区域最终将有相对较空的区域分隔开。

在密集区域的点称为核心点,由DBSCAN的两个重要参数半径eps最小采样点个数min_sample确定,其定义如下:如果在距一个给定数据点eps距离内至少有min_sample个数据点,那么这个数据点就是核心点。DBSCAN最终会将彼此距离小于eps的核心点分到同一簇中。

算法过程描述

首先任取一个点,找到这个点的距离小于等于eps的所有点,如果距起始点的距离在eps之内的数据点个数小于min_sample,那么这个点被标记为噪音点,也就是说它不属于任何簇。如果距离在eps之内的数据点个数大于min_sample,则这个点被标记为核心点,并分配一个新的簇标签。然后访问该点的所有eps以内的邻居,如果它们还没有被分配簇,那么就将刚才的簇标签分配给它们,如果它们也是核心点,那么继续依次访问其邻居,以此类推,否则即为边界点,不再访问其邻居。簇逐渐增大,直到簇的eps距离内没有更多的核心点为止。然后选取另一个尚未被访问的点,重复相同的过程。

最后,一共有三种类型的点:核心点、边界点、噪音点。如果DBSCAN算法在特定数据集运行多次,那么核心点的聚类始终相同,同样的点也始终被标记为噪音点。但边界点可能与不止一个簇的核心点相邻,这与数据点的访问顺序有关。一般情况下,边界点较少,因此这种歧义并不是很重要。

从上述描述中可以看到,DBSCAN算法不需要设置簇的个数,只需要确定两个参数eps、min_sample,实际上它们可以隐式地控制找到簇的个数。eps决定了点与点之间“接近”的含义,将eps设置过小,意味着没有核心点出现,可能导致所有点被标记为噪音点;eps设置过大,可能导致所有点形成单个簇。min_sample主要用于判断稀疏区域内点被标记为异常值还是形成自己的簇,决定了簇的最小尺寸。因此,两个参数的选取还是至关重要的。

:采用缩放技术使数据特征具有相似的范围,有时会更便于找到eps较好的取值。

DBSCAN算法可视化展示

自适应聚类算法,机器学习,聚类,算法,机器学习

DBSCAN聚类算法在二维平面中对数据点进行聚类的简化过程如图所示,选取min_sample=2,此时图中蓝色为噪音点,不属于任何簇;红色为核心点,黄色为边界点,它们均划分在同一簇中。

国外有个网站,可以把DBSCAN的过程以动图展示出来,可以选择几种不同的数据集,还可以自行设置参数,很有趣.

DBSCAN可视化网站

算法实现

算法流程

自适应聚类算法,机器学习,聚类,算法,机器学习

算法实现

DBSCAN可在python中的sklearn库调用实现,以下给出两个简单实例对算法的聚类效果进行展示.

实例一:半圆形数据分簇

import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler

X, y = make_moons(n_samples=200, noise=0.05, random_state=0)

#将数据缩放成平均值为0、方差为1
scaler = StandardScaler()
scaler.fit(X)
X_scaled = scaler.transform(X)

dbscan = DBSCAN()
clusters = dbscan.fit_predict(X_scaled)
#绘制簇分配
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=clusters, s=60)
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")
plt.show()

自适应聚类算法,机器学习,聚类,算法,机器学习

上图展示了在two_moons数据集上运行DBSCAN的结果,利用默认设置(eps=0.5),算法找到了两个半圆形并将其分开.由于算法得到了2个簇,默认参数的设置效果似乎很好,若eps=0.2,将会得到8个簇,显然太多了;若eps=0.7,则会导致只有1个簇.

实例二:品牌啤酒聚类分析

import pandas as pd
from matplotlib import colors
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt

#导入数据
beer = pd.read_csv('beer.txt', sep=' ')
print(beer)#查看数据集

X = beer[['calories', 'sodium', 'alcohol', 'cost']]

#设置半径为10,最小样本量2
db = DBSCAN(eps=10, min_samples=2).fit(X)

labels = db.labels_
beer['cluster_db'] = labels #在数据集最后一列加上DBSCAN聚类后的结果
beer.sort_values('cluster_db')
print(beer)

#查看根据DBSCAN聚类后的分组统计结果(均值)
print(beer.groupby('cluster_db').mean())

#画出在不同两个指标下样本的分布情况
print(pd.plotting.scatter_matrix(X, figsize=(10, 10), s=100))
plt.show()

查看数据集:

自适应聚类算法,机器学习,聚类,算法,机器学习

聚类结果:

自适应聚类算法,机器学习,聚类,算法,机器学习

下表给出了聚类后分组的均值结果.

自适应聚类算法,机器学习,聚类,算法,机器学习

图中展示了在不同两个指标下样本的分布情况.

自适应聚类算法,机器学习,聚类,算法,机器学习

算法优缺点

优点

  1. 不需要先验地指定簇的个数;
  2. 可以处理任意形状大小的簇,且结果相对而言优于K均值聚类;
  3. 基于密度定义,对噪音不敏感,可检测出数据异常点.

缺点

  1. 高维数据有些困难;
  2. sklearn中效率较低
  3. 对于密度不均匀、距离相差较大的数据集,聚类结果较差;
  4. 调参较为复杂,需要多次尝试,不同的参数组合对最终结果影响较大.

算法改进:自适应的DBSCAN算法

由于DBSCAN算法对eps和min_sample两个参数十分敏感,参数的确定是既重要又困难的事情,有学者进行了自适应确定DBSCAN算法参数的研究,即通过数据集自动确定两个参数.相应论文可以在知网查阅.

李文杰, 闫世强, 蒋莹,等. 自适应确定DBSCAN算法参数的算法研究[J]. 计算机工程与应用, 2019, 55(05):1-7.

补充内容:MATLAB代码及测试实例

% DBSCAN聚类算法

% 算法流程:
% 1.首先选择一个待处理数据;
% 2.寻找和待处理数据距离在设定半径之内的数据;
% 3.将找到的半径内的数据放到一个队列中;
% 4.从队列头数据开始作为当前待处理数据并执行步骤2;
% 5.直至遍历队列中所有数据,将它们记为一类;
% 6.从未处理数据中选择一个作为待处理数据重复步骤2-5;
% 7.直至遍历完所有数据,算法结束.

theta=0:0.01:2*pi;
p1=[3*cos(theta) + rand(1,length(theta))/2;3*sin(theta)+ rand(1,length(theta))/2];      %生成测试数据
p2=[2*cos(theta) + rand(1,length(theta))/2;2*sin(theta)+ rand(1,length(theta))/2];
p3=[cos(theta) + rand(1,length(theta))/2;sin(theta)+ rand(1,length(theta))/2];
p=[p1 p2 p3]';

randIndex = randperm(length(p))';       %打乱数据顺序
p=p(randIndex,:);
figure;
plot(p(:,1),p(:,2),'.')


flag = zeros(length(p),1);      %聚类标记
clsnum = 0;                     %类的个数
disnear = 0.3;                 %聚类半径

for i=1:length(p)
    nxtp=p(i,:); % 初始聚类半径内的邻域点队列
    if flag(i)==0
        clsnum=clsnum+1;
        pcstart=1; % 设置队列起始指针
        perflag=flag; % 聚类标记更新
        
       while pcstart<=length(nxtp) % 判断队列是否完成遍历
           curp=nxtp(pcstart,:); % 当前要处理的点
           pcstart=pcstart+1;
           diffp=p-repmat(curp,length(p),1);
           distance=sqrt(diffp(:,1).*diffp(:,1)+diffp(:,2).*diffp(:,2)); % 判断当前点与所有数据点间的距离
           
           ind=distance<disnear; % 得到距离小于阈值的索引
           flag(ind)=clsnum; % 设置当前聚类标记
           
           diff_flag=perflag-flag;
           diff_ind=diff_flag<0; % 判断本次循环相比上次循环增加的点,新增加的点要再放入队列中
           
           
           tmp=zeros(length(p),1);
           tmp(diff_ind)=clsnum;
           flag=flag+tmp;
           perflag=flag;
           nxtp=[nxtp;p(diff_ind,:)];
       end
    end
end

figure;
plot(p(flag==1,1),p(flag==1,2),'r.');
hold on
plot(p(flag==2,1),p(flag==2,2),'g.');
hold on
plot(p(flag==3,1),p(flag==3,2),'b.');

自适应聚类算法,机器学习,聚类,算法,机器学习
自适应聚类算法,机器学习,聚类,算法,机器学习
参考博客Dsp Tian文章来源地址https://www.toymoban.com/news/detail-737635.html

到了这里,关于DBSCAN聚类算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • DBSCAN聚类算法

    DBSCAN (density-based spatial clustering of applications with noise),即“具有噪声的基于密度的空间聚类应用”。它的原理是识别特征空间的“拥挤”区域中的点,在这些区域中许多点靠在一起,这些区域称为特征空间中的 密集 区域。密集区域最终将有相对较空的区域分隔开。 在密集区

    2024年02月06日
    浏览(29)
  • DBSCAN聚类算法——MATLAB实现

        声明:本文修改自《 数学建模清风 》老师的代码    DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪

    2024年02月11日
    浏览(32)
  • 机器学习|DBSCAN 算法的数学原理及代码解析

    聚类是机器学习领域中一项重要的任务,它可以将数据集中相似的样本归为一类。 DBSCAN(Density-Based Spatial Clustering of Applications with Noise) 是一种是一种经典的密度聚类算法,它能够有效地发现任意形状的聚类簇,并且可以识别出噪声点。在本文中,我们将深入探讨 DBSCAN 算法

    2024年02月11日
    浏览(35)
  • 密度聚类算法(DBSCAN)实验案例

    DBSCAN是一种强大的基于密度的聚类算法,从直观效果上看,DBSCAN算法可以找到样本点的全部密集区域,并把这些密集区域当做一个一个的聚类簇。DBSCAN的一个巨大优势是可以对任意形状的数据集进行聚类。 本任务的主要内容: 1、 环形数据集聚类 2、 新月形数据集聚类 3、

    2024年02月08日
    浏览(35)
  • 基于密度的聚类算法(1)——DBSCAN详解

    基于密度的聚类算法(1)——DBSCAN详解 基于密度的聚类算法(2)——OPTICS详解 基于密度的聚类算法(3)——DPC详解 1. DBSCAN简介 DBSCAN(Density-Based Spatial Clustering of Applications with Noise, 具有噪声的基于密度的聚类方法 )是一种典型的基于密度的空间聚类算法。和K-Means,BIR

    2024年01月24日
    浏览(33)
  • 毫米波雷达点云 DBSCAN聚类算法

    聚类的目的是将一组数据点划分为具有相似特征或属性的组或簇。通过聚类分析,我们可以识别出数据中的内在模式、结构和关联关系,从而获得对数据的更深入理解。 具体来说,聚类的目的可以分为以下三部分: 发现数据的内在结构: 聚类可以将数据分成簇,这些簇可能

    2024年02月06日
    浏览(34)
  • 深度解读DBSCAN聚类算法:技术与实战全解析

    探索DBSCAN算法的内涵与应用,本文详述其理论基础、关键参数、实战案例及最佳实践,揭示如何有效利用DBSCAN处理复杂数据集,突破传统聚类限制。 关注TechLead,分享AI全维度知识。作者拥有10+年互联网服务架构、AI产品研发经验、团队管理经验,同济本复旦硕,复旦机器人智

    2024年02月05日
    浏览(36)
  • 【详解算法流程+程序】DBSCAN基于密度的聚类算法+源码-用K-means和DBSCAN算法对银行数据进行聚类并完成用户画像数据分析课设源码资料包

    DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。 与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇, 并可在噪声的空间数据库中发现任意形状的聚类。         选

    2024年04月11日
    浏览(34)
  • C# | DBSCAN聚类算法实现 —— 对直角坐标系中临近点的点进行聚类

    聚类算法是一种常见的数据分析技术,用于将相似的数据对象归类到同一组或簇中。其中,DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法,能够有效地识别出不同形状和大小的簇,同时还能标识出噪声数据。本篇博客将介绍聚类算法的概念

    2024年02月09日
    浏览(26)
  • 【机器学习】机器学习上机作业聚类算法

    自编代码实现C均值聚类和FCM聚类,在“IRIS数据集(鸢尾花数据集)”上进行实验,验证所编代码是否正确,并计算准确率。 Iris鸢尾花数|据集:包含花萼长度、花萼宽度、花瓣长度、花瓣宽度四个属性,用于预测鸢尾花种类,标签0、1、2分别表示山鸢尾、变色鸢尾、维吉尼亚鸢

    2024年01月22日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包