（计算机软件与理论专业论文）文本分类相关技术与应用研究.pdf

摘哽 摘要 随着通信技术和计算机技术，尤其是i n t e m e t 的飞速发展，各种各样的信息 成几何级数增长，作为传统的信息载体，文本信息更是如此。为了能在海量的文 本中及时准确地获得有效的知识和信息，文本表示技术以及文本自动分类技术受 到了广泛的关注。 。 文本分类是指在给定的分类体系下，根据文本的内容自动判别文本类别的过 程。本文描述了文本分类的基础理论，讨论了文本分类的相关技术，在向量空间模 型的基础上构建文本表示模型，研究现有的特征选择及算法。主要研究如下： 1 提出文本分类的理论基础，讨论文本表示的整个过程：分词，建立停用词 表，特征选择，权重计算，生成向量空间。 2 介绍并讨论了四种文本分类方法：贝叶斯方法，k n n 方法，支持向量 机法，决策树分类法，并对他们进行对比研究。 3 针对文本分词技术，特征选取算法和训练分类算法三部分进行了详细的 分析和研究，并在现有方法的基础上予以改进，最后通过实验分析了系统的性能。 实验结果表明改进后分类系统的性能更加令人满意，证明了算法的有效性。 4 对文本分类的未来研究进行展望。 关键词：文本分类，向量空间模型，特征选择，分类算法 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m m u n i c a t i o na n di n t e r n e t 。v a r i o u s i n f o r m a t i o ni n c r e a s e se x p o n e n t i a l l y t e x t ，t h em o s tt y p i c a li n f o r m a t i o n c a r r i e r ，c a nn o tm a k ea ne x c e p t i o n i no r d e rt oc o n t r o la n dr e t r i e v e v a l u a b l ei n f o r m a t i o n ，r e s e a r c ho fa 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 c ) b e c o m e sv e r yi m p o r t a n t t e x tc a t e g o r i z a t i o ni st h ea s s i g n m e n to fp r e d e f i n e dc a t e g o r i e st o d o c u m e n t sb a s e do nt h e i rc o n t e n t i ti sac o r eo ft e x tm i n i n g t h ep a p e r d e s c r i b et h eb a s i ct h e o r yo ft e x tc a t e g o r i z a t i o n ，d i s c u s s e dr e l e v a n c e t e c h n o l o g yo ft e x tc a t e g o r i z a t i o n ，c o n s t r u c t et h ev e c t o rm o d e l jo ft e x t r e p r e s e n t a t i o nb a s eo nv e c t o rs p a c em o d e l ， a n ds t u d yt h en o wa v a il a b l e f e a t u r es e l e c t i o na n da l g o r i t h n lt h em a i nr e s e a r c h e sa r ef o c u s e da s f 0 1 l o w s ： ( 1 ) t h ew h o l ep r o c e s so ft e x tr e p r e s e n t a t i o nw e r ed i s c u s s e d 叫o r d s e g m e n t a t i o n ，b u i l d i n gs t o pw o r d sl i s t ，f e a t u r es e l e c t i o n ，w e i g h t c o m p u t a ti o na n dg e n e r a tl o n gv e c t o rs p a c e ( 2 ) f o u rm e t h o d so ft 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 ，k n n ， s v ma n d d e c i s i o nt r e ew e r ei n t r o d u c e da n dc o m p a r e d ( 3 ) t r e em a i np a r t so ft e x tw o r d ss e g m e n t a t i o nt e c h n i q u e s ，f e a t u r e s e l e c t i o na n de x t r a c t i o na l g o r it h m sa n dc a t e g o r i z a t i o 丌a l g o r i t h m sw e r e a n a l y s e da n dr e s e a r c h e d ，o nt h eb a s i so ft h er e s e a r c h e s ，g i v et h ei m p r o v e d a l g o r i t h m s a n dd i s c u s sc a t e g o r i z i n ga b i l i t yo ft h es y s t e mb ys o m e e x p e r i m e n t s t h er e s u l t so ft h ee x p e r i m e n t sp r o v et h a t t h ei m p r o v e d a l g o r i t h m sa r ee f f e c t i v ea n dc a t e g o r i z i n ga b i l i t yo ft h es y s t e mi s s a t i s f i e d ( 4 ) t h er e s e a r c h e so nt e x tc a t e g o r i z a t i o ni nf u t u r ew e r ep r o s p e c t e d k e yw o r d s ：t 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 em o d e l ：f e a t u r ee x t r a c t i o n ； c a t e g o r i z a t i o na l g o r i t h m 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明儿 学位论文作者签名：星! ! ：塾指导教师签名： 唧年伞月日 年月日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：垂! ：墼 功年牛月日 绪论 1 1 选题的目的和意义 第i 章绪论 随着信息技术的发展，特别是i n t e r n e t 的应用和普及，各种科技文献以及互 联网上的信息爆炸式的出现在人们面前，如何自动处理大量的数字化文本成了一 项重要的研究课题。传统的做法是对网上信息进行人工分类，并加以组织和整理， 为人们提供一种相对有效的信息获取手段。但是，这种传统的人工分类的做法存 在着许多弊端：一是耗费大量的人力、物力和精力；二是存在分类结果一致性不 高的问题。这就要求探索计算机自动进行文本分类的有效方法，使得分类的正确 率提高。只有这样才能保证检索的查全率和准确率都得到提高。为了人们更好的 查找知识，发现知识，必须发展文本数据处理技术，文本分类是文本数据处理中 最重要的技术之一。文本分类不仅方便用户准确定位所需的信息，很大程度上解 决了目前网上信息杂乱问题，而且很好的解决了人工分类周期长、费用高、效率 低的缺点，已成为一项具有较大使用价值的关键技术。文本自动分类技术现己广 泛应用于i n t e m e t 上资料的搜索，电子图书馆中对图书的分类，网络安全中在防 火墙技术上的应用以及电子邮件分类的应用等等，通过文本分类技术可以弥补传 统搜索引擎的不足，过滤用户不需要的文章，并将检索结果分门别类，使用户能 够清晰地发现自己感兴趣的内容，同样，在政府机关或企业的邮件接收器中使用 文本分类技术，有根据邮件标题和正文的内容将邮件分类，分发到与之相关的部 门，从而进行处理，提高工作效率。 文本自动分类是人工智能技术和信息检索技术相结合的研究领域，是进行基 于内容的自动信息管理的核心技术。文本分类是指根据一些已经分配好类标签 ( 这些类标签预先定义好) 的训练文档集合，来对新文档分配类标签，其目的就 是对文本集进行合理处理和组织，使得这些文本能够按照类别区分开来。作为知 识的组织工具，它为信息检索提供了更高效的搜索策略和更准确的查询结果。其 中，高效性在于用户可以首先确定查询的可能类别，以减小需进一步匹配的文本 数量；有效性在于相似的文本很可能与相同的查询相关，这样使得检索的查全率 和准确率都得到了提高。 1 2 国内外研究现状 由于分类可以在较大程度上解决信息杂乱的现象，方便用户准确地定位所需 的信息和分流信息，特别是随着i n t e m e t 的快速发展，人们可以通过网络很快地 得到大量的资料，因此，对文本自动分类技术的研究提高到了一个i i i 所未有的高 度，更加广泛地引起国内外学者的关注。 国外自动分类研究开始与1 9 5 0 年代末，h p l u h n 在这一领域进行了开创性 的研究，他首先将词频统计的思想应用于文本分类中。1 9 6 0 年m a r o n 在j o u n a n l o fa s m 上发表了有关自动分类的第一篇论文“o nr e l e v a n e e ，p r o b a b i l i t i c i n d e x i n ga n di n f o r m a t i o nr e t r i r a l ”。1 9 6 2 年博科( h b o r k o ) 等人提出了利用 因子分析法进行文献的自动分类。其后许多学者在这一领域进行了卓有成效的研 究。国外的自动分类研究大体上可以分为三个阶段：第一阶段( 1 9 5 8 年一1 9 6 4 年) ，主要进行自动分类的可行性研究；第二阶段( 1 9 6 5 年一1 9 7 4 年) ，自动分类 的实验研究；第三阶段( 1 9 7 5 年一至今) ，自动分类的实用化阶段凹邮1 。现已 在邮件分类、电子会议、信息过滤等方面取得了较为广泛的应用，其中较为成功 的系统有麻省理工学院( m i t ) 为白宫开发的邮件分类系统、卡内基集团为路透 社开发的c o n s t r u e 系统等。 国外对文本分类技术以及相关的信息检索、信息抽取等领域进行了较为深入 的研究，对文本分类算法的研究开展的也较早，取得了不少令人注目的研究成果， 并产生了一些可用的分类系统。例如：自动分类新闻稿件的文本分类器i 卵j ：自 动分类w e b 页的文本分类器【g l ；自动跟踪用户阅读兴趣的分类器i 川等等。这些系 统大多数都建立在向量空间模型( t o - 1 2 1 的基础上，着重解决特征项的选择和权重计 算、学习算法等问题，以提高系统的性能和效率。 至今国外在向量空间模型的研究方面日益成熟。通过不同文本分类系统的 运行和比较表明，v s m 模型是文本分类领域大规模语料库较好的表示模型。此 外。不少学者正在努力突破特征项的选择空间，定义自己的文本表示空间，如 s a ms c o t t 定义了一套符号系统，利用w o r d s 和附加信息表示文本，也取得了一 2 绪论 定的成果【1 3 1 。但在基于向量空间模型的特征选择算法的性能比较方面以及文本 分类算法的性能比较方面，还没有得出统一的结论 1 4 - 1 5 】。另外，对训练文档不充 足的情况下如何利用标记文挡提高文本分类系统的性能，也展开了一定的研究。 国内自动分类研究起步较晚【娉删，始于2 0 世纪8 0 年代初期。1 9 8 1 年侯汉 清对计算机在文献分类工作中的应用做了探讨，并介绍了国外在计算机管理分类 表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后， 国内的研究者在英文文本分类研究的基础上采取相应策略，结合中文文本的特定 知识，然后应用于中文之上，继而形成中文文本自动分类研究体系。到目前为 止，我国陆续研制出一批计算机辅助分类系统和自动分类系统。例如中国科学院、 清华大学、北京大学、北京信息工程学院、上海交通大学、复旦大学、东北大学、 山西大学、同济大学、南京大学、浙江大学以及西安电子科技大学等单位都有相 应的研究成果，也研制出不少的实验系统。这其中有基于人工智能技术的分类系 统，有基于统计学技术的分类系统，还有基于模糊技术的分类系统，近几年基于 统计知识的分类方法占主流，也不乏有基于规则的分类方法。 国外当前流行的文本分类方法有k 近邻法( 州) 【2 ”、决策树 2 2 1 、朴素贝叶斯 ( n b ) 2 3 1 、支持向量机( s v m ) t 2 4 、神经网络( n n e t ) 【2 1 - 2 3 1 、线性最小平方拟合( l l s f ) 法 2 3 1 、最大熵模型b 5 1 、回归模型【2 1 蠲、遗传算法1 2 7 1 等方法。这些方法在英文文 本自动分类上有广泛的研究，而且很多研究表明k n n 和s v m 是英文文本分类 的最好方法国外很多研究人员对英文文本分类领域的各个问题都有相当深入的 研究，对几种流行的方法进行的大量的对比研究。y i m i n gy a n ga n dx i nl i u t 2 s l 对 s v m 、k n n 、l l s f 、n n e t 和n b 这5 种方法进行了专门的比较研究。 国内当前流行的文本分类方法有k 邻近( k n n ) 1 2 ”0 1 、朴素贝叶斯( n a i v e b a y e s ) 方法3 1 - 3 2 1 、最大熵模型1 3 3 】、线性最小平方拟合( l l s f ) 【3 4 1 、决策树方法【蜘、 神经网络方法【3 6 】、遗传算法鲫、支持向量机( s v m ) 方法【3 8 i 以及概念推理网法 ”9 】等等。其中k n n 、n b 和s v m 由于分类效果比较好成为近几年人们研究的热 点。文本分类过程由文本的表示、特征选择和分类器训练组成。分类算法只是其 中的一个环节，另外两个环节也非常重要。现在人们普遍采用向量空间模型表示 文本，常见的加权方法有：布尔权重、词频权重、t f i d f 权重和信息熵权重等。 常见的特征选择方法有：文档频率、特征词和类别的互信息、特征词的，【2 统计、 绪论 信息增益等。 1 3 本文研究工作 基于对以上文本分类的分析，本文从以下几个方面进行研究： ， 本文首先提出文本分类的理论基础，讨论基于向量空间模型的文本分类技 术，在向量空间模型的基础上构件文本表示模型，研究现有的特征选择及算法， 进行系统设计与系统分析，最后实现文本分类系统。 提出文本分类的基础理论，讨论文本表示的整个过程：分词，去停用词， 特征抽取，权重计算，生成向量空间。 基于向量空间模型的文本分类方法的对比研究，对比研究了贝叶斯方法， k n n 方法，决策树分类法，支持向量机法等。 在向量空间模型的基础上构建文本表示模型，对现有的特征选择及提取 算法进行了研究，考察了先前的实验结果。在分析现有缺陷的情况下进一步提出 一种新的综合特征项权重与简化的特征评估函数的特征选择与提取算法。通过对 多种分类器构建算法的研究，找到合适的算法，对其进行分析改进，实现文本分 类系统。 1 4 本文组织结构 本文共五章，其中各章主要内容如下： 第一章是绪论。主要介绍了文本分类相关技术与应用研究选题的目的和意 义，介绍了国内外的研究现状，并给出了本文的研究工作，最后给出了本论文的 组织结构。 第二章是文本分类基础理论。主要介绍了文本分类的基础理论，从特征词， 特征选择，向量空间模型三方面介绍文本的表示，并描述了多种文本分类算法， 最后描述了文本分类系统的评价体系。 第三章是文本分类系统的实现 第四章是文本分类系统的实验测试。 第五章是对本文的研究工作做了总结，对未来的研究进行了展望。 4 文奉分类理论摹础 第2 章文本分类理论基础 文本分类作为数据挖掘的一个新主题，已经引起人们的极大兴趣，文本分类 技术的深入研究和信息检索领域的应用，进一步提高了信息检索的精度和效率。 在搜索引擎应用中，主要是通过人工对文档进行分类，这大大限制了其索引页面 的数目和覆盖范围。在文献服务部门根据主题对文献进行分类的时候，传统上， 文献分类都要由专门的人员完成，为了能胜任分类工作，这些专门人员要进行严 格的培训，由于文献数量巨大，培训雇用专门人员迸行文献分类成为一项极其昂 贵的工作。因此。研究文本自动分类有着广泛的商业前景和应用价值。 r 互连网及大量联机电子文本的出现也提出了众多新的分类需求。例如，互联 网上的内容提供商希望能够建立面向具体用户的个性化内容服务。在这种服务架 构下，提供商需定期或不定期的向用户提供其指定的文献内容。例如，通过电子 邮件的方式每天向用户发送用户最感兴趣的新闻文本，用户可直接指定感兴趣的 文献主题，提供商也可以根据用户阅读文献的历史数据分析用户的阅读兴趣。为 了能向用户发送特定类别的文献，内容提供商需要提供文献过滤服务，由于不同 用户要求不同，并且文献应在很短的时间间隔内发达用户，由专业人进行分类投 递往往不分类存放，对这样大量并需要经常更新的联机文献进行手工分类也是不 现实的。大量的文献分类需求也促使人们对文本自动分类技术进行研究，本论文 所研究的系统正是迎合这种需求而产生的。 2 1 文本分类基本概念 2 1 1 文本分类的定义 文本分类的研究包括若干学科领域，包括语言学中的自然语言处理，图书馆 科学中的分类数学领域的统计学等知识，以及计算机领域的模式识别、人工智能、 神经网络等研究课题。 文本分类是指按照预先定义的分类体系，根据文本的内容自动地将文本集合 的每个文本归入某个类别，系统的输入是需要进行分类处理的大量文本，而系统 的输出是与文本关联的类别。简单地说，文本分类就是对文档标以合适的类标签。 文本分类理论基础 文本分类就是将一个二元组( d 。，c i ) d x c 映射到一个布尔值的任务。该映射用 数学公式表示如下： 由：dxc 一 t ，f ) ，其中d 一( d l ，d 2 ，k o h ) ，c = - ( c l ，c 2 ，k , e 。) 这里d 为有待分类的文本的集合，c 为给定分类体系下所有预先定义的类 别的集合，d 可以是无限集合，而c 必须是有限集合。如果将二元组( d i ，c ) 映 射为值t ( t r u e ) ，则认为文档d i 属于类别c ：i ，否则认为文档d j 不属于c 。 文本分类的关键就是要找到一个函数中：d xc 一 t ，f ) ，使得通过该函数能 够将任意一个文本尽可能准确地分类。这里中是根据已掌握的每类若干样本的数 据信息，总结出分类的规律性而建立的判别公式和判别规则。根据系统使用的学 习方法的不同，这些判别公式和判别规则也有所不同。在已经确定的映射规则的 基础上，系统在遇到新文本时，通过计算和判断，最终确定文本相关的类别。因 而，从数学角度看，可以说文本分类就是一个映射过程j 它将未表明类别的文本 映射到分类体系下已有的类别中。 2 1 2 文本分类的类别 根据应用的需要可以给该映射加以不同的约束，因为该映射可以是一一映 射，也可以是一对多的映射，即某些文本不但可以和一个类别相关联，也可以同 多个类别相关联。对于一个文档只能分给一个类别的一一映射的分类器，称之为 单类别分类器。这时任意一个文档d ，d 要么属于类别c 。，要么不属于类别c j 。 而如果一个文档可以分给c 中的任意个类别，即允许一对多的映射，这样的分类 器就称为多类别分类器川”。 在理论研究方面，对单类别分类的研究要远远多于对多类别分类的研究。主 要是由于单类别分类算法可以非常容易地转化成多类别分类算法，如要将一篇文 档分到k 个类中可以采用递归的方法，先将其分给一个类，然后问题变成将它分 给k 1 个类的情况，循环k 次后，最终可以将其分到k 个类中。不过这种方法有 一个假设条件，即各个类之间是独立的，没有相互依存关系或其他影响，当然在 实际应用中，绝大多数情况是可以满足此假设条件的。但反而言之，多类别分类 算法则很难转为为单类别分类，主要由于很难从多类别分类算法的k 个结果中 找到一个最好的类号分配给该文档；有些文档可能被赋予0 个类号，这时根本 6 文本分类理论基础 无法转化为单类别分类问题。 2 2 文本表示 2 2 1 向量空间模型( v s m ) 向量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) 4 2 1 是由s a l t o n 等人在六十 年代末到七十年代初期提出的模型，近年来应用较多且效果好。v s m 是由一组规 范化正交词条矢量所组成的向量空间，每一个文档映射为向量空间的一个点，向 量间的距离表示文档之间的相似度。通过这种模型可以将给定的文档以向量的形 式表示在v s m 中，从而将文档之间的相似性这一抽象的问题转化为具体的空间的 点与点的距离问题，通过计算出任意两个向量之间的近似程度，从而来反映所对 应的文档自j 的相似性。 在v s m 中，主要涉及到以下几个概念： ( 1 ) 文档( d o c u m e n t ) ：指一篇文章。 ( 2 ) 项( t e r m ) ：也称为索引项或特征项，一般指文档中的词或短语。给文档 分类主要是依据特征项，即一些特殊的项，可以起到代表文档的作用。 ( 3 ) 项的权重( t e r m w e i g h t ) ；假设一个系统包含有m 个文档、n 个不同的项， 则d i - ( t ，t ”，t 。) ( 1 i m ) ，表示一个文档；给其中的项t 。( 1 k n ) 赋值， 记为w 。，表示它在文档中的重要程度，通常称为项t 。的权重。 ( 4 ) 向量空问模型：由( 3 ) 得到一个含值的文档表示，记作： d t = ( t , w 。，t 2 w 矿“，t w 。) 。由于t ，t 。，t 。互不相同，可以把它们看作是n 维欧氏 空间的n 个坐标，把( w 。，w 2 ，w 。) 看作是n 维欧氏空间的向量。这样，称 d l - - ( t l w 。，t z w 2 ，t w 。) 为文档d 。的向量表示。t ；为特征项词条，w ，为对应坐标值， 即特征词条权值。 2 2 2 文本特征词的表示 通过计算机对文本进行分类，首先要把文本表示成计算机能处理的数据形 式。在文本分类中最常见的是对文本进行分词，这样文本就变为词集，而将全部 词集作为文本分类的特征，构成文本词汇的数量是相当大的，可以达几万个，因 文本分类理论基础 此需要对词集进行相应的压缩以获得对分类有用的特征，这样做的目的主要有两 个：第一，为了提高分类程序的效率 第二，为了提高分类的精度，由于不同的 词汇对文本分类的意义是不同的，一些是通用的、各个类别都普遍存在的词汇对 分类的贡献大，因此，对于每一类，应去除那些表现力不强的词汇，筛选出针对 该类的特征项集合。 2 2 2 1 停用词对文本分类的影响 r 在文本分类中对文本进行分词后，文本就变为词集，但是词集中有很多虚词 在文章中仅起到结构作用，不表示实际意义，比如介词，副词等等，另外还有一 些词在整个语料中出现频率高而在每篇文档中出现概率大致相等，对分类来说作 用不大，把这些词合称为停用词。对于这些词，应该从特征集中去掉。停用词的 选取对词集的大小、分类的准确率都有影响。 停用词的选择原则：第一，删除停用词后，分类准确率应不降；第二，删除 停用词后能够达到粗降维的目的。 停用词表的生成过程： ( 1 ) 计算词频，人工从高频词中将认为对分类贡献不大的词选出，如： “的”、“在”、“是”、“不”、“否则”等1 8 0 个词，作为停用词，放入停用词表。 ( 2 ) 将代词表、副词表、介词表、连词表和助词表加入，经过反复实验对比 分析，最后将代词和连词扩充进停用词表。 ( 3 ) 通过( 2 ) ，得到停用词表中一共由1 4 3 2 个词组成。 在实验中，从特征集维数缩减率和分类准确率两方面进行了衡量。去停用词 前的分类准确率是9 7 ，去掉由( 1 ) 得到的停用词后的分类准确率为9 7 5 6 1 。然 后加入代词和连词后分类准确率不变，但特征集中的特征减少了，之后又分别继 续加入副词表、介词表和助词表后特征集中的特征同样也减少了，但分类准确率 都有所降低，这说明由( 1 ) 得到的停用词表中的词对分类有负面影响，而代词和 连词对分类不起作用，把两者结合形成了进行文本分类所用的停用词表。另外， 去停用词前特征集中有1 0 8 6 9 个词，去后有8 2 2 5 个词，维数缩减了2 4 3 。通 过以上分析可以得出，去除停用词确实能够起到租降维和提高分类精度的作用。 2 2 2 。2 特征词的权重 文本分类理论基础 不同的特征项对文档的重要程度和区分度的影响是不同的，因此系统在对文 本进行形式化处理的时候，需要对特征项进行加权，下面对常用的加权函数进行 详细介绍。 ( 1 ) 布尔权重 布尔权重是最简单的一种加权方法，如果特征词出现次数为d ，则其权重为o ， 如果特征词出现词次数大于o ，则其权重为1 公式如下： i1 , t f i j 0 w t 沪i( 2 1 ) 0 ，t f f = 0 其中w h j 表示特征词i 在文档j 中的权重；t f o 表示特征词i 在文档j 中出现次 数。 ( 2 ) 词频权重 该方法将特征词的频次作为权重。公式如下： w 岛1 r( 2 2 ) ( 3 ) t f - i d f 权重 该方法基于以下两点原因：一是特征词i 在文档j 中出现的次数越多越重要， 权重和t 民成正比；二是文档集中含有特征词i 的文档数d f i 越大越不重要，权 重和d f i 成反比。公式如下： w - 1 r + l o g ( n d f i ) ( 2 ，3 ) 该式表明，若特征词i 在所有文档中均出现，即d f 州，则w t 。= o ，也就是说， 虽然特征词i 出现的次数多，但它的分布比较均匀，说明它没有区分类别的能力。 对上面进行归一化： r f u l o g ( _ d f , 1 a “=厣磊 为了降低t f 的作用将式( 2 4 ) 调整为： 2 厦l 丽o g ( t 覆f “+ 鬲1 0 而) * l o 面g ( n 丽d f , ) y k 9 ( 2 4 ) ( 2 5 ) 文本分类理论基础 其中n 表示全部训练文档的总数，d f i 表示在文档集合中出现特征词i 的文 档数目。 ( 4 ) 信息熵权重 乩g 扎o ) + 【( 1 + 丽1 万若n 【磊- 。s ( 器) 】) 1 ( 2 6 ) 上式( 2 6 ) 中的古喜【器l o g ( 静称为特跏的熵或者平均不确定性。 当分布极度均匀：熵等于一l ，说明它没有区分类别的能力。只在一个文档中 出现：熵等于0 ，说明它的区分类别的能力最大。 2 2 3 特征选择 在中文文本分类中，文本集经过分词后变成词集，然后经过去掉停用词粗降 维得到特征集。但是特征集仍然是个高维的特征空问，对于所有的分类算法来说 维数都太大。因此，面临寻求一种有效的特征抽取方法，以降低特征空间的维数， 提高分类的效率和精度。 特征选择的目的是除去特征集中不能较好表示有效信息的特征。以提高分类 准确度和减少计算复杂度。常见的特征选择方法【4 3 】【删有以下4 种：文档频率、 信息增益( i g ) 、互信息( m i ) 、x 2 统计量( c h i ) 等。这些方法的基本思想都是对 每一个特征即词条，计算它的某种统计的度量值，然后设定一个阀值t ，把度量 值小于t 的那些特征值过滤掉，剩下的即认为是有效特征。 2 2 3 1 文挡频率 一个特征的文档频率( d o c u m e n tf r e q u e n c y ) 是指在文档集中含有该特征的 文档数目。采用d f 作为特征选择，基于如下基本假设：d f 值低于某个阀值的词 条是低频词，它们不含或含有较少的类别信息。将这样的词条从原始特征空间中 除去，不但能够降低特征空间的维数，而且还有可能提高分类的精度。文档频率 是最简单的特征抽取技术，由于其相对于训练语料规撞具有线性的计算复杂度， 它能够很容易被用于大规模语料统计。而在信息检索研究中通常却认为d f 值低 的词条相对于d f 值高的词条具有较多的信息量，不应该将它们完全移除。不同的 1 0 文本分类理论基础 应用将对d f 值的认识不同，因此应根据具体情况来选择该方法。 2 。2 3 2 信急增益 信息增益( i n f o r m a t i ng a i n ) 在机器学习领域被广泛使用。对于词条t 和文 档类别c ，用i g 考察文档类别c 中出现和不出现词条t 的文档频数来衡量词条 t 对于文档类别c 的信息增益。采用如下的定义式： ( 轫h o ) = 芝羔尸o ) l 。g 尸( c ) + 【p p ) ! ：p qi t ) l o g p ( c , i t ) 牡6 畦尸螂 网 2 7 其中p ( c ，) 表示c ，类文档在语料中出现的概率，p ( t ) 表示语料中包含词条 t 的文档的概率，p ( c i i t ) 表示文档包含词条t 时属于c ，类的条件概率，p ( t ) 表 示语料中不包含词条t 的文档的概率，p f ) 表示文档不包含词条t 时属于c t 的条件概率，m 表示类别数。 实验中可以对语料中出现的每个词条计算其信息增益值，从原始特征空间中 移除低于特定阀值的词条，保留高于阀值的词条作为表示文档的特征。当然，信 息增益方法也有缺点：当t 仅出现在一个类中时，即使t 在这个类中均匀分布， g a i n 的值也很小，但这时t 对该类具有很强的代表性。 2 2 3 3 互信息 互信息( m u t u a li n f o r m a t i o n ) 在统计语言模型中被广泛采用，m i 越大，共 现程度越大。如果用a 表示包含词条t 且属于类别c 的文档频数，8 为包含t 但 是不属于。的文档频数，c 表示属于c 但是不包含t 的文档频数，n 表示语料中 文档总数，t 和c 的互信息可由下式计算： 州刊昭器= l o g 等剖o s 靠 亿s ， 如果t 和c 无关( 即p ( f ，c ) = n q ) x p ( e ) ) ，i ( c ，t ) 值自然为零。为了将互信 息应用于多个类别，与x 2 统计的处理类似，由下式计算t 对于c 的互信息： j 4 p 6 ) = m a x p ( c ，v ，c ，) l 妄州 ( 2 9 ) 其中m 为类别数。将低于特定阀值的词条从原始特征空间中移除，降低特征 文奉分类理论摹础 空间的维数，保留高于阀值的词条。另一种方法是公式，将词条对于各个类别的 平均，。( f ) 值作为它对所有类别的j 。9 ) 值，但是它的表现不如( 2 9 ) 式，平 均l 。o ) 值的计算见下式： i , v a ( f ) = p ( c ，) ，p ，c ) ( 2 1 0 ) f = l 2 2 3 4x 2 统计 x 2 统计方法度量词条t 和文档类别c 之间的相关程度，并假设t 和c 之间符 合具有一阶自由度的x 2 分布。词条t 对于某类的x 2 统计值越高，它与该类之间 的相关性越大，携带的类别信息也较多，独立性也越小。令n ，a ，b ，c 的含义同上 述2 3 3 ，d 是既不属于c 也不包含t 的文档频数。若a d b c ，则类和词独立， n = a + b + c + d a 则t 对于c 的x 2 值，由下式计算： x 2 q , c ) = 百面两n ( a 面d 两- c b 面) 2 西面 ( 2 1 1 ) 对于多类问题，分别计算t 对于每个类别的x 2 值，再用下式计算词条t 对 于整个语料的x 2 值，分别进行检验： x 2 “xp ) = m a x x 2 0 ，c ，) ( 2 1 2 ) 1 9 其中m 为类别数。从原始特征空间中移除低于特定阀值的词条，保留高于该 阀值的词条作为文档表示的特征。另一种方法是将词条对于各个类别的平均x 2 值作为它对所有类别的x 2 值，但是它的表现不如( 2 1 2 ) 式。 x 2 a v g ( f ) = p ( c ，坡2 ( f ，c ，)( 2 1 3 ) 2 3 文本分类方法介绍 分类方法是文本分类系统的核心内容，文本分类方法用一个已标好类别的文 本数据集( 即训练集) 来训练分类器，然后用训练好的分类器对未标识类别的文本 进行分类文本分类方法通过构造某种分类模型( 分类器) ，并依此判断样本所属 的类别空间。研究文本分类的关键问题是如何构造分类函数( 分类器) ，分类函数 需要通过某种算法进行学习获得。分类是重要的数据挖掘方法，在文本分类中， 文本分类理论基础 几乎存在着和一般分类同样多的方法。目前，常用的分类技术多是通过统计方法 或知识工程的方法实现的。知识工程方法主要依赖于语言学知识，需要编制大量 的推理规则，实现相当复杂。因为自然语言的复杂性，现阶段还无法实现自然语 言的机器理解，所以当前对文本分类技术的研究主要是偏重于统计学方法实现的 文本分类。相对于知识工程方法来说，基于统计学方法实现的文本分类具有速度 快，实现简单等特点，并且分类的准确率也较高，能够满足一般应用的要求。在 众多的文本分类算法中，本文主要分析贝叶斯分类算法、k n n 分类算法，中心向 量比较算法和支持向量机分类算法。 2 3 1 贝叶斯方法 该分类法的基本思路是计算文本属于类别的概率，文本属于类别的几率等于 文本中每个词属于类别的几率的综合表达式，集体算法步骤如下： ( 1 ) 计算特征词属于每个类别的几率向量，( ，w 2 ，嵋) l + 艺( 暇，z ) 其中，w k = p ( w k i c ，) - - - 叶耙丌一，p ( m i e ) 为w 在e 中出现的比 i v l + ( 彤，t ) 重，i dj 为该类的训练文本数，n ( w ，吐) 为概念w 在z 中的词频，i vj 为总概念数， ( 睨，喀) 为该类所有概念的词频合。 ，( 2 ) 在新文本到达时，根据特征词分词，然后按下面的公式计算该文本z 属 于类e 的几率： p ( q tb ) i ：ip ( y , lq ；易”畦一 j p ( c ，l z ；护) = 币：广点鼍一 l 2 1 4 ) 。 p ( cio ) f i p ( w k c r ；b ) ”以4 7 她蚂渤= 嚣，p ( c r i 嗍相似俄为类的臧 ( 呒，吐) 为在z 中的词频，1 1 为特征词总数。 ( 3 ) 比较新文本属于所有类的几率，将文本分到几率最大的那个类别中h 5 】 文本分类理论基础 2 3 2 最近k 邻居方法 该分类法的基本思路是：在给定新文本后，考察在训练文本集中与该新文本 距离最近( 最相似) 的k 篇文本，根据这k 篇文本所属的类别判定新文本所属的 类别，具体的算法步骤如下： ( 1 ) 根据特征项集合重新描述训练文本向量 ( 2 ) 在新文本到达后，根据特征词分词新文本，确定新文本的向量表示 ( 3 ) 在训练文本集中选出与新文本最相似的k 个文本，计算公式为： s i m ( d ，d ，) = 旷。j i ( 2 1 5 ) 其中，k 值的确定目前没有很好的方法，一般采用先定一个初始值，然后根 据实验测试的结果调整k 值，一般初始值定为几百到几千之间。 ( 4 ) 在新文本的k 个邻居中，依次计算每类的权重，计算公式如下： d 一 口口m p ( x ，c j ) = s i m ( x ，d ) y ( d ，c ，) ( 2 1 6 ) 量e k n n 其中，；为新文本的特征向量，s i m ( x ，d ，) 为相似度计算公式，与上一步骤 的计算公式相同，而y ( z ，q ) 为类别属性函数，即，如果z 属于类e ，那么函 数值为i ，否则为0 。 ( 5 ) 比较类的权重，将文本分到权重最大的那个类别中。 2 3 3 中心向量比较算法( r o c c h io ) 该算法的分类思路 4 6 。4 7 十分简单，首先在训练阶段求出训练文档各个类 别的中心向量。如：训练文档中“体育”类的文档有m 篇，那么体育类的中心 向量的第j 分量c j 为这i l l 篇文档对应的特征向量的平均值。 。：娶 m ( 2 1 7 ) 其中。，表示中心向量的第j 分量，q 表示该类文档中第i 篇文档的第j 个 权值。对新文档进行分类的过程就是一个比较相似度大小的过程，相似度表示为 新文档与各个类别中心向量的夹角余弦值。设第k 类的中心向量为。k ，新文档 1 4 文奉分类理论基础 向量为d ，则文档d ；与第k 类中心的相似度为： s i m ( c k s ( d i ，c 沪矗蓑寿 亿 略表示第i 篇文档的第j 个权值，。目表示第k 类文档的第j 个权值的大 小。相似度越大说明两个向量之间的夹角越小，两个向量越接近，因此，分类结 果将输出与新文档的相似度最大的类别，并把它作为新文档的类别。 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 4 8 由v a p n i k 在1 9 9 5 年提出， 是一种基于统计学习理论的新型的通用学习方法，它建立在统计学习理论的v c 理论和结构风险最小化原理的基础上，根据有限样本信息在模型的复杂性( 即对 特定训练样本的学习精度) 和学习能力( 即无错误的识别任意样本的能力) 之间 寻求最佳折衷，以期获得更好的泛化能力。其基本思想是首先通过非线性变换将 输入空间映射到一个高维特征空间，然后在这个新空阳j 中求取最优线性分类面， 而这种非线性变换是通过定义适当的内积函数( 骸函数) 来实现的。 s v m 分类的过程是给定的一个训练集，且可被一个超平面线性分割( 超平面 是对两类分类的划分，对于有大于两类的多类文本分类，就对每个类构造一个超 平面，将这一个类与其余的类分开，有多少个类就构造多少个超平面，测试时就 看哪个超平面最适合测试文本。) 该超平面记为：( w x ) + b = o 如果一个训练集中的向量能被一个超平面无错误地线性分割，且距该超平面 最近的向量之间的距离最大( 又称为问隔( m a r g i n ) 最大) ，则称该超平面为最佳超 平面。其中距离超平面最近的点即为对决策面设计起作用的点，称为支持向量 ( s v ) 。 2 。3 5 决策树分类法 决策树分类是一种得到广泛使用的分类技术。在该分类技术中，分类模型是 一个树结构。在分类树中，每个内部接点上都附有一个问题，这个问题通常是对 分类对象摸个特征的一个测试。例如，待分类文本中是否出现过“计算机”这 文奉分类理论蓬础 个词，在分类时，根据对这个问题的回答情况，待分类文本被传递给树结点的某 个字结点继续进行特征测试。 在利用决策树进行分类之前，必须得到决策树，如何得到决策树呢? 同贝叶 斯方法一样，可以利用训练集得到决策树分类模型。假定训练集中共有7 6 8 1 个 文本，共有2 0 个特征分量。调练闷题首先要解决的是在根结点处，测试哪个特 征，这就要根据分裂原则( s p l i t t i n gc r i t e r i o n ) 来决定，通常使用的分裂原则 是信息收益准则。其原理是根据分类前后的信息来决定采用哪个特征。因为选定 任特征进行测试，都会把训练集分成两个集合，根据信息论的有关知识，由于 得知了一个特征值，训练集在分裂后熵值会有所变化，分裂后由于已知某个特征 的值，确定性增加，故而熵会减少，信息收益原则建议总是选择能带来最大信息 交化的特征测试。信息收益可形式定义如下： g ( a ，j ，) = o ) 一h ( t l a ) = 日( ，) 一( p l h ( t l ) + 最h ( t r ) ) ( 2 1 9 ) 有了确定的分裂准则，就可以着手构造决策树了，因为有了2 0 个特征可以 测试，按照每个特征都可把训练集分裂成两个更小的集合，分别计算每种情况下 的信息收益，选择导致最大信息收益的特征测试。以此类推，最终可以按照自顶 向下的原则构造出一个决策树，直至4 所有的特征都经过测试， 2 4 文本分