非负矩阵分解及其改进方法

刘志扬

(广东科技学院 基础部， 广东 东莞 523083)



非负矩阵分解及其改进方法

刘志扬

(广东科技学院 基础部， 广东 东莞 523083)

首先,给出非负矩阵分解的数学形式，分析欧式距离和相对熵(KL)散度两种分解误差评价函数.然后,针对3种特殊形式的非负矩阵进行分解方法的改进，优化函数和迭代过程分别适用于正交非负矩阵、凸非负矩阵、投影非负矩阵的分解.结果表明:提出的改进方法简化了非负矩阵分解的过程.

非负矩阵; 非负分解; 优化函数; 迭代方程

非负矩阵分解，是数据挖掘领域的一个关键问题.通过非负矩阵分解，原始矩阵的维度得以降低，且分解结果中的非负表达更适用于实际问题.由于非负矩阵分解的重要性，许多学者对这一领域开展了理论和实践研究，尤其在分解过程的收敛速度、分解过程的复杂性方面更加关注[1-4].非负矩阵分解理论建立之初，是针对用非负矩阵来表达的多维数据[5].同时，非负矩阵分解要求分解后的矩阵也要满足非负的特征.显然，这种约束的存在使得分解结果表现出一定的稀疏性，但这种稀疏性也可以有效地抵制来自外部的干扰.稀疏性特征也反映出非负矩阵分解只能清晰地表达多维数据的部分特征[6].随着非负矩阵分解的应用日益增多，学者们又发现了其聚类功能，从而拓宽了非负矩阵分解的应用领域[7-8].Kitamura等[9]在一般非负矩阵分解过程中进一步添加新的约束条件，使分解得到的结果可以成为另一个分解结果上的投影.在此基础上，正交性约束条件也被添加进来，非负矩阵分解的迭代过程得到更新，从而加快了拉格朗日最优解获得的收敛速度.Ludena等[10]在一般非负矩阵分解过程中添加了一个凸性约束，从而构建了一种凸非负矩阵的分解方法.这种方法获得的分解结果更加稀疏，但也增强了对凸非负矩阵多维数据的解释能力.本文在一般非负矩阵分解过程的基础上，探寻几种改进分解方法.

1 非负矩阵分解的理论基础

对于实际问题而言，非负的向量表达、非负的矩阵分解往往更有意义.正是这种实际需求，催生了非负矩阵分解方法的出现.从数学形式上看，高维数据矩阵经过非负矩阵分解后，求得的低维矩阵中的元素都应该是非负的.因为非负性要求的存在，也必然会使分解结果在一定程度上只能采用稀疏表达的结果.稀疏表达并不一定是不利的，在很多情况下甚至可以抵御外部的干扰.

至此，给出一个非负矩阵分解的一般性描述.设定Y是一个非负矩阵，它可以进一步分解为两个非负矩阵A和B，并且可以满足Y≈AB.如果矩阵A的列数少于矩阵B的列数，那么，就只能实现对矩阵Y的稀疏表达.这时，如果要尽可能地实现对矩阵Y的表达，就必须找到原始矩阵的类似结构，矩阵A和矩阵B的乘积才能实现对矩阵Y的最佳拟合.还需要指出，非负矩阵分解获得的投影系数，不会出现有正有负的情况，这一点和主成分分析方法存在明显不同.

假设给定的原始矩阵Y的维度是p×q，矩阵中全部元素都是非负的，同时，维度p大于维度q.经过非负矩阵分解的处理，原始矩阵Y被分解为两个非负矩阵A和B.其中，非负矩阵A的维度是p×s，非负矩阵B的维度是p×s.这里，维度s一般是一个先行给定的参数，且这个参数需满足s

对于矩阵A和矩阵B而言，因为非负属性的限制条件的存在，对于非负矩阵Y而言 ，很难做出准确性分解，一般都是带有一定误差的分解.因此,分解后3个矩阵的关系是Y≈AB.虽然很难实现非负矩阵的准确分解，但还是希望分解结果和原始矩阵之间的误差尽可能小些.为了分析这种误差的大小，一般要设定一个评价函数，用以判断非负矩阵Y的非负分解结果误差是否足够小.

第1种常见的评价函数，一般用欧式距离设计，具体形式为

(1)

由欧式距离评价函数，可评价非负矩阵分解结果和原始非负矩阵的近似情况，可得优化函数为

(2)

优化过程中，每一步骤的迭代操作为

(3)

第二种常见的评价函数，一般用相对熵(KL)散度设计，具体形式为

(4)

根据KL散度评价函数，可以评价非负矩阵分解结果和原始非负矩阵的近似情况，据此设计出的优化过程的2个迭代操作为

(5)

2 非负矩阵分解的改进方法

在实际应用中，非负矩阵存在一些特殊的形式，需要对原有的分解方法进行有针对性的改进.文中将分别探讨3类特殊的非负矩阵：正交非负矩阵、凸非负矩阵、投影非负矩阵.

2.1 正交非负矩阵的对应分解方法

在数据分类等实际应用中，正交非负矩阵有着非常高的实用价值.正交非负矩阵又可以分为水平单侧方向上的正交非负矩阵、垂直单侧方向上的正交非负矩阵、双向正交非负矩阵等3种类型.

1) 水平单侧方向上的正交非负矩阵分解.水平单侧方向上的非负矩阵，在非负分解过程中的优化函数为

(6)

在水平单侧方向上非负矩阵分解的过程中，所用的迭代公式分别为

(7)

2) 垂直单侧方向上的正交非负矩阵分解.垂直单侧方向上的非负矩阵，在非负分解过程中的优化函数为

(8)

在垂直单侧方向上非负矩阵分解的过程中，所用的迭代公式分别为

(9)

3) 水平垂直双向上的正交非负矩阵分解.水平垂直双向上的非负矩阵，在非负分解过程中的优化函数为

(10)

在水平垂直双向上非负矩阵分解的过程中，所用的迭代公式分别为

(11)

(12)

(13)

2.2 凸非负矩阵的对应分解方法

凸非负矩阵分解，一般是在考虑原始矩阵不受任何限制条件下展开的.在这种情况下，只要求分解出的矩阵有一部份是非负的，对另一部分则没有限制.

假设要求分解出的矩阵B是非负的，对矩阵A没有要求，那么，优化问题转变为

(14)

此时，可以对A施加一个凸性约束，即

(15)

式(15)也可以写为

(16)

至此，可以将凸非负矩阵分解优化过程的迭代公式设计为

(17)

(18)

2.3 投影非负矩阵的对应分解方法

投影非负矩阵的非负分解，可以写为

(19)

对于上述优化问题，优化过程中的迭代公式为

(20)

对于投影非负矩阵的非负分解，还可以进一步施加一个正交性约束，此时优化问题变为

(21)

对应的迭代公式变为

(22)

至此，给出了3种不同非负矩阵的非负分解方法，以及具体的优化函数和迭代操作过程.

3 结束语

针对非负矩阵的分解效果评价，提出欧式距离评价函数和KL散度评价函数.对正交非负矩阵、凸非负矩阵、投影非负矩阵的分解方案进行改进，分别建立分解过程的优化函数.分解结果显示，文中改进的分解方法，不仅使3种非负矩阵的分解过程得到简化，分解效率得到提升，分解误差也符合两种评价函数的检验标准.

[1] 李磊，李静.三端点区间数的判断矩阵分解及基于Fermat的算法集结研究[J].数学的实践与认识,2015,45(17):214-221.

[2]NEDUNGADIP,SMRUTHYTK.Personalizedmulti-relationalmatrixfactorizationmodelforpredictingstudentperformance[J].AdvancesinIntelligentSystemsandComputing,2016,38(4):163-172.

[3] 方蔚涛，马鹏，成正斌，等.二维投影非负矩阵分解算法及其在人脸识别中的应用[J].自动化学报,2012,38(9):1503-1512.

[4] 涂丹丹，舒承椿，余海燕.基于联合概率矩阵分解的上下文广告推荐算法[J].软件学报,2013,24(3):454-464.

[5]MESAROSA,HEITTOLAT,DIKMENO,etal.Soundeventdetectioninrealliferecordingsusingcoupledmatrixfactorizationofspectralrepresentationsandclassactivityannotations[C]∥InternationalConferenceonAcoustics,SpeechandSignalProceeding.London：AEAT，2015:151-155.

[6] 刘维湘，郑南宁，游屈波.非负矩阵分解及其在模式识别中的应用[J].科学通报,2006,51(3):241-250.

[7] 杨粤涛，朱明，贺柏根，等.采用改进投影梯度非负矩阵分解和非采样Contourlet变换的图像融合方法[J].光学精密工程,2011,19(5):1143-1151.

[8] 宋海州，徐强，田朝薇.计算非负不可约矩阵谱半径的新算法[J].华侨大学学报(自然科学版),2011,32(3):348-351.

[9]KITAMURAD,ONON,SAWADAH,etal.Efficientmultichannelnonnegativematrixfactorizationexploitingrank-1spatialmodel[C]∥InternationalConferenceonAcoustics,SpeechandSignalProceeding.London:AEAT，2015:276-280.

[10] LUDENA C J,GALLARDO A A.Acoustic event classification using spectral band selection and non-negative matrix factorization-based features[J].Expert Systems with Applications,2016,46(8):77-86.

(责任编辑： 钱筠 英文审校： 黄心中)

Research on Non Negative Matrix Factorization and It′s Improvement Method

LIU Zhiyang

(Basic Course Department， Guangdong University of Science and Technology, Dongguan 523083, China)

First of all, mathematical form of non negative matrix factorization is presented, and two decomposition error evaluation functions of Euclidean distance and relative entropy divergence are presented. Then, we improve the decomposition method for 3 kinds of non negative matrix, the used optimization function and the iteration process can respectively applied to the decomposition of orthogonal nonnegative matrix, convex nonnegative matrix and projection non negative matrix. The results show that the improved method simplifies the process of non negative matrix factorization.

non negative matrix; non negative decomposition; optimization function; iterative equation

10.11830/ISSN.1000-5013.201606025

2016-10-13

刘志扬(1964-)，男，副教授，主要从事非负矩阵分解算法的研究.E-mail:nbxylzy@163.com.

广东省教育厅、财政厅立项资助课题(2013WYXM0136)

O 151.21

A

1000-5013(2016)06-0782-04