（计算机应用技术专业论文）基于网页内容和链接的主题爬虫研究与实现.pdf

删删f f f f f i f f f 川川f f i f i f f f f f 洲 y 17 9 8 8 0 1 海南大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得 的成果。除文中已经注明引用的内容外，本论文不含任何其它个人或集体已经发表或撰写过 的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 声明的法律结果由本人承担。 论文作者签名：l 葭 e im ：为卜年f 月 学位论文版权使用授权说明 本人完全了解海南大学关于收集、保存、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权海南大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。本人在导师指导下完成的论文成果，知识产权归属海 南大学。 保密论文在解密后遵守此规定。 论文作者繇黔7 氐 翩签名：伽角 日期：7 叼。年易月中日 日期：o o 年易角日 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程”，同意将本人的学位论 文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章程”中规定享受相关 权益。旦塞途塞埕銮丘澄唇；旦坐生；旦= 生i 旦三生蕉盈。 论文作者签名：废 日期：7 p 年月牛日 翮虢伽 导师签名： fy ，j 日期：7 啦年6 月讧日 一 0 ，il【i_ 1 海南大学硕士学位论文摘要 摘要 随着互联网上的信息量越来越大，传统搜索引擎的局限性如覆盖率低、时效 性差、结果不准确等已日趋明显。针对以上情况，另一种搜索引擎悄然出现，它 可以在一定范围内取得比传统搜索引擎更令人满意的结果，这就是垂直搜索引 擎。主题爬虫是垂直搜索引擎的核心部分。主题爬虫对网络带宽的利用率、硬件 资源的使用以及搜索效率都有重要的影响，因此对主题爬虫的研究具有重要的意 义。 本文首先介绍爬虫的基本原理，接着讨论主题爬虫的关键技术如中文分词， 主题判断的方法以及主题向量的建立等，重点介绍了主题爬虫的爬行策略。本文 详细介绍了每类爬行策略的代表算法，并对这些算法的优缺点进行了分析，并在 此基础上提出了算法改进方法。 本文对传统向量空间模型特征词的权值计算方法进行改进：对文本中不同 位置的特征词赋予不同的权重；对h i t s 算法中不合理的链接互相加强关系进行 了改进：在扩展根集时，如果一个网站b 上有n 个其它网页指向另外一个网站上 的某个网页a 时，则将这些链接的权重设为1 n ，其它链接的权重依然设为l ； 针对s h a r k - s e a r c h 算法产生“近视和h i t s 算法产生“主题漂移的不足，将 这两种算法的优点结合起来形成两种新的主题爬虫算法：s - h i t s 算法和m t - h i t s 算法，并实现了这两种爬虫算法。实验表明新的算法效果较好。 关键词：垂直搜素引擎主题爬虫爬行策略 ij l上 j 海南大学硕十学位论文 摘要 a b s t r a c t w i t ht h ei n c r e a s i n ga m o u n to fi n f o r m a t i o no nt h ei n t e r n e t ，t h el i m i t a t i o n so f t r a d i t i o n a ls e a r c he n g i n e s ，s u c h 觞l o wc o v e r a g e ，p o o rt i m e l i n e s s ，i n a c c u r a t er e s u l t s ， h a v eb e c o m ei n c r e a s i n g l yo b v i o u s f o rt h ea b o v e ，a n o t h e rs e a r c he n g i n ec a l l e d v e r t i c a ls e a r c he n g i n eh a sa p p e a r e dw h i c hc a l lb eo b t a i n e dt h em o r es a t i s f a c t o r y r e s u l t st h a nt h et r a d i t i o n a lo n ew i t h i nac e r t a i nr a n g e t o p i c a lc r a w l e ri st h ec o r ep a r t o fv e r t i c a ls e a r c he n g i n e t h er e s e a r c ho nt o p i c a lc r a w l e rh a si m p o r t a n ts i g n i f i c a n c e o ni n c r e a s i n gn e t w o r kb a n d w i d t hu t i l i z a t i o na n d s a v i n gh a r d w a r er e s o u r c e sa n d i m p m v i n gt h es e a r c he f f i c i e n c y t h i sa r t i c l ef i r s t l yi n t r o d u c e st h eb a s i cp r i n c i p l e so fc r a w l e r , a n dt h e nd i s c u s s e s t h ek e yt e c h n o l o g i e so ft o p i c a lc r a w l e rs u c ha sc h i n e s ew o r ds e g m e n t a t i o n ，t h e m a t i c j u d g m e n ta p p r o a c h ，t h ee s t a b l i s h m e n to ft h e m a t i cv e c t o r , m a i n l yf o c u s e so nt h e c r a w l i n gs t r a t e g i e so ft h et o p i c a lc r a w l e r t h i sp a p e rd e s c r i b e se a c ht y p eo f r e p r e s e n t a t i v ea l g o r i t h m so fc r a w l i n gs t r a t e g y , a n a l y z e st h e a d v a n t a g e s a n d d i s a d v a n t a g e so ft h e s ea l g o r i t h m sa n dp r o p o s e st h ei m p r o v e da l g o r i t h mm e t h o d t h i sp a p e rt r i e st oi m p r o v et h ew o r dw e i g h tc a l c u l a t i o nm e t h o do ft h et r a d i t i o n a l v e c t o rs p a c em o d e l ：g i v i n gt h ed i f f e r e n tw e i g h to nt h ew o r d so fd i f f e r e n tl o c a t i o n s ； i m p r o v i n gt h eu n r e a s o n a b l el i n k so fh i t sa l g o r i t h ma n ds t r e n g t h e n i n gt h er e l a t i o n s w i t he a c ho t h e r ；w h e ne x t e n d i n gr o o ts e t ，i faw e b s i t ebh a sno fw e bp a g e sw h i c h p o i n tt ot h ew e bp a g eao fa n o t h e rw e b s i t e ，t h ew e i g h to ft h o s el i n k ss e t1 n ，t h e w e i g h to ft h eo t h e rl i n k sa l es t i l l s e tt o1 i nv i e wo ft h es h a r k s e a r c ha l g o r i t h m l e a d i n gt o “s h o r t - s i g h t e d a n dh i t sa l g o r i t h ml e a d i n gt o t o p i cd r i t t ”，i tc o m b i n e st h e a d v a n t a g e so fb o t hc o n t e n t b a s e ds h a r k - s e a r c ha l g o r i t h ma n dl i n k i n gr e l a t i o n b a s e d h i t sa l g o r i t h ma n df o r m st w on e wt o p i c a lc r a w l e ra l g o r i t h m ：s - h i t sa l g o r i t h ma n d m t - h i t sa l g o r i t h m ，a n di m p l e m e n t st h e m e x p e r i m e n t ss h o wt h a tt h en e wa l g o r i t h m s h a v ec e r t a i ne 位c t s k e y w o r d s ：v e r t i c a ls e a r c he n g i n e t o p i c a lc r a w l e rc r a w l i n gs t r a t e g y i i - 海南大学硕+ 学位论文 目录 目录 1 序言l 1 1 论文的背景l 1 2 国内外研究现状2 1 3 研究的目的及意义3 1 4 本文的组织工作3 2 主题爬虫的工作原理及关键技术5 2 1 爬虫原理5 2 1 1 通用网络爬虫的工作原理5 2 1 1 主题爬虫的工作原理6 2 2 主题相关度计算7 2 2 1 向量空间模型8 2 2 2 布尔模型1 l 2 2 3 贝叶斯方法1 l 2 3 中文分词简介1 2 2 3 1 中文分词1 2 2 3 2 常用的分词算法1 3 2 3 3 常见的中文分词开源项目1 4 2 4 主题向量的建立1 5 2 5 本章小结1 5 3 爬虫的爬行策略研究1 6 3 1 传统网络爬虫的爬行策略1 6 3 2 主题爬虫的爬行策略1 7 3 2 1 基于内容的主题爬行策略1 7 3 2 2 基于链接的主题爬虫爬行策略2 0 3 2 3 基于分类器的主题爬行策略2 6 3 3 本章小结2 7 4h i t s 算法及其改进2 8 4 1h i t s 算法的基本思想2 8 4 2h i t s 算法的过程2 9 4 2 1 构造w e b 子图2 9 4 2 2 计算权威值和中心值3 1 4 3h i t s 算法的优缺点3 3 4 4s - h it s 算法3 4 4 5m t h i t s 算法3 8 4 6 本章小结4 1 海南大学硕十学位论文目录 5 系统设计及实验。4 2 5 1 系统开发环境4 2 5 2 系统开发的目标4 2 5 3 系统设计4 2 5 4 爬虫主要类介绍4 5 5 5 系统界面4 7 5 6 实验结果及分析4 8 5 7 本章小结5 1 总结与展望5 2 参考文献5 3 攻读硕士学位期间发表的论文5 7 后记5 8 海南大学硕士学位论文 1 序言 1 序言 1 1 论文的背景 随着互联网的迅速发展，网络对我们的影响已越来越大。w e b 技术作为 互联网发展最为迅速的技术之一，以其方便简单的使用方式和丰富的表达能力， 已慢慢成为互联网上最重要的信息发布和传输方式。然而随着w e b 信息的急剧增 加，一方面网上的信息种类繁多、丰富多彩，而另一方面用户却很难找到他们所 需要的信息。搜索引擎就是在这样的背景下出现的，并且已经发挥出越来越重要 的作用，已成为人们从浩瀚的信息海洋中获取信息的重要工具之一。最新调查显 示【l j ：2 0 0 9 年中国网民中有7 3 3 的通过搜索引擎获取信息。搜索引擎技术已成 为计算机工业界和学术界争相研究、开发的对象，据艾瑞发布的0 9 年中国搜 索引擎年度数据报告显示2 0 0 9 年中国搜索引擎市场规模以达6 9 5 亿元。目前 我国除了占国内市场份额6 0 左右的百度搜索引擎( w w w b a i d u c o m ) 外，各大 门户网站几乎都有自己的搜索引擎，如网易有有道搜索引擎( w w w y o u d a o c o m ) ， 新浪有爱问搜索引擎( w w w i a s k c o m ) ，搜狐有搜狗搜索引擎( w w w s o g o u c o m ) ， 腾讯有搜搜搜索引擎( w w w s o s o c o m ) 等。搜索引擎已经成为信息技术领域的重 要产业之一【2 1 。 随着互联网的信息量越来越大，人们对搜索引擎的要求也越来越高，传统搜 索引擎的局限性已经开始体现出来了，包括： ( 1 ) 覆盖率低。最近的研究表明，即使大型的搜索引擎( 如g o o g l e ) 对 w e b 的覆盖率也只有3 0 4 0 【3 】，单个搜索引擎很难索引所有的w e b 资源。 ( 2 ) 时效性差。互联网信息呈指数增长，但大量信息的存活期却很短，使 互联网充斥着大量无效或过时的链接，传统的搜索引擎很难剔除这些链接。 ( 3 ) 结果不准确。在传统的搜索引擎中进行一次搜索可以返回千万级甚至 上亿的结果，但真正有用的信息却只是小部分，如在g o o g l e 中搜索关键字“计 算机 ，却返回了七千万多条结果。 针对以上情况，另一种搜索引擎悄然出现，它可以在较小的范围内取得比传 统搜索引擎更令人满意的结果，以满足某些特定用户的需要，这就是垂直搜索引 擎( v e r t i c a ls e a r c he n g i n e ) 【4 j 。所谓垂直搜索是针对某一特定领域、某一特 定人群所提供的有一定价值的相关服务定向分字段抽取出相应信息进行处 理后再以某种形式返回给用户，是传统搜索引擎的细分和延伸。其特点就是专、 精、深，且具有行业色彩。它与传统搜索引擎不尽相同，垂直搜索引擎专注于纵 1 海南人学硕士学位论文1 序言 向服务，致力于某一个领域的内容，这个领域以外的其它信息将尽量不收录。这 样使得垂直搜索引擎索引的信息量大大减少，索引周期大大缩短，从而保证了对 该领域信息的及时更新，能够从根源上减少搜索时产生的“噪音，从而提高了 查询效率。 主题爬虫是垂直搜索引擎的核心部分。主题爬虫( t o p i c a lc r a w l e r ) 又称为 聚焦爬虫( f o c u s e dc r a w l e r ) 【5 j ，就是有选择的遍历w e b 页面，并抓取那些与预 定主题相关的网页，而避免抓取与主题无关的网页。对于目前的w e b 规模来说， 利用爬虫技术爬行整个互联网是不可能的，而爬行互联网中的小部分，即有选择 的爬行某一个主题( 领域) 则是确实可行的。主题爬虫基于这样一个重要的假设： 相同主题或相近主题的网页趋向于互相连接，被称为w e b 上的主题局部性【6 】。主 题爬行目标就是保持访问主题相关的网页及其周围的网页，而不偏离主题网页。 一个理想的主题爬虫就是最大限度的抓取主题相关的网页，尽量少的抓取主题不 相关的网页。因此主题爬虫在很大程度上能节省硬件资源和网络资源，从而提高 检索效果。以何种策略遍历w e b 资源，成为近年来主题爬虫研究的焦点之一【7 j 。 1 2 国内外研究现状 主题爬虫最早是由d eb r a 等【8 j 提出的，该文将主题爬虫遍历w e b 的过程比 喻成鱼觅食的过程，将w e b 比喻成池塘，将网页比喻成鱼的f o o d ，页面中包含 的链接比喻成鱼的c h i l d r e n ，使用多线程下载网页，采用基于关键词和规则表达 式的匹配，从相关网页跟踪更多的链接。 s h a r k s e a r c h l 9 1 是对在f i s h s e a r c h 的基础上改进而成。爬虫从一个特定网页 开始并跟踪相关文本的链接，它使用向量空间模型来计算特定网页的主题相关 性，子网页继承父页的主题相关性值，并通过一些衰减系数进行修改。子结点的 主题相关性值受3 个因素影响：锚文本、锚文本附近的文字以及对父结点主题相 关性的继承。 文献【1 0 】中描述了一个改进的b e s tf i r s ts e a r c h 爬行策略，主题相关的页面有 时候是通过一序列主题不相关网页连接在一起的，那么爬虫在遇到主题不相关页 面时不是马上停下来而是继续向前爬行，当遇到主题不相关页面的数量达到一个 阈值时才放弃，即使用了通道( t u n n e l i n g ) 机制来克服b e s tf i r s ts e a r c h 爬行策 略所存在的缺陷。 针对基于关键词主题判断的不足，文献 1 1 】提出了基于本体( o n t o t o l g y ) 的算法来计算网页相关度。算法对网页抽出实体，对相同或相近意思的特征词进 行合并，将文本表示成相关概念的向量，这样可以大大降低向量的维数，而且可 以克服同义词问题。 2 海南大学硕士学位论文 1 序言 马亮等【1 2 l 在设计主题爬虫时考虑网页的标题、段落标题和锚文本等因素评 价网页不同区域，从而使网页的不同区域拥有不同重要程度，提高了主题判断的 准确性。 文献【1 3 】中提出了基于分类器的主题爬虫。该方法使用贝叶斯分类器并利用 网页中的内容和锚文本对链接进行计算，这样每个链接都有主题预测值，然后根 据这个预测值进行爬行。通过测试表明，与普通的爬虫相比，该主题爬虫能更多 的发现主题相关资源。 s r i r a mr a g h a v a n 等提出了针对暗网( d e e pw e b ) 的主题爬虫，主要是结合 领域的相关知识生成合理的查询关键词然后提交给查询接口，获得查询结果【1 4 】。 文献 1 5 】中提出了用户冲浪式的挖掘算法，即对某一特定的查询相关的网页 做相似性建模。该方法以公共域名代理的用户日志为参考，通过对大量的书籍信 息进行过滤，统计处了三种需要考虑的信息：用户对有不同特征的网页访问频率： 用户对不同网页的访问频率；用户对拥有相同或相近主题的网页访问的时间局域 性。 美国卡内基梅隆大学的a k m c c a l l u m 和m n i g a m 等人设计了c o r a 怕l 系统， 它利用机器学习( m a c h i n el e a r n i n g ) 技术，在互联网上搜索与计算机相关的论 文。它通过找出文章的题目、作者、摘要和参考文献等，利用文本分类的方法将 其按y a h o o 分类目录进行分类。 1 3 研究的目的及意义 网络中信息资源过于丰富，而与某个主题相关的网页是非常有限的，仅仅是 整个信息空间的很小部分，我们的硬件资源也是有限。因此极有必要研究高效的 主题爬虫策略，从而在有限的时间和硬件资源条件下，搜集到尽可能多的高质量 的与预定主题相关w e b 网页，进而提高网络带宽利用率和整个检索系统的查全 率、查准率和搜索效率。目前主题爬虫可以在很多领域得到应用，如个性化信息 检索【17 1 ，数字图书馆【1 3 】，专业数据集的获取【1 9 1 等方面。因此本课题的研究是一 个极富挑战性的研究课题，同时也具有重要的研究意义。 1 4 本文的组织工作 本文的章节主要是围绕主题爬虫的一些关键技术展开研究，重点研究了主题 爬虫的爬行策略，内容安排如下： ( 1 ) 绪论。主要介绍了主题爬虫研究的背景，国内外研究现状和主题爬虫 研究的意义。 - 3 - 海南人学硕士学位论文1 序言 ( 2 ) 主题爬虫的工作原理以及关键技术。首先介绍了传统网络爬虫以及主 题爬虫的工作原理；接着介绍了主题爬虫关键技术：主题相关度计算的几种方法， 并对这几种方法的优劣进行评价，针对向量空间模型的不足并对其进行改进；中 文分词以及中文分词的相关算法，并对几种分词方法进行比较；最后简单介绍了 主题向量的建立方法。 ( 3 ) 爬虫的爬行策略研究。首先介绍了传统网络爬虫的几种爬行策略，接着 详细介绍了主题爬虫的爬行策略，如s h a r k s e a r c h 算法和p a g e r a n k 算法等，并 对这几种爬行算法的优缺点进行了分析。 ( 4 ) h i t s 算法及其改进。首先详细的介绍了h i t s 算法的基本原理，接着介 绍了h i t s 算法的具体计算过程以及对其优缺点进行分析；最后对h i t s 算法进行 改进，形成s - h i t s 算法和m t h i t s ，并对这两种爬行算法进行了详细的介绍。 ( 5 ) 系统设计及实验。首先简单的介绍了一下系统开发环境以及程序中的主 要类；接着介绍了系统运行的结果并对结果进行了分析。 ( 6 ) 结论。首先对本文的工作进行了简单总结，接着针对本系统的工作列举 了下一步要继续进行的工作。 海南大学硕士学位论文 2 主题爬虫的_ r ：作原理及关键技术 2 主题爬虫的工作原理及关键技术 各种垂直搜索引擎虽形式各异，但基本原理都差不多，通常分为四大模块：主 题爬虫模块、索引模块、信息检索模块和用户接口模块。主题爬虫是垂直搜索引 擎的核心部分，在垂直搜索引擎中占有重要位置，既决定了垂直搜索引擎中索引 库的大小，也对垂直搜索引擎的查准率和查全率都有重要的影响，所以主题爬虫 设计的好坏直接影响搜索效果。因此本论文主要研究专业搜索引擎的数据准备部 分主题爬虫模块，本章接下来将详细介绍主题爬虫的工作原理及其关键技 术。 2 1 爬虫原理 2 1 1 通用网络爬虫的工作原理 网络爬虫是一个自动从互联网上下载网页等网络资源的应用程序，是搜索引 擎的重要组成部分。 传统搜索引擎的后台大都是采用了一个或多个通用的网络爬虫程序，为了能 够满足用户的各种各样的查询，需要较高的w 曲覆盖率，因此通常采用深度优 先或广度优先的爬行策略。 一个网络爬虫系统其实就是一个批量获取w e b 网页的程序，从初始种子链 接开始，然后下载其所指向的网页，同时对下载的网页进行解析，提取出网页中 的链接，如果这些链接没有访问过则将其加入待下载队列中，不断重复这个过程 直到下载队列为空或其它条件时停止。另一方面，爬虫程序要注意爬行的规则， 必须避免站点的负荷过重，一次y a h o o 的爬虫爬行淘宝网时使得淘宝网站不稳 定，造成用户访问受到影响，爬虫程序还得遵守r o b o t s t x t 文件规则。 网络爬虫必须处理大规模的数据，有的爬虫一边下载一边进行索引，有的是 下载完毕后再进行索引。网络爬虫必须处理链接的访问顺序以及舍弃一些不必要 的链接如广告链接等。将如此大规模的网页组织并存储在本地还应注意数据的组 织形式。整个互联网中的w e b 网页构成一个巨大的有向图，爬虫的任务就是从 某些节点开始，遍历这个有向图，并下载其中的结点。传统网路爬虫的基本工作 流程图如下图2 1 所示： 传统的网络爬虫一般都维护三个u r l 队列：待下载u r l 队列，已经下载u r l 队 列，出错u r l 队列。待下载队列是一个用来存放待下载链接的数据结构，爬虫从 这些链接中选取链接进行访问。最初下载的时候，待下载队列是空的，把选取的 海南大学硕十学位论文2 主题爬虫的工作原理及关键技术 种子u r l ( 一个或多个链接) 加入到待下载队列中初始化爬虫程序。爬虫程序运 行后，网页中的链接不断被解析并插入待下载队列中，作为以后的抓取的对象。 如果一个u d 已经成功下载则将其从待下载队列中删除，然后将其加入已下载u n 队列；如果下载的过程中遇到过期的死链就将该u r l 放入下载出错u d 队列中。 一般都是采用多线程下载，一个线程负责下载一个网页。网络爬虫在爬行时待下 载队列中的链接会不断增多，会影响查找下一个链接的速度，必须进行优化或采 取其它措施限制链接的数量。 足 图2 1 通用爬虫的工作流程 2 1 1 主题爬虫的工作原理 主题爬虫的基本思路是按照预定的主题，分析链接或已经下载的网页内容， 来预测下一个要爬行的链接，尽可能多的抓取与主题相关的网页，因此要解决以 下几个关键问题：( 1 ) 如何判断一个w e b 网页内容是否与预定主题相关，这个 可以采用传统的文本分类的技术实现；( 2 ) 如何决定待下载队列中u r l 的访问次 序，主题爬虫一般采取如下措施：根据相关因素给待下载的u r l 打分，根据得分 高低决定访问的先后顺序。而这个分值一般根据网页的内容与预定主题相关的程 度或是根据链接之间的相互关系等因素决定。不同主题爬虫的主要区别也就是在 给u r l 打分的策略上。 主题爬虫是在通用爬虫的基础上扩展的，所以主题爬虫的工作流程也跟通用 海南大学硕士学位论文 2 主题爬虫的j i ：作原理及关键技术 爬虫的流程差不多。主题爬虫在爬取初始阶段也需要初始化队列，将一个或多个 种子w l 加入待下载队列中，这些种子u r l 都是经过挑选的与主题高度相关的链 接，一般通过搜索引擎获取并经过人工挑选得到。主题爬虫系统与通用爬虫系统 遍历w e b 页面的原理类似。在下载完一个网页后要对该网页进行去掉“噪音 处理，从中抽取特征信息和超链接信息，按事先制定好的网页相关度判定规则分 析网页的主题相关性，如果得出的主题相关性值大于某阈值则认为该网页主题相 关，保存该网页，提取当前网页的超链接，过滤掉不合法( 不符合u r l 正则表达 式) 的u r l ，计算符合要求的u r l 主题得分，一般根据父网页主题相关度和链接关 系等因素计算该值，然后加入待下载队列中。那么下次主题爬虫将从下载队列中 取出得分最高的u r l 进行下载，直到满足相应条件停止。主题爬虫也要维护待下 载u r l 队列，已下载u r l 队列，出错u r l 队列。主题爬虫的基本工作流程如下图2 2 所示。 2 2 主题相关度计算 图2 2 主题爬虫的工作流程 垂直搜索引擎与通用搜索引擎最大的区别在于垂直搜索引擎只限定某个领 7 海南大学硕士学位论文2 主题爬虫的工作原理及关键技术 域，而通用搜索引擎则不限定领域，因而垂直搜索引擎只索引与预定主题相关的 网页，与主题无关的网页则丢掉。主题爬虫将网页下载到本地后，需要判断网页 的主题相关性，只有大于某个值的网页才被保存并索引。主题相关度的判断直接 影响了垂直搜索引擎的成败。目前主题相关度的计算方法主要有向量空间模型、 布尔模型、贝叶斯方法等，但主要使用向量空间模型。 2 2 1 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ) 【2 0 】是目前应用较多的信息检索模型之 一，它是由s a l t o n 等人提出来的。向量空间模型基于如下假设：一个文档所属于 的类别仅与文档中的特征词以及特征词在该文档中的频率有关，而与特征词在文 档中的先后顺序无关。向量空间模型与机器学习算法的紧密结合和成功运用，迅 速使向量空问模型成为文本分类中表示文本的主流方法。向量空间模型的基本概 念描述如下： 文档：泛指文献或文献中的片段，一般指一篇文章，本文中主要是指w e b 网页。在信息检索领域中，可以认为文档就是文本。 特征词：在向量空间模型中一般从一篇文档中抽出最能代表文档内容的基本 语言单位( 字、词、词组或短语等) 来代表这篇文档，那么这些基本的语言单位 就是特征词，即文档可以用特征词表示成d ( t l ，t 2 ，t o ) ，其中t i 表示文档 d 中的第i 个特征词，n 表示特征词的个数，其中1 i n 。也就是说一个向量 空间是由各个特征词组成，每个特征词表示向量空间中的一个维。 特征词的权重：在一个文档中，每个特征词的重要程度可能不一样，使用权 重w 加以区分，以表示该特征词在该文档的重要程度，则文档就可以表示为d ( t l ，w l ；t 2 ，w 2 * ：t n ，w n ) ，因为特征词的顺序固定，所以一般简写为d ( w i ，w 2 ，w n ) 。 向量空间模型忽略特征词在文本中的先后顺序，将文档d 抽象成以特征词的 权值为分量的特征向量d ( w l ，w 2 ，w n ) ，即把t l ，t 2 ，t 。看成n 维 的坐标系，而w l ，w 2 ，w n 为其相应的坐标值，因而文档d ( w l ，w 2 ， w 。) 被看成n 维空间中的一个向量，称d ( w l ，w 2 ，w 。) 为文档d 的特征 向量，其中t i 是第i 个特征词，w i 为其特征权重。 两个文本d i 和d j 之间的相关程度可以用它们的相似度s i m ( d i ，d j ) 来度量。 在计算网页的主题相关度时，将要判断的网页内容和能代表某个主题的特征词集 合表示成向量d ( w i ，w 2 ，w n ) 和t ( t i ，t 2 ，t f i ) 。当文档被表示为 向量时，我们可以借助与向量之间的某种距离来表示文档间的相似度。常用向量 之间的内积进行计算： 海南大学硕士学位论文 2 主题爬虫的j t ：作原理及关键技术 打 s i m ( d i ，t ) = ( ) k - i 或者用夹角的余弦值表示 s i m ( d i ，t ) = 打 ( ) k = l ( 2 1 ) ( 2 2 ) 其中，1 1 为文本向量的维数，w 。为文档d 。的特征词t 。的权重，w k 为主题向 量t 的第k 个特征词t 。的权重。 图2 3 为三维空间的两个文本特征向量。 图2 - 3 向量空间中的两个向量 另一个很重要的问题就是特征词的权重确定问题，目前最流行的方法是运用 统计的方法，即用文本的统计信息( 主要是指词频) 给特征词赋权重。最初的特 征词权重计算方法是o 、1 赋值法，即如果特征词在文档中出现，不管出现多少 次，该特征词的权重为l ，否则为o 。这种方法无法体现出不同特征词在文本中 的不同作用程度，也不能体现词频的重要程度，所以0 、1 赋值法逐渐被更精确 的词频统计代替。词频分为绝对词频和相对词频，绝对词频即使用特征词在文档 中出现的频率表示，相对词频为归一化后的词频，其计算方法主要运用t f - i d f 公 式，其中t f ( t e r mf r e q u e n c y ) 是特征词在文本中的绝对频率，i d f ( i n v e r t e dd o c u m e n t 9 海南大学硕士学位论文2 主题爬虫的工作原理及关键技术 f r e q u e n c y ) 表示特征词在文本中的文档内频数即含有某特征词的文档数与总文档 数的比值，目前存在多种t f - i d f 形式，其中最基本的一种形式为： w i j = f r e q 0 x l o g ( n n i ) ( 2 3 ) 其中，w i i 为特征词t i 在文档d j 中的权重，f r e q i j 为特征词t i 在文档d j 中的频 率( 如特征词在文档d j 中出现的次数) ，n 为文档总数，n i 为包含特征词t i 的文 档数。 文档经过分词后，首先去除停用词，合并人名等词汇，然后统计词频，最终 表示为上面描述的向量。 向量空间模型的主要优点在于： ( 1 ) 特征词加权改进了主题相关性判断的效果。 ( 2 ) 采用部分匹配的策略能够使得不同的文献体现出差别。 ( 3 ) 采用一定的相似度计算方法可以使得u r l 得分体现出差别，从而在爬虫 可以选择最高得分的u r l 进行下载。 向量空间模型虽然是目前最流行的信息检索模型，但也存在不足之处。在将 文档表示成向量的时候假设文档中的特征词之间是相互独立的，也就是说在计算 特征词权重时没有考虑其它词对该词的影响，但现实语言环境中同一文档的很多 特征词之间是有相互联系的。也就是说向量空间模型不能将特征词之间的相互关 系体现出来，从这一点来看向量空间模型依然不够完善。在实际过程中假设特征 词之间独立的计算特征词方法效果不错，而且计算量较小。实际上要在计算特征 词的权重时体现特征词之间的关系是比较困难的。 本系统中的主题判断也是采用向量空间模型的，但其权重的计算方法在传统 的基础上有所改进。传统权重的计算方法只是简单的考虑特征词在文本中出现的 频率，而没有考虑相同的特征词在文章的不同位置可能有不同的影响力，这是不 大合理的，如特征词在标题出现跟在正文中出现的重要程度肯定不一样。如果在 计算权重的同时考虑特征词在文本不同位置的重要程度将能提高特征词的不同 影响力，从而更准确的判断文章主题。在本系统中主要考虑了两点：一是特征词 在标题中的重要程度较高，文章的标题是整个文章内容的概括，所以重要程度要 高些；二是认为每一段话中第一句话较为重要，故特征词在每段第一句时应给予 较大的权值，其相对权重比标题的权重小。 j l w i j 22 k l o g ( n n i ) f r e q ( 2 4 ) 七。l 其中， 五表示文档的第k 个部分的权重系数值，m 表示文档总共分为m 个 部分，其它参数意义跟公式( 2 3 ) 相同。 海南大学硕士学位论文2 主题爬虫的t 作原理及关键技术 2 2 2 布尔模型 布尔模型【2 l 】是基于集合理论和布尔代数的一种简单的检索模型。由于集合 的概念比较直观，布尔代数的结构简单，因此布尔模型可以简单地表示文档，并 判断文档间的相似度关系。布尔模型为主题判断提供了一个简单的、可操的框架。 在标准的布尔模型中，将文档表示成： d ( w l ，w 2 ，w n ) 其中，n 是主题特征词的个数，w i 的值为1 或o ，分别表示特征词t i 在文献 d 中出现或不出现。由此可见，布尔模型中的文档表示是向量空间模型中文档表 示的特殊形式，它只采用二元的权值。预定主题也是以关键词集合的向量形式来 表示。判断文档与某主题的相关度，就相当于是计算两个关键词集合的交集。对 基于布尔模型的主题判断模型来说，交集中含有的元素个数越多，则认为与主题 的相关性越高。 布尔模型最主要的缺点是它不支持设定关键词的相对重要性，在查询的布尔 表达式中，查询字符串中的关键词是不区分重要性高低的。但是，其优点也非常 明显，它简单，易于实现，计算代价较小。 2 2 3 贝叶斯方法 贝叶斯方法【2 2 】是一种比较常用的有指导意义的方法，以贝叶斯定理为理论基 础，其特点是用概率去表示所有不确定性的形式，学习或者其它形式的推理也都 用概率规则来实现。具体步骤如下： ( 1 ) 将每一个文本用特征向量模型表示：d j - ( w l j ，、p ，w 。i ) 。 ( 2 ) 假设有m 个主题c l ，c 2 ，c m ，给定一个未知的样本x ，贝叶斯分 类器将预测x 属于具有最高后验概率的类，即： p ( c i l x ) p ( q l x ) 1 i ，j m 根据贝叶斯公式： p ( c 。i 炉盟掣 ( 2 5 ) p t x ) 其中，p ( xc ，) = np ( h ) ，概率p ( 也iq ) 可由事先的样本训练得出，如果 类的先验概率未知，则假定这些类的概率是相等的，即p ( c 1 ) = p ( c 2 ) = = p ( c m ) 。 计算出未知文档属于某个类的概率后，可以设定一个阈值，将概率值低于该 阈值的视为主题不相关文档。这种方法主要优点是有严格的数学理论基础，时间 复杂度较小，但在实现过程中的一些参数估计难度较大。 海南大学硕+ 学位论文2 主题爬虫的工作原理及关键技术 2 3 中文分词简介 2 3 1 中文分词 中文信息检索系统主要有两种检索方案：基于单字的检索和基于词的检索。 基于单字的检索按单字建立索引库，在检索时需要进行逻辑运算，效率较低： 基于词的检索按词建立索引库，检索时直接命中。基于词的检索方法具有检索速 度快、准确率高的优点，目前的中文信息检索系统大多支持基于词的检索。 中文文本不像英文那样在词与词之间有自然的分隔符空格，为了获得 词的信息，需要对文本进行自动的词语分割，这个过程就叫中文分词( w o r d s e g m e n t a t i o n ) 。中文分词是中文信息处理中最基本、最重要环节之一，国内已经 对这一领域进行了大量的研究，已经取得了许多重大成果，这些成果已经被应用 于很多领域如汉字拼音输入、语音识别、机器翻译等。其中，文献【2 3 】特别指出， 中文分词的精度和分词算法对中文信息检索系统的性能有着很大的影响，主要表 现在检索精度和召回率两个方面。目前中文分词面临着三个主要问题： ( 1 ) 分词规范 汉语是十分复杂的语言之一，词的概念不清晰，什么样的文字组合或多长的 文字能称为词，如何界定等都是比较困难的问题。 ( 2 ) 歧义识别 汉语中歧义是指同样的一句话，可能有两种或多种切分方法。例如短语“表 面的”，因为“表面 和“面的 都是词，那么这个短语就可以切分成“表面 的”和“表面的”两种方式。又如短语“化妆和服装”切分成“化妆和服装” 和“化妆和服装”都是可以的，由于没有人的知识去理解，计算机很难知道到 底哪个方案正确。 ( 3 ) 新词识别 新词专业术语称为未登录词，也就是在词典中查找不到的词。最典型的就是 人的名字，人可以很容易理解句子“刘鹏虎去北京了中，“刘鹏虎”是一个人 的名字，所以是一个词，但要是让计算机去识别就困难了。如果把“刘鹏虎”作 为一个词收录到词典中去，全世界有那么多人名，而且几乎每时每刻都有新的名 字诞生，新词中除了人名以外，还有机构名、地名、产品名、简称、省略语等， 这些未登录词的构词规律各异，数量众多，不可能全部收入词典中1 2 4 1 。但这些 又是人们经常使用的词，因此对于搜索引擎来说，分词系统中的新词识别十分重 要。目前新词识别率已经成为评价一个分词系统好坏的重要标志之一。识别新词 的方法主要有两种，其一是基于规则的方法，其二是基于统计、机器学习的方法。 海南大学硕士学位论文 2 主题爬虫的工作原理及关键技术 2 3 2 常用的分词算法 目前中文分词的方法较多，其中最常用的方法有正向最大匹配法、逆向最大 匹配法、双向最大匹配法、设立切分标志法、最佳匹配法、基于统计的分词方法 和基于理解的分词方法等等。这些方法虽然名称各异，分词的速度也不尽相同， 但是从本质上可以将它们归为三类，即基于字符串匹配的分词方法、基于统计的 分词方法以及基于理解的分词方法。 ( 1 ) 基于字符串匹配的分词方法 这种方法又称机械分词方法，是按一定的策略将待切分的字符串去匹配词典 中的词条，如果匹配成功，则切分成一个词【2 5 1 。按照扫描的方式不同，又可以 分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配等。常用的几种机械分词方法如下： 最大匹配方法。正向最大匹配、反向最大匹配和双向最大匹配三种方法都属 于最大匹配方法。正向最大匹配是将待分析语句从左到右每次取最长短语进行匹 配，反向最大匹配则反过来每次从右到左取最长词进行匹配。双向匹配则是同时 进行正向和反向匹配，然后对两种匹配结果的不同地方再利用一定的规则进行歧 义消除。最大匹配方法对于某些复杂的交集型歧义也会遗漏，但是该方法实现比 较简单，切分速度较快。统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ， 而单纯使用逆向最大匹配的错误率为1 2 4 5 。但这种精度还远远不能满足实际的 需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用 各种其它的语言信息来进一步提高切分的准确率。 全切分法。该算法主要是利用词典