龙超奇，蒋 瑜，谢 雨

（成都信息工程大学软件工程学院，成都 610225）

0 引言

小波聚类（WaveCluster）算法［1］是一种基于网格的聚类算法。该算法从多维信号处理的角度出发，能够有效地处理大数据集，发现任意形状的簇，不容易受到噪声的影响。这些优点使得小波聚类算法被广泛地应用于数据处理。

目前，国内外在小波聚类算法的应用上取得了较大的进展。文献［2］将小波聚类应用于数据约简，根据小波聚类结果抽选出不等数量的数据作为数据约简后的结果，能够很好地描述大致的数据分布情况；文献［3］将小波聚类应用于本科招生生源分析，分析结果对高校管理招生工作起到了科学指导和辅助决策作用；文献［4］将小波聚类应用于入侵检测系统，提高了入侵检测的检测率并降低了误报率；文献［5］从时空角度出发，将小波聚类算法应用于交通事故分析中，具体地分析了造成交通事故的主要原因，对预防交通事故有参考价值；文献［6］使用一维卷积神经网络和小波聚类分析方法检测和诊断传感器控制回路中的故障，提高了故障检测的准确性，并且在噪声下也具有良好的诊断效果。

同其他基于网格聚类的算法相同，小波聚类也同样会面临可塑性面积单元问题（Modifiable Area Unit Problem，MAUP），即依据不同网格划分尺度会有不同的聚类分析结果。过于细密的网格会使得簇内元素距离太远，造成同一簇元素被分割为多个簇的情况；而较为粗疏的网格会使簇间距离缩短，无法清晰地分割不同的簇。针对这个问题，文献［7］提出利用广度优先搜索（Breadth-First-Search，BFS）的方法判断连通区域，以广度优先搜索邻居聚类算法中控制类形状的类门限参数λ去弥补相连定义类划分不精确的问题，改善小波聚类的聚类精度及速度；文献［8］提出一种基于双网格校正小波聚类算法，通过校正算法利用校正网格的聚类结果对原始网格的结果进行校正，降低了网格划分和网格密度阈值对聚类质量的影响，为MAUP 提供了一种解决思路；文献［9］使用并行小波算法，通过使用不同尺度级别的小波变换，在并行处理的条件下扩展了聚类速度和规模，同时还克服了小波聚类中过大的空间复杂度的约束条件；文献［10］聚焦于网格边缘，运用partition and judge the gridCij算法［11］寻找簇与簇的边界，利用K-Means 算法划分边界，进一步细化了边界网格，在区分了簇与簇的边缘的问题上取得了较好的成果。

但上述算法均并没有从聚类精度与网格划分尺度的大小方向讨论MAUP，本文通过研究划分网格的粒度粗细对聚类精度影响，并提出了一种基于峰值网格的连通区域检测算法。实验结果表明改进后的算法能够在较低的网格粒度下得到较好的聚类结果。

1 基础概念

由于小波聚类算法是基于网格进行的聚类算法，需要将原始数据映射到网格空间中。

定义1对d维特征空间P=A1×A2× …×Ad，将特征空间中每一维Ai(i={1，2，…，d})分割为数量为m的网格。即把原数据中的每一个维度以固定步长分割为共计md个网格构成新的网格空间Pgrid，m为网格划分的尺度。

对于特征空间P中的任一元素{α1，α2，…，αn}，其在网格空间中的描述为{β1，β2，…，βn}，β的值为：

小波聚类算法采用离散小波变换，变换流程如图1 所示。图1 中：a[n]代表原始数据；g[n]和h[n]分别为小波基的低通滤波器和高通滤波器；↓2 表示对经滤波器变换后的数据进行下二元采样［12］。网格空间Pgrid经小波变换后取其低频区域a1，g[n]构成新的网格空间Pwave。a[n]到a1，g[n]的变换［1］如下：

由式（2）可知，网格空间进行小波变换后的网格空间Pwave中总网格数为：

其中：L为小波基的滤波器长度，即式（2）中g[n]的长度。滤波器长度L根据不同的小波基有不同的取值，本文选取的小波基为Daubechies 小波，其滤波器长度为2N，N为小波基的系数。

图1 一阶离散小波变换流程Fig.1 First-order discrete wavelet transform process

小波聚类中，对于低密度网格的判别主要依靠密度阈值作为主要判别依据，并根据高密度网格建立连通区域。

定义2设网格密度阈值为t。对于任意的变换后网格，若网格的值大于t，则视为稠密网格；否则为稀疏网格。

定义3在空间Pwave中，若网格a可以通过若干个稠密网格到达网格b，则称a与b互为可达网格。对于网格空间中某一区域的所有网格，若其中的网格均互为可达网格，则视该区域为连通区域。

算法1给出了传统小波聚类算法的算法步骤［13］。

算法1 小波聚类算法。

输入dt数据，m网格数目，t密度阈值，wavelet小波基。

输出cluster_result聚类结果。

1）构造大小为md的网格空间，将数据映射到网格空间中。

2）以wavelet作为小波基进行小波变换，得到变换后的网格空间Pwave。

3）遍历Pwave中的网格，检查其中的连通区域，Pwave中网格密度低于t的记为稀疏网格。

4）标记不同的连通区域为不同的簇类。

5）建立数据与小波变换后网格空间的查找表，将Pwave中的簇类记录到cluster_result中。

6）输出cluster_result。

2 算法改进

2.1 网格尺度分析

网格空间Pgrid经离散小波变换产生的网格空间Pwave中以数值形式反映网格间关系。由式（2）可知，离散小波变换过程中，能量会向具有更高密度的网格汇聚，变换后网格的数值是由其身周共计x个网格共同决定的。其中x的值为：

由式（3）和式（4）可知，选择的小波基的滤波器长度L决定了网格空间中划分尺度的最低大小。若滤波器长度大于网格划分尺度，则采样频率太低，小波变换的意义不明显。在变换后的网格空间Pwave中，聚类中心总是属于数值较大的网格。

图2 展示了两个簇间距离较小的簇类在小波变换之前的分布情况。

图2 两个不同的簇类Fig.2 Two different clusters

图2 为两个不同的簇在网格空间中的划分情况（网格划分为6×6 的网格），它们的边缘区域位于x∈(0.125，0.25)，y∈(0.25，0.375) 中。图3 展示了此网格空间经由算法1（t=0，稀疏网格记为X）在网格划分尺度分别为6 和10 时的聚类过程。

图3 中：图3（a）和（b）展示了不同网格密度下经算法1 中的步骤2）和步骤4）处理的结果，图3（c）和（d）分别为经图3（a）和（b）中描述的过程再经由步骤5）映射之后的聚类结果，图中簇2包含的数据点为小波聚类中所判定的离群点。

从图3 中可以发现，较低网格密度下，虽然产生的小波变换矩阵较小且算法的消耗较低，但密集的变换矩阵导致只划分出了一个有效的聚类；虽然图3（d）中通过提高网格尺度产生了两个有效聚类，但由于高网格尺度下的元素相对分散稀疏网格增多，从而产生了较多的离群点，导致算法只能大致地划分数据中不同的簇类，并且较大的网格划分尺度也会增加算法的时间及空间消耗。

对比图2及图3（a）和（b）可知，小波变换后的网格数值反映了原数据中高密度的区域和低密度区域的分布。在高密度的区域内其网格数值较大，而低密度区域和边缘区域的网格数值往往远小于高密度区域。然而从图3 中可以发现，小波聚类算法对经小波变换后的网格数值并没有很好地运用起来，仅通过密度阈值对其进行了分割处理。

基于上述情况，在原小波聚类连通检测方法的基础上，本文提出了使用高密度网格建立连通区域的方法，以改善较低网格密度下小波聚类算法的聚类效果。

图3 不同网格划分尺度的聚类过程Fig.3 Clustering processes of different grid division scales

2.2 基于峰值网格的连通区域检测

定义4对小波变换后的网格空间Pwave中任意网格Cw，若Cw中值大于周围x个数据点，则视Cw为峰值网格，Cw及其周围x个网格相连所构成的区域称为峰值连通区域。

如果有若干个峰值连通区域重合，则视整个连通区域为其中最大的峰值网格形成的极大峰值连通区域。

经小波变换的网格空间Pwave中可以获得若干个峰值网格，在判断峰值连通区域时可以使用广度优先搜索算法检测连通区域并处理连通区域的边缘网格。

若某网格Ca处于Cw所属极大峰值连通区域的边缘并且其邻近非该连通区域网格Cb满足如下关系，则将Cb加入该极大峰值连通区域中。

其中：θ为极大峰值连通区域波动系数，θ∈(0，1)，它决定了该连通区域的最大扩散程度。

因此，利用峰值网格建立连通区域的算法如算法2所示。

算法2 峰值网格连通检测算法。

输入dt数据，m网格数目，wavelet小波基，θ波动系数。

输出cluster_result聚类结果。

1）同算法1 中1）、2）两步，得到经小波变换后的网格空间Pwave。

2）对小波变换后的网格数据快速排序。

3）从下标0开始选取Pwave中未被标记的网格并入队。

4）队列队头元素出队并标记其为新的簇类。

5）通过广度优先搜索遍历与该出队元素相邻的所有网格，若其中某一网格的值满足式（5），将该网格入队并标记该网格属于当前极大峰值区域对应的簇。

6）重复步骤4）直到队列为空。

7）重复步骤3）直到Pwave中所有网格均被标记。

8）建立原数据与小波变换后数据之间的查找表，将Pwave中的簇类记录到cluster_result中。

9）输出cluster_result。

对图2 中的数据使用算法2，可以在较低网格划分尺度（m=6）下得到较好的聚类结果，如图4所示。

图4 算法2聚类结果Fig.4 Clustering results by algorithm 2

相对于算法1，在同样低网格尺度下，算法2 利用高密度区域的网格，能够更快地根据聚类中心寻找连通区域，同时还能分割处理较低网格划分尺度下不同的簇类，所取得的聚类结果更好。

2.3 时间复杂度分析

设小波聚类的网格空间为k=md，在算法中，读取数据集并映射到特征空间其时间复杂度为O（n），小波变换的时间复杂度最多为在划分合理的情况下，小波变换的网格空间k≪n，则小波变换的时间复杂度应小于O（n）。与传统小波聚类算法对比，本文算法对网格进行排序并使用广度优先搜索区分簇类的时间复杂度为O（k2），大于传统小波聚类算法O（k），建立查找表的时间复杂度为O（k）。则总计时间复杂度为：

在n≫k的情况下，本文算法的时间复杂度量级为O（n），与传统小波聚类算法的时间复杂度量级相同。虽然本文算法在计算连通区域时的时间复杂度大于原小波聚类算法，但本文算法能以更低的网格划分尺度进行聚类，所以时间性能上略优于传统小波聚类算法。

相较于算法1 中以连通区域划分簇的方式，以网格峰值为序的连通检测机制能够在低精度网格下有效地区分网格空间Pwave中的聚类边缘。

3 实验与结果分析

3.1 实验使用的数据集及参数

本文使用了人工数据集和UCI数据集分析本文算法相对于传统小波聚类算法以及现有的聚类算法的改进程度。其中，人工数据集主要用于测试本文算法在不同形状的数据集以及网格尺度方面的优化程度，UCI 数据集用于考察本文算法相对于其他聚类算法的优势和劣势。本文实验基于Windows10操作系统，使用的编译语言为Python 3.6.5。

使用的数据集如表1～2 所示，DS 系列数据集是由scikitlearn 库生成的凸数据集，对于数据集中的每个簇类，设定其簇间距离总是大于簇内距离，该数据集用于测试本文算法对于传统小波聚类算法在网格划分尺度的优化程度；sym、Aggregation、Zigzag和Ring数据集为具有特定形状的人工数据集：Zigzag 和Ring 是使用Matlab 生成的之字形及环形数据集，sym 和Aggregation 数据集为包含不同形状的具有不等的簇间距离的综合数据集，这四种数据集主要用于测试算法对簇间距离不等的特定形状数据聚类的效果。为方便对比，所有小波聚类算法均使用Daubechies小波（系数为2）。

表1 人工数据集Tab.1 Synthetic datasets

表2 UCI数据集Tab.2 UCI datasets

本文实验采用外部指标归一化互信息（Normalized Mutual Information，NMI）和内部指标CH（Calinski-Harabaz score）作为聚类效果评估参数。

NMI 常用在聚类中度量两个聚类结果的相近程度，是重要的外部衡量指标，可以比较客观地评价出当前簇类划分与标准划分之间相比的准确度。NMI的值域是0 到1，越高代表划分得越准。

CH 指标通过计算类中各点与类中心的距离平方和来度量类内的紧密程度，通过计算各类中心点距离平方和来度量数据集的分离度，CH 指标由分离度与紧密度的比值得到。CH 指标越大代表着类中元素越紧密，类与类之间越分散，且CH指标只受到数据自身分布的影响，有利于分析不同聚类簇数下的聚类效果。

不同的网格密度会产生不同的聚类结果，由第2 章可知，网格划分越紧密，网格空间中存有数据的网格越少。为了评价数据进网格划分后的密集程度，本文使用空间密度q表示了经过网格排列后数据的紧密程度，公式如下：

其中：Ngrid为数据映射到网格空间Pgrid中的非空网格个数；N为原始数据样本个数。

由网格划分的概念可知，对于任意的聚类数据集，其网格划分尺度m及密度q之间的大致关系如图5所示。

在网格空间中，空间密度q与网格划分尺度m呈正相关。随着网格划分尺度m的增长，空间密度q的递增速度会随着聚类分布逐步改变。当q的增长速度放缓时，则说明数据中的聚类程度通过网格空间已经难以划分，此时再增大网格划分尺度对于改善聚类的效果甚微。

基于以上分析，由于小波聚类算法时间密度与网格划分尺度关联紧密，为了避免网格划分尺度过大从而使得聚类效率低下，设定空间密度q＜0.9 为网格划分尺度的取值范围，同时根据式（4）给出的分析调整其最低划分尺度。即

式（7）限定了网格划分尺度m的取值范围，以下实验也将基于此范围展开。

图5 m-q曲线图Fig.5 m-q curve

3.2 网格优化分析

使用表1中的数据集，将本文提出的改进算法与算法1中的小波聚类算法比较，考察最优聚类效果下网格划分尺度的差异。

图6 为两种算法在式（7）给定的网格划分范围内对前四个数据集的聚类情况对比，采用NMI指标作为衡量标准，以散点图的形式记录其分布情况。由图6 可以看出，本文算法能够在较低的网格密度下形成效果较好的聚类，且总体的NMI指数仍大于原传统小波聚类算法。但由于算法本身聚类数目并不固定，可能会由聚类簇数的不同从而使结果偏差。因此，在图6 的实验基础上辅以CH 指标对比分析小波聚类算法和本文算法在数据及上的最优聚类效果。

图6 两种算法在DS数据集上的聚类情况Fig.6 Clustering situations of two algorithms on DS datasets

表3 分别选取了两种聚类算法中CH 指标较高且聚类数接近原始数据聚类数的聚类结果进行对比，考察两种算法在最优聚类效果下网格划分尺度的差异。

表3 不同算法在DS数据集上的聚类结果Tab.3 Clustering results of different algorithms on DS datasets

结合表3 与图6 可知，本文算法在精度变化不大的情况下，相较于传统小波聚类算法减小了50%～60%的网格划分尺度；但由于本文算法在处理连通区域时消耗的时间要远大于传统小波聚类算法，所以时间性能上只提升了25%左右。

但本文算法在非密集型簇类时聚类性能与传统小波聚类算法差别不太明显。图7 展示了在均匀分布数据下本文算法与传统小波聚类算法的聚类对比。由于两种算法在ring 和Zigzag 数据集上聚类效果相同，所以这两个数据集中仅展示了本文算法的聚类结果。表4 给出了两种算法在这四种数据集上的网格划分尺度及聚类数。

图7 均匀分布数据上的聚类结果Fig.7 Clustering results on uniformly distributed data

表4 非凸数据集上的网格划分尺度Tab.4 Grid division scales on non-convex datasets

结合表4 与图7 可知，对于ring 和Zigzag 数据集，本文算法与传统小波聚类算法聚类性能差别不大，并且它们使用的网格划分尺度也基本相同；但在处理形如sym 与Aggregation这种簇间距离较小的数据集聚类时，本文算法相比传统小波聚类算法的网格划分尺度平均减小了25%，且能够分离出较为紧密的簇类。

综合上述实验结果，本文算法相对于传统小波聚类算法，对于聚类紧密的数据集效果提升十分明显，尤其是在凸数据集上的提升尤为显著。产生上述结果的原因主要是传统小波聚类算法在检测连通区域时，以连通为条件判定该区域元素所属簇类。这种检测方式能够快速地寻找到数据集中相互连通的网格，但在对簇间距离较小的数据集聚类时，较小的网格划分尺度不足以分隔不同的簇类，而较大的网格划分尺度又会使得原本同一簇类的元素被分为多个簇类。

相对于传统小波聚类算法，本文算法在连通区域的基础上，使用峰值网格作为连通区域的中心，并以峰值连通区域边缘的低密度网格为边界分隔密度差距较大的网格，从一定程度上改善了原算法对于紧密簇类的聚类效果，能够在低网格尺度下形成较为稳定的聚类。这也是本文算法对高密度区域集中的凸数据集的聚类效果更好的原因。

3.3 与其他算法在UCI数据集的聚类对比

将本文算法运用到分布更为复杂的真实数据集中，分析其聚类的效果并验证相对于传统小波聚类算法的提升。本次实验使用多种聚类算法［7，10，15-17］进行对比。

表5 为本次对比实验采取的真实数据集，数据均来自UCI。从表5可以看出，本文算法在时间性能上较传统小波聚类算法平均提升了14%，与文献［7］算法和文献［10］算法相比在聚类性能上有所提高。本文算法与文献［7］算法相比，在其广度优先搜索的基础上更进一步地使用峰值网格区域划分簇类边缘，对于使用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）和CLIQUE（CLustering In QUEst）算法难以分割的簇类同样能得到较好的结果。与文献［10］算法相比，本文算法在时间性能上也有所提高，其原因在于本文算法在簇边界划分上仅使用峰值网格作为参考，相较于使用K-Means 算法划分网格边界的方法所需求的计算量更小；但本文算法总体时间性能仍要弱于K-Means算法。

表5 多种聚类算法在UCI数据集上的性能对比Tab.5 Performance comparison of multiple clustering algorithms on UCI datasets

4 结语

本文通过研究小波聚类算法中网格划分精度和检测连通区域的相关算法，提出了一种基于峰值网格的连通检测算法用以改进低密度网格划分尺度下的小波聚类算法的聚类效果。算法将峰值网格依序排列，通过广度优先搜索算法检测连通区域并按照不同的峰值区域分割聚类边缘。在网格优化测试中能够以低于原传统小波聚类算法的网格划分尺度区分不同的簇类，同时在UCI 数据集的聚类问题上取得了较好的聚类结果。

但在针对聚类边缘不清晰的数据聚类时，本文算法与传统小波聚类算法聚类性能差别不大。对于小波聚类算法这种基于网格的聚类算法而言，如果不从网格内部解决聚类边缘问题，那么只能通过改变网格划分尺度来分离不同的簇类。本文算法对小波聚类算法的改进并没有深入到网格内部，在连通区域检测方式上的改进虽然从一定程度上改善了对聚类边缘紧密的数据的聚类效果，但对簇类区域互有交叉的聚类应用效果不好。如何通过调整网格内部的关系从而改善对边缘不清晰的聚类效果将是以后改进研究的重点方向。