基于AHP 方法的成員搜索引擎調(diào)度策略

張卓

(西安科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，陜西西安710054)

1 現(xiàn)有成員搜索引擎調(diào)度策略

1．1 幾種經(jīng)典的調(diào)度算法分析

目前，成員搜索引擎調(diào)度算法［1］可概括為4大類:樸素算法、定性法、定量法和基于學(xué)習(xí)的方法。樸素算法是不采用任何選擇策略，將用戶的查詢請求發(fā)送給每個成員搜索引擎進行查詢，這種方法適用于成員搜索引擎數(shù)目比較少的情況;定性法是對于某一查詢，通過一定的評判準則，事先估測出各成員引擎的檢索性能，從而選擇最貼近查詢需求的引擎，此方法的缺陷在于評判準則往往不夠明確、不易理解;定量法是根據(jù)給定查詢計算出成員引擎數(shù)據(jù)庫的有用性，如估計有用的文件數(shù)量或估算最相似文件的相關(guān)度，以此作為衡量成員引擎的性能的標準，這種方法相對定性法來說，評判準則更加清晰;基于學(xué)習(xí)的方法根據(jù)各個成員搜索引擎的查詢經(jīng)驗來預(yù)測方法對新查詢的作用，可分為靜態(tài)學(xué)習(xí)和動態(tài)學(xué)習(xí)。

目前，采用較多的SavvySearch方法和ProFusion方法都是基于學(xué)習(xí)的調(diào)度方法。

SavvySearch［2］(www．search．com)是一個采用動態(tài)學(xué)習(xí)方法的元搜索引擎。它根據(jù)先前查詢經(jīng)驗來給出對于新查詢各個成員搜索引擎的評分。此方法通過不斷動態(tài)地將實際查詢過程中獲得的新結(jié)果加入訓(xùn)練結(jié)果集合中，使得訓(xùn)練結(jié)果集合始終處于動態(tài)的更新狀態(tài)中，不再是靜止不變的，這樣就能夠應(yīng)對不同的搜索請求。此方法的最大缺點就是不能很好地適應(yīng)短查詢和新出現(xiàn)的查詢關(guān)鍵詞。

ProFusion［3］(www．Profusion．com)是一種采用混合學(xué)習(xí)方法的元搜索引擎。其中預(yù)先設(shè)置了“旅行旅游”、“社會和宗教”、“歷史”、“音樂”等13個類別。為了獲得不同成員搜索引擎對于不同類別的響應(yīng)情況，在ProFusion中，為每個類別指定一組描述該類別主題的術(shù)語，而靜態(tài)學(xué)習(xí)就通過一組訓(xùn)練查詢獲得。盡管如此，ProFusion方法在靜態(tài)學(xué)習(xí)過程中的訓(xùn)練查詢方法和動態(tài)學(xué)習(xí)過程中的調(diào)整策略還有待改進。

1．2 現(xiàn)有調(diào)度策略存在的問題

傳統(tǒng)的元搜索引擎通常是將查詢請求不加選擇地發(fā)送給所有成員搜索引擎并發(fā)查詢，雖然能保證較高的查全率，但是由于調(diào)用所有的成員搜索引擎，容易導(dǎo)致返回過多的查詢結(jié)果，造成大量重復(fù)、冗余的信息，反而降低了元搜索引擎的查準率，查詢效果不佳。目前采用的幾種調(diào)度策略要么缺少對成員搜索引擎性能的評價，要么評價方式不清晰，不易理解。

基于這種現(xiàn)狀，本文提出一種基于AHP方法的成員搜索引擎調(diào)度策略。通過在元搜索引擎中引入AHP方法，將定量法和基于學(xué)習(xí)的方法相結(jié)合，運用層次分析法將成員搜索引擎的性能評價量化，優(yōu)先調(diào)用查詢性能最佳的前幾個(3～5個)成員搜索引擎完成查詢。

2 基于AHP方法的成員搜索引擎調(diào)度

2．1 AHP層次分析法

20世紀70年代初期，美國運籌學(xué)家托馬斯·塞蒂(T．L．Saaty)提出了層次分析法［4］(Analytic Hierarchy Process，AHP)的概念。AHP方法將復(fù)雜的決策情境劃分為若干部分，再將這些部分組織成一個樹型的層次結(jié)構(gòu)，然后，對每一個部分的相對重要性賦予一定的權(quán)值，最后進行分析，得出各部分優(yōu)先權(quán)。利用AHP算法可做到采用定量的方式對定性的問題進行權(quán)重衡量，并根據(jù)計算得出各因素的權(quán)重值進行評價。所以，AHP方法是一種將定性與定量相結(jié)合的決策分析方法。

用AHP解決問題，一般有以下4個步驟［5］:

Step1:建立問題的遞階層次結(jié)構(gòu);

Step2:構(gòu)造兩兩比較判斷矩陣;

Step3:由判斷矩陣計算被比較元素相對權(quán)重;

Step4:計算各層元素組合權(quán)重，并進行一致性檢驗。

2．2 成員搜索引擎評價指標體系構(gòu)建

元搜索引擎的調(diào)度策略［6］主要研究如何選擇貼近需求的成員搜索引擎組合，以較小的資源耗費，幫助用戶獲得較高的查詢質(zhì)量。那么，成員搜索引擎的選擇必然要依據(jù)一定的評價指標，本文采用的成員搜索引擎評價指標主要由成員搜索引擎對查詢內(nèi)容的相關(guān)度、系統(tǒng)平均響應(yīng)時間和當前負載量3方面組成。在查詢過程中，按照重要度將各個評價指標賦予不同的權(quán)值，通過計算綜合評分得到各成員搜索引擎的綜合評價，然后根據(jù)評分高低選擇合適的成員搜索引擎組合進行查詢。

定義1 設(shè) C={C1，C2，C3，…，Cn}為成員搜索引擎的集合，n為成員引擎的個數(shù)。

定義2 設(shè)第i個成員搜索引擎Ci的權(quán)重為W(Ci)={R(Ci)，tr(Ci)，L(Ci)}，其中R(Ci)表示成員Ci對查詢內(nèi)容的相關(guān)度，tr(Ci)表示成員Ci的平均響應(yīng)時間，L(Ci)表示成員Ci的當前負載量。

2．2．1 查詢內(nèi)容的相關(guān)度 設(shè)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次查詢中，成員搜索引擎對查詢內(nèi)容的相關(guān)度［7］

2．2．2 平均響應(yīng)時間 成員搜索引擎的響應(yīng)時間也是在調(diào)度中需要考慮的因素。這里的平均響應(yīng)時間，通過計算最近k次用戶查詢的平均值來獲得。假設(shè)響應(yīng)時間的閾值為th，響應(yīng)超時為to，提前給定這2個值，如果成員引擎Di的平均響應(yīng)時間tr大于閾值th，則對成員引擎的權(quán)重減少 Pr(Di)=(tr－ th)2/(to－ th)2(默認值［8］:th為 15 s，to為 45 s);如果成員引擎Di的平均響應(yīng)時間tr小于或等于閾值th，則Pr(Di)=0。這里的Pr(Di)為平均響應(yīng)時間評價指標，可通過式

2．2．3 當前負載量 成員搜索引擎的負載就是查詢?nèi)蝿?wù)的隊列長度。負載量L表示成員引擎當前的查詢?nèi)蝿?wù)量。成員引擎每接收一個查詢?nèi)蝿?wù)，負載量加1;每執(zhí)行完一個查詢?nèi)蝿?wù)，負載量減1。

負載狀態(tài)Ls表示當前服務(wù)器負載程度。當L＜Tlow時，Ls為輕負載;當Tlow≤L≤Thigh時，Ls為正常負載;當L≥Thigh時，Ls為重負載。

負載上限和下限分別用Thigh和Tlow表示。Thigh和Tlow值隨時根據(jù)當前的平均負載信息動態(tài)調(diào)整，具體調(diào)整策略是:將當前平均負載和歷史平均負載周期性地進行比較，設(shè)二者比值為P，則調(diào)整后的負載上限為Thigh×P，負載下限為Tlow×P。平均負載的計算式為

其中:n是成員引擎的個數(shù)，Lj為第j個節(jié)點的負載，Wj是各引擎在系統(tǒng)中的權(quán)重。

根據(jù)當前各成員搜索引擎的負載量、負載上下限和當前平均負載，可以計算出表示當前負載情況的特征值，稱為負載系數(shù)C(Di)，

負載系數(shù)的值越大，代表負載量越大。

進入2018年以來，受房地產(chǎn)調(diào)控加碼、消費需求低迷等影響，廚電行業(yè)的高速增長態(tài)勢戛然而止，整體呈現(xiàn)下滑態(tài)勢。在大環(huán)境不佳的情勢下，海爾廚電卻實現(xiàn)了連續(xù)十一個月的逆勢增長。

2．3 基于AHP方法的調(diào)度策略

根據(jù)成員搜索引擎的3個評價指標，運用AHP層次分析法進行綜合評價值的計算，以此作為此次查詢的成員引擎選擇的依據(jù)。

2．3．1 建立評價指標的 AHP層次模型(或建立AHP的評價模型) 根據(jù)AHP層次分析法的4個步驟，建立成員搜索引擎的評價模型。

(1)建立遞階層次結(jié)構(gòu)(圖1)。

圖1 成員搜索引擎綜合評價層次結(jié)構(gòu)圖Fig．1 Hierarchical structure chart for comprehensive evaluation of member search engines

目標層是決策的目的、要解決的問題。

準則層是考慮的因素、決策的準則。

方案層是決策時的備選方案。

由此，可建立3層層次分析模型，如圖1。最高層即目標層是成員搜索引擎綜合評價(G);第2層準則層(C)包括:檢索文檔與查詢主題的相關(guān)度(C1)、平均響應(yīng)時間(C2)、成員搜索引擎當前負載量(C3);最底層方案層(A)，選擇元搜索引擎萬緯中可調(diào)用的6個中文搜索引擎作為待調(diào)度的成員引擎，分別為 A1—A6。

為了得出C1，C2，C3對目標G的影響權(quán)重，可采用如圖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

下面，依據(jù)相對比例標度圖及C1，C2，C3的重要度，具體構(gòu)造兩兩比較判斷矩陣為

G 相關(guān)度C1 響應(yīng)時間C2 負載量C3相關(guān)度 C1137負載量 C2 1/3 1 3響應(yīng)時間 C3 1/7 1/31

同樣，方案層的A1—A66個成員搜索引擎分別相對于C1，C2，C33個評價指標也可構(gòu)造兩兩比較判斷矩陣。矩陣中的各項以公式(1)—(3)中計算值為依據(jù)。

(3)由判斷矩陣計算被比較元素相對權(quán)重，計算各層元素組合權(quán)重。

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:計算各列的平均值:

相關(guān)度C1:(21/31+5/7+7/13)/3=0．643;響應(yīng)時間C2:(7/31+5/21+5/13)/3=0．283;負載量C3:(3/31+1/21+1/13)/3=0．074;這些平均值，通稱為優(yōu)先向量(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:得出目標層 －準則層的權(quán)重(圖3)。

圖3 目標層－準則層權(quán)重Fig．3 Weights of target layer and criterion layer

同樣，也可得到準則層－方案層權(quán)重。

(4)一致性檢驗

計算一致性比率［10］

其中:CI稱為一致性指標;n值就是選擇準則的個數(shù);λ是各行總和與各列λ相乘之和;RI代表隨機一致性指標(Random Consistency Index)值，見表1。

表1 隨機一致性RI值Tab．1 Random Consistency Index

根據(jù)前面計算的PV值，可算出:λ=(1．476×0．643)+(4．2 ×0．283)+(13 ×0．074)=3．097;n值為3，經(jīng)查表可得到RI值為0．58。所以可算出:

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

如果CR值小于0．1時，表示具有相當?shù)囊恢滦裕鲜鲇嬎愕闹?．083小于0．1，所以是具有一致性的。反之，如果CR值大于0．1時，表示呈現(xiàn)顯著的不一致性。

2．3．2 基于AHP方法的調(diào)度方案 采用AHP層次分析法，可以對成員搜索引擎的綜合性能進行排名，以此發(fā)現(xiàn)查詢最佳的成員引擎。當系統(tǒng)收到用戶查詢q時，其調(diào)度過程如下:

(1)計算各成員引擎對于查詢內(nèi)容的相關(guān)度、平均響應(yīng)時間以及當前負載量;

(2)按照圖1所示的成員搜索引擎綜合評價層次結(jié)構(gòu)圖，分別計算各層元素組合權(quán)重并進行一致性檢驗;

(3)根據(jù)AHP層次分析法得出的各成員搜索引擎性能評價值對此次查詢進行成員引擎性能排序，以此作為調(diào)度的依據(jù)。

3 實驗測試

實驗選取目前比較流行的元搜索引擎萬緯網(wǎng)和本系統(tǒng)進行查詢性能的對比。由于萬緯可以調(diào)用百度、新浪等6個中文搜索引擎，因此本系統(tǒng)也添加相同的6個成員搜索引擎，隨機選取20個關(guān)鍵詞進行查詢測試。為驗證基于AHP方法的成員引擎調(diào)度策略的可行性，實驗將從查全率、查準率和查詢響應(yīng)時間3方面進行對比測試。在20次隨機查詢中，本系統(tǒng)根據(jù)AHP方法計算出各個成員引擎的綜合評分，從而選擇出查詢性能最優(yōu)的4個成員引擎進行查詢，與萬緯同時調(diào)用6個成員引擎進行檢索性能對比，下面的圖4、圖5和圖6分別列出了二者的查全率、查準率和查詢響應(yīng)時間情況。實驗結(jié)果表明，二者的查全率區(qū)別不是太大，但是在查準率方面本系統(tǒng)比萬緯有較明顯的提高，平均提高了10．4%，查詢響應(yīng)時間也明顯縮短了，平均縮短2．28 s。因此，本文研究的基于AHP方法的成員搜索引擎調(diào)度策略，在一定程度上提高了信息檢索的效率和質(zhì)量。

圖4 本系統(tǒng)與萬緯查全率比較Fig．4 Comparison of recall ratio of this system with Wideway system

圖5 本系統(tǒng)與萬緯查準率比較Fig．5 Comparison of precision ratio of this system with Wideway system

圖6 本系統(tǒng)與萬緯查詢響應(yīng)時間比較Fig．6 Comparison of response time of this system with Wideway system

4 結(jié)束語

本文提出了一種基于AHP方法的成員搜索引擎調(diào)度策略，該策略從成員搜索引擎對查詢內(nèi)容的相關(guān)度、成員引擎的平均響應(yīng)時間和當前負載量等3方面進行考慮，以此作為成員搜索引擎性能評價的指標，并利用AHP層次分析法來確定各項指標的權(quán)重，對成員搜索引擎的性能評價進行了量化管理，從而為成員引擎的選擇提供了重要的參考依據(jù)，使得檢索的效率和內(nèi)容相關(guān)度均有顯著提高。

［1］ 張卓．基于移動Agent的信息檢索系統(tǒng)中調(diào)度策略的研究［D］．西安:西安電子科技大學(xué)，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］ 程磊．個性化元搜索引擎的研究與設(shè)計［D］．武漢:武漢工程大學(xué)，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層次分析法在高校師資隊伍綜合評價系統(tǒng)中的應(yīng)用［J］．海南大學(xué)學(xué)報:自然科學(xué)版，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］．三明學(xué)院學(xué)報，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］ 薛云．元搜索引擎?zhèn)€性化調(diào)度策略的研究與設(shè)計［J］．煤炭技術(shù)，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］ 黃偉建，祝月紅，杜?。讵剟顧C制的成員搜索引擎調(diào)度策略［J］．圖書館學(xué)研究，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］．上?？茖W(xué)技術(shù)出版社，1990:20．LIU Xin-xian．Choice and judgment:AHP(Analytic Hierarchy Process)Decision［M］．Shanghai:Shanghai Scientific and Technical Publisher，1990:20．

［10］何夕平．模糊綜合評價在選擇最優(yōu)施工方案中的應(yīng)用［J］．合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，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．