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

1摘要摘要机器学习、模式识别、信息检索和生物信息中面临着一个主要的问题：维数灾难，因此维数约简方法的研究越来越有必要本论文以合成孔径雷达（SAR）图像目标识别、高光谱图像分类与人脸识别为应用背景，针对谱聚类算法自身具有的维数约简特性，研究基于谱聚类的维数约简算法结合国家自然科学基金项目和国家部委科技项目，将所提出的方法应用于SAR图像目标识别、人脸识别和高光谱遥感图像分类中本论文主要工作概括如下：（1）基于经典NJW谱聚类算法构造了一种谱特征分析方法，在此基础上对尺度参数进行研究，提出了一种基于多参数自调节谱聚类维数约简算法，并将其应用于手写体数字识别和SAR图像目标识别多参数自调节谱特征与传统特征变换方法得到的特征相比，提高了后续识别精度此外，自调节参数避免了手动调节全局尺度参数的麻烦，由于自调节尺度参数考虑了各个样本点自身的邻域统计信息，比给所有的样本点赋予相同的全局尺度参数更合理2）在构造谱聚类图切判据的过程中加入已知类别样本点的类别信息，提出了一种基于新的谱聚类图切判据——标度切判据的监督维数约简算法同时，为了降低计算复杂度，提高算法的推广性能，在构造切判据的过程中只考虑k-近邻之间的类间和类内不相似性，这样能放松数据的类内方差，增大数据的类间边缘，从而获得更合理的投影矩阵。

从人脸识别及高光谱遥感图像分类实验结果可以看出，基于局部标度切判据监督维数约简算法提取的特征能得到更好更稳定的识别结果在局部标度切判据监督维数约简算法基础上，借鉴最优维数判别分析方法思想，提出了最优维数标度切判据分析方法实验结果表明，最优维数判别分析方法能够获得满意的结果3）基于标度切判据监督维数约简算法，使用核技术提出了一种核标度切判据监督维数约简算法，从而扩大了其应用范围当原始特征维数大于样本数时，线性标度切判据监督维数约简方法会出现奇异问题，而该方法避免了此问题，对原始数据的原始特征维数没有限制将基于核标度切判据的监督维数约简方法用于SAR图像目标识别，实验结果验证了该方法在SAR图像目标识别领域的应用潜力关键字：维数约简 谱特征 图切判据 SAR目标识别 高光谱图像分类第一章 绪论目录目录摘要 1ABSTRACT 3第一章 绪论 11.1 研究背景和意义 11.1.1 研究背景 11.1.2 研究意义 21.2 维数约简国内外研究现状 31.3 论文的主要工作 5第二章 维数约简算法的研究 72.1 维数约简基本概念 72.2 PCA和KPCA 72.3 LDA和KFDA 92.4 MDS和ISOMAP 102.5 LLE 112.6 本章小结 11第三章 基于多参数自调节谱聚类维数约简的图像目标识别 133.1 引言 133.2 谱聚类算法简介 133.3 多参数自调节谱聚类 143.4 基于多参数自调节谱聚类的维数约简算法的构造 153.4.1 训练样本的维数约简 153.4.2 测试样本的维数约简 173.4.3 算法步骤 173.5 基于多参数自调节谱聚类维数约简的图像目标识别 183.5.1 UCI数据分类 183.5.2 手写体数字识别 203.5.3 SAR图像目标识别 243.6 本章小结 29第四章 基于局部标度切的监督维数约简及其应用 314.1 引言 314.2 规范切与Fisher准则 314.2.1 规范切 324.2.2 Fisher准则 324.3 基于局部标度切的监督维数约简 334.3.1 标度切的构造 334.3.2 局部标度切 344.3.3 基于局部标度切的监督维数约简 354.4 最优维数标度切判据分析方法 364.5 实验及结果分析 374.5.1 UCI数据分类 374.5.2 人脸识别 404.5.3 高光谱遥感图像分类 414.6 本章小结 43第五章 基于核标度切监督维数约简的图像目标识别 455.1 引言 455.2 基于核标度切判据的监督维数约简算法 465.3 实验结果及分析 475.3.1 UCI数据分类 475.3.2 SAR图像目标识别 485.4 本章小结 51总结与展望 53致谢 55参考文献 57研究成果 651第一章 绪论第1章 绪论1.1 研究背景和意义1.1.1 研究背景目前，众多领域的数据获取具有如下特点：首先，对于一些领域一次实验的费用十分昂贵，而对大量观察数据无法直接判断其价值；其次，两次观察之间不独立或属性之间不独立；此外，噪音数据不一定独立于问题世界；但是，相对而言，数据的存储比较便宜，所以人们不得不被动的记录所有的观察数据，这样的后果就是数据的维数巨大[1]。

如果将这些高维数据直接作为输入进行分类器训练，可能会带来两个棘手的问题：（1）计算复杂度高：很多在低维空间具有良好性能的分类算法在计算上变得不可行，此外一些分类算法的复杂度与数据特征维数相关[2]；（2）分类器的泛化能力低：在训练样本容量一定的前提下，特征维数的增加将使得样本统计特性的估计变得更加困难，从而降低了分类器的推广能力或泛化能力所以说，数据的特征维数不是越多越好一些特征之间会存在一定的相关性，这种相关性可能会降低最终的分类精度，而且冗余的特征会增加运算量此外，样本的本征维数很可能远小于特征维数因此有必要对特征向量进行维数约简[2][3]近年来，谱聚类（Spectral Clustering）方法[4][5][6][7]得到了突飞猛进的发展，并且较现存方法表现出明显的优势该类方法将聚类问题转化为谱图划分问题，进而再转化为特征求解问题，所以实现简单，也不会陷入局部最优解而且谱聚类算法能识别非凸分布聚类，迎合实际应用，已成功应用于图像分割[8]、计算机视觉[4]和文本挖掘[9]等领域谱聚类算法只涉及到数据点的数目，因而避免了维数过高所造成的奇异性问题从谱聚类算法的实现过程可以看出，谱聚类和主分量分析（Principal Component Analysis, PCA）[10]有着相同的地方，两者均要进行特征分解，在特征分解后，均得到包含原始数据最大特征信息的主分量。

因此，可以从PCA的角度来理解谱聚类[11]谱聚类分解成两个步骤，一是通过使用某个相似性矩阵的特征向量来得到数据点在低维空间的嵌入，从而获得更加紧致的聚类；二是使用经典的聚类算法将谱嵌入后的数据点进行分组谱聚类中的第一步和其他谱嵌入方法，如多维尺度分析（Multidimensional Scaling, MDS）[12]、局部线性嵌入（Locally Linear Embedding, LLE）[13]、等度规映射（Isometrical Mapping, ISOMAP）[14]、核主分量分析（Kernel Principal Component Analysis, KPCA）[15]一样都是建立在特征分解基础上的，这个特征分解过程最终得到一个更能表示原始数据的低维空间[16][17][18]本论文的工作正是基于上述背景展开的，论文研究了几种基于谱聚类的维数约简算法，并对其在SAR图像目标识别、手写体数字识别、人脸识别和高光谱遥感图像分类等方面的应用进行了研究1.1.2 研究意义模式识别自诞生以来，在多方面的应用获得大量的研究成果但是由于模式识别涉及到很多复杂的问题，因此仍有许多问题有待深入研究。

模式识别的基本框架[19][20]如图1.1所示从该框架可以看出，模式识别过程主要分为三部分：预处理，特征提取和选择，及分类器的设计每一步的目的都是为了提高最终的识别精度，而且每一步对结果的影响都非常大输入数据获取数据预处理特征提取和选择分类器设计分类判别决策图1.1模式识别基本框架[19][20]预处理的目的是为了减少噪声，提取有用信息，并消除目标的方位变化对结果的影响等，预处理方法包括去噪、分割、复原和归一化等特征提取和选择[19]的目的是用某种方法把预处理后得到庞大的原始数据从模式空间转换到特征子空间，使得在特征子空间中，数据具有很好的区分能力特征提取和选择对识别精度和稳定性的影响至关重要特征提取（或特征变换）是指针对数量可能很大的原始特征，通过映射或变换的方法抽取出能表示样本的少数维特征特征选择是指从一组特征中挑选出一些最有效的特征以达到降低特征空间维数，提高特征辨别力的目的特征选择所选择出来的特征通常是原始特征集合的一个子集，这些特征都有明确的物理意义常见的特征选择方法有：基于遗传算法的特征选择[21]、基于粗糙集理论的特征选择[22]、基于神经网络的特征选择[23]和基于关联规则的特征选择[24]。

虽然特征选择方法能提取出具有明确物理意义的特征子集，但是基于某种规则去掉的那些特征多数情况下也不是对结果毫无贡献，所以特征选择之后的最优特征子集往往不能得到最佳识别精度而特征变换之后的特征通常是原始特征的某种组合，一个好的特征变换规则能得到使得识别结果最佳的特征子集本文的重心在于特征变换方法的研究，目的就是构造基于谱聚类的特征变换方法，以提高后续分类识别精度分类器的设计是模式识别系统中继特征提取和选择之后的核心任务虽然特征提取和选择对分类结果影响较大，好的分类器设计和方法也会提高系统分类性能目前，比较流行的分类识别方法包括最近邻和k近邻[25]、决策树[26]、贝叶斯分类器[27]、神经网络[28]和支撑矢量机[29]等其中k近邻和支撑矢量机是本文后续实验中用到的分类器k近邻方法[25]（K Nearest Neighbor, KNN）是Cover和Hart于1968年提出的一个非常简单直观的分类方法如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别最近邻方法为k近邻方法的特例该类方法在分类决策上依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

支撑矢量机[29][30]是由Vapnik等提出的一种机器学习方法它以统计学习理论为基础，最基本思想之一的结构化风险最小化原则（Structural Risk Minimization, SRM）要优于传统的经验风险最小化原则（Empirical Risk Minimization, ERM）由于SVM拥有很好的泛化和推广能力，因此被广泛地应用于各个领域1.2 维数约简国内外研究现状2003年NIPS的一个workshop以特征提取与特征选择为主题作了广泛而深入的讨论，汇聚了该领域的最新研究成果[31]目前，已经有许多种维数约简方法，分类有很多种，具体如下：（1）按照实现的具体途径分为特征选择和特征变换；（2）根据变换函数的形式分为线性方法和非线性方法；（3）根据获得低维表示的方法不同分为投影方法和流形方法[32]；（4）根据是否考虑了已知样本的类别信息分为有监督维数约简方法[33]、无监督维数约简方法和半监督维数约简方法[34][35][36]在这些已有的降维方法中，PCA和Fisher线性判别方法（Linear Discrimination Analysis, LDA）[37]是最著名，也是应用最广的线性降维方法[20]。

PCA是基于K-L变换（也称Hotelling变换）的，其主要目标是寻找在最小均方意义下最能代表原始数据的投影方向，该投影方向是通过线性变换得到的一组最优的单位正交向量基，这些向量的线性组合可以重构原始样本，并且重构后的样本和原样本之间的误差最小PCA在许多模式识别应用中取得了较好的效果，但是由于它是一种无监督的降维方法，不适用于反映样本之间的差异相对于PCA方法，LDA是一种有监督。