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

核心提示： 上面分析了Weka中DBSCAN算法的执行流程，接下来就是C#版本的DBSCAN算法，对Weka中DBSCAN算法的分析以及在C#中的实现(3)，C#的实现与Weka中的版本有一些区别，在上面的注释中已经提到过，DBSCAN可以发现任意形状的聚类，并且可以发现样本集合中的噪声，Weka中的

上面分析了Weka中DBSCAN算法的执行流程，接下来就是C#版本的DBSCAN算法。C#的实现与Weka中的版本有一些区别。在上面的注释中已经提到过，Weka中的DBSCAN是以广度优先的方法来进行密度连接区域的扩展的，而在本文所提到的C#版本的DBSCAN算法是采用递归的方式以深度优先的方式进行密度连接区域的扩展。下面还是通过代码注释的方式进行分析，在分析之前先对几个自定义类型说明一下：

ClusterSample——用于表示样本对象的类

SampleStatus——用于表示样本对象状态的类，包含Unclassfied,Classfied,Noise三个枚举值

SampleCollection——用于表示样本集合的类，iCollection就是这个类的一个实例

代码分析：

C#.DBSCAN
for (int i = 0; i < iCollection.Count; i++)
{
　　　 ClusterSample sample = iCollection[i] as ClusterSample;

　　　 if (sample != null && sample.Status == SampleStatus.Unclassfied)
　　　 {
　　　　　　　 RangeExpand(sample);

　　　　　　　 //完成一个簇的扩展后更改聚类标号
　　　　　　　 if (sample.Status == SampleStatus.Classfied)
　　　　　　　 {
　　　　　　　　　　　 K++;
　　　　　　　 }
　　　 }
}

Code
IList<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.Noise;
}

C#版本的DBSCAN算法的递归实现源于对样本集合分布形态的考虑，即对密度连接区域的搜索扩展总会收敛到某个对象，这个对象的邻域所包含的对象个数不大于参数所指定的个数，那么这个对象就是密度区域的结束位置，这时一轮递归处理结束。当对所有邻域中的对象进行了递归处理后，一个簇的生成就完成了，接着再进行下一个簇的生成，以此类推……

DBSCAN的执行过程是一个簇区域不断扩张的过程，所以与KMEANS不同（KMEANS对噪声数据非常敏感，也就是说KMEANS算法可能会因为噪声点而影响其计算结果），DBSCAN可以发现任意形状的聚类，并且可以发现样本集合中的噪声。在DBSCAN中没有被包含在任何簇中的样本对象就是噪声对象。