（计算机应用技术专业论文）模式分类中特征降维方法的研究.pdf

摘要 摘要 模式识别的主要任务就是利用样本的特征，将样本划分为相应的模式类别。但在 实际的处理过程中经常会碰到高维数据样本。一方面，数据的特征维数越大，则数据 提供的有关客观现象的信息就越多。但另一方面，高维数据却给计算机的处理带来了 巨大的困难，而且其中可能存在着较大的相关性和冗余，影响分类精度，这就足维数 灾难问题。因此，特征降维是进行模式识别的重要任务之一。 特征提取和选择是特征降维的主要手段。特征排序是特征选择的一个分支，其计 算复杂度低，易于应用，能够一次将所有的特征进行排序，因此得到广泛的应用。本 文提出了一种新的特征排序的方法用于处理降维过程中的特征选择问题。文中先f u l 顾 了特征降维的相关信息，介绍了概率密度函数估计，并重点论述了非参数估计法和 p a r z e n 窗口概率密度估计原理。然后设计一种应用g a u s s i a n 窗函数的p a r z e n 窗口概 率密度估计进行特征排序的方法，并讨论该方法的无监督和有监督的情况。在无监督 的情况下，先对原始数据样本进行概率密度估计，然后对所有数据的某一维特征进行 加权变换，再对变换后的数据样本进行概率密度估计，计算由该特征加权变换前后所 引起的数据样本的概率密度距离，即前后两次概率密度的差值，把这个值作为该特征 的评价得分，根据这个得分来对特征进行排序，通过选择合适的维数来达到降维的目 的。在监督的情况下，充分利用数据的类别信息。先对所有数据的某一维特征进行加 权变换，然后计算变换后的类别间的概率密度距离，类别问的距离越大，说明该特征 对于区分各类别数据的作用越大，即该特征越重要。因此，把总体的类问概率密度距 离作为评价特征重要性的指标，以此进行特征排序。本文详细沦述了该方法的推导过 程和算法步骤，并用m a t l a b 编程实现。通过若干u c i 机器学习数据集的实验验证，该 方法可行且有效，并表现出比现有方法更好的效果。 关键词：特征降维；特征选择：特征排序；概率密度距离；p a r z e n 窗概率密度估计。 江南人学n ! 职人员学位论义 a b s t r a c t c l a s s i f i c a t i o ni st h ep r i n c i p a lt a s ko fp a t t e r nr e c o g n i t i o nu s i n gt h ef e a t u r e so ft h ep a t t e r n s p a t t e r nr e c o g n i t i o na l w a y sn e e d st op r o c e s sl a r g en u m b e r so fh i g hd i m e n s i o n a ld a t a o nt h e o n eh a n d ，t h eh i g h e rd i m e n s i o n a l i t yt h ed a t ah a s ，t h em o r ei n f o r m a t i o nt h ed a t ac a nt a k e o n t h eo t h e rh a n d ，t h ed a t aw i t hh i g hd i m e n s i o n a l i t yi sn o to n l yh a r dt op r o c e s s ，b u ta l s ol o w e r t h ec l a s s if i c a t i o na c c u r a c yo w i n gt ot h er e l a t i v i t ya n dr e d u n d a n c yo ft h ef e a t u r e s ，a n dm a y c a l lc u r s eo fd i m e n s i o n a l i t y s od i m e n s i o n a l i t yr e d u c t i o ni st h ep r i n c i p a lt a s ko fp a t t e r n r e c o g n i t i o n f e a t u r ee x t r a c t i o na n df e a t u r es e l e c t i o na r ep r i n c i p a lm e t h o d so fd i m e n s i o n a l i t yr e d u c t i o n f e a t u r er a n k i n gi sab r a n c ho ff e a t u r es e l e c t i o n t h ec o m p u t a t i o n a lc o m p l e x i t yi sl o wa n d e a s yt oa p p l i c a t i o n i tc a nr a n kt h ef e a t u r ef o ro n et i m ea n di s u s e dw i d e l y t h i sp a p e r p r o p o s e saf e a t u r er a n k i n gm e t h o dt or e s o l v et h ep r o b l e mo fd i m e n s i o n a l i t yr e d u c t i o n i nt h i s p a p e r , t h er e l e v a n ti n f o r m a t i o no fr e d u c i n g f e a t u r e sd i m e n s i o n a l i t i e si sr e v i e w e da n d p r o b a b i l i t yd e n s i t ye s t i m a t i o ni si n t r o d u c e d ，a n dt h ep r i n c i p l eo fn o n - p a r a m e t e re s t i m a t i o n a n dp a r z e nw i n d o w p r o b a b i l i t yd e n s i t ye s t i m a t i o ni se l a b o r a t e d i nt h i sp a p e r ，am e t h o do f t h e g a u s s i a nk e r n e lp a r z e nw i n d o wp r o b a b i l i t yd e n s i t ye s t i m a t i o ni si n t r o d u c e da n da p p l i e d a n d t h e n ，w eu s e dt h em e t h o dt op r o c e s ss o m eu n s u p e r v i s e dd a t ea n ds u p e r v i s e dd a t e i nt h e a p p r o a c ho fd e a l i n gw i t hu n s u p e r v i s e dd a t a ，w ew o r ko u tt h eo r i g i n a l d a t a s e t ss c o r eo f p r o b a b i l i t yd e n s i t ye s t i m a t i o nf i r s t t h e nw el e to n eo ft h ed a t a s e t sf e a t u r eb ew e i g h t e d s o t h es c o r eo fp r o b a b i l i t yd e n s i t ye s t i m a t i o nw i l lb ec h a n g e d 。t h ed i f f e r e n c eo ft h e s et w os c o r c s i st h er e s u l to ft h i sm e t h o d b a s eo nt h er e s u l t ，t h ef e a t u r e sc a nb er a n k e d t h e nt h ep u r p o s eo f d i m e n s i o n a l i t yr e d u c t i o nw o u l db et a k e nb yc h o o s eap r o p e rd i m e n s i o n i nt h ea p p r o a c ho f d e a l i n gw i t hs u p e r v i s e dd a t a ，o n eo f t h ed a t a s e t sf e a t u r ei sb e e nw e i g h t e df i r s t ，t h e nc a l c u l a t e t h ep r o b a b i l i t yd e n s i t yi n t e r v a lb e t w e e nc l a s s e s t h em o s ti m p o r t a n tf e a t u r e + w i l lr e s u l tt h e b i g g e s td i s t a n c e sb e t w e e nc l a s s e s t h e r e f o r e ，w eu s ep r o b a b i l i t yd e n s i t yi n t e r v a lo fi n t e r - c l a s s t or a n kf e a t u r e t h i sp a p e re l a b o r a t e st h ed e r i v a t i o np r o c e s sa n da l g o r i t h ms t e p so ft h i s m e t h o d t h ea l g o r i t h mp r o p o s e di sr e a l i z e db ym a t l a b w eu s e ds o m eu c im a c h i n e l e a r n i n gd a t a s e t s t ot a k ee x p e r i m e n t s t h er e s u l t so fo u ra p p r o a c hd e m o n s t r a t et h a tt h e m e t h o di se f f e c t i v e l ya n dg a i nt h ea d v a n t a g eo v e ro t h e r s k e y w o r d s ：d i m e n s i o n a l i t yr e d u c t i o n ；f e a t u r es e l e c t i o n ；f e a t u r er a n k i n g ；p r o b a b i l i t y d e n s i t yi n t e r v a l ；p a r z e nw i n d o wp r o b a b i l i t yd e n s i t ye s t i m a t i o n 独创 生声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签 名：4 予印移日 期：二oo 九年六月十五日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 魑 导师签名： 日 期：二oo 九年六月十五日 第一章绪论 1 1 研究背景 第一章绪论 模式识另l j ( p a t t e mr e c o g n i t i o n ) 诞生于2 0 世纪初，随着计算机技术和人工智能技术的 兴起，模式识别逐渐发展成一门独立的学科。模式识别主要是指用计算机实现人埘事物 的分析和判断的能力。我们在生活中随时随地都在进行识别，我们能辨认周围的事物， 能区分不同物体发出的声音，能嗅出不同的味道，甚至连动物也能识别出不同的食物和 敌害，但就是这我们认为是很简单的能力，计算机实现起来却很困难。因此，如何让计 算机来实现人或动物所具备的识别的能力为人类服务，己成为众多专家学者重点研究的 课题。 一般来说模式识别系统主要由4 个部分组成：数据获取、预处理、特征提取和选择、 分类决策，如下图所示。 训练过程 图1 - 1 模式识别系统的基本构成 f i g 1 1t h eb a s i cs tr u e t u r oo fp a t t e r nr e c o g n i t i o ns y s t e r n 对于文本分类中的分类识别系统则由以下各部分组成： 训练过程 图1 - 2 文本分类系统的基本构成 f i g 1 2 t h eb a s i cs t r u c t u r eo f t e x tc l a s s j f i c a t i o ns y s t e m 设 汁 实 现 实 现 从图中我们可以看到，特征提取和选择是这个系统中的关键部分，并且对于分类器 的设计及其性能来说，它起着决定性的作用。由于在很多实际的数据样本中很难找到那 l 垩堕叁堂尘坚塑堂垡笙苎 些最重要的特征，或受条件限制不能对它们进行测量，这就使得特征提取和选择的任务 变得复杂而成为构造模式识别系统的最困难的任务之一。特征提取和选择的主要任务是 将高维数据进行降维处理，以方便计算机处理。在信息社会中，现代化生产和科学研究 搜集了海量的数据，这些数据中很多都属于高维数据，如会融数据、生物基因数据、图 像数据等。在计算机中我们用多变量组成的向量数据来表达这些内容，变量越多，维数 越高。随着数据维数的不断提高，数据将提供有关客观现象更加丰富、细致的信息。但 是，数据维数的大幅度提高给随后的数据处理工作带来了巨大的困难，这就是“维数灾 难”( c u r s eo fd i m e n s i o n a l i t y ) 瞳3 | ，直接对高维数据进行分析和处理是困难的。降维方法 是克服“维数灾难”的典型数据处理技术，是用来解决这一问题的有效手段之一。在很 多领域中我们都用到了特征降维技术，不然的话，原始数据将变得难以处理。下面的两 个例子就很好的说明了特征降维在实际应用中的作用。 人脸识别( f a c er e c o g n i t i o n ) h 3 是基于人的脸部特征信息进行身份识别的一种生物 识别技术，也是典型的需要特征降维处理的技术。它需要分析的对象都足二维或者高维 数据。狄度人脸图像就是二维数据，彩色人脸图像是三维数据。人们在人脸识别中最常 用的方法就是把二维或者高维数据转变成一维的向量数据，然后再进行后续处理。但是 把二维或是高维数据转变成一维数据后，数据维数通常是非常大的，这就是“维数灾难” 的问题，比如一个2 5 6 2 5 6 的狄度图像，变换成一维数据后，将会是6 5 5 3 6 维。随着 维数的增加，数据运算量将变的非常大，严重影响数据处理的速度。更重要的是这样一 种描述并不能直接反映对象的本质，并且它随摄像机位置、照度等因素的变化丽变化。 因此为了进行分类器设计，需要把图像从测量空间变换到维数大大减少的特征空间，被 研究的图像在这个特征空间中就由一个特征向量来表示，计算机才能对其进行高效的 处理。 文本分类( t e x tc a t e g o r i z a t i o n ) 也是一种需要特征降维处理的技术。随着网络的发 展，网上的信息越来越多。面对汹涌而来的信息，人们已经感到难以选择。为了能够解 决这些问题，各种信息组织和管理的技术被提了出来，文本分类技术就是其中之一 瞄儿纠”。文本分类是给定分类体系，然后将文本分到某个合适的类别中的过程。对于一 篇文本，首先我们要按照某种确定的原则进行词切分，之后去掉形容词、助词等对文本 分类无用的信息，然后用向量空问模型来表示文本。在向量空间模型中，每一个文本都 被表示为由一组规范化正交词条矢量所组成的向量空间中的一个点，即形式化为f 维空 间中的向量。其文本表示形式为：d = ( 尔q ，t ：，0 3 护，厶，彩。) 。其中为特征词条，q 为特 征项在文本d 中的权重。权重越大，表示该特征项在文本中的份量越大，即该特征项越 能反映文本d 的内容。用向量空间模型表示文本之后，我们看到文本中词空间维度很高， 计算丌销急剧增加，对于许多的学习算法来说这么高维的特征项是无法处理的。比如贝 叶斯无法实现庞大的计算模型。而神经网络也几乎无法处理这样大数据量的输入节点。 因此非常需要对特征空间的维度进行降维处理，即将高维数据通过变换映射到低维空 间。模式的特征提取和选择是这一技术的关键。通过建立合适的特征评价函数，对特征 2 第一苹绪论 项进行选择。常用的方法有特征频度( t e r mf r e q u e n c y ，t f ) 、文档频度( d o c u m e n t f r e q u e n c y ，d f ) 、特征熵( t e r me n t r o p y ) 、互信息( m u l t i i n f o r m a t i o n ，m i ) 、信息 增益( i n f o r m a t i o ng a i n ，i g ) 、x 2 统计量( c h i s q u a r e ，c h i ) 、特征权( t e r ms t r e n g t h ， t s ) 、期望交叉熵( e x p e c t e dc r o s se n t r o p y ，e c e ) 、文本证据权( w e i g h to fe v i d e n c ef o r t e x t ，w e t ) 、几率比( o d d sr a t i o ，o r ) 等。通过特征提取和选择可以获得文本对应 的关键词向量，然后根据这些向量来计算一组文本的相似度，利用文本的+ h e f t 度，就可 以对文本进行分类了。由此看出，特征提取和选择技术对于文本分类起着重要的作用。 综上所述，特征降维是很多技术领域中必须面对的一个问题。面对高维数据所带来 的“维数灾难”，我们必须采用降维技术来减少样本的特征维数，使相应的问题能够顺 利解决。 1 2 研究现状 从样本的许多特征中找出那些最有效的特征所用的方法大致分两种：特征选择和特 征提取。对于这些概念，在文献 9 3 和 1 0 中有详细阐述。特征选择足一种选择，是从 输入特征集合中挑选最优特征子集的算法，它的特点是对于原始特征集不做任何变化； 特征提取则是对原始特征进行线性或非线性变换之后得到的一组新的特征，它们保留了 原始数据样本问的信息，并用以替代难以进行学习的原始特征集合。目前已有不少文献 对这样的问题进行了探讨n 1 羽1 如1 4 3 1 5 1 1 6 1 17 1 。 为了达到降维的目的，到底是采用特征提取方法还是特征选择方法，取决于应用领 域和现有样本的情况。特征选择可以很好的保留样本特征的原始含义，这对于理解数据 产生的过程和分类模型的结构是非常重要的。特征提取出来的特征可以比特征选择出来 的特征有更好的分类能力，但有可能会使特征失去原有的物理意义。在实际的应用过程 中，往往把两种方法结合起来使用。 本文主要研究的是特征选择方面的问题。它可分为筛选( f i l t e r ) 和复选( w r a p p e r ) 两大类比踟引。特征筛选根据判别函数所得到的最优特征子集仅依赖于训练数据样本的 统计特性，而与分类器所使用的学习算法无关。相反，特征复选却依据分类器的学习算 法在不同特征子集上的实际分类效果( f 确识别率) 来评判各个特征子集的优劣。从理论 上讲，无论是特征筛选还是特征复选，能确保找到最优特征子集的最可靠的算法是穷举 法，但这种方法计算量非常大，在高维数据中一般很难进行计算。 目前，有基于遗传算法的特征选择方法心引，这是一种随机搜索算法，而不是某种 特定的判别规则。有基于信息增益的特征选择方法3 和基于模式相似性判断的特征选择 方法3 。这几种方法没有考虑特征之间的相关性和特征对分类的影响乜。k i r a 和r e n d e l l 在上世纪九十年代提出一种r e li e f 心方法，这个方法主要是通过欧拉距离估算每维 特征区分与自己同类样本和不同类样本的性能来评定这一维的重要性，但是它不能处理 冗余特征且仅能应用于两类的情形乜别；文 2 3 提出了一种针对r e l i e f 的改进的方法名 为r e l i e f f ，r e l i e f f 能应用于多类的情况。r e l i e f - f 系列方法的要点是根据特征对 江南人学柞职人员学位论义 近距离样本的区分能力来评估特征。其思想为：好的特征应该使同类的样本接近，而使 不同类的样本之间远离。r e l i e f f 评估效率高，对数据类型没有限制，可以较好的去除 无关特征，但r e l i e f f 方法不能去除冗余特征幽。文 2 1 依据特征对分类结果的影响 和特征之间相关性分析两个方面，提出了一种基于k 一均值聚类方法的特征选择算法，用 于无监督学习的特征选择问题。其基本思想是对每一个特征子集利用k 一均值聚类算法确 定其最佳分类数，然后以d bi n d e x 准则设定一个判断函数用于特征选择，最后从选择的 特征子集中删除掉相关性较大的特征之一。文献 1 4 2 5 2 6 2 7 2 8 采用了信息沦中 的互信息标准来进行特征排序。在文 2 9 中，一种叫做f s m ( f e a t u r es a l i e n c ym e t h o d ) 的方法被用来进行特征重要性的排序。它主要利用了e m 算法来计算每一维特征的 f s ( f e a t u r es a l i e n c y ) 。文 11 采用s u d 进行了特征重要性的排序。它主要是通过计算熵 来排序，文 3 0 作者采用概率密度逼近方法对特征进行重要性的排序。它主要是通过调 整特征的权值，使特征变换前后，样本空阳j 的概率密度变化最小，这样，越足重要的特 征，它的权值越是小，根据这个原理，通过对权值的排序来对特征进行排序。 虽然国内外的专家和学者提出了很多特征降维的方法，但是没有哪一种方法能够用 于处理所有的特征降维情况。而从目前的技术角度来看，也不可能存在这样一种方法。 所以，对于不同的情况，必须设计不同的降维方法。 1 3 本文研究目的与意义 模式识别中进行分类识别的对象很多都具有高维的特性。而高维数据所造成的维数 灾难，将给识别造成严重的影响。因此，在进行分类识别之前，必须对高维数据进行降 维处理，减少数据样本的特征维数，把数据样本的最重要的特征找出来。在进行特征降 维时，一方面应使数据样本的特征维数尽可能的少，以提高计算机处理效率，另一方面 应把减少特征维数对分类识别准确率的影响减少到最小程度。因此，特征降维技术有着 重要的理论和应用价值。 本文的目的是探索一种新的特征排序的方法用于解决降维中的特征选择问题，并讨 论该方法的有监督和无监督的情况。通过实验证明该方法的可行性与效率。 1 4 论文的组织 本文主要对特征降维的相关技术进行研究和探讨。全文总共由5 章组成，具体内容 安排如下： 第一章为绪论。介绍了特征降维技术的基础知识，以及论文的研究问题。内容包括 特征降维技术的研究背景、国内外的研究现状、课题研究的目的与意义以及论文的组织 安排。 第二章为特征降维方法及概率密度函数估计概述。对降维技术中的特征提取、特征 选择和特征排序等相关方法进行阐述。并介绍了概率密度函数估计的基本原理及非参数 4 第一章绪论 估计法和p a r z e n 窗口概率密度估计原理。最后介绍了基于概率密度距离的特征排序方法 的基础。 第三章为基于概率密度距离的无监督的特征排序方法。介绍了在无监督的情况下， 基于概率密度距离的特征排序准则。根据特征加权变换前后，所引起的样本空问的概率 密度距离作为特征的评价得分。根据分值的大小进行特征排序。用多个实验验汪该算法 的可行性及效率，最后对该方法进行总结。 第四章为基于概率密度距离的监督的特征排序方法。针对第三章所提出的本文方法 的无监督的情况，本章将其推广到有监督的情况，充分利用数据的类别信息，并重新进 行算法推导和公式求解，根据特征加权变换后，所引起的总体类问概率密度距离来作为 特征的评价得分，以此进行特征排序。文中用多个实验验证该算法的可行性和效率，最 后进行总结。 第五章为结束语。进行了全文的总结并提出进一步的研究工作。 江南人学和职人员学位论义 第二章特征降维方法及概率密度函数估计概述 从上一章介绍的相关知识中可以知道，样本的特征越多提供的信息就越多，但是特 征的大幅度提高给数据处理工作带来了巨大困难。另一方面，在众多的特征之间，可能 存在大量的相关性和冗余性，影响分类识别。所以必须对高维数据进行降维。这一章首 先将对特征降维的相关内容进行详细介绍，然后介绍本文方法的基础：概率密度函数估 计及相关的方法原理。 2 1 特征降维方法 特征选择和提取是特征降维的主要手段，其基本任务是如何从许多特征中找出那止电 最有效的特征。分类器在使用过程中，如果样本不是很多但样本的特征很多，在这样的 情况下，计算复杂程度会提高且分类器的性能会下降，因此必须把高维特征空i 日j 压缩到 低维特征空间，以便有效的设计分类器。特征提取是通过映射( 或变换) 的方法用低维 空间来表示样本的过程。映射后的特征叫二次特征，它们是原始特征的某种组合。从广 义上来讲，特征提取就是一种变换。特征选择是从一组特征中挑选出一些最有效的特征 以达到降低特征空间维数的目的的过程。有的时候特征提取和选择并不是完全分丌使用 的。可以先将原始特征空问映射到维数较低的空间，在这个空间中再进行特征选择以进 一步降低维数。当然，也可以先经过特征选择以去掉那些对分类器基本无效的特征，然 后再进行特征提取来降低维数。下面，我们对特征提取、特征选择和特征排序等方法进 行阐述。 2 1 1 特征提取 特征提取是把高维特征空问变换为低维空问的过程，并且尽可能的保持样本之f n j 的 “距离”信息，从而大大降低对它们进行各项操作的复杂度。对于特征提取的定义为： 已知个数据对象和它们的高维特征信息( d 维) ，求出用d ( d d ) 维特征来表示的 个数据对象，要求尽可能地保持数据对象之间的距离，从而能够保持它们的特性。剐。 目前有很多特征提取算法，如主成分分析、因子分析、多维标度、投影追踪n 0 1 以及 f i s h e r 鉴别分析。而其中又以主成分分析最为著名，应用最为广泛。下面简要介绍一下 主成分分析法。 主成分分析法( p r i n c i p l ec o m p o n e n ta n a l y s i s ，简称p c a ) 是使用最广泛的线性降维 方法之一，它概念简单，实现算法高效。在信号处理中，k 一，变换其实就是主成分分析。 主成分分析法p c a 将方差的大小作为衡量信息量多少的标准，认为方差越大提供的信息 越多，反之提供的信息就越少。p c a 通过线性变换保留方差大、含信息量多的分量，丢 掉信息量少的。换句话说，就是将原来数据投影到由前，个最大的主成分张成的线性子 6 第一二章特征降维及概率密度函数估计概述 空间上，从而降低数据的维数。 p c a 的不足之处是：它是一种线性的投影，不能j 下确地处理位于非线性流形上的数 据。另外，我们也不清楚应该保留多少个主成分，只能根据情况舍去其中方差小于某个 门限值的成分。川。 2 1 2 特征选择 特征选择是从一组数量为d 的特征中选择出数量为d ( d d ) 的一组最优特征的过 程。这个子集应该具有比原有特征集更好或者相同的分类功能。为此有两个问题需要解 决，一是选择的标准，要选出是某一可分性达到最大的那一组特征。另一问题是要找到 一个好的算法，使运行时i h j 符合人们的要求。 如果把d 个特征每个单独使用时的可分性判据都算出来，按判据大小排队，选取前 面d ( d d ) 个特征来作为最有特征子集是否可行呢? 答案是否定的n 1 。如果这样做是可 行的话，那特征选择将变得简单。一般来说，前面d 个最有效的特征组合并非最优组合， 有的时候甚至是最不好的特征组合，因为这样做没有考虑特征之间的相关性。 从d 个特征中挑选出d 个特征，理论上用穷举法可以达到目的，但是这样做会因为 计算量太大而无法实现。因此，现在人们都用次优搜索算法，做到运算效果和运算逞的 一个折中。在所有这些算法中，人们一般用“自下而上 和“自上而下”的方法术选择 最优特征组。“自下而上”方法是特征从零个开始，将对分类作用大的特征选出，逐步 增加至d 个。“自上而下”方法是从整个特征集d 中逐步删除对分类作用小的特征，直 至减少到d 个为止。下面介绍几种常用的特征选择的方法。 2 1 2 1 最优搜索法 最优搜索法有穷举法和“分支定界”法1 。 ( 1 ) 穷举法 从理论上讲，穷举法能够从d 个特征中选择d 个特征的最优组合，但是穷举法计算 量太大。从d 个特征中挑选d 个，所有可能的组合数为： ，d ! q = 乙荔= i - i i( 2 1 )“ ( d d ) ! d ! 、7 如果d = 1 0 0 ，d = 1 0 则q 的数量级是l o “，若d 减少到2 0 ，d 为1 0 ，则印还是高达1 8 4 7 5 6 。 把各种可能的特征组合的可分性判据都算出来再进行比较，以选择最优特征组，则会冈 为计算量太大而无法实现。 ( 2 )q 分支定界”法 到目前为止唯一能得到最优结果的搜索方法是“分支定界”算法，它是一种自上而 下的方法，并具有回溯功能，可使所有可能的特征组合都被考虑到。由于该算法合理的 组织搜索过程，使得某些特征组合不用计算，而不会影响最后的结果。选出那些不用计 江南人学和：职人员学位论文 算的特征组合，主要是利用了可分离性判据的单调性，即对有包含关系的特征组 孵lc 倪2c c 孵，有j ( 贸1 ) ，( 贸2 ) j ( 贸，) ( 2 2 ) 则称判据具有单调性。因此，小于某一判据的所有特征组合可不用考虑，不必参与计 算。 整个搜索过程可用树来表示出来，树根为d 维特征的原模式，按特征子集的维数逐 个减小，树的子结点维数办逐级下降，直到规定维数的模式为终止结点时为止。搜索的 过程为：先找一个d 维特征组合，以该特征子集的判据值为界值，将该界值与后继搜索 到的结点判据值比较，如果界值大于该结点的判据值，则以该结点为根的子树上的所有 结点都不需要再搜索，按照判据的单调性，该子树上的结点没有可能是最优。如果结 点的判据值大于界值，则更新界值，继续搜索。 “分支定界”算法根据判据的单调性，只计算了部分可能的d 维特征组合，因此 比穷举法节约了很多时间，降低了计算量。但是该算法是建立在所用可分性判据j 满足 单调性基础上的，即使理论上所选的满足单调性，有时l ，必须用有限样本去估计，这 可能破坏了单调性，特别当各类分布密度是用非参数法估计时，更可能发生这种情况， 这时有可能不能保证结果为最优。 2 1 2 2 次优搜索法 最优搜索算法因为计算量大而难以实现，因此人们往往放弃最优解而转而寻找计算 量小的次优搜索法，下面介绍一些常用的方法。 ( 1 ) 单独最优特征组合 次优搜索法中最简单的是将各特征按单独使用计算其判据值进行排队，然后取其前 d 个判据值最大的特征作为最优特征组合。但是即使各特征是独立统计的，这一结果也 不一定就是最优结果。只有当可分性判据可写成如下形式时： 旦 j ( x ) = ：j ( x ，) 一t = l ( 2 3 ) 或 1 ) ( x ) = 兀j ( x ，) ，= i ( 2 4 ) 这种方法彳可以选出一组最优的特征来。有一种可能是在两类样本都是正态分布的 情况下，当各特征统计独立时，用m a h a l a n o b i s 距离作为可分性判据，才能满足要求。 ( 2 ) 顺序前进法( s e q u e n t i a lf o r w a r ds e l e c t i o n s f s ) 这是最简单的自下而上搜索方法，源于全局最优则局部最优原则。每次从未入选的 特征中选择个特征，使该特征与已入选的特征组合在一起时所得的判据值最大，直 到特征数增加至0d 为止。 s f s 法考虑了所选特征与已入选特征之间的相关性，比单独最优特征选择法要好， 但是，该方法也有缺点就是一旦某些特征已入选，即使由于后加入的特征使它变成多余， 第二章特征降维及概率密度函数估计概述 也无法再把它删除。 如果s f s 法每次不是增加一个特征，而是增加，个特征，就成为广义顺序前进法 ( g e n e r a l i z e ds e q u e n t i a lf o r w a r ds e l e c t i o n ，g s f s ) ，即每次从未入选的特征中选择厂个 特征，这，个特征和原来选出的特征组合后的判据，值达到最大。 ( 3 ) 顺序后退法( s e q u e n t i a lb a c k w a r ds e l e c t i o n ，s b s ) s b s 法是自上而下的方法，从全体特征开始每次删除一个特征，所删去的这个特征 应使剩下的特征组合的判据，值最大，以此类推，一直到剩下d 个特征为止。与s f s 法 相比，s b s 法在计算过程中可以估计每去掉一个特征所造成可分性的降低，另外，由于 顺序后退法的计算是在高维空间进行的，所以计算量要比s f s 大。 如果每次去掉的特征不是一个而是，个的话，则该方法称为广义顺序后退法 ( g e n e r a l i z e ds e q u e n t i a lb a c k w a r ds e l e c t i o n ，g s b s ) 。 ( 4 ) 增，减，法( ，一，法) 顺序前进法和顺序后退法都有缺点就是每次选入( 或删除) 的特征就不能在删除( 或 选入) ，为了解决这个问题，在选择的过程中加入局部回溯过程。例如，先用顺序前进 法一个个的把特征选入，当选入，个特征后，再用顺序后退法删去厂个，把这样的一种 算法叫做增，减，法。根据，和，的大小关系，该算法还分成两种：当， ，时，是属于自 下而上的算法；当， ( 恐) j ( x a ) ，选择自仃面若干个具有最高值的特征，来i g _ 至- u 降维的目的。 通过特征选择，一些和任务无关或者冗余的特征被删除b3 l 。简化的数据集常常会得到更 精确的模型，也更容易理解。 特征排序是先对样本特征进行评分，以此来排序特征，再通过选择合适的特征组合 9 江南人学礼职人员学位论文 来达到降维的目的。本文将利用特征的变化对数掘样本概率密度影响的大小来衡量特征 的重要性，因此下文将介绍概率密度函数估计及相关方法原理。 2 2 概率密度函数估计 在样本分类识别过程中，先验概率p ( c a ，) 和类条件概率密度p ( xi 国，) 是非常蕈要，对 分类起很大作用，但在实际工作中，先验概率和类条件概率密度往往是未知的。我们如 何用有限的样本集来估计尸( 缈，) 和e ( x l 彩。) ，以达到设计分类器的目的，这就是概率密 度函数的估计问题。 从样本集推断总体概率分布的方法有以下几种类型： ( 1 ) 监督参数估计。样本所属的类别及类条件总体概率密度函数的形式为己知，而 表征概率密度的某些参数是未知的。由已知类别的样本集对总体分布的某些参数进行统 计推断，这种情况下的估计称为监督情况下的参数估计。 ( 2 ) 非监督参数估计。已知总体概率密度函数形式但未知样本所属类别，要求推断 出概率密度函数的某些参数，称这种推断方法为非监督情况下的参数估计。 ( 3 ) 非参数估计。已知样本所属类别，但未知总体概率密度函数的形式，要求我们 直接推断概率密度函数本身。 下面，主要介绍一下总体分布的非参数估计。 2 2 1 非参数估计 在很多实际的问题中并不知道总体分布形式，或总体分布不是一些通常遇到的典型 分布，不能写成某些参数的函数。但为了设计分类器，仍然需要总体分布的知识，于是 提出了某些直接用样本来估计总体分布的方法，我们称之为估计分布的非参数法。 2 2 1 1 基本方法 非参数估计的目的是从样本集孵估计样本空间任何一点的概率密度k ( x ) 。如果样本 集孵来自某一类别，则估计结果为类条件概率密度b ( x f 够) 。如果样本集贸来自c 个类 别，则估计结果为混合密度p ( x ) 。下面介绍一下估计总体分稚函数的基本思想。 设p 为随机向量x 落入到区域贸中的概率： p 2 土tp ( x ) 出 ( 2 5 ) p ( x ) 为x 的总体概率密度函数。从式( 2 5 ) 中看出可以通过估计概率尸来估计概率密 度函数p ( x ) 。如果有个样本x l ，x 1 ，h 是从密度为p ( x ) 的总体中独立抽取的，则个 第一二章特缸降维及概牢密度函数估计概述 样本中有k 个落入区域贸中的概率最符合随机变量的二项分布，可以写为 尼= c ：尸( 卜p ) ( 2 6 ) 因而可以求出k 的期望值为 e k 】- n p 我们可以想象到比值专就是概率尸的一个很好的估计，即 户兰生( 2 7 ) n 这个估计在样本数足够大的时候将非常准确。设p ( x ) 连续并且区域孵足够小，以至使 p ( x ) 在这么小的区域中没有什么变化，那么我们司以得到 j p = 工p ( x ) 出= p ( x ) 矿 其中x 是区域孵中的一个点，而v 则是区域贸所包含的体积。 可得 专兰户= 上触) 出嘲缈 即 ( 2 8 ) 由式( 2 7 ) 和式( 2 8 ) ( 2 9 ) p ( 工) 2 等 ( 2 1 0 ) 式( 2 1 0 ) 就是x 点概率密度p ( x ) 的估计值，它与样本数、包含z 的区域倪的体 积v 及落入v 中的样本数k 有关。 另外有一些问题有待讨论。如果我们固定体积v 的值，并且能够获得更多的样本， 那么比值专会在概率上收敛，但即使这样，所获得的其实是p ( x ) 的空间平均估计 兰：j lp ( x ) d x ( 2 11 ) v d x 如果希望得到b ( x ) ，而不是p ( x ) 在区域暇上的平均，那么必须要求体积y 的值趋近 于零。但如果在固定样本的个数的前提下，令体积v 趋近于零，那么区域贸会变得如此 小，以至于其中可能不含有任何样本，此时有b ( x ) 兰0 。这样的估计结果就没有意义了。 或者说碰巧有1 个或2 个样本落在该区域内，那么估计的结果就变成无穷大，因此这样 也是毫无意义的。 实际上，我们能够获得的样本个数总是有限的，这样，体积v 就不能取得任意小。 从理论上来说，假设有无限多的样本，那我们采用以下方法：为了估计点x 处的概率密 度函数，构造一系列包含点x 的区域锨，贸：，对贸。采用一个样本进行估计，对婀，采 江南人学订i 职人员学位论文 用两个样本，以此类推。设是吼的体积，k 是落入在贸中的样本数， 的第次估计，则 姒加诺 若满足以下三个条件 ( 1 ) l i m = 0( 2 ) l i m k = 0 0 、 呻曲 则氐( x ) 收敛于p ( x ) 。 ( 3 ) l i m 盟：o 一一一 饥( x ) 是p ( x ) ( 2 1 2 ) 第一个条件保证了在区域均匀收缩，i 司时p ( z ) 在x 点连续的情况f ，司使空i 日j 平均 吾收敛于p ( x ) 。第二个条件只有在p ( x ) o 时爿有意义，保证了频率之比能够收敛到概 率p 。第三个条件对于式( 2 1 2 ) 显然是必须的。它说明了虽然最后落在一小区域孵中 的样本个数非常大，但这么多样本在全体样本中所占的比例仍然是非常小的。 有两种经常采用的获得这种区域序列的途径： ( 1 ) p a r z e n 窗法。根据某一个确定的体积函数，比如= 嘉，来逐渐收缩一个 给定的初始区间。这就要求随机变量后和万k n 能够保证p ) 能收敛到j f 7 ( x ) 。 ( 2 ) k 近邻估计。确定k 为n 的某个函数，比如k = 万。这样，体积就必须逐 渐增长，直到最后能包含进z 的k 。，个近邻点。 2 2 2p a r z e n 窗口概率密度估计 p a r z e n 窗口概率密度估计是一种非参数的概率密度估计法。它起源于统计的基本理 论。它可以在不知道样本的总体分布形式，或分布不能写成某些参数的函数的情况下， 直接利用样本值来估计总体概率密度。 首先我们定义窗函数( ) ，它表示一个中心在原点的单位超立方体，如果点一落在 超立方体中，那么( 三立) ：1 ，否则便为0 。因此，超立方体中的样本个数就是 疗 7 吒=备瓦1t百x-x,p- ) 吒= 厶f 纵丁) | = 、nh k 把式( 2 1 3 ) 代入式( 2 i 2 ) ( 2 1 3 )