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

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

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