基于权重曼哈顿非负矩阵分解的图像修复和聚类方法

陶盈吟 杨仪 代祥光 苏晓杰

摘要

当数据中存在大量椒盐噪声时，传统的鲁棒非负矩阵分解方法无法获得更具有鲁棒性的低维特征.为了解决该问题，本文提出了一种更具有鲁棒性的权重曼哈顿非负矩阵分解来修复被污染的数据点以及通过曼哈顿矩阵分解获得鲁棒的特征表示.本文提出的模型可以被看作為非凸非光滑的优化问题，可以通过加速梯优化理论和最小一乘法求其局部最优解.通过对人脸图像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