基于Nutch的网页排序算法研究

武警七台河支队 徐再林武警杭州士官学院 陆明昕



基于Nutch的网页排序算法研究

武警七台河支队 徐再林
武警杭州士官学院 陆明昕

【摘要】网页排序算法对根据用户查询词搜索到的大量页面进行排序，从而返回给用户，因此排序算法对搜索引擎的好坏起着关键作用。Nutch搜索引擎只实现了基本的综合排序模型，针对Nutch默认排序算法的不足，在PageRank算法中加入时间因子、链接权重因子，并结合HowNet来计算网页的语义相似度，将改进后的PageRank算法和基于语义的主题相关度算法应用在Nutch排序算法中。实验结果表明：改进的排序算法使得Nutch的搜索结果排序准确率和首页命中率都有了明显提升。

【关键词】网页排序算法；Nutch；PageRank；语义相似度

1 引言

随着互联网的快速发展，互联网平台上的数据呈现出指数增长的趋势，人们对于搜索引擎的依赖性日益显示出来。如何更快更准确的检索网络中的海量信息，并将人们最需要的信息优先返回给用户，成了国内外专家研究的热点。Nutch作为网络爬虫和Lucene索引器的结合，功能强大。但Nutch存在以下缺陷[1-2]：没有实现Google经典PageRank算法，其自身网页在线排序算法没有衡量网页重要性，偏重历史网页，没有考虑网页内容相关性，没有真正考虑到用户的需求，影响了搜索的质量和用户的检索体验。

基于以上问题，本文做出了一些相关改进：首先，在PageRank算法中考虑时间和链接权重因素，并结合HowNet来计算语义相似度，从而实现将语义因素加入到主题相关度算法中，最后将改进后的PageRank算法和基于语义的主题相关度算法结合起来，在Nutch中实现排序算法的改进。

2 算法思想

2.1 PageRank 算法改进

PageRank[3]算法是Google利用网络拓扑图离线计算网页等级的排序算法，算法的主要思想是：被高

度链接的网页可能是优秀网页；被优质网页链接的网页可能是优秀网页，其算法为公式(1)：

公式中,PR(A)是网页A的PageRank值；PR(Ti)是链接指向网页A的网页Ti自身的PageRank值；NTi是网页Ti的出链接总数；d为阻尼系数，一般取值为0.85。

针对PageRank原始算法的缺陷进行以下改进：

1）加入时间因子。针对PageRank算法注重旧网页在公式中加入时间衰减因子：Δ=eλ/t,其中λ为时间的常数因子，t为网页存在的时间，通过时间因子Δ能有效控制网站上存在时间比较长的网页权重的增长速度，防止偏重旧网页忽略了新网页。

2）加入链接权重因子。PageRank算法的特点[4]是平均分配一个网页的PR值，没有区分链接出去的网页的权威度，导致有些商家利用自身网站的导航和广告链接来进行网页作弊行为[5]从而提高网站的搜索排名。针对以上缺陷，在PageRank算法中加入链接权重因子：

SA是指链接到当前网页A的前向链接数，将由网页i出发链接到网络中所有网页组成一个序列，SK表示第k个网页的前向链接数。链接权重因子使得网页不再是根据链接数平均分配PR值，而是根据网页前向链接数在所有竞争网页前向链接总数中的比例来确定该网页获得PR值的比例，即确定当前网页前向链接的权重。

2.2 基于语义的主题相关度算法

PageRank算法只考虑到网页之间的链接关系[6]，并没有考虑到网页的主题相关度，容易陷入“主题漂移”。本文利用HowNet（知网）计算网页的语义相似度，将语义因素加入到主题相关度算法中去，在一定程度上提升了用户检索结果的全面性和准确性。HowNet通过对词语按照语义关系构建网状结构[7]，词语对应于网状结构中的各个节点， HowNet中表示不可分割的最小单元是义原，用户的关键词通常具有多个意义，表示为义项，义项可以用多个义原互相组合进行表示。

本文采用Wu-Palmer语义相似度算法[8]，也就是基于长度来定义网页的语义相似度，其计算公式(3)为：

其中，Sim(A)表示语义相似度，C表示从网页A中抽取出的待计算相关度的义原，T表示关键词的义原集合，ISO(C,T)表示C和T的最近共有的义原，depth表示义原在HowNet中的路径深度。

2.3 Nutch的排序算法改进

在进行网页排序时，综合考虑PageRank值与语义相似度，对每一个网页设定一个价值V,该V值反应了网页与用户需求之间的相关度，V值越大，则用户需求度越大，进行网页排名时，则越靠前。其计算公式如公式(4)：

其中，V(A)表示网页A的价值，β表示算法所占的权重，β取值0.8。

3 实验与分析

为了验证算法的性能，本文采用Nutch-1.2为网页抓取工具进行增量抓取，采用“户外运动”为抓取对象，共收集户外运动相关网站20个，无关网站8个，构成本次实验的测试集合，利用Lucene建立索引。以“登山”“滑雪”“帐篷”“攀岩”为搜索关键词（编号1-4）进行检索，在Nutch中用Java语言实现迭代排序算法，将搜索结果返回给用户。衡量标准采用TopN查准率[9]，数据显示，用户点击第一页的概率比较大，因此本文N=20，即首页命中率。

从查询关键词“登山”的返回结果看，在改进前返回的前20个页面中，近三个月的页面占据比例是1/4，而改进后的返回结果中近三个月的页面占据比例是7/20，可以看出，改进后的PageRank算法在一定程度上提升了新网页的比重。

4 小结

目前，搜索引擎是人们从浩瀚的数据海洋中获取信息的重要渠道，针对Nutch默认的排序算法的不足，本文在PageRank算法中加入时间因子和链接权重因子的基础上，结合HowNet在算法中考虑了语义相关度，对 Nutch默认的排序算法进行改进，提高了Nutch的查准率。本文还有不足之处，如在搜索引擎算法的速度方面进行提升，有待下一步的工作进行研究。

参考文献

[1]陶林,谌超等.基于Hadoop的Nutch网页排序算法研究与实现[J].桂林电子科技大学学报,2013,33(2):139-140.

[2]施磊磊,施化吉等.基于Hadoop和HBased的Nutch网页排序算法研究[J].软件导刊,2014,13(10):53-54.

[3]Pasquinelli M.Google’s pagerank algorithm:A diagram of cognitive capitalism and the rentier of the common intellect[J]. Deep Search,2009(3):152-162.

[4]Luo Wu,Fang Kui,Zhu Xing-hui.The ranking algorithms of search engine[J].Huan Agricultural Science,2010(7):137-140.

[5]刘发升,张菊琴.结合PCM聚类算法的网页排序[J].计算机工程与科学,2013,35(4):144-145.

[6]郭小溪.基于PageRank算法的分布式搜索引擎技术研究[D].大连交通大学,2013:22-27.

[7]刘群,李素建.基于知网的词汇语义相似度计算[J].中文计算语言学,2002,7(2):59-76.

[8]王清霞.基于领域本体的垂直搜索引擎页面排序算法的研究[D].兰州理工大学,2014:23-24.

[9]胡维华,曹奇峰.基于Nutch的页面排序算法研究[J].杭州电子科技大学学报,2013,33(6):76-77.