噪声环境下复杂流形数据的势能层次聚类算法

于晓飞，葛洪伟

(1.江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡 214122；2. 江南大学 物联网工程学院，江苏 无锡 214122)

0 引 言

聚类分析作为一种无监督的学习方法，是数据挖掘中的一项重要任务，它按照一定的规则将数据划分成若干类，使相同类数据尽可能相似，不同类数据尽可能相异[1]。聚类分析既可以作为独立的数据挖掘工具来对数据进行分析，也可以作为其他数据挖掘算法的预处理过程，其在生物信息、信息检索、机器学习、人工智能等领域有着重要作用[2-3]。

目前聚类分析已经吸引了大量的研究目光，有许多经典的聚类算法被提出，如基于划分方法的K-means[4-5]，K-mediods[6]等，这些算法虽然简单快速，但聚类结果对初始类簇中心的选取有一定的依赖；基于层次的聚类方法如Cure[7]，Chameleon[8]等，这些算法虽可检测非球形簇，但算法过程相对复杂，在具体应用中都存在一定的局限性；基于密度的聚类方法如DBSCAN[9]，OPTICS[10]等，这些算法虽然可以发现任意形状的簇，但对于参数十分敏感；基于网格的聚类方法如STING[11]，WAVECLUSTER[12]等，这些聚类算法虽有较好的聚类效果，但处理时间与空间所划分单元数有关，一定程度上降低了聚类的质量和准确度。

Yonggang Lu等[13]提出一种基于势能的聚类(clustering by sorting potential values，CSPV) 算法，该算法虽提出了基于势能的相似性度量准则，但聚类效果完全依赖于对参数B的选取。针对这一问题，Yonggang Lu等[14]于2013年在《Pattern Recognition》上提出了一种基于势能的快速凝聚层次聚类(potential-based hierarchical agglomerative clustering，PHA)算法。该算法十分便捷高效，首先依据各点的势能和与父节点的距离构造边缘加权树，然后依据树中权值大小使用层次聚类得到最终的聚类结果。PHA算法使用全新的相似性度量准则，并与凝聚层次聚类相结合，在时间上更快速，在精度上可以得到更好的聚类效果。

PHA算法虽然具有上述优点，但该算法只能处理一些结构简单的、簇内势能大小分布明显不同的球形簇，无法处理一些复杂的流形结构簇，而且聚类结果易受到噪声数据的影响。针对这一缺陷，本文提出了噪声环境下复杂流形数据的势能层次聚类算法 (hierarchical clustering based on potential in complex flow data with noise，HCPC)。首先，根据势能递增曲线确定势能阈值，找到数据集中的噪声点；其次，在非噪声数据点上，定义出势能最大、最小2层数据，并基于势能的分布特点，提出分层聚类的方法，以确定类簇的大体框架；最后，在分层聚类结果的基础上，对正常点使用层次聚类，同时将噪声点聚到距离自身最近的类簇中去。实验表明，HCPC算法不仅可以识别噪声点，而且能有效地处理复杂的流形数据集，同时在真实数据集上具有更优的聚类效果。

1 PHA算法及其缺陷分析

1.1 PHA算法

PHA算法[14]认为，数据点的势能大小与其概率密度分布是密切相关的。该算法首先根据重力势能的物理意义来计算每个数据的势能。其中，每2点之间的势能Φij定义为

(1)

(1)式中：rij是点i与点j之间的欧式距离；δ用来避免分母为零的情况出现。δ的计算方式为

(2)

δ=mean(MinDi)/S

(3)

(2)—(3)式中：MinDi是点i到其他各点的最短距离；N是数据点的个数；S是一个尺度因子[14]，一般设为10。

计算了每2点之间的势能Φij后，每个点的势能Φi定义为

(4)

文献[14]中使用Parzen窗口函数[15]这一非参数估计方法来证明势能和概率密度分布的关系。在Parzen窗口函数中概率密度的定义为

(5)

(5)式中，N表示数据点总数。

文献[14]经过证明得到

(6)

即势能和概率密度函数成反比，其中，α是归一化因子，它的主要作用是确保窗口函数在所有特征空间上的积分为1。因此，势能可以反映数据点的分布情况，如势能越小的点的周围数据点分布越密集。

将势能从小到大排序，并以势能最小的点作为根节点，构造边缘加权树，其他数据点寻找自身的父节点。其中，父节点定义为

(7)

即势能小于点i且与i距离最近的点为其父节点。

点i到父节点parent[i]的距离ρi为

ρi=ri,parent[i]

(8)

在边缘加权树中，每个数据点与父节点之间的权值为两者的距离。在树构造完成后，使用凝聚层次聚类算法进行聚类，得到聚类结果。

1.2 PHA算法缺陷分析

PHA算法虽然十分便捷快速，但其只能处理一些簇内势能分布明显不均匀的数据集如图1所示。然而，针对一些复杂的流形数据集，PHA算法无法得到理想的聚类结果。

图1 DS1数据集Fig.1 DS1 data set

其原因在于一些复杂的数据集簇内势能分布较均匀，无明显差异，缺陷分析示例如图2所示。图2a中，该数据集中2个环形簇的簇内势能分布相对均匀，且中间的团状簇势能整体偏小。PHA算法在构建树的过程中，环形簇上的点会错误地选取中间的团簇上的点作为父节点；图2b中，以点a，b，c为例：Φ(a)<Φ(b)，Φ(a)<Φ(c)，但由于r(a,b)

图2 缺陷分析示例Fig.2 Defect example analysis

同时，针对含噪声的数据集，由于PHA算法在聚类过程中没有对噪声数据进行处理，导致其聚类结果易受到噪声数据的影响，无法得到正确的聚类结果。

2 含噪声的复杂流形数据的势能层次聚类

2.1 识别噪声点

HCPC算法采用构造势能递增曲线的方法识别噪声点。一般情况下，由于各数据集中噪声点的数量远少于正常数据点，且噪声点的分布相对稀疏，因此其势能较大。噪声点判定如图3所示，在势能递增曲线上，噪声点与正常点之间存在一个拐点，图3a中的点C即为图3b中数据集的拐点，拐点之前的点为正常点，拐点之后的点为噪声点，图3b中的星型点为该数据集被识别的噪声点。

图3 噪声点判定Fig.3 Determination of noise points

2.2 势能的分层

基于对重力势能物理意义的分析发现，势能可以反映数据点的分布情况[14]。势能分布图如图4所示，势能大小由内向外逐层递增，边缘点的势能最大，中心点的势能最小。与此同时，受文献[16]中分层聚类的启发，提出依据势能将数据点分层聚类的方法。

图4 势能分布图Fig.4 Graph ofpotential field

定义1势能最大层数据集Smax定义为

Smax={i|Φi≥Φn}

(9)

定义2势能最小层数据集Smin定义为

Smin={i|Φi≤Φp}

(10)

(9)—(10)式中：Φn为去除噪声点后，势能从大到小排序后，第⎣N′×0.25」个数据[16]；Φp为势能从小到大排序后，第⎣N′×0.25」个数据[16]。

假设通过势能递增曲线确定的噪声点总数为n，正常点总数为N′

N′=N-n

(11)

以图1和图2a所示的2个数据集为例，分别取势能最大、最小2层数据，如图5，图6中星形点所示。由图5，图6可见，势能最大层的数据一般处于类边缘位置，或某类数据的势能整体较大；而势能最小层的数据一般处于中心位置，或某类数据的势能整体较小。

图5 DS1分层Fig.5 Layer of DS1

图6 DS2分层Fig.6 Layer of DS2

基于上述分析，分别将最大、最小层数据进行单独聚类，可以确定类簇的大致轮廓。因此，依据文献[17]中介绍的方法，通过势能和与父节点距离的乘积γi来自动聚类，其中，γi定义[17]为

γi=|Φi|·ρi=-Φi·ρ

(12)

2层数据的聚类结果如图7所示，图7中黑色圆点为未聚类数据点。

图7 分层聚类结果Fig.7 Clustering result of hierarchy clustering

最后使用最小类间距离测度将得到的子簇与剩余数据进行层次聚类，得到如图8所示的聚类结果。

图8 DS1与DS2聚类结果Fig.8 Clustering results of DS1 and DS2

综上所述，HCPC算法通过依据势能分层聚类，不仅可以自适应地识别噪声点，而且能够有效处理复杂的流形数据集。

2.3 HCPC算法步骤

HCPC算法流程简单描述如下。

步骤1由(1)—(4)式计算出每个数据点的势能Φi，并排序；

步骤2根据势能大小构造势能递增曲线，找到拐点，识别噪声点；

步骤3由定义1、定义2确定最大、最小层数据；

步骤4分别在最大、最小2层数据内依据(7)式确定每个数据点的父节点parent[i]，并由(8)式计算各层中的数据点到自身父节点的距离ρi；

步骤5分别在2层数据集内由(12)式计算各点的γi值，使用文献[17]中介绍的算法分别对2层数据进行自动聚类；

步骤6在步骤5的聚类结果基础上，对整个数据集采用最小类间距离测度进行层次聚类，直到所有正常数据点的类别都确定为止；

步骤7最后，将步骤2确定的噪声数据分别聚到离其最近的类别中去。

2.4 算法复杂度分析

HCPC算法的时间复杂度主要由3部分组成：计算势能和距离；在最大、最小层数据上对γi值分类；使用最小类间距离进行层次聚类。假设数据点个数为n，则计算势能和距离的时间复杂度为O(n2)，在最大、最小2层数据上对γi值分类的时间复杂度为O(n)，最后层次聚类的时间复杂度为O(n2)，因此，HCPC算法的时间复杂度为O(n2)。文献[14]中介绍PHA算法的时间复杂度为O(n2)，可见，HCPC算法在没有增加算法时间复杂度的同时，提高了算法的聚类效果。

3 实验分析

为了验证HCPC算法的性能，分别在人工数据集和UCI[18]数据集上与PHA算法[14]，CSPV(基于排序势能的聚类算法)[13]进行对比实验。

3.1 人工数据集的实验结果分析

表1 4个人工数据集信息

表1中，DS为Data Set的缩写，其中，DS1由3组服从标准正态分布的随机数构成，各组的中心数据点分别为(0,0)，(3,5)和(6,0)，每组有300个数据，如1.2节中图1；DS2由2个环状簇和1个团状簇构成，如1.2节中图2a；DS3由1个流形簇和2个团状簇构成，如图9a；DS4为2个流形簇相互缠绕所构成，如图9b(为证实HCPC算法能够处理噪声环境的复杂流形数据，特在DS3，DS4数据集上添加噪声点)。

基于欧氏距离测度，分别使用PHA，HCPC，CSPV 3种算法对表1中的4个数据集进行实验。其中，图10，图11分别为PHA和CSPV算法得到的聚类结果，由图10，图11可知，PHA和CSPV算法只能在类似DS1的球形数据集上得到正确的聚类结果，而无法处理复杂的流形数据集，且针对含噪声的数据集，聚类结果易受噪声点的影响。

图9 DS3，DS4数据集Fig.9 DS1 and DS2 data sets

图10 PHA在人工数据集的聚类结果Fig.10 Clustering results onsynthetic datasets by PHA

图12为HCPC算法得到的聚类结果，该算法首先识别噪声数据，然后根据势能分层聚类，确定了类簇的边缘与中心部分，最后在不受噪声数据的影响下得到正确的聚类结果。由图12a可见，针对类内势能分布明显不均匀的团簇结构，3种算法都可以得到正确的聚类结果；而针对PHA算法与CSPV算法无法处理的类内势能分布均匀、类间势能分布差异明显的DS2数据集，HCPC算法亦能得到正确的聚类结果。

针对含噪声的复杂数据集DS3，DS4，PHA算法与CSPV算法无法识别噪声点，而且受噪声点的影响，最终没有得到正确的聚类结果(见图10，图11)；但通过HCPC算法可以识别噪声点并有效处理这一类数据集。

图11 CSPV在人工数据集的聚类结果Fig.11 Clustering results on synthetic datasets by CSPV

图12 HCPC在人工数据集的聚类结果Fig.12 Clustering results on synthetic datasets by HCPC

由此可见，HCPC算法不仅保留了PHA算法快速高效的优点，还解决了该算法无法有效处理噪声环境下复杂流形数据的缺陷。

3.2 真实数据集的实验结果分析

为了进一步验证HCPC算法的性能，选取了5个UCI[18]数据集与PHA算法、CSPV算法进行实验对比，如表2所示。

表2 5个真实数据集信息

同时，使用FMIndex[19]，F1-measure[20]和ARI[21]3种聚类评价指标来衡量种算法的聚类效果。3种指标值的取值均为[0,1]，数值越大，表示聚类效果越好。实验结果如表3—表5所示(各指标的最大值用下横线标出)。

表3 PHA算法在真实数据集上的聚类指标值

表4 HCPC算法在真实数据集上的聚类指标值

表5 CSPV算法在真实数据集上的聚类指标值

由表3，表4中的数据可见，与PHA算法相比，在iris数据集上，2种算法的各聚类指标值相等；在letter数据集上，虽然PHA算法的ARI聚类指标值高于HCPC算法，但在其余2种聚类指标值上均为HCPC算法更高；除此之外，在剩余的3个数据集上，HCPC的3种聚类指标值均高于PHA算法。产生上述结果的原因：一方面，HCPC算法对噪声数据进行了识别，聚类结果不受噪声数据的影响；另一方面，HCPC算法采用势能分层的思想，可以得到更优的聚类效果。

由表4，表5中的数据可见，与CSPV算法相比，在iris数据集上，2种算法的各聚类指标值相等；在letter数据集上，虽然CSPV算法的3种聚类指标值最高，但该算法是在选取了最优参数B值的前提下得到上述聚类结果，且聚类数目远远高于HCPC算法；在vowel数据集上，虽然CSPV算法的ARI指标值高于HCPC算法，但另外2种指标值上均为HCPC算法更高；除此之外，在剩余的glass与wine数据集上，HCPC算法的3种聚类指标值均为最高。

整体而言，HCPC算法能够得到更优的聚类结果，具有更高的准确度。

4 结束语

针对PHA算法无法有效处理流形数据集且对噪声数据敏感的缺陷，本文提出了HCPC算法。与PHA算法相比，HCPC算法在保留原算法快速高效的优势的前提下，不仅弥补了PHA算法的不足，而且可以得到更优的聚类效果。然而，由于HCPC算法采用了欧氏距离的距离测度方法，不利于其处理一些维度较高的数据集。因此，如何使HCPC算法可以在高维数据集上得到更好的聚类结果，将是下一步的研究工作。