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

1 基于密度的聚类算法

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

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

3 仿真结果及Matlab主要代码

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

图1 原始数据分布

图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

if IDX(j) == 0

IDX(j) = C;

end

k = k + 1;

if k > numel(Neighbors)

break;

end

更多相关文章

随机推荐