（电路与系统专业论文）基于支持向量机分类算法的主题爬虫的研究与实现[电路与系统专业优秀论文].pdf

硕士学位论文 m a s t e r st h e s i s 摘要 网络爬虫为搜索引擎从互联网上下载网页，是搜索引擎不可或缺的组成部分。 通用网络爬虫会从一个或者多个种子u r l 链接开始，爬行整个网络上的网页。而主 题网络爬虫除了具有能够爬行下载网页的基本功能外，还能够分析链接以及页面内 容。主题网络爬虫提供数据资源给面向主题的用户查询，它的目标是抓取与特定主 题内容相关的网页，并不追求覆盖整个网络上的网页。主题网络爬虫已经成为网络 信息挖掘和获取领域的研究热点，对搜索专业领域的信息资源有着相当重要的意 义。本文着重研究了支持向量机算法在主题爬虫中的应用，研究工作有以下几个方 面： ( 1 ) 研究了支持向量机分类算法原理，并对网页的数学表示方法进行了具体 的描述，提出了一种基于支持向量机的网页分类算法，利用支持向量机对网页进行 二类分类，找出所需的网页；再利用向量空间模型，对分类好的主题网页进行多类 分类。 ( 2 ) 在构造支持向量机的过程中，为了有效提高分类的召回率，引入了一种 偏移因子，该算法对分类函数进行了修正，只需要计算二类分类器，减少了误分类 网页数，实验表明，它不仅具有较高的训练效率，同时能得到很高的分类准确率和 召回率。 ( 3 ) 围绕着算法和主题爬虫的爬行目标，重新设计了爬虫的工作流程和功能 模块，并利用h t t p 分析技术，多线程处理技术，增量检测技术实现了基于s v i d 主 题分类算法的主题爬虫p e r c a s p i d e r ，并对爬虫的总体性能进行了测试，对结果进行 了展示和分析。实验表明，新的主题爬虫在下载速度和准确率上都有理想的效果， 保证了爬虫有效性和实用性。 关键词：主题爬虫；支持向量机；网页分类；分类函数；多线程技术 a b s t r a c t w e bc r a w l e re n a b l e ss e a r c h i n ge n g i n et od o w n l o a dw e bp a g e s ，w h i c hi sa n i n s e p a r a b l ep a r to ft h es e a r c h i n ge n g i n e s t a r t i n gf r o mt h es e e d i n gl i n k s ，n o r m a lw e b c r a w l e rs e a r c h e sa l lt h ew e bp a g e st h r o u g h o u tt h ei n t e m e t t h et o p i c o r i e n t e dw e b c r a w l e r , a p a r tf r o mt h ef u n d a m e n t a lf u n c t i o no fd o w n l o a d i n gw e bp a g e s ，i sa l s oa b l et o a n a l y z el i n k sa n dp a g ec o n t e n t t h et o p i c o r i e n t e dw e bc r a w l e rm a i n l ya i m st ot h e t o p i c f o c u s e dq u e r ya n di t ，w h i c hd o e sn o tp u tp r i o f i t ) rt oc o v e ra l lt h ep a g e si nt h e i n t e m e t ，s e r v e st oc a p t u r es p e c i f i cw e bp a g e sr e l a t e dt oac e r t a i nt o p i c t h et o p i c f o c u s e d w e bc r a w l e rh a sb e c o m et h eh o t t o p i ci nt h ew e bi n f o r m a t i o nm i n i n ga n dc a p t u r i n gf i e l d a n ds h o w sg r e a ti m p o r t a n c et ot h ei n f o r m a t i o ns e a r c h i n gi n d u s t r y t h i sp a p e r , c e n t e r e d o nt h es u p p o r tv e c t o rm a c h i n ea p p l i c a t i o no fa l g o r i t h mi nt h et o p i c - f o c u s e dw e bc r a w l e r , r e s e a r c h e st h ef o l l o w i n ga s p e c t s ： t h ep r i n c i p l eo fs u p p o r tv e c t o rm a c h i n ec l a s s i f i c a t i o na l g o r i t h mi sr e s e a r c h e di n t h i sp a p e r f i r s t ，t h ep a p e rd e s c r i b e st h em a t h e m a t i c a lr e p r e s e n t a t i o no fw e bp a g e s ，i n t h es e q u e l ，a l li m p r o v e dw e bc l a s s i f i c a t i o na l g o r i t h mb a s e do nt h es u p p o r tv e c t o r m a c h i n ei sp r e s e n t e d ，w h i c hc l a s s i f i e sw e bp a g e sb y2 - c l a s s i f i e r sb a s e do ns v ma n d f i n d so u tt h ew e bp a g e si nt h et o p i c s p e c i f i cc l a s s t h e nt o p i cs p e c i f i cw e bp a g e sa r e c l a s s i f i e di n t os e v e r a lc h i l dc l a s s e s 、析mv e c t o rs p a c em o d e l ( v s m ) d u r i n gt h ep r o c e s so fc o n s t r u c t i n gs u p p o r tv e c t o rm a c h i n e ( s v m ) ah n d o fb i a s a d j u s t m e n ti s i n t r o d u c e di no r d e rt oe n h a n c et h er e c a l lr a t eo fc l a s s i f i c a t i o n t h i s a l g o r i t h mh a su p d a t e dc l a s s i f i c a t i o nf u n c t i o n ，i nw h i c ho n l y2 - c l a s s i f i e r sa r en e e d e dt ob e c a l c u l a t e d t h i sh a sg r e a t l yr e d u c e dt h ef a l s ec l a s s i f i c a t i o no fw e bp a g e s e x p e r i m e n t s h a v es h o w ni td o e sn o to n l yb r i n ge f f e c t i v et r a i n i n gb u ta l s oa c h i e v e sh i g hc l a s s i f i c a t i o n a c c u r a c yr a t ea sw e l la sr e c a l lr a t e c e n t e r e do na l g o r i t h ma n dc r a w l i n gt a r g e to ft o p i c f o c u s e dw e bc r a w l e r , t h ec r a w l e r w o r k i n gp r o c e s sa n df u n c t i o nm o d u l e sa r er e d e s i g n e d f u r t h e r m o r e ，h t t pa n a l y s i s t e c h n o l o g y , m u l t i t h r e a dt e c h n o l o g ya n da d d e d v a l u ei n s p e c t i o nt e c h n o l o g ya r ee m p l o y e d a l lt h e s et e c h n o l o g i e sr e a l i z et h et o p i c f o c u s e dw e bc r a w l e rp e r c a s p i d e rb a s e do ns v m t o p i cc l a s s i f i c a t i o na l g o r i t h m ，t e s tt h eo v e r a l lf u n c t i o no fc r a w l e r s ，d i s p l a ya n da n a l y z e t h er e s u l t s e x p e r i m e n t sh a v es h o w nt h a tn e wt o p i c - f o c u s e dw e bc r a w l e ri si d e a l l y e f f e c t i v ei nt e r m so fb o t hd o w n l o a ds p e e da n da c c u r a c yr a t e ，w h i c he n s u r e st h ev a l i d i t y a n dp r a c t i c a b i l i t yo ft h ec r a w l e r k e y w o r d s ：t o p i c f o c u s e dw e bc r a w l e r ；s v m ；w e bp a g e sc l a s s i f i c a t i o n ；c l a s s i f i c a t i o n f u n c t i o n ；m u l t i t h r e a dt e c h n o l o g y 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：景也盘 魄呷年r 月3 ) 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者签名：黑也杰、 喊2 的7 年岁月弓1 日 导师签名 日期：砑年妙月岁7 日 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程”中的 规定享受相关权益。园意诠塞握窒卮溢厦! 旦圭生；旦二生；旦三生筮盔! 作者签名：关也生、 日期。r 引日 导师签名： 日期一年哆月罗j 日 硕士学位论文 m a s t e r st t l e s i s 第1 章引言 1 1 研究背景和意义 网络爬虫是搜索引擎的重要组成部分，它为搜索引擎从网络上下载网页，是一 个自动提取网页的程序f l 】。通用网络爬虫从一个或多个初始网页上开始爬行，以此 获得初始网页上的u r l 列表；在爬行过程中，不断从当前页面上获得新的u r l 并将 其放入待爬行队列的队尾，当满足系统设定的停止条件时停止工作。主题网络爬虫 则是根据特定的网页分析算法，过滤掉与选定主题无关的链接，保留与主题相关的 网页将其放入待爬行的网页队列表中；然后根据特定的搜索策略从队列中选择下一 步要爬行的网页的u r l ，如此往复，直到满足系统的停止条件。所有的网页在被爬取 后都会被系统存储，经历分析过滤后建立索引。对于主题爬虫而言，这一过程相当 重要，它将对后续的爬行工作起到反馈和指导作用1 2 2 l 。 互联网的网页并不是孤立的，网页之间存在着逻辑或者物理上的联系f 2 i 。如果 超链接l 被包含在网页f 中，则f 是链接l 的父网页( f a t h e rp a g e ) 。如果网页s 被超链接l 指向，则称网页s 为子网页，又称为目标网页( s o np a g e ) 。主题爬虫的基 本思想就是按照事先给出的主题，分析已经下载的网页和超链接的内容，根据预测 算法预测待抓取的u r l 与主题相关度，根据相关度对待抓取的网页进行取舍，保证 爬虫的性能，包括准确率和覆盖度等方面。 主题爬虫需要考虑和解决以下几个问题： ( 1 ) 描述和定义爬行目标的方式。 ( 2 ) 确定待爬行网页访问次序。部分网络爬虫会分析已经下载的网页，将其相 关度按照一定的衰减原则传递给从属于该网页的子网页，并将子网页插入到待访问 队列中去，并设定为优先访问【引。这些爬虫的爬行策略不再仅仅简单考虑是采用深 度优先还是广度优先的问题，它需要参照相关度的大小和排位结果，相关度大的网 页会被优先爬行。如何计算和确定待爬行队列的访问次序是不同类别的主题爬虫的 一个重要区别。 ( 3 ) 计算和判定待爬行网页和给定主题的相关度。业界常常采用文本挖掘技术 来获取待爬行或者已经被下载的网页的文本内容。如何判定当前爬行网页与主题的 相关度也是主题爬虫问的另一个重要区别。 ( 4 ) 如何提高主题网络爬虫爬行的覆盖度。提高覆盖度的策略就是区分相关网 页和无关网页，从而使爬行变得有选择性，有效的覆盖度就自然会随之提高。 硕士学位论文 m a s t e r st h e s i s 主题爬虫在搜索引擎中占有重要地位，对搜索引擎的查全、查准 4 1 都有一定程 度的影响，它决定了搜索引擎数据容量的大小，而且网络爬虫设计得好与坏直接影 响搜索结果页面中的优等页面和此等链接的个数。主题式搜索引擎f 5 】的出现将会成 为今后搜索引擎的发展新动向，而主题爬虫作为主题式搜索引擎的重要组成部分， 必然也会备受业内研究者的推崇。 1 2 主题爬虫的国内外研究现状 爬行算法和策略直接影响着爬行效率和主题爬虫的性能，是业界所研究的主题 爬虫的最主要的区别1 6 i 。近年来国内外许多学者在主题爬虫的爬行策略和爬行方法 方面付出了诸多努力，也取得了可观的成果。笔者分析和比较了这些方法和策略， 将其分为以下四大类。 1 2 1 基于文字内容的启发式方法 该方法目前主要包括b e s tf i r s ts e a r c h 方法、f i s hs e a r c h 方法、s h a r ks e a r c h 方法。 这些方法和策略主要是考虑了w e b 网页文本内容，统一资源定位符字符串，锚文 本等内容。对这些内容分析方法上的对策是这些算法彼此问的显著区别。 ( 1 ) b e s tf i r s ts e a r c h 方法。该方法的思路是对给定的待爬行u r l 队列进行分 析和排序，确定优先级，即优先爬行最好的u r l 。采用关键词集合来描述爬行主题， 并根据已爬行网页c 的文字内容和主题词汇来计算，用他们的相关度来预计以爬行 网页c 中链接所指向的网页的相关度。优先级由相关度的大小来决定【7 l ，相关度越 大的网页获得的优先级越高，相关度越小的网页获得的优先级越低。假如待爬行队 列的缓冲区己满，则需要从该队列中移除优先级最低的u r l 。它采用h a r v e s tr a t e ( h a r v e s tr a t e 就是主题相关网页数目占所有抽取网页总数的比率) 来计算网页与主 题间的相关度。算式如下： s i m ( q ，p ) = ( 厶厶) ，磊2 厶2 o - 1 ) k e q c 、p 、fk e p 、4k e q 其中：主题用g 表示，抓取的网页用p 表示，词尼在q 中出现的频率用厶表示， 词k 在p 中出现的频率用，勋表示。该算法有w i l lq u e u e 和d o n eq u e u e 两个堆栈， 分别用来存储等待爬行的u r l 序列和己被爬行的u r l 序列。该算法具有一定和普 适性和竞争力，在主题网络爬虫中已作为不同的爬行算法性能评价的一个普遍采用 的标准【9 】o w i l l i a m s 等学者【l o j 在上述方法的基础上处理并改进了待爬行队列，将其一分为 2 硕士学位论文 m a s t e r st h e s i s 二，即w o r mq u e u e 和c o o lq u e u e ，前者队列里储存的是相关的网页序列，后者储 存的是非相关网页序列。w o r mq u e u e 的爬行优先级高于c o o lq u e u e ，只有当w o r m q u e u e 为空时，才爬行c o o lq u e u e 。相关性的判断并不是采用的h a r v e s tr a t e ， 而采用以下准则：如果主题词包含在u r l 字符串或者对应的锚文字中，那么就认 定是相关的将其加入到w o r mq u e u e 中，如果不包含则将其添加到c o o lq u e u e 中。 这种方法拥有计算量小的优势，在判定单一关键词的宽泛主题页面上，算法性能表 现相当优越。但是在关键不唯一的情况下，这种方法就显得捉襟见肘，算法效果大 打折扣。多个关键词蕴涵的真实主题往往很难被u r l 字符文字和锚文字反映出来。 ( 2 ) f i s hs e a r c h 方法。d eb r a 等学者1 1 1 1 在上世纪九十年代中叶，提出了f i s h s e a r c h 方法。这种方法由仿生学和生物群智能【4 0 1 中演化而来。在该算法里，网络爬 虫被模拟成海里中的鱼群。当鱼群发现了与食物相关的信息时，鱼群们开始繁衍后 代，扩大种群，籍此寻找更多的食物；当食物减少( 没有相关信息) 或者生存环境 恶化( 带宽不够) 是，就被迫减少种群，个体逐渐消亡。如何根据用户感兴趣的主 题种子站点和主题关键词的变化，适时更新和维护待爬行的u r l 优先级队列是该 算法的核心问题。 当一个网页被抓取以后，首先要分析页面所有的链接，找出该页面的子网页( s o n p a g e ) 。当抓取的网页属于主题相关网页时，可将一个预先设定的值赋给子网页的深 度值d e p t h ；如不相关，则将d e p t h 的深度设定为小于其父亲网页( f a t h e rp a g e ) 的 深度值 9 1 。如果满足深度值d e p t h 归零的条件，从这个网页往下的爬行就必须停止。 f i s hs e a r c h 算法包含一系列的入口参数，主要有种子站点( s e e ds i t e ) 、查询列 ( s e a r c h t i t l e ) 、查询深度( s e a r c h d e p t h ) 、查询宽度( s e a r c hw i d t h ) 。当子网页( s o n p a g e ) 的深度大于零时，其u r l 可按照一定的启发式策略插入到c o o lq u e u e 中， 该规则如下： 相关网页前部的口xw i d t h 个子网页可以添加到队列c o o lq u e u e 的顶端，其中 口为大于1 的常量； 在c o o lq u e u e 紧靠相关子网页的节点的队尾部，可添加无关网页之前的 w i d t h 个子u r l ； 剩下的子网页的u r l 加到c o o lq u e u e 的尾部，只在系统已爬行完之前所有 链接，并且仍有时间剩余的情况下才爬行。 上述规则所列举的情况，可以用一个变量来描述，r e l e v a n c e $ c o r e 来等价描 述： 满足规则时，r e l e v a n c es c o r e = 1 ； 硕士学位论文 m a s t e r st h e s i s 满足规则时，r e l e v a n c es c o r e = 0 5 ； 满足规则时，r e l e v a n c es c o r e = 0 ： 采用r e l e v a n c e s c o r e 值对待爬行队列来排序。该算法是面向c l i e n t ( 客户端) 的，它具有模式简易化、搜索动态化的优点。但是缺点也比较明显：r e l e v a n c es c o r e 可选值是离散的，可选择数量较少( 只包含三个值，即0 ，0 5 ，1 ) ，并且只选用字 符串匹配；与主题的相关度很难用被分配的权值准确的测度。在c o o lq u e u e 中，不 同类别的u r l 之间的优先级差距较小。在爬行时间受限时，很多具有相同优先级 的u r l 可能无法被访问到，导致有部分相关的网页因漏掉而无法被覆盖。另外， 将s e a r c hw i d t h 作为调节删除网页后面u r l 的参数标准值得商榷，会因此造成误删， 漏掉许多重要的网络资源。 ( 3 ) s h a r ks e a r c h 方法【1 2 j 。它是f i r s ts e a r c h 算法的变种和改良版本，其改进主 要表现在相关判断和计算u r l 的r e l e v a n c es c o r e 上，即：s h a r ks e a r c h 算法的相 关度值不是离散的，而是一个取值范围在( 0 ，1 ) 之间的连续值；s h a r ks e a r c h 算 法在计算r e l e v a n c es c o r e 时，不但考虑到了有“父子关系”的网页之问的值的继承 和传递，还参考了锚文字的上下文的联系。较之f i s h 算法，s h a r k 算法在算法精度、 选择爬行方向、爬行效率上的表现更胜一筹。 1 2 2 基于w e b 超链图的评价方法 上一章节所提及的算法没有考虑到w e b 有向图( 通过超链而形成) 对主题网络 爬虫的影响，利用的只是统一资源定位符、网页、锚文字等文字信息，必然存在一 定的局限性和提升的空问。引文分析理论是文献计量学的一个基本理论，也是基于 w e b 图的启发策略的思想来源。尽管与w e b 评价和引文分析理论的理论基础和应 用环境看似并不十分相关，但网页之间的超链到目前仍然具有参考价值。近年来在 研的w e b 超链图的爬行算法主要有b a c kl 址算法和p a g er a n k 算法。 ( 1 ) b a c kl i n k 算法。该算法的思想是网页的重要性与其被引用的次数成正比。 这就意味着一个网页被其他的网页指向或者引用的次数越多，这个网页就越重要， b a c kl i n k 值越大。按照b a c kl i n k 的值对待爬行的u r l 队列进行排序，b a c kl i n k 值较大的u r l 因获得较高的优先级被优先爬行。 ( ”p a g er a n k 算法。p a g er a n k 是当前全球使用得最多的搜索引擎g o o g l e 所 采用的搜索算法，是一种无关乎查询式的算法。g o o g l e 的两位创始人s b r i n 和l p a g e 是该算法的提出者【s 1 。p a g er a n k 算法基于w e b 超链图，按照p a g er a n k 值对待爬行 的u r l 队列进行排序来确定访问次序。单个网页的p a g er a n k 值按照公式( 1 1 ) 4 硕士学位论文 m a s t e r st h e s i s 来计算。p a g er a n k 算法认为一个网页的重要性与链入它的网页数量成正比，链入 数量越多，网页就越重要。在p a g er a n k 算法里，所有的网页都是平等关系，不考 虑网页的质量和贡献度问题，侧重点只是数量。然而在实际中，不同质量的网页的 贡献度和重要性是必须区分的。在b a c kl i n k 算法中，如果想要提高某个网页的重 要性，只需要增加指向它的网页的数量即可。p a g er a n k 算法的提出很大程度上克 服了b a c kl i n k 算法的不足。p a g er a n k 算法计算网页重要性的方法如下： r ( f ) = ( 1 一d ) + d 芝：l r ( j ) n ( j ) l( 1 2 ) j e b ( 0 式中：b ( f ) 是指向网页i 的网页集合；( i ) 表示网页冲的链出数目；r ( f ) 表示 网页f 的权威度。d 是一个衰减因子，其取值范围在( o ，1 ) ，而网页本身的权威度 则用( 1 d ) 来表示。由公式( 1 - 2 ) 本身组成可知，( 1 一d ) 的值是不会被传递的，但是 d 的值会被传递下去，即当前网页权威度的d 将会随着网页的链出而被传导给其它 网页。通过反复实验，s b r i n 和l p a g e 得出d 的最佳值约为o 8 5 的结论。 当一个网页被下载后，如果抽取该网页的所包含的超链，那么w e b 图就必须做 相应的调整，也就需要重新计算相应的优先级。所以w e b 超链图启发策略在设计时 需要引入闽值来平衡计算量大和网页下载的矛盾。 由于以下原因w e b 超链图评价的启发策略仍不完善：过多的导航超链导致在寻 找主题链时出现迷失；计算量大严重制约着网络爬虫的爬行速度；在寻找主题网页 上的表现远不及寻找权威网页。 1 2 3 基于分类器预测的方法 面对着基于文字内容的启发式方法和基于w e b 超链图分析方法分别在在描述 用户关注主题和分析效率上遇到的难题。种基于分类器引导和监督的主题网络爬 虫【1 4 i 应运而生。研究者们希望借分类模型来聚焦用户关注的主题和预测网页与主题 的相关度。分类模型的不再匹配关键词的层面上，在深层次描述用户关注主题信息 方面效果更好，计算的网页主题相关度值也更加精确。实验结果 1 5 - - ! j 显示其应用能 够提高主题爬虫的查准率和查全率，从而提高主题爬虫的性能。 s c h a k r a b a r t i 等学者【l8 】进行了一些与主题网络爬虫相关的实验，分析和研究了 半监督式的机器学习方法和网页的链接关系。其网络爬虫从分析用户给定兴趣点或 者主题开始，对所有网页进行分类，将用户可能感兴趣的网页做标识处理。爬虫由 爬取器、分类判别器、选择过滤器这三个部分组成，其评价指标是查准率。爬取器 用于分析链接的结构关系；分类判别器用于分析网页是否相关进而决定要访问的链 接对象；选择过滤器用于优先级的计算。 硕士学位论文 m a s t e r st t i e s i s s c h a k r a b a r t i 等学者l 均1 在研究主题爬虫时，对计算网页主题相关性和u r l 访问 次序上进行了改良，采用了两种不同的处理方式。用前文所述的二值分类器计算网 页主题相关度，只做是否相关的判断，取值为集合 0 ，1 ) 。采用a p p r e n t i c e 模型确定 u r l 访问次序。该模型先利用二值分类器得出的结论确定父网页【2 0 】从属类别，再根 据父网页周边的特征进行在线训练，从而预测被父网页所指向的网页的相关度。这 种爬虫能够有效控制爬行错误。 傅向华等学者【i5 l 提出了一种新的具有在线增量自学习能力的主题爬行方法。 该方法分解了网络爬虫的爬行过程，将爬行动作序列化，并且吸取了半监督式贝叶 斯分类器f 3 3 椰和快速q 学习的优点。该方法先获取和分析网页提取特征文本，再根 据特征文本估算网页与主题的相关性，然后通过预测q 值过滤掉与主题不相关的链 接。链路上所有链接的q 值会因为发现主题网页时产生的回报性反馈而更新，并且 在选择相应的特征文本作为训练样本后，q 值预测器和主题评估器被增量的改善。 该方法所具有快速化的学习能力和在获取的网页数目和精度均优于离线主题爬行 方法已在实验中得到证明。 李卫等学者【1 3 1 研究并实现了一个基于主题的智能信息采集系统i f w c 。该系统 以全信息理论为基础，采用了基于概念的向量空间模型，利用语义分析文本的主题 相关性。爬行算法对页面内的u r l 进行主题相关性预测使用了扩展元数据的语义 相关性判定算法。 s c h a k r a b a r t i 等学割1 9 j 提出的主题网络爬虫提出基于朴素贝叶斯分类模型引 导的。j o h n s o n 等学者1 2 2 j 提出的主题爬虫是基于s v m 分类模型来指导主题爬行的。 在爬行效果方面基于线性s v m 分类模型的主题w e b 爬虫比朴素贝叶斯分类模型2 2 】 表现更突出，这一结论已在文献 1 2 - 1 4 l 中通过对比实验得出。 1 2 4 其他主题爬行方法 m d i l i g e n t i 等学者1 2 i j 着重研究了上下文图在主题爬虫中的应用，认为要利用上 下文图来引导主题爬虫爬行的首要问题是在爬行中任务分配机制。他们提出了一种 基于上下文的主题爬虫。这种爬虫首先需要获取网页建立上下文图表，再利用图表 训练一组分类器，根据计算出来的链接与主题的距离值来对文本预测分类。在这种 爬行算法里每个起始网页都需要建立各自的上下文图表和分类器，直到达到预定的 顶级。该算法可以获得与主题相关的内容( 间接或者直接的) 和目标路径模型。与 其他的爬虫相比较，基于上下文图的主题爬虫( c f c ) 因为每层结构都有自己的贝 叶斯分类器和最优路径，它的性能更好，爬取的网页相关性更高。 c a g g a r w a l 等学者1 1 6 1 利用h u b sa n da u t h o r i t i e s 逻辑分组算法和向量空问模 6 硕士学位论文 m a s t e r st i t e s i s 型，提出了一种主题爬虫w t m s ( 网页主题管理系统) 。该爬虫只下载与主题相关 网页附近的网页，这些网页通常与主题相关页存在着一定的联系，如是其父网页、 子网页、兄弟网页等。算法为每个类制定了一个相关度阈值，一旦待爬行页的相关 度值小于阈值，立即停止爬行。 a m c a l l u m a 等学者 1 7 1 提出了使用贝叶斯分类算法和加强学习的方法开发了一 种主题爬虫。该算法的特点是在利用贝叶斯分类算法对网页文本和网页超链接进行 分类后，引入了链接激励值，这样有利于增强主题爬虫的训练学习能力。 m e h r i g 等学者【2 3 1 提出了一种基于计算o n t o l o g y 相关度的主题爬虫，并设计了 其体系结构和框架。该算法首先必须处理网页以抽取关键词，并统计计算其词频； 然后选择用户关注度较高的关键词，利用关键词匹配方法、类别分析法、复杂关系 计算法在o n t o l o g y 图上计算相关度。最后根据相关度确定爬行优先级。实验结果表 明该算法可以获得较高的h a r v e s tr a t e 。 1 3 本文的主要工作和内容安排 搜索引擎的应用和研究相当广泛，对于绝大部分的网络使用者而言搜索引擎甚 至是网络应用最重要的一部分。而主题爬虫则是搜索引擎最为基础的部分，其目的 就是从w r e b 上获取与主题相关的资源，下载和储存u r l 链接和网页内容，形成索 引，并定期进行增量检测。查询的响应时间、信息的覆盖率以及准确度是衡量爬虫 性能的主要指标。如何提升主题爬虫的性能是目前研究的一大热点。s v m 分类预 测算法使得尽可能多爬行与主题相关网页少爬行无关网页成为可能。本文将对s v m 分类算法应用到主题爬虫中进行理论和实践上尝试，主要工作为以下几个方面： ( 1 ) 研究基于s v m 的分类算法原理，结合网页的数学描述模型，针对传统技 术在网页分类过程中召回率偏低的问题，采用偏移因子，修i f 核函数k e r n e l ，提出 s v m 二类分类算法的改进算法叫主题分类算法。 ( 2 ) 分析s v m 主题分类算法，利用预先下载的网页对两种算法进行分类训练 实验，通过实验结果对比主题分类算法和多类分类算法的网页分类效果和性能。 ( 3 ) 设计并实现基于s v m 主题分类预测算法的主题爬虫p e r c a s p i d e r ，建立具 体的系统功能模块，包括h t t p 获取模块、u r l 队列管理模块、链接分析模块、分 类模块、增量检测获取模块、线程池工作模块等，并对爬虫的总体性能进行测试， 对实验结果进行展示和分析。 7 ： 硕士学位论文 m a s t e r st h e s i s 第2 章基于支持向量机分类算法的主题爬虫的算法研究 由于主题爬虫需要有选择性的爬行主题页面，因此应该对网页按照主题相关性 进行分类。与文本分类类似网页分类具有如下特点：( 1 ) 对网页进行分类需要处理的 网页的样本空间十分巨大；( 2 ) 网页文本内容在处理时会因为词汇排列次序、句意理 解、句子分割、语境差异等问题表现出高维特征；( 3 ) 网页之间存在较大的特征相关 性；( 4 ) 网页的向量具有稀疏性的特点；( 5 ) 噪声充斥在网页训练样本集中；( 6 ) 网页训 练集的样本数会因为从属不同类别而有较大差异。当前许多分类算法面对网页分类 的这些特征都有些力不从心，而支持向量机算法在网页分类方面却能够有较好的表 现。与其它分类算法相比，基于支持向量机的分类算法在对网页进行分类中有着以 下优越性： 支持向量机算法善于处理高维问题； 支持向量机算法受网页特征相关性的影响并不大； 支持向量机算法同时适用与稀疏矢量特征和稠密矢量特征； 支持向量机强大的增量学习和自主学习能力能够有效解决网页内容变化迅 速收集困难的难题1 4 6 1 。 因此将支持向量机算法应用于网页分类将大有可为。j o h n s o n t 2 2 】等学者已经对用 s v m 算法监督指导主题爬虫进行了理论上的探索，并进行了相关实验。本文将进 一步研究s v m 分类算法在网页主题分类预测中的应用，并用其指导主题爬虫的爬 行。 2 1 支持向量机的分类算法原理 支持向量机的分类算法原理支持向量机( s v m ) 是基于统计学习理论，以结构 风险最小化原n t 4 6 1 为理论依据的一种机器学习方法【2 8 1 。s v m 的主要方法是针对二类 分类问题，在高维空间中寻找一个超平耐蛔作为二类的分割，以保证最小的分类错 误率。对于网页分类而言，如果利用s v m 的重叠性进行通用的多类分类，会造成 训练时间过长的问题。在实际搜索中对大量的主题网页分类，可以考虑首先采用 s v m 进行二类分类，然后在此基础上做部分改进和优化进行s v m 主题分类，这样 既能获得较好的分类结果，又能克服s v m 通用多类分类效率低下的问题。 假定存在二类训练样本集： d = ( x l ，y l ，( x ，y ，) ) ，x r 刀，y 一l ，+ 1 ) ( 2 1 ) 硕士学位论文 m a s t e r st h e s i s 在线性可分的条件下存在一个超平面： ( c o x ) + b - - 0 ( 2 2 ) 将此样本集最优分类：如果训练样本可以无误差地被划分，每一类数据与超平面 最近的向量与超平面之间的距离值最大，此超平面称为最优超平面。其中，功是超 平面的法线方向。 求解最优超平面( 2 2 ) ，使下式最小化： m ( 彩) = 去l l 国0 2 ( 2 3 ) 并且同时满足约束条件： y f 【( 缈，x f ) + b 】l ，f - - 1 ，j ( 2 4 ) 此二次规划求解 4 6 1 等价于引入拉格朗同乘子q 0 ，i = 1 ，求解下列函数： ：( c o ，b ，口) = 去0 缈1 1 2 一口， 少， ( 国，t ) + 6 卜l ( 2 5 ) 厶 i = 1 这里l 的极值点为鞍点，可取l 对彩和b 最小值0 3 = 国，b = b ，以及对口的 最大值口= 口+ 。经过线性变换原问题转化为对偶形式，在约束条件： ， y ；a ；= o ，q o ，扛1 ， ( 2 - 6 ) 求解如下的极大化： ， 1 ， m a x w ( a ) = q 一去哆a j y 以k ( x i , x j ) j = ll = l ，= l 得到最优超平面： 国= a i + y i = 1 b b + = 一二 ，其中x ，x 。为任意向量 = 一一t , d ，共甲t ，t 为仕葸i 司重 二 从式( 2 8 ) 可以看出，= 0 的样本对分类不起任何作用， 对6 0 宰起作用，从而决定分类结果，这样的样本即为支持向量。 相应的分类器为： r，1 厂( x ) = s g n ( + 6 ) = s g n 西咒k + 6 li = 1j 根据厂( 工) 的符号来确定测试样本x 的归属。 9 ( 2 7 ) ( 2 8 ) ( 2 9 ) 只有口。 0 的样本 ( 2 1 0 ) 硕士学位论文 m a s t e r st i i e s i s 在线性可分的情况下，支持向量机的内积核函数为k = 。 对非线性问题，不同的内积核函数将形成不同的算法，目前研究最多的核函数 主要有三类削，一类为多项式核函数： k ( x ，x ，) = 融，x 。) + l r ( 2 1 1 ) 所得到的是d 阶多项式分类器； 二类为径向基核函数： ri 1 21 k g , x t ) - e x p _ 骘l ( 2 1 2 ) 【 盯 j 还可以采用s i g m o i d 函数作为内积，即： k ( x ，t ) = t a n h ( y ( x ，x f ) + c ) ( 2 1 3 ) 2 2 网页的数学描述 网页数据的结构是半结构化的，较之内容它更加注重格式。我们目前所见的网 页数据大多是以h t m l 、a s p 、j s p 、p h p 等格式的存在的文件。如果要表示一个 w e b 网页，需要借助搜索系统搜集网页，然后将网页文件转换为文本来处理。网 页的标题通常得视作处理后的文档正文的前部。近年来许多学者都在文本特征表示 方法上做了大量工作，取得了一定程度的进展。向量空间模型( v s m ) 1 4 6 1 是就是其 中被普遍承认且成效较好的一种方法。 在向量空间模型中，可将文本空间等效为一组由相互正交的词条向量所组成的 向量空间集合。不妨设n 为文本特征的总和，则可构成一个向量空间其维数为n ， 那么每一个文本均可用一个n 维特征向量表示： y ( d ) = ( f l ，国l ( d ) ；f 2 ，国2 ( d ) ；，乙，( o n ( d ) ) ( 2 - 1 4 ) 其中词条项的向量用t 表示，t 在文本d 中的权值用彩j ( d ) 表示。 本章中对皑( d ) 的计算采用目前应用较多的t f i d f 向量表示法【3 0 1 公式如下： 皑( d ) = 斫1 0 9 ( ) ( 2 1 5 ) 词条在网页d 中出现的词频用彰( d ) 表示，所有网页的总数用表示，出现 了词条t ，的网页的数目用n 。来表示。t f i d f 算法中，词条区分网页内容属性能力的 强弱可以用词频来衡量，即：词语出现频率越高，区分内容的能力越强；同时t f i d f 1 0 硕士学位论文 m a s t e r st h e s i s 算法也能够测定词条在网页集合中出现的范围，数量越多的网页包含该词条，那么 它区分网页内容属性的能力越差。 2 3 网页的s v m 主题分类算法 本章所提出的网页主题分类算法须分为两个不同的阶段。第一阶段是训练建模 阶段，这个阶段的工作分为两个部分，确定基于支持向量机算法的二类分类器，建 立从属于主题类别的小类的向量空间模型。第二个阶段是测试阶段，要对待处理的 网页进行训练分类。鉴于要被训练和测试的网页样本的类别比较多，在两个阶段中 都要采用非线性的支持向量机算法，支持向量机算法的内积函数须采用径向基函数 ( 2 1 2 ) ，将采用如下公式来计算径向基函数1 4 5 1 中的向量间距d ： c = = 一 d = ：( 国，( d i n ) 一国。( 以) ) 2 ( 2 一1 6 ) 经过多次实验证明要获得较高的准确率和召回率，须在测试阶段采用较为简单 的词条权值相乘累加比较的方法来比较相似度。 2 3 1 构建分类模型 网页文本表示问题是构建网页分类器模型前必需考虑的，选取网页的文本特征 词是一个较好的