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

李飛 杜亮 任超宏

摘 要：非負矩陣分解（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.