遼寧工業(yè)大學電子與信息工程學院 周 勇 孫福明 蔡希彪

?

基于NMF和一致性學習的半監(jiān)督分類算法

遼寧工業(yè)大學電子與信息工程學院 周 勇 孫福明 蔡希彪

【摘要】為了在分類中減少數(shù)據(jù)中的冗余信息、提高分類準確率，提出一種基于非負矩陣分解與一致性學習的半監(jiān)督學習。該算法首先通過非負矩陣分解（NMF）對原始數(shù)據(jù)進行有效的降維，并得到特征矩陣；然后再特征矩陣的基礎(chǔ)上通過標簽傳遞對原始數(shù)據(jù)進行分類。實驗結(jié)果證明，NMF-LLGC算法與其他方法相比不僅能有效地減少數(shù)據(jù)的冗余信息，還能夠提高分類準確率。

【關(guān)鍵詞】非負矩陣分解；一致性學習；半監(jiān)督學習

本課題得到國家自然科學基金（No.61272214，61272371）資助。

1 引言

近年來半監(jiān)督學習（semi-supervised learning）[1]越來越受到研究者的關(guān)注，已發(fā)展成為機器學習[2]中的一個熱門的研究領(lǐng)域。它能夠利用標記樣本和未標記樣本的分布信息，增強學習性能，提高分類精度，填補了傳統(tǒng)機器學習的不足。因此如何更好的利用未標記數(shù)據(jù)來挖掘數(shù)據(jù)的內(nèi)部結(jié)構(gòu)是非常有意義的。

然而，基于圖的半監(jiān)督學習方法更具有一般的解釋性和良好的分類性能，能更好的反映及描述樣本空間，解決現(xiàn)實生活中的許多問題。Zhou等人[3]在2004年提出局部和全局一致性學習(LLGC)算法，該算法是最具代表性的基于圖的半監(jiān)督學習算法。該算法不僅分類精確度高、計算速度快等優(yōu)點，而且對錯誤標注具有一定的容錯能力。在實際運用中，由于數(shù)據(jù)具有“海量性”與“高維性”等特點，從而掩蓋了數(shù)據(jù)的本質(zhì)特征。而且隨著數(shù)據(jù)維數(shù)的增大，很容易出現(xiàn)“維數(shù)災難”問題[4]，這會嚴重影響數(shù)據(jù)分析結(jié)果。

針對以上問題，本文提出一種有效的分類算法——基于非負矩陣分解與一致性學習的半監(jiān)督分類算法。該算法首先通過非負矩陣分解（NMF）對原始數(shù)據(jù)進行有效的降維，并得到特征矩陣，這樣做能有效的減少數(shù)據(jù)中的噪聲和不相關(guān)的特征信息；然后在特征矩陣的基礎(chǔ)上構(gòu)建鄰近圖，根據(jù)數(shù)據(jù)的相似性通過標簽傳播對原始數(shù)據(jù)進行分類。該算法不僅能夠獲得更高的分類精度、有效的減少數(shù)據(jù)冗余信息，而且對數(shù)據(jù)的存儲和計算復雜度大大降低。

2 非負矩陣分解

NMF算法[5]是高維數(shù)據(jù)處理與分析的一種手段，已被廣泛應(yīng)用于各個領(lǐng)域。

在給定迭代的終止條件后，迭代更新直到滿足終止條件，最終的矩陣U和V。

3 局部和全局一致性學習算法

LLGC算法由Zhou等人[3]在2004年提出，其核心思想是根據(jù)已標記樣本的類別標簽預測未標記樣本的類別標簽，最終達到樣本標簽全局穩(wěn)定為止。

（2）最小化正則化框架：

4 基于NMF與一致性學習的半監(jiān)督分類算法

在實際運用中，原始數(shù)據(jù)中隱含著冗余信息，數(shù)據(jù)維數(shù)也很高，從而會影響分類器的性能和分類效果。而且隨著數(shù)據(jù)維數(shù)的增大，對數(shù)據(jù)的存儲和計算復雜度帶來極大的困難。為了解決此類問題本文提出一種基于非負矩陣分解與一致性學習的半監(jiān)督分類算法。該算法LLGC類似同樣設(shè)表示為已標記樣本，表示為未標記樣本，并且。算法的目的是預測未標記樣本的標簽，其步驟描述如下：

5 實驗與結(jié)果分析

為評價算法的有效性，本文選用表1所示的2個數(shù)據(jù)集作為實驗對象。

表1　數(shù)據(jù)集信息

本文分別采用監(jiān)督學習K 近鄰(KNN)、LLGC 和NMFLLGC 算法解決表1這2個數(shù)據(jù)集的分類問題。在本實驗中KNN算法中的近鄰數(shù)K取為1。

隨機抽取前l(fā)個數(shù)據(jù)樣本組成已標記樣本集，剩下的n-l個數(shù)據(jù)樣本組成未標記樣本集在實驗過程中，為了保持公平起見維數(shù)r=312，參數(shù)a=0.99，=0.20。各數(shù)據(jù)集重復50次實驗得到的分類準確率如下表2和表3所示，相對應(yīng)的分類準確率的曲線如圖1所示。

由表2、3及結(jié)合圖1可以看出NMF-LLGC算法的分類性能優(yōu)于LLGC算法和KNN算法，當標記樣本數(shù)量達到一定程度時，其分類準確率將不再有明顯改進。因為通過NMF可以降低原始數(shù)據(jù)結(jié)構(gòu)中存在的噪聲或者不相關(guān)的特征信息，充分挖掘數(shù)據(jù)信息。而且在降低冗余信息的數(shù)據(jù)基礎(chǔ)上構(gòu)建鄰近圖能夠有效的表達數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，使得樣本的相關(guān)性增大，進一步提高了分類精度。

下面我們討論數(shù)據(jù)維數(shù)r對分類準確率的影響。我們隨機抽取前5個數(shù)據(jù)樣本組成已標記樣本集，參數(shù)a=0.99，=0.20，重復50次實驗得到分類準確率的曲線如圖2所示。

表2　不同算法在COIL20數(shù)據(jù)集上分類準確率

表3　不同算法在在PIE32數(shù)據(jù)集上分類準確率

圖2　降維的分類準確率

中的冗余信息，如：噪聲及不相關(guān)的特征信息；降維維數(shù)較低時，可能破壞原始數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，在構(gòu)圖時是數(shù)據(jù)的相似性降低，從而影響數(shù)據(jù)的分類準確率。

6 總結(jié)

本文提出了基于NMF與一致性學習的半監(jiān)督學習算法，該算法秉承了半監(jiān)督學習的優(yōu)點。在保持良好的分類效果的前提下有效的減小數(shù)據(jù)中的冗余信息及提高分類精度，降低了數(shù)據(jù)的存儲和計算復雜度。由實驗結(jié)果看出，該算法性能較優(yōu)易于推廣，是一種非常有效的半監(jiān)督分類算法。

參考文獻

[1]Zhang Chenguang,Li Yujian.Hash graph based semisupervised learning method and its application in image segmentation[J].Acta Automatica Sinica,2010,36(11):1527-1533.

[2]周志華,王玨.機器學習及其應(yīng)用[M].北京:清華大學出版社,2007: 259-275．

[3]Zhou D Y,Bousquet O,Lal T N,et al.Learning with local and global consistency[C].Proc of Advances in Neural Information Processing Systems.Massachusetts:MIT Press, 2003: 321-328.

[4]Duda RO,Hart PE,Stork Dg.Pattern Classification [M]. New York:John Wiley & Sons,2001.

[5]Lee D.D,&Seung H.S.Learning the parts of objects with non-negative matrix factorization. Nature,1999,401(6755):788-791.

周勇（1989—），男，主要研究領(lǐng)域為機器學習。

孫福明（1972—），男，博士，教授，計算機學會（CCF）會員（E200014102M），主要研究領(lǐng)域為計算機視覺、圖像語義理解。

蔡希彪（1972—），男，博士，副教授，主要研究領(lǐng)域為無線通信、計算機視覺、圖像語義理解。

作者簡介：