第45卷增刊2005年10月大连理工大学学报Journal of Dalian U niversity of T echnologyV ol.45,Suppl.Oct 12005文章编号:100028608(2005)S 2S257204收稿日期:2005208219.基金项目:国家自然科学基金资助项目(90104002).作者简介:李 粤(19742),女,博士生,主要研究方向:信息检索,个人信息管理平台,E 2mail :liyue @ ;安 捷(19692),女,助理研究员,E 2mail :anjie @ ;李 星(19582),男,博士,教授,博士生导师,E 2mail :xing @cernet..排序融合算法在校园网搜索引擎中的应用李 粤1, 安 捷2, 李 星1(1.清华大学电子工程系,北京 100084;2.清华大学网络中心,北京 100084)摘要:网页排序技术是搜索引擎的核心技术之一.校园网搜索引擎是指以一个校园网内的Web 网页为搜索内容的搜索引擎.由于校园网相对于互联网和内联网的特殊性,各种启发式条件对校园网网页排序优化的影响及排序融合技术在校园网搜索引擎的作用是研究的重点.实验结果表明各个启发式条件的影响和实验数据集有关,而不同启发式条件组合经过排序融合后所获得的查全率差别很大(2%～48%).查全率大于35%的启发式条件组合至少包含4个启发式条件,即校园网搜索引擎的排序需要依据数据集综合考虑多个启发式条件的排序结果.排序融合技术是校园网搜索引擎具有良好的查全率的必要技术之一.基于排序融合技术的网页排序模块已经应用于清华大学校园网搜索引擎中.关键词:搜索引擎;马尔可夫链;排序融合技术;启发式条件;查全率中图分类号:TP 391文献标识码:A0 引 言由于用户对搜索关键词选择的不精确性,搜索引擎通常会对用户的查询请求返回较多的结果,但研究显示用户通常只浏览前10～20个查询结果[1].因此,如何通过排序将最可能满足用户需求的结果或高质量的结果显示在返回结果列表中靠前的位置,即网页排序技术,是网页搜索引擎的关键技术之一.用于改进网页排序算法的启发式条件可分为与用户查询相关(例如查询词出现在标题中的次数)和与用户查询无关(例如网页的反向链接数)两大类.为综合使用这些条件或指标,需要根据具体的应用背景和目标,调整相应的排序函数中各个启发式条件的影响因子.排序融合技术就是一种自动调整各个启发式条件影响因子的算法,它在一系列候选结果中使用不同的排列组合以获得一个较优的排序[2、3].随着教育科研机构的网络普及与信息资源的增加,对校园网的信息检索需求也日益增长.而校园网相对于互联网和企业内联网,有其特殊性.例如:从内容而言,互联网包罗万象,校园网以学术为主,企业内联网是文档与通知;从平均页面质量 看,互联网质量较低(包含很多广告信息)、校园网和企业内联网质量较高(包含较少广告信息)等.校园网的特殊性给校园网搜索引擎带来了区别于传统的互联网搜索引擎和企业内联网搜索引擎的挑战.为了提高和改进校园网搜索系统的检索效率,本文研究多种启发式条件在校园网系统中的影响效果,并将排序融合技术应用于校园网搜索系统.1 排序融合技术排序融合技术在很多学科都有研究,如学习理论中协作过滤和元搜索[1]、社会学的选举机制[4]等.Y oung 等[4]用极大似然法则结合选举机制提出了排序选举———Kemeny 规则,这一方法可以满足投票人的最小分歧.Kemeny 优化方法的表述如下:设离散集合U{u (n ),n =0,1,2,…},{τi }是{u (n )}元素的所有排序组合,Kemeny 优化次序σ使所有排序组合间的K 2距离和最小.{τi (n )}表示元素u (n )在第i 个排序组合中的位置.则τi 和τj 的K 2距离定义为〈n ,m 〉元素对的个数.其中n ,m ∈τi 且n ,m ∈τj ;τi (n );τi (m ),τj (n ):τj (m ). 本质上,Kemeny优化方法可以产生最好的折衷结果.但文[5]研究表明Kemeny优化方法是N P2 Hard问题,为此Dwork等提出用基于Markov Chain的方法近似求解最优有序排列σ[2].Dwork求一步转移矩阵的平稳分布时,将该转移矩阵的所有强连接子图作为节点,视为一个有向无环图(direct2 ed acyclic grap h,DA G),并提出这个DA G在求解平稳分布时有3种特殊情况:(1)存在惟一的吸收点(充要条件是该点的p ii=1);(2)存在多个吸收点;(3)存在几个弱连接子图.这3种情况都无法保证网页的相对排序次序(会出现次序一样的网页).为解决以上问题,本文参照文[6]的方法将一步转移矩阵的平稳分布经过平滑变换,从而尽可能保证网页排序的惟一性.2003年Fagin等[3]对企业内联网(Int ranet)搜索引擎的研究中指出,应用于企业内联网的搜索引擎同应用于互联网(Internet)的搜索引擎之间存在很大的差异,并在IBM公司的内联网搜索引擎上使用基于Markov Chain的排序融合算法对各种排序启发式条件的影响效果作分析.Fagin等的工作表明,查全率高的排序算法需包含至少4个启发式条件,排序集合算法是企业内联网搜索引擎获得良好查全率的必需因素.2 实验方法设计2.1 实验原则以清华大学校园网Web网页为查询对象,建立查询结果标准测试集.将各个查询词获得的查询网页经过排序融合后与其对应的网页标准测试集比较,衡量排序融合技术优化效果以及各个启发式条件的影响因子.2.2 实验集获取于2004年7月挖掘205个清华校园网内站点(已经过滤了别名站点),共采集到1105467个网页(挖掘文件类型限于text/ht ml文件).收集清华校园网搜索引擎(测试版)2003年1月到2004年8月共249621次的查询日志.数据集1为清华大学查询日志中查询频率最高的100个查询词;数据集2为清华大学查询日志中查询频率中间的50个查询词(中间是指这些词的查询次数大概为第100个查询词次数的一半).查询词对应的网页标准测试集合采用人工选择方法获得:选择查询结果列表的前k个结果(Top2k List);其中k=1,2,10,20.5个测试者对同一个查询词返回集合的网页以少数服从多数原则,判别是否在该查询词的Top2k List中.排序融合启发式条件(μ)参考文[3、7]等的研究工作,选择下面9个启发式条件:查询词在标题、反向链接说明和文本的相对词频(分别记为t2t f、a2t f和f2t f),排列次序由大到小;查询结果中的各个网页被站内和其他站点的网页链接数目(分别记为t2num、o2num),由大到小;各个网页的Pagerank (记为pr)值[8],由大到小;各个网页url的长度(包含的字符数)、深度(所处的目录层数)和类型(主页、次主页、目录、静态网页、动态网页)(分别记为u2len、u2dep和u2t y p),由小到大.相对词频是归一化的词频,其计算方法主要运用TF2IDF公式.目前存在多种TF2IDF公式[9、10],因为本文的研究对象只选用文件中出现的部分词,所以选用文[9]的公式(文[10]中的公式需要知道同一文件出现的所有词在这一文件的词频).3 实验结果分析9个条件的排列组合有29=512种,但因为t2t f、a2t f和f2t f3个条件必须包含至少1个,所以最终排列组合为29-27=384种.3.1 实验结果评价方法查全率和查准率是反映搜索引擎质量不同方面的两个参数[10].本文将实验得出的结果和Top2k List进行比较,选用查全率作为衡量标准,即在系统返回同样数量的查询结果前提下,查询结果在Top2k List中数量越多,搜索引擎的排序质量越高.设数据集p(p=1,2,3,4)共有Q个查询词,则其在k(k=1,2,10,20)的查全率为R p k=K p1+…+K p Qk3Q(1) 由于每种排列融合后的结果只选择前k个值,为减少计算量,每一个启发式条件u的排序网页集只取排名前2k个网页即可.设该排列组合τi有m个启发式条件,只需计算在[m/2]+1个条件的网页集(前2k个)中都出现的网页.R p k′(μ)=max(R p k(τj)),μ∈τi包含条件μ的所有排列组合中最大的查全率;R p k″(μ)=max(R p k(τj)),μ∈τi不包含条件μ的所有排列组合中最大的查全率.定义1 启发式条件μ的影响因子S p k(μ)=(R p k′(μ)-R p k″(μ))/R p k″(μ)852S大连理工大学学报第45卷 3.2 查全率评估启发式条件的所有排列组合在k=20的最大查全率为:R120=48%;R220=43%.其中在两个数据集都满足R1,220≥35%的排列组合有19种.这19种组合的启发式条件个数都在4～7;这一结果证明排序融合算法的必要性,即不使用4个以上启发式条件的排序算法效果是比较差的.3.3 启发式条件影响因子表1 启发式条件在数据集1的影响因子Tab11 Influences of heuristics in Dataset1% (μ)S31(μ)S32(μ)S310(μ)S320(μ)t2t f-66.7-53.8-47.2-52.7a2t f50.030.034.814.4f2t f-16.7-15.4-12.4-10.0t2num9.215.423.633.3o2num41.430.034.814.4pr-16.70.42.010.1u2len-33.3-23.1-23.6-12.6u2dep10.315.423.610.1u2t y p10.315.47.916.6表2 启发式条件在数据集2的影响因子Tab12 Influences of heuristics in Dataset2% (μ)S31(μ)S32(μ)S310(μ)S320(μ)t2t f33.3-22.2-32.0-29.7a2t f0.066.70.0-18.4f2t f-33.3-40.00.022.5t2num0.0-50.0-8.7-15.8o2num0.0-40.00.08.2pr-16.7-15.4-12.4-10.0u2len0.0-40.00.010.5u2dep0.0-40.07.09.0u2t y p0.0-30.012.2-8.2分析表1和2的数据,可得出以下结论:(1)t2t f只在数据集2中k=1的位置影响明显.这与文[3]研究结果不同.原因是数据集1中的查询词不少都是清华大学的知名网站(例如“水木清华”(bbs.t )、“清华大学出版社”(www.t up.t )等),k=1的结果基本都是主页或次主页.而数据集2中k=1的结果大部分都是一般网页.(2)a2t f在数据集1、数据集2中各个位置都有相对明显影响,这和文[3]的研究结果相似.由于校园网和企业内联网的网页质量较高,商业因素不明显,anchor的描述较少有夸张和夸大的成分,对内容指示效果较强.(3)f2t f在数据集2的k=20开始有相对明显影响;而pr无明显影响.原因同(2).(4)t2num和o2num在数据集1中影响比较明显,这和文[3]的结论有较大差异.原因是校园网要为学校的资源共享、信息交流、引导或辅助教学及协同工作提供便利,网页间的链接较多,而企业内部网的信息大多为文档与通知,而不去刻意地吸引和考虑任何群体(即缺少相关网页间的链接).(5)u2len影响不明显,但u2dep和u2t y p影响很明显,尤其在数据集1中,这与文[3]的结论不同.原因是校园网的页面相对丰富,组织层次也较多,所以u2dep和u2t y p(u2de p和u2t y p有一定的相关性,例如u2t y p为主站点的u2dep为1,而url2len随意性较大)的影响较大.4 结 论本文成功地将基于Markov Chain的排序融合技术用于清华大学校园网搜索引擎.实验结果显示,各启发式条件的影响与Fagin等在企业内联网的研究结果有较大差异.实验结果表明排序融合技术是保证校园网搜索引擎具有良好查全率的必要技术之一.实验结果对校园网搜索引擎的排序算法有很大的指导意义,也适合于网页质量较高及网页间联系较多的网站群资源搜索.基于排序融合技术的清华大学校园网搜索引擎已经在http://info.t 上提供服务.参考文献:[1]RENDA M E,STRACCIA U.Web Metasearch:Rankvs.score based rank aggregation methods[A].Proc of the2003ACM symposium on Applied computing[C].Melbourne:ACM Press,2003:8412846.[2]DIN G C,H E X F,HUSBANDS P,et al.Rank aggrega2tion methods for the web[A].Proceedings of the10th International World Wide Web Conference[C].Hong K ong:ACM Press,2001:6132622.[3]FA GIN R,KUMAR R,McCU RL EY K,et al.Search2ing the workplace web[A].Proceedings of the Twelfth International Conference on World Wide Web[C].Hun2 gary,Budapest:ACM Press,2003:3662375.[4]YOUN G H P,L EV EN G L IC K A.A Consistent exten2952S 增刊 李 粤等:排序融合算法在校园网搜索引擎中的应用sion of condorcet ’s election principle [J ].SIAM Journal of Applied Mathem atics ,1978,35:2852300.[5]BAR T HOLDI J J ,TOV EY C A ,TRIC K M A.Votingschemes for which it can be difficult to tell who won the election[J ].Social Choice and Welfare ,1989,6(2):1572165.[6]L AN GV ILL E A N ,M EYER C D.Deeper inside PageR 2ank[J ].Internet Mathem atics ,2004,1(3):3352400.[7]KRAAI J W ,WESTERV ELD T ,HIEMSTRA D.Theimportance of prior probabilities for entry page search [A ].Proc 25th Annu al I nternational ACM SIGIR Confer 2ence on R esearch and Development in I nform ation R etriev 2al [C].Tampere :ACM Press ,2002:27234.[8]BRIN S ,PA GE L.The anatomy of a large 2scale hyper 2textual Web search engine [J ].Computer N etw orks andISDN Systems ,1998,30(127):1072117.[9]ALL AN J ,CONN ELL M ,CROFT W B ,et al.IN 2QU ER Y and TREC 29[A ].Proc 9th TREC [C ].G aith 2ersburg :USA N IST Special Publication ,2001.5512577.[10]庞剑锋,卜东波,白 硕.基于向量空间模型的文本自动分类系统的研究与实现[J ].计算机应用研究,2001,9(9):23226.Application of rank aggregation to campus net work search engineLI Y ue 1, AN J ie 2, LI X ing 1(1.Department of E lectronic Engineering ,Tsinghua Univ.,Beijing 100084,China ;work Center ,Tsinghua Univ.,Beijing 100084,China )Abstract :Relevance ranking is one of t he key technologies for web pages search engine.Camp us networksearch engine (CNSE )focuses on web informatio n wit hin a certain camp us network ,which has it s own characteristics co mpared wit h Internet and Int ranet s.The influence of heuristic evidence in web page ranking and t he performance of rank aggregation to CNSE were analyzed.The impact of each heuristic evidence differs in different data set s ,and t he recall of each combination of subset s of heuristics varies from 2%to 48%.The combination who se recall is over 35%includes at least four heuristics ,t hat is ,a few heuristics should be considered according to dataset in ranking system.The experimental result s show t hat rank aggregation technology is necessary for producing robust result s in CNSE.The rank aggregation algorit hm has been deployed in Tsinghua University camp us network search engine.K ey w ords :search engine ;Markov chain ;rank aggregation ;heuristic evidence ;recall62S 大连理工大学学报第45卷 。
![一种考虑多因素的全文搜索引擎网页排序算法[发明专利]](https://img.taocdn.com/s1/m/3f736e396ad97f192279168884868762caaebbcc.png)
