dbscan2.m

DBSCAN是一个基于密度的聚类算法。改算法将具有足够高度的区域划分为簇

function [Ker_b,out_b,Ker_w,out_w]=DBSCAN2(posb,posw,m,n,e,MinPts,T)
%posb为黑子点行列坐标，posw为白子行列点坐标
%m,n棋盘行列数
% T=1;%distance type:%1:Manhattan dist,2:Euclid
B=zeros(m,n);%黑子0－1矩阵
for i=1:size(posb,1)
    B(posb(i,1),posb(i,2))=1;
end
W=zeros(m,n); %白子0－1矩阵
for i=1:size(posw,1)
    W(posw(i,1),posw(i,2))=1;
end

Pos_b=[];
Sec_b=[];
for i=1:size(B,1)
    for j=1:size(B,2)
        
        if B(i,j)==0
            continue;
        end
        
        num=0;
        for m=max(1,i-e):min(size(B,1),i+e)
            for n=max(1,j-e):min(size(B,2),j+e)
                if Dst([m,n],[i,j],T)<=e&B(m,n)==1
                    num=num+1;
                end
            end
        end
        
        if num>=MinPts
            Pos_b=[Pos_b;[i,j]];
        else
            Sec_b=[Sec_b;[i,j]];
        end
        
    end
end

%构造邻接矩阵寻找连通分量
G=eye(size(Pos_b));
for i=1:size(Pos_b)
    for j=i+1:size(Pos_b)
        if Dst(Pos_b(i,:),Pos_b(j,:),T)<=e
            G(i,j)=1;
            G(j,i)=1;
        end
    end
end

%寻找核心点的连通分量
Ker_b=Graph_Search(G,Pos_b);

%探测孤立点
out_b=[];
for i=1:size(Sec_b,1)
    flag=0;
    for j=1:size(Pos_b,1)
        if  Dst(Sec_b(i,:),Pos_b(j,:),T)<=e
            flag=1;
            break;
            
        end
    end
    
    if flag==0
        out_b=[out_b;Sec_b(i,:)];
    end
    
end


Pos_w=[];
Sec_w=[];
for i=1:size(W,1)
    for j=1:size(W,2)
        
       if W(i,j)==0
            continue;
       end
       
       num=0;
        for m=max(1,i-e):min(size(W,1),i+e)
            for n=max(1,j-e):min(size(W,2),j+e)
                if Dst([m,n],[i,j],T)<=e&W(m,n)==1%Manhattan距离  
                    num=num+1;
                end
            end
        end
        
        if num>=MinPts
            Pos_w=[Pos_w;[i,j]];
        else
            Sec_w=[Sec_w;[i,j]];
        end       
        
        
    end
end

%构造邻接矩阵寻找连通分量
G=ones(size(Pos_w));
for i=1:size(Pos_w)
    for j=i+1:size(Pos_w)        
        if Dst(Pos_w(i,:),Pos_w(j,:),T)<=e
            G(i,j)=1;
            G(j,i)=1;
        end
    end
end

%寻找核心点的连通分量
Ker_w=Graph_Search(G,Pos_w);

%探测孤立点
out_w=[];
for i=1:size(Sec_w,1)
    flag=0;
    for j=1:size(Pos_w,1)
        
        if Dst(Sec_w(i,:),Pos_w(j,:),T)<=e
            flag=1;
            break;
        end
    end
    
    if flag==0
        out_w=[out_w;Sec_w(i,:)];
    end
    
end

%显示结果：
clc;
fprintf('黑子运行结果:\n')
for i=1:length(Ker_b)
    pos=Ker_b{i};
    fprintf('第%d个核心对象集:\n',i)
    for j=1:size(pos,1)
        fprintf('%2d %c\n',pos(j,1),pos(j,2)+'A'-1)
    end
end
fprintf('孤立点集:\n')
for i=1:size(out_b,1)
    fprintf('%2d %c\n',out_b(i,1),out_b(i,2)+'A'-1)
end

fprintf('\n白子运行结果:\n')
for i=1:length(Ker_w)
    pos=Ker_w{i};
    fprintf('第%d个核心对象集:\n',i)
    for j=1:size(pos,1)
        fprintf('%2d %c\n',pos(j,1),pos(j,2)+'A'-1)
    end
end
fprintf('孤立点集:\n')
for i=1:size(out_w,1)
    fprintf('%2d %c\n',out_w(i,1),out_w(i,2)+'A'-1)
end

return

%函数输入为样本点的邻接矩阵
%函数返回为简单聚类结果标记Lable
function Sets=Graph_Search(G,Pos)

    classnum=0;%初始类的个数置0
    i=1;        %搜索起始点1
    Labnum=1;   %被搜索到的点的个数，跳出最上层循环

    [M,N]=size(G);
    Label=zeros( M,1);  %标记向量记录各点对应分类

    while Labnum<(M+1)
    
        if Label(i)==0  
       
            classnum=classnum+1;
            Label(i)=classnum;
            Labnum=Labnum+1;
            
            L_Label1=1; 
            L_Label2=0;

            while L_Label1~=L_Label2
                L_Label1=sum(G(i,:)); 
                for j=1:N
                    if G(i,j)==1&Label(j)==0
                        Label(j)=classnum;
                        Labnum=Labnum+1;
                        G(i,:)=G(i,:)|G(j,:);
                    end
                end
                L_Label2=sum(G(i,:));                
            end
      
        end
   
        i=i+1;
   
    end  
    
    Sets={};
    for i=1:classnum
        ind=find(Label==i);
        Sets{i,1}=Pos(ind,:);
    end
    
return

function d=Dst(x1,x2,type)
%1:Manhattan dist
%2:Euclid
if type==1
    d=sum(abs(x1-x2));
end
if type==2
    d=sqrt((x1-x2)*(x1-x2)');
end

return

% T=1;%distance type:%1:Manhattan dist,2:Euclid
% m=11;
% n=11;
% e=2;
% MinPts=5;
% posb=[1 3
% 1 8
% 1 9
% 2 3
% 2 8
% 3 3
% 3 7
% 3 8
% 4 3
% 4 8
% 4 9
% 4 10
% 4 11
% 5 1
% 5 2
% 5 3
% 5 5
% 6 5
% 7 2
% 8 2
% 8 9
% 9 3
% 9 4
% 9 9
% 9 10
% 10 4
% 10 5
% 10 6
% 10 8
% 10 10
% 11 9];
% 
% posw=[1 2
% 1 4
% 1 6
% 1 7
% 1 10
% 2 1
% 2 2
% 2 4
% 2 5
% 2 7
% 2 9
% 2 11
% 3 2
% 3 5
% 3 6
% 3 9
% 3 10
% 3 11
% 4 1
% 4 2
% 6 7
% 6 8
% 6 9
% 7 5
% 7 6
% 7 7
% 7 9
% 8 3
% 8 4
% 8 5
% 8 7
% 8 8
% 9 5
% 9 6
% 10 2];