多搜索引擎權(quán)重計(jì)算及搜索結(jié)果排序質(zhì)量評(píng)估

李 超 ，謝坤武

LI Chao1，2，3,XIE Kunwu1，2

1.湖北民族學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，湖北 恩施 445000

2.湖北民族學(xué)院 科技學(xué)院，湖北 恩施 445000

3.河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 211000

1.Deparment of Computer Science and Technology,Hubei Minzu University,Enshi,Hubei 445000,China

2.School of Computer Science and Technology,Hubei Minzu University,Enshi,Hubei 445000,China

3.College of Computer and Information,Hohai University,Nanjing 211000,China

1 引言

目前，用戶在進(jìn)行信息檢索時(shí)，存在如下現(xiàn)象：（1）在進(jìn)行信息檢索時(shí)，無(wú)論是全文搜索引擎還是元搜索引擎，大多數(shù)查詢趨向于短查詢[1]。由于查詢?cè)~的多義性，使得搜索結(jié)果往往涉及多個(gè)主題內(nèi)容。返回結(jié)果數(shù)量往往較大（考慮到保密、搜索效率、用戶遍歷習(xí)慣情況等因素，各搜索引擎往往只提供部分索引內(nèi)容），且用戶通常沒(méi)有足夠的時(shí)間及耐心去遍歷很多的檢索結(jié)果，而往往只關(guān)注檢索排列在前面的少量結(jié)果。（2）由于WWW的龐大，目前大多數(shù)搜索引擎按照與用戶查詢的相關(guān)度進(jìn)行排序，返回結(jié)果太多，而對(duì)搜索引擎日志的分析表明多數(shù)用戶只會(huì)瀏覽10～30個(gè)搜索結(jié)果[2]。另外，各搜索引擎返回的搜索結(jié)果靠前的部分往往比后面的更能滿足用戶的要求。（3）各搜索引擎覆蓋內(nèi)容往往只涉及部分資源，即使是元搜索引擎也只集成了少數(shù)搜索引擎的搜索結(jié)果，各搜索引擎返回的結(jié)果及排序存在很大差異。（4）各搜索引擎所采用的技術(shù)、算法往往不同且不公開(kāi)，適用范圍存在差異。針對(duì)某個(gè)查詢請(qǐng)求，不同搜索引擎搜索結(jié)果的重疊率不到34%[3]。

搜索結(jié)果的重復(fù)識(shí)別及排序?qū)τ谒阉鞣?wù)質(zhì)量的影響很大，搜索結(jié)果的排序在很大程度上決定著元搜索引擎的服務(wù)質(zhì)量。為了實(shí)現(xiàn)搜索結(jié)果的整合與排序，目前主要結(jié)合文檔內(nèi)容、初始排序、分析用戶點(diǎn)擊行為、查詢請(qǐng)求和查詢意圖[4-5]等因素，以及采用賦予成員搜索引擎權(quán)重等方法[6-7]。其中基于查詢請(qǐng)求、文檔內(nèi)容和結(jié)合用戶點(diǎn)擊行為等方法，比較復(fù)雜且會(huì)導(dǎo)致服務(wù)器或（和）客戶端高能耗及時(shí)延。而采用直接賦予搜索引擎權(quán)重[8-10]等方法，主要依靠用戶和技術(shù)人員經(jīng)驗(yàn)實(shí)現(xiàn)，主觀性強(qiáng)不能體現(xiàn)用戶個(gè)性化搜索要求。為此，提出跟蹤用戶搜索情況，在開(kāi)源搜索引擎Nutch[11]平臺(tái)上集成了多個(gè)成員搜索引擎，并透明、動(dòng)態(tài)地賦予各成員搜索引擎權(quán)重，滿足用戶一定程度的個(gè)性化需求，同時(shí)提高搜索服務(wù)質(zhì)量。通過(guò)跟蹤用戶遍歷情況，論證了該方法的可行性和有效性。

2 搜索引擎權(quán)重計(jì)算模型

2.1 搜索結(jié)果用戶遍歷情況統(tǒng)計(jì)

為了掌握用戶對(duì)搜索結(jié)果的瀏覽及滿意度情況，對(duì)母語(yǔ)為中文的部分用戶群體進(jìn)行了問(wèn)卷調(diào)查（后面實(shí)驗(yàn)通過(guò)客戶端部署的Agent跟蹤用戶的搜索遍歷習(xí)慣，可以發(fā)現(xiàn)比較近似的結(jié)果），得到了近1 000份有效調(diào)查問(wèn)卷，統(tǒng)計(jì)結(jié)果如表1所示。

表1 用戶查看搜索引擎返回結(jié)果的數(shù)量及滿意情況1）

通過(guò)統(tǒng)計(jì)發(fā)現(xiàn)，多數(shù)用戶遍歷搜索結(jié)果時(shí)只會(huì)查看搜索結(jié)果的前100個(gè)（所占比例約90%），2/3以上的用戶可以通過(guò)搜索引擎得到有用信息，大約有2/5的人通過(guò)搜索引擎結(jié)果能搜索到滿意結(jié)果。因此，在進(jìn)行多搜索引擎搜索結(jié)果的排序時(shí)，可以根據(jù)用戶遍歷搜索結(jié)果的情況，選取一定數(shù)量（與用戶遍歷數(shù)量存在一定的關(guān)聯(lián)，但不一定相同）的搜索結(jié)果并進(jìn)行排序，把整合后的結(jié)果返回給用戶。

2.2 用戶點(diǎn)擊行為分析

基于客戶端部署的Agent實(shí)現(xiàn)用戶點(diǎn)擊行為的跟蹤，可以忽略多用戶和群體行為[12-13]、識(shí)別非正常網(wǎng)絡(luò)用戶及行為[14]等任務(wù)。對(duì)于用戶的點(diǎn)擊行為，Joachims等[15]指出，用戶點(diǎn)擊行為不能用來(lái)判斷查詢與文檔間的存在絕對(duì)相關(guān)性，只能用于評(píng)估相對(duì)相關(guān)性。無(wú)論查詢與用戶點(diǎn)擊對(duì)象是絕對(duì)相關(guān)性，還是相對(duì)相關(guān)性，對(duì)于完成搜索引擎權(quán)重影響不大（關(guān)注的是用戶遍歷結(jié)果的來(lái)源以及來(lái)源的比例，從而確定搜索引擎重要性，即權(quán)重）。為此，主要記錄用戶點(diǎn)擊對(duì)象的來(lái)源，而不用去進(jìn)行會(huì)話（Session）切分、主題識(shí)別等工作?？梢愿鶕?jù)歷史遍歷情況（在網(wǎng)絡(luò)、計(jì)算資源充裕情況下可以進(jìn)行實(shí)時(shí)跟蹤分析），結(jié)合用戶遍歷Web的內(nèi)容，實(shí)現(xiàn)多成員搜索引擎返回結(jié)果的有效整合。該方法可以有效利用網(wǎng)絡(luò)帶寬及能耗，避免了對(duì)實(shí)時(shí)響應(yīng)服務(wù)能力的要求。

2.3 搜索引擎權(quán)重計(jì)算模型及結(jié)果排序

（2）當(dāng)α取值較大時(shí)，而執(zhí)行的搜索請(qǐng)求次數(shù)較少（即n較小）時(shí)，各搜索引擎的權(quán)重基本上取決于α的值，即各搜索引擎權(quán)重基本一致。當(dāng)α較大時(shí)，而執(zhí)行的搜索請(qǐng)求次數(shù)逐漸增加時(shí)（或n趨于無(wú)窮大時(shí)），αe-β(n-1)的值趨于0，此時(shí)各搜索引擎的權(quán)重主要取決于搜索結(jié)果中用戶滿意或感興趣搜索結(jié)果的來(lái)源。在用戶遍歷偏好難以確定或者不確定（用戶前期執(zhí)行搜索請(qǐng)求及遍歷量較小情況下），可以設(shè)置α為一個(gè)比較大的值。

（3）用戶訪問(wèn)的搜索結(jié)果數(shù)量往往有限，而搜索結(jié)果本身數(shù)量較大，為此，可以用歷來(lái)用戶搜索遍歷數(shù)量的最大值或者均值，代替。

2.4 內(nèi)容相同或相似Web頁(yè)面的處理

在用戶遍歷的結(jié)果中，可能存在許多內(nèi)容相似甚至相同的Web頁(yè)面，而用戶往往只去瀏覽靠前的Web頁(yè)面，在進(jìn)行搜索引擎權(quán)重計(jì)算時(shí)將產(chǎn)生偏差。為此，可以借助URL、Web內(nèi)容重復(fù)識(shí)別技術(shù)[16]，對(duì)上面的模型進(jìn)行一定的改進(jìn)。當(dāng)用戶訪問(wèn)一個(gè)Web頁(yè)面時(shí)，判斷是否有來(lái)自其他搜索引擎返回的URL相同（內(nèi)容肯定相同）、URL不同但內(nèi)容相同或者高度相似的頁(yè)面，從而更好地實(shí)現(xiàn)搜索引擎權(quán)重計(jì)算。關(guān)于這部分的內(nèi)容，本文不作詳細(xì)介紹。

3 搜索結(jié)果排序質(zhì)量

設(shè)在賦予搜索引擎不同權(quán)重WS1和WS2情況下，經(jīng)過(guò)排序得到搜索結(jié)果分別為 RS1和RS2，RS1=＜rs1,rs2,…，rsu＞，RS2=＜ rs′1，rs′2，…，rs′u＞，其中 u 為返回的結(jié)果數(shù)量。顯然，在不同的排序情況下，用戶點(diǎn)擊或下載的頁(yè)面在次序和數(shù)量上可能不一致。同時(shí)，用戶遍歷時(shí)不一定按照返回結(jié)果的次序遍歷（全部或部分）結(jié)果。為此，設(shè)用戶點(diǎn)擊遍歷的頁(yè)面序列為：DoR1=＜s1，s2，…，sN0＞和DoR2=＜ s′1，s′2，…，s′N1＞。其中 N0和 N1為在權(quán)重分別為DoR1和DoR2情況下用戶遍歷序列總數(shù)，顯然v0≤u，v1≤u。為了定量地分析搜索引擎權(quán)重對(duì)搜索結(jié)果排序質(zhì)量的影響，使用向量空間模型，把排序差異轉(zhuǎn)化為向量空間的匹配問(wèn)題，兩個(gè)排序結(jié)果的相似度S用向量間的夾角來(lái)度量。

（2）假設(shè)用戶遍歷了10個(gè)結(jié)果，依次為＜e，d，i，b，a，g，f，j，c，h＞，則可以把RS1和 DoR1分別轉(zhuǎn)換為RS1=＜1，2，3，4，5，6，7，8，9，10＞，DoR1=＜5，4，9，2，1，7，6，10，3，8＞，則返回的搜索結(jié)果順序與用戶遍歷情況的匹配度為：S=0.842。假設(shè)交換遍歷次序，往往會(huì)得到不同的匹配度。從而可以發(fā)現(xiàn)，搜索結(jié)果服務(wù)質(zhì)量，與搜索結(jié)果排列次序及用戶遍歷次序密切相關(guān)，與用戶遍歷結(jié)果的數(shù)量沒(méi)有必然聯(lián)系。

4 實(shí)驗(yàn)及分析

通過(guò)跟蹤近150個(gè)用戶的搜索遍歷情況，過(guò)濾掉搜索頻率較低（小于7次）用戶，得到了118位搜索用戶情況，對(duì)多數(shù)用戶使用搜索引擎的頻率、用戶瀏覽頁(yè)面的數(shù)量以及點(diǎn)擊數(shù)量和搜索結(jié)果排序與遍歷匹配度進(jìn)行統(tǒng)計(jì)分析，并設(shè)定可調(diào)因子α=600，β=2，得到如下情況。

（1）用戶使用搜索引擎的頻率

用戶使用搜索引擎的頻率可以通過(guò)時(shí)間段內(nèi)使用搜索引擎的人次來(lái)進(jìn)行間接的反映。通過(guò)分析118個(gè)搜索頻率較大的用戶，得到2013年5月1日至28日期間，用戶每日使用過(guò)搜索引擎的人次。從圖1可以看出，使用搜索引擎的人次，基本保持平穩(wěn)。個(gè)別時(shí)段，如節(jié)假日，會(huì)有一定的上升。

圖1 不同日期使用搜索引擎的人次

（2）用戶瀏覽頁(yè)面及點(diǎn)擊情況變化

為了掌握用戶瀏覽搜索結(jié)果的數(shù)量以及點(diǎn)擊數(shù)量，對(duì)其進(jìn)行了統(tǒng)計(jì)，如圖2（a）所示。同時(shí)，為了掌握用戶的點(diǎn)擊數(shù)量與瀏覽數(shù)量間的關(guān)系，得到了點(diǎn)擊數(shù)量與瀏覽數(shù)量比值，如圖2（b）所示，其中A代表用戶瀏覽搜索結(jié)果的數(shù)量，B代表用戶點(diǎn)擊數(shù)量。

圖2（a） 用戶瀏覽與點(diǎn)擊結(jié)果數(shù)

圖2（b） 點(diǎn)擊數(shù)占瀏覽比例

從圖2（a）可以看出，通過(guò)動(dòng)態(tài)地賦予元搜索引擎中各成員搜索引擎權(quán)重的方法，用戶瀏覽數(shù)量和遍歷數(shù)量經(jīng)過(guò)一段時(shí)間下降后趨于平穩(wěn)，瀏覽數(shù)量均值基本分布在20～30個(gè)左右。通過(guò)圖2（b）可以看到，用戶遍歷數(shù)量與瀏覽數(shù)量的比值，同樣經(jīng)過(guò)一段時(shí)間下降后趨于平穩(wěn)，并且基本分布在0.25～0.30之間。綜合圖2（a）和圖2（b）可以發(fā)現(xiàn)多少用戶會(huì)瀏覽20～30個(gè)搜索結(jié)果，而同時(shí)會(huì)去進(jìn)一步點(diǎn)擊其中的5～10個(gè)結(jié)果。

（3）搜索結(jié)果排序與遍歷匹配度

為了對(duì)經(jīng)過(guò)改進(jìn)的排序策略進(jìn)行質(zhì)量分析，根據(jù)用戶遍歷數(shù)據(jù)及公式（3），對(duì)搜索結(jié)果排序與遍歷的匹配度進(jìn)行分析，得到如圖3所示結(jié)果。

圖3 搜索結(jié)果排序與遍歷匹配度

從圖3可以看出，通過(guò)動(dòng)態(tài)地賦予元搜索引擎中各成員搜索引擎權(quán)重的方法，搜索結(jié)果排序與遍歷匹配度得到了一定的提升，總體提升了10%左右。

（4）與基于內(nèi)容相關(guān)度和固定權(quán)重排序法的比較

為了掌握與其他方法的差異，另外采用了基于搜求請(qǐng)求與Web頁(yè)面內(nèi)容的相關(guān)度和固定分配搜索引擎權(quán)重兩種策略排序，分析統(tǒng)計(jì)分析了在實(shí)現(xiàn)重新排序的響應(yīng)時(shí)間、搜索結(jié)果排序與遍歷匹配度兩個(gè)方面的情況。對(duì)于一定數(shù)量的結(jié)果進(jìn)行排序，三種方法所耗時(shí)間（硬件配置信息略）結(jié)果如圖4所示。

圖4 排序所耗時(shí)間對(duì)比

圖4中，B_C、W和W_F分別表示基于搜索請(qǐng)求與Web頁(yè)面內(nèi)容相關(guān)度、本文方法以及固定權(quán)重法時(shí)對(duì)特定數(shù)量的搜索結(jié)果進(jìn)行排序所耗時(shí)間。從圖4可見(jiàn)，在排序目標(biāo)確定的情況下，基于內(nèi)容的方法，耗時(shí)較長(zhǎng)，固定排序法耗時(shí)最短，本文所采用的方法，比固定權(quán)重法略長(zhǎng)但很接近。

為了了解搜索結(jié)果排序與遍歷匹配度，通過(guò)跟蹤并分析了連續(xù)20天內(nèi)、基于這三種方法的用戶遍歷與搜索排序結(jié)果的匹配度，取用戶匹配度均值得到結(jié)果如圖5所示。

圖5 匹配度變化圖

圖5中，B_C、W和W_F分別表示基于搜索請(qǐng)求與Web頁(yè)面內(nèi)容相關(guān)度、本文方法以及固定權(quán)重法時(shí)對(duì)特定數(shù)量的搜索結(jié)果進(jìn)行排序時(shí)，用戶遍歷與搜索排序的匹配度。從圖5可以發(fā)現(xiàn)：基于內(nèi)容的排序的匹配度相對(duì)來(lái)說(shuō)比較穩(wěn)定，且多數(shù)情況下，比固定權(quán)重法匹配度要高；本文所采用的方法（統(tǒng)計(jì)的α的值大于500的用戶搜求遍歷情況）隨著用戶搜索及遍歷次數(shù)增加，匹配度逐漸趨于穩(wěn)定，且匹配度高于另外兩種方法。在考慮響應(yīng)時(shí)間及匹配度的情況下，通過(guò)圖4和圖5可以發(fā)現(xiàn)，本文方法比簡(jiǎn)單的基于搜索請(qǐng)求與內(nèi)容相關(guān)度，以及固定權(quán)重的排序方法更優(yōu)。通過(guò)設(shè)定不同的α和β的初始值，得到的結(jié)果略有偏差，但總體情況基本一致。

實(shí)驗(yàn)結(jié)果表明，通過(guò)挖掘用戶歷史搜索偏好，動(dòng)態(tài)地賦予各成員搜索引擎權(quán)重進(jìn)而實(shí)現(xiàn)搜索結(jié)果的整合方法，在對(duì)響應(yīng)速度影響不大情況下，可以提高用戶遍歷的效率，論證了該方法的可行性和有效性。

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

在實(shí)現(xiàn)多搜索引擎搜索結(jié)果整合時(shí)，采用賦予搜索引擎權(quán)重時(shí)，目前的方法主要根據(jù)用戶和技術(shù)人員經(jīng)驗(yàn)實(shí)現(xiàn)，主觀性強(qiáng)，不能體現(xiàn)用戶個(gè)性化搜索要求。為此，提出通過(guò)挖掘用戶搜索歷史，動(dòng)態(tài)地賦予各成員搜索引擎權(quán)重進(jìn)而實(shí)現(xiàn)二次排序?；谠摲椒捎行?shí)現(xiàn)多源的數(shù)據(jù)集成，也可以用于用戶偏好挖掘、商品推薦等方面。當(dāng)然，還有一些工作需要進(jìn)一步進(jìn)行或完善：（1）在搜索引擎初始權(quán)重賦值時(shí)，為了無(wú)區(qū)別對(duì)待搜索引擎，采用了初始等權(quán)重的方法。然而，因不同搜索引擎索引內(nèi)容及技術(shù)不同，可以考慮在實(shí)現(xiàn)不同類型資源搜索時(shí)賦予各搜索引擎賦予不同的初始權(quán)重，然后進(jìn)行多類型搜索權(quán)重折中，這也將是下一步的工作。（2）在現(xiàn)有工作基礎(chǔ)上，進(jìn)行現(xiàn)有主流搜索引擎權(quán)重賦值方法的實(shí)驗(yàn)對(duì)比分析，當(dāng)然這將是一個(gè)工作量很大的任務(wù)。（3）因?yàn)锳gent跟蹤對(duì)象在地域、文化、教育等方面差異，點(diǎn)擊事件存在噪音，跟蹤用戶及搜索請(qǐng)求的規(guī)模較小，以及對(duì)用戶搜索資料收集不全面性等問(wèn)題，統(tǒng)計(jì)數(shù)據(jù)可能與實(shí)際情況存在一定誤差。

[1]Franzen K，Karlgren J.Verbosity and interface design[J].SICS Research Report，2000，1（1）：1-5.

[2]Jansen B J，Spink A，Bateman J，et al.Real life information retrieval：a study of user queries on the Web[J].ACM SIGIR Forum，1998，32（1）：5-17.

[3]Wu S，McClean S.Result merging methods in distributed information retrieval with overlapping databases[J].Information Retrieval，2007，10（3）：297-319.

[4]Dai H K，Zhao L，Nie Z，et al.Detecting Online Commercial Intention（OCI）[C]//Proceedings of the 15th International Conference on World Wide Web，2006：829-837.

[5]Broder A.A taxonomy of web search[J].ACM Sigir Forum，2002，36（2）：3-10.

[6]Zhao Chongchong，Zhang Zhiqiang，Xie Xiang.A new keywords method to improve web search[C]//12th IEEE International Conference on High Performance Computing and Communications.Melbourne，VIC：Institute of Electrical and Electronics Engineers，2010：477-484.

[7]Haveliwala T H.Topic-sensitive page rank：a context-sensitive ranking algorithm for web search[J].IEEE Transactions on Knowledge and Data Engineering，2003，15（4）：784-796.

[8]Wu S，McClean S.Performance prediction of data fusion for information retrieval[J].Information Processing&Management，2006，42（4）：899-915.

[9]Wu S，McClean S.Improving high accuracy retrieval by eliminating the uneven correlation effect in data fusion[J].Journal of the American Society for Information Science and Technology，2006，57（14）：1962-1973.

[10]Meng Weiyi，Yu C.Building efficient and effective metasearch engines[J].ACM Computer Surveys，2002，34（1）：48-89.

[11]Khare R，Cutting D，Sitaker K，et al.Nutch：a flexible and scalable open-source web search engine[EB/OL].[2013-06-20].http：//citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.5978&rank=1.

[12]Guo F，Liu C，Wang Y M.Efficient multiple-click models in web search[C]//Proceedings of the Second ACM International Conference on Web Search and Data Mining，2009：124-131.

[13]Agichtein E，Brill E，Dumais S.Learning user interaction models for predicting web search result preferences[C]//Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，2006：3-10.

[14]Tan P N，Kumar V.Discovery of web robot sessions based on their navigational patterns[M]//Intelligent Technologies for Information Analysis.Berlin Heidelberg：Springer，2004：193-222.

[15]Joachims T，Granka L，Pan B，et al.Accurately interpreting click through data as implicit feedback[C]//Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，2005：154-161.

[16]Fetterly D，Manasse M，Najork M.On the evolution of clusters of near-duplicate web pages[J].Journal of Web Engineering，2003，2（4）：228-246.