〔摘要〕考慮到傳統(tǒng)的基于日志的查詢推薦算法受到數(shù)據(jù)稀疏問題的影響，本文在分析查詢?nèi)罩镜幕A上，構建查詢詞與點擊URL之間的雙向圖，計算查詢詞與候選詞之間的相似度。然后基于知網(wǎng)計算查詢詞與候選詞之間的相似度，考慮詞性和同義詞因素對相似度的影響。最后將兩個相似度分別賦予權重計算查詢詞與推薦詞的相關度。實驗結果表明，該方法不易受數(shù)據(jù)稀疏問題的影響，穩(wěn)定性較好。

〔關鍵詞〕查詢?nèi)罩?；查詢推薦；雙向圖

DOI：10.3969/j.issn.1008-0821.2013.10.015

〔中圖分類號〕TP391.1〔文獻標識碼〕A〔文章編號〕1008-0821（2013）10-0065-05

隨著互聯(lián)網(wǎng)和基礎設施的快速發(fā)展，搜索引擎已成為人們獲取信息的重要來源。根據(jù)中國互聯(lián)網(wǎng)絡信息中心2012年7月19日發(fā)布的《第30次中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告》中顯示[1]，截至2012年6月底，中國網(wǎng)民數(shù)量達到5.38億，搜索引擎的使用率為79.7%。有學者研究表明，用戶輸入的查詢通常只有兩三個詞[2]，并且對所要檢索的內(nèi)容知之甚少，所以用戶很難明確的表達自己的查詢意圖。查詢推薦技術是向用戶推薦若干個與用戶輸入相關的查詢，能幫助用戶生成更加符合其搜索意圖的查詢推薦詞，引導用戶的搜索行為，優(yōu)化搜索結果。

本文在已有的查詢推薦研究基礎上，從兩個方面對查詢詞和候選詞進行相似度計算。文章的結構如下：第一節(jié)介紹查詢推薦相關研究現(xiàn)狀；第二節(jié)分別基于雙向圖和知網(wǎng)計算查詢詞和候選詞的相似度；第三節(jié)介紹整個查詢推薦算法的流程；第四節(jié)進行實驗驗證和評價；第五節(jié)做總結分析。

1相關研究

早在上世紀90年代，信息檢索研究者就開展了一些查詢推薦相關研究[3]，查詢推薦技術在檢索和瀏覽過程中的確能提高檢索的質量和效率。根據(jù)所依賴的數(shù)據(jù)源大致可以分為兩大類：一是基于文檔的推薦方法；二是基于用戶查詢?nèi)罩镜耐扑]方法[4]。

基于文檔的推薦方法主要通過處理包含查詢詞的文檔來分析查詢，從查詢相關文檔或人工編輯語料中找出與查詢詞相關的詞或短語，然后利用這些相關詞或短語構建推薦查詢。有學者利用查詢相關文檔擴充查詢以解決查詢短的問題[5]，也有學者利用偽相關文檔檢索查詢相關詞[6]。

基于日志的方法依靠分析搜索引擎查詢?nèi)罩緛韺ふ页霈F(xiàn)過的相似查詢，并根據(jù)一定算法排序后擇優(yōu)推薦給用戶。查詢?nèi)罩局杏涗浟擞脩敉暾乃阉鼽c擊行為，基于查詢?nèi)罩镜耐扑]方法逐漸成為近年來常用的方法。有學者認為在同一session內(nèi)出現(xiàn)的查詢有可能語義相近，利用相關的相似度算法來度量查詢間的相關性[7]。有學者提出一種基于查詢共有相同點擊URL數(shù)的查詢推薦方法[8]，在此基礎上，有學者基于查詢點擊雙向圖提出了改進的SimRank相似度算法度量查詢相關性[9-10]。有學者基于一個大規(guī)模商業(yè)搜索引擎查詢?nèi)罩?，利用查詢?shù)據(jù)內(nèi)在的全局流行度來獲得查詢之間的相關性，并提出了一種基于流行度排序的查詢推薦方法[11]。也有學者研究查詢?nèi)罩局杏脩鬒D與點擊URL之間的聯(lián)系，提出基于主題與用戶偏好分析的查詢推薦方法[12]。

基于日志的方法根據(jù)搜索歷史推薦查詢詞，相對于基于文檔的方法更符合用戶查詢特點。但是查詢詞在日志中的出現(xiàn)頻率呈指數(shù)分布，大多數(shù)查詢詞在日志中出現(xiàn)次數(shù)不多，這使得基于日志的方法面臨嚴重的數(shù)據(jù)稀疏問題。

考慮到日志中數(shù)據(jù)稀疏問題，本文將從兩個方面對查詢詞和候選詞進行相似度計算。首先基于構建的雙向圖計算查詢詞與候選詞之間的相似度，然后利用中科院的分詞系統(tǒng)對查詢詞進行分詞處理，基于知網(wǎng)計算查詢詞與候選詞的相似度，最終得到查詢詞與候選詞的相關度，相關度滿足條件的候選詞即為推薦詞。

2基于日志和知網(wǎng)的查詢推薦算法

2.1基于雙向圖的相似度計算

查詢?nèi)罩镜呢S富與否直接影響候選查詢集合的質量，因此要獲得較好推薦的效果必須有豐富的查詢?nèi)罩?。這里我們采用搜狗搜索引擎公開的查詢?nèi)罩編臁Ｈ罩镜幕靖袷饺绫?：表1查詢?nèi)罩净靖袷?/p>

如表1所示，每一條檢索記錄由訪問時間（t），用戶ID（u），查詢詞（q），用戶點擊的URL（l），該URL在返回結果中的排名（r）和該URL點擊的順序組成（o）。因此，一條檢索記錄可由〈t，u，q，l，r，o〉表示。在這里我們只考慮查詢詞和用戶點擊的URL兩個因素，利用〈q，l〉構造查詢詞和點擊URL的雙向圖。其中，查詢詞集合Q={q1，q2…qn}表示日志中出現(xiàn)過的查詢詞的集合，URL集合L={l1，l2…ln}表示日志中用戶點擊過的URL的集合。查詢詞結點qi到URL結點urlj的邊eij由某一查詢詞節(jié)點出發(fā)到某一URL節(jié)點結束，表示用戶輸入該查詢進行檢索并在返回的結果中點擊了相應的URL。邊的權重wij是查詢?nèi)罩局衑ij出現(xiàn)的次數(shù)，一定程度反映了節(jié)點對之間的關聯(lián)程度。邊的集合E={eijqi∈Q，urlj∈L}表示了日志中所有的點擊行為集合。

查詢詞與點擊URL雙向圖如圖1所示：

1圖1查詢詞與點擊URL雙向圖1

在對雙向圖的觀察中發(fā)現(xiàn)，有些邊的權重值偏小?？紤]到用戶使用搜索引擎的一些無意識的隨機點擊行為會增加一些噪音數(shù)據(jù)。我們設定閾值m=4對邊噪音數(shù)據(jù)進行過濾，刪除權重小于m的邊，再刪除雙向圖中孤立的查詢詞節(jié)點和URL節(jié)點，減小雙向圖的復雜度。

在查詢詞推薦的研究中發(fā)現(xiàn)，查詢?nèi)罩局袃蓚€查詢詞有相近的語義關系，將有較多的點擊URL共現(xiàn)?；诖思僭O本文使用雙向圖的URL結點集合來定義查詢詞，對于查詢詞節(jié)點集合Q與URL節(jié)點集合L，第i個查詢詞節(jié)點（qi）的特征向量為i：

i[j]=wij1∑θijw2ij1eij存在

01eij不存在（1）

其中wij表示第i個查詢詞到第j個URL的邊的權重。

那么，對于查詢詞queryi和候選詞queryj的相似度可以采用余弦距離計算：

Simquery（queryi，queryj）=i×j1i×j（2）

2.2基于知網(wǎng)的相似度計算

《知網(wǎng)》是我國著名機器翻譯專家董振東先生創(chuàng)建的一個知識系統(tǒng)。在《知網(wǎng)》的結構中，詞是用概念來描述的，一個詞可以表達為幾個概念，而概念則用義原來描述，義原是用于描述一個概念的最小意義單位。

2.2.1詞性因素

我們認為在推薦的候選詞中，含有越多原查詢中權重值大的詞語，其與查詢詞的相似度就越高。例如查詢詞“華山風景”，華山作為惟一的專有名詞，出現(xiàn)的頻率較低，應具有更高的權重。在推薦的候選詞中，“華山簡介”就應該比“泰山風景”相似度更高。

首先利用中科院的分詞系統(tǒng)對查詢詞進行分詞處理，對于查詢詞query，經(jīng)過分詞處理，得到關鍵詞集合query={t1，t2…tn}（n為查詢詞q中含有的關鍵詞個數(shù)）。根據(jù)關鍵詞被標注的詞性，賦予關鍵詞不同的權重。

weight（t）=1.0t為專有名詞

0.8t為普通名詞

0.6t為動詞

0.4t為形容詞

0.2其它（3）

關鍵詞詞性對候選詞的相似度的影響計算如下：

Simetymology（queryi，queryj）=∑n1i=1weight（ti）ifti∈queryj（4）

其中，queryj為推薦候選詞，ti為查詢詞queryi所含的關鍵詞，n為關鍵詞個數(shù)。weight（ti）是查詢詞中第i個關鍵詞的權重。

2.2.2同義詞因素

我們認為同義詞因素對查詢推薦效果也存在同樣的影響。如查詢詞“華山圖片”就應該和“華山照片”、“華山風景”等在語義上有較大的相似度。在這里我們利用知網(wǎng)來計算查詢詞與候選詞之間的相似度[13]。

假設詞語K1有n個概念S1i，S12…S1n，K2有m個概念S21，S22…S2m，本文中定義詞語K1和K2的相似度是其所有概念之間相似度的最大值：

Sim（K1，K2）=Max（Sim（S1i，S2j））（5）

其中，0

用于描述概念的義原分為基本義原、關系義原和關系符號義原。概念間的相似度計算表示為：

Sim（S1，S2）=∑31i=1βi∏i1j=1Simj（P1，P2）（6）

其中，Simj（P1，P2）分別表示3種描述義原的相似度，βi是可調(diào)節(jié)的參數(shù)，且有β1+β2+β3=1，β1≥β2≥β3，1≤i，j≤3。

義原之間的相似度一般依據(jù)義原的層次結構來計算，本文基于兩個節(jié)點之間的路徑長度來計算：

Sim（P1，P2）=α1α+distance（P1，P2）（7）

其中，P1和P2表示兩個義原，distance（P1，P2）是P1和P2在義原層次體系中的最短路徑，α是一個可調(diào)節(jié)的參數(shù)。

同義詞對候選詞的相似度的影響計算如下：

Simtongyici（queryi，queryj）=∑n1i=1∑m1j=1weight（ti）Sim（ti，kj）（8）

其中，m，n分別為候選詞和查詢詞中關鍵詞的個數(shù)。Sim（ti，kj）為查詢詞中第i個關鍵詞與候選詞中第j個關鍵詞的相似度。

2.3查詢詞與候選詞的相關度計算

我們先利用雙向圖計算了查詢詞與候選詞的相似度，然后在分詞的基礎上，基于知網(wǎng)計算了查詢詞與候選詞之間的相似度。我們可以得到候選詞與查詢詞的相關度計算方法：

Relation（queryi，queryj）=γ1Simquery（queryi，queryj）+γ2Simtongyici（queryi，queryj）+γ3Simetymology（queryi，queryj）（9）

其中，γi是可調(diào)節(jié)參數(shù)，且有γ1+γ2+γ3=1。

3查詢推薦算法流程

由于搜索引擎的廣泛使用，查詢?nèi)罩久總€月新增約2 000萬條點擊記錄。隨著日志的不斷增長，算法需要動態(tài)支持添加新的查詢詞與點擊日志。算法步驟如下：

步驟1：遍歷雙向圖中查詢詞集合的節(jié)點query∈Q，獲取與query相連的所有點擊URL節(jié)點集合Lq。

步驟2：遍歷query的點擊URL節(jié)點集合Lq，獲取Lq相連的查詢詞節(jié)點集合q∈Q′。

步驟3：遍歷與query可能相近的查詢詞集合Q′，計算query與q的相關度，并根據(jù)相關度大小降序排序，選取前k個詞做為與query相近的查詢詞，本文取k=10。

算法流程如圖2所示：

1圖2查詢推薦算法流程1

如圖2所示該算法只需掃描一遍查詢詞集合，便可以挖掘出每個查詢詞的語義相近查詢詞。并且，對于新加點擊行為，只需修改新加邊的權重，針對該查詢詞重新執(zhí)行算法步驟2與步驟3，獲取到該詞的候選詞序列便可，不影響其他查詢詞的計算結果。

4實驗結果與評價

4.1實驗數(shù)據(jù)

本文采用搜狗查詢?nèi)罩咀鳛閿?shù)據(jù)集，該數(shù)據(jù)集記錄了搜狗搜索引擎在2006年8月的所有用戶查詢記錄，其中包含了19 562 507條點擊行為，2 898 971條查詢詞，8 018 410條點擊URL。根據(jù)實驗中的多次嘗試，我們將幾個參數(shù)值設置如下：α=1.5，β1=0.5，β2=0.3，β3=0.2，γ1=0.5，γ2=0.3，γ3=0.2。

4.2實驗環(huán)境

實驗用的系統(tǒng)是Windows XP，開發(fā)環(huán)境是Visual Studio.NET，開發(fā)語言是C++，數(shù)據(jù)庫環(huán)境是SQL Server 2000。

4.3實驗結果

由于查詢短語的相關性帶有極高的主觀性，不同的人由于背景或興趣的不同，同一組推薦結果也會有不同的評價結果。目前這方面的研究還沒有一個標準的評價標準，通常都采取隨機選取查詢并進行評分。我們從查詢?nèi)罩局须S機抽取10個查詢詞，得到與每個查詢詞相關度最高的10個候選詞，同時也從百度搜索引擎中獲取10個候選詞。

例如隨機抽取的查詢詞為“華山照片”，按照我們的方法和百度得到的推薦詞如下表所示：表2我們的方法得到的推薦詞

華山的照片1華山圖片1華山的圖片1華山風景1華山風景照片華山天氣1華山旅游1華山門票1華山攻略1華山住宿

表3百度搜索引擎得到的推薦詞

華山的照片1華山醫(yī)院1上海華山醫(yī)院1華山一日游1華山門票華山住宿1翠華山1西安華山

山頂住宿1華山天氣1華山論劍

我們請50個同學對推薦結果進行評價。根據(jù)結果的相關性從0～5分進行評分，最高分為5分，表示該推薦詞與查詢詞十分相關，最低分為0分，表示推薦詞與查詢詞毫不相關。當分值小于或等于1時，該推薦詞與查詢詞不相關。評價結果圖3所示：1圖3查詢評價效果圖1

從圖3中可以看出，百度的平均值為3.85，但不同的查詢詞得到的相關度評價波動幅度較大，說明結果受到數(shù)據(jù)稀疏的影響較大。用我們的方法得到的相關度評價的平均值為3.77，略低于3.85，但每個查詢詞的評價結果都在很小范圍內(nèi)浮動，說明我們的方法不易受數(shù)據(jù)稀疏的影響，穩(wěn)定性較好，具有一定的實際價值。

我們定義集合A為推薦系統(tǒng)返回的10個推薦詞，集合R為所有相關的推薦詞，即評分大于1的推薦詞。推薦詞的精確度定義為：

Pre（query）=R1A

根據(jù)以上方法，如圖4所示，我們得到推薦詞的精確度。從圖中可以看到我們的方法得到平均精確度為7.04，與百度的方法非常接近。即平均每10個推薦詞中，大約有7個與查詢詞相關。

1圖4查詢精確度

5總結

本文基于搜狗查詢?nèi)罩?，通過構建查詢詞與點擊URL雙向圖和分詞處理，分別基于雙向圖和知網(wǎng)計算查詢詞與候選詞之間的相似度。實驗表明，該方法不易受數(shù)據(jù)稀疏的影響，穩(wěn)定性較好。在今后的工作中，將進一步簡化雙向圖的復雜度，減少系統(tǒng)的時間消耗，進一步挖掘查詢?nèi)罩局械南嚓P信息，實現(xiàn)基于用戶和主題的個性化推薦，提高檢索服務的效率和質量。

參考文獻

[1]第30次中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告[EB].http：∥www.cnnic.cn.

[2]馬少平，劉奕群，劉健，等.中文搜索引擎用戶行為的演化分析[J].中文信息學報，2011，25（6）：90-97.

[3]E.Eftheimiadis.Query expansion[J].Annual Review of Information Science Technology，1996，31：121-187.

[4]李亞楠，王斌，李錦濤.搜索引擎查詢推薦技術綜述[J].中文信息學報，2010，24（6）：75-84.

[5]M.Sahami，T.D.Heilman.A web-based kernel function for measuring the similarity of short text snippets[C]∥Proceedings of the 15th international conference on World Wide Web.New York：ACM，2006：377-386.

[6]R.W.White，G.Marchionini.Examing the effectiveness of real-time query expansion[J].Inf Process Manage，2007，43（3）：685-704.

[7]Eric C Jensen，Steven M Beitzel，Abdur Chowdhury.Query Phrase Suggestion from Topically Tagged Session Logs[C]∥Proceedings of the 7th International Conference on Flexible Query Answering Systems，Milan，Italy.June 2006：185-196.

[8]王繼民，彭波.搜索引擎用戶點擊行為分析[J].情報學報，2006，25（2）：154-162.

[9]馬云龍，林原，林鴻飛.基于權重標準化SimRank方法的查詢擴展技術研究[J].中文信息學報，2011，25（1）：28-34.

[10]李亞楠，許晟，王斌.基于加權SimRank的中文查詢推薦研究[J].中文信息學報，2010，24（3）：4-10.

[11]朱小飛，郭嘉豐，程學旗，等.基于流形排序的查詢推薦方法[J].中文信息學報，2011，25（2）：38-43.

[12]陸偉，張曉娟，基于主題與用戶偏好分析的查詢推薦研究[J].情報學報，2012，31（12）：1252-1258.

[13]江敏，肖詩斌，王弘蔚.一種改進的基于《知網(wǎng)》的詞語語義相似度計算[J].中文信息學報，2008，22（5）：84-89.

（本文責任編輯：孫國雷）