（计算机应用技术专业论文）聚类特征选择方法的研究和应用.pdf

摘要 摘要 模式识别的主要任务就是利用样本中的特征，将样本划分为相应的模式类别。通常 情况下，样本特征中包含了足够的类别信息，才能通过分类器实现正确分类。为了提高 模式识别的正确识别率，人们通常需要采集数量巨大的原始特征，使得原始特征空间或 输入空间的维数可能高达几千维或几万维。这样，结果不仅使样本特征维数增大，而且 其中可能存在较大的相关性和冗余，影响最后的分类精度。这就造成所谓的维数灾难。 所以为了有效地进行模式分类和数据分析，特征降维就显得异常重要。 本论文的研究目的是为了探索新的特征选择方法，提出一种用于特征降维的特征排 序和特征选择，丰富减少特征维数的方法。文中简要介绍了特征降维的准则，回顾了当 前的主要特征降维技术。文中也对特征相关性分析和聚类有效性准则进行了阐述，重点 介绍了特征之间相似性度量的方法和聚类有效性的判断准则。 本论文重点是建立了一种基于对特征进行聚类的特征选择准则，阐述了应用该准则 进行特征排序的原理和方法。针对特征选择这一问题，文中从特征对分类结果的影响、 特征之间的相似度量公式和特征之间相关性的分析这三个方面出发，先利用特征相似性 度量公式计算每一维特征之间的相似度即求出相似度矩阵，再依据每一维特征对样本分 类的影响，结合聚类算法和聚类有效性的判断准则等，然后提出了一种基于聚类的特征 选择算法。 文中先前几个章节先对相关的知识背景进行粗略的介绍，如k 均值聚类算法、层次 聚类方法、聚类有效性判断准则等。论文对于无监督的情况，利用聚类的方法，提供一 种简化了的针对无监督情况的特征排序方法和一种简化了的特征选择方法。论文最后采 用c + + 来编程实现了文中提出的算法，选取了大量数据来进行实验。大量的基于的实验 结果表明，本文所提出的方法是有效、可行的，并且与现有的一些方法相比，更为有效。 它还有着运算速度快等优点。 关键词：特征选择；相关性分析；相似性度量；层次聚类；k 均值算法；无监督 a b s t r a c t 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 g e n e r a l l y , ap a t t e r nc a l lb ec o r r e c t l yc l a s s i f i e do n l yw h e nt h eo n e sf e a t u r e sh a v ee n o u g h c l a s s i f i c a t i o ni n f o r m a t i o n i no r d e rt oi m p r o v et h ea c c u r a c yo fc l a s s i f i c a t i o n ，t h el a r g e f e a t u r e sn e e dt ob ec o l l e c t e d ，s ot h a tt h eo r i g i n a lf e a t u r es p a c ei st h o u s a n d so rt e n st h o u s a n d s d i m e n s i o n a l i t i e s t h i sw i l ln o to n l yl e a dt h ed i m e n s i o n a l i t yo ft h ep a t t e r nt oe n l a r g e ，b u ta l s o l o w e rt h ec l a s s i f 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 t h i s i st h es o c a l l e dc u r s eo fd i m e n s i o n a l i t y s o ，i no r d e rt o e f f e c t i v e l ya n a l y z eh i g h d i m e n s i o n a l i t yd a t a , i ti sap i v o t a ls t e pt or e d u c et h e i rd i m e n s i o n a lm e m b e r s t h ep u r p o s eo ft h i sp a p e ri st oe x p l o r ean e wf e a t u r es e l e c t i o nw a ya n dp r o p o s eaf e a t u r e r a n k i n gm e t h o dt or e d u c ef e a t u r e sd i m e n s i o n a l i t i e s i nt h i sp a p e r , t h ep r i n c i p l eo 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 s b r i e f l yi n t r o d u c e d ，a n d t h e p r i n c i p a lw a y s o ff e a t u r e d i m e n s i o n a l i t yr e d u c t i o ni sr e v i e w e d i ta l s oe x p a t i a t e so nf e a t u r e sa n a l y s i sa n dc l u s t e r i n g e f f e c t i v e n e s sc r i t e r i aa n df o c u so nh o wt oj u d g et h ee f f e c t i v e n e s so fc l u s t e r i n ga n dc a l c u l a t e t h es i m i l a r i t i e sa m o n gt h ef e a t u r e s t h i sp a p e rf o c u s e so ne s t a b l i s h i n gt h er u l ew h i c hb a s i n g o nc l u s t e r i n go ff e a t u r e s ，a n dt h e nd e s c r i b i n gt h ep r i n c i p l e sa n dm e t h o d sa b o u tu s i n gt h i s c r i t e r i o nt os o r tt h ef e a t u r e s t ot h i si s s u ea b o u tf e a t u r es e l e c t i o n ，t h i sp a p e rb a s e so nh o wt h e f e a t u r e si m p a c tc l a s s i f i c a t i o nr e s u l t s ，t h em e t r i cf o r m u l au s e dt oc o m p u t et h es i m i l a r i t yo ft h e f e a t u r e sa n df e a t u r ea n a l y s e s ，f i r s tu s i n gt h ef o r m u l at oo b t a i n t h em a t r i xa b o u tt h e s i m i l a r i t yo ft h ef e a t u r e s ，a n dt h e na c c o r d i n gt ow h a te a c hf e a t u r ei m p a c t st h er e s u l to f c l a s s i f y u s i n gc l u s t e r i n ga l g o r i t h m sa n dt h ee f f e c t i v e n e s so fc l u s t e r i n g sc r i t e r i aa n ds oo n ， f i n a l l yp u t t i n gf o r w a r da na l g o r i t h mb a s i n go nc l u s t e r i n gf e a t u r e s i nt h ep r e v i o u sc h a p t e r si n t r o d u c et h eb a c k g r o u n do ft h er e l a t e dk n o w l e d g er o u g h l y , s u c ha sk m e a n sc l u s t e r i n ga l g o r i t h m 、h i e r a r c h i c a lc l u s t e r i n gm e t h o da n dt h ee f f e c t i v e n e s so f c l u s t e r i n g sc r i t e r i ae t c a i m i n ga tf e a t u r es e l e c t i o n , b a s e do nc l u s t e r i n g ，an o v e lf e a t u r e r a n k i n ga p p r o a c hi sp r o p o s e d as i m p l i f i e da p p r o a c hi si n t r o d u c e dt od e a lw i t hu n s u p e r v i s e d d a t a a tl a s t ，t h ea l g o r i t h mp r o p o s e di nt h i sp a p e ri sr e a l i z e db yc + + ，a n dm a n yd a t a s e t si s u s e dt oe x p e r i m e n t al o to fe x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h ev a l i d i t y , f e a s i b i l i t ya n d a d v a n t a g eo v e ro t h e r so fo u ra p p r o a c h k e y w o r d s ：f e a t u r es e l e c t i o n ；c o r r e l a t i o na n a l y s i s ；s i m i l a r i t ym e a s u r e ；h i e r a r c h i c a l c l u s t e r i n g ；k - m e a n sc l u s t e r i n ga l g o r i t h m ；u n s u p e r v i s e d l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究5 - 作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签各一日 期： 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定。 签名：导师签名： e l 期： 第章绪论 第一章绪论 1 1 研究背景 模式识另l j ( p a t t e r nr e c o g n i t i o n ) 诞生于2 0 世纪2 0 年代。随着4 0 年代计算机的出现，5 0 年代人工智能的兴起，它在6 0 年代初迅速发展成为- 1 7 学科。该学科研究的内容主要是 使机器能做以前只能由人类才能做的事，具备人所具有的、对各种事物与现象进行分析、 描述与判断的部分能力。它所研究的理论和方法在很多科学和技术领域中得到了广泛的 重视，推动了人工智能技术以及图像处理、信号处理、计算机视觉、多媒体技术等多种 学科的发展，扩大了计算机应用的领域。目前模式识别技术已成功应用于指纹识别、印 刷体字符识别、语音识别、车牌识别等领域。模式识别在人脸识别、手写体字符识别、 自动文本分类、多媒体数据挖掘等领域的应用研究也取得了长足进展【1 1 。模式识别系统 的基本组成和识别过程如下图所利2 i 。 训 分类结果 分类器参数 图1 - 1 模式识别过程 通过上图本文可以清晰的看到，特征降维( 特征提取或选择) 是模式识别过程中的 非常重要和关键的一环。它对于识别过程的后续步骤以及识别的结果起着至关重要的作 用。 模式识别的基本思想主要是利用从样本中提取的特征，将样本划分为不同的模式类 别。模式识别的主要步骤是，首先将样本( 或模式) 表示成线性空间中的向量，即特征 向量；然后用训练样本对事先选定的分类算法或学习算法进行训练，直接或间接地提取 出蕴涵在训练样本中有关各个模式类的统计特性，并根据这些特性确定出分类准则；最 后依据这些准则对未知模式样本进行分类决策。显然，模式表示( 样本特征) 的准确与 否，将严重影响到模式识别效果。模式识别主要任务是利用从样本中提取的特征将样本 划分为相应的模式类别，特征提取与选择是模式识别中的关键技术之一。 通常情况下，样本特征中包含了足够的类别信息，才能通过分类器实现正确分类。 江南大学硕士学位论文 然而，特征中是否包含足够的类别信息却很难确定。为了提高统计模式识别的正确识别 率，人们通常需要采集数量巨大的原始特征，使得原始特征空间或输入空间的维数可能 高达几千维或几万维，如果直接在输入空间上进行分类器训练，就可能带来棘手的问题。 因为这样采集巨大原始特征的结果不仅使样本特征维数增大，而且其中可能存在较大的 相关性和冗余，影响最后的识别或分类的精度。还有，很多在低维特征空间具有良好性 能的分类算法用在高维特征空间上时，就计算方面来说就变得不可行了；另一方面，即 使可以应用这些算法，但是精度或分类准确率也变得更低，以至于在实际应用中不能接 受这样低的精度。在训练样本容量一定的前提下，特征维数的增加将使得样本统计特性 的估计变得更加困难，从而降低分类器的推广能力或泛化能力，呈现所谓的“过学习”或 “过训练”的现象【3 i 。 所有这些由于样本特征维数的增加而造成了在模式识别应用和研究过程中的困难， 也就是人们所说的“维数灾难”( c u r s eo f d i m e n s i o n a l i 够) m 】。在应用模式识别技术的新兴 领域中，有两个典型的遭遇到样本特征维数问题的领域，就是微阵列数据基因选择和文 本分类中的特征维数问题【5 1 。在这些领域进行研究和实际处理数据的过程中，如果不预 先减少样本特征维数即进行特征降维，那么所得到的原始数据几乎就难以进行分析。 1 1 1 特征子集选择问题 下面首先给出相关概念： 定义l ：特征子集是将输入属性集合中不相关和冗余属性删除后得到的新属性集合。 定义2 ：特征子集选择是根据以下标准选择最小规模属性集合：( 1 ) 保证分类精度不 能明显下降；( 2 ) 特征子集选择前后，类的分布尽可能一致。目前，特征子集选择解决方 案分为两类 6 1 1 7 1 8 1 。 ( 1 ) 过滤法。过滤法独立于归纳学习算法，作为数据挖掘中数据预处理部分预先完成 特征子集选择，然后进行归纳学习。其代表模型为f o c u s 和r e l i e f t 8 i ，f o c u s 算法 对训练数据的所有特征子集穷举，以确定能提供一致性标记的最小特征子集，f o c u s 对数据中的噪声和不一致性很敏感，但此算法计算复杂性随属性数目增加呈指数级增 长，不适合属性数目超过2 5 - 3 0 3r e l i e f 算法赋予每一个属性一个权值以表示其与类 标记的相关程度，此算法在删除冗余属性方面效果差。 ( 2 ) 封装法。封装法以归纳学习算法的统计精度、评价指定特征子集的方式完成特征 子集空间的搜索。封装法将归纳算法封装于特征子集选择算法中，当处理大量属性时， 其计算规模和资源占用十分庞大。 2 第一章绪论 表1 1 所示为采用c 4 5 算法对数据库进行分类的结果 t a b 1 1t h er e s u l t so f c l a s s i f i y i n gt h ed a t a b a s eu s i n gc 4 5a l g o r i t h m 如表1 1 所示，无关和冗余属性导致了分类精度下降，计算时间延长。然而已证吲7 1 ， 最优( 最小) 特征子集选择o f s s ( o p t i m a lf e a t u r es u b s e ts e l e c t i o n ) 是n p i h - 题，因此，寻找 一个较好的近似算法具有现实意义。 1 1 2 微阵列数据基因选择1 6 i d n a 芯片技术成功地实现了人们对d n a 微阵列数据的自动获取，这对了解疾病在 基因级别产生的原因，基因级别的药物研制以及疾病的基因诊断和基因治疗具有重要的 理论和实际意义i 9 】【1 0 1 ( 实际上，基因诊断是对基因芯片所获得数据进行分析的最具商业价 值的应用之一) 。在基因空间中，每一个所采集的样本都是一个微阵列，其维数通常是上 千维的( 如2 0 0 0 6 0 0 0 维) ，其中每一维对应一个基因，每一维上数据的值描述了生物样 本在这个基因上的表达水平( 0 0 为该基因的拷贝数目) 。由于目前还没有关于哪些基因引 起某种疾病的先验知识，当然是越多的基因参与分析则分析结果的准确性就可能越高 ( 不易漏掉可能产生影响的基因) 。随着基因芯片技术的进一步发展和芯片集成度的进一 步提高，这个空间的维数还将进一步提高。但是这样的结果给d n a 微阵列数据的分析 带来了极大的挑战。 另一方面，为对各种癌症进行合理的基因级别的分类，发现癌症的基因模式即对模式 进行分类和识别( 基因诊断) ，理论上需要采集大量的病例基因表达数据，所采集的病例基 因表达数据的病人数目应至少多于基因空间维数的十倍1 1 1 i 。但实际上不可能在有限时间 内采集到如此多病人的d n a 表达数据。即使本文采集尽可能多病人的d n a 表达数据， 所获得的样本数据数目也非常有限。况且，目前的d n a 芯片技术需要昂贵的尖端仪器设 备，如原位合成芯片的光刻机和寡聚核苷酸合成仪、构建d n a 阵列的自动仪器芯片、检 测的激光共聚焦显微镜等设备，动则几万甚至几十万美元，这使得获取多于基因数目病 人的d n a 微阵列数据成为不可能。另外，药物研究的过程也不允许在如此大量的病人身 上进行实验。这样就造成了严重的基因数据分析中的“维数灾难”( c u r s eo f d i m e n s i o n a l i t y ) 问题【i o j 【2 j 。比如只有8 8 个模式样本且分属于4 种疾病，每一个样本的特征都是2 3 0 8 维，本文需要就这样的数据进行类发现、聚类、特定癌症的基因模式发现、找出最有利 于区分这4 类病人所属疾病的基因个体或子集等。这些过去从未有过的小样本、超高维 空间数据分析问题就是目前生物信息学领域必须面对和需要解决的问题。 由这些可以看到，超高维空间超小样本是d n a 微阵列数据的独特特点。正是因为 这些特点造成了的严重的维数灾难现象，基因数据特征选择或特征降维是后续实现数据 江南大学硕士学位论文 的类发现、聚类、特定癌症的基因模式、发现找出最有利于分类的基因个体或子集等基 因数据分析的关键一步。在文献【1 3 】中，作者详细描述了由于大规模d n a 微阵列数据的 出现所带来的对机器学习、模式处理研究的巨大挑战。 所以，基因数据样本特征的超高维就带来了极具挑战性的新课题：基因数据的特征 选择或特征降维。d n a 微阵列数据的基因特征选择问题是一个超高维特征空间的特征 选择问题。 1 2 研究现状 正是由于上述各种研究和应用过程中特征维数的问题，各种减少特征维数的方法被 提了出来，但是它们大体上说来可以分为特征选择( f e a t u r es e l e c t i o n ) 和特征提取( 特征转 换) ( f e a t u r ee x t r a c t i o 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 ) 、因 子分析( f a c t o ra n a l y s i s ，f a ) 、多维标度( m u t i l d i m e n s i o n a ls c a l i n g ，m s ) 、投影追踪 ( p r o j e c t i o np u r s u i t ，p p ) 1 1 7 1 以及本文常见的f i s h e r 鉴别分析( f i s h e r d i s c r i m i n a n t a n a l y s i s ，f d a ) t 1 8 】。其中以主成分分析和f i s h e r 鉴别分析最为著名，应用最为广泛。而在 在非线性特征提取方法中，常用的有基于自组织映射( s e l fo r g a n i z i n gm a p s ，s o m ) 的特征 提取方【1 9 】，基于核的主成分分析和基于核的鉴别分析( k e m e lp c a 和k e m e lf d a ，分别 简记为k p c a 和k f d a ) t 2 3 】1 2 4 1 。前者通过自组织神经网络，后两者通过核函数( k e r n e l f u n c t i o n ) 实现输入空间到特征空间的非线性映射。基于核的特征提取及分类方法在国际 上得到了广泛研究，取得了丰硕成果，近年来也引起了国内部分学者的关；生【3 i 。 对于特征选择，比较著名的有基于贪婪算法的循序向前选择( s e q u e n t i a lf o r w a r d s e l e c t i o n ，s f s ) 、循序向后选择( 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 ) 、和增减选择( “p l u s l - t a k e a w a yr s e l e c t i o n ，p t a ) 以及在这些算法上改进后而得到的循序向前浮动搜索 ( s e q u e n t i a lf o r w a r df l o a t i n gs e l e c t i o n ，s f f s ) 、循序向后浮动搜索( s e q u e n t i a lb a c k w a r d f l o a t i n gs e l e c t i o n ，s b f s ) 2 5 1 。此外，还有基于遗传算法的特征选择( g e n e t i c a l g o r i t h m ，g a ) t 2 6 1 、基于t a b u 搜索的特征选捌2 7 】1 2 8 】以及基于数学规划的特征选择【2 9 】等。 大量实验表吲3 们，当样本特征维数小于5 0 时，s f s s 和s b f s 的性能要略优于s f s 、s b s 、 p t a 以及基于遗传算法的g a 等算法；而当特征维数大于5 0 时，则基于遗传算法的特 征选择方法具有较大的优判3 i 。 针对各种模式识别的应用领域，结合该领域的具体特点，各种特征降维方法也被提 了出来。例如在文本分类学习中，特征选取方法主要集中在大幅度降维的研究上，因为 高维的特征集对分类学习未必全是重要的和有用的。针对这样高维的特征集，在机器学 习中的许多特征子集的选取方法都不再适用，因而常常采用评估函数的方法。对特征集 中的所有特征进行评估，然后将得到的评估分数进行有序排列，取闭值范围内的特征形 成特征子集，而闭值的选取要根据具体问题的实验来确定。文本分类中，用于特征选择 常采用的评估方法大致有：特征频度( t e r mf r e q u e n c y ，t f ) 、文档频度( d o c u m e n t 4 第一章绪论 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 ) 、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 rt e x t ，w e t ) 、 几率比( o d d sr a t i o ，0 r ) 等。这些统计量从不同的角度度量特征对分类所起的作用。其 中文档频次、信息增益、互信息和x 2 统计在实际应用中都是非常有效的评估函数。用 这儿种评估方法进行特征选取后，再用k 最近邻、贝叶斯等分类法分类文本，会得到 一个平均精确度较好的结果f 3 1 1 【3 2 1 。 然而，在所有这些方法中，没有一种能够适用于任何情况下的特征降维需要。如何 针对不同的情况，从不同的角度和标准提出新的方法，始终都是特征降维技术研究和发 展的方向。 1 3 研究意义与目标 通过上面的介绍，本文可以了解到众多模式识别理论研究和应用领域都面临着高维 特征问题，因而特征降维技术就应运而生，它们在模式识别的过程中扮演着很重要得角 色。高维数据造成的维数灾难以及特征之间可能存在的相关性和冗余，都严重得影响识 别的准确性，甚至影响着识别方法的可行性和应用性。选择合适的特征来描述模式( 样 本) 不仅对模式识别的精度、需要的训练时间和需要的实例等许多方面都影响很大，并 且对分类器的构造也起着非常重要的作用【3 们。减少数据样本的特征维数，将有利于降低 数据的测试和储存要求，有利于减少训练和分类的时间，有利于避免维数的灾难，也有 利于提高分类、预测的效果掣列。可以应用特征降维技术来减少特征空间的维数，优化 特征空间，使之更有利于后续的分类。所以说，特征降维无论在理论还是在应用中都有 着重要的价值。 在本文中，依据特征对分类结果的影响和特征之间相关分析，探索了从另一个角度 提出一种新的特征降维方法。本文提出的方法主要是，依据特征对分类结果的影响和特 征之间相关性的分析并结合特征之间的相似度度量公式，在对特征聚类的过程中，采用 d bi n d e x 准则【3 5 】作为分类有效性的判断依据，最后在分析特征之间相关性。依据这个进 行了特征重要性排序的特征序列，选出需要的特征组合，从而达到降维的目的。本文的 研究目标是： 1 探索一种新的用于特征降维的特征排序方法，并验证它的有效性和可行性。 2 尝试考虑从特征之间的相关性、特征对分类结果的影响出发进行特征排序研究。 3 提供一种简单的针对无监督的特征排序和特征选择方法。 1 4 论文结构 本文由5 章组成，各章的主要内容安排如下： 第一章为绪论，分为4 个小节。第l 小节介绍了课题研究的背景；第2 小节简要介 绍了课题研究相关内容的研究现状；第3 小节则介绍课题研究的意义和目标；第4 小节 则介绍了本文的章节安排。 第二章是特征降维。这一章主要内容是较全面的总结和回顾特征降维的准则和主要 方法。第- d , 节主要介绍了特征降维的准则；第- d , 节则介绍了特征选择的主要方法； 江南大学硕士学位论文 第三节介绍了特征排序的内容；第四节介绍了特征提取的内容；最后两节简要的介绍了 聚类算法以及聚类有效性判断依据等内容。 第三章是聚类分析，重点强调了本文即将用到了层次聚类方法和k 均值聚类算法， 同时也着重细述了聚类有效性等一些准则，这些内容将在余下的几个章节中用到，是本 文的重点内容和基础。 第四章是一种基于特征分类的特征选择方法。在这一章中重点介绍了本文所采用的 用于衡量特征之间相似性的度量公式，并介绍了在本文提出算法中将要采用的方法。第 一小节主要介绍了特征之间相似性度量的公式以及推导过程，它是本文方法的重点，第 二小结则是通过大量的实验证明其可行性和有效性，最后则是对本章节中的一些内容继 续进行探讨和展望。 第五章是一种基于双聚类无监督的特征选择方法。这一章里介绍了基于双聚类无监 督的特征选择方法，即对特征维数和样本同时采用不同的聚类算法同时进行聚类，用实 验来验证它的可行性，并和现有方法的比较情况。在第1 小节里，详细介绍了特征之间 的相似性度量公式；第2 小节中，详细介绍了特征选择算法的主要思想，这是本章节的 中心部分；并在3 小节中用大量的实验来验证本文算法的可行性：最后在第4 小节里对 这一章内容进行了总结。 第六章为总结与展望。在这一章里，主要是对本文进行了回顾总结，并对以后的工 作和方向进行了展望。 6 第二章特征降维理论基础 第二章特征降维理论基础 通过前面一章的介绍，本文可以了解到，在样本数有限或不是很多的情况下，采用 过多的特征来进行分类器设计，无论从计算的复杂程度还是就分类器的性能来说都是不 适宜的。因而，研究如何把高维特征空间压缩到低维特征空间以便有效地设计分类器， 就成为一个重要的课题。这一过程也就是特征降维。 高维数据特征不仅可能造成维数灾难，而且其中可能存在较大的相关性和冗余，影 响识别的准确性。高维数据也对数据的测量、储存以及训练和应用时间提出了更高的要 求，以至在一些情况下根本不能满足这种要求。因而选择合适的特征来描述模式或样本 不仅对模式识别的精度、需要的训练时间和需要的样本数等许多方面都有较大影响，并 且对分类器的构造也起着非常重要的影响。这样，为了有效地进行数据分析，提高正确 识别率和降低计算工作量，特征降维就显得异常重要。特征选择和特征转换( 特征提取) 就是降维两种主要的方法。特征选择是选出有用的或重要的特征，而抛弃其他的特征； 特征转换是根据原来的特征空间再建一个新的特征空间。在实际应用中可将两者结合起 来使用，比如先进特征提取，然后再进一步选择其中一部分，或反过来。在这一章中， 本文将较为详细的介绍特征降维的相关内容。 2 1 类别可分离性判据 特征提取与选择的共同任务是找到一组对分类最有效的特征，有时需要一定的定量 准则( 或称判据) 来衡量特征对分类系统( 分类器) 分类的有效性。换言之，在从高维 的测量空间到低维的特征空间的映射变换中，存在多种可能性，到底哪一种映射变换对 分类来说最有效，需要一个比较标准来衡量。此外，选出低维特征后，其组合的可能性 也不是唯一的，故还需要一个比较准则来评定哪一种组合最有利于分类。 如上所说，特征选择与特征提取的任务是求出一组对分类最有效的特征。所谓有效 是指在特征维数减少到同等水平时，其分类性能最佳。因此需要有定量分析比较的方法， 判断所得到的特征维数以及所使用特征是否对分类最有利，这种用以定量检验分类性能 的准则称为类别可分离性判据。 一般说来，分类器最基本的性能评估是其分类的错误率。如果能用反映分类系统的 错误率大小的准则，在理论上是最合适的。但是，由于计算错误率要用到类条件概率分 布密度，计算是极其复杂的；而且实际问题中，这一分布常常不知道。所以很难构筑直 接基于错误率的判据，在实际中运用错误率来作为类别可分离性判据是非常困难的。为 此人们设法从另一些更直观的方法出发，设计出一些适用的类别可分离性判据，用来检 验不同的特征组合对分类性能好坏的影响，甚至用来导出特征选择与特征提取的方法。 它们作为实用判据时，一般说来需要满足以下条件【2 】： ( 1 ) 与分类的错误率的上界、下界有单调关系。如能做到这一点，当判据达到其最大 值时，一般说来其错误概率较小。 ( 2 ) 判据在特征独立时具有可加性，即： 三 以( 而，勤) = 厶( ) ， ( 2 1 ) 7 江南大学硕士学位论文 其中，| ! 是第f 类和第j 类的可分性判据函数，厶( 吒) 表示相应的七分量的可分性 函数。可分离函数愈大，则类的分类程度愈大。 ( 3 ) 具有度量特性，即 j i i 0 ，当i j 时； 以，= 0 ，当f - j 时； j q = j 小 ( 4 ) 在加入新的特征后，判据并不减少。即： 厶( 五，x d ) 厶( 而，x d ，劫+ 1 )( 2 2 ) 实际常用的类别可分离性判据中，主要有基于类内类间距离的可分性判据、基于概 率分布的可分性判据、基于熵函数的可分性判据。下面就这几种判据进行简要的介绍。 2 1 1 基于类内类间距离的可分性判据 不同的类样本占有不同的特征空间的区域，只要这些区域不相交叠，它们就可以分 开。所以，不同类的样本区域间的距离愈大，其可分性就愈大。所以经常用样本间的平 均距离作为特征提取的判据函数。样本间平均距离的判据函数的基本式子是： 拍，= 鬻喜弓嘉喜善垛， g 3 ， 其中，和7 分别表示第f 类和类的d 维特征向量，万( ，巧表示它们之 间的距离，c 为类别数，吩和刀，分别表示第f 类和类的样本数，p 和分别表示它们 的先验概率。向量间距离的度量主要有m i n k o w s k i 度量、欧氏距离名、c h e b y c h e v 距离万r 、平方距离和非线性度量氏等。在多数情况下利用欧氏距离测度2 1 。 在基于类内类间距离的可分性判据中，常常要用到类间散布矩阵、类内散布矩阵以 及总体散布矩阵。假设有数据样本有c 个类别，每个类别有珥( f - l ，c ) 样本。用心表 示第f 类的样本均值，则类简散布矩阵s 、类内散布矩阵瓯和总体散布矩阵s 分别定义 为： 咒= 寺珥( 一) ( 五一) 丁 ( 2 4 ) v f = l 乱2 专善善( 一以) ( 一鸬厂 ( 2 5 ) s = 墨+ 瓯( 2 6 ) 用期望值代替上式中的样本均值后，可以定义判踞： 以( x ) = t r ( & + s )( 2 7 ) 并且有： 山( x ) = 以( x )( 2 8 ) 8 第二章特征降维理论基础 从类内类间距离出发，还可以定义一些其它判据： 以( x ) = 护( s ：1 s ) ( 2 9 ) 一h 嘲 亿呐 加) = 鲁 ( 2 1 1 ) 怕) = 督 ( 2 1 2 ) 这几种判据都考虑到了类内类间距离。判据厶( x ) 是计算特征向量的总平均距离， 而其它判据则是基于使类间离散度尽量大，类内离散度尽量小的考虑而提出的。上述判 据中，j 2 、j 3 和以判据在任意一种非奇异线性变换下保持下变，以判据与坐标系相关 联。从应用角度看，以与j 3 判据无须存储任何矩阵，计算最方便。应用以可以得到在 两类和多类都有用的可分性的特征。而用以判据在其s ：1 的本征值丑( f = 1 ，d ) 中有一 个很大就会出现对两类有很好的可分性，但对多类中的其他各类的可分性不好【2 】。 这种基于距离度量是人们常用来进行分类的重要依据，因为一般情况下同类物体在 特征空间呈聚类状态，即从总体上说同类物体内各样本由于具有共性，因此类内样本间 距离应比跨类样本间距离小。后面将要介绍的f i s h e r 鉴别分析正是以使类间距离尽可能 大同时又保持类内距离较小这一种原理为基础的。这一类也被称为基于距离的可分性判 据。 2 1 2 基于概率距离判据的可分性判据 上面讨论的是直接利用样本在特征空间的距离作为特征降维的依据。该种原理直 观，计算简便。但是这种原理没有考虑概率分布，因此当不同类别的样本中有部分在特 征空间中交迭分布时，简单地按距离划分，无法表明与错误概率之间的联系。例如，对 于只有两类的情况，如果本文不考虑各类的先验概率，或假设两类样本的先验概率相等， 那末从两类条件概率分布可以看出，如果两类条件概率分布互不交迭，即对p ( xi 鸱) 0 处都有p ( xi 劬) = 0 ，则这两类就完全可分；另一种极端情况是对所有z 都有 p ( xc a , ) = p ( xl 吐) ，则两类就完全不可分。因此，人们又提出了与概率分布交迭程度有 关的距离度量方法，这些距离( 用，。表示) 有以下几个共同点： ( 1 ) ，。是非负，即j 。 = 0 ； ( 2 ) 当两类完全不交迭时，。达到其最大值； ( 3 ) 当两类分布密度相同时，- 厂。= 0 。 这种距离函数的一般式可表示为： ，( ) = i g p ( xq ) ，p ( xl 吐) ，丑，e 2 d x ( 2 1 3 ) 9 江南大学硕士学位论文 研究表明，只有在概率密度有参数形式时才能把判据写成便于计算的解析式，故经 常研究多维正态分布时的两类问题。这时常用以、以两个判据。 ( 1 ) c h e m o f f 界限以： 以= 一i ni p 5 ( x ic 6 ) p 1 5 i 吐) 出 ( 2 1 4 ) 式中s 在【0 ，1 闭区问中取值的参数。 ( 2 ) 散度以： 它被定义为区分q 与缈，类的总的平均信息，它等于两类平均可分信息之和： 厶= l p ( xq ) 一p ( xq ) 】l i l 揣出 ( 2 1 5 ) 2 1 3 基于熵函数的可分性判据 前面讨论的基于概率分布的距离判据是研究类条件概率分布定义的可分性判据。而 这里介绍一种基于后验概率分布的判据。 本文知道一个样本对于不同类的后验概率是贝叶斯决策的依据。因此在特征空间的 任何一点，如果它对不同类别的后验概率差别很大，则为分类提供了很明确的信息。而 信息论中的s h a n n o n 定义的熵就可以用来对可分类性作出评价。故这方面可分性判据的 定义称之为基于熵函数的可分性判据。 众所周知，最佳分类器是由后验概率决定的，如果对某些特征，各类后验概率都相 等，即 1 尸( ql x ) = 二 c 其中c 为类别数，则样本的类属就无法确定，或者只能任意指定样本所属类别。此 时 只：1 一! c 这也就是错误率最大的情况。 如果考虑另一极端，假设能有一组特征使得 p ( qx ) = l ，且p ( 缈，ix ) = l 。w f 那末此时的x 肯定可划分为以，而错误率为零。由此可看出，后验概率越集中，错 误概率就越小，反之后验概率分布越平缓，即接近均匀分布，则分类错误概率就越大。 为了衡量后验概率分布的集中程度，可以借助于信息论中熵的概念，制订定量指标。 例如s h a n n o n 熵为： 以= 一e p ( q ix ) l 0 9 2 p q m ( 2 1 6 ) 另一常用的平方熵： 1 0 第二章特征降维理论基础 研= 2 1 1 - 尸2 ( 哆例 ( 2 1 7 ) 两者都有熵函数的以下共性。 ( 1 ) 熵为正且对称，即函数式内项的次序可以变换不影响熵的值； ( 2 ) 如p ( c o , l z ) = 1 ，( 1 f c ) ，贝0 厶l = 0 ； ( 3 ) 如p ( 皑ix ) = l ，( 1 f c ) ，则l = 0 ； ( 4 ) 对任意的概率分布p ( 哆lx ) o ，1 ，( 1 f c ) ，以及e ( c o , ix ) = 1 ，则 百 尸( 哆ix ) - c 【尸( qix ) ，e ( a , cx ) 】皿( 二，二) ( 2 1 8 ) 因而这些函数都可用作各类别样本后验概率集中分布程度的定量指标。 2 2 特征选择 特征选择的含意是指由原有d 维特征所组成的特征空间中选出若干个有用的或重 要的特征，而抛弃其他的特征，组成描述样本的新特征空间，即从原有的d 维空间选取一 个k 维子空间( k d ) ，在该子空间中进行模式识别。为此有两个问题要解决，一个是 选择特性的标准，可以就是选择前面讨论过的可分离性判据，以这些判据为准则，使所 选择的k 维子空间具有最大的可分离性；也可以是某一个特定的学习算法在这一特征子 集上的正确识别率。另一个问题是要找出较好的特征选择方法，以在允许的时间内选择 出一组最优的特征。 特征选择大体上可分为筛选( f i l t e r ) 和复选( w r a p p e r ) 两大类叩3 1 。特征筛选根据判别 函数所得到的最优特征子集仅依赖于训练样本的统计特性，而与分类器所采用的学习算 法无关。相反，特征复选则依据分类器的学习算法在不同特征子集上的实际分类效果( 正 确识别率) 来评判各个特征子集的优劣。无论是特征筛选还是特征复选，从d 个原始特 征中选出势为k 的最优特征子集的最简单也是最可靠的方法是逐一评估所有谚个不同 的特征子集，从中挑选出满足判别函数需求最优的那一个特征子集。不容置疑，从理论 上讲，这种穷举法是一种能确保找到最优特征子集的最可靠的特征选择算法，但这种方 法计算量很大，在高维数据中是不