Nutch 中网页排序效果的改进方法


—42— Nutch 中网页排序效果的改进方法 潘 涛,梁正友 (广西大学计算机与电子信息学院,南宁 530004) 摘 要:Nutch 是一个 Java 实现的开源搜索引擎。针对目前 Nutch 对中文进行单字切分且没有实现 PageRank 计算的缺点,改进 PageRank 算法,设计并实现基于 MapReduce 的 PageRank 计算方法,对 Nutch 中文分词进行改进,加入 JE 中文分词器。实验结果表明,改进后的 Nutch 具有更高的查询结果准确率和中文网页排序效果。 关键词:Nutch 搜索引擎;MapReduce 模型;PageRank 算法;JE 中文分词器 Improvement Method of Web Page Ranking Quality on Nutch PAN Tao, LIANG Zheng-you (School of Computer, Electronics and Information, Guangxi University, Nanning 530004) 【Abstract】Nutch is an open source search engine based on Java. In view of Nutch disappointment which uses Chinese individual character segmentation and can not realize the PageRank computation, the MapReduce-based PageRank computation is designed and implemented in the foundation of improving the PageRank algorithm. JE Chinese word segmentation is added to improve Chinese segmentation on Nutch. Experimental results show that the improved Nutch raises the inquiry rate of accuracy and the ranking quality of Chinese Web. 【Key words】Nutch search engine; MapReduce model; PageRank algorithm; JE Chinese word segmentation 计 算 机 工 程 Computer Engineering 第 36 卷 第 13 期 ol 2010 年 7 月 JulV .36 No.13 y 2010 术与数据库· 文章编号:1000—3428(2010)13—0042—03 文献标识码:A 中图分类号:TP391·软件技 1 概述 Web 搜索引擎目前有 Google、Yahoo、百度等商业搜索 引擎。Nutch[1]是一个 Java 实现的开源搜索引擎,目前为 0.9 版本。2 个优点决定了 Nutch 是目前最好的开源搜索引擎: (1)基于 Lucene 的高效索引和检索功能;(2)基于 Apache 开源 项目 Hadoop 实现类似 Google 的分布式文件系统,它大量使 用 Google 的 MapReduce 思想,极大简化了很多功能模块的 设计。但 Nutch 存在 2 个缺陷:(1)没有实现经典的 PageRank 算法,即没有衡量网页重要性的计算,影响了最终排序效果; (2)对中文进行单字切分,影响了查询结果准确率。因此,本 文提出 Nutch 中网页排序效果的改进方法。 2 MapReduce与PageRank 2.1 MapReduce MapReduce[2]是 Google 开发的一种简化的并行编程模 型,用于大规模数据集的分布式并行运算,通过映射(Map) 和化简(Reduce)思想实现。在 MapReduce 程序中包含映射函 数和化简函数。映射函数用于把一组输入数据键 值对做映射处理,并输出一组中间数据键值对。MapReduce 程序根据相同中间数据键给中间数据值分组,并把数据输送 给化简函数处理。化简函数接收到中间数据键以及与键相对 应的一些值,对这些数据进行归并处理,求得一组形式尽可 能更小的数据。 2.2 PageRank算法及其改进 PageRank 算法[3]由 Lawrence Page 和 Sergey Brin 提出, 它对每个网页赋予一个衡量其重要性的权威值。基本思想是 被大量高质量网页引用(链接)的网页也是高质量网页。用网 页随机漫游模型描述如下:假设一个 Web 漫游者每次按统一 概率 d 在当前网页中挑选下一步要访问的链接,而当遇到一 个没有链出的网页时,漫游者以一个小概率(1-d)跳到任意的 一个页面,则在任意时间点,漫游者位于页面 u 的概率为 1 ()() (1 ) () n i PRTiPR u d d CTi= =− +∑ (1) 其中,PR(u)为网页 u 的 PageRank 值,即网页的重要性;PR(Ti) 为链接到 u 的网页 Ti 的 PageRank 值;C(Ti)为 Ti 的链出数量; d 为阻尼系数,0对进行并行处理,非常适合处理大 规模网页的需求。Nutch 搜索引擎是最早使用 MapReduce 的 项目,在 Nutch 中,MapReduce 编程方式占据其核心结构的 大部分。因此,可以从中获得启发和借鉴,通过 Nutch 基于 MapReduce 的框架计算网页 PageRank 值,具体流程如下: (1)输入 Crawldb 库文件(存放爬虫抓取的 URL)数据进行 Map 操作,输出抓取成功的 URL 中间数据键值对,并利用 Reduce 操作进行合并和去重,最后输出抓取成功的 URL 库 fetchdb。 (2)输入 fetchdb 库和 linkdb 库(存放 URL 互联关系)数据 键值对进行 Map 操作,输出中间数据键值对 ,并把中间数据对按相同的 destUrl 进行分 组,获得链接到目标 URL 的源链接集合列表。把这些键值对进行 Reduce 操作,给每个源链 接网页赋初始值 1,依次输出目标 URL 和源链接网页对象 srcUrl 组成的键值对,构成 pagerankdb 库,为迭 代计算 PageRank 做准备。 (3)输入 pagerankdb 库中的键值对,开始进行 循环迭代计算 PageRank,直到指定的迭代次数后停止计算(本 文取 20 次迭代),计算过程包含 Map 操作和 Reduce 操作, 输出网页 URL 和 PageRank 键值对构成临时 tempdb 库,为把网页的 PageRank 值更新到 Crawldb 库做准 备。算法伪代码如下: Map(key, value){ // key:网页的 url //value:链向 url 的源网页对象 srcUrl double score=0.0; //式(2)中 PR(i)/C(i)运算 score=srcUrl.score/srcUrl.outLink(); temp=srcUrl; temp.score=score; //输出 output(url,temp); } Reduce(key, values) { // key:网页的 url // values:链向 url 的所有源网页对象集合 temp_list[i] double score, PRScore, inhost_score, outhost_score=0.0; for each temp in values { //源 url 与目标 url 在同一个站点 if(check(temp.getUrl(),url)==true) //式(2)中(1-a)PR(j)/C(j)运算 inhost_score+=(1-a)*temp.score; //源 url 与目标 url 不在同一个站点 else //式(2)中 aPR(i)/C(i)运算 outhost_score+=a*temp.score; } score=inhost_score+outhost_score; //求出网页 PageRank 值 PRScore=d+(1-d)*score; //输出 output(url,PRScore); } (4)输入 tempdb 库中键值对到 Update PRScore 函数,进行更新 Crawldb 库操作,为把网页 PageRank 值写入索引做准备。 (5)建立一个名为 pagerank 的索引域,读取 Crawldb 库中 网页 PageRank 值并写入该域中,把 pagerank 索引域添加到 文档中,并把文档添加到索引中,供 Nutch 进行综合网页评 分排序时调用。 3 Nutch的改进 3.1 Nutch评分公式的改进 Nutch 的网页综合评分算法主要由全文检索关键词匹配 算法和网页重要性权重 OPIC(On-line Page Importance Computation)算法[4]组成。PageRank 采用离线计算,对象是 所有已抓取的网页,能够很好地反应出已有页面间的相对重 要性。但 Nutch 并没有采用 PageRank,而 OPIC 只考虑网页 链接数目,并不考虑源网页分数,因此,不能很好地反应网 页重要性。需要把离线计算的 PageRank 因子与在线计算的 OPIC 因子相乘作为新的网页重要性因子,并加入到 Nutch 网 页评分公式中,以利于发现权威性网页并提高它们的得分, 因为只有 OPIC 值高且 PageRank 值高的网页才会被认为是重 要网页。改进后的评分式如下: __ __ (, ) t in q t in field score q d queryWeight fieldWeight=×∑∑ (, ) () queryWeight getBoost t field idf queryNorm q = × × () () () fieldWeight tf idf PR d OPIC d lengthNorm field = ×× × × (3) 其中,score(q,d)是网页文档 d 相对查询 q 的得分;queryWeight 是查询权重;fieldWeight 是文档域权重;tf 是查询中每个 term 在文档 d 中的出现频率;idf 是包含 term 文档数量的反向函 数;queryNorm(q)是检索调节因子;lengthNorm(field)是索引 域长度调节因子;PR(d)和 OPIC(d)分别表示网页 PageRank 值和 OPIC 值;getBoost(t,field)表示查询词中 term 出现在文 档域中的权值,例如网页标题域权值应比正文域大等。 3.2 Nutch中文分词的改进 Nutch 的分词器对英文切分比较完善,对中文只进行单 字切分,缺点是索引较大、查询复杂、效率不高,查询准确 率也较低,而中文分词的准确与否常常直接影响搜索结果的 相关度排序。若要实现较好的中文信息搜索查询,则必须在 Nutch 中增加中文分词处理的方法。 通过分析 Nutch 语言分析器结构,本文将基于词库的正 向最大匹配分词算法的 JE 分词系统与 Nutch 结合起来,改进 了 Nutch 中文分词质量。JE 分词是一套以 Java 编写的分词软 件,它提供了很多功能,如可设定分词粒度参数、增加词典 动态扩展能力、整理优化词库、全面支持 Lucene2.0 等[5]。 4 实验与分析 本实验将一些国内著名网站(新浪、搜狐、网易、hao123 等)首页地址作为 Nutch 爬虫的入口地址集合,把经过一段时 间后抓取的 12 583 张网页作为实验文档集。在 Nutch 搜索 页面输入查询词,进行搜索结果的查准率和排序效果对比 实验。 4.1 TopN查准率对比 对搜索引擎而言,最常用的评价指标是 TopN 查确率: 前 N 个检索结果中和查询相关的网页数与 N 之比。实验中, 输入的查询词为“奥巴马”,N 取值为 10~60,实验结果如 图 1 所示。可以看出,改进后查准率比改进前有明显提高。 通过计算可知,改进前平均查准率为 37.24%,改进后为 74.08%,比改进前提高了近一倍。主要原因是改进前 Nutch 使用中文单字分词,造成与查询无关的词,如“奥运会”、 “巴拿马”等大量网页出现在搜索结果中,致使查准率大幅 下降。 —43— 图 1 TopN 查准率 4.2 排序效果对比 排序效果一般由网页相关性、权威性和网页在排序结果 中的位置决定,网页内容越相关、权威性越大、排序位置越 靠前,排序效果越好。其中,相关性和权威性由人工判断, 为保证排序效果评估的有效性,本实验成立 5 人评测小组, 对网页相关性和权威性评估按少数服从多数原则最终确定等 级。假设 Quality 表示排序效果,定义如下计算式: 1 1 () ()( 1) n i Quality R i A i n in = =∑ −+ 1.0 0.5() 0.1 0.0 Ri ⎧ ⎪⎪= ⎨ ⎪ ⎪⎩ 网页与查询词非常相关 网页与查询词部分相关 网页与查询词微弱相关 网页与查询词毫不相关 (4) 其中,n 为结果网页数量,因为用户一般只关心前 2 页的搜 索结果,所以取 n=20;i 为网页的排序位置;R(i)为网页相关 度等级;A(i)为网页权威度等级。 1.0() 0.3Ai ⎧= ⎨ ⎩ 官方权威网页 网站转载网页 输入如下中文查询词“香港电影金像奖”、“博鳌亚洲 论坛”、“金融危机”、“猪流感病毒”、“北京奥运会”、 “火箭季后赛直播”、“斯诺克世锦赛”和“奥巴马”,按 式(4)分别计算出每个查询词的排序效果 Quality 得分,Quality 越高说明排序效果越好,实验结果如图 2 所示。 从图2 可以看出,改进后Quality得分比改进前有所提高, 通过计算可知,对 8 个查询词,Quality 分别提高了 58.17%、 11.23%、8.58%、10.19%、13.08%、24.48%、27.37%和 13.57%, 排序效果平均提高了 20.83%。主要原因是在改进中文分词基 础上剔除了大量与查询无关的网页结果,加入的 PageRank 改进算法提高了一些不仅相关且权威度高的网页的结果排 名,自动出现在搜索结果中靠前的位置,从而提高了 Quality 得分,使改进后的排序效果显著改善。 0 1 2 3 4 5 6 7 8 9 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 用户查询词 Quality 改进前得分 改进后得分 图 2 排序效果 5 结束语 针对 Nutch 存在的缺陷,本文在改进经典 PageRank 算法 的基础上实现了基于 MapReduce 的 PageRank 计算,并在 Nutch 中加入 JE 中文分词器。下一步工作是研究集群系统上 基于 MapReduce 的并行计算,提高 Nutch 计算 PageRank 的 效率。另外,可考虑在 Nutch 评分中加入网页更新时间和用 户点击度因子,以进一步改进排序效果,提高 Nutch 的用户 使用满意度。 参考文献 [1] Nutch: The Java Search Engine[Z]. [2009-05-18]. http://lucene. apache.org/nutch. [2] Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters[Z]. 2004. [3] 姚文琳, 刘 文. 一种基于本体的 PageRank 算法改进策略[J]. 计算机工程, 2009, 35(6): 50-51. [4] Castillo R, Marin C, Rodriguez M. Crawling a Country: Better Strategies than Breadth-first for Web Page Ordering[J]. ACM Transactions on Database Systems, 2005, 23(4): 864-872. [5] JE-analysis[Z]. [2009-06-03]. http://www.jesoft.cn. 编辑 陈 晖 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (上接第 41 页) 类的轻量级扩展机制。本文使用后者。使用 Stereotype 和 TaggedValue 类的轻量级扩展添加的新属性必须是字符串类 型,但这对简单的分类信息已经足够了。 TaggedValue 类有 2 个方法:setTag(String tag)和 setValue (String value)方法,可以保存一个名值对,正好保存一个分类 标记和分类标记值。Stereotype 类拥有一个 TaggedValue 列表, 可以保存多对分类信息。 4.4 持久化数据库元数据 本文使用 EMF 集成的第三方持久化框架 Hibernate 对封 装好的数据库元数据进行持久化。Hibernate 是当前 O/R 映射 的实际标准,能够轻松地实现对象和关系的相互映射。在 EMF 项目中基于 Ecore 模型可以自动生成 Hibernate 映射文 件,并在数据库中创建模型对应的数据库表结构,实现了数 据库创建的自动化。 EMF 的 HbDataStore 类提供了一个 getSessionFactory() 方法获取 Hibernate 的 session 工厂,再利用 session 工厂就能 获得 session 实例,进而持久化各种数据库元数据对象。 5 结束语 用 CWM 和 EMF 进行元数据处理只需建好 Ecore 模型就 能自动生成用于封装数据库元数据领域模型的代码和用于保 存元数据的数据库,大大简化了数据库元数据封装、扩展和 持久化等一系列处理过程,节省了业务人员的工作量。并且 数据库元数据的封装使用了业界标准 CWM,消除了元数据 的异构,便于元数据的共享。 参考文献 [1] Poole J, Chang Dan, Tolbert D, et al. 公共仓库元模型开发指 南[M]. 彭 蓉, 刘 进, 译. 北京: 机械工业出版社, 2004. [2] Eclipse Consortium. Eclipse Modeling Framework Version2.0[Z]. (2004-02-16). http://www.eclipse.org/emf. [3] Horstmann C S, Cornell G. Java 核心技术[M]. 陈昊鹏, 王 浩, 姚建平, 等, 译. 北京: 机械工业出版社, 2008. 编辑 任吉慧 —44— —1—
还剩3页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 1 人已下载

下载pdf

pdf贡献者

linyouzhu

贡献于2012-05-31

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf