一種非負(fù)矩陣分解的快速稀疏算法

宋金歌，楊 景，陳 平，佘玉梅

(云南民族大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，云南昆明650031)

1999年，Lee和Seung［1］首次提出了非負(fù)矩陣分解，為人們處理大規(guī)模數(shù)據(jù)提供了一種新的方法．2001年，Lee和Seung［2］給出了非負(fù)矩陣分解的乘性迭代公式，有效地保持了數(shù)據(jù)的非負(fù)性．由于非負(fù)矩陣分解算法易于實(shí)現(xiàn)，存儲(chǔ)空間小，分解形式的可解釋性好，所以被應(yīng)用于文本分析與聚類、數(shù)字水印、人臉識(shí)別、圖像檢索、基因特征提取等研究中［3］．目前，人們對(duì)于非負(fù)矩陣的研究主要集中在3個(gè)方面：稀疏性增強(qiáng)的NMF算法;鑒別性NMF算法;加權(quán)NMF算法．

本文提出了一種非負(fù)矩陣分解的快速稀疏算法，通過代數(shù)變換把對(duì)原矩陣分解轉(zhuǎn)化成對(duì)維數(shù)較低的對(duì)角矩陣的分解，在分解的過程中加入了對(duì)系數(shù)矩陣稀疏度的控制．給出了此算法的迭代規(guī)則以及收斂性證明過程，將其應(yīng)用在文本文摘中．

1 非負(fù)矩陣分解問題

1.1 問題描述

給定一個(gè)n×m階非負(fù)矩陣V，找到2個(gè)n×r和r×m階的非負(fù)矩陣因子W和H，使得V=WH．將矩陣W稱為基矩陣，矩陣H稱為系數(shù)矩陣．

1.2 算法步驟

非負(fù)矩陣的分解是一種低秩逼近算法，常用V和WH間的歐幾里德距離平方作為目標(biāo)函數(shù)來達(dá)到最佳逼近．目標(biāo)函數(shù)為：

NMF的實(shí)現(xiàn)是一個(gè)最優(yōu)化問題，就是在約束條件W，H≥0下，尋找矩陣W和矩陣H，使得(1)式達(dá)到最小值，只有當(dāng)V=WH的時(shí)候，(1)式才能取到最小值0．Lee等［2］利用梯度下降法給出一種乘法更新規(guī)則，迭代求得矩陣W和矩陣H．其算法如下：

Step1：對(duì)非負(fù)矩陣W和H隨機(jī)賦初值;

Step2：更新W和H，更新規(guī)則為

Step3：重復(fù)Step2直至收斂．

2 非負(fù)矩陣分解的快速稀疏算法

2.1 基本思想

對(duì)于非負(fù)矩陣的分解問題，王文俊等［4］曾提出一種快速方法，在V=WH的兩邊左乘VT得：

令VTV=X，VTW=Y，則(3)式可變形為

由于(1)式和(4)式都含有權(quán)重系數(shù)矩陣H，所以可以把對(duì)矩陣V的分解轉(zhuǎn)化為對(duì)矩陣X的分解，同樣可以得到矩陣H．矩陣V是n×m階的，而矩陣X是m×m階的，對(duì)于高維小樣本數(shù)據(jù)來說n＞＞m，所以此轉(zhuǎn)化在矩陣分解過程中起到了降維的作用，使矩陣分解的復(fù)雜度降低．

對(duì)于非負(fù)矩陣稀疏度的約束，Hoyer［5］提出：約束矩陣W的稀疏度好，還是約束矩陣H的稀疏度好，還是約束兩者的稀疏度好，取決于問題中特定的應(yīng)用情況．比如，一個(gè)醫(yī)生分析疾病模式，假設(shè)大部分疾病是稀有的(因此稀疏)．但是每種疾病都能引起大量的癥狀．假設(shè)矩陣的行代表癥狀，列代表不同的個(gè)體，這種情況下系數(shù)矩陣應(yīng)該稀疏而基矩陣可以不受約束．另如，當(dāng)需要學(xué)習(xí)圖像數(shù)據(jù)庫中有用的特征時(shí)，可能需要約束W和H的稀疏性才更有意義．這表明任何給定的對(duì)象是在當(dāng)前的幾張圖像中并影響一少部分的圖像．

對(duì)于處理行表示特征詞，列表示句子的文本矩陣的分解來講，采用約束矩陣H的稀疏度．所以在對(duì)上述對(duì)角矩陣X分解時(shí)，在目標(biāo)函數(shù)中采用了1－范數(shù)形式來約束矩陣H的稀疏度．目標(biāo)函數(shù)為：

這樣可以使矩陣分解的結(jié)果得到較高的稀疏性，合適的稀疏性在保留數(shù)據(jù)的主要特征的基礎(chǔ)上，還可以減少儲(chǔ)存空間，提高運(yùn)算效率，有利于快速處理大規(guī)模數(shù)據(jù)．

在X=YH的分解過程中，求得全局最優(yōu)解比較困難，因?yàn)?5)式對(duì)Y和H來講是非凸的．但是可以將數(shù)值優(yōu)化中的負(fù)梯度下降法和迭代規(guī)則應(yīng)用于局部最優(yōu)解中．

首先，在非負(fù)條件下初始化Y0和H0．通過迭代公式：

分別計(jì)算F(Y，H)關(guān)于Yik和Hkj的偏導(dǎo)數(shù)：

取步長為：

將(7)(8)(9)代入(6)中分別求得：

2.2 收斂性分析

引入文獻(xiàn)［2］中的定義和引理來證明(10)和(11)的收斂性．

定義1 稱函數(shù)G(h，h')為函數(shù)F(h)的輔助函數(shù)，如果滿足以下2個(gè)條件：

引理1 如果函數(shù)G(h，h')為函數(shù)F(h)的輔助函數(shù)，則按下式迭代，函數(shù)F(h)是非增的：

此引理能保證目標(biāo)函數(shù)F非增，

定理1 函數(shù)

這里h表示矩陣H中的某一列，hi表示該列的第i個(gè)元素，x表示矩陣X中相應(yīng)的列．顯然G(h，h)=F(h)．比較式(14)與下式

如果G(h，h')≥F(h)，須使0

當(dāng)(15)式中λ=0時(shí)，Lee和Seung已證明式(17)的正確性．當(dāng)λ＞0時(shí)，對(duì)角矩陣K可看成是2個(gè)半正定的矩陣的和．所以同理也可以證明式(17)的正確性．

定理2 利用迭代規(guī)則(10)和(11)交替求解Y和H時(shí)，目標(biāo)函數(shù)(5)非增，且函數(shù)值不再變化的條件是當(dāng)且僅當(dāng)Y和H是式(5)的穩(wěn)定點(diǎn)．

證明 由于G(h，h')是F(h)的輔助函數(shù)，根據(jù)引理，只需最小化G(h，ht)，即令

解之，得：

寫成矩陣元素形式為：

F(y)在關(guān)于矩陣Y的迭代規(guī)則式(10)下的非增和Lee的證明類似，就不再給出證明．

2.3 算法步驟

根據(jù)以上闡述，本文給出非負(fù)矩陣分解的快速稀疏算法的步驟如下：

Step1：在V=WH的兩邊左乘VT，得VTV=VTWH，令VTV=X，VTW=Y，則又可得X=YH;

Step2：在非負(fù)條件下對(duì)Y和H隨機(jī)賦初值;

Step3：更新Y和H，其更新規(guī)則為式(10)和式(11);

Step4：重復(fù)Step3直到目標(biāo)函數(shù)式(5)收斂．

2.4 實(shí)驗(yàn)及分析

2.4.1 分解速度

任意給定一個(gè)矩陣 V=rand(500，80)，我們?nèi)=30時(shí)，對(duì)NMF算法和FSNMF算法得到H矩陣隨迭代次數(shù)增加所需時(shí)間列表分析，如表1．

由表1我們可以看出，同樣的一個(gè)矩陣V，F(xiàn)SNMF算法得到H矩陣的分解速度要比NMF算法得到H矩陣的速度快的多．

2.4.2 稀疏性

給定一個(gè)文本矩陣我們對(duì)V按照本文給出的FSNMF算法進(jìn)行分解，取r=3時(shí)，并且控制λ值的大小觀察所得H矩陣中元素為0的個(gè)數(shù)．我們列表分析，如表2．

表2 稀疏度表

由表2我們可以看出，適當(dāng)?shù)摩酥的軌虻玫骄仃嘓較高的稀疏性，合適的稀疏度有利于保留數(shù)據(jù)的主要特征，學(xué)習(xí)更清楚的局部特征，還可以減少儲(chǔ)存空間．

2.4.3 文本文摘舉例

給定一段文章如下：教學(xué)具有多種形態(tài)，是共性和多樣性的統(tǒng)一．教學(xué)作為學(xué)校進(jìn)行全面發(fā)展教育的一個(gè)基本途徑，具有課內(nèi)、課外、班級(jí)、小組、個(gè)別化等多種形態(tài)．教師和學(xué)生共同進(jìn)行的課前準(zhǔn)備、上課、作業(yè)、練習(xí)、輔導(dǎo)、評(píng)定等都屬于教學(xué)活動(dòng)．隨著社會(huì)的發(fā)展，教學(xué)既可以通過師生間、學(xué)生間的各種交往進(jìn)行，也可以通過印刷、廣播、電視、錄音、錄像等遠(yuǎn)距離教學(xué)手段開展．教學(xué)作為一種活動(dòng)，一個(gè)過程，是共性與多樣性的統(tǒng)一．

對(duì)這段文章運(yùn)用Lee等［6］提出的文摘方法，并把求H矩陣的算法部分改為本文提出的FSNMF算法去求H矩陣，最后得到的每個(gè)句子的相關(guān)度為：

GRS=(1．0e －003) ×〔0．475 1 0．118 6 0．029 1 0．011 2 0．308 0〕．

由此，可以判斷出第1句是最重要的句子，其次是第5句．所以這一段的文摘句就為：教學(xué)具有多種形態(tài)，是共性和多樣性的統(tǒng)一．

由此例，可以看到將非負(fù)矩陣分解的快速稀疏算法應(yīng)用于文本分析能夠快速準(zhǔn)確地得到文章的文本文摘．

3 結(jié)語

本文提出的非負(fù)矩陣分解的快速稀疏算法，通過代數(shù)變換使得數(shù)據(jù)進(jìn)行降維，在目標(biāo)函數(shù)中附加約束稀疏度的稀疏項(xiàng)從而定義了目標(biāo)函數(shù)，并且給出了迭代規(guī)則和收斂性證明．并且舉例說明了此算法使得矩陣的分解速度和稀疏度都有所提高，又進(jìn)一步利用此算法進(jìn)行了一個(gè)簡單的文本文摘，準(zhǔn)確地得到了文摘的結(jié)果．

［1］LEE D D，SEUNG H S．Learning the parts of objects by non －negative matrix factorization［J］．Nature，1999，401(6755)：788 －791．

［2］ LEE D D，SEUNG H S．Algorithms for non －negative matrix factorization［C］//Advances in Neural Information Processing Systems 13．Cambridge：MIT Press，2001：556 －562．

［3］ 李樂，章毓晉．非負(fù)矩陣分解算法綜述［J］．電子學(xué)報(bào)，2008，37(4)：737 －743．

［4］王文俊，張軍英．一種非負(fù)矩陣分解的快速方法［J］．計(jì)算機(jī)工程與應(yīng)用，2009，45(25)：1－2，6．

［5］ HOYER P O．Non－negative matrix factorization with sparseness constraints［J］．J Mach Learning Res，2004，5(9)：1 457－1 469．

［6］LEE J H，PARK S，AHN C M，et al．Automatic generic document summarization based on non－negative matrix factorization［J］．Information Processing and Management，2009，45：20 －34．