基于网格和最近邻居的聚类算法

摘 要：针对目前已有的聚类算法不能很好地处理包含不同密度的簇数据，或者不能很好地区分相邻的密度相差不大的簇的问题，提出1种新的基于严格最近邻居和共享最近邻居的聚类算法. 通过构造共享严格最近邻图，使样本点在密度一致的区域保持连接，而在密度不同的相邻区域断开连接，并尽可能去除噪声点和孤立点. 该算法可以处理包含有不同密度的簇数据，而且在处理高维数据时具有较低的时间复杂度. 实验结果证明，该算法能有效找出不同大小、形状和密度的聚类.

关键词：聚类算法；相似度；密度；网格；最近邻居

中图分类号：TP301.6 文献标志码：A

Clustering algorithm based on grid and nearest neighbors

CHEN Yiru，SUN Guangzhong，XU Yinlong

(Anhui Province-MOST Key Co-Lab of High Performance Computing and its Application，

Univ. of Sci. & Tech. of China，Hefei 230027，China)

Abstract：Due to the fact that the current clustering algorithms can not perform well while processing clustering datasets which contain clusters with different densities or distinguishing adjacent clusters with similar densities，a new clustering algorithm is proposed based on strict nearest neighbors and shared nearest neighbors. The algorithm keeps the links in regions of uniform density and breaks the links in regions of different density and removes the noises and isolated points by constructing the shared strict nearest neighbor graph. It processes datasets containing clusters with different densities and has low time complexity while dealing with high dimensional data. The experiment results prove that the algorithm can efficiently find clusters with differing shapes，sizes and densities.

Key words：clustering algorithm；similarity；density；grid；nearest neighbor

0 引 言

聚类是将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高相似度，而不同簇中的对象差别较大.聚类分析是数据挖掘重要的研究领域之一，针对聚类已提出许多有效的算法，如K-means[1]，STING[2]，DBSCAN[3]和Chameleon[4]等都从不同的角度对大规模、高维数据库进行分析，但各有优势和不足.

如何找出不同大小、形状和密度的聚类，并且处理好噪音和孤立点，确定聚类的个数，这些仍然是目前面临的挑战.我们发现，现有的聚类算法在处理的数据集中存在以下几个问题：(1)包含有不同密度的簇；(2)包含有相连着密度相差不太大的簇；(3)包含有大量的高维数据.

具有上述特点的问题广泛存在.例如：在生物学上，通过基因分类获得对种群固有结构的认识，而基因的特征数据经常具有不同的密度；在市场分析上，用购买模式刻画不同客户群的特征，而客户基本库中相近的客户群经常具有相差不大的密度；在地球观测数据库中，则通常是大量的高维数据.[5]

本文提出1个新的基于严格和共享最近邻的聚类算法，能够较好地解决上述问题.算法通过构造共享严格最近邻图，使样本点在密度一致的区域保持连通，而在密度不同的相邻区域则断开连接.基于共享严格最近邻的相似度反映数据空间内局部样本点的构造情况，对密度的变化和空间维度都不太敏感，具有较好的健壮性.算法还借鉴网格的思想，对高维数据的时间复杂度不高.

1 相关工作

聚类分析在统计学、机器学习和数据库等领域得到广泛研究和应用.目前，主要的聚类算法可分为基于划分的算法、基于网格的算法、基于层次的算法和基于密度的算法.代表性的算法有K-means算法、STING算法、Chameleon算法和 DBSCAN算法.

K-means是基于划分的算法，是最普遍使用的聚类算法之一.该算法只有在簇的平均值被定义的情况下才能使用，不适合发现非凸面形状的或者大小差别很大的簇，并且对噪声和孤立点数据敏感.

STING是基于网格的多分辨率聚类算法.算法将空间区域划分为矩形单元，形成1个层次结构，许多高层单元被划分为第1层的单元，单元中存储着预先计算的统计信息.STING算法的优点是效率高，并且可以处理高维数据；缺点是聚类的质量取决于网格的粒度，而且用网格内的统计信息代替该网格内的所有点，聚类的边界是直线，聚类质量较低.算法的时间复杂度是O(n).

Chameleon是利用动态模型的层次聚类算法.其基本思想是，通过1个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用1个凝聚的层次聚类算法通过反复合并子类来找到真正的结果簇.Chameleon算法的优点是不依赖于1个静态模型，能够自动适应被合并的簇的内部特征；缺点是在分类时算法过于复杂，对所有样本点计算距离以寻找每个点的最近k个点，还有在每次判断子类的相似度时都要做最小连接二等分.算法对高维数据需要O(n2)的时间.通过分析还会发现，Chameleon算法把类从相连的密度相差不大的簇中区分出来的能力不强，只有在分开着的类间噪音较少、连着的类密度相差较大时才能够区分.在类间密度相差不是太大的情况下，算法很难作出正确的聚类.

DBSCAN是基于密度的聚类算法，将高密度的连接区域划分为簇.其基本思想是，对聚类中的每个对象，在其给定半径的邻域中包含的对象不能少于某个给定的最小数目，然后对具有密度连接特性的对象进行聚类.DBSCAN算法的优点是可以挖掘任意形状的聚类，对数据输入顺序不敏感，还具有处理异常数据的能力；缺点首先是对用户输入的参数十分敏感，其次是在没有采用空间索引的情况下，时间复杂度达到O(n2).

而且，DBSCAN算法不能处理包含有不同密度的簇的数据，因为它基于核心点的密度定义不能区别不同密度的簇的核心点.如图1所示，如果通过制定半径定义1个点的邻居，然后看核心点在给定的半径内是否有足够数目的邻居；那么要么左边较密的点被聚为1个簇而右边的被标记为噪音，要么所有点都被聚为1个单个的簇.这都是不合理的结果.

图 1 基于核心点密度定义的邻域

因此，需要设计1个聚类算法，能处理包含有不同密度的簇数据，并且在相连着的类密度相差不是太大的情况下也能作出正确的聚类.而且，还应该具有更健壮的相似度标准，以适应高维数据的处理.算法本身不应过于复杂，时间复杂度不能太高.我们发现，基于严格最近邻的思想，并参考JARVIS等[6]提出的共享最近邻概念，可以解决该问题.本文基于点的SKNN(Shared Strict K-Nearest Neighbors)定义1种新的相似度标准，并设计出合适的聚类算法.

2 SKNN算法

SKNN算法能较好地处理包含有不同密度的簇或者相连着的密度相差不太大的簇的数据集.算法的基本思想是，通过构造共享严格最近邻图，使样本点在密度一致的区域保持连通，在密度不同的相邻区域则断开连接，并尽可能去除噪声点和孤立点.基于共享严格最近邻的相似度则反映数据空间内局部样本点的构造情况，对密度的变化和空间维度都不太敏感，具有较好的健壮性.

算法分为3个阶段：第1阶段是找出每个点的严格K-最近邻集；第2阶段是计算点之间的相似度，构造共享严格最近邻图和计算点的密度；第3阶段是生成相应的簇.其中，第1阶段的最近邻集搜索部分对SKNN算法的运行时间影响较大.在这一部分，借鉴STING方法中网格的思想提出 K*-最近邻集搜索算法，可以有效提高SKNN算法的效率.

2.1 相似度和密度

定义1 给定序列X={xi}(i=1，2，…，n)，若x∈X，点x的K-最近邻集(K-Nearest Neighbors) 为{y| y是x的k个最近点之一，y∈X}，记为 KNN(x).

这里常用的是欧氏距离，也可以是其他距离.

定义2 对于x∈X，其严格K-最近邻集(Strict K-Nearest Neighbors)为{y|y∈KNN(x)，x∈KNN(y)}.

定义3 对于X中任意的两个点x和y，它们之间的连接度为

Link(x，y)=1，while x∈SKNN(y).

关于点的SKNN有以下性质：

性质1 SKNN(x)KNN(x)；

性质2 如果x∈SKNN(y)，那么y∈ SKNN(x)；

性质3 Link(x，y)=Link(y，x).

定义4 对于X中任意的两个点x和y，它们之间的相似度为

Similarity(x，y)=size (SKNN(x)∩SKNN(y))，

while Link(x，y)=1.

共享严格最近邻图是由相似矩阵构建成的.2个点x和y，如果互相都在对方的K-最近邻集中，那么它们之间产生1条边.在SKNN图中这条边的权重为这2个点所共享的严格近邻的个数.由此可以得到点x和y的相似度定义.在这里，如果给定1个相似度阈值，就可以通过移除低于这个阈值的边，然后把所有的连通片作为1个簇来产生聚类.

SKNN相似度反映数据空间内局部样本点的构造情况，对密度的变化和空间维度相对都不太敏感.SKNN相似度健壮性好，能很好地处理高维数据.

定义5 对于任意一点x，其密度为

Density(x)=∑Similarity(x，y)，其中y∈ SKNN(x).

可以采用SKNN相似度、严格K-最近邻的度量方法进行密度度量.如果某个样本点的第k个最近邻居与它本身很近，就意味着有较高的SKNN相似度，也可断定该点处于高密度区域内，因此可以作为新密度的度量.定义1个点的密度为它与严格K-最近邻的相似度之和.该方法能很好地反映这个点与其他点的连接情况.

2.2 严格近邻的特性

下面以2维点集为例，说明严格近邻的两个重要特性(见图2).

(a)

(b)

图 2 严格近邻的特性

在图2(a)中，每个点都与4-最近邻之间构造了边.图2(b)则是严格4-近邻图.在这幅图中，只有当点x和y，互为4-最近邻时，它们之间才有1条边.从这幅图中可以看到2个特性.首先，噪声点和孤立点被尽可能地去除.例如右下角的这个点已经不再与任何点相连，因为它不是其他点的严格最近邻.通过这样的方法，可以避免噪声点和孤立点的干扰.然后，在具有一致密度的区域保持连通性，而在密度不同的相邻区域则断开连接.这个特性，使得我们可以处理具有不同密度的簇的数据集，并且可以区分出相连着的不同密度的类.

2.3 K*-最近邻集搜索

在搜索某点的最近邻居时，为了避免比较其余所有点之间的距离，提出K*-最近邻集搜索算法，其目标是快速找到每一点的K*-最近邻集.算法只需计算每一点到它们的δ邻域附近的点之间的距离，然后通过比较得到距其最近的k*个点.

空间数据在局部随机分布，因此可以采用对象所在网格的矩形区域面积代替点的圆形邻域面积.借鉴STING[2]算法中网格的思想，提出基于网格的K*-最近邻集搜索算法.以2维空间为例进行说明：将n维数据空间划分为互不相交的长方形单元.对每个点，只需在它所在的网格内寻找其K*-最近邻.但这样做也存在缺点.如图3所示，在中间网格中的左下角那个点，其 4-近邻是那几个带叉形标记的点.但实际上，其4-近邻应该是那几个不带叉形标记的点.因此，采用如下方法：对1个点，把它所在的网格以及周围1圈的8个网格作为该点的参考区域.对中间网格中的点，图中的这9个网格就是其参考区域.对每个点，我们在其参考区域内搜索其K*-最近邻.

图 3 网格的划分及参考区域

不过在有些情况下，用户并不能1次就确定好合适的网格大小，需要反复试验才能成功.为了避免多次调用算法，可以采用这样的方法：对于1个点，如果不能找到它K*-最近邻集，就将其参考区域扩大，例如从开始的32=9个网格扩大到52=25个网格.这样的算法就可以1次把所有点的K*-最近邻集全部快速找出.这个算法的时间复杂度为 O(n2/g)，其中g为生成网格的数量.对于高维数据，算法具有近似线性的复杂度.

2.4 SKNN聚类算法的描述

首先说明点的数据结构：点的位置Xs和Ys，所属网格单元GridId，参考区域内点的集合Ps，K*-最近邻集Neighbors，K-严格最近邻集SKNN，点的密度Density.共享严格最近邻居图是无向图，图中边的权重就是这2个顶点的相似度.

算法的执行流程如下：

(1)调用第2.3节中基于网格的K*-最近邻集搜索算法，找出每个点的K*-最近邻集.

(2)用严格近邻的稀疏方法，找出每个点的严格K-最近邻集.

(3)基于该样本集，计算每个点与其严格K-近邻的相似度，构建相似度矩阵.

(4)用上述相似度矩阵构造共享严格最近邻居图.2个顶点间存在1条边，意味着这2个顶点互为K-最近邻，而边的权重就是这2个顶点的相似度.

(5)对图中的每个样本点计算其连接密度.1个点的密度是它与K-严格最近邻的相似度之和.

(6)将低密度值的点从样本点集中删去，将高密度值的样本点确定为代表点.

(7)根据此时的共享严格最近邻居图和确定的代表点进行聚类.通过移除低于阈值的边，把所有的连通片作为1个簇来产生聚类.

(8)将所有既非噪音点也非代表点的那些点，赋给相应的簇.

2.5 算法的时间复杂度

输入集合中点的数目为n.采用基于网格的搜索算法，设生成网格数量为g，找出每个点的K*-最近邻集的时间复杂度为O(n2/g).对于高维数据，搜索算法具有近似线性的复杂度.把每个点的K*-最近邻集稀疏为严格K-近邻集，时间复杂度为O(n).构建相似度矩阵，因为对每个点只需要计算它与近邻的相似度，时间复杂度为O(n).计算每个点的密度并去除低密度点，时间复杂度也为O(n).根据此时的共享最近邻居图和确定的代表点进行聚类，也就是找出所有的连通片，时间复杂度为O(n).因此，算法对数据集点数n有近似线性的复杂度.

3 算法的实验结果

实验环境：Athlon 1 GHz的CPU，主存512 MB，操作系统Microsoft Windows XP.实验采用5个数据集，前2个是为了验证本算法的特性而生成的模拟数据，第3和第4个是在KARYPIS等提出Chameleon算法的论文[6]中采用的数据集.在生成的聚类结果中，不同簇中的数据用不同灰度的点表示.最后，用KDD Cup’99网络非法入侵数据验证算法在实际问题上的效果.

首先对包含不同密度的簇的数据集进行聚类.如图4，原始数据集中有3 000个点，包含密度比为10∶1的数据，还存在一些噪音.结果见图4，可以得到很好的聚类效果.

图 4 不同密度的簇

然后对如图5的数据组进行聚类，簇之间相连，并且密度相差不大.在密度接近时，算法仍然可以得到很好的效果.图5是密度为3∶1时的聚类结果.

图 5 密度相差不大的相连的簇

从这两个实验可以看出，算法能够有效地处理包含有不同密度的簇的数据，并且能够很好地区分相连着的类密度相差不是太大的簇，解决了之前面临的问题.

下面对两组复杂数据进行聚类，见图6和7.

图 6 Chameleon数据集3

图 7 Chameleon数据集4

在这两组数据中，分别包含有8 000和10 000个点，包含不同的密度、形状和大小的类，并且还充斥若干噪音点在类之间.聚类结果见图8和9，每种色块代表1个结果簇.

图 8 对Chameleon数据集3的聚类结果

图 9 对Chameleon数据集4的聚类结果

从图8和9可以看到，算法正确地找到图6和7中的聚类.即使在一些聚类的边缘，受到密度分布不均及噪音的影响，算法也不会错误地合并聚类.从试验结果看，SKNN算法能较好地发现不同大小、形状和密度的聚类，同时较好地清除噪音.在这个实验中，k∈[15，30]算法都有较准确的结果，因此可以断定该算法对参数不敏感.

为检验聚类算法在实际问题上的效果，对10%的KDD Cup’99网络非法入侵数据进行聚类实验.该实验数据分为有标签的数据和未标签的数据，有标签的数据标签有多种，可将其分为正常和异常两大类.实验的任务是通过对已经标签数据的分析判断未标签数据属于正常还是异常.所有的数据都具有相同的属性，比如访问方式就是其中的1个属性，它的取值可以是HTTP和FTP等.因为数据量较大(494 021条)，只对前50 000条数据随机抽取 10 000条进行聚类.共进行3次这样的聚类和归类.对相同的数据还用K-means方法进行聚类，其中k为20.

在聚类之前标准化所有数量型属性，对字符型属性则认为取相同值时距离为0，否则为1.用欧氏距离计算两点间的距离，对于聚类的每个结果类，将其归为成员数最多的集，把标志为normal的类归为正常类，而将其他类归为非正常类.

在评估结果时采用两个指标[7]：1个是错误预警比率FA，在正常情况下系统产生预警；另一个是攻击被拦截的比率DR：系统对攻击产生预警.结果见表1和2.其中表1是未标签数据基于SKNN算法对应的结果，表2则是对应于K-means算法的结果，AV和ST分别是结果数据组的平均值和标准差.结果显示SKNN算法能够得到正确的聚类，并且在两个指标上都优于K-means算法.

4 结 论

基于严格最近邻和共享最近邻的思想，提出1种新的相似度标准，并设计出合适的聚类算法.该算法能够有效处理包含有不同密度的簇的数据，并且能够很好地区分相连着的类密度相差不是太大的簇.处理过程中，该算法借鉴网格的思想，有较好的时间复杂度.今后将研究算法参数设置对算法的影响，并验证本算法对余弦距离和Jaccard距离的适用性.随着并行计算成为处理大规模数据的重要技术手段之一，在下一步的工作中，还将研究并行的数据挖掘算法.

参考文献：

[1] JAIN A K，DUBES R C. Algorithms for clustering data[M]. Englewood Cliffs，New Jersey，USA：Prentice Hall，1988.

[2] WANG Wei，YANG Jiong，MUNTZ R. STING：a statistical information grid approach to spatial data mining[C]// Proc 1997 Int Conf on Very Large Data Bases (VLDB’97). Athens，Greece，1997：186-195.

[3] ESTER M，KRIEGEL H P，SANDER J，et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]// Proc 2nd Int Conf on Knowledge Discovery & Data Mining. Portland，1996：226-231.

[4] KARYPIS G，HAN E H，KUMAR V. Chameleon：a hierarchical clustering algorithm using dynamic modeling[J]. IEEE Computer，1999，32(8)：68-75.

[5] HAN Jiawei，KAMBER M. Data mining concepts and techniques[M]. San Francisco，USA：Morgan Kaufmann Publishers，2001.

[6] JARVIS R A，PATRICK E A. Clustering using a similarity measure based on shared nearest neighbors[J]. IEEE Trans on Computers ：C，1973，22 (11)：1 025-1 034.

[7] GOMEZ J，DASGUPTA D，NASRAOUI O. A new gravitational clustering algorithm[C]// Proc Third SIAM Int Conf on Data Mining. San Francisco，USA，2003.