非负矩阵集分解

非负矩阵集分解（共7篇）

非负矩阵集分解 篇1

摘要：非负矩阵分解(non-negative matrix factorization,NMF)是一种常用的非负多元数据描述方法。处理数据矩阵集时,NMF描述力不强、推广性差。基于双线性型的非负矩阵集分解(bilinear form-based non-negative matrix set factorization,BFBNMSF)是对NMF的扩展,处理数据矩阵集时,BFBNMSF比NMF描述力强、推广性好。但BFBNMSF在初始化时使用随机分布,为使BFBNMSF更快收敛,该文提出一种基于奇异值分解(Singular value decomposition,SVD)初始化的BFBNMSF,即SVD-BFBNMSF,对系数矩阵进行初始化,已达到快速收敛的目的。实验结果表明:与传统BFBNMSF比较,该方法在收敛速度确有所改善。

关键词：非负矩阵集分解,双线性型,SVD,图像描述,特征提取

0 引言

非负矩阵分解(non-negative matrix factorization, NMF)由Lee和Seung在《Nature》上提出[1], 它使分解后的所有分量均为非负值(即:要求进行纯加性的描述),并且同时实现非线性的维数约减。

为使NMF能达到快速收敛,C.Boutsidis、E.Gallopoulos等人提出一种基于SVD的NMF初始化研究[2],将原本随机分布的NMF的特征矩阵W和系数矩阵H先利用SVD进行初始化,然后再进行NMF。该方法在一定程度上提高了收敛速度,并在特征矩阵W的稀疏性与数据描述能力上有所改善。

然而,应用中,数据样本常以矩阵的形式呈现(如:灰度图像),而NMF的处理对象本质上是向量集,所以一般的做法是将这些数据矩阵先向量化,然后再放到NMF模型中去处理[3,4]。这样做的结果是用于学习的样本量可能远远小于被学习参数的维数(典型的小样本学习问题),这会导致NMF对数据的描述能力不强(描述的准确度不够)。

因而,李乐﹑章毓晋等人提出基于双线性型的非负矩阵集分解(bilinear form-based non-negative matrix set factorization,BFBNMSF)[5]。BFBNMSF比NMF描述力强。描述矩阵L和描述矩阵R代表了整个矩阵集的公共特性,(Dk=1,2,…,N)依L和R而确定,L和R是BFBNMSF训练过程中被学习的参数,它们蕴涵了BFBNMSF学习结果的全部。

为使BFBNMSF在收敛速度上有所改善,并保留BFBNMSF的良好描述力,本文提出一种基于SVD初始化的双线性型非负矩阵集分解,即SVD-BFBNMSF。即采用C.Boutsidis的SVD初始化NMF思想,先用SVD分别对描述矩阵L和描述矩阵R进行初始化,而{Dk,k=1,2,…,N}则仍采用随机分布系数初始化,然后再利用BFBNMSF完成分解过程。

1 NMF与BFBNMSF

1.1 NMF

定义1:NMF是在给定输入m×n维观测矩阵V条件下,求取非负的m×l维特征矩阵W和非负的l×n维系数矩阵H使:

V=WH+E (1)

的方法,其中,E为m×n维的噪声矩阵。

根据常用的最小二乘逼近思想,可用V和WH间的欧几里得距离平方来作为目标函数:

$\underset{0\le \mathit{W}‚\mathit{{\rm H}}}{{\displaystyle \min }}\parallel \mathit{V}-\mathit{W}\mathit{{\rm H}}\parallel {}^2(2)$

采用类似EM算法中使用的优化策略,可得交替迭代规则:

H←H⨂[WTV]·[WTWH] (3)

W←W⨂[VHT]·[WHHT] (4)

由于通常设定l·min(m,n)且$l\le \frac{m*n}{m+n}$所以只有在W包含了V的本质特征时,才可使V=WH+E(即:用很少量的特征可描述很大量的数据),且W具有稀疏性,因而其获取的特征矩阵为特征片段,能很好的避免目标被遮挡所带来的影响。

1.2 BFBNMSF

定义2:BFBNMSF是求取非负的m×l1维描述矩阵L、非负的l2×n维描述矩阵R以及非负的l1×l2维双线性型矩阵集{Dk,k=1,2,…,N}使:

Ak=LDkR+Ek,k=1,2,…,N (5)

的方法,其中,Ek为噪声项。

利用最小二乘逼近思想,使用欧几里得距离平方来作为目标函数:

$\underset{0\le \mathit{L},\mathit{R},\mathit{D}{}^k,k=1,2,\cdots ,{\rm N}}{{\displaystyle \min }}{\displaystyle \sum _{k=1}^{{\rm N}}\parallel }\mathit{A}{}^k-\mathit{L}\mathit{D}{}^k\mathit{R}\parallel {}_F^2(6)$

基于辅助函数法,可得交替迭代规则:

$\begin{array}{l}\mathit{L}\leftarrow \mathit{L}\otimes \{{\displaystyle \sum _{{\rm N}}^{{\rm N}}\mathit{A}}{}^k(\mathit{D}{}^k\mathit{R}){}^{{\rm T}}\}\cdot \{\mathit{L}{\displaystyle \sum _{{\rm N}}^{{\rm N}}\mathit{D}}{}^k\mathit{R}\\ (\mathit{D}{}^k\mathit{R}){}^{{\rm T}}\}(7)\\ \mathit{R}\leftarrow \mathit{R}\otimes \{{\displaystyle \sum _{k=1}^{k=1}(}\mathit{L}\mathit{D}{}^k){}^{{\rm T}}\mathit{A}{}^k\}\cdot \{{\displaystyle \sum _{k=1}^{k=1}(}\mathit{L}\mathit{D}{}^k){}^{{\rm T}}\mathit{L}\mathit{D}{}^k\mathit{R}\}(8)\\ \mathit{D}{}^p\leftarrow \max (\mathit{D}{}^p\otimes \sqrt{\mathit{L}{}^{{\rm T}}\mathit{A}{}^p\mathit{R}{}^{{\rm T}}\cdot \mathit{L}{}^{{\rm T}}\mathit{L}\mathit{D}{}^p\mathit{R}\mathit{R}{}^{{\rm T}}},\epsilon )(9)\end{array}$

从整体上看,BFBNMSF把所有训练用数据矩阵看成一个对象做处理,提取出全部矩阵所共用的描述因子L和R;从局部上看,BFBNMSF对矩阵集中的每一个矩阵都进行一次新形式的(3因子)NMF(Ak≈LDkR)。

需要强调,BFBNMSF是NMSF的一种实现形式,因此BFBNMSF具有NMSF的通性,它应比NMF描述力强、推广性好。L和R代表了整个矩阵集的公共特性,{Dk,k=1,2,…,N}依L和R而确定,和是BFBNMSF训练过程中被学习的参数,它们蕴涵了BFBNMSF学习结果的全部。

2 SVD-BFBNMSF

本文SVD-BFBNMSF思想是基于C.Boutsidis的SVD初始化NMF提出的,并对该方法在BFBNMSF中进行扩展,以自定义初始矩阵集的L和R,来达到快速迭代收敛的目的。

假设给定矩阵X,可定义矩阵X的正片段X+与负片段X-具有与X相同的结构,且X+≥0,X-≥0,同时X+内非零元素为矩阵X内大于0的元素,X-内非零元素为矩阵X内小于0的元素。故,有X=X+-X-[2]。

算法思想:

①输入m×n×N维观测矩阵Y,描述因子维数l和r;输出矩阵集L和R。

②将观测矩阵Y分别变换为维矩阵Y1,h=n×N和k×n维矩阵Yr,k=m×N。

③分别将矩阵Y1和Yr进行SVD变换,即:[U1,S1,V1]=svds(Y1,1),[Ur,Sr,Vr]=svds(Yr,r)。

④选择矩阵集L和R的第一行或列,即:L(:,1)=abs(U1(:,1)),R(1,:)=abs(U1(:,1)’)。

⑤选择矩阵集L和R余下的元素。

⑥分别选取好初始矩阵集的L和R后,随机(0,1)分布矩阵集Dk,然后利用1.2节中BFBNMSF进行后续分解过程。

选择矩阵集L余下的元素:

for i=2:p

uup=Up(:,i);vvp=Vp(:,i);

uupp=pos(uup); vvpp=pos(vvp); %获取矩阵的正片段

uupn=neg(uup);vvpn=neg(vvp); %获取矩阵的正片段

n_uupp=norm(uupp);n_vvpp=norm(vvpp); %求范数

n_uupn=norm(uupn);n_vvpn=norm(vvpn);

termpp=n_uupp*n_vvpp;termpn=n_uupn*n_vvpn;

if (termpp>= termpn)

L(:,i)=sqrt(termpp)*uupp/n_uupp;

else

L(:,i)=sqrt(termpn)*uupn/n_uupn;

end

end

同理,可选择出矩阵集R余下的元素。

3 实验仿真

实验一:数据集为400张50×50的黑白纹理图片,该数据采自黑白棋盘格,并按指定像素级进行行列的位移采集而来(如图1上半部分所示),设l=20,r=20,迭代次数为300次。

实验二:数据集为实验一中数据集,l=40,r=40,迭代次数为300次。

实验三:数据集为2429张19×19的人脸图片(如图1下半部分所示),l=7,r=7,迭代次数为300次。

实验四:数据集为实验三中数据集,l=12,r=12,迭代次数为300次。

实验分析:图2分别为以上实验的BFBNMSF与SVD-BFBNMSF比较结果,其中横坐标表示迭代次数(0～300次),纵坐标表示相对误差K为:

$\begin{array}{l}{\rm K}=\\ \frac{\text{m}\text{e}\text{a}\text{n}(\text{观}\text{测}\text{矩}\text{阵}\mathit{A}{}^k-\text{当}\text{前}\text{迭}\text{代}\text{次}\text{数}\text{下}\text{的}\text{重}\text{建}\text{数}\text{据}LD{}^{k}R)}{\text{m}\text{e}\text{a}\text{n}(\text{观}\text{测}\text{矩}\text{阵}\mathit{A}{}^k)}\end{array}$

从相对误差趋于稳定的迭代次数来看,SVD-BFBNMSF明显比BFBNMSF先趋于稳定;且在最初的50次迭代中,SVD-BFBNMSF要比BFBNMSF下降更快。同时L与R的约束还受输入图片尺寸的限制,且不同的L与R的设置会造成最终平稳时的相对误差值K的不同,L与R越接近于输入观测图像的宽与高,则K值越低,代表该实验结果最能反映真实情况。

实验结果:经过对比以上实验,得出SVD-BFBNMSF在收敛速度方面明显强于BFBNMSF, 然而L与R易受输入数据(即观测图像尺寸)限制,一般情况下采用50～250像素即可。

4 结束语

本文基于C.Boutsidis的SVD初始化NMF提出,并对该方法在BFBNMSF中进行扩展,以自定义初始矩阵集的L和R,来达到快速迭代收敛的目的。然而在L和R的选取上目前还没有较好的选取方法,是以后可以继续研究的一个领域。

参考文献

[1]Lee D D,Seung H S.Learning the parts of objects by non-negativematrix factorization.Nature[J].1999,401(6755):788-791.

[2]Boutsidis C,Gallopoulos E.SVD-based initialization:A head starton nonnegative matrix factorization[J].Pattern Recognition,Issue4,April 2008,41(4):1350-1362.

[3]李乐,章毓晋.非负矩阵分解算法综述[J].电子学报,2008,36(4):737-743.

[4]李乐,章毓晋.非负矩阵集分解[J].电子与信息学报,2009,31(2):255-260.

[5]李乐,章毓晋.基于双线性型的非负矩阵集分解[J].计算机学报,2009,32(8):1536-1549.

非负矩阵分解的研究现状 篇2

非负矩阵分解问题属于最优化范畴。仅对左右矩阵因子施加非负性的非负矩阵分解模型称为基本的NMF模型;根据某种需要, 对左右矩阵因子施加除非负性约束外的其他约束的模型称为改进的NMF模型。相应地, 现有的NMF算法可分为基于基本NMF模型的算法和基于改进NMF模型的算法。

1国外研究现状

NMF的思想是可追溯到1994年Paatero和Tapper提出的正矩阵分解 (Positive Matrix Factorization, PMF) , 在这篇文章里他们尝试对环境方面的实际数据进行因子分析。但真正使NMF的研究流行起来, 并成为一个研究热点, 是1999年Lee和Seung提出了一个以广义Kullback.Leibler散度为目标函数的基于基本NMF模型的算法, 并将其应用于人脸图像的表示, 将ORL人脸库上的人脸图像向量化, 构成一个非负矩阵, 运用NMF算法进行分解, 将得到的基图像矩阵中的每一列转换为与ORL人脸库中人类图像等尺寸的图像矩阵, 发现呈现在人们面前的是人脸面部的某些部件, 如眼睛、嘴巴、眉毛等。2001年, Lee和Seungi对基于基本NMF模型的算法进行了深入的研究, 提出了两个经典的NMF算法:基于欧氏距离的乘性迭代算法和基于广义Kullback.Leibler散度的乘性迭代算法, 并给出了收敛性证明, 这两个算法由于提出的比较早, 收敛速度较快, 已被应用于各个领域, 现已成为NMF的基准算法。

2国内研究现状

国内对NMF的研究, 相对开始的较晚。2001年, 原微软中国研究院的李子青博士、张宏江博士等人发现Lee和Seung提出的经典NMF算法在人脸图像未得到配准的情况下, 不能学习得到人脸的部件。并提出了局部非负矩阵分解 (Local Non.Negative Matrix Factorization, LNMF) 来解决这个问题。Chen等人将LNMF算法应用于人脸检测并取得了较好的效果。现为中科院自动化所生物识别与安全技术研究中心主任的李子青带领他的团队, 于2009年, 提出了基于吉布斯随机场的NMF算法 (GRF.NMF) , 该算法的收敛速度较快, 并且得到的分解结果具有较好的稀疏性和可解释性。清华大学信息科学与技术国家实验室的章毓晋教授、李乐博士对非负矩阵分解的研究做了大量的工作, 文献是对NMF算法的研究现状进行了综述, 对已有的NMF算法进行了很好的分类, 指出各个NMF算法的缺点, 并提出了改进的算。针对NMF的先天缺陷, 即数据描述能力不强、推广性差, 提出了非负矩阵集分解 (Non.Negative Matrix Set Factorization, NMFSF) 的概念和相应的算法。

浙江大学计算机学院的蔡登教授等人针对流形数据提出了图正则非负矩阵分解算法GNMF, 该方法在矩阵分解过程中明确考虑了数据集携带的几何信息:如果数据点在原空间是邻近点, 那么对应到新的基下也是邻近点。此外, 他们还提出了局部保留NMF。可见, 国内的研究机构和学者也逐渐加入NMF研究的行列, 并取得了一定的成果。

非负矩阵集分解 篇3

随着国民经济的快速发展,电力系统迅速向多级化、大电网、交直流联合输电及大区联网运行发展,电力系统的动态分析即使在离线状态下也变得十分困难。实际上对一个大电力系统的动态研究最感兴趣的只是其中某一个区域,称为研究系统,而距此区域较远的区域,研究中只考虑其对研究区域的影响,可作降阶及简化,这种拟作简化的区域称为外部系统。保留研究系统不变,而对外部系统在保证其对研究系统的动态影响不畸变的条件下,进行简化的过程称为动态等值[1]。

同调等值法是动态等值的基本方法之一,其关键步骤为识别同调机群。同调机群的识别方法有很多,如相关系数法[2]、状态空间法[3]、模糊聚类法[4,5,6]、模糊相关自组织数据分析算法[7,8]等。对于大系统而言, 这些方法一般比较复杂, 计算量较大,难以满足工程实用化的要求。当前,从实时的曲线对发电机进行分群[9,10]的方法已经比较成熟,但是该类方法对于功角曲线的数据时间窗宽度有一定要求,且数据处理方法本身存在一定的局限性,给分群结果带来较大的影响。随着新理论的不断涌现,文献[11]提出轨迹特征根的概念,文献[12,13]将此思想进一步推广,并在小故障下验证了该思路的实用性。在此基础上,文献[14]用故障后系统的轨迹特征根进行机组分群趋势的预测,但该方法能否适应复杂系统和连锁故障场景及多摆失稳的情况,有待进一步研究。文献[15]分别提出了基于小波变换和人工神经网络的同调机群识别法,但这些方法仍克服不了计算复杂、耗时的缺点,且神经网络建模技术所强调的训练误差最小化的做法,易引起模型对样本数据的过拟合,从而导致模型的泛化能力较差。

文献[16]提出了一种基于主成分分析(principal component analysis,PCA)方法的同调机群识别方法。该方法通过构造量测样本数据的线性组合,重新组成一组新的相互无关的综合变量,最终获得量测数据的主成分分量。从本质上说,该方法是通过降维达到分群目的,原理简单、计算量小,可以满足大系统在线应用的要求。然而,PCA完全是从数学角度分析量测样本矩阵,因此只能抽取样本的代数特征,从而有可能导致在分解结果中产生负值,而负值往往无法从物理角度进行解释,这样就失去了对原始问题的最佳解释,也就是说,提取特征的过程丢失了部分信息,有可能会导致最终结果的不准确。

针对上述问题,非负矩阵分解(non-negative matrix factorization,NMF)提供了一种新的解决方案[17]。NMF是由Lee和Seung在1999年提出的一种新的矩阵分解算法[17],与PCA等其他特征提取算法相比,该算法对分解结果非负的限制使得NMF具有实现上的简便性、分解形式的可解释性等优点。为简单方便地对分解结果进行聚类分析,采用了K均值聚类算法[18]。K均值聚类算法是一种能用在许多聚类问题上的快速迭代算法,算法简单且聚类效果较好,是到目前为止应用比较成熟的一种聚类分析算法。

基于上述分析,本文提出一种基于NMF的电力系统同调机群识别方法。通过NMF对发电机转速数据降维,降维结果归一化后再利用K均值聚类对其进行聚类,以达到同调机组的分群目的。

1 NMF和K均值聚类算法

1.1 NMF问题描述

NMF问题可描述为[19]:对一个n×m阶的非负矩阵V,可以将其分解为一个n×r阶的非负矩阵W和一个r×m阶的非负矩阵H的乘积。

分解后可理解为,原矩阵V中的列向量是对矩阵W中的所有列向量的加权和,而权重系数是矩阵H对应列向量中的元素。故称W为基矩阵,H为系数矩阵(权矩阵)。这种基于基向量组合的表示形式具有很直观的语义解释,它反映了人类思维中“局部构成整体”的概念[20]。一般情况下,r的选择值要比n小,即r满足(n+m)r<mn,这时用系数矩阵代替原始数据矩阵,就可以对原始数据矩阵降维(且是非线性的维数约减),得到数据特征的降维矩阵,从而可以减少存储空间,节约计算资源[21]。

1.2 NMF实现算法

NMF的实现可以表述成最优化问题,常用的目标函数有2个,其中,i和j分别表示矩阵的行和列。

1)矩阵V与矩阵M(M=WH)的欧氏距离的平方,即

$\parallel \mathit{V}-\mathit{{\rm M}}\parallel {}^2={\displaystyle \sum _{ij}(}V{}_{ij}-{\rm M}{}_{ij}){}^2(1)$

式中:Vij和Mij分别为矩阵V和M中的元素。

2)矩阵V与矩阵M推广的K-L离散度,即

$D(\mathit{V}\parallel \mathit{{\rm M}})={\displaystyle \sum _{ij}(}V{}_{ij}\lg \frac{V{}_{ij}}{{\rm M}{}_{ij}}-V{}_{ij}+{\rm M}{}_{ij})(2)$

式(1)与式(2)都是当且仅当V=M时达到最小值0。

因此,优化问题转变成:在约束W≥0,H≥0下,寻找使得式(1)或者式(2)表示的目标函数达到最小值时所对应的矩阵W和矩阵H。文献[17]提出了一种乘法迭代算法,即从任意非负初始值出发,交替更新矩阵W和矩阵H,直到它们的改变足够小。具体算法步骤如下。

步骤1:对非负矩阵W和H分别随机赋初值。

步骤2:更新W和H。

对于式(1),更新法则为:

$W{}_{ik}\leftarrow W{}_{ik}\frac{A{}_{ik}}{B{}_{ik}}(3){\rm H}{}_{kj}\leftarrow {\rm H}{}_{kj}\frac{C{}_{kj}}{D{}_{kj}}(4)$

式中:Wik,Hkj,Aik,Bik,Ckj,Dkj分别为矩阵W,H,A,B,C,D的元素,A=VHT,B=WHHT,C=WTV,D=WTWH;k为降维后矩阵的维数。

对于式(2),更新法则为:

$\begin{array}{l}W{}_{ik}\leftarrow W{}_{ik}\frac{{\displaystyle \sum _j\frac{{\rm H}{}_{kj}V{}_{ij}}{{\rm M}{}_{ij}}}}{{\displaystyle \sum _j{\rm H}}{}_{kj}}(5)\\ {\rm H}{}_{kj}\leftarrow {\rm H}{}_{kj}\frac{{\displaystyle \sum _i\frac{W{}_{ik}V{}_{ij}}{{\rm M}{}_{ij}}}}{{\displaystyle \sum _{i}W}{}_{ik}}(6)\end{array}$

步骤3:重复步骤2直至收敛。

本文以式(1)作为NMF的目标函数。

1.3 K均值聚类算法

聚类是将数据集划分为若干个类(cluster)的过程,使同一个聚类中数据对象(样本点)具有较高的相似度,而不同聚类中的对象相似度较低。聚类方法中的K均值聚类算法具有复杂度较低、效率高、可扩展等优点。其基本思想是首先确定若干初始聚类中心,然后逐步改变或者调整这些中心,使聚类趋于合理[22]。

K均值聚类算法流程如下。设X=[x1,x2,…,xi,…,xN]为原始数据,k为聚类数。首先,从N个数据对象中随机选取k个对象作为初始聚类中心,其他对象则根据它们与这些聚类中心的相似度(距离)分别分配到最相似的类中。假设cj为第j个类的聚类中心,则xi与cj的相似度为:

$\begin{array}{l}d(\mathit{x}{}_i,\mathit{c}{}_j)=[(x{}_{i1}-c{}_{j1}){}^2+\cdots +\\ (x{}_{i{k}^{\prime }}-c{}_{j{k}^{\prime }}){}^2+\cdots +(x{}_{i{n}^{\prime }}-c{}_{j{n}^{\prime }}){}^2]{}^{\frac{1}{2}}(7)\end{array}$

式中:xik′和cjk′分别为xi与cj的第k′个属性。

然后计算每个更新的类的聚类中心,假设第j个类中的样本为[xj1,xj2,…,xjm′],即包含m′个样本,则该类的聚类中心为cj=[cj1,…,cjk′,…,cjn′],其中cjk′可根据式(8)求得:

$c{}_{j{k}^{\prime }}=\frac{x{}_{j{}_1{k}^{\prime }}+x{}_{j{}_2{k}^{\prime }}+\cdots +x{}_{j{}_{m^{\prime }}{k}^{\prime }}}{m^{\prime }}(8)$

不断重复上述过程,直到标准测度函数收敛为止(从表现形式上看即更新后的聚类中心与更新前一致),一般采用均方差作为标准测度函数,其形式为:

$J=\sqrt{\frac{{\displaystyle \sum _{j=1}^k{\displaystyle \sum _{l=1}^{m^{\prime }}\parallel }}\mathit{x}{}_{j{}_l}-\mathit{c}{}_j\parallel {}^2}{{\rm N}-1}}(9)$

最后得到的聚类具有如下的特点:聚类内部尽可能紧凑,不同类之间尽可能分开。

2 基于NMF的同调机群识别

在发电机的分群问题上,将具有相似动态行为的机组划分为一组机群,需要处理的信息是发电机的转子角等指标在研究时间内的相互接近程度[4]。为了便于与基于PCA的同调机群识别方法的分群结果相对比并清晰展示NMF的思想,分群指标选取文献[16]中采用的发电机实际转速。

发电机转速矩阵作为原矩阵,其自身是一个非负矩阵,而NMF的乘法迭代算法保证了基矩阵W和系数矩阵H中无负数元素,满足了一定物理意义的约束。从另一个角度来看,测取的发电机转速可以看做是表征发电机动态行为的物理量,参照NMF在文本领域应用中的解释,可将分解得到的基矩阵中的列向量理解为对发电机转速产生影响的各个因素的集合,系数矩阵H则描述的是每个因素集合的重要程度。将列向量通过系数矩阵中的权值进行线性组合得到原矩阵,这就是本文发电机转速进行NMF的直观的“局部构成整体”的感受。通过对系数矩阵H的聚类,也就是对因素重要程度的聚类,可以实现同调机群的识别。

文献[16]采用PCA对发电机转速降维,然后分别取前2个主成分和前3个主成分进行机组分群,结果表明用后者进行分群比前者更精确。本文对NMF和PCA进行比较时,将降维的维数定为3,这样有利于作三维图,使结果可视化,确定机组的同调特性,并进行分群结果对比。

设系统有m台发电机,利用仿真测取各发电机N个转速数据,记为

$\mathit{V}(n)=[\mathit{v}{}_1(n),\mathit{v}{}_2(n),\cdots ,\mathit{v}{}_m(n)]{}^{\text{Τ}}n=1,2,\cdots ,{\rm N}(10)$

接着对N×r阶的非负矩阵W和r×m阶的非负矩阵H随机赋非负初值,其中r=3。依照式(3)和式(4)所示的更新法则更新W和H,重复上述步骤直至式(1)所示的目标函数达到最小值。降维所得到的r×m阶的矩阵H即为进行同调机群识别所需要的数据。可以看出,NMF解决了源数据维数高的问题,实现了对源数据的特征提取。

对于降维矩阵H,先进行归一化,再用K均值聚类算法对它进行聚类。通过对提取特征的聚类来确定各机组的同调特性,实现机组的分群。

基于NMF的同调机群识别的流程如图1所示。

3 算例分析

本文采用的算例以New England 10机39节点系统作为分析对象。通过算例中不同线路端点发生故障的2个方式来验证基于NMF的同调机群识别方法的有效性,并通过K均值聚类的标准测度函数J的值来比较基于NMF和基于PCA的方法的分群效果。在设置的2种不同故障方式下用PSD-BPA分别进行时域仿真,测取各发电机300个转速数据作为源数据进行算例分析。

3.1方式1

方式1在Bus9-Bus8的Bus9侧发生三相瞬时接地短路故障(定义为Bus9*-Bus8),0.10 s切除故障。下面分别采用基于NMF和基于PCA的同调机群识别方法,对10机39节点系统的机组进行分群。

将方式1中的源数据分别用NMF和PCA进行降维。NMF实现算法的目标函数值为7.996 4×10-9。NMF实现降维的过程实际上是一个优化问题,目标函数值越小,基矩阵W和系数矩阵H的乘积更接近于原矩阵V,W和H保留V的信息更多,也体现了“局部构成整体”的感受。降维数据归一化后利用K均值聚类的聚类结果如图2和图3所示。聚类结果均分为5类,即(G30),(G39),(G31,G32),(G34,G38),(G33,G35,G36,G37),由此可以看出,基于NMF和基于PCA的同调机群识别方法的结果是一致的。分群结果如表1所示。

此故障方式下各机3 s内的原始功角摇摆曲线如图4所示, G30为参考发电机。可以看出,(G31,G32),(G34,G38),(G33,G35,G36,G37)的同调特性较强,此方式下将10机系统分为5群符合系统发电机的功角轨迹趋势,同调机群结果为(G30),(G39),(G31,G32),(G34,G38),(G33,G35,G36,G37),验证了基于NMF和基于PCA的同调机群识别方法在该方式下的分群是合理的。

方式1分别用NMF和PCA对源数据降维并归一化后,K均值聚类的标准测度函数的值如表2所示。NMF的标准测度函数的值为0.24,PCA的标准测度函数的值为0.36。可见,方式1中NMF之后利用K均值聚类的标准测度函数的值小于PCA之后利用K均值聚类的标准测度函数的值。标准测度函数所描述的是每个数据样本与所属类的聚类中心之间的均方差,因此NMF使得同调机群的聚类内部更紧凑,表明此方式下相比于PCA,NMF可使同调机群聚类的效果更好。

3.2方式2

方式2在Bus28-Bus26的Bus28侧发生三相瞬时接地短路故障(定义为Bus28*-Bus26),0.10 s切除故障。将方式2中的源数据分别用NMF和PCA进行降维。NMF实现算法的目标函数值为4.539 4×10-10。降维数据归一化后利用K均值聚类的聚类结果如图5和图6所示,基于NMF和基于PCA的同调机群识别方法的结果是一致的。分群结果如表3所示。

此故障方式下各机3 s内的原始功角摇摆曲线如图7所示,G30为参考发电机。可以看出,(G31,G32,G33,G35,G36)的同调特性较强,此方式下将10机系统分为6群符合系统发电机的功角轨迹趋势,验证了基于NMF和基于PCA的同调机群识别方法在该方式下的分群是合理的。

方式2分别用NMF和PCA对源数据降维并归一化后,K均值聚类的标准测度函数的值如表4所示。2种方法的标准测度函数值的比较同样表明此方式下NMF比PCA的同调机群聚类效果更好。

综上所述,由方式1和方式2这2种不同故障的仿真算例可以看出,NMF较好地保留了原矩阵的主要信息,基于NMF进行同调机群识别也是可行有效的。标准测度函数值的比较表明,基于NMF的同调机群识别方法使同调机群的聚类内部更紧凑,即聚类效果更好。

4 结语

本文提出了基于NMF的同调机群识别方法,利用NMF对发电机转速源数据进行降维,得到具有非负性质的低维映射矩阵,归一化后进行K均值聚类,确定机组的同调特性,实现机组分群。基于不同方式下的算例测试结果验证了本文算法的有效性。本文的模型和方法具有以下特点。

1)低维矩阵较好地保留了原矩阵的信息,简化了分群工作。

2)在某些数据样本中,负值往往无法从物理角度进行解释,而NMF对分解结果非负的限制至少满足了一定的物理意义的约束,并使其具有分解形式的可解释性。

3)分群结果准确,聚类效果更好。通过与基于PCA方法的同调机群识别方法的分群结果的比较,清晰展示了本文方法的思想,并且通过标准测度函数值的比较表明了本文方法在聚类效果上的优势。

摘要：为了解决源数据维数较大的问题,提出了一种基于非负矩阵分解(NMF)的同调机群识别方法。采用发电机角速度作为源数据,使用NMF算法对其进行降维。由于此低维矩阵具有非负性质,因而该模型在消除冗余数据、降低维数的同时,保留了原始问题的实际意义。对低维矩阵归一化,再利用K均值聚类算法对其进行聚类,达到同调机群的分群目的。通过New England 10机39节点系统比较了基于NMF和主成分分析方法的分群效果,验证了基于NMF的同调机群识别方法的有效性。

非负矩阵集分解 篇4

关键词：社交网络,社团结构,非负矩阵分解

1 概述

社交网络如微博、微信、博客等在人们的生活中发挥的越来越广泛的应用,这些社交网络也在网络舆情等方面发挥了重要作用。这是因为在社交网络中,用户之间相互连接、影响,从而促进了信息像洪水一样的快速而广泛的传播,与传统媒体、门户网站不同之处就在于,他没有一个明显的传播主渠道。在社交网络中,用户经常只是和少部分其他用户信息交互频繁,而与其他大部分用户联系很少,这样,在用户之间就形成了许多明显的圈子,即社团结构。社团内的用户之间相互联系密切,相互共享信息或者进行合作,如微博、facebook、Twitter等网络应用中,有共同兴趣的节点相互分享视频、评论等信息,形成一种社团结构[1]。在这些圈子内,总会存在诸如名人、超级用户(如微博中的大V)和活跃用户,是社团中的活跃分子。相比之下,用户与社团外部之间的联系就相对稀疏的许多,但是,许多舆情也通过这些稀疏的连接将信息从一个社团散布到其他社团,从而引起其他社团广泛的关注。因此,在社交网络上,既要挖掘这些社团结构,获得用户之间的关系结构,便于对网络进行管理,又要掌握网络中社团活动的重要用户,掌握信息广泛传播的关键节点,只有这样,才可以全面掌握社交网络的活动规律,正确预见潜在的网络事件,挖掘诸如犯罪关系网等重要信息,保障网络的健康有序。

社交网络是一种复杂网络,它规模庞大,结构复杂,表现在节点数目巨大,网络结构呈现多种不同特征。连接具有多样性,节点之间的连接权重存在诧异。节点集可能属于非线性动力学系统,例如节点状态随时间发生复杂变化。自2002年Gir⁃ven和Newman提出社区挖掘的概念至今,新的理论、方法层出不穷,新的应用领域不断涌现.它不仅吸引了来自计算机科学、物理、数学、生物和社会学等领域的研究者,成为最具挑战性的多学科交叉研究课题之一;而且已被应用于社会网络分析,如恐怖组织识别、组织结构管理、网络推荐等方方面面。采用非负矩阵分解(NMF)的方法进行社团的发现。

2 基于非负矩阵分解的社团发现的方法

非负矩阵分解是近年来出现的一种新方法。它对矩阵分解中的元素都添加了非负的限制,即大于或等于0,这与事物的整体是部分之和的直观概念相符合,在应用中具有很强的可解释性,但是,对于非对称矩阵的非负分解,目前的算法效果并不太好,而在实际中,很多网络连接关系是有向的,它们对应的矩阵就是非对称的。我们通过对目标矩阵进行简单变换,添加必要的约束项,来实现基于非负矩阵分解的有向加权网络的社团发现,同时进一步分析用户在社团中的重要性,判断用户在社团中所处的作用和特点,从而可以达到有效分析和解剖网络结构的目的。

2.1 社团发现模型

对于一个网络连接关系,一般使用图来描述。其中:表示第i个节点,表示第i个节点到第j个节点关系的大小。其中,X是社团指示矩阵,其元素表示第i个节点属于第j个社团的大小。S是社团关系矩阵,其元素表示第i个社团与第j个社团的密切程度,n表示节点的个数,k表示社团的个数,一般来讲,社团的个数要远远小于节点的个数。

可见,对公式进行转置运算,并不改变节点属于哪个社团的特性,只是将社团之间的关系结构进行了融合。于是,对于非对称的目标矩阵,可以转化为对称矩阵。如下所示:

令,则:

由此,我们可以构建基于矩阵非负分解的社团发现目标函数:

|‖F表示Frobenius范数,简称F范数,‖‖1是l1范数,用来控制模型的稀疏度,让节点尽可能被清晰的划分。是可调节的平衡参数,0表示规模为n×k,元素全为0的矩阵,同样I表示元素全为1的矩阵。E是单位矩阵。

2.2 模型的优化求解

定义矩阵Nk×k是一个元素全部为1的矩阵,公式(3)可以改写为:

根据文献,我们可以获得迭代规则如下

其中,N表示元素全为1的k×k维矩阵。

3 实验

3.1 Zachary karate数据集

Zachary karate数据集是一个真实网。它是Zachary空手道俱乐部成员关系网络,是社会学分析等领域中最常用的一个小型检测网络之一。从1970到1972年,Wayne Zachary用三年时间观察了美国一所大学空手道俱乐部成员间的社会关系,并构造出了社会关系网(Zachary’s karate club network)。网络中的每个节点分别表示某一个俱乐部成员,节点间的连接表示两个成员经常一起出现在俱乐部活动(如空手道训练、俱乐部聚会等)之外的其他场合,即在俱乐部之外他们可以被称为朋友。调查过程中,该俱乐部因为主管John A(.节点34)与教练Mr.Hi(节点1)之间的争执而分裂成2个各自为核心的小俱乐部。这个矩阵经常被用来检测算法的有效性。

3.2 其他真实数据集

我们还利用其他真实数据集来做实验比较,如:American College Football,Neural Network数据集,以模块度值[11]作为衡量指标,实验表明,我们的算法都得到了较精确的社团划分结果。除了Dolphin Social Network数据集外,我们的算法都要好于其他基于非负矩阵分解的算法。

4 结论

本文针对网络中节点复杂的连接关系,改进了以往社团划分算法只能解决无向网络问题的缺点,构建了基于有向加权图的非负矩阵社团划分模型,提出了模型求解的算法,并且提出了社团中节点的重要性等性质的定量分析,在真实的网络数据集上的实验表明,我们提出的算法正确的给出了社团划分结果,并对节点在社团中的性质进行了详细的分析,其结果符合人们的直观认识。我们的算法对于研究社交网络中复杂的人际关系提供了一种有用的方法,对于网络的结构分析,信息在用户之间的传播有参考意义。

参考文献

[1]曹贵强.纸币识别及红外鉴伪技术的研究[D].辽宁科技大学,2014.

非负矩阵集分解 篇5

NMF问题可描述为: 已知V∈Rm+× n,求解非负矩阵H∈R+r × n和W∈Rm+× r,满足

其中,‖·‖F表示对应矩阵的Frobenius范数; ≥表示矩阵的元素均≥0。

对于此问题,当前的算法主要分两类: 一类是乘性迭代算法; 另一类是交替最小二乘算法( ANLS) 。乘性迭代算法［1］由Lee和Seung于2001年提出,算法本身简单但收敛速度较慢。交替最小二乘方法由于其的理论可靠性和实际有效性,逐渐受到研究者的重视。基于此,众多算法被提出,例如投影梯度法( PG)［12］、积极集法( AS) 、投影拟牛顿法( QN) 等［7 －8］。

ANLS框架如下

ANLS关键在于如何高效求解子式( 2) 和式( 3) 。 本文基于ANLS,将文献[13]中积极集共轭梯度算法应用于求解该子问题,并在一定条件下证明了其收敛性,数值实验表明新算法在迭代次数和时间方面具有一定的优越性。

1算法

由于式( 2) 和式( 3) 是对称的,所以只需讨论其中一个。

1. 1构造搜索方向

利用子空间的思想构造4个互不相交的指标集

其中,ε,ε1是常数; Hkia表示第k次迭代H的第i行第j列的元素; ▽f( Hk)ia表示Hk的梯度的第i行j列的元素; 〈·〉代表内积,迭代中搜索方向Dk= ( DBk,DAk1,DkA2∪A3)T,为使迭代点始终在可行集的内部,对应的迭代方向如下:

当ia∈B时

当ia∈A1时

当ia∈A2∪A3时

定理1若Hk不是式( 2) 的稳定点,则〈▽f( Hk) , Dk〉<0

证明当ia∈B时

所以ia∈B∪A1∪A2∪A3

由于当( Wk,Hk) 不是稳定点时f( Hk) ≠0,ia∈B∪A2∪A3,所以〈▽f( Hk) ,Dk〉<0。由定理1,可知Dk为下降方向。

1. 2非负矩阵分解的子空间共轭梯度算法

求解子式(2)的算法如下:

( 1) 给定初始点H0是一个可行点,正数tol,ε,ρ, δ∈( 0,1) 。( 2) 当Dk= 0时,停止。( 3) 由式( 4) ~ 式( 6) 计算Dk。( 4) 令 αk∶ = max{ βρj,j =0,1,…} 满足条件

令Hk + 1= PΩ( Hk+ αkDk) 。( 5) 令k∶ = k +1,转步骤2。 注:1) PΩ( X) 表示X在 Ω = { H ∶H ≥ 0} 上的投影,由式(8)可知f(H)是递减的,因此能推出当f(H)有下界时,尤其是有

2数值实验

KKT［14］条件等价于▽HPF( Hk) =0,其中▽HPF( Hk) 是投影梯度,定义为

类似于投影梯度法［12］,可使用下式

作为式( 2) 的终止条件,使用

作为式( 1) 的终止条件。

文中对提出的算法进行数值实验,程序采用Mat- lab7. 6编写,在主频为3. 10 GHz,内存3. 00 GB的电脑上实现。V,W,H为随机生成的服从正态分布阵, 维数为m =300,n =200。r分别取5,10,15; 分别选择PG算法、BP算法、AS算法来进行比较,所有算法均采用相同初始值。并对每个V分别取10组不同的初始值,给出10次实验结果的平均值。相关的参数如下

在比较了几种算法在迭代次数( iterations) 和迭代时间( time) ,投影梯度范数( pro - grad) ,矩阵分解后的误差 ω,其中 ω = ‖V - WHF‖,最大迭代时间为200 s,最大迭代次数5 000次。

图1选取维数为500 ×300,秩r =10,所有算法选取相同的初始值,取10次的平均值。

图2选取维数为1 000 × 500,秩r = 10,所有算法选取相同的初始值,取10次的平均值。

通过上表和图可看出,BP算法和AS算法在迭代次数上是相同的,但在时间上BP算法则更快。PG算法与文中的新算法均是采用相同的终止条件,但文中算法在迭代次数和时间上相比PG算法更具优势。在秩相同的情况下,4种算法的投影梯度范数( pro - grad) 、分解后的误差 ω 基本相同。但文中的NMFCG算法能在更少的时间和迭代次数内达到与经典算法相近的效果。

3结束语

本文基于交替最小二乘法将界约束优化中的积极集共轭梯度法运用到非负矩阵分解中,并通过实验结果验证了BP算法和AS算法在时间方面的差距,而新算法在迭代次数与时间方面也表现出了优越性,达到了预期效果。

摘要：交替最小二乘法由于其理论可靠性和实际有效性成为非负矩阵分解中备受欢迎的方法之一。文中基于交替最小二乘法将界约束优化中的积极集共轭梯度法运用到非负矩阵分解当中,算法在子问题的求解中,并利用子空间的思想来划分指标集,并利用文献CHENG Wangyou文中的共轭梯度法进行变量更新,在一定条件下证明了新算法的收敛性,实验结果表明算法是有效的。

非负矩阵集分解 篇6

关键词：多特征融合,二维主成分分析,非负矩阵分解

0 引言

近年来非负矩阵分解 (NMF) 的方法被广泛地应用于图像检索[1]、图像融合[2]、人脸识别[3]等领域。1999 年Lee和Seung在Nature上提出了非负矩阵分解算法理论。在矩阵中所有元素均为非负并且任意一行元素的和不为零的条件下, 该算法可以对其进行非负分解, 分解的结果中不出现负值。因此, 每幅图像可看作是基图像的线性组合。本文对每一个降噪后的图像分别进行分解, 降低分解矩阵的维度, 提高运算效率。

基于非负矩阵分解算法属于一种传统算法, 通过计算基矩阵 (投影矩阵) 和系数矩阵才能得到分析结果。但是运用维数较高的系数矩阵进行迭代求解, 计算过程相当复杂, 且计算量也非常大, 耗时又耗力。鉴于非负矩阵分解的不足, 本文提出了二维投影非负矩阵分解 (2-dimensional projective non -negative matrix factorization, 2DPNMF) [4]的图像检索算法, 该算法打破非负矩阵分解的损失函数的计算框架, 在二维主成分分析环节引入了非负性约束条件, 提出了系数矩阵的计算环节, 只需计算基矩阵即可完成特征提取, 所以2DPNMF算法的计算分析过程用时更短, 速度更快。

1 多特征融合

基于内容的图像检索是在提取图像中底层特征的基础上进行的。而图像的底层特征有很多, 包括颜色特征[5]、纹理特征[6]、形状特征[7]等。图像的颜色特征即视觉特征, 是最直观的图像识别因素, 也是识别图像色彩的主要依据, 有很强的鲁棒性;纹理特征图像检索中都会用到的一个底层特征, 彩色纹理相当于局部区域中像素之间关系的一种度量, 能够描述像素邻域灰度空间分布规律, 或者图像的色彩及结构特点。本文提取颜色和纹理特征。

1.1 颜色特征提取

Swain和Ballard[7]等人在1990 年提出利用颜色直方图作为图像颜色特征的方法, 人们常用颜色直方图来表示图像的颜色特征。颜色直方图是一个一维的离散函数, 即:

计算颜色直方图需要把颜色空间划分为若干个子区域, 各区间相当于直方图的一个间隔, 这就是颜色量化 (color quantization) 的过程。然后对每幅图像统计属于子空间的像素数目就得到了颜色直方图。本文在RGB空间下提取图像的颜色直方图。利用颜色直方图构建特征向量。

1.2 纹理特征提取

灰度共生矩阵 (GLCM Co.Occurrence Matri X) 由Haralick等人在1973 年提出的, 它建立在图像二阶组合条件概率密度函数基础上, 计算出图像中特定方向和特定的距离的两个像素灰度出现的频率, 该频率与空间位置中纹理灰度所呈现的频率特征基本相似, 因此灰度共生矩阵非常适合纹理分析。为了简便, 一般采用以下四种特征来提取图像的纹理特征。

1.2.1 角二阶矩

我们通常所说的能量实际是是灰度共生矩阵各元素的平方和, 即角二阶矩。它是影像纹理灰度变化均一度量, 反映了影像灰度分布均匀程度和纹理粗糙细度。

1.2.2 对比度

对比度是灰度共生矩阵主对角线附近的惯性矩, 它度量矩阵的值是如何分布和影像中局部变化的多少, 反映了影像的清晰度和纹理的沟纹深浅。

1.2.3 相关

它是度量空间灰度共生矩阵元素在行或列方向上的相似程度, 因此, 相关值大小反映了影像中局部灰度相关性。

1.2.4 熵

熵是度量影像纹理的随机性。当空间共生矩阵中所有值均相等时, 它取得最大值;相反, 如果共生矩阵中的值非常不均匀, 其值较小。

在对纹理特征提取的过程中, 我们对灰度共生矩阵的计算结果做简单的处理。最简单的方法取不同方向 (0°、45°、90°、135°) 的偏移参数, 作其灰度共生矩阵, 分别求出特征指标, 然后对这些特征指标计算均值和方差。这种处理方法抑制了方向分量, 使得到的纹理特征与方向无关。

利用以上提取的四种特征构建特征向量。颜色特征和纹理特征组成一个七维矩阵, 利用非负矩阵分解进行构建系数矩阵。

2 二维投影非负矩阵分解

本文在传统的二维主成分分析 (2DPCA) 方法和非负矩阵分解 (NMF) 方法的基础上, 进一步优化调整非负矩阵分解最小误差框架, 提出二维投影非负矩阵分解 (2DPNMF) 算法, 通过计算最优的投影矩阵 (基矩阵) 即可得到分析结果, 不必再计算系数矩阵, 这样既简化了迭代更新计算流程, 又缩短了训练时间, 大大提高了计算分析速度。

Zass等[8]提出了非负稀疏主成分分析 (Non -negative sparse PCA, NSPCA) NSPCA不再考虑非负矩阵分解算法的两类损失函数, 只是把非负限制加在了主成分分析目标函数上, 从而从根本上打破了非负矩阵分解框架。NSPCA先把每幅p×q大小的二维图像Ak按行 (或列) 拉伸为一个pq维的向Vk, V=[V1, V2, …, Vm]为全部训练样本的集合, 大小为pq×m假设训练样本集包含100 张64 像素×64 像素大小的训练图像, V的维数为4096×100。NSPCA是寻找4096×r大小的基矩阵W, 满足约束优化问题。

其中, I为r×r的单位矩阵, || *||代表* 的2 范数, α 为常数。然而NSPCA是基于一维向量的算法, 此迭代过程处理的基矩阵W规模很大, 使得迭代过程十分耗时。而且由于NSPCA是针对一维向量的算法, NSPCA不能保持图像行列之间的局部特征。

鉴于上述NSPCA的不足, 本文提出了二维投影非负矩阵分解 (2DPNMF) 该算法是NSPCA的延伸, 2DPNMF直接基于二维图像, 而不需要先把人脸图像转化为高维的向量。 因此2DPNM解决了传统非负矩阵算法面临的高维问题。并且, 2DPNMF具有非负约束, 能更好地保持图像行列之间的局部特征。2DPNMF是寻找一个p×r维的非负基矩阵W, 使得Ak在W上的投影最大, 同时要求W不同列之间尽量单位正交, 即

本文采用Lee提出的乘性迭代法求解上述约束条件

可以看出, m Wn和Wn (Wn) TWn维数为p×r, 比原始图像维数还小, 因此采用迭代法计算速度较快。

从表1 所示各类算法的迭代更新条件可以看出, 2DPNMF算法在传统算法的基础上简化了每次迭代更新的条件, 基矩阵比原始图像矩阵小, 不必高维问题, 因此特征提取用时较短。

训练和识别算法:

本文已设定了二维投影非负矩阵分解计算基矩阵W及识别过程的基本流程。假设训练样本集包含N个p×q大小的图像特征矩阵, V1.V2……Vm。

算法1 2DPNMF求解基矩阵W算法:

输入:m个p×q大小的人脸特征矩阵V1.V2……Vm。迭代次数max_iter以及压缩维数r。

输出:p×q大小的基矩阵W。

(1) 计算

(2) 随机生成初始基矩阵, 。

(3) While k≤max_iter

(4) Endwhile

算法2 2DPNMF识别算法:

输入:m个p×q大小的训练矩阵V1V2…Vm, p×r大小的基矩阵W。一个p×q大小的测试矩阵V0。

输出:测试样本V0的类别索引l (V0)

(1) 计算W1 的广义逆矩阵W-= (WTW) -1×WT。

(2) 计算训练样本和测试样本在W-上的额头应系数矩阵, Hi=W-Vi, i=1, 2, …, m和H0=W-V0。

(3) 计算H0与Hi之间的欧氏距离di (V0) =H0-Hi2, i=1, 2, …m。

(4) 判定V0的类别索引为di (V0) 最小值对应的索引i, l (V0) =argminidi (V0) , i=1, 2, …, m。

3 实验与分析

本实验通过采用国际通用500 副人物图像作为实验数据库。实验使用Matlab7.0 软件在Window XP, 3.0GHz, 内存2.0GB计算机上进行。实验从以下三个方面进行:

(1) 在图像库中, 在不同压缩维数和训练样本个数下, 分别将NMF算法分和现有2DPNMF算法进行比较, 目的是比较在不同压缩维数和训练样本个数下两种算法的检索效果。

(2) 在图像库中, 选定, 分别在多特征训练样本分析中, 将2DPNMF算法与一、二维算法的特征和检索效果进行对比。

(3) 在图像库中, 比较NMF (一维特征) 、NMF (二维特征) 、2DPNMF (一维特征) 、2DPNMF (二维特征) 四中方法的运行速度和准确率。

3.1 实验数据

图像库中包含了500 副人物图像, 每幅图像的分别率均为112 像素*92 像素, 本案例的要求是将其处理为100像素*100 像素。图1 是其中的7 副图像。

3.2 查准率随压缩维数的变化

通过设定不同维数和训练样本个数, 对比分析2DPNMF算法与NMF传统算法的检索效果。选择以上七张图像作为训练样本, 其余作为测试样本, 压缩维数从1*100 变化如图2 所示。

根据图2 所示各种算法随压缩维数以及训练样本特征的变化, 总结出以下结论:

(1) 虽然训练样本特征个数不同压缩维数不同, 但是本文的算法与传统NMF算法相比, 检索效果进一步优化, 更具实效性。

(2) 训练样本特征相同时, 2DPNMF算法的查准率高于传统NMF算法。

(3) 随着训练样本的增加, 样本之间的特征信息越来越丰富, 2DPNMF算法的检索结果优于传统的NMF算法。

3.3 算法运算时间的比较

本节通过计算NMF算法、本文2DPNMF算法与不同颜色特征融合后的运算速度进行比较如表2 所示。

通过表2 可以看出, 本文算法简化了NMF算法中的训练算法部分, 减少了损失函数的计算时间, 使得整个算法的运算时间得到了提高。

4 结论

本文提出多特征融合与二维投影非负矩阵分解结合的图像检索算法, 该算法不仅融合了多种特征, 更全面、准确的表达一副图像, 而且融合了二维投影非负矩阵分解算法, 直接基于二维图像, 同时非负限制能够保护图像的局部信息。2DPNMF算法不同于传统的非负矩阵分解算法, 二维投影非负矩阵分解算法不在考虑非负矩阵分解的损失函数, 只需计算基矩阵即可完成特征提取, 不必再构建系数矩阵, 简化了计算流程。实验结果证明本文算法提高了检索效率和查准率, 有很大的实用价值。

参考文献

[1]王科俊.左春婷.非负矩阵分解特征提取技术的研究进展[J].计算机应用研究, 2014, 04 (15) .

[2]蒋娇娇.非负矩阵分解算法的改进及应用[D].北京工业大学, 2011.

[3]张素娥, 周军.Gabor小波变换和NMF结合的人脸识别[J].计算机工程与应用, 2015.

[4]C.Boutsidis, E.Gallopoulos.SVD based initialization:A head start for nonnegative matrix factorization[J].Pattern Recognition, 2007 (4) .

[5]张鑫, 温显斌.基于颜色特征的图像检索方法研究[J].计算机科学, 2012, 11.

[6]刘丽.图像纹理特征提取方法综述[J].中国图像图形学报, 2009, 4.

[7]付伟.基于形状特征的图像检索技术研究[J].计算机科学与技术, 2007, 11.

非负矩阵集分解 篇7

关键词：非负矩阵分解,哈希算法,鲁棒性

随着网络通信技术的迅速发展和多媒体数字产品的爆炸式增长,大量的数字图像应用在日常生活和工作中。数字图像满足了人们的感观需要,也为人们的生活工作提供了便利。由于图像本身就是一个矩阵,所以矩阵的应用在数字图像处理中就显得尤为重要。

1 鲁棒Hash技术概述

鲁棒哈希是一种基于多媒体内容的数字摘要。现有的感知哈希认证方案主要结构如图1所示。

在感知哈希的构造中,首先利用密钥提取多媒体内容的某些鲁棒特征,然后通过进一步的压缩产生哈希值。生成的哈希值被嵌入媒体或伴随着媒体传输到接收端,接收端的认证者使用与发送端相同的密钥对接收到的图像提取哈希。认证者通过比较跟随媒体内容传送来的哈希和接收端产生的哈希,就可以实现对媒体内容的真实性认证。

对于图像哈希函数,有如下几方面要求:

(1)复杂度:哈希函数的算法应具有较低的计算复杂度。

(2)鲁棒性:相同感知的图像具有相同或相近的哈希值。传统哈希算法(MD5,SHA-1)对信息变动非常敏感,一个bit的信息变化都会造成生成的哈希序列完全不同。数字图像等多媒体数据可能会经过压缩增强等操作,这些操作虽然改变了图像信息,但并未影响图像的视觉内容。因此图像哈希算法需要考虑图像视觉域的内容信息改变,即相同内容的图像经过哈希函数运算生成的哈希序列应该相同或相近。

(3)唯一性:不同感知的图像经过哈希函数处理产生不同的哈希值。

(4)安全性:不同的密钥加密后,即使是相同的图像也要产生不同的哈希值。

2 基于NMF的鲁棒Hash算法过程

可以用如下的过程来实现一个鲁棒Hash函数:

(1)设给定的n×n图像I∈Rn×n为鲁棒Hash函数的输入函数。

(2)对给定的图像I,利用伪随机数发生器产生p个相互重叠的矩形局域,每个区域Ai的大小为m×m。

(3)对每个区域Ai,i∈{1,2,…,p}利用变换,产生特征矢量g軋i=T1(Ai)。

(4)根据得到的{g軋1,…,g軋p},伪随机地构造一个二次图像J。

(5)对二次图像J,伪随机地产生r个可相互重叠的矩形区域,Bi∈Rd×d,i∈{1,2,…,r};

(6)利用投影变换T2,对每个Bi,产生一个矢量

(7)将所有的组合产生最终的Hash矢量。

Matlab源程序如下:

最后进行图像认证,按照如下公式计算两哈希序列的距离来进行匹配,即:

其中,hnew表示要新生成的Hash值,horigin表示最终的Hash值。

3 NMF的鲁棒性实验及结果分析

实验使用了15幅512×512的标准灰度测试图像baboon、boat、bridge、couple、crowd、girl、goldhill、lake、Lax、Lena、man、milkdrop、peppers、plane、woman2进行测试,如图2所示。

分别进行格式转换、滤波、剪切、比例缩放、JPEG压缩、叠加噪声、旋转后图像与原图像的哈希序列匹配测试,然后测试15幅图像Hash变换的平均值,实验结果如图3～图8所示。

图9～图12给出了一般的图像处理后的Lena图像的结果。表1给出了这四种图像处理后的鲁棒Hash值的变换情况。

根据实验结果图3～图12以及表1可以看出,NMF的Hash算法在抵抗图像压缩、加噪和缩放攻击时具有较好的鲁棒性,其Hash值的距离均不超过门限0.03,而对其他一些信号处理如旋转、低通滤波、锐化和剪切类的几何攻击,鲁棒性比较差,即使一般的图像增强处理也无法保证足够的鲁棒性。

鲁棒Hash技术利用密钥提取多媒体内容的某些鲁棒特征,然后通过进一步的压缩产生哈希值。生成的哈希值被嵌入媒体或伴随着媒体传输到接收端,接收端的认证者使用与发送端相同的密钥对接收到的图像提取哈希。本文通过比较跟随媒体内容传送来的哈希和接收端产生的哈希,就可以实现对媒体内容的真实性认证。

本文针对非负矩阵分解鲁棒Hash技术进行了验证性的研究,设计了基于NMF的鲁棒Hash算法,并进行了大量的实验分析,通过分析发现,NMF有两个非常可取的方面:(1)由非负性限制带拉点可加性,使得用于捕捉图像的局部特征的“基”能显著的降低误分类概率;(2)图像空间域的几何攻击可以当作是NMF矢量中的独立同分布噪声。NMF的Hash算法在抵抗图像压缩、加噪和缩放攻击时具有较好的鲁棒性,其Hash值的距离均不超过门限0.03,而对其他一些信号处理如旋转、低通滤波、锐化和剪切类的几何攻击鲁棒性比较差,即使一般的图像增强处理也无法保证足够的鲁棒性。

参考文献

[1]Wang Shuozhong,Zhang Xinpeng.Recent development ofperceptual image hashing[J].Journal of Shanghai University,2007,11(4),323-331.

[2]MONGA V,MIHCAK M K.Robust image hashing vianon-negative matrix factorizations[C].IEEE InternationalConference on Acoustics,Speech,and Signal Processing,2006:II-225-228.

[3]SCHNEIDER M,CHANG S F.A robust content based dig-ital signature for image authentication[C].in Proc.IEEEInt.Conf.Image Processing,Lausanne,Switzerland,1996.

[4]KAILASANATHAN C,NAINI R C.Image authenticationsurviving acceptable modifications using statistical measuresand K-Mean Segmentation[C].IEEE-EURASIP Work.Nonlinear Sig.and Image Proc.,2001.

[5]ALGHONIEMY M,TEWFIK A H.Geometric invariance inimage watermarking[J].IEEE Trans.Image Process,2004,13(2):145-153.

[6]叶卫国,韩水华.基于内容的图像Hash算法及其性能评估[J].东南大学学报(自然科学版),2007(s1):109-113.