矩阵分解 篇1
关键词：三角分解,QR分解,奇异值分解
一、矩阵的三角分解
定义:如果方阵A可分解成一个下三角形矩阵L和上三角形矩阵U的的乘积, 则称A可作三角分解或LU分解。
定理1:高斯消元过程能够进行到底的充分必要条件是A的前n-1个顺序主子式都不为零, 即△k≠0, k=1, 2, …, n-1。 (1)
当条件 (1) 满足时, 有L (n-1) …L (2) L (1) A=U。其中U为上三角形矩阵
, i=k+1, …, n。容易得出, detL (k) ≠0 (k=1, 2, …, n-1) ,
故矩阵L (k) 可逆, 于是有A= (L (1) ) -1 (L (2) ) -1… (L (N-1) ) -1U。由于 (L (K) ) -1是下三角形矩阵, 故它们的连乘积仍然是下三角矩阵。令
则得A=LU。即A分解成一个单位下三角形矩阵L和一个上三角形矩阵U的的乘积。
二、矩阵的QR (正交三角) 分解
定义:如果实 (复) 非奇异矩阵A能化成正交 (酉) 矩阵Q与实 (复) 非奇异上三角矩阵R的乘积, 即A=QR, 则称上式为A的QR分解。
定理2:任何实的非奇异n阶矩阵A可以分解成正交矩阵Q和上三角形矩阵R的乘积, 且除去相差一个对角线元素之绝对值等于1的对角矩阵D外, 分解成A=QR是唯一的。
矩阵QR的分解具体做法如下:
令A的各列向量依次为α1, α2, …, αn, 由于A是非奇异的, 所以α1, α2, …, αn线性无关, 按照施密特正交法正交化得到个标准的正交向量β1, β2, …, βn, 且
这里bij都是常数, 且由正交化过程知bii≠0 (i=1, 2, …, n) 写成矩阵形式有 (β1, β2, …, βn) = (α1, α2, …, αn) β, 即Q=AB。其中
是上三角矩阵 (bii≠0, i=1, 2, …, n) 。显然B可逆, 而且B=R-1也是上三角矩阵, 由于Q的各列标准正交, 所以Q正交矩阵, 从而有A=QR。
三、矩阵的奇异值分解
定理3 (奇异之分解定理) 设A是一个m×n的矩阵, 且r (A) =r, 则存在m阶酉矩阵U和n阶酉矩阵V, 使得UHAV= (2) , 其中Σ=diag (σ1…σr) , 且σ1≥σ2≥…≥σr≥0。由 (2) 知A= (3) , 该式称为A的奇异之分解, σr (I=1, 2, …, r) 称为A的奇异值, U的第i列称为A对应σi的左奇异向量, V的第i列称为A对应σi的右奇异向量。
求解奇异值分解的步骤如下:
步骤1:确定Σ, 计算AHA, 求其特征值λi, 可得A的正奇异值σi=, i=1, 2, …, r, 则Σ=diag (σ1…σr) , 且σ1≥σ2≥…≥σr≥0。
步骤2:确定V, 求非零特征值对应的特征向量Pi, 将其用Schmidt正交化化为标准正交向量vi (i=1, 2, …, r) , 即得V1= (v1, v2, …, vr) 。再取V2与V1的列向量拼成Cn的标准正交基, 即得到= (v1, …, vr, vr+1, …vn) 。
步骤3:确定U, 求U1∈Cm×r, 取V1= (v1, …, vr) , ∑=diag (σ1, …, σr) , 计算U1=AV1Σ-1。在Cm中取U2∈Cm× (m-r) , 使得U1与U2的列向量成Cn的标准正交基, 从而U=[U1, U2]为酉矩阵, 则A=U
参考文献
[1]方保镕, 周继东, 李医民.矩阵论[M].北京:清华大学出版社, 2004.
[2]戴华.矩阵论[M].北京:科学出版社, 2001.
矩阵分解 篇2
自《Nature》1999 年刊登了两位科学家D. D.Lee和H. S. Seung有关非负矩阵( Non-negative matrix factorization,NMF) 研究的成果后,此分解算法逐渐被人们接受并应用到各种领域。NMF的基本思想可以简单描述为: 对于任意给定的一个非负矩阵A,NMF算法能够寻找到一个非负矩阵W和一个非负矩阵H,使得满足A = WH,从而将一个非负的矩阵分解为左右两个非负矩阵的乘积。非负矩阵分解已经应用到许多领域,比如计算机视觉、文本聚类、化学统计学以及推荐系统[1,2],其在网络安全的入侵检测、灰度图像的数字水印技术和脑电信号处理方面的应用,证明非负矩阵分解在智能信息处理和模式识别的大规模数据处理与分析中有着十分重要的意义。
1 非负矩阵分解
非负矩阵分解,又名非负矩阵优化,是多变量分析和线性代数中的一组算法,使得矩阵A分解为矩阵W和矩阵H,并且这三个矩阵均不含负的元素。这种非负性使得结果矩阵很容易检验,由于该问题一般不是精确可解的,它通常是近似数值。
NMF有一种固有的聚类属性,它能够自动地聚类。更具体地说,就是对于非负矩阵分解A = WH,最小化误差函数min‖A-WH | | ,subject to W,H≥0。本文将非负矩阵分解应用到了复杂网络社区检测领域[3],该算法在三个真实世界网络以及计算机生成的GN基准网络[4,5]和LFR基准网络上产生很好的模块度值,成功地检测出社区结构,证明了算法的有效性和准确性。
2 建立社区检测模型
2. 1 一般的非负矩阵分解模型
通过矩阵分解的方法做社区检测的模型一般为: min‖X - AAT‖F2,s. t A≥0。X表示网络的邻接矩阵,规模是n行n列。A表示社区隶属度矩阵,规模是n行k列,k表示社区划分的个数。
标准的非负矩阵分解试图分解一个n行m列的矩阵X成为两个非负矩阵U1 和U2,U1 是n行c列,U2 是m行c列,使得X≈U1* U2T,由于复杂网络中的无向图的邻接矩阵X是对称矩阵,所以非负矩阵分解( NMF) 可以表示为对称非负矩阵分解( SNMF) 。
在无监督学习领域,NMF成为最流行和普遍使用的模型之一,也有许多基于NMF的模型的社区检测方法。由于该模型非常灵活,NMF非常适用于做交叠社区检测[6]。非负矩阵分解的结果矩阵U可以看做是一个聚类隶属度矩阵,比如Uic表示节点i属于社区c的隶属度,并且∑Uij= 1,即可以知道一个节点属于每个社区的隶属度,提供网络的模糊社区划分。
本文提出的方法的优点是: 1产生交叠的结果( 软分类) ,允许社区共享成员; 2软分类的分布量化了每个个体在多大程度上属于某一团体; 3拥有优秀的模块度检测能力; 4该方法不像基于模块度优化算法那样,受到分辨率的限制。
本文提出了一种基于对称非负矩阵分解模型的社区检测方法,可以检测出每个节点属于每个社区的隶属度,相当于一种模糊聚类方法。
2. 2 提出新的对称非负矩阵分解模型
对称非负矩阵分解( SNMF) 模型的定义为: 对称矩阵Xnn表示该矩阵有n行n列,本文想找到一个矩阵Anc( n行c列) ,使得矩阵X≈A × AT。目标矩阵X表示复杂网络的邻接矩阵,结果矩阵A表示该网络的社区隶属度矩阵: Aic= 1 表示节点i属于社区c,Aic= 0 则表示节点i不属于社区c。在隶属度矩阵中,寻找第i行的最大值所对应的列数c,即节点最有可能属于的社区。将Aic的值赋为1,第i行的其他列的值均赋为0。此时,就将模糊社区检测转化为非模糊的社区检测,也就是本算法最后所得到的结果。如果节点i是一个离群值( 奇异点) ,则第i行的和为0,即: ∑Aij= 0。
假设有相对一小部分奇异点,即一个节点不属于任何一个社区,本文希望这些奇异点尽可能的少。因此将这个惩罚项加入了优化模型。在上文的NMF模型中,使用了F范数,而1 范数广泛应用在健壮的数据分析和特征选择的稀疏编码。本文处理的复杂网络也大多属于稀疏网络,所以,使用了1 范数来代替F范数,事实证明使用1 范数可以产生更好的算法结果。
SNMF模型表示为:
H是个阶跃函数,对于矩阵X:
3 基于非负矩阵分解的复杂网络社区检测算法GASBMF
预处理复杂网络的邻接矩阵A,设置邻接矩阵A的对角线元素为1; 该算法首先需要初始化矩阵U,利用乘法更新规则来初始化矩阵U。设置迭代次数T为50 次,该算法需要预先知道社区数目K。算法1 介绍了矩阵U的初始化过程。
算法1 矩阵A的初始化
输入: 邻接矩阵X,迭代次数T,社区个数K
输出: 矩阵A
4.end for
算法1 对邻接矩阵A进行非负矩阵分解: X≈A × AT,Ait表示矩阵A的第i行第t列的元素,Aij表示矩阵A的第i行第j列的元素,Ait= 1 表示节点i属于社区t,Ait= 0 表示节点i不属于社区t,∑Aij=0 时,即产生了异常值。
利用SNMF模型得到了初始化矩阵A后,通过离散化矩阵A,将优化的问题变成更为简单的无约束非线性规划问题。即优化公式( 3) :
其中,u是一个标量。本文利用遗传算法[7,8]对参数u进行优化,算法框架如算法2 所示。
算法2 利用遗传算法优化参数u
输入: 矩阵U,种群规模Popsize为100,染色体长度为10,交叉概率为0. 6,变异概率为0. 001,迭代次数为50
输出: 最优参数u
1. 随机产生初始化的种群
2.计算目标函数值,并求每个个体的适应度值
3.复制操作
4.交叉操作
5.变异操作
6.求出种群中适应度值最大的个体及其适应度值
7.达到最大迭代次数,算法结束
通过算法2 得到了矩阵A的最优参数u,将参数u带入矩阵A中。通过公式A = H( A - u) ,即可得到一个二值矩阵A。在该二值矩阵A中,矩阵行数为n即为网络中节点数目,矩阵列数K表示社区个数。Aij= 1 表示节点i属于第j个社区,Aij= 0 表示节点i不属于第j个社区。Aij> 1 表示节点i属于交叠节点,Aij= 0 表示产生了异常值。然后根据矩阵A就可以得到复杂网络的类标Label。
4 实验结果及分析
为了证明算法的有效性,将GA-SBMF算法应用于三个真实世界复杂网络和已知真实划分的人工合成复杂网络,并且与没有加入遗传算法优化参数SBMF算法得到的结果进行了比较。
4. 1 真实世界网络
将GA-SBMF算法应用到三个真实世界复杂网络上。
1Jazz数据集
爵士乐队合作网络,该数据集包含在1912 年至1940 年表演的198 个乐队,其中大部分乐队集中在二十世纪二十年代表演。每个乐队相对于每一个节点,如果两个乐队之间至少存在一个相同的歌手,则这两个乐队之间有连接,即两个节点之间有边相连。该网络节点数为198,边的数目为2742。
2E-mail数据集
该数据集是西班牙的URV大学的E-mail网络,该网络是由大约1700 名用户组成,包括教员、研究人员、技师、经理、管理员和研究生。考虑2002 年第一季度该学校人员的邮件交流情况。每一个人代表一个节点,如果两个人之间互相发过电子邮件,则这两个人是有联系的,即两个节点之间有边相连。大多数E-mails没有提供个体或团队是如何合作的信息,在加入了一些限制条件后,该无向网络由1133 个节点组成。
3Netscience数据集
在科学家合作网络中,把每位科学家看做是节点,把合作发表文章或者合作研究项目作为节点之间的边。该复杂网络共有来自各个领域的1589 名科学家。
由表1 可以看出在Jazz、E-mail和Netscience复杂网络上,GASBMF算法的平均模块度值高于原始的SBMF算法的平均模块度值,并且在Jazz和Email网络中模块度值Q的标准差低于SBMF算法,说明GASBMF算法不仅效果好,而且算法的稳定性也要好。在Netscience网络中,两种算法的平均模块度值和模块度的标准差相当。
4. 2 计算机仿真网络
GASBMF算法将遗传算法( GA) 与非负矩阵分解方法( NMF) 相结合,遗传算法能够搜索出最优解,从而找出最优参数,最终得到更好的社区划分结果。在计算机生成的基准网络———GN网络和LFR网络上均取得了很好的结果,将本算法结果与SBMF算法结果相比较如表2 所示。
SBMF算法在GN基准网络上三十次运行的平均模块度值Q和NMI值如表3 所示。
在图1( a) 中data1 表示GASBMF算法独立运行三十次的平均模块度值,data2 表示SBMF算法独立运行三十次的平均模块度值; 在图1( b) 中data1表示GASBMF算法独立运行三十次的平均NMI值,data2 表示SBMF算法独立运行三十次的平均NMI值。可以看出在GN网络中,在外度Zout从0 到8这9 个网络中,GASBMF算法均好于SBMF算法; 当外度Zout从0 到5 时,两种算法均能准确地检测出网络的社区划分,Zout为6、7 时,GASBMF算法的NMI平均值好于SBMF算法,当Zout为8 时,SBMF算法的NMI平均值略好于GASBMF算法。
Lancichinetti-Fortunato-Radicchi( LFR) 基准网络是一种被广泛用于复杂网络社区检测领域的计算机生成网络。与GN基准网络相比,LFR基准网络允许用户设定生成网络的节点数目、边数目、社团数目和混合参数,更具有现实网络属性。节点的度和社团尺寸均服从幂律分布,其参数分别为 α 和 β。令节点的个数为N,节点平均度为< k > 。在本实验中,参数设置如下: α = 2,β = 1,N = 1000,< k > =20,节点最大度kmax = 50,且社团最大规模Cmax = 50,社团最小规模Cmin = 10。
图2 ( a) 表示GASBMF算法与SBMF算法在1000 节点的LFR网络上三十次独立运行的平均模块度值Q的比较,可以看出,混合参数从0 到0. 7,GASBMF算法的模块度值均好于SBMF算法得到的结果; 图2( b) 表示GASBMF算法与SBMF算法在1000 节点的LFR网络上独立运行三十次的平均NMI值的比较,可以看出,当混合参数为0 时,两种算法均能产生准确的社区划分结果,而当混合参数大于0 时,GASBMF算法的NMI值均好于SBMF算法。
当LFR网络的节点数为5000 时,算法运行一次需要的时间是5800s左右,因此,本实验设置为,α = 2,β = 1,N = 5000,且社团最大规模Cmax = 200,社团最小规模Cmin = 100。混合参数: 0. 1,0. 2,0. 3,0. 4,0. 45,0. 5,0. 55,0. 6,0. 65,0. 7,表4 给出了混合参数取0. 1 ~ 0. 7,运行三十次取平均值得出的NMI值和模块度值Q。
定义了一个衡量社区检测效果的准确率( Accuracy) ,准确率表示社区中划分正确的节点占网络总节点数的比例。可以看出当混合参数从0. 1 到0. 6时,这8 个复杂网络的准确率均高于0. 94,而且模块度值均大于0. 3; 对于混合参数在0. 1 ~ 0. 65 之间的5000 节点复杂网络,GASBMF算法所取得的NMI值高于0. 9,即使当混合参数为0. 7,即社区结构非常不清晰的时候,本算法也能产生0. 8574 的NMI值。可以说该算法能够处理大规模的社区网络,并能找出该网络的社区结构,通过实验也证明了其有效性和准确性。
5 结束语
非负矩阵分解算法是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法。由于复杂网络的表示采用邻接矩阵的形式,因而NMF为处理大规模数据提供了一种新的途径; 另外,NMF算法相比传统算法,具有实现上的简便性、分解形式的可解释性,以及占用存储空间少等优点。本文运用NMF建立用于社区检测的模型,在优化模型的过程中,使用了遗传算法对参数进行优化,该算法除了在三个真实世界网络取得理想的结果之外,还能够处理5000节点以上大规模的计算机仿真的LFR网络[9],并且取得了较好的结果。
摘要：为了了解复杂网络的特性,研究了复杂网络中的社区交叠现象,将非负矩阵分解算法用于社区检测问题。而传统的用于社区检测SNMF模型是通过离散化参数的取值范围,然后遍历得到参数的最优值,对参数的优化方法不能准确而快速搜索到最优解。利用遗传算法对参数进行优化,能够准确地找到参数的最优解,从而得到最优的社区划分。并且能够检测出交叠节点和异常节点,该算法也适应于大规模的数据。
关键词：复杂网络,社区检测,非负矩阵分解,遗传算法
参考文献
[1]Shi C,Yan Z,Cai Y,et al.Multi-objective community detection in complex networks[J].Applied Soft Computing,2012,12(2):850-859.
[2]Lin C J.Projected gradient methods for nonnegative matrix factorization[J].Neural computation,2007,19(10):2756-2779.
[3]Alexanderson G L.About the cover:Euler and Konigsberg’s Bridges:A historical view[J].Bulletin-American Mathematical Society,2006,43(4):567.
[4]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[5]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical review E,2004,69(2):026113.
[6]Yang J,Leskovec J.Overlapping community detection at scale:a nonnegative matrix factorization approach[C]∥Proceedings of the sixth ACM international conference on Web search and data mining.ACM,2013:587-596.
[7]Su J,Havens T C.Fuzzy community detection in social networks using a genetic algortihm[C]∥Fuzzy Systems(FUZZ-IEEE),2014 IEEE International Conference on,2014:2039-2046.
[8]张彤,张华.浮点数编码的遗传算法及其应用[J].哈尔滨工业大学学报,2000,32(4):59-61.
矩阵分解 篇3
摘要：智能建筑工程项目周期长、技术新、涉及范围广、风险因素数量多且种类繁杂，文章提出了一种两阶段风险分解矩阵法，可以便捷有效地完成智能建筑工程项目的风险识别。
关键词：智能建筑；风险识别；风险分解矩阵
一、引言
目前，世界上最先进的智能建筑技术在中国都已得到应用。然而。许多定位于智能型的建筑，其智能化系统的开通率、无故障运行率、节能增效的实际情况与预期的要求有较大差距。上海有关单位对该地区智能大厦的BA系统进行了调研，其结果表明，在这些大厦中，智能化系统的监控项目运行正常，在物业管理方面起重要作用的仅占20％。部分监控项目运行不正常。但尚可使用的系统占45％。有35％的BA系统在使用多年后。仍不能开通运行的或运行一段时间后发生了故障，无人修复而废弃不用。相当大一部分BA系统不仅不能实现预期的目标，反而浪费了大量的人力财力。
如果说最初的智能建筑项目失败案例可以视为无法进行概率统计的不确定性事件的话，那么随着这样的记录越来越多。非确定事件已变成风险事件。智能建筑项目具有高风险性，这是个不争的事实。项目的规模越大、技术越新、越复杂，其涉及的不确定因素也就越多。因而风险程度就越高。
有调查表明，在我国，包括智能建筑在内的所有与信息化有关的工程项目成功率不到30％，大约有70％以上的工程项目超出预定的开发周期，功能和性能达不到预期的效果。这些都促使科研人员和管理人员从理论和实践上重视对智能建筑工程项目的风险管理。
二、项目的风险识别及其常用方法
根据C-PMBOK的定义，项目的风险管理是通过计划、组织、指导、控制等过程，通过综合、合理地运用各种科学方法来实现其目标的。它包括项目风险识别、风险量化、风险评价、风险规划、风险控制、风险监督等风险管理全过程，
项目的风险识别是项目风险管理的基础，即识别项目实施过程中可能遇到的所有风险源和风险因素，对它们的特性进行判断、归类，并鉴定风险性质。项目风险识别。应是一项持续的、反复进行的工作，贯穿于整个项目的生命周期。
风险识别主要内容包括：有哪些风险应当考虑：引起这些风险的主要因素是什么：这些风险所引起后果的严重程度如何。
项目风险识别的方法很多，常用的有以下这几种。
1头脑风暴法。就是以专家的创造性思维来索取未来信息的一种直观预测和识别方法。
2德尔菲法又称专家调查法。用德尔菲法进行项目风险识别的过程是由项目风险小组选定与该项目有关的领域和专家，并与这些适当数量的专家建立直接的函询联系，通过函询收集专家意见，然后加以综合整理，匿名反馈给各位专家，再次征询意见。
3情景分析法。根据发展趋势的多样性，通过对系统内外相关问题的系统分析，设计出多种可能的未来前景，然后用类似于撰写电影剧本的手法，对系统发展态势做出自始至终的情景和画面的描述。
4风险分解树法。利用图解的形式将大的风险分解成各种小的风险，或对各种引起风险的原因进行分解，这是风险识别的有利工具。
三、智能建筑工程项目的风险识别
智能建筑在我国的兴起，不过短短的十多年，按照项目管理知识体系进行智能建筑工程项目管理，也是近几年刚刚开展。无论是开发商、集成商、设计院、政府管理部门还是物业运营公司等项目千系人，在数据积累和历史经验方面都显得不足，因此基于统计理论的风险识别方法，尚不适用。智能建筑工程项目要求高、周期长、技术新、涉及范围广、风险因素数量多且种类繁杂，致使其在整个寿命周期内面临的风险多种多样。而且大量风险因素之间的内在关系错综复杂、各风险因素之间与外界交叉影响又使风险显示出多层次性，因此某一种单独的风险识别方法也不足以应对这样复杂的局面。目前，智能建筑项目风险识别方法尚在探索之中，在实践中。笔者尝试将多种风险识别方法综合运用。形成“两阶段风险分解矩阵法”。
第一阶段：识别风险源——头脑风暴——德尔菲法。
在此阶段，首先分别在不同人群范围内(系统集成商、开发商、物业管理公司……)召开会议，以智能建筑项目的风险识别为主题。请各方专家们畅谈智能建筑工程项目的成败经验。发挥专家的创造性思维来获取信息。通过专家之间的信息交流和相互启发。达到互相补充并产生组合效应，总结、筛选出直接影响建筑智能化系统正常运行的风险源。在运用头脑风暴法去激发创意时，应注意到这是由许多人共同提出大量想法的策略，不要过早对意见下结论。最大限度地延伸风险源的范围，使风险识别更加有效。然后将众多专家的观点归纳整理，确定出智能建筑工程项目的风险源来自五个方面：
1决策风险。(1)目标错误：比如房地产项目本身定位不准，建筑智能化总体方案定位不准等。(2)招，投标决策风险：包括设计，监理，施工承包，设备材料供应商等方面的招标。
2技术风险。(1)设计风险：设计者与用户沟通不够：规范，标准选择不当；设计存在安全隐患：未考虑施工的可能性：设计内容不全、设计存在缺陷、遗漏和错误等。(2)软件风险：如用户需求不明确：变更过多：软件成本日益增长：开发进度难以控制：软件质量差：软件维护困难等。(3)设备风险：如设备可靠性差：后续配件支持缺乏等。(4)系统集成风险：根本无法集成：集成成本过高：不合理的集成方案和技术；未考虑工程现场的具体情况；未达到质量检验和工程验收标准等。
3项目管理风险。(1)计划进度风险。劳动力缺乏／工作效率低下；材料设备供应滞后；设计图纸供应滞后：不可预见的现场条件等。(2)成本控制风险。工期的延误；不适当的工程变更；不适当的工程支付；承包人的索赔；预算偏低；不适当的采购策略；项目外部市场条件发生变化等。(3)项目组织管理风险。缺乏项目管理能力；组织不适当：关键岗位人员经常发生变动；项目目标不适当。加之控制不力；缺乏项目管理协调等。
4外部环境风险。政府，主管部门对项目干预太多：建设体制或建设法规不健全；相关规范或标准的改变：企业并购：自然灾害等。
5行为主体风险。(1)业主：项目可行性研究缺乏严肃性(倾向性要求)；希望少花钱多办事，不遵循事物客观规律；投资先天不足；盲目干预。(2)系统集成承包商：：技术实力不够；不诚实；缺乏职业道德；工程管理能力不足。(3)工程监理：业务水平不足；职业道德差。(4)设计单位：自身能力和水平不适应；设计流程组织管理不善。(5)供应商：不能提供足够的技术支持。(6)物业管理公司：人员技术素质差，培训投入不够。(7)评审专家；个人专业局限性，不公正。
在头脑风暴结果的基础上。绘制出风险分解树(RBS)，如图1所示。
据此编制智能建筑工程项目风险专家咨询调查表，在
更大范围内分发出去，请各方面相关专家填表咨询。专家们根据自己的理解，对调查表中所归纳的各种风险因素，按照其对于建筑智能化系统的负面影响程度进行排序。这些影响包括：风险发生的概率、对系统性能的影响、对成本造价的影响和对项目进度的影响。
专家调查评判的目的是为后续的风险分析奠定基础。对回收的调查表进行数据统计、评估，找到影响智能建筑项目正常运行的主要的、关键的风险因素。
第二阶段：确定风险出现的时间点——基于生命周期的风险分解矩阵法。
智能建筑项目属于大型工程项耳，包括的任务多、工期紧。为了更好地完成项目。在实施过程中通常用工作结构分解(WBS)对项目工作进行层次化的分解组织。而把项目的工作分解树(WBS)和它的风险分解树相互联系在一起，是把项目的活动与风险相关联的好方法。WBS采用分层结构定义了达到项目终极目标所要完成的主要任务、次要任务和工作包。而风险分解树(RBS)同样采用了一个分层结构，对项目的风险源加以分类。
在智能建筑工程项目的整个生命周期内，风险无处不在、无时不有。在项目的整个实施过程中，各种风险在性质和数量上都是在不断变化的。随着项目的进行。有些风险可以规避。有些风险会得到控制，有些风险会发生并得到处理。同时在项目的每一阶段都可能产生新的风险。
为了更直观地反映各种风险可能出现的时间点，首先把智能建筑工程项目按照生命周期路径进行工作分解，生成图2所示的WBS。然后将该WBS和风险分解树RBS(如图1所示)结合在一起。产生一个矩阵结构一基于项目生命周期的风险分解矩阵(RSM)。如图3所示。
这是一个二维的矩阵，行和列分别代表工作包与风险源。可以看到有的风险源只存在于一个工作包内，而有的风险源则贯穿整个项目的全部生命周期，更多的情况是在一个任务包内同时存在几个风险源。通过这样一个基于项目生命周期的RSM矩阵，直观地列出了所有与项目相关的过程、参与者及存在的问题，从中确定风险的来源、产生条件。
四、结论
采用二阶段风险分解，生成了基于生命周期的RSM矩阵，它有助于项目管理者快速、清晰地识别出在任何一个项目阶段可能存在的各种风险源，进一步进行风险估计，从而制定动态的项目风险应对方案，在信息系统的支持下，可以建立智能建筑项目风险的预警系统。
参考文献：
1中国项目管理研究委员会，中国项目管理知识体系与国际项目管理专业资质认证标准，北京：机械工业出版社，2002。
2符志民，航天项目风险管理，北京：机械工业出版社，2005。
3李坚，谈我国智能建筑发展的有关问题及对策，科教创业月刊，2007，(11)。
矩阵分解 篇4
线性判别分析是一种有效的降维方法,该方法通过最大化Fisher准则,寻找类间散度最大、类内散度最小的投影方向,使得降维后的数据类内聚合度最高,类间离散度最大,数据更精确分类。2DLDA[8,9,10]是直接对图像矩阵执行判别分析方法,无需将图像矩阵拉成向量,类内散度矩阵与类间散度矩阵维数仅为图像行数或列数,因此投影方向易于计算,节省时间。
本文提出将二维判别分析方法与非负矩阵分解方法融合,提出一种双边非负矩阵分解方法。该方法先执行一次行非负矩阵分解,求出行基矩阵,为提高识别精度,再将此基矩阵正交化,作为一个投影矩阵,再由2DLDA方法求出另一投影矩阵。由于2DLDA计算时矩阵维数小,因而较文献[6]先对图像矩阵执行行非负矩阵分解,得到行基矩阵与行系数矩阵,再将行基矩阵正交化,得到一个投影矩阵,再对行系数矩阵执行一次非负矩阵分解,得到另一投影矩阵和文献[7]通过对图像按行或按列的不同排列方式,执行两次非负矩阵分解的双边非负矩阵分解算法,提出方法样本训练时间大幅减小。更进一步,由于非负矩阵分解算法只是提取局部信息进行分类,而将判别分析算法引入,使得整体信息类内高度聚合,类间最大距离分开,进一步加强了分类效果,而且2DLDA得到的投影矩阵列是正交的,较非负矩阵分解中非正交的基矩阵,能较好地消除矩阵列间的相关性,因而相比执行两次非负矩阵分解的双边2LDNMF和2RNMF算法,提出算法对人脸的识别率也有所提高。
1 非负矩阵分解算法
非负矩阵分解( NMF) 的思想是: 在误差最小的准则下,将一非负矩阵,分解成两个非负矩阵的乘积。设是训练集中的N个非负样本,构成样本集将其分解为非负基矩阵与非负系数矩阵即 X≈WH式中压缩维数r应满足( m + n N) < mn N。
分解中要求产生的矩阵没有负元,这就使得分解后的矩阵具有可解释性。而且分解过程是通过迭代法在逼近程度局部最小,且矩阵非负约束下,应用乘性迭代规则得到。其中W和H的更新过程如下
按照上式迭代,直到损失函数
达到局部最小,此处距离用欧氏距离评价。
1. 1 二维非负矩阵分解算法
二维非负矩阵分解( 2DNMF) 无需将图像矩阵拉成向量,而是对矩阵直接应用非负分解,未破坏图像数据结构,能较好地保持图像信息,较向量的非负矩阵分解方法,其识别率大幅提高,此方法包括行非负矩阵分解和列非负矩阵分解两种。
1. 1. 1 列非负矩阵分解
设是N个训练样本图像,按行排列构成集合在乘性迭代规则下对矩阵A执行非负矩阵分解( 2DLNMF)过程,将其分解为非负基矩阵和非负系数矩阵的乘积,即
将矩阵H分块为N个矩阵则Hi是图像矩阵Ai的系数矩阵,第i幅图像被表示成
1. 1. 2 行非负矩阵分解
对于行非负矩阵分解( 2DRNMF) 提出了两种方法,一种是串行的方法,即利用两次非负矩阵分解,计算出行投影基矩阵,具体方法如下: 在列非负矩阵分解X = WH后,由系数矩阵构造新矩阵再次应用非负矩阵分解方法,得到行非负基矩阵和非负系数矩阵使得HT≈RC将C矩阵分块为C =[C1,C2,L,CN]对每个
将式( 6) 代入式( 5) 得
另一种方法类似于列非负矩阵分解,只需将图像矩阵AT i按行排列构成样本集执行非负矩阵分解,得到行基矩阵任一训练样本特征即为
2 二维线性判别分析算法
线性判别分析( 2DLDA) 的思想是通过寻找最大化Fisher准则的最优投影变换矩阵,将高维数据投影到低维子空间。2DLDA的具体做法为: 设训练样本集为A = { A1,A2,L,AN} 训练样本总数为假设训练样本分为C类,Ak i( i = 1,2,L,N) 是第i类中的第k个训练样本,第i类Ci共有Ni个样本,即,则 Fisher准则为
其中类间散度矩阵
类内散度矩阵
则最优投影矩阵即为最大化Fiehser准则的方向,即为Sw- 1 Sb的前l个最大特征值对应的单位正交特征向量W =[w1,w2,L,wl]T则图像矩阵特征为Bi= AiW( i = 1,2,L,N) ,对于任一测试样本求出测试样本特征为,最后运用欧氏距离分类。
3 快速二维非负矩阵分解算法
虽然文献[6]已充分说明基于局部脸的非负矩阵分解方法( 2DLDANMF) 对遮挡和光照等外交条件变化不太敏感,非负性具有可解释性,进而使得识别率较整体脸方法有所提高。文献[7]实验结果显示双边非负矩阵分解方法较单边的非负矩阵分解,识别率进一步提高。但由于它是通过迭代方法获得基矩阵,当样本维数较高时迭代过程十分缓慢,计算一次基矩阵相当耗时。双边非负矩阵分解需两次执行非负矩阵分解过程,时间复杂度进一步提高。本文将非负矩阵分解方法与判别分析方法融合,提出一种双边非负矩阵分解算法,非负分解使得矩阵具有可解释性,将判别分析思想融入其中,使数据聚类分离效果更加准确,进一步提高识别率。而且较双边非负矩阵分解方法,只需执行一次非负矩阵分解的迭代过程,再执行一次2DLDA过程,由于2DLDA矩阵维数小,故可降低计算时间。具体做法如下: 对训练样本集先通过行非负矩阵分解方法计算出行基矩阵,将其正交化,得到左投影矩阵U = orth( R) 再对训练样本集执行2DLDA过程求出样本集的右投影矩阵最后得到样本投影特征Yi= UTAiV( i = 1,2,L,N) 对于任一测试样本求出测试样本特征为ty= UTt V∈其中非负矩阵分解列数r应满足( m + n) r < mn,l应满足( r + m) l < rn,最后运用欧氏距离分类。
算法用于人脸识别的快速非负矩阵分解算法。
输入输入N个样本图像矩阵,分解的列数r,迭代次数matxier,右投影向量个数l。
步骤1将图像矩阵排列构造样本集X = [A1, A2,L,AN]。
步骤2执行行非负矩阵分解求出基矩阵R,求出左投影矩阵U = orth( R) 。
步骤3构造类内散度矩阵Sw和类间散度矩阵Sb。
步骤4求出Sw- 1Sb的前L个最大特征值对应的单位正交特征向量v,得到右投影矩阵V =[v1,v2,L, vN]T。
步骤5求出样本图像和测试图像投影特征,利用欧氏距离分类。
4 实验结果及分析
实验环境: Windows 7 + Matlab2012,计算机的CPU为Intel( R) Core( TM) i5 2. 5 GHz,共2. 00 GB内存,对于所有人 脸识别实 验,使用基于 欧氏距离 的1 NN[17,18]算法来分类。对于两个参数r和l为了方便实验均设定r = l = d2其中( d = 1,2,L,p) p = minm,n为图像维数。
在实验中,使用如下两个数据库:
( 1) Yale人脸数据库由15人、每人11幅共165幅人脸图像组成。每幅图像灰度级为256,分辨率为100×100。Yale数据库中人脸图像光照条件变化较大,而且人的脸部表情和细节也有一定的变化。
( 2) AR人脸数据库是一个大型的人脸图像数据集。包括200个人、每人14幅共2 800幅人脸图像组成部分图像由于存在的太阳镜和围巾,可能会包含大面积的遮挡,这增加了类内的差异和识别难度。
实验中,在Yale人脸数据库上,随机选取每个人的6张图像做训练,5张图像做测试,在AR人脸数据库上,随机选取每个人的8张图像做训练,6张图像做测试。
4. 1 识别率比较
如图1所示,在Yale和AR人脸数据库上,在d取相同的 值时,2DLDANMF算法的识 别率高于 ( 2D)2LNMF算法和 ( 2D)2RNMF算法的识别率。其次,在d取相同值时,( 2D)2LNMF算法和( 2D)2RNMF算法的识别率较接近,说明行方向和列方向的非负矩阵分解识别率相近; 最后,AR人脸数据库上的识别率显然高于Yale人脸数据库上的识别率。
图 1 3 种算法识别率比较
4. 2 训练时间和检测时间比较
从训练时间和检测时间两个方面对2DLDANMF、 ( 2D)2LNMF和 ( 2D)2RNMF算法进行比较。训练时 间即获得左右投影变换矩阵和投影特征矩阵所需的时间,测试时间即对未知数据的投影特征矩阵和已知数据的投影特征矩阵进行对比,判断其属于哪一类所需的时间。在实验中,使用10次训练时间的平均时间来作为训练时间,10次检测时间的平均时间作为检测时间。实验结果如图2和图3所示。
图 2 3 种算法训练时间比较
如图2所示,在Yale和AR人脸数据库中,2DLDANMF算法训练时间大幅小于( 2D)2LNMF和 ( 2D )2RNMF算法训练时间。且 随着d的增大,( 2D)2LNMF和 ( 2D)2RNMF两种算法的训练时间随之增加,而且增加较快,但2DLDANMF算法训练时间保持在较低范围内,增加不明显。这主要是由于2DLDA方法的融入, 使得计算右投影矩阵时,矩阵维数低,d的增加只是线性复杂度的增加,几乎不耗费额外时间。
如图3所示,2DLDANMF算法检测时间远小于 ( 2D)2LNMF和( 2D)2RNMF算法检测时间,且随着d的增大,3种算法的检测时间随之增加。
5 结束语
本文提出了一种快速的非负矩阵分解算法。实验结果表明: 当d相同时,2DLDANMF算法在节省了大量训练时间和检测时间的同时,取得了高于二维非负矩阵分解算法的识别率。但是必须认识到,对于压缩率的选择,没有提出理论性的可行方法,只是经验性选择,这需要进一步探讨。
图 3 3 种算法检测时间比较
摘要：用于人脸识别的非负矩阵分解算法,虽可提高图像识别率,但因其是通过迭代方法同时计算出基矩阵和系数矩阵,故当迭代次数较多时,计算过程耗时长。文中将二维线性判别分析方法与非负矩阵分解方法融合,提出了一种快速的双边二维非负矩阵分解算法。通过在AR、Yale人脸数据库上的实验结果显示,较二维双边非负矩阵分解算法,文中算法不仅使得训练时间大幅减少,而且识别率也有所提高。
矩阵分解 篇5
多光谱遥感系统分波段记录地物波谱反射、辐射特征的微弱差别, 具有丰富的光谱信息, 但一般空间分辨率较低, 而且易受到云雨雾的影响。合成孔径雷达 (synthetic aperture radar, SAR) 是一种先进的主动式微波遥感器, 能够提供高分辨率的目标图像, 具有全天候、全天时的优势, 并且雷达对地物又有一定的穿透力, 这恰恰是对光学遥感的有益补充。基于这些特点, 如何对多光谱遥感影像与SAR影像进行融合处理, 得到更丰富、更有用的信息将会是遥感影像处理领域中非常有意义的一项课题[1]。遥感影像处理算法存在不下百种[2], 例如HIS变换融合法[3]、PCA变换融合法[4]等, 但大多数算法都是基于全色影像和多光谱影像而提出的, 也有学者对SAR和光学影像融合进行了研究, 例如张红蕾等提出的运用相关性加权[5,6]方法对配准影像做融合, 这个方法对权值的选择非常敏感。曹银璇等人运用PCA[7,8]变换、HIS变换以及乘法复合变换对SAR影像与多光谱遥感影像进行融合, 这些方法可以增加融合图像的纹理信息, 但是存在比较严重的光谱失真。还有一些算法是在HIS变换的基础上通过不同的方式构造新的I分量来改进算法, 如伍娟等在HIS变换后[9], 对SAR图像进行直方图匹配;邓磊等将HIS与PCA结合[10], 采用PCA变换来构造I分量。本文提出的基于非负矩阵分解以及整数小波变换的融合算法, 既对影像融合结果的空间分辨率有较大提升, 同时对影像的光谱信息也有较好的保持, 与其他算法比较有更好的融合效果。
1NMF算法原理与融合过程
1.1 NMF算法原理
非负矩阵分解算法[11,12]的基本原理是对于任意给定的一个非负矩阵V, NMF算法都能够找到一个非负矩阵W和一个非负矩阵H, 且满足:
一般, 选取的r值要小于n和m, 而且r满足条件 (n+m) r<nm。非负矩阵分解将一个非负的矩阵分解为两个非负矩阵的乘积。算法的关键步骤是目标函数的设定和迭代规则的选择。实验中, 采用的目标函数和迭代规则如下:
目标函数:最小化‖V-WH‖2, 对于任意W, H, 当W, H≥0;
迭代规则:
1.2 融合过程
基于非负矩阵分解[13,14]的融合算法步骤为:
(1) 输入原始数据矩阵V。多光谱图像M, 包含3个波段, 将这3个波段图像作为输入矩阵V的3个列向量。
(2) 用NMF分解计算得到基准图像矩阵W和权重矩阵H。
(3) 依方差值, 将基准图像矩阵W的3个特征基向量按降序排序, 此时可获取基准图像矩阵W中方差最大的特征基向量K, 该向量集中了原始数据矩阵V中大量的能量与信息。
(4) 对SAR影像F和基准影像矩阵W的最大特征基向量K进行直方图匹配, 使两者的均值方差尽量相似。
(5) 将直方图匹配后的SAR影像F′替换基准影像矩阵W中的最大特征基向量K, 再进行逆变换V′=WH, 将基准图像矩阵W还原到源图像的像素级上, 此时, 可得清晰且细节丰富的融合结果图像G。
2试验结果图与性能比较
为说明算法的有效性, 本文采用珠三角地区经过配准的雷达数据和多光谱遥感影像数据进行试验, 分别为2008年珠三角地区的TerraSAR影像, 分辨率为1 m和2006年的珠三角地区的Spot5多光谱遥感影像, 分辨率为10 m。同时本文选取了PCA与NMF融合结果进行对比研究, 以说明本融合算法的优越性, 如图1所示。
2.1 基于目视判读的比较与分析
从目视角度来看, 几种融合方法在空间分辨率上都有比较明显的提高。主成分分析算法存在一定的光谱失真, 而本文提出的NMF算法在光谱保持程度上有明显的优势, 其光谱颜色与原始的多光谱遥感影像基本上一致。
2.2 基于数理统计的分析与评价
为了进一步客观评价融合结果, 选择了几种较常见的评价指标, 比如标准差、梯度、相关系数以及等效视数。结果如表1所示, 从表1的统计数据中可以得出:
(1) 本文提出的融合算法与原始多光谱遥感影像相比较, 原始多光谱图的梯度值为1.9, 梯度值有明显的提高;从等效视数来看, 本文算法的融合结果图在梯度值上达到5.3, 这说明融合结果在图像的清晰度和图像的解译能力上有明显的提高。
(2) 与PCA相比较, 本文提出的算法与原始多光谱影像的相关系数值达到0.87, 而其他算法的相关系数值只能达到0.698 8。从这个值说明本算法在光谱保持上具有较明显的优势, 同时本文的融合结果在等效视数和梯度方面也有一定的提高。
3结语
本文将非负矩阵分解算法用于SAR图像与多光谱遥感影像之间的融合。实验表明, 融合结果与原始光谱影像相比, 影像的清晰程度得到了很大提高, 具有较好的目视效果, 同时对图像的解译能力也有了较大的提高。
摘要：合成孔径雷达具有全天候、全天时的优势, 能够提供高分辨的目标图像, 而多光谱遥感影像能够提供丰富的光谱信息, 将两种不同影像进行融合, 综合两者的优势信息可以得到质量更高、信息更丰富的图像。提出了基于非负矩阵分解算法的融合算法对SAR影像和多光谱遥感影像进行融合。通过对比研究, 提出的融合算法在目视判读以及客观评价指标上和传统融合算法相比, 都有较明显的改善, 尤其是在细节表现力和光谱保持度方面优势显著。