非负矩阵分解及其在非均衡数据分类中的应用

1、、硕士学位论文非负矩阵分解及其在非均衡数据分类中的应用作者姓名范笑宇 导师姓名、职称 姬红兵教授一级学科信息与通信工程二级学科信号与信息处理申请学位类别工学硕士提交学位论文日期 2014年12月西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人己经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说 明并

2、表示了谢意。学位论文若有不实之处，本人承担一切法律责任。本人签名：他亲号 日 期：K山-以牛西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。学校有权 保留送交论文的复印件，允许查阅、借阅论文；学校可以公布论文的全部或部分 内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，获得学位 后结合学位论文研充成果撰写的文章，署名单位为西安电子科技大学。保密的学位论文在年解密后适用本授权书。本人签名，他父导师签名:日 期：u心.s 期:铲/每mResearch on Non-

3、negative MatrixFactorization and its Application toUnbalanced Data ClassificationA thesis submitted toXIDIAN UNIVERSITYin partial fulfillment of the requirementsfor the degree of Masterin Information and Communication EngineeringByFan XiaoyuSupervisor: Prof. Ji HongbingDecember 2014摘要摘要非负矩阵分解(NMF)是一

4、种处理大规模高维数据的矩阵分解方法，它以非负约 束和局部表示等独特的优势吸引了众多研究者的关注，并被广泛地应用于数据挖 掘、计算机视觉和模式识别等领域。此外，实际的分类问题中存在很多非均衡数 据，包括密度不均衡、类别不均衡和常见的样本数目不均衡等情况。基于此，本 文重点研究了基于数据结构信息的非负矩阵分解算法和面向非均衡数据分类的非 负矩阵分解算法。首先，概述了非负矩阵分解及非均衡数据分类的基础理论。给出了NMF基本 算法、数学求解方法，以及经典的衍生算法；并总结了数目不均衡数据的分类难 点及常用的抽样处理方法。其次，针对基于图信息的非负矩阵分解仅用欧式距离来衡量样本邻域结构的 局限性，将邻域

5、样本相似度引入非负矩阵分解，提出一种基于邻域样本相似度的 非负矩阵分解算法(NSS-NMF)。该方法通过引入邻域协方差矩阵来计算邻域样本 相似度，对于邻域结构相似的样本点，其分解所得的系数矩阵的约束项被赋予较 高的权值，以适应于样本密度不均衡的情况；进一步，引入邻域类标相似度，并 考虑基向量的正交性，提出一种基于邻域相似度的非负矩阵分解算法(NS-NMF)o 该方法在考虑邻域样本相似度的基础上，根据邻域样本的已知类标信息构建邻域 类标分布矩阵，这样组合得到的邻域相似度有效地兼顾到数据类别分布不均衡的 情况。实验结果表明，上述基于数据结构信息的非负矩阵分解算法可以获得比传 统方法更好的聚类分类性

6、能。最后，针对常见的非均衡数据问题(即样本数目不均衡)，提出一种新的加权 非负矩阵分解算法(WNMF)。该方法通过计算每类样本数在总样本数中的比例，求 其倒数作为训练样本的权值引入非负矩阵分解，因此在保持了多数类分类准确性 的同时，有效地提升了少数类样本的分类性能。此外，结合NS-NMF算法考虑了 邻域结构信息的优点，提出一种基于非负矩阵分解的混合重采样算法(HS-NMF)o 该方法先通过NS-NMF将数据集映射到更加可分的子空间，再通过经典的过采样、 欠采样技术改善数据的不均衡程度。实验结果表明，将非负矩阵分解应用于非均 衡数据分类中，可获得比传统重采样方法更高的分类准确率。关键词：非负矩阵

7、分解，非均衡数据分类，邻域相似度，重采样 论文类型：应用基础研究类ABSTRACTABSTRACTNon-negative Matrix Factorization(NMF) is a kind of matrix factorization method for dealing with large-scale and high-dimension data. With the unique advantages of non-negative constraints and local expression, NMF catches many researchers5 eyes, and

8、has been widely used in data mining, computer vision and pattern recognition, etc. In addition, many practical classification problems involve unbalanced data, which is of uneven density, unbalanced category or common seen unqueal number of samples. Therefore, this thesis mainly studies the Nonnegat

9、ive Matrix Factorization based on data structure information and its application to unbalanced data classification.Fiistly, the basic theories of Nonnegative Matrix Factorization and unbalanced data classification are introduced, with emphasis on conventional NMF algorithms, their mathematics models

10、 and some classic derivative algorithms. Then the difficulties of unbalanced data classification and the common sampling methods are summaiized.Secondly, aiming at the limitation of Graph Regularized Non-negative Matrix Factorization, which only measures the samples neighborhood structure with Eucli

11、dean distance, we introduce the metric of Neighborhood Sample Similarity and propose a Non-negative Matrix Factorization algorithm based on Neighborhood Sample Similarity (NSS-NMF). This method uses the neighborhood covariance matrix to compute Neighborhood Sample Similarity, and assigns higher weig

12、hts to the constraints of the coefficient matrix of the decomposited sample points whose neighborhood structure are more similar, so as to adapt to the uneven sample density. Further, by introducing Neighborhood Label Similarity and taking the orthogonality of the basis vectors into account, we prop

13、ose a Non-negative Matrix Factorization algorithm based on Neighborhood Similarity (NS-NMF). Inheriting Neighborhood Sample Similarity, NS-NMF constructs the neighborhood class distribution matrix according to the prior label information of the neighborhood samples. This combined neighborhood simila

14、iity effectively takes into consideration the unbalanced data density and label distribution simultaneously. The experiments vertify that the proposed algorithms outperform traditional methods in terms of clustering and classification performance.Lastly, in view of the common situation of unbalanced

15、 data, i.e., the number of samples is not balanced, we put forward a new Weighted Non-negative Matrix Factorization algorithm (WNMF). It calculates the proportion of the number of samples which belong to the same category to the total number of samples, and takes its inverse to weight the NMF. Conse

16、quently WNMF not only keeps the classification accuracy of the majority class samples but also effectively improves the classification performance for the minority class samples. In addition, combined the advantages of NS-NMF algorithm which respects neighborhood structure information, a Hybrid re-S

17、ampIing algorithm based on the Non-negative Matrix Factorization(HS-NMF) is put forward. It first maps the data into a more separable subspace thiough NS-NMF, then uses the classic over-sampling and under-sampling schemes to alleviate the degree of data imbalance. The experimental results show that

18、the application of NMF related methods to the unbalanced data can lead to better classification performance than traditional pure re-sampling methods.Keywords: Non-negative Matrix Factorization, unbalanced data classification, NeighborhoodSimilarity, re-samplingType of Dissertation: Applied Basic Re

19、search插图索引插图索引 TOC o 1-5 h z 图1.1 NMF模型及算法分类示意图3图2.1 NMF, VQ, PCA分别实现人脸的部分基表示囱10图2.2 SMOTE算法合成少数类样本点示意图18图2.3 SMOTE算法效果图18图2.4分界线不明显的SMOTE算法效果图19图2.5 Tomek links清理数据示意图19图3.1密度不均衡的数据分布示意图22图3.2 ORL数据库的图像样本25图3.3 ORL数据库各算法性能比较26图3.4 YALE数据库的图像样本27图3.5 YALE数据库各算法性能比较27图3.6数据1中1-6类样本信号模糊函数切片特征28图3.7雷达辐

20、射源数据库各算法性能比较29图3.8样本点邻域类标分布模拟示意图30图3.9 ORL数据库各算法性能比较33图3.10 Yale数据库各算法性能比较34图3.11雷达辐射源数据库各算法性能比较35图4.1 UMIST数据库的图像样本42 HYPERLINK l bookmark159 o Current Document 图4.2 NMF降维混合重采样算法框图44表格索引表格索引 TOC o 1-5 h z 表3.1 ORL数据聚类准确率(%)26表3.2 ORL数据归一化互信息(%)26表3.3 Yale数据聚类准确率(%)27表3.4 Yale数据归一化互信息(%)27表3.5雷达辐射源数

21、据聚类准确率(%)28表3.6雷达辐射源数据归一化互信息(%)28表3.7 ORL数据聚类准确率(%)33表3.8 ORL数据归一化互信息(%)33表3.9 Yale数据聚类准确率(%)34表3.10 Yale数据归一化互信息(%)34表3.11雷达辐射源数据聚类准确率(%)35表3.12雷达辐射源数据归一化互信息(%)35表4.1二分类数据集混淆矩阵40表4.2 Breast Cancer原始数据集SMOTE算法性能指标(%)41表4.3 Breast Cancer数据集各降维算法性能指标(%)41表4.4 UMIST数据库SMOTE算法性能指标(%)42表4.5 UMIST数据库各降维算法

22、性能指标(%)42表4.6 Breast Cancer原始数据集各抽样算法性能指标(%)45表4.7 Breast Cancer数据集各降维算法性能指标(%)45表4.8 UMIST数据库各抽样算法性能指标(%)45表4.9 USIMT数据库各降维算法性能指标(%)45符号对照表符号MNX符号名称向量维数样本个数M维随机向量XUV“201M维随机向量的N个观察值构成的矩阵，样本集 基矩阵系数矩阵（特征矩阵）MxL维非负实矩阵空间 降维所选特征维数D(XIIUV)IIMWu*V*UT相似度度量矩阵的Frobenius范数目标函数梯度基矩阵最优解系数矩阵（特征矩阵）最优解矩阵间的Hadamard积

23、U的转置矩阵a0Rir2tr(.)LNMF算法中基向量约束项的参数LNMF算法中系数矩阵约束项的参数GNMF基于SED的约束项GNMF基于GKLD的约束项矩阵的迹mkrand(0,l)w(咛，勺)CiC商叱w(w)N2SMOTE算法过取样倍数近邻点个数区间（0,1）内的一个随机数样本点X., Xj基于欧氏距离的相似性估计样本点气的近邻点协方差矩阵Ci样本点习的近邻点协方差矩阵Ci的简化：G的对角元素 邻域样本相似度最近邻个数参数包含邻域结构信息的约束项调节参数bnssWK) 叫%)YL邻域样本相似度调节参数邻域类标相似度邻域相似度基向量正交项调节参数 拉普拉斯矩阵甲成，代b”/sQ拉格朗日乘子

24、邻域类标相似度调节参数对角权值矩阵缩略语对照表缩略语英文全称中文对照PCAPi incipal Component Analysis主成分分析LDALinear Discriminant Analysis线性判别分析VQVector Quantization矢量量化NMFNonnegative Matrix Factorization非负矩阵分解BNMFBasic Nonnegative Matrix Factorization基本非负矩阵分解CNMFConstrained Nonnegative Matrix Factorization约束非负矩阵分解SNMFStructure Nonneg

25、ative Matrix Factorization结构化非负矩阵分解GNMFGraph Regularized Nonnegative MatrixFactorization for Data Representation图正则非负矩阵分解SPNMFSparsed Nonnegative Matrix Factorization稀疏非负矩阵分解ONMFOrthogonal Nonnegative Matrix Factorization正交非负矩阵分解DNMFDiscriminant Nonnegative Matrix Factorization判别非负矩阵分解MNMFNonnegativ

26、e Matrix Factorization on manifold复合非负矩阵分解CVNMFConvolutive Nonnegative Matrix Factorization卷积非负矩阵分解NMTFNonnegative Matrix Tri-factorization三系数非负矩阵分解NTFNonnegative Tensor Factorization非负张量分解NMSFNonnegative Matrix-Set Factorization非负矩阵集分解KNMFKernel Nonnegative Matrix Factorization核非负矩阵分解AAAIthe Associ

27、ation for the Advancement of美国人工智能发展协Ailificial Intelligence会ICMLthe International Conference on MachineLearning workshop机器学习国际会议ACMthe Association for Computing美国计算机协会NCRNeighborhood Cleaning Rule邻域清理技术CNNEdited Neaiest Neighbor Rule编辑最近邻规则SMOTESynthetic Minority Over-sampling Technique合成少数类过取样SEDS

28、quai e of Euclidian Distance平方欧式距离GKLDGeneralized Kullback-Leibler Divergence广义KL散度KKTKarush-Kuhn-Tucker求解矩阵最优性条件LNMFLocal Non-negative Matrix Factorization局部非负矩阵分解NSSNeighborhood Sample Similaiity邻域样本相似度NLSNeighborhood Label Similaiity邻域类标相似度NSNeighborhood Similaiity邻域相似度ACAccuracy聚类准确率NMINormalize

29、d Mutual Information归一化互信息KNNk-Nearest Neighbor algorithmK最近邻算法WNMFWeighted Nonnegative Matrix Factorization加权非负矩阵分解HS-NMFHybrid Sampling based on NMFNMF降维混合取样算 法目录目录摘要 TOC o 1-5 h z HYPERLINK l bookmark25 o Current Document ABSTRACTIll HYPERLINK l bookmark28 o Current Document 插图索引V HYPERLINK l boo

30、kmark31 o Current Document 表格索引VII符号对照表IX HYPERLINK l bookmark34 o Current Document 缩略语对照表XI HYPERLINK l bookmark37 o Current Document 目录XIII HYPERLINK l bookmark40 o Current Document 第一章绪论1 HYPERLINK l bookmark43 o Current Document 1.1课题研究背景及意义1 HYPERLINK l bookmark46 o Current Document 1.2国内外研究现状2

31、 HYPERLINK l bookmark49 o Current Document 1.2.1非负矩阵分解研究进展2 HYPERLINK l bookmark52 o Current Document 1.2.2非均衡数据分类研究进展4 HYPERLINK l bookmark55 o Current Document 1.3论文内容及章节安排6 HYPERLINK l bookmark58 o Current Document 第二章 非负矩阵分解及非均衡数据分类概述9 HYPERLINK l bookmark61 o Current Document 2.1引言9 HYPERLINK l

32、 bookmark64 o Current Document 2.2非负矩阵分解概述9 HYPERLINK l bookmark67 o Current Document 221非负矩阵分解基本算法9 HYPERLINK l bookmark70 o Current Document 2.2.2非负矩阵分解的数学求解10 HYPERLINK l bookmark82 o Current Document 2.2.3非负矩阵分解衍生算法12 HYPERLINK l bookmark93 o Current Document 2.3非均衡数据分类概述16 HYPERLINK l bookmark9

33、6 o Current Document 2.3.1非均衡数据分类难点16 HYPERLINK l bookmark99 o Current Document 2.3.2非均衡数据分类常用方法17 HYPERLINK l bookmark102 o Current Document 2.4本章小结20 HYPERLINK l bookmark105 o Current Document 第三章基于数据结构信息的非负矩阵分解21 HYPERLINK l bookmark108 o Current Document 3.1引言21 HYPERLINK l bookmark111 o Current

34、 Document 3.2基于邻域样本相似度的非负矩阵分解算法21 HYPERLINK l bookmark114 o Current Document 3.2.1邻域样本相似度(NSS)22 HYPERLINK l bookmark117 o Current Document 3.2.2基于邻域样本相似度的NMF算法(NSS-NMF)23 HYPERLINK l bookmark120 o Current Document 3.2.3实验结果与分析24 HYPERLINK l bookmark126 o Current Document 3.3基于邻域相似度的非负矩阵分解算法29 HYPER

35、LINK l bookmark129 o Current Document 3.3.1邻域类标相似度(NLS)29 HYPERLINK l bookmark132 o Current Document 3.3.2基于邻域相似度的NMF算法(NS-NMF)30 HYPERLINK l bookmark135 o Current Document 3.3.3实验结果与分析32 HYPERLINK l bookmark138 o Current Document 3.4本章小结36 HYPERLINK l bookmark144 o Current Document 第四章面向非均衡数据分类的非负矩

36、阵分解37 HYPERLINK l bookmark147 o Current Document 4.1引言37 HYPERLINK l bookmark150 o Current Document 4.2加权非负矩阵分解算法37 HYPERLINK l bookmark153 o Current Document 4.2.1加权非负矩阵分解算法(WNMF)37 HYPERLINK l bookmark156 o Current Document 4.2.2实验结果与分析394.3 NMF混合重采样算法43 HYPERLINK l bookmark162 o Current Document

37、4.3.1 NMF混合重采样算法(HS-NMF)43 HYPERLINK l bookmark165 o Current Document 4.3.2实验结果与分析44 HYPERLINK l bookmark168 o Current Document 4.4本章小结46 HYPERLINK l bookmark171 o Current Document 第五章总结与展望47 HYPERLINK l bookmark174 o Current Document 5.1全文总结47 HYPERLINK l bookmark180 o Current Document 5.2未来展望48 HY

38、PERLINK l bookmark186 o Current Document 参考文献49 HYPERLINK l bookmark268 o Current Document 致谢55 HYPERLINK l bookmark271 o Current Document 作者简介57第一章绪论1.1课题研究背景及意义一个深深根植于科学和工程学研究者心目中的基本信念，是在明显的混乱和 复杂中，一定有一些简单、紧凑和典雅的东西扮演着最基本的角色。在信号处理、 数据分析、数据挖掘、模式识别和机器学习中也是这样。近年来科学技术的飞速 发展使得原始数据的数量增多和可用性增强以爆炸的速度发生。随着传

39、感器和计 算机技术的发展，我们拥有了越来越多可用的原始数据，如何从如此海量的数据 中提取出有用的信息成为人们非常关注的焦点。人工智能领域中的机器学习是研 究如何将机器智能化的技术，而机器智能化的方式就是深入分析数据改善系统自 身性能，因此机器学习成为数据分析领域的一项主要技术。数据降维是机器学习的一个重要研究领域。通过适当的降维技术来获取一种 有效的表示方式，在多元数据分析中已经成为一个重要的、必要的和具有挑战性 的问题。降维一般来说应该满足两个基本性质：第一，原始数据的尺寸应该减小； 第二，主成分、隐藏的概念、突出的特性或潜在的变量的数据，根据应用程序上 下文，应该有效地识别。在许多情况下，

40、原始数据集或观察数据会被构成数据矩 阵或张量，会被描述为线性或多重线性组合模型，所以，从代数的角度来看，降 维可以被看做：将原始数据矩阵分解为两个因子矩阵。规范化方法，如主成分分 析(Principal Component Analysis, PCA),线性判 别分析(Linear Discriminant Analysis, LDA),独立分量分析(Independent Component Analysis, ICA),矢量量化(Vector Quantization, VQ)等等都是一些低秩近似的范本。这些方法的统计特性各不相同， 是因为它们对因子矩阵及其底层结构有不同的约束条件，它们也

41、有一些共性：对 因子矩阵中的元素没有任何约束。换句话说，在这些方法中，允许出现负数因子 矩阵和减法运算。相比之下，一个新的分解方法-非负矩阵分解(Nonnegative MatrixFactorization, NMF),它包含非负约束，具有局部表示特性，同时加强了相 应问题的可解释性。这种方法及模型最早由Paatero和Tapper提出，在Lee和 Seung4之后引起了广泛的关注。非负矩阵分解有两个互补的优点非负约束和加性结合。一方面，在现实世界的许多种数据，如图像、光谱和基因数据的分析任务中，不管是表面还是潜 在的结构，负值都是缺乏物理意义的。而原型通常都与特定的语义解释相对应。 例如在

42、人脸识别中，基图像通常是局部的而非整体的，类似人脸的一部分，如眼 睛、鼻子、嘴巴或脸颊。另一方面，人们最感兴趣的地方自然是构成物体的局部 特点，加性结合意味着这些感兴趣的局部可以组装在一起拼凑出整体。于是NMF 在真实环境的场景和任务中取得了极大的成功。如在文本聚类中，不管是在提高 精度还是在潜在语义识别上，NMF已经超越了谱聚类等经典的方法叫目前，NMF 已经成功地应用于人脸识别血、文本挖掘聚类1215社区发现、基因数据分析 回等问题中。从另外一个角度来说，分类技术是机器学习的核心技术之一。分类就是将样 本划分到相应的类别，从数学角度来说，分类就是确定对象属于哪一个预定义的 目标类。近年来，

43、随着分类问题的研究不断深入，人们发现现实生活中存在很多 数据类别不均衡的情况，如医疗诊断1引、信用卡欺诈检测成2。、网络入侵检测21 等领域中存在典型的非均衡数据集。可以看出在这些问题中，不常出现的少数类 样本往往显得更为重要。对于传统分类器来说，它们的首要目标都是减小其分类 错误，即最大化它的整体精度，且大多基于数据平衡分布的假设。但这并不适用 于非平衡数据集，由于非均衡数据集中少数类的误判损失往往更大，传统分类方 法应用于非平衡数据时，少数类的分类性能明显下降。因此，寻求有效的方法来 提高非平衡数据中少数类的分类性能显得急迫而有意义。非均衡数据集通常具有两个特点：一是数据类别数目差异大；二

44、是误分类代 价不同。两个主要特点决定了它与之前基于均衡数据的分类问题是完全不同的， 现有的分类算法不能或者不能直接应用其上。但均衡数据分类问题的解决和研究 成果对非均衡数据分类问题的解决仍然具有巨大的推动作用，最直接的使用方法 是将非均衡数据进行预处理，使之均衡化而后再用之前算法训练分类器，即可得 到很好的分类效果。十几年来，非均衡数据分类问题的步步深入，愈发激起研究 人员的研究热情，吸引了越来越多优秀人才的关注，在此过程中，国内外的学者 们提出了一个又一个性能卓越的分类算法。1.2国内外研究现状1.2.1非负矩阵分解研究进展由于在确保非负性和稀疏性的情况下增强了数据的可解释性，NMF已经成为

45、 多元数据分析的一种必要的工具，被广泛应用于数学、优化、神经计算、模式识 别和机器学习22】、数据挖掘I】、信号处理I、形象工程和计算机视觉VI、光谱数 据分析2习、生物信息学SI、化学计量学VI、地球物理学28】、财经29。更具体地说， 这些应用程序包括文本数据挖掘a】、数字水印、图像去噪DI】、图像恢复、图像分 割DI、图像融合、图像分类I、图像检索、人脸识别I、面部表情识别SI、音频 模式分离3们、音乐流派分类Ml、语音识别等。自从问题被提出以来已经产生了大量关于NMF的成果，研究者来自不同领域: 数学家、统计学家、计算机科学家、生物学家和神经学家等，都从不同角度探索 T NMF的相关问

46、题。总的来说，NMF理论是现今已经获得巨大的进步但仍在进 展中的一项工作。具体来说：第一，NMF自身的性质已获得很深入的探索，而严 格的统计支撑，像那些传统的分解方法PCA或LDA 一样，并没有完全地发展， 从某种程度上说这也是它的难题；第二，像文献国中提到的如加性约束的一些问 题已经被解决，而很多其他问题还有待解决。总结过去十几年，NMF算法的各种修改、扩展和推广已经形成了一个很全面 的系统，本文做出归纳总结见图1.1。总的来说，现有的NMF算法可以被划分为 四类，它们都遵循统一的标准。第一，基本NMF(BNMF),即NMF的原始模型， 它只规定了非负约束；第二，约束NMF(CNMF),它增

47、加了诸如正则化之类的加性 约束项；第三，结构化NMF(SNMF),它修改了标准分解公式；第四，广义 NMF(GNMF),它广义地突破了传统的数据类型和分解模式，使模型等级变得更加 宽泛。图1.1 NMF模型及算法分类示意图具体来说，首先，基本NMF为其它所有NMF模型建立了一个基础的分析框 架。基本NMF的研究主要集中在优化工具和计算方法方面以及大规模数据处理和 在线处理。约束NMF分为四个子类：第一，稀疏NMF(SPNMF)增加了稀疏约束； 第二，正交NMF(ONMF)增加了正交约束；第三,判别NMF(DNMF)增加了判别 约束；第四，复合NMF(MNMF)，保留了局部拓扑性质。事实证明这些

48、形态约束 在本质上也是必要的，从后面的理论和实验分析都可以看出来。结构化NMF分为 三个子类：第一，加权NMF(WNMF),依据它们的相对重要性对不同的元素添加 不同的权值；第二，卷积NMF(CVNMF),考虑了时频域分解；第三，三系数 NMF(NMTF),顾名思义，将数据矩阵分解为三个因子矩阵。此外，广义NMF也 可以分为四个子类：第一，半监督NMF(Semi-NMF),非负约束仅仅限制特定的因 子矩阵；第二，非负张量分解(NTF),将矩阵数据的维数拓展到更高维的张量；第 三，非负矩阵集分解(NMSF),将数据集从矩阵拓展到矩阵集；第四，热核 NMF(KNMF),创建了 NMF的非线性模型。

49、从以上总结分类来看，我们可以从另一个角度来归纳现今NMF算法的研究, 主要集中在这几方面：第一，约束条件的选择，诸如正交性、稀疏性、光滑性或 使用数据的先验知识等；第二，算法求解方法，很多学者分别使用了乘法更新法、 投影梯度法、最小二乘法、秩1残差法等方法，来求解不同模型下的NMF问题； 第三，数据形式，如CP张量、TUCKER张量等；第四，应用研究，前文已多次 归纳出应用方向，这里不再赘述。1.2.2非均衡数据分类研究进展在现实领域中，非均衡学习问题代表有着广泛应用的具有高度重要性的循环 问题，需要持续不断的开拓发展。这种需求和增长的关注度也反映在最近几个专 业研讨会或会议的特殊问题研讨会上

50、，包括美国人工智能发展协会关于非均衡数 据集的学习研讨会(AAAr00)t39,机器学习国际会议关于非均衡数据集的学习研讨 会(ICMmB),美国计算机协会关于知识发现和数据挖掘的特殊兴趣小组(ACM SIGKDD Explorations04)叫等。非均衡数据分类的根本问题是数据的非均衡性会严重降低大多数标准学习算 法的性能。大多数标准算法假设或预计的是平衡的类分布或平等的误分类代价。 因此，当面对复杂的非均衡数据集，这些算法无法正确地表示数据的分布特点， 最终会产生混淆不同类别的不好的结果。数据的不均衡分布主要有两方面的体现: 一方面表现为样本密度不均衡，另一方面为样本数目、类别不均衡。现

51、有的研究 方法主要集中在后者，即考虑样本数目差异大的情况。由于多类数据的分类可以 转化为二分类，因此现有的非均衡数据研究方法主要针对二分类问题。二分类非 均衡数据集，即为一个数据集中某一类的样本数远大于另一类的样本数，其中样 本数多的类一般称为多数类(负类)，样本数少的类称为少数类(正类)。非均衡数据 集分类问题的研究重点也就集中在如何提高少数类的分类性能上。目前，对于样本数目非均衡的数据分类研究主要集中在数据层、算法层和两 种层面结合起来的综合方法。在数据层面，主要是通过采样，重构数据集，改变 数据的不平衡分布，使不平衡性降低；在算法层面，主要是提出新的分类思想， 通过引入不同的权重值，诸如

52、代价敏感学习、集成学习等方法改进传统分类算法； 综合层面，则是将二者结合起来提高分类准确率。下面进行详尽的归纳总结。首先，数据层面抽样技术的使用。通常，在非均衡学习应用中采取包括某些 机械措施的抽样方法都是为了提供一个平衡的分布情况。研究表明，对于一些基 本的分类器，一个均衡的数据集能比不均衡的数据集更容易提高它的总体分类性 能4244。文献中的结果都证实了抽样方法对非均衡学习的必要性。最简单的抽样技术是随机过采样和欠采样。顾名思义，随机欠采样就是随机 去掉多数类样本集中的一些样本，随机过采样是随机复制少数类样本集中的样本 并添加到原数据集中，以此方式来降低数据集的不平衡性。但是，随机欠采样去

53、 样本时容易丢失掉多数类中的有用信息，随机过采样容易造成分类器的过度拟合。 因此产生了合成采样戏46、自适应合成采样印、基于数据清洗技术的采样48、采 样和迭代结合等方法，都是在前二者之上的衍生。其中，合成少数类过取样算 法(SMOTE),对少数类样本进行扩充，根据一定的规则随机制造生成新的少数类 样本，并将这些新合成的少数类样本合并到原来的数据集，产生新的训练集。这 种方法已成为该领域的一个标准算法。其次，在算法层面上。虽然抽样技术的应用确实有助于提高分类精度，但这 并不意味着分类器不能直接学习非均衡数据。相反地，研究表明由特定的非均衡 数据集诱导的分类器可以比得上由同样的经过抽样的均衡数据

54、集诱导的分类器 t5051o算法层面是指针对现有的分类算法，对不同类别的样本设置不同的权值、 改变概率密度、调整分类边界等措施解决。常用的改进算法包括：支持向量机、 聚类、神经网络、决策树等。支持向量机(Support Vector Machine, SVM)以统计学习理论为基础，采用结构 风险最小化准则设计学习机器，较好地解决了非线性、高维数、局部极小点等问 题。一些学者对支持向量机进行适当改进以更好地处理不平衡数据分类。比如， 将分类边界向多数类进行适当的偏移，以使更多的少数类样本不会被误判；或者 对正类和负类赋予不同的代价，作为支持向量机的惩罚因子。杨扬和李善平皿将 不平衡数据按照“最重

55、要”、“较重要”和“不重要”三个层次重新组织，提出了 基于实例重要性的支持向量机IISVM； Batuwita和Palade53提出了模糊支持向量 机；Hwangt54提出了一种基于拉格朗日支持向量机的加权方法来解决不平衡分类 问题。但由于支持向量机在学习过程中的被动性，不能有效地选择学习样本，使 得当支持向量机用于训练规模较大的分类时，支持向量较多，其训练速度和分类 速度较慢。另一个最常用的算法是代价敏感学习。它通过为小类设置更高的误分类代价 来解决类别非均衡问题，即将各类不同的错分代价用到分类决策中，尽可能降低 误分类的总体代价而不是尽可能降低误分类的错误率。改变现有分类算法使其变 得代价

56、敏感是非常困难的工作，有时效果并不明显。通常的方法是不改变原有的 算法，通过增加一个过程使原来的分类算法变得代价敏感。常用方法有如下几种： （1）调整样本分布。根据错误分类的代价按一定比例变换训练集中类别的频率，其 缺点是改变了样本的分布情况，有时会影响算法的性能。（2）元代价方法。通过“元 学习”过程，根据最小期望代价修改训练样本的类标记，并用修改过的训练集重 新学习新的模型。（3）代价敏感决策。首先在训练集中多次抽样，生成多个模型， 再根据模型，得到测试样本属于每个类别的概率，然后计算测试样本的所有错误 分类代价，并根据最小代价得到类标记。周志华等探讨了类别非均衡性对代价敏感学习的影响【5

57、5-56,对通用代价敏感 学习方法的共性机理进行了分析，指出其解决多类问题失效的原因，并提出了一 种多类代价敏感学习方法Rescalenew,该方法能有效地进行多类代价敏感学习。 Xia等人列基于数据空间扩张技术，将代价敏感学习问题转化为一个标准的0/1损 失分类问题，并提出了一个新的加权机制。Masnadi-Shirazi等人御提出了代价敏 感提升算法。由于支持向量机的良好分类性能，许多学者对基于支持向量机的代 价敏感学习问题也展开了研究工作。最后，在综合层面上。单一的研究方法对非均衡数据分类性能的提升有限， 因此许多学者致力于结合不同的方法来解决类别非均衡问题，如集成学习。集成 学习是将多

58、个分类器组合来解决同一个分类问题以提升性能。其中，基于代价敏 感Boosting的集成方法尤为常见，它们的通用策略是增加高代价样本的权重。 SMOTEBoost方法是一种基于上采样的提升方法，它将SMOTE和Boosting相 结合。该方法不是通过更新每类样本的权值来改变训练数据的分布，而是通过使 用SMOTE算法添加新的少数类样本。但该方法由于增加了过多的样本，使得训练 时间增大，同时可能导致过学习现象。1.3论文内容及章节安排本文首先从非负矩阵分解基本问题入手，对现有的NMF算法进行了总结和比 较，介绍了不同的目标函数构造方式、求解方法、约束条件和衍生算法。同时， 由于本文主要关注的是保持

59、数据结构信息的NMF算法，所以重点研究了样本密度 分布不均匀、邻域类标分布不均匀的情况，更加深入地挖掘样本数据的结构信息， 提出了改进算法。此外，考虑到在某种程度上样本密度不均衡是非均衡数据的一 种形式，因此先研究了现有的非均衡数据分类方法，然后提出了面向数目不均衡 数据的非负矩阵分解算法。根据上述研究内容，本文章节安排如下：第一章绪论，阐述了非负矩阵分解和非均衡数据分类的研究背景和现实意义, 总结归纳了它们的国内外研究进展和现状，最后给出论文的主要内容和章节安排。第二章研究了非负矩阵分解及非均衡数据分类的基础理论。首先给出了 NMF 基本算法及其数学模型、求解方法，建立了 NMF问题的基本框

60、架。然后介绍了经 典的NMF衍生算法，重点分析了各种算法的加性约束项。此外，总结了现有的数 目不均衡数据的分类难点，并重点介绍了常用的抽样处理方法。第三章研究了基于数据结构信息的非负矩阵分解算法。针对基于图信息的非 负矩阵分解仅用欧式距离来衡量样本邻域结构的局限性，首先将邻域样本相似度 引入NMF,提出一种基于邻域样本相似度的非负矩阵分解算法；其次进一步挖掘 邻域信息，引入邻域类标相似度，并且考虑了基向量的正交性，提出一种基于邻 域相似度的非负矩阵分解算法。并在标准数据库和雷达辐射源数据库上验证了两 种算法的有效性。第四章研究了面向非均衡数据分类的非负矩阵分解算法。首先针对常见的非 均衡数据问