realdbscan.m

二维的DBSCAN聚类算法

function [Clusters]=realDBSCAN(x,y,Eps,MinPts)
%MinPts实际上是书p242页的MinPts+1，因为计一个对象的Eps临域内的点时，把该对象计算在内了。
%输出: Clusters，每一行代表一个簇，形式为簇的对象对应的原数据集的ID
%ObjSet: 代表数据集，存在第i个对象则相应的ObjSet(i)=1
  DtNb=length(x);
  Clusters=[];
  ObjSet=linspace(1,1,DtNb);        %所有对象设置为1
    
  for ObjID=1 : 1 : DtNb            %遍历数据集
      if ObjSet(ObjID)==1           %如果数据集中有此对象则搜索其所在的簇,结果为簇的对象的ID的无序排列
          OneCluster=[];
          OneCluster=SearchCluster(ObjID,ObjSet,x,y,Eps,MinPts);
          if not(isempty(OneCluster))       %如果簇不为空则添加入簇组，同时从数据集中删除相应对象
              [Clusters,ObjSet]=PutInCluster(Clusters,OneCluster,ObjSet);
          end
      end
  end
end

function [MySet]=SearchCluster(ObjID,ObjSet,x,y,Eps,MinPts)
  MySet=[ObjID];
  pt=1;
  while pt<=length(MySet)               %只要没有到达聚类的尾部就继续（即聚类停止增长前）
      id=MySet(pt);
      x0=x(id);
      y0=y(id);
      EpsRange=[];
      for i=1:1:length(x)               %在整个数据集中查找仍然在（没有被其他聚类吸收）的对象
          if ObjSet(i)==1
            if (sqrt((x(i)-x0)^2+(y(i)-y0)^2)<=Eps)
                EpsRange=[EpsRange i];
            end
          end
      end
      if length(EpsRange)>=MinPts
          MySet=MyAppend(MySet,EpsRange);
      end
      pt=pt+1;
  end
  if length(MySet)<MinPts               %如果簇的元素少于MinPts即是没有产生簇，所以返回“空”
      MySet=[];
  end
end
  



function [AplusB]=MyAppend(A,B)  
%Append elements of B to the end of A,which was
AplusB=A;
t=0;
    for i=1:length(B)
        t=B(i);
        flag=0;
        for j=1:length(A)
            if t==A(j) 
                flag=1;         %when find the same: flag=1
                break
            end
        end
        if flag==0              %if not in A then append it to the end of A
            AplusB=[AplusB t];
        end
    end  
end


function [C,O]=PutInCluster(A,B,O)
%将新的簇B 放入簇组A中，更新数据集O
%OneCluster形式为[3 7 1 ...]对应的 Clusters中的相应行形式为[1 0 1 0 0 0 1 ...]
  if length(A)==0                       %簇组为空时添加入第一行
      i=1;
  else
      i=length(A(:,1))+1;               %簇组不为空时，添加入新行i
  end
  A(i,:)=linspace(0,0,length(O));
  for j=1 : 1 :length(B)
      t=B(j);
      A(i,t)=1;
  end  
  C=A;
  O=~sum(C,1);                          %取反即可得到剩余的对象
end

function [NewObjSet]=ReSetObjSet(ObjSet,Clusters)
  Lobj=length(ObjSet);
  Lclu=length(Clusters);
  tmp1=sum(Clusters,2);
  if Lclu<Lobj
      tmp2=linspace(0,0,Lobj-Lclu);
      tmp1=[tmp1 tmp2];
  end
  NewObjSet=xor(ObjSet,tmp1);
end