李 雪趙春霞 舒振球 郭劍輝

(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094)

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

李 雪*趙春霞 舒振球 郭劍輝

(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094)

針對(duì)概念分解(Concept Factorization, CF)算法沒有同時(shí)考慮樣本中存在的類別信息及數(shù)據(jù)間多元幾何結(jié)構(gòu)信息的問題，該文提出一種基于超圖正則化受限的概念分解(Hyper-graph regularized Constrained Concept Factorization, HCCF)算法。HCCF算法通過構(gòu)建一個(gè)無(wú)向加權(quán)的拉普拉斯超圖正則項(xiàng)，提取數(shù)據(jù)間的多元幾何結(jié)構(gòu)信息，克服了傳統(tǒng)圖模型只能表達(dá)數(shù)據(jù)間成對(duì)關(guān)系的缺陷；同時(shí)采用硬約束的方式使樣本的類別信息在低維空間中保持一致，充分利用了標(biāo)記樣本的類別信息。該文采用乘性迭代的方法求解HCCF算法的目標(biāo)函數(shù)并證明了其收斂性。在TDT2庫(kù)、Reuters庫(kù)和PIE庫(kù)上的實(shí)驗(yàn)結(jié)果表明，HCCF算法提高了聚類的準(zhǔn)確率和歸一化互信息，驗(yàn)證了算法的有效性。

信息處理；概念分解；聚類；硬約束；超圖；流形學(xué)習(xí)

1 引言

目前，矩陣分解方法在文本聚類、數(shù)據(jù)挖掘和信息檢索等方面起著重要作用[1]?；诰仃嚪纸獾乃惴ㄔ谔幚砗Ａ课谋締栴}時(shí)，通常把文本數(shù)據(jù)描述為高維空間中的一個(gè)點(diǎn)。通過有效的數(shù)據(jù)表示得到的樣本數(shù)據(jù)可以在低維空間中保持原始樣本在高維空間時(shí)的幾何流形結(jié)構(gòu)，提高算法的鑒別能力[2-4]。常用的矩陣分解算法包括奇異值分解(Singular Value Decomposition, SVD)，非負(fù)矩陣分解(Non-negative Matrix Factorization, NMF)[1]和概念分解(Concept Factorization, CF)[5]等。

文獻(xiàn)[1]提出的NMF算法用兩個(gè)非負(fù)的低秩矩陣的乘積逼近原始高維數(shù)據(jù)。針對(duì)NMF算法無(wú)法進(jìn)行核化的問題，文獻(xiàn)[5]提出了CF算法，其思想是每個(gè)聚類中心可用數(shù)據(jù)的線性組合來表示，而每個(gè)數(shù)據(jù)又可以用聚類中心的線性組合來表示。CF算法通過最小化數(shù)據(jù)間的重構(gòu)誤差，找到線性系數(shù)的非負(fù)解。近年來，文獻(xiàn)[6]提出一種半監(jiān)督的鑒別概念分解(Discriminative Concept Factorization, DCF)算法，DCF算法進(jìn)行分類器訓(xùn)練時(shí)考慮了樣本中存在的類別信息，但沒有考慮數(shù)據(jù)間幾何結(jié)構(gòu)信息；文獻(xiàn)[7]提出雙圖正則化的概念分解(Dual-graph regularized Concept Factorization, GCF)算法，GCF同時(shí)考慮基向量和特征向量的流形結(jié)構(gòu)，但沒有考慮樣本類別信息；文獻(xiàn)[8]提出一種局部一致性概念分解(Locally Consistent Concept Factorization, LCCF)算法，該算法通過構(gòu)造一個(gè)傳統(tǒng)圖模型，使其在低維空間中保持了數(shù)據(jù)原有的流形結(jié)構(gòu)信息，但GCF, LCCF算法均為無(wú)監(jiān)督的，并且忽略了數(shù)據(jù)的高階信息，破壞了數(shù)據(jù)內(nèi)在關(guān)聯(lián)性；文獻(xiàn)[9]提出超圖正則化的非負(fù)矩陣分解(Hyper-graph regularized Non-negative Matrix Factorization, HNMF)算法，實(shí)驗(yàn)證明HNMF聚類效果明顯高于傳統(tǒng)圖模型的NMF算法。上述算法均沒有同時(shí)考慮樣本的類別信息和數(shù)據(jù)間的高階關(guān)系，從而影響了最終的聚類效果。

為解決上述算法沒有同時(shí)考慮類別信息和數(shù)據(jù)間多元關(guān)系的缺陷，本文提出一種基于超圖正則化受限的概念分解算法，超圖正則化受限的概念分解(Hyper-graph regularized Constrained Concept Factorization, HCCF)算法采用硬約束[10]方式把樣本類別信息添加到目標(biāo)函數(shù)中，同時(shí)，用k個(gè)具有相似屬性的數(shù)據(jù)子集構(gòu)建超邊，建立拉普拉斯超圖正則項(xiàng)模型，提取數(shù)據(jù)間多元幾何結(jié)構(gòu)信息[11]。本文采用乘性迭代方法求解HCCF的目標(biāo)函數(shù)，并證明算法的收斂性，實(shí)驗(yàn)結(jié)果表明了算法的有效性和準(zhǔn)確性。

2 概念分解算法和超圖簡(jiǎn)介

傳統(tǒng)圖模型在點(diǎn)與點(diǎn)之間建立連接關(guān)系的邊，只考慮了數(shù)據(jù)間的成對(duì)關(guān)系，即二元關(guān)系。在實(shí)際應(yīng)用中，數(shù)據(jù)分布是非常復(fù)雜的，因此，基于點(diǎn)對(duì)的傳統(tǒng)圖模型不能有效描述數(shù)據(jù)間的復(fù)雜關(guān)系。超圖擴(kuò)展了傳統(tǒng)圖模型中兩個(gè)頂點(diǎn)組建邊的構(gòu)圖方式，以具有某種相似屬性的數(shù)據(jù)子集構(gòu)建超邊，從而可以有效刻畫數(shù)據(jù)間的高階關(guān)系。

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

HCCF算法結(jié)合流形學(xué)習(xí)和半監(jiān)督學(xué)習(xí)的思想，采用K近鄰[12](K-Nearest-Neighbor, KNN)方法選擇k個(gè)頂點(diǎn)組成超邊，構(gòu)建超圖[13,14]正則項(xiàng)保持?jǐn)?shù)據(jù)的多元幾何結(jié)構(gòu)信息；同時(shí)把已標(biāo)記樣本的類別信息采用硬約束方式加入到CF算法的目標(biāo)函數(shù)中，使得樣本從高維空間映射到低維空間后類別信息仍保持一致。

3.1 構(gòu)建超圖正則項(xiàng)

超圖G包含N個(gè)頂點(diǎn)，ix和jx在高維空間中是近鄰點(diǎn)，iz和jz分別是低維空間中的近鄰點(diǎn)，V是N個(gè)頂點(diǎn)在低維空間的集合。文獻(xiàn)[14]提出超邊權(quán)重計(jì)算方法。定義vD和eD是對(duì)角矩陣，分別表示頂點(diǎn)的度和超邊的度。數(shù)據(jù)映射到低維空間后，構(gòu)建超圖正則項(xiàng)?：

Tr(?)表示矩陣的跡，hL表示超圖的拉普拉斯矩陣：其中

為了盡可能使數(shù)據(jù)集在新的表示空間中保持光滑，需要最小化超圖正則項(xiàng)?。

3.2 構(gòu)建HCCF算法的目標(biāo)函數(shù)

其中矩陣In-d是大小為(n-d)×(n-d)維的單位矩陣。

在高維空間中，樣本xi的標(biāo)簽信息為cj, vi是 xi在低維空間中的表示，為確保vi的標(biāo)簽信息仍為cj，添加輔助矩陣Z：

為了同時(shí)考慮數(shù)據(jù)間多元幾何結(jié)構(gòu)信息和樣本類別信息，HCCF算法將超圖正則項(xiàng)和樣本類別信息同時(shí)添加到CF目標(biāo)函數(shù)式(1)中，得到HCCF算法的目標(biāo)函數(shù)為

W和Z均為非負(fù)矩陣，正則項(xiàng)參數(shù)α≥0。下面討論HCCF算法目標(biāo)函數(shù)的求解。

3.3 HCCF目標(biāo)函數(shù)求解

HCCF的目標(biāo)函數(shù)同時(shí)對(duì)于W和Z來說是非凸函數(shù)，無(wú)法得到目標(biāo)函數(shù)的全局最優(yōu)解，但是對(duì)于單獨(dú)的W或Z是凸函數(shù)，因此可以采用乘性迭代算法求解目標(biāo)函數(shù)的局部最優(yōu)解。根據(jù)矩陣性質(zhì)：目標(biāo)函數(shù)式(5)可化簡(jiǎn)為

分別對(duì)W和Z求偏導(dǎo)，通過Karush-Kuhn-Tucker條件，得到HCCF算法的更新迭代規(guī)則：

3.4 收斂性證明

上一小節(jié)對(duì)HCCF目標(biāo)函數(shù)進(jìn)行求解并求出更新規(guī)則，本節(jié)將證明目標(biāo)函數(shù)式(5)在更新規(guī)則式(7)和式(8)下的迭代是收斂的。為證明收斂性，引入相關(guān)定義和引理。

定義1 當(dāng)函數(shù)G(x,x′)滿足下列條件：G(x, x′)≥F(x),G(x,x)=F(x)時(shí)，則稱G(x,x′)是F(x)的輔助函數(shù)。

引理1 如果函數(shù)G是函數(shù)F的輔助函數(shù)，則F在下面條件下是非增的：

對(duì)式(8)，定義zab是矩陣Z的元素，F(xiàn)zab表示目標(biāo)函數(shù)OHCCF中與變量zab相關(guān)的函數(shù)，由于目標(biāo)函數(shù)OHCCF是逐個(gè)元素進(jìn)行更新的，因此首先證明Fzab在迭代式(8)下是非增的。

引理2 函數(shù)

是Fzab的輔助函數(shù)。

引理3 函數(shù)

是Fwab的輔助函數(shù)。

引理3的證明過程同引理2的證明，由于篇幅限制，此處具體證明參見引理2。

定理1 目標(biāo)函數(shù)式(5)在更新迭代規(guī)則式(7)，式(8)下是非增的。當(dāng)且僅當(dāng)W和Z是穩(wěn)定點(diǎn)時(shí)，目標(biāo)函數(shù)值是不變的。

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

3.5 復(fù)雜度分析

算法的復(fù)雜度常用O表示，為了準(zhǔn)確區(qū)分本文HCCF算法和其他對(duì)比算法的計(jì)算復(fù)雜度，本節(jié)使用算術(shù)運(yùn)算的方法計(jì)算算法的復(fù)雜度。由更新迭代式(2)可得CF算法的復(fù)雜度O(n2r)，HCCF算法需要計(jì)算核矩陣，復(fù)雜度為O(n2m); HCCF算法需要把具有相同屬性的k個(gè)近鄰點(diǎn)構(gòu)建為一條超邊，復(fù)雜度為O(n2k)。經(jīng)過t次迭代更新后，HCCF復(fù)雜度為O(tn2r+n2m+n2k)。表1總結(jié)了HCCF算法與CF, LCCF, CCF算法的復(fù)雜度計(jì)算，其中，n為樣本數(shù)目，m是特征值數(shù)目，r表示基向量個(gè)數(shù)，k是構(gòu)建邊的近鄰點(diǎn)數(shù)。

表1 算法每次迭代的計(jì)算次數(shù)

4 實(shí)驗(yàn)結(jié)果與分析

聚類實(shí)驗(yàn)中常用準(zhǔn)確率(ACcuracy, AC)和歸一化互信息(Normalized Mutual Information, NMI)[5]作為聚類算法的評(píng)價(jià)標(biāo)準(zhǔn)。本節(jié)重點(diǎn)評(píng)估本文HCCF算法與NMF[1], CF[5], CNMF[10], HNMF[9], LCCF[8], CCF[15]算法在3個(gè)數(shù)據(jù)集上的結(jié)果，進(jìn)行比較分析，證明了算法的有效性。

4.1 在TDT2文本庫(kù)上的實(shí)驗(yàn)

本文實(shí)驗(yàn)選取TDT2文本庫(kù)中樣本數(shù)目大于10的樣本。表2描述的是在TDT2庫(kù)上7種算法的平均AC和NMI，其中，本文算法比LCCF算法平均AC和平均NMI分別提高了5.04%和6.46%，比傳統(tǒng)CF算法的平均AC和平均NMI分別提高12.67%和15.53%。

4.2 在Reuters文本庫(kù)上的實(shí)驗(yàn)

在Reuters文本庫(kù)上的實(shí)驗(yàn)忽略屬于多個(gè)類別的樣本、選取樣本數(shù)目大于10的類簇組成的實(shí)驗(yàn)數(shù)據(jù)集。表3描述的是在Reuters數(shù)據(jù)集上7種算法的實(shí)驗(yàn)結(jié)果。由表3可知，本文算法與LCCF相比，平均AC和NMI分別提高15.14%和9.07%。

表2 在TDT2庫(kù)上的聚類實(shí)驗(yàn)(%)

表3 在Reuters庫(kù)上的聚類實(shí)驗(yàn)(%)

4.3 在PIE人臉庫(kù)上的實(shí)驗(yàn)

在PIE人臉庫(kù)中，固定姿勢(shì)和表情，在不同的照明條件下，選取11554張圖像進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果由表4可知：本文算法與CCF算法相比，平均AC和NMI分別提高6.40%和5.41%。

4.4 參數(shù)設(shè)置

HCCF模型中需要確定創(chuàng)建超邊時(shí)所選擇的k個(gè)近鄰點(diǎn)和正則項(xiàng)參數(shù)α, k取值從2～10，正則項(xiàng)參數(shù)α取值{10-1,100,101,102,103,104,105}，通過搜索不同參數(shù)值對(duì)實(shí)驗(yàn)結(jié)果的影響進(jìn)行評(píng)估。圖1，圖2分別表明當(dāng)正則項(xiàng)參數(shù)α變化時(shí)對(duì)聚類準(zhǔn)確率和歸一化互信息的影響。圖3，圖4表明當(dāng)α取實(shí)驗(yàn)效果最優(yōu)的條件下，搜索不同k值對(duì)聚類準(zhǔn)確率和歸一化互信息的影響。

表4 在PIE庫(kù)上的聚類實(shí)驗(yàn)(%)

圖1 正則項(xiàng)參數(shù)α對(duì)AC的影響

圖2 正則項(xiàng)參數(shù)α對(duì)NMI的影響

圖3 構(gòu)建超邊的頂點(diǎn)數(shù)k對(duì)AC的影響

圖4 構(gòu)建超邊的頂點(diǎn)數(shù)k對(duì)NMI的影響

4.5 結(jié)論分析

分析4.3節(jié)和4.4節(jié)實(shí)驗(yàn)結(jié)果可得如下結(jié)論：

(1)NMF, CF算法沒有考慮樣本的類別信息，CNMF和CCF算法分別對(duì)樣本類別信息采用“硬約束”的方式，確保高維空間中屬于同一類簇的樣本在維數(shù)約簡(jiǎn)后仍屬于同一類簇。與NMF, CF相比，添加了類別信息的CNMF, CCF算法的聚類AC和NMI在3個(gè)數(shù)據(jù)集上均優(yōu)于NMF, CF算法，說明考慮樣本的類別信息可以提高算法的鑒別能力，但是CNMF, CCF沒有利用樣本的幾何結(jié)構(gòu)信息；

(2)NMF, CF算法沒有考慮數(shù)據(jù)間的幾何機(jī)構(gòu)信息，HNMF算法利用超圖正則項(xiàng)獲得數(shù)據(jù)間的多元幾何結(jié)構(gòu)信息，LCCF算法在CF算法的目標(biāo)函數(shù)中增加一個(gè)拉普拉斯圖正則項(xiàng)，保持?jǐn)?shù)據(jù)的幾何流形結(jié)構(gòu)信息，使得HNMF和LCCF算法的聚類AC和NMI在3個(gè)數(shù)據(jù)集上明顯高于NMF和CF算法，說明考慮數(shù)據(jù)間潛在的流形結(jié)構(gòu)可以提高算法的鑒別能力，但是HNMF和LCCF是無(wú)監(jiān)督學(xué)習(xí)算法，忽略了樣本中可能存在的類別信息；

(3)與NMF, CF算法相比，HNMF, LCCF算法分別考慮了樣本的幾何結(jié)構(gòu)信息，CNMF, CCF算法分別考慮了樣本的類別信息，從3個(gè)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果知，CNMF和CCF的平均AC和NMI分別優(yōu)于HNMF和LCCF算法，說明聚類類別數(shù)小于10時(shí)，考慮樣本的類別信息比考慮樣本的幾何結(jié)構(gòu)信息更有利于提高算法的聚類準(zhǔn)確率；

(4)本文HCCF算法同時(shí)考慮了樣本的類別信息和樣本的幾何結(jié)構(gòu)信息，從3個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果來看，HCCF算法的平均AC和NMI優(yōu)于其他對(duì)比算法，說明HCCF利用超圖正則項(xiàng)保持了數(shù)據(jù)間高階關(guān)系，因此HCCF具有更強(qiáng)的鑒別性；

(5)參數(shù)k大小與數(shù)據(jù)集樣本分布有關(guān)，當(dāng)樣本分布相對(duì)分散時(shí)，較大的k值使得樣本相似度降低，而當(dāng)樣本分布相對(duì)集中時(shí)，若參數(shù)k較小，使得具有相同結(jié)構(gòu)信息的數(shù)據(jù)離散，故聚類準(zhǔn)確率曲線先上升到最優(yōu)值，如果k繼續(xù)增大，會(huì)使聚類準(zhǔn)確率下降；

(6)當(dāng)參數(shù)α過大(大于10000)或過小(小于10)時(shí)，過分強(qiáng)調(diào)或忽略了樣本的幾何結(jié)構(gòu)信息和類別信息，使得聚類AC下降。當(dāng)α在10～10000范圍內(nèi)變化時(shí)在3個(gè)數(shù)據(jù)庫(kù)上均可取的較好結(jié)果，說明HCCF算法具有一定的魯棒性。

5 結(jié)束語(yǔ)

根據(jù)流形學(xué)習(xí)和半監(jiān)督學(xué)習(xí)的思想，本文提出了基于超圖正則化受限的概念分解算法。HCCF算法選擇k個(gè)近鄰點(diǎn)構(gòu)建超邊，計(jì)算每條超邊上的權(quán)重，通過構(gòu)建一個(gè)無(wú)向加權(quán)的拉普拉斯超圖正則項(xiàng)，獲得數(shù)據(jù)間固有的多元幾何結(jié)構(gòu)信息，解決傳統(tǒng)圖模型只能表達(dá)數(shù)據(jù)間成對(duì)關(guān)系的缺陷；同時(shí)，HCCF算法采用硬約束的方式，使得已標(biāo)記樣本的類別信息在低維空間中保持一致，與軟約束[16]方法相比，硬約束的半監(jiān)督學(xué)習(xí)沒有增加參數(shù)，降低了重構(gòu)誤差。HCCF算法同時(shí)考慮了數(shù)據(jù)的高階幾何結(jié)構(gòu)信息和樣本的類別信息，增強(qiáng)了算法的鑒別能力。本文還給出了HCCF目標(biāo)函數(shù)的求解方法、收斂性證明、算法復(fù)雜度分析以及參數(shù)選擇分析，并在TDT2, Reuters和PIE數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，證明了HCCF算法的有效性。但是，HCCF模型中參數(shù)k和超圖正則項(xiàng)參數(shù)α需要通過區(qū)間搜索得到最優(yōu)值，因此如何自適應(yīng)地選擇k個(gè)節(jié)點(diǎn)構(gòu)建超邊以及有效選擇α是今后研究的重點(diǎn)方向之一。

[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年生，博士生，研究方向?yàn)槟Ｊ阶R(shí)別、圖像處理等.

趙春霞： 女，1964年生，教授，研究方向?yàn)槟Ｊ阶R(shí)別、機(jī)器人控制、人工智能、圖像處理等.

舒振球： 男，1985年生，博士生，研究方向?yàn)闄C(jī)器學(xué)習(xí)、模式識(shí)別.

郭劍輝： 男，1983年生，副教授，研究方向?yàn)闄C(jī)器學(xué)習(xí)、智能機(jī)器人、目標(biāo)跟蹤及數(shù)據(jù)融合.

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改回

國(guó)家自然科學(xué)基金(61272220, 61101197, 90820306)，中國(guó)博士后科學(xué)基金(2014M551599)，江蘇省社會(huì)安全圖像與視頻理解重點(diǎn)實(shí)驗(yàn)室基金(30920130122006)和江蘇省普通高校研究生科研創(chuàng)新計(jì)劃項(xiàng)目(KYLX_0383)資助課題

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