学位论文 > 优秀研究生学位论文题录展示

面向垂直搜索引擎的主题爬行技术研究

作　者: 陈竹敏
导　师: 马军
学　校: 山东大学
专　业: 计算机应用技术
关键词: 垂直搜索主题爬行主题描述网页分块相关度计算相关度预测优先级计算
分类号: TP393.092
类　型: 博士论文
年　份: 2008年
下　载: 2231次
引　用: 29次
阅　读: 论文下载

内容摘要

主题爬行是获取World Wide Web中特定领域（主题）的网页的关键技术。随着Web的快速增长,以及网络带宽和各种资源的有限性,从中获取全面、准确和高质量的信息变的越发困难。传统（通用）搜索引擎技术呈现出了严重的局限性。（1）对某一查询返回的结果太多且相关性、质量不高。（2）不能满足不同背景、不同目的和不同时期的用户的需求。（3）在索引的全面性、更新的及时性上存在着很大的不足。垂直搜索引擎（Vertical Search Engine）被作为解决通用搜索引擎局限性的一种潜在方案,有着智能化、个性化、领域化的特点,从而成为当前学术界和产业界研究的热点。它利用主题爬行（Focused Crawling or Topical Crawling）技术来搜集面向领域（主题）的Web网页,并提供面向主题的检索服务。无疑,主题爬行技术作为垂直搜索引擎的基础与核心,它的性能对垂直搜索引擎的性能至关重要。此外,主题爬行技术还可用于Web的实时检索、个性化检索、数字图书馆等领域。因此,对主题爬行技术的研究具有重要的学术意义和广阔的应用前景。主题爬行基于这样一个重要的假设:与同一主题相关的网页趋向于互相链接,被称为Web上的主题局部性。主题爬虫每次从待爬行URLs队列中选择最有希望的链接进行爬行,其目标是保持在主题相关的网页的周围,而不偏离主题。因此,主题爬行在很大程度上能节省硬件和网络资源,提高检索结果的查准率和质量,保证爬行的时新性。但由于Web是一个高度开放、异构、分布式的信息空间,网页杂乱地散布在全球各个站点上,而且每天以极快的速度更新。相对于巨大、无序的Web信息空间,与某个主题相关的网页是非常有限的,仅仅是整个信息空间的一小部分。而一个理想的主题爬虫需要最大限度的爬行与预定主题最相关的网页,并最小限度的爬行不相关的网页。因此,主题爬行又是一个极富挑战性的研究课题。主题爬行的关键技术有:主题（用户需求）描述、面向主题爬行的网页分块、待爬行URLs优先级计算、主题爬行算法。研究主题爬行技术的目标是提供建立垂直搜索引擎的一般技术和通用算法,通过提高网页搜集的效率和质量来提高垂直搜索引擎的性能,降低垂直搜索引擎的构造和运行代价。本文以“山东省科技攻关计划项目一垂直检索系统的研究与开发”为依托,针对上述关键技术展开研究,主要贡献和创新点包括如下几点:（1）提出了一种基于分类法的上下文主题描述（CTD-T,Contextual TopicDescription based on Taxonomy）方法。CTD-T方法基于ODF（open Directory Project）来表示主题（用户需求）。对于ODP中的任一主题结点,给出其“上下文主题关键词集合（CTKW,ContextualTopic Key Words）”和“主题描述（TD,Topic Description）”的定义及表示方法。针对直接从ODP中获取CTKW会引入很多噪音结点的问题,提出了一种基于逆路径频率（IPF,Inverse Path Frequency）对CTKW进行去噪的方法。另外,在对CTKW进行向量表示时,提出了一种基于主题结点在ODP中的相对层次位置来计算其权重的方法。利用CTKW来计算已知信息（网页,锚文本等）与给定主题及其上下文主题的相关度,用来在线指导主题爬虫的爬行。利用TD来计算已爬行网页与给定主题的相关度,用来离线评价主题爬虫的性能。（2）提出了一种面向主题爬行的在线网页分块（OPS4FC,Online PageSegmentation for Focused Crawling）方法。指出一个网页中影响主题爬行算法性能的块主要有两种:文本块和链接块。链接块可以进一步被细分为相关链接块,导航链接块和噪音链接块。OPS4FC的主要目标是识别出网页中的主题文本和相关链接块。首先,将一个已爬行的网页解析成DOM（Document Object Model）树。其次,提出一种基于多特征的概率统计方法来识别出该网页中的所有文本块和链接块。然后,根据文本块之间的语义相关性关系来识别出整个网页的主题文本。最后,根据链接块中所有链接的锚文本集合与主题文本的语义相关性关系识别出该网页所有的相关链接块。实验从Web信息检索和主题爬行两个角度证明了OPS4FC方法具有很好的通用性。适用于对海量的,不同版面格式的网页的处理,能够有效的提取网页的主题文本内容和相关链接块,有效的去除网页中的噪音文本和噪音链接,从而能显著的提高Web检索和主题爬虫的性能。（3）提出一种多粒度的TCURLs优先级计算（PUMG,Prioritizing URLs inMulti-Granularities）方法。主题爬行的基本思想就是计算爬行队列中的待爬行URLs（TCURLs,ToCrawl URLs）的访问优先级,并每次选最有希望者进行爬行。因此,主题爬行的核心计算问题是:计算每个TCURL的访问优先级。PUMG以CTD-T和OPS4FC为基础,利用站点、网页内容、相关链接块、锚文本、URL地址和链接类型六种特征,从站点级、网页级、块级和链接级四种不同的粒度来计算一个TCURL的优先级。在PUMG中的子创新点如下:a)提出了以站点为粒度来计算该站点中的TCURLs优先级的方法。如果站点S₁的相关网页数（相关度）大于站点S₂的相关网页数（相关度）,那么在动态的爬行过程中,S₁中已爬行的相关网页总数（相关度总和）的增速比S₂的快。因此,一个站点到目前为止已爬行的相关网页数（相关度总和）的增速可以用来衡量该站点的TCURLs的优先级。b)在基于网页粒度的TCURLs的优先级计算中,不是利用整个网页的内容,而是基于分块后的该网页的主题文本和所有相关链接块的锚文本集合。因为使用的是经过分块后的网页,有效的去除了其中的噪音,提高了优先级计算的准确性。c)针对当前网页中链接较多,且相关链接易于聚集成块的特点,提出了以链接块为粒度来计算该块中的TCURLs优先级的方法。在计算时,只利用网页的相关链接块,因此有效的过滤掉大量的噪音链接。此外,有些相关链接的锚文本较短,单纯依靠锚文本不能有效的发现它们,而以块为粒度很好的解决了这个问题。d)指出大部分网页的URLs地址包含了与网页内容相关联的一些语义标记（Token）,并提出了基于一个TCURL地址的语义标记来计算其优先级的方法。首先,把中文URLs中的语义标记主要分成四种形式:完整英文、英文缩写、完整拼音和拼音的第一个字母。然后,经过半自动的统计分析,创建了一个主题-标记映射表（TTMT,Topic-Token Mapping Table）。对于一个给定主题,从TTMT中找到对应的四种形式的标记;对于一个给定URL,根据分隔符“/”和“.”将其分割成多个标记;然后通过两者标记的匹配情况,确定该URL的优先级。e)提出了基于链接类型来计算一个TCURL的优先级的方法。一个网页的出链指向的网页继承了该网页与主题的相关性。首先,利用一个TCURL与其父网页在Web站点中的相对位置将链接分成五种类型。然后,给出了五种启发式规则根据链接类型来推断该TCURL指向的网页与其父网页的主题间的关系,并确定一个合理的继承因子。利用父网页与指定主题的相关度乘以继承因子作为预测的该TCURL指向的网页与指定主题的相关度,从而作为该TCURL的优先级。（4）提出了一种基于多粒度优先级计算的自适应主题爬行（AFC-PUMG,Adaptive Focused Crawling based on PUMG）算法。AFC-PUMG从一些与预定主题相关的种子出发,利用OPS4FC对已爬行的网页进行分块,并抽取出网页中的待爬行URLs,然后利用PUMG计算每个URL的优先级,并按照其优先级顺序进行访问。AFC-PUMG给出了一个可变长度的路径探测深度（PED,Path Exploring Depth）函数,使TCURLs的PED随着其所在网页与给定主题的相关度的变化而变化。从而使AFC-PUMG可以更加灵活的控制探测的方向和深度,获取更多更相关的网页。此外,根据不同粒度的优先级计算之间的依赖关系,定义了它们计算的先后顺序,并用来改进AFC-PUMG算法的优先级计算过程,降低了算法的运行时间复杂度。（5）基于上述技术实现了一个主题爬行原型系统,从多个角度对本文的方法进行了实验分析。给出了原型系统的体系结构和具体的设计方案。我们在该原型系统中同时实现了宽度优先（Bread-First）,最佳优先（Best-First）,Shark-Search和本文的AFC-PUMG。进行了一系列的实验,实验针对多个不同的主题,在真实的Web环境上,从多个角度证明了本文提出的CTD-T、OPS4FC、PUMG和AFC-PUMG的有效性。在整体性能方面,将本文的AFC-PUMG算法与系统中实现的其它三个爬行算法进行了比较。大量的实验证明,AFC-PUMG在不增加时间复杂度的前提下,在收获率和信息量总和上明显优于其它三种算法。

面向垂直搜索引擎的主题爬行技术研究

内容摘要

全文目录

相似论文