（计算机应用技术专业论文）智能搜索中的中文网页分类研究.pdf

一 l the r e s e a r c ho nc a t e g o r i z a t i o no fc h i n e s ew e b p a g e i ni n t e l l i g e n ts e a r c h - i - i p l q b y d e n gk e b e ( n o r t h w e s tn o r m a lu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n c o m p u t e ra p p l i c a t i o nt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f l a nz h o u u n i v e r s i t yo ft e c h n o l o g y s u p e r v i s o r a s s o c i a t ep r o f e s s o rz h a n g y o n g m a y , 2 0 1 1 ， 声 j ， 一 p 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 钾种 日期：弘f ? 年月一7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 婶研 砣沫 日期：砂77 年舌月7 日 日期：加7 年f 月沙日 ， 一 ， ， 硕十学位论文 目录 摘要i a b s t r a c t il 插图索引1 v 附表索引v 第1 章绪论1 1 1 课题背景1 1 2 网页分类的研究现状2 1 2 1 国外研究现状2 1 2 2 国内研究现状3 1 3 搜索引擎概述4 1 4 本文的主要研究内容5 1 5 论文组织5 第2 章中文网页分类技术概述6 2 1 中文网页分类模型6 2 2 中文网页分类的关键技术7 2 2 1 网页预处理7 2 2 2 网页文本表示8 2 2 3 特征降维方法9 2 2 4 分类算法概述9 2 2 5 分类器性能评价1 0 2 3 本章小结1 l 第3 章基于改进d o n 树的网页净化方法12 3 1 网页净化的方法1 2 3 2d o m 技术概述1 4 3 3 网页净化的模型设计1 4 3 4 id v a 算法和m c e 算法介绍1 5 3 4 1id v a 算法思想1 6 3 4 2m c e 算法思想1 7 3 5 本章小结1 8 第4 章特征降维和相似度计算19 ， r 一 ， ， ， 智能搜索中的中文网页分类研究 4 1 特征降维方法1 9 4 2 文本的相似度计算2 2 4 3 经典相似度评价模型2 2 4 3 1 布尔模型2 2 4 3 2 向量空间模型2 2 4 3 3 概率模型2 3 4 4 改进的相似度计算方法2 4 4 4 1 最优指派模型的改进2 4 4 4 2 知网知识库介绍2 5 4 4 3 改进的相似度计算方法一h sim 2 7 4 5 本章小结2 8 第5 章基于支持向量机的层次分类2 9 5 1 层次分类概述2 9 5 2 支持向量机方法3 0 5 2 1 支持向量机基础3 0 5 2 2 支持向量机的发展3 l 5 3k 一近邻( k - n n ) 方法3 2 5 3 1k - n n 基础3 2 5 3 2k - n n 的发展3 3 5 4 基于支持向量机的层次分类模型3 3 5 5 本章小结3 4 第6 章实验设计与分析3 5 6 1 网页净化实验3 5 6 1 1 实验数据和方法3 5 6 1 2 结果分析：3 5 6 2 层次分类实验3 7 6 2 1 实验设计3 7 6 2 2 实验结果分析3 8 6 3 本章小结4 0 总结与展望4 1 参考文献4 3 致谢4 8 附录a 攻读硕士学位期间所发表的论文4 9 n ， 硕十学位论文 摘要 随着互联网技术突飞猛进的发展，网络规模j 下以指数级增长。为了更加快捷 的找到所需的信息，而不被庞大无序且结构类型多样的信息海洋所淹没，智能搜 索已成为人们获取信息的主要途径。然而，当前的全文搜索引擎虽然提供了信息 检索服务，但是自身存在着种种缺陷导致了诸如信息孤岛、主题偏向性等问题的 出现。而如果对搜索信息按照所属类别进行分类，便可以在很大程度上满足用户 搜索的需求，网页自动分类便应运而生。 目前，中文网页自动分类技术在搜索引擎的目录导航服务、信息过滤、主题 搜索、个性化信息检索、主动信息推送服务领域得到了广泛地应用。本文主要研 究内容包括以下几个方面： 首先，通过分析网页中包含的“噪声”，结合网页内容的视觉信息和几何布 局，使用改进的网页d o m 树结构和可视化分析方法识别出主题型网页的内容块， 然后在得到的内容块中提取出网页的主要内容，利用统计学的方法来去除网页中 与主题不相关的内容，最终达到有效去除网页噪声的目的。实验表明，该方法可 以在很大程度上净化网页文本，删除网页中与主题不相关的信息。， 其次，针对余弦距离在计算文本相似度时，没有考虑文本特征词之间的语义 信息，结合知网对词汇间概念的语义定义，使用一种基于改进的最优指派模 型计算文本的最大相似度。该方法通过模型将网页文本中每个特征词对文本问语 义相似度的贡献值聚合在一起，得到网页文本间的相似度值。 最后，通过研究网页自动分类的一般常用模型，并结合网页类别定义的自身 特点，构建了一种基于支持向量机的层次分类模型。该模型首先用支持向量机识 别出所有的顶层类别，然后进行二次特征选择，去除子类间的无关特征，再对每 个顶层类别用k n n 识别出子类别。实验表明，该层次分类方法可以得到较好的分 类效果。 关键词：智能搜索；网页分类；网页净化；层次分类 r 、 、 a b s t r a c t t h es c a l eo fn e t w o r ki n f o r m a t i o ni n c r e a s e de x p o n e n t i a l l ya l o n go ft h er a p i d d e v e l o p m e n to ft h ei n t e r n e tt e c h n o l o g y i no r d e rt os e a r c ht h ei n f o r m a t i o nm o r e q u i c k l y , b u tn o tt ob ef l o o d e db yl a r g e ，d i s o r d e r e da n dv a r i o u st y p e so fs t r u c t u r a l i n f o r m a t i o n ，i n t e l l i g e n ts e a r c hh a sb e c o m et h em a i nw a yt o r e t r i e v ei n f o r m a t i o n h o w e v e r ，t h e r ea r em a n yd e f e c t sw i t hs e a r c he n g i n ei t s e l ft or e s u l ti np r o b l e m s ，s u c h a si n f o r m a t i o ns i l o s ，t h et h e m eo fb i a s w em a yl a r g e l ym e e tt h en e e d s o fu s e r s ，i fw e c l a s s i f yt h es e a r c hi n f o r m a t i o na c c o r d i n gt o t h e i rc a t e g o r i e sw h i c ha r eb e l o n g e dt o ， a u t o m a t i cc l a s s i f i c a t i o nf o rw e bp a g e sw a sb o r n c u r r e n t l y , w e b c l a s s i f i c a t i o n t e c h n o l o g y h a sb e e nw i d e l yu s e di nd i r e c t o r y n a v i g a t i o ns e r v i c eo fs e a r c he n g i n e ，i n f o r m a t i o nf i l t e r i n g ，t o p i cs e a r c h ，p e r s o n a l i z e d i n f o r m a t i o nr e t r i e v a l ，s e r v i c eo fp u s h i n ga c t i v ei n f o r m a t i o n ，e t c t h em a i nr e s e a r c h 。 e dc o n t e n t si n c l u d et h ef o l l o w i n ga s p e c t s ： f i r s t l y , b ya n a l y z i n gt h e n o i s e o f w e bp a g ea n dc o m b i n e dt h ev i s u a l i n f o r m a t i o na n dg e o m e t r i cl a y o u to fc o n t e n t ，t h ei m p r o v e dd o m t r e eo fw e bp a g e a n dv i s u a la n a l y s i sm e t h o d si su s e dt oi d e n t i f yc o n t e n tb l o c k s ，a n ds t a t i s t i c a l m e t h o d sa r eu s e dt or e m o v et h ei r r e l e v a n tc o n t e n t s ，f i n a l l yr e m o v e dt h en o i s e e f f e c t i v e l y e x p e r i m e n ts h o w st h a t t h em e t h o dc a nl a r g e l yp u r i f yt h et e x to fw e b p a g ea n dr e m a i nt h er e l e v a n ti n f o s e c o n d l y , a ss i m i l a r i t y c a l c u l a t e db yc o s i n ed i s t a n c ed i dn o tc o n s i d e rt h e s e m a n t i ci n f o r m a t i o nb e t w e e nt e r m so ft e x t at e x ts i m i l a r i t ym e t h o db a s e do n o p t i m a la s s i g n m e n ti sp r o p o s e du s i n gt h ec o n c e p to fl e x i c a l s e m a n t i cd e f i n e db y ch o wn e t ) ) i nt h i sm e t h o d ，t h em o d e lg a t h e r e dc o n t r i b u t i o no fs e m a n t i cs i m i l a r i t y o fe a c hf e a t u r ei np a g ei no r d e rt om a k ea c c u r a t es i m i l a r i t yv a l u e ，t h e nm a x i m u m s i m i l a r i t yv a l u eb e t w e e nt e x t st ob eg o t f i n a l l y , a f t e rr e s e a r c h i n gg e n e r a lm o d e lo fw e bp a g ea u t o m a t i cc l a s s i f i c a t i o n a n dc o m b i n i n gt h ed e f i n i t i o no fw e bp a g ec a t e g o r i e s ，ak i n do fh i e r a r c h i c a l c l a s s i f i c a t i o nm o d e lb a s e do ns u p p o r tv e c t o rm a c h i n ei sc o n s t r u c t e d i nt h i sm o d e l ， s u p p o r tv e c t o rm a c h i n ea l g o r i t h mi su s e dt oi d e n t i f ya l lo f t h et o p l e v e lc a t e g o r i e s ， t h e ns e l e c t i n gf e a t u r e sa ts e c o n dt i m et or e m o v et h es i m i l a r i t y c h a r a c t e r i s t i c s b e t w e e ns u b 1 e v e lc a t e g o r i e s ，a n dc o n t i n u i n gu s i n gk - n nt oi d e n t i f ys u b - c a t e g o r i e s i ne a c ht o p 1 e v e l e x p e r i m e n ts h o w st h a tt h i sm e t h o do fh i e r a r c h i c a lc l a s s i f i c a t i o n h a sg o tg o o dr e s u l t s 1 1 ， 硕十学位论文 k e yw o r d s ：i n t e l l i g e n t s e a r c h ；w e bp a g ec l a s s i f i c a t i o n ；p a g ep u r i f i c a t i o n ； h i e r a r c h i c a lc l a s s i 6 c a t i o n 1 1 1 t ， 智能搜索中的中文网页分类研究 插图索引 图2 1 网页分类基本模型6 图2 2 两层词典结构模型7 图3 1 网页的标签树结构1 3 图3 2 网页净化算法模型1 5 图3 3i d v a 算法划分的内容块1 7 图4 1c h i ，i g ，d f ，m i 的比较( m a c r o f 1 ) 2 1 图4 2 树状的义原层次结构2 6 图5 1 网页文本的两层类别层次目录树3 0 图5 2 最大分割超平面与支持向量3 l 图5 3k - n n 算法的决策过程3 2 图5 4 具有两层类别的层次分类模型：3 4 图6 1 网页净化后所得结果3 6 图6 2 净化前后特征项维数比较3 6 图6 3 净化前后特征项权值比较3 6 图6 4 两种方法的m i c - a v e 和m a c a v e 比较4 0 i v ， 硕十学何论文 附表索引 表4 1h o w n e t 知识描述语言部分实例2 7 表6 1 判断文本所属类别的四种情况3 6 表6 2 目录树中各类别训练及测试的网页文本数3 7 表6 3s v m - k n n 和s v m - p 的分类结果标准评价指标3 8 v p ， ， 硕十学位论文 1 1 课题背景 第1 章绪论 近年来，随着因特网技术和计算机技术的迅猛发展，w e b 己经成为拥有数十 亿个异构的、动态的、半结构化的分布式信息空间。据中国互联网络信息中心 ( c n n i c ) 报道，截止2 0 1 0 年1 2 月3 1 日，我国网站总量已达1 9 1 万个，网页总量 超过10 0 亿。并且由于任何个人都可以创建属于自己风格的网站并发布到互联网 上，想从其中迅速有效地获取所需要的信息是非常困难的事情。因此，通用搜索 引擎理所当然的就成为部分网民获取信息的重要手段。截至2 0 0 9 年6 月底，中 国搜索引擎用户规模达到2 3 5 亿人，较一年前相比，我国搜索引擎用户人数增 长了5 9 4 9 万人，但是每个使用搜索引擎的人都期望搜索引擎能够在精确性以及 适用的信息形式上做到各取所需。 通用搜索引擎虽然具有全面的检索能力，但、是在专业性知识的检索上面往往 。不能满足用户的需求。由于网络资源的形式多种多样，同一领域的类别繁多，全 文搜索引擎不能满足用户对查询结果的个性化要求，因此专业化、专题化的信息 搜索技术逐渐成为搜索领域的热点和趋势。 为了达到良好的搜索效果，专业性的搜索需要采用一些不同于通用搜索引擎 的技术，一是需要设计特定的针对专业性搜索的算法，另一个是需要将搜索到的 网页进行有效的分类。 另外，目录式搜索引擎还需要依靠编辑人员来完成目录式搜索引擎中网页类 别的分类工作。然而，网页信息每时每刻都在发生变化，依靠人工方法组织和管 理网页分类既不现实，又会耗费大量的人力、物力和财力。据报道，截止2 0 0 8 年2 月，有7 8 ，9 4 0 名工作者参与到了著名的开放式分类目录网站d m o z 的目录分 类中 n e t s c a p ec o m m u n i c a t i o n sc o r p o r a t i o n2 0 0 8 。如此多的分类人员都会无 法避免的出现错分和漏分的情况，由于他们在分类时对待分类的网页内容理解不 一样或者对待分类的某个领域不熟悉，都会影响分类的准确性并出现分类结果一 致性不高的问题。 分析以上各类搜索引擎中面临的问题，其关键就在于如何对搜索得到的网页 信息按照类别进行自动分类。在智能搜索任务中，网页分类技术在以下方面作为 关键技术被使用：根据不同的网页类型做相应的排序规则；在链接调度中需要主 智能搜索中的中文网页分类研究 题信息页、索引链接页这样的分类，以便在下载调度时使用不同的调度策略；在 页面信息抽取的时候，需要根据页面分类的结果做不同的抽取策略；在检索意图 识别的时候，需要根据用户点击的u r l 所属的类别来推断检索串的类别等。 综上所述，网页自动分类技术在智能搜索中占据着重要的地位，它能够保持 网页类别之间良好的组织结构，简化搜索时网页的存取操作，提高信息检索效率。 1 2 网页分类的研究现状 网页格式虽然种类有很多，但所包含的信息大多是文本格式的，因此，网页 分类技术是以文本分类技术为基础的。近年来，越来越多的概率统计方法、机器 学习方法、数据抽取技术和其他的新技术被应用到自动文本分类领域中，如支持 向量机、多层神经网络等，这些方法都能对一个预先分好类的文本集进行训练学 习，获取每个类别的特征，自动生成分类规则并建立一个文本分类器。目前，主 要的文档自动分类算法可以分为三类： 1 、基于词匹配的分类法。这种方法是分为简单词匹配法和基于同义词的词 匹配法两种。其中简单词匹配法是使用起来最简单的一种文档分类算法，它先查 询文档和类别中共同出现的词条，然后再判断文档属于哪种类别。这种分类算法 的虽然使用简单，但是分类效果也很差。 2 、基于知识推理规则的分类法。这种分类方法需要大量的面向具体领域的 推理规则，这些推理规则般由知识工程专家手工编制出来。当对不同的领域进 行分类时，就需要不同领域的专家制定不同的推理规则。这种方法由于分类时严 重依赖着推理规则的质量。因此，在实际的分类系统中较少使用这种分类方式。 3 、基于统计学习的分类法。这种方法是目前用的最多的方法了，它的基本 思想是利用概率统计出文档中的特征词条，对特征词进行加权，然后生成训练集 的特征向量空间，再使用分类算法训练特征集从中归纳出特征词条和类别之间的 关系，最后利用学习到的规则对待测文档进行分类。因此，这种方法通过有监督 的机器学习来得到类别的分类信息，分类时可以达到较好的分类效果。 1 2 1 国外研究现状 国外的自动文本分类的研究较早的就从理论研究阶段进入了实际应用阶段， 并在电子会议、邮件分类等领域实现了广泛的使用，其中较为成功的有卡内基集 团为路透社开发的c o n s t r u e 会议系统，麻省理工学院为白宫开发的邮件分类系 统等。 2 硕十学何论文 随后，在智能检索技术、人工智能技术和机器学习技术的辅助之下，以及人 们对网页文本信息进行智能处理的迫切需求下，网页文本分类技术的研究引起了 人们越来越多的兴趣和关注，并在智能搜索的诸多方面取得了初步的应用成果。 虽然，网页文本分类系统在商业领域中的应用还远不如信息检索系统这么普及， 但是网页文本分类系统的实验研究早己从之前的原型开发阶段走了出来。代表性 的有网页搜索结果自动分类系统s w i s h ，多国语言新闻智能过滤系统 h e r m e s 吲等。 另外，针对基于网页文本的分类方法没有考虑网页中大量的链接信息，也 有研究者在网页局部文本分类的基础上，结合网页的结构信息对网页进行分类， 代表性的是f u r n k r a n z 阳1 用指向该网页文本周围所有的链接、段落标题附近的链 接以及上一级标题文本表示网页，并用r i p p e r 算法对文本进行分类，虽然准确 率在特定的数据集上比使用网页中的局部文本有所提高，但是方法不易推广。 c h o o n 用组合网页分类器的方法进行网页分类，其中一个分类器用网页中的纯 文本、标题和子标题文本表示网页，另一个分类器用指向该网页所有链接周围的 文本表示网页。这种方法虽然取得了较好的分类效果，但是分类过程过于繁琐， 导致分类成本增加。 1 2 2 国内研究现状 相比于英文网页分类，中文网页分类的一个重要的差别在于预处理阶段，中 文网页文本需要分词，不像英文文本的单词那样有空格来区分。但是一旦经过预 处理将中文网页文本变成特征向量空间中的向量时，随后的分类过程就和英文网 页文本的分类相同了，即随后的文本分类过程是独立于语种的。因此，目前的中 文网页分类技术主要集中在如何利用中文自身的一些特点来改进分类器的效率。 侯汉清教授最先对计算机在文本分类工作中的应用作了探讨和阐述。此后， 陆续研究产生了一些文本分类系统，其中具有代表性的有上海交通大学研制的基 于神经网络算法的中文自动分类系统，清华大学吴军研制的自动分类系统、东北 大学图书馆的图书馆分类专家系统、北大天网搜索引擎的基于k 最近邻( k n n ) 网页自动分类系统等。 同时在不同的分类方法方面也展开了广泛的研究，中国科技大学的范众等在 贝叶斯、k n n 以及文档相似性研究的基础上提出了一个超文本协调分类器呖1 ， 它的特点是适当地考虑了h t m l 文本中结构化的信息。复旦大学计算机科学与 工程系的黄萱菁、吴立德等研究了独立语种的文本分类方法，考虑了单分类和多 分类问题并以特征词条和类别之间的互信息量作为评分函数，所建立的分类模型 3 智能搜索中的中文网页分类研究 在中文和日文两个语种的新闻语料分类实验中获得了较好的分类性能哺1 。 还有人提出了基于网页风格、形态和内容的网页形式分类方法，从另一方面 对网页分类进行研究 1 。谈佳宁则针对网页分类中数据集偏斜以及t s v m 方法无 法确定无标签样本中类别比例等问题阳1 ，结合数据融合理论和模糊聚类思想，提 出了一种基于模糊聚类的半监督网页分类方法，而谷峰在传统的分类方法上，为 了的对多类别问题进行更有效的分类阳1 ，提出并设计了一个基于s h r i n k a g e 算法 的三层层次分类模型，并达到了一定的效果。 ， 1 3 搜索引擎概述 随着互联网的飞速发展，网络的信息量不断的增加着。自从搜索引擎出现以 后，人们在互联网上获取信息的方式在很大程度上依赖着搜索引擎提供的服务。 搜索引擎通过一定的策略在网络中抓取并发现信息，对信息进行提取、分类并按 照用户提交的查询词提供一个排序好的搜索列表。 目前，搜索引擎按照搜索方式的不同可以分为四个类别，分别是全文搜索引 擎，目录式搜索引擎，元搜索引擎和垂直搜索引擎。尽管搜索引擎可以分为几类， 但是每个具体搜索引擎都是由以下几个部分组成的，只是在使用时对每个部分的 侧重点不同而已。 1 、信息搜索器，它的功能是在网络中发现和搜集信息。通常会有很多个“网 络蜘蛛”自动在网络中抓取信息，它们会查看一个页面，找出页面中包含的信息， 然后再从页面中的链接出发继续去找其他的信息，直到抓取结束。 2 、索引器，它的功能是对搜集到的信息进行理解，从中抽取出文档的索引 项，并生成文档索引表。索引项包括所指文档内容的关键字和与文档相关的权值 信息。索引表一般使用某种形式的倒排表，这样通过倒排表就可以查找到相应的 文档。 3 、检索器，它的功能是根据用户的查询信息快速的检索出和查询信息相关 的文档，并对查询结果进行排序。 4 、用户界面，它是用户和搜索引擎之间的接口，通过它用户可以向搜索引 擎提出查询请求，显示查询结果，并将用户的一些行为习惯反馈给搜索引擎。 在搜索引擎的这些关键技术中，网页分类扮演着非常重要的角色，从信息索 引阶段到最终查询结果的显示，都会遇到对信息按照类别进行分类操作。 4 硕十学位论文 1 4 本文的主要研究内容 首先，本文对介绍了中文网页一种比较常见的中文网页分类模型，并对分类 模型中部分关键技术的实现原理做了简要的说明。 其次，针对模型中网页预处理阶段，结合中文网页自身特点以及网页内容几 何布局的不同，提出改进的网页d o m 树和统计学方法相结合的网页净化算法， 该方法利用改进的d o m 树和可视化分析方法识别网页内容块，并通过统计学方 法来去除网页中与主题不相关的内容块，最终得到主题内容，达到净化目的。 然后，针对向量空间模型计算文本间相似度值时没有考虑到特征之间语义信 息的问题，利用知网中对词汇语义的描述，计算文本中特征词之间的相似度 值，再基于改进的最优指派模型构造文本问的相似度矩阵，最终得到文本间的最 大相似度值。 接着，通过分析网页类别之间的层次关系，建立基于支持向量机的层次分类 模型，在得到顶层类别后进行二次特征选择，并利用k n n 分类器将待测文本划 分到所属的子类别中，最终达到有效分类的目的。 最后，通过实验对本文中提出的净化算法和层次分类方法作了验证和分析。 1 5 论文组织 第l 章介绍中文网页分类的研究背景( 包括中文网页自动分类在智能搜索中 提出的应用背景和技术背景) 、国内外研究现状等。 第2 章介绍如何根据中文网页自身的特点，建立中文网页分类的一般过程模 型，并对模型涉及到的些关键技术做了概述。 第3 章介绍在网页预处理阶段中用到的网页净化算法。详细介绍了i d v a 算法以及m c e 算法是如何提取出主题型网页的主要内容块的。 第4 章主要介绍文本特征降维以及相似度计算方法，并结合知网对词汇语义 的定义和改进的最优指派模型，改进了相似度计算方法。 第5 章介绍常用的分类算法，并提出基于支持向量机的网页层次分类方法， 通过网页分类中的顶层类别和子类别之间的差异，分阶段使用支持向量机和 k n n 分类器。 第6 章介绍网页净化和层次分类实验的设计，对实验环境进行了说明，并分 析了两个实验的结果。 最后总结了本文的工作，并展望未来下一步的研究工作。 智能搜索中的中文网页分类研究 第2 章中文网页分类技术概述 2 1 中文网页分类模型 中文网页和英文网页、普通文本是不同的，它有自身的一些特点： 1 、中文网页的内容主要使用中文书写，文字之间包含着一定的语义信息，不 像英文中单词之间存在着自然的间隔。这就需要对网页中的文本内容进行分词处 理，而分词的好坏将直接影响到文本特征的提取，并最终影响分类器的效果； 2 、与普通文本不同的是，网页中使用了大量的超文本标记和超链接，里面包 含了很多各种各样的h t m l 标签。在分类过程中，可以利用这些信息来改进分类 的质量。比如包含在 ， 等标签内的内容通常要比出现在网页 正文 标签内的内容要重要一些，一般都是利用这些信息来改进特征权值的 计算。 3 、网页通常都包含着大量的“噪音”，比如各种各样的广告，导航栏以及版 权保护等与主题无关的信息。有时同一个网页甚至会包含多个不同的主题。因此， 在进行分类之前都要清除这些“噪音”，得到净化后文本再进行后续的分类步 骤。结合中文网页的特性，图2 1 给出了中文网页自动分类的一般过程州： 图2 1 网页分类基本模型 仔细分析以上分类模型后发现，在中文网页分类的过程中，包括几个关键步 骤：网页预处理、网页文本的向量表示、特征项降维、网页文本间的相似度计算 和分类算法，这些关键技术的实现对最终的分类效果都有定程度的影响。 硕十学位论文 2 2 中文网页分类的关键技术 2 2 1 网页预处理 网页预处理包括消除网页噪音，包括去掉一些标记，例如h t m l 中的t a g ，去 除各类广告，设计人员的注释以及版权申明等，并从网页中挖掘出主要的内容块。 本文第三章将对网页预处理中的网页净化算法做深入的研究。 另外，在得到网页内容的主要信息后，由于文本的词汇之间没有明显的切分 标志，所以需要分词得到文本的特征词条。 汉语分词是智能检索、机器翻译、文献标引以及自然语言理解与处理的基 础，也是中文文本分类最基本的步骤。目前国内的分词系统中所采用的理论依据 可以分为三类，分别是基于字符串匹配的方法，基于理解的方法和基于统计的方 法。实际中使用的分词算法通常是其中两类分词方法的结合，这样即可以提高分 词的效率，也能够识别新词。 吴涛等1 提出一种改进的统计与后串最大匹配的中文分词算法，该算法利 用基于词典的有穷自动机后串最大匹配算法以及博弈树搜索算进行分词，再使用 图2 2两层词典结构模型 改进的双向m a r k o v 链的统计方法对词库进行更新，在分词准确性以及对生词的辨 识上取得了一定的效果。而陈桂林n 幻等提出了一种改进的快速分词算法，在快 速查找两字词的基础上利用近邻匹配方法来查找多字词，明显提高了分词效率。 从目前对分词的研究可以看出，分词算法在理论上已经是比较成熟了，在 分词的方法上有较简单的也有相对复杂的，比如j 下向最大匹配，反向最大匹配， 双向最大匹配，最短路径算法，语言模型方法等。通常这些分词算法都是以庞大 7 智能搜索中的中文网页分类研究 的词典为基础，再结合高效的词典结构和相应的分词算法得到比较满意的分词结 果。 国内比较知名的商业搜索引擎，比如百度，在经过仔细研究后，发现其使 用的分词算法很可能是一种双向最大匹配算法。例如，当向百度提交查询“古希 腊肉 时，百度的分词结果是“古希腊，肉”，所以如果是正向最大匹配，那么 结果应该是“古希腊，肉”，而如果是反向最大匹配，那么结果应该是“古希， 腊肉。 从这个例子看，好像是用了正向最大匹配算法。但是在提交“白天天向上 时，正向最大匹配的结果是“白天，天，向上，反向最大匹配的结果是“白， 天天向上 。百度输出的是后者，说明采用的是反向最大匹配。从这点便可以猜 测百度采用的是双向最大匹配分词算法。 值得注意的是，当正向匹配的结果和反向匹配的结果不一致时，百度采取 最短路径方法，也就是切分的片断越少越好，比如“古希腊，传，说明和“古 希腊传说，明 相比选择后者。如果正反向匹配后，切分的片断数也相同，则默 认选择正向最大匹配算法。 2 2 2 网页文本表示 网页文本中的内容基本上都是用自然语言呈现出来的，文字之间包含着语 义，计算机不可能直接对其进行处理，所以必须将文本中的内容特征表示为计算 机能够处理的格式。向量空间模型是长期以来在自然语言处理、信息检索等领域 应用较广且效果比较好的文本表示模型。除此之外，其他一些能够用来表示文本 的模型还包括布尔逻辑型、概率模型、潜在语义索引模型以等。 向量空间模型的基本思想是把文档表示为以特征词条的权重为分量的向量 形式 应的 y ( d ) 义为 运用 中出 硕十学位论文 皇皇詈量暑皇詈曼皇皇詈! ! ! 皇量鲁鲁詈皇詈詈鼍置詈皇皇量皇皇曼鼍昌皇暑量皇鼍曼毫皇! 曼鼍量葛詈置皇詈! ! ! ! 曼皇皇墨鼍量曼! ! ! 皇毫皇鲁基詈皇曼皇皇詈曼i i 詈鼍毫皇詈葛! 曼! 葛 文本经过预处理后进行词频统计，最终表示为上面描述的向量。从t f i d f 公式的定义可看出，某一项词条出现在文档集合中的次数越多，则该词条区分类 别的能力就越低，其权值就越小；反之，如果某一词条出现在一个文档中的频率 越高，说明它区分文档内容属性的能力就越强，其权值就越大。 在网页分类过程中，网页的标题、副标题以及锚文本中的词条项一般都包含 了有关文本类别的重要信息，在对这些词条项进行加权时应该给予较高的权重。 2 2 3 特征降维方法 网页文本经过预处理，分词并去除停用词和高频词后，表示文本的向量空间 的维数也是相当大的。为了在分类后期训练分类器时降低其复杂度，需要对文本 的向量空间进行特征降维。 特征降维对分类过程中的训练时间以及分类的准确性都有比较明显的影响。 所以，文本特征空间的降维操作是文本分类准确率和效率的关键。目前，特征降 维方法主要有两类，分别是特征选择和特征抽取n 3 1 。 特征选择就是通过构造一个特征选择函数从特征集r = l i , t ：， 中选择一个 真子集t t l ，f 2 ，岛1 ，使得( d d ) 。其中，d 表示原始特征集的大小，d 表示特征 选择后的特征集的大小。选择的过程一般都是通过计算每个特征项的函数值并按 函数值的大小进行排序，最终选择函数值较高的一些特征项构成一个特征子集。 可以看出，特征选择的过程一般都不会改变原始特征空间的性质，只是通过 筛选的方式从原始特征空间中选择一部分较重要的特征，组成一个新的低维的特 征空间。 特征抽取通常也叫特征映射，通过映射的方式将原始向量空间中的特征变换 到新的特征空间，它不但可以降低文本向量空间的维数，提高分类器的速度和精 度，并且可以防止过拟合现象。 2 2 4 分类算法概述 网页文本分类通常都是一个有监督的机器学习问题，对网页文本进行分类的 过程一般可以分为对分类器的训练和利用分类器对待测文本进行分类这两个阶 段。其中使用某种算法训练分类器的工作是统计训练文本集合中的每篇文本对应 的词条项，然后计算出类别向量矩阵并对矩阵进行归一化处理，最后保存训练得 到的向量表，同时也就得到了分类知识库。在对文本进行分类时，则是依据训练 得到的分类知识库，并用特定的分类算法对待分类文本进行分类。目前，用到的 分类算法比较多，主要有以下几类： 9 智能搜索中的中文网页分类研究 1 、多分类器融合的方法，多分类器融合顾名思义就是使用多个分类器对待分 类文本进行分类判断，然后将各个分类器判断的结果进行加权结合来决定待分类 文本的最终类别。常见的多分类器融合技术有投票机制、证据理论、贝叶斯方法 g r 1 5 】_ 1 4 寸 o 2 、基于模糊一粗糙集的分类方法，该方法针对文本分类中出现的类别之间边 界模糊不可分和待测文本属于多个类别引起的分类重叠等问题，有效的结合模糊 理论和粗糙集理论在处理不确定性问题方面的能力解决文本分类中出现的这些 偏差m 1 。 3 、基于群的分类方法，该方法通过模拟鸟群或者蚁群在觅食时的行为和数据 挖掘的概念对分类的规则进行发现。这种方法可以分为两类，一类称为蚁群优化 n 7 1 8 1 ，另一类称为粒子群优化n 引。 4 、潜在语义分类模型，它是以潜在语义索引模型为基础，通过从原始文档空 间中的词信息来得到一个语义空间，该特征空间保留着原始文档空间中最主要的 全局信息，并将原始文档的类别信息和相关的词信息一起考虑构建模型，得到更 适合文本分类的语义空间心们。 5 、基于r b f 网络的分类模型，该模型将监督方法和非监督方法结合在了一起， 通过两层映射关系对分本进行分类，第一层映射由非监督聚类将文本聚集出多个 簇，得到文本到簇的映射；第二层映射是簇集到目标类集合的映射。一般对每个 簇定义一个径向基函数，利用这些函数的线性组合来拟合训练文本，并在计算权 值时加入权值惩罚项，以避免过度拟合。心 除了以上常用的分类算法外，用的较多并且技术相对成熟的分类器主要有 支持向量机和k 一近邻方法，支持向量机在小数据集的分类中，具有较高的分类 准确率。而k 一近邻是一种懒学习方法，它在分类时不需要学习，只是和周围的k 个近邻样本做比较，并选择最相似的样本所属的类别为自身所属类别。本文将在 后面章节中对支持向量机和k - n n 分类方法作详细的介绍。 2 2 5 分类器性能评价 利用各种分类算法建立分类器以后，整个分类系统就建立起来了，因此为 了能够发现每一个分类器或者分类算法的好坏，就需要用一些指标来评价，以便 给出依据来对分类系统进行改进并完善所使用的分类系统。目前，用的比较多的 评价指标有分类结果的查准率和查全率，宏观f l 值等。 1 0 硕十学位论文 2 3 本章小结 本章首先介绍了中文网页与英文网页之间的差别，得出中文网页有自身的 特点。接着，基于这种特点，给出了中文网页自动分类的一般过程模型。在研究 分析模型后，发现中文网页分类主要涉及到几个关键的技术，比如，网页预处理， 网页文本内容的表示，特征降维，网页分类算法等。最后，对其中几个关键技术 做了简要的介绍，以便为后面章节中的叙述做好铺垫。 智能搜索中的中文网页分类研究 第3 章基于改进d o m 树的网页净化方法 在网页的分类过程中，需要首先得到网页中的文本信息，然后才能进一步对 文本进行后续处理。因此，需要在预处理阶段去除网页中的噪声信息，并挖掘出 网页的主要内容。但是，一般的主题型网页中，主要内容都被很多无用的信息所 包围着，比如，导航条