matlab练习程序（DBSCAN）

年轻不如一拼

DBSCAN全称Density-Based Spatial Clustering of Applications with Noise，是一种密度聚类算法。

和Kmeans相比，不需要事先知道数据的类数。
以编程的角度来考虑，具体算法流程如下：
1.首先选择一个待处理数据。
2.寻找和待处理数据距离在设置半径内的数据。
3.将找到的半径内的数据放到一个队列中。
4.拿队列头数据作为当前待处理数据并不断执行第2步。
5.直到遍历完队列中所有数据，将这些数据记为一类。
6.选择没有处理到的数据作为一个待处理数据执行第2步。
7.直到遍历完所有数据，算法结束。
大概就是下图所示的样子：



我这里没有单独输出离群点，不过稍微改进增加离群点个数判断阈值应该就可以，比较容易修改。
代码如下：

1. clear all;
   
2. close all;
   
3. clc;
   
4. 
   
5. K=3;
   
6. theta=0:0.01:2*pi;
   
7. p1=[3*cos(theta) + rand(1,length(theta))/2;3*sin(theta)+ rand(1,length(theta))/2];      %生成测试数据
   
8. p2=[2*cos(theta) + rand(1,length(theta))/2;2*sin(theta)+ rand(1,length(theta))/2];
   
9. p3=[cos(theta) + rand(1,length(theta))/2;sin(theta)+ rand(1,length(theta))/2];
   
10. p=[p1 p2 p3]';
    
11. 
    
12. randIndex = randperm(length(p))';       %打乱数据顺序
    
13. p=p(randIndex,:);
    
14. plot(p(:,1),p(:,2),'.')
    
15. 
    
16. flag = zeros(length(p),1);      %聚类标记
    
17. clsnum = 0;                     %类的个数
    
18. disnear = 0.3;                 %聚类半径
    
19. 
    
20. for i=1:length(p)   
    
21.     nxtp = p(i,:);      %初始聚类半径内的邻域点队列
    
22.     if flag(i)==0
    
23.         clsnum = clsnum+1;
    
24.         pcstart = 1;            %设置队列起始指针
    
25.         preflag = flag;         %聚类标记更新
    
26.         while pcstart<=length(nxtp)         %判断是否完成队列遍历
    
27.             curp = nxtp(pcstart,:);         %得到当前要处理的点
    
28.             pcstart = pcstart+1;            %队列指针更新
    
29.             diffp = p-curp;                 %这里直接和所有数据比较了，数据量大的时候可以考虑kdtree
    
30.             dis = sqrt(diffp(:,1).*diffp(:,1)+diffp(:,2).*diffp(:,2));      %判断当前点与所有点之间的距离        
    
31. 
    
32.             ind = dis<disnear;                  %得到距离小于阈值的索引
    
33.             flag(ind) = clsnum;                 %设置当前聚类标记
    
34.             
    
35.             diff_flag = preflag-flag;   
    
36.             diff_ind = (preflag-flag)<0;        %判断本次循环相比上次循环增加的点
    
37.             
    
38.             tmp = zeros(length(p),1);
    
39.             tmp(diff_ind) = clsnum;
    
40.             flag = flag + tmp;                  %增加的点将其标记为一类
    
41.             preflag = flag;                 %聚类标记更新
    
42.             nxtp = [nxtp;p(diff_ind,:)];    %增加聚类半径内的邻域点队列
    
43.         end      
    
44.     end   
    
45. end
    
46. 
    
47. %聚类可能不止三组，我偷懒不想判断并plot了
    
48. figure;
    
49. plot(p(flag==1,1),p(flag==1,2),'r.')
    
50. hold on;
    
51. plot(p(flag==2,1),p(flag==2,2),'g.')   
    
52. plot(p(flag==3,1),p(flag==3,2),'b.')

复制代码

结果如下：
原始数据：

聚类结果：