改进的向量空间模型在主题爬虫中的应用

1、改进的向量空间模型在主题爬虫中的应用 改进的向量空间模型在主题爬虫中的应用*510摘要：主题爬虫是垂直搜索引擎中的关键组成模块，而向量空间模型 VSM 常被主题爬虫用来判断一个抓取到的网页与搜索主题的相关度。使用传统向量空间计算文档相关度值时不考虑特征项在网页中的位置,致使相关度计算不能达到最优。本文在研究传统向量模型的基础上,提出了一种改进的向量空间模型,将网页文档按位置分块后首先计算搜索表达式与文本块的相关度,然后依据位置权重综合计算出网页文档与搜索表达式的相关度。经实验对比验证,改进后的向量空间模型可以有效的提高爬虫的主题识别能力,并降低爬虫运行负载。关键词：计算机应用；位置分块；向量空

2、间模型；主题爬虫；中图分类号：TP39315Application of Improved VSM in Focused CrawlerZeng Ming, Yu Junsheng School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing100876 2025303540Abstract: Focused crawler is a key model of vertical search engine,and vector space model VSM is co

3、mmonly used to calculate the relevance of a fetched web page and the query topic. When thetraditional VSM is used,the calculation can not get the optimal result because it does not careabout the position of the feature items in the page.Based on the research on the traditional VSM,animproved VSM is

4、raised in this article.A web page is cut into several pieces based on its structurefirst and each piece is used to calculate its relevance with the query expression.Finally therelevance between the web page and the query topic can be calculated using all the relevance ofthe pieces and its weights.Ex

5、perimental comparison results indicates that the improved VSM canhelp the crawler effectively improve its ability of identifying the query topic and reduce itsrunning load.Key words: Computer Application;Position Cutting;VSM; Focused Crawler0 引言当前网络媒体发展迅速，其中蕴含的信息每天都是在以爆炸式的速度增长，搜索引擎已经成为人们访问互联网的一个重要的工

6、具。与传统搜索引擎不同，垂直搜索引擎是近些年来发展迅速的一个互联网应用。它为互联网用户提供专业的针对行业的深度查询服务，是传统的搜索引擎技术的延伸1。垂直搜索引擎对信息过滤精细，整合某类行业信息而使得搜索结果的查准率、查全率更高，返回给用户的结果集更加专而深，从而深受用户欢迎。一个专业的垂直搜索引擎一般由以下几个主要模型构成：主题爬虫模块、索引模块、检索模块以及用户接口，而主题爬虫无疑是整个引擎中一个核心的模块2。主题爬虫基于网页中的超链接不断爬行而抓取所爬到的网页，利用一定的搜索策略对网页进行分析，将不会抓取范围外的网页而只保存指定领域、指定范围内的相关网页信息，以使得抓取结果相对通用搜索引

7、擎更显精而深。主题爬虫的爬虫范围只限定于特定主题或专业领域，因而其在爬行的过程中不需要对整-1-个互联网进行遍历，而只需要选择与主题相关的页面进行访问3。依据这个原则，主题爬虫45往往采取最佳优先的爬行策略，此爬行策略的基本思想就是按照一定的模型来计算网页与主题的相关度，进而依据此相关度来确定是否抓取以及抓取的顺序，而向量空间模型即是一个被广泛应用的主题判定模型。1 传统向量空间模型501.1传统模型的基本思想Salton 等人在 70 年代提出了向量空间模型的概念，它是一个文档的特征向量表示模型，可将文档表示成为特征向量4。这个模型中的基本要素有：（1）文档 D，即平常意义上的电子文本，而具

8、体到搜索技术领域中即为一个具体的网页。（2）特征项 t，即文本所包含的基本语言单位，如词、短语等，向量空间模型用特征项5560组合来表示一个文档。（3）权重 w，用来标识特征项在文档中的重要程度。在此模型中，将每一个网页文档及用户的查询表达式都看作由相互独立的特征项 t1 , t 2 ,., t i ,., t n 组成的等长向量，对于每一个特征项 t i ，根据其在网页文档 D j 中重要程度 赋 予 其 一 个 权 重 wij ， 并 将 t1, t2 ,., ti ,., tn 看 作 一 个 n 维 坐 标 系 中 的 坐 标 轴 ，w1 j , w2 j ,., wij ,., wn

9、j 为对应的坐标值，由此可以将网页文档映射为 n 维空间中的一个点，文档 D j 可以表示为 n 维向量 D j w1 j , w2 j ,., wij ,., wnj ，而用户输入的查询式依据同样的转换方式可表示为 Qk wk1 , wk 2 ,., wki ,., wkn ，这样的话查询式与网页文档之间的匹配问题就转化为 n 维向量空间中的矢量匹配问题5。65特征项权重 wij 的计算特征项 t i 及其权重 wij 是利用向量空间进行网页主题判断的关键，因为它们决定了这个特征项在此文档 D j 中的重要程度，也即这个特征项在多大程度可以将此文档与其他文档区分开来6。在中文信息检索中，一般

10、选取字、词、短语等作为特征项 t i ，当然也会受系统的精度、存储空间等方面的影响。通常来讲，词作为特征项比较合适，因为它是文本的基本组成元素70且在文本中的出现频率呈一定的统计规律7。对于特征项的权重 wij ，定义方法可以依据具体使用环境决定。常用的权重计算方法是DF-IDF 算法，这个算法综合利用特征项的项频度 tf、逆文档频度 idf 以及文档加权 wa 来计算特征项的权重。项频度 tf ij 表示特征项 t i 在网页文档 D j 中出现的次数， tf ij 越大也就表示这个特征项对于此文档越重要。而逆文档频度 idf ij 的定义公式是8：75idf i log Ndf i 1 其

11、中 N 表示整个文档集合中文档的数量， dfi 为文档频度，即文档 D j 在整个文档集合中出现的次数。逆文档频度 idf ij 用来衡量特征项 t i 在整个文档集合中的分布情况，其值越高，就意味着-2-此特征项对于文档区分的作用越大。依据以上讨论，可以定义特征项 t i 的权重 wij 为：8085wij tf ij idf i waij其中 waij 表示文档加权。查询向量 Qk 与文档向量 D j 的相关性计算查询向量与文档向量具有相同的维度，其定义如下：其中 t i 为指定特征项，Q 为查询表达式。?1, ti Q?0, ti Q 2 3 查询向量与文档向量之间的相似度，也即 Qk

12、与 D j 的相关性函数，直接反映了用户查询式和文档集合中某一具体文档的匹配程度，是进行查询结果排序的重要标准。一般相似度的计算有多种方法，如内积法、余弦法等。常用的余弦法定义相关性函数 Sim Qk , Di 如下990Sim Qk , Di ni1ni1ki2ki? wijni1ij 2 4 其中 n 为文档向量及查询向量的维度， wki 和 wij 分别为查询向量 Qk 和文档向量 D j 在第 i 维上的坐标值。1.2传统模型的不足目前的信息检索系统中经常利用传统空间向量模型来处理查询文档匹配问题，按照此模95型可以依据计算出来的相似度来排列命中的文档，解决了查询结果部分匹配问题，检索

13、结果也相对更加精确。模型将自然语言文档转换到 n 维空间中，利用向量的相似度来反映文档与查询式的相关系，提高了匹配处理的可操控性，相关度值也克服了布尔模型的缺陷，部分匹配的结果更加符合用户的需要。但传统向量空间模型的不足也是明显的：100（1）向量空间模型是基于一个假定的，即所有特征项是独立的，没有考虑到特征项之间的关联，这与现实中的文档词汇分布词不符。（2）计算权重时，文本长度越长，则文档越容易被命中，因为长度越长，就意味着其中特征项的出现频度就可能越高。（3）计算权重时没有考虑特征项在文档中的位置，一般特征项位于网页文档中的不105同位置时，其对网页文档的主题决定性贡献也不相同，而传统向量

14、模型没有考虑这个因素。为了解决传统空间向量模型的不足，尤其针对其没有考虑特征项位置的缺点，本文提出了改进的空间向量模型，用于提高网页文档的主题判断的准确性，下一节会给出详细思想。-3-2 基于特征项位置的向量空间模型1102.1改进模型的基本思想针对传统向量空间模型没有考虑到特征项位置的缺陷，本文提出改进的基于特征项位置的向量空间模型。基本思想是将一个网页文档按结构自定义提取为与标题、正文、锚文本等位置相对应的文本块，其次针对各文本块建立特征向量，得到此网页文档的特征向量集合。进行信息检索时，首先分别计算检索表达式 Qk 与网页文档对应的位置特征向量集合中的各个位置特征向量进行相关性计算，可得

15、到与文档分块相同数目的相关性值，赋予不同位115置的计算出来的相关性值不同的权重，则最终可算出文档的基于特征项位置的加权相关性值。依据这种算法计算出来的相关性值可以更好的反映出特征项位于不同位置上时对网页文档主题与检索表示式的相关性的影响能力，并且设计者可以自定义不特征项位于不同位置时的影响权重，系统更加灵活。120基于位置分块的特征项权重计算将一个网页文档 D j 按照位置结构提取为 m 个文本块，第 l 个文本块的标记为 Sjl，则在此改进的向量空间中，特征项 ti 在 Sjl 中的块权重可表示为：S jl? S jl NtiS jl df iS jl N df ii ?2 5 其中 l

16、为位置加权，可依据特征项位于不同位置上时对该网页文档的主题贡献度进行调整，tfiS jl为特征项在文本块 Sjl 中出现的频度，dfi 为包含特征项 ti 网页文档在整个文档集125合中出现的次数。基于位置分块的查询向量与文档向量相关性计算依据上一节中提出的基于位置的特征项权重计算方法及传统模型中查询向量与文档向量相关性计算公式，我们可以推算出本文中改进的向量空间模型中一个查询向量 Qk 与一个文本块 Sjl 及一个网页文档 D j 的相关性计算公式分别为：130Sim Qk , S jl ni1ni1S jlii? wkini1ki2 6 ml1 7 其中 Sim Qk , S jl 表示查

17、询特征向量与网页文档 D j 中第 l 个文本块的相关性值，pl 表示特征项位于第 l 个位置时对文档主题的影响权重，n 表示查询向量的维度，m 表示网页文档分块的数目。-4-135改进的向量空间模型特点本文依据网页文档的半结构化特点，提出的基于特征向量位置的向量空间模型，相对于传统模型不考虑特征项在文档中位置的缺陷有了针对性的改进，使得特征项在位于不同位置时对文档主题影响的差异得到充分反映。与传统向量空间模型相比，改进后的向量空间模型引入文档文本分块并赋予其不同影响140权重，充分考虑到特征项出现的位置及附加的相关信息，而不是简单统计其在文档中出现的频率而忽略其他有用信息，对于 web 信息

18、检索的准确率的改善有很大的帮助。3 改进的模型在主题爬虫中的应用1451503.1主题爬虫系统组成本文设计的实验主题爬虫系统分为以下几个模块：（1） 抓取模块，依据设置的初始种子抓取 6html 网页文档。（2） 主题相关性判定模块，调用传统向量空间模型或者本文中改进的空间向量模型进行网页文档主题相关性判断。（3） 链接分析模块，利用 PageRank 算法分析网页上的链接，得出 PR 值。（4） 排序模块，依据主题相关性判定值及 PR 值综合对抓取结果排序。系统组成图如下：主题相关度判定模块抓取模块抓取模块抓取模块数据库图 1主题爬虫系统Fig. 1Focused Crawler Syste

19、m1551603.2主题爬虫工作流程本文设计的主题爬虫工作流程为：（1） 抓取模块取回网页；（2） 调用主题相关性判定模块，得到网页文档主题相关度值；（3） 调用链接分析模块，得到网页文档 PR 值；（4） 抓取模块综合返回的网页文档主题相关度值及 PR 值处理此文档；（5） 抓取模块继续处理抓取队列中的其他 url；（6） 排序模块依据主题相关度值及 PR 值进行结果排序。4 实验验证本实验分别实现了依据传统向量空间模型以及本文中改进的空间向量模型设计的主题165相关度判定模块并集成到实验主题爬虫系统中，利用 eclipse 开发环境开发系统并进行实验。-5-实验硬件环境为 CPU：P725

20、0 2.0GHz；内存：2.0G。爬虫的参数为：抓取深度为 5，判定模块判定模型阈值为 0.1。设置主题爬虫的初始种子为当前主流电子商务网站，抓取个人电脑有关信息，种子列表为：170175在两种主题判定模块工作时，爬虫抓取的网页数据统计数据如表 1 所示：表 1爬虫抓取数据统计Tab. 1Statistics of Data from Crawler发现文档/个提取文档/个提取失败/个收集数据/Byte抓取时间/s传统向量空间9 7637 638579278 238 738492模型改进的向量空8 5025 806506194 386 932362间模型比较爬虫在使用两种主题判定模块时抓取到的

21、数据，我们可以看出：（1）爬虫提取的文档数目出现了明显减少，这主要是因为主题相关性判定模块帮助180爬虫排除了大量的无关网页，这与我们前文中的分析基本吻合。（2）爬虫的抓取速度得到了明显提升，原因在于前面排除的大量网页使得爬虫需要分析的网页数据减少，降低了爬虫的运行负载。另外，从检索界面可以看出，利用改进的向量空间判定模块时，爬虫返回的结果集排序更加合理，与主题相关度较高的网页排名非常先前，这一点要优于使用传统的向量空间模型185190195200作为判定模块时的结果。总体分析来看，基于特征项位置的改进的向量空间模型在对主题爬虫的抓取精度、抓取速度方面都有很大改善。5 结论本文研究了传统向量空间模型在计算网页文档与查询表达式的相似度方面的缺陷，提出了一个改进的向量空间模型：将一个网页文档按照其结构提取为若干个文本块，每个文本块均表示为一个特征向量，利用查询表达式的特征向量分别与这些文本块计算相关度,最后对不同位置的文本块计算出来的相关度值进行加权计算而得到整个文档与查询表达式的相关度，而即网页的主题相关度。将改进的向量空间模型及传统向量空间模型分别实现并集成到主题爬虫中进行实验，结果表明，改进的向量空间模型能帮助爬虫更好的识别主题相关的网页文档，并有效的降低爬虫的运行负载，可见改进的效果明