密度聚类(DBSCAN)

密度聚类方法

原理解读

  DBSCAN(Density-Based Spatial Clustering Of Applications With Noise):DBSCAN需要两个参数，扫描半径 (eps)和最小包含点数(minPts)。 任选一个未被标记的点开始，找出与其距离在eps之内(包括eps)的所有附近点。如果附近点的数量大于等于minPts，则当前点与其附近点形成一个簇，并且出发点被标记。 然后递归，以相同的方法处理该簇内所有未被标记的点，从而对簇进行扩展。如果附近点的数量小于minPts，则该点被标记，不作扩展。如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后用同样的算法去处理未被访问的点，直到所有的点都被标记。

核心思想

  1. 挑选一个未标记样本，置为一类，搜索附近样本

  2. 如果附近样本数大于minPts，将这些样本归于该类，在此类中挑选未标记样本，继续搜索附近样本

  3. 重复步骤2，直到该类中所有样本都被标记

  4. 重复步骤1，直到所有样本都被标记

算法流程

代码实战

代码中所用数据集可以查看相关文档，数据集(Data Set)

DBSCAN_main.m

clear;clc;close all;
load('..\\cluster_cicle.mat');
%输入x的矩阵
x=data;
randIndex = randperm(size(x,2));
x=x(:,randIndex);
%搜索半径
eps=0.05;
%圆内点数
minpts=2;
%样本数
sample_num=size(x,2);
%特征数目
feat_num=size(x,1);
%尺度缩放到0-1
x_scale=zeros(size(x));
for i=1:feat_num
    x_scale(i,:)=(x(i,:)-min(x(i,:)))/(max(x(i,:))-min(x(i,:)));
end
[y,color_bar]=DBSCAN_classify(x_scale,sample_num,eps,minpts);
%如果数据的特征是二维的，可以绘图表示
if feat_num==2
    DBSCAN_display(x,y,color_bar,sample_num)
else
    disp('The Feature Is Not Two-Dimensional');
end

DBSCAN_classify.m

function [y,color_bar]=DBSCAN_classify(x_scale,sample_num,eps,minpts)
%标记是否已经分过类
flag=zeros(1,sample_num);
y=zeros(1,sample_num);
color_bar=[];
%类别数目
i=1;
%找到未标记的数据点则继续循环
while ~isempty(find(flag==0,1))
    %求出该点C到其余各点的距离
    distance=sum((x_scale-repmat(x_scale(:,find(flag==0,1)),1,sample_num)).^2);
    %将找到的点标记
    flag(find(flag==0,1))=1;
    %找出距离找到的点小于半径的所有点
    temp=find(distance<eps^2);
    %如果个数大于等于设定的个数
    if length(temp)>=minpts
        %建立一个类别的颜色信息
        color_bar(i,:)=[rand(1),rand(1),rand(1)];
        %将这些点全部分为i类
        y(temp)=i;
        %找出i类中没有标记的点则继续循环
        while ~isempty(find(y==i&flag==0,1))
            %求出该点D到其余各点的距离
            distance_part=sum((x_scale-repmat(x_scale(:,find(y==i&flag==0,1)),1,sample_num)).^2);
            %将找到的点标记
            flag(find(y==i&flag==0,1))=1;
            %找出距离找到的点小于半径的所有点
            temp_part=find(distance_part<eps^2);
            %如果个数大于等于设定的个数,
            if length(temp_part)>=minpts
                %将这些点全部分为i类
                y(temp_part)=i;
            end
        end
    else
        continue;
    end
    %这一类找完时，类别加1
    i=i+1;
end

DBSCAN_display.m

function DBSCAN_display(x,y,color_bar,sample_num)
figure;
hold on;
for i=1:sample_num
    if y(i)==0
        %画出噪声点，用*表示
        plot(x(1,i),x(2,i),'k*')
    else
        %画出每一类的样本数据，用o表示
        plot(x(1,i),x(2,i),'color',color_bar(y(i),:),'marker','o');
    end
end
hold off;

实验结果

性能比较

• 优点：
  • 算法简单，容易理解
  • 不依赖初始数据点的选择
  • 可以完成任意形状的聚类
• 缺点：
  • 对噪声数据敏感
  • 需要在测试前确定eps和minPts
  • 不适合数据集中密度差异较大的情况
  • 对于高维数据，距离的度量并不是很好