（计算机系统结构专业论文）基于rlsmars特征选择的文本分类方法研究.pdf

摘要 随着来自于互联网和企业内部网的信息不断增多，需要一种工具来帮助人们 对这些信息资源进行组织、存储和访问。自动文本分类是主要工具之。文本分 类( t e x tc l a s s i f i c a t i o n ，t c ) 就是将文档自动指派到预先设定类别的过程。自动文 本分类作为处理和组织大量文本数据的关键技术，可以在较大程度上解决信息杂 乱现象的问题，方便用户准确地得到所需的信息。 文本分类的一个主要的问题就是高维的特征空间。这些特征空间是由文档中 的词或词组构成的，对于一个中等程度的文档集可能就会形成成百上千万的特征 项。对于许多的学习算法来说这么高维的特征项是无法处理的，过大的特征空间 会导致“维数灾难 ，从而降低分类器的泛化能力，出现“过学习的现象。因 而在不影响特征准确度的情况下减少原来的文本描述空间是很有必要的。特征选 择与特征抽取有助于在文本数据集中移除噪音特征，降低维数。特征抽取是将原 始特征空间投影到一个低维空间从而创造出新的特征，通常是原始特征的线性或 非线性组合。特征抽取有助于解决多义词、同义词问题，但是不能给出新特征的 语义解释。特征选择是利用某种评价函数独立地对每个原始特征项打分，按分值 从高到低排序，从中选取若干分值最高的特征项。 特征选择方法的主要目的是在原始的特征空间中选择一个特征子集，组成 一个低维空间来表示原始特征空间。我们将e f r o n 的l e a s ta n g l er e g r e s s i o n ( 最小 角度回归) 方法和r e g u l a r i z e dl e a s ts q u a r e s ( 规则最小二乘) 方法相结合，提出了 规则最小二乘多角度回归( r l s m a r s ) 算法。该方法试图在特征空间中，寻找一 组方向，使得特征梯度矩阵能沿着这一方向变化，且特征梯度矩阵的模值越来越 小，在这一过程中，生成了一系列有序特征。新模型中特征选择方法主要考虑了 潜在变量之间( 文本词之间) 的关系，试图从原始特征集合中选取有效显著特征。 这些被选出来的特征之间的相关性很小，且与原始特征同分布。 通过r l s m a r s 特征选择技术，来提取核心特征是在多维空间中按照特征 的特性，设计算法在多角度中计算出相对最小角度，选出梯度下降方向，重新设 置梯度向量，从而提取到核心特征。r l s m a r s 特征选择技术，主要是研究在 低维数情况下特征选择的情况，在多个向量夹角中选出当前情况下的最小角度， 从而得到当前梯度向量的梯度下降方向，更新梯度向量值，选出函数拟合变量， 从而筛选出合理的特征。 我们的模型分别考察了类别不均衡与类别均衡情况下，参数二范数规范和参 数二范数忽略，各个数据集中各类的f 1 评估值情况。在r e u t e r 一2 1 5 7 8 语料库上 的试验表明，r l s m a r s 特征选择方法在考虑参数二范数规范的结果要比参数 二范数忽略情况下的要好很多。随着维数的增加，r l s m a r s 的分类效果在某 些类别上要优于卡方统计。 关键词：文本分类；特征选择；规则最d 、- - - - - 乘；最小角度回归；规则最小二 乘多角度回归。 a b s t r a c t a st h ev o l u m eo fi n f o r m a t i o na v a i l a b l eo nt h ei n t e m e ta n dc o r p o r a t ei n t r a n e t s c o n t i n u e st oi n c r e a s e ，t h e r ei sag r o w i n gn e e df o rt o o l sh e l p i n gp e o p l eb e t t e ro r g a n i z e ， s t o r e ，a n da c c e s st h e s er e s o u r c e s a so n eo fm a i nt o o l s ，t h et e x tc l a s s i f i c a t i o n ( t c ) i s ak e yt e c h n o l o g yt h a to r g a n i z e sa n dp r o c e s s e sl a r g ea m o u n to fd o c u m e n td a t at h r o u g h a p r o c e s st h a ta u t o m a t i c a l l ys o r t sa s e to fd o c u m e n t si n t oc a t e g o r i e sf r o ma p r e d e f i n e d s e t i tc a na l s os o l v et h ep r o b l e mo fi n f o r m a t i o nd i s o r d e rt oag r e a te x t e n t ，a n di s c o n v e n i e n tf o ru s e r st of i n dt h er e q u i r e di n f o r m a t i o nq u i c k l y t h eh i g h e rd i m e n s i o nf e a t u r e s p a c e i so n e m a j o rp r o b l e m i nt h et e x t c l a s s i f i c a t i o n t h eb a s i ct e r m si naf e a t u r es p a c ea r ew o r d sa n dp h r a s e s e v e ni na m o d e r a t e - s i z ed o c u m e n tc o l l e c t i o n ，t h ef e a t u r es p a c em a yh a v et e n so fh u n d r e d so f t e r m s m a n ys t a n d a r dc l a s s i f i c a t i o nt e c h n i q u e sc a nn o td e a lw i t hs u c hal a r g ef e a t u r e s e t l a r g en u m b e ro ff e a t u r e sw i l lr e s u l ti n “t h ec u r s eo fd i m e n s i o n a l i t y ”，a n d “o v e r s t u d y ”，a n dc l a s s i f i e r s p e r f o r m a n c ed e g r a d a t i o n t h e r e f o r e ，i ti sn e c e s s a r yt or e d u c e t h eo r i g i n a lt e x td e s c r i p t i o ns p a c ei ft h ea c c u r a c yo ff e a t u r e si sn o ta f f e c t e d f e a t u r e s e l e c t i o na n df e a t u r ee x t r a c t i o nw i l lh e l pr e m o v en o i s yf e a t u r e s ，a n dr e d u c et h e d i m e n s i o n a l i t yo ft e x td a t as e t s f e a t u r ee x t r a c t i o np r o j e c t st h eo r i g i n a lf e a t u r es p a c e o n t oal o w e rd i m e n s i o ns p a c ea n dc r e a t e sn e w ( e x t r a c t e d ) f e a t u r e s ，w h i c ha r eo f t e n l i n e a ro rn o n l i n e a rc o m b i n a t i o n so ft h eo r i g i n a lf e a t u r e s f e a t u r ee x t r a c t i o ni sh e l p f u l i n s o l v i n gt h ep r o b l e m sr e l a t e dt os y n o n y m ya n dp o l y s e m y , b u ti t i sd i f f i c u l tt o p r o v i d ead i r e c ts e m a n t i ci n t e r p r e t a t i o nt ot h en e wf e a t u r e s f e a t u r es e l e c t i o nm a r k s a n dr a n k se a c ho r i g i n a lf e a t u r eb yu s i n gs o m ee s t i m a t ef u n c t i o n s ，a n dt h e ns e l e c t st h e i t e m sw i t hh i g h e rr a n k s t h em a i np u r p o s eo ff e a t u r es e l e c t i o ni st os e l e c tas u b s e tw i t hal o w e r d i m e n s i o ns p a c ef r o mt h eo r i g i n a lf e a t u r es p a c e t h es u b s e tr e p r e s e n t st h eo r i g i n a l f e a t u r es p a c e t h i sp a p e rp r e s e n t sa ne f f i c i e n tm e t h o df o rf e a t u r es e l e c t i o n ，t h a ti s ，t h e r e g u l a r i z e dl e a s ts q u a r e s m u l t i a n g l er e g r e s s i o na n ds h r i n k a g e ( r t s - m a r s ) ， u s i n gac o m b i n a t i o no ft h ee f r o n s l e a s ta n g l er e g r e s s i o nm e t h o da n dt h e r e g u l a r i z e dl e a s ts q u a r e sm e t h o d t h em e t h o ds e l e c t st h eo r d e r i n gf e a t u r e si na m u l t i - d i m e n s i o n a lf e a t u r es p a c eb a s e do nt h ed i r e c t i o n sa l o n gw h i c ht h ef e a t u r e g r a d i e n tm a t r i xc h a n g e sa n dm o d u l u sv a l u e so ft h ef e a t u r eg r a d i e n tm a t r i xd e c r e a s e t h er l s - m a r sm e t h o dc o n s i d e r s t h e r e l a t i o n s h i pa m o n gl a t e n tv a r i a b l e s ，a n d s e l e c t sm o r ed i s t i n c ta n de f f e c t i v ef e a t u r e sf r o mt h eo r i g i n a lf e a t u r es e t t h es e l e c t e d i i i f e a t u r e sh a v et h es a m ed i s t r i b u t i o no ft h eo r i g i n a l s e tb u tt h e yh a v en oo rl i t t l e c o r r e l a t i o n t h er l s - m a r sf e a t u r es e l e c t i o n t e c h n i q u e ，am a i nm e t h o df o rf e a t u r e s e l e c t i o ni nal o w e rd i m e n s i o n ，d e t e r m i n e st h e k e r n e lf e a t u r e sf r o mam u l t i m m e n s i o n a ls p a c eb a s e do nf e a t u r e s p r o p e r t i e s i tc o n s i s t so ff o l l o w i n gs t e p s ：f 1 ) c a l c u l a t et h er e l a t i v em i n i m u ma n g l e sf r o mt h o s ev e c t o ra n g l e s ；( 2 ) d e t e 衄i n et h e c u r r e n tg r a d i e n td e c r e a s i n gd i r e c t i o no fv e c t o r sa n d r e - c o m p u t et h eg r a d i e n tv a l u e so f v e c t o r s ；a n d ( 3 ) s e l e c tt h ef i t t i n gv a r i a b l eo ft h ee s t i m a t i o nf u n c t i o nb e i n gu s e df o r s e l e c t i o no fr a t i o n a lf e a t l 】r e s e x p e r i m e n t so nr e u t e r - 2 1 5 7 8c o r p u ss h o w e dt h a ti n v e s t i g a t i o n0 nt h ee s t 蛔a t e d f 1v a l u e sf o rb o t hk e e p sa n dl e a v e s o u to ft h e l 2r e g u l a r i z e ri ne a c hc l a s si n d i c a t e s t h a tk e e p so ft h el 2r e g u l a r i z e rh a v eb e t t e rr e s u l t st h a nl e a v e s o u to f t h el 2r e 母l l 撕z e r u n d e rb o t ha s y m m e t r ya n de v e nc l a s s d i s t r i b u t i o na sd i m e n s i o ni i l c r e a s e s t h e p r o p o s e dm e t h o dc a p t u r e st h es e m a n t i ci n f o r m a t i o no ft h ec a t e g o r i e sa n dp e 怕姗s m o r ee f f e c t i v e l yt h a na f 2s t a t i s t i c so ns e v e r a lc l a s s e s k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；f e a t u r es e l e c t i o n ；r l s ；l a r s ；r l s m a r s i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：名晋签字日期：如j 彦年歹月矿日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) l 学位论文作者签名：力寻导师签名：五肌 签字日期：少o y 年。莎月矿日签字日期：m r 年万月矿日 基于r l s m a r s 特征选择的文本分类方法研究 1引 言 1 1研究背景 自上个世纪8 0 年代以来，互联网技术的发展使得信息技术迅速地渗透到社 会经济的各个领域。信息的来源是多方面的，比如报纸、电视、广播等等。近几 年来，随着i n t e r n e t 的普及和网络技术的不断完善，i n t e m e t 已经成为了全球最庞 大最丰富的信息资源库。由于i n t e m e t 的开放性，各类信息都能在第一时间发布 在i n t e r n e t 上。在人们的日常活动当中无时无刻不在获取信息，分析信息，并以 此来决策自我行为。从某种程度上来说，信息的拥有量已经成为决定和制约人类 社会发展的重要因素。 根据统计，互联网上在线发布的网页早已达到亿数量级，并以每天百万页 的速度增长。这些网页信息中包含的内容极为丰富，囊括了人类社会从政治、经 济、军事到生活、娱乐、体育的各个方面，而且这些信息又是完全开放的。从发 展趋势来看，互联网必将成为人们获取信息的最主要来源。然而，i n t e m e t 的开 放性也导致了i n t e r n e t 上信息的杂乱性和冗余性。因此，自动分类技术随着时代 的需求而蓬勃发展了起来。作为一种有效的信息处理方法，自动分类技术将各类 信息按照一定的分类体系进行分类整理，从而大大提高了用户搜集情报的效率。 因此，自动文本分类已经成为一项具有较大实用价值的技术受到广泛的关注，并 得到了空前的发展和应用，例如垃圾邮件过滤、邮件自动分类、网页搜索、网页 分类、主题索引和大型学术会议的论文组织于管理等等。 自动文本分类( 简称文本分类) 是将自然文本文件根据内容自动分为预先定 义的一个或者几个类别的过程【1 , 2 , 3 】。它是一种有指导的学习，根据一个已经被标 注的训练文档集合，找到文档特征和文档类别之间的关系模型，然后利用这种学 习到的关系模型对未被标注的文档进行类别判断。对自动分类技术的研究始于 5 0 年代末，h p l u l l i l 在这一领域进行了开创性的研究。1 9 6 0 年，m a r o n 在j o u r n a l o fa s m 上发表了关于自动分类的第一篇论文o nr e l e v a n c ep r o b a b i l i s t i ci n d e x i n g a n di n f o r m a t i o nr e t r i e v a l ，随后许多著名的情报学家，如k s p a r c h ，gs a l t o n 及 r m n e e d h a m 等都在这一领域进行了卓有成效的研究。到目前为止，对自动分 类的研究在国外经历了三个发展阶段：第一阶段( 1 9 5 8 - - 1 9 6 4 ) ，主要进行自动分 类的可行性研究；第二阶段( 1 9 6 5 - 1 9 7 4 ) ，进行自动分类的实验研究；第三阶段 ( 1 9 7 5 至今) ，进入实用化阶段。目前，越来越多的统计分类方法、机器学习方 法、数据挖掘技术和其它新技术被应用到文本自动分类领域中，如：回归模型、 最近邻分类器、规则学习算法、，相关反馈技术、专家投票分类法、人工神经网络 硕士学位论文 等，这些方法在参考文献【8 j 中有较好的综述。这些方法都能对一个预先分好类的 文本集合进行学习，获取每个类别的特征，从而自动生成分类规则，建立一个文 本分类器。它们的优势在于：在建立分类器时，不需要知识工程师和领域专家的 介入，大大节省了专家的人工劳动，却仍然能够获得与人工分类相当的分类精度。 在文本分类中，一般来说，在把文本表示为向量形式时，训练文本集中的 特征项可能多达数万个。通常认为，这些特征中的任何一个都对实现正确的分类 有着它的贡献。但是，在这些大量的特征中肯定还包含着许多彼此相关的特征， 这些相关的特征是冗余的，是可以去除的。过大的特征空间会导致样本统计特性 的评估变得更加困难，从而降低分类起的泛化能力，出现“过学习”的现象。而 且这种高维向量的处理具有极高的计算复杂度，尤其是会产生所谓的“维数灾 难”问题，因此，如何保留那些对分类起着重要贡献的特征，去除那些冗余的 特征，以减少特征总数，即如何进行维数约简，已成为一个日益重要的研究领域。 特征选择与特征抽取是维数约减常用的两种方法。特征选择的优点是，所 选择的特征都有很好的语义解释，但在文本分类中效果还不够理想。特征抽取能 够比较好地处理多义词、同义词问题，但是不能给出降维后所得到特征的语义解 释。 1 2 本文工作 从发展现状来看，文本分类技术现在已经相对成熟，但实用性强的技术仍 然比较缺乏。不少分类模型和特征提取算法复杂性较高，实现细节过于复杂，导 致训练和分类的效率低下，难以应付现实中庞大的数据集。 在文本分类中，卡方统计量( 矿) 、信息增益1 4 1 是特征选择常用的两种方法。 卡方统计量主要是比较两个及两个以上样本率( 构成比) 以及两个分类变量的关 联性分析。其根本思想就是在于比较理论频数和实际频数的吻合程度或拟合优度 问题。由于矿分布是一连续型分布，而样本的属性呈离散型分布，由此计算得 到的矿统计量的抽样分布亦呈离散型分布。为了改善矿统计量分布的连续性， 需要进行连续性校正。信息增益考虑了项未出现也可能对分类有贡献的情况，但 是，这种贡献远远小于它带来的干扰1 5 】。这两种方法从本质上来说都是贪心算法， 不一定能取得最优解；并且随着特征数目的提高，计算量逐渐增大。 e f r o n 于2 0 0 4 年提出了l e a s ta n g l er e g r e s s i o n ( 最小角度回归) 【6 】方法，并应 用于糖尿病人的病历分析，效果显著。s s k e e r t h i 在e f r o n 的基础之上，将最 小角度回归方法与传统二元分类器相结合 7 1 ，也取得了很好的效果。我们将规则 最小二乘分类器( r l s ) 与最小角度回归方法相结合，提出了规则最小二乘多角度 回归( r l s m a r s ) 算法，通过r l s m a r s 特征选择技术，来提取核心特征，在 多维空间中按照t e r m 的特性，设计算法在多角度中计算出相对最小角度，选出 基于r l s m a r s 特征选择的文本分类方法研究 梯度下降方向，重新设置梯度向量，从而选出特征。用这种方法从原始特征集合 中选取的特征具有显著特性，这些被选出来的特征之间的相关性很小，且与原始 特征同分布。该方法试图在多维空间中，寻找一组方向，使得梯度矩阵能沿着这 一方向变化，使得梯度矩阵的模值越来越小，在这一过程中，入选特征项。 r l s m a r s 特征选择技术，来提取核心特征，主要是研究在低维数情况下 特征选择的情况，在多个向量夹角中选出当前情况下的最小角度，从而选出当前 梯度向量的梯度的下降方向，更新梯度向量值，选出函数拟合变量，从而筛选出 合理的t e r m ；并考察不同拟合参数情况下( 参数二范数规范和参数二范数忽略) ， 分类器的分类效果。 本文运用线性回归分析和统计理论，开展了一些基于机器学习的特征选择 技术方面的研究工作。本文的工作主要包括以下几点： 1 介绍了规则最小二乘分类器( r l s ) 分类器和最小角度回归( l e a s ta n g l e r e g r e s s i o n ) 方法，分析了它们的特点及优点；并将这两种方法结合，提出了将规 则最小二乘分类器( r l s ) 与多角度回归方法相结合，设计了r l s m a r s 特征选 择算法来提取核心特征，在多维空间中按照t e r m 的特性，设计算法在多角度中 计算出相对最小角度，选出梯度下降方向，重新设置梯度向量，从而选出特征， 使得被选出来的特征之间的相关性很小，且与原始特征同分布； 2 在英文文本分类语料库“r e u t e r 2 1 5 7 8 ”下，验证了规则最小二乘多角度回 归( r l s m a r s ) 特征选择方法的性能； 3 在相同的文本数据预处理的情况下，使用不同的分类器，分析了卡方统 计特征选择与r l s m a r s 特征选择方法之间的性能差异； 4 分析了对判断函数中的参数二范数规范和参数二范数忽略两种情况下， 所选择的特征在不同分类器下的性能比较；得出对判断函数中的参数二范数规范 要比对判断函数中的参数二范数规范忽略的效果要好很多。 5 通过实验证明了数据集类别均衡情况下( 也即文档均匀分布于所有类别 时) ，相对于类别不均衡情况下( 也即文档分布不均匀) ，r l s m a r s 方法能够提 取出更好的特征。 1 3 论文组织 本文的组织如下： 1 引言：简介文本分类技术的研究背景、研究目的及其意义，分析国内 外文本分类的研究现状、研究重点，介绍了本文主要的研究工作。最后，给出本 文的整体组织结构。 2 文本分类综述：介绍文本分类的基本概念、分类的流程、应用领域以及 发展前景。同时详细介绍应用于文本分类的相关技术，按照文本分类系统的整个 硕士学位论文 流程介绍文本集合的预处理、文本表示方法、常用的分类器算法、文本分类器的 测试和性能的评价。 3 维数约减：简单叙述文本分类中常用的各种维数约减技术。 4 基于r l s m a r s 的特征选择：详细阐述了一种基于规则最小二乘多角 度回归( r l s m a r s ) 特征选择方法及其算法过程。 5 实验：给出了本文的实验过程与实验结果及结果分析。 6 总结与展望：对全文工作进行了总结，并提出下一步的工作展望。 4 基于r l s m a r s 特征选择的文本分类方法研究 2 文本分类概述 2 1文本分类的定义 文本分类( t e x tc a t e g o r i z a t i o no rt e x tc l a s s i f i c a t i o n ) ，缩写为t c ，是根据给 定文本的内容，将其判别为实现确定的若干个文本类别中的某一类或某几类的过 程。文本分类可以分为两个过程【9 j 。 1 首先建立一个模型，描述预定义的数据类集，为建立模型而被分析的数 据形成训练数据集，训练集中单个样本称为训练样本，它是随机地由样本群选取， 该步骤也称作有指导的学习( 即模型的学习在被告知每个训练样本属于哪个类的 “指导 下进行) 。它不同于无指导的学习( 或聚类) ，那里每个训练样本的类标 号是未知的，要学习的类集合或数量也可能事先不知道。通常，学习模型用分类 规则、判定树或数学公式的形式提供。这些规则可以用来为以后的数据样本分类， 也能对数据的内容提供更好的理解。 2 使用模型进行分类。测试集是在样本中随机选取，并独立于训练集的样 本。模型在给定的测试集上的准确率是正确被模型分类的测试样本的百分比。对 于每个测试样本，将已知的类标号与该样本的学习模型类预测比较。为什么模型 要使用测试集进行评估昵? 这是因为，如果模型的准确率根据训练数据集评估， 评估可能是乐观的，因为学习模型倾向于过分适合数据( 即是，它可能并入训练 数据中某些特别的异常，这些异常不会出现在总体样本群中) 。所以使用测试集。 如果认为模型的准确率可以接受，就可以用它对类别标号未知的数据样本进行分 类。这种数据样本在机器学习中也被称为“未知的”或“先前未见到的”数据样本。 2 2 文本分类的任务 文本分类系统的任务是【1 0 】：在给定的分类体系下，根据文本的内容自动地 确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，它将未标 明类别的文本映射到已有的类别中，该映射可以是一一映射，也可以是一对多的 映射，因为通常一篇文本可以同多个类别相关联。用数学公式表示如下： 彳上b ，其中，彳为待分类的文本集合，b 为分类系统中的类别集合，厂也就 是分类器；文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信 息，总结出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时， 根据总结出的判别规则，确定文本相关的类别。 5 硕士学位论文 2 3 文本分类系统的流程 实现文本的自动分类，必须要有完整的文本分类系统和一整套的数据处理 流程。然而计算机目前所具备的语言理解能力尚不足以处理原始的文本信息，因 此训练一个分类器需要经过一系列的预处理过程，然后抽取有效信息，用文档的 特征表示成为分类器能够处理的形式进行训练。一般来说，一个完整的文本分类 系统通常包括如下几个主要阶段：文本预处理、文本的表示、维数约减、分类器 的学习、分类器的测试以及性能评价，如图所示： 图2 - 1g 文本分类系统流程 1 文本预处理：处理文本信息的最初步骤。包括对文档集合进行格式分析 并提取出重要内容，中文分词、英文词干化、剔除停用词等操作。目前对于英文 的预处理技术相对比较成熟，对于中文来说，分词是最具有挑战性的难题。目前 处理方法有基于词典的方法、基于自然语言处理的方法和基于统计的方法。 2 文本集合的表示：将文本看成是出现在文本中的关键词的集合，这些关 键词就是特征项。为了能让计算机处理文本信息，通常将这些文档集用向量空间 模型( v e c t o rs p a c em o d e l ：v s m ) 来表示。 3 维数约减：由于从文本集合得到的特征数量很大，用众多的特征来表示 文本不仅不能提高分类效率反而会导致“维数灾难”。因此，必须利用一定的方法， 从特征集合中抽取若干最有利文本分类的特征项，并且按照一定的描述模型对文 本进行特征表示。 4 训练分类器：这是文本分类系统的核心。选择文档集合中的若干文档构 成训练集，利用一定的算法对该训练集合进行统计或者学习，确定分类器的各个 参数或者是阈值，最终构造一个分类器。 5 分类器的测试：用分类器对文档集合的测试集进行分类，得到分类结果。 。测试分为封闭测试和开放测试。 6 分类器性能的评价：采用一定的评价指标，对分类结果进行评价。不符 基于r l s m a r s 特征选择的文本分类方法研究 合要求时，需要返回到前面的某步骤，重新再做。 下面我们将上面几个处理模块分别进行介绍。 2 4 文本预处理 在计算机还不能够完全拥有智能化的极端，我们的文本分类系统还不能直 接处理原始文本信息，所以要进行预处理步骤。文本预处理是进行文本自动分类 的第一个步骤，预处理的好坏直接影响着分类结果。不同的语料库( c o r p u s ，也 称为文档集) 的存储格式不尽相同，特别有些语料库从互联网上直接抓取下来， 内容复杂，格式不规范并且编码格式多样。如果将这样的文档直接进行分类，这 些问题会严重影响分类系统后续的工作以及最终的分类效果。因此，必须经过一 定的处理，去除语料库中的噪音信息，规范化其内容，使得文档符合分类模型的 输入要求。 对于文本来说，我们知道在表示文本的语义方面，并不是所有的词语具有 同等的重要性，一些词语可能就比另一些词语携带更多的含义，比如：名词或是 一组名词具有很强的代表性。因此对于文档集中的文档进行预处理，确定哪些用 于索引项，是非常重要的。在这个预处理阶段的操作一般包括去除文档中的格式 标记、过滤非法字符、字母大小写转换、去除停用词和稀有词、词干化处理和中 文分词处理等处理步骤。 2 4 1 去除语料库的格式标记 每个语料库都有各自固定的存储格式，有的是网页格式，采用超文本标记 语言( h y p e rt e x tm a r k u pl a n g u a g e ：h t m l ) 描述；有的是半结构化的格式，自己 定义了一些标记；目前国际公开发布的标准文本分类语料库大部分则是采用了标 准通用标记语言( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ：s g m l ) 1 1 1 j 。 对于网页格式的文档，由于h t m l 文件中存在大量的格式信息标记符号， 在进行文本分类之前，我们必须根据格式标记提取出文档的主要内容，同时去除 无关的一些格式标记。例如，我们一般只关心文档的标题、正文和超链接描述， 处理时就可以通过 ， ， 等标签提取出相应的文档内容。目前 对于这类语料库，网上已经有一些开源工具以供研究者使用，例如s o u r c ef o r g e 网站上提供的h t m l 解析器：h t m l p a r s e r 以及微软亚洲研究院提供的基于视觉 的网页分割算法( v i s i o n b a s e dp a g es e g m e n t a t i o n ：v i p s ) 1 2 】等等。 2 4 2 去除停用词和词干化 并不是词的出现频率越高，它的代表性就越强。对于分类来说，在文档集 的文档中，出现频率高于8 0 的词是没有用的，这些词称为停用词( s t o p w o r d ) 。 英文的停用词包括冠词、代词、介词：a ，t h e ，i s 等等；中文包括“你”、“我”、“他”、 “的”、“呢”、“啊”等等。这些词本身没有太多的意义，而且往往频繁出现在每一 7 硕士学位论文 篇文档中；因此对文档之间的区分度不大，不具有分类贡献，在试验中我们通常 都滤掉这些词。一般来说，这样处理之后数据集可以压缩4 0 左右。但是去掉虚 词可能会减少招回率。 另外，文档集中的一些出现频率很低的稀有词也可以考虑滤去，因为这些 词可能是因为拼写错误偶然出现的【1 引。 在英文中，经常是文本中包含很多次的变异词，例如词的复数、动名词、 过去时态等形式的语法变异。词干化操作主要是对英文语料库而言，去除英文单 词的前缀、后缀提取单词的词根。英文的单词常由前缀、词根、后缀等部分组成。 具体到句子中，单词还有性、数、格以及时态引起的词形变化。但实际上，一个 单词的不同词形，还是可以认为是表示同一个意思。如c o n n e c t e d c o n n e c t i n g , c o n n e c t i o n ，c o n n e c t i o n s ，这几个单词就可以认为是表述同一个概念的；经过词干 化处理后，就可以提取出代表这四个单词的共同词干：c o n n e c t 。通过这样地处理， 这样就可以极大地减少文档集的文档特征项数量。 词干化处理常常采用基于自动机的规则方法，即将词形变化的规律总结成 规则，然后通过自动机的方法对词形进行转换。转换的过程当中可使用或者不使 用词典。但是，要做一个百分之百正确的词干化处理也是非常困难的，需要用到 词性分析、句法分析甚至语义分析的信息。好在，文本分类任务对词干化处理的 要求不是很高，利用不同词干化处理算法的分类结果相差不大。 目前使用最广泛的词干化处理算法是m a r t i np o r t e r 提出的p o r t e rs t e m m e r 算法【1 4 1 ，本文采用的也是这一词干化处理算法。 2 4 3 中文分词 用字母表示的语言，其分词有种天然的优势，即它们的分词是被空格或者 标点隔开，所以它们的分词是显而易见的。但是对于某些象形文字如中、日、韩 的文字却没有这样的优势。中文分词是中文信息处理所特有的步骤。与字相比， 词具有更多的语义信息，中文信息处理中词平台以上的技术都要以“词”为基 础，中文是一连串连续的汉字，词与词之间没有明显的分隔界限，无切分标志。 因此，自动识别词的边界，将汉字串切分为正确的词串的中文分词问题无疑是实 现中文信息处理的各项任务的首要问题i 目前的中文分词方法大致可以分为如下几类： 1 基于机械匹配的中文分词。即是通过对已有词典的机械匹配来得到分词 结果。所谓机械匹配，是指与已有词典里的词进行一一匹配，若在词典中找到某 个字符串，则匹配成功，匹配不到的词常以单字的形式输出。按照扫描方向的不 同，机械匹配分词方法可以分为正向匹配和逆向配配；按照不同长度优先匹配的 情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配【1 5 1 。使用较为广泛的是最大匹 配法( m a x i m u mm a t c h i n g ：m m ) ，该方法依据一个分词词表和一个基本的切分评 8 基于r l s m a r s 特征选择的文本分类方法研究 估原则，即“长词优先 原则，来进行分词。这种评估原则在大多数情况下是合 理的，但也会引发一些切分错误。 对于基于词典的分词方法，影响其精度的因素有：机器词典中词目的选择 和词条的数量、机器可读词典与待切分文本中词汇的匹配关系、切分歧义、未登 录词、分词方法。词典对分词精度造成的影响远远大于分词方法本身产生的歧义 切分错误1 1 6 1 。 2 基于统计语言模型的分词方法。该方法利用机器学习手段从语料库中直 接获取分词所需要的某些使用知识，因此就产生了基于统计语言模型( s t a t i s t i c a l l a n g u a g em o d e l s ) 的分词算法。该类算法的主要思想是：词是稳定的汉字组合， 在上下文中汉字与汉字相邻共现的概率能够较好地反映成词的可信度，因此对语 料库中相邻出现的汉字的组合频度进行统计，计算他们的统计信息并作为分词的 依据。基于统计语言模型的分词方法具有良好的切分歧义处理能力和识别新词的 能力，目前受到了越来越多的研究人员重视，发展较快。 3 基于人工智能技术的分词方法。应用人工智能中的神经网络和专家系统 来进行中文自动分词，以实现智能化的中文自动分词是近年来研究的一个热点。 该类算法的分词过程是对人脑思维方式的模拟，试图用数学模型来逼近人们对语 言认识的过程。 目前，国内有多家单位进行了中文分词方面的研究；其中包括清华大学、 北京大学、中科院计算所、微软研究院、东北大学和哈工大等多家研究机构。他 们在这方面研究取得了定的成果，并开发出了一些较为成熟的中文分词系统。 分词效果比较好的有中科院计算所井源项目“汉语词法分析系统i c t c l a s ”系 统( 下载地址为：h t t p ：w w w n l p o r g c n p r o j e c t ，p h p ? p r o j _ i d = 6 ) 。 2 5 文本表示方法 文档集预处理之后，我们必需把得到的文档信息转换为计算机可以接受和 识别的格式。从文本蕴涵信息的角度看，一个文本可以由特征项的权重和它们之 间的相互关系表示。全重信息可以由向量表示，特征项之间的关系可以由树、图 等带指针的结构表示。信息检索和文本聚类分类处理中要求定义一种距离函数， 用以表示文本之间的相似程度。如果用复杂的树或图的形式结构表示文本的话， 就很难定义一种合理的距离函数来表达它们之间的相似程度。而使用向量来表示 文本就不会遇到这种问题，数学中有很多种定义距离的方法，如：欧式距离、相 关系数等等。 为了处理的方便，通常的文本表示方法大都采用贝叶斯假设，这种假设把 组成文本的字或词对确定文本类别的作用认为是相互独立的，这样可以直接用文 档中出现的字或词的集合代替文档。在贝叶斯假设前提下，一个文本可以用字或 9 硕士学位论文 词等特征项的权重表示，特征项的权重信息可用向量表示，特征项之间的关系则 不予考虑。虽然，这种处理方式会丢失大量文档中的结构等内容信息，但文本只 使用向量表示要方便很多。文档的形式化的表示方式使得我们可以采用各种统计 和机器学习的方法对文档进行处理。从之前的研究结果看来，这种文本表示方法 在文本分类任务中能够取得较好效果的。 目前，在文本分类中，向量空间模型【1 8 1 9 ，2 0 】( v s m ：v e c t o rs p a c em o d e l ) 作 为一种常用的文本表示方法。在v s m 中，文档集被看作由一组正交词条0 1 ，t 2 ， 厶) 所张成的向量空间，每个文本可以看成空间的一个点( 向量) ：h 田= 1 a 2 ， 口 ) ，其中a f 为词条如的权值，表示该词条在文本中的重要程度。这样如果有m 个文本，则可以构成一个二维的m 咒阶的矩阵a ，其中第f 行代表第f 个文本， 第j 列代表第j 个词条( 特征项) ，彳玎则代表第歹个词条在第f 个文本中所具有的 权值。 权值的计算方法有很多，如概率方法，信息论方法等【2 1 , 2 2 ，2 3 1 ；判断词对于 分类提供的信息含量大小可以通过以下两条标准： 1 本类文章中出现频繁，而它类文章中出现不多的词，对于本类文章来说 具有较多的分类信息； 2