（计算机软件与理论专业论文）基于向量空间模型的中文网页自动分类技术研究.pdf

摘要 信息技术的发展和互联网资源的迅速膨胀对传统的搜索引擎提出了挑战。在提高搜 索引擎对信息的检索效率和用户操作的方便性方面，中文网页自动分类技术是一个有效 的解决方案，是中文信息处理中的重要环节。它能够自动地把搜索引擎检索到的结果归 类，便于用户按类别进行查找，提高检索信息的效率，已成为信息检索方向的研究热点。 介绍了网页分类的原理、流程和分类的各项关键技术。阐述了网页预处理、向量空 间模型的原理、特征选取技术、流行的分类算法和分类的评价指标，对这几种分类算法 的分析表明k n n 算法是最适合应用于网页分类的分类算法。概括了网页分类在搜索引 擎中的重要作用。深入研究了k n n 算法，分析了国9 杉 t - 主要的改进算法，发现k n n 在大规模在线分类方面存在着效率上的缺陷。从修剪训练集合的角度出发，提出了一种 生成代表样本集合的算法，并在中文网页分类器c p c k 上进行验证。实验证明，与普通 的k n n 分类算法相比，代表样本算法的分类效率得到了一定程度的提高。从网页的布 局和功能进行分析，发现在网页的分块信息中，相关链接与网页的主题存在着一定关联。 在研究网页分块算法的基础上，充分利用网页中的结构化信息和链接资源，提出了利用 分块算法提取主题相关链接块，并对相关链接的锚文本进行加权的权值修正方法。设计 并实现了一个中文网页分类器c p c k ，实现了对网页的自动处理、特征抽取和分类，并 将提出的改进算法应用到分类器中进行验证。 关键词：网页自动分类，向量空问模型，主题相关链接，k n n 算法，代表样本 r e s e a r c ho fc h i n e s ep a g ea u t o m a t i cc l a s s i f i c a t i o n b a s e do nv e c t o rs p a c em o d e l f e n gj i n g ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db yp r o f l ic u n h e a b s t r a c t w i t ht h eb l o o m i n go ft h ei n t e m e ti n f o r m a t i o n ，i ti sn e c e s s a r yf o ri n f o r m a t i o nr e t r i e v a l t e c h n o l o g yt ob ei m p r o v e d p a g ea u t o m a t i cc l a s s i f i c a t i o ni sa u s e f u lt o o lt oi m p r o v et h e p e r f o r m a n c eo fs e a r c he n g i n e i ti sak e yp r o c e d u r eo f t h ec h i n e s ei n f o r m a t i o np r o c e s s p a g e c l a s s i f i c a t i o nc a na u t o m a t i c a l l yc l a s s i f yw e b p a g e st oc e r t a i nt o p i c st os h o wu s e r sal e g i b l e t o p i cl i s ta n dm a k eu s e rf i n dw h a tt h e yw a n tm u c he a s i l y t h er e s e a r c ho fp a g ec l a s s i f i c a t i o n h a sb e c o m eah o t s p o ti ni n f o r m a t i o nr e t r i e v a lf i e l d f i r s ti n t r o d u c et h ep r i n c i p l e ，p r o c e d u r ea n dr e l a t i v et e c h n o l o g yo fp a g ec l a s s i f i c a t i o n ， i n c l u d i n gp a g ep r e p r o c e s s ，v e c t o rs p a c em o d e la n df e a t u r ee x t r a c t i o n t h e nd i s c u s s es e v e r a l p o p u l a rt e x tc l a s s i f i c a t i o na l g o r i t h m sa n dt h e i rm e t e w a n d a tl a s ts u m m a r i z ep a g e c l a s s i f i c a t i o n sa d v a n t a g et os e a r c he n g i n e b yc o m p a r i n gt h e s ea l g o r i t h m s ，f i n dt h a tk n ni s t h em o s tf a v o r a b l eo n ef o rw e bp a g ec l a s s i f i c a t i o na n di st h ek e y s t o n et or e s e a r c hf o ro u r w o r k r e s e a r c hk n n ( k - n e a r e s tn e i g h b o r s ) a l g o r i t h md e e p l y ，a n a l y z et h ed e f e c t so ft h e k n n ，a n dp r o p o s ea ni m p r o v e m e n tm e t h o d - r e p r e h e n s i v es a m p l ea l g o r i t h mt om a k ek n n m o r ee f f i c i e n c y t h i si m p r o v e m e n ti se x p e r i m e n t e do nt h ec h i n e s ep a g ec l a s s i f i e rk n n t o b ev a l i d a t e d a n a l y z et h el a y o u ta n ds t r u c t u r eo fp a g e sa n df i n dt h a tr e l a t i v el i n k sa l e a s s o c i a t e dw i t ht o p i ct oc e r t a i nd e g r e e o nt h eb a s i so ft h ep a g eb l o c k ，p r o p o s eam o d i f y w e i g h tm e t h o d ：a d d i n gw e i g h to ft h er e l a t i v el i n k sm e t h o du s i n gp a g es t r u c t u r ea n dl i n k s i n f o r m a t i o n d e s i g nac h i n e s ep a g ec l a s s i f i e ro fk n n ( c p c k ) a n di m p l e m e n t i tt ov a l i d a t e t h e s ei m p r o v e m e n ta l g o r i t h m s k e yw o r d ：p a g ec l a s s i f i c 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 es e l e c t i o n ，k n na l g o r i t h m ， r e p r e s e n t a t i v es a m p l e s 关于学位论的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均己在论文中做出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 同期：夕口略年乡月彩同 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：盈 彗 指导教师签名：主垒熔 r 期：如孵年乡月彳同 r 期：伽舛r 月“同 中围“油人学( 华东) 顾i ：学位论义 1 1 课题的研究背景及意义 第一章绪论 进入2 l 世纪以来，信息技术同新月异，每年网页的数量都在翻倍的增长。海量的 i n t e m e t 网络资源使得搜索引擎成为了w e b 信息检索的重要平台，成为人们获取知识的 有力途径。据2 0 0 7 年互联网统计报告指出，搜索引擎已成为目商妒用户年到达率最高的 互联网服务。然而用户在使用搜索引擎时也发现，已有的检索机制通常是对检索关键字 和网页文本内容的简单匹配，因此返回的结果集合通常非常庞大，且杂乱无章，大部分 是与用户需求不相关的信息，导致用户无法快速而准确的定位所需要的信息，是制约检 索效率提高的瓶颈问题，人们迫切需要更加智能化、简单化、便于准确定位的检索工具。 如果在输入查询关键词后，搜索引擎返回给用户的是按主题和类别呈现的相关网页，用 户便能够快速准确的定位到感兴趣的类别及其网页中，这无疑是解决检索效率不高的有 效方案。因此，网页自动分类已成为近年来信息检索领域的研究热点之一。 网页自动分类，以信息检索和文本挖掘领域中的文本自动分类文本( t e x t c a t e g o r i z a t i o n ，简称t c ) 技术为基础，将文本分类技术应用到搜索引擎中，以类别目录 的方式来显示检索结果【l l 。该技术能够大大减少浏览网页的数量，提高检索效率，方便 用户快速查询到需要相关的信息。此外，网页分类也有助于对信息资源进行组织管理， 合理的加以利用，有助于主题词典的建立和维护，对主题搜索引擎的发展起了推动作用。 目前自动分类技术已在数字图书馆、主题搜索、个性化搜索引擎、信息过滤、主动信息 推送服务等方面得到了实际应用【2 1 。 目前国外对网页分类的研究也比较多，结合数据挖掘和人工智能等理论提出了多种 分类技术，分类的结果也比较理想。然而，对中文的网页分类的分类效果并不理想，因 为不同于英文的结构化语言，中文是种语义语言，句子通过短语内容进行连接，同义 词的现象非常多，因此进行分类前需要进行中文分词处理，而且网页中通常包含大量的 广告、版权注释等“噪声数据”，都对分类的准确性造成了干扰。由于中文网页的语义 复杂性，使得中文网页分类器普遍呈现出分类效率低下，商业可行性不高，无法在现实 中得到推广和应用的缺陷。因此，研究中文网页自动分类技术，不能简单的使用文本分 类算法，要结合机器学习的理论，分析中文网页的结构特征，挖掘网页内的类别信息， 第一章绪论 迅速而又准确地分类。 实现中文网页的自动分类，一方面，可以将网页按类别建立相应的数据库，对分类 数据库进行查询，提高文章的查全率和查准率：另一方面，可以建立自动的分类信息资 源，为用户提供分类信息目录【3 1 。本文旨在对文本分类算法和网页结构进行分析研究， 克服中文网页分类算法存在的效率慢和精度不高的缺点，设计出一个类别划分更准确、 分类效率更高的中文网页分类器。 1 2 国内外研究现状 1 2 1 自动分类技术的发展趋势 网页自动分类隶属于信息检索领域，是自然语言理解的一个重要应用领域，涉及人 工智能、概率统计、数据挖掘等多个研究领域。在文本分类发展的初期，占主导地位的 一直是基于知识工程的分类方法，即采用人工方式来构建分类器，需要专业人员手工编 写分类规则来指导分类，如y a h o o ! 的目录式搜索引擎。上世纪5 0 年代术，h p l u h n 首 先提出了将词频统计思想用于自动分类，丌始从文本的词频统计分析、句法分析和语义 分析等三个层次上进行研究。其中，以基于词频统计分析的自动分类试验较为成功。直 到九十年代后期，随着电子文本的大量出现，基于机器学习的自动文本分类系统开始兴 起，成为信息系统学科关注的热点之一。到目前为止，自动分类在国外经历了三个发展 阶段：第一阶段( 1 9 5 8 1 9 6 4 ) 主要进行自动分类的可行性研究，第二阶段( 1 9 6 5 1 9 7 4 ) 进行 自动分类的实验研究，第三阶段( 1 9 7 5 至今) 进入实用化阶段。自动分类己在邮件分类、 电子会议、信息过滤方面取得了比较广泛的应用，其中比较成功的例子有麻省理工学院 ( m i t ) 为白宫所开发的邮件分类系统、卡内基集团为路透社所开发的c o n s t r u e 系统、美 国伍尔弗汉普顿网络图书馆的w w w i i b 自动归类系统、北欧w a i s 力维网自动分类项 目等。 在文本自动分类系统评测方面最权威的是著名的t r e c 会议 4 1 。t r e c ( t e x t r e t r i e v a lc o n f e r e n c e ) 是由美国国家标准和技术研究院( n i s t ) ，信息技术实验室( i t l ) 检索 小组、信息访问和用户界面公司( i a u i ) 、自然语言处理和信息检索部( g r o u po f n l p i r ) 、 美国国防部高级研究计划署信息技术处( d a r p a ) 共同主持召丌的年度国际信息检索 会议。在t r e c 会议上展示的分类系统代表了文本分类领域的最新研究成果，很多知名 2 中图石油人学( 华东) 硕f ：学位论文 大学，如c m u ，c o r n e l l 、b e r k l e y 和一些公司带着自己开发的分类系统参加会议， 由大会使用相同的训练集和测试用例对这些系统进行评测。从第五次会议丌始，增加了 对中文分类系统的评测【5 j 。随着分类技术的不断成熟，分类领域也建立了o h s u m e d ， r e u t e r s 等大型丌放的标准语料库，为自动分类的研究提供了一个标准化的平台。 国内对于文本自动分类的研究起步较晚，1 9 8 1 年，候汉清先生首先对自动分类在文 献分类中的应用做了探讨，从计算机管理分类表、计算机分类检索、计算机自动分类、 机编分类表等四个方面介绍了国外的发展概况。随着中文信息处理技术特别是中文自动 分词技术的同渐成熟，以此为基础的中文文本分类技术得到了快速发展。从2 0 0 4 年6 月起，北京大学网络实验室和北京大学计算语言学研究所建立并维护的，以大规模中文 w e b 信息为测试集的信息检索研究论坛( c w i r f ) 对中文网页分类起了很大的推动作用。 此外，还有广东省中山图书馆的计算机辅助图书分类系统，清华大学的自动分类系统， 南京大学的i d g s ( i n t e r n e td o c u m e n tg r o u p i n gs y s t e m ) 系统，海量智能公司的智能分词分 类系统等。 1 2 2 分类模型和分类算法的发展现状 大部分的分类系统都是以统计学为理论依托，通过对规模测试语料库进行分析，建 立经验模型，在模型的基础上应用具体的算法实现分类。比较成熟的分类模型有向量空 间模型、布尔模型概率模型、潜在语义模型等【6 】。 ( 1 ) 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 是1 4 - 1 g e r a r d s a l t o n 等人在2 0 世纪6 0 年代 提出的，并成功应用于著名的s m a r t ( s y s t e mf o r t h em a n i p u l a t i o na n dr e t r i e v a lo f t e x t ) 系统。向量空间模型在信息检索和文本分类领域得到了广泛应用，是目前非常流行的应 用模型。向量空间模型中的典型应用算法有有r o c c h i o l 7 1 、k n n 8 1 、s v m 9 1 和类中心向量 法【1 0 1 。 ( 2 ) 布尔模型是向量空间模型的一种特例，遵循二元判定标准，向量的权重只用0 或1 表示。它的优点在于具有清楚和简单的形式，而主要缺陷在于很难将信息转化为布尔值， 会导致太多或者太少的结果文档被返回。决策树、关联规则方法都足基于布尔模型。 ( 3 ) 9 - i 叶斯概率模型足以概率论为架构，该模型的特征向量均假定为相对独立的。基 于概率模型的算法包括n a i v eb a y e s t 1 及其改进算法。 ( 4 ) 潜在语义模型l s i ( l a t e n ts e m a n t i ci n d e x ) 是由d u m a i s ，f u m a s ，l a n d a v e r 和 第一章绪论 h a r s h m a n 等人于1 9 9 0 年提出，也用向量表示特征项，但是每一个向量代表一个“概念”， 就是通常所晚的“概念空间模型”，使用奇异值分解，把文档投影到一个具有潜在语义 的特征空间中【6 】。l s i 解决了向量空间模型的特征共现、同义问题。 此外，组合多种文本分类算法是网页分类中应用比较多的一种研究思路，可以综合 不同算法的优点来获得更好的分类性能。b o o s t i n g 算法是一种典型的多分类器方法，考 虑到代表样本和边缘样本的类信息含量，对不同的训练集产生多个学习机，分别进行权 值调整，按分类效果进行加权组合，产生最终分类器【1 2 】【13 1 。卡耐基一梅隆大学的c h o o n 用组合网页分类器的方法进行网页分类，其中一个分类器用网页中的纯文本、标题和子 标题文本表示网页，另一个分类器用指向该网页所有链接周围的文本表示网百【9 】；中科 院的李晓黎等利用s v m 准确度高和无监督聚类速度快的特点，提出了一种将s v m 和 无监督聚类相结合的i s u c 算法【1 4 j ；许多研究机构也在这方面展开了研究。 1 2 3 基于网页特性的分类研究现状 ( 1 ) 基于网页超链接信息的方法。可以通过超链接得到相邻超文本，为分类提供有效 的辅助参考，通过超链接可以得到多个超文本间的关系和不同超文本的权重。例如，n e c 研究所的e r i cj g l o v e r 和普林斯顿大学的k o s t a st s i o u t s i o u l i k l i s 等使用网页内的扩展超 链接对网页进行分类和类别描述【l5 】；清华大学的沈抖等人定义了网页的显式链接和隐式 链接并以此来帮助网页进行分类【l6 1 ，有效利用了超链接中的信息；侯小静分析h t m l 标签，统计文字链接a t r 比和表格标签比t t r ，筛选索引型网页和和数据表格型网页， 使用筛选后的网页集合训练分类器可以取得较好的分类结果【1 。7 1 。 ( 2 ) 基于网页结构化信息的方法。超文本页面中含有大量有用的结构信息，这些信息 包括该页面标题、重要的标题和各种其他标记等内容。可以将这些结构信息用于超文本 分类，一方面可以有效提高分类精度，另一方面叮以减少计算的复杂度。例如，有的学 者提出了使用数据库技术中的包装器( w r a p p i n g ) 来对网络数据结构化，将网络文档分割 为多个信息块【1 8 】【1 9 】【2 0 1 ；s l o v e n i a 的a n d r e jb r a t k o 提出了的s t a c k i n g 法，它适用于结构 化文档的分类【2 1 】；微软的s u s a nd u m a i s 对网页内容进行层次化分解，再使用s v m 分类 【2 引，解决了多层次类别的网页分类问题，适用于分类结构比较复杂的情况；邓健爽等提 出了一种对网站内部拓扑结构进行约简1 2 3 1 、提取网站层次结构实现多层次分类的方法 等，但是该方法的缺点是对每个网站分类时都需要建立一棵分类结构树；网页分块也是 4 中闺钉油人学( 乍东) 颀l j 学位论文 结构化的一种分类方法，根据信息块的重要程度分别进行加权，分块解析的实现方法有 h t m l 标签的d o m 树解析【2 4 】和基于视觉特征的分块解析。 综上所述，目前对于网页的搜索一般是基于关键词进行的，由于中文语言中的一词 多义和多词一义现象的普遍存在，使得网页的搜索的效果差强人意，特别是针对某一主 题领域的搜索，搜索结果往往会存在许多与该主题无关的结果，使得用户浪费大量时间 浏览自己并不感兴趣的内容，所有主流的搜索引擎普遍存在着搜索的准确率低、召回率 低、冗余度高的问题。中文网页分类虽然也在不断的完善和改进，但是仍然存在着一定 程度的缺陷，尚无特别理想的改进算法。因此针对中文网页集合的特性，本文将展丌深 入研究，研究适用于中文网页的自动分类技术，并对其进行实现和评测。 1 3 课题研究的主要内容 本文的主要研究内容如下： ( 1 ) 网页自动分类的基本原理和工作流程研究 网页分类属于文本挖掘和信息检索研究的范畴内，分为网页预处理、文本表示、特 征选取、自动分类和分类效果评价五个步骤。在网络信息检索的基础上，对这五部分进 行深入研究，掌握了网页自动分类的具体实现方案。 ( 2 ) k n n 分类算法研究与改进 k n n 算法是一种理论上比较成熟的分类算法，在基于统计的模式识别中非常有效， 具有很好的分类性能，但是其“懒惰学习”的特性造成了算法执行的复杂度高这一不利 因素，使得分类时的时间丌销比较大，不适用于在线文本的实时处理。通过分析k n n 算法的缺点，从样本分布的角度出发研究k n n 算法的改进策略，提出了一种新的代表 样本生成策略，利用代表样本代替原始训练集进行分类，并进行实验验证了改进算法的 可行性。 ( 3 ) 基于中文网页结构的特征加权研究 网页中的结构信息对于挖掘其中的主题信息起着指导和帮助作用。在文本分类的基 础上，研究网页的半结构化特性，分析网页的分块特性和超链接在网页中的不同功能， 利用主题相关链接信息对特征词的权值计算做出修正。 ( 4 ) 中文网页分类器c p c k 的设计与实现 第一章绪论 按照中文网页自动分类的步骤和流程，设计并实现一个中文网页分类器，将改进算 法应用其中，并与原算法的效率进行对比，并进行分析和总结。 1 4 论文的组织结构 论文共分六个章节，主要内容组织如下： 第一章，阐述了论文的研究背景和意义以及国内外研究现状，介绍了论文的主要研 究内容，最后给出论文的组织结构。 第二章，对网页分类的关键技术做了概述，首先介绍了文本分类的概念和分类依据， 然后详细阐述了网页分类的一般过程，包括网页预处理、向量空间模型、特征选取、常 见的分类算法和分类的评价指标，最后说明了网页分类在搜索引擎中的应用。 第三章，分析网页的结构化特性，并研究了网页超链接的特性，进而提出了一种利 用主题相关链接对特征项加权的权重修正法。 第四章，详细阐述了k n n 算法的基本原理，并在数据集挖掘的基础上，通过深入 分析数据集类别之间的关系，提出了一种生成代表训练集的算法，在此基础上对k n n 算法进行改进，提高了分类的效率。 第五章，介绍了中文网页的分类器c p c k 的设计方案和实现方案，并对实验结果进 行测试和评价。 结论，对全文进行了总结，说明了论文的主要工作、主要创新点、存在的问题以及 未来的发展方向。 6 中同，f j l 自人学( o 仁东) 硕i ：学位论文 第二章中文网页分类关键技术 2 1 文本分类技术概述 2 1 1 文本分类概念 文本分类：属于文本挖掘和机器学习的范畴，是一个有指导的学习过程。它利用预 先定标识了类别的文本集合，通过训练和学习，建立起文本与主题类别的关系模型，并 采用此关系模型为未知类别的文本确定某个类别。从本质上看，对文本进行分类的过程 也就是文本与主题类别相映射的过程，耳的是将将每个文本分别映射到一个或多个主题 类别中，可以形式化的表示为： f - d o c u m e n t - c l a s s d o c u m e n t 是待分类的文本，c l a s s 是已知类别的文本集合。函数f 把文本d o c u m e n t 映射到集合c l a s s 中。 文本分类的映射规则是系统根据已经掌握的每类若干文本的类别标识信息，总结出 分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结出的判别 规则，确定新文本所隶属的类别。因此，文本自动分类是一个有指导的学习过程。它根 据己经被标注的训练信息样本集合，找到信息属性和信息类别之问的关系模型，然后利 用这种学习得到的关系模型对新的信息样本进行类别判断。文本分类的关键问题是如何 构造一个分类函数或分类模型( 也称为分类器) ，并利用此分类模型将未知文本映射到 给定的类别空间。 2 1 2 自动分类的方法 根据分类知识的获取途径不同，可以将文本分类系统分为词匹配法，基于知识工程 的方法和基于统计学的方法【2 1 。 词匹配法又可以分为简单词匹配法和基于同义词的词匹配法两种。简单词匹配法是 最简单、最直观的文本分类算法，它根据文本和类名中的共现词决定文档属于哪一类。 这种算法的分类规则过于简单，分类效果很差。基于同义词的词匹配法是对简单词匹配 法的改进，它预先定义一张同义词表，然后根据文本和类名以及类中的共现词( 含同义 词) 决定文本属于哪一类。这种分类法扩大了词的匹配范围，在性能上优于简单词匹配 法，但是分类规则仍然是机械的，同义词表是静态的，分类准确度也很低。 7 第二章中义嗍灭分类关键技术 基于知识工程的分类方法主要依赖语言学知识，需要知识工程师手工地编制大量地 推理规则，这些规则通常面向具体的领域，当处理不同领域的分类问题时，需要不同领 域的专家制定不同的推理规则，而且分类质量严重依赖于推理规则的质量，实现相当复 杂，而且其丌发费用相当昂贵。这方面的系统有卡内基集团为路透社丌发的c o n s t r u e 系 统f 2 6 】。 统计学习法是先搜集一些与待分类文本处于同一个领域的文档作为训练集，并由专 家进行人工分类，保证分类的准确性，然后分析这些已经分好类的文本，从中挖掘关键 词和类别之间的联系，最后再利用这些学到的知识对文本进行分类。基于统计学的方法 以统计学为基础，忽略文本的语言学结构，将文本作为特征项集合来看，利用特征向量 进行文本表示，利用词频信息对文本特征进行加权。它实现起来比较简单，并且分类准 确度也高，能够满足一般应用的要求。基于统计学的方法最典型的模型是向量空间模型。 2 1 3 网页分类过程 网页自动分类分为三个过程，文本表示过程、训练过程和分类过程，如图2 1 所示： 固 图2 - 1 网页自动分类的一般过程 f i 9 2 1p r o c e d u r eo ft h ep a g ea u t oc a t e g o r i z a t i o n 文本表示过程是网页向特征向量转化的过程，包括： ( 1 ) 预处理过程。就是将输入的数据转化为计算机能够识别和处理的数据，在网页分 类中是指将半结构化的w e b 文档转化为特征向量。 ( 2 ) 权重计算。是指对预处理之后的词条计算分类权重，也就是分类重要度。 8 中固油人学( 仁东) 顺f ：学位论文 训练过程是使用选定的算法，对训练集进行特征抽取和分类的过程，反复调整算法 的参数，直到分类器得到一个理想的分类精度。特征选取有两方面的要求：一是降低特 征向量的维数，使得特征项的个数尽量少，二是选出的特征项尽可能的有代表性，能最 大限度的表示文本。 分类过程是将待分类的中文网页经过文本表示和特征选择两个步骤后，应用训练过 程得到的分类算法和阈值策略进行分类，得到所属类别的过程。 2 2 网页预处理 在文本挖掘的工作中，预处理要占到整个工作的6 0 以上，在网页分类中也是如此。 网页预处理有以下几个子步骤，分别是h t m l 解析、词法分析、中文分词、停用词删 除几个过程【2 7 1 。 2 2 1 h t m l 文档解析 h t m l 解析的目的在于去掉与网页分类无关的h t m l 源码，抽取出文本。为了清 晰地表示h t m l 解析的结果，将解析结果保存为x m l 格式。这种结构化的格式有利于 进一步的预处理和特征的抽取。 常用的h t m l 中的标记有4 种类型：基本标签、与结构相关的标签、与显示相关 的标签和链接相关的标签。其中能够表示内容重要程度的主要是与结构相关的标签和与 显示相关的标签，另外有一些标记( 例如表示分段显示的 和分行显示的 等) 对 于内容重要程度没有多大意义【2 8 】。 h t m l 解析的步骤如下： 首先，除去 、 、 、 、 等与显示相关的标签及其 所嵌套的h t m l 源码，因为这些代码只与网页表现形式有关，而与网页内容无关。 标签用来描述一个h t m l 网页文档的属性，包含网页描述、关键词等属性， 标签 用来描述网页标题： 和 、 ， ， ，粗体 ，下划线 ，斜体 ， 所描述的信息与网页内容有很强的相关性，需要保刚2 9 1 ； 标签的h r e f 属性描述的超链接的u r l ，如果想利用网页的链接结构来进行分类， 那么最好保留 标签的属性。 9 第一二幸中文网灭分类关键技术 除了 、 和 之外，其它标签的属性对于网页分类的作用不大，可以忽 略。为了便于处理，我们人为地为其中的文本添加自定义的标签，定义规则如下：网页中 的“普通文字”( 即不含超链接的文字) 用 标签标识，链接文字用 标签标识。 按上述规则，解析h t m l 源码，h t m l 网页便可以表示为一棵h t m l 标签树。标签树 的叶子节点为 所标识的普通文字或者 所标识的链接文字。 2 2 2 中文分词 中文分词对中文搜索引擎具有重要意义。对于搜索引擎来说，最重要的并不是找到 所有结果，因为在上百亿的网页中找到所有结果没有太多的意义，没有人能看得完，最 重要的是把最相关的结果排在最前面，这也称为相关度排序。中文分词的准确与否，常 常直接影响到对搜索结果的相关度排序。在文本分类中，中文分词的准确程度直接影响 着特征项的划分，而特征项划分的准确与否直接影响着分类精度。中文词法分析，即中 文分词，是中文网页分类的基础与关键。 例如对某一段文字“在美国此次降息后，中美利率就此出现倒挂局面，即中国 的基准利率超过了美国。经过去年1 2 月的加息后，中国目前的一年期存款基准利率为 4 1 4 ；而美国目的的利率已降至3 5 ”，经过分词处理、无用词删除后被切分为“美国 此次降息中美利率就此出现倒挂局面中国基准利率超过美国经过去年 加息中国目前一年期存款基准利率美国目前利率降至”。切分后的词进行统 计和去除重复词，每个词对应倒排文档中的一个倒排表，他们的交集即为对应查询结果 的结果集。 国内的分词算法大体分为两种：种是机械分词，即按照一定的算法从待分析的文 本中提取出一系列字符串，依次与词典中的词条进行匹配，匹配成功则认为分出一个词。 常用的有m m 法，即正向最大匹配法( m a x i m u mm a t c h i n g ) ，r m m 法即逆向最大匹配法 ( r e v e r s em a x i m u mm a t c h i n g ) ，最少切分法等等。另一种思路可称之为知识分词，利用 有关词、句子等的句法和语义信息或者从大量语料中找出汉字组词的结合特点来进行评 价，以期找到最贴近于原句语义的分词结果。大部分实际运用中的分词算法都结合这两 种思路，以机械分词为基础，辅以知识分词来进行歧义处理【3 0 1 1 3 1 】。 2 2 3 停用词删除 停用词指的是那些语法词以及一些虚词、感叹词、连词等，另外有些高频词汇在所 l o 中罔石油人学( o 坪东) 倾l ：学位论文 有的文本中出现的频率都基本相同，区分性差，也不能作为文本类别的特征。分词得到 的单个字不仅所携带的文本信息量较少，而对其他实词起到一定的抑制作用，降低了分 类系统的处理效率和准确度。引入停用词表和高频词表，剔除这些对分类没多大影响的 词语。 2 2 4 词性选择 通过分析中文语法可知，句子一般是由各种词性的词组成，句子的主干为主，但是 对句子内容的影响并不大。由于词频和文档频率比较高，这些词常常会得到比较高的权 重。采用预处理过程中的停用词，往往只会删除一小部分语气词和单字，正义中还保留 着大量的形容词和助动词等，而停用词表的更新也是一个需要解决的问题。句子的主干 为主语+ 谓语+ 宾语，构成主谓宾的词语主要是名词、动词，还有代词、介词、形容词、 副词等修饰成分，这些修饰成分在一篇文章中占据的比例非常大，出现的频率很高。 从另一个角度出发，句子的主干就能够基本表达句子的主要语义。因此在特征项的 选取过程中，选择名词和动词作为特征空间中的词条足一种缩小特征空间、减少噪音、 提升分类效果的可行办法。对于中文自然语言的句子，依靠i c t c l a s 中文分词工具， 可以比较准确地进行词性标注，从而进一步将句子中的名词和动词抽取出来【3 6 1 。 正则表达式是描述符合某种复杂规则的字符串的常用工具。对特征项的词性识别， 采用一则表达式匹配来实现。构造一个正则表达式，使之能匹配文本中标注为名词和动 词的文本，便能提取文本中的名词和动词作为特征词。例如对“网页自动分类隶属于信 息检索领域，是自然语言理解的一个重要应用领域”这句话进行分词的结果为：“网页 n 自动d 分类v d 隶属v 于p 信息n 检索v n 领域n ，w 是v 自然a 语言n 理解v的u 一个m 重要a 应用v n 领域n ”。要提取这句话中的名词和 动词，就要构造一个只匹配字符串“n ”或者“母木v ”的正则表达式。在正则表达式中， “x y ”表示匹配“x ”或者“y ”。“+ ”表示匹配至少前面的一个字符例如“a b + ” 可以匹配“a b b ”、“a b b b ”等。“【a m n 】”表示某个范围之外的字符，匹配除m 到 n 之l 、日j 的任何字符。“s ”匹配处换行符之外的任意空白字符等。考虑很多网页，尤其 是科技类网页的正文中，英文单词也会常常出现，不加选择的把英文字母排除可能会丢 失很多关键信息，但是对类别标识和特征提取而言，为了符合大多数中国人的习惯，都 是以中文的形式来表述，因此在词性提取时，采取忽略英文单词的方式。数字和其他符 第二章中文网畎分类关键技术 号对类别特征也并无很大影响，可以忽略。因此j 下则表达式( 【 s ! 释$ & 宰a z a - z o 9 ) + ( n l v l v n ) 就可以在分词后的中文文本中匹配出词性标注为n 或者词性标 注为v 的词。再使用正则式( 【 ( n l v ) 】) + 将词性标注去掉，得到词性提取后最终的特征项。 利用j 下则表达式匹配，能够方便快捷的匹配出所需要的名词和动词，有效地降低了特征 向量的维数，而且算法效率也非常高。 2 3 文本表示 网页经过预处理之后，表示为由一定的结构化信息和大量的词条项所组成的文本信 息，就需要进行下一步文本表示的工作。 在文本分类技术，应用的基础模型主要有向量空间模型( v e c t o rs u p p o r tm a c h i n e ，简 称v s m ) 、贝叶斯模型、决策树模型、神经网络模型、潜在语义模型等，其中空间向量 模型的原理主要基于统计学方法，其原理简单、易于实现，且在实际应用中取得了很好 的效果，是一种最流行的文本表示模型。 2 3 1 向量空间模型 向量空间模型的基本思想是将一篇文本表示为由特征项( 字、词、词组或短语等) 组 成的向量，向量的每一维对应一个特征项，特征项的维数对应于不重复词汇的个数。特 征项是指文本经过中文分词后得到的词或短语。在该模型中，把文本看作是一组特征项 的集合，并给每个特征项赋予一个对应的权值，用于表示该词语描述这篇文本的能力， 它的大小用来表示该词语在此篇文档中的重要程度。 用数学方法表示，将文本映射为一个特征向量v ( d ) = ( f ，w i ，厶，w 刀) ，其中 为特征项，w ，为如在d 中的权重，一般定义为岛在d 中的出现频率斫的函数：w , - - 0 ( 鳓。 2 3 2 权重计算 权重的大小代表了该词语在文本中的重要程度。特征项权重的计算方法有很多种， 比如布尔权重，基于熵概念的权重计算和t f i d f 公式等。其中，t f i d f 计算公式是最 常见的权重计算方法。 词语权重计算的准则就是要最大限度的区分不同文档，一个有效的特征项集， 必 须具备以下两个特征： ( 1 ) 完全性：特征项能够体现目标内容； 1 2 中国油人学( 华东) 硕i ：学位论义 ( 2 ) 区分性：根据特征项集，能将目标同其它文档相区分【3 2 】。 所以，针对词语权重w 的计算，需要考虑两方面的因素： 词语频率t f ( t e r mf r e q u e n c e ) ：该词语在此文档中出现的频率； 词语倒排文档频率i d f ( i n v e r s ed o c u m e n tf r e q u e n c e ) ：该文档在文档集合中的分布情 况，用于计算该词区分文档的能力，见公式( 2 1 ) ： f 够= l o g ( n 一+ o 0 1 ) ( 2 1 ) 由此，s a l t o n 和m cg i l l 提出了基于香农信息理论的t f i d f 公式f 3 3 1 ，己成为分类中 最常用的计算权重的方法： w i = 矿硕( 2 - 2 ) 并经过正规化处理，通常采用归一化方法，使得到的权重分布在【0 ，1 】之间： 彬2 t f , l o g ( n 珥+ 0 0 1 ) ( 2 - 3 ) 其中，斫为第f 个特征项在文本d 中出现的词频，为训练文本的总数，聆，为训练 集中出现该特征的文本数，即文档频率，分母为归一化因子，用作标准化处理。 此外，还有其他的正规化处理方法，如对数词频法( l o g a r i t h m i ct e r mf r e q u e n c y ) 、 余弦f 规化( c o s i n en o r m a l i z a t i o n ) 方法等，都从不同程度上解决了高频词对权重的影响 问题。 文本经过预处理后进行词频统计，最终表示为上述的向量。t f i d f 公式的依据是： 在文本中出现频率越高、而且只在同类文本中出现频率高的特征，对分类的贡献度越大； 并且考虑区分文档的能力，文档频率表越小，它区分文档的能力就越高。根据t f i d f 公式，文档集中包含某一词条的文档越多，说明它区分文档类别属性的能力越低，其权 值越小；某一文档中某一词条出现的频率越高，说明它区分网页内容的能力越强，权值 越大【3 3 】。 目前针对向量空间模型的改进技术，大多集中在项的选择、加权策略，以及采用相 关反馈进行优化查询等方面。例如陆玉昌等人从单词加权和向量旋转的角度解释t f i d f 并提出了使用文本特征选择中的评估函数来代替函数进行权值调整的方法 3 4 l 。 g a b r i e l 等人提出了词类权重的思想，认为应该将特征词放在整个类中考虑，将整个类 第：章中艾州灭分类关键技术 看成一个庞大的文档，这种做法加强了类别中文本之间的相互联系和不同类别文本之问 的相互区别，能够提高文本分类的精度【3 5 1 。 2 4 特征选取技术 文本经过特征表示后，仍然存在着大量的特征项。特征空间的维数过高，一方面导 致分类算法的代价太高，另一方面导致无法准确地提取文档的类别信息，造成分类效果 不佳。因此，需要在不牺牲分类质量的自仃提下尽可能地降低特征空问的维数。特征选取 的任务就是要将信息量小、不重要的词汇从特征项空i 日j 中删除，减少特征项的个数，它 是文本自动分类系统中的一个关键步骤【3 6 】。 在文本自动分类过程中，文本的特征选取应该注意特征项所在的区域。文本的标题、 副标题以及关键字中的词条项包含了有关文档类别的重要信息，所以应该把其中的特征 项作为重要特征保留，摘要中的特征词条对于分类的贡献也很大，但是仅仅这些特征信 息是不够的，还需从正文内容中选取特征信息。 特征选取的一般过程如下： 给定训练集d = d t ，d 2 ，巩 ，设特征项集合t e r m s = t l ，t 2 ，“ ，用沏 表 示集合 l ，2 ，掰 ，特征选取可以看作是从t e r m s 至l j m 的一个l 一1 映射，即 f - s e l e c t i o n ：死r m s 一【小】，然后从计算复杂度的角度出发，选取一个f 【朋】，认为 t e r m s 中的那些函数值不小于f 的词汇为“选取的特征项”，记做丁。完成了特征选取后， 分类就是基于t 的，即以其中的元素为基础，用一个向量来表示每一个文档。 目前特征选取的方法主要有：文档频率( d o c u m e n tf r e q u e n c y ，d f ) 、信息增益 ( i n f o r m a t i o ng a i n ，i g ) 、互信息( m u t u a li n