（计算机应用技术专业论文）非监督特征约简算法的研究与应用.pdf

摘要 在机器学习、模式识别、信息检索和生物信息等很多领域人们都面临海量的 高维数据，由此引发维数灾难问题。特征约简旨在解决上述难题，其任务是将原 始特征空间映射到一个低维空间，以期在降低维数的同时j 保持原空间的重要信 息。特征约简可大致分为特征抽取和特征选择两部分。特征抽取试图获得原始特 征的线性或非线性组合，以期去除特征间的冗余性；特征选择试图选择与学习任 务最相关的特征，以期去除噪声特征。由于在非监督背景下缺少类别信息，使得 特征约简尤其是特征选择任务，变得异常困难。 流形学习是特征抽取的一个重要分支。本文提出了一种局部线性镶嵌 ( l o c a l l yl i n e a ri r a a y i n g ，l l i ) 方法。l u 是一种流形学习方法，该类方法假设原始 高维空间分布在或近似分布在一个低维非线性流形之上。l l i 利用分而治之的策 略，将高维空间中的各个线性区域进行局部嵌入和全局拼接。该算法可以在很大 程度上改善流形学习算法的时间复杂度和鲁棒性，具体表现在：第一，l l i 的时 间复杂度与样本点数目成线性关系；第二，l l i 可以适用于任何非凸的数据集； 第三，l l i 有很高的鲁棒性，能够很好的工作于存在异质噪声或同质噪声的数据 集。基于仿真数据和真实人脸数据的实验证实了l l i 的上述特点。 针对特征选择任务，因为原特征集中存在大量噪声特征，这些特征会严重干 扰合理的测度( 即中肯的测度) ，使得特征空间变得不中肯。当前大部分非监督 特征选择算法因为缺少测度不变的性质，在强非中肯空间中其效果会很差。本文 提出了一种处理非中肯空间的测度不变性模型，该模型基于以下重要观察：如果 指导非监督特征选择的统计量在测度缩放时保持不变，那么特征选择模型的解也 将是不变的；如果这个模型在一个中肯的特征空间中可行，它也将在由于测度缩 放后得到的非中肯空间中可行。本文从理论上证明了该模型的测度不变性，基于 仿真数据和真实文本数据的实验结果证实了该模型的有效性。 关键词：非监督学习特征约简特征抽取特征选择流形学习局部线性镶嵌 测度不变性 a bs t r a c t i nm a n ya r e a so fm a c h i n el e a r n i n g ，p a t t e r nr 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 d b i o i n f o r m a t i c s ，o n ei so f t e nc o n f r o n t e dw i t ht h em a s s i v eh i g h d i m e n s i o n a ld a t a s e t , w h i c hl e a d st ot h ec u r s eo fd i m e n s i o n a l i t y t h ec o m p u t a t i o n a lc o m p l e x i t yo fl e a r n i n g m a c h i n e si nh i g h - d i m e n s i o n a lf e a t u r es p a c ei sv e r ye x p e n s i v e i na d d i t i o n , n o i s y f e a t u r e sw i l lr e d u c et h ep e r f o r m a n c eo fl e a r n i n ga l g o r i t h m s t os o l v et h e s ep r o b l e m s ， f e a t u r er e d u c t i o nm a p st h eo r i g i n a lf e a t u r es p a c ei n t oal o wd i m e n s i o n a ls p a c e ，i n w h i c ht h ei m p o r t a n ti n f o r m a t i o nf o rt h ef o l l o w i n gl e a r n i n gt a s k si sp r e s e r v e d f e a t u r e r e d u c t i o nc a nb eb r o a d l yd i v i d e di n t ot w oc a t e g o r i e s ：f e a t u r ee x t r a c t i o na n df e a t u r e s e l e c t i o n f e a t u r ee x t r a c t i o nt r i e st oo b t a i nal i n e a ro rn o n l i n e a rc o m b i n a t i o no f o r i g i n a lf e a t u r es e ta n dd e c o r r e l a t et h ed e p e n d e n c ya m o n gf e a t u r e s f e a t u r es e l e c t i o n t r i e st oi d e n t i f ya n dd e p r e s st h ef e a t u r e st h a ta ren o td i s c r i m i n a t i v et ot h er e a lc l a s s e s i nt h eu n s u p e r v i s e db a c k g r o u n d ，d u et ot h ea b s e n c eo fc l a s si n f o r m a t i o n , f e a t u r e r e d u c t i o n , e s p e c i a l l yf o rf e a t u r es e l e c t i o n , i sar e a lc h a l l e n g e m a n i f o l dl e a r n i n gi sa l l i m p o r t a n t b r a n c h o ff e a t u r ee x t r a c t i o n i nt h i s d i s s e r t a t i o n , w ep r o p o s ean o v e lm a n i f o l dl e a r n i n gm e t h o d ，c a l l e dl o c a l l yl i n e a r i n l a y i n g ( l l i ) t h eb a s i ca s s u m p t i o no f m a n i f o l dl e a r n i n ga l g o r i t h m si st h a tt h ei n p u t d a t al i eo no rc l o s et oal o w d i m e n s i o n a ln o n l i n e a rm a n i f o l d b y a d o p t i n g d i v i d e a n d c o n q u e rs t r a t e g y , l l ii n s te m b e dv a r i o u sl o c a ll i n e a ra r e a sa n dt h e ni 1 1 1 a y t h e mg l o b a l l y l l ig r e a t l yi m p r o v et h et i m ec o m p l e x i t ya n dr o b u s t n e s so fm a n i f o l d l e a r n i n ga l g o r i t h m s f i r s t l y , i t st i m ec o m p l e x i t yi sl i n e a ri nt h en u m b e r o fd a t ap o i n t s ； s e c o n d l y , l l io v e r c o m e sp r o b l e m sc a u s e db yt h en o n - u n i f o r ms a m p l ed i s t r i b u t i o n t h i r d l y , l l ii sr o b u s tt ob o t hh o m o g e n e o u sa n dh e t e r o g e n e o u sn o i s e w ed e m o n s t r a t e t h ee f f i c i e n c ya n de f f e c t i v e n e s so fl l i b ys y n t h e t i ca n dr e a l - w o r l df a c ed a t a s e t s a sf o rf e a t u r es e l e c t i o n , i nt h eo r i g i n a lf e a t u r es e t ，t h e r ea r eal a r g en u m b e ro f n o i s yf e a t u r e s ，w h i c hw i l ls e r i o u s l yd i s t u r bt h er e a s o n a b l ed i s t a n c em e t r i c ( o r r e l e v a n t m e t r i c ) m o s te x i s t i n gf e a t u r es e l e c t i o nm e t h o d sl a c km e t r i ci n v a r i a n c ea n dh e n c ea r e s u s c e p t i b l et os t r o n g l yi r r e l e v a n td i s t a n c em e t r i c s i nt h i sd i s s e r t a t i o n , w ep r o p o s ea m e t r i ci n v a r i a n ta p p r o a c ht od e a l i n gw i t hi r r e l e v a n td i s t a n c em e t r i c s t h ei m p o r t a n t o b s e r v a t i o ni st h a t ，i fas t a t i s t i cg u i d i n gu n s u p e r v i s e df e a t u r es e l e c t i o ni si n v a r i a b l e u n d e rp o s s i b l e 地t r i cs c a l i n g ，t h es o l u t i o no ft h ef e a t u r es e l e c t i o nm o d e lw i l lb e i n v a r i a b l e ；h e n c e ，i ft h i sm o d e lc a l lw o r ko nar e l e v a n tf e a t u r es p a c e ，i tw i l ls t i l lw o r k o na n yi r r e l e v a n tf e a t u r es p a c et r a n s f o r m e df r o mt h er e l e v a n to n e b ym e t r i cs c a l i n g t h e o r e t i c a lj u s t i f i c a t i o no ft h ei n v a r i a n c eo fo u rm o d e li sd e m o n s t r a t e d e x p e r i m e n t s o ns y n t h e t i ca n dr e a l w o r l dt e x td a t a s e t sa l ea l s op r o m i s i n g k e y w o r d s ：u n s u p e r v i s e dl e a r n i n g ，f e a t u r er e d u c t i o n ，f e a t u r ee ) 【仃a c t i o 玑 f e a t u r es e l e c t i o n , m a n i f o l dl e a r n i n g ，l o c a l l yl i n e a ri n l a y i n g ，m e t r i ci n v a r i a n c e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫盗叁堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：弓彩朋岛 签字日期： 渺宫年月占日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞蕉茎有关保留、使用学位论文的规定。 特授权苤鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：卯g 年 导师签名：饭触、坟j 签字日期：枷占年易月厶日 第一章绪论 1 1 研究背景和目的 第一章绪论 在机器学习、模式识别、信息检索和生物信息等领域中人们都面临海量的高 维多模( m u l t i m o d a l ) 数据，由此引发维数灾难问题，其主要表现在：一方面，高 维空间中的学习器计算复杂性高；另一方面，高维空间存在很多噪声特征，影响 学习器的准确率。特征约简旨在解决上述难题，其任务是给定原始特征集，从中 选择一些重要特征( 原始特征子集或特征变换后的新特征) 以减少特征数量，同 时尽量保留学习任务所需要的信息。 特征约简可大致分为特征抽取和特征选择两部分。特征抽取试图保持原始高 维特征空间的几何和拓扑结构，将原空间映射到一个低维空间，映射后的特征是 原始特征的某种组合( 线性组合或非线性组合) ，以期去除特征间的冗余性。特 征选择试图依据某个评价函数从原始特征集中选择一部分最能反映类别统计特 性的相关特征，以期去除与类别非相关( 噪声) 特征。 在非监督背景之下，由于缺少类别信息，这使得特征约简任务变得很难。尤 其当进行特征选择时，去除与类别不相关特征更是一大挑战。本文将深入研究非 监督特征约简，旨在设计新颖的特征抽取和特征选择算法。 1 2 研究现状 1 2 1 特征抽取研究现状 在机器学习，神经计算和数据挖掘等很多领域都将遇到高维数据；但这些高 维数据的内在结构通常可以由少数几个自由度来刻画，这些自由度可以表示成一 个低维空间。比如，一组，l n 的人脸( 同一个人) 灰度图像，其内在维度可以由 拍摄这组图像的摄像机的三个自由度( 人脸左右朝向、上下朝向和光照强度) 决定。为了发现高维数据空间的内在低维结构，很多线性和非线性算法被提了出 来。 经典的线性特征抽取方法，如主成份分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ， p c a ) 】和多维尺度分析( m u l t i d i m e n s i n a ls c a l l i n g ，m d s ) 1 2 ，只能考察欧氏空间结 构，即线性结构，不能有效发现输入数据的非线性内在结构【3 】。另外一些非线性 第一章绪论 映像算法，比如自组织映像( s e l f - o r g a n i z i n gm a p s ，s o m ) 阳、主曲线法( p r i n c i p l e c u r v e s ) t 5 】和拓扑表示网络( t o p o l o g yp r e s e r v i n gn e t w o r k s ) 【6 】，可以发现非线性结 构，但这些算法没有给出全局的优化函数，又涉及很多的参数，并且只能处理较 低维的输入数据【3 】。为了克服以上弱点，一些经典的流形学习方法，如等距映射 算法( i s o m e t r i cf e a t u r em a p p i n g ，i s o m a p ) p j ，局部线性嵌k 。( l o c a l l yl i n e a r e m b e d d i n g ，l l e ) 1 8 和拉普拉斯特征映像( l a p l a c i a ne i g e n m a p ) 【9 】被提了出来。这些 流形学习算法的基本假设是输入数据分布在( 或大致分布在) 一个低维非线性流 形之上。 但是仍然存在着一些严重的障碍，使得这些流形学习算法不能很好的应用到 现实世界中。首先，现有的算法时间复杂性都很高，至少是的二次方时间的 复杂度( 是数据集的数据数目) ；其次，对于非凸情形下的样本分布，现有的 某些算法不能有效工作。在这种情况下，邻域点数k 的选取就成了困难。文献 11 】 中报道i s o m a p 并不能正确处理样本为非凸( 比如有洞的样本) 的情况。第三， 大部分现有的算法不能正确处理存在异质噪声( 即标准差有上下浮动的噪声) 的 样本。 最近，一些旨在改善流形学习算法时间复杂度和鲁棒性的的算法被提了出 来。锚点集等距映射算法( l a n d m a r ki s o m a p ，l i s o m a p ) 【1 0 】着眼于利用锚点集及斐 波纳契堆的优化，其时间复杂度可低于的二次方。l i s o m a p 可以很好的运行 在“干净 的仿真数据上，但在含有噪声数据的情况下，某些噪声可能会被认为 是锚点，从而导致全局嵌入结构的扭曲。改进的局部线性嵌入算法( m o d i f i e d l o c a l l yl i n e a re m b e d d i n g ，m l l e ) i l l 利用多个局部权值向量来改进l l e 算法，获 得了较好的嵌入效果。鲁棒局部线性嵌入( r o b u s tl o c a l l yl i n e a re m b e d d i n g ， l l e ) t 1 2 】和后继拉普拉斯特征映像f s u c c e s s i v el a p l a c i a ne i g e n m a p s ) ”】可较好工作 于含有大量噪声样本点的流形。但是，上述这三个算法是在牺牲了复杂度和增加 了额外的参数的前提上来提高算法的性能。局部线性模型全局调和算法( g l o b a l c o o r d i n a t i o no f l o c a l l yl i n e a rm o d e l ) u 4 j 基于混合因子分析( m i x t u r ef a c t o r a n a l y s i s ，m f a ) 15 】提出了一个全局优化函数，但是这个优化函数没有一个闭形式 的解析解，于是求解过程就涉及到期望最大化( e x p e c t a t i o nm a x i m i z a t i o n ，e m ) h 6 算法，e m 算法的计算复杂度高且容易收敛到局部最优。局部线性调和法( l o c a l l y l i n e a rc o o r d i n a t i o n ，l l c ) 册给出了一个有解析解的全局优化函数，但这个优化 函数对于流形学习的学习任务未必是中肯的。这是因为l l c 用到和l l e 一样的 局部线性拟合误差作为指标来计算全局嵌入，据l l e 的作者所说，这种拟合误 差在有些情况之下不能保持局域几何结构的完整信息。局部切空间排列算法 ( l o c a l l yt a n g e n ts p a c e a l i g n m e n t ，l t s a ) 【1 8 】对每一个点建立了一个切空间的近似 2 第一章绪论 解，然后这些切空间通过一组优化的仿射变换来得到全局嵌入。l l c 和l t s a 都 可以很有效地解决存在洞的流形嵌入问题，但这两种算法都对异质噪声敏感，比 如在存在噪声点的情况下，l t s a 的仿射变换不同于正交变换( o r t h o g o n a l t r a n s f o r m a t i o n s ) ，在真实的物理世界中就会存在问题。并且，这两种算法的约束 条件使得它们不能保持测地线距离。 1 2 2 特征选择研究现状 特征抽取算法在一定程度上取得了成功，它们可较有效的去除特征之间的冗 余性。但特征选择算法还不能很好的处理那些噪声特征( 即与真实类别不相关的 特征) 。另外，虽然特征抽取方法可有效去冗余，但去冗余算法却不能同时去除 噪声特征。在非监督背景下，由于缺少类别信息，去除噪声特征仍然是一大挑战。 在噪声环境下，导致非监督学习效果下降的主要原因是距离测度( 或者相似 性测度) 不能有效地反应出真实类别间的关系。一个典型的例子是，假设文本的 真正的类别是由一小部分关键词确定的，而使用空间向量模型( v e c t o rs p a c e m o d e l 。v s m ) 表示的词汇集合包括了很多与真正类别无关的“垃圾”词。在这种情 况下，“垃圾”词经常会严重干扰由关键词所确定的合理的距离测度值，从而引起 了不佳的聚类效果。 现有的大部分非监督特征选择算法可以大致分为两类：包装器和过滤器【l 圳。 包装器方法调用学习算法来评估每个特征( 子集) 的效果；迭代地在候选的特征 子空间中划分数据；然后根据某些标准选择最“相关”子空间。如果聚类效果和特 征选择能够迭代地相互促进，那么包装器策略甚至可能在初始的距离测度值与真 实类别无关的情况下可行。但是这种假设缺少有力的理论证明，且并不为实验所 支持。过滤器策略不关心接下来的学习算法，而只评价每个特征( 子集) 的中肯 程度，且相应的选择标准要与类别信息无关而从“第一原则”构造得来。假设给定 一个中肯的距离测度，那么可以期望现有的过滤器统计量能够较好的除噪。但是， 在强非中肯距离测度之下，大多数过滤器统计量因为缺少测度不变的性质，其结 果会很差。 对于包装器方法，文献 2 0 提出一个一般化的特征选择方法用于肛均值聚类 中。文献 2 1 研究了基于分散程度和最大似然为标准来评价候选特征子集的特征 选择框架。文献 2 2 以f i s h e r 判别式相关的分数为基础，通过权重赋予给不同组 的特征来进行特征选择。文献 2 3 中提出了一种利用混合模型使得特征选择与聚 类同时进行的方法。 在文本背景下，已经有很多过滤器方法被提出。词汇强度( t e r ms t r e n g t h , t s ) 幽】基于一个词出现在相关文本的上半部分的情况下同时又出现在下半部分的 第一章绪论 条件概率。熵排序( e n t r o p y b a s e dr a n k i n g ，e n ) 【2 5 】测量词被移除后熵的减少程度。 词汇贡献( t e r mc o n t r i b u t i o n , t c ) 2 6 】计算每个词对文本相似度的贡献。在更一般 的背景下，对于多模聚类，文献 2 7 提出不同的特征子集和类别数目通过边缘似 然函数和交叉验证似然函数求得。拉普拉斯分( l a p l a c i a ns c o r e ，l s ) 幽j 通过一种测 量局部保持能力的统计量来评价特征的中肯性。谱分解特征选择框架( s p e c t u r a l f e a t u r es e l e c t i o n , s p e c ) 网一般化了拉普拉斯分的概念，给出了带有惩罚项的拉 普拉斯以及一系列的排序函数。 除了以上两种方式，测度学习【3 0 】1 也试图学习中肯的距离测度。但是，在非 监督的背景下测度学习必须依赖于很强的假设条件。 1 3 本文结构 依据本论文两方面的研究内容( 特征抽取和特征选择) ，安排论文结构如下： 第一章介绍特征约简的研究背景、目的，并且综述了目前特征抽取和特征 选择两个领域的研究现状。 第二章分别介绍了特征抽取和特征选择两个领域的经典算法。关于特征抽 取，首先介绍了传统的线性特征抽取方法，接着介绍了几种经典流形学习方法， 该类方法是特征抽取目前重要的研究分支：关于特征选择，首先介绍了包装器方 法，然后介绍了几种过滤器方法。 第三章提出了局部线性镶嵌算法，介绍了该算法框架的各个部分，借助理 论证明和大量实验说明了l l i 可以改善流形学习方法的计算复杂性和鲁棒性。 第四章提出了测度不变性特征选择模型，该模型旨在解决由噪声特征导致 的不中肯特征空间问题。给出了相关定理，证明了该模型的测度不变性，然后通 过大量基于仿真数据和真实文本数据的实验证实了该模型的有效性。 第五章对全文的研究工作进行了总结，并且对未来的研究工作的方向提出 了计划和展望。 4 第二章相关工作 2 1 特征抽取相关工作 2 1 1 线性方法 2 111 主成分分析 第二章相关工作 p c a 的基本思想是：将数量较多的原始的相关变量转换为数量较少的不相 关变量。通常的做法是将原始变量进行线性组合为若干综合变量，这些综合变量 之间不相关，并且尽可能表示原始变量包含的信息，选取最大的几个主成分进行 分析，这样就可以在尽可能少损失原有信息的基础上，降低数据的维度，提高运 算的效率。 p c a 数学模型如下【1 】： 设有，z 个样品，每个样品观测p 项变量：五，五，x 。，得到原始数据资 料矩阵： 其中x ，= x l i x 2 i ： x n “ x = x a l 而2 恐1x z z l2 i = 1 ，p 五p j c 2 p ： 全( x l ，五，4 ) 设f = q 五+ 口2 五+ + 口p x p 全口，其中口= ( 口l ，口2 ，口p ) ， x = ( x i ，五，巧) ，求主成分就是寻找x 的线性函数口公使相应的方差最大， 且满足a a = 1 ，即： v a r ( a x ) = e ( a x e 公) ) x e 0 公) ) 7 = a e ( x - e x ) ( x e x ) a = a z a 设协方差矩阵的特征根为 如以 o ，相应的单位特征向量为 “l ，“2 ，“p ，令 第二章相关工作 定义 u 全( ，“2 ，“p ) = = u 五0 o +。 以 u ：p 丑吩彬 i = i 上述推导表明：五，五，x 。的主成分就是以的特征向量为系数的线性 组合，互不相关，方差为特征根。 p c a 对椭球状分布的样本集有较好的效果，学习得到的主方向就是椭球的 主轴方向。该算法是一种非监督的算法，可以找到能最好的代表所有样本的方向。 2 1 1 2 经典多维尺度分析( c m d s ) 经典多维尺度分析( c l a s s i c a lm u l t i d i m e n s i o n a ls c a l i n g ，c m d s ) 研究这样的问 题：已知n 个样本点，每个样本点都可以表示为欧氏空间中的一个点。假设已知 研究样本点两两间的相异性度量，求出这刀个样本点在该空间的散布图，使图中 点间的欧氏距离与已知的相异性度量吻合得尽可能好。 c m d s 的数学模型【2 】： 假设d = 【嘭 。是n x n 维的距离矩阵，在d 维空间中求，z 个点五，恐， 使得n 个点的距离与矩阵d 中的距离在某种意义下尽量接近。设求得的n 个点为 x t ，x 2 ，x n ，表示为： 石= ( 五，恐，毛) 1 则称x 为距离矩阵d 的一个低维嵌入，由这n 个点之间的距离构成的距离阵 称为d 的拟合距离阵西。为证明方便，先引入中心矩阵的概念，其定义如下： 设中心矩阵日：l 一三以，其中厶是一个以刀维的单位矩阵，以是一个所有 元素均为1 的，z 刀维矩阵。令彳= ，其中勖= - 三2d 扩；b = h a h ，则b 中 的一个元素由下式给出： 岛= q ，一i 善n 一i 善n + 专喜喜 6 p p p 咖哆：忉 第二章相关工作 定理2 - 1 ：假设矩阵曰的p 个非零特征值a 五乃 o ( 以+ 。= 以= o ) 对应的特征向量为五，五，o9 t ，即有 b x i = 五置 ( 公式2 1 ) 若墨o = l ，2 ，p ) 满足，五r 五= 五，令石r = ( 五，置，x 。) ，则x r 是原始距离 矩阵d 的一个低维嵌入。 c m d s 通过计算高维空间中样本之间的相似性，并把这种相似性尽可能的在 低维空间得到保持，通过这种表示空间的转换，能有效降低高维空间中的数据表 示，并有可能帮助识别那些影响向量问相似度的潜在因素。 2 1 1 3 线性方法小结 作为最经典的线性流形学习算法，p c a 和c m d s 思路直观简洁，有严格的 数学基础，编码实现简单，可以确保发现处于高维向量空间的线性子空间上的数 据集的真实几何结构，在工程、化学和医学等科学研究中有着广泛的应用并取得 较好的实际效果。但是这类算法的线性本质使其无法解决高维空间的非线性流形 学习问题。 2 1 2 非线性流形学习方法 2 1 2 1 等距映射算法( i s o m a p ) 等距映射算法( i s o m e t r i cm a p p i n g ，i s o m a p ) 是一种全局优化算法，建立在 c m d s 基础之上。其基本思想是当数据集的分布具有低维嵌入流形结构时，可以 通过保距映射获得观测空间数据集在嵌入空间的表示。为此，算法利用样本间的 测地线距离来替代c m d s 中的欧氏距离，试图保持数据的内在几何特性，从而 使样本之间内部的距离信息在从高维到低维的流形学习过程中能够得到最大的 重构和恢复。 i s o m a p 存在两个前提假设：1 高维数据中的低维流形与欧氏空间的一个子 集是整体等距的；2 与数据所在的流形等距的欧氏子空间的子集是一个凸集。 算法的关键问题是计算远点( 非邻域点) 之间的测地线距离。对于邻域点， 由输入空间可直接得到其测地线距离( 即以欧氏距离表示) ；对于非邻域点，其 测地线距离可近似为最短路径上的一系列邻域点的测地线距离之和。 i s o m a p 算法的步骤如下【1 9 】： 1 构造邻域图：可以采用k 邻域或s 邻域，以占邻域为例。将与当前样本 点的距离小于固定邻域半径占的所有点都认为是样本点的邻域点，则根 7 第二章相关工作 据输入空间x 中每两个样本点间的欧氏距离可以确定流形膨上点之间 的邻域关系。这些样本点之间的邻域关系通过一个加权无向图g 来表 示，邻域点之间的权为距离d x ( f ，) ； 2 估算点之间的测地线距离：将流形膨上点之间的测地线距离用图g 上 的最短路径距离作为近似估计。具体做法如下：若初始时点i 和点，之 间存在连线，则d o ( f ，) = 以( f ，) ；否则d o ( f ，j ) = 0 0 。对所有的样本点 k = 1 ，2 ，n， 需要依次更新d o ( f ，) 的值： d o ( i ，歹) = m i n d c ( f ，) ，d o ( i ，k ) + d o ( k ，) ) ，这样最终得到的距离矩阵 p g ( f ，) = 如( f ，) ) 表示了图g 中每两点之间的最短距离； 3 构造低维嵌入：将c m d s 算法应用于最短距离矩阵d g ( f ，j ) = d g ( f ，) ， 构造d 维欧氏空间中的嵌入】，这个嵌入空间能够最大限度的保持流形 的内在几何特征。则d 维嵌入向量y ，的第p 个分量等于名，嘭，其中五， 是矩阵r ( d g ) 的第p 个特征值( 特征值已按降序排列) ，吃是第p 个特 征向量的第i 个分量。 i s o m a p 算法中使用d i j k s t r a 算法所有样本点之间的测地线距离的时间开销为 o ( n 2l o g ( n ) ) ，最后矩阵的特征值求解过程的复杂度为o ( n 2 ) ，因此i s o m a p 算 法的总体复杂度近似为o ( n 2l o g ( n ) ) 。 2 1 2 2 局部切空间排列法( l t s a ) l t s a 是一种基于切空间的流形学习方法。它通过逼近每一样本点的切空间 来构建低维流形的局部几何；然后利用局部切空间排列求出整体低维嵌入坐标。 l t s a 方法的主要思想是找出每个数据点的邻近点，用邻域中低维( 如d 维) 切空 间的坐标近似表示局部的非线性几何特征；再通过变换矩阵将各数据点邻域切空 间的局部坐标映射到一个统一的全局坐标上，从而实现数据维数约简，即从d 维数据中得到一个全局的d 维坐标。l t s a 方法的主要步骤如下： 1 构造局部邻域，对数据集x = x l ，x 2 ，x n r d ) 中的每一个数据点玉的 近邻点x j ( k 邻域) ( i = 1 ，n ；j = l ，k ) ，构成邻域置= “。，薯：，) ； 2 局部线性拟合，在每个数据点五的邻域内选择一组正交基q 构成薯的d 维切空间，计算邻域中的每个点x u ( j = 1 ，k ) 到切空间上的正交投影 秒；d = 醇( 嘞一五) 其中：为邻域内的均值；q 通常取置的前d 个最大 的左奇异向量； 3 将局部坐标转换为局部坐标，对每个邻域的局部切空间坐标 只= 研n ，绣n ，磁。】o = l ，) ，构造转换矩阵厶= 霉酵r 叔d 。通过 m i n z i iz ( 1 一e e r k ) 一厶岛屺的求解，得到行向量为正交的低维全局坐标 第二章相关工作 映射丁= 巧，乞，f d 】r 出d 。其中：鲈是谚的广义m o o r - p e n r o s e 逆； 互= 气，吃，气 对应的下标集合 f l ，之，如) 由数据点薯的邻域确定；p 为全1 向量。 2 1 2 3 非线性方法小结 流形学习算法可以很好的发现数据集内在的非线性流形结构，且都给出了全 局的优化函数。但是，这些算法存在着一些严重的障碍，使得它们不能很好的应 用到现实世界中。首先，现有的算法的时间复杂性都很高，至少是的二次方 时间的复杂度( 是数据集的数据数目) ；其次，对于非凸情形下的样本分布， 现有的某些算法并不能有效工作。第三，大部分现有的算法不能正确处理存在异 质噪声( 即标准差有上下浮动的噪声) 的样本。 2 2 特征选择相关工作 2 2 1 包装器方法 文献 1 9 提出的包装器方法无需关注所选择的学习器。实际上，学习器被看 作是一个理想的“黑盒子”，而这种方法将自身应用于离线机器学习软件包之中。 在大多数情况下，包装器方法根据一个给定的学习机器的预测结果来评估特征子 集的相对有效程度。在实际使用中，通常需要定义以下三个方面：第一，如何搜 索空间中所有的可能的特征子集；第二，如何评估学习机器的预测效果以指导搜 索的进行；第三，使用何种预测器。 包装器通常会使用于监督学习条件下，但是在非监督条件下包装器技术也同 样适用。非监督基于包装器的特征选择技术( 如图2 1 ) 是以使用聚类算法来评 估特征子集的方法为特点的。其基本思想是用每一个候选特征子空间尽可能好地 对数据进行聚类，然后寻找拥有最少特征数的最有意义的子空间。与监督条件下 不同，这个架构并不是将最好特征子集的搜索包装在监督算法的周围，而是包装 在聚类算法的周围。 f e a t u r e s u b s e t f e a t u r e e v a l u a t i o n c r i t e r i o n 图2 - 1 非监督w r a p p e r 特征选择方法框架 9 一 第二章相关工作 2 2 1 1 信息增益方法 信息增益可被用作判断单词优良的标准。信息增益衡量的是某个词的出现与 否对判断这个文本是否属于某个类所提供的信息量。令豫恐m 表示目标空间中的 类别集合。单词t 的信息增益值定义为： g ( f ) = 一p ( q ) 1 0 9 e ( q ) + e o ) e ( c ii f ) l o g e ( ql f ) + e o ) e ( qi t ) l o g p ，( qf ) i = ii = 1i = l 这种定义要比在二元分类模型中所使用的要更加一般化。在这里使用更一般 的形式是因为在文本分类问题中通常出现m 个类的空间( 其中，m 可能达到成 千上万) ，所以需要根据一个词对所有类别来讲的全局作用来评价其优良程度。 给定一个训练集，对于每一个惟一的单词进行信息增益值的计算，并且移除 那些值小于某个预定阈值的词汇。计算包括给定一个单词的情况下，对于某一个 类的条件概率的估计，以及定义中的熵值的计算。概率计算的时间复杂度为d ( ) 而空间复杂度为o ( v n ) ，其中为训练集中文本的个数，y 为单词数。熵计算的 时间复杂度为伙踟) 。 2 2 1 2 包装器方法小结 包装器方法调用学习算法来评估每个特征( 集) 的效果；迭代地在候选的特 征子空间中划分数据；然后根据某些标准选择最“相关”子空间。该方法假设特征 选择算法和聚类效果可以相互促进，但这种假设缺少有力的理论证明，且并不为 实验所支持。 2 2 2 过滤器方法 过滤器策略不关心接下来的学习算法，而只评价每个特征( 子集) 的中肯程 度。相应的选择标准要与类别信息无关而从“第一原则”构造得来。使用过滤器方 法进行特征选择有下列几个原因：第一，与包装器相比，过滤器更加快速，计算 复杂度更低。第二，一些过滤器( 如那些基于共享信息标准的过滤器) 提供了更 加一般化的特征选取，而不过分依赖于某个给定的学习算法。第三，过滤技术可 以作为预处理步骤来降低空间维数并且克服过拟合问题。 2 2 2 1 单词贡献度 文本背景下，聚类的结果是高度依赖文本间的相似性的。所有一个词的贡献 程度可以被看作是它对文本相似性的贡献程度。文本d ，和d ，是通过点积来计算 的： l o 第二章相关工作 s i m ( d i ，乃) = f ( t ，d i ) xf ( t ，乃) f 其中，f ( t ，d ) 代表单词f 在文档d 中的权重矿宰i a f 。 因此，定义数据集中一个单词的贡献度为它对所有文本相似度的整体贡献。 公式为： 乃( f ) = f ( t ，4 ) x f ( t ，嘭) t ，j 一丰j 如果所有单词的权重都是相等的，当单词t 出现在文档d 中时，可以简单地 让f ( t ，d ) = l 。然后t c ( t ) 的值可以写成公式： t c ( t ) = d f ( t ) ( d f ( t ) - 1 ) 当d f ( t ) ( 单词l 的文档频数) 是正数，那么这样的转换是单调增加的。d f 只是 t c 的一种特殊形式。 2 2 2 2 拉普拉斯分数( l s ) 拉普拉斯分数( l s ) 是一种新的特征选择算法。对于每个特征，其拉普拉斯分 数用以表示它的局部保留能力。l s 是基于如下直觉：如果两个数据点相互靠近， 那么它们很可能与同一个主题相关。实际上，在许多学习问题中，如分类问题， 数据空间的局部结构比全局结构更加重要。为了能够对局部数据结构建模，l s 将建立一个最近邻结点图。l s 试图找到能够表示这个图结构的特征子集。拉普 拉斯分数的根本思想是基于拉普拉斯特征映射以及局部保留映射。l s 的基本思 路是根据特征的局部保留能力来评估这些特征。 令三，代表第r 个特征的拉普拉斯分数，令厶代表第，个特征的第i 个采样点， 其中i = 1 ，m l s 算法可以如下描述： 1 建立拥有m 个结点的最近邻结点图g 。第i 个结点对应对x ，。如果x ，和x ， 足够接近，即x ，是x ，的最近的k 个邻结点或者x ，是x ，的最近的k 个邻结 点，就在它们之间加一条边。当类标签信息可见，就可以在共享同一个 类标签的两个结点上加一条边： i l x i - x f l l 2 2 如果结点i 和，是相连的，令s ，= e r ，其中t 是一个合适的常数。 否则，令s ，= 0 。图的权重矩阵s 将数据空间的局部结构建立成为模型： 3 对于第厂个特征，定义： f ，= z 。，2 ，厶r ，d = d i a g ( s 1 ) ，1 = 1 ，1 r ，l = d - s 其中，矩阵三称为拉普拉斯谱矩阵； 第二章相关工作 4 令h 一塑l r d l l ，计算第r 个特征的拉普拉斯分数= 骚； 2 2 2 3s p e c 算法 将监督特征选择和非监督特征选择进行融合看似是很困难的，因为前者拥有 类标签而后者没有。但是，如果换一个角度，两种特征选择都可以看成是为了达 成与目标概念相一致而选择特征，前者的目标概念与类标签相关，而后者是与数 据的内在结构相关。在两种情况下，目标都是将根据不同的分离定义而将实例划 分一组子集。无论是监督特征选择或者非监督特征选择，成对实例的相似度都可 以作为一种可测量不同