现有的基于网格聚类算法在付出较小的时间复杂度的同时,牺牲了聚类的质量,得到的往往并不是最理想的聚类结果,尤其是在簇边缘可能出现数据点聚类不准现象。本文提出了一种将网格化空间中位于簇边缘的网格进行精度进一步细化处理的算法,将这些边缘网格中的这些不确定的点重新

一种基于网格和密度的簇边缘精度增强聚类算法

张宁，单世民，江贺，张宪超

大连理工大学软件学院，辽宁大连 （116621）

E-mail：

摘 要：现有的基于网格聚类算法在付出较小的时间复杂度的同时，牺牲了聚类的质量，得到的往往并不是最理想的聚类结果，尤其是在簇边缘可能出现数据点聚类不准现象。本文提出了一种将网格化空间中位于簇边缘的网格进行精度进一步细化处理的算法，将这些边缘网格中的这些不确定的点重新恢复他们的固有信息，再利用相似度函数将他们分配到合适的簇中。在空间数据集上实验数据表明，这种簇边缘精度增强聚类算法可在O(n)时间内得到优于CLIQUE算法的聚类结果。

关键词：数据聚类，基于网格，基于密度，混合算法

文献标识码：A 中图分类号：TP18

1 引言

聚类（clustering）是将数据集划分为若干个类，使得相同类中的数据具有较高相似度，而不同类中的数据具有较高相异度的过程[9]，广泛应用于地理、医学、化学、商业等领域中

[14]。现有的经典聚类算法可分为[13]：基于划分的方法，如k-means[1]；基于层次的方法，如CHAMELEON[8]、CURE[6]、BIRCH[2]；基于密度的方法，如DBCSCAN[3]、DENCLUE[7]和基于网格的方法，如STING[4]、CLIQUE[5]等。基于网格和密度的方法由于其对数据输入顺序不敏感，适于增量处理数据，能发现任意形状聚类等特点引起了众多研究人员的注意。

基于密度的聚类方法认为，簇（cluster）是那些被低密度区域隔离开来的高密度区域[3]。这种方法可以很好地处理形状不规则的聚类，并可以排除噪声的干扰，得到较高质量的聚类结果。但是，由于这种方法需要计算每个点与其他点的距离，因此时间代价较高，达到了O(n2)，不适于处理大规模数据集。DBSCAN虽然使用R*树来降低时间复杂度到O(nlogn)，但是建立R*树结构本身也耗费资源。基于网格的方法将数据空间划分为若干互不相交的网格单元（cell），以网格单元为单位进行聚类过程而不是单个数据点。基于网格的典型算法是CLIQUE，它首先根据密度阈值发现一些小的簇，然后将相连的簇合并成较大的簇。由于CLIQUE没有考虑到数据的分布情况，因而会导致聚类质量的降低。MAFIA[14]是一种CLIQUE的改进算法，它使用一种适应性网格的方法，根据数据集的数据分布找到网格的最佳化分方法。不过这种方法依然存在划不准现象，同一网格中的点仍然有可能处于不同的簇中。网格方法的时间复杂度为线性的O(n)，对数据集有很好的扩展性。不过，用对网格的计算取代了对点的计算，在换取速度的同时丢失了大部分点的信息，导致聚类质量有所下降。如图1所示，（左）图中A2和C2的数据点很可能被当作噪声来处理，而（右）图中两个簇的边缘网格B2的存在很可能误将两个簇当作一个簇来看待。

图1 边缘聚类不准现象