一种基于密度的聚类的算法

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异目前，它已成为数据挖掘研究领域中一个非常活跃的研究方向。聚类分析技术在模式识别、数据分析、图像处理和市场研究等许多领域得到了广泛的应用。

　　许多算法被设计用来聚类数值类型的数据。但是，应用可能要求聚类其他类型的数据，如二元类型（binary），分类/标称类型（categorical/nominal），序数型（ordinal）数据，或者这些数据类型的混合。 其主要思想是：只要临近区域的密度（对象或数据点的数目）超过某个阈值就继续聚类。样的方法可以用来过滤噪声和孤立点数据，发现任意形状的类。

　　DBSCAN算法利用类的高密度连通性可以快速发现任意形状的类，但是当处理的数据量较大时，一般的聚类算法不能满足在线聚类这一特点，计算复杂度高，速度慢。

　　1 DBSCAN算法

　　DBSCAN（Density-Based Spatial Clustering of Applacations with Noise）是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。DBSCAN算法具有足够高密度的区域划分为一类，并可以在带有噪声的空间数据库中发现任意形状的聚类

　　DBSCAN算法提出了一些新的定义：

　　DBSCAN算法是基于密度的聚类算法，它将类看作是数据空间中被低密度区域分割开的高密度对象区域。在该算法中，发现一个聚类的过程是基于这样的事实：一个聚类能够被其中的任意一个核心对象所确定。其基本思想是：考察数据库D中的某一个点P，若P是核心点，则通过区域查询得到该点的邻域，邻域中的点和P同属于一个类，这些点将作为下一轮的考察对象，并通过不断地对种子点进行区域查询来扩展它们所在的类，直至找到一个完整的类。

　　2 M-DBSCAN算法

　　2.1 在线聚类

　　由于处理数据量较大，一次性处理完毕不但运算量大，复杂度高，而且对存储空间的需求量大，因此本文提出一种在线式聚类算法，可以动态增加聚类数目。

　　算法的原理是：随着输入样本数据的不断增加，实时动态地增加聚类个数或调整聚类中心及聚类半径，在形成的任意一个聚类中，聚类中心与属于此聚类的样本点的相似度都不小于一个阈值dthr，dthr的选取将直接影响到聚类数目。

　　将在线式聚类算法引入后，算法的描述如下：

　　（1）积累一小段时间内的数据，进行归一化压缩，进行相似度计算，得到相似度矩阵；

　　（2）通过对相似度矩阵进行比较分析，找出邻域密度最大的数据点作为第一个初始类的中心c1；

　　（3）对尚未加入此类的数据点xi，比较与类中心的距离是否大于给定阈值dthr，若是，则加入此类，否则创建一个新类cj；

　　（4）处理完这一小段数据后，对新到来的一个数据点进行与（3）相同的做法，确定其类别；

　　（5）直到没有数据到来为止，输出聚类结果。[!--empirenews.page--]

　　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’中。[!--empirenews.page--]

　部分伪代码：

　　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’

　　}[!--empirenews.page--]

　　3 算法性能及分析

　　对M-DBSCAN算法的性能作了测试，并与DBSCAN作了比较。所有的测试都在1台PC机上进行，配置P4，2.0 GHz CPU，512 MB内存，80 GB硬盘，算法用Matlab7.3实现。

　　首先用构造的模拟数据对聚类结果进行验证。图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虽然有较短的运行时间，但是存在大量的噪音点。

　　本文讨论了一种将DBSCAN聚类算法进行改进的M-DBSCAN聚类算法，它克服了DBSCAN聚类算法不能处理大数据集的问题，并实现可以对阈值进行实时更改。试验结果显示，M-DBSCAN算法的准确性比DBSCAN算法要好，处理大数据集的速度更快。但是对于聚类数目的确定仍然是判断是否超过某阈值才可算作某一类的标准，聚类数目与阈值的选择有很大关系。因此如何自动确定聚类数目将是下一步工作的方向。