dbscan算法是一种基于密度聚类的算法。
核心点：若某个点的密度达到算法设定的阈值（即 r 邻域内点的数量不小于 minPts），则其为核心点。 直接密度可达：若某点p在点q的 r 邻域内，且q是核心点，则称p从q出发直接密度可达。 密度可达：若有一个点的序列q0、q1、…qk，对任意qi从qi-1出发是直接密度可达的，则称从q0到qk密度可达，这实际上是直接密度可达的“传播”。 密度相连：若从某核心点p出发，点q和点k都是密度可达的，则称点q和点k是密度相连的。
如上图所示，圆圈代表 r 邻域，红色点为核心点，从点A出发，B、C均是密度可达的，B、C则是密度相连的，且B、C为边界点，而N为噪声点。
dbscan算法本质上是一个寻找类簇并不断扩展类簇的过程，要形成类簇首先数据密度要满足要求。对任意点p，若其是核心点，则以p为中心 r 为半径可以形成一个类簇C，扩展类簇的方法则是遍历簇中的点，若有点q是核心点，则将q的 r 邻域内的点也划入类C，递归执行直到C不能再扩展。 以上图为例，假设 minPts 为3，r 为图中圆圈的半径，算法从A开始，经计算其为核心点，则将点A及其邻域内的所有点（共4个）归为类Q，接着尝试扩展类Q。查询可知类Q内所有的点均为核心点（红点），故皆具有扩展能力，点C也被划入类Q。在递归拓展的过程中，查询得知C不是核心点，类Q不能从点C处扩充，称C为边界点。边界点被定义为属于某一个类的非核心点。在若干次扩展以后类Q不能再扩张，此时形成的类为图中除N外的所有的点，点N则成为噪声点，即不属于任何一个类簇的点，等价的可以定义为从任何一个核心点出发都是密度不可达的。在上图中数据点只能聚成一个类，在实际使用中往往会有多个类，即在某一类扩展完成后另外选择一个未被归类的核心点形成一个新的类簇并扩展，算法结束的标志是所有的点都已被划入某一类或噪声，且所有的类都不可再扩展。
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; double dis=0; if((dis = Global.calEuraDist(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; } //扩展cluster private void expandCluster(DataObject p, Vector<DataObject> neighbors, int clusterID,ArrayList<DataObject> objects) { //设置id 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(); //没被加入任何cluster，加入之 if(no.getCid()<=0) no.setCid(clusterID); } } } if(q.getCid()<=0){ //q不是任何簇的成员 q.setCid(clusterID); } } }