论文部分内容阅读
随着互联网的快速发展,数据的规模越来越庞大,数据的相关性也变得越来越复杂,譬如:越来越高分辨率的监控视频、图像,错综复杂的关系网络等.因此对大数据的处理变得重要而迫切.矩阵的低秩逼近是一种大规模数据矩阵低秩近似表示技术,从而可实现矩阵的降维.非负矩阵分解(Nonnegative Matrix Factorization,NMF)是矩阵的低秩逼近方法之一,它将一个给定的非负矩阵分解成两个低秩的非负矩阵的乘积,从而可得到所给非负矩阵的低秩逼近.这样的分解得到的非负数据可解释性强,在实际应用领域有较好的物理意义.自从NMF算法的思想被提出后,很多NMF算法被提出并被应用于实际应用领域.在前人研究的基础上,本文主要研究了几种新的NMF算法并将之应用于图像处理和复杂网络社区发现领域,其中图像数据的处理解决图像重构、图像共性特征提取等问题,而对复杂社区网络数据着重解决重叠社区发现的问题.论文结构如下:绪论部分先介绍了 NMF的研究背景和意义,然后根据NMF算法分类,按时间先后顺序详细阐述了 NMF的国内外研究现状、发展趋势和存在的问题及不足,最后对本文的主要工作和组织结构作了概括说明.第1章主要介绍了NMF的相关知识和几种经典的NMF算法.第2章针对NMF中的牛顿型算法存在当前点的Hessian矩阵若不可逆则进行不下去的缺点,本章提出了一个具有通用意义的牛顿型NMF算法(NBA算法),它采用在牛顿方向进行不下去时用梯度方向使目标函数值下降的策略,从而很好地解决上述问题.最后,将NBA算法用于三个公共的图像数据集,实验结果表明该算法适用于所有的非负矩阵,且在速度和效果上比同时期的其它算法更优.第3章针对NBA算法中计算Hessian矩阵的逆要消耗的运算量比较大,为了减少运算量且兼顾收敛速度,本章提出两个秩一校正的NMF(1DNMF)算法,即修正的秩一残差迭代算法(MRRI算法)和按元素残差迭代算法(ERI算法).为了避免传统1DNMF中容易丢失一些隐藏在原始图像中的结构信息的问题,我们将二维NMF(2DNMF)算法与MRRI算法和ERI算法分别结合,得到MRRI-2DNMF和ERI-2DNMF 算法.将 MRRI、ERI、MRRI-2DNMF、ERI-2DNMF算法与已有的一些算法分别在三个公共的图像数据集和一个实际应用的图像数据集上进行有效性验证,实验结果表明在同等条件下,MRRI和ERI算法有更小的相对误差、绝对误差、欧氏距离及更好的图像重构质量.在相近的压缩率下,MRRI-2DNMF和ERI-2DNMF算法比各自相应的1DNMF算法有更好的图像重构质量和更少的运行时间.第4章针对重叠社区中的重要节点(重叠节点、中心节点、离群节点)及其固有的重叠社区结构的发现问题,将逼近误差项与非对称惩罚项的和作为目标函数,基于梯度更新的原则及非负约束条件推导出一种新的对称非负矩阵分解(Symmetric nonnegative matrix factorization,SNMF)算法(SNMFP 算法).将 SNMFP 算法用于五个公共网络数据集,实验结果显示SNMFP算法能较好地将实际网络的重要节点及其固有的社区结构发现出来.从社区发现结果的平均导电率和算法的执行时间来评价,基于SNMFP算法的社区发现方法优于非负矩阵分解社区发现方法(CDNMF方法);从准确率和召回率的调和平均值的加权平均值来评价,基于SNMFP算法的社区发现方法比较适合较大数据集的重叠社区发现.第5章从提高SNMF算法稳定性的角度,推导了一个SNMF的乘子交替方向算法(AULAG算法),并对其作了收敛性分析,证明了该算法具有一阶稳定性.本章还对重叠社区发现方法—CDNMF方法作了改进.将AULAG算法与改进的重叠社区发现方法结合后的方法记为AUCDSNMF方法.将AUCDSNMF在五个公共网络数据集上做了实验.大量的实验结果表明AUCDSNMF方法所得结果稳定,能将重叠社区发现的固有结构发现出来,且在多个通用指标上都有较好的表现第6章对论文的整体工作作了归纳总结并对今后的研究方向作了展望.