基于AP聚类的多特征融合方法

郭蕾蕾，俞 璐，段国仑，陶性留

(1.陆军工程大学 通信工程学院，江苏 南京 210007；2.陆军工程大学 指挥控制工程学院，江苏 南京 210007)

0 引 言

随着互联网技术的快速普及与发展，Web数据量急剧增长，这些海量的数据包含着丰富的信息，如何对其进行有效的挖掘已经成为当前互联网应用的关键问题之一。聚类分析作为一项十分有效的数据挖掘技术，需要的驱动条件少[1]，而且适应能力强，适合处理多种类型数据。

数据通常可以从不同领域的不同来源收集或从不同视图观察得到，即多数据包含多种类型的特征。例如，网站上的文档可能包含页面文本、链接文本以及一些伴随图像等；同一幅图像可由不同的特征(如HOG特征、SIFT特征等)进行描述；传感器信号可在时域和频域分解等。诸如此类的数据也称为多视图数据，因其从不同角度刻画同一事物，因此包含了更丰富的识别信息。不同视图数据通常存在一定的信息冗余，如何充分地从多视图数据中提取有用特征并进行融合是一个较新的研究方向。

多视图聚类是将多个异构特征进行融合的聚类技术，目前多视图聚类已经取得了很多研究成果。根据多特征融合方式的不同，多视图聚类可以分为前融合聚类、后融合聚类和过程中融合聚类[2-3]。前融合聚类就是将数据信息的多个特征集成到一个公共向量空间上，再利用传统的聚类方法进行聚类。特征集成常用的方法是将各个特征直接拼接或加权相加。后融合聚类是分别对不同的特征进行单独聚类，再将它们的结果采用投票等策略进行集成。过程中融合聚类是指对多视图属性特征融合时存在多次迭代，每次迭代只产生一个具有所有视图信息的聚类结果，通常有基于协同训练和非负矩阵分解的方法等[3]。多特征融合聚类虽然取得了一些成果，但对于不同的问题仍然缺乏完善且普适的算法。

针对多特征信息融合的Web图像聚类这一具体问题，分析Web图像的特点，融合图像特征和文本特征，提出了一种基于成对约束的多特征融合AP聚类算法。

1 相关工作

1.1 AP聚类

Affinity Propagation聚类算法又叫近邻传播算法，简称AP[4]，其基本思想是将全部样本看作网络的节点，通过数据元素之间的消息传递，实现数据集合中元素的自适应聚类[5]。AP聚类的输入为节点间的相似度矩阵S，其中s(i,j)表示节点i与节点j之间的相似度值，表明了j作为i的聚类中心的能力。聚类过程中，共有两种消息在各节点间传递，分别是吸引度(responsibility)和归属度(availability)。AP算法通过迭代过程不断更新每一个节点的吸引度和归属度值，直到产生m个高质量的质心，同时将其余的数据点分配到相应的聚类中。吸引度信息用r(i,k)表示，即数据点k适合作为数据点i的聚类中心的程度，r(i,k)值越大，数据点k成为聚类中心的能力越强；归属度信息用a(i,k)表示，即数据点i选择数据点k作为聚类中心的合适程度。两种信息的迭代公式如下：

(1)

(2)

(3)

其中，a(i,k')表示除k外其他点对i点的归属度值，初始为0；r(i,k')表示节点k作为除i外其他节点的聚类中心的吸引度值。

在相似度矩阵中，索引相同的点(如s(i,i))的值称为参考度或偏好参数(preference)，此参数会影响到最后聚类的数量，参考度越大则说明某个数据点成为聚类中心的能力越强，则最终聚类中心的个数越多。迭代开始前，假设所有点成为聚类中心的能力相同，因此参考度一般设为相似度矩阵中所有值的最小值或中位数。

在消息传递过程中，为防止数据震荡，引入衰减系数。在每次循环迭代中，r(i,k)和a(i,k)的更新结果都由当前迭代过程中更新的值和上一次迭代的结果加权得到[6]。加权公式为：

rnew(i,k)=λrold(i,k)+(1-λ)rnew(i,k)

(4)

anew(i,k)=λaold(i,k)+(1-λ)anew(i,k)

(5)

迭代完成后，综合吸引度值和归属度值确定最终的聚类中心点，即对于点i来说，不论是否k=i，使得a(i,k)+r(i,k)取值最大的那个k即为点i的聚类中心。当经过若干次迭代后其聚类中心不变或者迭代次数超过既定的次数时，算法结束。

不同于其他聚类算法，AP聚类算法不需要指定聚类簇数或其他描述聚类个数的参数，而且样本中的所有数据点都可当作潜在的聚类中心，实值信息在节点之间传播直至产生一组高质量的聚类簇。同时它对初始值不敏感，并且比其他方法产生的误差平方和都要低。

1.2 图像特征提取

(1)颜色特征。

颜色特征代表图像色彩整体的分布规律，是人眼能识别的最直观显著的特征。常用的图像颜色特征提取方法有：颜色直方图、颜色矩和颜色熵等[7]。颜色直方图是使用最广泛的颜色特征，用来表示整个不同的颜色分量在图像中所占的比例。文中使用HSV颜色空间直方图来对图像的颜色特征进行描述。首先，将RGB模型转为HSV模型，然后将HSV颜色空间分为若干个小的颜色区间，每个小区间成为直方图的一个bin，这个过程叫做颜色直方图的量化。最后，通过计算颜色落在每个小区间内的像素数量可以得到颜色直方图。

(2)纹理特征。

纹理特征是一种不依赖于颜色或亮度而变化的视觉特性，它刻画了图像像素邻域灰度空间的分布规律[8]，常采用灰度共生矩来描述图像的纹理特征。纹理特征统计量包括能量、熵、对比度和相关性，分析图像相邻像素的灰度排列，根据图像在0°、45°、90°、135°方向的灰度共生矩[6]，分别计算每个方向的能量、熵、对比度和相关性，求取每个方向的均值和方差作为纹理特征向量。

(3)形状特征。

形状特征是人类进行物体识别所需要的关键信息之一，通常有两类表示方法：描述边界的轮廓特征和描述整个区域的区域特征。常用的形状特征描述子有傅里叶描述子、Hu矩、Zernike矩等。文中利用Hu矩来提取形状特征，即利用二阶和三阶中心距构造七个不变矩，这七个不变矩构成一组特征量，在连续图像条件下可保持平移、缩放和旋转不变性。相较于其他提取形状特征的方法，由Hu矩组成的特征量对图像进行识别，可以得到更快的处理速度。

(4)HOG特征。

HOG又名梯度方向直方图，由Dalal和Triggs于2005年提出[9-10]。提取HOG特征的过程：首先将图像分割成多个小的连通区域，称为细胞单元(cell)，然后在cell中统计所有像素点的梯度或边缘方向信息得到梯度方向直方图，最后将所有直方图组合起来即可得到HOG描述子特征向量。

1.3 文本特征提取

文本特征常用向量空间模型(VSM)来表示，其主要思想是将文本用多维空间的向量来表示，每一个不同的特征项(词语或句子)对应向量空间的一维，而每一维的值就是对应的特征项在文本中的特征值。之后在这个向量空间模型中，采用欧氏距离或夹角余弦等相似度度量方法，得到文本之间的相似度。特征权重常用的计算方法有TF-IDF统计法、word2vec模型训练法等。

2 基于AP聚类的多特征融合算法

现有的聚类方法大多只适用于有单个特征的数据集，无法直接应用于多视图数据。而现有的拼接、加权等特征融合方法又都存在着明显的缺陷，直接拼接容易引发维数灾难问题，且由于不同特征量纲和物理意义的不同会导致样本数据不具有可解释性，此外还可能因为不同特征的尺度不同导致有价值但尺度较小的特征被忽视。不同特征线性加权的融合方法只适用于各特征维数相同的情况，也同样面临着加权后的样本不具有可解释性和尺度较小的特征易被忽视的问题。

多视图学习，包括有监督的分类和无监督的聚类，都可能存在各特征单独使用时的学习效果差异较大的问题，即有的特征经过学习可以获得很好的分类或聚类效果，称为“好特征”；有的则不能得到好的效果，称为“差特征”，文中将这种现象称之为“视图(特征)不平衡”问题。针对“视图(特征)不平衡”数据，直接拼接的特征融合方式很可能会因为表现较差的特征的平等加入而影响最终学习效果；加权相加的特征融合方式虽可以通过设定权重因子调节不同视图特征之间的权重，但仍然无法避免由于特征物理意义、量纲、尺度不同而导致的问题。据了解发现，现有的多视图学习方法没有考虑“视图(特征)不平衡问题”，在特征融合时大都平等地对待不同的视图数据，这样很可能会导致“差特征”极大地影响到“好特征”学习的结果。

由前文对AP聚类算法的介绍得知，相似度矩阵S的定义直接影响到AP聚类算法的性能，若相似度矩阵能够准确地度量数据点之间的相似性关系，则可以得到很好的聚类结果。针对“视图(特征)不平衡”数据，文中提出了一种基于成对约束的多特征融合AP聚类算法。该算法主要思想是利用成对约束来调整AP聚类的相似度矩阵，“好特征”数据在相似度矩阵中占据主导，“差特征”数据以约束的形式发挥作用。

约束信息有多种，聚类算法中较为重要和常用的是成对约束，成对约束信息最早来源于半监督学习，即约束信息是少量且已知的。成对约束包括正约束和负约束两种[11]：若两个数据点一定属于同一个类，则这两个数据点属于正约束对；反之若两个数据点一定不属于同一个类，则这两个数据点属于负约数对。

同半监督学习不同，文中的聚类是无监督学习，样本类别、聚类个数、约束信息都未知。为此，用一种特征进行聚类产生约束信息。对于“视图(特征)不平衡”数据，“差特征”数据被加入了较大噪声，有用且正确的信息不是特别多，但这些信息又不能完全丢弃，此时将“差特征”信息以约束形式加入有利于充分利用各特征。虽然“差特征”计算的相似度矩阵可信度不高，但若设置较大的聚类簇数，可以较好地保证聚类纯度，那么此时位于同一个簇内的样本最终属于同一个聚类的概率较大。文中就将这些信息作为正约束，用于调整基础相似度矩阵得到最终的相似度矩阵S。

通常而言，调整相似度矩阵S的基本原则应该是当约束对属于正约束时，即认为两样本具有很高的相似性，将其相似度值置为较高值；当约束对属于负约束时，即认为两样本相似度很低，将其相似度值置为较低值。那么文中为何不使用负约束对。如前所述，聚类是无监督学习，由聚类所获得约束信息不能保证完全准确，无论设置多大的聚类簇数，不同簇之间样本都不能完全确定一定不属于同一类。文中仅通过设置较大的聚类簇数保证纯度以提高正约束对的准确性。

(6)

这样得到的约束矩阵S1中有2Q个元素值为1，其余值为0。假设“好特征”数据的余弦相似度矩阵为S2，则对S的调整方式如下：

S=S2+αS1

(7)

其中，α为调节因子，表示样本相似度修改的程度，取值为[0,1]。α为0时，表示不加入约束信息。

具体的算法流程如下所示：

输出：聚类簇C1,C2,…,Ck2。

(3)随机从集合M中选取Q个约束对，按如下规则转化为稀疏的约束矩阵S1：

(5)调整S：S=S2+αS1，其中α∈[0,1]；

(6)在S上进行AP聚类，输出聚类结果C1,C2,…,Ck2。

3 实验结果

3.1 实验数据集

在PyCharm EDU环境下编写python程序爬取百度百科网页，获得了480幅图像及对应的伴随文本(一幅图像对应一个伴随文本文档)，这些图像大致分为7类：狗(70)、植物(70)、飞机(70)、桥(70)、鸟类(70)、建筑(70)、山水(60)。

用前文所述的图像特征提取方法，提取了每幅图像的256维颜色特征、7维形状特征、8维纹理特征以及3 780维HOG特征。对于文本，经过分词、去除停用词、训练word2vec模型后得到其余弦相似度矩阵。

3.2 评价标准

对于聚类结果，首先采用纯度[12]进行了简单的评价，定义第i簇的纯度为：

(8)

其中，mi是第i簇中样本的个数；mij是第i簇中第j类的样本个数；K是聚类簇的个数。

聚类的总纯度为：

(9)

其中，K是聚类簇的个数；m是样本的总数。

聚类纯度这一评价指标有一个明显的缺点，即若每个样本单独聚为一类，此时纯度值为1，认为所有样本都被划分到正确的簇中，显然这一结果是不准确的。因此单独使用纯度这一指标，将无法对这种退化的聚类结果给出正确的评价[13]。为了更进一步评价聚类结果与实际分配的吻合程度，文中还计算了调整兰德指数、标准化互信息量、调整互信息量三个指标。

调整兰德指数需要给定实际类别信息L，假设K是聚类结果，a表示在L和K中都是同类别的元素对数，b表示在L和K中都是不同类别的元素对数，则兰德指数为：

(10)

(11)

假设L和K分别是n个样本标签的实际分配和聚类后分配情况，则两种分布的熵分别为：

(12)

(13)

其中，P(i)=|Li|/n；P'(j)=|Kj|/n。

(14)

其中，P(i,j)=|Li∩Kj|/n。

标准化后的互信息(normalized mutual information)为：

(15)

调整互信息(adjusted mutual information)定义为：

(16)

其中，NMI取值范围为[0,1]，AMI取值范围为[-1,1]。它们都是值越大，意味着聚类结果与真实标签越吻合。

3.3 实验结果与分析

文中先利用图像特征进行K均值聚类，将得到的带类标签的结果转化为约束对集合，随机选取Q个约束对求得约束矩阵S1。然后用前文所述方式调整文本相似度矩阵，之后再进行AP聚类，此方法用KAP表示。实验中根据不同特征聚类所得约束对数目的不同选择不同的Q值，约占总约束对数目的10%；调节α值得到不同结果。

为了验证文中方法的有效性，将得到的结果与以下几种方式进行对比：

(1)单特征聚类：只用图像特征和文本特征进行AP聚类。

(2)两种特征简单拼接后再聚类。

(3)多视图谱聚类算法[14]：首先在每个视图中根据输入的相似度矩阵获得各自拉普拉斯矩阵的特征向量U1和U2，然后使用U1和U2分别更新第2个视图和第1个视图的相似度矩阵，这个过程进行多次重复迭代。

结果如表1～表4所示。

表1 图像颜色特征与文本特征融合聚类结果 (KAP算法中Q=40，α=0.9)

表2 图像形状特征与文本特征融合聚类结果 (KAP算法中Q=30，α=0.6)

表3 图像纹理特征与文本特征融合聚类结果 (KAP算法中Q=40，α=0.1)

表4 图像HOG特征与文本特征融合聚类结果 (KAP算法中Q=100，α=0.4)

图1展示了各指标随α值的变化情况。

(a)颜色、文本特征融合聚类结果指标变化

(b)形状、文本特征融合聚类结果指标变化

(c)纹理、文本特征融合聚类结果指标变化

(d)HOG、文本特征融合聚类结果指标变化

由以上4个表的结果可以看出，单独使用某个图像特征聚类的效果很差，且与单独文本特征聚类效果差异较大，将这两种特征简单拼接后再聚类结果也较差。这是因为简单拼接“差特征”严重影响了“好特征”的效果发挥。多视图谱聚类虽较拼接聚类有所提高，但仍落后于单独使用文本特征聚类，这是因为在多视图谱聚类过程中，“好特征”与“差特征”同等对待造成聚类结果也被平均。由此可见，直接拼接、多视图谱聚类等所有平等对待各种特征的聚类方法都不适合处理“视图(特征)不平衡”数据。

无论采用哪种图像特征，相比于比对算法，文中提出的多特征融合聚类算法都得到了较好的聚类结果。由图1可以看出，随着α值的增大，各指标呈现震荡趋势，但幅度变化不大，α值继续增大，各指标有下降趋势，特别是HOG特征与文本特征的融合，因此α值不宜过大。由于成对约束信息是图像经过K均值聚类后得到，并不能完全保证约束信息的准确性，因此相较于单独文本聚类结果评价指标提高不是很大，这也是今后仍需努力提高的地方。总而言之，文中算法达到了预期的目标。

4 结束语

提出了一种基于成对约束的多特征融合AP聚类算法。该算法针对多视图数据存在“特征不平衡”问题以及现有聚类技术的不足，启发式地引入某个特征聚类后得到的带标签的结果形成的约束对信息来调整相似度矩阵，即“好特征”数据占主导地位，“差特征”数据以约束信息形式加权，然后在新的相似度矩阵基础上进行AP聚类。实验结果表明，该算法有效地改善了聚类性能。但由于约束对信息是经过特征聚类所得，并不能完全保证其准确性，故下一步将对如何保证约束对信息的完全准确性进行探索研究。