王宇辰

(兰州财经大学统计学院,甘肃兰州 730020)

0 引言

随着大规模海量数据的不断产生,图像、音频等非结构化数据通常表示为取值非负的高维数据矩阵。处理高维数据矩阵时,通过对矩阵进行分解可完成数据压缩与聚类等任务。非负矩阵分解(Non-negative Matrix Factorization,NMF)是一种简洁直观、效果优良的矩阵分解技术[1],其核心思想是在一定约束条件下将原始数据分解为低维的基矩阵和系数矩阵,并在低维矩阵中能够更好地体现出数据本身所隐含的性质,对数据挖掘具有重要的意义。非负矩阵分解是高维数据聚类的新方法,在机器学习、生物信息[2]等领域具有广泛的应用。

本文旨在对非负矩阵分解方法的基本原理和发展现状进行综述。本文所用符号的具体说明见下表1。

1 非负矩阵分解的基本原理

矩阵分解方法是应用数学领域的研究重点,其目的在于对原始矩阵在一定约束条件下进行分解,从而简化矩阵运算效率并取得良好的解读性。在工程计算领域中,矩阵的QR分解、Cholesky分解在求解线性方程等问题上效果良好;在机器学习领域中,矩阵的奇异值分解可完成对数据的特征提取与压缩,并广泛应用于图像处理、推荐系统等实际问题。

1999年,Lee[3]在《Nature》上发表了关于非负矩阵分解的相关研究,非负矩阵分解算法的基本思想是:在对矩阵元素的非负约束条件下,将原有的数据矩阵X分解为基矩阵U和系数矩阵V,基矩阵U的每一列代表一个局部特征,系数矩阵V的每一列代表一个样本在低维空间中的表示。具体定义如下:

给定m维的非负随机向量x,其n个观测样本表示为xj,j=1,2,...,n,m维的n个列向量x组成数据矩阵X。NMF算法是将X分解成非负的m×r维的基矩阵U和非负的r×n维的系数矩阵V,使得:

m×n维的噪声矩阵E表示逼近误差,一般要求较小且快速收敛。r表示矩阵Y的秩,通常根据实际情况确定并满足 (m+n)r＜mn,即利用少量的基向量便可表示高维数据。若采用欧式距离来度量矩阵分解的损失,则NMF可表述为式(2)所示的优化问题:

表1 符号说明Tab.1 Symbol description

2005年,Ding[4]等对非负矩阵与聚类算法的等价性进行探讨,并以K-means算法为例对非负矩阵分解的聚类特性加以说明。

假设X=[x1,x2,...,xn]为n个数据点,K-means算法将其划分为k个类。K-means算法的目标函数可写成:

其中uk为每一类的类中心,k为预先设定的聚类类别数目。

若将K-means算法得到的类中心表述为U=(u1,...,,uk),将聚类结果用矩阵H表示,hki= 1 表示xi属于第k类ck,否则hki= 0。此时,可将K-means算法的目标函数写为:

不难看出,K-means算法的目标函数与NMF之间存在某种等价关系。U可理解为聚类中心矩阵,V可理解为聚类标签矩阵。当约束矩阵V为正交矩阵时,NMF分解问题与K-means聚类问题等价,如下式(4)所示。

2 非负矩阵分解方法的发展现状

根据实际问题的需要,近些年出现了大量非负矩阵分解的拓展研究与算法。主要围绕以下几个方面:(1)矩阵分解约束条件的设计,其目的是放松非负性约束使得更符合实际问题求解需要;(2)迭代更新算法的设计,其目的是在求解NMF时更快更稳定收敛;(3)实际应用。

2.1 矩阵分解约束条件的设计

在原始NMF算法的基础上,根据实际问题的需要,研究者们提出一系列改进的非负矩阵分解方法。

2001年,Guillamet[5]使用对角矩阵Q对原始数据矩阵X进行加权,分解问题变为XQ≈UVQ,得到加权的矩阵分解结果。2004年,Hoyer借助稀疏编码思想,提出了稀疏约束的非负矩阵分解模型,对分解后的矩阵U和V施加稀疏性约束,从而取得更好的聚类精度。2008年,Cai[6]提出流形上的非负矩阵分解算法。其核心思想是,在非负矩阵分解度量欧式空间距离的基础上,附加几何流形上度量的数据亲疏程度,使得聚类时所考虑特征的距离度量方式更加全面,优化目标函数变为:

由于现实问题中存在大量混合符号的数据,Ding提出Semi-NMF算法,其核心思想是当数据矩阵X元素有正有负时,仅约束系数矩阵V元素非负,基矩阵U中的元素可正可负,优化目标函数则变为:可将Semi-NMF视为K-means算法的“软聚类”版本。2010年,Lee提出了半监督非负矩阵分解算法,使得预先具备相同标签信息的数据点被聚为一类。2017年,Trigeorgis[7]提出了深度矩阵分解框架,对分解出的矩阵V进行多次矩阵分解,从而得到可反映深层次聚类信息的矩阵。

2.2 迭代更新算法的设计

非负矩阵分解的求解过程较为复杂。已有研究者对非负矩阵分解的求解优化方法进行设计,总体上可分为三大类:乘性更新方法、投影梯度法和交替非负最小二乘方法,其中乘性迭代算法应用最为广泛。

Lee在非负矩阵分解框架下给出了乘性更新算法。在原有的非负矩阵分解问题中,同时求解矩阵U和V是非凸问题,求解较为困难。乘性更新算法原理是在固定U或V的情况下更新求解另一矩阵,此时为凸优化问题。在预设迭代次数时,可完成对矩阵U、V的近似求解。矩阵U和V的更新公式如下式(5)所示。

2.3 实际应用

非负矩阵分解可用于解决数据的聚类问题,是目前机器学习、模式识别等领域的研究热点,在人脸识别、文本挖掘[8]等方面应用广泛。

人脸识别是基于人脸特征信息进行身份识别的识别技术,是计算机视觉领域的重要研究问题。人脸识别任务中关键步骤可理解为图像聚类的过程。将每张图像数据矩阵元素规范化至[0,1],并转换为列向量形成数据矩阵X,对数据矩阵X进行非负矩阵分解,可得到具有人脸识别信息的矩阵V完成人脸识别。

文本聚类包括根据文本内容对文本主题进行划分。在多视角聚类问题中,同一文档可能由不同语言进行表述,问题则变为对多种不同语言不同主题的文本进行聚类。假设文本中具有v种语言,每种语言的数据矩阵记为X(v),多视角聚类[9]通过非负矩阵分解得到各视角的聚类结果V(v),再通过正则化方法求出聚类结果的一致表述V*,完成多视角的文本聚类。

3 非负矩阵分解进一步研究的方向

尽管已有诸多学者对非负矩阵分解的分解形式、求解方法进行研究,但非负矩阵分解中仍存在一些细节问题待研究与讨论。

3.1 矩阵初始化

非负矩阵分解的优化过程是迭代更新求解,最终的收敛解依赖于矩阵初始值。传统的非负矩阵分解初始化采用均匀随机数填充,这种方法并没有考虑数据本身的信息,当矩阵初始值与最优解距离较远时,所需的计算成本较大。如何设计出计算成本较小、收敛性较快、更具理论依据的矩阵初始化方法是后续待研究的问题。

3.2 分解的秩 r的确定

非负矩阵分解是将Xm×n分解为Um×r和Vr×n,分解后的秩r要满足条件(m+n)r＜mn,数据压缩程度与秩r的值关系密切。目前确定秩r的方法往往基于实验效果与人为经验,并没有完善的理论对秩r的取值进行客观评价。如何采用先验信息来完成秩r的最优值选择还需进一步讨论。

4 结论

本文对非负矩阵分解的思想、算法和应用等方面进行了详细说明,指出了现有研究的不足,展望了进一步研究的方向。