注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

Weka开发[42]——DBScan源代码分析  

2010-05-15 14:16:48|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

       DBScan是由论文A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise提出的,不过我想看看wiki里的解释就差不多了,甚至可以直接看代码,这算法概念很多,实现起来倒不难。

DBScan的算法如下,不过它与weka里的实现有点区别。

DBSCAN(D, eps, MinPts)

C = 0

for each unvisited point P in dataset D

   mark P as visited

   N = getNeighbors (P, eps)

   if sizeof(N) < MinPts

      mark P as NOISE

   else

      C = next cluster

      expandCluster(P, N, C, eps, MinPts)

      

expandCluster(P, N, C, eps, MinPts)

add P to cluster C

for each point P' in N

   if P' is not visited

      mark P' as visited

      N' = getNeighbors(P', eps)

      if sizeof(N') >= MinPts

         N = N joined with N'

   if P' is not yet member of any cluster

      add P' to cluster C

       DBScan算法的优缺点,翻译自wiki

优点:

1.       DBScan不需要像k-means算法一样,要指定簇的个数。

2.       DBScan可以聚出任意形状的簇,它甚至可以找到被另一个簇包围(但不连起来的)的簇,因为有MinPts参数,single-link现象(不同的簇被一个点连起的细线连起来了)被降低了。

3.       DBScan有噪音的概念。

4.       DBScan只需有两个参数,并且对数据库中点的排列顺序不敏感。

缺点:

1.       只有当getNeighbors(P,epsilon)中的距离公式合理时,DBScan才能产生好的簇,最常用的距离公式是欧几里德距离公式。但在高维数据时,这个距离公式简直是没用。

2.       DBScan对变密度数据集效果不佳。

源码从buildClusterer开始看:

database = databaseForName(getDatabase_Type(), filteredInstances);

for (int i = 0; i < database.getInstances().numInstances(); i++) {

    DataObject dataObject = dataObjectForName(

           getDatabase_distanceType(), database.getInstances()

                  .instance(i), Integer.toString(i), database);

    database.insert(dataObject);

}

database.setMinMaxValues();

       database_Type=”weka.clusterers.forOPTICSAndDBScan.Databases.SequentialDatabase”为默认值,在databaseForName中:

Object o = null;

 

Constructor co = null;

try {

    co = (Class.forName(database_Type))

           .getConstructor(new Class[] { Instances.class });

    o = co.newInstance(new Object[] { instances });

}

中调用的是:

public SequentialDatabase(Instances instances) {

    this.instances = instances;

    treeMap = new TreeMap();

}

       将下来在buildClusterer中的dataObjectForNamedatabaseForName相似,调用的是:

public EuclidianDataObject(Instance originalInstance, String key, Database database) {

    this.database = database;

    this.key = key;

    instance = originalInstance;

    clusterID = DataObject.UNCLASSIFIED;

    processed = false;

    c_dist = DataObject.UNDEFINED;

    r_dist = DataObject.UNDEFINED;

}

       SequentialDatabaseinsert函数为:

public void insert(DataObject dataObject) {

    treeMap.put(dataObject.getKey(), dataObject);

}

       dataObject.getKey返回的k,就是原数据集中样本的下标。

       buildClusterer中的setMinMaxValues是得到每个属性的最小值(attributeMinValues[j])最大值(attributeMaxValues[j])。

Iterator iterator = database.dataObjectIterator();

while (iterator.hasNext()) {

    DataObject dataObject = (DataObject) iterator.next();

    if (dataObject.getClusterLabel() == DataObject.UNCLASSIFIED) {

       if (expandCluster(dataObject)) {

           clusterID++;

           numberOfGeneratedClusters++;

       }

    }

}

       直接看expandCluster函数,expandCluster的调用的第一个函数是epsilonRangeQuery

public List epsilonRangeQuery(double epsilon, DataObject queryDataObject) {

    ArrayList epsilonRange_List = new ArrayList();

    Iterator iterator = dataObjectIterator();

    while (iterator.hasNext()) {

        DataObject dataObject = (DataObject) iterator.next();

        double distance = queryDataObject.distance(dataObject);

        if (distance < epsilon) {

            epsilonRange_List.add(dataObject);

        }

    }

 

    return epsilonRange_List;

}

       这里将与dataObject距离小于epsilon的放到epsilonRage_List中。

/** dataObject is NO coreObject */

if (seedList.size() < getMinPoints()) {

    dataObject.setClusterLabel(DataObject.NOISE);

    return false;

}

       这里就是前面伪代码中的Size(N)<MinPts,如果小于MinPts,也就是周围没有足够的点,就将它设为噪音。

/** dataObject is coreObject */

for (int i = 0; i < seedList.size(); i++) {

    DataObject seedListDataObject = (DataObject) seedList.get(i);

    /** label this seedListDataObject with the current clusterID,

because it is in epsilon-range */

    seedListDataObject.setClusterLabel(clusterID);

    if (seedListDataObject.equals(dataObject)) {

       seedList.remove(i);

       i--;

    }

}

       如果大于MinPts,就将seedListDataObject中的样本都标记为当前簇的IDclusterID)。

/** Iterate the seedList of the startDataObject */

for (int j = 0; j < seedList.size(); j++) {

    DataObject seedListDataObject = (DataObject) seedList.get(j);

    List seedListDataObject_Neighbourhood = database.epsilonRangeQuery(

           getEpsilon(), seedListDataObject);

 

    /** seedListDataObject is coreObject */

    if (seedListDataObject_Neighbourhood.size() >= getMinPoints()) {

     for(int i = 0; i < seedListDataObject_Neighbourhood.size(); i++) {

           DataObject p = (DataObject) seedListDataObject_Neighbourhood

                  .get(i);

           if (p.getClusterLabel() == DataObject.UNCLASSIFIED

                  || p.getClusterLabel() == DataObject.NOISE) {

              if (p.getClusterLabel() == DataObject.UNCLASSIFIED) {

                  seedList.add(p);

              }

              p.setClusterLabel(clusterID);

           }

       }

    }

    seedList.remove(j);

    j--;

}

       将刚才得到的邻居循环,将每个邻居(P’, seedListDataObject)再找邻居,如果邻居的邻居数大于MinPts,那么对这些邻居循环,如果这个点还是没有处理过的,就将它放到seedList中,也就是扩展。然后把未处理过的点和噪音点设为当前的簇ID,这里没有将噪音点放到seedList中的原因是噪音点以前就判断过它的邻居不会超过MinPts,所以没必要再处理一次。最后移除这个点,进行下一次循环(这种情况应该用whie循环比较好吧?)。

public int clusterInstance(Instance instance) throws Exception {

    if (processed_InstanceID >= database.size())

       processed_InstanceID = 0;

    int cnum = (database.getDataObject(Integer

           .toString(processed_InstanceID++))).getClusterLabel();

    if (cnum == DataObject.NOISE)

       throw new Exception();

    else

       return cnum;

}

       这个是返回第processed_InstanceId个样本的簇ID,与instance没关系。也就是说,每次调用都返回下一个样本的簇ID

 

 

 

 

 

  评论这张
 
阅读(3505)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017