一種自反饋式元搜索系統(tǒng)的設(shè)計(jì)

程傳鵬,王天志

(1.中原工學(xué)院,鄭州 450007;2.云南師范大學(xué),昆明 650092)

一種自反饋式元搜索系統(tǒng)的設(shè)計(jì)

程傳鵬1,王天志2

(1.中原工學(xué)院,鄭州 450007;2.云南師范大學(xué),昆明 650092)

分析了常見元搜索系統(tǒng)中普遍存在的問題,對(duì)獨(dú)立搜索引擎的選擇以及搜索結(jié)果的集成提出了改進(jìn)的方法,并在此基礎(chǔ)上設(shè)計(jì)出一種自反饋式元搜索系統(tǒng).實(shí)驗(yàn)結(jié)果表明,該元搜索系統(tǒng)提高了用戶的搜索效率.

元搜索;自反饋;獎(jiǎng)勵(lì)系數(shù);查詢相關(guān)度

隨著Internet的迅猛發(fā)展,搜索引擎已是人們獲取知識(shí)最重要的來源之一.但由于信息量的龐大以及采用的技術(shù)不同,大部分的獨(dú)立搜索引擎都只涉及到整個(gè)WWW資源的30%～50%[1].元搜索引擎的出現(xiàn),整合了獨(dú)立搜索引擎的資源,一定程度上解決了搜索引擎查全率低的問題.元搜索引擎依賴于獨(dú)立搜索引擎進(jìn)行查找,但由于各個(gè)獨(dú)立搜索引擎的差異性,元搜索引擎在對(duì)各個(gè)獨(dú)立搜索引擎返回的搜索結(jié)果的整合上還存在一定的問題.本文對(duì)元搜索引擎中的獨(dú)立搜索引擎調(diào)度以及輸出結(jié)果排序兩項(xiàng)關(guān)鍵技術(shù)進(jìn)行了研究,在此基礎(chǔ)上提出了一種自反饋式元搜索系統(tǒng).實(shí)驗(yàn)結(jié)果表明,該元搜索系統(tǒng)提高了用戶的搜索效率.

1 關(guān)鍵技術(shù)

元搜索引擎的主要作用是對(duì)獨(dú)立搜索引擎的檢索結(jié)果作進(jìn)一步處理.它沒有自己的文檔索引數(shù)據(jù)庫,其信息來源于獨(dú)立搜索引擎的結(jié)果輸出[2].從元搜索引擎的工作過程來看,元搜索引擎的關(guān)鍵工作主要集中在對(duì)獨(dú)立搜索引擎的選取以及獨(dú)立搜索引擎返回的搜索結(jié)果的排序.下面對(duì)這兩項(xiàng)技術(shù)進(jìn)行分析.

1.1 獨(dú)立搜索引擎返回結(jié)果的選擇

對(duì)于每個(gè)查詢字符串,元搜索引擎通過代理接口向獨(dú)立搜索引擎提交查詢請求,一般獨(dú)立搜索引擎都將返回成千上萬甚至幾十萬個(gè)搜索結(jié)果,這其中含有我們需要的結(jié)果,然而更多的是干擾信息[3].目前的元搜索引擎一般都事先設(shè)置好參數(shù),從各個(gè)獨(dú)立搜索引擎的搜索結(jié)果中提取同等數(shù)量的搜索結(jié)果.這種方法其實(shí)是不妥當(dāng)?shù)?對(duì)于同一個(gè)查詢請求,有的獨(dú)立搜索引擎查詢精度高,有的獨(dú)立搜索引擎查詢精度低,我們應(yīng)該從搜索精度高的獨(dú)立搜索引擎里多取出一些搜索結(jié)果.由此本文提出一種可以根據(jù)反饋信息自動(dòng)調(diào)整獨(dú)立搜索引擎權(quán)重的算法.為了便于討論,給出如下幾個(gè)定義:

定義1 從獨(dú)立搜索引擎的搜索結(jié)果中所取回的搜索比例,定義為獨(dú)立搜索引擎的權(quán)重,用符號(hào)Wi表示.

定義2 每個(gè)獨(dú)立搜索引擎的搜索結(jié)果的數(shù)量,定義為獨(dú)立搜索引擎的基,用符號(hào)|Rei|表示.

定義3 元搜索引擎最終向用戶提交的結(jié)果集,定義為最終結(jié)果集,用符號(hào)|R|表示.

定義4 獨(dú)立搜索引擎在最終搜索結(jié)果集中所占的比例,定義為獨(dú)立搜索引擎比重,用符號(hào) Pi表示.

在以上分析的基礎(chǔ)上,形成如下的算法:

(1)對(duì)每個(gè)獨(dú)立搜索引擎 Rei賦以初始權(quán)重W0,即Wi=W0=1/n,n為所調(diào)用的獨(dú)立搜索引擎?zhèn)€數(shù).

(2)計(jì)算最初從 Rei中提取的結(jié)果的數(shù)量Ni:

式中:Rei表示第i個(gè)獨(dú)立搜索引擎;|Rei|表示集合 Rei的基.

對(duì)于一個(gè)查詢請求,獨(dú)立搜索引擎都會(huì)返回很多搜索結(jié)果,但用戶一般只會(huì)選擇前面的幾頁來瀏覽,實(shí)際瀏覽量很少.所以在(1)式的基礎(chǔ)上加一個(gè)常數(shù)c1,形成公式(2):

式中:c1視對(duì)返回結(jié)果數(shù)量的要求而定,可以取0.01、0.001等,目的是來縮小搜索范圍.

(3)將每個(gè) Rei中前Ni個(gè)結(jié)果取出,合并形成原始結(jié)果集,對(duì)結(jié)果集用本文所提出的位置/摘要排序法進(jìn)行排序,取前 n個(gè)結(jié)果形成最終結(jié)果集.其中:

式中:M為獨(dú)立搜索引擎?zhèn)€數(shù);c2為常數(shù),用來縮小搜索規(guī)模.

(4)計(jì)算每個(gè)獨(dú)立搜索引擎在最終結(jié)果集中所占的比例:

pi=ni/n (5)

式中:ni表示第i個(gè)獨(dú)立搜索引擎中最終入選搜索結(jié)果集的搜索結(jié)果數(shù)量.

對(duì) pi規(guī)范化,形成如下公式:

(5)根據(jù)獨(dú)立搜索引擎比重重新調(diào)整每個(gè)獨(dú)立搜索引擎 Rei的權(quán)重:

ωi=c3ω0+c4Pi(6)

式中:c3和 c4為常數(shù),且c3+c4=1.c3和 c4的大小決定了 Pi對(duì)ωi的影響力.

對(duì)ωi規(guī)范化,形成如下公式:

(6)從獨(dú)立搜索引擎所返回的搜索結(jié)果中提取的數(shù)量為:

1.2 位置/摘要排序法的改進(jìn)

元搜索系統(tǒng)中搜索結(jié)果的排序,一般采取的是位置/摘要排序法.它的主要思想是根據(jù)用戶查詢串與搜索結(jié)果記錄中摘要信息的相關(guān)性以及查詢串在摘要中的位置來對(duì)搜索結(jié)果進(jìn)行排序.先計(jì)算查詢串與每條搜索結(jié)果記錄的相關(guān)程度,最后將這些搜索結(jié)果記錄按照相關(guān)度從大到小的順序返回給用戶[4].摘要排序法的計(jì)算步驟如下:

(1)對(duì)查詢串 Q進(jìn)行詞條切分,形成詞條 l1,l2,l3,…li,…,lm,其中,m為詞條個(gè)數(shù).

(2)計(jì)算查詢串Q中每個(gè)詞條lj與文摘Abstracti的相關(guān)度 Rl(lj,ABstracti):

式中:Length(Abstracti)為 Abstracti的長度;Occurence(lj,Abstracti)為 lj在Abstractj中出現(xiàn)的次數(shù);L ocation(lj,k,Abstracti)為詞條 lj在 Abstracti中第k次出現(xiàn)的位置.

(3)計(jì)算 Abstracti與Q的相關(guān)度 Rq(Q,Abstracti) :

式中:m為查詢串Q中的詞條數(shù).

下面我們通過一個(gè)例子,來說明此方法的不足之處.假設(shè)查詢串“搜索引擎的設(shè)計(jì)與實(shí)現(xiàn)”,通過分詞,該查詢串被切分為“搜索引擎”、“設(shè)計(jì)”、“實(shí)現(xiàn)”3個(gè)詞條.“搜索引擎”字串在 Abstract1中出現(xiàn)了3次,而在Abstract2中3個(gè)詞條各出現(xiàn)了1次,如果按照式(10)來計(jì)算,那么 Rq(Q,Abstract1)=Rq(Q,Abstract2),也就是說,Q相對(duì)于Abstract1的查詢相關(guān)度與 Q相對(duì)于Abstract2的查詢相關(guān)度一樣.但直觀上來看,Abstract2更符合查詢的要求,理應(yīng)得到更多關(guān)注,基于此,我們考慮給詞條匹配全面的文檔獎(jiǎng)勵(lì).

定義5 定義元搜索引擎最后提交給用戶的搜索結(jié)果集為最終結(jié)果集.

定義6 假設(shè)查詢串Q經(jīng)過詞條切分后,有 M個(gè)詞條在文摘Abstracti中出現(xiàn),則定義 Abstracti獎(jiǎng)勵(lì)系數(shù)為M T(Q,Abstracti).

定義7 定義詞條 lj與文摘Abstracti的詞條匹配系數(shù)為mt(lj,abstracti):

在以上分析的基礎(chǔ)上,本文提出的搜索結(jié)果的排序算法如下:

(1)計(jì)算文摘 Abstracti的獎(jiǎng)勵(lì)系數(shù)M T(Q,Abstracti):

式中:X為查詢串Q中詞條的個(gè)數(shù).

(2)計(jì)算查詢串 Q與文摘Abstracti的相關(guān)度R(Q,Abstracti):

(3)計(jì)算最終結(jié)果集中第 i個(gè)搜索結(jié)果的位置信息得分Pos(ri):

(4)綜合位置信息和相關(guān)度信息,得到最終排序分?jǐn)?shù)Rank(ri):

式中:c5、c6是常數(shù),它們的大小決定了位置信息和相關(guān)度信息對(duì)最終排序的影響力;K為最終選擇的搜索結(jié)果個(gè)數(shù).

(5)將最終結(jié)果集中的 r1按照 Rank(ri)的值從大到小排列.

2 自反饋式元搜索系統(tǒng)的結(jié)構(gòu)

元搜索引擎又稱作搜索引擎之上的搜索引擎,它沒有自己的網(wǎng)頁數(shù)據(jù)庫和索引庫.用戶通過元搜索引擎接口向獨(dú)立搜索引擎提交查詢請求,獨(dú)立搜索引擎返回的結(jié)果再通過元搜索引擎進(jìn)一步整合后,提交給用戶.在以上分析的基礎(chǔ)上,設(shè)計(jì)出一個(gè)元搜索引擎模型,其中包含有用戶接口、元搜索接口、搜索結(jié)果提取和搜索結(jié)果排序4個(gè)模塊.整個(gè)系統(tǒng)的結(jié)構(gòu)如圖1所示.

圖1 自反饋式元搜索系統(tǒng)結(jié)構(gòu)圖

自反饋式元搜索系統(tǒng)的流程如下:

(1)用戶通過元搜索接口提出搜索請求;

(2)元搜索接口將查詢短語整理后,發(fā)送到獨(dú)立搜索引擎,并獲取搜索引擎的搜索結(jié)果,形成原始網(wǎng)頁集;

(3)由元搜索接口返回的搜索結(jié)果集,通過本文所提出的選擇方法進(jìn)行二次選擇;

(4)經(jīng)過二次選擇的搜索結(jié)果集,按照本文所提出的相關(guān)度排序方法進(jìn)行排序;

(5)經(jīng)過查詢相關(guān)度排序后,最終提交給用戶一定數(shù)量的搜索結(jié)果.

3 實(shí)驗(yàn)結(jié)果及分析

在搜索引擎返回的結(jié)果中,符合用戶查詢意圖的結(jié)果數(shù)量所占的百分比,稱作搜索引擎的查準(zhǔn)率.查準(zhǔn)率是衡量搜索引擎搜索質(zhì)量的一個(gè)重要指標(biāo),但目前還沒有很好的方法對(duì)這一指標(biāo)作出量化.本文中查準(zhǔn)率可通過多個(gè)人工專家分別打分,取得分的平均值來確定.這里假設(shè)人工專家的查準(zhǔn)率為100%,以百度和搜狗2個(gè)搜索引擎作比較,以不同的關(guān)鍵詞進(jìn)行搜索,百度和搜狗的返回結(jié)果只取前面10頁.經(jīng)過實(shí)驗(yàn),得到如表1所示的結(jié)果.

表1 實(shí)驗(yàn)結(jié)果

從表1中的實(shí)驗(yàn)數(shù)據(jù)可以看出,本文中的方法雖然在時(shí)間上劣于其他搜索引擎的搜索時(shí)間,但大大提高了查準(zhǔn)率.

4 結(jié) 語

搜索引擎的選擇和查詢結(jié)果的排序是元搜索引擎需要重點(diǎn)解決的關(guān)鍵技術(shù).本文在分析了常見元搜索系統(tǒng)結(jié)果集成的基礎(chǔ)上,根據(jù)每次查詢的反饋信息自動(dòng)調(diào)整獨(dú)立搜索引擎的權(quán)重,做到了依據(jù)查詢串動(dòng)態(tài)地調(diào)整從每個(gè)獨(dú)立搜索引擎中返回的結(jié)果,并且對(duì)傳統(tǒng)的位置/摘要排序方法進(jìn)行了分析,指出了其不足之處,提出了相應(yīng)的改進(jìn)措施.

[1] 李永平,文坤梅.集成搜索引擎中結(jié)果排序的優(yōu)化分析[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)2001,31(11):28-30.

[2] 王敏,楊炳儒.基于主題的個(gè)性化元搜索引擎的設(shè)計(jì)與實(shí)現(xiàn)[J].情報(bào)檢索2005,31(11):57-58.

[3] 肖建華,蔣明,何瑗,等.二次搜索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究2003,20(9):28-30.

[4] 張衛(wèi)豐,徐寶文,周曉宇,等.元搜索引擎結(jié)果生成技術(shù)研究[J].小型微型計(jì)算機(jī)系統(tǒng),2003,24(1):123-126.

Design of Self-response Meta Search System

CHENG Chuan-peng1,WANG Tian-zhi2
(1.Zhongyuan University of Technology,Zhengzhou 450007;2.Yunnan Normal University,Kunming 650092,China)

This paper analyzes the common question in meta-search system,and proposes improvement method for selection of independent search and integration of search result.On this basis,a response metasearch system is designed.Experiments show that the meta search system has improved efficiency of search

meta-search engines;self-response;incentive factor;query relevance

TP391

A

10.3969/j.issn.1671-6906.2011.04.015

1671-6906(2011)04-0068-04

2011-06-13

程傳鵬(1977-),男,河南鄭州人,講師,碩士.