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

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

许多算法被设计用来聚类数值类型的数据。但是，应用可能要求聚类其他类型的数据，如二元类型（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）直到没有数据到来为止，输出聚类结果。

2.2 改进的算法

DBSCAN算法在对类的划分时采用的方法是：比较此数据点到各类中心的距离，若小于某阈值，则属于此类。可见阈值的选择直接影响类的划分及类的数目。但是如图1所产生的聚类模块[3]所示，这种方法带来的问题就是：距离近的不一定属于同一类，在阈值半径内的不一定属于同一类。

针对此问题，本文提出一种改进的算法M-DBSCAN。首先实现在线聚类，可以动态调整聚类的数目；之后，通过将数据点到类的平均距离与类内平均距离以及新半径与原半径作比较进行双重判决，确定数据点是否可以加入此类中，以实时调整阈值半径，解决了类划分错误的问题。

改进后整个算法描述如下：

（1）积累一小段时间内的数据，得到相似度矩阵

（2）给定阈值dthr，找出邻域密度最大的数据点作为第一个初始类的中心c1，计算S中每行值大于dthr的个数，个数最多的行号即为第一个类的中心，将第一类中的数据点存放到矩阵S’（n×n+2）的第一行，每行中的第一个为类中心，计算类的平均半径r，同时计算此类的平均距离d2，放到最后两位。

（3）对尚未加入的数据点，计算某一个数据点到类c1中的所有点的平均距离d1，类的平均距离d2；

若d1d2，则判断加入此数据后类的半径是否变大；如果变小，将数据点加入此类，同时改变此类的平均半径；否则寻找下一个聚类，计算同上。

如果不能加入到任何一个已有聚类，则创建一个新的类，将其存入S’中。

　部分伪代码：

Cluster M-DBSCAN（）

{

Initialize S（n×n），dthr;

For i=1:n

If S（i,j）>=dthr

sum（i）++;

count（i,