基于權重曼哈頓非負矩陣分解的圖像修復和聚類方法

陶盈吟 楊儀 代祥光 蘇曉杰

摘要

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

關鍵詞

曼哈頓非負矩陣分解;魯棒性;凸優化;降維

中圖分類號 O235

文獻標志碼 A

0 引言

非負矩陣分解（NMF）[1]是一種經典的無監督降維學習方法，即NMF尋求兩個非負矩陣使其乘積非常近似于原始數據矩陣.通常，一個矩陣是基矩陣，用于表示原始的輸入數據矩陣;另一個矩陣是系數矩陣，用來表示低維特征[2]. 根據文獻[3-4]，非負矩陣分解的非負性低維表示更有意義，因為學習到的特征更符合人類感知. 由于出色的數據表示方法，NMF被廣泛應用于聚類[5-6]、推薦系統[7]、社區檢測[8]和半監督學習[9]等.

盡管NMF可以應用于各種領域，但是當原始數據被異常值和噪聲破壞時，傳統的NMF無法學習魯棒的低維表示.因此，許多魯棒NMF方法被用來消除數據中的異常值和噪聲[5-10]. Hamza等[5]首先提出了超曲面函數（HCNMF）來代替Frobenius范數.與標準NMF相比，HCNMF可以實現更魯棒的表示，但是其優化算法在Armijo線搜索上花費了大量時間.Kong等[6]提出了L2，1范數作為損失函數來處理異常值和噪聲.相比HCNMF，雖然該方法對噪聲不太敏感，但因為其非光滑的損耗函數，所提出的算法導致分解過程更加復雜.為了解決這個問題，Guan等[7]提出了曼哈頓非負矩陣分解，該算法通過Nesterov的優化方法[11]優化L1范數.Gao等[8]提出了一個上限閾值NMF來過濾異常值，但是，沒有具體的方法來確定異常值閾值.Zhang等[9]提出了L1范數正則化的NMF來將被污染的數據矩陣分解成一個稀疏誤差矩陣和兩個非負矩陣.Guan等[10]提出了三西格瑪規則來檢測異常值，并提出了截斷柯西損失函數（CauchyNMF）來處理異常值.盡管CauchyNMF可以消除高斯分布中的離群值和噪聲（例如椒鹽噪聲等），但它不能應用于處理大量的椒鹽噪聲.

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

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

2） 為了實現數據恢復并從損壞的數據中學習魯棒的表示，我們介紹了如何構建噪聲位置與噪音點的關系.結合曼哈頓矩陣分解，可以從損壞的數據中獲得干凈的數據空間，并從恢復的數據中獲得魯棒的低維表示.

3.1 圖像修復

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

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

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

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

3.2 聚類

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

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

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

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

4 結束語

本文提出了一種有效的權值曼哈頓非負矩陣分解框架用于處理椒鹽噪聲.該框架的優勢如下：

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

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

3）聚類實驗結果表明本文提出的算法可以得到更加穩定的子空間并得到較好的聚類效果.

參考文獻

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

資助項目 重慶市高校市級重點實驗室資助項目（[2017]3）;重慶市發展和改革委員會資助項目（2017[1007]）;重慶市教委科技研究項目（KJQN201901203，KJQN201901218，KJ1710248）;重慶市自然科學基金（cstc2019jcyj-bshX0101）

作者簡介陶盈吟，女，碩士生，研究方向為優化算法、機器學習.597370352@qq.com

楊儀（通信作者），女，博士，研究方向為神經網絡、非線性動力系統.yang1595@126.com