（计算机软件与理论专业论文）大规模中文网页的自动分类研究.pdf

摘要 随着信息技术的飞速发展，人们从信息缺乏的时代过渡到信息极为丰富的数字 化时代。在这个数字化的时代里，人们可以获得越来越多的数字化信息包括文本、 数字、图形、图像、声音甚至是视频。这些信息大都是半结构化或者是非结构化的 数据，想从其中迅速有效地获得所需信息是非常困难的事情。为此目的，网页自动 分类被研究者提出并进行了应用研究。研究网页分类具有重要意义，它可以大大缩 短在线文档的整理时间，为信息检索提供方便，有利于实现在线文档的存档管理。 本文的主要工作包括以下几个方面： 1 本文提出了一种网页噪音自动过滤和基于d o m 树解析的网页内容提取方法 “二元匹配法”。该方法根据w e b 页面的特征，从分析其结构的角度入手，去除网 页中的t a g 标签、广告、版权信息，并有效地剔除与网页主题无关的内容，保留网 页正文及相关信息。 2 本文通过分析经典的i 可i d f 公式存在的问题，并结合前人的研究，给出了 “词类权重”的权重计算方法，该方法将三个方面的因素考虑进来，即特征对某个 类的重要性、在类中分布的平均性和对文本集的重要性，从而在衡量词对类别的重 要性中达到平衡，提高了有用特征对于类的重要程度，起到了较好的类别区分作用。 3 本文分析了常用的c 缸觑e 相似度的不足之处，在此基础上，采用如c c 口州 系数的相似度公式，通过考虑文档的重叠程度，将大文档与小文档的重要性区分开 来，使分类器适应网页分类。 经过开放测试，本方法在进行大规模语料训练后可以使相关网页的平均分类准 确率达到8 3 以上，比未使用本方法进行分类的效果有了明显提高，而且计算成本 低，速度快，符合大规模中文网页自动分类的需要。该研究可应用于信息检索、信 息过滤、文本自动分类、网页自动分类等应用领域。 关键词：网页自动分类网页内容提取文本自动分类 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 fi n f o 衄a t i o nt e c h n o l o g y ，t i m eh a sb e e nc h a n g e d 丘o m i n f 0 珊a t i o n1 a c h n gt oe x 伽e m e l ya b u n d a n t n o w a d a y s ，p e o p l ec 孤a t t a i nm o r e 卸dm o r e d i 酏a li n f o n i l a t i o ni 玎c l u d i n gt e x t s ，d a t a ，i m a g e s ，a u d i o s ，v i d e o s ，e t c b u tj t sq u i t e d i f f i c u l tt oa c q u j r ei n f o n l l a t i o nw en c e db e c a u s em o s to ft h e ma r es e m i s t c t 司o r n o n s t n l c t u r e dd a t a f o rt l l i sp u r p o s e ，a u t o m a t i cw e b p a g ed 舔s i 矗c a t i o nh a sb e e np u t f b n a r da dr c s e a r c h e di nt h ef i e l do fa p p l i c a t i o n n so fv i t a li m p o n a n ts i 印i f i c a n c et o s t u d ya u t o m a t i cw e b p a g ec l a 站i f i c a t i o n ，f o ri tc a l lr e d u c et h et i m et od e a ru pt h eo n l i l l e d o c u m e n t s i ta l s oc a nb en v e n i e n tt 0i n f b m l a t j o nr e t r i e v a la n do n l i n e丘l e m a n a g e m e n t r e s c a f c h e si nt h i st h e s i si n d u d e ： 1 t h et h e s i sp r o c e e dw i t ha n a l y z i n gw e b p a g c s s t m c t eb a s e do nt h e i rf e a t u r ea i l d p m p o s eam e t h o dn 锄e dw b b p a g en o i s ef i l t e r i n g ( w n f ) w n fc a ne l i m i n a t eh t m l t a g ，c o p y r i g h ti n f o m a t i o na n dm o s ta l so faw c b p a g e e x p e r i m e n t si nt l l i st l l e s i ss h o wa g o o de f f i c i e n c y 1 nt l l ew a yo fw e b p a g em e m ee x 昀c t i o n ，t h cp a p e ru s ed o mt r e e p a r s i i l ga n dp r o p o s eb i 一黟a mm a t c l l i n gm e t h o d e x p e r j m e n t ss h o w st l l a tt h ee x t r a c t i o m e t h o d sc a ne m c i i v e l ye l 枷n a t ec o n t e t si r r e l a t i v ew j t hw e b p a g e sm e m ea n dr e s e r v e w e b p a g e s t h e m e 壮dr e l a t i v ei f o m a t i o n 2 u s et e m c a t e g o r yw e i 曲t i i l g ( t c w ) m e t h o db ya n a l y z i l l gi n s u f f i c i c n c yo f c l a s s i c a l ) ff b 柚u l a t c mt h i n ko v e r t l l r e ef a c i o 硌：i m p o n a n c eo ff c a t u r ei no n e c a t e g o r y ，f e a t u f ca v e r a g ed i s t r i b u t i o n ，i i l l p o n a i i c eo ff c a t u r ec m s s 山ew h o l es e t t c w i m p r o v ev a l u a b l ef c a t i l r e s 。s i g n i n c a n c ea n dt h ed a s s i f i e r sd i s c r i m i n a t i v ea b i l j t y 3 u s e 妇c c 4 埘c o e 铂c i e n ti n s t e a do fq 靖f ，l ec o e 箭c i e n tb y 孤a l y z i n gt h cl a t t e r ，s i n s u f f i c i e n c y 儿c 衄耐c o e m c i e n te x p r e s s e st h ed e 伊e eo fo v e r l 印p i n gb e m e e nt h e d o c 啪e n ta n dt h ec a t e g o r y e x p e r i m e n t ss h o wt h a t j tc a nh e l pc l a s s i f i e rt oa d a p t w e b p a g e s c l a s s i f i c a t i o n k o p e nt e s t ，t h ea v e r a g ep r e s i c i o nc a l la t t a i n8 3 a f t e rl a r g es c a l et e x tt a i l l i n g i t p r o v e st h a tt h ed a s s i f i e r h a v eh i 庐p r c d s i o n ，1 0 wc o m p u t a t i o n a lc o s ta n d ah i g hr a t e ，a n d a c c o r dt h er e q u i r e m e n t0 fl a 唱es c a l ec h i n e s ew e b p a g e sc l a s s i f i c a t i o n t h er e s e a r c hc a n b e 印p l i e di ni n f 0 肌a t i o nr e t r i e v a l ，i n f o 啪a t i o nf i l t e r i n 岛t e x td a s s i f i c a t i o n ，w c b p a g e d a s s i f i c a t i o n e t c k e y w o r d ：a u t o m a t i cw e b p a g ec l a s s i f i c a t i o n ；w e b p a g et h e m ee x t r a c t i o n ； a u t ot e x tc l a s s i f i c a t i o n i i 硕士学位论文 m a s t e r st h e s l s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：任淫日期：珈年占月f 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名：桂函 日期：加6 年6 月g 日 导师签名： 日期： 年月 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。回意途塞握銮后进卮! 旦圭生i 旦= 生；旦三生筮查! 作者签名：彳王函 日期：撕6 年月牙日 导师签名： 日期：年月日 第一章绪论 1 1 课题研究的目的和意义 随着互联网技术的飞速发展，网络上的信息资源呈指数级增长，i n t e m e t 己经成 为拥有几十亿个页面的分布式信息空间，人们从信息缺乏的时代过渡到信息极为丰 富的数字化时代。在这个数字化的时代里，人们可以获得越来越多的数字化信息包 括文本、数字、图形、图像、声音甚至是视频。这些信息大都是半结构化或者是非 结构化的数据，想从其中迅速有效地获得所需信息是非常困难的事情。同时，快速 而有效的w 曲文本检索也是充分发挥w 曲在数字化图书馆、电子商务、远程教学 等众多方面应用的一个基础前提。在这种情况下，如何缩短在线文档的整理时间， 对在线文档进行有效的存档管理，也就成为一项重要而迫切的研究课题，而网页的 自动分类正是其中的一个核心问题。 网页自动分类也称为在线文档分类( o n l i n cd o c 啪e m sc a t e g o r i z a t i o n ) ，通过分 析被分类网页的特征，并与各类别中网页所具有的共同特征进行比较，将被分类网 页化归为特征最接近的一类并赋予相应类别。传统上，网页分类是由人来完成的， 即人在分析了网页的内容后，给它一个比较合适的类别。如m o o ! 、n o r t h c m i j g h t 、 a 1 t a v i s t a 等搜索引擎为了方便用户对信息的查找和提高搜索速度，由专业人员手工 对网页进行分类，很明显，这需要大量的人力资源。随着网页信息的快速增长，特 别是i n t c r n e t 上各种信息的迅速增加，仅靠人工的方式来处理是不切实际的。同时， 由于分类可以在较大程度上解决目前网上信息杂乱的现象，并方便用户准确地定位 所需信息，因此，网页自动分类已成为一项具有较大实用价值的方法，是组织和管 理数据的有力手段。 就目前的研究来看，网页自动分类的准确率还不高，但网页自动分类的研究对 基于内容的信息检索、w 曲挖掘以及各种基于w 曲的应用有着深远的意义。本文将 主要针对基于统计方法的中文网页自动分类进行研究。 1 2 课题研究的背景与发展现状 网页分类是在文本分类的基础上发展起来的。从方法上来讲，首先需要进行网 页内容的提取，然后再对提取内容进行分类。 1 2 1 文本自动分类的研究现状 文本自动分类研究始于5 0 年代末，h p ：h h n 在这一领域进行了开创性的研究。 1 9 6 0 年，m a r o n 在j a c m 上发表了有关自动分类的第一篇题为“0 nr c l e v a c e p m b a b i l i s t i ci n d e x i n ga l l di n f o 姗a l i 0 r c t r i e v a l ”的论文，随后许多著名的情报学家， 如k s 口a r c h 、g s a l t o n 以及r m n e e d h 锄等都在这一领域进行了卓有成效的研究。 到目前为止，自动分类在国外经历了三个发展阶段：第一阶段( 1 9 5 8 1 9 6 4 ) 主要 进行自动分类的可行性研究，第二阶段( 1 9 6 5 1 9 7 4 ) 进行自动分类的实验研究， 第三阶段( 1 9 7 5 至今) 进入实用化阶段。 文本自动分类的方法分为两大类：一是基于规则的分类方法：二是基于统计的 分类方法。基于规则的分类方法多应用于某一具体领域，需要该领域的知识和规则 库作为支撑。但是，对知识和规则的制定、更新、维护以及自我学习等方面存在种 种问题，使得应用面比较窄。基于统计的方法采用纯粹的数学运算，不苛求复杂的 语言学知识和领域知识，同时具有较高的准确率，因而日益受到人们的重视。 文本自动分类的统计模型主要有向量空间模型、概率模型、线性模型、非线性 模型以及组合模型等。 在向量空间模型中，种方法是计算文本与代表某文本类别的中心向量之间 的相似度，如r o c c h i o 公式1 8 ，哪。另一种方法不需要建立描述文本类别的中心向量， 而是依赖于测试文本与训练文本之间的相似度，如k 近邻算法 1 0 “】。 概率模型中典型的算法是朴素贝叶斯算法【1 1 1 3 1 ，以及对朴素贝叶斯算法的改 进，如增强型朴素贝叶斯算法【1 4 】、基于潜在语义索引的贝叶斯方法1 1 5 1 、贝叶斯层次 分类1 1 6 l 。 线性模型有线性最小二乘拟合方法( u s d 【1 7 】和支持向量机( s v m ) f 1 19 1 。非线性 模型可以分为层次模型和网络模型，如决策树【2 0 】，以及在决策树思想的指导下的其 他很多知名的算法，如i d 3 【2 1 】等。网络模型的代表是神经网络m e u r a ln c t 、j l ，o r k ) 【2 3 ，2 4 1 。 组合模型陋，2 6 】的思想是选取k 个不同的分类算法，综合这k 个算法分类的结果 进行整体的分析和判断。目前通用的决策方法有多数表决( m a j o r i t yv o t j n 舀m v ) 【2 2 1 、 权值线性组合( w e i 曲t e du n e a rc o m b i n a t i o n ，w 1c ) 1 2 ”、动态分类器选择( d y n a m i c c l a s s i f i e rs e l e c t i o n ，d c s ) 1 ”、适应性分类器组合( a d a p t i v ea a s s i f i c rc o m b i n a t i o n ， a c c 、1 2 2 】。 我国的文本自动分类工作始于8 0 年代初期，大体上经历了从可行性探讨 2 辅助分类系统自动分类系统三个发展阶段。1 9 8 1 年，侯汉清先生首先对自动分 类进行探讨。早期的系统主要特点是结合主题词表进行分析分类，人工干预的成分 很大，如南京大学开发的系统1 3 9 】，分类准确率在8 0 左右，上海交通大学开发的系 统【4 2 】，准确率为8 9 ；此后，基于统计学的思想，以及分词、语料库等技术被不断 应用到分类中，如文献f 4 0 ，4 1 】。 随着技术的不断发展、成熟，研究者们又不断地改进文本的分类方法和算法， 文献【4 7 】中作者使用n g f 狮作为特征，不进行分词达到9 0 以上的准确率；文献 【4 3 】中则提出基于核的距离加权k n n 算法，达到8 6 3 8 的准确率；文献【4 4 】则将规 则与统计相结合进行分类研究，达到8 0 的准确率和7 5 8 的召回率；文献【4 5 】则 是利用向量空间模型进行层次分类，准确率达到9 0 以上；在文献【4 6 】中提出了将 规则作为自动分类的补充，针对不同的情况，采用不同的分类器进行分类，准确率 也达到9 0 左右：还有神经网络在分类中的应用等等。这些都是近年研究的新发展， 并且都取得了很不错的分类效果。 1 2 2 网页自动分类的研究现状 网页的自动分类研究自上世纪8 0 年代互联网兴起以后才逐渐发展。由于文本 自动分类的研究相对较早，而且拥有比较成熟的技术，因此有不少研究工作试图使 用纯文本分类技术实现网页分类。这些研究主要分两种思路，一是用表示纯文本的 方式表示网页，二是组合文本分类器的方法。f u r n b a r i z 【3 0 j 用指向该网页所有链接周 围的文本、链接所在段落的标题以及上级标题文本表示网页，并用r i p p e r 算法对文 本进行分类，准确率比使用网页局部文本提高了2 0 ；c h a k r a b a n i 【3 l 】和g h a l l i 3 2 】尝 试用网页的局部文本和跟它链接网页的文本表示网页，分类结果还没有只使用网页 局部文本好；d h l 3 3 j 等人也结合网页局部文本和链接网页的文本表示网页，但没有引 入所有链接网页的文本，而是基于文本相似性选择了部分跟原网页较接近的网页文 本，试验结果f 1 值比使用所有链接网页提高了7 。但这些工作并没有得到公认的 结论。y 抽9 1 2 9 】等人通过在h o o v e r s 和w 曲k b 数据集上的研究给出了比较客观的解 释：网页是否集中地存在某种规律以及能否利用这些规律，对网页分类算法的性能 影响较大，因此应该根据这些规律设计网页的表示方式和网页分类算法。 c h o o n l 3 4 j 用组合网页分类器的方法进行网页分类，其中一个分类器用网页中的 纯文本、标题和子标题文本表示网页，另一个分类器用指向该网页所有链接周围的 文本表示网页；国内的范焱【惦j 等人提出一种用朴素贝叶斯协调分类器综合网页纯文本 和其它结构信息的分类方法。试验结果证明组合后的分类器性能都有一定程度的提高。 1 3 课题研究的难点及突出问题 网页分类是在文本分类技术上发展起来的，但网页分类问题相对文本分类更加 难处理，要考虑更多因素，这一特点主要是由网页特征决定的。网页分类面临的突 出问题主要有以下几个方面： 1 网页格式多样化：多种格式并存，而且同一格式的网页也存在多个标准， 同时由于网页的写作风格及内容变化都很大，因此如何解析不同格式、不同风格的 网页成为网页预处理的一个难点； 2 分类主题的模糊：互联网的知识系统发展异常迅猛，各种新的知识结构不 断涌现，如果训练语料库得不到及时更新，就会导致网页无法分类； 3 网页去噪：网页中存在大量与页面主题无关的噪音信息，如何提高去噪算 法的性能是有待研究的问题； 4 网页结构信息：网页含有丰富的结构信息，除纯文本以外，还有其它一些 内容对分类有贡献【捌。如 m 和t i e 标注网页的标题和段落予标题，m e t a 标记中的 n a m e 属性值和c o n t e n t 属性值是对网页主题的描述，网页中的超链接指向的内容有 可能是与该网页主题相关的内容，这些信息都对网页分类有贡献，也可能存在噪声， 综合利用上述特征设计分类算法是网页分类的关键，也是难点所在； 5 缺乏评价标准：对于网页分类系统，目前没有统一的评价标准，常用的评 价指标有准确率和召回率。网页数量极其巨大，单纯的召回率已经没有实际价值， 准确率的意义也要作相应的变通：数据库规模，索引方法，用户界面，响应时间应 该纳入评价体系，作为评价指标。 此外，文本分类中存在的一些问题，如特征选择、分类器效率等问题同样会给 网页分类带来影响。如何有效地减少以上突出问题的影响，从网页中提取出有用信 息，同时降低分类过程中不利因素的影响，就是本文将要讨论的问题。 1 4 本文工作及内容安排 在已有的网页分类的研究中，多数是基于单个网页的分类系统，由于网页格式 的多样化，因此无法有效地提取到全部有用信息。本文提出利用网站拓扑结构来进 行网页噪音过滤，取得了不错的效果。在分类阶段，文中使用基于改进的“词一类权 重”的特征权重计算方法，有效提高了有用词对类别的贡献，降低了网页中噪音词 的影响。此外，本文还对分类器的设计和相关机器学习问题做了进一步的理论研究 4 和实验分析。 本文的结构安排如下： 第一章绪论，主要介绍网页分类的研究现状及存在的问题。 第二章文本分类的基础理论及相关技术，主要介绍目前与文本分类相关的理论 及方法。 第三章中文网页内容的自动提取，主要介绍我们提出的网页主题内容提取的相 关方法。 第四章网页自动分类系统的构造，主要介绍我们设计并实现的分类系统的关键 技术。 第五章实验设置与结果分析，主要介绍文本的实验过程与实验结果。 第六章结论与展望，对全文工作进行了总结，并提出下步的工作展望。 5 第二章文本分类的基础理论及相关技术 网页分类中，比较核心的仍然是文本自动分类技术。文本自动分类的研究涵盖 若干学科领域，包括语言学中的自然语言处理，图书情报学中的分类学，数学领域 的统计学等，以及计算机领域的模式识别、人工智能、神经网络等研究方向。本章 将分别介绍文本分类的基本概念、文本自动分类系统的基础理论和相关技术，以及 文本分类的评价体系。 2 1 文本分类的基本概念及特点 2 1 1 文本分类的基本概念 文本分类是指按照预先定义的分类体系，根据文本的内容自动地将文本集合的 每个文本归入某个类别，系统的输入是需要进行分类处理的大量文本，而系统的输 出是已标好类的文本集。简单地说，文本分类就是对文本标以合适的类标签。 从数据挖掘的角度来说，自动分类是一个有指导学习( s u p e i s e dk a r n i n g ) 的 过程。在这个学习过程中，它根据一个已经被人工处理过的训练文本集合( t r a i n i n g s e t ) 去挖掘出文本属性和文本类别之间的关系模型，然后根据学习得到的这种关系 模型对新到来的文本测试集合( t c s ts e t ) 进行自动的类别判断。文献3 5 给出了文 本分类的形式化定义： 文本分类就是将一个二元组( 西，日) d c 映射到一个布尔值的任务。该映射用 数学公式表示如下： 中：d c + r ，f ，其中d 一( d l ，d 2 ，巩) ，c = ( c 1 ，c 2 ，c k ) 这里d 为待分类的文本集合，c 为给定分类体系下所有预先定义的类别的集 合，d 可以是无限集合，而c 必须是有限集合。如果将二元组( 击，o ) 映射为值t ( t 九】e ) ，则认为文本画属于类别g ，否则认为文本击不属于类别c ! f 。 文本分类的关键就是要找到一个函数巾：d c 一 丁，f ，使得通过该函数能够 将任意一个文本尽可能准确地分类。这里m 是根据已掌握的每类若干样本的信息， 总结出分类的规律而建立的判别公式和判别规则。根据系统使用的学习方法的不 同，这些判别公式和判别规则也有所不同。在已经确定的映射规则的基础上，系统 在遇到新文本时，通过计算和判断，最终确定文本相关的类别。因而，从数学角度 看，可以说文本分类就是一个映射过程，它将未标明类别的文本映射到分类体系下 已有的类别中。 2 1 2 文本分类的特点 文本分类实际上是一个模式分类任务，所以许多模式分类的算法可以应用到文 本分类中。但是，文本分类同时又是模式分类和自然语言处理的一个交叉学科，是 和文本的语义紧密相关的，所以与普通的模式分类任务相比有许多独特之处。 1 高维特征空间 在文本特征提取的时候，存在大量的候选特征。如果使用词语作为文本特征， 即使一个1 0 0 0 篇左右的训练文本集，一般也会产生上万的候选特征。如果使用 n - g r 锄项作为特征，会产生更多的候选特征。 2 特征语义相关 一种避免特征维数过大的解决方法是，假设大部分特征之间是相互独立的，使 用特征选择方法选取那些彼此无关的特征。但是，文本分类中很少特征之间是彼此 无关的。很多特征与上下文之间存在较强的关联性。 3 特征存在多义和同义现象 文本分类中一般使用词、短语和n g r a m 等作为表征语义的文本特征。但是， 这些特征往往无法清晰地表达一种含义。一个特征可能有多种含义，即多义现象。 如：“教授”既可以表示一种职称的含义，也可以代表一种传授知识的含义。同时， 许多相同的含义又可以用不同的特征来掐述，即同义现象。如：“计算机”和“电 脑”这两个特征都表示相同的含义。 4 特征分布稀疏 根据z i p f 法则，如果能够统计一种语言中所有的词在一个大型语料库中的出现 次数，并且按它们出现次数的大小顺序把这些词排列起来，会发现个词出现的频 率厂和它的排列位置之间的关系。设它的排列位置为r ，那么z i p f 法则可以表示成： ，菇三 ， 这意味着排列在第5 0 位的词的出现次数大约是排在第1 5 0 位的词的出现次数 的3 倍。文本特征空间的维数是非常高的，而能够作为文本特征的往往是那些在语 料库中出现频度适中的词。对于一篇不是很长的文本来说，特征空问中多数特征词 的出现频率都为o ，导致文本向量中多数特征值都为o ，特征的分布非常稀疏。 2 2 文本表示模型 在大规模文本分类系统中，首要任务就是将非结构化的自语语言文本转化为结 构化的计算机可识别的信息，即对文本进行形式化处理。这一形式化的结果称为文 本表示。在文本分类领域，文本表示涉及以下两个问题： 一是如何确定表示文本的基本单位。用于表示文本的基本单位通常称为文本的 特征或特征项。文本表示就是要用一定的特征项构成特征向量来代表文本信息，最 终通过这些特征向量来评价未知文本与类的相关程度。在不同内容的文本中，各特 征项出现频率有一定的规律性，不同的特征项就可以区分不同内容的文本。 上节已经讨论过，中文的文本特征通常可以选用字、词、短语以及句子等高层 次的单位。在实际应用中，到底选择哪种单位作为文本的特征必须要综合考虑，如 处理速度、精度要求、存储空间等诸多因素。选择的单位越具有代表性，语言层次 越高，它所包含的信息也就越丰富，但同时进行分析所付出的代价也就越大。大量 的研究表明，单个的词作为特征与用其它复杂的表示( 如短语) 作为特征分类的效 果差异不大。但是，用短语表示特征必然会导致计算更加复杂以及耗费更多的资源， 因此大部分文本分类的研究中都是将单个的词作为特征。 文本表示的另一个问题是采用什么方法建立模型。文本表示模型是文本自动分 类的一个重要技术问题。文本表示所采用的模型有很多种，目前通常采用的有布尔 模型、概率模型和向量空间模型。 2 2 1 布尔模型( b o o l e a nm o d e l ) 布尔模型就是采用布尔表达式对文本进行表示。布尔模型在传统的信息检索中 有广泛的应用，它通过与用户给出的检索式进行逻辑比较来检索文本，是一种基于 关键词的匹配。在标准的布尔模型中，文本采用如下的表达形式： 面墨( w f l ，w f 2 ，w * ，w h ) ，七一1 ，2 ，” 其中n 为特征项的个数，w * 为o 或1 ，表示第k 个特征项在文本j 中是否出现。 布尔模型易于实现，但在文本分类领域，它的准确率和召回率较差。 8 硕士学位论文 m a s t e r st h e s l s 2 2 2 概率模型( 胁b a b j i i s t i cm o d e i ) 概率模型考虑词与词的相关性，把文本集中的文本分为相关文本和无关文本。 以数学理论中的概率论为原理，通过赋予特征词某种概率值来表示这些词在相关文 本和无关文本之间出现的概率，然后计算文本问相关的概率，系统据此概率作出决策。 概率模型有多种形式，常见的一种是贝叶斯概率模型。贝叶斯概率模型是用概 率架构来表示特征项，将训练实例分解为特征向量和决策类别变量；该模型假定特 征向量的各分量问相对于决策变量是相对独立的，也就是说各分量独立地作用于决 策变量。尽管这个假定在一定程度上限制了贝叶斯模型的适用范围，然而在实际应 用中，以指数级降低了贝叶斯网络构建的复杂性。在很多领域即使违背这种假定的 条件下，贝叶斯概率模型也表现出相当的健壮性和高效性，已经成功地应用到分类、 聚类中。 2 2 3 向量空问模型( v e c t o rs p a c em o d d ，v s m ) 向量空间模型是由g c r a r ds a l t o n 和m c g i l l 于1 9 6 9 年提出。因其概念简单，在 信息检索( i n f o n n a t j o nr e t r i e v a l ，简称1 r ) 中得到广泛应用。在文本自动分类中使 用这种方法主要是从l r 中引进过来的。向量空间模型的基本思想是：将每个词条 作为特征空间坐标系的一维，将文本看作特征空间的一个向量，用两个向量之间的 夹角来衡量两个文本之间的相似度。在向量空间模型中，每一个文本都被表示为由 一组规范化正交词条向量所张成的向量空间的一个点，即形式化为n 维空间中的 向量，因此我们可以将文本抽象为： y ( 西) ；( ( f - ，w - ，) ，q ，q ) ，( 厶， v ) ) ，f ，1 ，” 其中是特征项i ，岫是在文本西中的权重。对于一个训练文本集合，我们 就可以得到如图2 1 所示的一个向量空间w 。 图2 1 向量空间模型下的文本表示 9 w 通常是一个稀疏矩阵。训练文本和待分类文本在向量空间模型中都可用相同 的方法表示出来。待分类文本的向量越接近训练文本向量，说明其与训练空间中的 文本的相似度越大，越有可能和训练文本属于同一个类别。在计算时，相似度通常 用向量之间的夹角的余弦值来度量，训练文本类别向量与待分类文本向量的余弦值 越大则越相似，越小则越不相似。 向量空间模型是目前广泛使用的文本表示模型，具有如下优点： 文本内容被形式化到多维空间中的一个点，通过向量形式给出，将文本以向 量的形式定义到了实数域中，提高了自然语言文本的可计算性和可操作性； 为词引进权值，通过调节词对应权值的大小来反映词与所在文本的相关程 度，克服了传统布尔模型的缺陷： 通过计算文本之问的相似度，使属性相似的文本尽量聚拢在一起，以提高匹 配效率； 但该模型也存在一些缺点，主要表现为：向量空间的维数往往很高，导致计算 量大，影响系统速度。此外，向量中特征的权值的确定也是较难考量的一个部分。 2 3 文本特征选择 由于文本数据无结构化的特点，使用特征向量对文本进行表示的时候，向量维 数通常会达到几万甚至几十万。即使经过一些预处理( 如去停用词) ，仍然无法显 著地降低特征向量的维数。高维会导致机器学习的时间的大大增加，而学习效果却 可能并不比小得多的特征子集的效果更好。因此文本分类系统应该尽可能地选择少 而精的特征，尤其是和文本类别密切相关的特征进行分类。因此，寻求一种有效的 特征选择方法，降低特征空间的维数，提高分类的效率和精度，成为文本自动分类 中至关重要的问题。 特征选择目的主要是排除给定特征空问中被认为无关的或是关联性不大的特 性，即尽量保留重要程度较高的特征，剔除无用特征。目前特征选取一般是通过构 造一个特征评估函数，把原始空间的数据投影到特征空间，得到在特征空间的值， 然后根据特征空间中的值对每个特征进行评估，并对所有的特征按照其分数的大小 进行排序，选取预定数目的最佳特征作为结果的特征子集。 文本分类的特征选取中常见的评估函数有：文档频率、信息增益、f 统计法 ( c h i ) 、互信息等等。这些方法的基本思想都是基于阈值的统计方法，即对每一个 特征( 中文词或词组) ，计算某种统计值，然后设定一个阈值t ，把值小于t 的那些 l o 硕士学位论文 m a s t e r st h e s i s 特征过滤掉，剩下的即认为是有效特征。 2 3 1 文档频率( d o c u m e n tf 聘q u 蛐c y ) 文档频率是指训练集合中出现某特征项的文档数。其主要思想是：在训练文本 集中对每个特征计算它出现的文档次数，若该项的d f 值小于某个阈值则将其剔除， 若其d f 值大于某个阈值也将其去掉，因为d f 值太低则说明该特征缺乏代表性， d f 值太高则说明缺乏区分度。基于文档频率的特征选择是最筒单的特征选取手段。 它通过计算线性近似复杂度来衡量巨大的文档集，被认为是一个提高效率的有效方 法。但该方法也存在着缺点，即对于某些特征，可能在某一类文本中大量存在，但 却包含着关于类别的重要判断信息。 2 3 2 信息增益( i n f o 珊a t i o ng a i n ) 信息增益表示文本中包含某一特征值时文本类的平均信息量。它定义为某一特 征在文本中出现前后的信息熵之差，即该特征为该类别提供的信息量的大小。一般 方法是，根据训练数据，计算出各特征项的信息增益，按照信息增益的大小排序。 信息增益评估函数定义如下： 佑( f ) 一砌们砂岱) 一叵挚8 c 矧勘f 唧y 一 一：i ：，p ( c f ) l o g p ( c f ) 卜 ( 2 - 1 ) 【j p o ) 一：。p ( c fi f ) l o g p ( c ji f ) + p ( _ ) 一：= l p ( qi f ) l o g p l f ) 】 公式中，t 表示特征项，p o ) 表示t 发生的频率，p ( g ) 表示第i 类发生的概率 值，p ( o l f ) 表示文本中出现t 时，文本属于。的概率。 从信息论角度出发，信息增益方法的本质是用各个特征值来划分训练样本空 间，根据所获信息增益的多少来选择相应的特征。不足之处在于，它考虑了词未出 现的情况。虽然某个词不出现可能对判断文本类别也有贡献，但实验证明，这种贡 献往往小于考虑词不出现情况所带来的干扰，因为一篇文本仅能包含特征空间中的 很少一部分特征，此时信息增益大的特征主要是信息增益公式中后一部分( 代表单 词不出现情况) 大，而非前一部分( 代表单词出现情况) 大，信息增益的效果就会 大大降低了。 1 l 2 3 3 互信息( m u t i i a li f d m a t i o n ) 互信息是一种广泛用于建立特征项关联统计模型的标准，它体现了特征项与类 别的相关程度。对于特征项t 和某一类别o ，在g 中出现的概率高，而在其它类别 中出现的概率低的特征t 将获得较高的互信息，也就有可能被选取为类别c f 的特征。 t 和。的互信息定义为： 埘( f ，c f ) _ 1 0 8 面苌：* 两 ( 2 - 2 ) l + l t 以+ 直， 其中，a 表示包含词t 且属于类别。的文档数，b 表示包含t 但不属于c l 的文 档数，c 表示属于d 但不包含t 的文档数，n 表示语料中文档总数。 互信息的一个好处是，既能反映类与特征之间的关系( 相对于d f ) ，计算又不 至于太复杂( 相对于c h i 和i g ) 。缺点是没有考虑特征发生的频率，这造成了互信 息评估函数经常倾向于选择稀有单词，从而淘汰了很多高频的有用词条。 2 3 4 # 统计法 # 统计法用于度量特征和类别之间独立性的缺乏程度，它同时考虑了特征存在 与不存在的情况。f 越大，独立性越小，相关性越大：反之独立性越大，相关性越 小。 f 统计量表示为： z 2 阶两者罱篙而 ( 2 s ) 其中，a 为t 和c 同时出现的次数，b 为t 出现而c 没有出现的次数，c 为c 出 现而t 没有出现的次数，d 为t 和c 都没有出现的次数，n 为训练集中所有实例文 本数。 矛统计量可以用来度量类c 和特征t 的关联性，使得它在特征削减中十分有用。 对每一对c 和t 都计算x 2 ( t ，c ) 的值，并按照降序排列，去除排在后面的特征。铲统 计量与互信息的差别在于它是归一化的统计量，但是它对低频特征项的区分效果也 不好。 1 2 2 4 文本分类算法 研究文本自动分类的关键问题是如何构造分类器，分类器需要通过某种算法进 行学习获得。文本分类的算法大多来自于模式分类，基本上可以分为三大类：一类 是基于统计的方法，如中心向量法、朴素贝叶斯( n a v eb a v e s ) 、k 近邻( 心) 、 回归模型、支持向量机( s v m ) 、最大熵模型等方法；另一种是基于连接的方法， 如人工神经网络；还有一种是基于规则的方法，如决策树、关联规则等。这些方法 的主要区别在于规则获取的方式。 2 4 1 中心向量法 中心向量算法比较简单，它利用向量空间模型，对各个训练类别分别计算平均 向量，进行标准化处理，再计算相似度。 对于类别q ，其中心向量玩一 ，其中： w m - yw 口，f 一1 ，m ，= 1 ，l 危色 w “表示特征i 在文本j 中的权重，m 为特征数，n 为类别q 中的文本数。 2 4 2 朴素贝叶斯( n a v eb a y 髂) 方法 朴素贝叶斯方法是一种在已知先验概率与条件概率的情况下得到后验概率的 模式识别方法，这种方法可以确定一个给定样本属于一个特定类的概率。朴素素叶 斯方法基于一个前提，即在给定的文本类语境下，文本属性是相互独立的。 设d 为一任意文本，它属于文档类c = c ，c ：，g ) 中的某一类g 。根据朴素 贝叶斯分类法，有： p ( 叫) = 警 ( 2 - 4 ) p “) 一p ( g ) 尸以i c )( 2 - 5 ) 上式表示在给定文档d 的条件下，d 属于类别g 的概率( 即后验概率) 。所以 分类的问题就转化为计算p ( d l d ) 的值，使p ( g l d ) 取得最大值的那个类别就是d 所属的类别。对所有类别来说，p ( d ) 总是相同的，则分类问题就成为求c j ，使得 p ( c ) i d ) - 去 以c f i d ) 2 4 3k n n ( k n e a r e s tn e i 咖b 盯) 方法 ( 2 - 6 ) k n n 方法是一种基于实例的文本分类方法。首先，对于一个测试文本，计算 它与训练样本集中每个文本的相似度，找出k 个最相似的训练文本。然后在此基础 上给每一个文本类打分，分值是k 个训练文档中属于该类的文本与测试文本之间的 文档相似度之和，然后按分值进行排序。同时选定一个阙值，分数超过阈值的类才 予以考虑。形式化表示为： ，q ，g ) t 罗砌矩 ，西) y ，) 一挑 ( 2 7 ) 其中， y ，一优主兰 加为阈值，跏“，西) 为文本d 和西的相似度，似，o ) 为文本d 属于类d 的分 值。 k n n 的实质就是以特征权重作为特征空间的坐标系测度。圈州方法是目前精 度较好的分类器之一，不过它没有考虑特征属性关联及共现等因素对文本相似度的 影响，如果加以适当地考虑，州的效果会更好。 2 - 4 4 支持向量机( s l l p p o r tv e c t o rm a c h i 耻) 支持向量机是在统计学习理论的基础上发展起来的一种机器学习方法，它基于 结构风险最小化原理，将原始数据集合压缩到支持向量集合，学习得到分类决策函 数。其基本思想是：根据结构风险最小化的原理，对一个给定的具有有限数量训练 样本的学习任务，如何在高维空间中寻找一个超平面作为两类的分割，以保证最小 的错误率。支持向量机在解决小样本、非线性及高维模式识别问题上表现出许多特 有的优势，并在很多领域得到成功的应用。在文本分类方面s v m 的表现也不错， 其分类的准确率和召回率超过了现有的大部分方法。 s v m 使用公式： 1 4 硕士学位论文 m a s t e r st h e s i s s ) ；脚( d ) + 6 一口弘( d ，盔) + 6 ( 2 8 ) 将向量d 分成1 ( s s o ) 或一1 。其中： 西，f 。1 ，是训练集向量； 弘f - 1 ，是相对应的类； k 似，d i ) 是核心，是用来表示d 度数的多项式： 置似，击) 一 7 击+ 1 ) ( 2 9 ) 若数据是线性可分的，s v m 为距离最小的两个类构造一个超平面 舻似) + 6 - o