（计算机软件与理论专业论文）主题爬虫关键技术研究及应用.pdf

浙江工业大学硕士学位论文 主题爬虫关键技术研究及应用 摘要 近年来，随着w e b 信息资源的快速增长，通用搜索引擎存在无法检索所有页面的问题， 也不能满足人们日益增长的个性化服务需要，因此各类适应特定人群需要的主题搜索引擎 应运而生。为保证主题搜索引擎返回信息的准确性，开展对承担主题相关信息采集任务的 主题爬虫系统研究具有重要意义。 主题爬虫的基本工作原理是按照预先确定的主题，分析超链接和所抓取的网页内容， 获取下一个要爬行的u r l ，尽可能保证多爬行与主题相关的网页。在主题爬虫系统研究中， 主要涉及主题基准模型、网页分析方法和网页搜索策略等方面的内容。主题基准模型是爬 虫判别所抓取网页主题是否相关的依据，其研究重点是如何建立合适的主题基准模型以及 主题基准模型和待判别网页的映射关系，以提高对所抓取网页的主题性判别；网页分析方 法主要分析所抓取网页的内容和超链接，研究如何对网页内容进行正确提取，以获取网页 所表示的主题，避免网页主题提取粒度不够影响对该网页的主题相关度判别；网页搜索策 略主要解决待访问u r l 的次序问题，提高主题爬虫覆盖度。目前的研究主要集中在通过预 测u r l 的主题相关来决定u r l 访问次序，但这样又容易使主题爬虫陷入局部寻优的状态。 基于上述分析，本文主要从主题基准模型、网页分析方法和网页搜索策略三方面展开 研究，设计和构建相应的主题爬虫系统框架，并以信用主题为应用，实现主题爬虫原型系 统，并对相应的实验结果进行分析比较。本文主要研究工作包括以下几个方面： 1 、对主题爬虫系统的结构开展研究，从提高主题爬虫抓取质量的角度出发，将主题 基准模型、网页分析方法和网页搜索策略三个重要组成部分进行分析整合，设计了主题爬 虫系统的框架。 2 、从主题基准模型建立方法和待判别网页主题抽取上展开研究，通过统一主题基准 模型和待判别网页的主题关键词的权重设置，来提高爬虫对网页的主题性判别。 3 、针对常用的基于网页结构内容块提取方法中提取正文粒度不够细问题，本文采用 基于t a g w i n d o w 标签窗e l 进行网页正文提取，以适应于正文篇幅长和正文中链接比较少的 i 浙江工业大学硕士学位论文 网页类型。 4 、为提高主题相关资源发现率，针对现有主题爬虫存在无法访问链接不可达资源， 无法跨越主题团之间的主题不相关链接等问题，本文对自适应遗传算法网页搜索策略展开 研究，以缓和上述隧道问题。 5 、以信用主题为应用实现主题爬虫原型系统，并对相应的实验结果进行分析比较。 关键词：主题爬虫，自适应遗传算法，网页分析方法，信用主题模型 浙江工业大学硕上学位论文 r e s e a r c ha n da p p l i c a t i o no ff o c u s e d c r a w l e rk e yt e c h n o l o g y a b s t r a c t i nr e c e n ty e a r s ，w i t ht h er a p i dg r o w t ho fw e bi n f o r m a t i o n r e s o u r c e s ，s p e c i f i ct o p i cs e a r c h e n g i n ei sd e s i g n e dt oa d d r e s st h ep r o b l e mo fg e n e r a ls e a r c he n g i n e sw h i c hc a nn o tr e t r i e v ea l l t h ep a g e sr e l a t e da n ds a t i s f yp e o p l e sg r o w i n gn e e d so fp e r s o n a l i z e ds e r v i c e i ti so fg r e a t s i g n i f i c a n c ef o rr e s e a r c h e r st os t u d yt h ei n f o r m a t i o nc o l l e c t i o nr e l a t e dt o p i c a lc r a w l e rs y s t e mt o e n s u r et h et o p i c a ls e a r c he n g i n er e t u r n st h ei n f o r m a t i o na c c u r a t e l y t h eb a s i cw o r k i n gp r i n c i p l eo ft o p i c a lc r a w l e ri sb yd e p e n d i n go nap r e - d e f i n e ds u b j e c t , a n a l y z i n gt h eh y p e r l i n ka n dt h ec r a w l e dc o n t e n t ，a n de x t r a c t i n gt h en e x tu r ln e e d e dt oc r a w l ，t o e n s u r et h et o p i c a lc r a w l e rc a l lc r a w lt h et o p i cr e l a t e dp a g e s 铺m u c ha sp o s s i b l e t h es t u d yo f t o p i c a lc r a w l e rs y s t e mm a i n l yi n c l u d e ss u b j e c tb a s e l i n em o d e l ，w e b p a g ea n a l y s i sm e t h o d , w e b p a g es e a r c hs t r a t e g y , e t c s u b j e c tb a s e l i n em o d e li st h eb a s ep a r tf o rt h et o p i c a lc r a w l e rt o j u d g ew h i c hs u b j e c to ft h ec r a w l e dp a g e sr e l a t e dt op r e - d e f i n e ds u b j e c t i no r d e rt oe n h a n c et h e j u d g m e n t a la b i l i t yo ft h et o p i c a lc r a w l e r ，t h i ss t u d yt r i e st oa n s w e rq u e s t i o n sa sf o l l o w s ：h o wt o e s t a b l i s ha na p p r o p r i a t es u b j e c tb a s e l i n em o d e la n dh o wt oe s t a b l i s ht h em a p p i n gr e l a t i o n s h i p b e t w e e ns u b j e c tb a s e l i n em o d e la n dt h ew e b p a g e sn e e d e dt oj u d g e w e b p a g ea n a l y s i sm e t h o d m a i n l ya n a l y z e st h ec o n t e n ta n ds u p e rl i n k so fc r a w l e dw e b p a g e i no r d e rt oa v o i dm i s j u d g m e n t o ft h es u b j e c to ft h ec u r r e n tw e b p a g e s ，t h ew e b p a g ea n a l y s i sm e t h o df o c u s e so nh o wt oo b t a i n r i g h ts u b j e c to ft h ec r a w l e dw e b p a g eb yt h er e s e a r c ho ft h er i g h tm e t h o do fe x t r a c t i n gw e b p a g e b o d yt e x t w e b p a g es e a r c hs t r a t e g ym a i n l ya d d r e s s e st h ep r o b l e mo ft h ea c c e s so r d e ro fu r l si n w a i t i n gq u e u et oi m p r o v et h ec o v e r a g er a t eo ft o p i c a lc r a w l e r t h ec u r r e n ts t u d yf o c u s e so nt h e p r i o r i t yo ft h eu r l t od e t e r m i n et h ea c c e s so r d e rb yp r e d i c t i n gt h et o p i c a lr e l e v a n to ft h eu r l ， b u ti ti se a s yf o rt o p i c a lc r a w l e rt og e ti n t oas t a t eo fl o c a lo p t i m i z a t i o n b a s e do nt h ea b o v ea n a l y s i s ，t h i sp a p e rm a i n l yd ot h r e ea s p e c t so fr e s e a r c h e sw h i c h i n c l u d e ss u b j e c tb a s e l i n em o d e l ，w e b p a g ea n a l y s i sm e t h o da n d w e b p a g es e a r c hs t r a t e g y o nt h e b a s i so ft h ea p p l i c a t i o no fc r e d i ts u b j e c t ，ac o r r e s p o n d i n gt o p i c a lc r a w l e rs y s t e mf r a m e w o r ki s d e s i g n e da n db u i l t ，a n ds o m ec o r r e s p o n d i n ga n a l y s i sa n dc o m p a r i s o no fe x p e r i m e n t a lr e s u l t sa r e i t t 塑婆三些奎兰堡圭兰垡笙奎 _ _ - _ 一 d o n eb a s e do nt h ei m p l e m e n to f t h ep r o t o t y p es y s t e m t h i sp a p e ri n c l u d e st h ef o l l o w i n ga s p e c t s ： 1 i no r d e rt oi m p r o v et h ef e t c h e dr e s u r ，t h i sp a p e re x p a n d s t h er e s e a r c ho nt h es t r u c t u r eo f t o p i c a lc r a w l e rs y s t e mb yi n t e g r a t i n gs u b j e c tb a s e l i n em o d e l ，w e b p a g ea n a l y s i sm e t h o da n d w e b p a g es e a r c hs t r a t e g yw h i c ha r ei m p o r t a n tc o m p o n e n t st o g e t h e r ，a n dd e s i g n s af r a m e w o r kf o r t o p i c a lc r a w l e rs y s t e m 2 t h i sp 印e re x p a n d sr e s e a r c ho nt h ee s t a b l i s hm e t h o do fs u b je c tb a s e l i n em o d e l a n dt h e e x t r a c t i o no fw e b p a g en e e d e dt oj u d g e ，t oi m p r o v et h ea b i l i t yo fs u b j e c tj u d g m e n tb y u n i f y i n g t h ek e y w o r d sw e i g h ts e t t i n gi nb o t hs u b j e c tb a s e l i n em o d e l a n dw e b p a g ew h i c hn e e dt oj u d g e 3 r e g a r d i n gt h ee x t r a c t i o nm e t h o db a s e do nw e b p a g es t r u c t u r ec o n t e n tb l o c kh a s c o a l 8 e g r a n u l a r i t y ，t h i sp a p e ra d o p t st h ee x t r a c t i o nm e t h o d b a s e do nt a g w i n d o w ，i no r d e rt oa d j u s tt h e t y p eo fw e b p a g ew h i c hc o n t a i n sl o n gc o n t e n t sa n dh a s f e ws u p e rl i n k si nb o d yt e x t 4 h lo r d e rt or a i s et o p i c a lr e l a t e dr e s o u r c ed i s c o v e r yr a t e ，t h i sp a p e re x p a n d sr e s e a r c ho n s e i fa d a p t i v eg e n e t i ca l g o r i t h ms e a r c hs t r a t e g yt o a l l e v i a t et h ea b o v em e n t i o n e dt u n n e l i n g p r o b l e m 5 f i n a l l y b a s e do nt h ea p p l i c a t i o no fc r e d i ts u b j e c t ，t h i sp a p e rr e a l i z e s t h ep r o t o 帅e s y s t e mo ft o p i c a lc r a w l e rt od oc o r r e s p o n d i n ga n a l y s i sa n dc o m p a r i s o n o fe x p e r i m e n t a lr e s u l t s k e yw o r d s ：t o p i c a lc r a w l e r , s e l fa d a p t i v eg e n e t i ca l g o r i t h m ，w e b p a g ea n a l y s i sm e t h o d ， c r e d i ts u b j e c tm o d e l i v 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名： 吼中7 1 月哆日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密嘶 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 日期： 日期： 2 月 ，l 月 哆日 哆日 浙江工业大学硕士学位论文 1 1 选题背景 第1 章绪论 互联网的迅速发展和普及导致网上信息指数级增长，在信息的海洋中，为了能快速、 准确而又全面的得到所需要的信息，人们开发了网络检索工具，用户只需在诸如网络蜘蛛 ( s p i d e r ) 、机器人( r o b o t ) 的计算机程序中输入关键词，程序便会在其内部数据库中查询与关 键词相匹配的信息，按照一定的规则处理后通过网络提供给用户。这样的检索工具就称之 为搜索引擎【l 】。 目前的搜索引擎大多数是面向所有信息的，可以称之为综合型搜索引擎，但随着 i n t e r n e t 信息急剧膨胀以及信息多元化的发展，传统综合型搜索引擎的采集、素引、查询内 容不断扩大，对于用户高质量和多种类的要求也越来越显得力不从心【2 】：搜索引擎对w e b 的覆盖率只能达到3 0 4 ；页面采集失效率达到1 4 9 ；系统资源和网络资源极大浪费； 无法满足特定用户针对受限领域和面向特定主题的信息的需求。显然这种适用于所有用户 的综合型搜索引擎已经不能满足用户更深入的查询需求。针对这种情况，面向主题发现的 爬行技术应运而生，并且以其较高的目标化和专业化在当前搜索引擎发展与研究中占据了 一席之地。面向主题的爬行技术研究如何利用爬虫在网上进行选择性下载，努力避免无关 网页的下载，尽可能多地收集与特定主题相关的网页。 最近几年，随着我国经济体制改革的不断深入和债券市场的迅速发展，我国信用评级 业逐渐成长起来，人们开始普遍关注单位和个人的信用问题。虽然对信用信息的需求很大， 各种信息也很多，但如何有效获取信用信息依然是一个亟待解决的问题。 本文在这种背景下，针对信用主题信息获取比较困难的情况，对主题爬虫原理及关键 技术展开研究，构造主题爬虫系统框架，并以信用主题为应用，进行实现和验证。 1 2 论文研究意义 近年来，随着主题搜索引擎的不断发展，面向特定信息采集的主题爬虫已经成为当今 搜索领域的研究热点。而主题爬虫系统作为一个复杂的主题信息搜索过程，不仅受到主题 浙江工业大学硕士学位论文 基准模型好坏的影响，也受到网页分析方法以及网页搜索策略的影响。本文主要从这三个 因素展开研究与改进，构建主题爬虫系统框架，结合信用主题为应用，进行信息采集研究。 这将有助于主题爬虫系统性能改进与信用信息的获取。 在主题基准模型建立上，通过改进的t f i d f 算法进行权重统计，建立合适的主题基准 模型以及主题基准模型和待判别网页的映射关系，以提高对所抓取网页的主题性判别。然 后根据信用领域的应用，建立相应的主题基准模型。 在网页分析方法上，用改进的基于t a g w i n d o w 标签窗口进行正文提取，可以对网页正 文获取提供更细粒度控制，提高网页正文获取准度。 在搜索策略上，通过引入自适应遗传算法搜索策略，研究提高主题覆盖度以完备索引 信息。 在信用领域信息获取上，该主题爬虫实现了一条廉价的信用信息资源获取通道，相对 缓和了信用信息收集相对困难的问题。 1 3 主题爬虫关键技术研究现状 1 3 1 主题基准模型 主题基准模型为主题爬虫对刚抓取网页的主题鉴别提供判断依据，最终通过主题相关 度计算模块计算网页的主题相关度。主题基准模型构建质量直接影响网页内容取舍，以及 后续的主题相关链接提取。 d h a r m a n 3 】提出了布尔模型，基于二元判定标准( b i n a r yd e c i s i o nc r i t e r i o n ) ，对于一篇 文档只有相关和不相关两种状态，缺乏对文档相关性排序的概念，限制了过滤功能。为克 服以上缺点，人们对布尔模型进行了改进，其中一种方法是对关键词引进权值，权值的大 小即反映关键词在文档中的重要程度，由此，形成了所谓的加权布尔函数，如b o o k s t e i n 检索模型，s a l t o n 模型等。因为关键词的权重从根本上提高了过滤系统的功能，从而导致 了向量空间模型【4 】的产生。由于向量空间模型中词之间假设是相互独立的，而这种假设有 时会不符合实际情况。针对这个问题，s k mw o n g t 5 】等人提出用一组经过挑选的正交基向 量来表示特定主题，词间关系可直接由其向量表示，给出较为精确的计算，这种模型称为 广义向量空间模型。向量空间模型在实际主题爬虫系统中比较实用，很多主题爬虫的主题 基准模型都是通过向量空间模型来建立。以提高爬虫系统的运算效率。 由于前面一些模型都没有考虑主题基准模型中关键词的语义和概念关系，a r u n g s a w a n g 6 1 等人提出了基于知识库的主题基准模型，首先根据用户感兴趣关键词集通过 2 浙江工业大学硕士学位论文 元搜索收集主题相关页面，再结合主题相关页面里的链接文本构建主题知识库，并在爬行 当中持续构建知识库。r o b e r tm e e r s m a n t 7 】等人提出了基于本体的主题基准模型，考虑了主 题含有语义关系，从语义层次上来判别网页的主题相关性。 1 3 2 网页分析方法 网页分析方法主要是对刚抓取的网页进行分析处理，然后按照一定规则抽取网页正文 构建网页主题模型。然后按照指定的主题基准模型对刚刚构建的网页主题模型进行主题相 关度判别。 张志刚【8 】等人提出基于网页结构的内容块提取方法，通过这种方法提取的网页正文对 第一块获取的正文内容块要求非常高，并且这个内容块的主题质量影响着后面内容块的获 取。有些学者发现某一类网站网页具有一定的模板性，针对这一特点，a d e l b e r g ，b 等人提 出了基于模板的网页分析系统n o d o s e t 9 1 ，l a e n d e r 等人提出了d e b y e t l 0 , 1 1 1 系统。基于网页 模板的正文提取方法存在一定的适用局限性，只限于某一类网站下有模板统一生成的网 页。针对基于网页模板适用的局限性，文继荣【1 2 】等人提出了基于可视化信息( v i p s ) 提取网 页正文方法，充分利用用户的阅读习惯：网页设计者一般会把语义相关的内容放在临近位 置。v i p s 通过基于视图提取网页的语义结构，并结合网页布局特点找出网页垂直、水平分 割线。通过这些分割线网页可以被切割成不同语义区域块，再从这些语义块中提取网页正 文。 1 3 3 网页搜索策略 网页搜索策略是影响主题爬虫抓取结果的关键因素之一，主要解决待访问u r l 优先 次序和如何提高主题爬虫覆盖度问题。 b r a ，r d t l 3 】等人提出了f i s h 搜索策略，使用查询来指导主题爬虫爬行。由于f i s h 策略 不能评价页面与主题相关程度的高低，h e r s o v i c i ，m t l 4 1 对f i s h 策略进行改进出现了s h a r k 搜索策略，采用基于连续值的相似度函数计算链接价值，这样不但可以计算哪些页面与主 题相关，还可得出相关性的大小。类似地，j c h o t ”1 等人提出了b e s t f i r s t 搜索策略，利用 向量空间模型计算页面与主题的相关度。由于在b e s t f k s t 中父网页的主题相关程度直接决 定子链接的主题相关预测值，存在一定的片面性。在b e s t f i r s t 基础上，m o h s e nj 锄a l i 【1 6 1 等人提出了结合链接拓扑结构和文本相似度的搜索策略；a r u n g s a w a n g 1 7 】等人提出了学 习型主题爬虫，通过结合b e s t f i r s t 算法搜索策略和当前网页、链接文本的主题相关性决定 待访问u r l 序列；k o uc h u n h u a t l 8 1 等人提出了综合性的搜索策略，对待访问u r l 队列按正 则化后p a g e r a n k 分值大小进行优先级排序。k o uc h u n h u a 等人通过p a g e r a n k 值大小访问 待爬行u r l ，一定程度上考虑了网页链接的拓扑结构，但没有考虑网页主题内容的传递性。 3 浙江工业大学硕士学位论文 前面一些搜索策略都是基于链接拓扑结构进行搜索，而无法访问链接不可达主题资 源。针对这个问题，j i a l u nq i n t l 9 】等人提出了基于遗传算法的搜索策略，用基于文本分析的 选择操作下载主题相关网页，用基于链接分析的交叉操作决定待爬行u r l 序列，用基于元 搜索的变异操作引进新的主题团资源；d i l i g e n t i l 2 0 提出了基于语境图的搜索策略，它通过 构建典型的w e b “语境图 来估计离目标页面的距离，以跨越主题不相关链接。张玲【2 1 】将 当前网页主题性和历史抓取网页相关性结合，对链接的重要性进行预测，主题爬虫能够根 据搜索的实际情况动态调整搜索策略。 到目前为止，对主题爬虫的相关技术研究仍处于探索阶段，研究人员一直致力于研究 更有效的主题基准模型、网页分析方法和搜索策略来提高主题爬虫性能。因此对主题爬虫 相关技术进行研究具有很高的学术理论意义和广阔的应用前景。 1 4 本文主要研究内容 本文主要从主题爬虫系统结构以及主题基准模型、网页分析方法和网页搜索策略三方 面展开研究。然后设计和构建相应的主题爬虫系统框架，实现主题爬虫原型系统，结合信 用主题为应用对相应的实验结果进行分析比较。本文主要研究内容包括以下几个方面： 1 、主要针对主题爬虫系统结构开展研究。为提高主题爬虫抓取质量，将主题基准模 型、网页分析方法和网页搜索策略三个重要组成部分进行分析整合，设计了主题爬虫系统 的框架。 2 、针对主题基准模型建立方法和待判别网页主题抽取方法权重设置不一样问题，研 究如何建立合适的主题基准模型以及主题基准模型和待判别网页的映射关系，来提高爬虫 对网页的主题性判别。 3 、针对常用的基于网页结构内容块提取方法中提取正文粒度不够细问题，本文采用 基于t a g w i n d o w 标签窗1 2 1 进行网页正文提取，以适应于正文篇幅长和正文中链接比较少的 网页类型。 4 、为提高主题爬虫覆盖度，针对现有主题爬虫存在无法访问链接不可达资源，无法 跨越主题团之间的主题不相关链接等问题，本文通过对自适应遗传算法网页搜索策略展开 研究，以缓和上述隧道问题。 5 、最后，构造以信用主题为应用的主题爬虫原型系统，并对相应的实验结果进行分 析比较。 4 浙江工业大学硕士学位论文 1 5 论文组织结构 论文共分7 个章节，主要内容组织如下： 第一章、介绍了主题爬虫的选题背景及研究意义，以及主题爬虫关键技术研究现状和 主要研究内容。 第二章、首先介绍主题爬虫的工作原理，然后对主题爬虫相关技术进行分类研究，通 过分析比较得出各方法的优缺点。 第三章、根据第二章对主题爬虫相关技术的分析研究，给出本文的主题爬虫总体框架， 并对主题爬虫中各主要模块进行详细介绍。 第四章、首先介绍了向量空间模型，然后对主题基准模型展开研究，确立主题基准模 型。从4 3 节开始对网页分析方法展开研究，在基于内容块提取网页正文方法的基础上， 采用基于t a g w i n d o w 标签窗口正文提取方法，以提高正文提取的准度，最后结合权重设置 方法对网页正文内容构建向量空间模型。 第五章、介绍了遗传算法以及遗传算法在主题爬虫中的应用，然后引入自适应遗传算 法以提高主题资源信息覆盖率。 第六章、设计和完成信用主题爬虫，构建信用主题模型以及初始化信用种子和表结构 设计。最后对实验结果进行分析比较。 第七章、归纳总结了全文的主要研究成果，并对进一步的工作重点和研究方向做了展 望。 5 浙江工业大学硕士学位论文 第2 章主题爬虫相关技术研究 2 1 主题爬虫工作原理 主题爬虫的基本工作原理是按照预先确定的主题，分析超链接和刚刚抓取的网页内 容，获取下一个要爬行的u r l ，尽可能保证多爬行与主题相关的网页，因此主题爬虫要解 决以下关键问题： ( 1 ) 怎样判断一个已经抓取的网页是否与主题相关。对于已经抓取的网页可以采用传统 的文本信息检索和数据挖掘技术来实现，但是为了提高主题判别性必须要对两方面作改 进：其一是网页分析方法的增强，以保证能正确提取所抓取网页的主题内容；其二是主题 相关度判别方法的增强，以保证正确判断所抓取网页的主题性。 ( 2 ) 怎样决定待访问u r l 的访问次序。许多主题爬虫根据己下载的网页的主题相关度， 按照一定的原则，将相关度进行衰减，分配给该网页中的超链接，而后插入到优先级队列 中。不同主题爬虫之间的主要区别也就在于它是如何决定待访问u r l 的爬行顺序。 ( 3 ) 怎样提高主题爬虫的覆盖度。这个问题解决主题爬虫如何跨越主题不相关链接到达 到真正的主题相关网页以及如何访问到链接不可达主题团资源，从而提高主题资源的覆盖 度。 其实主题爬虫是通用爬虫应用的一种扩展，所以主题爬虫的工作流程是在通用爬虫的 基础上得到的。一般主题爬虫系统的工作流程图如下： 6 浙江工业大学硕士学位论文 图2 1 主题爬虫工作流程图 主题爬虫在初始爬行阶段，也需要种子u r l ，初始u r l 种子要求必须是和主题相关 度非常高的权威网站u r l 的导航页，因为这样的网页包含大量与主题相关的链接，以便 获得比较高的搜索精确性。 抓取到原始h t m l 文档后，从中抽取特征信息和超链接信息，按事先制定好的主题基 准模型分析网页内容主题相关性及其链接的相关性和重要性。对刚抓取网页的主题相关度 的判别是一个复杂算法分析过程，也是主题爬虫需要解决的关键问题之一。本文将在第四 章详细阐述如何建立主题基准模型和相应的网页分析方法构建网页主题模型，以提高网页 主题抽取正确程度，提高网页主题相关度的判别。 对主题相关度值大于设定阈值的文档，提取当前h t m l 文档的超链接，过滤不合法 u r l ，将符合要求的u r l 结合网页内容的相关度与重要度等综合因素预测出网页链接的 优先级，按优先级放入待访问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 1 基于常规方法建立主题基准模型 1 ) 布尔模型 布尔模型是基于集合论和布尔代数的一种简单的模型。首先，建立一个二值变量的集 合，这些变量对应于文本的特征项。文本用这些特征变量来表示，如果出现相应的特征项， 则特征变量取“t r u e ”；否则，特征变量取“f a l s e ”。查询由特征向量和逻辑运算符“a n d ”、 “o r ”和“n o t ”组成。文本与查询的匹配规则遵循布尔运算的法则。 虽然布尔模型有着许多优点，但它的缺陷也是很明显的： ( 1 ) 布尔模型的匹配策略是基于二元判定标准( b i n a r yd e c i s i o nc r i t e r i o n ) 的，对于一篇文 档只有相关和不相关两种状态，缺乏对文档相关性排序的概念，限制了过滤功能。 ( 2 ) 虽然布尔表达式具有精确的语义，但常常很难将用户的信息需求转换为布尔表达 式，实际上大多数查询用户发现把他们需要的查询信息转换为布尔表达式时并不那么容 易，从而影响基准主题布尔模型的主题相关度判别。 ( 3 ) 匹配标准存在某些不合理的地方，如在响应某个用“ ”连接的检索式时，系统把 只含有检索式中的一个或数个但不是全部检索词的文档看作与那些不含有检索式中的任 一检索词的文档一样无用，而加以排除。 ( 4 ) 检索结果不能按照用户定义的重要性排序输出。系统检索输出的文档中，排在第 一位的文档不一定是文本集中最适合用户需要的文档，用户只能按照检索结果的顺序浏览 才能找到哪些是自己需要的文档。 为了克服以上缺点，人们对布尔模型进行了改造，其中一种方法是对标引词引进权值， 权值的大小即反映标引词在文档中的重要程度，由此，形成了所谓的加权布尔函数，如 b o o k s t e i n 检索模型，s a l t o n 模型等。因为标引词的权重从根本上提高了过滤系统的功能， 从而导致了向量空间模型的产生。 2 ) 概率模型 8 浙江工业大学硕士学位论文 布尔模型是将文档表示为相互独立的项，忽视了词条之间的关联性。概率模型基于概 率排序原理，考虑词与词之间的相关性，把文档分为相关文档和无关文档。概率模型是一 种基于贝叶斯( b a y s e ) 决策理论的自适应模型，其以成熟的数学理论为基础，通过赋予词的 概率值来表示这些词在相关文档和无关文档之间出现的概率，然后计算文档间相关的概 率。 概率模型有多种形式，常见的一种称之为第二概率模型，其基本思想是：词的概率值 一般是对重复若干次相关性计算，每重复一次，就由用户对检测文档进行人- r n 断，然后 利用这种反馈信息并根据每个词在相关文档集合和无关文档集合的分布情况计算它们的 相关概率。在该模型中，词的权值设计公式2 1 如下： l o g 詈粉 q - 1 式中p ，p 分别表示某特征项在相关文档集和无关文档集中出现的概率。 概率模型的优点在于： ( 1 ) 有严格的数学理论为基础，并采用了反馈原理。 ( 2 ) 文档可以按照相关概率递减的顺序来排序。 主要缺点在于； ( 1 ) 开始时需要把文档分为相关文档和不相关文档的两个集合，实际上这种模型没有 考虑关键词在文档中的频率。 ( 2 ) 使用这种模型增加了存储开销和计算量，其参数估计的难度也较大。 3 ) 向量空间模型 向量空间模型【4 】是由s a l t o n 等人提出来的，并在著名的s m a r t 系统中实现，具有效果 好、近年来被广泛应用的一种方法。在向量空间模型中，主题被看作由一组正交词条组成 的n 维向量空间，主题被形式化成n 维空间中的向量。这里介绍几个向量空间模型中的基 本概念。 ( 1 ) 索引项( i n d e xt e r m ) - 是一组可以代表主题内容的关键词。通常，索引项是名词或 名词组，索引项一般称为特征项，或简称项。一般选择那些能突出表达文本主题的名词、 名词组或者动词，如对于信用领域方面的文档，可以选择“信用”、“信用等级”、“信用制 度”等这样的主题关键词来充当索引项，索引项的个数也是根据特定主题领域而定的【2 2 1 。 ( 2 ) 索引项权重( t e r mw e i g h t ) ：由于考虑到布尔模型只能判别文档是否相关，而不能对 文档主题相关度进行排序，所以向量空间模型通过引进索引项权重可以计算某一文档的具 体主题相关度值。索引项权重设置有人工设定、自动化词频统计设定和两者结合设定三种 浙江工业大学硕士学位论文 方法。 在向量空间模型中，文档之间的相似性可以通过文档向量间距离的大小来衡量。如果 两个文档所对应的向量之间的距离最小，就认为这两篇文档最为相似。 衡量两个向量的距离，到目前为止并没有最好的办法。一般有两种方法计算向量之间 的相似度： ( 1 ) 欧氏距离，两个标准化的文本向量a 、b ，它们之间的欧氏距离公式2 2 如下： d ( 口，功2 辱咱) 2 q 。2 ( 2 ) 余弦距离，计算两个向量的余弦夹角公式2 3 如下。 c o s 2 尚 协3 ) 向量空间模型的优点在于： ( 1 ) 主题内容通过向量形式给出，将某一主题这样的非结构化和抽象化的内容以向量 的形式具体化到实数域中，提高了自然语言文档的可计算性和可操作性。 ( 2 ) 可以对文档向量中特征词赋予权值，权值的大小将反映关键词与文档之间的相关 程度大小，克服了传统布尔模型无法计算具体相关度值的缺陷。 ( 3 ) 有效提高了匹配效率。 向量空间检索存在的缺点： ( 1 ) 反映文档主题的特征词的权值，没有绝对准确的方法确定。 ( 2 ) 向量空间模型基于词之间相互独立的假设，而这种假设有时会不符合实际情况。 对于这些缺点，s k mw o n g 5 】等人在1 9 8 5 年提出用一组经过挑选的正交基向量来表 示特定主题向量。词间关系可直接由其向量表示，给出较为精确的计算，这种模型称为广 义向量空间模型。向量空间模型在实际主题爬虫系统中比较实用，很多主题爬虫的主题基 准模型都是通过向量空间模型来建立，以提高爬虫系统的运算效率。 2 2 2 基于知识库建立主题基准模型 基于知识库表示领域主题的方法是在2 0 世纪7 0 年代开始发展起来的【2 3 1 ，可以大致分 为两类： ( 1 ) 基于逻辑的知识表示方法：其中语言通常是一阶谓词逻辑的变异，推理相当于证 明逻辑推论。但是一阶逻辑的表达能力太强，如果不加任何约束，很有可能破坏知识结构， 导致无法进行有效的推理f 2 4 j 。 ( 2 ) 非基于逻辑的表示方法：通常是基于图形化界面的使用，知识通过某种特殊的数 浙江工业大学硕士学位论文 据结构来表示，推理可以简单地通过处理结构过程来完成。 主题基准模型表示一般分为两步：第一步，基于一定的途径得到表示某一主题的关键 词集合；第二步，根据关键词集合推出概念集合，并用向量的形式表示。第二步是关键， 由于一词多义和同义词现象的存在，需要一个概念知识库来解决多义、同义以及概念间的 语义关系。“知网”是一个以描述概念与概念之间以及概念所具有的属性之间的关系为基 本内容的常识知识库，能够为汉语语义处理提供一个比较全面的语义知识库，为基于概念 的主题相关度分析提供概念网络。 a r u n g s a w a n g t l 7 1 等人提出了基于知识库的主题模型，首先根据用户感兴趣关键词集 通过元搜索收集主题相关页面，再结合主题相关页面里的链接文本构建主题知识库，并在 爬行当中持续构建知识库，最后通过公式2 - 4 对刚抓取的网页进行主题相关度计算： 跏化炉羞倦 协4 ， 跏取卜茬荸苏 q - 4 ) 其中k 表示描述某一用户感兴趣的主题的关键词集，d 表示刚刚抓取的网页，f , k 和乙表 示关键词t 在词集k 和d 中的词频。 基于知识库建立的主题模型一般从关键词集基础上建立基准模型，并用一定的逻辑规 则对关键词集进行概念抽取。而概念抽取的两种方法语义网络和框架系统都缺乏精确的语 义，在实际主题知识表示模型中表现都不尽人意。并且基于知识库的主题模型最终一般是 通过余弦距离结合一定的概念相似度计算进行主题相关度判别，在判别时根据网页中关键 词词频来进行权重抽取，而没有考虑如何避免网页欺骗：网页设计者故意提高某些词的词 频以提高网页主题度，增加被主题爬虫抓取的概率。 2 2 3 基于本体建立主题基准模型 基于本体建立主题基准模型，目前基本上还是采用手工方式，三种比较典型的主题本 体模型建立方法如下： 骨架法【2 5 ( m i k eu s c h o l d d e d e ，k i n g ，又称e n t e r p r i s e 法) 是爱丁堡大学从开发企业本 体的经验中产生。该方法只提供本体开发指导方针，并没有针对具体特定领域如何建立本 体基准模型展开研究。 七步法【2 6 1 是由斯坦福大学医学院开发，主要用于医学领域本体的构建，是一种比较成 熟的方法。通过自顶向下法、自底向上法和综合法这三种途径来建立本体中类和类的等级 体系。这些研究主要适合医学领域本体基准模型，而不是针对所有领域主题都适合。 s e n s u s 本体【2 7 1 是由美国南加州信息科学研究所( i s i i n f o r m a t i o ns c i e n c e si n s t i t u t e ) 研 浙江工业大学硕士学位论文 制开发。i s i 自然语言研究