一种基于最大熵与相关性分析的非负矩阵分解方法

摘要

本发明公开了一种基于最大熵与相关性分析的非负矩阵分解方法，其利用最大熵原理描述非负矩阵分解中的潜在因子分布，以捕捉语义质量的潜在因子特性，提出了一种基于相似性的方法来度量差异性。另外，还将自适应加权策略引入因子间的相互关系，使得每个潜在因子能够无监督的获得自适应权重，并对自适应加权的潜在因子进行非线性变换。最后在多个数据集上的实验结果表明，本发明提出的方法能够解决传统非负矩阵分解不考虑潜在因子的相关性与分布特征等缺点。

说明书

技术领域

本发明涉及信息处理技术领域，尤其涉及一种基于最大熵与相关性分析的非负矩阵分解方法。

背景技术

矩阵分解(MF)模型是多元分析中降维和特征学习的有效方法，高维数据样本被格式化为矩阵，然后分解成低维矩阵的乘积。非负矩阵分解(NMF)是最流行的矩阵分解模型之一，它允许将一个非负输入矩阵分解成两个低阶非负矩阵，通过原始特征的分布因子分解，样本由学习的潜在因子的相加组合重构，非负矩阵分解被广泛应用于数学、最优化、神经计算、模式识别与机器学习、数据挖掘、图像工程与计算机视觉等领域。

为了学习高质量的潜在因子，学者在许多类MF模型中研究了潜在因子的性质。主流研究学派建议减少共适应，以便有效地捕捉数据中罕见的隐藏模式。黄卫春等提出了一种正交约束非负矩阵三因子分解(NMTF)，使潜在因子的多样性最大化，从而得到严格的聚类解释。Chen提出在奇异值分解(SVD)中为学习的潜在因子分配权重，而不是矩阵项。余江兰等提出了非负多矩阵分解(NMMF)，它将用户项矩阵与两个辅助矩阵一起分解，以合并边界信息。徐霜等提出了一种改进NMF(ENMF)来进一步从一系列矩阵中提取知识。然而，上述方法受到硬几何约束的巨大计算量的限制，并且这些经典的方法主要用于整合更多的辅助信息和领域知识上，而对学习的潜在因子的特性关注较少。

刘国庆等利用大锥罚函数寻找具有大互角的潜在因子，可以很好地推广到其他不可知的数据中。另外，为了有效地分解高度混合的数据，李向利等提出了一种最小体积约束的NMF(MVCNMF)来学习彼此相对相似的潜在因子，MVCNMF模型也成功地应用于高相关度的人脸图像处理。但是上述方法未能解决各因素的相关性进行建模，并且缺乏对词或像素等原始输入特征应如何分布的因子内分析。

发明内容

为解决上述问题，本发明提出了一种基于最大熵与相关性分析的非负矩阵分解方法(MECNMF)，利用最大熵原理描述非负矩阵分解中的潜在因子分布，以捕捉语义质量的潜在因子特性，并提出了一种基于相似性的方法来度量差异性。另外，将自适应加权策略引入因子间的相互关系，使得每个潜在因子能够无监督的获得自适应权重。

本发明所采用的技术方案如下：

一种基于最大熵与相关性分析的非负矩阵分解方法，其特征在于：包括以下步骤：

S1：输入原始数据矩阵

X＝UV (1)

其中，

S2：利用最大熵测量方法得到潜在因子u

S3：利用互相关测量方法得到潜在因子u

S4：利用自适应加权策略，将S2和S3的测量值整合分配到给各个潜在因子的自适应权重λ

S5：求解U和V，输出最终的基矩阵和系数矩阵。

本发明的有益效果是：

本发明提出了一种基于最大熵与相关性分析的非负矩阵分解方法，用于解决传统非负矩阵分解不考虑潜在因子的相关性与分布特征等缺点。通过多个数据集的实验结果表明，其具有以下优点：

第一，对于具有代表性的NMF模型，MECNMF比其他算法的性能更优越，且具备更好的泛化能力，同时算法的收敛速度很快；

第二，MECNMF通过提高语义空间的紧凑性可以提高潜在因子的权重，有效地解决语义空间容易被误导的问题，并且MECNMF的显式分析比DNMF中的内部丢弃表现得更好；

第三，MECNMF中的分布状态函数和相关函数进行了融合，从而进一步提高了系统的性能。

附图说明

图1为非负矩阵分解NMF的框架图；

图2为实施例中超参数α∈{0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1}时的AC和NMI曲线；

图3为实施例中不同超参数β值的ACC和NMI曲线；

图4为实施例中平衡参数K取不同值时四种算法的聚类结果变化曲线；

图5为实施例中MECNMF，MECNMF-g和NMF收敛后信息熵函数g(·)的值变化曲线；

图6为实施例中MECNMF、MECNMF-h和NMF收敛后因子相关函数h(·)的值变化曲线；

图7为实施例中不同数据集上本发明的收敛曲线。

具体实施方式

为了使本领域的普通技术人员能更好的理解本发明的技术方案，下面结合附图和实施例对本发明的技术方案做进一步的描述。

传统的非负矩阵分解介绍

非负矩阵分解NMF的目的是将输入的非负数据矩阵分解为非负基矩阵和非负系数矩阵。假设输入样本大小为N，每个样本由M维原始特征组成，NMF构建一个数据矩阵

X＝UV (1)

其中，

以NMF的损失函数测量X和UV之间的重构误差，而平方欧几里德距离和广义Kullback-Leibler散度是最常用的距离度量。则平方欧几里德距离损失函数如公式(3)所示：

最大熵理论介绍

一、分布状态分析

NMF框架中的关键问题是找出哪些潜在因子对数据的语义重构贡献更大，从而更好地拟合输入矩阵X。如图1所示，从式(2)的数据重构角度来看，NMF可以类比为一种深度神经网络(DNN)模型。

在图1的左半部分，输入样本x

在这种无监督学习环境下，本发明提出了两种基于对潜在因子的直观分析的自适应加权策略，如图1的右侧所示。首先，一个潜在因子应该对更多原始特征中的语义进行编码。如果u

为了改善数据表示，每一个潜在因子首先需要传达完整的语义。在NMF中，一个潜在因子u

信息熵是对事件状态的不可预测性的度量。在此，潜在因子u

其中，|u

通过归一化，将|u

根据最大熵原理，将g(u

二、相关性分析

从上述分析来看，u

因此针对潜在因子提出了各种相关措施，例如采用了广泛使用的分布向量间的余弦相似性，即u

其中，绝对值|u

三、加权转换

根据上述对潜在因子的分析，除了最小化分解损失之外，还有两个项可以如式(5)和式(6)中那样进行最大化。一种方法是将它们规范化，然后附加到损失函数中，但也存在较明显的缺陷。首先，为了将损耗最小化问题与两个目标最大化相结合，需要通过一些减法操作和两个超参数来平衡它们。但是，参数调整过程非常困难，因为这三个项的取值范围彼此相差较大。另外，最大熵和互相关约束不会直接施加在单个潜在因子上，而是间接地作为除了重构误差之外的损失。因此，本发明提出了一种自适应加权策略，将两种测量结果以紧密耦合的方式集成到重构损耗中。

对目标矩阵X的行、列甚至向量分配特定权重的常规加权策略，ME CNMF通过对语义重构的贡献来权衡单个u

根据分布状态分析，如果u

其中，f(·)是双曲正切函数f(z)＝tanh(z)，有平滑数据的作用，然后除以最大值f(log

如果u

除以最大值f(K)后，其取值范围可以扩大到[0,1]。使用可调超参数α，可将这两个权重值可以整合到一起，并可计算出总权重λ

其中，0≤α≤1。利用上述权重变量λ

其中，σ(·)是sigmoid函数。

结合式(10)可将式(2)中输入样本向量x

则可得到新的损失函数为：

其中，Λ是由K加权变量λ

此时U∈R

本发明提出的MECNMF不同于传统的加权NMF，因为分配给潜在因子的权重是通过两个建议的测量值进行自适应学习，而不需要先验知识。方程(12)中的最终损失函数与非负矩阵三因子分解(NMTF)中的类似，因为输入矩阵X被分解为三个矩阵。然而，矩阵Λ中的元素不再是自由参数，而是以非线性的方式从矩阵U进行自适应学习。

优化的非负矩阵分解算法

一、对V进行优化

将非负参数

通过采用与文献[1]相同的办法，使用乘法运算得到V：

二、对U进行优化

由于包含非线性分析函数g(·)和h(·)，L对U求导比较复杂。因此，本发明采用经典梯度法对U进行优化，当L对U求偏导数时，首先求解对角权矩阵Λ对U的梯度，λ

其中，f(g(u

其中，sign(·)是符号函数，f(h(u

给定上述对角线权重矩阵的导数，可以很容易求出L对u

其中，σ'(·)是σ(·)函数的导数，

根据以上分析，本发明提出了一种如算法1所描述的迭代优化算法。在每一次迭代中，使用式(14)中的乘法更新规则来更新矩阵V，如第4行所示。还有一个内部迭代，用式(23)更新矩阵U，如第6到12行所示。外迭代和内迭代的最大次数分别为T和S。在实际应用中，选择合适的步长η有些困难，因为当η值不适合时，优化过程要么存在收敛慢的问题，要么出现来回振动问题。因此，通过文献[2]中的自适应调整规则，引用文中的衰减策略：

η

其中，γ是衰减率。

当输出矩阵收敛或达到最大迭代次数时，将结束迭代。

由上所述，为了达到优化目的，本发明提出了算法1，它是传统的NMF乘法更新算法和梯度下降算法的结合，因此下面给出该新算法的收敛性的证明。

令L

L

其中，L

那么如果可以证明上述序列是单调递减的，由于损失函数值总是非负的，那么经过足够的迭代次数，优化过程无疑会收敛到某一点，最终结果至少是一个局部最优解(即该算法是收敛的)。

在算法1中，每个迭代步骤都包含两个子步骤，分别是V和U的优化。因此，每一步损失L

...,L

将非负的

下面对算法1的复杂性进行分析。

算法中的T代表外部最大迭代次数，S代表内部最大迭代次数，M，N，K分别代表输入样本数量，原始特征，以及潜在因子。

在算法1中，主要的运算是求导和矩阵运算。为了方便，假设所有浮点运算的时间复杂度都是相同的。根据迭代公式，可以得出NMF和MECNMF的计算复杂度，如表1所示。从表1可知，当K＜＜min(M,N)和S足够小时，本算法与文献[1]中原始NMF算法的计算复杂度相同。由于矩阵运算具有很好的可并行性，因此将本算法看作一个并行框架，可以进一步提高计算效率。

表1NMF和MECNMF的计算复杂性

实施例：计算机数值仿真实验结果与分析

一、数据集

为了测试本发明所提优化算法的有效性，在实验中使用了五个数据集，其中两个是文档数据集，另外三个是图像集。表2为统计的贡献度较高的数据。

(1)20NG:20新闻组语料库是一个约20000个新闻文件的集合，分为20个不同的组和6个普通类别。它包含18291个文档和9313个经过预处理的常用词。本实施例把普通类别作为聚类的基本依据。

(2)WebKB:WebKB语料库包含4所大学计算机科学系的人工分类网页。网页分为7个类别，删除了其中的3个类别，这些删除的类别包含很少的样本，或者没有特定的含义，其余4个类别共4168页、7770个术语。

(3)COIL20:COIL20是一个图像数据集，包含20个对象的从不同角度的形态，图像是像素大小为32×32的灰度图像，每个对象有72个不同的图像，每个对象的图像归为一个簇。

(4)Yale:Yale是一个包含15个人，像素大小为32×32灰度图像的人脸图像数据集。每个实验对象有11张不同面部表情或形态的图像。每个人的所有图像归为一个簇。

(5)NUS-WIDE-OBJECT(简称NUS)：NUS-WIDE-OBJECT数据集是NUS-WIDE的一个子集，它是一个真实的Web图像数据集.它包含了31个类别的30000张图片。参考文献[3]后，本实施例移除了带有多个标签的图像，并从每个类别中随机选择了100个图像。每个图像由500个维度BoW向量表示。

表2数据集统计

二、不同算法比较

MECNMF是NMF及其变形的一种通用方法。因此将所提出的加权策略和非线性变换应用于具有代表性的NMF基线，以验证其灵活性。并将MECNMF与最近提出的NMF方法进行了比较，以说明其优越性。所有算法的比较结果及说明如下：

(1)NMF：通过使用式(3)中的平方欧几里德距离损失函数实现NMF。将输入矩阵X分解为子矩阵U和V，其中V是输入样本的潜在表示。

(2)MECNMF：MECNMF通过在因子分解过程中自适应学习潜在因子的权重来改进NMF。通过分布状态分析、相关分析和非线性变换，改进了表示矩阵V。

(3)SNMF：正则化NMF最常采用稀疏NMF(SNMF)。矩阵V的L

(4)MECSNMF：与MECNMF类似，最大熵相关稀疏矩阵分解(MECSNMF)通过在因子分解过程中自适应学习潜在因子的权重来改进SNMF，非线性变换进一步提高了对数据非线性建模的能力。

(5)NWNMF:Ncut-weighted NMF(NWNMF)使用特征相似图计算X的权重，然后将NMF应用于加权X以学习数据表示。

(6)MECNWNMF最大熵相关Ncut-weighted MF(MECNWNMF)通过应用状态分布分析、相关分析和非线性变换改进了NWNMF，增强了数据表示。

(7)NMTF：非负矩阵三因子分解(NMTF)将输入矩阵X分解为三个子矩阵，X＝USV，其中V为表示矩阵。

(8)GNMF：图正则化NMF(GNMF)构造了一个相似图来编码数据样本之间的几何关系，并进一步令相似样本在表示空间中处于相邻位置。

(9)LCNMF：相反在MECNMF的外部分析中，Large-ConeNMF(LCNMF)采用了促进潜在因子多样性的large-cone惩罚。large-cone惩罚分为两种形式，一种是由这些因素形成的平行面体积，另一种是它们成对夹角的总和。因此，LCNMF有两种变体，大体积NMF(LVNMF)和大角度NMF(LANMF)都与MECNMF进行了比较。

(10)DNMF：Dropout NMF(DNMF)试图通过以一定概率随机删除潜在因子来促进其语义独立性。与MECNMF和LCNMF不同，潜在因子之间的相关性和多样性对它并没有很大影响。

三、实验参数设置

在分析实验结果之前，先比较和解释不同算法间的参数设置。在所有三个MECNMF(MECNMF、MECSNMF、MECNWNMF)中，对于20NG、WebKB、COIL20、Yale和NUS数据集，平衡参数α设置为0.5，β分别设置为1、10

对于所有五个数据集中的11个NMF变体，潜在因子K的数量设置为50。SNMF和MECSNMF中稀疏项的平衡参数的取值范围是{10

四、评价指标

本发明采用聚类准确度(ACC)和归一化互信息(NMI)进行评价。用a

其中，map(l)＝arg

其中，C和C'是同一样本集的两个不同的聚类，p(c

其中，H(C)表示聚类熵。

五、聚类结果

表3涵盖了以上五个数据集上所有算法的聚类结果。用黑体表示原始NMFs和相应MECNMFs之间较好的结果，并且在所有参与比较的方法中最好的结果加下划线。可以发现：

与大多数算法相比，MECNMF在所有五个数据集上都表现出更好的性能，并且MECNMF(MECNMF、MECSNMF和MECNWNMF)始终优于原始算法(NMF、SNMF和NWNMF)。因此，有力地证明了对于具有代表性的NMF模型，本文所提出的算法比其他算法的性能较优越以及更能广泛被运用。因此，与传统的加权NWNMF相比，该策略能有效地提高潜在因子的权重。MECNMF在所有数据集上表现的性能都优于LVNMF和LANMF。此外，LVNMF和LANMF在数据集20NG上表现的性能比NMF要差，其原因在于紧凑的论题可以更好地适应输入数据。20NG数据集是一个松散分类的新闻语料库，数据中存在噪声和冗余。如果不考虑潜在因子之间的关系，学习到的语义空间很容易被误导。然而，MECNMF通过提高语义空间的紧凑性可以解决这个问题。DNMF性能优于NMF，但比MECNMF差。这说明，对学习过程中潜在因子之间的关系进行建模确实可以改善NMF，并且MECNMF的显式分析比DNMF中的内部丢弃表现得更好。最后，所有的MECNMF总是比NMTF表现更好，因此可以看出本发明所提的加权策略发挥了作用，而不是简单地在因子分解中插入一个对角矩阵。

表3各个模型在不同数据集上的表现

六、参数分析

(1)α敏感性分析

超参数α平衡了最大熵权重

(2)β敏感性分析

在最终损失函数中，超参数β平衡了L

此外，ACC和NMI曲线如图3所示，其中β∈{10}。从图3可以看到，随着β的增加，MECNMF的性能先略有提高，然后迅速下降。这是因为较小的β值可以增强U的稀疏性，从而阻止g(·)产生不必要的解。因此，曲线在开始时随β的增加而略有增长。然而，由于L

(3)K的敏感性分析

影响NMF性能的另一个参数是潜在因子K的数量。对于一个给定的数据集，潜在因子的数量不能预先精确估计。较小的K值不能学习数据中全部的信息，而较高的K值会增加计算复杂度和学习参数的难度。因此，有必要分析该算法对K的敏感性，为此本实施例进行了当K∈{20,30,40,50,60,70,80,90,100}时的实验。

附图4描绘了当K取不同值时四种算法的聚类结果变化情况。理想情况下，随着K的增加，聚类结果变得更好。然而，在实验过程中，曲线是波动的，但总体趋势是向上的。不稳定的主要原因可能是本发明采用梯度下降法对算法进行了优化，算法往往受到初始化值等因素的影响，有可能陷入局部优化。此外，参数的随机性也会导致曲线波动。然而，无论K值如何变化，本发明提出的改进算法(MECNMF和MECNWNMF)总是比原算法(NMF和NWNMF)性能更好。考虑到性能和时间消耗，综上所述，将K设置为50。

七、语义空间分析

首先，MECNMF考虑了潜在因子的分布状态，并强制它们从原始特征中编码更多的信息，以减少语义歧义。g(·)函数用来衡量一个潜在因子对语义的编码程度。当α＝1(表示为MECNMF-g)时，它是影响权重的唯一因素。如果有效地降低模糊度，u

其次，MECNMF还考虑了潜在因子之间的相关性，并将其归纳为一个紧凑的语义空间，过滤掉异常值和噪声。用h(·)函数来度量语义空间的紧密性，当α＝0(表示为MECNMF-h)时，它是权重中唯一需要考虑的因素。当MECNMF、MECNMF-h和NMF收敛后，在图6中绘制出h(·)的值。为了便于说明，将潜在因子按h(·)的升序排列，且仅描绘前15个值。很明显，MECNMF和MECNMF-h都比NMF有更大的h(·)值，因为潜在因子需要学习一个紧凑的语义空间。另外，由于MECNMF-h的加权策略只考虑了语义的紧凑性，所以它的h(·)值比MECNMF大。总之，分布状态函数g(·)和相关函数h(·)在MECNMF学习过程中都起着举足轻重的作用，而且二者的融合进一步提高了系统的性能。

八、收敛性与计算效率

附图7描绘了上述数据集的收敛曲线。在每个图中，x轴表示迭代次数，y轴表示目标函数值。从图中可以看到，本发明算法在上述五个数据集上经过大约200次迭代后达到收敛，说明了本算法收敛速度很快。

结合表1可知，当K＜＜min(M,N)时，该算法的一步计算复杂度接近NMF，其效率主要取决于迭代次数。在设置相同的COIL20数据集参数情况下，分别运行MECNMF和NMF，结果表明MECNMF的运行时间比NMF大约长10倍，这是因为MECNMF的内部迭代次数较多。

参考文献：

文献[1]余江兰,李向利,赵朋飞.基于核技巧和超图正则的稀疏非负矩阵分解[J].计算机应用,2019,39(03):742-749.

文献[2]:刘国庆,卢桂馥,张强.一种稀疏图正则化的非负低秩矩阵分解算法[J].重庆邮电大学学报(自然科学版),2020,32(02):295-303.

文献[3]:李向利,贾梦雪.基于预处理的超图非负矩阵分解算法[J].计算机科学,2020,47(07):71-77.

以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。