钱雪忠，王卫涛

江南大学 物联网工程学院，江苏 无锡 214122

1 引言

聚类分析是对一组对象进行处理，最终将对象分成几类，使得同一类对象之间的相似度更大，不同类对象的相似度更小。在聚类分析的发展过程中，提出了k-means、DBSCAN、FCM等聚类算法，2007年Frey和Dueck在Science阐述了近邻传播聚类算法（affinity propagation，AP）的原理和应用。与其他聚类方法相比，近邻传播算法不需事先设定聚类的个数，不需初始化聚类中心点，是一种快速有效的聚类算法。由于AP算法是基于中心的聚类算法，因此在处理紧凑的具有超球形分布的数据集上有较好的性能，但是不适合具有任意空间形状和多重尺度的数据集。

针对上述问题，Dong等[1]提出了可变相似性度量的近邻传播聚类（affinity propagation of variable similarity measure，AP-VSM），该方法采用可变度量来改善数据的总体分布特性，该方法在处理一些复杂的高维数据时有较好的效果，然而该方法在处理不同类之间有相互交叉的情况时效果较差；Jia等[2]提出了基于光谱尺寸减小的密度自适应近邻传播聚类（density-adaptive affinity propagation clustering algorithm based on spectral dimension reduction，DAAP），该方法采用最短路径构建相似度矩阵，利用该方法能够较好地处理多尺度数据集的问题，但是该算法在计算最短路径时算法时间复杂度过大；Gan等[3]提出了子空间近邻传播聚类（subspace clustering using affinity propagation，SAP），该算法利用属性权重计算相似度矩阵，并在迭代过程中动态更新属性的权重，从而更新相似度矩阵，利用该方法可以较好地处理复杂空间的数据，但是在处理样本量较大时稍显不足；Li等[4]提出了自适应调整偏向参数的近邻传播聚类算法（adjustable preference affinity propagation clustering，APAP），该方法为不同的数据点设置不同的偏向参数，并动态更新，该方法适合高斯分布以及流行分布的数据，但不适合处理图像相关的数据集。

本文针对文献[1-4]中处理数据集中不同类数据有交叉的问题，算法时间复杂度过大的问题，不适合处理多样本的问题以及不适合处理图像相关的数据等问题提出了MSAAP（multidimensional similarity adaptive affinity propagation）算法。首先，针对文献[5-8]的想法，本文根据熵值法计算数据集的属性权重，然后根据属性权重和高斯核函数构造出一种更加准确的计算相似度矩阵的方法；接着针对文献[9-13]的想法，本文根据权重矩阵选取优先级高的属性，跟该属性的个数n，将空间分成2的n次方个子空间，最后针对文献[14-20]，本文提出计算分布各个子空间的邻域数据点的吸引度和归属度之和，进而调整该样本点的空间分布。然后调整后的样本点去重新迭代计算相似度、吸引度和归属度，一直到迭代结束。本文在第3章详细介绍该算法的计算过程。

2 近邻传播算法

AP算法把所有的样本点作为候选聚类中心点。AP算法主要利用数据集中任意两个样本点之间的相似度进行迭代计算。其中相似度的定义为两个样本点之间欧式距离平方的负数，计算相似度矩阵的公式如下：

在AP算法中需要设置偏向参数的值，默认设置为相似度矩阵的均值，即p=median(s)。该算法在计算过程中引入了归属度矩阵A(availability)和吸引度矩阵R(responsibility)，在算法迭代过程中两个信息矩阵不断地迭代更新。其中：A=(a(i,j))m×n,a(i,j)是样本点j向样本点i发送的信息值，表示为样本点i选择样本点j作为聚类中心点的合适程度；R=(r(i,j))m×n,r(i,j)是样本点i向样本点j发送的信息值，表示为样本点j作为样本点i聚类中心点的合适程度。归属度矩阵和吸引度矩阵的迭代更新的计算公式如下：

在计算归属度矩阵相似度矩阵过程中，为了防止震荡，引入了阻尼因子λ来增强算法的稳定性，计算公式如下：

根据以上公式迭代计算归属度矩阵和吸引度矩阵，最终使得聚类目标函数最大化，其聚类目标函数如下：

式中，ci为样本点i的聚类中心点，C是由ci组成的向量，i=1,2,…,N（N为样本点个数），S(C)为所有样本点到各自的聚类中心点的相似度之和。其中δk(C)计算公式如下：

此式为一致性约束惩罚项，如果有样本点i选择k作为其聚类中心点，即ci=k，那么样本点k必定选择自身为聚类中心点，即ck=k，否则函数取值-∞，使样本点i在下次迭代中不再选择k作为自身聚类中心点。

迭代后通过计算A+R的值来确定聚类中心点，当(r(k,k)+a(k,k))＞0时，样本点k即为聚类中心点。各个样本点的聚类中心点ci的计算公式如下：该式表示为每个样本点选择归属度和吸引度之和最大的聚类中心点作为自身的聚类中心点。

3 MSAAP算法

3.1 算法描述

3.1.1 熵值法计算属性权重

熵值是具有不确定性的一种度量。信息量越大，不确定性就越小，熵也就越小；信息量越小，不确定性越大，熵也越大。因此根据熵的特性，可以利用熵值来判断某个指标的离散程度，指标的离散程度越大，该指标对综合评价的影响（权重）越大，其熵值越小。同时熵在信息论中已经得到广泛的应用，因此本文通过计算数据样本点的熵值来确定各个属性的权重，可以更能真实表达数据集的特性。

计算熵值的过程需要依次计算归一化指标、指标比重、指标熵值、信息熵冗余度、指标权值。其公式如下：

式中，xij为数据集中第i个数据点的第j项指标，i=1,2,…,n（n为样本点个数），j=1,2,…,d（d为样本点属性个数）；k=1/ln(n)＞0，满足ej≥ 0。ej表示第j项指标的熵值，rj表示信息熵冗余度，wj则表示为最终的指标权重。

图1中的横轴为数据集的维数，纵轴为每一维特征的权重，从图中可以看出，通过计算样本点各个属性的熵值可以很好地区分出属性的重要程度，然后根据实际实验的需要，选取若干个权重属性。图中用到的数据集的具体属性在第4章中介绍。

3.1.2 根据权重计算相似度矩阵

Fig.1 Attributes weighted graphs calculated by entropy method图1 通过熵值法计算的属性权重图

其中，r为核变换系数。

为了充分验证本文所采用的相似度计量方法的有效性，需要通过数据集的相似性度量来对比，本文通过任意选取两个同类的数据点和一个不同类的数据点，分别计算出这两组的相似度s1和s2，然后计算出一个比值rate=(s1-s2)/s2，这样做的目的在于保证在做不同相似度对比实验时，都在同一个数量级内，使得实验结果具有更好的可靠性。对比结果见图2、图3。

Fig.2 Comparison chart of wine data set图2 wine数据集对比图

Fig.3 Comparison chart of YaleB data set图3 YaleB数据集对比图

图中es_rate为欧式距离平方的负数计算的相似度比值，ds_rate为密度自适应计算的相似度比值，ws_rate为本文采用的加权密度自适应比值。从结果看出，ws_rate的比值是最大的，说明了此方法在计算同类数据点的相似度比es_rate和ds_rate更大，在计算不同类数据点之间时，ws_rate相比另外两种则更小，说明ws_rate计算相似度更准确。为保证实验的公正性，同类数据点和不同类数据点都是随机选取的，并做10次对比实验。

3.1.3 根据多维空间调整个体空间分布

AP算法每次迭代后，会有吸引度和归属度矩阵生成，吸引度和归属度矩阵的加和表示了两两数据点之间的相似程度，因此将吸引度和归属度加和的指标作为衡量指标，来调整个体的空间分布。

首先需要前期处理工作，为了避免正负数的相互抵消，首先采用sigmoid函数将AR矩阵映射到[0,1]区间内，AR为归属度矩阵A和吸引度矩阵R之和。然后根据3.1.1节计算出的权重矩阵W，选出前l个属性，属性集合为ls。

然后将根据样本点的距离求出阈值Eps，本文中Eps是通过距离矩阵的平均数（Median(D)）计算得出的。因为距离矩阵的平均数反映的是整个数据集样本点之间距离的平均情况，利用该平均数可以过滤一些边缘点、噪声点的干扰。当两个样本之间的距离小于该阈值时表明这两个样本相对整个数据集来说更有可能属于同一类簇，反之，则说明该两个样本属于同一类簇的可能性较低，接着根据阈值Eps计算每个样本点的邻域areas，通过areas中的样本点去调整当前样本的区域分布，如果D(i,k)≤Eps，则areas(t)=k,t=t+1。如果areas为空，则处理下一个数据点；如果不为空，则根据l值计算出需要划分的子空间数目nums=2l。接着初始化2l个空间的初始状态，初始化的计算公式如下：

其中，1表示正相关，-1表示负相关，j∈ls时的计算步骤如下：

1.首先初始化变量：nums=2l

2.forcol=1∶l

3.index=cols(col)，step=2(l-col),frep=0,flag=1

4.fort=1∶nums

5.frep=frep+1

6.iffrep≤step status(t,index)=flagend if

7.iffrep==step

8.frep=0

9.ifflag==1flag=-1elseflag=1end if

10.end if

11.end for

12.end for

图4中，左侧图为调整前的样本点分布，右侧为调整后的样本点分布，其中左侧图中处于坐标轴的中心黑点为当前调整的样本点。图4是从模型的角度来分析整体数据点调整的基本规律，为了更好地展示，采用二维空间来表示，因此划分的总的子空间数目为22，其中A、B、C、D分别代表四个空间，每个空间内包含若干当前数据点的邻域点，然后分别计算：

Fig.4 Chart of spatial adjustment图4 空间调整分布示意图

接着计算max{sumA,sumB,sumC,sumD}，求出吸引度和归属度之和最大的区域，并计算出该区域中所有数据点的中心点center，然后用center代替当前处理的数据点x，最后继续迭代计算下一个数据点。当计算完所有数据点之后，更新数据集的相似度矩阵s、偏向参数p，然后进行下次迭代。

在实验中，为了缩短运行时间，同时保证迭代过程更加稳定，在迭代过程中增加更新频率freq，如果满足 mod(iter,freq)=0，则update(data,s,p)；反之，则 continue，继续下次迭代。在本文中freq是通过sigmoid函数计算出的，sigmoid函数是一个从大到小变化的平滑函数，在AP算法迭代的初始阶段，幅度较大，既保证了迭代的速率又保证对数据集一个整体的调整变换。随着算法迭代的深入，幅度缩小，保证了对个别数据点的调整，同时也避免了算法为了适应不同数据集而去不断调整频率的大小，这样保证了算法的效率性和鲁棒性。表1和表2是频率选取固定值和sigmoid函数计算的对比实验。当固定值为1时，为每次迭代都更新。以此来验证采用sigmoid函数在此处的有效性。

Table 1 Parameter selection table of wine表1 wine数据集的参数选取表

Table 2 Parameter selection table of leuk72_3k表2 leuk72_3k数据集的参数选取表

表1和表2中固定值对应的数据为freq取一定值时所对应的准确率和时间，sigmoid对应的数据为本文利用sigmoid函数计算频率对应的准确率和时间。从表中可以看出频率的选取与准确率没有比例关系，对于任意的数据集可能是任意的固定值，因此在实际的仿真实验有一定的难度，同时当频率取某个固定值时准确率高了，那么时间就会很慢，时间快了，准确率就会下降。而利用sigmoid函数计算频率就会在保证准确率的同时，降低时间复杂度。此处提到的准确率会在本文4.1节介绍。

3.2 算法步骤

Input：X={x1,x2,…,xn}.

Output：idx：Clustering results.

1.w=entropy(X)//由3.1.1节计算

3.pm=Median(Sn×n)

4.iter←0

5.A′=AP.update(A),R′=AP.update(R)

6.frep=floor(a⋅ln(iter)/ln(b)+c)

7.if mod(iter,frep)==0

8.AR=sigmoid(A+R)

9.ls=sort(w,-1)(1∶l)

10.fori=1∶n

12.Eps=Median(dis)t=0

13.fork=1∶n-1

14.ifdis(i,k)≤Eps t=t+1areas(t)=kend if

15.end for

16.iflength(areas)＞0

17.status=init(l,cols)//由表1计算

18.fork=1∶length(areas)

19.forj=1∶l

20.ifx(i,j)＞x(k,j)status′=-1end if

21.ifx(I,j)≤x(k,j)status′=1end if

22.end for

23.index=find(status′,status) set(index,t)=kt=t+1

24.end for

25.fort=1∶nums

26.sumARs=sum(AR(set(t)))

27.end for

28.x(i)=avg(max(sumARs))

29.end if

30.end for

31.Algorithm terminated.

4 实验结果与分析

不同指标往往具有不同的量纲和单位，这样会影响数据分析的结果，为了消除指标之间的量纲的影响，本文对数据集进行了归一化处理。本文选取了13个UCI数据集和ORL、YaleB、JAFFE人脸数据库。数据集信息见表3。

4.1 评价指标

为了更加客观地反映聚类算法的优劣，本文选取F-Measure作为算法的评价指标，F-measure是由precision（精确率）和recall（召回率）共同表示，准确率（F-measure）通常用来表示聚类准确性的优劣。计算公式如下：

Table 3 Information of data set表3 数据集信息

4.2 参数调整分析

由于在实验过程中，引入了邻域的阈值和特征维度两个参数，当参数不同时，实验结果也不同。因此需要在大量的实验中，找出适合不同数据集的参数，表4、表5为本文做的参数选取实验。

表4、表5中，eps表示阈值，dim表示维度。从表4、表5可以看出，参数阈值和维度对聚类结果影响很大，因为在实验中，阈值是控制样本点的邻域个数，能影响散落在各个空间中邻域点的数目，最终会影响样本点的分布的调整，所以阈值对聚类结果影响较大。而维度是m个权重最大的属性，当m取不同值时，选取的属性个数就不同，而在调整样本点分布时，所改变的样本点的属性不同，因此最终对聚类结果影响较大。

Table 4 Parameter selection table of wine表4 wine数据集的参数选取表

Table 5 Parameter selection table of zoo表5 zoo数据集的参数选取表

4.3 准确率、时间、类数分析

本文从准确率、时间、聚类类数3个维度对AP、AP-VSM、DAAP、SAP、APAP、MSAAP进行了对比。其中，F为准确率（F-measure），Time单位为秒（s）。对比如表6所示。

从准确率来看，MSAAP算法在这16个数据集上，相比其他5种算法有了明显的提升。AP-VSM、DAAP、SAP、APAP这4种算法都有各自适合的数据集。DAAP在Sonar、YaleB等数据集上处理效果较其他方法差；SAP在leuk72_3k、haberman、ORL等数据集上处理效果较差；APAP在JAFFE数据集上处理效果较差。而本文提出的MSAAP处理这16个数据集相比其他算法都有较好的改进。

从时间方面看，DAAP算法由于需要计算最短路径，时间复杂度最大，其次本文提出的MSAAP算法需要在迭代中调整样本点的空间分布，因此时间复杂度稍大，MSAAP的时间复杂度为O(m×n2)，AP、AP-VSM、SAP、DAAP算法的时间复杂度都为O(m×n)，其中m为近邻传播算法的迭代次数，n为样本点数。

从聚类类数来看，AP-VSM和SAP分别有6个数据集与真实类数不同，APAP有5个，DAAP有3个，但都比原始AP算法更接近真实类数，而MSAAP算法在这16个数据集上最终的聚类个数都与真实类数相符。

Table 6 Table of F-measure,Time and clusters表6 F-measure、时间、类数对比表

从准确率、时间、类数来看，MSAAP算法除了在时间复杂度上略大于AP、AP-VSM、SAP、APAP这4种算法外，准确率、类数相比来说更好。从整体来看，本文算法具有更好的聚类性能。

4.4 效果图分析

为了直观地看出6种聚类算法优劣，本文通过聚类效果图展示的形式，来更加直观地反映表4数据的有效性。为了更好地显示聚类效果，通过PCA将数据集降至2维，从而可以在平面上显示最终的聚类结果。本文选取wine、seeds、YaleB、JAFFE数据库进行对比。wine有178个样本点，13维属性，3类数据，wine的属性变量为连续变量，是流行分布的，是不平衡的数据；seeds有210个样本点，7维属性，3类数据，seeds的所有属性值都为实值连续的；YaleB数据库有45个样本点，192×168维属性，5类数据，YaleB每幅图像都有相对较大的光照变化、表情变化、部分缺损以及姿态变化；JAFFE数据库有50个样本点，256×256维属性，5类数据，每个人有7种表情的图片。

wine和seeds数据集聚类难度在于3类数据在分布的区域位置上相互交叉，不同类的数据点之间的距离比同类之间的距离要近，如果算法中用一些传统的相似度计算公式或者维度选取不合适会造成聚类结果的差异性。YaleB和JAFFE数据库聚类难度在于孤立点较多，会造成聚类时选取聚类中心点过多，最终聚类的类数与实际情况不符。聚类效果图见图5到图8。

Fig.5 wine data set clustered by 6 methods图5 wine数据集6种方法聚类效果图

Fig.6 seeds data set clustered by 6 methods图6 seeds数据集6种方法聚类效果图

Fig.7 YaleB data set clustered by 6 methods图7 YaleB数据集6种方法聚类效果图

Fig.8 JAFFE data set clustered by 6 methods图8 JAFFE数据集6种方法聚类效果图

图5到图8左至右依次为原始数据分布图，AP、AP-VSM、DAAP、SAP、APAP、MSAAP聚类效果图，从图5、图6和图8可知，当数据集中有若干个数据点为孤立点时，AP、AP-VSM、DAAP、SAP、APAP这5种算法将这些孤立点单独聚为一类，而MSAAP算法很好地处理了这些孤立点，证明该方法在处理边缘点时效果较好。同时从4幅图中可以看出MSAAP聚类的效果图中的类数以及聚类中心点的选取都与原始数据相符合，聚类后样本点分布的区域与原始数据集分布的很接近，区域密度也类似，并且类与类之间相互交叉得很少。而其他5种算法在处理这些数据集时均出现聚类结果与原始数据不一致的情况。

从这些效果图中可以直观地看出MSAAP算法对传统AP算法有了明显的改进，同时相比较本文中提到的其他改进算法也有明显的改进。再结合表6的数据分析说明MSAAP具有很好的聚类性能。

5 结束语

本文介绍了近邻传播算法(AP)和基于多维空间调整数据点空间分布的原理与步骤，首先介绍了熵的概念，并通过熵值求解属性的权重的计算步骤；其次利用熵值权重构造新型的相似度矩阵；然后对数据点在多维空间分布的位置进行动态调整的问题进行建模和求解；最后在UCI数据集和人脸数据库上进行了对比实验。证明了本文所研究的方法在处理多重尺度和任意形状的数据集时具有较好的聚类效果。