dbscan算法实验报告

一．算法概述1.密度聚类原理DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。2.DBSCAN密度定义DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(ϵ,MinPts)用来描述邻域的样本分布紧密程度。其中，ϵ描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为ϵ的邻域中样本个数的阈值。假设我的样本集是D=(x1,x2,...,xm),则DBSCAN具体的密度描述定义如下：1）ϵ-邻域：对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ},这个子样本集的个数记为|Nϵ(xj)|2)核心对象：对于任一样本xj∈D，如果其ϵ-邻域对应的Nϵ(xj)至少包含MinPts个样本，即如果|Nϵ(xj)|≥MinPts，则xj是核心对象。3）密度直达：如果xi位于xj的ϵ-邻域中，且xj是核心对象，则称xi由xj密度直达。注意反之不一定成立，即此时不能说xj由xi密度直达,除非且xi也是核心对象。4）密度可达：对于xi和xj,如果存在样本样本序列p1,p2,...,pT,满足p1=xi,pT=xj,且pt+1由pt密度直达，则称xj由xi密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本p1,p2,...,pT−1均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。5）密度相连：对于xi和xj,如果存在核心对象样本xk，使xi和xj均由xk密度可达，则称xi和xj密度相连。注意密度相连关系是满足对称性的。3.DBSCAN密度聚类思想DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。4.DBSCAN聚类算法下面我们对DBSCAN聚类算法的流程做一个总结。输入：样本集D=(x1,x2,...,xm)，邻域参数(ϵ,MinPts),样本距离度量方式输出：簇划分C.1）初始化核心对象集合Ω=∅,初始化聚类簇数k=0，初始化未访问样本集合Γ=D,簇划分C=∅2)对于j=1,2,...m,按下面的步骤找出所有的核心对象：a)通过距离度量方式，找到样本xj的ϵ-邻域子样本集Nϵ(xj)b)如果子样本集样本个数满足|Nϵ(xj)|≥MinPts，将样本xj加入核心对象样本集合：Ω=Ω∪{xj}3）如果核心对象集合Ω=∅，则算法结束，否则转入步骤4.4）在核心对象集合Ω中，随机选择一个核心对象o，初始化当前簇核心对象队列Ωcur={o},初始化类别序号k=k+1，初始化当前簇样本集合Ck={o},更新未访问样本集合Γ=Γ−{o}5）如果当前簇核心对象队列Ωcur=∅，则当前聚类簇Ck生成完毕,更新簇划分C={C1,C2,...,Ck},更新核心对象集合Ω=Ω−Ck，转入步骤3。6）在当前簇核心对象队列Ωcur中取出一个核心对象o′,通过邻域距离阈值ϵ找出所有的ϵ-邻域子样本集Nϵ(o′)，令Δ=Nϵ(o′)∩Γ,更新当前簇样本集合Ck=Ck∪Δ,更新未访问样本集合Γ=Γ−Δ,更新Ωcur=Ωcur∪(Nϵ(o′)∩Ω)，转入步骤5.输出结果为：簇划分C={C1,C2,...,Ck}二．实验目标算法：DBScan，基于密度的聚类算法输入：D：一个包含n个数据的数据集r：半径参数minPts：领域密度阈值输出：基于密度的聚类集合三．实验步骤标记D中所有的点为unvistedforeachpinDifp.visit=unvisted找出与点p距离不大于r的所有点集合NIfN.size()minPts标记点p为噪声点Elseforeachp'inNIfp'.visit==unvisted找出与点p距离不大于r的所有点集合N'IfN'.size()=minPts将集合N'加入集合N中去EndifElseIfp'未被聚到某个簇将p'聚到当前簇Ifp'被标记为噪声点将p'取消标记为噪声点EndIfEndIfEndIfEndforEndifEndifEndfor四．代码实现1.Point.java定义点，其中距离计算采用欧式距离publicclassPoint{privatedoublex;privatedoubley;privatebooleanisVisit;privateintcluster;privatebooleanisNoised;publicPoint(doublex,doubley){this.x=x;this.y=y;this.isVisit=false;this.cluster=0;this.isNoised=false;}publicdoublegetDistance(Pointpoint){returnMath.sqrt((x-point.x)*(x-point.x)+(y-point.y)*(y-point.y));}publicvoidsetX(doublex){this.x=x;}publicdoublegetX(){returnx;}publicvoidsetY(doubley){this.y=y;}publicdoublegetY(){returny;}publicvoidsetVisit(booleanisVisit){this.isVisit=isVisit;}publicbooleangetVisit(){returnisVisit;}publicintgetCluster(){returncluster;}publicvoidsetNoised(booleanisNoised){this.isNoised=isNoised;}publicvoidsetCluster(intcluster){this.cluster=cluster;}publicbooleangetNoised(){returnthis.isNoised;}@OverridepublicStringtoString(){returnx++y++cluster++(isNoised?1:0);}}2.DBScan.java算法实现类publicclassDBScan{privatedoubleradius;privateintminPts;publicDBScan(doubleradius,intminPts){this.radius=radius;this.minPts=minPts;}publicvoidprocess(ArrayListPointpoints){intsize=points.size();intidx=0;intcluster=1;while(idxsize){Pointp=points.get(idx++);//chooseanunvisitedpointif(!p.getVisit()){p.setVisit(true);//setvisitedArrayListPointadjacentPoints=getAdjacentPoints(p,points);//setthepointwhichadjacentpointslessthanminPtsnoisedif(adjacentPoints!=null&&adjacentPoints.size()minPts){p.setNoised(true);}else{p.setCluster(cluster);for(inti=0;iadjacentPoints.size();i++){PointadjacentPoint=adjacentPoints.get(i);//onlycheckunvisitedpoint,causeonlyunvisitedhavethechancetoaddnewadjacentpointsif(!adjacentPoint.getVisit()){adjacentPoint.setVisit(true);ArrayListPointadjacentAdjacentPoints=getAdjacentPoints(adjacentPoint,points);//addpointwhichadjacentpointsnotlessthanminPtsnoisedif(adjacentAdjacentPoints!=null&&adjacentAdjacentPoints.size()=minPts){adjacentPoints.addAll(adjacentAdjacentPoints);}}//addpointwhichdoestnotbelongtoanyclusterif(adjacentPoint.getCluster()==0){adjacentPoint.setCluster(cluster);//setpointwhichmarkednoisedbeforenon-noisedif(adjacentPoint.getNoised()){adjacentPoint.setNoised(false);}}}cluster++;}}}}privateArrayListPointgetAdjacentPoints(PointcenterPoint,ArrayListPointpoints){ArrayListPointadjacentPoints=newArrayListPoint();for(Pointp:points){//includecenterPointitselfdoubledistance=centerPoint.getDistance(p);if(distance=radius){adjacentPoints.add(p);}}returnadjacentPoints;}}3.Data.java随机模拟产生数据publicclassData{privatestaticDecimalFormatdf=(DecimalFormat)NumberFormat.getInstance();publicstaticArrayListPointgenerateSinData(intsize){ArrayListPointpoints=newArrayListPoint(size);Randomrd=newRandom(size);for(inti=0;isize/2;i++){doublex=format(Math.PI/(size/2)*(i+1));doubley=format(Math.sin(x));points.add(newPoint(x,y));}for(inti=0;isize/2;i++){doublex=format(1.5+Math.PI/(size/2)*(i+1));doubley=format(Math.cos(x));points.add(newPoint(x,y));}returnpoints;}publicstaticArrayListPointgenerateSpecialData(){ArrayListPointpoints=newArrayListPoint();points.add(newPoint