基于密度的聚类算法——DBSCAN算法

基于密度的聚类算法

基于密度的聚类算法(也叫做“密度聚类算法”)假设聚类结构能通过样本分布的紧密程度确定。在通常情况下,基于密度的聚类算法从样本密度的角度来考察样本之间的可连接性,并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。DBSCAN是一种典型的基于密度的聚类算法。

基于密度的聚类算法——DBSCAN算法

基于密度的聚类算法——DBSCAN算法

基于密度的聚类算法——DBSCAN算法

基于上述概念,DBSCAN将簇的定义为:由密度可达关系导出的最大的密度相连样本集合。DBSCAN聚类算法伪代码如下所示。

基于密度的聚类算法——DBSCAN算法

基于密度的聚类算法——DBSCAN算法

基于密度的聚类算法——DBSCAN算法

仿真结果及Matlab主要代码

下图是使用DBSCAN算法的聚类结果图。图1是设定生成的数据点,图2是聚类结果图。

基于密度的聚类算法——DBSCAN算法

图1 原始数据分布

基于密度的聚类算法——DBSCAN算法

图2 聚类结果

Matlab代码实现(主要函数):

main函数:

clear all; close all; clc; 

%% 生成测试数据

theta = 0:0.01:2*pi;

d1 = [3*cos(theta) +rand(1,length(theta))/2;3*sin(theta)+ rand(1,length(theta))/2];

d2 = [2*cos(theta) +rand(1,length(theta))/2;2*sin(theta)+ rand(1,length(theta))/2];

d3 = [cos(theta) +rand(1,length(theta))/2;sin(theta)+ rand(1,length(theta))/2];

d = [d1 d2 d3]'; 

randIndex = randperm(length(d))';

d = d(randIndex,:);

figure(1)

plot(d(:,1),d(:,2),'.')  %原始数据画图

epsilon = threshold_calculate(d);  %计算epsilon值

MinPts = 5;

IDX1 = DBSCAN(d,epsilon,MinPts);   %利用DBSCAN聚类

figure(2)

plot_clusterin_result(d,IDX1);     %画出结果图

 

threshold_calculate阈值计算函数

function threshold = threshold_calculate(d)

%% KNN k距离图,确定ε

N = size(d,1);

M = 1000;

ratio = 0.007;

Kdist = zeros(M,1);

[~,Dist] = knnsearch(d(2:end,:),d(1,:)); %在d(2:numData,:)找到和A(1,:)最相似的行

Kdist(1) = Dist;

for i = 2:M

    [~,Dist]= knnsearch(d([1:i-1,i+1:end],:),d(i,:));

    Kdist(i)= Dist;

end

[sortKdist,~] = sort(Kdist,'descend');

threshold = sortKdist(round(M*ratio));

 

DBSCAN聚类函数

function [IDX,isnoise] = DBSCAN(A,epsilon,MinPts)

C = 0;

n = size(A,1);

IDX = zeros(n,1);

D = pdist2(A,A);   %计算(A,A)的行的距离

visited = false(n,1);

isnoise = false(n,1);

for i = 1:n

    if~visited(i)

       visited(i) = true;

       Neighbors = find(D(i,:) <= epsilon);

        ifnumel(Neighbors) < MinPts    %X(i,:)是噪声,标为0

           isnoise(i) = true;

        else

            C= C+1;    %对簇进行扩展

           IDX(i) = C;

            k= 1;

           while true

               j = Neighbors(k);

               if ~visited(j)

                   visited(j) = true;

                   Neighbors2 = find(D(j,:) <= epsilon);

                   if numel(Neighbors2) >= MinPts

                        Neighbors = [NeighborsNeighbors2];

                   end

               end

               if IDX(j) == 0

                   IDX(j) = C;

               end

               k = k + 1;

               if k > numel(Neighbors)

                   break;

               end

           end

        end

    end

end


上一篇:6. DBSCAN浮光略影


下一篇:shiro源码篇 - shiro的session创建,你值得拥有