dbscan的matlab代码实现

%-------------------------------------------------------------------------%Function:[class,type]=dbscan(x,k,Eps)%-------------------------------------------------------------------------%Aim:%ClusteringthedatawithDensity-BasedScanAlgorithmwithNoise(DBSCAN)%-------------------------------------------------------------------------%Input:%x-dataset(m,n);m-objects,n-variables%k-numberofobjectsinaneighborhoodofanobject%(minimalnumberofobjectsconsideredasacluster)%Eps-neighborhoodradius,ifnotknownavoidthisparameterorput[]%-------------------------------------------------------------------------%Output:%class-vectorspecifyingassignmentofthei-thobjecttocertain%cluster(m,1)%type-vectorspecifyingtypeofthei-thobject%(core:1,border:0,outlier:-1)%-------------------------------------------------------------------------%Exampleofuse:%x=[randn(30,2)*.4;randn(40,2)*.5+ones(40,1)*[44]];%[class,type]=dbscan(x,5,[])%clusteringfigs('Dbscan',x,[12],class,type)%-------------------------------------------------------------------------%References:%[1]M.Ester,H.Kriegel,J.Sander,X.Xu,Adensity-basedalgorithmfor%discoveringclustersinlargespatialdatabaseswithnoise,proc.%2ndInt.Conf.onKnowledgeDiscoveryandDataMining,Portland,OR,1996,%p.226,availablefrom:%=--CO%[2]M.Daszykowski,B.Walczak,D.L.Massart,Lookingfor%NaturalPatternsinData.Part1:DensityBasedApproach,%Chemom.Intell.Lab.Syst.56(2001)83-92%-------------------------------------------------------------------------%WrittenbyMichalDaszykowski%DepartmentofChemometrics,InstituteofChemistry,%TheUniversityofSilesia%December2004%[class,type,clusteridx]=clu_dbscan_fn(x,k,Eps)x=zscore(x);%standarlize[m,~]=size(x);ifnargin3||isempty(Eps)[Eps]=epsilon(x,k);endx=[(1:m)',x];[m,n]=size(x);type=zeros(1,m);no=1;touched=zeros(m,1);fori=1:miftouched(i)==0;ob=x(i,:);D=dist(ob(2:n),x(:,2:n));ind=find(D=Eps);iflength(ind)1&&length(ind)k+1type(i)=0;class(i)=0;endiflength(ind)==1type(i)=-1;class(i)=-1;touched(i)=1;endiflength(ind)=k+1;type(i)=1;class(ind)=ones(length(ind),1)*max(no);while~isempty(ind)ob=x(ind(1),:);touched(ind(1))=1;ind(1)=[];D=dist(ob(2:n),x(:,2:n));i1=find(D=Eps);iflength(i1)1class(i1)=no;iflength(i1)=k+1;type(ob(1))=1;elsetype(ob(1))=0;endfork1=1:length(i1)iftouched(i1(k1))==0touched(i1(k1))=1;ind=[ind,i1(k1)];class(i1(k1))=no;endendendendno=no+1;endendendi1=find(class==0);class(i1)=-1;type(i1)=-1;maxlab=max(class);clusteridx=[];clun=[];forck=1:maxlabtidx=find(class==ck);clusteridx=[clusteridx;[tidx,zeros(1,m-length(tidx))]];clun=[clun,length(tidx)];enddisp(clun);%...........................................function[Eps]=epsilon(x,k)%Function:[Eps]=epsilon(x,k)%%Aim:%AnalyticalwayofestimatingneighborhoodradiusforDBSCAN%%Input:%x-datamatrix(m,n);m-objects,n-variables%k-numberofobjectsinaneighborhoodofanobject%(minimalnumberofobjectsconsideredasacluster)[m,n]=size(x);Eps=((prod(max(x)-min(x))*k*gamma(.5*n+1))/(m*sqrt(pi.^n))).^(1/n);disp('EPS:');disp(Eps);%............................................function[D]=dist(i,x)%function:[D]=dist(i,x)%%Aim:%CalculatestheEuclideandistancesbetweenthei-thobjectandallobjectsinx%%Input:%i-anobject(1,n)%x-datamatrix(m,n);m-objects,n-variables%%Output:%D-Euclideandistance(m,1)[m,n]=size(x);D=sqrt(sum((((ones(m,1)*i)-x).^2)'));ifn==1D=abs((ones(m,1)*i-x))';end%********************************************************