（计算机软件与理论专业论文）基于机器学习的文本分类研究.pdf

基于机器学习的文本分类研究 摘要 随着信息技术尤其是因特网相关技术的发展与成熟，人们可获得的 信息越来越多。面对海量信息，一方面是人们对快速、准确且全面获取 信息的渴望，而另一方面却是信息的杂乱无序。如何尽可能有效地组织 和管理信息，是信息处理研究的重要问题之一。因此，文本分类得到了 广泛关注，成为自然语言处理领域最重要的研究方向之一。本论文研究 了文本分类中特征提取，大规模文本分类和跨语言文本分类等问题。我 们主要解决下面三个问题，如何高效准确的进行分类、如何利用大规模 的文本分类数据以及如何在多语言环境下利用某种语言的训练集，去分 类另外一种语言的文本的问题。 本文的主要研究工作及创新点体现在以下五个方面： ( 1 ) 将一个基于概率解释的多类特征选择算法应用在文本分类中。 与将每个特征作为一个单一的个体的信息增益和x 2 统计量等传统方法相 比，这种多类特征选择的优势在于它通过线性支持向量机所特有的结构 风险最小化原则来选择一个好的特征集。实验中使用了三种常见的多类 分类器测试了该特征提取方法。实验结果均显示了该方法的有效性。 ( 2 ) 将最近邻算法的不同投票策略应用于文本分类中，并结合最小 最大模块化网络来处理大规模数据的文本分类。一般情况下，最近邻算 法在文本中采用相似性累加投票法，类似于机器学习中的反距离投票策 略。本文将机器学习研究领域中最近邻算法的不同投票策略引入到文本 分类中进行研究，而且进一步将它们引入到最小最大模块化网络中来处 理大规模的数据。实验结果显示，高斯投票能在文本分类中表现出较好 的综合性能。 ( 3 ) 将最小最大模块化支持向量机中的超平面数据划分方法应用在 大规模文本分类中。最小最大模块化网络在处理大规模数据时，通常有 三个问题，一个是集成什么样的分类器，第二个是模块冗余消除问题， 第三个是数据划分问题。这里研究了第三个问题，即使用超平面划分方 法到文本分类领域进行研究。传统的数据划分方法，一般使用随机划分 和聚类方法划分。然而，随机划分方法可能会破坏数据本身分布的空间 上海交通大学博士学位论文 属性，聚类方法划分又过于消耗计算资源。超平面划分方法一定程度上 克服了这两种方法的缺点。实验结果验证了该方法的有效性。 ( 4 ) 首次提出使用双语词典解决跨语言文本分类问题。在进行多语 言分析的时候，通常需要一些额外的双语资源来沟通两种语言的差异， 像双语电子词典，大规模的平行语料库和自动机器翻译等等。但是，跨 语言文本分类，至今没有使用双语电子词典方面的研究。本文提出了一 种跨语言朴素贝叶斯算法。该算法借助双语电子词典，第一次将单语言 的朴素贝叶斯算法扩展到了双语言上。初步的实验结果验证了该方法的 有效性。 ( 5 ) 提出了一种跨语言文本分类的精细框架。考虑到使用双语电子 词典的词汇覆盖率可能会影响到最终分类的性能，本文提出了在目标语 言中利用其语料之间的结构属性更新初始自动标注信息的思想。初步的 实验结果显示了该框架的有效性。 关键词：文本分类，特征选择，最小最大模块化网络，最近邻算法，支 持向量机，跨语言文本分类，朴素贝叶斯算法 一一 a s t u d y o nt e x tc a t e g o r i z a t i o nb a s e do nm a c h i n el e a r n i n g w i t ht h ed e v e l o p m e n ta n dm a t u r i t yo fi n f o r m a t i o nt e c h n o l o g y , e s p e c i a l l yt h ei n t e r n e t - r e l a t e dt e c h n o l o g y , p e o p l ec a no b t a i nm o r ea n dm o r ei n f o r m a t i o n f a c e dw i t had e l u g eo f i n f o r m a t i o n ，o nt h eo n eh a n d ，p e o p l eh a v ead e s i r ef o rf a s t ，a c c u r a t ea n dc o m p r e h e n s i v ea c t e s st oi n f o r m a t i o n o nt h eo t h e rh a n d ，i n f o r m a t i o ns t a y si na nu n e x p e c t e dw a y sa n dt h u s l o o k sd i s o r d e r l y h o wt oo r g a n i z ea n dm a n a g ei n f o r m a t i o na se f f e c t i v e l ya n de f f i c i e n t l ya s p o s s i b l ei st h ef o c u so fi n f o r m a t i o np r o c e s s i n g c o n s e q u e n t l y , t e x tc a t e g o r i z a t i o nh a se x t e n - s i v ea t t e n t i o n ，a n db e c o m eo n eo ft h em o s ti m p o r t a n tt a s k si nn a t u r a ll a n g u a g ep r o c e s s i n g t h i st h e s i sc o v e r sf e a t u r es e l e c t i o n ，l a r g e s c a l et e x tc l a s s i f i c a t i o na n dc r o s s l a n g u a g et e x t c l a s s i f i c a t i o n w eh a v ea t t e m p t e dt or e s o l v et h et h r e ei s s u e s t h ef i r s ti sh o we f f i c i e n ta n d a c c u r a t ec l a s s i f i c a t i o n ，t h es e c o n di st h eu s eo fl a r g e s c a l ed a t aa n dt h el a s ti st e x tc a t e g o r i z a - t i o ni nt h em u l t i - l a n g u a g ee n v i r o n m e n t ，t h a ti s ，h o wt oe x p l o i tt r a i n i n gc o r p u si na l a n g u a g e t oc a t e g o r i z ed o c u m e n t si na n o t h e rl a n g u a g e t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： ( 1 ) m u l t i c l a s sf e a t u r es e l e c t i o na l g o r i t h mi nap r o b a b i l i s t i cw a yi sa p p l i e dt ot e x tc a t e - g o r i z a t i o n c o m p a r e dw i t ht h et r a d i t i o n a lf e a t u r es e l e c t i o na l g o r i t h m s ，s u c ha si n f o r m a t i o n g a i na n dx 2s t a t i s t i c s ，w h i c hc o n s i d e re a c hf e a t u r ea l o n e ，t h ea l g o r i t h mc a np i c ko u tag o o d f e a t u r es e tb a s e do nt h es t r u c t u r er i s km i n i m i z a t i o no fl i n e a rs u p p o r tv e c t o rm a c h i n e s i no u r e x p e r i m e n t s ，t h r e ec o m m o nm u l t i c l a s sc l a s s i f i e r sa l eu s e dt ot e s tt h ea l g o r i t h m e x p e r i m e n - t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi se f f e c t i v eo v e rt e x td a t a ( 2 ) d i f f e r e n tv o t i n gs t r a t e g i e so fk n e a r e s tn e i g h b o r s ( k n n ) a r ea p p l i e dt ot e x tc a r e - g o r i z a t i o na n da r ec o m b i n e dw i t hm i n m a xm o d u l a rn e t w o r kt oh a n d l el a r g e s c a l et e x td a t a u s u a l l y , s i m i l a r i t yc u m u l a t i v ev o t i n gs t r a t e g yi sa d o p t e d i nt e x td a t a t h i si sv e r ys i m i l a rt o t h ei n v e r s ed i s t a n c ev o t i n gs t r a t e g y i nt h i st h e s i s ，d i f f e r e n tv o t i n gs t r a t e g i e so fk n ni nt h e m a c h i n el e a r n i n gf i e l da r ei n t r o d u c e di n t ot e x tc a t e g o r i z a t i o na n df u r t h e ra r ea p p l i e dt om i n m a xm o d u l a rn e t w o r kf o rl a r g e s c a l et e x td a t ap r o c e s s i n g e x p e r i m e n t a lr e s u l t ss h o wt h a t t h em e t h o d sw i t hg a u s s i a nv o t i n gs t r a t e g ya r eb e t t e rt h a nt h em e t h o d sw i t ho t h e rs t r a t e g i e s ( 3 ) ah y p e r p l a n ed a t ad e c o m p o s i t i o ni sa p p l i e di nm i n m a xm o d u l a rs u p p o r tv e c t o r m a c h i n ef o rt e x tc a t e g o r i z a t i o n w h e nm i n m a xm o d u l a rn e t w o r ki su s e dt oh a n d l el a r g e s c a l ed a t a ，t h e r ea r eu s u a l l yt h r e ep r o b l e m st ob es t u d i e d t h ef i r s ti sw h a tc l a s s i f i e rt o t t t 上海交通大学博士学位论文 e n s e m b l e ，t h es e c o n di sp r u n i n go fr e d u n d a n tm o d u l e sa n dt h et h i r di sd a t ad e c o m p o s i t i o n i nt h i st h e s i s ，s o m er e s e a r c hi sd o n eo nt h el a s tp r o b l e m ，t h a ti s ，a l la p p l i c a t i o no fah y p e r - p l a n ed a t ad e c o m p o s i t i o nt ot e x tc a t e g o r i z a t i o n t r a d i t i o n a ld a t ad e c o m p o s i t i o n su s u a l l yu s e r a n d o ms t r a t e g ya n dc l u s t e r i n gd i v i s i o ns t r a t e g y h o w e v e r , r a n d o md e c o m p o s i t i o nm a yu n - d e r m i n et h es p a t i a ls t r u c t u r eo fd a t a i ra c l u s t e r i n gm e t h o d i su t i l i z e dt od e c o m p o s eo r i g i n a l d a t a ，al a r g ea m o u n to fc o m p u t i n gr e s o u r c e sw o u l db ec o n s u m e d h y p e r p l a n ed a t ad e c o m - p o s i t i o nm e t h o dc a nt os o m ed e g r e ea v o i d t h ea b o v e m e n t i o n e ds h o r t c o m i n g s e x p e r i m e n t a l r e s u l t sv a l i d a t et h ee f f e c t i v e n e s so ft h eh y p e r p l a n ed a t ad e c o m p o s i t i o ni nt e x td a t a ( 4 ) f o rt h ef i r s tt i m e ，t h eu s eo fb i l i n g u a ll e x i c o ni nc r o s s - l a n g u a g et e x tc a t e g o r i z a t i o n i sp r o p o s e d m u l t i l i n g u a la n a l y s i s ，u s u a l l yr e q u i r e ss o m ea d d i t i o n a lb i l i n g u a lr e s o u r c e st o f i l lt h eg a pb e t w e e nt w ol a n g u a g e s t h e s eb i l i n g u a lr e s o u r c e sm a yb eb i l i n g u a ll e x i c o n ， l a r g e - s c a l ep a r a l l e lc o r p u so ra u t o m a t i cm a c h i n et r a n s l a t i o n ，e t c h o w e v e r , t h e r ei sl i t t l e r e s e a r c ho nt h eu s eo fb i l i n g u a ll e x i c o ni nc r o s s - l a n g u a g et e x tc a t e g o d z a t i o n t h i st h e s i s p r o p o s e st h eu s eo ft h i sb i l i n g u a lr e s o u r c e st os t u d yt h i sp r o b l e m a l s o ，ac r o s s l a n g u a g e n a i v eb a y e sa l g o r i t h mi sp r o p o s e d w el e v e r a g eb i l i n g u a le l e c t r o n i cd i c t i o n a r yt oe x t e n d t r a d i t i o n a ln a i v eb a y e sa l g o r i t h mt oac r o s s l a n g u a g en a i v eb a y e sa l g o r i t h m p r e l i m i n a r y e x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m ( 5 ) ar e f i n e m e n tf r a m e w o r kf o rc r o s s l a n g u a g et e x tc a t e g o r i z a t i o ni sp r o p o s e dt h e e s s e n c e t h el i m i t e dc o v e r a g eo fb i l i n g u a ll e x i c o nm a ya f f e c tt h ep e r f o r m a n c eo ft h er e - s u i t i n gc l a s s i f i c a t i o n c o n s e q u e n t l y , t h i st h e s i sp r o p o s e st h eu s eo ft h eo r i g i n a lc o r p u si na t a r g e tl a n g u a g et or e f i n et h ei n i t i a ll a b e l sf r o mt h et r a n s f e r r e dm o d e lv i aab i l i n g u a ll e x i c o n p r e l i m i n a r ye x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e df r a m e w o r ki se f f e c t i v e k e yw o r d s ：t e x t c a t e g o r i z a t i o n ，f e a t u r es e l e c t i o n ，m i n - m a xm o d u l a rn e t w o r k ，n e a r - e s tn e i g h b o r , s u p p o r tv e c t o rm a c h i n e s ，c r o s s l a n g u a g et e x tc a t e g o r i z a t i o n ，n a i v eb a y e s 一一 s v m s k 撼 m a m a s v m s m a k n n p c a e m m 限 l s i c l n b c c l m t 主要符号对照表 支持向量机( s u p p o r tv e c t o rm a c h i n e s ) k 最近邻算法( kn e a r e s tn e i g h b o r s ) 最小最大模块化网络( m i n m a xm o d u l a rn e t w o r k ) 最小最大模块化支持向量机( m i n - m a xm o d u l a rs u p p o r tv e c t o rm a c h i n e ) 最小最大模块化k 最近邻算法( m i n m a xm o d u l a rk n e a r e s tn e i g h b o r s ) 主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 期望最大化( 算法) ( e x p e c t a t i o nm a x i m i z a t i o n ) 机器翻译( m a c h i n et r a n s l a t i o n ) 潜在语义索引( l a t e ms e m a n t i ci n d e x i n g ) 跨语言朴素贝叶斯分类器( c r o s sl a n g u a g en a i v eb a y e sc l a s s i f i e r ) 跨语言模型转换( c r o s sl a n g u a g em o d e lt r a n s f e r ) 一一 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：吴科 日期：2 0 0 8 年5 月1 9 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密。 ( 请在以上方框内打“”) 学位论文作者签名：吴科指导教师签名：吕宝粮 日期：2 0 0 8 年5 月1 9 日 日期：2 0 0 8 年5 月1 9 日 第一章绪论 n o t h i n gi sm o r ep r a c t i c a lt h a nag o o dt h e o r y 1 1 研究的目的、意义及背景 电子计算机硬件技术的飞速发展，加上网络技术、数据库技术的普及和发展为 信息革命提供了技术保证和平台。现在，人类的大部分信息已经由纸质载体过渡到 电子载体，而且这种过渡正在加速发展。因特网更是一个透明的、覆盖全球的信息 网。通过因特网，人们可以方便地获取世界各地的信息资源，也可以向世界发布自 己已有的信息。这种开放、自由的信息共享和流动方式带来了信息的巨大积累。一 方面是人们对快速、准确且全面获取信息的渴望，而另一方面却是因特网上信息的 杂乱无序。如何尽可能地为用户提供满意的服务，是信息处理研究的重点，也是一 件非常有意义的任务。为了给信息检索提供更高效的搜索策略和让其返回更准确的 检索结果，人们应该采取措施对网上的信息进行有序地组织，把相关的文档组织在 一起。文本分类因此得到广泛的关注，成为信息处理领域最重要的研究方向之一。 对于信息检索，文本分类能够在以下几个方面上有帮助： 加速检索过程和提高检索性能。传统信息检索在网络文本库中搜索用户输入的 关键字检索条件，出现了关键字的文本即被检出返回给用户。如果文本库中文 本数目过多，这个过程将是非常耗时的。同时，这种基于关键字的简单匹配算 法，检索性能不高，会返回很多不符合用户要求的无关文本。文本分类使相似 ，的文档组织在一起。输入查询将表示成一个亡维向量，然后将该向量与每个类 的质心进行比较。搜索过程处理最相似的那些类，即那些与输入向量相似度大 于某个阈值的类。这样可以加速检索过程，并提高检索i 生能。 组织检索结果。通过文本分类技术，可以把信息组织成目录树结构，使用户通 过预分类的目录来浏览网页信息，这种提供目录检索网页的方式使得用户可以 在较短的时间内找到所需的相关信息。y a h o o ! 就支持这种目录结构的网页浏 览。 个性化信息推送。采用自动文本分类算法可以为用户提供主动的，个性化的信 息推送服务。通过跟踪一段时间内用户浏览过的网页，分析出用户的兴趣，然 后可以有针对性地进行主动服务。 一1 一 上海交通大学博士学位论文 信息过滤。在因特网上，不仅存在大量的有用信息，同时也潜伏着许多垃圾信 息和危险信息。如何避开那些令人讨厌的，甚至是危险的信息，比如垃圾邮 件、黄色信息、恶意代码、病毒、木马等，文本分类同样能够在这些方面有所 帮助。 除了信息检索方面，文本分类还能在下列方向上发挥作用。像新闻专线 过滤( n e w s w i r ef i l t e r i n g ) 1 】、专利分类( p a t e n tc l a s s i f i c a t i o n ) 【2 】和网页分类( w e b p a g ec l a s s i f i c a t i o n ) 【3 】都是文本分类应用的领域。另外，文本分类已经在现实世 界中的一些领域得到了应用。比如，垃圾邮件过滤( s p a r ef i l t e r i n g ) 【4 】、文档作 者归属( a u t h o r s h i pa t t r i b u t i o n ) 【5 】、作者性别侦测( a u t h o rg e n d e rd e t e c t i o n ) 6 】、文 体分类( g e n r ec l a s s i f i c a t i o n ) 7 】7 、调查编码( s u r v e yc o d i n g ) 【8 】和态度分类( s e n t i m e n t c l a s s i f i c a t i o n ) 9 】等等。 另外，从研究的角度来讲，文本分类中数据往往具有的高维、稀疏、多标号等 特点，这些往往是机器学习需要解决的问题，因此文本分类在机器学习方面具有重 要的价值。反过来，机器学习方法在文本分类中的应用，也为机器学习的发展和应 用提供更多的佐证，同时，为文本分类提供更多的理论支持。 1 2 文本分类的发展过程 随着计算机硬件技术和网络技术的高速发展以及计算机的普及，计算机处理和 存储数据的能力不断提高，特别是因特网的普及，电子文档成指数级的增长，加上 人们对于信息的需求，基于内容的文档管理在信息检索中己获得了显著的地位。文 本分类便是其中一项任务。 自动文本分类是信息检索、机器学习和计算语言学这些领域的交叉学科【1 0 。 它的理论研究可以追朔到2 0 世纪6 0 年代初【1 1 1 。它的发展过程大致可以划分为三 个阶段： 第一阶段是2 0 世纪8 0 年代前。1 9 6 1 年，m a r o n 1 2 】最早提出了关于文本自 动分类的研究。在那个时候，它被称为自动标引。这个名字反映了当时文本分类主 要应用在布尔信息检索系统自动索引科学文章方面。在这一时期，模式识别也正发 展成为一门学科。1 9 6 3 年，r o s e n b l a t t 设计了感知机( p e r c e p t r o n ) ，通过具有阈 值的神经元处理二类的分类问题【1 3 】；g e r a l ds a l t o n 提出了向量空间模型( v e c t o r s p a c em o d e l ，v s m ) 用于对文本进行描述【1 4 】。这阶段主要是集中在对分类理论 的研究，应用方面则主要是用于信息检索。这一时期采用的方法主要是词匹配法。 第二阶段是2 0 世纪8 0 年代。这一阶段主要是采用传统的知识工程( k n o w l e d g e e n g i n e e r i n g ) 技术，根据专家提供的知识形成规则，手工建立分类器。这实际上 是专家系统。h a y e s 等的c o n s t r u e 1 】是典型的代表。在这一时期，信息检索技 一2 一 第一章绪论 术逐渐成熟应用，为文本分类提供了许多技术支持，最著名的m 系统是s a l t o n 的 s m 脚 1 5 。 手工建立分类器的缺点在于：一是依赖于专家：二是面向领域，一旦应用领域 变化，需要重新生成规则。三是分类器建设周期长，工作量大，分类质量难以保 证。 第三阶段是2 0 世纪9 0 年代以后。互联网技术的发展，对文本分类提出了迫切 要求。在这一时期，文本分类的主要特点是采用统计机器学习方法，自动建立分类 器 11 】。基于机器学习的文本分类方法克服了以前手工建立分类器的缺点，使得文 本分类具有了真正的实用价值。 相对于知识工程的方法它有一些优点：一是文本分类被自动地建立，分类知识 来源于机器对训练集的自动学习，不再依赖于领域专家；二是学习和分类过程不需 要人工干预，分类效率和准确率得以提高。 目前所说的文本分类主要是指第三阶段的基于机器学习的文本分类。因此，文 本分类的研究严格来说只有十几年的历史。在开始时期，研究的重点是将机器学 习、信息检索等相关领域中的成果应用到文本分类中【1 6 ，1 5 】。随着研究的深入， 文本分类问题被进一步细化，研究人员对各个子问题进行深入研究，例如：分类方 法，特征降维，性能评价，j r d , 样本学习，分类性能推广，语言知识利用等 11 】。 试图在对文本内容更多理解的基础上，提高文本分类的效果 1 7 ，1 8 】。 我们一般研究的文本分类通常指的是二类或多类文本分类。但是，现实中一个 文本往往拥有多个类别标号，我们把这种文本分类称为多标号文本分类。多标号文 本的研究开始于2 0 世纪9 0 年代末期，处理多标号文本分类最简单的做法就是将它 分解为多个二类问题【1 9 ，2 0 】。另外一种方法就是标号排序 2 1 - 2 3 】。最近，研究人 员将重点放在利用类之间的关系来提高多标号文本分类的分类效果。在 2 4 】中，在 使用的产生式模型( g e n e r a t i v em o d e l ) 中考虑了任意两个类别之间的关系。2 0 0 5 年， z h u 等人【2 5 】提出一个最大熵模型来获取类之间的关系。在 2 6 ，2 7 】中，基于潜在 语义的不同方法被提出来获取不同类之间的关系。在 2 8 】中，r o u s u 等人利用给定 层次结构的类的相互关系，来做多标号文本分类。2 0 0 6 年，在 2 9 】中，根据现实 世界，类别多，训练样本少的特点，提出了一个约束非负矩阵分解的半监督多标号 学习方法。虽然这样，我们在这篇文章中仍然研究多类文本分类这个基本的研究问 题。 另外，随着因特网的进一步发展，非英语语种的文本越来越多，怎样把这些文 档组织好，从中挖掘有效的信息显得越来越重要。另一方面，随着全球化的发展； 越来越多的公司和组织需要管理多语种的文本。这是一个非常年轻的学科。它是机 器学习、跨语言检索、机器翻译和词义消歧多个研究方向的交叉学科。据作者了 一3 一 上海交通大学博士学位论文 解到的情况，跨语言分类最早出现在2 0 0 3 年，荷兰的b e l 等人【3 0 】在其p e k i n g 项 目中第一次提出了跨语言文本分类。他们将跨语言分类分为两类：一种是多语种 ( m u l t i 1 i n g u a l ) 训练；另一种是跨语种( c r o s s l i n g u a l ) 训练。前者是指不同语言书写的 文档都带有标号，训练在这些文档集上完成；后者是指使用带有标号信息的语言的 文档进行训练，测试在另外一种语言的文档中完成。目前，后一种类型的跨语言 分类研究的比较多。2 0 0 5 年，来自马里兰大学的o l s s o n 3 1 】在英语和捷克语之间 做了跨语言分类。同一年，意大利的r i g u t i n i 3 2 】使用基于e m 的算法来做跨语言的 分类问题。f o r t u n a 【3 3 】使用机器翻译工具获得伪双语来训练核典型相关判别分析 ( k c c a ) 而得到语义空间。y a o y o n gl i 【3 4 】使用获得的双语运用核典型相关判别分 析( k c c a ) 来做日英跨语言分类。g l i o z z o 等人 3 5 】利用可比较语料库( c o m p a r a b l e c o r p u s ) 和双语词典来做跨语言分类。这是一个新兴的方向，目前研究主要集中在文 本的表示问题上。在本文中，我们将提出一个新的解决方案对这个问题进行进一步 的研究。 1 3 国内外研究现状 1 3 1 文本标引 对文本标引的研究主要是确定特征单位。特征单位决定了对文本内容描述的数 据粒度。英文中常用的特征单位有词( w o r d ) 、词串( w o r dn g r a m ) 和词组( p h r a s e ) 。 采用词对文本进行标引时，每个特征就是在文本中出现的词；词串是指在文本中出 现的固定长度的多个词 3 6 - 3 9 】；词组是指在文本中出现的不固定长度的多个词，可 以是句法意义( s y n t a c t i c a l l y ) 上的词【4 0 ，1 8 】，也可以是统计意义( s t a t i s t i c a l l y ) 上的词 【4 1 ，4 2 】。采用词作为特征，标引简单，而且很有效。到目前为止，在英文文本集上 的实验结果表明，基于词的标引是最适合文本分类的。相对而言，词串和词组是更 复杂的标引方式。直觉上，它们应该更能描述文本中独立的概念，具有更强的文本 内容描述能力。在实验中，它们的效果比词标引差。原因是尽管它们具有更好的语 义描述能力，但是统计性能很差，不适合于现在采用的基于统计的机器学习方法。 但是，为了实现对文本内容的理解，使分类能够更多地基于文本内容，采用更好的 描述方法和特征单位是达到此目标的第一步。部分学者尝试利用特征的语法和语义 信息进行学习【1 7 】，以获取文本中更多的知识。 在【4 3 】中，s h e n 等人将文本标引分为四种情况：( 1 ) 使用词组表示 4 4 ，4 0 ，4 5 】； ( 2 ) 使用词的语义表示 4 6 ，4 7 】：( 3 ) 通过文章中的隐含概念增强文本表示【4 8 】；( 4 ) 使用语言模型表示【3 7 - 3 9 】。 在【4 4 】和【4 5 】中，作者们通过被抽取的词组来表示文本。短语的抽取依赖于像 w o r d n e t 和m e s h 树结构主体等现存的主体中的背景知识。在【4 4 】中，s t e p h a n 等 一4 一 第一章绪论 人调查了在三个数据集上的效果，结果显示了这个方法的有效性。通过抽取基于公 共可用的知识库u m l s 的短语，y e t i s g e n - y d d i z 和p r a t t 在一个由医疗文本组成的数 据集上得到了与 4 4 】中一样的结论。在【4 0 】中，l e w i s 使用语法分析来得到标引词 组。这些词组对应原始文档某种特定语法关系的词对。这些语法关系包括动词和主 语的中心名词( h e a dn o u no fs u b j e c t ) 的关系，名词和修饰形容词的关系等等。但是， 短语数据稀疏性使估计短语的相对频率很困难。而且，语法短语表示出现高度的冗 余性并且有很多噪音数据。为了解决这个问题，l e w i s 将这些短语先做聚类，识别 出冗余的短语，然后作为一个整体来处理。虽然短语聚类改进了性能，但是改进并 不是特别显著。作者将这归因于语法分析器的性能不太好。k e h a g i a n s 等人【4 6 】使 用w o r d n e t 定义了一个语义空间，然后比较了四种文本表示方法( w o r db o o l e a n ， w o r d f r e q u e n c y ，s e n s eb o o l e a n 和s e n s ef r e q u e n c y ) ，实验证明这种使用词义空间的 方法并没有什么优势。r a m a k r i s h n a n 和b h a t t a c h a r y y a 使用排好序同义词向量来表示 文档。为了得到排好序的同义词，他们使用w o r d n e t 中的同义词和词汇关系为每个 文档建立一个语义图。一些基于图的排序算法被用来排序这些同义词。在2 0 新闻组 语料库上的实验显示，基于排序算法的表示方法能改进分类性能。2 0 0 3 年，c a i 和 h o f m a n n 提出了使用概率潜在语义分析( p l s a ) 产生的表示来补充词或词组表示的 特征。实验证明想法的正确性。另外，语言模型使用在前n 1 个词后的一个词的概 率来对语言建模。2 0 0 4 年，b a i 等人和p e n g 等人都在文本分类上使用语言模型， 证明了它表示文本的有效性。 关于中文的特征单位，一些研究是基于词特征的 4 乳5 4 】，另外一些研究是基于 n g r a m 特征的【5 5 - 5 9 】。2 0 0 6 年李景阳等人【6 0 】对n g r a m 特征和词特征在中文文 本分类中的使用进行了全面的比较。作者们发现，在大多数情况下基于字的二元特 征要好于词特征。 在文本分类中，广泛使用向量空间模型v s m 【1 4 】来标引文本。在v s m 中，文 本d 被看成是由特征二元组组成的特征向量( f e a t u r ev e c t o r ) ： d = ( 亡1 ，w l a ) ，( t 。， 3 。d ) ) 其中：( t k ，w k d ) ，1 忌8 为特征如的二元组，2 1 3 k d 为如在文本d 中的权重，s 为 特征集的大小。在v s m 中，没有考虑特征在文本中的位置信息以及语法作用等，一 个文本向量是一个词袋( b a go fw o r d s ) 。一个特征向量对应于高维特征空间中的一个 点，这时可以简化为公式1 1 。这时，特征向量对应于下面的权重向量： d = ( w l d ，叫。d ) 一5 一 ( 1 2 ) 上海交通大学博士学位论文 在向量空间模型中，由于文本被描述为向量，因此对文本的各种操作就可以借助向 量运算进行，例如文本的合并、删除、比较等操作，文本与文本之间的相似度可以 用向量之间的相似度来度量。 1 3 。2 特征降维 在v s m 中，文本数据通常是稀疏高维数据。例如中等规模英文文本集的词特征 集的大小( 在本文中，特征集的大小与特征空间的维数是同一个概念) 通常超过十 万。而这些高维的特征集对分类学习未必全是重要和有效的，同时高维特征集会加 剧机器学习的负担。是否进行特征降维对文本分类的训练时间、分类准确性都有显 著的影响，而且分类器的算法和实现的复杂度都随特征空间维数的增加而增加。所 以，特征集的降维操作是文本分类准确率和效率的关键。特征选择( 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 ) 是特征降维中的主要方法。以下分别对特征选择和 特征抽取中涉及的不同方法进行介绍。 1 3 2 1 特征选择 特征选择就是从特征集t = 亡1 ，屯】p 中选择一个真子集r = 亡1 ，亡。，) ，满 足s 8 。其中，8 为原始特征集的大小，8 7 为选择后的特征集大小。选择的准则 是经特征选择后能有效提高文本准确率。选择没有改变原始特征空间的性质，只是 从原始特征空间中选择了一部分重要的特征，组成一个新的低维空间【6 l 】。文本分 类中，用于特征选择的统计量【11 ，6 1 - 6 3 】大致有：特征频度( t e r mf r e q u e n c y ) ，文 档频度( d o c u m e n tf r e q u e n c y ) ，特征熵( t e r me n t r o p y ) ，互信息( m u t u a li n f o r m a t i o n ) ，信息增益( i n f o r m a t i o ng a i n ) ，x 2 统计量( c h i - s q u a r e ) ，特征权( t e r ms t r e n g t h ) ， 期望交叉熵( e x p e c t e dc r o s se n t r o p y ) ，文本证据权( w e i g h to fe v i d e n c ef o rt e x t ) ，比 值比( o d d sr a t i o ) 等。这些统计量从不同的角度度量特征对分类所起的作用。 1 3 2 2 特征抽取 特征抽取也叫特征重参数化( f e a t u r er e p a r a m e t e r i z a t i o n ) 【4 l 】。由于自然语言 中存在大量的多义词、同义词现象，特征