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
输出:聚类C
DBSCAN(D, Eps, MinPts)
Begin
init C=0; //初始化簇的个数为0
for each unvisited point p in D
mark p as visited; //将p标记为已访问
N = getNeighbours (p, Eps);
if sizeOf(N) < MinPts then
mark p as Noise; //如果满足sizeOf(N) < MinPts,则将p标记为噪声
else
C= next cluster; //建立新簇C
ExpandCluster (p, N, C, Eps, MinPts);
end if
end for
End
其中ExpandCluster算法伪码如下:
ExpandCluster(p, N, C, Eps, MinPts)
add p to cluster C; //首先将核心点加入C
for each point p’ in N
mark p‘ as visited;
N’ = getNeighbours (p’, Eps); //对N邻域内的所有点在进行半径检查
if sizeOf(N’) >= MinPts then
N = N+N’; //如果大于MinPts,就扩展N的数目
end if
if p’ is not member of any cluster
add p’ to cluster C; //将p‘ 加入簇C
end if
end for
End 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);
    }
}

 

 
 
 

DBScan聚类算法原理与实现整理,布布扣,bubuko.com

DBScan聚类算法原理与实现整理

上一篇:功能齐全、效率一流的免费开源数据库导入导出工具(c#开发,支持SQL server、SQLite、ACCESS三种数据库),每月借此处理数据5G以上


下一篇:linux 进程管理和内存分配