基于超图正则化受限的概念分解算法

李 雪赵春霞 舒振球 郭剑辉

(南京理工大学计算机科学与工程学院 南京 210094)

基于超图正则化受限的概念分解算法

李 雪*赵春霞 舒振球 郭剑辉

(南京理工大学计算机科学与工程学院 南京 210094)

针对概念分解(Concept Factorization, CF)算法没有同时考虑样本中存在的类别信息及数据间多元几何结构信息的问题，该文提出一种基于超图正则化受限的概念分解(Hyper-graph regularized Constrained Concept Factorization, HCCF)算法。HCCF算法通过构建一个无向加权的拉普拉斯超图正则项，提取数据间的多元几何结构信息，克服了传统图模型只能表达数据间成对关系的缺陷；同时采用硬约束的方式使样本的类别信息在低维空间中保持一致，充分利用了标记样本的类别信息。该文采用乘性迭代的方法求解HCCF算法的目标函数并证明了其收敛性。在TDT2库、Reuters库和PIE库上的实验结果表明，HCCF算法提高了聚类的准确率和归一化互信息，验证了算法的有效性。

信息处理；概念分解；聚类；硬约束；超图；流形学习

1 引言

目前，矩阵分解方法在文本聚类、数据挖掘和信息检索等方面起着重要作用[1]。基于矩阵分解的算法在处理海量文本问题时，通常把文本数据描述为高维空间中的一个点。通过有效的数据表示得到的样本数据可以在低维空间中保持原始样本在高维空间时的几何流形结构，提高算法的鉴别能力[2-4]。常用的矩阵分解算法包括奇异值分解(Singular Value Decomposition, SVD)，非负矩阵分解(Non-negative Matrix Factorization, NMF)[1]和概念分解(Concept Factorization, CF)[5]等。

文献[1]提出的NMF算法用两个非负的低秩矩阵的乘积逼近原始高维数据。针对NMF算法无法进行核化的问题，文献[5]提出了CF算法，其思想是每个聚类中心可用数据的线性组合来表示，而每个数据又可以用聚类中心的线性组合来表示。CF算法通过最小化数据间的重构误差，找到线性系数的非负解。近年来，文献[6]提出一种半监督的鉴别概念分解(Discriminative Concept Factorization, DCF)算法，DCF算法进行分类器训练时考虑了样本中存在的类别信息，但没有考虑数据间几何结构信息；文献[7]提出双图正则化的概念分解(Dual-graph regularized Concept Factorization, GCF)算法，GCF同时考虑基向量和特征向量的流形结构，但没有考虑样本类别信息；文献[8]提出一种局部一致性概念分解(Locally Consistent Concept Factorization, LCCF)算法，该算法通过构造一个传统图模型，使其在低维空间中保持了数据原有的流形结构信息，但GCF, LCCF算法均为无监督的，并且忽略了数据的高阶信息，破坏了数据内在关联性；文献[9]提出超图正则化的非负矩阵分解(Hyper-graph regularized Non-negative Matrix Factorization, HNMF)算法，实验证明HNMF聚类效果明显高于传统图模型的NMF算法。上述算法均没有同时考虑样本的类别信息和数据间的高阶关系，从而影响了最终的聚类效果。

为解决上述算法没有同时考虑类别信息和数据间多元关系的缺陷，本文提出一种基于超图正则化受限的概念分解算法，超图正则化受限的概念分解(Hyper-graph regularized Constrained Concept Factorization, HCCF)算法采用硬约束[10]方式把样本类别信息添加到目标函数中，同时，用k个具有相似属性的数据子集构建超边，建立拉普拉斯超图正则项模型，提取数据间多元几何结构信息[11]。本文采用乘性迭代方法求解HCCF的目标函数，并证明算法的收敛性，实验结果表明了算法的有效性和准确性。

2 概念分解算法和超图简介

传统图模型在点与点之间建立连接关系的边，只考虑了数据间的成对关系，即二元关系。在实际应用中，数据分布是非常复杂的，因此，基于点对的传统图模型不能有效描述数据间的复杂关系。超图扩展了传统图模型中两个顶点组建边的构图方式，以具有某种相似属性的数据子集构建超边，从而可以有效刻画数据间的高阶关系。

3 超图正则化受限的概念分解(HCCF)算法

HCCF算法结合流形学习和半监督学习的思想，采用K近邻[12](K-Nearest-Neighbor, KNN)方法选择k个顶点组成超边，构建超图[13,14]正则项保持数据的多元几何结构信息；同时把已标记样本的类别信息采用硬约束方式加入到CF算法的目标函数中，使得样本从高维空间映射到低维空间后类别信息仍保持一致。

3.1 构建超图正则项

超图G包含N个顶点，ix和jx在高维空间中是近邻点，iz和jz分别是低维空间中的近邻点，V是N个顶点在低维空间的集合。文献[14]提出超边权重计算方法。定义vD和eD是对角矩阵，分别表示顶点的度和超边的度。数据映射到低维空间后，构建超图正则项ℜ：

Tr(⋅)表示矩阵的迹，hL表示超图的拉普拉斯矩阵：其中

为了尽可能使数据集在新的表示空间中保持光滑，需要最小化超图正则项ℜ。

3.2 构建HCCF算法的目标函数

其中矩阵In-d是大小为(n-d)×(n-d)维的单位矩阵。

在高维空间中，样本xi的标签信息为cj, vi是 xi在低维空间中的表示，为确保vi的标签信息仍为cj，添加辅助矩阵Z：

为了同时考虑数据间多元几何结构信息和样本类别信息，HCCF算法将超图正则项和样本类别信息同时添加到CF目标函数式(1)中，得到HCCF算法的目标函数为

W和Z均为非负矩阵，正则项参数α≥0。下面讨论HCCF算法目标函数的求解。

3.3 HCCF目标函数求解

HCCF的目标函数同时对于W和Z来说是非凸函数，无法得到目标函数的全局最优解，但是对于单独的W或Z是凸函数，因此可以采用乘性迭代算法求解目标函数的局部最优解。根据矩阵性质：目标函数式(5)可化简为

分别对W和Z求偏导，通过Karush-Kuhn-Tucker条件，得到HCCF算法的更新迭代规则：

3.4 收敛性证明

上一小节对HCCF目标函数进行求解并求出更新规则，本节将证明目标函数式(5)在更新规则式(7)和式(8)下的迭代是收敛的。为证明收敛性，引入相关定义和引理。

定义1 当函数G(x,x′)满足下列条件：G(x, x′)≥F(x),G(x,x)=F(x)时，则称G(x,x′)是F(x)的辅助函数。

引理1 如果函数G是函数F的辅助函数，则F在下面条件下是非增的：

对式(8)，定义zab是矩阵Z的元素，Fzab表示目标函数OHCCF中与变量zab相关的函数，由于目标函数OHCCF是逐个元素进行更新的，因此首先证明Fzab在迭代式(8)下是非增的。

引理2 函数

是Fzab的辅助函数。

引理3 函数

是Fwab的辅助函数。

引理3的证明过程同引理2的证明，由于篇幅限制，此处具体证明参见引理2。

定理1 目标函数式(5)在更新迭代规则式(7)，式(8)下是非增的。当且仅当W和Z是稳定点时，目标函数值是不变的。

证明 由引理2知： 把式(10)代入式(9)得

3.5 复杂度分析

算法的复杂度常用O表示，为了准确区分本文HCCF算法和其他对比算法的计算复杂度，本节使用算术运算的方法计算算法的复杂度。由更新迭代式(2)可得CF算法的复杂度O(n2r)，HCCF算法需要计算核矩阵，复杂度为O(n2m); HCCF算法需要把具有相同属性的k个近邻点构建为一条超边，复杂度为O(n2k)。经过t次迭代更新后，HCCF复杂度为O(tn2r+n2m+n2k)。表1总结了HCCF算法与CF, LCCF, CCF算法的复杂度计算，其中，n为样本数目，m是特征值数目，r表示基向量个数，k是构建边的近邻点数。

表1 算法每次迭代的计算次数

4 实验结果与分析

聚类实验中常用准确率(ACcuracy, AC)和归一化互信息(Normalized Mutual Information, NMI)[5]作为聚类算法的评价标准。本节重点评估本文HCCF算法与NMF[1], CF[5], CNMF[10], HNMF[9], LCCF[8], CCF[15]算法在3个数据集上的结果，进行比较分析，证明了算法的有效性。

4.1 在TDT2文本库上的实验

本文实验选取TDT2文本库中样本数目大于10的样本。表2描述的是在TDT2库上7种算法的平均AC和NMI，其中，本文算法比LCCF算法平均AC和平均NMI分别提高了5.04%和6.46%，比传统CF算法的平均AC和平均NMI分别提高12.67%和15.53%。

4.2 在Reuters文本库上的实验

在Reuters文本库上的实验忽略属于多个类别的样本、选取样本数目大于10的类簇组成的实验数据集。表3描述的是在Reuters数据集上7种算法的实验结果。由表3可知，本文算法与LCCF相比，平均AC和NMI分别提高15.14%和9.07%。

表2 在TDT2库上的聚类实验(%)

表3 在Reuters库上的聚类实验(%)

4.3 在PIE人脸库上的实验

在PIE人脸库中，固定姿势和表情，在不同的照明条件下，选取11554张图像进行实验。实验结果由表4可知：本文算法与CCF算法相比，平均AC和NMI分别提高6.40%和5.41%。

4.4 参数设置

HCCF模型中需要确定创建超边时所选择的k个近邻点和正则项参数α, k取值从2～10，正则项参数α取值{10-1,100,101,102,103,104,105}，通过搜索不同参数值对实验结果的影响进行评估。图1，图2分别表明当正则项参数α变化时对聚类准确率和归一化互信息的影响。图3，图4表明当α取实验效果最优的条件下，搜索不同k值对聚类准确率和归一化互信息的影响。

表4 在PIE库上的聚类实验(%)

图1 正则项参数α对AC的影响

图2 正则项参数α对NMI的影响

图3 构建超边的顶点数k对AC的影响

图4 构建超边的顶点数k对NMI的影响

4.5 结论分析

分析4.3节和4.4节实验结果可得如下结论：

(1)NMF, CF算法没有考虑样本的类别信息，CNMF和CCF算法分别对样本类别信息采用“硬约束”的方式，确保高维空间中属于同一类簇的样本在维数约简后仍属于同一类簇。与NMF, CF相比，添加了类别信息的CNMF, CCF算法的聚类AC和NMI在3个数据集上均优于NMF, CF算法，说明考虑样本的类别信息可以提高算法的鉴别能力，但是CNMF, CCF没有利用样本的几何结构信息；

(2)NMF, CF算法没有考虑数据间的几何机构信息，HNMF算法利用超图正则项获得数据间的多元几何结构信息，LCCF算法在CF算法的目标函数中增加一个拉普拉斯图正则项，保持数据的几何流形结构信息，使得HNMF和LCCF算法的聚类AC和NMI在3个数据集上明显高于NMF和CF算法，说明考虑数据间潜在的流形结构可以提高算法的鉴别能力，但是HNMF和LCCF是无监督学习算法，忽略了样本中可能存在的类别信息；

(3)与NMF, CF算法相比，HNMF, LCCF算法分别考虑了样本的几何结构信息，CNMF, CCF算法分别考虑了样本的类别信息，从3个数据集实验结果知，CNMF和CCF的平均AC和NMI分别优于HNMF和LCCF算法，说明聚类类别数小于10时，考虑样本的类别信息比考虑样本的几何结构信息更有利于提高算法的聚类准确率；

(4)本文HCCF算法同时考虑了样本的类别信息和样本的几何结构信息，从3个数据集的实验结果来看，HCCF算法的平均AC和NMI优于其他对比算法，说明HCCF利用超图正则项保持了数据间高阶关系，因此HCCF具有更强的鉴别性；

(5)参数k大小与数据集样本分布有关，当样本分布相对分散时，较大的k值使得样本相似度降低，而当样本分布相对集中时，若参数k较小，使得具有相同结构信息的数据离散，故聚类准确率曲线先上升到最优值，如果k继续增大，会使聚类准确率下降；

(6)当参数α过大(大于10000)或过小(小于10)时，过分强调或忽略了样本的几何结构信息和类别信息，使得聚类AC下降。当α在10～10000范围内变化时在3个数据库上均可取的较好结果，说明HCCF算法具有一定的鲁棒性。

5 结束语

根据流形学习和半监督学习的思想，本文提出了基于超图正则化受限的概念分解算法。HCCF算法选择k个近邻点构建超边，计算每条超边上的权重，通过构建一个无向加权的拉普拉斯超图正则项，获得数据间固有的多元几何结构信息，解决传统图模型只能表达数据间成对关系的缺陷；同时，HCCF算法采用硬约束的方式，使得已标记样本的类别信息在低维空间中保持一致，与软约束[16]方法相比，硬约束的半监督学习没有增加参数，降低了重构误差。HCCF算法同时考虑了数据的高阶几何结构信息和样本的类别信息，增强了算法的鉴别能力。本文还给出了HCCF目标函数的求解方法、收敛性证明、算法复杂度分析以及参数选择分析，并在TDT2, Reuters和PIE数据集上进行实验，证明了HCCF算法的有效性。但是，HCCF模型中参数k和超图正则项参数α需要通过区间搜索得到最优值，因此如何自适应地选择k个节点构建超边以及有效选择α是今后研究的重点方向之一。

[1] Xu Wei, Liu Xin, and Gong Yi-hong. Document clustering based on non-negative matrix factorization[C]. Annual ACM SIGIR Conference, Toronto, Canada, 2003: 267-273.

[2] Li Ze-chao, Liu Jing, and Lu Han-qing. Structure preserving non-negative matrix factorization for dimensionality reduction[J]. Computer Vision and Image Understanding, 2013, 117(9): 1175-1189.

[3] Yu Jun, Liu Dong-quan, Tao Da-cheng, et al.. Complex object correspondence construction in two-dimensional animation[J]. IEEE Transactions on Image Processing, 2011, 20(11): 3257-3269.

[4] Yu Jun, Tao Da-peng, Li Jonathan, et al.. Semantic preserving distance metric learning and applications[J]. Information Sciences, 2014, 281(10): 674-686.

[5] Xu Wei and Gong Yi-hong. Document clustering by concept factorization[C]. ACM SIGIR, Sheffield, UK, 2004: 202-209.

[6] Hua Wei and He Xiao-fei. Discriminative concept factorization for data representation[J]. Neurocomputing, 2011, 74(10): 3800-3807.

[7] Ye Jun and Jin Zhong. Dual-graph regularized concept factorization for clustering[J]. Neurocomputing, 2014, 138(3): 120-130.

[8] Cai. Deng, He Xiao-fei, and Han Jia-wei. Locally consistent concept factorization for document clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(6): 902-913.

[9] Zeng Kun, Yu Jun, Li Cui-hua, et al.. Image clustering by hyper-graph regularized non-negative matrix factorization[J]. IEEE Transactions on Neurocomputing, 2014, 138(22): 209-217

[10] Liu Hai-feng, Wu Zhao-hui, Li Xue-long, et al.. Constrained non-negative matrix factorization for image representation[J]. IEEE Transctions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1299-1311.

[11] Yu Jun, Rui Yong, and Chen Bo. Exploiting Click Constraints and multiview features for image re-ranking[J]. IEEE Transactions on Multimedia, 2014, 16(1): 159-168.

[12] Yu Jun, Tao Da-cheng, and Wang Meng. Adaptive hypergraph learning and its application in image classification[J]. IEEE Transactions on Image Processing, 2012, 21(7): 3262-3272.

[13] Hong Chao-qun, Yu Jun, Li Jonathan, et al.. Multi-view hypergraph learning by patch alignment framework[J]. IEEE Transctions on Neurocomputing, 2013, 118(2013): 79-86.

[14] Huang Yu-chi, Liu Qing-shan, Zhang Shao-ting, et al.. Image retrieval via probabilistic hypergraph ranking[C]. Proceedings of the International Conference on Computer Vision and Pattern Recognition, San Francisco, 2010: 3376-3383.

[15] Liu Hai-feng, Yang Gen-mao, Wu Zhao-hui, et al..Constrained concept factorization for image representation[J]. IEEE Transactions on Cybernetics, 2014, 44(7): 1214-1224.

[16] He Yang-cheng, Lu Hong-tao, Huang Lei, et al.. Non-negative matrix factorization with pair-wise constraints and graph Laplacian[J]. Neural Processing Letters, 2014, 12(7): 82-91.

李 雪： 女，1989年生，博士生，研究方向为模式识别、图像处理等.

赵春霞： 女，1964年生，教授，研究方向为模式识别、机器人控制、人工智能、图像处理等.

舒振球： 男，1985年生，博士生，研究方向为机器学习、模式识别.

郭剑辉： 男，1983年生，副教授，研究方向为机器学习、智能机器人、目标跟踪及数据融合.

Hyper-graph Regularized Constrained Concept Factorization Algorithm

Li Xue Zhao Chun-xia Shu Zhen-qiu Guo Jian-hui

(College of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China)

The Concept Factorization (CF) algorithm can not take into account the label information and the multi-relationship of samples simultaneously. In this paper, a novel algorithm called Hyper-graph regularized Constrained Concept Factorization (HCCF) is proposed, which extracts the multi-geometry information of samples by constructing an undirected weighted hyper-graph Laplacian regularize term, hence overcomes the deficiency that traditional graph model expresses pair-wise relationship only. Meanwhile, HCCF takes full advantage of the label information of labeled samples as hard constraints, and it preserves label consistent in low-dimensional space. The objective function of HCCF is solved by the iterative multiplicative updating algorithm and its convergence is also proved. The experimental results on TDT2, Reuters, and PIE data sets show that the proposed approach achieves better clustering performance in terms of accuracy and normalized mutual information, and the effectiveness of the proposed approach is verified.

Information processing; Concept Factorization(CF); Cluster; Hard constraints; Hyper-graph; Manifold learning

TP391

A

1009-5896(2015)03-0509-07

10.11999/JEIT140799

2014-06-17收到，2014-10-15改回

国家自然科学基金(61272220, 61101197, 90820306)，中国博士后科学基金(2014M551599)，江苏省社会安全图像与视频理解重点实验室基金(30920130122006)和江苏省普通高校研究生科研创新计划项目(KYLX_0383)资助课题

*通信作者：李雪 lixue_angel@163.com