（计算机应用技术专业论文）基于范例推理的文本自动分类研究.pdf

摘要 迅猛发展的现代科技带来了大量的信息资料。如何对这些信息资料进行有效 地管理成为了现代科学的一个重要问题。对信息进行管理一个常用的方法就是对 它们进行系统的分类。由于信息通常以文本的形式存在，文本自动分类在图书馆 图书文献管理、语音u 别、互联网信息处理、数据挖掘、信息检索、信息过滤等 诸多应用中有着非常重要的作用。 本文将基于范例推理c b r ( c a s eb a s e dr e a s o n i n g ) 技术应用到文本自动分 类中，并对范例表示进行了研究，实现了基于范例推理的文本自动分类系统和 e m a i l 自动分类系统。针对目前常规的向量空间模型v s m ( v e c t o rs p a c em o d e l ) 文档表示方法不能反映概念的问题，本文首先提出了用v s m 和词共现共同表示 文档的方法，用词共现来表达文档的概念信息。将训练集中的每一类文档聚类， 聚类后的结果作为范例存入范例库中，然后用最近邻方法进行分类。由于e m a i l 具有文本长度短、内容覆盖面大的特点，用关键词匹配的方法很难取得比较好的 效果，因此，本文采用潜在语义分析l s a ( l a t e n ts e m a n t i ca n a l y s i s ) 的方法， 利用矩阵的奇异值分解理论s v d ( s i n g u l a r v a l u ed e c o m p o s i t i o n ) 来获得e m a i l 的概念空间，在此概念空问上表示e m a i l 作为范例，再用最近邻方法分类。实验 结果验证了本文提出的方法是r i _ 行的和有效的。 本文的特色之处在于： 1 将c b r 技术应用到文本自动分类中，在提高速度的同时提高了分类性能： 2 提出了综合v s m 和词共现的文档表示方法，该方法保留了v s m 简单易 实现的优点，又增加了对文档语义的考虑，使分类性能有所提高： 3 用潜在语义分析的方法来表达文档的概念，将词和文档投影到低维的语 义空间，实现了基于概念的文本自动分类。 关键词：基于范例推理，文本自动分类，向量空阳j 模型，词共现，潜在语义分析。 a b s t r a c t t h er a p i dd e v e l o p m e n to fm o d e ms c i e n c eb r i n g so u tam a s so fi n f o r m a t i o n h o w t om a n a g et h e me f f e c t i v e l yh a sb e c o m em o r ea n dm o r ei m p o r t a n t o n eo ft h em a j o r m e t h o d si st oc l a s s i f yt h e m m o s ti n f o r m a t i o na r et e x t s ，s ot h ea u t o m a t i ct e x t c a t e g o r i z a t i o ni sp l a y i n gav e r yi m p o r t a n tr o l ei nv o i c er e o r g a n i z a t i o n ，i n f o r m a t i o n p r o c e s s i n go fi n t e m e t ，d a t am i n i n g ，i n f o r m a t i o nr e t r i e v a l ，i n f o r m a t i o nf i l t e ra n ds o m e o t h e rr e l a t e df i e l d s i nt h i s p a p e r , c a s eb a s e dr e a s o n i n g ( c b r ) i sa p p l i e di n a u t o m a t i ct e x t c a t e g o r i z a t i o na n dt h ep r e s e n t a t i o no ft h ec a s ei ss t u d i e d i na d d i t i o n ，w ei m p l e m e n t a na u t o m a t i ct e x tc a t e g o r i z a t i o ns y s t e ma n da na u t o m a t i ce m a i lc a t e g o r i z a t i o nb a s e d o nc b r w h i l et h et r a d i t i o n a lv e c t o rs p a c em o d e l ( v s m ) d o e sn o tc o n s i d e rt h e c o n c e p to ft h et e x t ，t h i sp a p e rf i r s tp r o p o s e sam o d e lo ft e x tp r e s e n t a t i o nu s i n g t r a d i t i o n a lv s ma n dt e r mc o o c c u r r e n c e ，w h i c h p r e s e n t st h ec o n c e p tb yt e r m c o o c c u r r e n c e t h em e t h o dc l u s t e ra l lo ft h ed o c u m e n t si nt h et r a i n i n gs e ta n ds t o r e s t h er e s u l t si n t ot h ec a s eb a s e ，t h e nc l a s s i f i e sd o c u m e n t sb yk n e a r e s tn e i g h b o r ( k n n ) f o re m a i l sa l w a y sh a saf e ww o r d sa n dt h e i rc o n t e n t sc o v e rm a n ya s p e c t s ，i t i sd i f f i c u l tt og a i nag o o dp e r f o r m a n c eb ys t a t i s t i cm e t h o d s ot h i sp a p e rb r i n g so u ta l a t e n ts e m a n t i ca n a l y s i s ( l s a ) m e t h o dt o g e tt h ee m a i l s c o n c e p t u a ls p a c eb y s i n g u l a r v a l u ed e c o m p o s i t i o n ( s v d ) t h e o r y e x p e r i m e n t ss h o wt h a t t h i sm e t h o di s f e a s i b l ea n de f f e c t i v e t h i sa r t i c l em a i n l yw o r k so nt h ef o l l o w i n gt o p i c s ： 1 u s e sc b ri na u t o m a t i ct e x tc a t e g o r i z a t i o n t h i sm e t h o de n h a n c e sb o t ht h e s p e e da n dt h ep e r f o r m a n c eo fc l a s s i f i c a t i o n 2 p u t sf o r w a r dad o c u m e n tp r e s e n t a t i o nm e t h o db a s e do nv s ma n dt e r m c o - o c c u r r e n c e t h i sm e t h o di se a s yt oi m p l e m e n ta n dc a ng e tah i g h p e r f o r m a n c eb yc o n s i d e r i n gt h ec o n c e p to f t h ed o c u m e n t s 3 p r e s e n t st h ec o n c e p t so ft h ed o c u m e n t sb yl s aa n di m p l e m e n tt h et e x t c a t e g o r i z a t i o nb a s e do nc o n c e p tb ym a p p i n gt e r m sa n dd o c u m e n t st o 2 c o n c e p t u a ls p a c ew i t hl o wd i m e n s i o n k e y w o r d s ：c a s eb a s e dr e a s o n i n g ，a u t o m a t i ct e x tc a t e g o r i z a t i o n ，v e c t o rs p a c e m o d e l ，t e r mc o o c c u r r e n c e ，l a t e n ts e m a n t i ca n a l y s i s 3 第一章绪论 迅猛发展的现代科技带来了大量的信息资料。如何对这些信息资料进行有效 地管理成为了现代科学的一个重要问题。对资料进行管理一个很常见的方法就是 对它们进行系统地分类。据统计。在信息领域中，8 0 以上的信息是以语言文字 为载体的，因此，文本分类成为处理和组织大量文档数据的关键技术。 1 1 文本自动分类的意义及现状 二十一世纪是一个信息化的社会。以i n t e r n e t 为主体的信息高速公路的建立 是人类全面进入信息时代的重要标志。i n t e m e t 是世界上规模最大、用户最多、 影响最大的计算机互连网络，许多国家和地区部萨式加入了i n t e r n e t 。按照中国 互联网络信息中心( c n n i c ) 于2 0 0 5 年1 月最新发布的“第十五次中国互联网 络发展状况统计报告”川，至2 0 0 4 年底，我国i 二网用户数已经达到9 4 0 0 万，上 网主机数已达4 1 6 0 力台。i n t e r n e t 为人们提供了信息共享和交流的现代化通道， 它的应用也已从原来的军事和商业渗透到了社会各个领域，对整个人类社会进步 起到了极为重要的作用。然而，随着i n t e r n e t 应用的不断普及和深入，却又使人 们从信息缺乏的时代过渡到了信息极大丰富的时代。当今社会的信息突出表现为 信息量急剧增加，各种电予文本形式的情报源所提供的信息量正以惊人的速度递 增；信息结构更加复杂，w w w 阀上包含的信息以文本、图像、视频等多媒体格 式存在：信息的全球化，要求处理与传递信息的速度加快。面对i n t e r o e t 上f | 益 膨胀的信息，如何快速、计e 确地从浩瀚的信息资源中寻找到所要的狭小领域内的 相关内容就成了一项i 分有意义的课题。f 是在这样的背景之下，文本分类f 逐 渐成为一个f 1 益重要的研究领域。随着文本信息的快速增长，特别是i n t e r n e t 上 在线信息的增加，文本分类显得越来越重要。传统的方法是采用手工对庞大的原 始文本组织分类，但手工分类存在着工序复杂、效率低下等缺点，而且分类的结 果受人的主观因素影响较大。因此，文本自动分类( a u t o m a t i ct e x tc a t e g o r i z a t i o n ) 技术应运丽生。文本自动分类在图书馆图书文献管理、语音识别、i n t e r n e t 数据挖掘、信息检索、信息过滤等诸多应用中有着非常重要的作用1 2 j 。 文本自动分类的研究始于二十世纪5 0 年代，h p l u h n 在这一领域进行了丌 创性的研究【3 1 ，他提出了词频统计思想，主要用于自动分类。1 9 6 0 年，m a r o n 发 表了有关自动分类的第一篇论文【4 j 。1 9 6 2 年，博科( h b o r k o ) 等人提出利用因 子分析法进行文献的自动分类1 5 i 。其后许多著名的情报学家如、k s j o n e s 、 g s a l t o n 以及r m n e e d h a m 、m e ，l e s k 等众多学者在这一领域进行了卓有成效 的研究工作“。概括起来，他们主要从文本的词频统计分析、句法分析和语义 分析等i 个层次上进ij ：研究。其中，以基于词频统计分析的自动分类实验较为成 功。国内最早是山候汉清先生于1 9 8 1 年首先i t 自动分类进行探讨，目前，我 国已经研制出- - 一批自动分类系统1 3 - 2 0 1 。文本自动分类中应用较早的机器学习方法 是纯粹贝叶斯( n a i v eb a y e s ，n b ) 2 t - 2 3 。大量其它机器学习的技术也被用于文 本分类，如支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 2 4 2 5 1 ，最大摘算法 ( m a x i m u m e n t r o p y ) 【2 6 】，神经网络( n e u r a l n e t s ) 1 2 7 】和规则学习算法【2 8 】，k 近 邻算法( kn e a r e s tn e i g h b o r ，k n n ) 1 2 9 j 等。至今没有哪个单独的技术体现出超 出其他技术的明显优势，但最近的数据表明k 近邻法和支持向量机在充足的训 练样本的情况下性能较好i 如j 。目前研究者主要集中在如何提高文本分类的性能 上，即如何改进分类的召回率和准确率。但是从文本分类的应用例子中可以看出， 实际应用中数据量非常大，而且一般会有实时的需求。受自然语言处理技术的局 限( 也 j ：于实用性的考虑) ，目前相对成熟的方法均不涉及任何语义处理，只以 单个的词或者短语作为文档的特征，并且忽略了他们在文档中出现的顺序( 即结 构信息) 。 1 2 基于范例推理c b r 概述 基于范例的推理( c a s e b a s e dr e a s o n i n g ，c b r ) 是近十几年来人工智能中 发展起来的区别于基于规则推理的一种推理模式，是对人类认知过程的一种模 拟，它是指借用旧的事例或经验来解决问题、评价解决方案、解释异常情况或理 解新情况。c b r 兴起的主要原因是传统的基于规则的系统存在诸多的缺点，如 在知议获取问题上存在困难，导致推理效率低下，不能做范例的例外处理，整体 性能较为脆弱等等而c b r 恰好能解决以上问题。 c b r 先从范例库中检索出与当前问题类似的以往问题的解决方案，再以此 为出发点，综合运用领域知t l ，推理技术帮助设计师不断交互修改浚范例直至产 生能够解决当前问题的新方案，最后将评价合格的新方案作为范例存入范例库 中。 文本自动分类是根据训练文档集来判断新文档的类别，而c b r 借用旧的事 例或经验来解决新闽题，我们可以将二者结合起来，在c b r 框架下进行文本分 类。 1 3 本文工作内容 本文将基于范例推理( c a s eb a s e dr e a s o n i n g c b r ) 技术应用到文本自动 分类中。并对范例表示进行了研究，最后实现了基于c b r 的文本自动分类系统 和e m a i l 自动分类系统。 文中采用k 近邻的分类方法，出于k 近邻方法分类时需要将待分类文档与 所有的训练样本进行比较来选择类别，在训练样本数量非常大时分类时间很长， 不能很好地满足用户的实时需求。于是，我们将训练样本抽象为数量少得多的范 例，以减少分类时间，提高分类速度。 针对目前常规的v s m 文档表示方法不能反映概念，分类性能4 i 高的问题， 本文首先提出了用v s m 和词共现共同表示文档的方法，用词共现来表达文档的 概念信息。将训练集中的每一类文档聚类，聚类后的结果作为范例存入范例库r p ， 然后用k 近邻方法根据范例库进行分类。用上述方法实现了一个文本自动分类 系统，并做了一些实验，实验结果表明，该方法在提高了分类召回率和准确率的 同时，使得系统的分类速度有了很大的增长。 与一般的文本不同，e m a i l 具有文本长度短、内容覆盖面大的特点，用关键 词匹配的方法分类难以取得比较好的效果。本文运用潜在语义分析( l a t e n t s e m a n t i ca n a l y s i s ，l s a ) 的方法，利用矩阵的奇异值分解理论柬获得e m a i l 的 概念空间，在此概念空j 日i 上表示e m a i l 作为范例，再用最近邻方法分类。基于此 方法实现的e m a i l 自动分类系统，有很高的召回率和准确率。 本文的主要工作有： 1 将c b r 技术应用到文本自动分类中，在提高速度的同时提高了分类性 能； 2 提出了综合v s m 和词共现的文档表示方法浚方法保留了v s m 简单 易实现的优点，义增加了对文档语义的考虑。使分类性能有所提高； 3 用潜在语义分析的方法来表达文档的概念将词和文档投影到低维的语 义空间，实现了基于概念的文本自动分类。 1 4 本文组织结构 本文共有六章。 第一章：简述文本自动分类意义及现状和基于范例推理技术： 第二章：简要介绍文本臼动分类过程和关键技术； 第三章：概述基于范例推理技术的研究状况； 第四章：详细介绍基于c b r 的文本自动分类方法，重点描述了综合v s m 和 词共现的文档表示方法、范例的生成： 第血章：详细介绍基于l s a 的范例表示方法，并在此基础上实现了一个基 于c b r 的e m a i t 自动分类系统： 第六章：总结与展望。 第二章文本自动分类技术 本章首先简要说明什么是文本自动分类，然后介绍一些常用的文本自动分类 技术，分别从以下几个方面来介绍：特征提取、特征表示和分类模型。为了衡量 分类方法的性能在本章的最后我们还介绍了文本自动分类的性能评价指标。 2 1 文本自动分类概述 文本分类的任务是在给定的分类体系下，根据文档的内容或属性，将大量的 文档归到一个或多个类别中。文本分类足个有指导的学习过程。它根据一个已 经被标注的训练文档集合，找到文档属性和文档类别之间的关系模式，然后利用 这种学习得到的关系模式对新的文档进行类别判断。用数学公式表示如下： f ：a b ，其中a 为待分类的文档集合，b 为分类体系中的类别集合。 2 2 特征提取 根扔：j o h np i e r r e 的理论川，用来表示文本的特征理论上应其有如下特点： 数量上尽量少： 出现频率适中： 。 冗余少： 噪音少： 与其所属类别语义相关： 含义尽量明确： 就文档来况，最方便采川的特征就是词或者短语1 3 2 l 。作为组成文档的最小 单位，选择他们作为特征具有天然的优势。受自然语言处理技术的局限( 也出于 实用性的考虑) ，目d “相对成熟的方法均不涉及任何语义处理，只以单个的词或 者短语作为文档的特征。并儿忽略了他们在文档中出现的顺序( 即结构信息) 。 ( 某种程度上这也是出于实月】性的考虑) 。在多数基于统计的分类模型中。这种 文档的表示方法均取得了良好的效果。 现有的文档多数以网页的形式存在而网页中往往包括了为数众多的多媒体 信息。包括图像、音乐、动画等等。从蚝远的发展来看，这些多媒体的信息也应 浚作为文档的特征被选取出来，但现在多媒体处理的技术还不足够支持这种处 理。 但是，如果仅以从文档中得到的训或者短语作为特征。很难符合前面提到的 特征应具有的特点。i f 相反： 他们数量众多；从个拥有数千个文档的数据集中抽取得到的特征将 数以力计。 出现频率h i 等：常川词汇 现概率高冷僻词汇则很少。 噪音多：文档中包含了很多无实际含义的词汇， ；t & l l t h e ，a 等。还有 很多拼写错误的词汇。 与其所属类别不一定相关；往体育类的文档中可能会出现很多其他无 关词汇i ：l t = 【n 经济词汇。 特征提取下是解决这个闯题的方案。从文档中得到的初始全特征集可以简单 的被分为有用特征集和无用特征集两部分。特征提取的目的就是尽量的保留有用 特征，剔除无用特征。它通常会采用某种标准来对特征的重要性进行评价。之后 只要保留重要程度较高的特征即可。特征提取的好处有二： a 提高分类效率：因为无用特征被剔除使得特征集得到压缩。 b 提高分类精度：因为减少了无月j 特征对于分类结果的干扰。 下面介绍己有的常见特征提取算法f 3 3 f 3 4 j 。他们相互间的不同之处主要在于 不同的特征重要性评价方法。 2 2 1 i g 特征提取 i g 【5j ( i n f o r m a t i o ng a i n ) ，即信息赢取。i g 值代表了特征在训练集上的分布 情况，它通过统计特征在各个类别中的出现次数来计算，公式如下： 嘶) = 只( c ) i o 妒( c ) + p ( ，) e 心i o i o g p a c , i t ) + p a i 迈( c i i ) l o g g ( c , i i ) ( 21 ) i - it = l，d 其中t 代表特征，c i 代表第i 个类别m 为类别数，p 代表概率。i g 值越高， 表示该特征在训练集中的类别上分布越集中。i g 方法提取i g 值较高的特征，其 基本思想为分布越集中的特征越重要。 2 2 2m i 特征提取 m i t ”i ( m u t u a li n f o r m a t i o n ) ，互信息值，它通过计算特征t 和类别c 问的相 关性来完成提取。计算公式为： m = l o g 丢若等志 仁z ， 为方便计算，简化为： ，( f l o g 而舌姑面 江a ， 其中n 为训练集中包含的文档总数，a 为t 与c 同时出现的次数，b 为r 出 现而c 不出现的次数c 为c 出现而t 不出现的次数。通过该公式就可以取得特 征与各类别问的互信息值。为了能取得特征在数据集上的整体评价，有以下两种 计算方法： ，。q ( ，) = p ) ，( f c ，) ( 2 4 ) ，= i ，。、( ，) = m a x i i ( t c ，) ( 2 5 ) 公式2 4 代表了特征和各类别的 均互信息值，公式2 5 则取特征与各类别 互信息值中的最大值。m i 方法提取互信息值较高的特征，其基本思想为与类别 相关性越高的特征越重要。 2 2 3c h i 特征提取 c h i l 3 5 1 具有和m i 方法基本相似的思想，同样通过计算特征t 和类别c 问的 依赖程度束完成提取。但二者的计算钏节不同，c h i 作了更多地考虑，有剃- 看法 认为c h i 是一种“j f 规化”了的m i 。c h i 的计算公式如下： c h i ( t , c ) ： 型! ! 生望二塑! ： ( 26 ) ( 彳+ c ) ( 口+ d ) ( 一+ 占) ( c + d ) 其中n 为训练集中包含的文档总数，a 为t 与c 同时出现的次数，b 为t 出 现而c 未出现的次数，c 为c 出现而t 未出现的次数，d 为二者都未出现的次数。 与m i 相同，c h i 也有平均值和最大值两种方法来取得特征的整体评价： c h i o w ( ，) = p ，( c , ) c h i ( t ，c ) ( 27 ) j _ i m c h i m 。( f ) = m，c ) ( 28 )_axcm(, c h i 方法的基本思想也是与类别关系越密切的特征重要程度越高。 2 2 4d f 特征提取 d f l 3 5 1 ( d o c u m e n tf r e q u e n c y ) ，即文档频率，指训练集中包含该特征的文档 总数。所谓文档包含特征是指这个特征在浚文档中出现，忽略其在文档中的出现 次数。d f 方法提取d f 值较高的特征，它的 f 的是去掉在训练集上出现次数过 少的特征，保留出现达到一定次数、具有一定影响力的特征。在各个特征提取方 法中，d f 方法的计算是最简单的。 2 3 特征表示 在完成特征提取以后我们就可以用这蝗特征来表示一个文档。特征表示就 是指用一定特征项末代表文档，在文水分类时只需对这些特征项进行处理，从而 实现对非结构化的文档的处理，这是一个非结构化向结构化转化的处理步骤。对 应每种特征表示的方法，要有一套检索的方法来检索相关的文档。现有的信息检 索的数学模型有多种，常甩的有布尔模型、向量空问模型、概率检索模型、模糊 集合模型和扩展布尔模型p “。其中，币j 尔模型采用精确匹配技术，不能做部分 相关程度的判断，对匹配结果不能产，j i 排序输出。概率检索模型、早期的模糊集 合模型和扩展布尔检索模型也存在这个问题。向量空问模型通常采用计算文档 向量和查询向量之| 日j 的央角的方式来衡量文档的相关性，是最常用的一种模型。 下面详细介绍其中比较常用的三种： 2 3 。1 布尔模型 布尔模型f 36 】是以集合论和布尔代数为理论基础的一个非常简单的检索模 型，它基于特征项的严格匹配。它用关键词组合来表示文本信息，关键词的权值 为布尔变量，如果某关键词在文本中出现，其取值为1 ，否则为0 。用户查询 ( q u e r y ) 表示为由逻辑运算符( 与、或、非) 连接起来的布尔表达式，用检索 状态值( r s v ，r e t r i e v a ls t a t u s v a l u e ) 来度量文档和用户查询之问的相似度，文 档与查询的匹配规则遵循布尔运算的法则。如果查询式的值为1 ，则r s v 值为l ， 否则为0 。所有r s v 为l 的文档与查嘲式相关。所有r s v 为0 的文章则与查询 式不相关。所以柑尔模型是基于二值评价体系的它更像是在做数据检索而不是 信息检索。 实现柿尔检索，首先要对文档集e | l 的每个文档进行标识，标引词可以采用关 键字、自由词、作者、篇名等能反映文档特征的词，其次要对文档进行合理的组 织，建立文档的索引通常把文档组l ： 【成倒排文档结构，就是把与某标引词有关 的所有文档的号数通过索引集中在一起，“1 迎过浚标引泪查找该文档时，可以立 即找到文档所在位置，从而检索到文档。 柿尔模型的主要优点是：实现简单、速度快，易于表达一定程度的结构化信 息，如同义关系( 电脑o r 微机o r 计算机) 或词组( 文档a n d 过滤a n d 系 统) 。其缺点是：无法精确表达文本信息的内容，不能反映特征项对_ f 文档的重 要性，缺乏定量的分析，过于严格，缺乏灵活性，更谈不上模糊匹配，这往往忽 略了许多满足用户需求的文档。为了克服这些缺点，人们对布尔检索理论进行了 改造，一种方法是对标引词引进权值，权值大小反映了标引词在文档中的重要程 度，由此形成了所谓的加权靠尔检索，或成为扩展布尔检索，如b o o k s t e i n 检索 模型，s a l t o n 模型等。 2 3 2 向量空间模型 向量空i 瑚模型( v s m ，v e c t o rs p a c em o d e l ) 1 3 6 1 是一种文档表示的统计模型， 其基本思想是以向量来表示文档：( w l ，w 2 ，w 。) ，其中m 为特征项的个 数，w 为第i 个特征项的权重。通常情况下，特征项可以选择字、词和词组等。 实验表明，选取词作为特征项要优f 7 和嗣组1 3 7 】。 向量宅唰模型具有如下优点； 1 文档内容被形式化到多维空问的一个点，通过向量的形式给出，将文档 以向量的形式定义到了实数域中提高了自然语言文档的可计算性和可 操作性： 2 对词引进了权值，通过调节词所对应权值的大小来反映词与所在文档的 相关程度，部分克服了传统的如尔模型的缺陷： 3 匹配通过计算文档之问的相似度使属性相似的文档尽量聚在一起。以 提高匹配效率； 4 满足用户需求多样化以及匹配手段多样化的需要。用户可以根据需求特 点选择一组可供使用的匹配手段。 向量空蒯检索存在的缺点： 1 计算量大，影响系统执行速度： 2 标引词的权值较难确定； 2 3 3 概率模型 布尔模型和向量空间模型都假没关键字之问足相互独立( 即相互正交) 的， 这与实际情况不符。r o b e r t s o n 和s p a r c k j o n e s 提出的概率模型则考虑了关键词 之问、关键词和文档之间内在联系，以贝叶斯公式为理论缝础，利用它们的概率 相依性进行信息检索。概率模型基于提吼关键词在相关和不相关文档中的分靠。 这是采用关键词的权重来表示的，这样每个查询的文档就按照符合提问的关键词 权重之和进行排序。 二值独立检索( b i n a r yi n d e p e n d e n c er e t r i e v a l ) 模型是一种实现简单并且效 果较好的概率模型。假设文档d 和用j 。查咖q 部l j ：用二值阔条向量( x i , x 2 ，x n ) 表示，如果词条t i d ，则x i = l ，台则x ，= 0 。同时假定i j ；i i 个互斥事件w 1 ：文档与 用户查询相关：w 2 ：文档与用户查询不相关，通过计算每一个文档的p ( w i ，x ) 或者 是p ( w 2 x ) ，就可以判断文档与用户查洵的相关性。由于无法直接得到p ( w ，x ) ， 必须采用一些己知量来估计它。对于离散分布，利用b a y e s 公式并经过简化后可 得到文档与用户查询阳j 的相关函数： 鼢c 叩，= l o g 等导舞 仁。， 其中p i = r i r ，q 。= ( 一r 。) ( f - r ) ，f 表示训练文档集中的文档总数，r 表示训练文档 集中与用户查询相关的文档数，表示在训练文挡集中包含词条t 的文档数，r i 表示r 个相关文档中包含词条t 。的文档数。 上面的模型属于概率相关模型，这种模型对所处理的文档集依赖过强，而且 处理问题过于简单。鉴于概率帽关模型存在这样的弱点，人们又提出了改进模型： v r i j s b e r g e n 把信息检索看成是一个非确定性的推理过程，把查询和文档的 内容表示为逻辑形式。并利用推理规则进行演绛。该模型把文档与用户查询之阳j 的相关性判断看作是一个从文档命题到查询命题、描述命题的不确定的推断过 程。 还有一种概率模型使用推理网络。刚络中的个结点代表一个文档、一个查 询或一个概念，网络中结点问的弧表示结点问的概率相关性。其基本思想是：计 算p ( d - q ) 时，把文档结点置为t r u e ，计算与该文档结点相依的结点的概率， 直到得到p ( q = t r u e ) 的值为止。 概率模型的优点足： 1 采用严格的数学理论为依据，为人们提供一种数学理论基础来进行匹 配： 2 采用相关反馈原理，可以7 r 发出理论更为峰实的方法。 概率模型的主要缺_ i 是： 1 增加存储年n i t - 算资源的丌销： 2 参数估计难度较大。 2 4 分类模型 每利z 分类模型都会采用自己的方法永表示一个文档。并将这种表示方法纳入 到自己的体系中去。所有的分类模型大体卜都i _ 分未训练和分类两个步骤。一般 来说。d i i 练例越多分类的准确度越有保证，但也并不是越多越好【3 9 】。 2 4 1r o c c h i o 算法 r o c c h i o 算法1 3 3 】i 为i 采用向量空问模型来表示文档，向量的分量是特征的某种 权重表示，权重用t f i d f l ”1 方法计算，步骤如下： 1 文档d 上的特征w 的权值= t f ( w ，d ) * l d f ( w ) 2 t f ( w ，d ) 为特征w 在文档d 中出珧的次数 3 i 。f ( w ) = i 。甙古) ，其中吲为训练集中的文档总数，d f ( w ) y , j i j 练集中 包含w 的文档数。i d f ( w ) 即逆文档频它讵比于w 在训练集中的稀有 程度。 通过t f i d f 方法首先将训练集中的文档表示为向量然后生成类别特征向 量。类别特征向量取值为陔类中所有文档向最的平均值。r o c c h i o 算法训练的过 程就是建立类别特征向量的过程。分类时先将待分类文档表示成向量，然后计算 i j 向量与各类别特征向量的相似度最后将陔文档分到与之最相似的类别中去。 向量的相似度度量方法主要有如下两种：( 以x ，y 代表向量，x i ，y 代表向量分 量) 1 欧几罩德距离：d i s ( x ，y ) d i s 值越小表示距离越近，向量 2 向量央角的余弦：c o s ( x _ j 孙叫j 2 的十h 似度越高； 毒， y ) 2 t 墨霄一 j 善办j 善一 c o s 值越大表示角度越小，向量的利似度越高。 r i c c h i o 方法是一种简单易行的分类方法，分类速度较快。 2 4 2 朴素贝叶斯模型 贝叶斯分类【4 0 1 1 4 2 是一种统计学分类方法，它基于贝叶斯定理，可以用来预 测类成员关系的可能性，给出文档属于某特定类别的概率。分类时根掘预测结果 将该样本分到概率最高的类别中即可。似定有m 个类c l ，c 2 ，c 。，给定待分 类文档x ，贝叶斯分类将给出条件x 卜，具有最高后验概率的类别，即最大化 p ( c d x ) 。根据贝叶斯定理可得： 删价警 ( 21 2 ) 显嘶易见，p ( x ) 对于所有类是个常数，则只需最大化p ( x k ) ，) ( c ，) p , t j 可。 尸( 。) 可以根据训练集中的类别分布来计鳟，即尸( c ) = 兰等哥( 2 ，具叫i l c ，i 为 类别c 包含的文档数，i d l 为g l l 练集中的文档总数。 在个具有很多属性的事例中，计算p ( x i c ，) 的丌销会非常大，为了降低这 种j r 销，引入了称为类条件独立的朴素假定：假定文档的一个属性对于分类的影 响独立于其它属性，即文档的属性之州是不相关的。这就是孝卜素贝叶撕( n a i v e b a y e s ，n b ) 的由来。这样就可以简单地以各个属性在类别c 上出现的概率来推 算| p ( i c ，) 。通常使用拉普拉斯估计【4 3 i ( l a p l a c e a np r i o r ) 来推算。又囚实现细 节的不同有两种朴素贝叶斯模型【钉i ，多元模型( m u l t i v a r i a t eb e r n o u l l im o d e l ) 只考虑了特征在文档中是否出现。多项式模型( m u l t i n o m i a lm o d e l ) 考虑了特征 在文档中的出现次数： i 1 多元模型中p ( x i c ) = 丌( 既j p ( ”ji c ，) + ( 1 一口。) ( i 一尸( hi e ) ) ) f ，1 4 ) ，其中 ，= 1 w i 代表第t 个特征( 即向最的痢t 分量) - l v 汀表特征总数，b u 表示 w t 足否在文档x 中出现( 出现汇为1 ，否则记为o ) ， 讹| c 卜坚器筹蒜半僻： 2 绷式模型栅邢j ) = # 警( 2 1 6 ) 堪艰n x l 代表了特征t 在 d i i + v p ( c 。l a ， 文档x 中的出现次数。而j p ( qi c ) = 一卉b r 一 i 矿i + n 。p ( c ，l a ，) i l f d l 代表训i 练文档总数，i v i 代表特征总数，n 。代表特征t 在文档d 。中的 出现次数，n j s 代表特征s 在文柏d j 1 ，的出现次数。 朴素贝叶斯分类模型训练的过程其尖就是统计每一个特征在各类一p 出现规 律的过程。从理论上讲，贝叶斯分类的出错率最小，就实验结果来看，朴素贝叶 斯在大型的数据集上表现出来难得的速度和准确度。 2 4 3 决策树 决策树1 3 3 1 1 4 4 1 ( d e c i s i o nt r e e ) 是一个类似r 流程图的树结构，其中缚个节点 代表一个属性上的测试，每个分支代表一一个测试输出，最后的叶结点代表类别。 决策树方便改写为形如i f - t h e n 的分类规则，易于理解。 决策树的核心算法是一种贪心算法，它以自顶向下的方式在训练集的基础上 构造决策树，之后耿未知文档的属性在决策树上测试，路径山根结点到叶结点 从而得到该文档的所属类别。决策树的算法有c 4 5 | 4 0 l ( 发展于i d 3 ) ，c a r t l 4 0 1 ， c h a i d l 4 0 】等。他们的区别在于构造决策树与树枝剪除的算法细节不同。决策树 可以很好的抵抗噪声。最大的缺点在于刁：适应大规模的数据集，此种情况下决策 树的构造会变得效率低下。 2 4 4 神经网络 神经网络( n e u r a l n e t w o r k ) 3 3 1 拇1 的学习结果为日标函数，以这个目标函数 的输出作为分类的依据。输入即为文档在各个特征上的各分量值。神经网络实际 上是一组连接的输入输出单元，其中每一个连接都典钉一定的权值。通过训练 集来训练的过程就是调整这些权值的过“使得神经网络可以证确的预测类别。 神经网络的训练是针对训练例逐个进行的，所以神经网络的训练集可以随时 添加，不需要重新进行训练就可完成网络的嘲整。同时有实验结果表明在训练 例过少的情况下神经网络的分类准确牢较低。因为可通过训练米针对特征耿 定的合适的权值神经刚络可以较好地抵御噪爵的一f 扰。 2 4 5k 近邻 k n n ( k n e a r e s tn e i g h b o r ) 3 9 t 4 5 1 1 4 1 , 1 方法即k 近邻法，于1 9 6 8 年山c o v e r 和h a r t 提出f ”1 ，其基本思路为：如果一个待分类文档所在的特征空间中，与陔 文档最相似的k 个样本中大多数样本部埘于菜一个类别，则浚文档也属于这个类 别。相似度可以通过欧几里德距离或向j 连州央f f j 来度量。k n n 是。种基j 二类比 的分类方法，在训i 练的过程中k n n 会小成所有训练倒的特征向量，斤将其保存 下来。k n n 方法分类的。般过程为： 1 特征表示 划_ f 分类文档进行特征提取，表示j , 2 d h 权特征向量的形式。 2 相似样本选取 计算待分类文档与训练样本库q 每个训练样本之叫的相似度，选择相似度 最火的k 个样本作为选取的相似样本。 3 类别选择 在得到k 个与待分类文档最相似的洲练样本后，对这k 个样本所在的n 个 类别进行类别相似度计算，根据分类系统的实际需求选择相似度最大的m 个类 别作为分类结果输出。 k n n 是一种懒敞的方法，即它没有学习过程，只是存放所有的训练例，直 到接到待分类文档的时候才建立分类。k n n 的训练过程较快，而且可以随时添 加或更新训练例来调整。但它分类的丌销会很大，因为霈要很大的空渊来保存训 练例，而且分类时要比较待分类文档与所有的洲练例，时丑j 复杂度很大。有看法 认为在小数据集上k n n 的表现优异。 2 5 性能指标 般采用召隧率( 公式2 1 8 ) 和珂i ；确率( 公2 1 9 ) 作为基本测试指标并 可以使用微平均和宏平均计算其在所有类别中的，f 均值，有如下4 个测试指标： 微平均召回率( m i r ) ( 公式2 2 0 ) 、微平均准确率( m i p ) ( 公式2 2 1 ) 、宏 平均召回率( m a r ) 和宏平均准确率( m a p ) 。m a r 和m a p 的计算公式同公 式2 1 8 和公式2 1 9 ，在计算时文档数取所彳f 类相应的文档数之和。 f a l 亭( r e c a l l ) 一笔翼 亿，s ， 准确率( p r e c i s i o n ，= 筹鬻器 仁 y 类。的川一i 率 微平均召川率( m 1 r ) = 型一 ( 22 0 ) y 类c 的准确率 微平均准确率( m p ) = 型一 ( 2 2 1 ) 准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可 偏废，因此，存在一种新的评估指标，f 1 测试值，其数学公式如下： 删雌= 篇黑 仁：z ， 2 6 本章小结 本章详细介绍了文本自动分类中常j 打的特征提取、特征表示方法以及分类模 型并分析了各自的优点和不足，最后还介绍了文本自动分类的性能评价指标。 本文后面的工作中将用到其中的一些技术，并用本章中提到的性能评价指标来衡 量分类方法的性能。 第三章基于范例推理技术 基于范例的推理( c a s e b a s e dr e a s o n i n g ，c b r ) 是近十几年来人： 智能中 发展超来的区别于基于规则推理的一种推理模式，是对人类认知过程的一种模 拟，它是指借用旧的事例或经验来解决川题、评价解决方案、解释异常情况或理 解新情况。c b r 兴起的上要原因足传统的o , t - q ：规则的系统存在诸多的缺j _ ，如 在知以获取问题上存在困难，导致推理效率低下，不能做范例的例外处理，整体 性能较为脆弱等等，而c b r 恰好能解决以上问题。 c b r 的认知观点最切由耶鲁大学的k o g e rs c h a n k 和a b e l s o n 于7 0 年代后期 8