一种基于稀疏因子图的大数据近邻传播聚类算法

赖健琼 周金治

1(西南科技大学信息工程学院 四川 绵阳 621000) 2(特殊环境机器人技术四川省重点实验室 四川 绵阳 621000)

0 引 言

近邻传播(Affinity Propagation，AP)聚类是Frey等于2007年在Science上发表的一种基于代表点的聚类算法[1-2]。它一般选取N个数据作为输入，将N个数据点之间的欧氏距离构成相似度矩阵S作为算法的工作基础，该矩阵大小为N×N。按照AP聚类的因子图，N个对象对应N×N条边，算法通过顺着因子图的边传递N×N个吸引度值(Responsibility,R)和归属度值(Availability, A)来完成更新迭代。鉴于该算法通过无监督学习完成聚类，不需要事先人为设定代表点或聚类数目，因此，自问世以来，许多领域都在运用AP聚类算法实现聚类，如推荐系统[3]、文本数据挖掘[4]、数字医疗[5]和商务智能[6]等。

AP聚类算法不仅在算法上具备简单、快速等特点，且在解决大多数数据集聚类问题上，与传统聚类算法相比能够获取更好的聚类效果。但是，原始的AP聚类算法的复杂度为O(N2T),其中T表示迭代次数。随着人工智能时代的到来，各种感知和通信设备以及存储设备的普及，使当前数据形式发生翻天覆地的变化，生活中的数据规模都在爆炸式增长。这使得数据量级别在增大，不仅会增大现有的AP聚类算法时间复杂度，还会占用大量内存空间。对此，文献[1]提出稀疏AP聚类算法，但没有给出具体的稀疏化方法。由于AP聚类算法是以数据对象之间的相似度作为算法的数据基础，所以如何保证在矩阵稀疏化过程中留下最重要的相似度信息，使得稀疏AP聚类算法不出现严重失真显得至关重要。因此，Xiao等[7]提出了基于K最近邻的快速AP聚类算法；Jia等[8]通过K最近邻来构建稀疏相似度矩阵来实现快速AP聚类算法；Shang等[9]通过因子图稀疏化来实现快速AP聚类算法。

上述对提高AP聚类算法性能的主要研究思路大多基于如下思想：在聚类过程中，均认为一个数据对象只和它比较近的代表点的选择过程有关，且起到至关重要的作用，相反和离它较远的代表点的选择过程中起到的作用微乎其微。对于每个数据对象只留下和它相邻的相似度，舍弃了离它较远的相似度。但是，这一改进策略都只考虑局域相似度信息而忽视了全局相似度信息，从而导致了聚类结果中聚类中心数目过多或难以控制的问题。为此，本文提出一种基于稀疏因子图的DPCA_AP聚类算法，即将基于密度峰值聚类算法和AP聚类算法进行融合的方法。首先将N个数据对象作为输入，使用基于密度峰值聚类算法(Density Peaks Clustering Algorithm，DPCA)的决策图选择潜藏代表点完成对相似矩阵的稀疏化；其次依据上述稀疏矩阵得到稀疏因子图；最后通过在稀疏因子图上完成R和A值的循环更新，以获取最后的聚类结果。

1 相关理论

1.1 因子图

因子图是由Kschischang等[10]于2001年提出的对函数进行因子分解的一种概率图模型，主要包括变量节点和函数节点。如图1所示，f(x1,x2,x3)=f1(x1,x2,x3)f2(x1,x2,x3)，其中：x1、x2、x3为变量节点；f1和f2为函数节点。因子图的消息是通过变量节点和函数节点构成并进行相互传递的。

图1 因子图

1.2 决策图

图2 50个数据点分布图

图3是利用基于密度峰值聚类算法得到的决策图，其中点1、2和3为离群点，被选为聚类中心的可能性较大。

图3 决策图

2 AP聚类算法

AP聚类算法将N个数据对象作为输入，计算N个数据之间的相似度并将其组成N×N的相似度矩阵S或s(i,k)，即similarity，其中相似度矩阵是利用欧氏距离作为测量标准，数据对象i和k之间的相似度记作s(i,k)=-‖xi-xk‖2，并且将所有的数据点都视为潜藏代表点；N个数据对象对应因子图的N×N条边，通过因子图的边传递完成R和A的更新迭代；重复上述过程直到达到最终终止条件，算法结束，获得最终的聚类结果。

算法1AP聚类算法

输入：N个数据对象。

输出：k个聚类数目。

1.根据N个数据对象计算它们之间的相似度得到相似度矩阵s(i,k)；

2.初始化吸引度矩阵r(i,k)和归属度矩阵a(i,k)；

3.根据式(1)构造AP聚类算法的因子图[4]，其中s(i,.)代表点i与ci的相似度，如图4所示；

图4 AP聚类算法因子图

(1)

式中：c=(c1,c2,…,cn);δk(c)是惩罚项，定义为:

4.沿着因子图的N×N条边更新r(i,k)和a(i,k)；

(2)

r(i,k)=(1-λ)×r(i,k)+λ×r(i,k)old

(3)

(4)

a(i,k)=(1-λ)×a(i,k)+λ×a(i,k)old

(5)

5.重复步骤4，直到满足终止条件，以获得最终聚类结果。

3 算法设计

处理大数据集时，为了提高算法的效率，文献[1]提出可以通过对因子图稀疏化来提高算法的运行效率，但是，他们并未给出具体的因子图稀疏化的具体方法。因此，本文通过减小相似度矩阵的规模来解决这个问题。鉴于AP聚类算法的相似度矩阵大小与因子图的规模关系紧密，本文选用DPCA算法中的决策图来选择潜藏的代表点，从而减小相似矩阵的大小，与此同时，因子图的规模也会随之减小，即对因子图进行稀疏化，以此来提高算法效率。

3.1 相似度矩阵稀疏化

针对N个数据对象组成的规模为N×N的相似度矩阵S，其实际维数要远远小于数据对象的数量，因此，可以在保证不破坏数据对象之间的相似关系的前提下，对其进行降维处理。在文献[5]中已经对结构化数据和非结构化数据进行特征提取，利用负欧氏距离度量其特征向量之间的相似度，证明在不同的情境下，均可以将N个数据对象嵌入到一个低维特征空间中，并保持数据对象之间的相似度关系不变。在对于基于代表点的聚类问题中，最重要的任务就是如何在N个数据对象中选取代表点集合E。然而在选择代表点的过程中，需要不停地更新迭代R和A的消息值，在此过程中由于相似度矩阵S的规模为N×N，算法的时间复杂度为O(N2T)。

为了提高算法的速率，首要任务就是解决如何完成相似度矩阵S稀疏化的问题，处理步骤如下：

(1)设代表点集合为E，E∈S；

(2)在消息更新迭代之前，对数据对象完成挑选取得潜藏代表点序列E′；

(3)根据吸引度R和归属度A消息的不断更新迭代，得出最终的代表点序列E*，且|E|=|E*|。

在文献[5]中已经证明，若相似度矩阵S的内在维数不高，潜藏代表点的数量|E′|相当大时，那么能够使得从|E′|中获取的代表点序列E*无限靠近代表点序列，则可以选用E*替换作为最终的代表点序列。该方法能够做到兼顾聚类效果和运行速率。文献[5]将相似度矩阵作为输入，采用了一种自下而上选择代表点实现相似度矩阵稀疏化的微簇合并算法(Micro Cluster Merging,MCM)，而本文是通过将所有对象作为输入，采用全局搜索潜在代表点的方法，即利用基于密度峰值聚类算法的决策图来选择潜在代表点实现相似矩阵稀疏化。

3.2 算法步骤

(a)相似度矩阵

算法2DPCA_AP聚类算法

输入：N个数据。

输出：k个聚类数目。

1.将r(i,k)和a(i,k)进行初始化。

5.重复步骤4直到达到算法终止条件，输出并获得最终聚类结果，即k个聚类数目。

3.3 复杂度分析

4 实 验

本节通过实验来验证DPCA_AP聚类算法的有效性，以AP、K-Means和DPCA聚类算法的各项性能指标作为评价的标准，选取轮廓系数(Silhouette Coefficient)[12-13]、调整互信息(Adjusted Mutual Information,AMI)[14]和调整兰德指数(Adjusted Rand index,ARI)来评价算法的聚类效果[15]，选取真实计算时间作为聚类效率的评价指标。

4.1 评价指标

(1)轮廓系数。轮廓系数是评价聚类结构的类内紧密性和类间可分性，能够用来评估聚类质量和最优聚类数目。计算公式为：

(6)

式中：a代表数据对象和类内余下的点之间距离的均值；b代表数据对象与类间其余点之间距离的均值。Sil值越大，聚类效果越好。

(2)调整互信息。调整互信息是通过labels_true(真实类标号)和predict_labels(聚类结果后的类标号)之间的互信息来评价labels_true和predict_labels的一致性。计算公式为：

(7)

式中：U表示真实类标号；V表示聚类结果后的类标号；MI表示labels_true和predict_labels之间的互信息；E(MI)表示U、V的相互信息的期望值；H(U)、H(V)分别表示U、V的信息熵。

(3)调整兰德指数(ARI)。调整兰德指数通过labels_true(真实类标号)和predict_labels(聚类结果后的类标号)之间的一致性来评价被聚在一起的数据对象是否被正确分类。计算公式为：

(8)

4.2 实验数据和运行环境

实验运行环境为Windows 10 64位操作系统，物理内存8 GB，Python 3.7(IDLE)编程实现算法。算法的最大迭代次数设为5 000，稀疏化比率设为0.2。所有程序在同一台笔记本电脑上运行。以scikit-learn 的clustering中AP聚类算法Python源程序为基础，取人工数据集和UCI公共数据集来印证算法的有效性。人工随机生成数据集是以[1,1]、[1，-1]、[-1，-1]三个点为中心，生成100、500、1 000、1 500和2 000等5个数据集，且标准的聚类数目个数为3。UCI公共数据，如表1所示，选用Iris、Wine、Yeast、Balance Scale和Heart等真实数据测试DPCA_AP聚类算法的有效性和运行速率。

表1 5个UCI公共数据集

4.3 聚类效果对比

(1)人工数据集。实验选取K-Means、DPCA、AP三种聚类算法用作评估标准，实验结果如表2所示。可以发现，K-Means、DPCA、AP和DPCA_AP聚类算法所取得的轮廓系数、调整互信息、调整兰德系数和聚类数目大致相同；DPCA_AP聚类算法与AP聚类算法的计算效率在很大程度上得到提高。

表2 K-Means、DPCA、AP和DPCA_AP算法实验对比

为了更好地说明DPCA_AP聚类算法在保证聚类效果的同时在计算速率方面与AP聚类算法相比更胜一筹，图6给出2种算法在相同数量级上的计算时间曲线。当数据量不断变大时，2种聚类算法的计算时间也随之增加，但是DPCA_AP聚类算法增加的速度慢于AP聚类算法，特别是在数据量较大时，DPCA_AP聚类算法在计算速率方面更有优势。

图6 AP和DPCA_AP聚类算法时间对比

图7-图9给出了4种聚类算法的聚类效果对比。

图7 4种算法轮廓系数对比

图8 4种算法AMI对比

图9 4种算法ARI对比

由图7可知，K-Means、AP和DPCA_AP聚类算法的轮廓系数相差不超过0.01，且DPCA_AP聚类算法的轮廓系数明显优于DPCA聚类算法。

由图8可知，当数据在200～500之间，DPCA_AP聚类算法的AMI优于其他3种聚类算法；当数据量大于500，DPCA_AP、K-Means和AP这3种聚类算法的AMI值相差未超过0.01，且DPCA_AP聚类算法的AMI值明显优于DPCA聚类算法。

由图9可知，当数据在200～500之间，DPCA_AP聚类算法的ARI优于K-Means和DPCA聚类算法,与AP聚类算法ARI差值小于0.01；当数据量大于500，DPCA_AP、K-Means和AP这3种聚类算法的ARI值相差未超过0.01，且DPCA_AP聚类算法的ARI明显优于DPCA聚类算法。

图10和图11是数据点为500时的聚类效果图，其中●和▲表示聚类中心。因此，DPCA_AP聚类算法在保证聚类效果的前提下提高了运行速率。

图10 AP聚类算法500个数据点的聚类结果

图11 DPCA_AP聚类算法500个数据点的聚类结果

表3 4种算法聚类效果对比

(2)公共数据集(UCI)。为了更清楚地测试DPCA_AP聚类算法的有效性，本文选取了Iris、Wine、Yeast、Balance Scale和Heart等5个真实数据集进行测试。由于数据集通常拥有不同量纲评估指标，因此数据之间具有差异，如果不解决很可能会影响聚类效果。因此，在执行聚类之前需完成数据标准化处理，将所有的指标按比例缩放，映射到[-1,1]之间。然后，以标准化后的数据作为输入，分别用AP和DPCA_AP聚类算法进行测试，聚类结果如表4所示。

表4 AP和DPCA_AP算法实验对比

从表4中可以发现，在相同的聚类数目上，2种算法最终的聚类效果相差不大，但DPCA-AP算法的运行速率在一定程度上得到提升，且数据量逐渐增大的时候，效果更加明显。

表5给出了DPCA_AP聚类算法采用Iris数据集作为输入的实验结果对比。可以看出，DPCA_AP聚类算法在各个方面与其他3种聚类算法相比均有优势，在轮廓系数方面提高2%，AMI值提高8%，ARI值提高了10%，在计算速度方面提高了16.5%。

表5 4种算法聚类效果对比

通过上述评价指标可以证明，在相同数量级上，DPCA_AP聚类算法在保证聚类效果的同时其计算速率胜过标准AP聚类算法，且数量级越大，优势就更加突出。

5 结 语

本文提出一种基于稀疏因子图的DPCA_AP聚类算法，在聚类之前对相似矩阵完成稀疏化处理，将矩阵的规模从N2降低到Nx,从而使得利用因子图的边进行消息传递时，R和A的计算量减少，使其减少了聚类算法的时间复杂度，提高了算法的运行效率。本文利用轮廓系数、调整互信息、调整兰德系数和实际运行时间来评价算法的聚类有效性和运行速率，并利用随机生成数据集和UCI公共数据集验证了DPCA_AP聚类算法的有效性。