基于主題模型的資源選擇算法*

董守斌 謝一帆 袁華 陳建豪

(華南理工大學(xué) 計算機科學(xué)與工程學(xué)院∥廣東省計算機網(wǎng)絡(luò)重點實驗室， 廣東 廣州 510006)

基于主題模型的資源選擇算法*

董守斌 謝一帆 袁華?陳建豪

(華南理工大學(xué) 計算機科學(xué)與工程學(xué)院∥廣東省計算機網(wǎng)絡(luò)重點實驗室， 廣東 廣州 510006)

在具有多個真實搜索引擎的聯(lián)邦檢索環(huán)境下，基于小文檔的資源選擇算法由于難以估計每個搜索引擎的真實網(wǎng)頁數(shù)量，因此準確率較低.針對這個問題，文中提出了基于主題模型的資源庫描述方法，利用LDA主體模型獲取每個資源庫的描述詞；在此基礎(chǔ)上提出新的資源選擇算法，結(jié)合垂直領(lǐng)域權(quán)重和詞向量計算資源庫和查詢請求之間的相關(guān)度，并根據(jù)相關(guān)度大小獲取最終資源選擇結(jié)果.實驗結(jié)果表明，基于主題模型的資源選擇算法能很好地提高資源選擇效果，可有效應(yīng)用于分布式搜索引擎的聯(lián)邦檢索環(huán)境.

分布式檢索；資源選擇；主題模型；垂直領(lǐng)域；詞向量

資源選擇是典型分布式檢索系統(tǒng)需要解決的主要問題之一[1].當(dāng)給定一個查詢和一個文檔資源庫集合，資源選擇意在判斷和選擇出與該查詢相關(guān)的資源庫.資源選擇方法可用于不同的信息檢索應(yīng)用，如聚合搜索、桌面搜索、聯(lián)邦檢索等.

早期的資源選擇算法將每個資源庫看成一篇大文檔，然后使用標(biāo)準的信息檢索模型計算出查詢與資源庫的相關(guān)性，如CORI方法[2]和CVV方法[3]等.這種將資源庫看做大文檔的方法消除了資源庫中文檔與文檔的差異性，一定程度上影響了資源選擇的效果.而ReDDE[4]、ReDDE.Top[5]、Approx.CiSS[6]、CRCS[7]、SUSHI[8]和GAVG[9]等類ReDDE方法則是利用建立的資源庫的中央索引庫，根據(jù)查詢獲得的索引庫結(jié)果，使用一定的方法估計資源庫中包含的相關(guān)文檔的數(shù)目，從而獲得與查詢相關(guān)的資源庫列表.但這一類方法需要先對資源庫進行抽樣，利用抽樣文檔建立中央索引庫.而在實際的分布式檢索環(huán)境下，這些資源庫真實的網(wǎng)頁數(shù)量是難以準確估計的.此外，某些分布式檢索環(huán)境會要求每個查詢至少選擇出若干資源庫數(shù)目，而由于此類方法需要通過查詢中央索引庫獲取資源庫列表，因此有可能出現(xiàn)資源庫數(shù)量不滿足要求的情況.陳志敏[10]提出了結(jié)合資源庫對應(yīng)網(wǎng)站的PageRank[11]、市場份額和部分日志統(tǒng)計信息來衡量資源庫重要性，將其反饋到查詢與資源庫的相關(guān)性評分；該方法取得一定效果，但核心部分仍為類ReDDE方法.

在現(xiàn)代分布式檢索系統(tǒng)中，各個資源庫根據(jù)其自身內(nèi)容的不同分屬于不同的主題領(lǐng)域，稱之為垂直領(lǐng)域.每個垂直領(lǐng)域包含相似類型的信息和一系列與該垂直領(lǐng)域相關(guān)的資源庫.如垂直領(lǐng)域“software”包含了軟件領(lǐng)域的相關(guān)網(wǎng)頁和軟件類型的資源庫[12]，如GitHub和SourceForge等.

為解決傳統(tǒng)類ReDDE方法的不足，文中提出了一種全新的資源選擇算法.該方法與傳統(tǒng)的類ReDDE方法不同點在于，不需要構(gòu)建中央索引庫和估計原始資源庫的網(wǎng)頁數(shù)量，僅基于資源庫和查詢詞自身信息進行研究.該算法需要解決兩個問題：一是如何對資源庫進行描述；二是如何判斷資源庫于查詢請求之間的相關(guān)度.針對第1個問題，文中提出了基于主題模型的資源庫描述方法；針對第2個問題，文中提出了一種新的資源選擇算法框架，在垂直領(lǐng)域權(quán)重和資源庫描述的基礎(chǔ)上，結(jié)合詞向量技術(shù)計算資源庫與查詢請求之間的相關(guān)度.

1 基于主題模型的資源選擇算法

1.1 基于主題模型的資源庫描述

主題模型能夠刻畫一篇文檔的潛在主題，并得出與主題關(guān)系最緊密的相關(guān)詞匯和相關(guān)度.一個資源庫擁有內(nèi)容紛繁多樣的海量文檔，因此，可以認為資源庫具有不同的主題分布.如果將資源庫看做一篇大文檔，同樣可以使用主題模型來刻畫出資源庫的主題分布以及主題關(guān)鍵詞匯分布.用資源庫的主題分布下各個主題的關(guān)鍵詞匯來作為該資源庫的描述，既能夠體現(xiàn)資源庫主題的多樣性，也能夠體現(xiàn)資源庫描述的準確性.文中提出基于LDA[13]主題模型的資源庫描述方法，包括以下兩個步驟：

(1)對每個資源庫進行LDA主題模型的訓(xùn)練，得出資源庫的k個主題以及主題-關(guān)鍵詞分布；

(2)選取k個主題下各n個關(guān)鍵詞匯作為資源庫的關(guān)鍵詞描述.

圖1為資源庫訓(xùn)練LDA模型示意圖.該方法首先對資源庫內(nèi)所有的文檔進行分詞、去除停用詞等預(yù)處理，將預(yù)處理后的文檔集作為LDA模型的訓(xùn)練數(shù)據(jù)輸入.LDA模型通過吉布斯采樣[14]方法對資源庫相關(guān)信息進行采樣訓(xùn)練，最終輸出該資源庫的主題分布以及主題對應(yīng)關(guān)鍵詞列表以及這些關(guān)鍵詞與主題之間的相似度大小，主題數(shù)同詞匯數(shù)可事先設(shè)定.在LDA訓(xùn)練后，選取每個主題排名前n的關(guān)鍵詞匯作為該資源庫的描述信息.獲取的資源描述信息可用于后續(xù)資源選擇算法的計算.

1.2 資源選擇算法RS_LDA

對基于垂直領(lǐng)域的分布式檢索系統(tǒng)的資源選擇來說，資源庫與查詢詞之間的相關(guān)性不僅取決于資源庫描述信息同查詢詞之間的相關(guān)性，還和其所屬的垂直領(lǐng)域和查詢詞之間的相關(guān)性有關(guān).若對一個資源庫來說，它所屬的垂直領(lǐng)域若屬于與查詢詞相關(guān)的垂直領(lǐng)域， 那么該資源庫與該查詢詞相關(guān)聯(lián)的可能性將增大，因此在計算資源庫分數(shù)時，要考慮垂直領(lǐng)域的權(quán)重的影響.

圖1 基于LDA主題模型的資源描述

若一個詞項越頻繁出現(xiàn)在一個垂直領(lǐng)域中，那么它越能夠作為該垂直領(lǐng)域的代表性詞項，借鑒頻繁詞項排序FTR模型[15]，用一個詞項在垂直領(lǐng)域的詞匯排序表中的排序位置來判斷兩者之間的相似度.因此文中采用詞權(quán)重TF- IDF[16]方法衡量詞匯的重要性，并以該值對每個垂直領(lǐng)域中的所有詞匯進行排序，形成每個垂直領(lǐng)域的特有詞匯排序表，然后利用詞向量Word2Vec[17]方法獲取查詢詞的擴展詞匯，用查詢詞的擴展詞匯在垂直領(lǐng)域的詞匯排序表中的排序位置來判斷兩者之間的相似度.在此基礎(chǔ)上計算資源庫對應(yīng)的垂直領(lǐng)域權(quán)重：若該資源庫屬于與查詢詞相關(guān)的垂直領(lǐng)域，那么該資源庫和查詢詞的相關(guān)性更大，則賦予該資源庫更高的權(quán)重.

基于上述問題的討論，文中提出了基于LDA資源描述的資源選擇算法RS_LDA，具體包括以下幾個步驟：

(1)通過詞向量Word2Vec方法獲取查詢詞的擴展詞匯集合Q={qk,k=1,2,…,C},C是擴展詞個數(shù)，用rqk表示某擴展詞匯qk在垂直領(lǐng)域Vi的詞匯排序表中所在的排序位置，則可計算擴展詞匯qk的權(quán)重wqk：

(1)

(2)設(shè)資源庫Ri(i∈{1,2,…,F})的所屬垂直領(lǐng)域為Vi，F(xiàn)是資源庫個數(shù).計算所有的查詢詞擴展詞匯所在位置并求和，作為查詢詞q與垂直領(lǐng)域Vi的相似性分數(shù)：

(2)

(3)通過LDA模型訓(xùn)練出資源庫Ri的主題分布Topict,t∈{1,2,…，G}，以及主題描述詞匯Verbaltj，j∈{1,2,…，H}，G是主題數(shù)，H表示每個主題下選取的關(guān)鍵詞匯個數(shù).計算詞匯vtj權(quán)重：

(3)

式中，rvtj表示詞匯vtj的排名.

(4)

式中的w2v_sim(qk,vtj)指用Word2Vec計算的擴展詞匯qk和資源庫主題關(guān)鍵詞匯vtj的相似值.

(5)

RS_LDA資源選擇算法的具體描述如下.

輸入：查詢詞q，待排序的資源庫列表，

ListR={Ri,i=1,2,…，C}

輸出：資源選擇結(jié)果列表

∥初始化所有資源庫的垂直領(lǐng)域權(quán)重

Q={qk,k=1,2,…，C}←Word2Vec(q)

∥查詢詞擴展

forqkinQ

wqk←根據(jù)式(1)計算擴展詞匯權(quán)重

end for

forRiin ListR

sim(q,Vi)←根據(jù)式(2)計算查詢與垂直領(lǐng)域的相似度

if sim(q,Vi)大于閾值T

end if

end for

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

2.1 實驗設(shè)置

實驗使用的數(shù)據(jù)集為FedWeb2014數(shù)據(jù)集[18]，該數(shù)據(jù)集是從149個真實的搜索引擎通過抽樣搜索獲取的.實驗對75個查詢詞進行資源庫選擇實驗，待選擇的資源庫數(shù)即為149個.每個資源庫中包含大致40 000個網(wǎng)頁，這些網(wǎng)頁摘要信息保存在FW14- sample- search數(shù)據(jù)集合中，可用于訓(xùn)練資源庫的LDA模型和Word2Vec模型.數(shù)據(jù)集提供資源庫與24個垂直領(lǐng)域之間的映射關(guān)系.實驗先針對每個資源庫的網(wǎng)頁摘要進行預(yù)處理并作為LDA模型訓(xùn)練的輸入數(shù)據(jù)集，獲得每個資源庫的LDA主題-詞匯分布及TF-IDF詞匯排序表.實驗同樣使用Word2Vec模型對輸入的查詢詞進行擴展，選取C個查詢擴展詞并記錄其與查詢詞之間的相似度值.

2.2 RS_LDA資源選擇算法參數(shù)實驗

2.2.1 不同主題數(shù)和不同關(guān)鍵詞匯數(shù)下的實驗結(jié)果

對于RS_LDA資源選擇算法而言，LDA模型選取不同的主題個數(shù)和不同的主題關(guān)鍵詞匯，都會對結(jié)果產(chǎn)生不一樣的影響.本實驗針對選取不同主題個數(shù)G和不同主題詞匯數(shù)H的情況進行實驗，使用nDCG@20的值作為測評指標(biāo)，并取LDA主題個數(shù)G的區(qū)間在{2，4，6，8，…，18，20}內(nèi)，LDA主題關(guān)鍵詞匯H的范圍在{5，10，15，20，25，30，35}內(nèi)，同時固定其他參數(shù)值：a為1.7，C為10，權(quán)重因子α值和β值均為1，閾值T設(shè)置為0.8.實驗結(jié)果如圖2所示，橫坐標(biāo)為不同主題數(shù)G，縱坐標(biāo)為nDCG@20值，RS_LDA@H曲線表示當(dāng)H取不同值的時候，資源選擇的效果變化趨勢.

由圖2可見，對LDA詞匯數(shù)H為20、25、30、35的曲線來說，在主題數(shù)由2升至8或10的范圍內(nèi)，隨著主題數(shù)的增加，曲線不斷上升；當(dāng)主題數(shù)大于10時，曲線隨著主題數(shù)的增加不斷下降.而對于LDA詞匯數(shù)為5、10、15的曲線來說，隨著主題數(shù)的增加，曲線趨勢在緩慢增長中.因此可以推斷，資源選擇算法RS_LDA的準確率或許和主題數(shù)G與各主題下關(guān)鍵詞匯數(shù)H的乘積有關(guān)，即選取的總LDA詞匯個數(shù)相關(guān).同由圖2可知，最大值出現(xiàn)在主題數(shù)為8、LDA詞匯數(shù)為30的情況下，在該參數(shù)值下資源選擇算法RS_LDA獲得最高效率，為 0.524 4.

圖2 不同主題數(shù)G和關(guān)鍵詞數(shù)H下的效果對比

2.2.2 不同權(quán)重參數(shù)下的實驗結(jié)果

資源選擇算法中有兩個重要的權(quán)重參數(shù)α和β.本實驗在{0.1，0.2，0.3， …， 0.9，1.0}范圍內(nèi)設(shè)置α和β，并使用nDCG@20作為測評指標(biāo)，觀察在不同α、β參數(shù)值設(shè)置下，RS_LDA算法準確率的變化情況.該實驗固定其他參數(shù)值：a為1.7，H取值30，G取值8，C取值10，閾值T設(shè)置為0.8.表1為RS_LDA算法在不同參數(shù)設(shè)置下的nDCG@20值.由表1可知，當(dāng)α、β取值分別為0.7、0.8時，RS_LDA取得最好效果(為0.540).由此可知，RS_LDA算法的最終分數(shù)融合部分，略青睞于LDA權(quán)重所帶來的準確度信息.

表1 在不同權(quán)重參數(shù)α和β下的nDCG@20值

1)該數(shù)值是指β的數(shù)值.

2.2.3 不同擴展詞匯數(shù)下的實驗結(jié)果

查詢詞的擴展詞匯個數(shù)C也是影響實驗結(jié)果的一個因素.本實驗研究不同C值對資源選擇的影響情況.固定其他參數(shù)的取值:a為1.7，H為30，G為8，資源選擇算法的α和β的比值分別設(shè)置為0.7、0.8.將C的取值范圍固定在{5，10，15，20，25，30，35，40}內(nèi)，觀測最終結(jié)果的變化情況.本實驗同樣使用nDCG@20作為評價指標(biāo).實驗結(jié)果如圖3所示.

圖3 不同C值下資源選擇算法效果對比

Fig.3 Performance comparison in resource selection for diffe-rentC

由圖3可見，隨著C取值的不斷增大，資源選擇算法RS_LDA的nDCG@20值不斷下降，當(dāng)C值取5時，資源選擇算法的效果最好.因此，對于資源選擇算法來說，C值取5時，獲得最佳效果.

2.3 對比實驗與分析

文中選取了CRCS(e)資源選擇算法[10]的最優(yōu)結(jié)果，以及TREC FedWeb2014資源選擇任務(wù)中ICTNET團隊[14]提出的ICTNETRS這一最優(yōu)資源選擇算的結(jié)果與RS_LDA資源選擇算法的資源選擇效果進行比較.結(jié)果如表2所示.表中，nP為歸一化查準率，@5表示取前5個排序結(jié)果進行統(tǒng)計.

可以看出，文中提出的資源選擇算法在nDCG@ 20值、nDCG@10值和nP@5上均超過了其他算法，

表2 不同資源選擇算法的對比

包括最優(yōu)算法ICTNETRS.

由于LDA主題模型的訓(xùn)練以及Word2Vec的詞向量訓(xùn)練均可以離線進行，在線計算開銷是比較小的.因此可說明文中提出的資源選擇算法在分布式檢索資源選擇中的可行性、高效性和準確性.

3 結(jié)語

傳統(tǒng)的類ReDDE方法由于需要利用中央索引庫進行資源庫抽樣估計，在資源庫真實網(wǎng)頁數(shù)目估計和待補充資源庫問題上會帶來一定的準確度損失.對此，文中提出了基于主題模型的資源選擇算法.該算法通過LDA主題模型的離線訓(xùn)練得出資源庫描述，并結(jié)合詞向量技術(shù)進行資源選擇.通過實驗證明，基于主題模型的資源選擇算法能夠有效提高資源選擇的準確率，與以往算法比較有較大的性能提升，是準確有效的.下一步工作是將資源選擇算法應(yīng)用于分布式檢索系統(tǒng)中，基于資源選擇算法評估資源查詢的有效性，以提高分布式檢索結(jié)果融合的效果.

[1] NGUYEN D,DEMEESTER T,TRIESCHNIGG D,et al.Federated search in the wild [C]∥Proceedings of CIKM’12.Maui:ACM, 2012.

[2] CALLAN J P， LU Z， CROFT W B. Searching distributed collections with inference networks [C]∥Proceedings of International ACM SIGIR Conference on Research and Development in Information Retrieval. New York：ACM， 1995：21- 28．

[3] YUWONO B， LEE D L. Server Ranking for Distributed Text Retrieval Systems on the Internet [C]∥Proceedings of 5th International Conference on Database System for Advanced Applications.Melbourne:Wohd Scientific Press,1997:41- 49.

[4] SI L， CALLAN J. Relevant document distribution estimation method for resource selection [C]∥Proceedings of the 26thInternational ACM SIGIR conference on Research and Development in Information Retrieval.Toronto:ACM， 2003: 298- 305.

[5] ARGUELLO J， CALLAN J， DIAZ F. Classification- based resource selection [C]∥Proceedings of the 18th ACM conference on Information and Knowledge Management. Hong Kong：ACM， 2009：1277- 1286．

[6] MARKOV I， CRESTANI F. Theoretical， qualitative， and quantitative analyses of small- document approaches to resource selection [J]. ACM Transactions on Information Systems (TOIS)， 2014， 32(2)：9．

[7] SHOKOUHI M. Central- rank- based collection selection in uncooperative distributed information retrieval [M]. Berlin， Heidelberg：Springer，2007．

[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.Boston:ACM,2009:419- 426.

[9] Arguello J.Federated search for heterogeneous environment [D].Pittsbargh:Carregie Mellon University,2011.

[10] 陳志敏. 聯(lián)邦檢索系統(tǒng)的關(guān)鍵技術(shù)研究與實現(xiàn) [D]. 廣州：華南理工大學(xué)， 2015．

[11] PAGE L， BRIN S，MOTWANI R, et al. The PageRank citation ranking：Bringing order to the web [R].Stanford：Stanford InfoLab， 1999.

[12] THOMAS D， DOLF T， DONG N， et al. Overview of the TREC 2014 federated web search track [C]∥Proceed-ings of the 23rd Text Retrieval Conference (TREC).Maryland：National Institute of Standards and Technology，2014:1- 11．

[13] BLEI D M，NG A Y，JORDAN M I.Latent dirichlet allocation [J]. Journal of Machine Learning Research， 2003， 3:993- 1022．

[14] STUART G，DONALD G. Stochastic relaxation，Gibbs distributions， and the Bayesian restoration of images [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1984， PAMI- 6(6):721- 741．

[15] GUAN F， ZHANG S，LIU C，et al. ICTNET at federated web search track 2014 [C]∥Proceedings of the 23rd Text Retrieval Conference (TREC).Maryland：National Institute of Standards and Technology，2014.

[16] SALTON G，BUCKLEY C. Term-weighting approaches in automatic text retrieval [J]. Information Processing & Management， 1988， 24(5):513- 523．

[17] ZHANG D， XU H，SU Z，et al.Chinese comments sentiment classification based on word2vec and SVM perf [J]. Expert Systems with Applications，2015，42(4):1857- 1863．

[18] U.S. lommerce Department. Text REtrieval Conference[EB/OL].[2015- 10- 06]. http:∥trec.nist.gov/.

Resource Selection Algorithm on the Basis of Topic Model

DONGShou-binXIEYi-fanYUANHuaCHENJian-hao

(School of Computer Science and Engineering//Computation & Computer Network Laboratory of Guangdong Province, South China University of Technology, Guangzhou 510006, Guangdong, China)

In the federated search environment with multiple real search engines, the small- document approach, which is inefficient in estimating the accurate number of indexed files in the process of resource description, may result in poor performance of resource selection methods. In order to solve this problem, a resource library description method on the basis of topic model is proposed, which adopts LDA topic model to obtain the description word of each resource library. Then, a new resource selection algorithm is proposed, which combines with both vertical weight and word vector to calculate the correlation between resource library and query request, and to obtain the final resource selection results according to the correlation. Experimental results show that the proposed resource selection algorithm on the basis of topic model improves the performance of resource selection and can be effectively applied in the federated search environment of distributed search engines.

distributed search; resource selection; topic model; vertical domain; word vector

2016- 11- 27

廣東省自然科學(xué)基金重大基礎(chǔ)研究培育項目(2015A030308017)；教育部中國移動科研基金資助項目(MCM20150512) Foundation items: Supported by the Significant Fundamental Cultivate Project of Guangdong Province Natural Science Foundation(2015A030308017)and the Scientific Research Joint Funds of Ministry of Education of China and China Mobile(MCM20150512)

董守斌(1967-)，女，博士，教授，主要從事信息檢索與高性能計算研究. E-mail:sbdong@scut.edu.cn

?通信作者: 袁華(1969-)，女，博士，副教授，主要從事信息檢索研究. E-mail:hyuan@scut.edu.cn

1000- 565X(2017)03- 0048- 06

TP 391

10.3969/j.issn.1000-565X.2017.03.007