基于LDA主題模型的分布式信息檢索集合選擇方法

何旭峰，陳 嶺，陳根才，錢 坤，吳 勇，王敬昌

(1. 浙江大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310027; 2. 浙江鴻程計算機(jī)系統(tǒng)有限公司，浙江 杭州 310009)

基于LDA主題模型的分布式信息檢索集合選擇方法

何旭峰1，陳 嶺1，陳根才1，錢 坤1，吳 勇2，王敬昌2

(1. 浙江大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310027; 2. 浙江鴻程計算機(jī)系統(tǒng)有限公司，浙江 杭州 310009)

該文針對分布式信息檢索時不同集合對最終檢索結(jié)果貢獻(xiàn)度有差異的現(xiàn)象，提出一種基于LDA主題模型的集合選擇方法。該方法首先使用基于查詢的采樣方法獲取各集合描述信息；其次，通過建立LDA主題模型計算查詢與文檔的主題相關(guān)度；再次，用基于關(guān)鍵詞相關(guān)度與主題相關(guān)度相結(jié)合的方法估計查詢與樣本集中文檔的綜合相關(guān)度，進(jìn)而估計查詢與各集合的相關(guān)度；最后，選擇相關(guān)度最高的M個集合進(jìn)行檢索。實驗部分采用Rm、P@n和MAP作為評價指標(biāo)，對集合選擇方法的性能進(jìn)行了驗證。實驗結(jié)果表明該方法能更準(zhǔn)確的定位到包含相關(guān)文檔多的集合，提高了檢索結(jié)果的召回率和準(zhǔn)確率。

集合選擇；分布式信息檢索；LDA

1 引言

隨著網(wǎng)絡(luò)信息的膨脹，傳統(tǒng)的集中式信息檢索在面對海量數(shù)據(jù)時往往不堪重負(fù)。分布式信息檢索系統(tǒng)[1](distributed information retrieval，DIR)將大范圍分布的異構(gòu)數(shù)據(jù)聯(lián)合起來，形成一個邏輯整體，為用戶提供強(qiáng)大的信息檢索能力，被用來解決海量數(shù)據(jù)的存儲檢索問題。DIR系統(tǒng)通常由一個代理服務(wù)器和很多檢索服務(wù)器組成。代理服務(wù)器提供統(tǒng)一的查詢接口，負(fù)責(zé)將查詢請求分發(fā)給各檢索服務(wù)器。

將查詢請求發(fā)送給所有信息集檢索將導(dǎo)致大量的網(wǎng)絡(luò)帶寬消耗和較低的系統(tǒng)響應(yīng)速度。集合選擇，就是對每個查詢請求，在代理服務(wù)器上決策出選擇哪些信息集去檢索，使得在較少的信息集合中檢索，得到盡可能多的相關(guān)文檔。

近十年來在分布式信息檢索集合選擇領(lǐng)域進(jìn)行了許多研究，這些研究大抵可分為以下三類。

(1) 將集合中包含的文檔看成一個邏輯整體，一個集合即是一個超大“文檔”(big document)，將計算查詢與集合的相關(guān)度就轉(zhuǎn)化為計算查詢與文檔相關(guān)度，按相關(guān)度的高低對各集合排序。

CORI[2]方法采用INQUERY推理網(wǎng)絡(luò)計算集合相關(guān)度，關(guān)鍵詞的權(quán)重用TF-IDF的方法計算。然后利用各集合與查詢包含的詞和詞的權(quán)重，計算各集合與查詢的相關(guān)度。Xu和Croft[3]建立語言模型并用集合和查詢詞的KL距離(Kullback-Leibler divergence)計算集合相關(guān)度，Si等人[4]基于語言模型以單個集合為語料庫，通過各個語料庫生成查詢詞的概率計算集合相關(guān)度。Yuwono等人提出了CVV方法[5]，該方法引入了線索有效性(cue validity)的概念來描述詞t對屬于集合Ci中的文檔和屬于其他集合的文檔的區(qū)分度。以上方法將各個集合中的所有文檔看成一個邏輯上的統(tǒng)一整體，從而將分布式的集合選擇問題轉(zhuǎn)化為傳統(tǒng)的查詢詞對文檔的檢索問題，然而由于虛擬文檔與真實的文檔之間實際上存在著很大的不同，如文檔長度、主題等，以上方法傾向于選擇小的、主題較少的集合，而不是大的、主題復(fù)雜、包含相關(guān)文檔更多的集合，不適用于集合大小不均勻的環(huán)境。

(2) 估算集合中包含的與查詢相關(guān)的文檔數(shù)目，以相關(guān)文檔數(shù)目的多少對各集合排序，從而選擇排名較高的集合檢索。

ReDDE[6]、CRCS[7]通過基于查詢采樣方法對各集合采樣，構(gòu)建中心樣本，通過查詢詞和被采樣文檔的信息，估計各個集合和文檔的相關(guān)度。SUSHI[8]方法在ReDDE方法及CRCS方法的基礎(chǔ)上，通過曲線擬合的方法，用中心樣本集檢索結(jié)果中各文檔的得分，估計原集合中各文檔的得分，從而得到各集合的得分。以上方法通過估計各個集合包含的與查詢相關(guān)的文檔數(shù)，按包含文檔數(shù)目從高到低對集合排序，能夠有效定位到包含相關(guān)文檔數(shù)目更多的集合。然而，對于返回topN個結(jié)果的檢索請求，與查詢最相關(guān)的文檔未必包含在相關(guān)文檔數(shù)目最多的集合，從而不會被檢索到。

(3) 計算集合與查詢的相關(guān)度得分，按得分的高低對集合排序。

SHiRE[9]將查詢檢索中心樣本的結(jié)果構(gòu)造成樹結(jié)構(gòu)，通過三種不同的遍歷該樹的次序的方法(Lex-S、Rank-S和Conn-S)，分別得到三種不同的確定樣本集檢索結(jié)果影響的指數(shù)衰減數(shù)的方法，并以此指數(shù)衰減數(shù)確定文檔對應(yīng)集合的得分。

Cetintas等人提出基于歷史查詢的集合選擇方法[10]，通過歷史查詢結(jié)果指導(dǎo)新查詢，新查詢利用歷史相似查詢的結(jié)果進(jìn)行集合選擇。劉穎等人提出了基于歷史點擊數(shù)據(jù)的集合選擇方法[11]，通過歷史查詢的用戶點擊結(jié)果，以及新查詢與歷史查詢的相似度，估計新查詢與各集合的相關(guān)度。然而由于詞語普遍存在二義性且查詢比較簡短，查詢并不總能準(zhǔn)確的表達(dá)出用戶的信息需求，導(dǎo)致一些相關(guān)度得分高的文檔和查詢并不相關(guān)。

Wauer等人[12]提出了基于本體論的方法，該方法首先選取一組特定的主題，然后將查詢與集合分別表示成關(guān)于這一組主題的向量，利用向量余弦計算相關(guān)度。但是該方法只能在特定的、主題集中的數(shù)據(jù)集下選取一組特定的主題，很難推廣到其他數(shù)據(jù)集。

針對第三類集合選擇方法存在查詢與集合間語義關(guān)系分析不準(zhǔn)確的問題，本文提出基于LDA[13]主題模型的集合選擇方法LBCS。由于LDA主題模型克服了pLSI模型的過度擬合問題，同時，相比于聚類模型，LDA主題模型通過多個主題，可對大文檔集進(jìn)行更為準(zhǔn)確的描述，因此，LDA主題模型在信息檢索中得到了廣泛的應(yīng)用[14-16]。本文嘗試在集合選擇過程中引入LDA主題模型，以實現(xiàn)對查詢和集合間語義關(guān)系的準(zhǔn)確描述；同時，通過引入查詢擴(kuò)展，避免因查詢詞稀疏而產(chǎn)生的主題漂移問題。本文的主要工作如下。

(1) 在計算查詢與樣本集文檔的相關(guān)度中，提出了基于關(guān)鍵詞相關(guān)度和基于主題相關(guān)度結(jié)合的方法來估計查詢與樣本集中各文檔的綜合相關(guān)度的計算方法。

(2) 在計算查詢與文檔的主題相關(guān)度時，充分考慮二者潛藏的語義關(guān)系，提出了基于LDA主題模型的計算方法。

(3) 在得到查詢與樣本集中文檔的綜合相關(guān)度后，考慮各文檔所屬的原集合信息，提出了計算查詢與集合相關(guān)度的方法。

(4) 設(shè)計實驗對比了本文提出的LBCS集合選擇方法和ReDDE、CRCS方法在測試集上的檢索召回率和準(zhǔn)確率，通過實驗數(shù)據(jù)說明了方法的性能。

1 LBCS集合選擇方法

1.1 分布式信息檢索架構(gòu)與LBCS方法流程

分布式信息檢索系統(tǒng)結(jié)構(gòu)如圖1所示，由一個檢索代理服務(wù)器和一組檢索服務(wù)器構(gòu)成。其中檢索服務(wù)器中存放著各自的信息集合，并獨立地檢索各自的信息集合。檢索代理服務(wù)器負(fù)責(zé)為每次的查詢選擇合適的檢索集合及檢索結(jié)果的合并。本文主要關(guān)注檢索集合的選擇問題。

圖 1 分布式檢索體系結(jié)構(gòu)

LBCS方法的總體流程圖如圖2所示，分為在線和離線兩部分，離線部分包括： (1)檢索代理服務(wù)器使用基于查詢的采樣方法[17]。對各集合采樣，對于每個查詢，各個集合返回前三個檢索結(jié)果，在檢索代理服務(wù)器上構(gòu)建樣本集；(2)檢索代理服務(wù)器對樣本集預(yù)處理，構(gòu)建倒排索引，同時對樣本集建立LDA主題模型，推導(dǎo)出主題—詞分布φ，以及文檔—主題分布θ。在線部分包括： (1)查詢檢索倒排索引，計算查詢與各文檔關(guān)鍵詞相關(guān)度(計算方法見1.3.1節(jié))； (2)通過歷史查詢得到新查詢的擴(kuò)展查詢，同時利用擴(kuò)展查詢和LDA主題模型推斷出的分布計算查詢與各文檔主題相關(guān)度(計算方法見1.3.2節(jié))； (3)得到查詢與樣本集中各文檔的綜合相關(guān)度(計算方法見1.3節(jié))，并按相關(guān)度高低對各文檔排序，然后以此計算查詢與各集合的相關(guān)度(計算方法見1.4節(jié))，并按相關(guān)度高低對各集合排序；(4)選擇排序結(jié)果最靠前的M個集合，將檢索請求發(fā)送到這些集合。

圖 2 LBCS方法的總體流程圖

在實際的系統(tǒng)中，各檢索服務(wù)器的信息集合的內(nèi)容不會一成不變，因而離線預(yù)處理部分需要定期的觸發(fā)執(zhí)行，從而不斷的更新樣本集合，為集合選擇提供依據(jù)。而基于查詢的采樣方法和基于LDA的主題建模方法需要消耗不短的時間，為了保證在進(jìn)行數(shù)據(jù)預(yù)處理時，檢索系統(tǒng)能正常提供服務(wù)，需要以離線方式運行數(shù)據(jù)預(yù)處理模塊。即假設(shè)當(dāng)前存在樣本集合Sample_1，集合選擇利用樣本集Sample_1的數(shù)據(jù)提供服務(wù)，當(dāng)觸發(fā)數(shù)據(jù)預(yù)處理模塊時，集合選擇繼續(xù)使用樣本集Sample_1的數(shù)據(jù)，直到數(shù)據(jù)預(yù)處理完成得到建模后的樣本集Sample_2，集合選擇再切換到使用樣本集Sample_2的數(shù)據(jù)，然后刪除原樣本集Sample_1。

1.2 LDA主題模型

LDA主題模型，是一種完全的概率生成模型，目的是要以一種非監(jiān)督的機(jī)器學(xué)習(xí)方法，由信息集各文檔的詞與詞頻的靜態(tài)信息學(xué)習(xí)出信息集中文檔與主題、主題與詞的概率模型，然后按照學(xué)習(xí)出的概率模型可以有效的識別語料庫或大規(guī)模文檔集中隱藏的主題信息。LDA通過基于詞袋的方法，將文檔的文本信息轉(zhuǎn)為成了形式化的數(shù)學(xué)統(tǒng)計信息。LDA生成文檔集中的各個文檔的步驟可以描述如下。

(1) 首先從文檔集中任意選取一篇未讀文檔di；

(2) 基于狄利克雷參數(shù)α，從文檔—主題分布θ中選取一個與文檔di相關(guān)的主題zk；

(3) 對于選取到的主題zk，基于參數(shù)β，從主題—詞分布φ中選取一個與該主題相關(guān)的詞tj；

(4) 重復(fù)步驟(2)、(3)直到生成了文檔di中的所有的詞，將文檔di標(biāo)記為已讀；

(5) 重復(fù)步驟(1)、(2)、(3)、(4)直到遍歷完文檔集中所有文檔。

文檔在主題空間服從多項式分布θ，主題和文檔集中的所有詞服從多項式分布φ，其中θ和φ的先驗分布是狄利克雷分布，分別帶有參數(shù)α和β。

LDA主要利用模型作者提出的變分-EM算法[13]和現(xiàn)在常用的Gibbs抽樣法[18]，來推斷其參數(shù)，其結(jié)果包括文檔—主題分布P(z|d,θ)，主題—詞分布P(w|z,φ)。本文使用Gibbs抽樣法作為LDA參數(shù)的推理方法，利用LDA推斷出的文檔—主題分布與主題—詞分布，計算查詢詞和文檔的主題相關(guān)度。

1.3 查詢與樣本集文檔相關(guān)度

定義1擴(kuò)展查詢。查詢q={t1,t2, ...,tm}，另一組查詢?yōu)閧p1,p2, ...,pn}，其中每個查詢pi都可以表示為一組詞的形式pi={tpi_1,tpi_2, ...,tpi_mi}，則查詢q基于這組查詢{p1,p2, ...,pn}的擴(kuò)展查詢q′ ={t1,t2, ...,tm,tp1_1,tp1_2, ...,tp1_m1, ...,tpn_1,tpn_2, ...,tpn_mn}，擴(kuò)展查詢q′中的每個詞的影響度為該詞所屬的原查詢與查詢q的相似度，即對于詞t∈q′且t∈pi，詞t在擴(kuò)展查詢q′中的影響度efft=sim(q|pi)，其中sim(q|pi)為計算查詢pi與查詢q相似度的函數(shù)。

定義2詞與文檔主題相關(guān)度。一個詞t與一組主題{z1,z2, …,zk}相關(guān)的概率為{Pt1,Pt2, …,Ptk}，文檔d與這組主題相關(guān)的概率為{Pd1,Pd2, …,Pdk}，那么詞t與文檔d的主題相關(guān)度，即對于主題{z1,z2, …,zk}，t和d相關(guān)的概率P(t,d) =Pt1×Pd1+Pt2×Pd2+… +Ptk×Pdk。

定義3查詢與文檔主題相關(guān)度。一個查詢q由一組詞{t1,t2, …,tj}構(gòu)成，這組詞對查詢q的影響度分別為{eff1, eff2,..., effj}，查詢與文檔的主題相關(guān)度即為查詢中的各個詞與文檔的主題相關(guān)度，以及該詞在查詢中的影響度之積的累加和，即P(q,d) =P(t1,d) ×eff1+P(t2,d) ×eff2+… +P(tj,d) ×effj。

LDA主題模型提供了一種新的基于主題的文檔建模方式，然而僅僅使用LDA主題模型本身用于檢索過于粗糙而影響檢索結(jié)果，使用LDA主題模型與傳統(tǒng)檢索方法結(jié)合有利于提高檢索準(zhǔn)確率。

文檔與查詢的得分由兩部分線性組成，一部分是基于LDA主題模型的文檔和查詢的主題相關(guān)度，另一部分是基于詞的文檔與主題的關(guān)鍵詞相關(guān)度。樣本集當(dāng)中的各文檔與查詢q的綜合相關(guān)度為式(1)所示。

Score(di,q)=λ×Scorelda(di,q)+

其中，λ取值為[0, 1]。各文檔按照相關(guān)度排序，排序的結(jié)果用于估計集合和查詢的相關(guān)度。

1.3.1 查詢與樣本集文檔關(guān)鍵詞相關(guān)度

式中,tfi為查詢q或文檔di中詞ti出現(xiàn)的頻率，idfi為逆向查詢頻率，dfi為包含ti的文檔數(shù)，|S|為樣本集文檔總數(shù)。

1.3.2 查詢與樣本集文檔主題相關(guān)度

由于查詢通常包含的詞較短，而詞的二義性普遍存在，直接利用主題—詞分布φ推斷其主題過于粗糙導(dǎo)致不夠準(zhǔn)確，從而影響檢索效果。LBCS方法使用歷史查詢詞來擴(kuò)展當(dāng)前查詢詞，利用擴(kuò)展查詢來推斷當(dāng)前查詢的主題。

由定義1可知，擴(kuò)展查詢中各詞的影響度，與兩個查詢的相似度有關(guān)。查詢q與歷史查詢p的相似度計算函數(shù)sim(p|q)需要滿足以下條件： 首先，sim(p|q)的取值范圍在[0, 1]；其次，兩個完全相同的查詢相似度為1，即sim(p|q)=1；最后，兩個查詢的相似性越高，則sim(p|q)的值越大。相似度函數(shù)計算如式(6)所示。

其中,result(q)和result(p)分別為查詢q和查詢p檢索樣本集合得到的返回結(jié)果的文檔集合。N(result(q)∩result(p))表示查詢q和查詢p檢索結(jié)果中相同文檔數(shù)，N(result(q)∪result(p))表示查詢q和查詢p檢索結(jié)果中的文檔總數(shù)(去重)。

擴(kuò)展查詢q′中的詞tj與文檔di在LDA主題模型中得出的主題{z1,z2, …,zk}上的主題相關(guān)度計算如式(7)所示。

其中，P(tj|zx,φ)為通過主題—詞分布φ可以得到查詢q中的詞tj與主題zx相關(guān)的概率。而另一個P(zx|di,θ)為通過文檔—主題分布θ得到的樣本集中的文檔di與主題zx相關(guān)的概率。

通過擴(kuò)展查詢q′中各個詞與文檔的主題相關(guān)度，可以得到擴(kuò)展查詢q′與文檔di的主題相關(guān)度，計算如式(8)所示。

其中，eff(tj)為詞tj對擴(kuò)展查詢q′的影響度。

我國從個人稅收遞延型商業(yè)養(yǎng)老保險開始試點，探索建立我國個人養(yǎng)老金體系。試點區(qū)域為上海市、福建省(含廈門市)和蘇州工業(yè)園區(qū)，為期一年。我國個人養(yǎng)老金計劃堅持賬戶多元化金融投資的方向，待試點結(jié)束后，還將根據(jù)試點情況有序擴(kuò)大參與的金融機(jī)構(gòu)和產(chǎn)品范圍，將公募基金等產(chǎn)品納入個人商業(yè)養(yǎng)老賬戶投資范圍。

將之歸一化得到原查詢q與文檔di的主題相關(guān)度，即

查詢q與文檔d的綜合相關(guān)度計算的偽代碼如算法1所示，首先，計算查詢向量q的模和文檔向量和查詢向量的內(nèi)積(第2～7行)，計算文檔向量d的模并計算查詢與文檔的關(guān)鍵詞相似度，將相似度除以相似度最大值歸一化，得到查詢與文檔關(guān)鍵詞相關(guān)度(第8～12行)。然后，通過歷史查詢生成原查詢q的擴(kuò)展查詢q′(第13行)，計算擴(kuò)展查詢q′與文檔的主題相關(guān)度，并將相似度除以相似度最大值歸一化，得到原查詢q與文檔的主題相關(guān)度(第14～19行)。最后，計算查詢q與文檔的綜合相關(guān)度(第20行)，返回各文檔的綜合相關(guān)度(第22行)。

算法1：docsScore(q)輸入：查詢語句q輸出：樣本集中文檔與查詢的綜合相關(guān)度1：FOReachdocumentdinthesamplecollection2： FOReachtermtinq3： normQ=getWeigth(q，t)×getWeigth(q，t)；4： IF(d．contains(t))Then5： dotProduct+=getWeight(d，t)×getWeight(q，t)；6： ENDIF7： ENDFOR8： FOReachtermtinq9： normD=getWeigth(d，t)×getWeigth(d，t)；10： termSim=dotProduct/sqrt(normQ+normP)；11： score＿keyword=termSim/max(termSim)；12：ENDFOR13：Expandqueryq′=Expand(q)；14：FOReachtopiczinLDAmodel15： FOReachtermt′inq′16： p＿qd+=getProbability(t′，z，φ)×getProbability(z，d，θ)×weight(t′|q′)；17： score＿lda=p＿qd/max(p＿qd)；18：ENDFOR19：ENDFOR20：scorelist[d]=λ×score＿lda+(1-λ)×score＿keyword；21：ENDFOR22：RETURNscorelist[]；

1.4 查詢與集合相關(guān)度

將樣本集里的各文檔，按照與查詢相關(guān)度從高到低排序，對于采樣自不同集合中的兩個文檔，顯然與查詢相關(guān)度更高、排名更靠前的文檔所在集合與查詢的相關(guān)度更高。同時，在樣本集的檢索結(jié)果中，屬于某集合的文檔數(shù)量越多，則該集合對查詢的貢獻(xiàn)度越大，集合相關(guān)度就越高。

檢索結(jié)果中的每個文檔對其所在集合相關(guān)度的相關(guān)度權(quán)重為：

其中，dk為樣本集中與查詢的綜合相關(guān)度排名為k的文檔，Score(dk, q)為文檔dk與查詢q的綜合相關(guān)度，|S|為樣本集的文檔總數(shù)，γ為樣本集中與查詢相關(guān)文檔的閾值，表示與查詢相關(guān)的有效文檔數(shù)量，參數(shù)ratio表示檢索結(jié)果的相關(guān)文檔數(shù)占樣本集文檔總數(shù)的比例。

集合的大小也是評價集合相關(guān)度的重要因素。假設(shè)兩個集合在樣本集top γ個檢索結(jié)果中擁有相同數(shù)量文檔，由于基于查詢的采樣每個集合返回的被采樣文檔的總數(shù)目幾乎相同，那么顯然更大的集合可能包含有更多的相關(guān)文檔。綜合考慮上述因素，LBCS按如下的方式估計集合Ci與查詢的相關(guān)度，即

其中，|Ci|為集合Ci包含的文檔總數(shù)，Sci為樣本集中采樣自Ci的文檔，|Sci|為樣本集中采樣自Ci的文檔總數(shù)。

查詢與集合相關(guān)度計算的偽代碼如算法2所示，通過算法1得到樣本集中文檔與查詢的綜合相關(guān)度(第1行)，對樣本集中文檔按其與查詢的綜合相關(guān)度從高到低排序得到排序列表(第2行)。選擇排名大于閾值γ的文檔(第4行)，計算該文檔對其所在集合與查詢的相關(guān)度的影響(第5行)，計算集合與查詢的相關(guān)度(第6、7行)，并返回各集合的相關(guān)度的得分(第9行)。

算法2：colRelevance(q)輸入：查詢語句q輸出：各集合與查詢的綜合相關(guān)度1： scorelist=docsScore(q)；2： ranklist=Rank(scorelist)；3： FOReachdocumentdrankedkinranklist4： IF((k<γ)ANDdisincollectioncThen5： R＿d=scorelist[d]×sqrt(1-k/γ)；6： collist[c]+=R＿d×NumOfDocs[c]/NumOfDoc[c＿sample]；7： ENDIF8： ENDFOR9： RETURNcollist[]；

2 實驗

2.1 測試集

實驗使用的測試集為TREC數(shù)據(jù)集The ClueWeb09 Dataset Category B，包含有五千多萬個英文網(wǎng)頁，壓縮后大小為229.9 GB。實驗中，數(shù)據(jù)集被隨機(jī)劃分成100個大小不等的集合，這些集合中包含的文檔數(shù)最多為123.3萬篇，最少為14.3萬篇，平均為50.2萬篇，壓縮后集合大小，最大為 6.25 GB，最小為821 MB，平均為2.29 GB。

TREC給出了基于該測試集的50個真實查詢話題(TREC topic1-50)，以及每個查詢所對應(yīng)的相關(guān)文檔。

2.2 評價指標(biāo)

Rm(召回率)、P@n(前n個檢索結(jié)果的準(zhǔn)確率)及平均準(zhǔn)確率MAP通常被用作集合選擇方法的評價指標(biāo)。

其中，Ei為測試的集合選擇方法選擇的第i個集合中包含的相關(guān)文檔的總數(shù)，Bi為理想的集合選擇方法選擇的第i個集合(理想的集合選擇方法按集合中相關(guān)文檔總數(shù)從多到少排序)中包含的相關(guān)文檔的總數(shù)，Rm的值越大，說明被測的集合選擇方法選出的集合序列越接近理想的集合排序。P@n表示在集合選擇方法選出的集合中檢索，返回前n個結(jié)果的準(zhǔn)確度，P@n的值越大，則檢索的準(zhǔn)確度越高。本文中，Rm與P@n都是50個查詢的平均值。

2.3 實驗設(shè)置

2.3.1LBCS參數(shù)設(shè)置

本文的LBCS方法包含兩個參數(shù)： λ和ratio。其中，λ為主題相關(guān)度得分在綜合相關(guān)度得分的權(quán)重，λ越大表示主題相關(guān)度得分在綜合相關(guān)度得分中影響更大。實驗中設(shè)置λ=0.3，后面的實驗結(jié)果也證明了λ取值0.3將獲得不錯的檢索效果。參數(shù)ratio表示檢索結(jié)果的相關(guān)文檔數(shù)占樣本集(所有集合)文檔總數(shù)的比例，ratio過大將會引入許多不相關(guān)文檔，ratio過小可能會過濾掉許多相關(guān)文檔。Callan指出[6]在基于查詢的采樣中，樣本集中相關(guān)文檔數(shù)占樣本集文檔總數(shù)的比例取值為0.002～0.005。實驗中設(shè)置ratio=0.003。

2.3.2LDA參數(shù)設(shè)置

在通過基于查詢的采樣方法對各集合采樣構(gòu)成樣本集后，需要對樣本集中的文檔建立LDA主題模型。按照研究中的通常設(shè)定[16]，設(shè)置α=50/K，β=0.01，實驗顯示α和β的值對最終檢索效果的影響很小。另外需要確定的參數(shù)是LDA的迭代次數(shù)Iterations和主題數(shù)目K。采用Gibbs抽樣法推斷LDA的分布，迭代次數(shù)Iterations越大，推斷出的分布越接近真實分布，但同時需要的時間也更長。圖3顯示了當(dāng)K=400，M=5，n=10時，Iterations對檢索結(jié)果準(zhǔn)確度的影響，當(dāng)Iterations小于170時，檢索結(jié)果的準(zhǔn)確率隨著迭代次數(shù)Iterations的增加而顯著的提高，而當(dāng)Iterations大于170時，檢索結(jié)果的準(zhǔn)確率趨于平穩(wěn)，本文選取Iterations=200。

圖 3 當(dāng)K=400，M=5，n=10時，不同Iterations值對檢索結(jié)果準(zhǔn)確度的影響

選取合適的主題數(shù)目對建立的主題模型的優(yōu)劣同樣有著重要的影響。主題數(shù)過小不能充分的反映文檔集合的主題，主題數(shù)過多建模時耗時越長。圖4顯示了當(dāng)M=5，n=10時，主題數(shù)的多少對檢索結(jié)果準(zhǔn)確度的影響，當(dāng)K到達(dá)一定數(shù)目時檢索結(jié)果的準(zhǔn)確率趨于平穩(wěn)，實驗證明取K=400能得到很好的檢索效果。

圖4 當(dāng)M=5，n=10時，不同主題數(shù)對檢索結(jié)果準(zhǔn)確度的影響

2.3.3 基準(zhǔn)方法

ReDDE方法作為基準(zhǔn)方法廣泛地用于集合選擇方法的研究，因而被本文選作基準(zhǔn)的對比方法之一。由于CRCS(e)方法的效果顯著得好于CRCS(l)[7]，因而選擇CRCS(e)方法作為基準(zhǔn)的對比方法之一。在對比方法中，參數(shù)均按照原文中的設(shè)置，ReDDE方法的參數(shù)相關(guān)文檔占樣本集文檔的比例取0.003，CRCS(e)方法的兩個參數(shù)分別取1.2和2.8。

2.3.4 采樣參數(shù)設(shè)置

實驗采用基于查詢的采樣方法[18]獲取各集合的描述信息。從查詢?nèi)罩倦S機(jī)選取1個查詢作為初始查詢詞；每輪檢索中，每個集合返回其檢索結(jié)果的前3個文檔加入到樣本集合，并從樣本集文檔中隨機(jī)抽取1個關(guān)鍵詞作為下一輪檢索的關(guān)鍵詞。當(dāng)樣本集中的文檔數(shù)量大于或等于所有集合總文檔數(shù)的3%時，即停止采樣。

2.3.5 合并策略

實驗中采用兩次往返的查詢方式的檢索合并策略。第一次統(tǒng)計全局信息；第二次將查詢與全局信息發(fā)送到要檢索的集合，以計算出文檔的全局評分，使各文檔的評分具有可比性。對于topn的查詢，被檢索的集合返回n個檢索結(jié)果，檢索代理服務(wù)器合并各集合返回的結(jié)果。

2.4 實驗結(jié)果與分析

圖5顯示當(dāng)分別選擇1～10個集合時，ReDDE、CRCS(e)和LBCS三種集合選擇方法在這50個查詢下的平均召回率Rm值。在分別選擇1～10個集合時，LBCS方法在每個集合數(shù)的召回率的值都高于ReDDE方法和CRCS(e)方法，較ReDDE方法和CRCS(e)方法分別平均提高14.2%和19.9%，當(dāng)選擇的集合數(shù)增大的時候，LBCS的Rm值增長更快。

圖 5 三種集合選擇方法的召回率

實驗結(jié)果表明，LBCS相較于ReDDE、CRCS(e)有更高的召回率，說明基于LDA主題模型的集合選擇方法能有效地挖掘出查詢和集合的語義層面的關(guān)系，使得LBCS能更準(zhǔn)確地選擇到包含更多相關(guān)文檔的集合。

表1～表4顯示了ReDDE、CRCS(e)和LBCS三種集合選擇方法返回n個檢索結(jié)果的準(zhǔn)確率 P@n 結(jié)果對比，當(dāng)三種集合選擇方法分別選擇相關(guān)度最高的2，5，7，10個集合進(jìn)行檢索時，50個查詢分別返回5，10，15，20，30，40，50個結(jié)果的平均準(zhǔn)確率。當(dāng)選擇2，5，7，10個集合進(jìn)行檢索時，LBCS較ReDDE準(zhǔn)確率分別平均提高7.8%，8.8%，5.6%，4.8%，LBCS較CRCS(e)準(zhǔn)確率分別平均提高8.7%，10.5%，6.8%，7.0%。結(jié)果表明，LBCS相比于ReDDE和CRCS(e)在選擇相同集合數(shù)目時有更高的準(zhǔn)確率，說明LBCS相比于ReDDE和CRCS(e)能夠選擇到與查詢更相關(guān)的集合。

表1 選擇2個集合時兩個方法的準(zhǔn)確率

表2 選擇5個集合時兩個方法的準(zhǔn)確率

表 3 選擇7個集合時兩個方法的準(zhǔn)確率

表 4 選擇10個集合時兩個方法的準(zhǔn)確率

另外可以看到，當(dāng)返回相同數(shù)量的檢索結(jié)果時，選擇的集合數(shù)目越多，三種方法的準(zhǔn)確率越高。當(dāng)選擇同樣數(shù)目的集合時，返回的結(jié)果數(shù)n值越大，即返回的檢索結(jié)果越多，三種方法的準(zhǔn)確率越低，說明隨著返回的檢索結(jié)果數(shù)目變大，更多的不相關(guān)文檔會混入其中，并且當(dāng)選擇的集合越少時，隨著返回結(jié)果數(shù)的增加，混入的不相關(guān)文檔比例更大。

圖6顯示了對于50個查詢(TREC topic1-50)，CRCS(e)、REDDE和LBCS分別在選擇2，5，7，10個集合時前10個結(jié)果的MAP值。當(dāng)選擇2，5，7，10個集合進(jìn)行檢索時，LBCS較ReDDE的MAP值分別平均提高9.2%，5.1%，3.7%，2.9%，LBCS較CRCS(e)的MAP值分別平均提高8.2%，7.7%，4.7%，3.8%。結(jié)果表明，LBCS相比于ReDDE和CRCS(e)在選擇相同集合數(shù)目時有更高的MAP值，說明LBCS相比于ReDDE和CRCS(e)在得到相同的召回率時，檢索結(jié)果的準(zhǔn)確度更高。

圖 6 三種集合選擇方法的MAP

3 結(jié)語

集合選擇是分布式信息檢索系統(tǒng)中的重要環(huán)節(jié)，可有效減少網(wǎng)絡(luò)帶寬消耗，減少檢索時的計算開銷，提高分布式信息檢索系統(tǒng)的效率。本文提出基于LDA主題模型的集合選擇方法LBCS，引入LDA方法對樣本集建立主題模型。實驗結(jié)果表明，LDA主題模型能有效挖掘查詢與集合潛在的語義關(guān)系，從而選擇到與查詢更相關(guān)的集合，有效提高了最終檢索結(jié)果的準(zhǔn)確率及召回率。

本集合選擇方法主要以提高檢索準(zhǔn)確率與召回率為目標(biāo)設(shè)計的，然而在實際應(yīng)用中，可能需要考慮更加復(fù)雜的因素，如檢索服務(wù)器的吞吐率、負(fù)載、響應(yīng)時間、各檢索服務(wù)器的檢索策略等。若能充分考慮DIR系統(tǒng)的性能及檢索的準(zhǔn)確度與召回率，建立統(tǒng)一的集合選擇模型將是一個很好的研究方向。

[1] Callan J. Distributed information retrieval. Croft W B. Advances in information retrieval[M]. USA: Kluwer Academic Publishes, 2000: 127-150.

[2] Callan J P, Lu Z, Croft W B. Searching distributed collections with inference network[C]// Proceedings of the 18th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 1995: 21-28.

[3] Xu J, Croft W B. Cluster-based language models for distributed retrieval[C]// Proceedings of the 22nd International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 1999: 254-261.

[4] Si L, Jin R, Allan J. et al. A language modeling framework for resource selection and results merging[C]// Proceeding of ACM Conference on Information and Knowledge Management. McLean, Virginia, USA, 2002: 391-397.

[5] Yuwono B, Lee D L. Server ranking for distributed text retrieval systems on the Internet[C]// Proceedings of International Conference on Database Systems for Advanced Applications. 1997, 97: 41-49.

[6] Si L, Callan J. Relevant document distribution estimation method for resource selection[C]// Proceedings of the 26th International ACM SIGIR Conference on Research and Development in Informaion Retrieval. ACM, 2003: 298-305.

[7] Shokouhi M. Central-rank-based collection selection in uncooperative distributed information retrieval[M]. Advances in Information Retrieval. Springer Berlin Heidelberg, 2007: 160-172.

[8] Thomas P, Shokouhi M. SUSHI: Scoring scaled samples for server selection[C]// Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2009: 419-426.

[9] Kulkarni A, Tigelaar A S, Hiemstra D, et al. Shard ranking and cutoff estimation for topically partitioned collections[C]// Proceedings of the 21st ACM International Conference on Information and Knowledge Management. ACM, 2012: 555-564.

[10] Cetintas S, Si L, Yuan H. Learning from past queries for resource selection[C]// Proceedings of the 18th ACM Conference on Information and Knowledge Management. ACM, 2009: 1867-1870.

[11] 劉穎, 陳嶺, 陳根才. 基于歷史點擊數(shù)據(jù)的集合選擇方法[J]. 浙江大學(xué)學(xué)報 (工學(xué)版), 2013, 47(1): 23-28.

[12] Wauer M, Schuster D, Schill A. Integrating explicit semantic analysis for ontology-based resource selection[C]// Proceedings of the 13th International Conference on Information Integration and Web-based Applications and Services. ACM, 2011: 519-522.

[13] Blei D M, Ng A Y, Jordan M I. Latent dirichlet allocation[J]. the Journal of Machine Learning Research, 2003, 3: 993-1022.

[14] 張俊林, 孫樂, 孫玉芳. 基于主題語言模型的中文信息檢索系統(tǒng)研究[J]. 中文信息學(xué)報, 2005, 19(3): 14-20.

[15] 劉振鹿, 王大玲, 馮時,等. 一種基于LDA的潛在語義區(qū)劃分及Web文檔聚類算法[J]. 中文信息學(xué)報, 2011, 25(1): 60-65.

[16] Wei X, Croft W B. LDA-based document models for ad-hoc retrieval[C]// Proceedings of the 29th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2006: 178-185.

[17] Callan J, Connell M. Query-based sampling of text databases[J]. ACM Transactions on Information Systems, 2001, 19(2): 97-130.

[18] Porteous I, Newman D, Ihler A, et al. Fast collapsed gibbs sampling for latent dirichlet allocation[C]// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2008: 569-577.

ALDATopicModelBasedCollectionSelectionMethodforDistributedInformationRetrieval

HE Xufeng1, CHEN Ling1, CHEN Gencai1,QIAN Kun1,WU Yong2, WANG Jingchang2

(1. College of Computer Science and Technology, Zhejiang University, Hangzhou, Zhejiang 310027, China; 2. ZheJiang Hongcheng Computer System Co.,Ltd., Hangzhou, Zhejiang 310009, China)

Considering that different collections have different contributions to the final search results, a LDA topic model based collection selection method is proposed for distributed information retrieval. Firstly, the method acquires information about the representation of each collection by query-based sampling. Secondly, a method using the LDA topic model is proposed to estimate the relevance between the query and a document. Thirdly, a method based on both term and topic is proposed to estimate the relevance between the query and the sample documents, by which the relevance between the query and collections can be estimated. Finally, M collections with the highest relevance are selected for retrieving. Experiment results demonstrates that the proposed method can improve the accuracy and recall of search results.

collection selection; distributed information retrieval; LDA

何旭峰(1989—)，碩士研究生，主要研究領(lǐng)域為信息檢索。

陳嶺(1977—),通信作者，博士，副教授，主要研究領(lǐng)域為普適計算、數(shù)據(jù)庫。

陳根才(1950—)，教授，主要研究領(lǐng)域為人工智能、數(shù)據(jù)庫。

1003-0077(2017)03-0125-09

2016-02-13定稿日期： 2016-05-26

“核高基”國家科技重大專項(2010ZX01042-002-003)；國家自然科學(xué)基金(60703040，61332017)；浙江省重大科技專項(2011C13042，2013C01046)；中國工程科技知識中心(CKCEST-2014-1-5)

TP391

： A