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

一、基于密度的聚类算法的概述

    最近在Science上的一篇基于密度的聚类算法《Clustering by fast search and find of density peaks》引起了大家的关注(在我的博文“论文中的机器学习算法——基于密度峰值的聚类算法”中也进行了中文的描述)。于是我就想了解下基于密度的聚类算法,熟悉下基于密度的聚类算法与基于距离的聚类算法,如K-Means算法之间的区别。

    基于密度的聚类算法主要的目标是寻找被低密度区域分离的高密度区域。与基于距离的聚类算法不同的是,基于距离的聚类算法的聚类结果是球状的簇,而基于密度的聚类算法可以发现任意形状的聚类,这对于带有噪音点的数据起着重要的作用。

二、DBSCAN算法的原理

1、基本概念

2、算法流程

(流程)

三、实验仿真

    在实验中使用了两个测试数据集,数据集的原始图像如下:

(数据集1)

(数据集2)

数据集1相对比较简单。显然我们可以发现数据集1共有两个类,数据集2有四个类,下面我们通过DBSCAN算法实现数据点的聚类:

MATLAB代码

主程序

%% DBSCAN
clear all;
clc;

%% 导入数据集
% data = load('testData.txt');
data = load('testData_2.txt');

% 定义参数Eps和MinPts
MinPts = 5;
Eps = epsilon(data, MinPts);

[m,n] = size(data);%得到数据的大小

x = [(1:m)' data];
[m,n] = size(x);%重新计算数据集的大小
types = zeros(1,m);%用于区分核心点1,边界点0和噪音点-1
dealed = zeros(m,1);%用于判断该点是否处理过,0表示未处理过
dis = calDistance(x(:,2:n));
number = 1;%用于标记类

%% 对每一个点进行处理
for i = 1:m
    %找到未处理的点
    if dealed(i) == 0
        xTemp = x(i,:);
        D = dis(i,:);%取得第i个点到其他所有点的距离
        ind = find(D<=Eps);%找到半径Eps内的所有点
        
        %% 区分点的类型
        
        %边界点
        if length(ind) > 1 && length(ind) < MinPts+1
            types(i) = 0;
            class(i) = 0;
        end
        %噪音点
        if length(ind) == 1
            types(i) = -1;
            class(i) = -1;
            dealed(i) = 1;
        end
        %核心点(此处是关键步骤)
        if length(ind) >= MinPts+1
            types(xTemp(1,1)) = 1;
            class(ind) = number;
            
            % 判断核心点是否密度可达
            while ~isempty(ind)
                yTemp = x(ind(1),:);
                dealed(ind(1)) = 1;
                ind(1) = [];
                D = dis(yTemp(1,1),:);%找到与ind(1)之间的距离
                ind_1 = find(D<=Eps);
                
                if length(ind_1)>1%处理非噪音点
                    class(ind_1) = number;
                    if length(ind_1) >= MinPts+1
                        types(yTemp(1,1)) = 1;
                    else
                        types(yTemp(1,1)) = 0;
                    end
                    
                    for j=1:length(ind_1)
                       if dealed(ind_1(j)) == 0
                          dealed(ind_1(j)) = 1;
                          ind=[ind ind_1(j)];   
                          class(ind_1(j))=number;
                       end                    
                   end
                end
            end
            number = number + 1;
        end
    end
end

% 最后处理所有未分类的点为噪音点
ind_2 = find(class==0);
class(ind_2) = -1;
types(ind_2) = -1;

%% 画出最终的聚类图
hold on
for i = 1:m
    if class(i) == -1
        plot(data(i,1),data(i,2),'.r');
    elseif class(i) == 1
        if types(i) == 1
            plot(data(i,1),data(i,2),'+b');
        else
            plot(data(i,1),data(i,2),'.b');
        end
    elseif class(i) == 2
        if types(i) == 1
            plot(data(i,1),data(i,2),'+g');
        else
            plot(data(i,1),data(i,2),'.g');
        end
    elseif class(i) == 3
        if types(i) == 1
            plot(data(i,1),data(i,2),'+c');
        else
            plot(data(i,1),data(i,2),'.c');
        end
    else
        if types(i) == 1
            plot(data(i,1),data(i,2),'+k');
        else
            plot(data(i,1),data(i,2),'.k');
        end
    end
end
hold off

距离计算函数

%% 计算矩阵中点与点之间的距离
function [ dis ] = calDistance( x )
    [m,n] = size(x);
    dis = zeros(m,m);
    
    for i = 1:m
        for j = i:m
            %计算点i和点j之间的欧式距离
            tmp =0;
            for k = 1:n
                tmp = tmp+(x(i,k)-x(j,k)).^2;
            end
            dis(i,j) = sqrt(tmp);
            dis(j,i) = dis(i,j);
        end
    end
end

epsilon函数

function [Eps]=epsilon(x,k)

% Function: [Eps]=epsilon(x,k)
%
% Aim: 
% Analytical way of estimating neighborhood radius for DBSCAN
%
% Input: 
% x - data matrix (m,n); m-objects, n-variables
% k - number of objects in a neighborhood of an object
% (minimal number of objects considered as a cluster)



[m,n]=size(x);

Eps=((prod(max(x)-min(x))*k*gamma(.5*n+1))/(m*sqrt(pi.^n))).^(1/n);

最终的结果

(数据集1的聚类结果)

(数据集2的聚类结果)

在上面的结果中,红色的点代表的是噪音点,点代表的是边界点,十字代表的是核心点。不同的颜色代表着不同的类。

参考文献

[1] M. Ester, H. Kriegel, J. Sander, X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise,  www.dbs.informatik.uni-muenchen.de/cgi-bin/papers?query=--CO [2] M. Daszykowski, B. Walczak, D. L. Massart, Looking for Natural Patterns in Data. Part 1: Density Based Approach

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习之旅

应用:数据预处理-异常值识别

上四分位数Q3,又叫做升序数列的75%位点 下四分位数Q1,又叫做升序数列的25%位点 箱式图检验就是摘除大于Q3+3/2*(Q3-Q1),小于Q1-3/2...

15030
来自专栏大数据挖掘DT机器学习

比较R语言机器学习算法的性能

原文:Compare The Performance of Machine Learning Algorithms in R 译文:http://g...

35660
来自专栏AI科技评论

干货 | 史上最好记的神经网络结构速记表(上)

本文提供了神经网络结构速查表,盘点了神经网络的大量框架,并绘制了直观示意图进行说明,是人手必备的神经网络学习小抄。 新的神经网络结构不断涌现,我们很难一一掌握。...

434120
来自专栏大数据挖掘DT机器学习

数据处理的统计学习(scikit-learn教程)

Scikit-learn 是一个紧密结合Python科学计算库(Numpy、Scipy、matplotlib),集成经典机器学习算法的Python模块。 一、统...

62450
来自专栏AI科技大本营的专栏

多图 | 从神经元到CNN、RNN、GAN…神经网络看本文绝对够了

作者 | FJODOR VAN VEEN 编译 | AI100(ID:rgznai100) 在深度学习十分火热的今天,不时会涌现出各种新型的人工神经网络,想要实...

83590
来自专栏AI研习社

史上最好记的神经网络结构速记表(上)

翻译 / 陈俊雅 校对 / 李傲 整理 / 雷锋字幕组 本文提供了神经网络结构速查表,盘点了神经网络的大量框架,并绘制了直观示意图进行说明,是人手必备的神经网络...

422120
来自专栏深度学习入门与实践

【深度学习系列】用PaddlePaddle和Tensorflow实现经典CNN网络AlexNet

上周我们用PaddlePaddle和Tensorflow实现了图像分类,分别用自己手写的一个简单的CNN网络simple_cnn和LeNet-5的CNN网络识别...

39780
来自专栏杨熹的专栏

什么是 Dropout

为了应对神经网络很容易过拟合的问题,2014年 Hinton 提出了一个神器, **Dropout: A Simple Way to Prevent Neur...

42880
来自专栏Petrichor的专栏

论文阅读: ResNet

ResNet论文是里程碑级的basemodel,因此获得了 CVPR 2016 Best Paper,并统领江湖至今:

38530
来自专栏IT派

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

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

19640

扫码关注云+社区

领取腾讯云代金券