稀疏約束的L21增量式非負(fù)矩陣分解研究

摘 要：針對新增數(shù)據(jù)增大而引起的運算效率增大的現(xiàn)象，提出了一種稀疏約束的增量式非負(fù)矩陣分解改進(jìn)算法，該算法是在加入稀疏條件的情況下對增量數(shù)據(jù)使用L21范數(shù)。首先對初始數(shù)據(jù)進(jìn)行經(jīng)典非負(fù)矩陣分解，其次再利用其分解結(jié)果參與增量數(shù)據(jù)的運算，使目標(biāo)函數(shù)在分解計算中具有較好的收斂效果和分解后數(shù)據(jù)有較好的稀疏度。實驗部分，主要是將該算法與增量式非負(fù)矩陣分解、稀疏約束的增量式非負(fù)矩陣分解、經(jīng)典非負(fù)矩陣分解算法進(jìn)行了對比，得出在分解后數(shù)據(jù)的稀疏度和收斂快慢方面該算法均優(yōu)于其他3個算法。

關(guān)鍵詞： 非負(fù)矩陣分解 增量式學(xué)習(xí) 圖像識別 稀疏約束 L21范數(shù)

中圖分類號：TP391.41

Research onfRobustL21Incremental Non-nNegative Matrix Factorization with Sparseity Constraints

YANG Liangdong1ZHAOYanjie1 PANZhenghong 2*

1.Basic Teaching Department， Lanz Zhou Resources &Environment Voc-Tech University，Lanzhou ，GansSu Province， 730021 China;2.School of Public Health， GansSu University of cChinese Medicine ， Lanzhou，GanSsu Province， 730022 China

Abstract：In order tTo solve the phenomenon of the increasing operation efficiency caused by increasing new data， a sparse constraintn improved algorithm of incremental non-negative matrix factorizationdecompositionwith sparsityconstraints improvement algorithm is proposed， and Tthe algorithm isusestheinglL21 norm for incremental data in the case ofwith the addition a sparse conditions. Firstly， theclassical non-negative matrix factorizationdecomposition is performed on the initial data， and then its factorizationthe decomposition results are used to participate in the operation of the incremental data， so that the objective function has a better convergence effect in the decompositioncalculationof factorization and a better sparsity of thedecomposed data after factorizationhas a better sparsity. In the experimental part， the proposed algorithm is compared with incremental non-negative matrix factorization，sparse constraint incremental non-negative matrix factorizationwith sparsity constraints and classical non-negative matrix factorizationalgorithms， and it is concluded that the proposed algorithm is superior tobetter than the other three algorithms in terms of the sparsity and convergence speed of the decomposed dataafter factorization.

KeyWords：Non-negative matrix factorization; Incremental learning; Image recognition; Sparseity constraint; L21 norm

近年來智慧校園建設(shè)是一個重點工作，在校園安全方面圖像識別技術(shù)是其中一項主要分支，而處理圖像數(shù)據(jù)最為常見的一種方法是高維特征向量（矩陣數(shù)據(jù)）低維，有效避免了維度災(zāi)難[1]。為了達(dá)到這個目的，通常將矩陣進(jìn)行分解，而矩陣分解最為常見的方法有主成分分析[2]、矩陣分解[3] 、判別分析[4]等。但是這些方法所得到的結(jié)果中會出現(xiàn)負(fù)值，可解釋性不充分。因此1999年經(jīng)典非負(fù)矩陣分解（Non-negative matrix factorization，NMF）算法在《Nature》雜志上由LEE D[5]和LEE D D[6]首次被提出，該算法的獨特之處是添加了非負(fù)限制，不僅保證了分解結(jié)果的可解釋性，還使分解后的數(shù)據(jù)具有較好的局部表達(dá)。有學(xué)者在此基礎(chǔ)上又提出了一些改進(jìn)算法[7-9]，并應(yīng)用在圖像識別、半監(jiān)督學(xué)習(xí)、聚類等領(lǐng)域[10-13]。Bucak S S 等人[8]提出了增量式非負(fù)矩陣分解（Incremental non-negative matrix factorization，INMF），是利用前一步的分解結(jié)果參與后續(xù)運算，避免了重復(fù)運算。王萬良等人[9]在此基礎(chǔ)上對該算法進(jìn)行了更新使算法更有時效性，提出了稀疏約束的非負(fù)矩陣分解增量式學(xué)習(xí)（Incremental non-negative matrix factorization with sparseconstraints，INMFSC）算法。

本文在對系數(shù)矩陣施加了稀疏約束的情況下，對增量數(shù)據(jù)的分解部分用L2，1范數(shù)來度量，從而提出了稀疏約束的L21增量式非負(fù)矩陣分解（Robust incremental non-negative matrix factorization with sparse constraints， RINMFSC）。

1 經(jīng)典非負(fù)矩陣分解

對于初始樣本 ，其中 為一個樣本，n為初始樣本的個數(shù)，則經(jīng)典非負(fù)矩陣 的分解可表示如下：

（1）

式（1）中： 為基本矩陣，

為系數(shù)矩陣， 為基本矩陣的列數(shù)。當(dāng) 時，就實現(xiàn)了對初始樣本 的降維。

非負(fù)矩陣分解（NMF）算法[5-6]采用F范數(shù)來度量 與 的逼近程度，其優(yōu)化問題可表示為如下：

min （2）

s .t.

由于目標(biāo)函數(shù) 對 和 來說都是凸函數(shù)，因此在求解問題（1）時可采用梯度下降法分別對其進(jìn)行交替更新。其更新公式如下所示：

（3）

（4）

其中，

。

2 RINMFSC算法

對給定的 個初始樣本 ， 當(dāng)有新增樣本 加入時，

。為了對新增后的樣本 進(jìn)行稀疏約束的經(jīng)典非負(fù)矩陣分解，可建立如下優(yōu)化問題：

min （5）

s.t.

其中 和 分別是對初始樣本 分解得到的基本矩陣和系數(shù)矩陣，而 和 分別是對新增樣本 后的樣本 分解得到的基本矩陣和系數(shù)矩陣 的最后一列， 為分解后基本矩陣的列數(shù)， 是稀疏限制項。 是矩陣的 范數(shù)[14]，其定義如下：

（6）

這里

，

是一個對角矩陣，并且

（7）

在優(yōu)化問題（4）中， 新增樣本的表達(dá)能力會隨著初始樣本的增加逐漸減弱。 因此當(dāng)初始樣本 足夠大時， 并不會因新樣本的增加而產(chǎn)生太大變化。因此根據(jù)以上假設(shè)，優(yōu)化問題（5）可近似為：

min?; （8）

s.t.

式（8）中：

是基本矩陣， 是當(dāng)初始樣本為 時由問題（1）計算得出，因此最終所求解的系數(shù)矩陣為 ，可得問題（8）對新增一個樣本后的數(shù)據(jù)矩陣 就近似做了分解。

為了求解問題（8），可將問題（8）的目標(biāo)函數(shù)改為矩陣跡的形式如下：

（9）

其中 ，其元素分別為：

（10）

而式（9）中的 和 都是常數(shù)，其形式為：

（11）

（12）

式（12）中： 是很小的一個正數(shù)，這樣處理是為了避免分母為0的情形。

因此， 可將優(yōu)化問題（8）等價為：

min

s.t. （13）

為了求解帶約束的優(yōu)化問題（13）對約束條件 引入拉格朗日乘子 ， ，構(gòu)造拉格朗日函數(shù)為：

（14）

分別對上式（14）中 和 求偏導(dǎo)，并令其等于零。 即

（15）

（16）

對（14）和（15）式兩邊分別乘以 和 ，利用KKT條件： ， ，可得如下的迭代法則：

（17）

（18）

根據(jù)式（17）、式（18）交替迭代得到當(dāng)新增樣本加入后最終所得系數(shù)矩陣增量部分 和新的 ，從而得到 。

3 實驗結(jié)果及其結(jié)論

3.1 數(shù)據(jù)描述及其參數(shù)設(shè)置

（1）圖1（a）中給出了USPS手寫數(shù)字識別庫[15]中部分樣本的照片數(shù)據(jù)， 該數(shù)據(jù)集共有500張分辨率為 像素的照片組成。在每個數(shù)字中我們隨機選擇20張照片共有200張照片進(jìn)行數(shù)值實驗。

（2）圖1（b）中給出了YALE人臉數(shù)據(jù)集[16]中部分樣本的照片數(shù)據(jù)， 該數(shù)據(jù)庫包含15人共165張分辨率為 像素的人臉照片數(shù)據(jù)。每類取6張共90張照片數(shù)據(jù)作為初始數(shù)據(jù)， 剩余75張照片作為新增數(shù)據(jù)進(jìn)行實驗。

在每次運算中使用隨機初值對NMF[6]，INMF[8]，INMFSC[9]和RINMFSC進(jìn)行實驗， 如果 ≥ 時， 算法終止。

本文（RINMFSC）中有兩個主要參數(shù)： 稀疏約束的參數(shù) 和基本矩陣的列數(shù)r。 通過對比多次實驗， 在USPS手寫數(shù)字識別庫中稀疏約束的參數(shù) ，設(shè)置基向量個數(shù)r為49。 在YALE人臉數(shù)據(jù)庫中稀疏約束的參數(shù) ， 設(shè)置基向量個數(shù)r 為36。

3.2 收斂效果對比

在YALE人臉數(shù)據(jù)庫和USPS手寫數(shù)字識別庫上比較NMF[6]、INMF[8]、INMFSC[9]和本文算法的收斂效果情況如圖2所示。

可得本文提出的算法的收斂效果均強于其他3個算法， 隨著迭代次數(shù)的增加，本文算法目標(biāo)函數(shù)值下降的最快，收斂效果較好，最先達(dá)到平衡，提高了運算效率。

3.3 稀疏限制的度量

首先定義稀疏函數(shù)為：

（19）

式（19）中：n為向量 的維數(shù)， 和 分別為向量 的1范數(shù)和2范數(shù)[16]。

式（19）作為稀疏度計算標(biāo)準(zhǔn)， 得到了本文算法和其他三個算法分解后的基本矩陣 的的基圖像和它們的稀疏度如圖3、圖4所示。

由圖3、圖4可知，NMF算法的基圖像最接近原圖像，但是它的稀疏度較差， 存儲率低，RINMFSC算法能得到更稀疏的基圖像，圖像的局部表達(dá)最佳。

4 結(jié)論

本文提出了一種增量式非負(fù)矩陣分解新的改進(jìn)算法，并在YALE人臉數(shù)據(jù)和USPS 手寫數(shù)據(jù)庫上對該算法進(jìn)行了驗證， 結(jié)果顯示與其他算法相比該算法仍然保持較好的收斂速度， 不僅減少了計算時間， 而且得到了更為稀疏的基圖像，具有較強的局部表達(dá)能力。 但是， 該算法的不足之處是迭代初值和稀疏參數(shù)的選取， 目前沒有一個統(tǒng)一的標(biāo)準(zhǔn)。

參考文獻(xiàn)

[1] PARDALOS PM. Approximate dynamic programming：solvingthe curses of dimensionality[M]. Wiley， 2009：68-71.

[2] SHI W Y，GUO Y F，XUE X Y.A kernel principal component analysis algorithm for solving large scale data sets problem[J].Journal of Software，2009， 8（20）： 2153-2159 （in Chinese）.

[3] GOLUB G H， REINSCH C. Singular Value Decomposition and Least Squares Solutions[M]. Springer Berlin Heidelberg， 1971：403-420.

[4] XIAOHENG TAN， LU DENG.Optimized regularized linear discriminant analysis for feature extraction in face recognition[J]. Evolutionary Intelligence，2019（12）1：73-82

[5] LEE D. Learning the parts of objects with non-negative matrix factorization[J]. Nature， 1999， 401（6755）：788.

[6] LEE D D. Algorithms for non-negative matrix factorization[J]. Advances in Neural Information Processing Systems， 2001， 13（6）：556--562.

[7] 蔡競，張嘉琪，錢康. 改進(jìn)增量式非負(fù)矩陣分解算法及其在人臉識別中的應(yīng)用[J]. 信息通信，2016（7）：4-7，8.

[8] BUCAK S S， GUNSEL B. Incremental subspace learning via non-negative matrix factorization[J]. Pattern Recognition， 2009， 42（5）：788-797.

[9] 王萬良，蔡競.稀疏約束下非負(fù)矩陣分解的增量學(xué)習(xí)算法[J].計算機科學(xué)， 2014， 41（8）：241-244.

[10] 李向利，梅建平，莫元健.基于超圖正則NMF的自適應(yīng)半監(jiān)督多視圖聚類[J/OL].廣西師范大學(xué)學(xué)報（自然科學(xué)版）：1-16[2024-04-25].https：//doi.org/10.16088/j.issn.1001-6600.2023110202.

[11] 陳善學(xué)，許少華.基于圖拉普拉斯正則化的柯西非負(fù)矩陣分解高光譜解混[J/OL].激光與光電子學(xué)進(jìn)展：1-16[2024-04-25].http：//kns.cnki.net/kcms/detail/31.1690.tn.20231214.0028.022.html.

[12] 劉敬，李康欣，張悠，等.多圖正則多核非負(fù)矩陣分解高光譜圖像解混[J].光學(xué)精密工程，2022，30（14）：1657-1668.

[13] 董秋宇.非負(fù)矩陣分解及其在遮擋人臉識別中的應(yīng)用[D].西安：西安電子科技大學(xué)，2022.

[14] KONG D， HUANG H. Robust nonnegative matrix factorization using L21-norm[J] AcmConference on Information & Knowledge Management ， 2011：673-682.

[15] 楊亮東.基于L_（2.1）稀疏限制的增量式非負(fù)矩陣分解[D]. 烏魯木齊：新疆大學(xué)，2019.

[16] 楊亮東，楊志霞.稀疏限制的增量式魯棒非負(fù)矩陣分解及其應(yīng)用[J].計算機應(yīng)用，2019，39（5）：1275-1281.