稀疏誘導流形正則化凸非負矩陣分解算法

2020-06-06 00:54:42邱飛岳陳博文陳鐵明章國道

通信學報 2020年5期

邱飛岳，陳博文，陳鐵明，章國道

（1.浙江工業大學教育科學與技術學院，浙江杭州 310023；2.浙江工業大學計算機科學與技術學院，浙江杭州 310023）

1 引言

在一些研究和應用領域里，經常遇到輸入的數據維數過于龐大，導致計算復雜度過高和模型過擬合[1]。為了保證模型的簡潔性和準確性，尋求一種盡可能簡單地描述數據的方法至關重要。矩陣的乘法分解是解決這一類問題的常用方法，常見的分解方式有主成分分析（PCA,principal components analysis）、奇異值分解（SVD,singular value decomposition）、矢量量化（VQ,vector quantization）和非負矩陣分解（NMF,nonnegative matrix factorization）等。1999 年，Lee 等[2]提出了對所有元素都是非負的矩陣的乘法分解方法NMF，將數據矩陣分解為基矩陣和編碼矩陣的乘積。由于得到的矩陣均為非負矩陣，即基之間只允許做加法運算，不允許做減法運算，因此，NMF 保留了數據的局部特征。同時，新的隱式表征空間的維度遠小于原始空間的維度，這些特性賦予了其可以從輸入的數據中學習嵌入其中的低維子空間的能力。NMF 被廣泛應用于降維與特征提取領域，如網絡結構檢測[3-5]、高光譜解混[6-7]、人臉識別[8]和推薦系統[9]等。

流形學習認為低維子空間是鑲嵌在高維特征空間中的低維流形[10]，通過恢復流形結構可以學習常被傳統方法所忽略的樣本空間的結構信息。常見的流形學習思想有局部線性嵌入（LLE,Locally linear embedding）、拉普拉斯圖（LAPE,Laplacian eigenmap）和等距特征映射（ISOMAP,isometric feature mapping）[11]等。Cai 等[12]將基于拉普拉斯圖的流形正則化項引入NMF，在非負矩陣分解的過程中學習了樣本空間的隱式結構信息，提出了圖正則化非負矩陣分解（GNMF,graph regularized NMF）。Huang 等[13]提出RGNMF（robust GNMF），把原始數據空間表示為特征空間與噪聲空間的和，在添加圖結構約束的同時向噪聲矩陣添加L1范數，在原始數據存在噪聲和野值點時仍然有良好的穩健性。Li等[14]提出圖正則化低秩非負矩陣分解（GNLMF,graph regularized non-negative low-rank matrix factorization），先對數據進行降噪處理，再進行基于流形學習的非負矩陣分解。Wu 等[15]提出MNMFL2,1（manifold NMF withL2,1norm），在GNMF 的基礎上為矩陣分解的誤差添加L2,1稀疏約束，提高了模型的泛化能力和對噪聲的穩健性。GNMF 中流形結構（關聯圖）旨在表達樣本之間的近鄰關系，Zeng等[16]基于超圖理論構建超圖流形結構，提出超圖正則化非負矩陣分解（HNMF,hyper-graph regularized NMF）。超圖中的近鄰關系不再限制頂點數量，可以將關聯圖結構理解為超圖結構的二階特例，超圖相比關聯圖可以保留更多的近鄰關系。多數流形學習方法預先定義圖結構，在算法迭代過程中圖結構保持不變，因此失去了對空間結構信息變化的敏感性。為了解決這個問題，一些算法添加了動態圖約束，以在迭代過程中保證圖結構對目標空間的持續影響力。Wang 等[17]提出RALSE（robust adaptive low-rank and sparse embedding for feature representation）框架，集合了矩陣的稀疏低秩表示與添加了L1范數的圖結構，實現了特征的有效學習與空間結構的實時保留。Yi 等[18]將正交約束、近鄰樣本間稀疏表示關系相結合，提出了帶有局部關系保持約束的動態圖結構的非負矩陣分解（NMFLCAG,NMF with locality constrained adaptive graph）。Lu 等[19]將局部線性嵌入模型與稀疏的動態圖約束結合，在動態學習結構信息的同時保證了相似度矩陣的稀疏性。Yin 等[20]通過學習自適應的低秩圖親和矩陣來進行子空間聚類，其中圖正則化項的各項參數不再預先指定，而是在更新過程中自適應更新。

NMF 和GNMF 都只適用于非負約束下的矩陣分解，即輸入數據不允許出現負值，不能滿足實際應用場景的需求。為了解決這個問題，Ding 等[21]提出了凸非負矩陣分解（CNMF,convex NMF），將NMF 適用范圍從非負矩陣擴大至混合符合矩陣。Wang 等[22]在矩陣分解的基礎上對非負基矩陣引入正交約束，提出基于矩陣分解的特征提取算法（MFFS，feature selection via matrix factorization）。一些方法將混合符號矩陣分解與流形正則化相結合，如Hu 等[23]提出帶有流形正則化項的凸非負矩陣分解（GCNMF,CNMF with manifold regularization），聚類實驗表明，其相較于沒有學習數據空間結構信息的方法有很大的性能提升。Cui 等[24]將子空間學習與凸非負矩陣分解相結合提出SCCNMF（subspace clustering guided convex NMF），利用樣本間的線性表示關系進行流形結構的動態保持。Li 等[25]考慮相同類標簽的圖像擁有類似的圖像表示，在GCNMF 的基礎上添加了成對約束，提出了PGCNMF（pairwise constrained graph regularized CNMF）。

傳統的特征選擇往往忽略了特征之間的關系，而基于稀疏約束的方法可以發掘特征間的潛在關聯，同時可以增強模型的泛化能力和穩健性[26]。因此，各種稀疏化方法被引入非負矩陣分解方法。Kong 等[27]提出了L2,1-NMF，引入L2,1范數對編碼矩陣做泛化處理。Hoyer 等[28]提出帶有稀疏約束的非負矩陣分解（NMFSC,NMF with sparseness constraint），其對基矩陣、編碼矩陣添加稀疏約束，提高了分解結果的稀疏性。張旭等[29]采用L2,1范數增強了圖正則化非負矩陣分解在基因表達譜上的噪聲穩健性。本文在GCNMF 的基礎上引入L2,1范數，提出一種新的稀疏誘導流形正則化凸非負矩陣分解（SGCNMF,sparsity induced GCNMF）算法。該算法不僅學習了數據空間隱式流形結構信息，同時使數據矩陣不再受限于非負約束，將非負矩陣分解擴展到了混合符號矩陣分解。另外，SGCNMF 對模型進行了稀疏化處理，提高了其泛化能力和噪聲穩健性。在一組圖像數據集上的聚類實驗結果驗證了SGCNMF 的有效性。

2 相關工作

2.1 凸非負矩陣分解

NMF 將非負數據矩陣分解為2 個非負矩陣的乘積。給定一個矩陣，找到2 個非負矩陣，使

其中，U為基矩陣，V為編碼矩陣。原數據矩陣與分解后矩陣乘積的誤差越小，則對原始數據的擬合越好。為了最小化分解誤差，Lee 等[30]提出了乘法更新規則算法。

混合符號矩陣是指含有正數、零和負數的矩陣，經典NMF 只解決含非負元素矩陣的分解問題。Ding 等[21]提出了CNMF 并證明其收斂性。與NMF將矩陣分解成2 個非負矩陣的乘積不同，CNMF 是一種矩陣的三分解方法[31]，其允許數據矩陣X中出現負元素，分解為式(2)所示形式。

本文采用歐氏距離描述分解誤差，CNMF 的代價函數O1定義為

與NMF 的乘法更新規則[30]類似，CNMF 有乘法更新規則[21]，如式(4)所示。

2.2 圖正則化非負矩陣分解GNMF

局部不變性假設[32]認為，在高維空間里局部近鄰樣本映射到低維空間時對應的樣本仍為近鄰的。為了保持數據空間的幾何結構，對于2 個原本近鄰的點xi與xj，用新的基表示的兩點vi和vj也應該相近。基于此，GNMF 首先構建一個鄰接圖G，并連接X=[x1,x2,…,xn]中近鄰的點。然后，構建權重矩陣W用于量化點之間的近鄰程度。構建W有3 種方式：0?1 加權、熱核加權和點積加權。本文以0?1 加權為例。

為了保持vi與vj兩點間的近鄰關系，定義圖正則化項如式(6)所示。

其中，Tr(?)表示矩陣的跡；D表示一個對稱矩陣，其對角元素Dii為矩陣W的第i行的元素和（或者對應第i列的元素和）；L為描述空間結構特征的拉普拉斯矩陣，且L=D?W。將圖正則化項作為懲罰項，構建目標函數O2，如式(7)所示。

λ是非負的正則化參數，當λ=0 時GNMF 退化成NMF。使式(7)最小化，乘法更新規則為

Cai 等[12]證明了在乘法更新規則式(8)下，目標函數O2可以保證收斂性。

2.3 流形正則化凸非負矩陣分解

CNMF可以看作K-means松弛編碼空間的正交約束后的版本[21]，CNMF 在分解過程中丟失了數據的空間結構信息。Hu 等[23]將GNMF 與CNMF 相結合，提出GCNMF，在松弛了NMF 的非負約束的同時，通過最小化流形正則化項來保留數據空間的流形結構特征。與GNMF 類似，GCNMF 構建了鄰接圖G、權重矩陣W和拉普拉斯矩陣L，并在代價函數O1中添加圖正則化項R(V)。GCNMF 的目標函數O*為

2.4 稀疏約束非負矩陣分解

基于稀疏約束的方法可以發掘特征空間的潛在關聯。稀疏約束通常以對目標約束項添加Lp,q范數的形式存在，是一種常見的提高矩陣分解性能的方式。在矩陣分解中施加稀疏約束有多種方式，施加不同的約束項也有不同的側重點[28]。例如，MNMFL2,1在全局分解誤差上添加L2,1范數稀疏約束使分解誤差更加平滑[15]；RGNMF 向數據中的噪聲添加L1范數，以提高對噪聲特征的屏蔽能力[13]；LMFAGR（low-rank matrix factorization with adaptive graph regularize）對局部線性嵌入的權重向量添加L1范數稀疏約束以提取更加有判別能力的特征[19]。在現有的多種范數中，L2,1范數對數據野值點的平衡更加平滑，對異常數據更加穩健，對處理噪聲有良好的效果，是特征提取中常用的一種稀疏方式[33]。對于矩陣Xm×n，其L2,1范數定義如式(10)所示。

3 SGCNMF 算法描述與求解

現實中的原始數據往往夾雜著噪聲，如圖像中不同強度的光照、語音數據中的噪音等，這些噪聲對特征學習造成了一定的干擾。在非負矩陣分解中，基矩陣是新的特征子空間的基，保留了原始特征空間中的局部特征，數據中的噪聲特征同時被部分學習并保留到基矩陣中成為“噪聲特征”。考慮到L2,1范數對野值點具有抑制和平衡作用，還可以提高模型的泛化能力，本文在GCNMF 的基礎上引入L2,1范數，通過對基矩陣施加稀疏約束的方式，增強模型的泛化能力和抗噪聲能力。

3.1 算法描述

對于非負矩陣分解，基矩陣越稀疏，局部特征的貢獻度越低。式(9)中U為保留了噪聲特征的基矩陣，采用基于L2,1范數的稀疏約束，提出目標函數O，如式(11)所示。

其中，α、β為正則化參數，α控制流形正則化項在矩陣分解過程中的影響力，β控制基矩陣的稀疏程度。E為對稱矩陣，且其對角元素為

下面將討論目標函數O的更新規則和在此規則下目標函數收斂的理論分析。

3.2 算法求解

令θik,φ jk分別為約束uik≥ 0,vjk≥ 0 下的拉格朗日乘子，構建矩陣Θ=[θik]，Φ=[φ jk]。對式(11)構造拉格朗日函數G。

G對U、V分別求偏導并令其偏導數為0，有

對式(14)和式(15)應用 KKT（Karush-Kuhn-Tucker）條件，即

將式(16)代入式(14)和式(15)可得

定義2 個非負矩陣(XXT)+和(XXT)?，如式(19)所示。

則存在式(20)所示的關系。

將式(20)代入式(17)和式(18)，可得

解得乘法更新規則，如式(23)所示。

定理1式(11)所示的目標函數在式(23)所示的更新規則下是單調非增的。

證明見附錄A。

在求出U、V的更新規則后，SGCNMF 如算法1 所述。

算法1稀疏誘導流形正則化凸非負矩陣分解算法

輸入數據矩陣，聚類中心數k

輸出低維矩陣

其中，?表示矩陣的哈達瑪積；

6) while 目標函數式(11)收斂。

4 聚類實驗及結果分析

非負矩陣分解在圖像聚類上具有廣泛應用，因此本節設計了圖像聚類實驗來測試所提算法SGCNMF 的有效性。本文對所提SGCNMF 算法與非負矩陣分解算法，即GNLMF[14]、HNMF[16]、NMFLCAG[18]、CNMF[21]、MFFS[22]、GCNMF[23]、SCCNMF[24]進行對比實驗。當SGCNMF 的流形正則化項參數設為0 時，SGCNMF 退化為帶有稀疏約束的凸非負矩陣分解算法（SCNMF,CNMF with sparse constraint）。為了驗證流形學習和稀疏約束的效力，本文設置了一組SCNMF 對照實驗，分別驗證流形正則化項和稀疏約束對矩陣分解性能的影響。

4.1 數據準備

本文選取了圖像聚類常用的3 個公開數據集，即Grimace 數據集、Faces95 數據集和USPS 數據集，并且設計了隨機遮擋算法與Grimace 數據集和Faces95 數據集合成相應的有噪聲數據集。

Grimace 數據集和Faces95 數據集是由英國埃塞克斯大學創建的面部數據庫。Faces95 數據集包括72 個人、每人20 張，共1 440 幅面部圖像；Grimace數據集包括18 個人、每人20 張，共360 幅面部圖像。2 個數據庫的每幅圖像均為64 像素×64 像素，表示為一個4 096 維的列向量。數據集的所有元素為非負值。

USPS（United States postal service）數據集是美國郵政掃描快件上的手寫體數據集，其中包括手寫體字母和數字數據集。其手寫數字數據集包括0～9 的手寫體，共7 291 張訓練圖像和2 007 張測試圖像，每張圖像為16 像素×16 像素的256 灰度圖[34]。本文采用其訓練圖像數據集，每類數字選取前 200 張圖像組成聚類數據集進行聚類實驗。該數據集為混合符號矩陣，同時存在正數、負數和零[23]，因此不對其進行HNMF、GNLMF 和NMFLCAG 聚類實驗。

4.2 噪聲處理

圖1 不同噪聲類型示例

為了測試噪聲的類型與強度對算法模型的影響，本文設置了3 種噪聲類型，即黑色椒鹽噪聲、白色野值椒鹽噪聲和黑色塊狀噪聲的對比實驗。不同噪聲類型如圖1 所示。針對噪聲強度實驗，對于椒鹽噪聲，設置噪聲強度數值組為[0.001,0.01,0.1,0.2,0.3]，每個噪聲強度數值代表噪聲點占總元素數的比例；對于塊狀噪聲，設置噪聲寬度數值組為[2,4,6,8,10]，每個噪聲強度數值代表噪聲塊邊長。具體噪聲算法如算法2 所述。

算法2隨機噪聲算法

輸入數據矩陣，噪聲率ρ，噪聲類型T

輸出有噪聲圖像矩陣

4.3 性能評價指標

本實驗采用2 個常用聚類評價指標，即準確度（AC,accuracy）和歸一化互信息（NMI,normalized mutual information），來驗證SGCNMF 的準確性和穩健性。AC 和NMI 的定義如下。

AC 用于衡量樣本獲得正確的類標簽的比率。對給定n個樣本的數據集，令其通過聚類方法獲得的類標簽集為L={l1,l2,…,ln}，真實的類標簽集為R={r1,r2,…,rn}。則該次聚類結果的AC定義為

其中，map(?)表示基于Kuhn-Munkres 方法的一個最佳映射函數，它將聚類方法獲得的類標簽與真實的類標簽做最佳匹配[35]；Γ(?)是一個二值函數，當聚類標簽映射后與真實標簽相同時則為1，否則為0。AC 值越高則說明聚類準確度越高。

互信息（MI,mutual information）常用來度量2個聚類集合間的相似度。給定數據集的真實類別信息集合C和算法聚類出來的類別信息集合C′，則MI(C,C′)定義為

其中，p(ci)和代表從數據集中任意抽取一個樣本分別屬于類別ci和的概率代表抽取的樣本既屬于C又屬于C’的聯合概率。將MI 歸一化后，定義NMI 為

其中，H(C)和H(C’)分別表示C和C’的熵。NMI值越接近于1，則2 個聚類結果相似度越高；反之，則相似度越低。

4.4 參數選擇

SGCNMF 的2 個核心參數為流形正則化項參數α和稀疏系數β。本節在3 個數據集上進行了實驗以確定α和β的取值范圍。實驗發現，α取值在10～102時效果良好且結果較穩定。若稀疏系數β太大，分解出來的基圖像過于稀疏，圖像的特征不能得到很好的保留；若稀疏系數β太小，則抗噪能力不足（β=0 時SGCNMF 退化成GCNMF）。β取值在10～103時效果良好且結果較穩定。實驗選擇流形正則化參數α為10，稀疏系數β為100。

經實驗測試發現，各個算法在迭代50 次以內已基本收斂，因此將聚類實驗中每次迭代的次數設為100 次，收斂情況詳見4.6 節收斂性分析。

4.5 聚類實驗

對每個數據集都均勻地選取了多個聚類中心進行聚類實驗。為了消除實驗結果的隨機性，設計實驗過程如算法3 所述。

算法3聚類實驗算法

輸入數據矩陣V，待測試聚類中心數K

輸出各算法在數據集上聚類結果的平均值和標準差

1) 從數據集中隨機選擇K類數據，并選取K值作為編碼矩陣的聚類數（進行噪聲類型、強度對算法性能的影響實驗時，K值固定為數據集最大樣本類別數）；

2) 對于給定的K值，運行相應的算法獲取低維的特征空間；

3) 在新的低維空間上執行20 次隨機初始化K個聚類中心的K-means 聚類。對聚類結果進行AC 和NMI 評估，每次運行的最佳值作為該次運行的結果；

4) 計算20 次聚類結果的平均值和標準差；

5) 重復20 次步驟1)～步驟4)并記錄平均值和標準差。

對Grimace 數據集和Faces95 數據集添加噪聲強度為0.2、噪聲值為255 的白色野值椒鹽噪聲，各算法在數據集上的結果如表1～表4所示。對USPS數據集進行噪聲處理，各算法的實驗結果如表5～表6 所示。表1～表6 中數值都為百分數。

為了驗證不同噪聲類型和強度對模型性能的影響，按照算法2 所述流程對Grimace 數據集和Faces95 數據集添加3 種不同強度的噪聲并進行實驗，實驗結果如圖2 和圖3 所示。

從實驗結果可以得到以下結論。

1) 基于流形學習的算法在實驗數據集上聚類準確度和歸一化互信息均明顯優于非流形學習算法，證明了特征空間的隱式結構信息在聚類應用中的重要性。

表1 聚類算法在噪聲Grimace 數據集上的準確度對比

表2 聚類算法在噪聲Grimace 數據集上的歸一化互信息對比

表3 聚類算法在噪聲Faces95 數據集上的準確度對比

表4 聚類算法在噪聲Faces95 數據集上的歸一化互信息對比

表5 聚類算法在USPS 數據集上的準確度對比

表6 聚類算法在USPS 數據集上的歸一化互信息對比

2) 在不同的噪聲環境下，SGCNMF 的效果均優于其他同類凸非負矩陣分解方法，證明了本文提的增加基矩陣稀疏約束的有效性。稀疏約束平滑了數據中野值點對分解結果的影響，同時使基矩陣所表達的局部特征更加稀疏，提高了模型的泛化能力。但是，在黑色椒鹽噪聲和黑色塊狀噪聲中其效果往往不如GNLMF，在白色野值噪聲中SGCNMF 的效果優于其他算法。證明了GNLMF的去噪算法的有效性，以及L2,1范數對數據中的野值點的平滑作用。

3) 在將SGCNMF 方法的圖正則化參數設置為0 時，SGCNMF 退化為SCNMF。與CNMF 相比，SCNMF 的性能雖有一定的提升，但是不夠穩定。盡管基矩陣的稀疏約束給GCNMF 帶來了穩健的性能提升，聚類結果顯示獨立的稀疏約束還不足以改進算法的性能，需要與流形正則化項等其他約束項結合才能達到更好的效果。

圖2 Faces95 數據集在不同噪聲強度下的準確度

4) 非負矩陣分解（X≈UVT）著重于非負矩陣的局部特征提取與線性加權，而 SGCNMF 拓展非負矩陣到混合符號矩陣的分解，并引入了帶有噪聲的數據矩陣作為分解結果的一部分，即X≈XUVT這種三分解方式，這也使SGCNMF 很難取得比HNMF 和GNLMF 明顯優異的效果。但是，SGCNMF 分解混合符號矩陣的能力是這2 種方法所不具備的，因此在實際使用中也有著更大的應用范圍。

5) 對于噪聲類型來說，黑色噪聲相較于白色野值椒鹽噪聲對算法的性能影響更小。這可能是由于在歸一化數據后數據接近0，即黑色噪聲對原始數據的改變幅度小于白色野值椒鹽噪聲，這意味著無論是在計算樣本間距（即流形結構）還是計算分解誤差時影響程度均小于白色野值椒鹽噪聲。

圖3 Grimace 數據集在不同噪聲強度下的準確度

6) 對于噪聲強度來說，隨著噪聲強度的增加，各個方法的準確度和歸一化互信息一般均有不同程度的下降，這在白色野值椒鹽噪聲上表現尤為明顯。在噪聲強度分別為0.001 和0.01 時，其效果相差往往不大，這說明了流形非負矩陣分解類方法本身就帶有一定的稀疏性[23]，在噪聲強度過小時并不會過多影響算法的性能。隨著噪聲強度的增加，基于流形學習的方法相較于非流形學習方法仍然能保持較大的性能優勢。值得注意的是，NMFLCAG 在低噪聲環境下效果優異，但是其性能在噪聲強度達到0.1 時出現大幅度下降，遠低于其他流形學習算法，這意味著該方法的動態圖結構對噪聲的穩健性不夠強。

4.6 收斂性分析

本文在附錄A 給出在式(23)所示的更新規則條件下，式(11)所示的目標函數式(11)的收斂性理論證明。在聚類實驗過程中SGCNMF 在3 個數據集的收斂結果如圖4 所示。圖中縱軸表示算法的分解誤差值，橫軸表示迭代次數。從圖4 中明顯可以看出，SGCNMF在3 個數據集上都很快收斂，在迭代20 次以內就幾乎逼近極限值。

圖4 SGCNMF 收斂情況

5 結束語

本文結合流形學習和凸非負矩陣分解，提出了一種稀疏誘導的流形正則化的凸非負矩陣分解算法SGCNMF。所提算法在松弛非負矩陣分解的非負約束的同時，通過流形學習，保留了數據空間的結構特征，向基矩陣添加了稀疏約束，給出了乘法更新規則，證明了在該規則下目標函數的收斂性，增強了算法的聚類準確性和對噪聲的穩健性。實驗結果表明，添加了基矩陣稀疏約束的流形正則化凸非負矩陣分解在聚類問題上，與沒有稀疏約束的方法相比聚類準確度得到了提升，并且在數據存在大量噪聲時具有更強的抗干擾性。

附錄A 定理1 的證明

目標函數O（如式(11)所示）在U,V上并不同時具有凸的性質，但固定一個變量，求解另一個變量時目標函數是收斂的。下面證明目標函數O在式(23)所示的乘法更新規則的收斂性。

定義1當Q(u,u’)滿足下列2 個性質時，定義Q為函數T的輔助函數，具有以下性質。

1)Q(u,u’) ≥T(u)

2)Q(u,u’)=T(u)

引理1如果Q是T的輔助函數，則T在式(27)約束條件下迭代時，值不會增大。