基于全局融合的多核概念分解算法

李飞 杜亮 任超宏

摘 要：非负矩阵分解（NMF）算法仅能用于对原始非负数据寻找低秩近似，而概念分解（CF）算法将矩阵分解模型扩展到单个非线性核空间，提升了矩阵分解算法的学习能力和普适性。针对无监督环境下概念分解面临的如何设计或选择合适核函数这一问题，提出基于全局融合的多核概念分解（GMKCF）算法。同时输入多种候选核函数，在概念分解框架下基于全局线性权重融合对它们进行学习，以得出质量高稳定性好的聚类结果，并解决概念分解模型面臨核函数选择的问题。采用交替迭代的方法对新模型进行求解，证明了算法的收敛性。

将该算法与基于核的K-均值（KKM）、谱聚类（SC）、KCF（Kernel Concept Factorization）、Coreg（Co-regularized multi-view spectral clustering）、RMKKM（Robust Multiple KKM）在多个真实数据库上的实验结果表明，该算法在数据聚类方面优于对比算法。

关键词：多核学习;概念分解;矩阵分解;多核聚类;全局融合

中图分类号：TP181

文献标志码：A

文章编号：1001-9081（2019）04-1021-06

Abstract： Non-negative Matrix Factorization （NMF） algorithm can only be used to find low rank approximation of original non-negative data while Concept Factorization （CF） algorithm extends matrix factorization to single non-linear kernel space， improving learning ability and adaptability of matrix factorization. In unsupervised environment， to design or select proper kernel function for specific dataset， a new algorithm called Globalized Multiple Kernel CF （GMKCF） was proposed. Multiple candidate kernel functions were input in the same time and learned in the CF framework based on global linear fusion， obtaining a clustering result with high quality and stability and solving the problem of kernel function selection that the CF faced. The convergence of the proposed algorithm was verified by solving the model with alternate iteration. The experimental results on several real databases show that the proposed algorithm outperforms  comparison algorithms in data clustering， such as Kernel K-Means （KKM）， Spectral Clustering （SC）， Kernel CF （KCF）， Co-regularized multi-view spectral clustering （Coreg）， and Robust Multiple KKM （RMKKM）.

Key words： multiple kernel learning; Concept Factorization （CF）; matrix factorization; multiple kernel clustering; global fusion

0 引言

数据挖掘从看似无序的数据中寻找有序、有价值的信息。聚类分析是数据挖掘、机器学习中的一项重要技术，也是国内外学者研究的一个重点领域。聚类技术可用来探索数据的内部结构，并就其某种相关关系进行挖掘，因而在很多领域中得到广泛应用，例如：在电子商务中，应用聚类算法可以发现不同客户群体，有利于寻找潜在市场;在生物学领域，可以对基因、蛋白质等进行聚类研究，从而获取对其结构的深入认识;在互联网上，可以对微博、新闻中的文档进行聚类研究，从而进行热点事件发现等。

根据聚类算法的输入数据类型分类，聚类算法可以分为数值型算法（如K-means[1]、非负矩阵分解（Non-negative Matrix Factorization， NMF）[2]等）、离散型（如AT-DC[3]）、关系型（如NCut[4]、仿射传播AP[5]）和混合型（如图正则的NMF（Graph regularized NMF， GNMF）[6]）算法等。根据输出结果，聚类算法分为层次聚类和划分式聚类[1]。根据簇的描述形式，聚类算法可分为基于原型的方法（也叫簇代表元，代表性算法有K-means， K-medoids等）和基于模型的方法（代表性算法有高斯混合模型（Gaussian Mixture Model， GMM）[7]）。

近年来研究人员提出许多方法进一步提高非负矩阵分解算法的效果。文献[6]提出利用数据流形结构提升聚类结果;文献[8]研究矩阵分解的稀疏性提高结果的可解释性;文献[9]研究噪声数据上的矩阵分解提高分解结果的鲁棒性。文献[10]提出概念分解（Concept Factorization， CF）方法将矩阵分解从线性原始空间扩展到非线性核空间并用于文本聚类，文献[11]提出基于图正则的概念分解算法，文献[12]进一步提出自适应邻居正则化的概念分解算法，文献[13-15]提出基于多图/多层/多视图的正则化的概念分解算法，文献[16-18]提出新型单视图数据的正则化概念分解算法。值得指出的是这类正则化方法通常需要引入额外的参数用于平衡概念分解目标函数和正则目标，但实际应用中如何设置较为准确的参数是比较困难的。

文献[10]提出的核概念分解方法在实际应用中面临的核心问题之一是针对特定任务和数据集如何设计和选择合适的核函数。需要进一步指出的是，由于缺乏数据标签等监督信息，核函数选择在无监督学习任务中变得更加困难。

为了减轻核函数选择带来的困难，本文提出在无监督多核学习框架中通过全局线性加权方法从一系列初始给定的核矩阵中学习聚类质量更高、稳定性更好的核函数。针对本文提出的多核概念分解模型，推导和设计了对应的迭代式优化求解算法——基于全局融合的多核概念分解（Globalized Multiple Kernel CF， GMKCF）算法，并证明该算法的收敛性以及算法的时间和空间复杂度。本文提出的多核概念分解模型没有引入额外的超参数，降低了算法在实际应用中实施部署的难度。

多个基准数据集上的聚类实验结果表明多核聚类方法明显优于单核平均结果，验证了多核学习可以提升聚类算法性能。本文提出的多核概念分解在聚类准确性、归一化互信息和聚类纯度上的性能优于对比多核聚类方法。

1 相关工作

1.1 非负矩阵分解

针对非负值矩阵数据X∈Rd×n，Lee等[2]于1999年在《Nature》上正式提出了非负矩阵分解的基本概念。非负矩阵分解的认知基础是：对整体的感知由基于对组成整体的部分（局部）。NMF通过非负约束纯加性的感知过程刻画出数据的组成部分和数据如何由局部感知构成的本质。该方法用两个低秩非负矩的乘积阵UVT近似原始非负数据，其中U∈Rd×k，V∈Rn×k。非负矩阵分解方法对应的最优结果可以通过求解以下优化问题[19]获得：

从式（1）可看出：每一个样本xi可以通过U，V的线性合并得到，即xi=∑k ukvik。因此，矩阵U可以看作是一组非负基向量，而矩阵V可以看作数据在基矩阵U下新的表示。

上述优化问题是关于联合（U，V）的非凸优化问题，因此很难用非线性优化方法得到全局最优解。然而对于仅关于U或者仅关于V的子问题，仍然是一个凸优化问题。其局部最优解可以通过分块坐标轮换法分别求解。通用的非负矩阵分解求解算法通过以下乘法更新公式获得：

1.2 概念分解

Xu等在文献[10]中提出概念分解算法。在概念分解模型中，分解后的基向量u要求通过对原始空间样本的非负线性组合得到，其对应的优化问题可以写成：

2 本文算法

上述提到的核概念分解算法仅适用于单核数据聚类问题;然而，核方法面临的核心问题之一是针对特定任务和数据集如何设计和选择合适的核函数。需要进一步指出的是，由于缺乏数据标签等监督信息，核函数选择在无监督学习任务中变得更加困难。

为了减轻核函数选择带来的困难，本文提出在无监督多核学习框架中通过全局线性加权方法从一系列初始给定的核矩阵中学习聚类质量更高、稳定性更好的核函数。

2.1 多核概念分解

假设一共给定m个不同的核关系数据用于聚类过程{Ki}mi=1，与此对应的是m个不同的特征空间{Hi}mi=1。为了合并这些核空间并且使得合并后的核矩阵仍然满足Mercer条件，可以采用基于非负全局权重线性加权的方式，即合并后的特征空间可以表示为：

2.2 多核概念分解模型求解算法

首先需要指出的是，上述多核概念分解模型整体对于所有待求变量仍然是一个非凸优化问题，但是对于单个变量的各子优化问题都是凸优化问题。为此，本文提出迭代式求解算法对整体问题进行求解，并采用分块坐标轮换法分别对每个变量对应的子优化问题进行单独求解。最终通过求解一系列子优化问题，可以获得对应的局部最优解。

2.2.4 多核概念算法

算法1 全局多核概念分解算法。

后處理：利用K-means算法对多核低秩表示V进行二次聚类获得高质量的离散化聚类结果。

2.2.5 算法收敛性证明

式（7）中的全局多核概念分解算法是一个关于联合（{Ui}mi=1，V，w）的非凸优化问题，因此很难用非线性优化方法得到全局最优解。然而对于仅关于{Ui}mi=1或者仅关于V 或者仅关于w的子问题，仍然是一个凸优化问题。通过分块坐标轮换法的迭代式求解可以使整体目标函数单调下降。并且可以很明显看出式（7）的目标函数是有下界的。因此，整体求解算法的收敛性可以得到保障。

具体来讲，容易看出式（7）的目标函数是有下界的（下界为0），并且式（7）的函数值随着算法迭代每一步都是非增的（Non-increasing）。本文引入非负矩阵分解（NMF）和概念分解（CF）模型乘法更新过程（Multiplicative update rule）中常见的辅助函数（Auxiliary function）定义[10]。因为非负因子U的更新过程和非负因子V更新类似，本文仅给出求解非负因子V时的辅助函数证明。

此外，式（16）中关于w的问题是凸优化问题，式（17）可以获得最优解。

2.2.6 算法复杂性说明

初始阶段， 本文算法需要计算m个核矩阵，对应的计算复杂性是O（mn2d），其中n是样本个数，d是特征个数。每次迭代过程中的计算量分别为：1）更新变量U，其中需要计算P+和P-，对应的计算复杂性为O（n2k+k2n），更新U的复杂性是O（n2k）。

2）更新变量V，其中需要计算Q+和Q-，对应的计算复杂性为O（n2k+k2n），更新V的复杂性是O（n2k）。

3）更新变量w，对应的计算复杂性为O（m（n2k+k2n））。

4）更新变量Kw，对应的计算复杂性为O（mn2）。

假设迭代算法在迭代t次后收敛，多核概念分解的整体复杂度表示为O（mn2d+n2t（k+m））。可以看出，多核概念分解整体算法复杂性和单核概念分解在同一量级。

3 实验与结果分析

本文实验通过基准测试数据集上的聚类结果对比来验证本文提出的多核方法在聚类问题上的有效性。

实验平台的配置：PC为Intel Core i5处理器，8GB内存，120GB硬盘;操作系统为Windows 10;编程环境为Matlab 2015a。

3.1 数据集的选择

本文分别选择了BBC、TR31、K1B、WebKB四个数据集作为测试基准数据集。这些数据集经常被用于评估聚类算法的性能，数据集的统计信息如表1所示。

BBC数据集包含了来自BBC新闻网站提供的2225份文件，对应于2004—2005年5个主题领域的故事，共有5类标签：商业、娱乐、政治、体育、科技。

TR31数据集来自TREC收集的文本数据集，包含927个文本，分为7个类别。

K1B数据集来自WebACE项目，包括2340篇文章，这些文章来自于路透新闻的20个类别中，其中每个文档对应于Yahoo！的主題层次结构中列出的网页。

WebKB数据集包含了约6000个从4所高校（康奈尔大学、德克萨斯大学、华盛顿大学、威斯康星大学）的计算机科学部门收集的网页。每个网页都标有一个标签：学生、教授、课程、项目、人员、部门，以及其他。

和其他多核学习方法中的策略类似，本文使用了12种不同的核函数作为多核学习的输入。这些核函数包括7个不同带宽的径向基函数（Radial Basis Function，RBF）核函数k（x， y）=exp（-‖x-y‖22δ2）d，其中令δ=tD0，且D0是样本两两之间距离的平均值，而t的变化范围包括{0.01，0.05，0.1，1，10，50，100};4个多项式核函数k（x， y）=（a+xTiy）b，其中a的取值范围包括{0，1}，b的取值范围包括{2，4};1个余弦核函数k（x， y）=xTy‖x‖·‖y‖。最后，所有的核函数都又经过了标准化k（x， y）=k（x， y）k（x，x）k（y， y），并且被进一步缩放到区间[0，1]内。

3.2 对比方法

本文实验是多核数据聚类实验，实验中对比了单核方法和多核方法。采用的单核方法包括：基于核的K-均值（Kernel K-Means， KKM）、谱聚类（Spectual Clustering， SC）、KCF（Kernel CF）。

采用的多核方法包括：Coreg（Co-regularized multi-view spectral clustering）[20]、RMKKM（Robust Multiple KKM）[21]，以及本文GMKCF算法。

针对多核实验数据，单核方法可以获得多组实验结果，为了准确刻画单核方法在不同核函数上的性能，

本文实验采用单核方法在多个核函数上聚类结果的平均值。

根据文献[20-21]中的实验结果，Coreg在本文实验中的参数设置为0.1，RMKKM的实验参数设置为0.3。概念因子的个数设置为数据集中类的个数。

聚类中簇的个数设置为数据集中真实类别的个数。SC和Coreg获得样本低维表示后都采用K-means算法最终得到离散化的聚类结果。针对聚类算法需要初始化的问题， 本文实验采用随机值对算法进行初始化，重复实验20次并报告对应的平均值。

3.3 评价指标

因本文实验所采用的数据集类别标签已知，本文选择三个外部评价指标来评估算法在聚类问题上的性能，各评价指标介绍如下：

而map（·）是置换映射函数，它将簇标签映射到类标签。最佳映射可以通过Kuhn-Munkres算法获取。ACC是0～1的值，ACC的值越大说明聚类效果越好。

其中：H（C）和H（C′）分别是类C和簇C′对应的信息熵。容易验证NMI位于0～1，并且NMI的值越大说明聚类效果越好。

3）聚类纯度（Purity）是一种简单的聚类评价方法，只需计算正确聚类的样本数占样本总数的比例，其计算方法如下：purity=1n∑kmax（c′k，cj）

其中：用C={c1，c2，…，ck}表示真实标签中类的集合;用C′={c′1，c′2，…，c′k}表示聚类算法获得的簇的集合。Purity同样位于0～1，并且Purity的值越大说明聚类效果越好。

3.4 结果与分析

表2～4分别列出了不同的聚类方法在这些数据集上聚类准确性、归一化互信息和聚类纯度的结果。

实验结果表明多核方法（Coreg、RMKKM和GMKCF）普遍优于单核方法（KKM、SC和KCF）。从表2聚类准确性指标可看出多核方法在多个数据集上的平均结果达到0.5809，而单核方法的平均结果为0.4915，多核方法在聚类准确性上的平均提升达到了18.2%;从表3归一化互信息指标可看出多核方法在多个数据集上的平均结果达到0.3741，而单核方法的平均结果为0.2463，多核方法在归一化互信息上的平均提升达到了51.8%;从表4聚类纯度指标可看出多核方法在多个数据集上的平均结果达到0.6599，而单核方法的平均结果为0.5766，多核方法在归一化互信息上的平均提升达到了14.4%。

实验结果表明本文提出的多核概念分解方法要优于其他单核方法和多核方法。三种不同指标上GMKCF在多个数据集上的平均结果明显高于其他方法。

具体来看，GMKCF在聚类准确性上达到0.6145，而第二名的算法Coreg为0.5664，性能提升为8.5%。GMKCF在归一化互信息上达到0.4344，第二名为0.4032，性能提升为7.7%;GMKCF在聚类纯度上达到0.6982，第二名为0.6756，性能提升为3.3%。

需要指出的是多核方法Coreg和RMKKM都帶有超参数，无监督聚类问题中如何选择有效的超参数本身就是一个非常困难的问题。而本文提出的GMKCF算法无需设置其他特定参数，极大提升了算法的实际可用性。

此外，本文提出的GMKCF算法在空间复杂度上和其他多核方法类似，都是O（n2），从时间复杂度看GMKCF和RMKKM都是O（n2），而Coreg的时间复杂度为O（n3）;并且GMKCF和RMKKM中主要涉及矩阵和向量的基本操作，可以借助MapReduce等框架容易实现分布式部署，而Coreg由于需要计算特征空间导致分布式实现较为困难。

实验结果表明，本文提出的多核概念分解方法在多种聚类评价指标上的结果要优于其他单核和多核聚类方法，无需设置超参数，并且算法复杂度较低，容易分布式部署。

4 结语

针对核概念分解模型在实际应用中面临的核函数选择问题，本文提出基于多核全局融合的概念分解模型。与核概念分解模型类似，本文推导出对应的迭代式乘法更新公式作为求解算法并且证明算法的收敛性。多个基准数据集上的实验结果表明，本文算法在不引入额外超参数的情况下能够有效提升核分解模型在实际应用中的聚类性能。未来，我们将进一步研究如何在分布式环境中部署实施多核概念分解算法。

参考文献（References）

[1] HAN J， KAMBER M， PEI J. Data Mining： Concepts and Techniques[M]. 3rd ed. San Francisco： Margan Kaufmann， 2011： 525-527.

[2] LEE D D， HSEBASTIAN S S. Learning the parts of objects by non-negative matrix factorization [J]. Nature， 1999， 401： 788-791.

[3] CESARIO E， MANCO G， ORTALE R. Top-down parameter-free clustering of high-dimensional categorical data [J]. IEEE Transactions on Knowledge and Data Engineering， 2007， 19（12）： 1607-1624.

[4] SHI J， MALIK J. Normalized cuts and image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（8）： 888-905.

[5] FREY B J， DUECK D. Clustering by passing messages between data points[J]. Science， 2007， 315（5814）： 972-976.

[6] CAI D， HE X， HAN J， et al. Graph regularized nonnegative matrix factorization for data representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（8）： 1548-1560.

[7] BISHOP C M. Pattern Recognition and Machine Learning[M]. 2nd ed. New York： Springer， 2010： 291-292.

[8] HOYER P O. Non-negative matrix factorization with sparseness constraints [EB/OL]. [2018-05-10]. https：//arxiv.org/abs/cs/0408 058.

[9] DU L， LI X， SHEN Y. Robust nonnegative matrix factorization via half-quadratic minimization [C]// Proceedings of the 2012 IEEE 12th International Conference on Data Mining. Piscataway， NJ： IEEE， 2012： 201-210.

[10] XU W， GONG Y. Document clustering by concept factorization [C]// SIGIR 2004： Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2004： 202-209.

[11] CAI D， HE X， HAN J. Locally consistent concept factorization for document clustering [J]. IEEE Transactions on Knowledge and Data Engineering， 2011， 23（6）： 902-913.

[12] PEI X， CHEN C， GONG W. Concept factorization with adaptive neighbors for document clustering [J]. IEEE Transactions on Neural Networks and Learning Systems， 2018， 29（2）： 343-352.

[13] LEE D D， SEUNG H S. Algorithms for non-negative matrix factorization [EB/OL]. [2018-05-10]. http：//papers.nips.cc/paper/1861-algorithms-for-non-negative-matrix-factorization.pdf.

[14] KUMAR A， RAI P， DAUM H. Co-regularized multi-view spectral clustering [EB/OL]. [2018-05-10]. http：//www.cs.utah.edu/～piyush/recent/spectral-nips11.pdf.

[15] DU L， ZHOU P， SHI L， et al. Robust multiple kernel k-means clustering usingL21-norm [C]// Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2015： 3476-3482.

[16] LI X， SHEEN X， SHU Z， et al. Graph regularized multilayer concept factorization for data representation [J]. Neurocomputing， 2017， 238： 139-151.

[17] ZHAN K， SHI J， WANG J， et al. Adaptive structure concept factorization for multiview clustering [J]. Neural Computation， 2018， 30（2）： 1080-1103.

[18] SHU Z， WU X， HUANG P， et al. Multiple graph regularized concept factorization with adaptive weights [J]. IEEE Access， 2018， 6： 64938-64945.

[19] MA S， ZHANG L， HU E， et al. Self-representative manifold concept factorization with adaptive neighbors for clustering [C]// IJCAI 2018： Proceedings of the 27th International Joint Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2018： 2539-2545.

[20] KUMAR A， RAI P， DAUM H， Ⅲ. Co-regularized multi-view spectral clustering [C]// NIPS 2011： Proceedings of the 24th International Conference on Neural Information Processing Systems.  New York： ACM， 2011： 1413-1421.

[21] YAN W， ZHANG B， MA S， et al. A novel regularized concept factorization for document clustering [J]. Knowledge-based Systems， 2017， 135： 147-158.