基于NMF和一致性學習的半監督分類算法

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

?

基于NMF和一致性學習的半監督分類算法

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

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

【關鍵詞】非負矩陣分解；一致性學習；半監督學習

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

1 引言

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

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

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

2 非負矩陣分解

NMF算法[5]是高維數據處理與分析的一種手段，已被廣泛應用于各個領域。

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

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

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

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

4 基于NMF與一致性學習的半監督分類算法

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

5 實驗與結果分析

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

表1　數據集信息

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

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

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

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

表2　不同算法在COIL20數據集上分類準確率

表3　不同算法在在PIE32數據集上分類準確率

圖2　降維的分類準確率

中的冗余信息，如：噪聲及不相關的特征信息；降維維數較低時，可能破壞原始數據的內部結構，在構圖時是數據的相似性降低，從而影響數據的分類準確率。

6 總結

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

參考文獻

[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]周志華,王玨.機器學習及其應用[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—），男，主要研究領域為機器學習。

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

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

作者簡介：