（计算机应用技术专业论文）基于信息论的文本分类模型与算法研究.pdf

中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 摘要 随着网络上文本信息爆炸式的增长，文本分类已成为非常重要的研究方向。 为了面对时代的挑战，本文针对文本分类问题进行了深入的研究，取得了一系列 突破性进展。 本文在研究了现有分类模型的基础上，提出了文本分类的信息论模型。该模 型以信息论为基础，将文本所提供的关于各个不同类别的信息作为分类的依据。 文本分类的信息论模型从另一个的角度来思考文本分类问题，具有一定的理论价 值。同时，该模型统一了传统的朴素贝叶斯法和基于k l 距离的中心向量法两种 不同的分类模型，为研究统一的分类算法奠定了基础。而且，该模型在各种不同 的语料库上都表现出了非常高的分类性能。 根据文本分类信息论模型的基本思想，以互信息最大化原则为指导，本文提 出了一种新的特征选择算法和两种特征聚类算法。并从实验上证实了该特征选择 算法优于传统的特征选择算法。在保证分类准确率降低不到2 的条件下，特征 聚类算法可以将文本特征空间的维数降低2 3 个数量级，大大降低了文本特征的 数量。 为了进一步推广文本分类的信息论模型，本文基于广义信息论模型的基本理 论，提出了文本分类的广义信息论模型。该模型为文本空间中的各个特征赋予不 同的权重，区分重要的特征和不重要的特征。不同于特征的其它属性，特征的权 重无法通过公式直接计算得到。为了计算特征的权重，本文从不同的角度提出了 两种权重学习算法基于错误驱动的特征权重学习算法和基于免疫进化的特 征权重学习算法，并且从实验上验证了这两种算法的有效性。 关键词：文本分类、信息论、特征选择、特征聚类、免疫进化算法 中国科学技术大学硕士学位论文 基于信息论的文本分类模型与算法研究 a b s t r a c t w i t ht h ee x p l o s i v eg r o w t ho ft e x ti n f o r m a t i o ni nt h ei n t e m e t ，t e x tc l a s s i f i c a t i o n h a sb e c o m eav e r yi m p o r t a n tr e s e a r c hd i r e c t i o n t of a c et h ec h a l l e n g eo ft i m e s ，t h e p a p e rg i v e sad e e ps t u d yo nt e x tc l a s s i f i c a t i o n ，a n da c h i e v e sas i g n i f i c a n tp r o g r e s s w i t ht h eb a s i so ft h es t u d y i n go fe x i s t i n gc l a s s i f i c a t i o n m o d e l ，t h ep a p e r p r o p o s e s at e x t c l a s s i f i c a t i o n i n f o r m a t i o n t h e o r ym o d e l t h em o d e lb a s e s o n i n f o r m a t i o nt h e o r y , a n dc l a s s i f i e st e x t a c c o r d i n gt o t h ei n f o r m a t i o ng a i n e df o r d i f f e r e n t c l a s s e s t e x t - c l a s s i f i c a t i o n i n f o r m a t i o n t h e o r y m o d e lr e s o l v e s t e x t c l a s s i f i c a t i o np r o b l e mf r o ma n o t h e ra n g l e ，w h i c hh a ss o m et h e o r yv a l u e m e a n w h i l e ， t h em o d e lu n i f i e sn a i v eb a y e s i a na n dc e n t e r v e c t o rb a s e do nk u l l b a c k - l e i b l e r d i v e r g e n c et w ok i n d sc l a s s i f i c a t i o nm o d e l s ，e s t a b l i s h e saf o u n d a t i o nf o rs t u d y i n gt h e u n i f i e dc l a s s i f i c a t i o na l g o r i t h m a n d ，t h em o d e ls h o w sav e r yh i 曲c l a s s i f i c a t i o n p e r f o r m a n c eo nv a r i o u st e x tc o r p u s e s b a s e do nt h ei d e ao ft e x t - c l a s s i f i c a t i o n - i n f o r m a t i o n t h e o r ym o d e la n dt h e g u i d a n c eo fm u t u a li n f o r m a t i o nm a x i m i z a t i o n ，t h ep a p e rp r o p o s e so n en e wf e a t u r e s e l e c t i o na l g o r i f l 】l - na n dt w of e a t u r ec l u s t e r i n ga l g o r i t h m s a n di th a sv e r i f i e dt h a tt h e f e a t u r es e l e c t i o na l g o r i t h mi ss u p e r i o rt ot 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 f r o me x p e r i m e n t s ，w i t ht h el o s so fa c c u r a c yl e s st h a n2 t h ef e a t u r ec l u s t e r i n g a l g o r i t h mc a r lr e d u c et h ed i m e n s i o no ft e x tf e a t u r es p a c eb y2 - 3o r d e r so fm a g n i t u d e ， w h i c hm o r ee f f e c t i v e l yr e d u c e dt h ef e a t u r es p a c e f o re x t e n d i n gt h e t e x t - c l a s s i f i c a t i o n - i n f o r m a t i o n - t h e o r ym o d e l ，t h ep a p e r p r o p o s e san e w t e x tc l a s s i f i c a t i o nm o d e lb a s e do ng e n e r a li n f o r m a t i o nt h e o r y i nt h i s m o d e l ，e v e r yf e a t u r eh a saw e i g h ti no r d e rt od i s t i n g u i s hi m p o r t a n tf e a t u r e sa n d u n i m p o r t a n tf e a t u r e s u n l i k eo t h e ra t t r i b u t eo ft h ef e a t u r e ，t h ew e i g h ti su n a b l et o c a l c u l a t ed i r e c t l y t h ep a p e rp r o p o s e st w oa l g o r i t h m sf o rc a l c u l a t i n gt h ew e i g h to f t h e f e a t u r e ，o n eb a s e d o nm i s t a k e d r i v e n ，a n dt h eo t h e ro n eb a s e do ni m r f l u n e e v o l u t i o n a r ya l g o r i t h m ，a n dv e r i f i e st h ev a l i d i t yo ft h e s et w oa l g o r i t h m sf r o m e x p e r i m e n t s k e y w o r d s ：t e x tc l a s s i f i c a t i o n ，i n f o r m a t i o nt h e o r y , f e a t u r es e l e c t i o n ，f e a t u r e c l u s t e r i n g ，i m m u n ee v o l u t i o n a r ya l g o r i t h m i i l 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 致谢 首先，衷心感谢我的导师曹先彬教授，感谢他三年来对我孜孜不倦的教诲。 这三年来，曹老师渊博的知识、敏锐的思维、高深的学术造诣和严谨的治学态度 使我受益匪浅。在学术问题上，曹老师的高瞻远瞩总让人有一种豁然开朗的感觉。 尤其重要的是，曹老师在教育我们做学问的同时，也教育了我们做人的道理。曹 老师自身积极奋斗、永无止境的探索精神将永远激励我在今后的工作中刻苦努 力，力求上进。 然后感谢联想实验室的老师和同学，他们在我平时的研究过程中和论文的完 成过程中提供了很多的帮助，营造了良好的研究氛围。感谢郭圆平博士生、华北、 郑先荣、尹鸿章、许言午、陈达、张卫、魏闯先、马静小妹妹等同学们和远在天 津的刘健小妹妹对我工作生活上的帮助和鼓励。在此，一并表示感谢。 同时也要感谢计算所的程学旗研究员、郭莉研究员和许洪波副研究员对我论 文研究过程中的指导。他们对我研究的课题进行了认真的分析和细心的指导，对 于实验结果进行了充分的讨论，并提出了很多真知灼见。 感谢我的亲人们! 十多年来，自己的大部分时间都远离了父亲、母亲、姐姐、 妹妹，但他们对我的关心与支持未减分毫，衣食住行、冬寒夏暖无一不是他们的 牵挂。父母亲给予我的支持和教诲使我不断地努力和成长，他们的关爱与期望是 我今后更加努力的动力。 最后，感谢中国科学技术大学七年来对我的培养。今日我以我是科大的学生 而自豪，希望明日科大以我是科大的学生而骄傲。 段建国 2 0 0 6 年5 月 中国科学技术大学硕士学位论文 基于信息论的文本分类模型与算法研究 第一章引言 随着计算机技术的发展、w e b 应用的逐步普及，数字媒体正在引发不断膨胀 的数字海啸。作为数字信息中最主要的表现形式，文本数据正在以指数级的速 度不断膨胀。文本数据的膨胀带来了一系列新的科研挑战，基于人工的传统的信 息处理方式已不能满足信息分析的需要，所以建立一套有效的文本分类系统已迫 在眉睫。 对于文本分类模型的研究已逐渐成熟，目前正在向产业化的方向发展，但并 不意味着文本分类的研究已达到了完美的状态。纵观目前的研究成果，在算法的 模型和算法的性能方面还有很大的提升空间；在理论方面，现在从各个角度提出 了大量的计算模型，但是分类问题没有一个统一的理论基础。本文在现有模型的 基础上，从信息论角度来研究文本分类问题，提出了文本分类的信息论模型、基 于互信息最大化的特征压缩算法和特征权重的学习算法等。 本章将简单地介绍文本分类的问题描述、评价指标，讨论文本分类系统的研 究意义及可能的应用范围，并观察了文本分类系统的研究现状，最后给出了本文 的工作和内容安排。 1 1 文本分类系统的问题描述 文本自动分类是数值分类学与信息处理技术相结合而产生的研究方向。在最 初的分类学中，人们往往通过经验和专业知识对事物进行定性分析，很少使用数 学工具。随着信息的不断增长，信息之间的关系也日益复杂，从而导致分类程度 越来越细，分类规模越来越大。这时仅仅依靠定性分析将无法满足要求，于是人 们引进类统计学、人工智能等各种工具，从而形成了数值分类学( n u m e r i c a l t a x o l o g y ) ，大大推动了信息处理技术的步伐【2 j 。 简单地说，文本分类系统的任务是：在给定的分类体系下，根据文本的内容 自动地确定文本关联的类别。系统的输入是需要进行分类处理的大量文本，而系 统的输出为每一篇文本对应的类别。从数学的角度来看，文本分类是一个映射的 过程，它将未标明类别的文本映射到已有的类别中。该映射可以是一一映射，也 可以是一对多的映射，因为通常一篇文本可以同多个类别相关联。该映射用数学 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 公式表示如下： ，：d 斗c ，d = d ，d ：，d 。 ，c = b ，c 2 ， ( 1 1 ) 其中，d 为待分类的文本集合，c 为文本的类别集合。 文本分类的映射规则r 是文本分类系统的关键，它是根据已经掌握的每类若 干样本的数据信息，总结出分类的依据而建立的判别公式和判别规则。根据总结 方法的不同，这些判别公式和判别规则也有所不同。传统的方法有：中心向量法、 r o c c h i o 、朴素贝叶斯、w i n n o w 、k 近邻、支持向量机和神经网络等。 1 2 文本分类系统的评价指标 文本分类问题从根本上说是一个映射过程，评价的主要方法就是映射的效率 ( 速度) 和映射的准确程度。 在给定输入和分类体系的情况下，映射的速度取决于映射规则的复杂程度。 系统建立的映射规则越复杂，分类时所需的时间代价就越大。 映射的准确程度往往通过分类的结果与标准参照物进行比较而得到，这里所 说的参照物就是通过专家思考判断后给出的文本分类结果。分类的结果与专家分 类结果越接近，分类的准确程度就越高。所以，这里隐含了评估文本分类系统的 两个指标：准确率和召回率。 准确率是分类系统判断正确的文本数量占分类系统中实际文本数量的比率。 准确率的定义为 准确p r e c i s i o n ) = 蒹罴 ( 1 2 ) 召回率是分类系统判断正确的文本数量与专家判定分类结果中文本数量的 比值。召回率的定义为 召嘲一硼= 笔鬻 s ， 准确率和召回率反映了分类质量的两个不同方面，两者必须综合考虑，不可 偏废，因此，存在一种新的评估指标- f 值，f 值的定义为 瞄：! ! 堡堕垩! 堡旦皇 ( 1 4 ) 准确率+ 召回率 另外，可以从两个不同的角度来定义准确率、召回率和f 值微平均和宏 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 平均。微平均将整个语料库作为一个整体，计算准确率、召回率和，值。宏平均 则计算每个类的准确率、召回率和f 值，然后取平均值。 相对于分类的效率，分类的准确程度更受到学者的重视。m u c ( 信息理解 会议) 和t r e c ( 文本检索会议) 都没有将响应时间作为系统评测的标准。分析 其原因，主要因为目前文本分类的主要问题是准确性问题，而不是系统的效率。 而在实际的应用系统中，效率和准确程度具有同样重要的地位。如果能在不削弱 准确程度的前提下，降低系统的响应时间，也是极有意义的工作。 1 3 文本分类系统的研究意义 文本分类系统的应用领域很广，如信息组织、信息过滤、邮件分类和话题跟 踪等1 3 】。 1 3 1 信息组织 对文本进行组织可以提高用户查找的效率，如图书馆的分类体系有利于用户 查找自己需要的信息。目前，网络上的文本数据成指数上升，而这些数据的归类 工作主要通过人工进行组织。如新浪、搜狐、雅虎等都由人工将网页按照内容进 行层次归类。显然，这必将耗费极大的人力物力。若能够采用计算机自动文本分 类技术来辅助文档归类，这必将大大地提高分类的效率。 很显然，文档组织属于典型的多类文本分类问题。 1 3 2 信息过滤 随着信息获取方便性的提高，人们对获取网络上特定信息的需求也在不断增 长。于是，人们迫切需要一种智能的信息过滤技术，该技术能够根据用户的需要， 对源源不断到来的文本进行动态的分类、筛选。从而保留有用信息，屏蔽无关信 息。从文本分类的角度来说，它属于两类文本分类问题，它将所有文本区分为“相 关文本”与“无关文本”。 传统的获取信息的技术中用户是主动方，因此可以称之为“拉”( p u l l ) ，与 之相反的另一种方式则称为“推”( p u s h ) ，由信息发布方主动地将信息推送给感 兴趣的用户。用户的兴趣可以用用户自己提交的p r o f i l e 来表示，也可以用用户 访问过的文本集合来描述。此外，通过适当引导用户参与到过滤过程中或者分析 用户对待过滤结果的网络行为等技术实现动态反馈，根据这些反馈动态调整用户 兴趣的表示和信息筛选的规则，从而实现更加高效的自适应式信息过滤。 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 1 3 3 邮件分类 电子邮件作为最广泛和成功的i n t e r n e t 服务已经成为人们f 1 常生活中不可 缺少的组成部分。但在给人们带来巨大方便的同时，也日益显示出其负面影响， 那就是我们每天收到的邮件中有很大部分是那种“不请自来”的所谓“垃圾” 邮件。它们或者是推销广告，或者是一些有害的不良信息，甚至还有病毒。这些 垃圾邮件不仅对网络安全形成威胁，而且还造成了各方面资金上的巨大浪费。垃 圾邮件正以爆炸性的速度增长，最终将超过网路的承受能力。据预测，目前全世 界的垃圾邮件数量以每5 个月翻一番的速度高速增长，2 0 0 5 年垃圾邮件比例将 上升至9 0 。如果不能尽快遏制病毒和垃圾邮件，全球互联网系统有可能不堪重 负而在两年内崩溃。对垃圾邮件进行“围剿”已经刻不容缓。 目前邮件分类可以看作通常的文本分类问题，它可以分为两种模式。其一是 两类模式，即按照垃圾与非垃圾来分类；另一种是多类模式，比如工作、会议、 垃圾等。 1 3 4 话题跟踪 话题识别与跟踪的基本思想源于1 9 9 6 年，当时美国国防高级研究计划署 ( d a y , i ，a ) 根据自己的需求，提出要开发一种新技术，能在没有人工干预的情况下 自动判断新闻数据流的主题。随后，来自d a r p a 、卡内基梅隆大学、d r a g o n 系 统公司以及麻萨诸塞大学的研究者开始定义话题识别与跟踪( t o p i cd e t e c t i o na n d t r a c k i n g ，t d t ) 研究的内容，并开发用于解决问题的初步技术。从文本挖掘的 角度上来说，话题识别类似于文本聚类；而话题跟踪类似于多类文本分类。 话题识别与跟踪，作为一项旨在帮助人们应对信息过载问题的研究，以新闻 专线( n e w s w i r e ) 、广播、电视等媒体信息流为处理对象，将语言形式的信息流 分割为不同的新闻报道( n e w ss t o r y ) ，监控对新话题的报道，并将涉及某个话 题的报道组织起来以某种方式呈现给用户。它的研究目标是要实现按话题查找、 组织和利用来自多种新闻媒体的多语言信息。这类新技术是现实中急需的，比如： 自动监控各种信息源( 如广播、电视等) ，并从中识别出各种突发事件、新事件 以及关于已知事件的新信息。这可广泛用于信息安全、证券市场分析等领域。另 外，还可以找出用户感兴趣话题的所有报道，研究这一话题的发展历程等等。 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 1 4 文本分类系统的研究现状 文本分类是信息检索领域中的个非常活跃的研究方向。目前研究的热点主 要集中于以下几个方面：特征压缩、分类器组合、小样本问题、层次分类器、样 本不均衡问题等。下面我们就在这几个方向上简单介绍一下。 1 4 1 特征压缩 文本数据具有高维性和稀疏性两个特点，过高的特征数量会降低系统的效率 和性能，往往会导致“维数灾难”等问题，因此对文本数据进行特征压缩就显得 极为重要。目前特征压缩的算法主要分为两类：特征选择( 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 ) 。特征选择根据某种准则从原始特征中选择部分最 有区分能力的特征；特征抽取则将高维的文本空间转换为一种低维的空间，从而 在这个低维的文本空间中对文本进行处理。 根据特征选择是否依赖于分类器，将特征选择分为过滤法( f i l t e r ) 和融合 法( w r a p p e r ) 。过滤法不依赖于分类器，它只根据某种标准对特征进行排序，然 后选择前n 个特征；而融合法需要跟分类器密切结合，并根据分类精度来判断某 个特征子集的优劣。 目前许多特征衡量标准被引入到文本中来，如文档频率、信息增益、互信息、 c h i 统计、交叉熵和术语强度等。在特征抽取方面，主成分分析 4 】、线性区分分 析【5 】、概念索引6 1 等众多方法都先后被提出和引入到文本领域。 1 4 2 分类器组合 分类器组合( c o n b i n a t i o n ) 7 】【8 】【9 1 又叫分类器委员会( c o m m i t t e e ) ，熔合( f u s i o n ) ， 整体( e n s e m b l e ) 或聚合( a g g r e g a t i o n ) 等。它的基本思想就是将多个分类器组合成 一个大的分类系统。 根据是否对训练集进行取样，分类器组合大体上可以分为两类：分类器简单 组合方式与重采样方式。在分类器简单组合方式中，训l 练集对所有成员分类器而 言保持不变，训练时各成员分类器独立进行，分类时组合所有成员分类器的分类 结果。重采样方式对训练集进行多次有放回采样，然后采用某个弱分类器算法在 这些采样出来的多个训练集上训练出多个分类器。 l a r k e y 设计了一个基于r o c c h i o 、贝叶斯与最近邻的组合分类器【1 0 1 。他的实 验结果表明任何两两组合的分类精度要高于单个分类器的分类精度；而三个分类 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 器的组合的分类精度要高于任何两两组合的分类精度。l a r k e y 的实验在一定程 度上表明了组合分类器能够对其成员分类器进行取长补短。 b a g g i n g 与b o o s t i n g 是重采样方式的代表。b a g g i n g 采用均匀采样：而 b o o s t i n g 根据已经产生的分类器的分类效果对训练集进行采样，重点突出错分 样本。s c h a p i r e 开发了b o o s t e x t e r 系统【7 】，该系统采用决策树作为弱分类器， 实现了两个b o o s t i n g 算法，即a d a b o o s t i 与a d a b o o s t m r 。实验结果表明 a d a b o o s t 表现出了不错的分类质量。 1 4 3 小样本问题 传统的文本分类需要标记大量的样本来进行训练，然而在实际工作中，获得 加标签的训练样本常常需要较大的人力物力。因此，分类器所能得到的有标签的 训练样本往往是有限的。相反，常常能够很容易地获得大量无标签的样本。因此， 这就很自然地产生了一个如何利用少量的有标签样本和大量的无标签样本训练 出一个较好的分类器的问题。 n i g a r n i l 2 】i 提出了基于期望最大( e x p e c t a t i o n m a x i m i z a t i o n ) 和朴素贝叶斯 分类器相结合的算法来从标记和未标记文档中学习。e m 是在不完整数据问题中 寻求最大可能性或最大化后验估计的一类迭代方法【“1 。该算法首先使用可用的 标记文档训练出一个分类器，大概标定未标记文档的类别。然后使用所有的文档 训练一个新的分类器，重复直到收敛。他们的研究表明，通过使用大量的未标记 文档来增大少量的标记文档集合，可以提高文本分类器的精确度。 j o a c h i m s 1 5 】提出了直推式支持向量机( t s v m ) 。t s v m 首先按照某个规则估 计无标签样本中的正例数。然后使用s v m 学习算法对有标签样本训练出一个 初始分类器。用初始分类器对无标签样本进行分类，对判别函数输出值最大的 个无标签样本暂时赋为正标签，其余的赋为负标签。对所有样本重新训练，对新 得到的分类器，按一定的规则交换一对标签值不同的测试样本的标签符号。这一 步骤反复执行，直到收敛。实验表明，该方法取得了较好的分类精度。 1 4 4 层次文本分类 大多数文本分类算法仅关注非层次化的“平面”型分类。事实上，层次化分 类较之平面型分类更为实用、有效。这主要体现在两个方面。首先，以层次形式 组织的文档更符合用户的思维模式，也更容易被用户访问与获取；其次，层次化 分类方法在高层即可滤除许多与测试文档( 即被分类文档) 无关的类别，这使得 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 该方法能在保证分类结果准确性的前提下具备更快的分类速度。 根据袁时金【16 】的总结，层次化文档分类可以有三种实现途径。其中，最简 单的一种就是把层次分类问题转化为只包含基类( 即叶节点类别) 的平面型分类 问题。第二种方法是：按照文档类别层次结构树，将层次分类问题逐层分化为一 个个的局部分类问题，在类树的每一内部节点分别建立分类器。这一类的文献最 多。c a i ”l 采用s v m 来进行层次分类，他们对s v m 进行了推广，使它的区分 函数建立在语料集的层次关系之上。r a n g a n a t h a n ” 采用组合聚类与层次方法来 做文本分类，他使用聚类算法来选择训练文档。实验结果表明，结合聚类的层次 分类相对于普通的层次分类有了较大幅度的改进。第三种方案是把层次化分类问 题看成是一个更一般的多类、多标注分类问题来进行求解。这种思想较新，文献 较少。d e k e l 1 9 1 吸收了边缘( m a 画n ) 核方法和贝叶斯分析的一些基本思想，设计了 一个大边缘层次分类器。他把每个节点表示成一个典型( 或向量) ，并把学习问 题转化为带有边缘约束的优化问题。 1 4 5 样本不均衡问题 样本不均衡问题 2 川指的是某些大类占据了绝大部分训练样本，而其余小类 却只包含少数样本。事实上，大部分文本分类问题都是样本不均衡问题。而大部 分经典的机器学习算法都是建立在均衡训练样本之上的。因此，这些算法在不均 衡语料上的表现常常难以令人满意。它们在大类上精度很高，但在小类上精度很 差【2 1 l 。 许多学者在这个问题上进行了大量研究，提出了许多解决办法( ”i 。这些方 法大致可以分为三类：基于取样、基于误差加权与基于识别。基于取样的方法使 用最广泛。大致可以分为三类：上取样口”、下取样、混合取样“1 。虽然使用 取样的办法非常简单直接，但也存在一些不足之处，就是上取样会增加噪音；下 取样会损失有用信息。基于误差加权的方法通过加大小类样本的错分成本，来增 加小类对分类器训练的影响【2 l l 。基于识别的方法通过单从小类来学习分类规则。 j a p k o w i c z 2 0 1 设计了一个只学习正例( 小类) 的神经网络。采用这种策略的支持 向量机也被用来学习小类。 1 5 本文的主要工作和内容安排 本文的主要工作可以概括为三个方面： 中国科学技术大学硕士学位论文 基于信息论的文本分类模型与算法研究 1 提出了文本分类的信息论模型。该模型以信息论作为基本理论，以文本提 供的关于各个类的信息作为分类的依据。文本分类的信息论模型从另一个 的角度来思考文本分类问题，并且统一了传统的朴素贝叶斯法和基于k l 距离的中心向量法两种不同的分类模型。 2 根据互信息最大化原则，提出了一种特征选择算法和两种特征聚类算法。 从实验的角度看，该特征选择算法优于传统的特征选择算法。在保证分类 精度的情况下，特征聚类算法可以大大降低文本特征空间的维数。 3 对文本分类的信息论模型进行推广，提出了文本分类的广义信息论模型。 该模型为文本空间中的各个特征赋予不同的权重，区分重要的特征和不重 要的特征。不同于特征的其它属性，特征的权重无法通过公式直接计算得 到。为了计算特征的权重，本文从不同的角度提出了两种权重学习算法一 一基于错误驱动的特征权重学习算法和基于免疫进化的特征权重学习算 法，并且从实验上验证了这两种算法的有效性。 本文共分为五章，各章的内容安排如下： 第一章为引言，首先简单介绍文本分类的问题描述和评价指标，然后讨论了 文本分类研究的意义和现状，最后给出了本文的主要工作和内容安排。 第二章为文本分类的信息论模型，首先介绍了信息论中的基本概念，如熵、 互信息等，并且给出了两种常用的概率分布距离的度量方法一瞄f 肋d 以一e f 6 胞r 俾劲距离和j e n s e n s h a n n o n 倒距离。然后从信息论的基本原理出发，给出了本 文建立的基于信息论的文本分类模型，并且证明了该模型与传统的中心向量法和 朴素贝叶斯法之间的关系。 第三章为基于信息论模型的特征压缩算法，从文本分类的信息论模型出发， 根据互信息最大化原则，提出了一种新的特征选择算法和两种特征聚类算法，并 从实验上验证了这些方法的有效性。 第四章从广义信息论的角度，提出了一种基于广义信息论的分类模型。并且 从不同的角度提出了两种特征权重的学习算法，它们分别为基于错误驱动的特征 权重学习算法和基于免疫进化的特征权重学习算法。 第五章总结全文，并讨论了下一步的工作。 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 第二章文本分类的信息论模型 文本分类是一种很重要的文本信息处理方法，它将文本自动地标记匕预先定 义好的文本类别。目前已有大量的文本分类模型，如中心向量法、r o c c h i o 、朴 素贝叶斯、w i n n o w 、k 近邻、支持向量机和神经网络等。本章首先介绍信息论 的基本概念，然后提出一种基于信息论的分类模型，最后从理论上证明这种模型 与传统分类模型之间的关系。 2 1 信息论基础 信息论是人们在长期通信工程的实践中，由通信技术与概率论、随机过程和 数理统计相结合而逐步发展起来的- 1 7 科学。s h a n n o n 2 5 1 在1 9 4 8 年发表了著名 的论文“a m a t h e m a t i c a lt h e o r yo f c o m m t m i c m i o n ”，为信息论奠定了理论基础。 s h a n n o n 将各种通信系统概括成如图2 1 所示的框图。 干扰或噪音 图2 1 通信系统框图 在各种通信系统中，其传输的形式是消息。收信者在收到消息以前不知道消 息的具体内容，即对信源发送的消息具有某种不确定性。退一步说，即使收到了 消息，由于干扰和噪音的存在，他也不能断定该消息是否与信源发送的消息一致， 即仍然对信源发送的消息具有某种不确定性。 根据香农的信息理论，信息是事物运动状态或存在方式不确定性的描述。这 种不确定性消除得越多，获得的信息就越多。如果原先的不确定性全部消除了， 就获得了全部的信息；如果消除了部分的不确定性，就获得了部分信息；如果原 先不确定性没有任何消除，就没有获得任何信息。 具体地说，信息论是一套研究通信过程中信源、信道、信宿以及他们之间关 系的基础理论。信源是信息的来源，即产生消息。消息不是信息本身，它是信息 的表达者。在通信系统中，收信者在没收到任何消息以前，对信源发出的消息是 9 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算_ 去研究 不确定的，我们可用随机变量来描述信源输出的消息。如( 2 1 ) 式所示。 轰x ， = p 0 ，p 。x 。2 ：，：p 。x _ r ， c zt ， 信宿接收信源产生的消息，由于信源和信道的不确定性，信宿接收到的消息 也具有某种不确定性。一般情况下，用接收n n 息的概率分布来描述信宿。如 ( 2 2 ) 式所示。 y b y l ， y 2 p ( y ：)别 ( 2 2 ) 信道是传输消息的媒体。由于噪音的存在，消息在信道中传输是不确定的 可以用一个转移概率矩阵来描述信道。如( 2 3 ) 式所示。 p ( y 。i ) p ( y ：l x ，) p ( y ；h ) p ( y ，i x 2 ) p ( y ：i x ：) p ( y ，lx ：) p ( y 。i x ，) p ( y ：lx ，) p ( y ，i x ，) ( 2 3 ) 信道表达了消息传输过程中的不确定性。 2 1 1 信息熵的基本概念 根据香浓的信息理论，收信者所获得的信息量应等于信息传输前后对信源不 确定性减少( 消除) 的量。在无干扰和噪声的情况下，信宿可以完全不失真地收 到信源所发的消息，所以，信宿收到消息后可以完全消除对信源的不确定性。此 时获得的信息为该消息的自信息。根据香浓的信息理论，若某个消息五发生的概 率为p ( x ；1 ，则该消息的自信息为： m f ) = 。s 高 ( 2 4 ) 自信息表示某个消息本身所含有的信息量。我们定义自信息的数学期望为信 源的信息熵，即 r1 ， 片) 胡ll o g 高i 一善p ( x i ) 1 0 9 p ( x i ) 。5 信源的信息熵日是对整个信源进行统计而得出的物理量。它从平均意义上 来表征信源的总体信息测度。对于特定的信源( 概率分布已知) ，其信息熵是一 个确定的数值。从不确定性的角度来说，信息熵是信源平均不确定性的描述，它 是信源的属性，与信道无关，它并不等于接收者平均获得的信息量。只有在无噪 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 声的情况下，信息熵才等于接收者平均获得的信息量，因为接收者能正确无误地 接收到信源所发出的消息。 信息熵是一个永远不小于0 的物理量，它是信源概率分布的函数，信源的概 率分布越集中，信息熵越小，信源的概率分布越分散，信息熵越大。 2 1 2 互信息和多信息 日( 肖) 是在接收到输出】，以前，关于输入变量先验不确定性的度量，称为先 验熵。一般的信道中有噪声存在，即使接收到输出符号y 后，也无法确定信源发 送的符号。当接收到输出符号y = y j 后，输入符号的概率分布表示为p ( x l y i ) ， 此时，关于x 的平均不确定性可以表示为 日( x y 小善p ( z ry s ) l o g 丙裔 我们称其为输入变量x 在接收到输出符号y ，后的后验熵。可见，当接收到 输出符号y ：后，对于输入变量x 的不确定性由先验熵转为后验熵。将后验熵对 随机变量y 求期望，得到输入变量x 的条件熵为 h 伍il ，) = e 陋伍i y ，) 】= 吝p ( y - ) 喜p ( 引y ，) l o g i # 丽 2 善蔷烈乃) 1 0 9 页丽2 善烈五力l o g 瓦者万 q 6 这个条件熵又称为信道疑义度。它表示在接收端接收到输出变量y 的符号 后，对于发送端的变量尚存在的平均不确定性( 疑义) 。这个对z 尚存在的不 确定性是由于噪声引起的。一般条件下，随机变量x 的条件熵不可能大于其先 验熵，即有h ( xy ) h ( x ) 。这说明接收到变量y 的所有符号后，关于输入变 量x 的平均不确定性将减少，即总能消除一些关于输入端x 的不确定性，从而 获得了些信息。所以定义 ，( x ；y ) = h ( x ) 一h ( x l y ) = 日( y ) 一h ( r 1 x ) ( 2 7 ) 为鼻和y 之间的平均互信息。他表示接收到输出符号后获得的关于x 的信 息量的平均值。它也表明，输入与输出两个随机变量之间的统计约束程度。可阻 推导出 删；y ) 2 丢p 力l o g 篙熬 汜8 中国科学技术大学硕士学位论文 基于信息论的文本分类模型与算法研究 平均互信息，( x ；y ) 是互信息i ( x ；y ) 在两个概率空间x 和j ，上的统计平均 值。互信息，( x ；y ) 表示收到消息y 后所获得的关于事件x 的信息量。即 m ；y h 。s 等刮。s 器刮。s 掣 眨， 互信息可取正值，也可取负值。如果互信息i ( x ；y ) 取负值，说明接收端在未 收到消息y 以前对事件x 发生的猜测的难疑程度较小。但由于噪声的存在，接收 到消息y 后，反而使接收端对事件x 发生的猜测的难疑程度增加了。也就是说， 接收端在接收到消息y 后对x 发生的不确定性反而增加了，所以获取的信息量为 负值。但是，平均互信息i ( x ；y ) 永远不会取负值，最差情况下是平均互信息 ，( x ；y ) = 0 ，也就是在信道输出端接收到输出符号y 后不获得任何关于输入符号 x 的信息。 互信息是两个随机变量之间相互提供的信息量，表达两个以上随机变量之间 相互提供的信息量就需要用多信息( m u l t i i n f o r m a t i o n ) 【2 6 1 的概念。 设”个离散随机变量彳，五，x 。的概率分布为p ( x ，x ：，x 。) ，则这个变 量之间的多信息为 i ( x 。，：，以) = p ( x 。，x ：，j 。) l o g 曼竖：兰：玉! p ( x 1 ) p ( x 2 ) p ( x 。) ( 2 1 0 ) 当h = 2 时，2 个变量之间的多信息就是它们之间的互信息。熵与互信息之间 的关系可以扩展到多信息的情形，如公式( 2 1 1 ) 所示。 i ( x 。，x ：，x 。) = 日( 五) 一日( 五，x ：，瓦) ( 2 1 1 ) i = l 多信息满足下式 i ( x 。，x 2 ，。，x ) = t ( x 1 ，x 2 ，z 。) + t ( x 1 ，x 2 ，并。；x 。) ( 2 1 2 ) 公式( 2 1 2 ) 等号右边的第二项表示一个随机向量肖。x ：以与一个随 机变量x 。之间的互信息。 2 1 3 概率分布之间的距离度量 在研究两个不同概率分布之间的关系时，往往需要计算这两个概率分布之间 的距离。本节所说概率分布之间的距离指的是两个描述相同空间上的不同概率分 布之间的距离。距离的计算方法很多，同样也可以采用普通欧式空间中的距离定 中国科学技术大学硕士学位论文 基于信息论的文本分类模型与算法研究 义，但是，对于概率分布可以定义一套独特的计算方法。这里介绍两种常用的计 算方法胁l 肋n c 女一三p i 6 膪r 俾到距离和j e n s e n s h a n n o n 例距离。 定义2 1 两个不翰豹概率分布p 。x 、s p ! t 心之阃的t a c k - l e i b t e r ( k l ) 距 离定义为 。n b 川p z 】2 莩删l o g 器 ，j 箕手赌锄删。l 。g 詈j 。，且l 。g 鲁呻o o k l 距离又称为相对熵。从k l 距离的定义不难看出，k l 距离不满足对称性 和三角不等式，而且必须平滑后才能使用，但是k l 距离满足 d 。b ，( 工) | l p 2 ) 】0 等号成立，当且仅当h ，p 。( z ) = p ：( ) a 观察互信息计算公式( 2 8 ) 可知，互信息可以表达成联合概率分布和边缘 概率分布的乘积之间的k l 距离，即 ，( x ；y ) = d k l b ( 工，y ) l ip ( z ) p ( y ) j ( 2 1 4 ) 同理，多信息可以表示成联合概率分布与各变量边缘概率分布的乘积之间的 k l 距离。 i ( x 1 ，x 2 ，x 。) = d n b ( 一，x 2 ，) | | p ( x t ) p ( x 2 ) p ( x 。) 】 ( 2 1 5 ) 定义2 2 两个不同的概率分布p 。s p 2 t 心之a - j f f j j e n s e n s h a n n o n ( j s ) 距离 定义为 j & ( p l ，p 2 ) = 万l 工( p l ，刃+ 万2 魁( p 2 ，芦) = h ( f i ) 一7 l ：1 h ( p 1 ) 一万2 h ( p 2 ) 臼1 6 ) 菇尹万= 协l ，石2 ，0 万l ，7 2 l ，7 9 l + 7 1 2 = l ，f = 玎i p l + 石2 p 2 从j s 距离的定义不难看出，( 7 g ，p ，) 与( 7 2 ，p ：) 之间的距离是对称的，而且 满足 坶。( p l ，p 2 ) 0 等号成立，当且仅当v x ，p l ( x ) = p ：( z ) 。 不同于k l 距离只能定义两个概率分布之间的距离，j s 距离可以定义多个概 率分布之间的距离。多个概率分布之间的j s 距离定义为 中国科学技术大学硕士学位论文基于信息论的文本分类模型与算法研究 i s 如，p ：，p 。1 = h ( 万) 一石i h ( p i ) = 1 n月 其中，万= 函，丌：，) ，0 z ， 卢 ( 3 1 0 ) 其中口是一个相似闽值，用来判断两个文本是否相关。 因为要计算所有文本对之间的相似度，所以术语强度算法的时间复杂度相对 较高。但是，术语强度和文档频率两