首页 > 代码库 > DBScan聚类算法原理与实现整理
DBScan聚类算法原理与实现整理
百度百科中的描述
算法描述：（1）检测数据库中尚未检查过的对象p，如果p为被处理(归为某个簇或者标记为噪声)，则检查其邻域，若包含的对象数不小于minPts，建立新簇C，将其中的所有点加入候选集N；（2）对候选集N 中所有尚未被处理的对象q，检查其邻域，若至少包含minPts个对象，则将这些对象加入N；如果q 未归入任何一个簇，则将q 加入C；（3）重复步骤2)，继续检查N 中未处理的对象，当前候选集N为空；（4）重复步骤1)~3)，直到所有对象都归入了某个簇或标记为噪声。 伪代码：输入：数据对象集合D，半径Eps，密度阈值MinPts输出：聚类CDBSCAN（D, Eps, MinPts）Begininit C=0; //初始化簇的个数为0for each unvisited point p in Dmark p as visited; //将p标记为已访问N = getNeighbours (p, Eps);if sizeOf(N) < MinPts thenmark p as Noise; //如果满足sizeOf(N) < MinPts，则将p标记为噪声elseC= next cluster; //建立新簇CExpandCluster (p, N, C, Eps, MinPts);end ifend forEnd其中ExpandCluster算法伪码如下：ExpandCluster(p, N, C, Eps, MinPts)add p to cluster C; //首先将核心点加入Cfor each point p’ in Nmark p‘ as visited;N’ = getNeighbours (p’, Eps); //对N邻域内的所有点在进行半径检查if sizeOf(N’) >= MinPts thenN = N+N’; //如果大于MinPts，就扩展N的数目end ifif p’ is not member of any clusteradd p’ to cluster C; //将p‘ 加入簇Cend ifend forEnd ExpandCluster
DBSCAN的Java实现：转自http://www.cnblogs.com/zhangchaoyang/articles/2182748.html
package orisun; import java.io.File;import java.util.ArrayList;import java.util.Vector;import java.util.Iterator; public class DBScan { double Eps=3; //区域半径 int MinPts=4; //密度 //由于自己到自己的距离是0,所以自己也是自己的neighbor public Vector<DataObject> getNeighbors(DataObject p,ArrayList<DataObject> objects){ Vector<DataObject> neighbors=new Vector<DataObject>(); Iterator<DataObject> iter=objects.iterator(); while(iter.hasNext()){ DataObject q=iter.next(); double[] arr1=p.getVector(); double[] arr2=q.getVector(); int len=arr1.length; if(Global.calEditDist(arr1,arr2,len)<=Eps){ //使用编辑距离// if(Global.calEuraDist(arr1, arr2, len)<=Eps){ //使用欧氏距离 // if(Global.calCityBlockDist(arr1, arr2, len)<=Eps){ //使用街区距离// if(Global.calSinDist(arr1, arr2, len)<=Eps){ //使用向量夹角的正弦 neighbors.add(q); } } return neighbors; } public int dbscan(ArrayList<DataObject> objects){ int clusterID=0; boolean AllVisited=false; while(!AllVisited){ Iterator<DataObject> iter=objects.iterator(); while(iter.hasNext()){ DataObject p=iter.next(); if(p.isVisited()) continue; AllVisited=false; p.setVisited(true); //设为visited后就已经确定了它是核心点还是边界点 Vector<DataObject> neighbors=getNeighbors(p,objects); if(neighbors.size()<MinPts){ if(p.getCid()<=0) p.setCid(-1); //cid初始为0,表示未分类；分类后设置为一个正数；设置为-1表示噪声。 }else{ if(p.getCid()<=0){ clusterID++; expandCluster(p,neighbors,clusterID,objects); }else{ int iid=p.getCid(); expandCluster(p,neighbors,iid,objects); } } AllVisited=true; } } return clusterID; } private void expandCluster(DataObject p, Vector<DataObject> neighbors, int clusterID,ArrayList<DataObject> objects) { p.setCid(clusterID); Iterator<DataObject> iter=neighbors.iterator(); while(iter.hasNext()){ DataObject q=iter.next(); if(!q.isVisited()){ q.setVisited(true); Vector<DataObject> qneighbors=getNeighbors(q,objects); if(qneighbors.size()>=MinPts){ Iterator<DataObject> it=qneighbors.iterator(); while(it.hasNext()){ DataObject no=it.next(); if(no.getCid()<=0) no.setCid(clusterID); } } } if(q.getCid()<=0){ //q不是任何簇的成员 q.setCid(clusterID); } } } public static void main(String[] args){ DataSource datasource=new DataSource(); //Eps=3,MinPts=4 datasource.readMatrix(new File("/home/orisun/test/dot.mat")); datasource.readRLabel(new File("/home/orisun/test/dot.rlabel")); //Eps=2.5,MinPts=4// datasource.readMatrix(new File("/home/orisun/text.normalized.mat"));// datasource.readRLabel(new File("/home/orisun/text.rlabel")); DBScan ds=new DBScan(); int clunum=ds.dbscan(datasource.objects); datasource.printResult(datasource.objects,clunum); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。