基于權(quán)重曼哈頓非負(fù)矩陣分解的圖像修復(fù)和聚類方法

陶盈吟 楊儀 代祥光 蘇曉杰

摘要

當(dāng)數(shù)據(jù)中存在大量椒鹽噪聲時(shí)，傳統(tǒng)的魯棒非負(fù)矩陣分解方法無法獲得更具有魯棒性的低維特征.為了解決該問題，本文提出了一種更具有魯棒性的權(quán)重曼哈頓非負(fù)矩陣分解來修復(fù)被污染的數(shù)據(jù)點(diǎn)以及通過曼哈頓矩陣分解獲得魯棒的特征表示.本文提出的模型可以被看作為非凸非光滑的優(yōu)化問題，可以通過加速梯優(yōu)化理論和最小一乘法求其局部最優(yōu)解.通過對(duì)人臉圖像ORL數(shù)據(jù)集加入椒鹽噪聲，實(shí)驗(yàn)結(jié)果表明本文提出的算法在圖像修復(fù)和學(xué)習(xí)特征表示方面更有效、更魯棒.

關(guān)鍵詞

曼哈頓非負(fù)矩陣分解;魯棒性;凸優(yōu)化;降維

中圖分類號(hào) O235

文獻(xiàn)標(biāo)志碼 A

0 引言

非負(fù)矩陣分解（NMF）[1]是一種經(jīng)典的無監(jiān)督降維學(xué)習(xí)方法，即NMF尋求兩個(gè)非負(fù)矩陣使其乘積非常近似于原始數(shù)據(jù)矩陣.通常，一個(gè)矩陣是基矩陣，用于表示原始的輸入數(shù)據(jù)矩陣;另一個(gè)矩陣是系數(shù)矩陣，用來表示低維特征[2]. 根據(jù)文獻(xiàn)[3-4]，非負(fù)矩陣分解的非負(fù)性低維表示更有意義，因?yàn)閷W(xué)習(xí)到的特征更符合人類感知. 由于出色的數(shù)據(jù)表示方法，NMF被廣泛應(yīng)用于聚類[5-6]、推薦系統(tǒng)[7]、社區(qū)檢測(cè)[8]和半監(jiān)督學(xué)習(xí)[9]等.

盡管NMF可以應(yīng)用于各種領(lǐng)域，但是當(dāng)原始數(shù)據(jù)被異常值和噪聲破壞時(shí)，傳統(tǒng)的NMF無法學(xué)習(xí)魯棒的低維表示.因此，許多魯棒NMF方法被用來消除數(shù)據(jù)中的異常值和噪聲[5-10]. Hamza等[5]首先提出了超曲面函數(shù)（HCNMF）來代替Frobenius范數(shù).與標(biāo)準(zhǔn)NMF相比，HCNMF可以實(shí)現(xiàn)更魯棒的表示，但是其優(yōu)化算法在Armijo線搜索上花費(fèi)了大量時(shí)間.Kong等[6]提出了L2，1范數(shù)作為損失函數(shù)來處理異常值和噪聲.相比HCNMF，雖然該方法對(duì)噪聲不太敏感，但因?yàn)槠浞枪饣膿p耗函數(shù)，所提出的算法導(dǎo)致分解過程更加復(fù)雜.為了解決這個(gè)問題，Guan等[7]提出了曼哈頓非負(fù)矩陣分解，該算法通過Nesterov的優(yōu)化方法[11]優(yōu)化L1范數(shù).Gao等[8]提出了一個(gè)上限閾值NMF來過濾異常值，但是，沒有具體的方法來確定異常值閾值.Zhang等[9]提出了L1范數(shù)正則化的NMF來將被污染的數(shù)據(jù)矩陣分解成一個(gè)稀疏誤差矩陣和兩個(gè)非負(fù)矩陣.Guan等[10]提出了三西格瑪規(guī)則來檢測(cè)異常值，并提出了截?cái)嗫挛鲹p失函數(shù)（CauchyNMF）來處理異常值.盡管CauchyNMF可以消除高斯分布中的離群值和噪聲（例如椒鹽噪聲等），但它不能應(yīng)用于處理大量的椒鹽噪聲.

基于曼哈頓矩陣分解框架，本文提出了權(quán)重曼哈頓非負(fù)矩陣分解（WNMF）來克服上述問題.WNMF使用權(quán)值矩陣來標(biāo)記污染點(diǎn)和未污染點(diǎn)，并將該權(quán)重矩陣引入曼哈頓非負(fù)矩陣分解.因此，WNMF不僅可以恢復(fù)損壞的數(shù)據(jù)矩陣，還可以通過恢復(fù)的數(shù)據(jù)矩陣來學(xué)習(xí)更加魯棒的特征表示.由于WNMF的目標(biāo)函數(shù)是非凸且非平滑的，因此可以通過塊坐標(biāo)下降法將其轉(zhuǎn)化為三個(gè)凸且非平滑優(yōu)化問題[12]，并交替求解直至收斂.第一個(gè)非平滑優(yōu)化問題可以看作是最小絕對(duì)偏差問題的變種問題[7]，可以通過最小一乘法[13]進(jìn)行優(yōu)化. 另外兩個(gè)非光滑優(yōu)化問題是L1范數(shù)優(yōu)化問題[6]，可以通過Nesterov的光滑方法[11]進(jìn)行優(yōu)化.本文的主要貢獻(xiàn)概述如下：

1） 標(biāo)準(zhǔn)NMF和存在的NMF變種方法未研究原始數(shù)據(jù)與噪聲位置之間的關(guān)系. 在本文中，我們提出了一個(gè)權(quán)重曼哈頓非負(fù)矩陣分解框架來處理椒鹽噪聲. 此外，該方法利用曼哈頓距離作為損失函數(shù)，并利用權(quán)重矩陣來約束修復(fù)矩陣.

2） 為了實(shí)現(xiàn)數(shù)據(jù)恢復(fù)并從損壞的數(shù)據(jù)中學(xué)習(xí)魯棒的表示，我們介紹了如何構(gòu)建噪聲位置與噪音點(diǎn)的關(guān)系.結(jié)合曼哈頓矩陣分解，可以從損壞的數(shù)據(jù)中獲得干凈的數(shù)據(jù)空間，并從恢復(fù)的數(shù)據(jù)中獲得魯棒的低維表示.

3.1 圖像修復(fù)

圖1給出了5類非負(fù)矩陣分解算法的圖像修復(fù)效果，表2給出了污染數(shù)據(jù)矩陣與修復(fù)數(shù)據(jù)矩陣的峰值信噪比.通過圖1和表2，我們得出如下結(jié)論：

1） WNMF和CauchyNMF對(duì)椒鹽噪聲并不非常敏感，其余算法無法從帶有椒鹽噪聲的ORL數(shù)據(jù)集中得到清晰的修復(fù)圖像集.

2） WNMF和CauchyNMF具有更好的修復(fù)效果以及較高的峰值信噪比，這意味著WNMF和CauchyNMF可以得到較小的相對(duì)誤差值.

3） 隨便污染比例增加，WNMF仍然保持最高的峰值信噪比，而CauchyNMF的峰值信噪比急劇下降，這說明CauchyNMF無法處理污染比例較高的椒鹽噪聲.

3.2 聚類

圖2給出了5類非負(fù)矩陣分解算法的聚類效果，我們得出如下結(jié)論：

1） WNMF和CauchyNMF具有更好的聚類效果，這意味著WNMF和CauchyNMF可以學(xué)到有效的子空間.

2） 在污染比例較小情況下，CauchyNMF有著較好的聚類效果，然而，隨著污染比例增加，CauchyNMF的聚類效果急劇下降.

3） WNMF具有相對(duì)穩(wěn)定的聚類準(zhǔn)確值，這說明WNMF對(duì)椒鹽噪聲更具有魯棒性.隨著污染比例增加，WNMF始終保持相對(duì)較好的聚類效果.

4 結(jié)束語

本文提出了一種有效的權(quán)值曼哈頓非負(fù)矩陣分解框架用于處理椒鹽噪聲.該框架的優(yōu)勢(shì)如下：

1）相比于傳統(tǒng)的非負(fù)矩陣分解算法，本文提出的算法能更有效處理椒鹽噪聲;

2）隨著椒鹽噪聲污染比例增加，本文提出的算法仍然可以完成圖像修復(fù)以及獲得較小的分解誤差;

3）聚類實(shí)驗(yàn)結(jié)果表明本文提出的算法可以得到更加穩(wěn)定的子空間并得到較好的聚類效果.

參考文獻(xiàn)

References

[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] Wu W H，Kwong S，Hou J H，et al.Simultaneous dimensionality reduction and classification via dual embedding regularized nonnegative matrix factorization[J].IEEE Transactions on Image Processing，2019，28（8）：3836-3847

[3] Palmer S E.Hierarchical structure in perceptual representation[J].Cognitive Psychology，1977，9（4）：441-474

[4] Logothetis N K，Sheinberg D L.Visual object recognition[J].Annual Review of Neuroscience，1996，19（1）：577-621

[5] Hamza A B，Brady D J.Reconstruction of reflectance spectra using robust nonnegative matrix factorization[J].IEEE Transactions on Signal Processing，2006，54（9）：3637-3642

[6] Kong D G，Ding C，Huang H.Robust nonnegative matrix factorization using L21-norm[C]∥Proceedings of the 20th ACM International Conference on Information and Knowledge Management，2011：673-682

[7] Guan N，Tao D，Luo Z，et al.MahNMF：Manhattan non-negative matrix factorization[J].arXiv preprint，2012，arXiv：1207.3438

[8] Gao H C，Nie F P，Cai W D，et al.Robust capped norm nonnegative matrix factorization[C]∥Proceedings of the 24th ACM International on Conference on Information and Knowledge Management，2015：871-880

[9] Zhang L J，Chen Z G，Zheng M，et al.Robust non-negative matrix factorization[J].Frontiers of Electrical and Electronic Engineering in China，2011，6（2）：192-200

[10] Guan N Y，Liu T L，Zhang Y，et al.Truncated Cauchy non-negative matrix factorization[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2019，41（1）：246-259

[11] Nesterov Y.Smooth minimization of non-smooth functions[J].Mathematical Programming，2005，103（1）：127-152

[12] Lin C J.Projected gradient methods for nonnegative matrix factorization[J].Neural Computation，2007，19（10）：2756-2779

[13] Ho N D，van Dooren P，Blondel V D.Descent methods for nonnegative matrix factorization[M].Numerical Linear Algebra in Signals，Systems and Control.Springer，Dordrecht，2011：251-293

Image recovery and clustering approach based on weighted

Manhattan non-negative matrix factorization

TAO Yingyin1 YANG Yi1 DAI Xiangguang1 SU Xiaojie2

1 Key Laboratory of Intelligent Information Processing and Control of Chongqing Municipal Institutions

of Higher Education，Chongqing Three Gorges University，Chongqing 404100

2 College of Automation，Chongqing University，Chongqing 400044

Abstract Traditional robust non-negative matrix factorization methods cannot achieve robust low-dimensional features while the data is heavily contaminated by Salt and Pepper noise.To address this issue，this paper proposes a more robust weighted Manhattan non-negative matrix factorization to recover the contaminated data and obtain robust part-based representations.Our proposed model can be formulated as a non-convex and non-smooth problem，which can be solved by the accelerated gradient method and the rank-one-residual-iteration method.Experiments on the ORL face dataset contaminated by Salt and Pepper noise demonstrate that our proposed algorithm is more effective and robust in image recovery and feature representation learning.

Key words Manhattan non-negative matrix factorization;robustness;convex optimization;dimensional reduction

收稿日期 2020-02-26

資助項(xiàng)目 重慶市高校市級(jí)重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目（[2017]3）;重慶市發(fā)展和改革委員會(huì)資助項(xiàng)目（2017[1007]）;重慶市教委科技研究項(xiàng)目（KJQN201901203，KJQN201901218，KJ1710248）;重慶市自然科學(xué)基金（cstc2019jcyj-bshX0101）

作者簡(jiǎn)介陶盈吟，女，碩士生，研究方向?yàn)閮?yōu)化算法、機(jī)器學(xué)習(xí).597370352@qq.com

楊儀（通信作者），女，博士，研究方向?yàn)樯窠?jīng)網(wǎng)絡(luò)、非線性動(dòng)力系統(tǒng).yang1595@126.com