摘 要： 基于密度的聚类是聚类算法中的一种，其主要优点是可以发现任意形状的簇，但处理大数据集时效果不佳，为此提出了一种改进的算法M-DBSCAN，保留了基于密度聚类算法的优点，同时克服了以往算法不能处理大数据集的缺点。实验结果证明，M-DBSCAN聚类算法在聚类质量及速度上都比原DBSCAN有较大提高。
关键词： 聚类； DBSCAN算法； 在线聚类
聚类就是把相似的东西归为一类，有明显区别的事物分属在不同的类别中，方便处理的一种数据挖掘的方法。目前，它已成为数据挖掘研究领域中一个非常活跃的研究方向。聚类分析技术在模式识别、数据分析、图像处理和市场研究等许多领域得到了广泛的应用。
迄今为止，人们提出了许多聚类分析的算法，其中基于密度的聚类算法能够发现任意形状的簇，应用较为广泛。其主要思想是:只要临近区域的密度(对象或数据点的数目)超过某个阈值就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤噪声和孤立点数据，发现任意形状的类。
基于密度的聚类算法主要有：DBSCAN（Density Based Spatial Clustering of Applications with Noise），OPTICS（Ordering Points to Identify the Clustering Structure）等。DBSCAN算法利用类的高密度连通性可以快速发现任意形状的类，但是当处理的数据量较大时，一般的聚类算法不能满足在线聚类这一特点，计算复杂度高，速度慢。针对此问题本文提出了一种改进的M-DBSCAN（Modified-DBSCAN）算法，改善了DBSCAN存在的不足，而且对处理大量数据有较好的效果。
1 DBSCAN算法
MARTIN E等人提出的DBSCAN算法将具有足够高密度的区域划分为一类，并可以在带有噪声的空间数据库中发现任意形状的聚类[1]。
DBSCAN算法提出了一些新的定义：
DBSCAN算法是基于密度的聚类算法，它将类看作是数据空间中被低密度区域分割开的高密度对象区域。在该算法中，发现一个聚类的过程是基于这样的事实：一个聚类能够被其中的任意一个核心对象所确定。其基本思想是：考察数据库D中的某一个点P，若P是核心点，则通过区域查询得到该点的邻域，邻域中的点和P同属于一个类，这些点将作为下一轮的考察对象(即种子点)，并通过不断地对种子点进行区域查询来扩展它们所在的类，直至找到一个完整的类。然后，依此过程寻找其他的类。最后剩下的不属于任何类的点即为噪声。DBSCAN算法可以挖掘任意形状的聚类，对数据输入顺序不敏感，并且具有处理异常数据(噪音)的能力。对具有N个样本的数据库，该算法的时间复杂性为O(NlogN)。
2 M-DBSCAN算法
2.1 在线聚类
由于处理数据量较大，一次性处理完毕不但运算量大，复杂度高，而且对存储空间的需求量大，因此本文提出一种在线式聚类算法，可以动态增加聚类数目。
算法的原理是：随着输入样本数据的不断增加，实时动态地增加聚类个数或调整聚类中心及聚类半径，在形成的任意一个聚类中，聚类中心与属于此聚类的样本点的相似度都不小于一个阈值dthr，dthr的选取将直接影响到聚类数目。
将在线式聚类算法引入后，算法的描述如下：
(1)积累一小段时间内的数据，进行归一化压缩，进行相似度计算，得到相似度矩阵；
(2)通过对相似度矩阵进行比较分析，找出邻域密度最大的数据点作为第一个初始类的中心c1；
(3)对尚未加入此类的数据点xi，比较与类中心的距离是否大于给定阈值dthr，若是，则加入此类，否则创建一个新类cj；
(4)处理完这一小段数据后，对新到来的一个数据点进行与(3)相同的做法，确定其类别；
(5)直到没有数据到来为止，输出聚类结果。
2.2 改进的算法
DBSCAN算法在对类的划分时采用的方法是：比较此数据点到各类中心的距离，若小于某阈值，则属于此类。可见阈值的选择直接影响类的划分及类的数目。但是如图1所产生的聚类模块[3]所示，这种方法带来的问题就是：距离近的不一定属于同一类，在阈值半径内的不一定属于同一类。
针对此问题,本文提出一种改进的算法M-DBSCAN。首先实现在线聚类，可以动态调整聚类的数目；之后，通过将数据点到类的平均距离与类内平均距离以及新半径与原半径作比较进行双重判决，确定数据点是否可以加入此类中，以实时调整阈值半径，解决了类划分错误的问题。
改进后整个算法描述如下：
(1)积累一小段时间内的数据，得到相似度矩阵
(2)给定阈值dthr，找出邻域密度最大的数据点作为第一个初始类的中心c1，计算S中每行值大于dthr的个数，个数最多的行号即为第一个类的中心，将第一类中的数据点存放到矩阵S’(n×n+2)的第一行，每行中的第一个为类中心，计算类的平均半径r，同时计算此类的平均距离d2，放到最后两位。
(3)对尚未加入的数据点，计算某一个数据点到类c1中的所有点的平均距离d1，类的平均距离d2；
若d1<d2，则判断加入此数据后类的半径是否变大；如果变小，将数据点加入此类，同时改变此类的平均半径；否则寻找下一个聚类，计算同上。
如果不能加入到任何一个已有聚类，则创建一个新的类，将其存入S’中。直到没有新数据到来，算法结束。
部分伪代码：
Cluster M-DBSCAN()
{
Initialize S(n×n),dthr;
For i=1:n
If S(i,j)>=dthr
sum(i)++;
count(i,j)=j;
j++;
end
end
sort(sum(:));
S’(1,:)=count(,:);
S’(1,n+1)=meanradius;
S’(1,n+2)=meandistance2;
If meandistance1<meandistance2
If meanradiusnew<meanradius
Add xj to S’(1);
S’(1,n+1)=new meanradius;
Else
Next class;
End
If no class
Create a new class S’(2);
End
…
Until no data come
It’s over
Output S’
}
3 算法性能及分析
对M-DBSCAN算法的性能作了测试，并与DBSCAN作了比较。所有的测试都在1台PC机上进行,配置P4，2.0 GHz CPU，512 MB内存，80 GB硬盘,算法用Matlab7.3实现。
测试数据集同时使用了真实数据和自行构造的模拟数据，真实数据采用SEQUOIA 2000数据库，该数据库也被参考文献[4]用于对算法的性能测试。
首先用构造的模拟数据对聚类结果进行验证。图2为DBSCAN算法在阈值半径为20时得到的结果，明显地将不同的三类作为一类输出，形成了错误的类划分；而在取同样的初始阈值半径时，图3可以看出M-DBSCAN算法得到更好的聚类结果。
从图4中可以看到两种算法在SEQUOIA 2000数据库上对不同数据量样本的执行时间的比较。算法M-DBSCAN比算法DBSCAN快得多，且随着数据量的不断增大，这种速度上的差别越来越大。表1为两种算法的错误率比较图，错误率为
，N1为算法所得聚类数目，N2为实际聚类数目。表1中可看出,改进的M-DBSCAN算法错误概率普遍要小于DBSCAN的，表明改进后的算法减小了错误率,对处理大样本集有较好的性能。
表2中的测试数据集来自Dr．JSrg Sander提供的仿照DBSCAN 中DataBase2生成的数据集DB2[8]。由表中可以看出，当数据规模为50 000时，虽然SGDO[7]处理噪音点的能力比M-DBSCAN强，但是从错误率和运行时间上M-DBSCAN比前两者都有较大的改善。CURD[6]虽然有较短的运行时间，但是存在大量的噪音点，所以从综合性能上比较M-DBSCAN更加完善，聚类质量更高。
本文讨论了一种将DBSCAN聚类算法进行改进的M-DBSCAN聚类算法，它克服了DBSCAN聚类算法不能处理大数据集的问题，并实现可以对阈值进行实时更改。试验结果显示，M-DBSCAN算法的准确性比DBSCAN算法要好，处理大数据集的速度更快。但是对于聚类数目的确定仍然是判断是否超过某阈值才可算作某一类的标准，聚类数目与阈值的选择有很大关系。因此如何自动确定聚类数目将是下一步工作的方向。
参考文献
[1] ESTER M，KRIEGEL H P，SANDER J，et a1． A densitybased algorithm for discovering cluster in large spatial databases with noise[A]． In：SIMOUDIS E，HAN J， FAYYAD U． Proeeedins of the 2nd International Conference Knowledge Discovering in Databases and Data Mining (KDD-96)[C]．Massachusetts：AAAI Press．1996:226-232．
[2] HAN Jia Wei，KAMBER M． Data mining，ovncepts and Techniques[M]．CA：Morgan Kaufmann Publishers，2000．
[3] 朱蔚恒，印鉴，谢益煌．基于数据流的任意形状聚类算法[J]．软件学报，2006，17(3)：379-386．
[4] 忻凌，倪志伟，黄玲.基于数据流的BIRCH改进聚类算法[J].计算机工程与应用，2007，43（5）：121-123
[5] 田地，王世卿.数据挖掘中基于密度和距离聚类算法设计[J].计算机技术与发展，2006，16（10）：254-257.
[6] 陈燕，耿国华，郑建国.一种改进的基于密度的聚类算法.微机发展，2005，15(3).
[7] 王翠茹，朵春红.一种改进的基于密度的DBSCAN聚类算法.广西师范大学学报：自然科学版，2007，25（4）.
[8] 周水庚，周傲英，曹晶． 基于数据分区的DBSCAN算法[J]．计算机研究与发展，2000，37(10)：1153-1159.