基于AHP 方法的成员搜索引擎调度策略

张卓

(西安科技大学计算机科学与技术学院，陕西西安710054)

1 现有成员搜索引擎调度策略

1．1 几种经典的调度算法分析

目前，成员搜索引擎调度算法［1］可概括为4大类:朴素算法、定性法、定量法和基于学习的方法。朴素算法是不采用任何选择策略，将用户的查询请求发送给每个成员搜索引擎进行查询，这种方法适用于成员搜索引擎数目比较少的情况;定性法是对于某一查询，通过一定的评判准则，事先估测出各成员引擎的检索性能，从而选择最贴近查询需求的引擎，此方法的缺陷在于评判准则往往不够明确、不易理解;定量法是根据给定查询计算出成员引擎数据库的有用性，如估计有用的文件数量或估算最相似文件的相关度，以此作为衡量成员引擎的性能的标准，这种方法相对定性法来说，评判准则更加清晰;基于学习的方法根据各个成员搜索引擎的查询经验来预测方法对新查询的作用，可分为静态学习和动态学习。

目前，采用较多的SavvySearch方法和ProFusion方法都是基于学习的调度方法。

SavvySearch［2］(www．search．com)是一个采用动态学习方法的元搜索引擎。它根据先前查询经验来给出对于新查询各个成员搜索引擎的评分。此方法通过不断动态地将实际查询过程中获得的新结果加入训练结果集合中，使得训练结果集合始终处于动态的更新状态中，不再是静止不变的，这样就能够应对不同的搜索请求。此方法的最大缺点就是不能很好地适应短查询和新出现的查询关键词。

ProFusion［3］(www．Profusion．com)是一种采用混合学习方法的元搜索引擎。其中预先设置了“旅行旅游”、“社会和宗教”、“历史”、“音乐”等13个类别。为了获得不同成员搜索引擎对于不同类别的响应情况，在ProFusion中，为每个类别指定一组描述该类别主题的术语，而静态学习就通过一组训练查询获得。尽管如此，ProFusion方法在静态学习过程中的训练查询方法和动态学习过程中的调整策略还有待改进。

1．2 现有调度策略存在的问题

传统的元搜索引擎通常是将查询请求不加选择地发送给所有成员搜索引擎并发查询，虽然能保证较高的查全率，但是由于调用所有的成员搜索引擎，容易导致返回过多的查询结果，造成大量重复、冗余的信息，反而降低了元搜索引擎的查准率，查询效果不佳。目前采用的几种调度策略要么缺少对成员搜索引擎性能的评价，要么评价方式不清晰，不易理解。

基于这种现状，本文提出一种基于AHP方法的成员搜索引擎调度策略。通过在元搜索引擎中引入AHP方法，将定量法和基于学习的方法相结合，运用层次分析法将成员搜索引擎的性能评价量化，优先调用查询性能最佳的前几个(3～5个)成员搜索引擎完成查询。

2 基于AHP方法的成员搜索引擎调度

2．1 AHP层次分析法

20世纪70年代初期，美国运筹学家托马斯·塞蒂(T．L．Saaty)提出了层次分析法［4］(Analytic Hierarchy Process，AHP)的概念。AHP方法将复杂的决策情境划分为若干部分，再将这些部分组织成一个树型的层次结构，然后，对每一个部分的相对重要性赋予一定的权值，最后进行分析，得出各部分优先权。利用AHP算法可做到采用定量的方式对定性的问题进行权重衡量，并根据计算得出各因素的权重值进行评价。所以，AHP方法是一种将定性与定量相结合的决策分析方法。

用AHP解决问题，一般有以下4个步骤［5］:

Step1:建立问题的递阶层次结构;

Step2:构造两两比较判断矩阵;

Step3:由判断矩阵计算被比较元素相对权重;

Step4:计算各层元素组合权重，并进行一致性检验。

2．2 成员搜索引擎评价指标体系构建

元搜索引擎的调度策略［6］主要研究如何选择贴近需求的成员搜索引擎组合，以较小的资源耗费，帮助用户获得较高的查询质量。那么，成员搜索引擎的选择必然要依据一定的评价指标，本文采用的成员搜索引擎评价指标主要由成员搜索引擎对查询内容的相关度、系统平均响应时间和当前负载量3方面组成。在查询过程中，按照重要度将各个评价指标赋予不同的权值，通过计算综合评分得到各成员搜索引擎的综合评价，然后根据评分高低选择合适的成员搜索引擎组合进行查询。

定义1 设 C={C1，C2，C3，…，Cn}为成员搜索引擎的集合，n为成员引擎的个数。

定义2 设第i个成员搜索引擎Ci的权重为W(Ci)={R(Ci)，tr(Ci)，L(Ci)}，其中R(Ci)表示成员Ci对查询内容的相关度，tr(Ci)表示成员Ci的平均响应时间，L(Ci)表示成员Ci的当前负载量。

2．2．1 查询内容的相关度 设D=(D1，D2，…，Dk，…，Dm)表示某成员搜索引擎检索到的文档集合，Dk表示第k篇文档，所有文档按照下载顺序排列。利用向量空间模型，任一文档Dk可表示为Dk=(Dk1，Dk2，…，Dki，…，Dkn)，其中，Dki表示向量 Dk的第i维。元搜索引擎的查询主题可表示为Kw=(Kw1，Kw2，…，Kwi，…，Kwn)，其中，Kwi表示向量 Kw的第 i维。因此，在第i次查询中，成员搜索引擎对查询内容的相关度［7］

2．2．2 平均响应时间 成员搜索引擎的响应时间也是在调度中需要考虑的因素。这里的平均响应时间，通过计算最近k次用户查询的平均值来获得。假设响应时间的阈值为th，响应超时为to，提前给定这2个值，如果成员引擎Di的平均响应时间tr大于阈值th，则对成员引擎的权重减少 Pr(Di)=(tr－ th)2/(to－ th)2(默认值［8］:th为 15 s，to为 45 s);如果成员引擎Di的平均响应时间tr小于或等于阈值th，则Pr(Di)=0。这里的Pr(Di)为平均响应时间评价指标，可通过式

2．2．3 当前负载量 成员搜索引擎的负载就是查询任务的队列长度。负载量L表示成员引擎当前的查询任务量。成员引擎每接收一个查询任务，负载量加1;每执行完一个查询任务，负载量减1。

负载状态Ls表示当前服务器负载程度。当L＜Tlow时，Ls为轻负载;当Tlow≤L≤Thigh时，Ls为正常负载;当L≥Thigh时，Ls为重负载。

负载上限和下限分别用Thigh和Tlow表示。Thigh和Tlow值随时根据当前的平均负载信息动态调整，具体调整策略是:将当前平均负载和历史平均负载周期性地进行比较，设二者比值为P，则调整后的负载上限为Thigh×P，负载下限为Tlow×P。平均负载的计算式为

其中:n是成员引擎的个数，Lj为第j个节点的负载，Wj是各引擎在系统中的权重。

根据当前各成员搜索引擎的负载量、负载上下限和当前平均负载，可以计算出表示当前负载情况的特征值，称为负载系数C(Di)，

负载系数的值越大，代表负载量越大。

进入2018年以来，受房地产调控加码、消费需求低迷等影响，厨电行业的高速增长态势戛然而止，整体呈现下滑态势。在大环境不佳的情势下，海尔厨电却实现了连续十一个月的逆势增长。

2．3 基于AHP方法的调度策略

根据成员搜索引擎的3个评价指标，运用AHP层次分析法进行综合评价值的计算，以此作为此次查询的成员引擎选择的依据。

2．3．1 建立评价指标的 AHP层次模型(或建立AHP的评价模型) 根据AHP层次分析法的4个步骤，建立成员搜索引擎的评价模型。

(1)建立递阶层次结构(图1)。

图1 成员搜索引擎综合评价层次结构图Fig．1 Hierarchical structure chart for comprehensive evaluation of member search engines

目标层是决策的目的、要解决的问题。

准则层是考虑的因素、决策的准则。

方案层是决策时的备选方案。

由此，可建立3层层次分析模型，如图1。最高层即目标层是成员搜索引擎综合评价(G);第2层准则层(C)包括:检索文档与查询主题的相关度(C1)、平均响应时间(C2)、成员搜索引擎当前负载量(C3);最底层方案层(A)，选择元搜索引擎万纬中可调用的6个中文搜索引擎作为待调度的成员引擎，分别为 A1—A6。

为了得出C1，C2，C3对目标G的影响权重，可采用如图2所示的1～9相对比例标度［9］完成。其中，标度1、3、5、7、9代表了2个因素的相对重要程度，标度2、4、6、8代表了两相邻标度的中值。如果把因素i和j比较的判断记为kij，则因素j和i比较的判断为kji=1/kij。如图2中三角标记处就表示kij=3，则kji=1/3。

图2 1～9相对比例标度Fig．2 1 ～9 relative proportion scale

下面，依据相对比例标度图及C1，C2，C3的重要度，具体构造两两比较判断矩阵为

G 相关度C1 响应时间C2 负载量C3相关度 C1137负载量 C2 1/3 1 3响应时间 C3 1/7 1/31

同样，方案层的A1—A66个成员搜索引擎分别相对于C1，C2，C33个评价指标也可构造两两比较判断矩阵。矩阵中的各项以公式(1)—(3)中计算值为依据。

(3)由判断矩阵计算被比较元素相对权重，计算各层元素组合权重。

Step1:计算各行的总和:

C1 C2 C3 C1137 C2 1/3 1 3 C3 1/7 1/3 1总和 31/21 21/513

Step2:各个值除以该行的总和:

C1 C2 C3 13 C2 7/31 5/21 5/13 C3 3/31 1/21 1/13总和 31/21 21/5 C1 21/31 5/7 7/13

Step3:计算各列的平均值:

相关度C1:(21/31+5/7+7/13)/3=0．643;响应时间C2:(7/31+5/21+5/13)/3=0．283;负载量C3:(3/31+1/21+1/13)/3=0．074;这些平均值，通称为优先向量(Priority Vector，简称PV)值:

C1 C2 C3 PV 值643 C2 0．226 0．238 0．385 0．283 C3 0．097 0．048 0．077 0．074总和 31/21 21/5 13 C1 0．677 0．714 0．538 0．

Step4:得出目标层 －准则层的权重(图3)。

图3 目标层－准则层权重Fig．3 Weights of target layer and criterion layer

同样，也可得到准则层－方案层权重。

(4)一致性检验

计算一致性比率［10］

其中:CI称为一致性指标;n值就是选择准则的个数;λ是各行总和与各列λ相乘之和;RI代表随机一致性指标(Random Consistency Index)值，见表1。

表1 随机一致性RI值Tab．1 Random Consistency Index

根据前面计算的PV值，可算出:λ=(1．476×0．643)+(4．2 ×0．283)+(13 ×0．074)=3．097;n值为3，经查表可得到RI值为0．58。所以可算出:

CR=0．048/0．58=0．083。

如果CR值小于0．1时，表示具有相当的一致性，上述计算的值0．083小于0．1，所以是具有一致性的。反之，如果CR值大于0．1时，表示呈现显著的不一致性。

2．3．2 基于AHP方法的调度方案 采用AHP层次分析法，可以对成员搜索引擎的综合性能进行排名，以此发现查询最佳的成员引擎。当系统收到用户查询q时，其调度过程如下:

(1)计算各成员引擎对于查询内容的相关度、平均响应时间以及当前负载量;

(2)按照图1所示的成员搜索引擎综合评价层次结构图，分别计算各层元素组合权重并进行一致性检验;

(3)根据AHP层次分析法得出的各成员搜索引擎性能评价值对此次查询进行成员引擎性能排序，以此作为调度的依据。

3 实验测试

实验选取目前比较流行的元搜索引擎万纬网和本系统进行查询性能的对比。由于万纬可以调用百度、新浪等6个中文搜索引擎，因此本系统也添加相同的6个成员搜索引擎，随机选取20个关键词进行查询测试。为验证基于AHP方法的成员引擎调度策略的可行性，实验将从查全率、查准率和查询响应时间3方面进行对比测试。在20次随机查询中，本系统根据AHP方法计算出各个成员引擎的综合评分，从而选择出查询性能最优的4个成员引擎进行查询，与万纬同时调用6个成员引擎进行检索性能对比，下面的图4、图5和图6分别列出了二者的查全率、查准率和查询响应时间情况。实验结果表明，二者的查全率区别不是太大，但是在查准率方面本系统比万纬有较明显的提高，平均提高了10．4%，查询响应时间也明显缩短了，平均缩短2．28 s。因此，本文研究的基于AHP方法的成员搜索引擎调度策略，在一定程度上提高了信息检索的效率和质量。

图4 本系统与万纬查全率比较Fig．4 Comparison of recall ratio of this system with Wideway system

图5 本系统与万纬查准率比较Fig．5 Comparison of precision ratio of this system with Wideway system

图6 本系统与万纬查询响应时间比较Fig．6 Comparison of response time of this system with Wideway system

4 结束语

本文提出了一种基于AHP方法的成员搜索引擎调度策略，该策略从成员搜索引擎对查询内容的相关度、成员引擎的平均响应时间和当前负载量等3方面进行考虑，以此作为成员搜索引擎性能评价的指标，并利用AHP层次分析法来确定各项指标的权重，对成员搜索引擎的性能评价进行了量化管理，从而为成员引擎的选择提供了重要的参考依据，使得检索的效率和内容相关度均有显著提高。

［1］ 张卓．基于移动Agent的信息检索系统中调度策略的研究［D］．西安:西安电子科技大学，2008．ZHANG Zhuo．Research on scheduling policy in information retrieval system based on mobile Agent［D］．Xi＇an:Master’s Degree Thesis of Xidian University，2008:10-14．

［2］ Howe A E，Dreilinger D．SavvySearch:A Meta-search engine that learns which search engines to query［J］．AI Magazine，1997，18(2):18-20．

［3］ 程磊．个性化元搜索引擎的研究与设计［D］．武汉:武汉工程大学，2008:16-20．CHENG Lei．Research and design on personalized meta search engine ［D］．Wuhan:Master＇s Degree Thesis of Wuhan Institute of Technology．2008:16-20．

［4］ 王秀明，陈明锐．AHP层次分析法在高校师资队伍综合评价系统中的应用［J］．海南大学学报:自然科学版，2012，30(3):277．WANG Xiu-ming，CHEN Ming-rui．Application of AHP analytic hierarchy process in the comprehensive evaluation of university teachers in the system［J］．Journal of Hainan University:Natural Science Edition，2012，30(3):277．

［5］ 徐涛，史开泉．基于粗糙集理论的AHP层次分析法［J］．三明学院学报，2006，23(4):416-417．XU Tao，SHI Kai-quan．The theory of AHP analytic hierarchy process based on rough set［J］．Journal of Sanming University，2006，23(4):416-417．

［6］ 薛云．元搜索引擎个性化调度策略的研究与设计［J］．煤炭技术，2011，30(5):220-221．XUE Yun．Research and design of personalized scheduling strategy of meta search engine［J］．Coal Technology，2011，30(5):220-221．

［7］ 黄伟建，祝月红，杜巍．基于奖励机制的成员搜索引擎调度策略［J］．图书馆学研究，2012(3):66-71．HUANG Wei-jian，ZHU Yue-hong，DU Wei．Scheduling strategy of member search engines based on incentive mechanism［J］．Research on Library Science，2012(3):66-71．

［8］ Danial Dreillinger，Adele E．Engines using meta search［J］．ACM TOIS，1997(3):195-222．

［9］ 刘新宪．选择与判断:AHP(层次分析法)决策［M］．上海科学技术出版社，1990:20．LIU Xin-xian．Choice and judgment:AHP(Analytic Hierarchy Process)Decision［M］．Shanghai:Shanghai Scientific and Technical Publisher，1990:20．

［10］何夕平．模糊综合评价在选择最优施工方案中的应用［J］．合肥工业大学学报:自然科学版，2000，23(6):1050-1054．HE Xi-ping．Application of fuzzy comprehensive evaluation to selecting the optimal construction plan［J］．Journal of Hefei University of Technology:Natural Science，2000，23(6):1050-1054．