数据维数约简及分类算法研究

1、分类号 密 级ij DC单位代码 10154_辽宁工业大学硕士学位论文数据维数约简及分类算法研究专 业:通信与信息系统研究生：周勇指导教师：蔡希彪副教授二。一六年三月独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中，不包含 其他人已经发表或撰写过的研究成果，也不包含为获得辽宁工业大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所作的任 何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名:关于论文使用授权的说明本人完全了解辽宁工业大学有关保留、使用学位论文的规定，即：学校有 权

2、保留送交的复印权，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。（保密的论文在解密后应遵守此规定）Master ThesisData Dimensionality Reduction and ClassificationAlgorithmsSpeciality: Communication and Information SystemsCandidate: ZHOU YongSupervisor: Associate Professor CAI Xi-biaoLiaoning University of TechnologyJinzhou,

3、 121001, ChinaMarch 2016摘要随着信息技术的发展，涌现出海量数据，推动了机器学习理论不断地向前发展。样 本数据维数越高，数据存储越困难，同时数据的计算量也越大；此外，数据中还存在着 噪声或者冗余特征。因此，如何降低高维数据的维数，避免“维数灾难”问题，提高数 据的分类精度，已经成为机器学习领域关注的一个热点问题。非负矩阵分解作为一种矩阵分解算法，约束待分解矩阵中和因式分解获得的矩阵中 所有的元素为非负。这种非负性约束具有明确的物理意义，使得非负矩阵分解作为一种 维数约简算法得到了广泛关注。同时，半监督学习(semi-supervised learning)由于能够 同时利

4、用少量的已知标记样本和大量未标记样本数据进行有效的学习，大大克服了有监 督学习算法中样本数量不足问题，提高了分类的精度，因而半监督学习方法在图像分类、 文本分类及邮件分类等问题中得到了普遍的运用。论文集成基于非负矩阵分解的维数约简算法和基于半监督学习的分类算法，首先提 出了一种基于非负矩阵分解与一致性学习的半监督学习算法。然后，在非负矩阵分解过 程中引入类别信息，提出了一种基于约束非负矩阵分解与一致性学习的半监督分类算 法。该算法在降维过程中引入少量巳知标签类别信息作为约束条件，增强数据降维后的 特征表示能力。最后，引入类别之间的依赖性，提出了一种基于构建类别图的维数约减 的半监督学习算法。该

5、算法分别在样本与样本之间、类与类之间创建图，构建基于图的 正则化框架，再通过求解Sylvester方程得到未标记样本的标签。在公开数据集上的实验 结果表明，论文算法在充分利用少量已知标签的同时用于数据的维数约简，不仅能有效 地降低了数据的维度，还能够有效地提高分类器的泛化能力。关键词：机器学习；维数灾难；维数约简；半监督学习；Sylvester方程AbstractWith the development of information technology, huge amounts of data have constantly sprung up, which pushes forward

6、the theory of machine learning. The higher dimension of example data causes the more difficulty of data storage, the larger calculation of data, and in addition, the more occurance of the characteristics of noise or redundancy in the example data. Therefore, how to reduce the dimensionality of high-

7、dimensional data, avoid the curse of dimensionaIity, problem and improve the classification accuracy of data has become a hot issue in the field of machine learning.Non-negative matrix factorization (NMF) is a matrix decomposition algorithm. The algorithm constraints all elements to be nonnegative i

8、n the matrixs, which include the ones underdecomposed and obtained by factorization. The non-negative constraint of NMF has explicit physical significance and makes it widely concerned as a dimension reduction algorithm. At the same time, semi-supervised learning can combine limited labeled examples

9、 data and plenty of unlabeled ones for effectively learning, which overcomes the shortage of labeled examples in supervised learning algorithm and thus improves the accuracy of the classification. Therefore, it is widely used in image classification, text classification and e-mail classification.Fir

10、stly, in view of NMF and semi-supervised learning, the thesis proposes a semi-supervised learning algorithm based on non-negative matrix factorization and consistency of learning. Secondly, a novel semi-supervised learning approach based on constrained nonnegative matrix factorization and learning w

11、ith consistency is proposed by introducing class information in the process of non-negative matrix factorization, which introducing limited labeled examples classification information as constraints in the process of dimensionality reduction, enhanced data dimensionality reduction feature representa

12、tion capability. Finally, it be introduced the dependencies between classes, and it is proposed about semi-supervised learning algorithm based on the class graph of dimensionality reduction. The algorithm respectively between the examples and examples and between classes and classes create graphs to

13、 construct a graph regularize! based on frame, and then it is obtained unlabel samples of labels by solving the Sylvester equation. Experimental results on public data datasets show that the proposed algorithm are both make use of limited labeled examples data and about datasets dimension reduction,

14、 and not only can effectively reduce the dimension of the data, but also can improve the classifier generalization ability.Key words: machine learning; the curse of dimensionality; dimensionality reduction; semi-supervised learning; Sylvester equation目录 TOC o 1-5 h z HYPERLINK l bookmark14 o Current

15、 Document 摘要IAbstractII HYPERLINK l bookmark20 o Current Document 1绪论1 HYPERLINK l bookmark23 o Current Document 1.1研究背景与意义1 HYPERLINK l bookmark26 o Current Document 1.2国内夕卜研究现状31.2.1维数约简研究现状31.2.2数据分类研究现状6 HYPERLINK l bookmark36 o Current Document 1.3论文的主要工作和结构安排81.3.1论文的主要工作81.3.2论文的组织结构8 HYPERLI

16、NK l bookmark44 o Current Document 2维数约简与半监督学习概况10 HYPERLINK l bookmark47 o Current Document 2.1维数约简10 HYPERLINK l bookmark64 o Current Document 2.2半监督学习的基本知识162.2.1半监督学习基本思想及其未标记数据的作用162.2.2半监督学习假设17 HYPERLINK l bookmark69 o Current Document 2.3基于图的半监督学习182.3.1基于图的半监督学习框架182.3.2基于图的半监督分类算法192.3.3基于

17、图的半监督学习算法20 HYPERLINK l bookmark81 o Current Document 2.4本章小结22 HYPERLINK l bookmark84 o Current Document 3基于非负矩阵分解和一致性学习的半监督分类算法23 HYPERLINK l bookmark87 o Current Document 3.1非负矩阵分解233.1.1非负矩阵分解原理233.1.2非负矩阵分解算法收敛性证明25 HYPERLINK l bookmark90 o Current Document 3.2基于NMF和一致，性学习半监督分类算法27 HYPERLINK l

18、bookmark104 o Current Document 3.3实验结果与分析293.3.1 评价指标293.3.2数据集与参数选择293.3.3分类结果及分析30 HYPERLINK l bookmark107 o Current Document 3.4本章小结32 HYPERLINK l bookmark116 o Current Document 4基于约束非负矩阵分解和一致性学习的半监督分类算法33 HYPERLINK l bookmark119 o Current Document 4.1约束非负矩阵分解334.1.1约束非负矩阵分解原理334.1.2约束非负矩阵分解算法收敛性

19、证明35 HYPERLINK l bookmark125 o Current Document 4.2基于CNMF和一致性学习的半监督分类算法38 HYPERLINK l bookmark140 o Current Document 4.3实验结果与分析414.3.1数据集与参数选择414.3.2分类结果及分析42 HYPERLINK l bookmark143 o Current Document 4.5本章小结44 HYPERLINK l bookmark146 o Current Document 5基于构建类别图的维数约简半监督学习45 HYPERLINK l bookmark149

20、o Current Document 5.1基于类别图的结构框架45 HYPERLINK l bookmark160 o Current Document 5.2基于构建类别图的维数约简半监督学习48 HYPERLINK l bookmark167 o Current Document 5.3实验结果及分析495.3.1评价指标4953.2 数据集与参数选择495.3.3分类结果及分析49 HYPERLINK l bookmark170 o Current Document 5.4本章小结50 HYPERLINK l bookmark173 o Current Document 6总结与展望5

21、1 HYPERLINK l bookmark176 o Current Document 6.1总结51 HYPERLINK l bookmark182 o Current Document 6.2展望51 HYPERLINK l bookmark188 o Current Document 参考文献53 HYPERLINK l bookmark194 o Current Document 攻读硕士期间发表学术论文情况56 HYPERLINK l bookmark197 o Current Document 致谢571绪论在丰富多彩的复杂世界中，人们正在以超乎想象的能力，不断的改变着我们的世界

22、。 如今，各行各业都积累了大量的数据，数据作为信息交流、传送的主要载体，填充着整 个空间，换句话说，我们的生活被大量的数据所笼罩着。一般情况下，这些数据具有高 维性和复杂性等特点，使其较难发现其隐藏的本质特性。所以，从汪洋复杂的高维数据 中获得符合现实运用所需的有用信息显得迫为重要。“维数约简”简单来说就是数据的降维，将数据中的冗余信息删除，充分提取出人 们所关心的数据信息。从某种意义来说，维数约简是“机器学习” 1的一个重要的研究 范畴，它也属于“人工智能”的探究的重点领域。在本节中，针对维数约简问题所面临的挑战性，主要从数据处理和实际运用两个方 面来进行阐述；其次，在高维数据处理的层次上介

23、绍半监督学习的重要性；最后，介绍 维数约简、数据分类的那个研究现状及与其它研究课题的关系。1.1研究背景与意义伴随着科学信息技术水平的不断提高，人们对数据的存储与采集能力的快速提升， 使得获取数据变得越来越容易，而数据处理的能力却没有得到较好地改善。在科学研究 的诸多领域中，如人脸识别、生物信息学、信息检索、遥感图像处理等都积累了大量的 数据。就普遍而言，这些数据具有“高维性”和“海量性”等特点，而且数据构造变得 越来越复杂。如果直接对高维数据进行处理时会带“维数灾难”(Curse of Dimensionality) 问题；而且，如果样本数小于数据的特征维数时，会导致模型估计的性能恶化，出现

24、 所谓的小样本问题。因此，如何挖掘出高维海量的数据中背后蕴藏的符合实际需求有用 知识，探索高维数据中隐藏的数据结构和内在分布规律将成为模式识别囹、机器学习、 数据挖掘习、计算机视觉等6诸多研究领域的极大挑战。计算机网络对于检测问题的入侵和蛋白质关系的调控问题是高维数中的两个典型 实例。就实际运用而言，这些数据需要大量的存储空间，数据特征万千复杂，并且维度 极其的高。就这样的情景下，如果直接对数据进行的分析，较难达到预想的分类效果。 一方面，“虽然我们被信息淹没，但是我们缺乏知识”。人们比较关注的是在万千复杂的 高维数据中存在的某种内在分布规律和数据中所涵盖关于描述事物的特征本质问题。因 此，对

25、数据的预先处理给我们提出更高的要求，去除高维数据中的不相关信息和冗余信 息，从而进一步提取高维数据中所描述事物的特征本质信息。另外，在计算机图像处理中，通常将图像进行按每一行(列)逐一拉伸成为一个向 量处理，且用图像灰度值来表示图像特征，最终用这些特征向量表示这些图像7。不管 对其采用统计学方法进行统计推断，还是估计其所对应的空间组成，都会使得计算变得非常复杂与此同时也会对存储造成极大的困难和挑战。如图1.1所示和图1.2所示。(a)初始图像(b)三维俯视图图1.1初始灰度图像及三维坐标表示Fig. 1.1 Original gray image and its three-(dimensio

26、nal coordinate representation图1.2三维表示灰度图侧视图Fig. 1.2 Three-dimensional representation side view在图1.1中图(a)为初始灰度图像，图(b)为原始图像将转换成三维坐标系下的 表示图，其中，Z轴表示图像的灰度值。图(b)是三维的俯视图，图中每行(列)表 示一个维度，每点代表其一个灰度值。在图1.2所示为视角为侧面的灰度图表示。由以 下图可以看出，计算机要处理的图像维数是非常高，如果预先对数据不进行处理，会对 计算机存储和计算带来严重的挑战圆。维数约简作为机器学习的重要课题，是处理高维数据的强有力的方式，它

27、的实际意 义是将原维数较高的数据映射到较低维的子空间中，获得能够尽可能描述原数据特征的 低维表示更加紧凑而有意义，从而寻找隐藏在高维数据中的本征低维结构9。从几何的 角度来讲，维数约简可以解释为高维数据投影到低维流形结构空间表示。这样的低维度 投影不仅保持原数据的内在隐藏结构分布，而且保证了观测原始空间相互靠拢的节点映 射到较低维度的空间表示也相互靠近。通过维数约简方法可以有效的去除数据中隐藏的 冗余信息和不相关的信息从而有效的保留数据中的有用信息，为进一步的数据处理和分 析，如降噪、分类、插值和可视化等奠定良好的应用基础。随着互联网技术的推进，涌现海量数据，致使机器学习有了迅速的发展。与传统

28、的 监督学习方法相比，机器学习要获得更好的学习性能需要进行大量训练和学习，而且一 般需要充足的标签数据样本。然而，在实际运用中，由于数据信息具有多样性的特点， 使得获取大量标记样本数据变得相对比较困难，还可能需要耗费大量的人力、物力，且 需要很有经验、专业知识领域强的专家学者通过大量的工作和努力进行人工标注，使得 付出的代价过于“昂贵”。对于没有利用少量宝贵的已标记样本的传统无监督学习方法, 将会造成对“昂贵”数据的浪费，而且在一定程度上对算法的性能的提高也是一种限制。 与此同时，伴随着科技技术的高速发展，获取大量未标记数据已经变得不是难事。试图 仅仅通过使用没有标记的数据来进行机器学习具有一

29、定的盲目性，使得结果在一定程度 上很难保证较高的学习性能；不光如此，对于少量的已标记样本数据来说是一种对数据 资源的损失及浪费。因此，如何有效的结合已知标记数据和未知标记数据来挖掘数据所 隐含的数据信息进行机器学习是十分有意义的。如今，半监督学习问题受到越来越多的研究者的关注和青睐，己发展成为机器学习 中的热门研究领域。半监督学习(semi-s叩ervised learning) 3】能够在减少人工标注类别 信息为代价及增强学习性能的同时充分利用少量的已知标记样本数据和大量的未标记 样本数据进行有效的学习，弥补了传统机器学习的不足。半监督学习方法的这种优越性 已经在数字图像处理、文本分类、医学

30、数据处理和邮件分类等领域得到了普遍的运用。 在实际运用中，机器学习难以发现模型的真实变量，原因是高维数据中隐藏着大量的冗 余信息，因此，在半监督学习前对高维数据进行有效的降维预处理过程显得十分有必要 的。1.2国内外研究现状1.2.1维数约简研究现状科技技术地发展，使得高维数据遍布应用于各类场景中，如：文本分类、Web多媒 体以及文本数据挖掘等研究领域。这些高维数据带来日常生活“维数福音”的与此同时 也对数据的处理带来严峻的挑战和代价。维数约简作为机器智能领域处理高维数据的一 种主要方式，己被广泛应用于解决信息处理等实际应用，有效的对高维数据进行维数约 简，是提高数据分类处理、机器学习性能以及

31、解决类似问题显得十分重要的。以往的高维数据处理是将原始的高维数据通过相应的转换或者映射到低维数据空 间表示，按照其转换或映射函数f(x)的不同可将其分为线性方法和非线性方法。线性降维方法最为经典和常用的方法有主成分分析(Piincipal Component Analysis,PC A) Un 和 Fisher 线性判别(Linear Discriminant Analysis, LDA),其方法也是应用 最为广泛的降维方法BL PCA利用初始数据和重构后的数据之间的差的绝对值最小为 目的，通过向量空间的线性组合重建原始数据空间，已被普遍应用到机器学习、模式识 别等多个研究领域，并取得较好的效

32、果。但是一种无监督的降维方法不适用于反映样本 之间的差异。相对于PCA方法而言，LDA方法利用了类别信息，其降维方法是一种有 监督的方法，它以聚内散度最小化、聚间散度最大化为目的，最终能够将各类数据有效 的分开，在分类问题上比PCA更有效。但由于原始高维数据样本的维度远远大于样本 个数，则LDA会存在“奇异值”问题。为了有效地解决此类问题，研究者经过共同的 努力提出了较多且合理的解决方案，如：正则线性判别分析(Regulaiized LDA, RLDA)、 PCA+LDA法和零空间法LDA等。另外，通过LDA得到的投影向量更倾向于被混淆在 原始数据特征空间中较为相近的标签类别信息之中。因此，为

33、了处理此类问题，Ta。等 人14从几何均值的角度出发最优化相异类之间的K-L散度(Kullback-Leibler divergences),提出了几何均值散度分析(Geometric Mean Divergence Analysis, GMDA)。 经过人们长期的努力出现了许多的线性降维方法，如：独立成分分析、局部保持投影、 稀疏保持判别分析等，在此就不作逐一的介绍。线性降维方法是基于统计分布规律假设，且具有相对严谨的理论依据；简单实现、 易于执行和分析，且能保持高维数据样本在线性子空间上的几何真实结构、计算复杂度 低等优点，因而得以被各个领域广泛地运用。但在现实生活中数据并非是线性的，且数

34、 据通常情况下分布规律为非线性，以致于对处理复杂的非线性高维数据时现有的线性降 维方法得不到很好的运用，而且也无法揭示高维数据的内在结构。因此，对非线性降维 方法的研究显得十分的迫切。近年来，在研究者的共同努力下非线性降维技术取得了长足进展，主要通过以下几 个方面来实现：核技巧。将原始空间数据利用核函数转换到一个空间，这空间是高维且线性 的空间，然后，在此特征空间上通过线性方法对其进行降维，最后，获得所需的低维空 间表示。该技巧是对现有的线性降维方法的改进与补充，该方式巳经成熟的运用于机器 学习和模式识别等相关领域中成。最为典型的算法包括Schdlkopf等16提出了核主分量 分析(Kerne

35、l Principal Component Analysis, KPCA)与核线性判别分析(Kernel LDA, KLDA)O还有核邻域保持嵌入(Kernel NPE)、核半监督判别分析(Kernel SDA)、核稀 疏保持判别分析(Kernel SPDA)以及核局部保持投影(Kernel LPP, KLPP)等叫都属 于此类方法。实际上，核技巧或核方法是实现非线性和线性转换的有效桥梁，是模式识 别崭新研究阶段的重要标记。但核化方法过度依赖于某些隐藏变换，不能直解地理解为 降维的概念I%而且如何选择核参数至今没有相对统一及可依据的理论印证。流形学习方法(Manifold Learning)1

36、9o流形学习方法的最初是在2000年science 上所发表的文章中所提出的算法：等距映射(Isometrical Mapping, ISOMAP)和局部线 性嵌入(Locally Linear Embedding, LLE)方法吸引了研究者的眼球，通过流形学习方 法实现非线性维数约简是处理高维数据问题的一个从前所未有的新视角，而且避免了局 部极小的优化问题所带来的困扰，该方法利用了嵌入在高维空间中低维流形上的数据集 隐藏的流形内在结构。典型的流形学习算法除了 ISOMAP和LLE外，还有拉普拉斯特 征映射(Laplacian Eigenmaps, LE)和 Local Tangent Spa

37、ce Alignment (LTSA)等。虽 然在某些人造数据集上流形学习方法呈现出显著的性能，但研究表明，在实实在在的数 据集上流形学习无法获得比传统PCA更好的学习效果。另外，流形学习会带来“外样 本(out-of-sample)”问题啊，而解决此问题需要求助于特殊的处理技巧刖。为了解决 解决此类问题且提高流形学习在实际数据上的性能，2003年He等心提出了局部保持投 影算法，此方法宗旨是保留了数据的局部拓扑构造，其本质是LE的线性化版本。经过 学者们的艰苦努力提出了一系列旨在保持数据局部结构的算法，如：近邻保持嵌入NPE(Neighborhood Preserving Embedding

38、)、局部线性嵌入特征分析、等距投影等。其他方法。局部混合线性的方法，该方法从局部表示整体，通过局部线性组 合表示来重新构造全局数据的思绪为出发点。然而，怎样通过局部线性模型来得到转换 的低维空间中的基向量线性组合来表示整体的低维坐标系；其次，通过利用EM(Expectation Maximization)网算法对数据进行处理，则会使得其结果陷入局部极小值 得缺点；而且算法效率不高，对参数极其敏感。所以，此类算法的实用性较差，对其使 用较少。从方法上来讲，维数约简除了依据变换函数的形式分为线性和非线性外，还可根据 其准则的不同进行分类：按照已知少量类别标签是否被充分考虑可划分为无监督维数约简学习

39、方法2、 半监督维数约简学习方法和有监督维数约简学习方法26。无监督降维方法就是在降维过程中没有利用数据集的标号信息只利用数据自身进 行学习训练；也就是说，其只关心未标记样本的分布情况而不需人为的添加样本，进而 得到一个分类器，用来估计出样本的标签；其主要提取的是数据的结构信息。典型的无 监督降维方法有 k-聚类(k-means)、主成分分析(Principal Component Analysis, PCA) 以及其他一些流形学习算法等，比如等距映射、局部线性嵌入(Locally Linear Embedding, LLE)等。无监督方法没有使用已知的标记数据和大量未标记数据，对其数据资源是

40、一 种浪费；而且对实验结果的精确度不能保证，分类结果在很大程度上具有一定的盲目性 和不依赖性。有监督降维方法不仅利用数据自身的特征而且利用了数据已知少量的类别信息，其 主要是对数据样本判别信息的提取。其目标是在标签数据中建立一个从样本到标签的映 射。通过标签信息来反映对应数据集的特征关系，进而得到一个有效的分类器，用来分 类测试样本。也可以建立标签样本集到实值(不一定是标签)的映射，此称之为回归(regression) t27k有监督监降维方法包括线性判别分析(Linear Discriminent Analysis, LDA)、支持向量机(Support Vector Machine, SV

41、M)、局部保持判别投影(Locality Preserving Discriminant Projections, LPDP)等。半监督学习降维方法不仅能利用数据自身而且充分考虑了已知对应的少量的类标信 息以确保获得的低维空间表示有良好的判别性，又能利用大量无类别标签数据来充分挖 掘数据的内在结构以达到在低维空间中保持原始高维数据潜在结构的目的。半监学习督 降维方法巳成为如今的研究焦点，其方法包括半监督线性判别分析(Semi-supervised LDA, SSLDA) 口刃，SSDR (Semi-supervised Dimensionality Reduction)等。根据处理数据自身的特

42、点可分为：单视图学习、多视图学习DU。单视图学习：数据从某个单一的视角观测得到的，传统的降维方法大多数都是在 单视图的假设下进行处理的。多视图学习：数据具有显著的不仅仅只有一个视图的特性，而且可以划分为彼此 不相关的几个单一视图。最后，总结维数约简方法分类如图1.3所示。图1.3维数约简方法分类图Fig. 1.3 Dimensionality reduction methods for classification1.2.2数据分类研究现状在“信息爆炸”的今天，海量数据的获取和使用变得越来越容易，与此同时，高维1绪论 辽宁工业大学硕士学位论文 数据的存储和处理也就成了一个一直困扰我们的难题。数

43、据的搜集和分类信息成为人类 每天的必备工作，而随着数据急剧扩张，手工分类已经远远不能满足我们的需求。因此， 如何快速准确的自动识别数据，选择合适的方法对数据进行分类显得十分的重要。分类 问题是机器学习中的基本问题，而图像分类是分类问题中的一个子问题，已成为许多研 究领域的热门话题。数据分类相关过程如图1.4所示。图1.4数据分类过程基本结构Fig. 1.4 The basic framework of data classification process数据分类的过程主要有：分类器的训练过程和数据的分类过程SI。分类器训练过程 主要是根据训练样本集中数据样本的本质特征结构和相关的巳知标签信息

44、进行训练学 习得到有效的分类器模型；而数据分类过程是利用的获得的分类器模型对待分类的数据 进行预测并根据相关的决策函数输出预测结果。而分类的目标就是通过少量已标记样本 进行训练学习出一个性能较佳的分类器，再利用训练学习好的分类器对添加的样本进行 标签信息的预测。在给定X =X“X2,X,的样本集合和类别信息集合 卜=少见，肩，分类就是根据样本相应的已知类别信息V得到适合样本X的每一个 样本类别信息的过程。在传统的分类学习问题一般是单标签分类，也就是说单一样本只能允许对应有一个 唯一标签，诸如此类的分类问题在以往的两类或多类的分类问题中较为最多。而在真实 应用中，单标签己经不能完整的描述数据样本

45、的信息，因此，对多标签分类学习的研究 具有相当重要的理论与应用价值，而且多标签分类问题已经成为了如今研究的焦点问 题。多标签分类就是单一对象往往会对应于多重类别信息的情况。多标签分类算法主要 包含两种类型：问题转换和算法适应。问题转换方法是将学习目标变换成一个或多个相 互独立的单个标记分类问题，此类方法没有特定的算法约束；算法适应类型是将己有的 学习分类算法经过改善为多重标签学习问题，从而使得算法能够对多标签数据的问题进行处理。当前，针对多标签学习问题上，研究者提出了许多经典学习算法，其中应用比较广 泛且最为基础的学习分类算法有：Boosting算法33、支持向量机(Support Vecto

46、r Machines, SVM)啊、K 近邻(K Nearest Neighbor, KNN)和朴素贝叶斯模型(Naive Bayes)四等。但依然存在许多问题有待于进一步解决。1.3论文的主要工作和结构安排13.1论文的主要工作论文主要将维数约简理论、半监督学习、数据分类等理论结合并应用到了高维数据 分类中，进行了相关的研究，主要完成了以下工作：首先从实际运用出发阐述维数约简的重要求，并介绍维数约简的相关研究现 状。研究了维数约简的相关理论知识并介绍了维数约简的经典算法的比较；然后， 介绍半监督学习的理论概述和相应的算法。首先介绍非负矩阵分解算法的相关知识，并对其算法推导、迭代规则、收敛 性

47、证明作相关方面的阐述，并提出一种基于非负矩阵分解与一致性学习的半监督分类算 法，对其算法进行实验验证及分析。研究了类别约束(半监督)的非负矩阵分解算法得相关理论知识，对其迭代 规则、收敛性进行证明。并提出一种基于约束非负矩阵分解与一致性学习的半监督分类 算法，对其算法进行实验验证及分析。结合类别之间的依赖关系，对其基于约束非负矩阵分解与一致性学习的半监 督分类算法进行改进，通过实验验证算法的可行性和有效性。13.2论文的组织结构全文的章节安排及具体内容如下：第一章，绪论。说明了维数约简的重要性及分析了课题的研究背景及研究意义，以 此同时结合相关的机器学习领域阐述了维数约简的相关研究现状。第二章

48、，维数约简与半监督学习概况。介绍了维数约简与半监督学习的相关理论知 识和常见的算法分析，并给出相关图的半监督结构框架。第三章，基于非负矩阵分解与一致性学习的半监督分类算法。为了在分类中减少数 据中的冗余信息、提高分类准确率，提出了一种基于非负矩阵分解与一致性学习的半监 督分类算法。第四章，基于约束非负矩阵分解与一致性学习的半监督分类算法。为了它充分挖掘 了已知的少量样本的标签信息。标签信息不仅作为约束条件用于数据的维数约简，同时 也作为工具用于衡量图上样本标签的光滑性。提出了基于约束非负矩阵分解与一致性学 习的半监督分类算法。第五章，基于构建类别图的维数约简半监督学习算法。在以往的半监督学习中

49、往往 只对样本之间构建图，而未考虑类与类之间的相关性。所以，在训练样本和类别标签上 分别构建邻近图，对基于约束非负矩阵分解与一致性学习的半监督分类算法进行改进， 提出基于构建类别图的维数约简半监督学习算法。第六章，总结和展望。对本文进行总结，并对未来的研究进行了下一步的展望。2维数约简与半监督学习概况在信息化时代，维数约简是高维数据处理的有效手段，其在数据有效降低维度的同 时减少数据中的噪声和冗余信息；是人工智能的研究核心之一，在科学研究领域中承担 着十分重要的作用。而半监督学习充分利用了少量的已知标记标签和大量的未标注标签 进行机器学习问题，提高了数据的分类效果。本章将具体介绍维数约简相关理

50、论及常见 的维数约简算法；详细阐述半监督学习相关知识和经典半监督学习算法。2.1维数约简在实际运用中，高维数据的广泛分布致使对数据维度约简已变得颇为需要。维数约 简是指将样本从原始输入空间通过某种变换或映射获得原数据集有效子空间的低维表 示。维数约简作为高维数据处理的一种有效方式，其对数据降维希望不损失数据的关键 特征信息，且同时保留原始数据的潜在的内在结构。维数约简作为数据处理的预处理过 程，能够有效的提高后续机器学习的性能和有效的提高分类效果。然而，也会造成一定 的信息损失。维数约简方法在用于降维的同时不仅有效的减少数据中冗余信息、噪声信 息及不相关的信息，而且能够有效的解决高维数据所带来

51、的维数灾难性问题大大减低数 据处理的计算复杂度。在很多的实际情况下，将高维数据的维数的降到一个适当的范围， 而且在能尽可能的不破坏初始数据的结构分布，进而有利于对数据的处理。因此，维数 约简的一般处理过程描述如图2.1所示。图2.1维数约简的基本过程Fig. 2.1 The basic process of dimensionality reduction维数约简在实际运用带来诸多的益处，首先，维数约简能够有效的减低数据维数， 降低了计算复杂度，提高了计算速度；其次，维数约简能够发现数据的内在隐藏结构和 内部的分布规律，达到可视化的目的；最后，维数约简能去除数据间的冗余信息。经过学者共同的实践

52、努力，已有许多维数约简方法得到了改善和完善，因此，下面 简单介绍几种应用较为广泛的降维方法。首先介绍两个典型的线性方法：(1)主成分分析(Principal Component Analysis, PCA)主成分分析由1933年被Hotellin于提出的，也被称之为Hotelling变换，其主要思 想是以低维子空间来表示原始高维数据，将高维数据从原来的D维降到d维(Dd),提取主要特征(主元)、减少数据冗余；利用协方差矩阵的相关变量对数据进行有效的 压缩、提取，是一种无监督最经典的维数约简方法。其目标是寻找若干个彼此正交且能 够保持数据尽可能分开的投影方向，通过线性变换函数f3)转成另一组不相

53、关的变量。 如图2.1所示。Fig. 2.2 PC A method Geometric InterpretationPCA的目标函数为:NuPCA = arg max 一 yi=N=arg maxp心N=arg max Z 尸 xip ；=i IT tnX|2a心VI(2.1)=arg max 叭S,P)其中，,=*,且为总体离散矩阵：= 卜一尤)(改-x) o对 转换矩阵作尺度约束PTP = Id ,其中L为dxd的单位矩阵。因此，PCA求解优化问题 如下：aigmaxrr(PrSfP) s.t.PTP = Id(2.2)利用拉格朗日乘子法，构造拉格朗日函数为：”(prp)_n(4(尹P_

54、/)(2.3)其中，人为实对称矩阵，可以对角化为叶=UAIJT , U为正交矩阵，A为对角矩阵。对F 求偏导数并令其结果置零可得：SfP-PA = O= SrP = PUAUt = StPU =PUA(2.4)最终，问题转化为求解前d个最大特征值对应的特征向量ppp?,P,所求特征 向量的集合就为变换矩阵P = P|，P2，P。所以，PCA降维的过程可以表示为：Xi-yi=PTxiOPCA算法的具体步骤如下：输入：原数据样本集知易,，叫如。，N为样本的个数，。为原始特征维数 过程：建立相关矩阵(计算协方差矩阵)，根据K-L变换矩阵的特征值和特征向量。选取主分量。D建立优化方程，求解主分量。第，

55、个主成分分量表示为其中j=i 七U = l,2,)为对应于特征值*得特征向量的分量，.为各个分量的标准化数值。 得到所需要的主分量值，即为新样本集。输出：新的样本集3,力，一，为)如厂d为输出的特征维数。可以看出主成分分析通过对原始样本集进行变换后，根据信息量大小对数据特征进 行排序，保留数据信息靠前的特征，去除较小的特征信息，从而减少对数据表示所需的 特征维数以及减少算法运算的复杂度，同时尽可能的减低数据恢复或从新线性组合时的 误差。此算法不仅能提高算法的分类精度，而且能有效的去除数据中的不相关信息从而 改善数据的质量。另外，PCA没有利用到数据的类别信息，对分类结果具有盲目性和不 确定性，

56、因此从分类的角度考虑其不是最佳的投影选择。(2)线性鉴别分析(Linear Discriminant Analysis, LDA)Fisher最早在1936年提出LDA算法印】，伴随鉴别矢量对两类或多类计算方法的提 出，LDA得以普遍的应用于许多场景。LDA充分考虑了类别间的依赖性，将原始数据 投影到维度较低的特征子空间中，从而使类别不同的数据距离尽量大，同类样本尽量集 中。在这种情况下，LDA能提高分类器的分类精度。给定数据样本集(冲q),1 = 1,2,其中x G Rd为训练样本，C.的标签信息，k为类别个数。LDA的目的是寻找一个适合的投影矩阵PeRE(dvD), 使得在低维空间中样本的

57、总类间距与样本的总类内距的比值最大。所以，定义类内散度 矩阵S”和类间散度矩阵岛如下：(2.6)kSb=Nr=其中，x=y 七为第，类样本的均值，为全部样本的均值，记， N 心 jni/.=栅1勺=尸, N,.=gd(%.)为.的势，即/.中元素的个数，以此,=N,=N。在此，给出PCA和LDA算法之间的简单对比图，如图2.3所示。图2.3 PCA和LDA的比较Fig. 2.3 The comparison of PCA and LDA通常情况下，LDA的目标函数优化有两种：比值迹准则啊和迹比值准则39。比值迹准则如下： TOC o 1-5 h z max打(尸以寸尸厂尹&P)(2.7)住将上

58、述目标函数关于F求导并将其置零，令A = PSbP、B = PTSwP ,最终可得：SbP = SwPAB(2.8)又因为A和3均为实矩阵且为对称矩阵，所以存在矩阵Q且可逆，使得：QtAQ = I, QtBQ=A(2.9) 其中A为对角矩阵。将/UQTQT和3 = QAQT带入公式(2.8)中可得：ShP = SwP(Q-TQiy Q-tXQ(2o)=SbPQ = SwPQA所以，LDA的最终解P由矩阵和矩阵岛中的前d个最大广义特征值对应的特征 向量所组成的集合。迹比值准则如下：tr(PTS.P)P = arg max s.t.PTP = I(2.11)*(P0P)一般通过迭代方法进行求解此优

59、化目标函数，求解过程计算量较大。此方法易于直 观解释，因此，此方法在某些领域中的应用优于比值迹准则的实际效果。LDA充分利用了类别标签信息同时用于维数约简，不仅提高了算法的性能而且增 加了分类器的性能。因次，LDA被广泛运用于计算机视觉、图像检索以及人脸识别等 领域中，但以此同时，LDA也存在着一些问题：如求解S,”是会出现奇异值问题(即小 样本问题)、求解的投影特征向量个数受限制等。下面详细介绍常见的几种非线性维数约简方法。(1)局部线性嵌入(Locally Linear Embedding, LLE)LLE算法由Sam T. Roweis和Lawrence K. Saul于2000年于提出

60、的，是一种无监 督流形学习算法。该算法简言之利用局部线性来表示全局非线性，从而使局部代表整体 的性质特点，即处理后的低维数据能够保持原有数据的拓扑结构。在降维过程中，通过 寻找保持局部线性的重构系数能够在低维空间表示。LLE算法形象地表示如图2.4所示。Step 1Step 2Step 3图2.4 LLE算法示意图Fig. 2.4 LLE algorithm schematicLLE算法主要步骤如下:选择数据点兀的*邻域；通过寻欧式距离找数据点吐的#个近邻点，其k个数据 点组成的集合N（xJ = 气叫，气 , z?. =z1,z2,-，4） o根据相邻数据之间的相互关系计算重构相似矩阵WeRN