对Weka中DBSCAN算法的分析以及在C#中的实现

核心提示：DBSCAN算法是常用的数据挖掘算法，所有的聚类方法分为若干类型，对Weka中DBSCAN算法的分析以及在C#中的实现，前面讨论过的KMEANS算法是基于划分的方法进行聚类，而这次提到的DBSCAN算法是基于密度的方法，在这个方法中处理的主要代码如下，当expandCluster方法返回真的时候就说明一个簇已经形成，当

DBSCAN算法是常用的数据挖掘算法。所有的聚类方法分为若干类型，前面讨论过的KMEANS算法是基于划分的方法进行聚类，而这次提到的DBSCAN算法是基于密度的方法。当然其它的还有基于层次凝聚和分裂的方法、基于模型的方法等。我先对Weka中实现的DBSCAN算法进行一个介绍和分析，然后再分析自己用C#实现的DBSCAN方法。但在这之前要解释几个概念，如果之前没有了解过这个算法的话，最好是先熟悉几个概念：epsilon-邻域、核心对象、（直接）密度可达、密度相连，这些概念可以在《数据挖掘概念与技术》一书中找到，了解这些概念对理解这个算法来说是很重要的。

我们先来看看在Weka中是如何实现DBSCAN算法的：

DBSCAN算法的源代码在Weka的weka.clusterers这个包中，文件名为DBScan.java。其中buildClusterer和expandCluster这两个方法是最核心的方法。buildClusterer是所有聚类方法的接口方法，而expandCluster是用于扩展样本对象集合的高密度连接区域的。另外还有一个叫epsilonRangeQuery的方法，这个方法位置Database类中，用于查询指定对象在epsilon邻域内的样本对象集合。

在buildClusterer方法中，通过对每个未聚类的样本点调用expandCluster方法进行处理，查找由这个对象开始的密度相连的最大样本对象集合。在这个方法中处理的主要代码如下，当expandCluster方法返回真的时候就说明一个簇已经形成，取下一个聚类标号。

Weka.DBSCAN
while (iterator.hasNext()) {
　　　 DataObject dataObject = (DataObject) iterator.next();
　　　 if (dataObject.getClusterLabel() == DataObject.UNCLASSIFIED) {
　　　　　　　 if (expandCluster(dataObject)) {
　　　　　　　　　　　 clusterID++;
　　　　　　　　　　　 numberOfGeneratedClusters++;
　　　　　　　　 }
　　　 }
}