王煥庭，王鑫印

(1.桐城師范高等?？茖W校，安徽 桐城 231400；2.上海電力大學，上海 200333)

信息化時代背景下數據呈現出高維、海量的特點，對各種數據的處理往往借助于計算機來實現。各種數據在計算機的存儲是以矩陣的形式，如圖像的像素數據和矩陣相對應。處理高維、海量數據的關鍵是降維，通過矩陣分解將規(guī)模比較大的復雜問題轉變?yōu)橐?guī)模比較小的簡單問題。傳統的矩陣分解算法有主成分分析法、獨立分量分析法、奇異值分解算法等，這些方法的缺點是不能確保矩陣分解結果的非負性。盡管從數學的角度來講，分解的結果中出現負值是正常的，但是負值在實際問題中往往無意義、無法解釋。非負矩陣分解(NMF)由Lee和Seung在1999年提出，其有效解決了傳統矩陣分解中存在的負數問題[1]。NMF是一種新的矩陣分解算法，對矩陣的元素加入了非負性的約束，使得分解得到的矩陣元素不存在負值，這樣在實際應用中就會具有明確的物理意義。另外，NMF分解所得到的矩陣具有一定程度的稀疏性，這樣能夠達到抑制外界噪聲干擾的目的[2]。目前，非負矩陣分解被廣泛應用于機器學習、模式識別等領域中，具有重要的理論意義和應用價值。

1 非負矩陣分解

1.1 非負矩陣分解定義

非負矩陣分解是一種多變量分解的方法，對非負矩陣An×m進行線性分解，

An×m≈Un×rVr×m

(1)

其中，矩陣U為基矩陣，矩陣V為稀疏矩陣。

采用稀疏矩陣V替代矩陣A，那么就實現了對原矩陣A的降維處理，通過非負矩陣分解達到了減少存儲空間，節(jié)約計算資源的目的[3]。

1.2 非負矩陣分解算法

標準非負矩陣分解是一個優(yōu)化問題，通過定義目標函數來度量分解的程度與迭代的規(guī)則。Lee和Seung定義了矩陣A與UV的F-范數以及K-L散度兩個目標函數[4]。矩陣A和UV之間的F-范數如式(2)所示，矩陣A和UV之間的K-L散度如式(3)所示。

(2)

+(UV)ij)

(3)

對于式(2)和式(3)這兩個目標函數，單獨考慮U或者單獨考慮V，其均為凸函數，但是如果同時考慮U和V，那么這兩個目標函數就不再是凸函數。因此，找到兩個目標函數的最優(yōu)解是不現實的，只有去尋找局部最優(yōu)解才是可行的。

按照公式(4)和(5)進行迭代運算，

(4)

(5)

按照公式(6)和(7)進行迭代運算，

(6)

(7)

此時，目標函數D(A‖UV)單調非增。

進行非負矩陣分解的關鍵在于獲得有效的迭代公式，不論是基于F-范數還是基于K-L散度，其非負矩陣分解的流程類似，具體如圖1所示。

圖1 非負矩陣分解流程

令基矩陣U和稀疏矩陣V第n次迭代結果為Un和Vn，第n+1迭代結果為Un+1和Vn+1。非負矩陣分解算法收斂的條件是對于任意ε1>0和ε2>0，均滿足D(Un+1‖Un)<ε1和D(Vn+1‖Vn)<ε2。ε1和ε2為收斂精度，D為K-L散度。該種進行非負矩陣分解的算法稱之為乘性迭代算法。由于該種算法綜合考慮了算法的效率和實現的難易程度，同時在實際應用中效果也比較好，因此常常被作為經典的算法進行引用和介紹。

1.3 非負矩陣分解算法改進

對于乘性迭代算法而言，其收斂速度相對比較慢，同時也存在不穩(wěn)定，因此需要對其進行改進。改進非負矩陣分解算法的思想是僅僅保留非負約束條件，最速下降法是求解無約束問題的有效方法，因此采用最速下降法求解，同時通過添加稀疏約束條件來提高算法的計算效率，從而得到改進后的非負矩陣分解算法(SNMF)[5]。

設函數f連續(xù)可微，負梯度方向dk為函數f數值下降最快的方向，即

dk=-▽f(xk)

(8)

令步長為λk，那么第k+1次迭代為

xk+1=xk+λkdk=xk-λk▽f(xk)

(9)

能夠通過少量元素近似替代大量數據稱之為稀疏，通常利用向量1范數和向量2范數來對稀疏度進行衡量，定義式為

(10)

式中：n為向量x的維數，‖·‖1為1范數，‖·‖2為2范數。

假設矩陣V已知，同時要求矩陣U的所有元素之和為1，使得‖U‖2最大化，此時可以使得矩陣U的稀疏度比較大。設目標函數為

(11)

將負梯度方向設置為下降的方向，設φia為負梯度方向步長，那么

(12)

由于

(13)

因此令步長φia為

(14)

關于矩陣U的迭代公式為

(15)

假設矩陣U已知，同時要求矩陣V的所有元素之和為1，使得‖V‖1最小化，此時可以使得矩陣V的稀疏度比較大。設目標函數為

(16)

將負梯度方向設置為下降的方向，設μai為負梯度方向步長，那么

(17)

關于矩陣V的迭代公式為

(18)

改進非負矩陣分解算法的流程為：

1)設置分解誤差，初始化非負矩陣Uia>0和Vaj>0；

2)運用矩陣U和矩陣U的迭代公式進行迭代運算；

3)判斷‖A-UV‖誤差是否小于設置的分解誤差ε以及迭代次數是否達到最大值，得到分解結果。

2 非負矩陣分解在人臉識別中的應用

2.1 智能識別應用概述

非負矩陣分解的算法實現簡便、有效，被廣泛應用于模式識別研究領域的特征提取和數據降維中，在高維、海量數據的處理中具有十分廣泛的應用前景。

2.1.1 圖像識別

圖像是以矩陣的形式存儲在計算機中，這使得非負矩陣分解在進行圖像分析和識別中大有用武之地。對圖像矩陣進行非負矩陣分解，有效提取圖像的本質特征，找出圖像內部的關系，同時將提取的特征用于圖像識別、圖像降噪、圖像融合中[6]。目前應用比較廣泛的有利用非負矩陣分解進行人臉檢測、圖像融合、圖像復原、圖像壓縮等等。

2.1.2 文本聚類

一般的文本數據信息量巨大且無固定結構，但典型文本數據通常采用矩陣形式在計算中存儲并處理[7]。計算機所存儲的文本數據矩陣具有高維、稀疏的特點，因此海量的文本信息處理必須降低原始數據的維數。非負矩陣分解算法可以有效地捕捉文本中的語義和相關信息，實現對文本的聚類分析[8]。商業(yè)數據庫軟件Oracle采用非負矩陣分解算法對文本的特征進行提取，同時在特征提取的基礎上進行分類。

2.1.3 語音識別

語音在國民生活中隨處可見，同時語音數據包含有巨大的信息量，這使得對語音的識別具有至關重要的現實意義。采用非負矩陣分解可以有效地提取語音信息特征，通過語音信息特征的提取以借助于機器實現語音的自動識別[9]。如對復調音樂信號矩陣進行非負矩陣分解來實現對不同調子的識別，并記錄不同的音調。

2.1.4 機器人控制

工業(yè)生產中機器人的應用越來越廣泛，對物體的高效、準確識別是機器人研發(fā)的核心技術。機器人只有快速、準確地識別周圍的物體，才能更好地開展工作，使得機器人的智能化程度提高。借助外設獲取周圍環(huán)境數據，環(huán)境數據以矩陣的形式存儲在計算機中，采用非負矩陣分解算法來使得機器人完成對特定目標的識別。

2.2 人臉識別應用實例

人臉識別是模式識別的一個重要方向，本部分針對非負矩陣分解在人臉識別中的應用進行研究。人臉識別是利用計算機來提取人臉的相關特征從而達到對人身份進行辨別的目的。圖2給出了人臉識別的流程[10]。

圖2 人臉識別流程

2.2.1 試驗數據來源

試驗數據來源于ORL人臉數據庫。ORL人臉數據庫共包含有40個人的人臉信息，包括其在不同的光照條件下、不同的表情下、不同的面部飾物下、不同的姿態(tài)下所拍攝的照片。所拍攝的每一張照片像素大小為112×92。ORL人臉數據庫中共包含有400張灰度圖像，對40個人每個人選擇5張作為訓練集，共有200張圖片作為訓練集，剩下的200張圖片作為測試集。

2.2.2 試驗過程描述

訓練集中包含有200個訓練樣本，將每一個樣本像素矩陣的每一列元素串成一列，使得每一個樣本用一個列向量表示，那么整個訓練樣本矩陣為A10304×200。對訓練樣本矩陣A進行非負矩陣分解，得到基矩陣U和稀疏矩陣V。最后求解得到重構圖像A=UV。

2.2.3 試驗結果分析

設定誤差ε=0.05，λ1=0.02，λ2=0.01，分別進行300次和500次迭代，降維維度r為30和50，對比NMF算法和SNMF算法的結果。圖3為迭代次數為300次，降維維度r=30的重構后圖像。圖4為迭代次數為500，降維維度r=50的重構后圖像。

通過對比圖3和圖4可知，隨著迭代次數的增加和降維維度的增加，所重構出的圖像變得越來越清晰。由表1可見，迭代的次數增加和降維維度的增加使得算法的運行時間變長，但是不論是迭代次數300次還是500次，降維維度是30還是50，采用SNMF算法的運行時間均小于NMF算法，即改進的非負矩陣分解算法效率有一定程度的提升。

圖3 迭代300次降維維度30的重構后圖像

圖4 迭代500次降維維度50的重構后圖像

表1 運行時間對比

3 結論

非負矩陣分解具有明確的物理意義和良好的可解釋性，這使得其在機器學習、模式識別等領域得到了廣泛的應用。在對非負矩陣分解算法進行研究的基礎上，給出了其在模式識別中的應用。對于非負矩陣分解算法而言，其將高維的數據映射到低維的空間，獲取原數據的本質信息。采用最速下降法且添加稀疏約束條件對非負矩陣分解進行改進，并應用于人臉識別中，通過和傳統非負矩陣分解算法進行對比，顯示改進的非負矩陣分解算法在人臉識別中的效率大大提升，這對人臉識別的研究具有一定的理論參考價值。