毕业设计（论文）谱聚类维数约简算法研究与应用

1、1摘要摘要机器学习、模式识别、信息检索和生物信息中面临着一个主要的问题：维数灾难，因此维数约简方法的研究越来越有必要。本论文以合成孔径雷达（sar）图像目标识别、高光谱图像分类与人脸识别为应用背景，针对谱聚类算法自身具有的维数约简特性，研究基于谱聚类的维数约简算法。结合国家自然科学基金项目和国家部委科技项目，将所提出的方法应用于sar图像目标识别、人脸识别和高光谱遥感图像分类中。本论文主要工作概括如下：（1）基于经典njw谱聚类算法构造了一种谱特征分析方法，在此基础上对尺度参数进行研究，提出了一种基于多参数自调节谱聚类维数约简算法，并将其应用于手写体数字识别和sar图像目标识别。多参数自调节谱

2、特征与传统特征变换方法得到的特征相比，提高了后续识别精度。此外，自调节参数避免了手动调节全局尺度参数的麻烦，由于自调节尺度参数考虑了各个样本点自身的邻域统计信息，比给所有的样本点赋予相同的全局尺度参数更合理。（2）在构造谱聚类图切判据的过程中加入已知类别样本点的类别信息，提出了一种基于新的谱聚类图切判据标度切判据的监督维数约简算法。同时，为了降低计算复杂度，提高算法的推广性能，在构造切判据的过程中只考虑k-近邻之间的类间和类内不相似性，这样能放松数据的类内方差，增大数据的类间边缘，从而获得更合理的投影矩阵。从人脸识别及高光谱遥感图像分类实验结果可以看出，基于局部标度切判据监督维数约简算法提取的

3、特征能得到更好更稳定的识别结果。在局部标度切判据监督维数约简算法基础上，借鉴最优维数判别分析方法思想，提出了最优维数标度切判据分析方法。实验结果表明，最优维数判别分析方法能够获得满意的结果。（3）基于标度切判据监督维数约简算法，使用核技术提出了一种核标度切判据监督维数约简算法，从而扩大了其应用范围。当原始特征维数大于样本数时，线性标度切判据监督维数约简方法会出现奇异问题，而该方法避免了此问题，对原始数据的原始特征维数没有限制。将基于核标度切判据的监督维数约简方法用于sar图像目标识别，实验结果验证了该方法在sar图像目标识别领域的应用潜力。关键字：维数约简 谱特征 图切判据 sar目标识别 高

4、光谱图像分类第一章 绪论目录目录摘要1abstract3第一章绪论11.1研究背景和意义11.1.1研究背景11.1.2研究意义21.2维数约简国内外研究现状31.3论文的主要工作5第二章维数约简算法的研究72.1维数约简基本概念72.2pca和kpca72.3lda和kfda92.4mds和isomap102.5lle112.6本章小结11第三章基于多参数自调节谱聚类维数约简的图像目标识别133.1引言133.2谱聚类算法简介133.3多参数自调节谱聚类143.4基于多参数自调节谱聚类的维数约简算法的构造153.4.1训练样本的维数约简153.4.2测试样本的维数约简173.4.3算法步骤1

5、73.5基于多参数自调节谱聚类维数约简的图像目标识别183.5.1uci数据分类183.5.2手写体数字识别203.5.3sar图像目标识别243.6本章小结29第四章基于局部标度切的监督维数约简及其应用314.1引言314.2规范切与fisher准则314.2.1规范切324.2.2fisher准则324.3基于局部标度切的监督维数约简334.3.1标度切的构造334.3.2局部标度切344.3.3基于局部标度切的监督维数约简354.4最优维数标度切判据分析方法364.5实验及结果分析374.5.1uci数据分类374.5.2人脸识别404.5.3高光谱遥感图像分类414.6本章小结43第五

6、章基于核标度切监督维数约简的图像目标识别455.1引言455.2基于核标度切判据的监督维数约简算法465.3实验结果及分析475.3.1uci数据分类475.3.2sar图像目标识别485.4本章小结51总结与展望53致谢55参考文献57研究成果655第一章 绪论第1章 绪论1.1 研究背景和意义1.1.1 研究背景目前，众多领域的数据获取具有如下特点：首先，对于一些领域一次实验的费用十分昂贵，而对大量观察数据无法直接判断其价值；其次，两次观察之间不独立或属性之间不独立；此外，噪音数据不一定独立于问题世界；但是，相对而言，数据的存储比较便宜，所以人们不得不被动的记录所有的观察数据，这样的后果就

7、是数据的维数巨大error! reference source not found.。如果将这些高维数据直接作为输入进行分类器训练，可能会带来两个棘手的问题：（1）计算复杂度高：很多在低维空间具有良好性能的分类算法在计算上变得不可行，此外一些分类算法的复杂度与数据特征维数相关error! reference source not found.；（2）分类器的泛化能力低：在训练样本容量一定的前提下，特征维数的增加将使得样本统计特性的估计变得更加困难，从而降低了分类器的推广能力或泛化能力。所以说，数据的特征维数不是越多越好。一些特征之间会存在一定的相关性，这种相关性可能会降低最终的分类精度，而且冗

8、余的特征会增加运算量。此外，样本的本征维数很可能远小于特征维数。因此有必要对特征向量进行维数约简error! reference source not found.error! reference source not found.。近年来，谱聚类（spectral clustering）方法error! reference source not found.error! reference source not found.error! reference source not found.error! reference source not found.得到了突飞猛进的发展，并且较现存方

9、法表现出明显的优势。该类方法将聚类问题转化为谱图划分问题，进而再转化为特征求解问题，所以实现简单，也不会陷入局部最优解。而且谱聚类算法能识别非凸分布聚类，迎合实际应用，已成功应用于图像分割error! reference source not found.、计算机视觉error! reference source not found.和文本挖掘error! reference source not found.等领域。谱聚类算法只涉及到数据点的数目，因而避免了维数过高所造成的奇异性问题。从谱聚类算法的实现过程可以看出，谱聚类和主分量分析（principal component analysis

10、, pca）error! reference source not found.有着相同的地方，两者均要进行特征分解，在特征分解后，均得到包含原始数据最大特征信息的主分量。因此，可以从pca的角度来理解谱聚类error! reference source not found.。谱聚类分解成两个步骤，一是通过使用某个相似性矩阵的特征向量来得到数据点在低维空间的嵌入，从而获得更加紧致的聚类；二是使用经典的聚类算法将谱嵌入后的数据点进行分组。谱聚类中的第一步和其他谱嵌入方法，如多维尺度分析（multidimensional scaling, mds）error! reference source n

11、ot found.、局部线性嵌入（locally linear embedding, lle）error! reference source not found.、等度规映射（isometrical mapping, isomap）error! reference source not found.、核主分量分析（kernel principal component analysis, kpca）error! reference source not found.一样都是建立在特征分解基础上的，这个特征分解过程最终得到一个更能表示原始数据的低维空间error! reference source

12、 not found.error! reference source not found.error! reference source not found.。本论文的工作正是基于上述背景展开的，论文研究了几种基于谱聚类的维数约简算法，并对其在sar图像目标识别、手写体数字识别、人脸识别和高光谱遥感图像分类等方面的应用进行了研究。1.1.2 研究意义模式识别自诞生以来，在多方面的应用获得大量的研究成果。但是由于模式识别涉及到很多复杂的问题，因此仍有许多问题有待深入研究。模式识别的基本框架error! reference source not found.error! reference sou

13、rce not found.如图1.1所示。从该框架可以看出，模式识别过程主要分为三部分：预处理，特征提取和选择，及分类器的设计。每一步的目的都是为了提高最终的识别精度，而且每一步对结果的影响都非常大。输入数据获取数据预处理特征提取和选择分类器设计分类判别决策图1.1模式识别基本框架error! reference source not found.error! reference source not found.预处理的目的是为了减少噪声，提取有用信息，并消除目标的方位变化对结果的影响等，预处理方法包括去噪、分割、复原和归一化等。特征提取和选择error! reference source

14、 not found.的目的是用某种方法把预处理后得到庞大的原始数据从模式空间转换到特征子空间，使得在特征子空间中，数据具有很好的区分能力。特征提取和选择对识别精度和稳定性的影响至关重要。特征提取（或特征变换）是指针对数量可能很大的原始特征，通过映射或变换的方法抽取出能表示样本的少数维特征。特征选择是指从一组特征中挑选出一些最有效的特征以达到降低特征空间维数，提高特征辨别力的目的。特征选择所选择出来的特征通常是原始特征集合的一个子集，这些特征都有明确的物理意义。常见的特征选择方法有：基于遗传算法的特征选择error! reference source not found.、基于粗糙集理论的特征

15、选择error! reference source not found.、基于神经网络的特征选择error! reference source not found.和基于关联规则的特征选择error! reference source not found.。虽然特征选择方法能提取出具有明确物理意义的特征子集，但是基于某种规则去掉的那些特征多数情况下也不是对结果毫无贡献，所以特征选择之后的最优特征子集往往不能得到最佳识别精度。而特征变换之后的特征通常是原始特征的某种组合，一个好的特征变换规则能得到使得识别结果最佳的特征子集。本文的重心在于特征变换方法的研究，目的就是构造基于谱聚类的特征变换方法，

16、以提高后续分类识别精度。分类器的设计是模式识别系统中继特征提取和选择之后的核心任务。虽然特征提取和选择对分类结果影响较大，好的分类器设计和方法也会提高系统分类性能。目前，比较流行的分类识别方法包括最近邻和k近邻error! reference source not found.、决策树error! reference source not found.、贝叶斯分类器error! reference source not found.、神经网络error! reference source not found.和支撑矢量机error! reference source not found.等。其

17、中k近邻和支撑矢量机是本文后续实验中用到的分类器。k近邻方法error! reference source not found.（k nearest neighbor, knn）是cover和hart于1968年提出的一个非常简单直观的分类方法。如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。最近邻方法为k近邻方法的特例。该类方法在分类决策上依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。支撑矢量机error! reference source not found.error! reference source not found.是由v

18、apnik等提出的一种机器学习方法。它以统计学习理论为基础，最基本思想之一的结构化风险最小化原则（structural risk minimization, srm）要优于传统的经验风险最小化原则（empirical risk minimization, erm）。由于svm拥有很好的泛化和推广能力，因此被广泛地应用于各个领域。1.2 维数约简国内外研究现状2003年nips的一个workshop以特征提取与特征选择为主题作了广泛而深入的讨论，汇聚了该领域的最新研究成果error! reference source not found.。目前，已经有许多种维数约简方法，分类有很多种，具体如下：

19、（1）按照实现的具体途径分为特征选择和特征变换；（2）根据变换函数的形式分为线性方法和非线性方法；（3）根据获得低维表示的方法不同分为投影方法和流形方法error! reference source not found.；（4）根据是否考虑了已知样本的类别信息分为有监督维数约简方法error! reference source not found.、无监督维数约简方法和半监督维数约简方法error! reference source not found.error! reference source not found.error! reference source not found.。在这

20、些已有的降维方法中，pca和fisher线性判别方法（linear discrimination analysis, lda）error! reference source not found.是最著名，也是应用最广的线性降维方法error! reference source not found.。pca是基于k-l变换（也称hotelling变换）的，其主要目标是寻找在最小均方意义下最能代表原始数据的投影方向，该投影方向是通过线性变换得到的一组最优的单位正交向量基，这些向量的线性组合可以重构原始样本，并且重构后的样本和原样本之间的误差最小。pca在许多模式识别应用中取得了较好的效果，但是由于

21、它是一种无监督的降维方法，不适用于反映样本之间的差异。相对于pca方法，lda是一种有监督的降维方法，主要目标就是寻找在最小均方意义下，最能够分开各类数据的投影方向，实现上是通过寻找一组线性变换以达到类内散度最小且类间散度最大的目的。目前，lda是最基本也是应用最广的降维方法。但是lda的定义决定了它的不足存在“奇异值”问题：当原始高维空间中的样本维数远大于样本数，则lda中散度矩阵会出现奇异性。为了有效地解决lda的奇异性问题，学者们提出了多种解决方法，如：pca+lda法error! reference source not found.error! reference source no

22、t found.和零空间法ldaerror! reference source not found.等。线性的维数约简方法因为具有实现简单、计算效率高，并且能够保证发现嵌入在高维输入空间中的线性子空间上的数据集的真实的几何结构error! reference source not found.等优点，被广泛应用于各个领域。但是由于真实世界中多数数据都是非线性分布的，这使得以上线性维数约简方法不能处理很复杂的真实数据，因而有必要展开对非线性维数约简方法的研究。对线性维数约简方法进行改进，使其能用于处理非线性数据，方法有不少，目前常用的有error! reference source not fo

23、und.：1. 混合局部线性的方法：将全局非线性转换为局部线性，然后通过组合局部线性来描述全局信息。这类方法的假设前提是：非线性高维数据是局部线性的。2. 核方法：用一个非线性核函数将原始数据映射到一个更高维的线性特征空间，然后在该特征空间中执行相应的线性维数约简算法，从而得到数据的低维表示。除了对已有线性算法进行改进和补充得到非线性维数约简算法，近年来发展起来的基于流形学习的降维方法是一种从全新角度来解决高维数据的降维问题的方法。混合局部线性方法的思想接近于逼近算法，计算效率不高，而且多数方法都使用em（expectation maximization）算法进行学习，容易陷入局部极小。此外最

24、重要的是，如何将局部线性模型中获得的低维坐标组合在一个全局的低维坐标系统中是该类方法必须面对的问题error! reference source not found.。基于以上原因，混合局部线性方法的研究没有像核方法那样成为研究的热点。首先使用核方法解决非线性维数约简的研究是bernhard schölkopf等人error! reference source not found.于1998年提出的核主分量分析方法（kernel pca, kpca），kpca首先使用一个非线性函数将原始数据映射到一个更高维的线性特征空间，然后在这个特征空间中执行pca。在算法的实现中，原始数据映射到

25、更高维特征空间的过程只需通过计算核函数的点积就可实现，不仅方便而且计算量小。核fisher判别分析方法（kernel fisher discrimination analysis, kfda）借鉴kpca的思想，用核方法成功地将fisher判别分析方法推广到了非线性领域。常用的核函数有：线性核函数、多项式函数、径向基函数、动态核函数等。选择不同的核函数可构成不同的kpca或kfda方法。面对不同的问题选择合适的核函数是一个难题，核函数中核参数的设置也是一个需要考虑的问题。基于流形学习的降维方法起源于2000年science上面的两篇文章所提出的两种降维方法：isomaperror! refer

26、ence source not found.和lleerror! reference source not found.，分别由tenebaum和roweis提出。此外还有拉普拉斯特征映射（laplacian eigenmaps）error! reference source not found.、hessian局部线性嵌入（hessian-based locally linear embedding, hlle）error! reference source not found.和保角映射算法error! reference source not found.等算法。谱聚类算法作为流形学习的

27、一种，也可在此基础上构造基于谱聚类的维数约简算法，如谱特征分析（spectral feature analysis）error! reference source not found.。基于流形学习的降维方法的一个难点就是如何实现超越样本的扩展（out-of-sample extension），在已有的框架下，以上提及的基于流形学习的降维方法只能通过nyström公式来计算测试样本的低维嵌套error! reference source not found.。c. alzate等人提出可用加权核主分量分析（weighted kernel pca, wkpca）error! refer

28、ence source not found.error! reference source not found.error! reference source not found.框架来计算测试样本的低维嵌套。在wkpca框架下，可以通过直接计算新的样本点在特征向量上的投影得到。这些基于流形学习的维数约简算法都是通过求解一个特征值问题来获得原始高维数据的低维表示，算法实现简单，而且能够发现隐含的非线性流形，同时也可避免局部极值问题error! reference source not found.。基于流形学习的维数约简方法仍然处于发展阶段，很多理论还不成熟，已有的算法也存在诸多问题，而且该类

29、方法主要还集中在非监督学习，在监督学习研究中，该类方法目前并不占明显优势。这些问题并未妨碍许多学者对流形学习维数约简算法的兴趣，他们从不同的角度对已有算法进行分析和总结，并提出改进。随着维数约简方法理论研究的深入，其广泛应用于图像处理、手写体数据处理error! reference source not found.、语音信号处理error! reference source not found.、文本数据处理error! reference source not found.、医学error! reference source not found.、天文数据处理error! referenc

30、e source not found.以及金融数据处理error! reference source not found.等领域。其中图像处理方面的应用还可细分为：sar图像目标识别error! reference source not found.、高光谱图像处理error! reference source not found.error! reference source not found.、人脸识别error! reference source not found.error! reference source not found.、人脸表示error! reference sour

31、ce not found.、图像检索error! reference source not found.、三维动画处理error! reference source not found.等方面。1.3 论文的主要工作本论文在模式识别基本框架下，以识别精度的提高为主要目的，针对维数灾难问题，研究基于谱聚类维数约简算法，并结合国家自然科学基金项目和十五国防预研项目，将所提出的方法应用于sar图像目标识别、手写体数字识别、人脸识别和高光谱遥感图像分类中。本论文的主要创新点如下：（1）基于经典njw谱聚类算法构造了一种谱特征分析方法，在此基础上对尺度参数进行研究，提出了一种基于多参数自调节谱聚类维数约

32、简算法，并将其应用于手写体数字识别和sar图像目标识别。多参数自调节谱特征与传统特征变换方法得到的特征相比，提高了后续识别精度。此外，自调节参数避免了手动调节全局尺度参数的麻烦，由于自调节尺度参数考虑了各个样本点自身的邻域统计信息，比给所有的样本点赋予相同的全局尺度参数更合理。（2）在构造谱聚类图切判据的过程中加入已知类别样本点的类别信息，提出了一种基于新的谱聚类图切判据标度切判据的监督维数约简算法。同时，为了降低计算复杂度，提高算法的推广性能，在构造切判据的过程中只考虑k-近邻之间的类间和类内不相似性，这样能放松数据的类内方差，增大数据的类间边缘，从而获得更合理的投影矩阵。从人脸识别及高光谱

33、遥感图像分类实验结果可以看出，基于局部标度切判据监督维数约简算法提取的特征能得到更好更稳定的识别结果。在局部标度切判据监督维数约简算法基础上，借鉴最优维数判别分析方法思想，提出了最优维数标度切判据分析方法。实验结果表明，最优维数判别分析方法能够获得满意的结果。（3）基于标度切判据监督维数约简算法，使用核技术提出了一种核标度切判据监督维数约简算法，从而扩大了其应用范围。当原始特征维数大于样本数时，线性标度切判据监督维数约简方法会出现奇异问题，而该方法避免了此问题，对原始数据的原始特征维数没有限制。将基于核标度切判据的监督维数约简方法用于sar图像目标识别，实验结果验证了该方法在sar图像目标识别

34、领域的应用潜力。本论文的主要内容安排如下：第一章：介绍了本课题的研究背景及意义，概述了维数约简的研究现状，并且概要地介绍了本文的主要工作和创新点。第二章：介绍现有的具有代表性的几种维数约简方法。第三章：基于经典njw谱聚类算法构造了一种谱特征分析方法，在此基础上对尺度参数进行研究，提出了一种基于多参数自调节谱聚类维数约简算法，在部分uci数据集上验证算法性能，并将其应用于手写体数字识别和sar图像目标识别。第四章：在构造谱聚类图切判据的过程中加入已知类别样本点的类别信息，提出了一种基于标度切判据的监督维数约简算法。同时，为进一步提高算法的推广性能及降低计算复杂度，结合局部化的k-近邻图，提出了

35、一种局部标度切判据监督维数约简算法，并成功应用于人脸识别和高光谱遥感图像分类。在这一章中，我们在所提出的算法基础上，研究了最优维数提取问题，提出了一种最优维数标度切判据分析方法。第五章：在标度切判据监督维数约简算法基础上，使用核技术提出了一种核标度切判据的监督维数约简算法，从而扩大了其应用范围，并将其成功应用于sar图像目标识别领域。总结和展望。总结全文并提出了值得进一步研究的方向。11第二章 经典维数约简算法的研究第2章 维数约简算法的研究2.1 维数约简基本概念维数约简是指将样本从原始输入空间通过线性或者非线性映射到一个低维空间，从而获得一个原数据集有效的低维表示error! refere

36、nce source not found.error! reference source not found.。获得的低维表示要尽量保留分类信息和不损失后续分类性能。维数约简问题可描述为error! reference source not found.error! reference source not found.：输入高维空间中的一个维样本集，找到一个映射函数，其中，得到该样本集在低维空间中的表示，与此同时尽可能地保持原高维数据的几何结构信息。按照具体实现途径，维数约简分为线性和非线性维数约简方法。常用的线性维数约简方法有pca，lda，奇异值分解（singular value dec

37、omposition, svd）error! reference source not found.等等。这类变换方法对提取的高维特征向量进行正交变换，可以证明正交变换能消除原始向量各分量之间的相关性，并进行降维。以上几种方法都属于线性变换方法，只能提取数据的线性成分。而实际上，真实世界中的数据大部分都是非线性分布的，这使得以上方法不再适用。非线性维数约简方法有kpca，kfda，lleerror! reference source not found.，iosmaperror! reference source not found.等。在上述提及的非线性维数约简方法中，kpca和kfda分别

38、是用核方法对pca和lda方法的非线性推广，而lle和iosmap则是基于流形学习的非线性降维方法，其中与iosmap有关的线性方法是mdserror! reference source not found.。本章中我们将仔细讨论这几种方法。2.2 pca和kpcapcaerror! reference source not found.error! reference source not found.的目标是在低维子空间表示高维数据，使得在误差平方和最小的意义下低维表示能够更好地描述原始数据。它是在数据空间中找出一组向量来解释数据的方差，将数据从原来的维降到维（）。它是根据k-l变换从最大

39、信息压缩方向获得模式在低维空间的信息表达，所以用pca方法所获得的特征空间就是原模式空间的一个最优低维逼近。pca的基本原理为：根据k-l变换在测量空间中找到一组正交向量，这组数据能最大化表示出数据的方差，将原样本向量从维空间投影到这组正交向量张成的维子空间上，其投影系数构成样本的特征向量，从而完成了维数的降维。pca的主要步骤如表2.1所示。表2.1 pca算法流程输入原始数据样本集，为样本数，为原始特征维数。步骤（1） 建立相关矩阵，根据k-l变换求矩阵的特征值和特征向量。利用标准化值计算变量之间的相关系数，可建立阶相关矩阵，由该矩阵可获得特征值，个特征值对应个特征向量，每个特征向量包括个

40、分量。（2） 选取主分量。计算第个主分量对总方差的贡献率，按贡献率由大到小的顺序对个主分量进行排序，贡献率最大的主分量称为第一主分量，其次的分量称为第二主分量，依此类推。选取主分量的个数取决于主分量的累计方差贡献率，通常使累计方差贡献率大于85%。所需的主分量数能够代表个原始变量所能提供的绝大部分信息。（3） 建立主分量方程，计算主分量值。各主分量值方程为，其中为对应于特征值的特征向量的分量，为各分量的标准化数值。计算出所需要的各主分量值，形成新的样本集。输出新的样本集，为输出的特征维数。kpca是bernhard schölkopf等人error! reference source

41、 not found.于1998年提出的，是在pca的基础上加入核方法来提取数据的非线性成分。kpca方法在特征空间内具有与pca相同的数学和统计特性，如提取的各主分量互不相关；主分量都能够表示原始数据的最大方差；用主分量进行样本数量重构时均方误差最小等等。除此之外，kpca提取的特征具有比pca提取的特征更好的稀疏性error! reference source not found.。kpca算法具体推导error! reference source not found.如下：设输入的数据集为，用某种核函数映射到高维特征空间，即：(2-1)且假设。定义该数据集在高维特征空间中的协方差矩阵为：

42、(2-2)对其进行特征值分解可得：(2-3)则就是需要的非线性主方向。令，则可以得到如下公式：(2-4)其中，点积就是核矩阵元素，代入公式(2-4)得到。由于是对称矩阵，且有可以张成整个空间的一系列特征向量，因此上式可以简化为。由此，我们可以得到第个数据点在第个主分量上的投影：(2-5)由公式(2-5)我们可以看出，只要核函数定义恰当，就可以得到所有数据点的各个核主分量。2.3 lda和kfdaldaerror! reference source not found.error! reference source not found.是在fisher判别准则函数取极值的条件下，求得一个最佳鉴别

43、方法，然后将数据从高维特征向量投影到该最佳鉴别方向上，构成一维的鉴别特征空间，于是数据分类可在一维空间中进行。对于类问题，就需要维向量张成的最佳鉴别空间。对于一个类问题，输入个维样本，为样本子集的样本个数。定义类内散度矩阵和类间散度矩阵分别为：(2-6)(2-7)其中，为第类样本的类内散度矩阵，为第类样本的均值向量，是所有样本的均值向量。将维样本投影到维子空间的过程为：(2-8)其中，为投影矩阵，即为投影之后新的样本。这些新的样本在维子空间均值向量和散度矩阵分别为：(2-9)(2-10)(2-11)(2-12)公式(2-6)和(2-11)及公式(2-7)和(2-12)之间的关系为：(2-13)

44、(2-14)lda的目的为寻找一个最优的投影矩阵，使得类间散度尽可能大，同时类内散度尽可能小，即类间散度和类内散度比值最大。由此用如下准则函数来判定：(2-15)该式为广义的瑞利商，可用广义的特征值问题来求解，即转化为：(2-16)由此解得的由特征向量构成的最优投影矩阵即为最能区分样本的特征子空间。kfdaerror! reference source not found.error! reference source not found.本质同kpca一样，是在lda基础上引入核函数，是核学习方法的思想与lda算法相结合的产物。该方法由mika等人于1999年提出，首先把数据非线性地映射到某

45、个特征空间，然后在这个特征空间中进行fisher线性判别，这样就隐含地实现了对原输入空间的非线性判别。2.4 mds和isomapmdserror! reference source not found.是指一系列应用于维数约简，数据分析和可视化领域的算法。mds算法的目的在于所得到的低维空间表示是能够保留原始空间中样本点结构。该类算法以两两数据点之间的相似矩阵（或者称距离矩阵）作为输入，根据这个输入矩阵的不同，可分为：度量mds（metric mds）error! reference source not found.和非度量mds（non-metric mds）error! referen

46、ce source not found.。这两种算法的最主要区别就是输入是否可度量。metric mds算法由torgeson于1965年提出，通过一定的变换函数得到数据之间的相似性，能够精确重构样本点之间的结构。non-metric mds算法由shepard于1962年提出，由于输入是不可度量的，所以不要求知道变换函数的具体形式，只需知道样本点之间距离的排序情况。由于non-metric mds算法有明显的优势，所以较metric mds更为常用。isomaperror! reference source not found.算法可以视为是mds算法的一种变形，其目的也是得到的低维表示能够

47、最大限度保留两两原始样本点之间的距离。isomap与mds的最大区别在于isomap用子流形上的测地线距离代替欧氏距离。isomap算法具体实现步骤可分为：1、构建原始输入样本集的k-近邻图；2、用dijkstra最短路径算法求图上两两样本点之间的近似测地线距离；3、执行mds算法，获得嵌入在高维空间中的低维表示。由于isomap算法考虑的是最短路径，并且综合考虑各个区域，所以寻优过程不会陷入局部极值，得到的是一个全局最优的结果。isomap算法的不足也很明显：如果原始数据集包含的噪声过大，算法将很难有效恢复嵌入在高维数据集的内在结构error! reference source not fo

48、und.；如果要为步骤1中的近邻图创建足够多的连接，可能会出现“短路”现象，导致该算法拓扑稳定性差error! reference source not found.；此外，isomap算法对原始数据的流形结构有要求，限制了其应用范围error! reference source not found.。一些学者针对isomap算法的不足，提出了不少改进算法，如c-isomap算法error! reference source not found.，s-isomap算法error! reference source not found.，p-isomap算法error! reference so

49、urce not found.等。2.5 llelle算法由sam t. roweis和lawrence k. saul于2000年提出error! reference source not found.，是一种通过局部线性关系的联合来揭示全局非线性结构的基于流形的非线性降维方法。lle与isomap的共同点在于都是需要构造数据点的k-近邻图的非线性降维方法，不同点在于isomap是一种全局的方法，而lle是一种保留数据局部性质的局部方法。lle算法能保留数据流形的局部性质，主要是因为用某数据点的近邻点的线性组合来表示该数据点。lle算法的实现主要包含三步：1、找到每个样本点的k个近邻点；2、

50、由每个样本点的近邻点计算出该样本点的局部重构权值矩阵；3、计算由重构权重描述的局部几何的低维表示。其中步骤2有意义的前提是该流形是局部线性的，即每个数据点与其k-近邻域在流形上是局部线性的或者能在近似的局部线性片段上展开。学者们对lle算法也提出了很多改进算法，比较典型的改进算法有：hlleerror! reference source not found.，slleerror! reference source not found.，plleerror! reference source not found.，wlleerror! reference source not found.等。l

51、le算法及其改进算法已经广泛应用于图像数据的分类与聚类error! reference source not found.、人脸识别error! reference source not found.、以及多维数据的可视化error! reference source not found.等领域中。2.6 本章小结本章先对维数约简基本概念进行阐述，然后从线性、非线性以及流形的角度分别阐述了几种经典的维数约简算法，包括pca、kpca、lda、kfda、mds、isomap和lle算法。其中pca和lda属于线性维数约简算法，kpca和kfda属于用核方法由线性维数约简方法推广而来的非线性维数约

52、简算法，mds、isomap和lle算法则属于基于流形学习的非线性维数约简算法。从这些经典的维数约简方法已经衍生出许多相应的改进算法，被广泛应用于众多领域。43第三章 基于多参数自调节谱聚类维数约简的图像目标识别第3章 基于多参数自调节谱聚类维数约简的图像目标识别3.1 引言谱聚类算法error! reference source not found.error! reference source not found.是近些年发展起来的一种高性能计算方法。该类方法思想源于谱图划分，首先将聚类问题转化为一个无向图的多路划分问题，继而用一种有效的连续放松形式将图划分问题转化为特征分解问题，即求解包

53、含了待聚类数据所有信息的矩阵的特征值和特征向量，然后再用经典聚类算法对选取出来的特定的特征向量进行聚类，得到聚类结果。从谱聚类的实现过程来看，谱聚类算法已经将维数约简过程隐含其中。在最终用经典聚类算法进行聚类之前，谱聚类算法已经完成了维数约简过程。由此可见，用谱聚类算法构造维数约简算法是可行的。目前已经有学者构造出谱特征分析等基于谱聚类的维数约简算法。谱聚类算法取得了很好的效果，但是仍然有很多不足，其中尺度参数的选择就是一个尚未有公认解决办法的，却严重影响谱聚类效果的问题。因此，基于谱聚类的维数约简算法也存在这个问题。目前人们常用的方法是人工手动给定一系列的尺度参数进行聚类，分析得到的所有结果

54、，从中选择一个相对最优的结果。这样处理明显存在不足，不仅费时，而且可能得不到合适的结果。在已有的谱聚类算法中，njw算法是比较常用的。本章在njw谱聚类算法的基础上提出了一种基于多参数自调节谱聚类的维数约简算法。在已有的基于谱聚类维数约简方法中，多数是使用nyström逼近方式来解决测试样本的扩展问题，而本章提出的方法是在wkpca框架下，用简单投影来解决该问题的。此外，用多参数自调节的相似度代替原来的相似度，即根据不同样本点自身的邻域信息，自动赋予每个样本点局部尺度参数，这样不仅避免了尺度参数的选择，而且局部尺度参数的使用考虑了数据的局部统计特性，比全局尺度参数更加合理。3.2 谱

55、聚类算法简介谱聚类算法是建立在谱图理论基础之上的一种高性能计算方法。它将聚类问题看成是一个无向图的多路划分问题。其本质是利用数据相似矩阵的特征向量将数据点聚类成不同的类。先将数据点看成是一个无向图的顶点，边表示基于某一相似性度量得到的两点间的相似性，边的集合构成待聚类数据点间的相似性矩阵，它包含了聚类所需的所有信息。然后定义一个划分准则，在映射空间中最优化这一准则使得同一类内的点具有较高的相似性，而不同类之间的点具有较低的相似性。谱聚类算法具体实现的时候一般包括如下三个部分：（1）预处理，也就是拉普拉斯矩阵的构造，不同的谱聚类算法构造拉普拉斯矩阵的方法不同，但不同拉普拉斯矩阵所代表的意义是相同

56、的，也就是衡量样本点之间的相似程度；（2）谱映射，通过特征分解和规范化处理来实现，不同的谱聚类算法在特征分解之后所取的特征向量会有所不同error! reference source not found.，规范化处理也会有差异，但是这两个步骤合起来就是将高维数据嵌入到低维空间的过程；（3）后处理，将聚类结果重新映射到原始空间，就得到了原始样本的聚类结果，不同的谱聚类算法用不同的经典聚类算法对谱映射后的数据进行简单的聚类。现在比较流行的谱聚类算法有：由shi和malik提出的sm算法error! reference source not found.和ms算法error! reference s

57、ource not found.，由kannan，vetta和vempala提出的kvv算法error! reference source not found.，由ng，jordan和weiss提出的njw算法error! reference source not found.等。其中，以njw算法使用最为广泛，具体算法见表2.2。表2.2 njw谱聚类算法流程输入输入一个中的样本集，类别数为步骤（1） 构造该样本集的亲和度矩阵，定义：当的时候，而；（2） 定义对角矩阵，其第个元素为矩阵的第行的元素之和，并构造拉普拉斯矩阵；（3） 找到矩阵的前个最大的特征值对应的特征向量（如果特征值相等，取两

58、两正交的向量），并按列映射到矩阵；（4） 重新按行归一化到单位长度，构成矩阵，也就是；（5） 将中的每一行看成是中的一个点，通过k-均值或者其他算法将它们聚到类中；（6） 如果矩阵的第行被归到第类，则将数据点归到第类。输出输入样本集中所有样本点对应的类标：。3.3 多参数自调节谱聚类尽管谱聚类方法取得了很好的效果，该类方法目前仍处于发展阶段，有很多待研究的问题。其中如何选择合适的尺度参数是一个亟待解决的问题，目前没有普遍公认的解决方法。而谱聚类算法对的选择非常敏感，不同的会得到完全不同的聚类结果。上面所描述的谱聚类算法都是使用一个全局尺度参数来构造相似性矩阵，这样处理的缺陷在于，当不同类数据的局部统计特性相差很远时