西安优秀的集团门户网站建设服务商,搜索引擎登录入口,邮箱登陆登录入口,北京智能模板建站最近由于要实现‘基于网格的DBSCAN算法’#xff0c;网上有没有找到现成的代码[如果您有代码#xff0c;麻烦联系我]#xff0c;只好参考已有的DBSCAN算法的实现。先从网上随便找了几篇放这儿#xff0c;之后对比研究。DBSCAN简介#xff1a;1.简介DBSCAN 算法是一种基于密…最近由于要实现‘基于网格的DBSCAN算法’网上有没有找到现成的代码[如果您有代码麻烦联系我]只好参考已有的DBSCAN算法的实现。先从网上随便找了几篇放这儿之后对比研究。DBSCAN简介1.简介DBSCAN 算法是一种基于密度的空间聚类算法。该算法利用基于密度的聚类的概念即要求聚类空间中的一定区域内所包含对象(点或其它空间对象)的数目不小于某一给定阀 值。DBSCAN 算法的显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。但是由于它直接对整个数据库进行操作且进行聚类时使用了一个全局性的表征 密度的参数因此也具有两个比较明显的弱点1. 当数据量增大时要求较大的内存支持 I/0 消耗也很大;2. 当空间聚类的密度不均匀、聚类间距离相差很大时聚类质量较差。2.DBSCAN算法的聚类过程DBSCAN算法基于一个事实一个聚类可以由其中的任何核心对象唯一确定。等价可以表述为 任一满足核心对象条件的数据对象p数据库D中所有从p密度可达的数据对象o 所组成的集合构成了一个完整的聚类C且p属于C。3.DBSCAN中的几个定义密度可达是直接密度可达的传递闭包非对称性关系密度相连是对称性关系。DBSCA目的是找到密度相连对象的最大集合。E领域给定对象p半径为E内的区域称为该对象的E领域核心对象p的E领域内样本数大于MinPts(算法输入值)则该对象p为核心对象直接密度可达对于样本集合D如果样本点q在p的E领域内且p为核心对象则p直接密度可达q密度可达对于样本集合D存在一串样本点p1,p2,p3,...pn,其中连续两个点直接密度可达则 pp1,qqn,则p密度可达q密度相连对于样本集合D中任意一点o存在p到o密度可达并且q到o密度可达那么q从p密度相连算法伪代码1 DBSCAN(SetOfPoints, Eps, MinPts){2 ClusterIdnextId(NOISE)3 for(i0;i13 ExpandCluster(SetOfPoints,Point, ClId, Eps, MinPts){14 seedsSetOfPoints.regionQuery(Point, Eps)15 if(seeds.size()0){22 currentPseeds.first()23 resultSetOfPoints.regionQuery(currentP, Eps)24 if(result.size()MinPts){25 for(i0;iView CodeJAVA实现1 packageorisun;23 importjava.io.File;4 importjava.util.ArrayList;5 importjava.util.Vector;6 importjava.util.Iterator;78 public classDBScan {910 double Eps3; //区域半径11 int MinPts4; //密度1213 //由于自己到自己的距离是0,所以自己也是自己的neighbor14 public Vector getNeighbors(DataObject p,ArrayListobjects){15 Vector neighborsnew Vector();16 Iterator iterobjects.iterator();17 while(iter.hasNext()){18 DataObject qiter.next();19 double[] arr1p.getVector();20 double[] arr2q.getVector();21 int lenarr1.length;2223 if(Global.calEditDist(arr1,arr2,len)Eps){ //使用编辑距离24 //if(Global.calEuraDist(arr1, arr2, len)Eps){//使用欧氏距离25 //if(Global.calCityBlockDist(arr1, arr2, len)Eps){//使用街区距离26 //if(Global.calSinDist(arr1, arr2, len)Eps){//使用向量夹角的正弦27 neighbors.add(q);28 }29 }30 returnneighbors;31 }3233 public int dbscan(ArrayListobjects){34 int clusterID0;35 boolean AllVisitedfalse;36 while(!AllVisited){37 Iterator iterobjects.iterator();38 while(iter.hasNext()){39 DataObject piter.next();40 if(p.isVisited())41 continue;42 AllVisitedfalse;43 p.setVisited(true); //设为visited后就已经确定了它是核心点还是边界点44 Vector neighborsgetNeighbors(p,objects);45 if(neighbors.size()48 }else{49 if(p.getCid()0){50 clusterID;51 expandCluster(p,neighbors,clusterID,objects);52 }else{53 int iidp.getCid();54 expandCluster(p,neighbors,iid,objects);55 }56 }57 AllVisitedtrue;58 }59 }60 returnclusterID;61 }6263 private void expandCluster(DataObject p, Vectorneighbors,64 int clusterID,ArrayListobjects) {65 p.setCid(clusterID);66 Iterator iterneighbors.iterator();67 while(iter.hasNext()){68 DataObject qiter.next();69 if(!q.isVisited()){70 q.setVisited(true);71 Vector qneighborsgetNeighbors(q,objects);72 if(qneighbors.size()MinPts){73 Iterator itqneighbors.iterator();74 while(it.hasNext()){75 DataObject noit.next();76 if(no.getCid()0)77 no.setCid(clusterID);78 }79 }80 }81 if(q.getCid()0){ //q不是任何簇的成员82 q.setCid(clusterID);83 }84 }85 }8687 public static voidmain(String[] args){88 DataSource datasourcenewDataSource();89 //Eps3,MinPts490 datasource.readMatrix(new File(/home/orisun/test/dot.mat));91 datasource.readRLabel(new File(/home/orisun/test/dot.rlabel));92 //Eps2.5,MinPts493 //datasource.readMatrix(new File(/home/orisun/text.normalized.mat));94 //datasource.readRLabel(new File(/home/orisun/text.rlabel));95 DBScan dsnewDBScan();96 int clunumds.dbscan(datasource.objects);97 datasource.printResult(datasource.objects,clunum);98 }99 }View CodeC实现数据结构1 #include 23 using namespacestd;45 const int DIME_NUM2; //数据维度为2全局常量67 //数据点类型8 classDataPoint9 {10 private:11 unsigned long dpID; //数据点ID12 double dimension[DIME_NUM]; //维度数据13 long clusterId; //所属聚类ID14 bool isKey; //是否核心对象15 bool visited; //是否已访问16 vector arrivalPoints; //领域数据点id列表17 public:18 DataPoint(); //默认构造函数19 DataPoint(unsigned long dpID,double* dimension , bool isKey); //构造函数2021 unsigned long GetDpId(); //GetDpId方法22 void SetDpId(unsigned long dpID); //SetDpId方法23 double* GetDimension(); //GetDimension方法24 void SetDimension(double* dimension); //SetDimension方法25 bool IsKey(); //GetIsKey方法26 void SetKey(bool isKey); //SetKey方法27 bool isVisited(); //GetIsVisited方法28 void SetVisited(bool visited); //SetIsVisited方法29 long GetClusterId(); //GetClusterId方法30 void SetClusterId(long classId); //SetClusterId方法31 vector GetArrivalPoints(); //GetArrivalPoints方法32 };View Code实现1 #include DataPoint.h23 //默认构造函数4 DataPoint::DataPoint()5 {6 }78 //构造函数9 DataPoint::DataPoint(unsigned long dpID,double* dimension , boolisKey):isKey(isKey),dpID(dpID)10 {11 //传递每维的维度数据12 for(int i0; idimension[i]dimension[i];15 }16 }1718 //设置维度数据19 void DataPoint::SetDimension(double*dimension)20 {21 for(int i0; idimension[i]dimension[i];24 }25 }2627 //获取维度数据28 double*DataPoint::GetDimension()29 {30 return this-dimension;31 }3233 //获取是否为核心对象34 boolDataPoint::IsKey()35 {36 return this-isKey;37 }3839 //设置核心对象标志40 void DataPoint::SetKey(boolisKey)41 {42 this-isKey isKey;43 }4445 //获取DpId方法46 unsigned longDataPoint::GetDpId()47 {48 return this-dpID;49 }5051 //设置DpId方法52 void DataPoint::SetDpId(unsigned longdpID)53 {54 this-dpID dpID;55 }5657 //GetIsVisited方法58 boolDataPoint::isVisited()59 {60 return this-visited;61 }626364 //SetIsVisited方法65 void DataPoint::SetVisited( boolvisited )66 {67 this-visited visited;68 }6970 //GetClusterId方法71 longDataPoint::GetClusterId()72 {73 return this-clusterId;74 }7576 //GetClusterId方法77 void DataPoint::SetClusterId( longclusterId )78 {79 this-clusterId clusterId;80 }8182 //GetArrivalPoints方法83 vectorDataPoint::GetArrivalPoints()84 {85 returnarrivalPoints;86 }View CodePYTHON实现1 from matplotlib.pyplot import *2 fromcollections import defaultdict3 import random45 #function to calculate distance6 def dist(p1, p2):7 return ((p1[0]-p2[0])**2 (p1[1]-p2[1])**2)**(0.5)89 #randomly generate around 100cartesian coordinates10 all_points[]1112 for i in range(100):13 randCoord [random.randint(1,50), random.randint(1,50)]14 if not randCoord inall_points:15 all_points.append(randCoord)161718 #take radius 8 and min. points 819 E 820 minPts 82122 #find outthe core points23 other_points []24 core_points[]25 plotted_points[]26 for point inall_points:27 point.append(0) # assign initial level 028 total 029 for otherPoint inall_points:30 distance dist(otherPoint,point)31 if distanceE:32 total13334 if total minPts:35 core_points.append(point)36 plotted_points.append(point)37 else:38 other_points.append(point)3940 #find border points41 border_points[]42 for core incore_points:43 for other inother_points:44 if dist(core,other)E:45 border_points.append(other)46 plotted_points.append(other)474849 #implement the algorithm50 cluster_label05152 for point incore_points:53 if point[2]0:54 cluster_label155 point[2]cluster_label5657 for point2 inplotted_points:58 distance dist(point2,point)59 if point2[2] 0 and distanceE:60 print point, point261 point2[2] point[2]626364 #after the points are asssigned correnponding labels, we group them65 cluster_list defaultdict(lambda: [[],[]])66 for point inplotted_points:67 cluster_list[point[2]][0].append(point[0])68 cluster_list[point[2]][1].append(point[1])6970 markers [,*,.,d,^,v,,72 #plotting the clusters73 i074 print cluster_list75 for value incluster_list:76 clustercluster_list[value]77 plot(cluster[0], cluster[1],markers[i])78 i i%1017980 #plot the noise points aswell81 noise_points[]82 for point inall_points:83 if not point in core_points and not point inborder_points:84 noise_points.append(point)85 noisex[]86 noisey[]87 for point innoise_points:88 noisex.append(point[0])89 noisey.append(point[1])90 plot(noisex, noisey, x)9192 title(str(len(cluster_list))clusters created with E str(E)Min Pointsstr(minPts)total pointsstr(len(all_points))noise Points str(len(noise_points)))93 axis((0,60,0,60))94 show()View Code参考http://www.cnblogs.com/zhangchaoyang/articles/2182748.htmlhttp://www.cnblogs.com/lovell-liu/archive/2011/11/08/2241542.htmlhttp://blog.sudipk.com.np/2013/02/implementation-of-dbscan-algorithm-for.htmlhttp://caoyaqiang.diandian.com/post/2012-09-26/40039517485
