基于约束非负矩阵分解的图像表示

对于图像的约束非负矩阵分解

摘要：非负矩阵分解(NMF)对于寻找非负数据的块基础和线性表示是一个常用的方法。它已经广泛的应用于各种应用，比如模式识别，信息检索，计算机视觉。但是，NMF本质上是一个非监督方法，不能利用标签信息。在本文中，我们提出一种新的半监督矩阵分解方法，叫约束非负矩阵分解(CNMF)，将标签作为附加约束合并进来。特别地，本文显示出结合标签信息能非常简洁地提高矩阵分解的识别能力。我们利用两个函数公式和提供的相应优化问题的更新解决方法来研究所提出的CNMF方法。通过实际数据的评估，我们所提出的方法和最先进的方法相比更有效。

索引词：非负矩阵分解，半监督学习，降维，聚类

1.简介

许多数据分析中一个基础的问题就是寻找一个合适的表示数据[1]，[2]，[3]，[4]，[5]，[6]，[7]，[8]。可以应用一个非常有效的方法表示数据之间的潜在结构。矩阵分解技术作为这类数据表示的基础工具已经得到越来越多的注意。运用不同的标准已经得到了大量不同的方法。最流行的技术包括主成分分析(PCA)[9]，奇异值分解(SVD)[10]，和向量量化[11]。矩阵分解的中心是找到两个或者更多的因子产生原始数据的一个好的逼近。在实际应用中，分解之后的矩阵维数通常远远小于原始数据的维数。这就引起了数据的压缩表示，促进了其他研究比如聚类和分类。

在矩阵分解方法中，非负矩阵分解(NMF)有一个限制即所有的矩阵因子都必须是非负的，即所有的因子必须大于等于零。这个非负性约束使NMF从感觉上只能对原始数据进行加操作不能减。因此，对于图像处理，人脸识别[2][12]，文件聚类[13][14]是一个理想的降维方法，它们就是由部分组成整体的。

NMF是一个非监督学习方法。NMF不能应用于许多实际的问题当专家认为是可行的有限知识中。但是许多机器语言的研究发现未标签的数据当与一些少量的标签数据相结合时在研究精确度上会产生相当大的提高[15][16][17]。全标签训练集的处理过程可能会很昂贵，然而少量的标签数据的获得相对便宜。在这种情况下，半监督学习方法就有很大的实用价值。因此，用半监督学习方法研究NMF很有意义。

最近，蔡登等人提出了一种图表正则化NMF(GNMF)方法来编码数据空间的几何信息。GNMF构建一个最近邻图表模拟多种结构。当标签信息可行时，它自然地应用到图表结构中。特别地，如果两个数据点使用同一个标签，大的权重会被分配到边缘连接它们。如果两个数据点使用不同的标签，相应的权重都是0。这就引起了半监督GNMF。这个方法的最大缺点是相同类别的数据点将会一起映射到一个新的表示空间，而且怎样有原则的选取权重并不清晰，这一观点没有理论保证。

本文中，我们提出一种新的矩阵分解方法，叫约束非负矩阵分解(CNMF)，将标签信息作为附加的约束。我们算法的中心是相同类别的数据可以在一个新的表示空间中合并。这样，已经获得的部分表示就有和原始数据一致的标签，因此就有多的识别能力。我们方法的另一个优点是参数自由，避免了参数调试来获得更好的结果。这就使我们的算法更容易方便的应用于真实世界应用中。我们还讨论了怎样高效的解决相应的最优化问题。给出最优化收敛性证明。本文贡献如下： 1.标准NMF是一个非监督学习算法不需要结合标签信息。本文中，我们将它扩展为半监督学习算法。此外，我们将标签信息作为约束；这样一来，有相同标签

的数据在新的表示空间里就有相同的坐标。通过这种方法，表示可以有更多的识别能力。

2.以前的研究[18]显示NMF和概率潜在语义分析(PLSA)都是多项式PCA的实例。特别的是，PLSA利用KL[19][20]分解解决NMF问题。为了更深入的探讨，我们将CNMF应用于KL分解公式中并且提供更新规则解决最优化问题。 3.与半监督GNMF不同，我们算法的优点是参数自由。因此不用靠调参来获得更好的结果。CNMF算法更容易方便的应用于真实世界中。实验结果表明，该算法能有效提高聚类性能。

4.就我们目前的知识而言，没有一种方法能直接获得NMF的解决办法。目前最好的方法是使用更新迭代获得目标函数的最优解。因此算法的效率对真实应用很重要。本文中，我们定性的分析算法复杂度并通过实验测试收敛率定量地证明算法效率。

本文结构如下：第二部分，我们简要的介绍了NMF的背景和相关工作；第三部分介绍了NMF约束的相关工作，具体的算法和理论证明在第四和第五部分，第六部分讨论了算法的复杂度。第七部分实验结果，第八部分是总结。

2．相关工作

矩阵分解存在大量方法，如PCA,SVD，每种分解方法都有相应的约束条件，NMF的约束条件是分解因子矩阵元素必须非负。假设矩阵X RN d，行代表样本点，列代表样本维数。NMF的目的是找到满足X UVT的两个非负因子矩阵U,V。逼近质量由代价函数评价，一种是欧式距离平方度量JF，另一种是Kwellback-Liebler散度或相对熵JKL，这两种目标函数都是关于U,V的非凸函数，很难得到J的全局最小值，因此只能用迭代更新算法寻找上述优化问题的局部最小值及局部最优解U和V。

NMF中X在基函数U上的投影值是V，即NMF将d维向量X映射到k维向量V，新空间是由U张成的。因此当k d时，NMF可作为一种降维方法。(可与其他降维方法比较)

NMF没有利用样别标签信息，它是一种无监督的学习方法。

3．半监督NMF思想

设xi，i 1,2, n Rd,其中i 1,2, l的样本标签已知，而i l 1, n的样

本标签未知。设存在c类，我们建立l c矩阵C，当xi的标签是j类时，其元素 Cl c

Cij=1，否则Cij=0.我们建立半监督矩阵A=

0X U AZ

T

0

，令V=AZ，则

In-l n n l c

(硬约束条件A 软约束条件B，奇稀疏表示或后验概率) (Xd n Ud kVk nT,VN K AN N L C Z N L C K) L=N监督NMF

4.最优化问题及更新算法

4.1更新算法

利用F范数，带标签约束的CNMF算法变为最小化下式函数：

OF X UZTAT (1)

其中ui,j，zi,j是非负的。

(1)中U,Z都是非凸的，要想找到OF的全局最小量不切实际。接下来我们用迭代更新算法获得OF。利用矩阵性质Tr AB Tr BA ，目标函数OF重新写作

OF Tr(X UZTAT)=Tr((X UZTAT)(X UZTAT)T) Tr(XX) 2Tr(XAZU) Tr UZAAZU

T

T

T

T

T

2

ij， ij分别是uij 0，zij 0的拉格朗日乘子， ij ， ij ，拉格朗日函数L是：

L OF Tr UT Tr ZT

L分别对U,Z求偏导，我们得到：

L

-2XAZ 2UZTATAZ 0 U L

2ATXTU 2ATAZUTU 0 Z

根据Kuhn-Tucker条件 ijuij 0， ijzij 0，可以得到关于uij，zij等式：

XAZ ijuij UZTATAZ ijuij 0，

A

T

XTU zij ATAZUTU zij 0

ij

ij

这些等式带来下面的更新准则：

XAZ ij

， (2) uij uij

TT

UZAAZij

zij zij

AA

T

T

XTU

T

AZUUij

(3)

ij

关于上面的迭代准则有下面的定理：

定理1：(1)中目标函数OF在(2)(3)条件下不会增长。当且仅当U,Z在稳定点时，目标函数不会变化。 4.2收敛证明

为了证明定理1，我们利用一个辅助函数的性质。

引理2：如果存在辅助函数G，满足G x,x' F x 和G x,x F x ，则F在 …… 此处隐藏：7635字，全部文档内容请下载后查看。喜欢就下载吧 ……