（计算机软件与理论专业论文）文本特征选择算法研究.pdf

、 辽宁师范人学硕七学位论文 摘要 数据挖掘是一个融合了数据库技术、人工智能技术、机器学习等多学科交叉研究的 领域。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。文本分 类是数据挖掘的一个重要的研究内容，而特征选择又是文本分类的关键技术和核心问 题。 在文本分类过程中，面对高维的文本特征空间，存在着大量的不相关特征和冗余特 征，因此许多学者采用各种方法试图去除文本特征空间中的不相关特征和冗余特征从而 得到一个近似最优的特征集合。目前，普遍采用的特征选择算法大都只可以去除文本的 不相关特征，对文本的冗余特征考虑的比较少，导致虽然可以大大的降低文本空间的维 度，但是分类结果不够精确。 本文首先对文本分类特征选择的一些经典算法进行了系统的分析和总结，然后在此 基础上提出了新的解决相应问题的特征选择算法： 首先，提出了一种基于动态规划思想的文本特征选择算法( d p f s ) ，该算法是从特 征的不相关性和冗余性的全局考虑，结合动态规划思想，通过对特征子集做不相关性和 冗余性分析，进而得到一个近似最优的特征集合。实验结果表明，该算法通过结合动态 规划思想，将计算出来的c 一相关和r 一相关进行存储，避免了大量的重复计算，提高了 程序的执行效率。另外，该算法对特征同时做了不相关性和冗余性分析，所以提高了特 征选择的准确度，从而也就大大的提高了文本分类的精确度。 其次，提出了一种改进的l a m 文本特征选择算法( i l a m f s ) ，该算法也是从特征的 不相关性和冗余性的全局考虑，在对特征集合进行了一次不相关性和冗余性分析的基础 上又做了二次冗余处理，所以得到了一个更为近似最优的特征集合。除此之外，此算法 采用的是线性计算，在某种程度上说，大大提高了计算的速度，同时为了解决阈值难以 给定的问题，该算法还结合了黄金分割，加权平均值等思想。实验结果表明，i l a m f s 算法对数据降维、阈值选择以及在降维过程中减少计算量和提高特征选择精确度是有效 的。 关键词：特征选择；冗余性；动态规划：加权平均值 氆常一 r e s e a r c ho na l g o r i t h m sf o rt e x tf e a t u r es e l e c t i o n a b s t r a c t d a t am i n i n gi saf u s i o no fd a t a b a s et e c h n o l o g y ，a r t i f i c i a li n t e l l i g e n c et e c h n i q u e s ， m a c h i n el e a r n i n ga n dm a n yo t h e ri n t e r d i s c i p l i n a r yr e s e a r c ha r e a s d a t am i n i n gi sf r o mal a r g e n u m b e ro f , i n c o m p l e t e ，a n dt h e r ei sn o i s e ，a n dv a g u e ，t h ep r a c t i c a la p p l i c a t i o no fr a n d o md a t a , e x t r a c t i n gi m p l i c i ti nt h ew o r k ，t h a tp e o p l ed on o tk n o w i na d v a n c e ，b u ti sp o t e n t i a l l yu s e f u l i n f o r m a t i o na n dk n o w l e d g e t e x tc l a s s i f i c a t i o ni sa l li m p o r t a n td a t am i n i n gr e s e a r c hc o n t e n t a n dt e x tc l a s s i f i c a t i o nf e a t u r es e l e c t i o ni st h ek e yt e c h n o l o g ya n dc o r e ：i s s u e s i nt h et e x tc l a s s i f i c a t i o np r o c e s s ，t h et e x to ft h ef a c eo fh i g h d i m e n s i o n a lf e a t u r es p a c e ， t h e r ea r eal a r g en u m b e ro fi r r e l e v a n tf e a t u r e sa n dr e d u n d a n tf e a t u r e s ，s om a n ys c h o l a r st r i e d t ou s ev a r i o u sm e t h o d st or e m o v et h et e x tf e a t u r es p a c ei r r e l e v a n tf e a t u r e sa n dr e d u n d a n t f e a t u r e si no r d e rg e ta na p p r o x i m a t i o no ft h es u p e r i o rf e a t u r es e t a tp r e s e n t ，t h ew i d e l yu s e d f e a t u r e s e l e c t i o na l g o r i t h mt or e m o v et h et e x ta r em o s t l yc o n f i n e dt oi r r e l e v a n tf e a t u r e s ， r e d u n d a n tf e a t u r e so ft h et e x tt oc o n s i d e ri sr e l a t i v e l ys m a l l ，l e a d i n gt ot h et e x ta l t h o u g ht h e y c a l ls i g n i f i c a n t l yl o w e rt h ed i m e n s i o no fs p a c e ，b u tt h ec l a s s i f i c a t i o nr e s u l t sn o ta c c u r a t e e n o u g h i nt h i sp a p e r f e a t u r es e l e c t i o nf o rt e x tc l a s s i f i c a t i o na l g o r i t h mo fs o m ec l a s s i c a ls y s t e m o fa n a l y s i sa n ds u m m a r y ，a n dt h e np u tf o r w a r do nt h i sb a s i san e wp r o b l e mt o s o l v et h e c o r r e s p o n d i n gf e a t u r es e l e c t i o na l g o r i t h m s ： f i r s t ，at e x tb a s e do nd y n a m i cp r o g r a m m i n gf e a t u r es e l e c t i o na l g o r i t h mt h o u g h t ( d p f s ) ， t h ea l g o r i t h mi sn o tf r o mt h ec h a r a c t e r i s t i c so fr e l e v a n c ea n dr e d u n d a n c yo ft h eo v e r a l l c o n s i d e r a t i o n ，c o m b i n e dw i t i ld y n a m i cp r o g r a m m i n g ，t h r o u g ht h e f e a t u r es u b s e td o n o t r e l a t e da n dr e d u n d a n c ya n a l y s i s ，a n dt h e ng e tan e a ro p t i m a lf e a t u r es e t e x p e r i m e n t a l r e s u l t ss h o wt h a tt h ea l g o r i t h mt h r o u g h ac o m b i n a t i o no fd y n a m i cp r o g r a m m i n g ，t h e c a l c u l a t e dc r e l a t e da n dr r e l a t e dt os t o r a g e ，t oa v o i dal o to fd o u b l ec o u n t i n g ，t oi m p r o v et h e p e r f o r m a n c eo fp r o g r a m s i na d d i t i o n ，t h ea l g o r i t h ma l s o d i dn o tf e a t u r er e l e v a n c ea n d r e d u n d a n c ya n a l y s i s ，s oi m p r o v i n gt h ea c c u r a c yo ff e a t u r es e l e c t i o n ，w h i c ha l s og r e a t l y i m p r o v et h ea c c u r a c yo ft e x tc l a s s i f i c a t i o n s e c o n d l y t h ep a p e rp r o p o s e s a ni m p r o v e dv e r s i o no ft h el a mf e a t u r es e l e c t i o n a l g o r i t h m ( i l a m f s ) ，t h ea l g o r i t h m i sn o tf r o mt h ec h a r a c t e r i s t i c so fr e l e v a n c ea n d r e d u n d a n c yo ft h e o v e r a l lc o n s i d e r a t i o n s ，t h er i g h tf e a t u r es e t t oan o n - c o r r e l a t i o na n d r e d u n d a n c ya n a l y s i sb e e nd o n eo nt h eb a s i so fas e c o n d a r yr e d u n d a n t ，s oig o ta ne x c e l l e n t 辽宁师范大学硕士学位论文 f e a t u r es e ti sm o r es i m i l a r i na d d i t i o n t h i sa l g o r i t h mu s e sal i n e a rc a l c u l a t i o n ，i naw a yt h a t g r e a t l yi m p r o v e dt h es p e e do fc a l c u l a t i o n ，w h i l et h et h r e s h o l di sd i 艏c u l tt os o l v eag i v e n p r o b l e m ，t h ea l g o r i t h ma l s oi n c o r p o r a t e s t h e g o l d e ns e c t i o n ，t h ew e i g h t e da v e r a g e ， e t c e x p e r i m e n t a lr e s u l t ss h o wt h a ti l a m f sd a t ad 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 m t h e t h r e s h o l ds e l e c t i o na n dd i m e n s i o n a l i t yr e d u c t i o np r o c e s st or e d u c et h ec a l c u l a t i o na m o u n ta n d i m p r o v et h ea c c u r a c yo ff e a t u r es e l e c t i o ni se f f e c t i v e k e yw o r d s ：f e a t u r es e l e c t i o n ；r e d u n d a n c y ；w e i g h t e da v e r a g e ；d y n a m i cp r o g r a m m i n g 文本分类特征选择算法研究 目录 摘要 。l a b s t r a c t i i l 绪论1 1 1 数据挖掘的基本定义- l 1 2 数据挖掘产生的背景及意义1 1 3 主要工作及论文组成1 2 文本特征选择的相关知识3 2 1 文本特征选择的基本概念3 2 2 文本特征选择算法的种类4 2 2 1 信息增益( i c ) “4 2 2 2 互信息( m i ) 4 2 2 3 文本频数( d f ) 5 2 2 4 开方校验( c h i - s q u a r e ) 5 2 2 5 期望交叉熵( e x p e c t e dc r o s se n t r o p y ) 5 2 3 文本特征选择现有算法存在的问题5 2 4 本章小结6 3 基于动态规划思想的文本特征选择算法一d p f s 7 3 1 相关知识7 3 2 基本思想8 3 2 1 动态规划思想8 3 2 2d p f s 文本特征选择算法的基本思想9 3 3 基于动态规划思想的文本特征选择算法9 3 3 1d p f s 算法的基本步骤9 3 3 2d p f s 算法的基本流程图1 0 3 3 3d p f s 算法描述1l 3 4 算法分析与比较12 3 5 本章小结1 4 4 改进的l a m 文本特征选择算法一i l a m f s 15 4 1 相关知识1 5 4 2l a m 特征选择算法16 4 - 3i l a m f s 特征选择算法基本思想17 辽j 师范大学硕+ 学位论文 4 4 改进的l a m 文本特征选择算法l7 4 4 i i l a m f s 算法的基本步骤1 7 ，4 4 2 i l a m f s 算法的基本流程图1 9 4 4 3 i l a m f s 算法描述2 0 4 5 算法分析与比较 2 2 4 6 本章小结2 4 结 论2 5 参考文献2 6 攻读硕士学位期间发表学术论文情况2 8 攻读硕士学位期间参与的科研项目2 8 致 射2 9 一v 一 辽宁师范大学硕士研究生学位论文 1 绪论 1 1数据挖掘的基本定义 数据挖掘的概念包含丰富的内涵，是一个多学科交叉研究领域。大致可以从统计学、 数据库和机器学习等三个角度进行定义。从统计学的角度，数据挖掘是指分析所观察的 数据集以发现可信的数据间的未知关系并提供给数据拥有者可理解的、新颖的和有用的 归纳数据。从数据库的观点来看，数据挖掘是指从存储在数据库、数据仓库或其它信息 仓库中的大量数据中发现有趣的知识的过程。从机器学习的角度，数据挖掘定义为从数 据中抽取隐含的、明显未知的和潜在有用的信息。 综合上述三种数据挖掘的定义，数据挖掘可以定义心1 为：数据挖掘( d a t am i n i n g ) 是从大规模数据集中抽取隐含的有意义的规律或模式的过程。 数据挖掘( d m ) 与数据库中的知识发现( k d d ) 是不同的，数据挖掘只是数据库中 的知识发现的一个步骤。 数据挖掘是一个包含了数据库技术、统计学、机器学习、可视化和信息科学的交叉 学科领域，它是当今信息技术学科最前沿的领域之一。 1 2 数据挖掘产生的背景及意义 近年来，随着计算机技术、存储技术及互联网的快速发展，大量的数据在企业、政 府部门、科研教学机构的服务器及计算机的数据库中累积起来。存储数据的爆炸性增长 业已激起对新技术和自动工具的需求，以便将海量数据转换成信息和知识1 。由于在这 些大量的数据中隐藏着许多有用但通过手工分析不出来的信息，所以在庞大的数据量面 前，许多组织陷入了数据丰富而信息贫乏的尴尬境地。如何充分利用数据，发掘出有用 的知识，成为广大拥有大量数据组织非常关心的问题。在此背景下，源自古老的数据分 析及统计技术，加上现代的人工智能、数据库和统计学相关的技术，产生了数据库知识 发现这门跨学科分支数据挖掘，即从数据中挖掘出有用的知识。 数据挖掘实质上是智能技术和数据库技术的结合，从2 0 世纪8 0 年代后期的出现到 9 0 年代的突飞猛进的发展，数据挖掘技术发展的时间并不长，但其在知识发现等领域起 到了很重要的角色。数据挖掘技术解决了信息时代数据爆炸，有用信息匮乏的问题，为 公司及个人的经济利益获取提供了很大的帮助。 1 3 主要工作及论文组成 本论文的主要工作及创新点： 辽宁师范大学硕士学位论文 第一从特征的不相关性和冗余性的全局考虑，结合了动态规划思想，将计算出来 的c 一相关和r 一相关进行存储，减少后续比较步骤的计算量，提高了算法的执行效率， 去除了文本特征向量空间的不相关性和冗余性特征，提高了文本分类的精确度。 第二对文本特征向量空间进行了二次冗余性分析，提高了文本特征选择的准确 度，并且采用了黄金分割和加权平均值等思想解决了文本特征选择过程中阈值选择难的 问题。线性计算的引入，减少了计算量，降低了算法的时间复杂度。 本文共分四章，第一章为绪论，介绍了数据挖掘的基本概念、研究背景及目前国内 外的研究现状；第二章介绍了文本特征选择的相关知识；第三章基于动态规划思想，介 绍了一种基于动态规划思想的文本特征选择算法( d p f s ) ，给出了新算法的执行步骤， 并进行了分析和实验比较；第四章基于l a m 特征选择算法，提出了一种改进的l a m 文本 特征选择算法( i l a m f s ) ，给出了算法的执行步骤，并对新算法进行了分析和实验比较； 最后对文本特征选择研究做出了总结。 辽宁师范大学硕士研究生学位论文 2 文本特征选择的相关知识 2 1 文本特征选择的基本概念 文本特征选择是文本分类过程中的一个关键技术和核心步骤。它是一种有效的高维 文本特征的降维方法。文本特征选择是指根据某个准则从众多原始文本特征中选择部分 最能反映模式类别统计特征的相关文本特征。如图2 1 所示，文本特征选择的过程大致 可以分为产生文本特征子集、文本特征子集评估、终止条件和最优文本特征子集等四个 部分1 4 - 6 1 。 图2 1 文本特征选择框架 f i g 2 1 t h ef r a m e w o r ko ft e x tf e a t u r es e l e c t i o n 学者们将文本特征分成三个互不相交的类别，即强相关性文本特征、弱相关性文本 特征和不相关性文本特征。设f 是所有文本特征的集合，f i 是其中一个文本特征，s j = f f i ，c 是给定的类别，则相关性的三种类别分别在下面给出l 7 j ： 定义2 1 强相关性如果文本特征f i 满足p ( c i f i ，s i ) p ( c l s i ) 则称文本特征f i 是与 类别c 强相关的。一个文本特征的强相关性表明该文本特征对一个最优的文本特征子集 总是必需的，在不影响最初的类别分布的情况下该文本特征不能被删除。 定义2 2 弱相关性如果文本特征f f 满足p ( c i f j ，s d - p ( c i s j ) ，且存在s ：cs ，使得 p ( c i f ，s i ) ：p ( c is ，) 则称文本特征f ，是与类别c 弱相关的。一个文本特征的弱相关性 表明该文本特征对一个最优的文本特征子集并不总是必需的，但是在某种条件下可能加 入到一个最优的文本特征子集中去。 辽宁师范大学硕士学位论文 定义2 3 不相关性如果文本特征f f 满足vs ，s f ，p ( c i f ，s f ) = p ( c 阱) 则称文本特 征f ，是与类别c 不相关的。不相关性表明该文本特征在最优特征子集中总是不必要的。 所以，一个最优文本特征子集应该是由强相关性文本特征和部分弱相关性文本特征 组成的。 2 2 文本特征选择算法的种类 文本特征选择算法是利用某种评价函数独立地对每个原始文本特征项进行评估，然 后将它们按评估值的大小按降序排序，从中选取若干个评估值最高的文本特征项。 一般的文本特征选择算法主要包括：信息增益o c ) 、互信息( m i ) 、文本频数( d f ) 、 开方校验( c h i s q u a r e ) 、期望交叉熵( e x p e c t e dc r o s se n t r o p y ) 、文本权i 正( t h ew e i g h to f e v i d e n c ef o rt e x t ) 掣引。 2 2 1 信息增益( ic ) 文本分类过程中，特征t k 的信息增益表示为 i g ( t k ) = 一 p ( c 1 ) l o gp ( q ) 滓1 mm( 2 1 )mm、二i + p ( t k ) yp ( c 。i r k ) l o g p ( c ：l t ：) 。p ( ) yp ( c ：i t - k ) l o gp ( c ：l 气) j_ l - 11 1 1 其中，p ( c i ) 表示类别出现的概率，p ( t k ) 表示训练集中出现文本特征t k 的概率，p ( c 。i t l c ) 表示文档中出现t k 时文档属于c i 的概率，e ( c ；i ) 表示文档中不出现文本特征t k 时文档 属于c i 的概率。文本是否出现特征都将为文本分类提供重要的信息，i g 是机器学习领 域常见的文本特征选择算法，特征选择时应该选择信息增益大的特征。 ，2 2 2 互信息( 川) m i 反映了文本特征与类别之间的相关程度，互信息越大，文本特征的出现就只依 赖于某一种类别；当m i - - o 时，文本特征与类别相互独立；当互信息是负数的时候，文 本特征就很少在该类别中出现。频度小的文本特征是互信息中的主要组成部分，在文本 特征选择时应选择互信息大的特征。但是因为互信息对低频文本特征有利，所以很容易 引起学习过度。 m l ( t k 砧2 i ) l 。g 揣2 善p ( q ) ( 1 0 9 p ( t k l q ) 一o g p ( t k ) ) ( 2 2 ) 一4 一 辽宁师范大学硕士研究生学位论文 2 2 3 文本频数( d f ) 文本特征的文档频率就是指在训练样本集中出现该文本特征的文档数，计算训练集 中每个文本特征的文档频率，滤除掉低于某个设定阈值的文本特征。文档频率的思想是 假设在于稀有特征携带少量有用信息或对分类影响不大。d f 是最简单的一种文本特征选 择方法，它耗费低、易于实现，在一定程度上起到了文本特征的降维作用，并取得了一 定的分类效果，如果某一稀有文本特征主要出现在某类训练集中，却能很好地反映类别， 而因低于某个设定的阈值而滤除掉，这样就会对分类精度有一定的影响。 2 2 4 开方校验( c h 卜s q u a r e ) n 表示所有文本特征的总数。c h i 和m i 很类似，文本特征的c h i 比较了文本特征 对一个类别的贡献和对其它类别的贡献，以及文本特征和其它文本特征对分类的影响。 t k 和c i 相关性越大，c h i 的值越大，在文本特征选择的过程中，应当选择c h i 统计值大 的文本特征。 瓷、 删( t k ) = p ( c i ) x ：( t 小i ) = 球) 壁黑嘉群 亿3 ， 2 2 5 期望交叉熵( e x p e c t e dc r o s se n t r o p y ) 当p ( c li r k ) 得值较大时，类别与文本特征就是强相关的，倘若p ( c t ) 在这种条件下较 小，那么该文本特征对分类的作用就比较大。e c e 反应了文本类别的概率分布以及在出 现某种特定特征情况下文本类别概率之间的距离。文本特征选择应当选取e c e 大的特征。 但是e c e 的缺点是它没有考虑文本特征没有出现的情况。 k ) = p ( q t k e c f ( t e ( t k ) p ( q i v ) l o g 黹( 2 4 ) )=等( 2 4 2 3 文本特征选择现有算法存在的问题 传统文本特征选择算法只注重单一特征的评价阳1 ，虽然可以大幅度提高分类器的性 能，但它们只对原始特征进行了类别不相关性的分析，而忽略了特征的冗余性分析，这 种情况会导致在文本特征高维的情况下，有些文本特征之间的相关性很大，并且它们与 类别的相关性也很大，于是这些相似的文本特征都被作为候选文本特征选入了最优文本 特征子集，导致了文本特征子集中存在着大量的冗余特征，从而影响了分类器的性能。 而这种情况在某些类别的训练集数目不足够多的情况下将会更加糟糕，因为在稀疏类别 中的文本特征比那些在主要类别中文本特征的评估值要低，传统的文本特征选择算法往 辽宁师范大学硕+ 学位论文 往会倾向于那些主要类别中的文本特征，而且有些文本特征选择算法采用的计算代价是 很大的。 2 4 本章小结 本章对文本特征选择的理论进行了概述，论述了文本特征选择的相关算法。本章研 究和论述的内容是本论文研究的基础和铺垫。 下面的第三章和第四章，针对目前文本特征选择算法的局限性提出自己的算法。 一6 一 辽宁师范大学硕士研究生学位论文 3 基于动态规划思想的文本特征选择算法一d p f s 文本特征选择过程中，对于原始文本特征空间维数过高，计算量过大，并且存在较 大不相关性和冗余性特征的问题。本章提出了一种基于动态规划思想的文本特征选择算 法1 ( d p f s ) 。 首先，结合动态规划思想，基于文本特征与类别的相关性分析，对原始文本特征集 合进行特征筛选，保留与类别具有强相关性和弱相关性的文本特征；然后，再次结合动 态规划思想，对文本特征子集做冗余性分析，滤除弱相关且冗余的文本特征；最后，得 到一个近似最优的文本特征子集。实验结果表明，此算法在对文本数据的降维和在降维 过程中减少计算量是有效的。 3 1 相关知识 定义3 1m a r k o vb l a n k e t 给定一个文本特征f 。，对于m 。c f ( f 萑m 。) ，如果m 。满足 公式p ( f - m 。- f 。，clf 。，m ；) = p ( f m 。一f 。，cm ，) ，则称m ，是关于特征f 。的一条m a r k o v b l a n k e t 盯1 。在m a r k o vb l a n k e t 的定义中，其条件指出m ，不只包含文本特征f 。与类别c 之间相关的信息，同时也需要包含文本特征f 。与所有其它特征之间的相关信息。强相关 文本特征不存在m a r k o vb l a n k e t 。 特征冗余n 3 3 一般是以文本特征的关联来确定，如果两个文本特征的数值完全的相 互关联，那么它们彼此是冗余的，实际上，当一个文本特征与一组文本特征部分地相互 关联的时候，不可能直接决定该文本特征是冗余的。 定义3 1 冗余特征设g 是当前文本特征集，如果一个文本特征是弱相关的，并 且存在g 中的一个文本特征子集m ，形成关于该特征的m a r k o vb l a n k e t ，则该文本特征 是冗余的。 定义3 2 对称的不确定量度r m i r m i ( x , y ) = 2 意。 其中，i ( x ：y ) 是指文本特征x 与文本特征y 之间的互信息，h ( x ) 和h ( y ) 分别是随机 文本特征x 和y 的信息熵。 定义3 3 互信息两个随机变量x 、y ，它们的密度分布函数分别为p ( x ) 、p ( y ) ， 联合概率分布为p ( x ，y ) ，则x ，y 的互信息为： 一7 一 辽宁师范大学硕士学位论文 舭= 肛y ) l 0 9 2 高出砂 ( 3 2 ) 当x 、y 为离散变量时，则： ，功= 莩弘圳。器出方3 ， 互信息越大，说明两个变量的相关性越强。 定义3 4 信息熵设x 是一个离散随机变量，它可能的取值为x 的概率为p ( x ) ， 那么： 觑= 蚤从圳喝高 4 ) 它可以作为数据集的不纯度或者不规则程度的量度。所谓的不规则程度指的是数据 集中数据元素之间的依赖关系的强弱。 为了表达方便，区别文本特征之间的两种类型的相关性，我们给出了以下两个定义。 定义3 5c 一相关任何的文本特征f 。和类别c 之间的相关度叫做c 一相关，用 r m i ( i ，c ) 表示。 定义3 6f 一相关文本特征f 。和f j ( i j ) 之间的相关度叫做f 一相关，用r m i ( i ， j ) 表示。 3 2 基本思想 3 2 1 动态规划思想 获得最优文本特征子集的问题与用动态规划法求最优解的问题相类似。在动态规划 法求最优解的问题中，经分解得到的子问题往往不是互相独立了。一般动态规划法分为 四个步骤：( 1 ) 找出最优解的性质，并刻画其结构特征；( 2 ) 递归的为最优解定义； ( 3 ) 以自底向上的方式计算出最优解；( 4 ) 根据计算最优解过程中得到的信息，构造 最优解。 动态规划的基本思想n 钔是能够保存已解决的子问题的答案，而在需要时再找出已求 得的答案，这样就可以避免大量重复计算，从而减少算法的执行时间。为了达到此目的， 可以用一个存储结构来记录所有已解决的子问题的答案。不管该子问题以后是否被用 到，只要它被计算过，就将该结果存储。我们将动态规划的这一基本思想结合到对特征 一8 一 辽宁师范大学硕十研究生学位论文 相关性和冗余性筛选的过程中，可以大大的减少c 一相关和f 一相关的计算量，从而提高 获取最优文本特征子集的效率。 3 2 2d p f s 文本特征选择算法的基本思想 d p f s 的基本思想是：基于文本特征相关性的三个定义，结合动态规划思想，对相关 性值进行存储，可以通过先去除不相关文本特征，然后再去除弱相关冗余文本特征得到， 最终得到一个近似优的文本特征子集。下面对这个算法进行详细的论述。 3 3 基于动态规划思想的文本特征选择算法 3 3 1d p f s 算法的基本步骤 s t e p l ：读取文本数据集并给定一个阈值，通过该阈值对各个数据集中的所有文本特 征的c 一相关值进行筛选。在训练过程中，发现随着阈值p 的增大，算法的运行时间会相 应减少，可以通过增大阈值来提高算法的运行速度。但是在实验过程中必须选择适当的 阈值，在提高运行效率的同时，避免去删除过多的文本特征。 帮n 舀 采用文本数据集m u l t i - f e a t u r e s 进行举例说明，如表3 1 所示，分别取阈值p = o 和p = o 1 ，随着阈值的增大，运行时间有大幅度的提高，而且两者具有相似的j 下确率。； 二：， 表3 1 不同阈值的比较 t a b l e3 1t h ec o m p a r i s o no f d i f f e r e n tt h r e s h o l d s 缸 ， 提取文本特征数运行时间( s ) 分类正确率 p = 01 3 03 0 2 s9 5 6 2 p = o 12 72 3 s9 5 8 9 s t e p 2 ：根据定义3 6 分别计算每个文本特征f ；的c 一相关，即r m i ( i ，c ) 。结合动 态规划的思想，依次将计算的c 一相关进行存储，然后比较预先给定的阈值和计算出的 r m i ( i ，c ) ，如果某个文本特征f ；的c 一相关大于预先给定的阈值p ，即r m i ( i ，c ) p ，则 该文本特征与类别c 的关联度较大，并由此可以确定文本特征f 。为与类别相关的文本特 征，将已选择的相关文本特征加入到文本特征子集n 中。 s t e p 3 ：对整个原始文本数据集进行了s t e p 2 的处理之后，将文本特征子集n 中的 文本特征按照c 一相关的大小按降序排列。在下一步做冗余性分析。将排在第一个的文本 辽宁师范大学硕士学位论文 特征直接添加到最优文本特征子集中，因为它的c 一相关最大，可以将其看成是强相关文 本特征。 s t e p 4 ：对s t e p 3 处理后剩下的相关文本特征做冗余性分析。通过估计文本特征之 间的关联性来实现冗余分析。在定义5 中，如果只考虑文本特征集f = f 。，f ， ，设m r - f ， 则p ( f - m 。- f 。，c i f 。，m 。) = p ( c i f 。，f j ) ，p ( f - m 。- f 。，c | m i ) = p ( c i f j ) ，即在该文本特征集中， 若p ( cf 。，f j ) = p ( cf j ) ，则f j 是关于f 。的一条m a r k o vb l a n k e t 。对于文本特征集中的文 本特征f 。和文本特征f 。，当r m i ( j ，c ) r m i ( i ，c ) 时，为了要维持文本特征与类别之间更 多的信息，所以将r m i ( i ，c ) 作为一个阈值来确定f 一相关r m i ( i ，j ) ，即文本特征f ，与文 本特征f 。之间的互信息是否比文本特征f 。与类别c 之间的互信息更多。分别计算每个文 本特征之间的f 一相关，即r m i ( i ，j ) 。 在这一步中，引入动态规划的思想，将计算出的f 一相关，存储到一个结构中，在进 行比较时，直接进行调取，而不用反复计算浪费时间，以便提高获取最优文本特征子集 的效率。 s t e p 5 ：如果r m i ( i ，j ) r m i ( i ，c ) ，那么将文本特征f 。从n 中移除，最终获得一个 近似最优的文本特征子集。 3 3 2d p f s 算法的基本流程图 图3 1d p f s 文本特征选择算法的算法流程图 f i g 3 ia l g o r i t h mf l o wc h a r to fd p f st e x tf e a t u r es e l e c t i o n 辽宁师范大学硕七研究生学位论文 3 3 3d p f s 算法描述 ( 1 ) 算法3 1 滤除不相关文本特征 输入：原始文本特征集合s ( f l ，f 2 ，f n ，c ) 和阈值p 输出：文本特征子集n ( 不含有不相关文本特征) 、 j 。 l 、b e g i n 。 2 、c a l c u l a t ei ：u m i ( i ，c ) f o rf i ； 一 + 严对集合s 中的每一个文本特征计算其c 相关 3 、s t o r er m i ( i ，c ) ；严分别对r m i ( i ，c ) 进行存储幸 4 、 i f ( r m i ( i ，c ) p ) ； “ 严调用存储的c 相关与阈值p 进行比较 5 、 a p p e n df i t o n ； 牛将文本特征f i 存放到新集合n 中 6 、e n d ； ( 2 ) 算法3 2 滤除冗余文本特征并得到近似最优文本特征集合 输入：文本特征子集n ( 不含有不相关文本特征) 输出：近似最优文本特征子集s b e s t l 、b e g i n 2 、o r d e rni nd e s c e n d i n gr m i ( i ，c ) v a l u e ； ， 严对集合n 中的每个文本特征按其c 相关的大小进行降序排列幸 3 、 f j = g e t f i r s t e l e m e n t ( n ) ； p 将排列在首位的文本特征当作强相关特征，作为最优为文本特征子集 的第一个特征 4 、d ob e g i n 5 、f i = g e t n e x t e l e m e n t ( n ，f j ) ；宰取下一个文本特征宰 6 、 i f ( f i ! = n u l l ) * 直到文本数据集取空为止 7 、c a l c u l a t er m i ( i j ) ；* 对集合n 中的每一个文本特征计算其f 相关 8 、s t o r er m i ( i , j ) ；木分别对r m i ( i , j ) 进行存储木 9 、 i f ( r m i ( i j ) r m i ( i ，c ) ) ；严调用存储的c 一相关和存储的f - 相关进行比较牛 1 0 、r e m o v ef if r o mn ；木将文本特征f i 从n 中移出 l l 、 f i = g e t n e x t e l e m e n t ( n ，f j ) ； 1 2 、e n du n t i l ( f i - = n u l l ) ； l3 、 f ：i 2g e t n e x t e l e m e n t ( n ，f g ； 辽宁师范大学硕士学位论文 1 4 ,e n du n t i l ( f j 2 2 。nu l l ) ； 1 5 、s b e s t = n ；* 得到近似最优文本特征子集 1 6 、e n d ； 3 4 算法分析与比较 本章提出的文本特征选择算法主要是针对高维文本数据的特征选择。在实验中，使 用了文本数据集2 0n e w s g r o u p n 6 3 中的s p o r t s 数据集作为实验的数据集，为了减少文章 中的噪声，首先对所有文档进行预处理，使用s t e m m i n g 的方法n 刚，完成名词复数的去 除、动词时态的转换、动词第三人称转换等工作。另外还要去除一些在文本中有很高的 出现频率对文本没有区分作用并且干扰关键词所起的作用的s t o p w o r d s 。数据集的原始 文本特征数为2 4 0 8 4 ，分为5 类。通过d f 过滤后，文本特征数为1 1 1 6 7 。利用本章提出 的算法( d p f s ) 对数据集进行文本特征提取，最终得到了2 4 8 7 个文本特征。在实验过 程中，把7 5 的数据集作为训练集，把2 5 的数据集作为测试集。 在文本分类领域中，常用的评价指标是准确率( p r e c i s i o n ) 和召回率( r e c a l l ) ， 准确率= 焉善黼；召回率= 葡蒺雾鬈瓣； 综合两个指标，可以得到一个新的综合评价指标，即： 蚴c r o f1