（计算机应用技术专业论文）基于贝叶斯的网页文本分类算法.pdf

华中科技大学硕士学位论文 摘要 作为从w e b 信息资源中发现潜在的有价值知识的一种有效技术，基于w e b 的 数据挖掘正倍受关注，w e b 文本挖掘是w e b 数据挖掘的一个研究热点。目前基于 文本挖掘提出了很多算法，而简单贝叶斯算法是其中一种重要的方法。利用简单 贝叶斯进行分类，需要大量训练文本来进行分类，代价很大。如何提高简单贝叶 斯分类准确度，并减少训练文档数量是文本挖掘的研究重点。 w e b 文本挖掘研究涉及取词、分词等切词处理，以及文本分类方法。这里针 对英文文本作为文本分类的数据，采用改进的文档频度作为特征选取的标准，参 照标准数据集进行文本特征抽取，基于简单贝叶斯带潜在主题词改进了文本分类 器。在分类过程中，引入迭代因子提升迭代的速度，根据简单贝叶斯分类的基本 原理，基于先验假定带有类别标签的文档，对潜在类别关键词通过有限次迭代得 到分类结果。在每次迭代过程中，后验概率最大的潜在分类词作为该次迭代的分 类结果，最终分类结果由每次迭代得到的分类结果综合而得。 分类算法是针对w e b 文本分类而提出的一种基于简单贝叶斯文本分类方法， 它利用了简单贝叶斯分类的基本原理，大大简化了构造贝叶斯网络的复杂性；又 引用了潜在语义分析的思想，能减少贝叶斯分类的所需的大量训练文档，试验结 果证明，它是一种比较有效的分类方法。所做的研究主要针对英文文本，考虑到 中文取词分词的复杂性，在中文文本分类方面还需进行进一步研究。 关键词：数据挖掘，文本分类，简单贝叶斯，迭代 华中科技大学硕士学位论文 a b s t r a c t w i t ht h ef l o o do fi n f o r m a t i o no nt h ew e b ，w e bm i m n gi san e wr e s e a r c hi s s u e w h i c hd r a w s g r e a t i n t e r e s tf r o m m a n yc o m m u n i t i e s c u r r e n t l yt h e r e a l e m a n y a l g o r i t h m sa b o u tw e bm i n i n g s i m p l eb a y e si sag o o da l g o r i t h mo ft h e m i tn e e d s m a n yt r a i n i n gd o c u m e n t st om a k ec l a s s i f i e r s oh o wt oi m p r o v ea c c u r a c ya n dd e c l i n e t h en u m b e r s o f t r a i n i n gd o c u m e n t s i sv e r y i m p o r t a n t f o rs i m p l e b a y e s - b a s e dc l a s s i f i e r t e x tm i m n gi n c l u d e sw o r d sp r o c e s s i n ga n dt e x tc l a s s i f y i n gm e t h o d e n g l i s ht e x t i sm a d ea st h ec l a s s i f i e d s a m p l e i no r d e rt od e c l i n et h e c o m p l e x o ft h ew o r d s t e m m i n g ，s i n c e c h i n e s et e x tn e e dm u c hw o r ko nw o r d p r o c e e d i n g a n da ni m p r o v e d d o c u m e n tf r e q u e n c ym e t h o di sm a d et h es t a n d a r do ft h ec h a r a c t e rv e c t o r i nt h e c l a s s i f i e r , t h e r e a r es e v e r a lm e t h o d s ，w h i c hi n c l u d et h em e t h o do fp r o b a b i l i t ya n d i t e r a t i o n i t g i v e s s o m ew o r d sw h i c ha r e r e g a r d e d a st h el a t e n tl a b e lb e f o r et h e c l a s s i l y i n g t h e n t h e d o c u m e n ti sl a b e l e d 谢t l lt h el a b e lw h i c hh a st h em a x i m p o s t p r o b a b i l i t yi ne v e r yc l a s s i f i c a t i o n t h ef i n a ll a b e li sm a d eu po f t h ea l ll a b e l st h a t a r eg o tf r o mi t e r a t i o n s t h i sc l a s s i f i e ri sas i m p l eb a y e s - b a s e dc l a s s i f i e rf o rw e bt e x t i tu s e sm e t h o d so f s i m p l eb a y e s i a nm o d e la n dl a t e n t w o r da n a l y s e s i td e c r e a s e st h e c o m p l e x i t y o f b a y e s i a nn e t ，a n di ti m p r o v e st h ea c c u r a c yo fc l a s s i f i e ra n dd e c l i n et h en u m b e ro f t r a i n i n gn u m b e r s oi t i sag o o dt e x tc l a s s i f i e rb yt h ee x p e r i m e n t s a n di ts h o u l db e t e s t e df o rc h i n e s et e x ti nn e x ts t a t es t u d y k e y w o r d s ：d a t am i n i n g ，t e x t c l a s s i f i c a t i o n ， s i m p l eb a y e s i a n ， i t e r a t i o n i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均己在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承 担。 学位论文作者签名：；江 日期：删绰f 月z 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于不保密口。 ( 请在以上方框内打“”) 学位论文作者签名：歇弘 日期：”霹罗月7 蝈 指导教师签名：导豸主p 日期：口掣确胁日 华中科技大学硕士学位论文 1 1 课题背景 1 绪论 让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 查找信息。只要你说出想查询什么，马上就能得到所有 符合要求的信息，并且不被那些不相干的信息所打扰。这实际上隐含了对信息检 索的两个要求：查全率和查准率【2 1 。 查准率是检出文档之中真正符合检索意图的文档所占的比率即： 查准率= 器豢 查全率是所有符合检索意图的文档之中被检出的文档所占的比率，即： 杏全率：堡塑塞些塑 应有文档数 查全率和查准率反映了检索质量的两个不同方面，二者必须综合考虑，不可 偏废。如果只考虑查准率，那么只检出1 篇文档最有把握，得到了查全率是1 0 0 ， 但是这样的话，符合要求的文档被检出的数目太少，不能满足全面了解相关信息 内容的要求；同样地，如果片面的追求查全率，那么把所有的信息都端出来，查 全率固然可以达到1 0 0 ，但是真正有用的信息就都淹没在大量的无用信息之中 了，无法满足快速地、有针对性地了解信息内容的需求。因此，任何信息检索系 统都要在查全率和查准率之间进行权衡。 华中科技大学硕士学位论文 在网络时代谈起信息检索，这里就得提到搜索引擎。现在的确有很多声名显 赫的搜索引擎，比如y a h o o ! 等 3 1 i 但是问题并没有因此实际解决。实际使用过搜 索引擎的人想必都有这种体会：想查的东西查不着，不相关的东西倒是很多。构 造更好的信息检索系统仍然是人们努力的目标。 其次是利用i n t e r n e t 订阅信息。只需事前在某个地方登记对哪些信息感兴趣， 由某种机制从用户的浏览历史行为中学习出用户的兴趣，然后只要有人在网络上 发布了相关信息，就能立刻推送到用户手中，也就是个性化、主动化的“信息找 人、按需服务”。 每个用户都有自己特定的信息需求，设法获得这些信息需求，进而使用这些 信息需求组成过滤条件，对信息资源进行过滤，就能把符合条件的信息抽取出来 进行服务。 个性化的实质是针对性，即对不同的用户采取不同的服务策略，提供不同的 服务内容：主动服务的实质是主动性，即不需用户做什么，系统自动按照用户的需 求来提供相应的服务。个性化主动服务将使用户付出尽可能小的努力，获得尽可 能好的服务。 另一方面是信息的加工、过滤和整理。i n t e m e t 上的信息浩若烟海而又纷繁芜 杂，怎样才能掌握尽可能多的信息，同时避免那些令人讨厌的信息，始终是一个 有意思的话题。 信息的加工和整理能够使得人们更好地掌握信息。在搜索引擎上，随便输入 一个查询，就能得到成千上万个页面，如果你想作全局了解的话，除了逐篇阅读 别无他途。一种可行的解决办法就是把获得的大量信息进行条理化，自动地将页 面分检成不同的类别。初步的实验表明【4 1 ，把信息分组并且每组都抽取出一个主 题的做法有助于使用者找到他感兴趣的文件。 信息过滤是i n t e m e t 上另一个重要的问题。在网络空间中，人们不仅与熟人 或朋友进行商业和社交来往，同时还要和形形色色的陌生人打交道。换句话说， i n t e r n e t 上不仅存在数不清的机遇，同时也潜伏着许多危险。如何避开那些令人 讨厌的，甚至是危险的信息，就是信息过滤专家关注的课题。 华中科技大学硕士学位论文 这些只是人们对信息服务的各式各样需求的冰山之一角。总之，一方面是人 们对快速、准确全面获取信息的渴望，而另一方面却是i n t e r n e t 上信息的纷繁芜 杂，在这两者之间架设一座桥梁的确是一个巨大的挑战。 作为从浩瀚的w e b 信息资源中发现潜在的、有价值知识的一种有效技术，w e b 挖掘正悄然兴起，倍受关注。目前w e b 挖掘的研究正处于发展阶段，尚无统一的 结论，需要国内外学者在理论上开展更多的讨论。同时，w e b 挖掘系统的开发对 其研究也将起到很大推进作用【5 j 。 1 2 国内外概况 1 2 1w e b 挖掘的起源 w e b 挖掘必须从数据挖掘谈起。根据w j f r a w l e y 和g e s h a p i r o 等人的定义【6 _ 7 】，数据挖掘是指从大型数据库的数据中提取人们感兴趣的知识，而这些知识是 隐含的、事先未知的、潜在的有用信息。如：股票经纪人需要从日积月累的大量 股票行情变化的历史记录中发现其变化规律，以供预测未来趋势之用；超级市场 的经理人员希望能从过去几年的销售记录中，分析出顾客的消费习惯和行为，以 便及时变换营销策略等等。 数据挖掘的提出最初是针对大型数据库n t 8 1 ，这些数据库容量可能达到 g b ( 1 0 9 ) 字节，甚至t b ( 1 0 ”) 字节，最近i b m 提出其数字图书馆的数据将可能达 p b ( 1 0 ”) 字节。 从更广义的角度来讲，数据挖掘意味着在一些事实或观察数据的集合中寻找 模式的决策支持过程。因而，数据挖掘的对象不仅是数据库，还可以是任何组织 在一起的数据集合，如w w w 信息资源等。目前数据挖掘工具能处理数值型的结 构化数据，而文本、图形、数学公式、图像或w w w 信息资源等半结构、无结构 的数据形式将是数据挖掘的挑战之一【9 】。 华中科技大学硕士学位论文 1 2 2w e b 挖掘的定义 w e b 挖掘是一项综合技术，涉及w e b 、数据挖掘、计算机语言学、信息学等 多个领域。不同研究者从自身的领域出发，对网络信息的含义有着不同的理解， 项目开发也各有其侧重点。例如，国外学者认为【lo 】：w e b 挖掘就是利用数据挖掘 技术，自动地从网络文档以及服务中发现和抽取信息的过程。国内则众说纷纭。 有学者将网络环境下的数据挖掘归入网络信息检索与网络信息内容的开发f 1 1 。也 有站在信息服务的角度上提出“w e b 挖掘”，指出其有别于传统的信息检索，能 够在异构数据组成的信息库中，从概念及相关因素的延伸比较上找出用户需要的 深层次的信息 1 2 1 ，并提出w e b 挖掘将改革传统的信息服务方式而形成一个全新的 适合网络时代要求的信息服务组合。可以一般地将w e b 挖掘定义为【1 3 l ： w e b 挖掘是指从大量w e b 文档的集合c 中发现隐含的模式集p 。将c 看作输 入，p 看作输出，w e b 挖掘的过程就是从输入到输出的一个映射：c p 。 w e b 挖掘从数据挖掘发展而来，因此其定义与一般熟知的数据挖掘定义相类 似。但是，w e b 挖掘与传统的数据挖掘相比有许多独特之处。首先，w e b 挖掘的 对象是大量、异质、分布的w e b 文档。因此，以w e b 作为中间件对数据库进行 挖掘，以及对w e b 服务器上的日志、用户信息等数据所开展的挖掘工作，仍属于 传统的数据挖掘的范畴。其次，w e b 在逻辑上是由一个由文档节点和超链接构成 的图，因此w e b 挖掘所得到的模式可能是关于w e b 内容的，也可能是关于w e b 结构的。此外，由于w e b 文档本身是半结构化或无结构的，且缺乏机器可理解的 语义，而数据挖掘的对象局限于数据库中的结构化数据，并利用关系表格等存储 结构来发现知识，因此有些数据挖掘技术并不适用于w e b 挖掘，即使可用也需要 建立在对w e b 文档进行预处理的基础之上。这样，开发新的w e b 挖掘技术，以 及对w e b 文档进行预处理以得到关于文档的特征表示，便成为w e b 挖掘研究的 重点。 华中科技大学硕士学位论文 1 2 3w e b 挖掘与w e b 信息检索 1w e b 信息检索的定义 w e b 信息检索14 1 ，是指从大量w e b 文档的集合c 中找到与给定的查询请求集 q 相关的、恰当数目的文档子集s 。w e b 信息检索的过程也对应于一个映射：( c ， q ) 一s 。 从6 0 年代以来，信息检索领域在索引模型、文档内容表示、匹配策略等方面 取得了许多研究成果【1 5 】。这些成果被成功地应用在w e b 上，产生了搜索引擎，例 如y a h o o ! ，a l t a v i s t a 等1 1 6 - 1 8 】。搜索引擎工作的一般流程包括：使用r o b o t 搜集 w e b 文档、对文档集合建立倒排索引、分析用户的查询请求、匹配文档与查询请 求以计算二者之间的相似度、对查询结果进行排序以及用户相关度回馈。 2 两者的关系 w e b 上的挖掘和信息检索是两种不同的技术，其区别主要表现在以下几个方 面： ( 1 ) 方法论不同：信息检索是目标驱动的，用户需要明确提出查询要求；而挖 掘是机会主义的，其结果独立于用户的信息需求，也是用户所无法预知的； ( 2 ) 着眼点不同：信息检索着重于文档中显式存储的字词和链接：而挖掘试图 更多地理解其内容和结构； ( 3 ) 目的不同：信息检索的目的在于帮助用户发现资源，即从大量文档中找到 满足其查询请求的文档子集：而挖掘是为了揭示文档中隐含的知识； ( 4 ) 评价方法不同：信息检索使用精度( p r e c i s i o n ) 和召回率( r e c a l l ) 来评价其性 能，要求返回尽可能多的相关文档，同时不相关的文档尽可能少。而挖掘采用收 益( g a i n ) 、置信度( c e r t a i n t y ) 、简洁性( s i m p l i c i f y ) 等来衡量所发现知识的有效性、 可用性和可理解性； ( 5 ) 使用场合不同：有时信息检索系统返回太多的结果以致用户无法一一浏 览，有时用户没有明确的信息需求，有时用户希望发现文档集合中所具有的结构、 趋势、含义，在这些场合下，就需要使用挖掘技术。 尽管w e b 挖掘是比信息检索层次更高的技术，但它并不是用来取代信息检索 华中科技大学硕士学位论文 技术，二者是相辅相成的。一方面，这两种技术各有所长，有各自适用的场合： 另一方面，可以利用w e b 挖掘的研究成果来提高信息检索的精度和效率，改善检 索结果的组织，使信息检索系统发展到一个新的水平。 狭义上讲，w 曲信息检索就是w e b 挖掘的一种。最初，信息检索的目标是标 引文本，并从集合中找出有用的文档：发展到今天，信息检索研究涉及到建立模 型、文档分类与聚类、用户交互、数据可视化、数据过滤等等。从这个角度看， w e b 挖掘只能作为信息检索过程的一部分。最明显的一个例子就是w e b 文档的分 类与聚类。 1 2 4 w e b 挖掘的研究方向 在逻辑上，可以把w e b 看作是位于物理网络之上的一个有向图g = ( n ，e ) ， 其中节点集n 对应于w e b 上的所有文档，而有向边集e 则对应于节点之间的超链。 对节点集作进一步的划分n = 川，。) ，所有的非叶节点。，是h t m l 文档， 其中除了包含文本以外，还包含了标记以指定文档的属性和内部结构，或者嵌入 了超链以表示文档间的结构关系。叶节点，可以是h t m l 文档。也可以是其它 格式的文档，例如p o s t s c r i p t 等文本文件，以及图形、音频等媒体文件。如图1 1 所示。n 中每个节点都有一个u r l 。其中包含了关于该节点所位于的w e b 站点和 目录路径的结构信息。 图1 1w e b 的逻辑结构 华中科技大学硕士学位论文 w e b 上信息的多样性决定了w e b 挖掘任务的多样性。根据挖掘对象的不同， w e b 挖掘可以分为w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e b s t r u c t u r em i n i n g ) 以及w e b 使用记录挖掘( w e bu s a g em i n i n g ) 。内容挖掘指的是从 w e b 文档的内容或描述信息中抽取知识，结构挖掘指的是从w w w 的组织结构和 链接关系中推导知识，而使用记录挖掘则是指w e b 的访问记录中抽取感兴趣的模 式。内容挖掘又分为对文本文档( 包括t e x t ，h t m l 等格式) 和多媒体文档包括( 包 括i m a g e ，a u d i o ，v i d e o 等媒体类型) 的挖掘。w e b 结构挖掘不仅仅局限于文档之 间的超链结构，还包括文档内部的结构、文档u r l 中的目录路径结构等。如图 1 2 所示。在本章中仅对w e b 上的文本挖掘和结构挖掘和使用记录挖掘加以讨论。 下文中提及的“文档”是指文本文档，不包括多媒体文档。有关w e b 上的多媒体 文档挖掘，z a j a n e 等在这个方向已做了出色的工作【1 9 1 ，感兴趣的读者可参见他们 的相关文献。 w e b 挖掘 1 一 ；l 内容挖掘 jj使用记录挖掘ff l 。一一1 1 、一一 l 一 。 l l 一j _ l、上lf 上- i 文本挖掘l；多媒体挖掘j【超链挖掘】 结构挖掘 u r l 挖掘 图l2w e b 挖掘的分类 1w e b 文本挖掘 w e b 文本挖掘可以对w e b 上大量文档集合的内容进行总结、分类、聚类、信 息，也可以弱用这些信息来提高w e b 文本挖掘的性能。w e b 文本挖掘包括了从w e b 上提取信息行成w e b 页面的特征集，并利用定的方法对特征集进行分类、聚类 并最终得到文本分类视图。图1 3 给出了w e b 文本挖掘的般流程图。 华中科技大学硕士学位论文 分类器 眵弋多r ；购零 图1 3 文率分类的一般流程 h l 文本视图 当前用于文本分类的主要技术有：概率统计方法1 8 q 0 1 ，决策树( d e c i s i o n t r e e ，d t ) 1 2 1 ，决策规则( d e c i s i o nr u l e ) ，回归模型( r e g r e s s i o nm o d e l ) 1 2 2 ，神经 网络( n e u r a ln e t w o r k ，n n ) 2 3 1 ，k - 最近邻居( k - n e a r e s tn e i g h b o r ，k 小附) 2 4 1 ，支持 向量机( s u p p o r t v e c t o rm a c h i n e ，s v m ) 2 5 j 等 2w e b 结构挖掘 由于w e b 中包含的结构信息处理起来比较困难，因此通常的w e b 搜索引擎 等工具仅将w e b 看作是一个平面文档的集合，而忽略了其中的结构信息。w e b 结 构挖掘的目的在于揭示蕴含在这些文档结构信息中的有用模式。 文档之间的超链反映了文档间的某种联系，例如包含、从属等。超链中的标 记文本( a n c h o r ) 对链宿页面也起到了概括作用，这种概括在一定程度上比链宿页 面作者所作的概括( 页面的标题) 要更为客观、准确。 c r a v e n 等人使用阶学习方法对w e b 页面间的超链类型进行分类1 2 6 ，以判 断页面间的m e m b e r so f p r o j e c t ，d e p a r t m e n t o f - p e r s o n s 等关系；同时，他们还利用 超链中的标记文本对链宿页面进行分类，取得了较好的效果。超链还反映了文档 间的引用关系，一个页面被引用的次数体现了该页面的重要性。b r i n 等人通过综 合考虑页面的引用次数和链源页面的重要性来判断链宿页面的重要性口7 】，从而设 计出能够查询与用户请求相关的“权威”页面的搜索引擎。 接口 n 卜 华中科技大学硕士学位论文 每个w e b 页面并不是原子对象，其内部有或多或少的结构。s p e r t u s 对w e b 页面的内部结构作了研究2 引，提出了一些启发式规则，并用于寻找与给定的页面 集合 p 1 ，p n ) 相关的其它页面。d i p a s q u o 使用h t m l 结构树对w e b 页面进 行分析 2 9 - 3 0 】，得到其内部结构特征，从而学习公司的名称和地址等信息在页面中 的出现模式。 w e b 页面的u r l 可能会反映页面的类型，也可能会反映页面之间的目录结构 关系。s p e r t u s 提出了与w e b 页面u r l 有关的启发式规则 3 1 】，并用于寻找个人主 页，或者寻找改变了位置的w e b 页面的新位置。 3w e b 使用记录挖掘 w e b 使用记录挖掘的主要目标是从w e b 的访问记录中抽取感兴趣的模式。通 过w e b 使用记录挖掘，可以了解用户的网络行为数据所具有的意义。w e b 内容挖 掘、w e b 结构挖掘的对象是网上的原始数据，而w e b 使用记录挖掘则不同于前两 者，它面对的是在用户和网络交互的过程中抽取出来的第二手数据。这些数据包 括：网络服务器访问记录、代理服务器日志记录、浏览器日志记录、用户简介、 注册信息、用户对话或交易信息、用户提问式等等。分析这些数据可以帮助理解 用户的行为，从而改进站点的结构。或为用户提供个性化的服务。这方面的研究 主要有两个方向3 2 】：一般的访问模式追踪和个性化的使用记录追踪。一般的访问 模式追踪通过分析使用记录来了解用户的访问模式和倾向。以改进站点的组织结 构。而个性化的使用记录追踪则倾向于分析单个用户的偏好，其目的是根据不同 用户的访问模式，为每个用户提供定制的站点。 1 3 课题的主要研究工作 1 3 1 课题的研究设想及工作 目前，与w e b 挖掘有关的各种项目涉及了上述任务的某个方面，也有一些项 目综合考虑了w e b 的内容和结构因素，将文本挖掘与结构挖掘结合起来，以取得 更好的效果。尽管与多媒体信息相比，文本信息显得比较普通，但文本仍然是记 华中科技大学硕士学位论文 载和传播信息的最主要媒体。此外，文本挖掘又相对容易取得技术突破，其中的 许多研究成果也可以为多媒体挖掘和结构挖掘所借鉴。因此对文本挖掘技术的研 究具有十分重要的意义和广泛的应用前景。因此，本文重点对w e b 文本挖掘的方 法和系统设计进行讨论。 本文中主要是给出了一种带有潜在关键词的简单贝叶斯分类器，它主要是利 用简单贝叶斯分类的思想，并借用了潜在语义分析的方法，在分类过程中引入了 潜在类别关键词。在原来分类器的基础上引入了一种迭代分类过程。主要包括了 简单贝叶斯方法，概率统计理论，潜在语义分析咀及加权迭代提升的思想。 1 3 2 本文的组织结构 本文的组织结构如下：在第二章中介绍了文本分类的一般方法，并对几种分 类方法的优缺点进行了比较；第三章重点介绍了本文采用的分类器的主要方法及 思想，并说明了该方法所需用到的技术；第四章给出了分类的预处理一切词处理 的一般方法，并给出了本文的切词方法；第五章是试验验证，比较了该分类器和 未改进前的分类器的比较结果；第六章对本文做了总结，并对未来工作进行了展 望。 华中科技大学硕士学位论文 2 文本分类 本章主要讨论文本分类的定义及文档的表示方法，接着介绍了几种常用的分 类方法，着重介绍了贝叶斯分类算法，并给出了几种分类算法的优缺点。然后给 出了评价分类器的标准。 2 1 文本分类的定义 简单地讲，文本分类就是运用机器学习( m a c h i n el e a r n i n g ，m l ) 、知识工程 ( k n o w l e d g ee n g i n e e r i n g ，k e ) 或其它方法来建立一个分类模型，然后利用这个模 型将未知类别的文本文档分类到个或多个预定义的类别中。【3 3 给出了文本分 类的形式化定义。 文本分类就是将一个二元组 d x c 映射到一个布尔值的任务。其 中d 是所讨论的文档的集合，c = c ic ：q ) 是预先定义的类别的集合。如果将二 元组 映射为值t ( t r u e ) ，则认为文档d j 属于类别c ，否则认为文档d ，不 属于类别c ，。 更形式化地说，假设有个未知的目标函数妒：d x c - - 4 t ，f ，这个函数能够 将任意个文本准确地分类。文本分类就是要找到一个函数：d x c 一 t ，f ) 使 得它的结果能够尽可能地与庐接近。 根据应用的需要可以给文本分类加以不同的约束。例如可能需要这样一个分 类器，对给定豹整数k ，每个文档d d 需要分类到c 中的k 个不同的类别中。 k = l 时，即一个文档只能分给一个类别，这样的分类称为单类别分类，而如果一 个文档可以分给c 中的任意个类别，这样的分类称为多类别分类。单类别分类的 一个特例就是二值分类，即对任意一个文档d ，d 要么属于类别c ，要么不属予 华中科技大学硕士学位论文 类别c ，( 这时属于类别c ，的补集c ，) 。 理论上，只需二值分类( 同时也是单类别分类) 就可解决所有分类的问题。这 是因为一个二值分类的算法也可以用于多类别分类，只需将类别集c = k ，c ，c 。 上的多文档分类问题转变为c 个独立的在类别集 c ，c ，) 上的二值分类问题。 但是这样做的前提条件是c 中的各个类别必须是随机独立的，即对c 中的任意两 个类别c 和c ”，o ( d ，c ) 的值不依赖于巾( d ，一) 的值，反之亦然。然而反过 来一个多类别分类的算法不能够用于二值分类和单类别分类。这是因为，给定一 个待分类文档d ，多类别分类算法可能将其分类到k 1 个类别中，很难从这k 个 类别中选择一个最合适的类别来用于单类别分类。另外多类别分类可能根本就没 有将d ，分类到任何类别中，这时也很难从类别集合c 中选择一个类别分给d 使其 适用于单类别分类。 因此，可以将类别集c = c 。，c ：，c 。) 上的分类问题看作是i c | 个独立的二值分 类问题，为c 中的每一个类别c ( f = 1 , 2 ，i c l ) 构造二值分类器o f d 呻 r ，f ) 。 2 2 文档的表示 原始的文本不能够被分类器构造算法和分类器直接处理，所以需要将文本进 行某种处理，以分类器构造算法和分类器能够处理的形式表示出来。在文本分类 领域，一个文档d 通常由一个带权重的特征向量来表示，即 d = 其中，f 是特征集，0 w 目 l 表示特征以在多大程度上代表了文档d ，的语 义。对这种表示方法，有两个问题需要考虑： 1 如何表示一个特征； 2 如何计算特征的权重。 华中科技大学硕士学位论文 对第一个问题来说，通常的做法是用个单词来表示一个特征。这种表示方 法称为单词集( s e to f w o r d s ) 方法或单词包( b a go f w o r d s ) 方法( 具体地讲如果权 重只能取0 和l ，则称为单词集方法，否则称为单词包) 。另外也有人用词组( p h r a s e ) 作为特征。用词组作为特征时，有两种定义一个词组的方法：一种是根据语法信 息，即在语法上有一定联系的多个单词认为是一个词组：另外一种是根据统计信 息，即认为多个频繁地同时出现的单词序列或单词集合是词组。 对第二个问题，权重一般在0 到1 之间取值。一种特例就是布尔权重，即= 】 表示特征 在文档d ，中出现，而w h = 0 表示特征 在文档d ，中未出现。 使用布尔权重还是非布尔权重取决于分类器学习算法。使用非布尔权重时， 如何来决定的值有很多种方法。通常使用t f i d f 函数。特征 对于文档d ，的 t f i d f 定义为： o d f ( f , , d j ) 2 # ( 六, d j ) l o g - 萍y r t 【r ， 万 2 1 ) 其中，# ( 五，以) 表示特征厶在文档办中出现的次数，舟乃( ) 表示特征五的 文档频率( d o c u m e n t 行e q u e n c y ) ，即训练集t r 中包含特征 的文档数，i t r | 表示 训练文档集中包含的文档数。由式( 2 1 ) 可以看出，这个定义体现了以下两点： 1 某个特征在一个文档中出现的次数越多，它就越能代表这个文档的内容； 2 包含某个特征的文档数越多，这个特征就越不具有分类的能力。 需要注意的是这个公式只考虑了特征在文档中出现的次数，并未考虑特征在 文档中出现的位置，顺序，及句法等信息。 为了使权重落在 0 ，1 的区间范围内，并且为了使文档以相同长度的向量来 表示，需要将t f i a f 得到的结果进行规范化处理，通常用余弦规范化： 岷： 丝丝竺!( 2 一2 ) w h = f 3 = = = = = = 兰= = 一 1 z j m i f l 俨叭叫j 2 。 华中科技大学硕士学位论文 2 3 分类技术 在2 0 世纪8 0 年代，文本分类系统主要是基于知识工程( k n o w l e d g e e n g i n e e r i n g ，k e ) 的方法的，这种方法需要由人类专家来手工构造分类模型。到 2 0 世纪9 0 年代早期，机器学习( m a c h i n el e a r n i n g ，m l ) 方法渐渐流行起来并至 少在研究领域占据了主导地位。 现在，大多数的文本分类器是基于机器学习方法的。当前用于文本分类的主 要技术有：概率统计方法，决策树( d e c i s i o nt r e e ，d t ) ，决策规则( d e c i s i o nr u l e ) ， 回归模型( r e g r e s s i o nm o d e l ) ，神经网络( n e u r a ln e t w o r k ，n n ) ，k - 最近邻居 ( k - n e a r e s tn e i g h b o r ，k - n n ) ，支持向量机( s u p p o r tv e c t o rm a c h i n e ，s y m ) 等。其中 s v m ，k - n n 是性能比较优秀的分类器。 2 3 1 贝叶斯网络 贝叶斯分类器是一种典型的基于概率统计分类器。贝叶斯分类器的数学基础 是贝叶斯定理，主要思想就是计算在给定一待分类文档的条件下其属于各个类别 的条件概率，即： 脚沪掣 ( 2 3 ) 然后选择条件概率最高的那个类别为该文档所属的类别。由于在计算过程中 采用不同的方法，贝叶斯分类器有不同的变种，最常用的有简单贝叶斯分类器 ( n a i v eb a y e sc l a s s i f i e r ) 。简单贝叶斯分类器采用简单贝叶斯假设，即假设一个文 档中任何两个单词之间的出现与否是相互独立的。 几种常用的先验分布选取方法： 1 共轭分布族 定义2 3 1 设样本x ，五，以对参数0 的条件分布为p ( x ，x ：，j 0 ) 如果 先验分布密度函数玎( 彩决定的后验密度石( 0 f x ) 与7 r ( o ) 同属于一种类型，则称 4 华中科技大学硕士学位论文 口( 曰) 为p ( x 1 0 ) 的共轭分布。 定义2 3 2 设p = p ( x l 目) ：0 ) 是以目为参数的密度函数族，h = 丌( 臼) 是0 的先验分布族，假设对任何p p 和万h ，得到的后验分布石( 目lz ) 仍然在h 族中，则称h 为p 的共轭分布族。 定义2 3 3 如果随机变i z 的分布密度函数f ( x ) 的核为指数函数，则该分布 属于共轭分布族。 用共轭分布作先验可以将历史上做过的各次试验进行合理综合，也可以为今 后的试验结果分析提供一个合理的前提。相比非共轭分布，共轭分布计算后验只 需要利用先验做乘法，其计算特别简单。可以说共轭分布族为贝叶斯学习的实际 使用铺平了道路。 2 最大熵原则 定义2 3 4 设随机变量x 是离散的，它取a 1a ：，a 。一至多可列个值，且 p ( x = a j ) = 且，i = 1 , 2 ，则h ( x ) = 一p ，i n p 。称为x 的熵。对连续型随机变 l 量x ，它的概率密度函数为p ( x ) ，若积分h ( x ) = 一 p ( x ) i n p ( x ) d x 有意义，称 它为连续型随机变量的熵。 最大熵原则：无信息先验分布应取参数0 的变化范围内熵最大的分布。 可以证明，随机变量的熵为最大的充分必要条件是随机变量为均匀分布。因 此，贝叶斯假设取无信息先验分布是均匀分布是符合信息论的最大熵原则的。 定义2 3 5 设随机变量工只取有限个值a ，d ：，口。，相应的概率记为 1 p ，p 2 ，p 。，则z 的熵日( x ) 最大的充分必要条件是：p l = p 2 = = p 。= 二。 仃 定理本身针对非连续变量做的充分必要条件，实际上对于连续的随机变量也 有同样的结果。因此，在没有任何信息确定先验分布时，采用无信息先验分布是 合理的。 在本系统中采用的简单贝叶斯模型，大大简化了贝叶斯网络的复杂性。关于 华中科技大学硕士学位论文 贝叶斯分类器将在第三章详细介绍。 2 3 2 决策树 决策树文本分类器就是构造一棵分类树来对文本进行分类。在决策树中，内 部节点表示特征，从内部节点引出的分枝表示在这个特征上的测试输出，而每个 叶子节点表示类别。对一个待分类的文本文档d ，从这棵树的根节点开始，测试 这个节点指定的特征，按照文档d ，在该特征上的值对应的树枝向下移动。然后这 个过程在以新节点为根的子树上重复，直到到达一个叶子节点为止，这个叶节点 代表的类别就是该文档所属的类别。 决策树的学习算法采用分而治之的策略，首先查看所有的训练文档是否都属 于同一个类别( 都属于类别c ，或c ，) ，如果不是，选择一个特征 ，将训练文档集 t r 分成两部分，每一部分要么都包含特征五，要么都不包含特征正，然后每一 部分作为一个独立的子树，重复进行这个过程，直到每棵树的叶子节点的所有训 练文档都属于同一个类别为止。 以上的学习过程中主要的问题是如何选择特征作为测试节点。通常的做法是 计算各个特征的信息增益或者熵的值，然后根据这些值的大小顺次选择。用这样 的方法建立的决策树一般都存在对训练数据过分适合( o w r f i t t i n g ) 的问题，所以大 多数的决策树学习算法都包含有一个剪枝过程。 对决策树剪枝有两种方法：前剪枝( p r e p m n i n g ) 和后剪枝( p o s t p m n i n g ) 。前剪 枝在决策树的构造过程中进行，而后剪枝在决策树完全构造好后进行。 2 3 3 神经网络 神经网络( n e u r a ln e t w o r k ，n n ) 文本分类器是一个单元网络，其中输入单元 表示特征，输出单元表示类别，连接单元的边的权重表示依赖关系。对个待分 类文档一，将它的特征和权重输入到输入单元，这些单元通过网络向前传播，最 6 华中科技大学硕士学位论文 后输出单元的值就代表分类的结果。 典型的神经网络的学习方法是用后向传播法。后向传播通过迭代地处理一组 训练样本，将每个样本的网络预测与实际知道的类标号比较，将比较结果反馈到 网络的前层单元中，修改单元之间的权重，使得网络预测和实际类之间的均方误 差最小。 2 3 4 最近邻居 最近邻居法是基于类比学习的一种方法。每个训练文档代表 f l 维空间的一个 点，这样所有的训练文档都存放在l f | 维模式空间中。给定一个待分类文档d ， k 一最近邻居法搜索模式空间，找出最接近待分类文档d ，的k 个训练文档。这k 个 训练文档称为文档d 的“近邻”。“临近性”用欧几里德距离定义，其中两个文档 t = ，畋= 的欧几里德距离是 d i s t ( d ，以) = ：( 叱一九) 2 ( 2 4 ) 文档d 。被分配到k 个最邻近训练文档中占比例最大的类别中。当k = l 时，文 档d 被指定到模式空间中与之最邻近的训练文档所属的类别中。 最近邻居法是一种懒散的学习法，几乎不需要训练时间，但是由于所有的计 算都推迟到分类过程中，所以分类速度比较慢。这种特点决定了其不适于应用到 在线文本分类中。 2 3 5 支持向量机 支持向量机( s u p p o r t v e c t o r m a c h i n e ，s v m ) 最先由j o a c h i m s 应用在文本分类 中，并取得了巨大的成功，可以说支持向量机文本分类器是当前性能最好的文本 分类器。支持向量机的主要思想是针对两类分类问题，在高维空间中寻找一个超 平面作为两类的分割，以保证最小的分类错误率。而且支持向量机的一个重要的 优点是可以处理线性不可分的情况。y a n g 曾经做过实验，发现s v m 处理线性不 华中科技大学硕士学位论文 可分问题比处理线性可分问题差不了多少【”】。i t ! 女hj o a c h i m s 在中所述，s v m 之 所以在文本分类领域表现如此优秀，主要有由于以下两个特点：1 ，s v m 中不需 要进行特征筛选，因为s v m 可以处理高维特征空间而不需要额外的开销；2 ，大 多数文本分类问题是线性可分的，例如在文档集o h s u m e d 中，所有的类别都是线 性可分的，r e m u s 文档集中的大多数类别也是线性可分的”1 。 2 4 分类器评价标准 相对于文本搜索系统来说，文本分类器的性能评价更多的是经验性的，而不 是分析性的。这是因为要分析性地评价一个系统，比如证明一个系统的正确性和 完备性，必须能够对这个系统所要解决的问题给出一个形式化的表述，然而由于 文本分类的主观性( 比如一个文本是否属于某一类别带有很大的主观性，两个不同 的专家可能将其归类到不同的类别中) ，在本质上不能给出一个形式化的表达，所 以要分析性地对分类器进行评价( 比如证明这个分类器是正确的) 是不可能的。 通常对一个文本分类器进行评价主要是针对它的性能( e