Matlab实现DBSCAN算法(每行代码标注详细注解)

本文主要是为了完成日常功课,进一步加深对算法的理解。也希望对来访的读者有所帮助。

内容

一、什么是DBSCAN算法

二、DBSCAN算法的意义

三、DBSCAN算法代码解析

1.关键概念

2.大致思路

3.对照每行代码的详细注解

(1)DBSCAN.m文件注解如下:

(2)mydata.mat文件注解如下:

(3)PlotClusterinResult.m文件注解如下:

(4)main.m文件注解如下:

4.总结


一、什么是DBSCAN算法

DBSCAN基于高密度连通区域的、基于密度的聚类算法,能够将具有足够高密度的区域划分为簇,并在具有噪声的数据中发现任意形状的簇。简单来说,DBSCAN目的就是找到密度相连对象的最大集合。其原理的基本要点有:DBSCAN算法需要选择一种距离度量,对于待聚类的数据集中,任意两个点之间的距离,反映了点之间的密度,说明了点与点是否能够聚到同一类中。由于DBSCAN算法对高维数据定义密度很困难,所以对于二维空间中的点,可以使用欧几里德距离来进行度量。

二、DBSCAN算法的意义

首先,有必要提一下聚类算法。聚类算法可以利用数据内部的聚类结构和模式对数据进行分类,不需要训练样本来获得先验知识,降低了计算复杂度。引入深度学习,学习数据内部结构和模式的特征,得到数据的初步聚类,然后不断优化初步聚类,得到最终的分类效果。实验结果表明,该算法很好地解决了综合信息与维数灾难之间的矛盾,具有较好的实用性和主观一致性。

而DBSCAN聚类算法广泛应用于人脸识别以及交通等领域。

三、DBSCAN算法代码解析

1.关键概念

Eps 参数:定义密度时的邻域半径;

MmPts 参数:定义核心点时的阈值;

E-邻域:给定对象半径内的区域称为对象的E-邻域;

核心对象:如果给定对象Ε领域内的样本点数大于等于MinPts,则称该对象为核心对象;

直接密度可达:对于样本集合D,如果样本点q在p的Ε领域内,并且p为核心对象,那么对象q从对象p直接密度可达;

密度可达:对于样本集合D,给定一串样本点p1,p2….pn,p= p1,q= pn,假如对象pi从pi-1直接密度可达,那么对象q从对象p密度可达;

密度相连:存在样本集合D中的一点o,如果对象o到对象p和对象q都是密度可达的,那么p和q密度相联。

2.大致思路

DBSCAN 算法对簇的定义很简单,由密度可达关系导出的最大密度相连的样本集合,即为最终聚类的一个簇。DBSCAN 算法的簇里面可以有一个或者多个核心点。如果只有一个核心点,则簇里其他的非核心点样本都在这个核心点的 Eps 邻域里。如果有多个核心点,则簇里的任意一个核心点的 Eps 邻域中一定有一个其他的核心点,否则这两个核心点无法密度可达。这些核心点的 Eps 邻域里所有的样本的集合组成一个 DBSCAN 聚类簇。
DBSCAN算法的描述如下:

  • 输入:数据集,邻域半径 Eps,邻域中数据对象数目阈值 MinPts;
  • 输出:密度连接的集群。

具体处理流程如下:
1)从数据集中任意选取一个数据对象点 p;
2)如果对于参数 Eps 和 MinPts,所选取的数据对象点 p 为核心点,则找出所有从 p 密度可达的数据对象点,形成一个簇;
3)如果选取的数据对象点 p 是边缘点,选取另一个数据对象点;
4)重复(2)、(3)步,直到所有点被处理。

3.对照每行代码的详细注解

(1)DBSCAN.m文件注解如下:

%
% Copyright (c) 2015, Yarpiz (www.yarpiz.com)
% All rights reserved. Please read the "license.txt" for license terms.
%
% Project Code: YPML110
% Project Title: Implementation of DBSCAN Clustering in MATLAB
% Publisher: Yarpiz (www.yarpiz.com)
% 
% Developer: S. Mostapha Kalami Heris (Member of Yarpiz Team)
% 
% Contact Info: sm.kalami@gmail.com, info@yarpiz.com
%
//上面的部分应该是运行前的加载文件,不做过多解读

function [IDX, isnoise]=DBSCAN(X,epsilon,MinPts)    //DBSCAN聚类函数

    C=0;                       //统计簇类个数,初始化为0
    
    n=size(X,1);               //把矩阵X的行数数赋值给n,即一共有n个点
    IDX=zeros(n,1);            //定义一个n行1列的矩阵
    
    D=pdist2(X,X);             //计算(X,X)的行的距离
    
    visited=false(n,1);        //创建一维的标记数组,全部初始化为false,代表还未被访问
    isnoise=false(n,1);        //创建一维的异常点数组,全部初始化为false,代表该点不是异常点
    
    for i=1:n                  //遍历1~n个所有的点
        if ~visited(i)         //未被访问,则执行下列代码
            visited(i)=true;   //标记为true,已经访问
            
            Neighbors=RegionQuery(i);     //查询周围点中距离小于等于epsilon的个数
            if numel(Neighbors)<MinPts    //如果小于MinPts
                % X(i,:) is NOISE        
                isnoise(i)=true;          //该点是异常点
            else              //如果大于MinPts,且距离大于epsilon
                C=C+1;        //该点又是新的簇类中心点,簇类个数+1
                ExpandCluster(i,Neighbors,C);    //如果是新的簇类中心,执行下面的函数
            end
            
        end
    
    end                    //循环完n个点,跳出循环
    
    function ExpandCluster(i,Neighbors,C)    //判断该点周围的点是否直接密度可达
        IDX(i)=C;                            //将第i个C簇类记录到IDX(i)中
        
        k = 1;                             
        while true                           //一直循环
            j = Neighbors(k);                //找到距离小于epsilon的第一个直接密度可达点
            
            if ~visited(j)                   //如果没有被访问
                visited(j)=true;             //标记为已访问
                Neighbors2=RegionQuery(j);   //查询周围点中距离小于epsilon的个数
                if numel(Neighbors2)>=MinPts //如果周围点的个数大于等于Minpts,代表该点直接密度可达
                    Neighbors=[Neighbors Neighbors2];   %#ok  //将该点包含着同一个簇类当中
                end
            end                              //退出循环
            if IDX(j)==0                     //如果还没形成任何簇类
                IDX(j)=C;                    //将第j个簇类记录到IDX(j)中
            end                              //退出循坏
            
            k = k + 1;                       //k+1,继续遍历下一个直接密度可达的点
            if k > numel(Neighbors)          //如果已经遍历完所有直接密度可达的点,则退出循环
                break;
            end
        end
    end                                      //退出循环
    
    function Neighbors=RegionQuery(i)        //该函数用来查询周围点中距离小于等于epsilon的个数
        Neighbors=find(D(i,:)<=epsilon);
    end

end

(2)mydata.mat文件注解如下:

原始数据显然是二维数据,即平面上的点。源代码中的数据如下所示:

Matlab实现DBSCAN算法(每行代码标注详细注解)

(3)PlotClusterinResult.m文件注解如下:

%
% Copyright (c) 2015, Yarpiz (www.yarpiz.com)
% All rights reserved. Please read the "license.txt" for license terms.
%
% Project Code: YPML110
% Project Title: Implementation of DBSCAN Clustering in MATLAB
% Publisher: Yarpiz (www.yarpiz.com)
% 
% Developer: S. Mostapha Kalami Heris (Member of Yarpiz Team)
% 
% Contact Info: sm.kalami@gmail.com, info@yarpiz.com
%
//上面的程序依旧应该是加载文件,不做过多的解析

function PlotClusterinResult(X, IDX)                //绘图,标绘聚类结果

    k=max(IDX);                                     //求矩阵IDX每一列的最大元素及其对应的索引

    Colors=hsv(k);                                  //颜色设置

    Legends = {};
    for i=0:k                                       //循环每一个簇类
        Xi=X(IDX==i,:);                    
        if i~=0                                     
            Style = 'x';                            //标记符号为x
            MarkerSize = 8;                         //标记尺寸为8
            Color = Colors(i,:);                    //所有点改变颜色改变
            Legends{end+1} = ['Cluster #' num2str(i)]; 
        else
            Style = 'o';                            //标记符号为o
            MarkerSize = 6;                         //标记尺寸为6
            Color = [0 0 0];                        //所有点改变颜色改变
            if ~isempty(Xi)
                Legends{end+1} = 'Noise';           //如果为空,则为异常点
            end
        end
        if ~isempty(Xi)
            plot(Xi(:,1),Xi(:,2),Style,'MarkerSize',MarkerSize,'Color',Color);
        end
        hold on;
    end
    hold off;                                    //使当前轴及图形不在具备被刷新的性质
    axis equal;                                  //坐标轴的长度单位设成相等
    grid on;                                     //在画图的时候添加网格线
    legend(Legends);
    legend('Location', 'NorthEastOutside');      //legend默认的位置在NorthEast,将其设置在外侧

end                                              //结束循环

(4)main.m文件注解如下:

%
% Copyright (c) 2015, Yarpiz (www.yarpiz.com)
% All rights reserved. Please read the "license.txt" for license terms.
%
% Project Code: YPML110
% Project Title: Implementation of DBSCAN Clustering in MATLAB
% Publisher: Yarpiz (www.yarpiz.com)
% 
% Developer: S. Mostapha Kalami Heris (Member of Yarpiz Team)
% 
% Contact Info: sm.kalami@gmail.com, info@yarpiz.com
%
//上面的代码又应该是加载程序,这里不做过多解释

clc;                    //清理命令行的意思
clear;                  //清楚存储空间的变量,以免对下面的程序运行产生影响
close all;              //关闭所有图形窗口

%% Load Data            //定义data.mat数据文件加载模块

data=load('mydata');    //数据读取
X=data.X;


%% Run DBSCAN Clustering Algorithm    //定义Run运行模块

epsilon=0.5;                          //规定两个关键参数的取值
MinPts=10;
IDX=DBSCAN(X,epsilon,MinPts);         //传入参数运行


%% Plot Results                       //定义绘图结果模块

PlotClusterinResult(X, IDX);          //传入参数,绘制图像
title(['DBSCAN Clustering (\epsilon = ' num2str(epsilon) ', MinPts = ' num2str(MinPts) ')']);

4.总结

以上就是对于DBSCAN算法每行代码详细注解的全部内容啦,希望对大家有所帮助,快快收藏,好好学习这个算法吧!我也很乐意与读者进行探讨!

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
xiaoxingxing的头像xiaoxingxing管理团队
上一篇 2022年4月4日 下午1:12
下一篇 2022年4月4日 下午1:22

相关推荐