（通信与信息系统专业论文）基于链接分析的web组合分类器研究.pdf

摘要 论文从网页自身的结构化信息出发，分析和改进w 曲分类的相关环节：网页 表达、特征选择和分类算法；从网页之间的链接信息出发，讨论了结合分类技术 的排序算法，并在此基础上，综合考虑结构化信息和链接信息，将基于链接分析 的级联组合分类器作为研究重点主要工作包括以下方面： ( 1 ) 提出了标签词频加权标引法，综合考虑不同标签中的特征词反映网页主 题的差别以及特征词在整个特征空间中的比例，对网页表达进行改进 ( 2 ) 研究一种基于一定类别空间阈值的m i + c h i 联合特征选择法，该算法弥 补了c h i 选择法的缺陷：过滤指定类别中出现频率低，其它类别中出现频率高 的词；提高特定类中出现的低频词的权重 ( 3 ) 提出了基于n g i 锄模型对n 莉eb a y c s 的改进算法，一定程度上改进 n 砬v eb a v 豁的特征相关性问题 ( 4 ) 研究一种使用分类技术改进的排序算法借助预分类技术增强p a g e 黜m k 与h i t s 算法在计算网页中的链接所指向页面的重要性的能力，使得重要程度高 的网页对于同一类别或相关类别的其它网页具有更好的类别调整能力，进而提高 网页分类的精确度 ( 5 ) 提出了两种可行的组合分类器策略( s v l 悯、n b 帅旧) ，分类器由两 层分类器级联组成，传统纯文本分类器作为一级分类器，基于超链接分析的分类 器作为二级分类器，前一级分类器的分类信息用于指导下一级分类器的训练和分 类过程 ( 6 ) 研究一种基于类别归并的组合分类方法，对训练集的一些小类别和交叉 类别进行归并，重组类别集，采用二级分类器对原始训练集和新训练集进行分类， 解决由训练信息过少，类别信息交叉带来的训练不均衡问题 关键词：词频加权，n 元文法，链接分析，组合分类，类别归并 a b s t i a c t t l l i sp 印盯锄a l y s 豁锄di i l l p r 0 v 懿w e bc l 弱s i f i c a t i o nt i c c ：h o n o l o g yb a s e d w e b s t r u c t i | i 司i n f 0 珊撕o n ，鲫c h 嚣：w e b 懿p 蕾鹪s i o n 、f e 毒曲心s e l e c t i o na n dc l a 豁i f i c 撕 a 1 9 0 r i m m ；t h cr a n ka l 鲥t l l mb 勰e d w e ；bd 够s i f i 训o nt e c h i l o g yi sd i s c i 塔d b a s e d0 nh y p 盯i i i l ki i l 细m a 虹，触m o r e ，t l l ea i t i c l ef 0 c 嘴s c q u c o m b i n e d d 嬲s i 丘e 璐b 鹪o do nh ) 1 e rl i i 墩觚a l y s i sc o m b i l l i l l gt h e 灿c 删觚d h ) 哩) e rl i r l l 【 i i l 矗脚a 6 0 n t h cm a i l ic o n 缸j b l l ：t i o n si n c l u d e ： ( 1 ) a c c o r d i i l gt ot 1 1 ed i f l j 锄m o fd i 岱静e n tt a g s 咖r i b u t i o n 觚dm ep p o r t i o n 0 f 做曲s 】p a 姐a 1 9 0 r i t l l i nb 舔o d 伽缸喀舭q u 触c yw e i 咖c di sp m p o s e dt o i i i l p r o v e 廿l ew e b i p a g ee x p r 豁s i o n ( 2 ) a na l g 砥t t 姐t 1 1 a tm i + c h ib 嬲e d 傩c l 嬲ss p a c c l | 髑h o l di sd i s 哪s e dt o 触c h u pm cd c 俄to f c h i ，m em i + c h if e 舭s e l e c t i o nc 觚矗l t 贸m ew o 豳n l a t h 孙r eh i g h 置b e q u e n c yi ns p i e c i a lc a t e g d 矗z a 缸o nb 毗1 0 wf e q u e n c yi nm o s tc a t e g 嘶z 硝0 n s ，a l ， i n 也ew c i g h to ft h el o w 自e q u c yw o r di l is p i a lc a t e 9 0 r i z a t i o n ( 3 ) an a n eb a y 髂a 1 9 0 r i 也mb 弱c d n 一笋a mm o d e li sp r o p o s c dt o l v et l l c 邮b l 锄哪e db yf i e 砷盯鹤r e l a t i v i 够 ( 4 ) a 咖k i n ga 1 9 0 r i t l l l ni l i l p m v e db yd 舔s i 矗c a l i i sd i s c 峭s c dt oe i l l l 觚t l l c a b i l i t ) ，o fc a l c u l 蚰gm ei m p ( 斌锄c eo fw c b p a g ：e m ei n l p o i t a n tw 曲l p a g co fn l eg i v e n 钟埘撕v ed 弱sh a v e 纰b e 懈a b i l 时t 0 嫡似m ed 弱s i 五c 撕sr 咖l t 谢m 龇 a 1 9 0 r i n l m ( 5 ) n 旧d 勰s i f i e 鹤c o m b i n a l i o ns b 眦e g yi sp r o p o s e di l i 廿坞a r t i d e ( s v m 斗- n b 、 n b + n b ) ，m e 姗_ l l 缸矗勰s i 6 盯i sc o n s t i t u t e db yt w os e q u d 越s i f i e 您，n 蟛缸r s t c l 勰s i f i 盯i s 锄d i t i o n mt e x tc l 弱s i 6 廿地s e c o n do i sad 鹤s i f i e fb 勰e 佃h y p 盯i i i l l 【 如a 1 ) ，s i s ，t h ef i l s to n ep r 0 讥d ee l 锄髓i 协盯c l 嬲s i f i 训o n 托s u l t st og u i d em cs 饫姗n d o n e ss 锄y 觚dc l 鹤s i 石c a t i o n ( 6 ) am e t h o db a s o do nd a s ss e t1 1 i l i t c di sd i s c u s s o dt o 他c 咖l c tn l et e s ts e t 细 l 诎l g 也ei n f 0 m a t i o n a r c i t ) r 锄dc s v 盯p r o b l e m ，a 舢l t i c l 觞s i 6 日i s 璐e dt 0 p l 嘲s 也eo 五百n a lt 销ts e t 雏d 廿l en e w o n e k e y w o r d s ：w o r d 自e q u e n c yw e i 曲e d ；n - g r a m ；h y p e rl i r l l 【锄a l y s i s ；c o m b i i 埘 d 鹤s i f i e 璐；d 够ss e t 瑚1 i t e 海南大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写 过的作品或成果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。 本声明的法律结果由本人承担。 论文作者签名： 日期：a 一手年6 月醇日 7 学位论文版权使用授权说明 本人完全了解海南大学关于收集、保存、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权海南大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。本人在导师指导下完成的论文成果，知识产权归属海 南大学。 保密论文在解密后遵守此规定。 论文作者签名： 日期：螂年厶月胁日 导师签名： 日期： 圜 年月日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的学位论 文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中规定享受相关 论文作者签名： 日期：又喵年 导师签名： 日期： 1 引言 1 1 研究背景 网页分类是使用机器学习的方法实现网页类别的自动标注，可以在较大程度 上解决信息杂乱问题，方便用户准确地定位所需要的信息和分流信息例如目录 导航式搜索引擎采用网页分类技术，事先对网页进行索引，帮助用户沿着分类目 录的层次逐步进入自己感兴趣的主题，进而找到所需的信息 网页分类源自文本分类技术，但网页分类问题相对文本分类更加难以处理， 要考虑更多因素，这一特点主要是由网页结构化特性决定的网页使用超文本语 言设计，它包含丰富的文本信息、标签结构信息、超链接信息、元数据信息、图 片信息、音频信息和视频信息等以往的处理方式是根据标签名，标签位置、标 签属性的不同对文本进行加权处理，从而改进网页分类的效果，但没有仔细考虑 标签中的特征词相对于同一标签的其它词在分类效果上的差异因此能否合理的 利用网页的结构化信息，结合传统的文本表达方式在分类过程中正确地描述网页 是提高网页分类性能的关键 网页同时也包含大量的冗余信息，与普通文本相比，网页中有随意性的代码、 非主题文本、各类广告、作者注释，版权申明等无用信息，如何从结构化文本中 有效地提取特征，并处理掉“噪声”特征给分类带来的负面影响，成为提高网页分 类质量的另一关键 网页分类的研究存在一个值得关注的问题：由成千上万的网页组成的互联网 包含了传统数据环境所没有的丰富信息，即互联网的链接拓扑结构在w 曲环境 中，几乎所有网页之间都是通过超链接来建立联系的超链接一方面可以引导网 页浏览，另一方面也反映了网页之间的主题具有一定的联系：如果把网页看作节 点，页面之间的超链接看作边，那么整个w 曲环境可以看作一张巨大的有向图 整个w 曲图中绝大多数的网页可以通过超链接进行连通并且存在大量的相互连 通的w 曲子图一个网页的设计者把某个链接加入自己的页面中，一般认为他们 在内容或某些特性上具有一定的相关性这种有意识或无意识的网页之间的相互 链接很容易形成一个具有鲜明主题的网页集合因此有效利用超链接文本、超链 接周边文本以及同属一个w 曲子图的多个网页主题内容进行网页分类，对提高 网页分类的准确率具有重要作用 在w 曲环境下，网页分类是组织与揭示网络信息资源的重要方法，它不仅适 用于文本信息，而且可以用来解决非文本信息、超文本信息等的组织与揭示问题 许多大型门户网站都基于主题、当前热点问题和用户的兴趣爱好，建立自己的分 类体系，如网易、搜狐、m s n 等，最直接的目的在于提供方便用户浏览信息的 网络分类目录；搜索引擎在海量网页中进行检索，往往会返回一个庞大的结果列 表，原因是基于关键词的搜索会返回包含该关键词的所有网页，而这些网页经常 跨越多个领域，其中许多内容根本不属于用户感兴趣的范围，研究和改进网页分 类技术，对向用户提供更有效的信息，提高搜索的准确性有重要意义 1 2 研究发展现状 当前在网页分类领域的研究中，国外具有代表性的有：s o u m 饥c h a l ( r a b a r t i 【l l 基于网页的局部信息用纯文本分类器对网页进行粗分，接着利用相邻网页的类别 信息去改善分类的潜力，通过多次考虑相邻网页的类别，对粗分网页的类别进行 迭代调整实验证明在错误率上有明显提高，但该种方法的问题是计算量大，并 且不适用于网页间链接不频繁的情况m a r kg r a v 锄【2 】等提出用有向图来描述超 文本间的结构，并把网页相应的描述成图的节点，网页间的超链接对应图的边， 使用基于文本单词的统计分类器和考虑了超文本之间存在链接特性的一阶逻辑 规则对网页进行分类，这种算法的缺点是归纳速度慢，并且用学习到的规则进行 分类时，通常会出现查准率高，查全率低的现象y i m i n gy 缸g 等【3 】提出了五种对 分类器有重要影响的超文本规则，他们发现：将链接所指向的相邻的网页的文本 加到链接所在的网页对分类的作用随着数据集的不同而呈现有益或有害性，而从 相关的网站中提取出m e t a 标记信息对改善分类精度非常有用因此应该分析不 同分类算法所适用的w 曲数据环境，并测试组合分类策略，选取最优组合方式 提高分类准确率 国内具有代表性的有：范琰等【4 】针对超文本机构中的结构特征，分别利用超 文本页面中的文本信息和结构信息，提出用n 柳eb a y 锵方法协调分类的方法 秦兵等【5 1 在贝叶斯分类的基础上，通过对区分性好的词增加权重，对分类性差的 词降低权值，提出利用类别密度函数似然比来增加特征词的可分性信息，基于统 计进行中文网页分类y ap e l l g 等人【6 】认为超链接、m e l 隗标签等为超文本分类提 供了丰富的信息，仅仅单独利用y i m i n g y 撕g 提出的五种超文本规则，不能集成 所有信息，因此，通过综合利用不同的规则，提出基于c o w e i 曲t i n g 和 m u l t i i n f 0 咖撕o n 的超文本分类算法其思想是：在分类之前，解析超文本文档中 的标题、超链接以及标签等信息，在分类过程中，对这些信息进行c o w e i g h t i n g 联合加权处理 2 1 3 研究内容与结构安排 现在的网页分类技术实现细节，主要分为两类：基于纯文本分类技术进行分 类和基于组合分类器进行分类基于纯文本形式分类的依据是将文本从网页的 标签、链接、脚本、样式表中脱离出来，采用传统的文本分类处理技术进行分类 这种处理方式忽略了网页自身含有的丰富标注、描述和网页之间的拓扑信息因 此这种分类器性能较差而基于组合分类的技术和传统文本分类的最大不同在 于考虑了网页中的超文本结构和链接信息对分类结果的影响，因此分类效果比前 者要好 论文对网页分类的相关技术：网页表达、特征选择、分类算法等环节进行分 析与改进：网页表达方面，由于网页的结构化特性，传统的处理方式是根据标签 名，标签位置、标签属性的不同对文本进行加权处理，从而改进网页分类的质量， 但没有仔细考虑标签中的特征词是否对网页分类有贡献论文综合考虑不同标 签中的特征词反映网页主题的差别以及特征词在整个特征空间中的重要程度，提 出了标签词频加权标引法；特征选择方面，基于一定类别空间阈值，用m i + c h i 组合选择法弥补c h i 选择法的缺陷：过滤指定类别中出现频率低，其它类别中 出现频率高的词，提高特定类中出现的低频词的权重；分类算法方面，基于 n q 狮模型对n 酊v cb a y 伪算法进行改进n 抓，eb a y 岱实际上是一种u n i 蓼缸l 模型，它假设特征词之间是相互独立的，并不适应特征之间相关性较大的情况， 使用n 辨锄方法对其进行改进，可进一步提高n 孙，cb a y c s 的分类精度，考虑 到计算的复杂度，使用的是b i 廖锄模型 论文重点研究链接分析算法和组合分类算法：( 1 ) 使用链接分析算法来调节 网页分类，主要考虑到在网页分类过程中，需要使用链接所指向网页的类别来调 整分类结果因此借助排序算法p a g c r 柚k 与h i t s 的优势，对训练集的特定类别 集基于链接进行扩展，计算网页中的链接所指向页面的重要性，使得重要程度高 的网页对于同一类别或是相似类别的网页具有更好的类别调整能力( 2 ) 使用级 联分类算法进行分类，分类算法由两层分类器级联组成，前一级粗分分类器为后 一级分类器提供分类信息，指导下一级分类器的训练和分类过程基于级联分类 思想，制定两种可行的组合分类器策略( s + n b 、n b + n b ) ，这样一方面可以 避免迭代调整带来的计算量大、收敛速度过慢问题；另一方面可以避免一阶逻辑 规则所导致的归纳速度慢、查准率高、查全率低问题，实验证明提出的改进方法 能有效的提高网页分类的整体性能 论文分为五个章节，对网页分类环节中的基本概念进行说明，并基于以上研 究内容进行展开阐述： 第一章引言，综述了本研究课题的背景、应用领域和发展现状介绍论文研 究的主要工作和论文的结构安排 _ 。 第二章系统的描述网页分类系统的流程，并介绍网页分类中的文本表示方法、 特征的可分性、特征选择、分类算法，重点介绍基于标签词频加权的网页表达方 法、m i + c h i 组合特征选择方法的改进、结合n g h m 模型的n a v eb a y 鹤分类 算法 第三章详细介绍了p a g e r a i l l 【和h i t s 两种排序算法，并基于链接分析思想， 提出两种结合网页分类技术的改进排序算法 第四章从组合分类的角度出发，简要介绍并联组合分类技术，侧重介绍级联 组合分类技术的两种新方法，即基于链接分析的n 柳eb a y 璐级联组合分类与基 于类别归并的级联组合分类，最后进行实验分析，验证算法的有效性 第五章对全文所做工作进行总结，基于研究要点提出将来待改进的方面 4 2 w e b 分类技术 2 1 网页分类概念与流程 网页分类与文本分类的最大不同在于网页自身具有的超文本结构化特性，该 特性包含文本信息、标签结构信息、超链接信息、元数据信息、图片信息、音频 信息、视频信息等由于包含丰富的信息，如何正确并完整的描述一张网页，使 页面中的更多的语义信息能从其表达方式中体现出来成为研究网页分类的难题 之一排除掉视频、音频、图片等多种多媒体信息，网页分类与文本分类具有密 不可分的关系：网页的标签结构信息本质上是通过结构信息中所包含的文本信息 表现出来的，即通过浏览器解释后的超文本文档直接提供给用户的文本视图效 果；元数据信息的内容无法展现给用户，但其鲜明的主题文本描述或关键字往往 能提供更有效的信息；超链接信息作为一种引导网页浏览的实体，体现了网页之 间的文本信息联系，其潜在的分类功能最终也需要通过文本信息来间接体现 2 1 1 网页分类的概念 网页分类的概念是：分析待分类网页中的特征，使之与各类别中对象所具有 的共同特征进行比较，然后将网页归为特征最接近的一类并赋予相应的分类号 这种分类实质上是一种映射过程，它将未标明类别的网页映射到已有的类别中， 该映射可以是一对一映射，也可以是一对多映射用数学公式表示：厂：尸一c ， 其中p 为待分类的网页集合，c 为类别集合 在网页分类方面占主导地位的技术是基于知识工程的分类方法，该方法由专 业人员手工编写分类规则来指导分类，时常需要人工介入调整分类结果基于机 器学习的方法在近年来已逐渐取代了前者，成为网页分类技术的主流基于机器 学习的网页分类方法通常包含两个即相互独立又彼此联系的基本过程，即离线训 练过程和在线分类过程1 7 j ： ( 1 ) 离线训练过程的主要任务是对文本进行必要的分析和处理，找到有效概括 其类别信息或鉴别信息的特征表示，从而从训练集( 已知类别的网页) 中学习分 类知识，构建分类器 ( 2 ) 在线分类过程的主要任务是将待分类的网页转化为与训练集相同的表现形 式，并用训练好的分类器对其进行分类为确保分类器的分类性能，需要不断地 对分类器的实际分类结果进行评估，并根据评估结果对原先的文本表示方式和分 类器进行必要的调整，使得分类效果达到最优，即一个反馈的过程 2 1 2 网页分类的流程 网页分类系统一般分为3 大模块( 如图2 1 所示) ，3 模块主要处理两个集合： 训练网页集与测试网页集：( 1 ) 网页预处理模块，这其中包括：网页集的解析、 去噪、规范化、提取和分词等步骤( 2 ) 特征处理模块，特征处理首先对两集合 的特征空间进行降维，降维方法可为：全局降维与局部降维，进一步又可分为： 特征选择和特征重构，然后采用降维后的特征向量来对数据集中的网页进行表示 ( 3 ) 分类算法模块，该模块是网页分类的核心，即如何构建分类模型对之前两 个模块处理后的特征向量进行分析、比较和计算，将网页赋予相应的类别号分 类算法包括：n a 蕾v eb a y e s 、l b c c h i o 、叮n 、s 讧、决策树等方法 2 2 网页文本表示 网页预处理模块特征处理模块分类算法模块 图2 1 网页分类流程图 2 2 1 文本表示方法 与所有的机器学习问题一样，要让计算机自动对文本分类，就需要把一篇文本 表示成一个个的特征，比如词、字、n 舯m 、词组、概念等很显然，这将丢 失大量关于文章内容的信息，但是这种表示可以使文本的处理形式化，并且可以 在文本分类中取得较好的效果 2 2 1 1 文本特征表示 ( 1 ) 词 6 词是文本分类中使用最广泛的特征对英文及类似的语种来说，因为这些语种 采用空格或标点将词隔开，所以词的获取相对简单但对汉语及类似语种来说， 由于词与词之间没有空格，因此词的获取必须通过分词来实现 由于文本中很多词对分类没有贡献，比如汉语中的“的、地、得 与英语中 的“a 、a n 、t h e 一这些就是通常所说的停用词因此，为了节省处理时间，通常 在预处理阶段采用一个停用词表把这些停用词过滤掉 ( 2 ) n g r 锄 n g 衲m 是一种独立于语言的文本表达方式字符串方式n c 衲m 方式根本 不考虑组成文本的语义单位是字、词还是词组，而是将整个文本看成是由不同字 符组成的字符串，因而可以方便地表示包括汉语、阿拉伯语在内的各种语言文本 文档 n g 衲m 有其缺点，就是计算量随n 的增大而增大，同时n ( 衲m 表示还存 在着数据噪声大，易于过学习等缺点 ( 3 ) 词组 词语表示法的一个显著的缺点是，原始文本中的大量信息丢失，比如，段落、 句子、词序等都被忽略了这结果就是虽然满足学习算法所需要的连续性，但扰 乱了人们正常的思维连续性词组表示法的一个目标就是为了尽量挽回一些词语 表示法所丢失的有用信息 词组表示法在自动文本分类领域得到较为广泛的应用，取得一些成果，但总 的来说，其表示能力并不明显优于词表示法原因在于，词组表示法虽然提高了 特征向量的语义含量，却降低了特征向量的统计质量，使得特征向量变得更加稀 疏，难以从中提取用于分类的统计特性 ( 4 ) 概念 概念相比词语而言，具有更高的抽象性一个概念可以对应文中的一个词，也 可以对应若干个有语义联系的词从原理上说，采用概念作为文本特征有许多好 处首先，将关键词空间映射到概念空间会大大降低分类空间的维数，从而节省 分类的训练时间，也节省了分类期间用于相似度比较的时间因此基于概念的文 本分类在时间效率上要优于基于关键词的分类；同时将具有同义关系的关键词映 射到一个概念，可以避免一个重要的分类特征因为采用关键词的分散而削弱其分 类的权重；再次，将一个多义关键词映射到多个概念，可以避免只采用关键词作 为特征所产生的特征歧义，即虽然都是采用同一个，但所代表的意义完全不同， 从而提高分类准确性 概念表示方法的缺点是：概念建立极其复杂，往往依赖于专家或者领域专家， 这事实上包含了很强的人为干预 7 2 2 1 2 文本表示模型与相似度计算 ( 1 ) 布尔模型( b o o l e 锄m 0 d d ) 布尔模型是一种比较简单，但非常通用的检索模型早期的文献检索系统大都 采用布尔模型布尔模型大体可分为两类：经典的布尔模型和扩展的布尔模型 经典的布尔模型建立于集合论与布尔代数的基础之上嗍，主要应用于信息检 索中在这种模型中，每篇文档表示成文档中出现的特征集合，也可以表示为特 征空间中的一个向量，向量中每个分量权重为o 或者1 经典的布尔模型中查询 与文档的相关性只能是0 或者l ，满足查询q u e r y 中的所有逻辑表达式的文档被 判定相关，不满足的被判定为不相关 经典布尔模型通常只能用于信息检索中计算用户查询与文档的相关性，而不 能利用该模型计算两个文档更深层面的相似度，无法在更多的文本处理应用中使 用在经典布尔模型的基础上，研究人员重新定义了a n d 与o r 操作符，使相关 性成为 o ，l 】之间的数这便是通常所说的扩展布尔模型到目前为止，学者们已经 提出了众多扩展布尔模型，比如f u z z ys e t 、w a l l 昏心a f i 、p n o m 、i 而n i 协o i 圮 等k 认为s a l t o n 提出的p n o m 模型具有相对更优秀的性能 假设文档d 可表示为d = ( d i ，d 2 d 。) ，查询可表示为q = ( g i ，9 2 ，g 。) ，其 中d ；和g ，分别表示第f 个特征词对文档内容和查询内容的贡献程度，d 。，口；在区 间 0 ，1 】上取值则p - n o 肌模型定义相似度计算公式如下： 删见妒卜 止业箬并去掣螋r 娩2 ig l + 9 2 + g l 其中l p 在实际使用中p 的取值由实验得出，取值范围一般为【2 ，5 】当参数 p 趋近于无穷时，p n o m 模型相当于经典布尔模型；而矿1 时相当于向量空间 模型 ( 2 ) 向量空间模型( v e c t l o rs p a c cm o d e l ) 向量空间模型将文档表示为特征词向量，向量中元素对应词频，丢弃特征词在 文档中的顺序信息使用v s m 的算法大多属于基于词频统计的学习方法，如朴 素贝叶斯( n a i v eb a y e s ) 、支持向量机( s v m ) 、k 近邻( 州) 、神经元网络( n n ) 和r o c c k o 等特征词通常要进行特征降维，文档向量根据特征词权重对词频权 值进行调整 最初的特征权重计算方法是0 、l 赋值法，也就是布尔权重布尔权重无法体现 特征词在文本中的作用程度，所以逐渐被更精确的词频代替词频分为绝对词频 和相对词频绝对词频，即使用特征词在文本中出现的频率表示文本；相对词频 为归一化的词频，其计算方法主要用t f d f 公式 其中t f 是特征词在文本中的绝对频率，而i d f 表示特征词在文本中的内频 数t f 越大，此特征词在文档集中出现的范围越广，说明它的重要程度越高；d f 越大，此特征词在文档中的分布越集中，说明它在区分该文档内容属性方面的能 力越强存在有多种t f i d f 公式，一种比较普遍的t f i d f 公式为： 职厕= 趟筹一 眩2 e 孑矿( f ，孑) x l o 甙一+ o 0 1 ) j z 。 其中矿( f ，孑) 为特征词f 在文本孑中的权重，而矿( f ，孑) 为词f 在文本孑中的词频， 为训练文本的总数，啊为训练集中出现f 的文本数，分母为归一化因子 相似度通常可以采用三种函数来计算，即内积、夹角余弦与相关系数 内积函数是一种简单但很常用的相似度计算函数它在基于支持向量的分类 算法中广泛使用，取得不错的效果，计算公式如下： 跏i ( x ，y ) = 置】i ： 2 2 3 ) 夹角余弦函数采用空间中的两个向量的夹角余弦值来度量文档之间的语义相 似度两个向量在空间中的夹角越小，余弦值越大，表示其语义相似度越大，文 档越相似，反之亦然余弦函数是文本领域中使用最广泛的相似度计算函数公式 如- f ： y 置z 即2 了卜旆 ( 2 2 4 ) 相关系数是对向量做标准化后的余弦函数它表示两个向量的线性相关程度 相关系数在文本领域较少使用，其公式如下： ( 置一i ) ( 一歹) 溉了卜蓐蓊霉丽 q 2 5 2 2 2 网页表示规则 网页具有与传统文本不同的之处，它们大多采用超文本标记语言编写，其内部 表现为由离散文本条与标记组成的字符串序列从网页自身含有的丰富标注、描 述和网页之间的拓扑信息出发，y i m i n g y 觚g 在【9 】提出了五种网页规则： ( 1 ) n oh y p 嘶e x tr e g u l 撕t y ( 无超链规则) 对于一些数据集而言，唯一对分类有用的信息只有在当前网页自身中获得， 9 而网页以外的信息( 如：主题相关的邻居网页上包含的信息) 未必能改善 分类效果，但是，在现实的网页分类中，有些邻居网页上的信息的确能改 善分类效果 ( 2 ) e n c y d o p e d i ar e g u l 撕瞅百科全书规则) 一个网页和它所链接到的邻居网页很可能是属于同一个类别，即网页经常 链接到类别相关的网页 ( 3 ) c o - r e 衙朗c i n gr e g u l a r i 瞅共引用规则) 拥有相同类别的网页可能属于不同的主题，另外也有可能同时链接到同一 张网页上的网页时具有相同的类别，但它们与该网页类别是不同的 ( 4 ) p r 耐嬲s i f i e dr e g u l 撕趴预分类规则) 存在一种叫h u b ( 中心枢纽) 的网页，其中包含的超链接所指向的网页属于同 一个类别规则( 2 ) 和规则( 3 ) 都是考虑其相邻的网页，而超链接本身也 含有许多对分类有用的信息在w 曲中流行一种网页，它包含许多指向相 同类别的网页的超链接找出这些h u b 网页( 如0 0 、网址之家等) 有 助于我们对其包含的超链接所指向的网页进行分类 ( 5 ) m e t ad a t ar c g u i a r i t y ( 元数据规则) 一些浏览器不可见的网页标签( 如：t i t l e 、m e t a 等) 中包含着对分类有 用的信息元数据包含在t i t l e 、m e t a 、a l t 等标记中，可以将其提取出 来，单独构建分类器或者与超链接信息结合构建分类器 对应以上五种网页规则，一张网页可以有以下5 种描述方法： ( 1 ) 无超链规则 当数据集满足无超链规则时，网页分类需要基于自身的纯文本进行分类， 因为使用超链接反而会使分类器的性能降低一般情况下，考虑待分类网页 中 、 、 标签下的特征词，并赋予相应的权 值 ( 2 ) 百科全书规则 ， 当数据集满足百科全书规则，则将链接网页中的文本作为待分类网页文本 的一部分来考虑因为更多主题相关的特征词会在网页表达中出现，使分类 性能得以改进除了待分类网页自身标签特征词，需要考虑属于链接网页的 、 和其超文本所含有的 、q i t l e 、 锄g g e dw o r d s 标签下的特征词 ( 3 ) 共引用规则 当数据集满足共引用规则时，同百科全书规则一样，将链接网页中的文本 当作待分类网页文本的一部分考虑但区别在于：它们并不是等同对待的， 1 0 需要对它们进行分组处理分组的依据是链接网页与待分类网页之间的相 似度，根据相似度范围将链接网页归于不同区间中，并赋予特定的权值 设待分类网页为成，链接网页为a ，相似度大小为j 砌，相似度区间为 【s 拥。，s 帆】的链接网页有权值w 西，为网页中出现的特征词，则有： r ：| 圻 e 以 【圻m o 鼽，j 拥。s 拥s 砌 ( 2 2 6 ) ( 4 ) 预分类规则 当数据集满足预分类规则，即待分类网页已存在于某些中心网页时，如 m s n 中将部分网页根据类别排列在主题相关的位置，且该位置存在表明网 页的类别文字；待分类网页在链入网页中的锚文本中已标明类别文字以上 两种网页的类别文字若存在于类别集中或同义于类别，则直接标记类别， 否则将关键字作为待分类网页 标签中的特征词看待 ( 5 ) 元素据规则 当数据集满足元数据规则时，则采用主题抽取的方式，收集来自相关类别 的链接网页中的 和娟t l e 标签下的关键词，组成元数据集计算待 分类网页元数据与元数据集之间的相似度来确定类别 2 3 网页分类的特征选择 2 3 1 特征选择的概念 标准的网页分类技术需要对网页集中抽取来的特征词进行处理而原始的网 页特征经常是：( 1 ) 数量多，从一个拥有数千张网页的数据集中抽取得到的特征 将数以万计；( 2 ) 出现频率不等，常用词汇出现频率高，冷僻词汇则很少；( 3 ) 噪音多，网页中包含了许多无实际含义的词汇，如版权声明词汇，还有一些拼写 错误的字和词 特征选择是解决的正是上述的网页高维性问题：从网页中得到的初始特征集 可以简单的被分为有用特征集和无用特征集两部分特征选择的目的就是尽量保 留有用的特征，剔除无用特征它通常会采用某种标准来对特征的重要性进行评 估，之后只要保留重要程度较高的特征项特征选择可以：( 1 ) 提高分类的效率， 降低计算复杂度，因为无用的特征被剔除使得特征集得予压缩；( 2 ) 提高分类精 度，因为减少无用特征对于分类结果的干扰 2 3 2 特征选择的可分性准则和方式 2 3 2 1 特征选择的可分性准则 特征选择的任务是求出一组对分类最有效的特征，因此需要一个定量的准则 来衡量特征对分类的有效性具体而言，从原始特征集中选择出若干特征的各种 组合是很多的，选择哪一种组合的分类效果最好，需要一个比较标准 在理想的情况下，分类错误概率是最好的判别标准，也就是使分类器错误概 率最小的那组特征，应当是一组最好的特征，但是在实际应用中，分类器错误概 率是无法计算的，所以应找出一些实用的标准以衡量各类的可分性【1 0 1 ，并希望 准则满足下列要求： ( 1 ) 同错误概率有单调关系，这样使准则取最大值时一般来说其错误概率也较 小 ( 2 ) 当特征独立时有可加性 ( 3 ) 单调性，即加入新的特征时，准则不改变 常用的准则如下： ( 1 ) 类间距离可分性准则，类间距离是直接从各类样本间的距离计算得到的， 没有考虑各类的概率分布，不能确切表明各类交叠的情况，因此与错误概 率没有直接联系，优点是计算方便，概念直观清楚，所以在特征选择中经 常使用 ( 2 ) 基于概率分布的可分性准则，基于概率分布的可分性准则计算比较复杂， 但能够很好的反映各类分类的错误概率 ( 3 ) 基于熵函数的可分性准则，熵函数的期望值可以表明类别的分裂程度，因 此它可以用作为所选择特征的分类性能的评价指标 2 3 2 2 特征选择的方式 特征选择的方式有四种： ( 1 ) 用映射或变换的方法来把原始的特征项变换为较少的新特征 ( 2 ) 从原始的特征项中挑选出一些最具代表性的特征 ( 3 ) 根据专家的知识挑选最有影响的特征 ( 4 ) 用数学的方法进行选取，找出最具分类信息的特征，这种方法是一种比较 精确的方法人为因素干扰较少 2 3 3 特征选择的常用方法 特征选择的常用方法有：文档频率( d o c 眦e n t 蛔u 饥c y ，d f ) 方法、互信息 ( m u n l a li n 硒n n a t i o n ，m i ) 、信息增益( i n f o m a t i o ng a i n ，i g ) 、x 2 统计( c h i ) 、期望 交叉熵( e x p e c t c dc m s se n 仃o p h y ) 、文本证据权( w e i g h to fe d 锄c e 矗) r1 e x t ) 等【1 1 1 1 2 这些方法的基本思想都是对每一个特征计算某种统计度量值，然后设定一个阈值 乃把度量值小于r 的那些特征项过滤掉，剩下的即认为是有效特征 对于特征词，烈c ： ) 表示第f 类网页在网页集中出现的概率，尸( f ) 表示词f 出现的概率，以f ) = l 一只f ) 表示f 不出现的概率，只glf ) 表示在出现词，的情况 下，网页属于第j 类的概率烈gif ) 表示词f 不出现时，网页属于第f 类的概率 各种选择标准的方法如下： ( 1 ) 文档频率( d o c l l i n t 姻u e n c y ) ，即特征f 在网页集中出现的网页频率将网 页频率小于预定义阈值的特征词去掉其假定很少出现的特征词携带的信 息量为0 ，或者说对分类性能的影响不大该方法通常用作辅助的特征选择 方法 ( 2 ) 信息增益( i i l f o l 皿a l i o ng a j l l ) ：信息增益值度量了当知道一个特征词是否在文 档中，进行类预测所获得的信息比特数，如公式( 2 3 1 ) 所示 e ( c ) = p ( c 1 ) l o g 粥) 层( clf ) = p ( f ) 艺粥if ) l 。g p ( clf ) + p ( ；) 芝粥i ；) l 。g 以qi ； r 粥( f ) = 一e ( o + e ( c i f ) ( 2 3 1 ) 公式中：e ( c ) 表示所有类的平均条件信息熵占( cif ) 表示知道特征词f 是 否在网页中出现的条件下所有类的平均条件信息熵它们之间的差值表示 了特征词f 所蕴含的信息量 ( 3 ) 互信息( m u n l a li n f o m a t i o n ) ：互信息可以度量特征词f 和类别的共现关系， 特征词f 对类别的互信息量越大，它们之间的共现概率也越大 撇，= 薯删崦等汰2 ， f = l j 、，l z j zj ( 4 ) x 2 统计( c h d ：x 2 值度量特征词f 和类别的独立性程度，石2 越大说明独 立性越小，相关性越大 r 以驴两翥篙髫 x 嘴2 ：艺p ( q ) x 2 ( l q ) 2 矧 其中为训练集中的文本数，彳是特征f 和第f 类网页共同出现的次数，雪 是特征r 出现而第f 类网页不出现的次数，c 是第f 类网页出现而特征f 不出 现的次数，d 是第f 类网页和特征f 都不出现的次数 1 3 ( 5 ) 期望交叉熵( e x p e c t c dc r o s se r 帅p h y ) ： c e ( f ) = p ( f ) 善p ( q lf ) l 。g ( p ( cif ) 以c ) ) ( 2 3 4 ) ( 6 ) 文本证据权( w e i g l l to f e v i d 饥c cf o r t e x t ) ： 昭r ( f ) = p ( f ) 以g l l o g 扣li ( 2 3 5 ) 尽管每种特征选择方法都有其独特的公式与概念，但它们的价值是根据其降 维的效果得以体现的目前，已经有多项研究完成了不同降维方法的比较研究 结果显示这些降维方法都可以提高d f 方法的结果例如y 觚g 与p e d e 岱的研究 【6 】显示，在不同的分类器以及不同的初始语料的实验背景下，诸如信息增益( i g ) 和x 2 统计等先进的降维方法能够使特征项空间减少1 0 0 倍而不失其效率研究 还发现在一般情况下，i g 和x 2 统计较m i 和d f 更高效 2 4 网页分类算法 网页分类算法与文本分类算法不存在本质差别，因为它们都是直接或者间接 的提取文本内特征进行分类，基于某种计算模型对文本特征向量进行统计、比较、 计算网页所属的类别但网页自身固有的结构化特性又决定了单一利用纯文本分 类必然会导致大量语义信息的丢失，需要在文本分类算法的基础上，综合考虑结 构化标签、元数据、超链接对类别区分度的影响，并对此采取相应的调整策略 本章首先介绍当前比较常用的方法有叮n ( k 近邻) 、s v i ( 支持向量机) 和n a v e b a y 伪( 朴素贝叶斯) 算法并在此基础上，对当前具有代表性的3 种网页分类算 法：f o i u 一阶规则学习) 、迭代概率调整模型、支持向量机模型进行概括重点 介绍基于超文本结构的n a w eb a y 豁算法 2 4 1 常用的文本分类算法 2 4 1 1 支持向量机( s v m ) 支持向量机( s u p p o r tv e c t o rm a c h i i l 鹤，s v m ) 是建立在结构风险最小化原理基 础上的一种相对比较新颖的统计学习方法1 9 9 8 年j o a c h i m s 【1 2 】将支持向量机引 入自动文本分类研究领域，取得了非常理想的分类效果支持向量机本质上是一 种二类分类器，其实质是寻找一个最优超平面( 或最优超曲面) ，使得两类样本 之间的间距( m a r 西n ) 达到最大 设训练数据集加= ( 薯，m ) ) 羔，是线性可分的其中，是第f 个训练样本的 1 4 特征向量，弗 l ，一1 为其类别标号线性支持向量机( 一类最简单的支持向量机) 最优分离超平面矿工一6 = o 的法向量w 和截距6 ，由以下模型来确定： m i i l 劲叫| 2 ；y i ( w r 而一6 ) l ( 2 a 1 ) 当训练样本线性不可分时，通过引入松弛变量茧o ，从而使公式( 2 4 1 ) 式 转化为： m i i l 去8 叫1 2 一c 艺号；y ，( 矿一6 ) l 一号， ( 2 4 2 ) 扭l 其中，c 为一正实数，用来平衡经验风险和v c 置信范围，以期达到最小的实际 风险另外，通过引入核函数( k 锄c l 删o n ) ，可以将线性支持向量机推广到非 线性情况常用的核函数有多项式核、径向基核和两层神经网络核等 大量实验结果表明，线性支持向量机的文本分类效果与非线性支持向量机的 文本分类效果相差很小，均明显高于其它文本分类算法而且，线性支持向量机 的分类效率比非线性支持向量机的效率要高得多 2 4 1 2k 近邻( 1 ( 1 蝌) k 近邻( kn