1、 基于詞匯相關(guān)度的個(gè)性化搜索算法1譚振華1,2,程維1,2,常桂然,1,高曉興1,21東北大學(xué)信息科學(xué)與工程學(xué)院,沈陽(1100042東北大學(xué)軟件學(xué)院,沈陽(110004摘要:本文提出了一種基于詞匯相關(guān)度的個(gè)性化搜索算法。提出使用詞匯之間的“相關(guān)度”來存儲(chǔ)單個(gè)用戶的個(gè)性化信息,并提出了能夠在用戶進(jìn)行檢索的過程中利用用戶偏好自動(dòng)建立針對該用戶的“詞匯相關(guān)度網(wǎng)”的方法,以及三種不同的利用詞匯相關(guān)度對底層搜索引擎所返回的結(jié)果進(jìn)行重新評估并進(jìn)行個(gè)性化排序的策略。關(guān)鍵詞:信息檢索,個(gè)性化,詞匯相關(guān)度1.引言普通的Web搜索引擎,由于其使用的頁面評估技術(shù)并不考慮各個(gè)不同用戶的使用習(xí)慣和偏好,導(dǎo)致搜索結(jié)果中

2、的絕大多數(shù)文檔內(nèi)容不是用戶所需要的,查準(zhǔn)率和查全率都無法達(dá)到用戶的要求。對這個(gè)問題的一種解決辦法就是建立個(gè)性化的Web搜索引擎。所謂的“個(gè)性化”,也就是搜索引擎會(huì)根據(jù)單個(gè)用戶的習(xí)慣自動(dòng)調(diào)整自己的設(shè)置,以使檢索結(jié)果盡量滿足該用戶的需求。從某種意義上說,個(gè)性化搜索引擎就好像為每一個(gè)用戶單獨(dú)量身定做了一個(gè)搜索引擎。本文中提出使用詞匯之間的“相關(guān)度”來存儲(chǔ)特定用戶的個(gè)性化信息。并提出了能夠在用戶進(jìn)行檢索的過程中自動(dòng)建立針對該用戶的“詞匯相關(guān)度網(wǎng)”的方法,以及3種不同的利用詞匯相關(guān)度對底層搜索引擎所返回的結(jié)果進(jìn)行重新評估并進(jìn)行個(gè)性化排序的策略。最后我們設(shè)計(jì)了基于詞匯相關(guān)度的個(gè)性化元搜索引擎的原型系統(tǒng)。2

3、.相關(guān)工作目前對個(gè)性化信息檢索技術(shù)的研究比較很廣泛,已經(jīng)出現(xiàn)了很多關(guān)于個(gè)性化搜索的服務(wù)系統(tǒng)3,4 ,提出了很多思路以及實(shí)現(xiàn)。如:在文獻(xiàn)1中,提出了一種基于智能代理(Intelligent Agent技術(shù)的智能化信息檢索體系結(jié)構(gòu);文獻(xiàn)2中所提到的Autonomy智能代理系統(tǒng)使用神經(jīng)元網(wǎng)絡(luò)來識(shí)別信息模式;文獻(xiàn)9提出了對Yahoo進(jìn)行基于層次聚類式重組和檢索方式的改造方法,并實(shí)現(xiàn)了基于特征矢量空間模式檢索方法。個(gè)性化搜索引擎一般都基于元搜索引擎來進(jìn)行個(gè)性化服務(wù)。元搜索引擎5,6指的是搜索引擎之上的搜索引擎,可以將用戶的檢索詞轉(zhuǎn)發(fā)給多個(gè)底層的搜索引擎,使用戶不必直接跟底層的各個(gè)搜索引擎交互,相當(dāng)于增加

4、了搜索引擎的信息覆蓋面。搜索引擎中最關(guān)鍵的部分是文檔建模技術(shù),目前的眾多文本模型一般可以分為向量空間模型、布爾邏輯模型和概率推理模型11。人們普遍認(rèn)為向量空間模型是一種非常有效的文本模型7。它使用一個(gè)多維的向量來表示一個(gè)文檔,每一個(gè)維度對應(yīng)于文檔中的一個(gè)關(guān)鍵詞,維度上的值是對應(yīng)關(guān)鍵字的權(quán)值。只要通過某種策略計(jì)算出每一個(gè)字項(xiàng)的權(quán)值,就可以將文檔D表示成一個(gè)向量。這里假設(shè)每一個(gè)字項(xiàng)的權(quán)值分別用W1、W2、W3W m表示,則文檔D的向量表示為:D=(W1, W2, W3, W m但是,向量空間模型有一個(gè)固有的缺點(diǎn),即假設(shè)所有的索引項(xiàng)都是獨(dú)立的,而事實(shí)上信1本課題得到高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(項(xiàng)

5、目編號:20030145017的資助。 息的索引項(xiàng)之間常常是具有某種內(nèi)部關(guān)聯(lián)的。為了描述文本詞匯之間的相關(guān)聯(lián)的程度,本文提出了一種新的文本建模技術(shù),即詞匯相關(guān)度模型。3.詞匯相關(guān)度模型3.1 詞匯相關(guān)度模型中文檔的表示在詞匯相關(guān)度模型中,一個(gè)包含m 個(gè)詞匯的文檔D 被表示成m 個(gè)二元組的集合:,(,.,(,(2211m m w t w t w t D =其中,t i 表示詞匯,w i 表示t i 在文本D 中的權(quán)重(重要程度,取值范圍為-1,1。3.2 詞匯相關(guān)度定義約定:用戶對檢索結(jié)果的反饋有三種情況:好結(jié)果、壞結(jié)果和不好不壞結(jié)果。系統(tǒng)取顯示反饋的好結(jié)果和壞結(jié)果兩種情況。定義:1“#”代表相

6、關(guān)度運(yùn)算,是一個(gè)二元運(yùn)算符;對于詞匯A 和B ,A#B 代表A 、B 之間的相關(guān)度;通常情況下,#運(yùn)算不可交換。2Good_A 表示用戶檢索詞匯A 時(shí)反饋好結(jié)果的個(gè)數(shù);Bad_A 表示用戶檢索詞匯A 時(shí)反饋壞結(jié)果的個(gè)數(shù)。3Good_A_B 表示用戶檢索詞匯A 的“好結(jié)果”中,出現(xiàn)詞匯B 的好結(jié)果的個(gè)數(shù);Bad_A_B 則表示相應(yīng)的壞結(jié)果的個(gè)數(shù)。4GoodA#B=Good_A_B/Good_A ,取值在閉區(qū)間0,1之間,表示在用戶反饋的“好結(jié)果”中兩詞匯同時(shí)出現(xiàn)在文本中的概率,我們稱此為正相關(guān)度。正相關(guān)度對詞匯之間總的相關(guān)度有正面影響。5BadA#B=(-1×Bad_A_B/Bad_A

7、 ,取值在閉區(qū)間-1,0之間,表示在用戶反饋的“壞結(jié)果”中兩詞匯同時(shí)出現(xiàn)在文本中的概率,我們稱此為負(fù)相關(guān)度。負(fù)相關(guān)度對詞匯之間總的相關(guān)度有負(fù)面影響。6A#B = GoodA#B + BadA#B,表示A 與B 之間總的相關(guān)度,取值在閉區(qū)間-1,1之間。詞匯相關(guān)度反映了在特定用戶眼中詞匯與詞匯之間的相關(guān)聯(lián)的程度。對于不同的用戶和不同的搜索,詞匯之間的相關(guān)度是不同的。如:對喜歡音樂下載的用戶來說“音樂”#“下載”值會(huì)比較高,而對喜歡音樂軟件的用戶“音樂”#“軟件”值會(huì)比較高。3.3 用戶偏好信息的存儲(chǔ)在詞匯相關(guān)度模型中,我們使用一個(gè)邏輯上的相關(guān)度網(wǎng)來表示用戶的偏好信息。這個(gè)相關(guān)度網(wǎng)中的每一個(gè)節(jié)點(diǎn)代

8、表一個(gè)詞匯,兩個(gè)節(jié)點(diǎn)之間的連線代表了兩個(gè)詞匯之間的關(guān)系,連線上方的數(shù)值代表了這兩個(gè)詞匯之間相關(guān)度。如圖1所示,是一個(gè)簡單的相關(guān)度網(wǎng)。 圖1 簡單的詞匯相關(guān)度網(wǎng)圖1中,詞匯之間的連線表示詞匯之間的關(guān)系,這個(gè)關(guān)系是單向的。連線上的數(shù)值表示兩個(gè)詞匯之間的相關(guān)程度。例如圖1中“t1”與“t2”之間的相關(guān)度是v1,也就是說明該用戶搜索“t1”的時(shí)候,與“t2”相關(guān)的程度為v1。在相關(guān)度網(wǎng)中,箭頭一般都是單項(xiàng)箭頭,表示詞匯相關(guān)程度不可交換。對于某個(gè)特定的用戶,在他使用個(gè)性化信息檢索系統(tǒng)的過程中,會(huì)不斷地向系統(tǒng)發(fā)出一些反饋信息。系統(tǒng)就可以利用這個(gè)反饋信息自動(dòng)構(gòu)造或更新相應(yīng)的相關(guān)度網(wǎng)。由于詞匯關(guān)系網(wǎng)是在用戶反

9、饋過程中建立起來的,關(guān)系網(wǎng)就好像“指紋”一樣,各不相同。有了這樣的一個(gè)相關(guān)度網(wǎng),就可以通過查詢這個(gè)網(wǎng)來得到任意給定的兩個(gè)詞匯的相關(guān)度。4.個(gè)性化評估算法個(gè)性化元搜索引擎依賴于底層搜索引擎的搜索結(jié)果,系統(tǒng)必須對底層返回的結(jié)果文本集按一定算法進(jìn)行重新評估,最后排序輸出。根據(jù)用戶輸入的檢索詞,系統(tǒng)可以通過詞匯相關(guān)度網(wǎng)查詢關(guān)鍵字與摘要關(guān)鍵詞中的每一個(gè)詞匯的相關(guān)度,來計(jì)算文本中二元組里的詞匯權(quán)重。4.1 單檢索詞的文本評估計(jì)算模型我們首先考慮用戶只輸入單個(gè)檢索詞q時(shí)文本評估值的計(jì)算,如圖2所示。假定底層搜索引擎根據(jù)q返回的結(jié)果文本D中包含m個(gè)關(guān)鍵詞t1、t2、t m。通過查詢詞匯相關(guān)度網(wǎng)可以獲得各個(gè)關(guān)鍵

10、詞與檢索詞q的相關(guān)度,分別用w1、w2w m表示。此時(shí),相關(guān)度就是二元組中的權(quán)重。 圖2 單個(gè)檢索詞時(shí)文本評估值的計(jì)算 那么,(,.,(,(2211m m w t w t w t D =的評估值為各個(gè)權(quán)重(相關(guān)度之和(w 1+w 2+w m 歸一化之后的結(jié)果,我們用w(D表示結(jié)果文本D 的評估值。(1=ni i w D w 1(4.2 多檢索詞的文本評估計(jì)算模型假如用戶輸入n 個(gè)檢索詞,可以按照單個(gè)檢索詞類似的方式單獨(dú)處理每一個(gè)檢索詞。如圖3所示。 圖3 n 個(gè)檢索詞時(shí)文本評估值的計(jì)算假設(shè)根據(jù)n 個(gè)檢索詞檢索得到的結(jié)果文本D 包含m 個(gè)關(guān)鍵詞t 1、t 2、t m ,每一個(gè)關(guān)鍵詞與各個(gè)檢索詞之

11、間都有一個(gè)相關(guān)度。在只考慮q 1檢索詞的情況下可以計(jì)算出文本中各個(gè)關(guān)鍵詞與q 1之間的相關(guān)度;同樣,在只考慮q n 檢索詞的情況下,可以計(jì)算出文本中各個(gè)關(guān)鍵詞與q n 之間的相關(guān)度。我們用w i1、w i2、w im 來表示各個(gè)關(guān)鍵詞與檢索詞q i 之間的相關(guān)度。顯然,對于文本D 中的任意關(guān)鍵詞t i 都有n 個(gè)檢索詞與之相關(guān),形成n 個(gè)相關(guān)度,此時(shí)必須使用一定的策略來計(jì)算t i 的最終權(quán)重,我們用w(t i 來表示這個(gè)最終權(quán)重。本文采用如下3種策略來計(jì)算w(t i 。策略1:剩余項(xiàng)加權(quán)和在這種策略中,我們將數(shù)值1與關(guān)鍵詞當(dāng)前權(quán)重之差稱作剩余項(xiàng)。每當(dāng)計(jì)算出關(guān)鍵詞與檢索詞之間的一個(gè)權(quán)重,就在關(guān)鍵

12、詞當(dāng)前權(quán)重的基礎(chǔ)之上加上當(dāng)前剩余項(xiàng)與新計(jì)算出的相關(guān)度的積。這種策略主要考慮到關(guān)鍵詞與檢索詞的相關(guān)度中的高相關(guān)度群體的利益,計(jì)算的結(jié)果主要靠近高相關(guān)度群體。用w j 表示q j 與t i 的相關(guān)度: w j =q j # t i (j 1,n,i 1,m 則:w(t i = w 1+ (1- w 1×w 2+ (1- w 1-(1- w 1×w 2×w 3檢索詞文本關(guān)鍵詞 + (1- w 1-(1- w 1×w 2-(1- w 1-(1- w 1×w 2×w 3×4 + 化簡得:+=,1,1,.,1211,1,12,1.1(.

13、1(n i iik n ik i i i k ji n j i jin i ij ww w w ww wt w (且互不相等(2可以看出,公式2就是容斥定理,因此我們也可以把該策略叫做容斥策略。策略2:平均值即關(guān)鍵詞的最終權(quán)重等于各個(gè)相關(guān)度的平均值。該策略的出發(fā)點(diǎn)在于平衡相關(guān)度之間的值差。(3=nj ji n w t w 1/(策略3:連乘積該策略中,關(guān)鍵詞的最終權(quán)重等于它的各個(gè)相關(guān)度的連乘積。與剩余加權(quán)和不同的是,該策略主要考慮到低相關(guān)度群體的利益,計(jì)算結(jié)果將靠近低相關(guān)度群體。(4=n j jww 1i t (容易驗(yàn)證,只要相關(guān)度在-1,1區(qū)間上,以上三種策略計(jì)算出來的權(quán)重也在-1,1區(qū)間上,并且權(quán)重與相關(guān)度的計(jì)算順序無關(guān)。得出摘要中的關(guān)鍵詞t i 的權(quán)重w(t i 之后,可以通過這些權(quán)重來計(jì)算整條結(jié)果的評估值。由于在個(gè)性化元搜索引擎中,所評估的對象為網(wǎng)頁的摘要,長度基本相當(dāng),因此,可以直接使用各個(gè)關(guān)鍵詞的權(quán)重之和來作為整條結(jié)果文本的評估值,不必考慮歸一化問題。此時(shí)計(jì)算W(D的公式如下:(5=ni it w D w 1(4.3 個(gè)性化搜索算法對于底層搜索引擎產(chǎn)生的結(jié)果文本集合R(D中的每一個(gè)文本D i ,首先按照確定好的策略來計(jì)算公式5的