（电路与系统专业论文）谱聚类维数约简算法研究与应用.pdf

摘要 摘要 机器学习、模式识别、信息检索和生物信息中面临着一个主要的问题：维数 灾难，因此维数约简方法的研究越来越有必要。本论文以合成孔径雷达( s a r ) 图像目标识别、高光谱图像分类与人脸识别为应用背景，针对谱聚类算法自身具 有的维数约简特性，研究基于谱聚类的维数约简算法。结合国家自然科学基金项 目和国家部委科技项目，将所提出的方法应用于s a l l 图像目标识别、人脸识别和 高光谱遥感图像分类中。 本论文主要工作概括如下： ( 1 ) 基于经典n j w 谱聚类算法构造了一种谱特征分析方法，在此基础上对 尺度参数进行研究，提出了一种基于多参数自调节谱聚类维数约简算法，并将其 应用于手写体数字识别和s a r 图像目标识别。多参数自调节谱特征与传统特征变 换方法得到的特征相比，提高了后续识别精度。此外，自调节参数避免了手动调 节全局尺度参数的麻烦，由于自调节尺度参数考虑了各个样本点自身的邻域统计 信息，比给所有的样本点赋予相同的全局尺度参数更合理。 ( 2 ) 在构造谱聚类图切判据的过程中加入已知类别样本点的类别信息，提出 了一种基于新的谱聚类图切判据标度切判据的监督维数约简算法。同时，为 了降低计算复杂度，提高算法的推广性能，在构造切判据的过程中只考虑肛近邻 之间的类间和类内不相似性，这样能放松数据的类内方差，增大数据的类间边缘， 从而获得更合理的投影矩阵。从人脸识别及高光谱遥感图像分类实验结果可以看 出，基于局部标度切判据监督维数约简算法提取的特征能得到更好更稳定的识别 结果。在局部标度切判据监督维数约简算法基础上，借鉴最优维数判别分析方法 思想，提出了最优维数标度切判据分析方法。实验结果表明，最优维数判别分析 方法能够获得满意的结果。 ( 3 ) 基于标度切判据监督维数约简算法，使用核技术提出了一种核标度切判 据监督维数约简算法，从而扩大了其应用范围。当原始特征维数大于样本数时， 线性标度切判据监督维数约简方法会出现奇异问题，而该方法避免了此问题，对 原始数据的原始特征维数没有限制。将基于核标度切判据的监督维数约简方法用 于s a r 图像目标识别，实验结果验证了该方法在s a r 图像目标识别领域的应用潜 力。 关键字：维数约简谱特征图切判据s a r 目标识别高光谱图像分类 a b s t r a c t3 a bs t r a c t c u r s eo fd i m e n s i o n a l i t yi sn o wam a i np r o b l e mi nm a c h i n el e a r n i n g , p a t t e m r e c o g n i t i o n , i n f o r m a t i o nr e t r i e v a la n db i o l o g i c a li n f o r m a t i o n , w h i c hr e s u l t si nm o r e a t t e n t i o n s0 1 1d i m e n s i o n a l i t yr e d u c t i o nm e t h o d s i no r d e rt oe n h a n c et h ep e r f o r m a n c eo f s a rt a r g e tr e c o g n i t i o n , f a c er e c o g n i t i o na n dh y p e r s p e c t r a lr e m o t es e n s i n gi m a g e c l a s s i f i c a t i o n , t h i sd i s s e r t a t i o nf o c u s e so nt h er e s e a r c ho ns p e c t r a lc l u s t e r i n gb a s e d d i m e n s i o n a l i t yr e d u c t i o na l g o r i t h mu s i n gt h ei n t r i n s i c a ld i m e n s i o n a l i t yr e d u c t i o no f s p e c t r a lc l u s t e r i n g s u p p o r t e db yt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n aa n d t h en a t i o n a ls c i e n c ea n dt e c h n o l o g ym i n i s t r yo fc h i n a , s o m en e wa l g o r i t h r n sa r e p r o p o s e da n da p p l i e dt os a rt a r g e tr e c o g n i t i o n , f a c er e c o g n i t i o na n dh y p e r s p e c t r a l r e m o t es e n s i n gi m a g ec l a s s i f i c a t i o n t h em a i nc o n t r i b u t i o n sc a nb es u m m a r i z e da sf o l l o w s ： ( 1 ) b a s e do ns p e c t r a lf e a t u r ea n a l y s i s d e r i v e df r o mc l a s s i c a ln j ws p e c t r a l c l u s t e r i n g ，an e wd i m e n s i o n a l i t y r e d u c t i o n a l g o r i t h mb a s e d o n m u l t i - p a r a m e t e r s e l f - t u n i n gs p e c t r a lc l u s t e r i n gi sp r o p o s e d ，w h i c hs o l v e st h ep r o b l e mo fs c a l ep a r a m e t e r c o m p a r e d 、析t l lt h et r a d i t i o n a lf e a t u r et r a n s f o r m a t i o nm e t h o d si nt h ea p p l i c a t i o n st o h a n d w r i t t e nd i g i t sr e c o g n i t i o na n ds a rt a r g e tr e c o g n i t i o n , t h ep r o p o s e dm e t h o dc a n a c h i e v eb e t t e ra c c u r a c y b e s i d e s ，s e l f - t u n i n gp a r a m e t e r sn o to n l yc a ng e tr i do ft h e t r o u b l eo fs e l e c t i n gap r o p e rg l o b a ls c a l ep a r a m e t e r , b u ta l s oa r em o r er e a s o n a b l et h a n g l o b a l s c a l e p a r a m e t e r , f o rs e l f - t u n i n gp a r a m e t e r sc o n s i d e rt h en e i g h b o r h o o d i n f o r m a t i o no fe a c hs a m p l e ( 2 ) as u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o na l g o r i t h mi sp r o p o s e db a s e do nan e w s p e c t r a lc l u s t e r i n gg r a p hc u tc r i t e r i o n ，s c a l i n gc u tc r i t e r i o n , w h i c hc o n s i d e r st h ec l a s s i n f o r m a t i o no ft h el a b e l e ds a m p l e s i no r d e rt or e d u c et h ec o m p u t a t i o n a lc o m p l e x i t y , a s w e l la se n h a n c et h eg e n e r a l i z a t i o np e r f o r m a n c eo ft h ea l g o r i t h m ，l o c a l i z e dkn e a r e s t n e i g h b o rg r a p hi si n t r o d u c e di n t ow h e nc o n s t r u c t i n gs c a l i n gc u tc r i t e r i o n am o r e r e a s o n a b l ep r o j e c t i o nm a t r i xc a no b t a i n e df o rt h eu s eo fl o c a l i z e dkn e a r e s tn e i g h b o r g r a p hc a l lr e l a xt h ev a r i a n c ew i t h i nc l a s s ，w h i l ee n l a r g et h ee d g eb e t w e e nc l a s s e s e x p e r i m e n t so nf a c er e c o g n i t i o na n dh y p e r s p e c t r a lr e m o t es e n s i n gi m a g ec l a s s i f i c a t i o n s h o wt h a tt h ep r o p o s e da l g o r i t h m sc a na c h i e v eb e t t e ra n dm o r es t a b l er e s u l t s o p t i m a l d i m e n s i o n a l i t ys c a l i n gc u tc r i t e r i o na n a l y s i si so b t a i n e db a s e do nt h ep r o p o s e d a l g o r i t h m , d r a w i n go no p t i m a ld i m e n s i o n a l i t yd i s c r i m i n a n ta n a l y s i s t h ee x p e r i m e n t a l r e s u l t sd e n o t et h a to p t i m a ld i m e n s i o n a l i t ys c a l i n gc u tc r i t e r i o na n a l y s i sc a i le x t r a c tt h e 4 谱聚类维数约简算法研究与应用 o p t i m a ld i m e n s i o no ft h eo r i g i n a ld a t a s e t ( 3 ) k e r n e ls c a l i n g c u tc r i t e r i o nb a s e ds u p e r v i s e d d i m e n s i o n a l i t yr e d u c t i o n a l g o r i t h mi st h en o n l i n e a rg e n e r a l i z a t i o no fs c a l i n gc u tc r i t e r i o nb a s e ds u p e r v i s e d d i m e n s i o n a l i t yr e d u c t i o na l g o r i t h mu s i n gk e r n e lt e c h n i q u e w h e nt h en u m b e ro f o r i g i n a lf e a t u r e si sg r e a t e rt h a nt h en u m b e ro fs a m p l e s ，s c a l i n gc u tc r i t e r i o nb a s e d s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o n h a ss i n g u l a r i t yp r o b l e m , w h i l et h e p r o p o s e d a l g o r i t h mh a sn ol i m i t a t i o no ft h ei n p u tf e a t u r ed i m e n s i o n a p p l y i n gt h ep r o p o s e d m e t h o dt os a rt a r g e t r e c o g n i t i o n , t h ee x p e r i m e n t a l r e s u l t ss h o wt h e p r o m i s i n g p o t e n t i a li nt h ef i e l do fs a rt a r g e tr e c o g n i t i o no ft h ep r o p o s e dm e t h o d k e y w o r d s ：d i m e m i o n a l i t yr e d u c t i o n , s p e c t r a lf e a t u r e ，s p e c t r a lg r a p hc u tc r i t e r i o n , s a r t a r g e tr e c o g n l t i o n , h y p e r s p e c t r a lr e m o t es e n s i n gi m a g ec l a s s i f i c a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确地说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期：丝兰：! 三：! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本人授权西安电子科技大学图书馆保存学位论文，并同意将论文在互联网上 发布。 本人签名： 导师签名： 同期：兰璺：! 兰：! r 期：重璺二! 兰：竺 第一章绪论 1 1 1 研究背景 第一章绪论 1 1 研究背景和意义 目前，众多领域的数据获取具有如下特点：首先，对于一些领域一次实验的 费用十分昂贵，而对大量观察数据无法直接判断其价值；其次，两次观察之间不 独立或属性之间不独立；此外，噪音数据不一定独立于问题世界；但是，相对而 言，数据的存储比较便宜，所以人们不得不被动的记录所有的观察数据，这样的 后果就是数据的维数巨大【l 】。 如果将这些高维数据直接作为输入进行分类器训练，可能会带来两个棘手的 问题：( 1 ) 计算复杂度高：很多在低维空间具有良好性能的分类算法在计算上变 得不可行，此外一些分类算法的复杂度与数据特征维数相关吲；( 2 ) 分类器的泛化 能力低：在训练样本容量一定的前提下，特征维数的增加将使得样本统计特性的 估计变得更加困难，从而降低了分类器的推广能力或泛化能力。所以说，数据的 特征维数不是越多越好。一些特征之间会存在一定的相关性，这种相关性可能会 降低最终的分类精度，而且冗余的特征会增加运算量。此外，样本的本征维数很 可能远小于特征维数。因此有必要对特征向量进行维数约简1 2 儿引。 近年来，谱聚类( s p e c t r a lc l u s t e r i n g ) 方法【4 】【5 】【6 1 1 7 1 得到了突飞猛进的发展，并 且较现存方法表现出明显的优势。该类方法将聚类问题转化为谱图划分问题，进 而再转化为特征求解问题，所以实现简单，也不会陷入局部最优解。而且谱聚类 算法能识别非凸分布聚类，迎合实际应用，已成功应用于图像分割【8 j 、计算机视觉 h 和文本挖掘【9 】等领域。谱聚类算法只涉及到数据点的数目，因而避免了维数过高 所造成的奇异性问题。从谱聚类算法的实现过程可以看出，谱聚类和主分量分析 ( p r i n c i p a lc o m p o n e n t a n a l y s i s 。p c a ) t 1 0 1 有着相同的地方，两者均要进行特征分解， 在特征分解后，均得到包含原始数据最大特征信息的主分量。因此，可以从p c a 的角度来理解谱聚类【l 。谱聚类分解成两个步骤，一是通过使用某个相似性矩阵 的特征向量来得到数据点在低维空间的嵌入，从而获得更加紧致的聚类；二是使 用经典的聚类算法将谱嵌入后的数据点进行分组。谱聚类中的第一步和其他谱嵌 入方法，如多维尺度分析( m u l t i d i m e n s i o n a ls c a l i n g ，m d s ) 【1 2 l 、局部线性嵌入 ( l o c a l l yl i n e a re m b e d d i n g ，l l e ) 1 1 3 1 、等度规映射( i s o m e t r i c a lm a p p i n g ，i s o m a p ) 【1 4 1 、核主分量分析( k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ，k p c a ) 1 5 】一样都是建立 在特征分解基础上的，这个特征分解过程最终得到一个更能表示原始数据的低维 2 谱聚类维数约简算法研究与应用 空间【16 】【1 7 1 1 8 1 。 本论文的工作正是基于上述背景展开的，论文研究了几种基于谱聚类的维数 约简算法，并对其在s a r 图像目标识别、手写体数字识别、人脸识别和高光谱遥 感图像分类等方面的应用进行了研究。 1 1 2 研究意义 模式识别自诞生以来，在多方面的应用获得大量的研究成果。但是由于模式 识别涉及到很多复杂的问题，因此仍有许多问题有待深入研究。 模式识别的基本框架1 9 】【2 川如图1 1 所示。从该框架可以看出，模式识别过程 主要分为三部分：预处理，特征提取和选择，及分类器的设计。每一步的目的都 是为了提高最终的识别精度，而且每一步对结果的影响都非常大。 图1 1 模式识别基本框架l l 9 j 【2 0 1 预处理的目的是为了减少噪声，提取有用信息，并消除目标的方位变化对结 果的影响等，预处理方法包括去噪、分割、复原和归一化等。 特征提取和选择【l9 j 的目的是用某种方法把预处理后得到庞大的原始数据从模 式空间转换到特征子空间，使得在特征子空间中，数据具有很好的区分能力。特 征提取和选择对识别精度和稳定性的影响至关重要。特征提取( 或特征变换) 是 指针对数量可能很大的原始特征，通过映射或变换的方法抽取出能表示样本的少 数维特征。特征选择是指从一组特征中挑选出一些最有效的特征以达到降低特征 空间维数，提高特征辨别力的目的。特征选择所选择出来的特征通常是原始特征 集合的一个子集，这些特征都有明确的物理意义。常见的特征选择方法有：基于 遗传算法的特征选择【2 l j 、基于粗糙集理论的特征选择【2 2 】、基于神经网络的特征选 择1 2 3 】和基于关联规则的特征选择【2 4 1 。虽然特征选择方法能提取出具有明确物理意 义的特征子集，但是基于某种规则去掉的那些特征多数情况下也不是对结果毫无 贡献，所以特征选择之后的最优特征子集往往不能得到最佳识别精度。而特征变 换之后的特征通常是原始特征的某种组合，一个好的特征变换规则能得到使得识 别结果最佳的特征子集。本文的重心在于特征变换方法的研究，目的就是构造基 于谱聚类的特征变换方法，以提高后续分类识别精度。 分类器的设计是模式识别系统中继特征提取和选择之后的核心任务。虽然特 征提取和选择对分类结果影响较大，好的分类器设计和方法也会提高系统分类性 第一章绪论 3 能。目前，比较流行的分类识别方法包括最近邻和k 近邻【2 5 1 、决策树 2 6 l 、贝叶斯 分类器【2 7 1 、神经网络1 2 8 】和支撑矢量机 2 9 1 等。其中七近邻和支撑矢量机是本文后续 实验中用到的分类器。 k 近邻方法【2 5 ( kn e a r e s tn e i g h b o r , k n n ) 是c o v e r 和h a r t 于1 9 6 8 年提出的 一个非常简单直观的分类方法。如果一个样本在特征空间中的k 个最相似的样本 中的大多数属于某一个类别，则该样本也属于这个类别。最近邻方法为k 近邻方 法的特例。该类方法在分类决策上依据最邻近的一个或者几个样本的类别来决定 待分样本所属的类别。 支撑矢量机1 2 9 】【3 0 1 是由v a p n i k 等提出的一种机器学习方法。它以统计学习理论 为基础，最基本思想之一的结构化风险最小化原则( s t r u c t u r a lr i s km i n i m i z a t i o n , s r m ) 要优于传统的经验风险最小化原则( e m p i r i c a lr i s km i n i m i z a t i o n , e r m ) 。 由于s v m 拥有很好的泛化和推广能力，因此被广泛地应用于各个领域。 1 2 维数约简国内外研究现状 2 0 0 3 年n i p s 的一个w o r k s h o p 以特征提取与特征选择为主题作了广泛而深入 的讨论，汇聚了该领域的最新研究成果【3 1 1 。目前，已经有许多种维数约简方法， 分类有很多种，具体如下： ( 1 ) 按照实现的具体途径分为特征选择和特征变换； ( 2 ) 根据变换函数的形式分为线性方法和非线性方法； ( 3 ) 根据获得低维表示的方法不同分为投影方法和流形方法【3 2 】； ( 4 ) 根据是否考虑了已知样本的类别信息分为有监督维数约简方法【3 3 1 、无监 督维数约简方法和半监督维数约简方法i 川【3 5 】【3 6 1 。 在这些已有的降维方法中，p c a 和f i s h e r 线性判别方法( l m e a rd i s c r i m i n a t i o n a n a l y s i s ，l d a ) 【3 7 】是最著名，也是应用最广的线性降维方法1 2 0 1 。p c a 是基于k l 变换( 也称h o t e l l i n g 变换) 的，其主要目标是寻找在最小均方意义下最能代表原 始数据的投影方向，该投影方向是通过线性变换得到的一组最优的单位正交向量 基，这些向量的线性组合可以重构原始样本，并且重构后的样本和原样本之间的 误差最小。p c a 在许多模式识别应用中取得了较好的效果，但是由于它是一种无 监督的降维方法，不适用于反映样本之间的差异。相对于p c a 方法，l d a 是一种 有监督的降维方法，主要目标就是寻找在最小均方意义下，最能够分开各类数据 的投影方向，实现上是通过寻找一组线性变换以达到类内散度最小且类间散度最 大的目的。目前，l d a 是最基本也是应用最广的降维方法。但是l d a 的定义决定 了它的不足存在“奇异值”问题：当原始高维空间中的样本维数远大于样本 数，则l d a 中散度矩阵会出现奇异性。为了有效地解决l d a 的奇异性问题，学 4 谱聚类维数约简算法研究与应用 者们提出了多种解决方法，如：p c a + l d a 法【3 8 】【3 9 】和零空间法l d a m l 等。 线性的维数约简方法因为具有实现简单、计算效率高，并且能够保证发现嵌 入在高维输入空间中的线性子空间上的数据集的真实的几何结构【1 4 】等优点，被广 泛应用于各个领域。但是由于真实世界中多数数据都是非线性分布的，这使得以 上线性维数约简方法不能处理很复杂的真实数据，因而有必要展开对非线性维数 约简方法的研究。 对线性维数约简方法进行改进，使其能用于处理非线性数据，方法有不少， 目前常用的有【4 l 】：1 混合局部线性的方法：将全局非线性转换为局部线性，然后 通过组合局部线性来描述全局信息。这类方法的假设前提是：非线性高维数据是 局部线性的。2 核方法：用一个非线性核函数将原始数据映射到一个更高维的线 性特征空间，然后在该特征空间中执行相应的线性维数约简算法，从而得到数据 的低维表示。除了对已有线性算法进行改进和补充得到非线性维数约简算法，近 年来发展起来的基于流形学习的降维方法是一种从全新角度来解决高维数据的降 维问题的方法。 混合局部线性方法的思想接近于逼近算法，计算效率不高，而且多数方法都 使用e m ( e x p e c t a t i o nm a x i m i z a t i o n ) 算法进行学习，容易陷入局部极小。此外最 重要的是，如何将局部线性模型中获得的低维坐标组合在一个全局的低维坐标系 统中是该类方法必须面对的问题】。基于以上原因，混合局部线性方法的研究没 有像核方法那样成为研究的热点。 首先使用核方法解决非线性维数约简的研究是b e r n h a r ds c h 6 1 k o p f 等人【1 5 】于 1 9 9 8 年提出的核主分量分析方法( k e r n e lp c a , k p c a ) ，k p c a 首先使用一个非线 性函数将原始数据映射到一个更高维的线性特征空间，然后在这个特征空间中执 行p c a 。在算法的实现中，原始数据映射到更高维特征空间的过程只需通过计算 核函数的点积就可实现，不仅方便而且计算量小。核f i s h e r 判别分析方法( k e r n e l f i s h e rd i s c f i m i n a t i o na n a l y s i s ，k f d a ) 借鉴k p c a 的思想，用核方法成功地将f i s h e r 判别分析方法推广到了非线性领域。常用的核函数有：线性核函数、多项式函数、 径向基函数、动态核函数等。选择不同的核函数可构成不同的k p c a 或k f d a 方 法。面对不同的问题选择合适的核函数是一个难题，核函数中核参数的设置也是 一个需要考虑的问题。 基于流形学习的降维方法起源于2 0 0 0 年s c i e n c e 上面的两篇文章所提出的两 种降维方法：i s o m a p 1 4 】和l l e 13 1 ，分别由t e n e b a u m 和r o w e i s 提出。此外还有 拉普拉斯特征映射( l a p l a c i a ne i g e n m a p s ) 4 2 、h e s s i a n 局部线性嵌入( h e s s i a n - b a s e d l o c a l l yl i n e a re m b e d d i n g ，h l l e ) 【4 3 l 和保角映射算法d 4 等算法。谱聚类算法作为 流形学习的一种，也可在此基础上构造基于谱聚类的维数约简算法，如谱特征分 析( s p e c t r a lf e a t u r ea n a l y s i s ) 【4 5 l 。 第一章绪论 基于流形学习的降维方法的一个难点就是如何实现超越样本的扩展 ( o u t o f - s a m p l ee x t e n s i o n ) ，在已有的框架下，以上提及的基于流形学习的降维方 法只能通过n y s t r 6 m 公式来计算测试样本的低维嵌套【峒。c a l z a t e 等人提出可用 加权核主分量分析( w e i g h t e dk e r n e lp c a , w k p c a ) s l 4 7 1 1 4 8 1 框架来计算测试样本 的低维嵌套。在w k p c a 框架下，可以通过直接计算新的样本点在特征向量上的 投影得到。 这些基于流形学习的维数约简算法都是通过求解一个特征值问题来获得原始 高维数据的低维表示，算法实现简单，而且能够发现隐含的非线性流形，同时也 可避免局部极值问题】。基于流形学习的维数约简方法仍然处于发展阶段，很多 理论还不成熟，已有的算法也存在诸多问题，而且该类方法主要还集中在非监督 学习，在监督学习研究中，该类方法目前并不占明显优势。这些问题并未妨碍许 多学者对流形学习维数约简算法的兴趣，他们从不同的角度对已有算法进行分析 和总结，并提出改进。 随着维数约简方法理论研究的深入，其广泛应用于图像处理、手写体数据处 理【4 9 】、语音信号处理【5 0 l 、文本数据处理【5 1 1 、医学网、天文数据处理【5 3 】以及金融数 据处理【跏等领域。其中图像处理方面的应用还可细分为：s a r 图像目标识别【5 5 1 、 高光谱图像处理【5 6 】【5 刀、人脸识别删1 5 8 】、人脸表示【5 9 1 、图像检索例、三维动画处理 【6 l 】等方面。 1 3 论文的主要工作 本论文在模式识别基本框架下，以识别精度的提高为主要目的，针对维数灾 难问题，研究基于谱聚类维数约简算法，并结合国家自然科学基金项目和十五国 防预研项目，将所提出的方法应用于s a r 图像目标识别、手写体数字识别、人脸 识别和高光谱遥感图像分类中。 本论文的主要创新点如下： ( 1 ) 基于经典n j w 谱聚类算法构造了一种谱特征分析方法，在此基础上对 尺度参数进行研究，提出了一种基于多参数自调节谱聚类维数约简算法，并将其 应用于手写体数字识别和s a r 图像目标识别。多参数自调节谱特征与传统特征变 换方法得到的特征相比，提高了后续识别精度。此外，自调节参数避免了手动调 节全局尺度参数的麻烦，由于自调节尺度参数考虑了各个样本点自身的邻域统计 信息，比给所有的样本点赋予相同的全局尺度参数更合理。 ( 2 ) 在构造谱聚类图切判据的过程中加入已知类别样本点的类别信息，提出 了一种基于新的谱聚类图切判据标度切判据的监督维数约简算法。同时，为 了降低计算复杂度，提高算法的推广性能，在构造切判据的过程中只考虑肛近邻 6 谱聚类维数约简算法研究与应用 之间的类间和类内不相似性，这样能放松数据的类内方差，增大数据的类间边缘， 从而获得更合理的投影矩阵。从人脸识别及高光谱遥感图像分类实验结果可以看 出，基于局部标度切判据监督维数约简算法提取的特征能得到更好更稳定的识别 结果。在局部标度切判据监督维数约简算法基础上，借鉴最优维数判别分析方法 思想，提出了最优维数标度切判据分析方法。实验结果表明，最优维数判别分析 方法能够获得满意的结果。 ( 3 ) 基于标度切判据监督维数约简算法，使用核技术提出了一种核标度切判 据监督维数约简算法，从而扩大了其应用范围。当原始特征维数大于样本数时， 线性标度切判据监督维数约简方法会出现奇异问题，而该方法避免了此问题，对 原始数据的原始特征维数没有限制。将基于核标度切判据的监督维数约简方法用 于s a r 图像目标识别，实验结果验证了该方法在s a r 图像目标识别领域的应用潜 力。 本论文的主要内容安排如下： 第一章：介绍了本课题的研究背景及意义，概述了维数约简的研究现状，并 且概要地介绍了本文的主要工作和创新点。 第二章：介绍现有的具有代表性的几种维数约简方法。 第三章：基于经典n j w 谱聚类算法构造了一种谱特征分析方法，在此基础上 对尺度参数进行研究，提出了一种基于多参数自调节谱聚类维数约简算法，在部 分u c i 数据集上验证算法性能，并将其应用于手写体数字识别和s a r 图像目标识 别。 第四章：在构造谱聚类图切判据的过程中加入已知类别样本点的类别信息， 提出了一种基于标度切判据的监督维数约简算法。同时，为进一步提高算法的推 广性能及降低计算复杂度，结合局部化的七- 近邻图，提出了一种局部标度切判据 监督维数约简算法，并成功应用于人脸识别和高光谱遥感图像分类。在这一章中， 我们在所提出的算法基础上，研究了最优维数提取问题，提出了一种最优维数标 度切判据分析方法。 第五章：在标度切判据监督维数约简算法基础上，使用核技术提出了一种核 标度切判据的监督维数约简算法，从而扩大了其应用范围，并将其成功应用于s a r 图像目标识别领域。 总结和展望。总结全文并提出了值得进一步研究的方向。 第二章经典维数约简算法的研究 7 第二章维数约简算法的研究 2 1 维数约简基本概念 维数约简是指将样本从原始输入空间通过线性或者非线性映射到一个低维空 间，从而获得一个原数据集有效的低维表示【3 】1 3 2 】。获得的低维表示要尽量保留分类 信息和不损失后续分类性能。 维数约简问题可描述为 2 1 1 3 1 ：输入高维空间r r 中的一个k 维样本集 x = x l ，x 2 ，x ，找到一个映射函数：x j y ，其中y r a , d k ，得到该样本 集在低维空间尺d 中的表示y = y l , y ：，y ，与此同时尽可能地保持原高维数据 的几何结构信息。 按照具体实现途径，维数约简分为线性和非线性维数约简方法。常用的线性 维数约简方法有p c a ，l d a ，奇异值分解( s i n g u l a r v a l u ed e c o m p o s i t i o n , s v d ) 【6 2 】 等等。这类变换方法对提取的高维特征向量进行正交变换，可以证明正交变换能 消除原始向量各分量之间的相关性，并进行降维。以上几种方法都属于线性变换 方法，只能提取数据的线性成分。而实际上，真实世界中的数据大部分都是非线 性分布的，这使得以上方法不再适用。非线性维数约简方法有k p c a ，k f d a ， l l e i l 3 1 ，i o s m a p 1 4 1 等。 在上述提及的非线性维数约简方法中，k p c a 和k f d a 分别是用核方法对p c a 和l d a 方法的非线性推广，而l l e 和i o s m a p 则是基于流形学习的非线性降维 方法，其中与i o s m a p 有关的线性方法是m d s l l 2 】。本章中我们将仔细讨论这几种 方法。 2 2p c a 和k p c a p c a 8 】【2 0 】的目标是在低维子空间表示高维数据，使得在误差平方和最小的意义 下低维表示能够更好地描述原始数据。它是在数据空间中找出一组向量来解释数 据的方差，将数据从原来的k 维降到d 维( k d ) 。它是根据k - l 变换从最大信 息压缩方向获得模式在低维空间的信息表达，所以用p c a 方法所获得的特征空间 就是原模式空间的一个最优低维逼近。 p c a 的基本原理为：根据k l 变换在测量空间中找到一组正交向量，这组数 据能最大化表示出数据的方差，将原样本向量从尺维空间投影到这组正交向量张 成的d 维子空间上，其投影系数构成样本的特征向量，从而完成了维数的降维。 p c a 的主要步骤如表2 1 所示。 8 谱聚类维数约简算法研究与应用 表2 1p c a 算法流程 输入 原始数据样本集 x 。，x ：，x 肌f ，n 为样本数，k 为原始特征维数。 步骤( 1 ) 建立相关矩阵，根据k - l 变换求矩阵的特征值和特征向量。利用标准化值 计算变量之间的相关系数，可建立k 阶相关矩阵，由该矩阵可获得特征值 凡( f = l ，2 ，k ) ，k 个特征值对应k 个特征向量，每个特征向量包括k 个分量。 ( 2 ) 选取主分量。计算第f 个主分量对总方差的贡献率，按贡献率由大到小的 顺序对k 个主分量进行排序，贡献率最大的主分量称为第一主分量，其次的分量称 为第二主分量，依此类推。选取主分量的个数d 取决于主分量的累计方差贡献率， 通常使累计方差贡献率大于8 5 。所需的主分量数能够代表x 个原始变量所能提供 的绝大部分信息。 ( 3 ) 建立主分量方程，计算主分量值。各主分量值方程为q = 罗a ，x ，其中 石。 口，( - ，= l ，2 ，k ) 为对应于特征值a ，的特征向量的分量，x ，为各分量的标准化数值。 计算出所需要的各主分量值，形成新的样本集。 输出 新的样本集 y ，y ：，y ) 。d ，d 为输出的特征维数。 k p c a 是b e r n h a r ds c h 6 1 k o p f 等人【l5 j 于1 9 9 8 年提出的，是在p c a 的基础上加 入核方法来提取数据的非线性成分。k p c a 方法在特征空间内具有与p c a 相同的 数学和统计特性，如提取的各主分量互不相关；主分量都能够表示原始数据的最 大方差：用主分量进行样本数量重构时均方误差最小等等。除此之外，k p c a 提取 的特征具有比p c a 提取的特征更好的稀疏性【6 3 1 。 k p c a 算法具体推导【l5 l 如下： 设输入的数据集为f x 。l ! ! ! r k ，用某种核函数映射到高维特征空间，即： ：，r k 一 ( x ，) ) o f ( 2 一1 ) 且假设：。( x ，) = o 。 _ ，= l、， 定义该数据集在高维特征空间中的协方差矩阵为： c = 丙l 乙两n ( x 弘( x ，) r 对其进行特征值分解司得： c v = a v = 丙1 善n ( 西( x 。) rv 卜( x 。) 则v 跏刀 o ( x 。) ，( x ) 就是需要的非线性主方向。 令v = 口，( x ，) ，则可以得到如下公式： a 口。( ( x 。) ( x 。) ) = 寺q ( ( x 。) ( x ，) ) ( ( x ，) ( x ，) ) t = l vj = l f = l 。 ( 2 - 2 ) ( 2 - 3 ) ( 2 - 4 ) 第二章经典维数约简算法的研究 9 其中，点积( ) 就是核矩阵元素( k ) l f = ( ( x ) ( x j ) ) ，代入公式( 2 4 ) 得到 n z k a = k 2 a 。由于k 是对称矩阵，且有可以张成整个空间的一系列特征向量， 因此上式可以简化为n z a = k a 。由此，我们可以得到第f 个数据点( x ，) 在第k 个 主分量上的投影： wwk ( x ，) v = ( x ，) a j ( x ，) = a j ( ( x ，) ( x ，) ) = 口j ( k ) f ( 2 5 ) = lj 霉lj l 由公式( 2 - 5 ) 我们可以看出，只要核函数( k ) 矿= ( ( x 。) ( i ) ) 定义恰当，就可 以得到所有数据点的各个核圭分量。 2 3l d a 和k f d a l d a 2 0 1 1 3 7 1 是在f i s h e r 判别准则函数取极值的条件下，求得一个最佳鉴别方法， 然后将数据从高维特征向量投影到该最佳鉴别方向上，构成一维的鉴别特征空间， 于是数据分类可在一维空间中进行。对于c 类问题，就需要c 一1 维向量张成的最佳 鉴别空间。 对于一个c 类问题，输入个k 维样本x = x 。，x ：，x 。置，吩为样本子集x ， 的样本个数。 定义类内散度矩阵s 。和类间散度矩阵s 。分别为： s 。= z s ， ( 2 - 6 ) s 。= 吩( m ，一m ) ( m 。一m ) r ( 2 7 ) 其中一2 荟( x m f ) ( x 吨) ，为第f 类样本的类内散度矩阵一2 吉委x 为第f 类 样本的均值向量，m 2 砉荟x ，是所有样本的均值向量。 将k 维样本投影到c 一1 维子空间的过程为： y = w 7 x ( 2 8 ) 其中，w 为投影矩阵，y 即为投影之后新的样本。这些新的样本在c 一1 维子空间 均值向量和散度矩阵分别为： 氲2 寺磊y ( 2 9 ) m = 二面， (2-10一)n= 一7 m ；z - l 智 、7 w = z ( y - 面，) ( y 一面，) r ( 2 1 1 ) 1 0 谱聚类维数约简算法研究与应用 = q ( 面。一面) ( 面，一面) r ( 2 1 2 ) t = l 公式( 2 6 ) 和( 2 1 1 ) 及公式( 2 - 7 ) 和( 2 1 2 ) 之间的关系为： s 。= w 。s 。w( 2 1 3 ) s 6 = w 。s 6 w( 2 1 4 ) l