DBSCAN聚类

一、基本原理

基于密度的聚类方法，聚类前不需要预先指定聚类的个数，生成的簇的个数基于给定数据。优点：能发现任意形状的簇，同时过滤噪声信号。
三种数据
核心点：在半径Eps内含有不少于MinPts数目的点
边界点：在半径Eps内点的数量小于MinPts，但是落在核心点的领域内
噪音点：既不是核心点也不是边界点的点

二、代码（来自matlab源码）

%
% 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)
%epsilon表示点的半径，MinPts表示关键点半径内所需包含的最小点数
    C=0;
    n=size(X,1);    % n代表点的数量
    IDX=zeros(n,1);  % IDX存储了所有元素的分类，初始化全部为0，即全部为噪音点
    D=pdist2(X,X); % 计算两点之间的距离
    visited=false(n,1); %初始化
    isnoise=false(n,1);
    for i=1:n
        if ~visited(i)
            visited(i)=true;
            Neighbors=RegionQuery(i);% 找到半径内所包含的点
            if numel(Neighbors)<MinPts  % 标记噪音点
                % X(i,:) is NOISE
                isnoise(i)=true;
            else
                C=C+1;
                ExpandCluster(i,Neighbors,C);
            end
        end
    end
    function ExpandCluster(i,Neighbors,C) % 找到同一类的点并打标
        IDX(i)=C;
        k = 1;
        while true
            j = Neighbors(k);
            if ~visited(j)
                visited(j)=true;
                Neighbors2=RegionQuery(j);
                if numel(Neighbors2)>=MinPts
                    Neighbors=[Neighbors Neighbors2];   %#ok
                end
            end
            if IDX(j)==0
                IDX(j)=C;
            end
            k = k + 1;
            if k > numel(Neighbors)
                break;
            end
        end
    end
    function Neighbors=RegionQuery(i)
        Neighbors=find(D(i,:)<=epsilon);
    end
end