（计算机软件与理论专业论文）中文网页分类特征提取方法研究.pdf

摘要 随着信息技术的不断发展，网页分类已经成为目前研究的一个热点。网页分类，即 根据一定的分类规则实现大量w e b 文本的自动归类。它能够对网页进行有序组织，改善 信息检索的性能，提高网络资源的利用率。特征提取是网页分类过程中的一个重要步骤， 也是网页实现高效分类的前提，提取算法的优劣将直接影响到分类器的性能。 介绍了网页自动分类的原理、过程和发展，详细阐述了分类流程的各个步骤，并分 析、比较了几种常见的分类算法。在网页分类过程中，详细研究了特征提取方法，阐述 了特征提取的意义和工作原理。在介绍常用的特征提取算法基础上，系统分析了互信息 ( m i ) 和) c 2 统计量( c h i ) 算法，发现m i 算法忽略负值特征、过分倾向低频词，而c h i 算法 无法过滤无用高频词、对特有低频词又不重视。此外，二者均未考虑特征词在类别中的 出现概率对分类的影响。针对以上不足，对m i 和c h i 算法做了相应改进。在特征提取对 象上，分析了可提取的对象范围，重点考虑了标题、正文、超链接、超文本标记等信息， 并根据特征出现的不同位置，赋予不同权重，从而提出了位置加权法。同时在预处理上 考虑到停用词表的不完备性和计算复杂度，直接使用正则表达式提取对文本类别最具代 表性的名词和动词作为初始特征，实现向量空间的初步降维。 为了验证改进的特征提取方法，将其应用到具体的中文网页分类系统中，实验结果 表明，改进的特征提取方法不仅提高了分类质量，还提升了分类效率，有效减少了计算 开销。 关键词：网页分类，特征提取，互信息，y 2 统计量，位置加权 r e s e a r c ho ff e a t u r es e l e c t i o n f o rc h i n e s ew e b p a g ec a t e g o r i z a t i o n z h u l i n a ( 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 eg r e a t l yr a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , w e bp a g ec a t e g o r i z a t i o n h a sb e c o m eo n eo ft h em o s ta t t r a c t i v ef o c u s e si nr e s e a r c h t h ew e bp a g ec a t e g o r i z a t i o ni sa p r o c e s su s i n gc o m p u t e r st oc l a s s i f yl a r g eq u a n t i t yo fw e bp a g e sa u t o m a t i c a l l ya c c o r d i n gt o s o m ec a t e g o r i z a t i o nr u l e s i tc a l lo r g a n i z et h ew e bp a g e so r d e r l y , i m p r o v et h ep e r f o r m a n c eo f i n f o r m a t i o nr e t r i e v a ls y s t e ma n di n c r e a s et h ea v a i l a b i l i t yo fw e br e s o u r c e s f e a t u r es e l e c t i o n i sak e ys t e po fw e bp a g ec a t e g o r i z a t i o n i tc a ni n f l u e n c et h ec a p a b i l i t yo fc a t e g o r i z a t i o n d i r e c t l y f i r s t ，w ei n t r o d u c et h ew o r k i n gt h e o r y ，p r o c e d u r ea n dd e v e l o p m e n to fw e bp a g e c a t e g o r i z a t i o n t h e nd i s c u s se a c hs t e po ft h ew o r k i n gf l o w a l s o ，w ei n t r o d u c es e v e r a l c o m m o nu s e dc l a s s i f i c a t i o na l g o r i t h m sa n dd os o m ec o m p a r i s o n s d u r i n gt h ec a t e g o r i z a t i o n p r o c e s s i n g ，w em a i n l ys t u d yf e a t u r es e l e c t i o nm e t h o d , l e a r ni t sp r i n c i p l ea n ds i g n i f i c a n c e o n t h eb a s i so fs o m ep o p u l a rf e a t u r es e l e c t i o na l g o r i t h m s ，w er e s e a r c ht h em u t u a li n f o r m a t i o n ( m i ) a n dx 2s t a t i s t i c s ( c h i ) a l g o r i t h md e e p l y , f m d i n gt h a tm ii g n o r e st h ef e a t u r e sw h o s e m ia r en e g a t i v ea n do f t e nb ei n c l i n e dt ot h ew o r d sw i t hl o wo c c u r r e n c ep r o b a b i l i t i e s ，b u tc h i e v e np a yn oa t t e n t i o nt ot h o s ew o r d sa n dc a l l tr e m o v et h em e a n i n g l e s sw o r d sw 池h i 曲 o c c u r r e n c ep r o b a b i l i t i e s b e s i d e s ，t h et w oa l g o r i t h m sb o t hn e g l e c tt h ef e a t u r ep r o b a b i l i t i e s o c c u r r i n gi nd i f f e r e n tc a t e g o r i e s a g a i n s tt h e s ed e f e c t s ，w ep r o p o s es o m ei m p r o v e m e n t st o m o d i f ym ia n dc h ia l g o r i t h me x p r e s s i o n a f t e ra n a l y z i n gt h er a n g eo fp r o b a b l ef e a t u r e s e l e c t i o no b j e c t s ，w et a k et i t l e ，m a i nt e x t ，h y p e r l i n kc o n t e n ta n dt a gw o r d si n t oa c c o u n tw h i c h m a yc o n t a i na v a i l a b l ei n f o r m a t i o nf o rc a t e g o r i z a t i o n ，p r o p o s eap o s i t i o n w e i g h tm e t h o d , g i v i n gd i f f e r e n tw e i g h t st od i f f e r e n tp o s i t i o nf e a t u r e s c o n s i d e r i n gt h ei n c o m p l e t e n e s so f s t o p - w o r d sl i s t ，w eu s er e g u l a re x p r e s s i o nt o s e l e c tn o u n sa n dv e r b sa st h ep r i m a r yf e a t u r e s u b s e ti no r d e rt op r e r e d u c et h ed i m e n s i o no ff e a t u r ev e c t o rs p a c e w eu s e 也e 佃叩r o v e df e a ：t l 】r es e l e c t i o nm e t h o d s t oc l a s s i f yw e bp a g e s - t h er e s l l l t ss h o w 恤tm en e w 秘础n o to n l yi m p r o v e st h ec a t e g o r i z a t i 。na e e u r a c y 。b v i o u s l y ，b u t a l s 。 d e e r e 鹳et h ec o m p u t e rc o s ta n dp r o m o t et h ee f f i c i e n e yo fe a t e g o r i z a t i o n k e yw 。r d s ：w 曲p a g ec a t e g o r i z a t i o n , f e a t u r e s e l e c t i o n , m u t u a li n f o 吼a t i 。巩妒 s t a t i s t i c s ，p o s i t i o n w e i g h t 1 1 1 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：牛 日期：砌7 年岁月2 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名： 辇虱挪 指导教师签名：一和舍0 日期：娜7 年穸月2 日 日期：z o o 年岁月沈日 中国石油大学( 华东) 硕士学位论文 1 1 课题的研究背景及意义 第一章前言 自1 9 9 1 年w e b 浏览器问世以来，经过短短十余年时间，i n t e m e t 已经发展成为一 个巨大的全球化信息空间，尤其是w w w ( w o r l dw i d ew e b ) 技术的普及，使得互联网上 的信息丰富无比。然而，随着w e b 信息的急剧增加，人们发现网络资源丰富的同时也 引出了新的问题，他们真正感兴趣的东西往往被淹没在浩瀚的信息海洋里，无从找寻。 因此，如何有效地组织、处理这些海量信息，如何更好地搜索、管理所需的网络资源成 为一个亟待解决的问题。 搜索引擎的出现在一定程度上为人们寻找资源提供了便利，比如，g o o g l e 、百度已 经成为人们熟知的信息检索常用工具，但有时仍存在诸如查准率低、信息冗余大等缺点。 为了能够有效地组织和分析这些海量w e b 信息，使用户快速、准确地定位到感兴趣的类 别和网页中，人们希望网页能够按照其内容实现自动分类。网页自动分类具有如下优点： 不需要人工干预，节省大量人力、物力，而且分类速度较快，精度较高，满足实际应用 的要求【1 1 。 目前，网页自动分类已经成为w e b 领域的一个研究热点，网页自动分类技术也成为 一项极具实用价值的关键技术，它在搜索引擎的目录导航服务、主题搜索、个性化信息 检索、数字图书馆、信息过滤、主动信息推送服务等领域都得到了广泛应用。 网页自动分类就是对网页进行有序地组织，这在一定程度上可以改善搜索引擎的性 能，帮助用户更好地搜索、过滤、定位和管理所需的网络资源，提高网络信息利用率。 可以说，网页自动分类是搜索引擎实现分类查询的关键，同时也是搜索引擎提高性能的 新方法。 网页自动分类是在文本自动分类( a u t o m a t i ct e x tc a t e g o f i z m i o n ，a t c ) 技术上发展起 来的 2 1 。随着w e b 的出现，a t c 技术的处理对象从普通文档扩展到网页信息，于是成了 网页自动分类的基础，但由于网页本身的结构特征，使得网页自动分类比文本分类要复 杂得多。在分类过程中，w e b 文本通常使用向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 来 标引，v s m 是近年来应用较多且效果较好的方法之一，最早是s a l t o n 教授在1 9 6 9 年提 出的【3 1 ，其基本思想就是用向量来表示文本，而该向量则是由一些可以代表文本主题信 息的特征项组成的。 第一章前言 实现网页自动分类的一个主要困难就是特征向量空间的维数过高，数量过大的特征 项一方面使得分类算法的计算代价过高，另一方面又无法准确地提取文档中的类别信 息，造成分类效果不佳。因此，人们迫切需要找到一种能够减小向量空间维数而又不影 响网页分类效果的方法，这就是网页的特征提取( f e a t u r es e l e c t i o n ) h i 。 网页特征提取的任务就是要将信息量小，“不重要”的词汇从特征向量空间中剔除， 从而减少特征项个数，降低向量空间维数，简化计算【5 j 。通常，如果特征项没有选取、 表示适当，不管后期分类算法如何改进，都无法改变网页分类性能低下这个事实。可以 说，特征提取是网页自动分类系统中的一个重要环节，也是网页实现高效分类的前提， 其提取算法的优劣程度将直接影响到分类结果的准确与否。 本课题旨在对中文网页分类中的特征提取方法进行研究，主要是互信息( m u t u a l i n f o r m a t i o n ，) 和x 2 统计量( x 2s t a t i s t i c ，c m ) 算法，对它们进行优缺点分析，提出相应 的改进措施，达到特征向量空间降维的目的，并将改进的特征提取方法应用到具体的中 文网页分类过程中，从而提高分类的查全率和查准率，改善网页分类效果。 1 2 国内外研究现状 网页分类是组织和利用海量w e b 信息的有效途径，其核心仍然是文本分类。在2 0 世 纪9 0 年代前，占主导地位的文本分类方法一直是基于知识工程的，即由专业人员进行手 工分类，往往存在效率低下且出错率高的现象。随着文本分类研究的发展，引入了统计 方法和机器学习方法，使得文本分类朝着自动分类的智能方向发展，并逐渐成为文本挖 掘的主要研究方向。基于人工智能的文本分类技术能依据语义将大量文本自动分类，它 按照预先定义的主题类别，由计算机自动地为文档集合中的每一篇文档确定类别，使得 用户能够方便地浏览文档，并且可以通过限制搜索范围，让文档的查找变得更加容易、 快捷【6 】。 网页分类是文本分类在w e b 文本集合上的应用。在分类算法上，目前英文自动分类 已经取得了丰硕成果，提出了多种成熟的分类方法，如文本相似度法、k _ 最近邻算法 ( k - n e a r e s tn e i g h b o r ，k n n ) 、朴素贝叶斯分类( n a f v e b a y e s ，n b ) 、决策树方法以及支 持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 等方法，在实验中得到：s v m 的分类精度较高， 而运算时间最短的则舯。 中文网页自动分类研究起步较晚，但是随着中文信息技术，如中文分词技术的逐渐 2 中国石油大学( 华东) 硕士学位论文 完善，对中文网页分类的发展起到了一定的推动作用，同时也激发了国内的一些学者的 研究兴趣，如：2 0 0 0 年清华大学的张俐等人在英文文本自动分类算法的基础上，结合中 文网页的特点，引入关键词的正负权重，提出了一种非参数在线训练方法【刀；9 0 0 3 年北 京理工大学的贺海军等人将支持向量机和二叉决策树思想融入分类器中，提出了基于决 策支持向量机的中文网页分类算法【8 】；2 0 0 6 年中科大的李滔等将粗糙集理论应用于网页 分类，提出了一种基于粗糙集的决策表约简的增量式学习算法f 9 】；2 0 0 7 年华南理工的陈 胜荣提出了基于优选链接的分类方法【1 0 】：另外还有损失最小化的s v i d 多类网页分类算法 【l l 】、基于模糊分类的k n n 改进算法等。 特征提取是网页分类中的一个必然步骤。向量空间模型把文本看做特征词的序列， 有可能涉及到大量词汇，使得向量空间维数巨大。而高维特征空间对网页文本分类的训 练时间、分类准确性都有显著的影响，分类器算法的时间、空间复杂度都会随向量空间 维数的增加而增加。因此，特征向量空间的降维操作是提高网页文本分类效率和准确率 的关键，而特征提取就是一种有效的降维方法。 对于英文网页，1 9 9 7 年y a n g ”1 等人研究了多种特征提取方法，如：文档频率 ( 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 f o r m a t i o n ， m i ) 、开方检验( z 2s t a t i s t i c ，c h i ) 、术语强度( t e r ms t r e n g t h ，t s ) 等，实验表明，c h i 和i g 方法效果最佳，m i 效果最差。 对于中文网页，其结论是否同样正确，目前还没有很明确的结论。但国内许多学者 对上述特征提取方法进行了一定的研究、比较，改进了相关算法，在中文分类测试中取 得了一定进步。 目前，特征提取的改进方法主要有以下几种： ( 1 ) 特征频率、文档频率的组合改进 特征频率( t e r mf r e q u e n c y ，t f ) 指训练集中某个特征词条出现的次数，这是最简单 的特征提取方法。通过设定t f 阈值对过滤低频特征非常有效，可以获得很大的降维度。 因此，t f 主要用于文本标引时直接删除某些低频特征【1 4 】【1 5 】。文档频率是训练集中含有 某个特征词条的文档数在总文档数中出现的概率，通常特征按照d f 值排序，优先取d f 较大的特征，但是容易将某类特有的稀有词条错误地滤掉。y a n g 通过实验表明，用d f 和t f 的组合进行特征提取可以得到更好的降维效果【1 3 1 。 ( 2 ) 信息增益的改进 3 第一章前言 信息增益是一种在机器学习领域应用较为广泛的特征提取方法，它表示文档中包含 某一特征词条时文档类别的平均信息量，定义为某一特征在文档中出现前后的信息熵之 差。信息增益考虑了文本特征未发生的情况，使得分类性能偏低。北京工业大学的李文 斌【1 6 1 等人在信息增益公式中加入了修正因子，平衡了信息熵对i g 的影响，设计了3 种基 于i g 特征权重的分类方法，根据特征对i g 贡献的大小及新文本中出现的次数进行分类， 效果较为理想。 ( 3 ) 互信息的改进 在文本预处理系统中，互信息衡量的是特征和类别之间的统计关联程度【1 7 1 ，但是它 没有考虑特征发生的频率，这造成了互信息评估函数经常倾向于低频词，从而淘汰了很 多高频的有用词条【1 8 1 。针对互信息算法的缺点，部分学者提出了改进方法。南京大学的 谭金波等【1 9 1 加上了表征词条出现概率的p ( 聊因子函数，提升高频词的权重，成为改进型 互信息算法( m i p w ) 。湖南大学的卢新国等【2 0 】提出的改进算法从全局角度考虑了特征项 对分类的影响，加强了互信息量较小的特征项在分类中的作用，在全局选择方法中效果 较好，但在局部选择方法中不适用。北京邮电大学的王秀娟等f 2 1 1 提出的互信息比值方法 考虑了特征项分别对各类提供的信息量间的大小关系，采用特征项对各类提供的信息量 的最大值与次大值之比来计算，比值越大，说明这个特征项对某类的区别能力越强。 ( 4 ) 开方检验的改进 基于x 2 统计量的特征提取方法又称为开方检验，用于度量特征和类别之间独立性的 缺乏程度【2 2 ，2 3 1 ，它同时考虑了特征存在与不存在的情况。x 2 越大，独立性越小，相关性 越大。y a n g 的研究证明，) c 2 统计量法是目前效果最好的特征选择方法之一【5 1 ，大多数中 文分类系统均采用这种方法【2 4 】，但是从理论上分析，该方法中也存在一些缺陷。 h w e et o un g 2 5 1 等人认为仅使用本类别文档中出现频率高的词语作为特征项，能取 得更好得分类效果。诚然，在其它类中出现频率高的词语也能够对人们判别文本不属于 某一类别有很好的提示作用，但是这个作用对分类效果的影响并不明显。于是他们对) c 2 统计量进行了改进，彳| 导至l j c o r r e l a t i o nc o e f f i c i e m 法。l u i g ig a l a v o t t i f 2 6 】等人在此基础上， 提出了一种更为简化的x 2 统计量( s i m p l i f i e dc h i s q u a r es t a t i s t i c ，s c h i ) 。 国内的许多学者也对c h i 算法进行了深入研究，李明杰【2 7 1 提出了选择用x 2 统计量法 和信息增益法结合后的联合特征选择法，使得分类效果有了提高。呼声波等【1 8 】考虑了特 4 中国石油大学( 华东) 硕士学位论文 征和类别的正相关和反相关两种情况，增加了相关性因子，同时滤去一些区分度差的高 频词，分类的准确率也得到了一定的提高，但是在网页的信息提取中没有链接等文字信 息，可能丢失一些信息。 ( 5 ) 算法组合改进 各种特征提取算法存在自身的优缺点，有时进行适当的算法组合也是改进的策略之 一。如：y a n g 提到的d f 和组合【1 3 】；清华大学的李粤【2 4 1 等人将互信息m i 和c m 结合起 来，提出联合的特征选择方法；李明杰【2 刀提出改进的特征选择方法将c h i 和i g 算法公式 进行有机组合，互相弥补了不足；武汉大学的徐军林【2 绷等人d f 和c h i 的组合特征提取方 法首先利用d f 算法进行过滤形成初始集，然后用c h i 算法提取有效特征，起到了降维的 目的。 ( 6 ) 特征提取新方法 对特征提取新方法的研究，国内也有学者提出相关算法。如：吉林大学的许建潮【4 】 等人设计了综合考虑位置、频率、词长3 个因素的权重计算公式，提出了一种用变长度 染色体遗传算法提取特征的方法，在降低特征向量维数上较为有效，但在有效信息损失 的问题上仍要继续研究。上述的特征提取方法只利用了正文中关键词的信息，对超链接 中所包含的信息没有有效地利用。为克服现有方法的不足，清华大学的吕滓【3 0 】等人对因 特网上的数据模型进行了研究，指出了网页间的超链接对于信息提取的重要作用，提出 了基于“超链接森林 的特征提取方法，并有效考虑了关键词与网页主体的隶属程度， 该方法被用于网页的自动分类效果很好。 综上所述，网页分类技术已经引起越来越广泛的研究，而作为分类基础的特征提取 算法也一直是网页分类的研究热点，同时它在机器学习领域的研究也备受关注。好的特 征提取方法可以明显提高网页分类的查准率和查全率，改善用户的搜索性能。在以往的 研究中，人们提出了很多种特征提取方法和模型，但是每个算法都各有优缺点，且没有 哪一种算法表现出明显的优势。目前，在特征提取算法的分析和改进上，很多学者提出 了自己的方法，但仍有很大的改进空间。因此，本文对特征提取方法进行研究，有着较 为重要的现实意义。 1 3 课题研究的主要内容 本课题的主要研究内容如下： ( 1 ) 中文网页自动分类的工作原理和分类算法研究 5 第一章前言 ( 2 ) 网页特征提取原理和常用算法研究 ， ( 3 ) 互信息f m i ) 、x 2 统计量( c m ) 算法的研究与改进 ( 4 ) 网页特征提取对象分析和维数压缩 ( 5 ) 改进的特征提取方法在中文网页分类中的应用研究 1 4 论文的组织结构 论文共分六个章节，具体结构如下： 第一章，阐述了课题的研究背景、意义以及国内外研究现状，介绍了课题研究的主 要内容，最后给出了论文的组织结构。 第二章，首先介绍了文档自动分类的定义和主要的文档分类算法类型，然后就网页 自动分类的一般过程进行了详细阐述，包括网页预处理、特征提取、分类算法、截尾算 法、结果评价等步骤，同时对几种常见的分类算法进行了比较，最后简要叙述了中文网 页自动分类的发展方向。 第三章，详细阐述了网页特征提取的工作原理，介绍了几种常用的特征提取算法并 进行比较，重点分析了互信息( 旧、x 2 统计量( c h i ) 算法，最后强调了特征提取在网页 分类中的作用及其研究的发展方向。 第四章，研究分析了互信息( m i ) 、x 2 统计量( c h i ) 算法的特点，找出m i 算法过分 倾向低频词和c h i 算法存在无用高频词的缺点，针对其存在的问题，提出了相应的改 进方法。 第五章，首先针对网页包含的丰富信息，列出了可供特征提取的对象元素，然后介 绍了网页的特征表示，重点阐述了向量空间模型( v s m ) 的概念，除了正文，还结合标题、 超链接、超文本标记等隐含信息，提出特征的位置加权法，最后提出了用正则表达式对 特征进行预降维的方法。 第六章，将改进的m i 算法和c h i 算法应用到具体的网页分类实验中，对实验结果 进行了评价和分析，并对两种改进算法进行了比较。 总结，对全文进行了总结，说明了论文的主要工作、主要创新点、存在的不足以及 未来发展的方向。 6 中国石油大学( 华东) 硕士学位论文 第二章中文网页自动分类技术 2 1 文档自动分类算法定义及分类 在w e b 问世之前，人们已研究过许多普通文档分类的方法，形成了各种文档自动分 类( a t c ) 技术f 2 】。随着w r e b 的普及，海量网页信息不断涌现，a t c 技术的处理对象逐渐从 普通文档扩展到了w e b 文本，自然地，a t c 技术也就奠定了现代网页自动分类的基础。 所谓文档自动分类就是用计算机程序来确定指定文档和预先定义类别之间的隶属关系 【3 l 】。从数学角度来看，文档分类是一个映射的过程，它将未标明类别的文本映射到已有 的类别中，该映射可以是一对一映射，也可以是一对多映射，因为通常一篇文本可以同 多个类别相关联【2 引。简单的说，就是利用计算机根据一定的分类原则，在给定的分类体 系下，自动地确定文档所属的类别。 目前，主要的文档自动分类算法可以分为三类： ( 1 ) 词匹配法i 词匹配法又可以分为简单词匹配法和基于同义词的词匹配法两种。 简单词匹配法是最简单、最直观的文档分类算法，它根据文档和类名中共同出现的词决 定文档属于哪些类。很显然，这种算法的分类规则过于简单，分类效果也很差。基于同 义词的词匹配法是对简单词匹配法的改进，它先定义一张同义词表，然后根据文档和类 名以及类的描述中共同出现的词( 含同义词) 决定文档属于哪些类。这种分类算法扩大 了词的匹配范围，在性能上要优于简单词匹配法。不过，这种算法的分类规则仍然很机 械，而且同义词表的构成是静态的，对文档的上下文不敏感，无法正确处理文档中其具 体含义依赖于上下文的词，分类的准确度也很低。 ( 2 ) 基于知识工程的方法。基于知识工程的文档分类方法，需要知识工程师手工地 编制大量的推理规则，这些规则通常面向具体的领域，当处理不同领域的分类问题时， 需要不同领域的专家制定不同的推理规则，而分类质量严重依赖于推理规则的质量。因 此，在实际的分类系统中较少使用基于知识工程的学习法。 ( 3 ) 统计学习法。统计学习法和词匹配法在分类机制上有着本质的不同。它的基本 思路是先搜集一些与待分类文档同处一个领域的文档作为训练集，并由专家进行人工分 类，保证分类的准确性，然后分析这些已经分好类的文档，从中挖掘关键词和类之间的 联系，最后再利用这些学到的知识对文档分类，而不是机械地按词进行匹配。因此，这 种方法通常忽略文档的语言学结构，而用关键词来表示文档，通过有指导的机器学习来 7 第二章中文网页自动分类技术 训练分类器，最后利用训练过的分类器来对待分类的文档进行分类。这种基于统计的经 验学习法由于具有较好的理论基础、简单的实现机制、以及较好的文档分类质量等优点， 目前实用的分类系统基本上都是采用这种分类方法。 根据分类结果的不同，基于统计学习法的分类系统在整体上可以被分为两类：独立 二元( i n d 印e n d e n tb i n a r y ) 分类系统和m 元( m a r y ) 分类系统【3 2 】。所谓独立二元分类，就是 给定一篇文档，分类系统对每一个类都独立地判断这篇文档是否属于该类：要么属于， 要么不属于，而不存在其它的结果，并且在分类过程中，不同类别之间互不影响。所谓 m 元分类就是给定一篇文档，系统计算这篇文档与所有预先定义的类的相似度，并按这 篇文档和各个候选类的相似度排序，最后输出候选类列表。 文档分类算法示意图如图2 1 所示： 图2 - 1自动文档分类算法的分类 f i 9 2 - 1c a t e g o r i e so fa t ca l g o r i t h m 2 2 中文网页自动分类一般过程 网页自动分类的核心是分类器，分类器要实现功能，主要包括“训练”和“分类 过程。所谓“训练 ，就是在已知文档类别的情况下，统计不同类别内词的分布情况， 即在预先定义的类别集合c g ，瓯，q 与特征词条集合即j ，玩，彬的幂集之间 建立一种加权的映射关系，形成一种向量表示【3 3 1 。简单的说，就是通过训练学习，提炼 出一套规则，将每个类别转换成其对应的特征词向量，供“分类 过程比较、使用。所 谓“分类”，就是已知一篇文档内词的分布，一般是一个向量表示，将该文档向量和训 练形成的每个类别向量比较( 通常就是用一种分类算法) ，最终确定该文档所属的类别。 r 中国石油大学( 华东) 硕士学位论文 下面给出中文网页分类的基本过程，如图2 2 所示： 图2 - 2 中文网页分类的基本过程 f i 9 2 - 2p r o c e s s i n go fc h i n e s ew e bp a g ec a t e g o r i z a t i o n 其中，预处理主要包括h t m l 解析、中文分词、停用词删除、词条选择及网页“噪 声”清除等处理，将网页由半结构化形式转换成含大量词条的结构化文本信息，供下一 步特征提取使用；特征提取主要对预处理后得到的所有词条进行选取，选择最能代表网 页内容主题的词条组成特征向量，成为计算机可以识别、处理的数据。通过分类算法得 到一定的结果，并不是最佳效果，此时必须反复调整相关算法的参数，达到理想的分类 效果。最后的分类结果，基于二元分类算法的分类器，可直接将分类结果作为网页的最 终类别结果，而基于m 元分类算法的分类器，还需要对该分类结果做进一步筛选，才 能得到待分类网页的类别结果。 2 2 1 网页预处理 在特征提取之前需要对网页进行预处理，这是因为：和普通文档相比，网页具有以 下特性【3 】： ( 1 ) 网页采用超文本设计，网页内包含大量的h t m l 标签，这使得它比普通文本表现 力更强，可利用的信息更多，如包含在标题 中的内容通常和网页主题关系密切， 而各级标题中，字号大的h 1 又总比字号小的h 6 重要。 ( 2 ) 网页间采用超链接相连，在w e b 中相邻的网页通常具有相关或相同的主题，因此 可以为分类提供一定的启发。 ( 3 ) 中文网页使用汉字，不像英语单词之间存在自然的间隔，中文需要分词处理，而 且分词的效果能够显著地影响分类质量。 9 第二章中文网页自动分类技术 ( 4 ) 网页通常包含大量的“噪音”，如各类广告、导航条、推荐栏、作者的注释以及 版权申明等和内容无关的信息。有时同一个网页甚至会包含多个不同的主题。在分类之 前需要清除这些噪音，否则这些噪音会影响分类性能。 因此，需要对网页预处理后才能进行分类过程。结合中文网页的特性，介绍一些预 处理的过程： ( 1 ) h t m l 解析 h t m l 解析是网页分类的第一步，主要是去掉一些与分类无关的h t m l 源码，保留 文本，它解析出来的内容的正确性对于后面的分类精确度将有很大的指导作用【3 4 】。 h t m l 解析将用到如下文本用以分类： 标题，即t i n e 标记的文字，它与网页主题的关系很密切，起着概括全篇的作用。t i t l e 标签在搜索引擎中占有非常重要的地位，里面的内容往往是该网页较为精确的说明。 链接文字，有两类：一类是与网页内容相关的推荐链接，所连接的网页主题与本该 页相似，需要保留；另一类是广告或导航链接，对分类没有什么作用，属于“噪音 ， 应该去除。 一 m e t a 标签，含有k e y w o r d s 和d e s c r i p t i o n ，这两个元素的设置关系到网页在搜索引擎 中的排名，k e y w o r d s 告诉搜索引擎网页的关键字是什么，d e s c r i p t i o n 是对网页内容的描 述，因此设置好关键字可以提高网页搜索点击率。我们可以利用m e t a 标签中的有关文本 内容来帮助我们完成网页分类。 正文，也就是在 里面的文字，是网页内容的显示，含有大量主题相关词条。 正文文本一般都是网页中文字最集中的较长的字符串，整个出现在一个标签中，如 划p 间的文字，因此，提取文本类标签中的文本作为正文，利用它们进行网页分类。 当然，网页中有一些信息是分类不需要的，女i j a v a s c r i p t 、s y t l e 等只与网页表现形 式有关，而与主题无关，如果将这些信息带入到后续的特征提取过程中，h t m l 解析出 来的信息和获取的正文文本的准确度将大大下降，因此，必须将它们事先去除掉。 ( 2 ) 中文分词 词是最小的能够独立活动的有意义的语言成分，但是汉语以字为基本书写单位，词 语间没有明显的区分标记，中文分词处理就是在汉语词条间加入分隔符，使之转换为分 散的词流形式，利于中文信息处理。例如，句子“今天天气晴朗”，经过中文分词得到： “今天t 天气1 1 晴朗a ”，每个词后面都带有词性标注，t 表示时间，、i l 表示名词，a 表示 形容词。 1 0 中国石油大学( 华东) 硕士学位论文 汉语智能分词是中文信息处理的基础和关键，如果没有一个好的中文词法分析系统 的支持，那么所有涉及中文信息处理系统的正确率都会大大下降。而一个好的中文词法 分析系统最终依靠的是好的分词算法。 分词的基本算法有：( 1 ) 基于词典与规则匹配法。基于词典与规则的方法应用词典匹 配，汉语词法或其它汉语语言知识进行分词，这类方法简单、分词效率较高，但对词典 的完备性、规则的一致性等要求比较高。配策略有：最大匹配法、最小匹配法、逆向匹 配法、增字或减字匹配法、双向扫描法。( 2 ) 标志法。如切分标志法、统计标引法。( 3 ) 词频统计法。基于统计的分词方法将汉语基于字和闻的统计信息，完备性较差。( 4 ) 语义 语用法。如后缀分词法。目前使用最多的是基于词库的分词方法，由于中文在分词时可 能产生二义性。如“计算机器”可分成“计算“机器”和“计算机 “器，这样 必须结合其它分词方法。如基于语法规则的分词法、基于朴素贝叶斯分词法等。在具体 的分词过程中，我们还可以将单词变型归并，像同义词、近义词可进行归并，如“因特 网 和“万维网 可当成一个词条处理。c h i n e s es e g r n e n t e r 3 5 】采用最大匹配算法，即试 图匹配可能的最长的字符串，算法简单且非常有效。中国科学院计算技术研究所基于多 层隐马尔科夫模型，研制出汉语词法分析系统i c t c l a s ( i n s t i m t co fc o m p u t i n g t e c h n o l o g y ，c h i n e s el e x i c a la n a l y s i ss y s t e m ) 3 6 ，主要功能包括：中文分词、词性标注、 命名实体识别、新词识别等，目前已升级到i c t c l a s 3 o ，分词精度达9 8 4 5 ，是当前 公认最好的汉语词法分析器。 ( 3 ) 停用词删除 停用词s t o p w o r d s ，就是出现频率很高的词，它们对分类没有任何价值，反而会增大 特征空间的维数，搜索引擎遇到这些词一般都不会执行搜索。如副词、介词、连词、语 气词等。在分类之前，需要引入停用词表来过滤掉停用词。 英文停用词表，比较著名的是v a nr j j s b e r g e n 3 7 1 发表的停用词表以及b r o w nc o r p u s 停用词表【3 8 】。y a n g 并i p e d e r s e n 认为，将停用词按出现的文本频数降序排序，用前1 0 个停 用词过滤特征向量空间不会产生负面影响；用前1 0 0 个停用词过滤特征向量空间产生的 负面影响非常小【1 3 】c a t a r i n as i l v a 验证了应用停用词表削减特征空间可以提高基于支持 向量机的文本分类器的准确率【3 9 1 。 关于中文停用词的研究，虽然当前已有一些较好的停用词表，但其构造与选取语料 相关，针对不同应用很难直接应用。有学者试图根据任务需求、采取熵【4 0 】、联合熵【4 1 】 和基于t f i d f 词语k l 分布的重采样技术自动获取停用词表【4 2 1 。目前可以查到的中文停 1 1 第二章中文网页自动分类技术 用词表正在不断完善和扩充中。 ( 4 ) 词条选择 由于构成文本的词汇量较多，表示文本的向量空间维数也相当大，有时甚至达到几 万维。为了提高程序效率，有必要进行维数的压缩工作，在预处理中进行词条选择可以 起到缩小空间的作用。 从汉语言角度出发，可以标识文本信息的一般都是名词、动词和形容词等这样的实 词，而一些虚词，如语气词、介词、连词等，对文本的分类毫无意义。因此，我们选择 表意的名词、动词，剔除一些对类别没有贡献或者贡献很小的词，实现了对文本词条的 过滤，可以认为这是对向量空间的初步降维。提取的工具，可以利用i c t c l a s 3 6 分词工 具进行词性标注，然后运用正则表达式( r e g u l a re x p r e s s i o n ) 进行匹配，将句子中的名词 和动词选取出来。 2 2 2 特征提取 特征提取在分类中起着重要作用，提取算法的优劣直接影响到分类质量。网页的特 征提取主要是对分词后的词条进行选择，提取可以代表网页类别信息的词条组成特征向 量。提取特征时，一般根据特征评估函数计算各个特征的评分值，然后按评分值由大到 小排序，选取若干个评分值高的词条作为特征词。在文本处理中，用于特征提取的评估 函数有：特征频率( t f ) 、文档频率( d f ) 、信息增益( i g ) 、互信息( m i ) 、开方拟和检验( c h i ) 、 期望交叉熵( e c e ) 、特征熵( t e ) 、术语强度( t s ) 等。 具体算法将在第三章中进行详述。 2 2 3 分类算法 根据图2 2 所示的中文网页分类过程，分类器的工作原理【3 3 l 般如图2 3 所示。从 总体上来说，分类器的整个工作周期包括“训练”和“分类”两个过程。在训练阶段， 训练集经过中文分词和特征提取后被表示成向量形式，该特征向量用来代表类别，供分 类时使用。校验集是训练集的一部分，通过应用相应的阈值策略来预先确定每个类别的 截尾阈值。在分类过程中，一个待分类的中文网页经过中文分词和特征提取后被表示成 向量形式，应用分类算法同训练过程得到的类别向量一一比较，得到候选类别列表，然 后同训练过程中得到的每个类别的阈值进行比较，保留大于阈值的类别，并作为该网页 的分类结果。 1 2 中国石油大学( 华东) 硕士学位论文 图2 - 3中文网页分类器工作原理 f i 9 2 - 3p r i n c i p l eo fc h i n e s ew e bp a g ec a t e g o r i z a t i o n 2 2 4 截尾算法 对于一个待分类网页，应用m 元分类算法通常得到多个类别。一般情况下都要求从 这些候选类别中选择部分类别作为该网页的最终分类结果，这个过程使用的方法被称为 阈值策略，其中使用的算法就是截尾算法。常见的截尾算法有： ( 1 ) 位置截尾法( 刚【一b a s e dt h r e s