《毕业设计论文谱聚类维数约简算法研究与应用》由会员分享，可在线阅读，更多相关《毕业设计论文谱聚类维数约简算法研究与应用（56页珍藏版）》请在金锄头文库上搜索。
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研究成果651第一章 绪论第1章 绪论1.1 研究背景和意义1.1.1 研究背景目前，众多领域的数据获取具有如下特点：首先，对于一些领域一次实验的费用十分昂贵，而对大量观察数据无法直接判断其价值；其次，两次观察之间不独立或属性之间不独立；此外，噪音数据不一定独立于问题世界；但是，相对而言，数据的存储比较便宜，所以人们不得不被动的记录所有的观察数据，这样的后果就
7、是数据的维数巨大1。如果将这些高维数据直接作为输入进行分类器训练，可能会带来两个棘手的问题：（1）计算复杂度高：很多在低维空间具有良好性能的分类算法在计算上变得不可行，此外一些分类算法的复杂度与数据特征维数相关2；（2）分类器的泛化能力低：在训练样本容量一定的前提下，特征维数的增加将使得样本统计特性的估计变得更加困难，从而降低了分类器的推广能力或泛化能力。所以说，数据的特征维数不是越多越好。一些特征之间会存在一定的相关性，这种相关性可能会降低最终的分类精度，而且冗余的特征会增加运算量。此外，样本的本征维数很可能远小于特征维数。因此有必要对特征向量进行维数约简23。近年来，谱聚类（Spectra
8、l Clustering）方法4567得到了突飞猛进的发展，并且较现存方法表现出明显的优势。该类方法将聚类问题转化为谱图划分问题，进而再转化为特征求解问题，所以实现简单，也不会陷入局部最优解。而且谱聚类算法能识别非凸分布聚类，迎合实际应用，已成功应用于图像分割8、计算机视觉4和文本挖掘9等领域。谱聚类算法只涉及到数据点的数目，因而避免了维数过高所造成的奇异性问题。从谱聚类算法的实现过程可以看出，谱聚类和主分量分析（Principal Component Analysis, PCA）10有着相同的地方，两者均要进行特征分解，在特征分解后，均得到包含原始数据最大特征信息的主分量。因此，可以从PCA
9、的角度来理解谱聚类11。谱聚类分解成两个步骤，一是通过使用某个相似性矩阵的特征向量来得到数据点在低维空间的嵌入，从而获得更加紧致的聚类；二是使用经典的聚类算法将谱嵌入后的数据点进行分组。谱聚类中的第一步和其他谱嵌入方法，如多维尺度分析（Multidimensional Scaling, MDS）12、局部线性嵌入（Locally Linear Embedding, LLE）13、等度规映射（Isometrical Mapping, ISOMAP）14、核主分量分析（Kernel Principal Component Analysis, KPCA）15一样都是建立在特征分解基础上的，这个特征分
10、解过程最终得到一个更能表示原始数据的低维空间161718。本论文的工作正是基于上述背景展开的，论文研究了几种基于谱聚类的维数约简算法，并对其在SAR图像目标识别、手写体数字识别、人脸识别和高光谱遥感图像分类等方面的应用进行了研究。1.1.2 研究意义模式识别自诞生以来，在多方面的应用获得大量的研究成果。但是由于模式识别涉及到很多复杂的问题，因此仍有许多问题有待深入研究。模式识别的基本框架1920如图1.1所示。从该框架可以看出，模式识别过程主要分为三部分：预处理，特征提取和选择，及分类器的设计。每一步的目的都是为了提高最终的识别精度，而且每一步对结果的影响都非常大。输入数据获取数据预处理特征提
11、取和选择分类器设计分类判别决策图1.1模式识别基本框架1920预处理的目的是为了减少噪声，提取有用信息，并消除目标的方位变化对结果的影响等，预处理方法包括去噪、分割、复原和归一化等。特征提取和选择19的目的是用某种方法把预处理后得到庞大的原始数据从模式空间转换到特征子空间，使得在特征子空间中，数据具有很好的区分能力。特征提取和选择对识别精度和稳定性的影响至关重要。特征提取（或特征变换）是指针对数量可能很大的原始特征，通过映射或变换的方法抽取出能表示样本的少数维特征。特征选择是指从一组特征中挑选出一些最有效的特征以达到降低特征空间维数，提高特征辨别力的目的。特征选择所选择出来的特征通常是原始特征
12、集合的一个子集，这些特征都有明确的物理意义。常见的特征选择方法有：基于遗传算法的特征选择21、基于粗糙集理论的特征选择22、基于神经网络的特征选择23和基于关联规则的特征选择24。虽然特征选择方法能提取出具有明确物理意义的特征子集，但是基于某种规则去掉的那些特征多数情况下也不是对结果毫无贡献，所以特征选择之后的最优特征子集往往不能得到最佳识别精度。而特征变换之后的特征通常是原始特征的某种组合，一个好的特征变换规则能得到使得识别结果最佳的特征子集。本文的重心在于特征变换方法的研究，目的就是构造基于谱聚类的特征变换方法，以提高后续分类识别精度。分类器的设计是模式识别系统中继特征提取和选择之后的核心
13、任务。虽然特征提取和选择对分类结果影响较大，好的分类器设计和方法也会提高系统分类性能。目前，比较流行的分类识别方法包括最近邻和k近邻25、决策树26、贝叶斯分类器27、神经网络28和支撑矢量机29等。其中k近邻和支撑矢量机是本文后续实验中用到的分类器。k近邻方法25（K Nearest Neighbor, KNN）是Cover和Hart于1968年提出的一个非常简单直观的分类方法。如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。最近邻方法为k近邻方法的特例。该类方法在分类决策上依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。支撑矢量机29
14、30是由Vapnik等提出的一种机器学习方法。它以统计学习理论为基础，最基本思想之一的结构化风险最小化原则（Structural Risk Minimization, SRM）要优于传统的经验风险最小化原则（Empirical Risk Minimization, ERM）。由于SVM拥有很好的泛化和推广能力，因此被广泛地应用于各个领域。1.2 维数约简国内外研究现状2003年NIPS的一个workshop以特征提取与特征选择为主题作了广泛而深入的讨论，汇聚了该领域的最新研究成果31。目前，已经有许多种维数约简方法，分类有很多种，具体如下：（1）按照实现的具体途径分为特征选择和特征变换；（2）
15、根据变换函数的形式分为线性方法和非线性方法；（3）根据获得低维表示的方法不同分为投影方法和流形方法32；（4）根据是否考虑了已知样本的类别信息分为有监督维数约简方法33、无监督维数约简方法和半监督维数约简方法343536。在这些已有的降维方法中，PCA和Fisher线性判别方法（Linear Discrimination Analysis, LDA）37是最著名，也是应用最广的线性降维方法20。PCA是基于K-L变换（也称Hotelling变换）的，其主要目标是寻找在最小均方意义下最能代表原始数据的投影方向，该投影方向是通过线性变换得到的一组最优的单位正交向量基，这些向量的线性组合可以重构原始样本，并且重构后的样本和原样本之间的误差最小。PCA在许多模式识别应用中取得了较好的效果，但是由于它是一种无监督的降维方法，不适用于反映样本之间的差异。相对于PCA方法，LDA是一种有监督
