对Weka中DBSCAN算法的分析以及在C#中的实现
2009-05-23 08:29:21 来源:WEB开发网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++;
}
}
}
- ››算法大全(3) 二叉树
- ››算法
- ››算法从哪学起
更多精彩
赞助商链接