（信号与信息处理专业论文）基于vsm的中文网页分类特征选择技术研究与实现.pdf

摘要 随着信息技术的不断发展，网页自动分类技术成为了w e b 领域的一个研究 热点，它在信息检索、信息过滤等多个领域得到了广泛地应用。特征选择是实 现网页自动分类的重要环节，它从初始特征空间中选出类别区分能力强的特征 项以降低网页文本向量空问维数，提高分类器的分类效率和分类精度。 本文在对中文网页自动分类相关技术研究的基础上，实现了分类系统中网 页清洗、中文分词、去停用词、特征选择及权重计算生成向量空间模型等模块 的基本功能，重点研究并实现了基于统计学习的文档频率、z 2 统计量和信息增 益特征选择算法。通过实验比较了上述三种特征选择算法的分类性能，实验结 果表明基于z 2 统计量的特征选择算法的分类性能要优于信息增益法和文档频率 法，而文档频率法在特定特征项数目下与z 2 统计量法分类性能相当，基于信息 增益的特征选择算法虽然分类准确率不及上述两种算法，但其分类的稳定性与 z 2 统计量法相当，优于文档频率法。在对传统特征选择算法分析的基础上，本 文针对它们各自的不足之处进行了相应的改进，并实现了改进的算法。 针对传统文档频率法对全局高频特征项过分偏袒，致使特征优化选择出的 特征项类间分布不均衡，导致部分类别分类性能低下的不足，本文实现了基于 类内相对文档频率的特征选择算法，使用类内相对文档频率进行局部特征选择 再取并集的方式取代传统的全局文档频率的特征选择算法。 针对z 2 统计量法当特征项数目递增到一定程度时对集中度高、文档频率较 低、代表性不强的特征项倚重过大，从而导致分类性能骤降的不足，本文实现 了将文档频率阈值与z 2 统计量相结合的特征选择算法，去除了全局高频特征项 和类内低频特征项，改善了传统z 2 统计量法对低频特征项过分依赖的缺陷。 由于信息增益法总体分类性能表现不佳，因此本文对其进行了全面改进， 将类内词频、集中度和类内分散度综合考虑进信息增益法的评估函数中，并采 取类内信息增益特征选择法取代了传统算法在类i i j 取最大值的全局选择方式 本文通过实现上述的改进算法，并将生成的向量空间模型带入分类器中进 行实验，发现改进的特征选择算法对分类系统的性能均有不同程度的改善。 关键词：网页分类特征选择，向量空问模型( v s m ) ，信息增益，z 2 统计量 a b s t r a c t w i t ht h ed 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 , t h ea u t o m a t i cw e bp a g e c l a s s i f i c a t i o nt e c h n o l o g yh a sb e c o m eo n eo ft h em o s ta t t r a c t i v er e s e a r c hf o c u s e si n t h ef i e l do fw e b ，i th a sb e e nw i d e l yu s e di ni n f o r m a t i o nr e t r i e v a l ，i n f o r m a t i o n f i l t e r i n g ，a n ds o m eo t h e rf i e l d s f e a t u r es e l e c t i o ni sa ni m p o r t a n tl i n ki na u t o m a t i c w e bp a g ec l a s s i f i c a t i o n ；i ts e l e c t st e r m sw h i c hh a ss t r o n ga b i l i t yt od i s t i n g u i s h c a t e g o r i e sf r o mo r i g i n a lf e a t u r es p a c et or e d u c et h ed i m e n s i o n so fw e bp a g et e x t v e c t o rs p a c e ，a n di m p r o v e sc l a s s i f i c a t i o ne f f i c i e n c ya n da c c u r a c yo fc l a s s i f i e r s t h i sp a p e re x p o u n d se a c hs t e pi nt h ep r o c e s so fa u t o m a t i cc h i n e s ew e bp a g e c l a s s i f i c a t i o n ，a n dr e a l i z e dc l e a n i n gw e bp a g e s ，s e g m e n t i n gc h i n e s ew o r d s ，r e m o v i n g s t o pw o r d s ，s e l e c t i n gf e a t u r et e r m s ，w e i g h t i n gf e a t u r et e r m s ，g e n e r a t i n gv e c t o rs p a c e m o d e la n ds o m eo t h e rr e p r o e e s s i n go p e r a t i o n si nc h i n e s ew e bp a g ec l a s s i f i c a t i o n t h ek e yr e s e a r c hi n t h i sp a p e ri st h ef e a t u r e s e l e c t i o nm e t h o d sb a s e do ns t a t i s t i c a l l e a r n i n gs u c ha sd o c u m e n tf r e q u e n c y ( d f ) ，c h i s q u a r es t a t i s t i c s ( c h i ) a n dt h e i n f o r m a t i o ng a i n ( i g ) f e a t u r es e l e c t i o nm e t h o d s e x p e r i m e n t sa r ed o n et ot h ea b o v e t h r e e f e a t u r e s e l e c t i o nm e t h o d st oc o m p a r et h e i rc l a s s i f i c a t i o np e r f o r m a n c e ，a n d f o u n dt h a tt h e f e a t u r es e l e c t i o nb a s e do nc h ii ss u p e r i o rt od fa n di g , a n dd f m e t h o di nap a r t i c u l a rq u a n t i t yo ff e a t u r et e r m sp e r f o r m a n c ee q u a lt oc h im e t h o d a l t h o u g ht h ec l a s s i f i c a t i o na c c u r a c yo fi gm e t h o dc a nn o tc o m p a r ew i t hd fa n dc h i m e t h o d s ，b u t i t sc l a s s i f i c a t i o ns t a b i l i t yi s e q u a l t oc h ia n db e t t e rt h a nd f m e t h o d b a s e do nt h ea n a l y s i so ft h et r a d i t i o n a lf e a t u r es e l e c t i o nm e t h o d s ，t h i sp a p e r p r e s e n t ss o m ei m p r o v e m e n tm e a s u r e sa c c o r d i n gt ot h e i rd e f i c i e n c y a c c o r d i n gt ot h et r a d i t i o n a ld fm e t h o d sb i a st og l o b a lh i g h 仔e q u e n c yt e r m s ， t h ef e a t u r et e r m ss e l e c t e db yd fi sd i s t r i b u t e du n e v e na m o n gc a t e g o r i e s ，l e a d i n gt o s o m ec a t e g o r i e sh a v el o wc l a s s i f i c a t i o np e r f o r m a n c e t h i sp a p e rp u t sf o r w a r dan e w f e a t u r es e l e c t i o nm e t h o db a s e do nr e l a t i v ed fi ne a c hc a t e g o r y t h em o d i f i e dd f m e t h o df i r s ts e l e c t st e r m si ne a c hc a t e g o r ya n dm e r g e dt h el o c a lf e a t u r et e r m s t h et r a d i t i o n a lc h i s q u a r es t a t i s t i c sm e t h o di sr e l y i n gh e a v i l yo nt h et e r m s o w n i n gh i g hc o n c e n t r a t i o n i n f o r m a t i o nb u tl o wd o c u m e n tf r e q u e n c ya n dl o w r e p r e s e n t a t i v ew h e nt h e n u m b e ro ff e a t u r et e r m si n c r e a s i n gt oac e r t a i nd e g r e e i e a d i n gt oav e r t i c a l l yd r o p p i n gi nc l a s s i f i c a t i o np e r f o r m a n c e t h i sp a p e rp u t sf o r w a r d 锄o m e rn e wf e 撒鹏s e l e c t i o nm e t h o dt h a tc o m b i n i n gt h ed f t h r e s h o l dm e t h o d 锄d t 1 1 et 训i t i o h a lc h im e t h o d t h en e wc h i m e t h o dr e m o v e st h eg l o b a lh i g hd ft e r m s a n dr c s p e c t i v el o wl o c a ld ft e r m si m p r o v i n gt h ed e f e c t st h a th e a v i l yr e l y i n go nl o w f r e q u e n c yt e r m si nt h e t r a d i t i o n a lc h im e t h o d a c c o r d i n gt ot h et r a d i t i o n a li gm e t h o d sp o o rp e r f o r m a n c e i nc l a s s i f i c a t i o n , t i f f s p a p e rm a k eao v e r a l li m p r o v e m e n to fi tb yc o m p r e h e n s i v em e r g i n gc o n c e n 唿t i o n i n f o 咖a t i o n d i s p e r s i o ni n f o r m a t i o na n dt e r mf r e q u e n c yi n t ot h ee v a l u a t i o nf u n c t l o n o f 位l d i t i o n a li gm e t h o d i na d d i t i o n ，t h i sp a p e ru s e dl o c a l i gf e a t u r es e l e c t i o n r e p l a c i n gt h et r a d i t i o n a lm e t h o ds e l e c t i n gt e r m so w n i n gm a x i m u m e v a l u a t i o nv a j u e a m o n g a l lc a t e g o r i e s w i t i lt l l ei m p l e m e n t a t i o no ft h ea b o v em o d i f i e dm e t h o d s ，t h ep r o g r a mg e n e r a t e d b o t ht r a i n i n ga n dt e s t i n gw e bp a g e s v e c t o rs p a c em o d e l ( v s m ) a n d m a k et h e ma st h e i n p u to fac 1 嬲s i f i e r a c c o r d i n g t 0 也e 他s u l t0 f 删v ee x p e r i n l e n t s ，t h i sp a p e rm a k e ac o n c l u s i o nt 1 1 a t a l lt h ea b o v em o d i f i e df e a t u r es e l e c t i o nm e t h o d sc a ni m p r o v et h e p e r f o r m a n c eo ft h ec l a s s i f i c a t i o ns y s t e m k 眄w o r d s ：w e bp a g ec l a s s i f i c a t i o n , t e r ms e l e c t i o n , v e c t o rs p a c em o d e l ( v s m ) ， i n f o r m a t i o ng a i n ，c h i s q u a r es t a t i s t i c s i i i 武汉理+ l ：人学硕+ 学位论文 1 1 研究背景及意义 第1 章引言 万维网是当今互联网上最重要的应用之一，迄今为止，互联网上的中文网 页数量已经超过了6 0 0 亿，并且还在以年增长率7 8 6 的速度在递增。网页量的 迅猛增长使得获得真正有用的网页信息变得更加困难i l j 。 搜索引擎在一定程度上为查找所需的网络信息资源带来了便利，目前的搜 索引擎主要有两种，一种是以基于目录结构的，另一种是基于检索程序的1 2 j 。前 者的典型代表是y a h o o 以及新浪，但目前，这类搜索引擎仍然依靠手工或者半 自动化的方式进行分类，人力物力的开销太大且效率低下。后者的典型代表是 g o o g l e 以及百度，它们根据用户的检索条件从自建数据库中返回检索结果，但 是结果涵盖了包含关键词的全部网页，并按程序认为的匹配程度从高到低进行 排序，而当用户和程序的观点不一致时，将花去大量的时问从检索结果中逐个 寻找。因此人们希望计算机能够代替他们分析网页内容并实现自动分类，这样 用户可以更快、更准确、更全面的搜索到真正需要的有用网页p j 。 w e b 数据挖掘技术随着互联网的发展以及w e b 用户知识获取的需求而得以 发展【i i 。网页自动分类技术属于w e b 内容挖掘的范畴，它在分类过程中不需要 领域专家的人工干预，可以节约大量的人力物力的开销，并且可以实现搜索引 擎的按类别检索，提高网络资源的利用率，成为一项极具实际应用价值的科学 技术【2 1 。 网页自动分类技术是在文本自动分类技术( a u t o m a t i ct e x tc a t e g o r i z a t i o n ， a t c ) 的基础上发展起来的1 4 j ，但由于网页结构内容的多样化，使得网页自动分 类比文本自动分类更为复杂。实现网页自动分类的第一个瓶颈是要将无结构或 者半结构化的网页文本数据转换成计算机能够理解和处理的数据形式，向量空 间模型( v e c t o rs p a c em o d e l ，v s m ) 便是近年来应用较为广泛并且效果较好的文本 表示模型1 5 i 。网页信息经过处理后得到表示网页主体内容的文本信息，运用v s m 网页文本信息将以由表征网页内容的特征项组成的向量表示。 实现网页自动分类的第二个瓶颈是表征网页的特征项数量巨大，对应的 v s m 为高维向剧酬。v s m 维数过高一方面会加大后续分类操作的计算量，使得 武汉理1 ：人学硕十学位论文 分类时间过长，无法满足分类实时性的要求；另一方面，会导致具有明显类别 区分力的特征项被大量不具有类别区分力的特征项所干扰，造成分类效果不理 想。因此人们迫切需要寻求一种方法来合理降低表征网页信息的v s m 维数，使 得降低分类操作运算量的同时提高网页分类的效果i ，i 。 网页的特征选择( t e r ms e l e c t i o n ) 是当前解决这一问题的有效方法。特征选择 又称特征子集选择，或者属性选择l 引。在网页自动分类中，特征选择就是根据某 个评价函数，如文档频率( d o c u m e n tf r e q u e n c y , d f ) 、z 2 统计量( c h i ) 、信息增益 ( i n f o r m a t i o ng a i n ，i g ) 等1 9 j 【1 0 】从网页原始的特征向量空问中进行选择，只挑选出 部分对网页分类贡献大的特征项，过滤大量不相关或者冗余的特征项，达到降 低分类计算量提高分类效果的双重目的。大量实验表明，如果没有合适的选择 和表示特征项，那么无论对后续的分类算法做何改进，网页分类的性能都无法 达到理想水平【i l j 。因此，网页的特征选择是实现网页高效分类的前提，是网页 自动分类的一个重要的环节，特征选择算法的性能将直接影响分类系统的最终 效果。 本文主要对中文网页自动分类技术中特征选择的算法进行研究，实现了文 档频率、z 2 统计量和信息增益算法，通过实验数据分析上述三种算法的优缺点， 并进行相应的改进。利用改进特征选择算法提取出的特征项构建训练集和测试 集网页的v s m ，将该v s m 作为已有网页分类系统的输入，从而改善网页分类 系统的性能。总而言之，对网页分类特征选择的深入研究，将对互联网海量信 息的处理提供帮助，极具实际应用价值1 1 2 1 。 1 2 国内外研究现状 h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) 网页是带有结构标记的文本，经过结构 信息抽取可以将网页转换为文本信息，因此，文本自动分类技术是网页自动 分类的基础。 文本自动分类简称文本分类( t e x tc a t e g o r i z a t i o n ) ，是在分类体系一定的前 提下，通过分析文本的内容将其判定为分类体系中的某一个或多个类别。文 本分类的研究涉及包括文本内容理解和模式分类等多个领域的问题1 5 l ，随着人 们对这些问题有了更为深入的了解和重视，目l i ，已经有大量的专家学者投 入到该领域的研究中，取得了若干引人关注的研究成果。 武汉理i ：人学硕+ 学位论文 1 2 1 国外研究现状 国外对于文本自动分类的研究起步较早，该项研究已经进入了实用化阶 段，并且大量的研究工作开始涌入面向互联网的文本自动分类。近几年来， 国外在文本自动分类特征选择算法上提出了许多具有实用价值的方法。 s a k e t 乃j 和m e n g l e i h j 等人提出了一种基于歧义值度量( a m b i g u i t ym e 硒u r c ， a m ) 的特征选择算法，该算法从特征集合中挑选出具有明确类别指示度的特征 项。o g u r a1 1 5 1 等人提出了一种基于泊松分布的特征选择算法，该算法通过评估 每个特征项的概率分布与标准泊松分稚的偏离程度来衡量每个特征项的重要程 度。c h e n i i 提出了一种基于鉴另【 力度量( d i s c r i m i n a t i n gp o w e rm e 嬲u r e ，d p m ) 的 特征选择方法，d p m 方法不仅计算开销低，而且同时强调了特征项与类别的正 相关性以及负相关性，此外，该方法强调了分类过程的并行处理而不是串行处 理。r o h i n i ! r 7 1 提出了一种基于图( g r a p h b a s e d ) 的文本表示模型，与基于响亮空间 模型的文本表示模型不同之处在于，该方法可以捕获到词语次序、术语频率、 术语共现以及文档中词语上下文关系。 g h a s e m a g h a e cn i i g 】、a e ；h d a r nmh 【1 9 1 和n e m m is 【2 0 1 等人将蚁群算法( a 眦 c o l o n y o p t i m i z a t i o n ，a c o ) 弓i 入到了文本分类中，提出了一种新的基于a c o 的特 征选择算法。将蚁群算法应用到文本分类特征选择需要关注三个方面：第一个 方面是，要将特征选择问题转换为适合蚁群算法解决的问题形式，a c o 可以解 决图表形式的最优化问题，所以他们用节点来表示文本特征项，每两个文本特 征项之间的连线表示对下一个特征项的选择路径，通过该表示模型可以将寻找 最优化特征子集的问题转换为寻找蚂蚁通过该图表的最少节点子集：第二个方 面是构建启发式函数( h e u r i s t i cd i s a b i l i t y ) ，作者指出，譬如基于信息熵( e n t r o p y ) 和 | l 糙集( r o u g hs e t ) 的特征子集选择算法都是构造启发式函数的有效方法；第三 个方面是信息素浓度( p h e r o m o n e ) 更新规则，该算法中信息素浓度的更新由分类 器的性能和特征子集的长度共同决定，并且两者对于特征选择任务的重要程度 是不一样的。 t a s c i 2 1l 等人对现有的文本分类特征选择算法进行了大量评价实验，分别采 用了局部和全局特征选择方式。他们使用在规模、复杂度、和均衡度各异的三 个语料库，采取t f i d f 权重计算方法，并用s v m 分类器进行分类实验。实验 结果显示，对于几乎所有的特征选择算法，在特征空问维数低的情况下局部选 择方式都比全局选择方式表现好，全局特征选择方式会随着特征空问维数的逐 武汉理jl ：人学硕+ 学位论文 步提升而表现出较好的分类性能。他们针对现有的特征选择算法的不足，提出 了一种新的算法a k s ( a d a p t i v ek e y w o r ds e l e c t i o n ，自适应关键词选择) ，该算法的 基本思想是根据每个类别的文档数量n 来确定该类别所应提取的特征项数量， 实验表明，a k s 算法在不均衡语料库下表现要优于其他算法。 1 2 2 国内研究现状 国内在文本分类方面的研究与国外相比起步较晚，中文和英文在语言表达 形式、句法分析和语义分析等方面都有较大差异，不能照搬国外的研究成果瞄1 。 现有的研究表明以词作为文本内容的特征项较好，这就需要对文本进行分 词处理四1 ，中科院研制出的汉语分词系统i c t c l a s 是最早的中文开源分词项 目。在分词技术逐步发展的带动下，国内的专家学者在中文文本分类领域展开 了大量的研究，提出了许多宝贵的意见。 在特征选择方面，杨凯峰1 2 4 i 等人针对传统的文档频率( d f ) 方法在进行特征 选择时仅考虑特征词在类别中出现的d f ，没有其在每篇文档中出现的词频率 ( t f ) ，提出了将t f 与特d f 结合的特征选择方法。李会瞄1 等人通过构造树结构 模型来消除噪音文本，同时还可以降低计算复杂度。范小丽1 2 6 1 等人针对互信息 特征选择方法没有很好结合正相关特征和负相关特征，采用了平衡因子调整正 相关和负相关特征比例，加强特征选择时负相关特征的作用。同时引入特征分 布差异因子，区分类强相关特征，提高分类效果。刘庆和1 2 7 】等人将频度、集中 度、分散度应用到信息增益方法上，提出了一种基于信息增益的特征优化选择 方法。裴英博【2 8 1 等人跟踪和分析了传统c h i 统计方法，发现影响该方法分类效 果的主要因素是它考虑了特征项与类别负相关，针对该问题，提出了一种改进 的方法去除负相关对于c h l 分类效果的影响。 在权重计算方面，张宝富【2 9 】和苏立华【3 0 l 等人针对传统t f i d 权重计算方法 没有考虑到特征项在类问和类内的分布情况的不足，结合特征项在类问和类内 信息分布熵来调整t f i d f 特征项的权重计算，提出了一种结合信息熵的 t f i d f 改进方法。 在分类算法方面，孙荣宗【3 1 i 等人提出了一种提高k n n 分类效率的改进算 法，该算法在训练过程中计算出各类文本的分相范围，在分类过程中，根据待 分类文本向量在样本空f b j 中的分御位置，缩小了其k 最近邻搜索范围。徐丽【3 2 j 等人在支持向量机分类- - 器( s v m ) 基础上进一步结合遗传算法，将s v m 决策树分 4 武汉理j i ：人学硕十学位论文 类器的分类正确率作为g a 适应度函数，对s v m 决策树层次结构进行优化， 在每一决策节点自动选择最优或近优的分类决策。体现了将遗传算法与s v m 决策树结合的优越性。樊康新【3 3 】针对朴素贝叶斯( n b ) 分类器在分类过程中存在 诸如分类模型对样本具有敏感性、分类精度难以提高等缺陷，提出一种基于多 种特征选择方法的n b 组合文本分类器方法。依据b o o s t i n g 分类算法，采用多 种不同的特征选择方法建立文本的特征词集，训练n b 分类器作为b o o s t i n g 迭代过程的基分类器，通过对基分类器的加权投票生成最终的n b 组合文本分 类器。 纵观国内外学者对文本分类特征选择的研究，可以发现d f 、i g 、c h i 仍然 是目前主流的特征选择算法，通过对他们进行适当的改进可以在诸如语料库不 均衡、语料内容高度关联等情况下改善分类性能。d f 算法由于计算成本低在小 样本集上仍具有其优势，而i g 和c h i 算法由于有信息论和统计学的理论支撑和 良好的性能表现成为寻找更优的特征选择算法的基础。但目前文本自动分类技 术的应用仍不广泛，网页自动分类在实际应用中的准确率也不高，所以需要继 续对相关技术进行深入研究，加大其在实际生活中的应用。 1 3 研究的主要内容 本文在国内外对文本特征选择的研究基础上，主要针对中文网页自动分类 的特征选择及其相关技术进行研究。本文的实验中，用于网页分类特征选择的 数据集均来自新浪门户网站，以获得全部链接的方式随机选取，所得网页集合 未经过任何的人工筛选，因此为本文的研究提供了最真实的语料环境。基于此 训练和测试集，本文展开的工作主要有以下几点： ( 1 ) 对网页集合进行清洗，运用正则表达式去除与网页正文内容无关内容， 着重获得网页的标题和正文。基于本文的研究重点是网页分类中的特征选择算 法，故并未保留过多的其他网页信息，以便更好地分析特征选择算法对网页分 类性能的影响。 ( 2 ) 使用中科院汉语分词系统i c t c l a s 的j a v a 版本i e t e l a s 4 j 对网页集合进 行分词处理；对照停用词表去除停用词；滤除分词后生成的单字词，进行初步 降维；建立词条、网页索引和词频问的联系，构建词典向量。 ( 3 ) 对传统的文本分类特征选择算法进行分析的基础上，实现了文档频率、 c h i 统计和信息增益特征选择算法。通过分类实验数据分析这三种特征选择算法 武汉理。l ：人学硕+ 卜学何论文 的优点和不足，进行相应的改进，并最终实现改进的算法。 ( 4 ) 用t f i d f 权重计算方法对特征项进行加权；依据特征选择算法挑选出的 特征项，为训练集和测试集网页构建向量空问模型；在已有的支持向量机分类 系统下进行实验。 ( 5 ) 使用查全率、查准率、f 1 值以及对应宏平均值对各种特征选择算法下的 分类器性能进行评价，验证改进后的三种特征选择算法对网页分类效果的改善。 1 4 本文的组织结构 本文以中文网页分类的特征项选择算法为研究重点，从中文网页分类基本 原理和实现框架为起点，首先通过实现分类预处理过程的各个步骤来为本文的 研究对象做铺挚，然后对传统的基于统计学习的特征选择算法进行研究和实现， 最后通过分析传统算法的优点和不足之处进行相应的改进，并实现改进的算法。 第l 章引言：介绍了中文网页分类的研究背景及研究意义，分析了国内外文 本分类特征选择算法的研究现状和研究重点，并介绍了本文的主要研究工作。 第2 章中文网页自动分类系统设计：完成了中文网页自动分类系统的总体设 计，并用j a v a 实现了网页清洗模块、中文分词模块、构建词典模块以及构建v s m 模块的基本功能。 第3 章特征选择算法的研究与实现：详细分析并推导了基于文档频率、信息 增益和基于z 2 统计量的特征选择的算法，并用j a v a 实现了上述三种算法，通过 分类实验比较分析它们的优点和不足。 第4 章网页分类特征选择算法的改进与实现：对基于文档频率、z 2 统计量 和信息增益的特征选择算法进行改进，实现基于类内文档频率的特征选择算法、 基于文档频率阈值和z 2 统计量相结合的特征选择算法以及融合了词频、集中度、 分散度的类内信息增益的特征选择算法，通过大量的对比性分类实验验证改进 的特征选择算法对中文网页分类性能的改善。 第5 章总结和展望：对本文所做的工作进行了总结，并对进一步研究工作进 行了展望。 6 武汉理ji ：人学硕十学位论文 第2 章中文网页自动分类系统设计 网页自动分类技术已经成为w e b 领域的一个研究热点，它在信息检索、信 息过滤等多个领域得到了广泛地应用。本章在对基于统计学习的网页自动分类 技术研究的基础上，实现了分类系统中网页清洗模块、中文分词模块、词典建 模模块以及构建v s m 等模块的基本功能。 2 1 网页自动分类概述 网页自动分类是在预定义的分类体系下，根据网页文本的内容或属性，将 给定网页与一个或多个类别相关联的过程p i 。s e b a s t i a n i 以一种数学模型 ：d x c 专 t ，f ) 描述了该分类任务，其中d = 西，畋，4 ，) 表示需要进行分类 的文档，c = c ，c ，c u ) 表示预定义的分类体系下的类别集合。r 值表示对于 来说，文档d ，属于类c 而f 值表示对于 而言文档d ，不属于 c 。0 4 j 。网页分类目前主要有词匹配法、基于知识工程和基于统计学习的方法。 词匹配法根据网页中是否出现与类名相同词来判断该网页的类别，这种方 法不仅误判率高，而且会出现大量网页无法判断类别的情况。后来人们引入了 同义词表，根据网页中是否出现与类名相近的词来判断网页是否属于某个类别， 这中方法虽然在一定程度上改进了分类效果，但是仍然无法改变分类效果低下 的事实。显然，这种过于简单机械的方法无法为网页分类带来良好的效果。 基于知识工程的方法由领域专家为每个类别定义大量的推理规则，若预分 类网页能满足这些规则，则可以判定为该类别。由于在分类系统中加入了领域 专家的人为干预，所以分类的准确率与此匹配法相比大为提高m j 。 尽管基于知识工程的分类方法准确率高，但该方法仍然有其局限性，主要 表现在3 个方面：首先，编写分类规则的劳动量大，如c o n s t r u e 系统在开发和 调整上足足花费了数人工年，且分类规则的编写人员都是领域专家，人力成本 会大幅上升；其次，分类结果过分依赖于人为因素，领域专家分析的个人能力 直接决定了网页分类的效果：第三点也是最重要的一点，基于知识工程的分类 系统完全不具备可推广性，例如一个针对财经领域编写的分类系统若要扩展到 医疗领域，除了重新编写一个全新的分类系统外没有别的方法，这将造成巨大 7 武汉理：i ：人学硕 ：学位论文 的人力和物力的浪费。 由于基于词匹配和知识工程的网页分类方法都无法满足实际应用的需求， 人们开始寻求一种新的分类方法，并最终从探究人类具有对事物进行分类的能 力的原因上找到了突破。 基于统计学习的分类方法类似于人类学习的方式，人类可以从过去的经验 中获取知识用于提高解决当前问题的能力，计算机虽然没有经验可用，但可以 从搜集的过去的数据中获取知识，这些数据就代表了过去的“经验，i 。使用统 计学习技术开发网页分类系统时，首先需要一批由人工进行了准确分类的网页 作为学习的资料，这些供给计算机进行学习的网页集合统称为训练集。然后计 算机从训练集中挖掘出一些能够有效分类的规则，这个挖掘分类规则的过程称 为训练，而总结出的分类规则称为分类器。训练完成后，计算机需要对未知类 别的新网页进行分类时，便会使用训练阶段生成的分类器进行分类。 现如今，基于统计学习的网页自动分类方法已经成为网页分类领域绝对的 主流。其主要的原因在于其中的特征选择、分类器构造等诸多技术都拥有曝实 的理论基础，存在明确的评价标准，以及良好的实际表现。随着互联网技术的 迅速发展和普及，网页自动分类技术已经不仅仅局限与对网页内容所描述的主 题进行分类，网络信息的主观倾向性分类即情感分类( s e n t i m e n tc l a s s i f i c a t i o n ) 也 受到了越来越多的关注。总之，与网页有关，与分类有关，无论从何种角度出 发都可以称为网页分类。当然，对网页主题分类进行深入研究将为其他类型的 网页分类研究奠定坚实的基础。 2 2 系统总体方案设计 网页分类问题可以归结为，根据待分类网页的某些特征来进行匹配，选择最 优的匹配结果来完成分类。因此将分类核心的问题转化为用哪些特征来表征网 页才能保证网页分类的准确性与时效性。现有的研究表明以词作为为特征项比 较合理1 2 3 1 。国内对于中文网页分类的研究主要是基于向量空问模型( v e c t o rs p a c e m o d e l v s m ) 。在v s m 中，每个网页都被表征为特征空问中的一个向量，而该 向量中的每一维都对应于网页中的一个特征项。 中文网页分类的处理过程主要包括训练阶段和测试阶段。在训练阶段，首 先过滤掉与网页内容无关的广告等信息后获得网页训练集的文本集合，然后将 每个文本网页进行分词处理，分词后借用停用词表删除每个网页文本中的停用 8 武汉理r 人学硕十学位论文 词，并且通过过滤单字词来达进行初步降维。初步降维后就可以对每个网页中 的每个特征项进行词频统计构建词典模型，接下来利用词典信息进行特征选择， 挑选出对网页分类来说最重要的- 些特征项，之后所有的训练集以及测试集网 页全部将由这些特征选择后的特征项来表征。接着引入了权重计算，通过每个 特征词在每个网页中的权重值的不同来区分网页问的差异，并采用向量空问模 型来进行特征表示，构建计算机可以理解和计算的网页向量模型。最后将训练 集的全部网页向量输入分类系统来构造网页分类器。 在测试阶段，同样需要对测试网页进行分词、去停用词和初步降维的操作， 但区别在于测试网页集合不再需要构建词典，直接利用训练阶段生成的词典； 不再进行特征选择，直接使用训练阶段特征提取后的特征项来表征测试集网页； 借助训练阶段的词典来计算测试集网页的逆文档频率。当测试网页以特征项构 成网页向量形式后，将该向量作为分类器的输入，分类器将输出该网页的类别。 当所有测试网页分类完毕后对分类结果进行评价。 本文将网页分类系统按功能进行了模块划分，系统总体方案设计如图2 1 所 示。 图2 1 系统总体方案设计图 9 武汉理i ：人学硕1 ：学他论文 2 3 预处理功能模块设计与实现 本文将如图2 1 所示的系统总体方案设计图i f i ，特征选择之i 讨的所有模块统 称为预处理模块，预处理模块以原始网页为输入，以词典向量为输 i ，为特征 选择模块提供原始数据。本文预处理部分程序流程如图2 2 所示。 图2 - 2 预处理部分流程图 2 3 1 基于正则表达式的网页清洗模块设计与实现 万维网上的网页除了包含了体现网页主题信息的j f 文、标题、作者等信息 外，还充斥了大量的与网页主题内容无关的广告、导航条、脚本代码、c s s 页 1 0 武汉理r 人学硕十学位论文 面装饰代码以及不计其数的h t m l 标签。因此，倘若网页中的噪音没有得到全 面而快速的清理，那么将给之后的网页分类系统带来很大的困难。针对这个问 题，赵人杰等人利用c + + 正则表达式引擎x p r e s s i v e 实现了网页清洗 3 5 1 。该方法 具有复杂度低，执行效率高的特点，因此具有实际的应用价值。 本文的网页清洗模块是基于j a v a 正则表达式来完成的，使用i a v a u t i l r c g 类 库包配合j 下则表达式来对训练集和测试集网页进行清洗。网页清沈模块程序流 程如图2 3 所示。 n 图2 3 网页清洗模块流程图 ( 1 ) 分析网页结构编写正则表达式 目前w e b 页面的来源大多都在门户网站和各类社区论坛，这类网页的共同 特点是，结构稳定单二，同时包含了大量的信息，是w e b 挖掘的主要对象【1 7 l 。 本文的训练集和测试集网页均来自新浪门户网站，通过对该网站大量网页的比 对分析发现，这些网页确实具备赵仁杰【3 5 l 所述的特征。其中最重要的一点是， 该网站的正文信息会以注释开始，并以注helper 释 结束，如同该注释所述，它为网页原始正文的发布 提供帮助。该方法简单易行，实验表明，通过对该注释代码进行初步匹配，就 能过滤新浪门户网站中几乎所有网页中的包括广告、导航栏等9 0 以上的网页 武汉理l ：人学硕十学位论文 噪音。匹配正文区域的证文表达式如下。 s t r i n gr e g e x _ c o n t e n t = ” ! _ x x s * ? p u b l i s h h e l p e r l _ 、k s l 事? n a m e = 原始j e 文 ( ? ) 附临】? ”； ，定义匹配s t y l e 网页样式的止! l ! i j 表达式 s t r i n gr e g e x _ s t y l e = ” 】? 、s 】? ”； 定义匹配h t m l 标签的止则表达式 s t r i n gr e g e x _ h t m l 2 ” 】+ | i i ； 上述正则表达式除了清除大量网页结构信息和样式信息外，还可以同时清除 网页中的图片和视频。本文在清洗完网页中的脚本代码、c s s 代码以及h t m l 标签后，增加一个过滤所有非中英文字符的网页清洗操作。j a v a 正则表达式引 擎是以u n i c o d e 来表示字符的，其中的针对汉字的集合e p 9 3 6 约等于g b k 共有 2 万多汉字，本文即使用该集合来针对非中英文字符进行过滤，正则表达式如下。 f l 匹配非中英文的正则表达式 s t r i n gr e e f i x _ e l s e = ” a - z a - z u 3 0 0 7 x u 4 e 0 0 - u 9 f c b u e 8 15 - u e 8 6 4 + ”： ( 2 ) 使用p a t t e m 和m a t c h e r 类匹配正则表达式清洗网页 本文中，每个网页加载进内存后都会以s t r i n g 类型的字符串来存储，由于 s t r i n g 类的功能有限，不能满足匹配网页标题和正文的需求，所以引入了 i a v a u t i l r e g e x 类库包，它可以用正则表达式所定制的模式来对字符串进行匹配。 它包括了两个类：p a t t e r n ( 模式类) 和m a t e h e r ( 匹配类) 。p a t t e m 类型的对象是正则 表达式经过编译后的表现模式。m a t c h e r 类型的对象依据p a t