張卓

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

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

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

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

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

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

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

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

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

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

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

2．1 AHP層次分析法

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

用AHP解決問(wèn)題，一般有以下4個(gè)步驟［5］:

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

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

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

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

2．2 成員搜索引擎評(píng)價(jià)指標(biāo)體系構(gòu)建

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

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

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

2．2．1 查詢(xún)內(nèi)容的相關(guān)度 設(shè)D=(D1，D2，…，Dk，…，Dm)表示某成員搜索引擎檢索到的文檔集合，Dk表示第k篇文檔，所有文檔按照下載順序排列。利用向量空間模型，任一文檔Dk可表示為Dk=(Dk1，Dk2，…，Dki，…，Dkn)，其中，Dki表示向量 Dk的第i維。元搜索引擎的查詢(xún)主題可表示為Kw=(Kw1，Kw2，…，Kwi，…，Kwn)，其中，Kwi表示向量 Kw的第 i維。因此，在第i次查詢(xún)中，成員搜索引擎對(duì)查詢(xún)內(nèi)容的相關(guān)度［7］

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

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

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

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

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

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

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

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

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

根據(jù)成員搜索引擎的3個(gè)評(píng)價(jià)指標(biāo)，運(yùn)用AHP層次分析法進(jìn)行綜合評(píng)價(jià)值的計(jì)算，以此作為此次查詢(xún)的成員引擎選擇的依據(jù)。

2．3．1 建立評(píng)價(jià)指標(biāo)的 AHP層次模型(或建立AHP的評(píng)價(jià)模型) 根據(jù)AHP層次分析法的4個(gè)步驟，建立成員搜索引擎的評(píng)價(jià)模型。

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

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

目標(biāo)層是決策的目的、要解決的問(wèn)題。

準(zhǔn)則層是考慮的因素、決策的準(zhǔn)則。

方案層是決策時(shí)的備選方案。

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

為了得出C1，C2，C3對(duì)目標(biāo)G的影響權(quán)重，可采用如圖2所示的1～9相對(duì)比例標(biāo)度［9］完成。其中，標(biāo)度1、3、5、7、9代表了2個(gè)因素的相對(duì)重要程度，標(biāo)度2、4、6、8代表了兩相鄰標(biāo)度的中值。如果把因素i和j比較的判斷記為kij，則因素j和i比較的判斷為kji=1/kij。如圖2中三角標(biāo)記處就表示kij=3，則kji=1/3。

圖2 1～9相對(duì)比例標(biāo)度Fig．2 1 ～9 relative proportion scale

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

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

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

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

Step1:計(jì)算各行的總和:

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

Step2:各個(gè)值除以該行的總和:

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

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

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

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

(4)一致性檢驗(yàn)

計(jì)算一致性比率［10］

其中:CI稱(chēng)為一致性指標(biāo);n值就是選擇準(zhǔn)則的個(gè)數(shù);λ是各行總和與各列λ相乘之和;RI代表隨機(jī)一致性指標(biāo)(Random Consistency Index)值，見(jiàn)表1。

表1 隨機(jī)一致性RI值Tab．1 Random Consistency Index

根據(jù)前面計(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í)，表示具有相當(dāng)?shù)囊恢滦?，上述?jì)算的值0．083小于0．1，所以是具有一致性的。反之，如果CR值大于0．1時(shí)，表示呈現(xiàn)顯著的不一致性。

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

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

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

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

3 實(shí)驗(yàn)測(cè)試

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

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

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

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

4 結(jié)束語(yǔ)

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

［1］ 張卓．基于移動(dòng)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］ 程磊．個(gè)性化元搜索引擎的研究與設(shè)計(jì)［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層次分析法在高校師資隊(duì)伍綜合評(píng)價(jià)系統(tǒng)中的應(yīng)用［J］．海南大學(xué)學(xué)報(bào):自然科學(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］ 徐濤，史開(kāi)泉．基于粗糙集理論的AHP層次分析法［J］．三明學(xué)院學(xué)報(bào)，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ì)［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］ 黃偉建，祝月紅，杜?。讵?jiǎng)勵(lì)機(jī)制的成員搜索引擎調(diào)度策略［J］．圖書(shū)館學(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］何夕平．模糊綜合評(píng)價(jià)在選擇最優(yōu)施工方案中的應(yīng)用［J］．合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(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．