基于超圖正則化受限的概念分解算法

李 雪趙春霞 舒振球 郭劍輝

(南京理工大學計算機科學與工程學院 南京 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