匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。宿命宽恕轮回修仙--（转）对Weka中DBSCAN算法的分析以及在C#中的实现
&&&&&&&&&&&& &&&
宿命宽恕轮回修仙
我的分类（专题）
-----------数据挖掘-----------
-----------同行博客-----------
-----------学者信息-----------
-----------回忆过去-----------
blog名称:宿命宽恕轮回修仙日志总数:18评论数量:3留言数量:0访问次数:94588建立时间:日
April 2017日一二三四五六123456789101112131415161718192021222324252627282930
　　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.DBSCANwhile (iterator.hasNext()) {　　　 DataObject dataObject = (DataObject) iterator.next();　　　 if (dataObject.getClusterLabel() == DataObject.UNCLASSIFIED) {　　　　　　　 if (expandCluster(dataObject)) {　　　　　　　　　　　 clusterID++;　　　　　　　　　　　 numberOfGeneratedClusters++;　　　　　　　　 }　　　 }}
　　buildClusterer方法中的代码比较简单，主要是提供一个处理入口。下面再来看expandCluster方法，这个方法要接收一个样本对象作为参数。在这个方法主要干几件事情：判断这个样本对象是不是核心对象，如果是核心对象再判断这个样本对象的epsilon邻域中的每一个对象，检查它们是不是核心对象，如果是核心对象则将其合并到当前的聚类中。源代码分析如下：
Weka.DBSCAN//查找dataObject这个样本对象的epsilon邻域中的所有样本对象并将其存放到一个列表中，这个列表用于存放在密度区域过程扩展中欲处理的样本对象，后面还会用到这个列表List seedList = database.epsilonRangeQuery(getEpsilon(), dataObject);//判断dataObject是不是核心对象if (seedList.size() & getMinPoints()) {　　//如果不是核心对象则将其设置为噪声点　　dataObject.setClusterLabel(DataObject.NOISE);　　//将其设置为噪声点后要返回false以防止聚类编号的增加　　}//如果样本对象dataObject是核心对象，则对其邻域中的每一个对象进行处理for (int i = 0; i & seedList.size(); i++) {　　DataObject seedListDataObject = (DataObject) seedList.get(i);　　　　//设置dataObject邻域中的每个样本对象的聚类标识，将其归为一个簇　　seedListDataObject.setClusterLabel(clusterID);　　　　//如果邻域中的样本对象与当前这个dataObject是同一个对象那么将其删除，如果在这里不做这个处理将会引起死循环　　if (seedListDataObject.equals(dataObject)) {　　　　 　　seedList.remove(i);　　　　i--;　　}}　　//对dataObject的epsilon邻域中的每一个样本对象进行处理　　for (int j = 0; j & seedList.size(); j++) {　　　 　　　　//从邻域中取出一个样本对象seedListDataObject　　　　DataObject seedListDataObject = (DataObject) seedList.get(j);　　　　　　//查找seedListDataObject的epsilon邻域并取得其中所有的样本对象　　　　List seedListDataObject_Neighbourhood =　database.epsilonRangeQuery(getEpsilon(), seedListDataObject);　　　　//判断seedListDataObject是不是核心对象　　　　if (seedListDataObject_Neighbourhood.size() &= getMinPoints()) {　　　　　　for (int i = 0; i & seedListDataObject_Neighbourhood.size(); i++){　　　　　　　　DataObject p =　(DataObject) seedListDataObject_Neighbourhood.get(i);　　　　　　　　//如果seedListDataObject样本对象是一个核心对象则将这个样本对象邻域中的所有未被聚类的对象添加到seedList中　　　　　　　　//并且设置其中未聚类对象或噪声对象的聚类标号为当前聚类标号　　　　　　　　if (p.getClusterLabel() == DataObject.UNCLASSIFIED ||　p.getClusterLabel() == DataObject.NOISE) {　　　　　　　　　　if (p.getClusterLabel() == DataObject.UNCLASSIFIED)　{　　　　　　　　　　//在这里将样本对象添加到seedList列表中的做法是一种广度优先的方法，通过这种方法来逐步扩展当前聚类。　　　　　　　　　　//这是非常重要的一条语句。如果没有这句就不能形成扩展的查找趋势，不能找到一个完全的密度连接区域。　　　　　　　　　　seedList.add(p);　　　　　　　　}　　　　　　　　p.setClusterLabel(clusterID);　　　　　　}　　　　}　　}　　//去除当前处理的样本点，其目的与前面一样，为了避免死循环　　seedList.remove(j);　　j--;}//查找到一个完整的密度连接区域后，返回真完成处理
　　上面分析了Weka中DBSCAN算法的执行流程，接下来就是C#版本的DBSCAN算法。C#的实现与Weka中的版本有一些区别。在上面的注释中已经提到过，Weka中的DBSCAN是以广度优先的方法来进行密度连接区域的扩展的，而在本文所提到的C#版本的DBSCAN算法是采用递归的方式以深度优先的方式进行密度连接区域的扩展。下面还是通过代码注释的方式进行分析，在分析之前先对几个自定义类型说明一下：
　　ClusterSample——用于表示样本对象的类
　　SampleStatus——用于表示样本对象状态的类，包含Unclassfied,Classfied,Noise三个枚举值
　　SampleCollection——用于表示样本集合的类，iCollection就是这个类的一个实例
　　代码分析：
C#.DBSCANfor (int i = 0; i & iCollection.C i++){　　　 ClusterSample sample = iCollection[i] as ClusterS　　　 if (sample != null && sample.Status == SampleStatus.Unclassfied)　　　 {　　　　　　　 RangeExpand(sample);　　　　　　　 //完成一个簇的扩展后更改聚类标号　　　　　　　 if (sample.Status == SampleStatus.Classfied)　　　　　　　 {　　　　　　　　　　　 K++;　　　　　　　 }　　　 }}
CodeIList&ClusterSample& epslionNeighborSamples = new List&ClusterSample&();　　　 epslionNeighborSamples = FindNeighborObjects(currSample);currSample.ClusterID = K;//如果大于iMinPts值则为核心对象(此判断也是递归的结束条件)//移除当前样本点否则会造成无限递归，导致溢出epslionNeighborSamples.Remove(currSample);if (epslionNeighborSamples.Count &= iMinPts){　　　 foreach (ClusterSample item in epslionNeighborSamples)　　　 {　　　　　　　 //对于currSample邻域中的每一个样本，检查其是否也是核心对象　　　　　　　 //如果是核心对象那么从currSample到这个点是直接密度可达的。并且这两个对象之间就是密度相连的　　　　　　　 //如果不满足这一点，从currSample到item这个点就不是密度相连的，这个点也就不属于当前密度连接区域　　　　　　　 IList&ClusterSample& item_neighbours = FindNeighborObjects(item);　　　　　　　 if (item_neighbours.Count &= iMinPts)　　　　　　　 {　　　　　　　　　　　 if (item.Status == SampleStatus.Unclassfied || item.Status == SampleStatus.Noise)　　　　　　　　　　　 {　　　　　　　　　　　　　　　 item.ClusterID = K;　　　 　　　　　　　　　　　　　　　 //递归地查找密度可达的样本对象　　　　　　　　　　　　　　　 RangeExpand(item);　　　　　　　　　　　 }　　　　　　　 }　　　 }　　　 epslionNeighborSamples.Clear();}else{　　　 currSample.Status = SampleStatus.N}
　　C#版本的DBSCAN算法的递归实现源于对样本集合分布形态的考虑，即对密度连接区域的搜索扩展总会收敛到某个对象，这个对象的邻域所包含的对象个数不大于参数所指定的个数，那么这个对象就是密度区域的结束位置，这时一轮递归处理结束。当对所有邻域中的对象进行了递归处理后，一个簇的生成就完成了，接着再进行下一个簇的生成，以此类推……
　　DBSCAN的执行过程是一个簇区域不断扩张的过程，所以与KMEANS不同（KMEANS对噪声数据非常敏感，也就是说KMEANS算法可能会因为噪声点而影响其计算结果），DBSCAN可以发现任意形状的聚类，并且可以发现样本集合中的噪声。在DBSCAN中没有被包含在任何簇中的样本对象就是噪声对象。
发表评论：
Sponsored By W3CHINA Blog 0.8&Processed in 0.016 second(s), page refreshed实验3_用算法实现数据聚类_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
实验3_用算法实现数据聚类
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢【转载】Weka开发—OPTICS聚类源代码分析
(Ordering points to Identify the Clustering
Structure)在论文中提出。这个算法也在中有。
源代码从开始看：
database&=
databaseForName(getDatabase_Type(), filteredInstances);
for&(int&i
= 0; i &&SPAN class=Apple-converted-space&&database.getInstances().numInstances();
&&&&DataObject
dataObject = dataObjectForName(
&&&&&&&&&&&getDatabase_distanceType(),&database.getInstances()
&&&&&&&&&&&&&&&&&&.instance(i),
Integer.toString(i),&database);
&&&&database.insert(dataObject);
database.setMinMaxValues();
这部分在中讲过了。
UpdateQueue seeds =&new&UpdateQueue();
Iterator iterator =&database.dataObjectIterator();
while&(iterator.hasNext())
&&&&DataObject
dataObject = (DataObject) iterator.next();
&&&&if&(!dataObject.isProcessed())
&&&&&&&expandClusterOrder(dataObject,
对对样本进行循环，如果没处理过，调用，调用的第一个函数：
public&List
coreDistance(int&minPoints,&double&epsilon,
DataObject dataObject) {
list = k_nextNeighbourQuery(minPoints, epsilon,
dataObject);
&&&&if&(((List)
list.get(1)).size() & minPoints) {
&&&&&&&&list.add(new&Double(DataObject.UNDEFINED));
&&&&&&&&return&
&&&&}&else&{
&&&&&&&&List
nextNeighbours_List = (List) list.get(0);
&&&&&&&&PriorityQueueElement
priorityQueueElement =
&&&&&&&&&&&&&&&&(PriorityQueueElement)nextNeighbours_List
.get(nextNeighbours_List.size() - 1);
&&&&&&&&if&(priorityQueueElement.getPriority()
&= epsilon) {
&&&&&&&&&&&&list.add(new&Double(priorityQueueElement.getPriority()));
&&&&&&&&&&&&return&
&&&&&&&&}&else&{
&&&&&&&&&&&&list.add(new&Double(DataObject.UNDEFINED));
&&&&&&&&&&&&return&
k_nextNeighbourQuery返回的中是所有的个邻居，是所有邻域中的点。如果小于，也就是它不是一个核心点，否则就是一个核心点，另外是一个优先队列，所以它最后一个元素就是最远的点。
expandClusterOrder前一部分代码为：
List list =&database.coreDistance(getMinPoints(),
getEpsilon(),
&&&&&&&dataObject);
List epsilonRange_List = (List) list.get(1);
dataObject.setReachabilityDistance(DataObject.UNDEFINED);
dataObject.setCoreDistance(((Double)
list.get(2)).doubleValue());
dataObject.setProcessed(true);
resultVector.addElement(dataObject);
得到得到的结果，初始化一些变量。
if&(dataObject.getCoreDistance()
!= DataObject.UNDEFINED)
&&&&update(seeds,
epsilonRange_List, dataObject);
&&&&while&(seeds.hasNext())
&&&&&&&UpdateQueueElement
updateQueueElement = seeds.next();
&&&&&&&DataObject
currentDataObject = (DataObject) updateQueueElement
&&&&&&&&&&&&&&.getObject();
&&&&&&&currentDataObject.setReachabilityDistance(updateQueueElement
&&&&&&&&&&&&&&.getPriority());
&&&&&&&List
list_1 =&database.coreDistance(getMinPoints(),
&&&&&&&&&&&&&&getEpsilon(),
currentDataObject);
&&&&&&&List
epsilonRange_List_1 = (List) list_1.get(1);
&&&&&&&currentDataObject.setCoreDistance(((Double)
list_1.get(2))
&&&&&&&&&&&&&&.doubleValue());
&&&&&&&currentDataObject.setProcessed(true);
&&&&&&&resultVector.addElement(currentDataObject);
&&&&&&if&(currentDataObject.getCoreDistance()
!= DataObject.UNDEFINED)
&&&&&&&&&&&update(seeds,
epsilonRange_List_1, currentDataObject);
先看一下函数：
private&void&update(UpdateQueue
seeds, List epsilonRange_list,
&&&&&&&DataObject
centralObject) {
&&&&double&coreDistance
= centralObject.getCoreDistance();
&&&&double&new_r_dist
= DataObject.UNDEFINED;
&&&&for&(int&i
= 0; i & epsilonRange_list.size(); i++) {
&&&&&&&EpsilonRange_ListElement
listElement =
(EpsilonRange_ListElement) epsilonRange_list.get(i);
&&&&&&&DataObject
neighbourhood_object = listElement.getDataObject();
&&&&&&&if&(!neighbourhood_object.isProcessed())
&&&&&&&&&&&new_r_dist
= Math.max(coreDistance,
listElement.getDistance());
&&&&&&&&&&&seeds.add(new_r_dist,
neighbourhood_object,
&&&&&&&&&&&&&&&&&&neighbourhood_object.getKey());
这里是判断领域中的点与的距离，这里中保持的就是可达距离：
中文版的《数据挖掘：概念与技术》第页，英文版页有一个例子可以讲清和的关系。
回到中，下面的代码很像是中的，从一个邻居开始，去扩展这个簇。
先翻译一段中的解释：
使用可达图（），簇的层次结构很容易得到，在下图中是一个维露天，轴是排过序的点，轴是可达距离，因为属于一个簇的点到它们最近的邻居有较低的可达距离值，所以簇在可达图中以谷，，数据挖掘那本书里的翻译有问题的形式出现，谷越深，簇越紧密（）。
下图中展示了这一概念，在它的上半部分，一个显示了一部分的人工维数据集。它的下半部分显示了用算法计算的可达图，黑色的连线把簇与它对应的谷连起来了。红色的横线表示如何得到一个簇，红线所穿过的谷都是一个簇。如果这个线向下移，就会有更多的簇合并，特别是最上面的簇，即那些变密度特征。
在这幅图中蓝点被视为噪音，在可达图中没有关于它们的谷。
现在的问题是这个图是怎么来的，通过什么方式排的序呢？还是看函数，是最终结果。而且每次都是从中取一个点，是个优先队列，它以升序排序，也就是每次取的都是最小的可达距离，这样就形成了谷状的结构，因为后来越来越找不到一个簇可达距离小的点的了。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。}