基于樸素貝葉斯點擊預測的查詢推薦方法

石　雁　李朝鋒

(江南大學物聯網工程學院　江蘇 無錫 214122)

?

基于樸素貝葉斯點擊預測的查詢推薦方法

石雁李朝鋒

(江南大學物聯網工程學院江蘇 無錫 214122)

查詢推薦作為一種改善用戶查詢體驗和效率的重要方式，可以幫助用戶篩選并提供更加準確的查詢描述。目前很多查詢推薦方法主要集中在熱門推薦或是基于相似度匹配的推薦上，忽略了用戶的查詢意圖，無法有效提供個性化推薦。為此，基于對用戶查詢點擊日志進行分析與挖掘，訓練出一個樸素貝葉斯模型，針對用戶輸入的查詢，根據歷史數據預測其與URL的點擊率，再利用二分圖將URL的預測點擊值平均分配給相對應的每個查詢項，最后結合Jaccard相似度和時間相關因子綜合分析用戶當前輸入的查詢與歷史中查詢的相關度，并給出推薦。實驗證明了該方法的可行性并取得了較好的推薦效果。

查詢推薦用戶日志點擊預測樸素貝葉斯二分圖Jaccard相似度

0　引　言

在目前主要根據關鍵詞進行檢索的搜索引擎框架中，用戶往往無法得到令其滿意的返回結果。這一方面是由于網絡數據呈海量增長態勢，每條查詢都可能會有上萬到幾十萬條的相關反饋信息，在這龐雜的信息中要找到用戶滿意的結果，這就要求用戶盡可能準確地描述查詢請求，同時需要搜索引擎在一定程度上能夠理解用戶查詢意圖，這對用戶和搜索引擎來說，都面臨一定挑戰。而另一方面，在用戶獲得了比較滿意的結果后，如何幫助用戶發掘潛在的相關信息來提升用戶的搜索體驗，這也是亟待解決的問題。

查詢推薦作為搜索引擎改善用戶查詢體驗的有效方式之一，其旨在接受用戶輸入某個查詢后，盡可能理解用戶的查詢需求并向用戶推薦與用戶查詢語義相關的其他查詢[1]。

在搜索點擊日志中，包含了大量用戶真實的搜索行為[2]，對這些數據進行分析與挖掘，可以更好地理解用戶查詢意圖，發現與用戶查詢相關的其他查詢。因此，本文在用戶點擊日志的基礎上，對用戶搜索行為進行建模，找出與用戶查詢意圖相關的查詢信息，并給出個性化推薦。

1　查詢推薦相關研究

目前查詢推薦已經作為國內外各大商業搜索引擎的標準配置功能之一，在學術界也得到了廣泛關注和研究。然而現在的搜索引擎中大多針對用戶輸入的查詢文本本身，進行改寫和擴展，或是簡單地提供與用戶查詢文本近似的熱門搜索作為推薦，并沒有考慮查詢中潛在的用戶搜索意圖。如果搜索引擎能夠根據查詢詞自動找出背后的用戶搜索意圖，然后根據不同的用戶，提供不同的查詢推薦，這無疑會增加搜索引擎用戶的搜索體驗。而查詢日志中記錄了用戶大量的查詢點擊信息，這些信息體現了用戶的查詢習慣和點擊意圖，利用日志可以挖掘用戶潛在的查詢意圖，目前針對日志進行分析的主流方法主要有兩類[3]：基于查詢會話(Session)的方法和基于點擊圖的方法。

1.1基于查詢會話方法

查詢會話是某個用戶在較短時間內連續發出的多個查詢，一般而言，在同一查詢會話內的查詢之間往往存在一定的語義相關性[4]。比如某個用戶想要購買手機，在某個集中的時間內連續向搜索引擎發出：“蘋果手機”、“iphone 6圖片”、“iphone 6價格”等一連串查詢，這就形成一個查詢會話。通過將用戶搜索日志劃分為大量不同的查詢會話，然后利用各種數據挖掘算法對查詢會話進行統計與分析，推薦的結果往往是一批查詢對，這些查詢在搜索過程中經常共同出現，反應了用戶的搜索意圖。李亞楠等人認為同一Session中的查詢都具有語義相關性，而其中的前后查詢具有一定的概率“跳轉”，所以對Session進行劃分，并據此建立查詢關系圖，使用加權的SimRank算法在圖結構中進行相似計算，從而挖掘出查詢間的間接關聯和語義關系[4]。在文獻[5]中，將查詢推薦分為兩階段：第一階段分析用戶日志，從中抽取用戶Session，第二階段從用戶Session中使用關聯規則算法挖掘出查詢間的關系，找出相關查詢。Sadikov等人提出一種結合文檔點擊和用戶查詢Session的共現信息，利用近似用戶搜索行為的馬爾可夫多隨機游走模型，根據用戶的可能潛在意圖進行查詢修改聚類，用來改善搜索引擎中返回的查詢建議[6]。

1.2基于點擊圖方法

從用戶查詢日志記錄中可以看到用戶提出某個查詢，搜索引擎返回相關結果后，用戶會有選擇地點擊其中某些鏈接。之所以認為這種點擊行為很有意義，是因為用戶在看了返回的網頁標題和摘要后，認為此鏈接和查詢比較相關，所以才會點擊。而將用戶的查詢和相對應點擊的鏈接網址(URL)使用邊連接起來，就構成了點擊圖，這是一種二分圖[7]，一端節點是用戶發出的查詢，另一端是對應點擊的URL。在使用點擊圖作為查詢推薦的一個簡單的通用基本框架是：如果兩個查詢分別對應的點擊URL中，有相當一部分比例是相同的，那么說明這兩個查詢有很大的語義相關性，可以作為相關查詢進行推薦。不同的學者據此也提出了各種擴展和改進的方法。Hamada M.Zahera 等人提出根據查詢和URL點擊二分圖，對查詢進行相似聚類，然后對用戶提出的查詢，找出與其最相似的一組進行排序推薦[8]。劉鈺峰等人提出基于查詢上下文訓練詞匯與查詢間的語義關系，并結合查詢和URL對應的點擊圖以及查詢的序列行為構建Term-Query-URL異構信息網絡，采用重啟動隨機游走算法進行查詢推薦，該方法綜合了語義和日志信息，提高了稀疏查詢的推薦效果[9]。文獻[10]中，提出一種新的基于上下文感知查詢建議方法，該方法分為線下和線上兩步。在線下，使用用戶點擊圖進行聚類，把查詢總結成不同概念，然后為Session數據序列構造概念后綴樹作為查詢建議模型。在線上，把用戶提交的查詢序列映射到概念中，獲取用戶搜索上下文，通過查詢概念后綴樹得到相關查詢。

綜上，除了日志分析方法中的兩個主流方法外，還有基于相似度方法、基于時間分布法等[1]。雖然目前提出的很多方法對查詢推薦有一定的效果，但由于大多具有高度復雜性并且用戶意圖不明確，所以很難得到廣泛的實際應用。本文根據點擊日志，對用戶的查詢進行意圖點擊預測，進而將預測值傳播給其他查詢，結合相似度和時間因子獲得相關查詢。最后在搜狗實驗室提供的數據中進行實驗，獲得了較好的推薦效果。

2　基于用戶日志挖掘的查詢推薦

在對用戶日志和搜索引擎進行深入分析后，提出基于圖1的框架來研究查詢推薦。從中可以看出用戶在發出查詢后，一部分經搜索引擎返回相關網頁，而另一部分使用樸素貝葉斯針對用戶查詢，預測URL的點擊率，將其值用在反向點擊圖中，從而找出相關查詢，推薦給用戶。

圖1　查詢推薦基本結構

2.1使用樸素貝葉斯進行URL點擊率預測

樸素貝葉斯是一種基于貝葉斯理論的有監督的概率分類算法，尤其適用于樣本特征維數很高的情形。有資料顯示，就算樣本屬性相互獨立的假設不成立，或者在完全相反的情況下(屬性相互依賴)，依然可以證明該算法是最優的[11]。在這里，將樸素貝葉斯算法作為一種預測模型，用它來預測URL對于用戶及其所提交的查詢的點擊率，也就是說可以根據它計算出用戶在提交某個查詢時想要看到某個鏈接的概率。

首先，需要根據用戶日志對樸素貝葉斯進行訓練，將每個URL作為概念，每個與其對應的查詢作為樣本，根據所需計算出各個概念的先驗概率及其對應的樣本的條件概率，然后再依據用戶當前輸入的查詢(實例)計算其與每個概念的點擊值。具體過程如下：

輸出：實例q對應URL的點擊率。

a) URL的先驗概率及樣本屬性的條件概率

(1)

(2)

式(1)代表每個URL的先驗概率，分子為每個URL的頻數，分母為樣本個數；式(2)代表每個屬性的條件概率，分子為屬性和URL的聯合概率。

b) 經過訓練后，就可以對用戶當前提出的查詢實例q=(q1,q2,…,qn)，進行URL點擊預測。公式如下：

(3)

這樣每個相關URL都會有一個預測值，該預測值代表了用戶輸入的查詢和URL的點擊相關度，值越大，表示用戶想要點擊URL的意圖性越強。

2.2使用反向點擊圖進行查詢推薦

2.2.1反向點擊圖推薦模型

基于二分圖結構，提出一種URL-Query的反向點擊圖推薦模型，如圖2所示。

圖2　反向點擊圖模型

在該模型中，根據2.1節計算出用戶當前查詢對于歷史點擊中URL的預測點擊值，作為URL的權重，并將其平均分配給與其對應的查詢，這樣每個查詢經過整合后會有一個相關值，這個相關值也代表了用戶的查詢意圖，如圖3所示。

圖3　預測點擊值的分配

考慮一個由n個URL和m個查詢(Query)構成的點擊二分圖，表示為G(U,Q,E)，E表示URL和Query之間連接的邊，URL節點表示為U={(u1,a1),(u2,a2),…,(un,an)}，其中ai為計算用戶當前查詢的預測點擊值，Query節點表示為Q={q1,q2,…,qm}。根據圖3中的計算，每個qi的相關值經過傳播求和，計算如下：

(4)

其中：k(uj)表示與uj連接的qi的個數；aj為URL的預測值。

然而由于對用戶輸入的查詢進行樸素貝葉斯URL點擊預測后的值會被均分到相對應的歷史查詢中，這會導致將每個查詢均等化。鑒于此，對式(4)進行補充修正，加入了用戶歷史查詢和對應URL的點擊比率，公式如下：

(5)

其中：公式的后半部分表示qi的點擊數占總點擊數的比率，比率越大，表示在點擊歷史中，用戶關注的越多，用戶想要點擊的意圖性就越強。

2.2.2融合文本相似度和時間因子

利用樸素貝葉斯預測用戶查詢行為，本質上是找到查詢與鏈接(URL)的關系，但這忽略了用戶查詢與歷史查詢之間的文本相似性，很多時候我們想搜索的是和當前詞相似的或是擴展的查詢內容，比如在百度輸入“江南大學”，在網頁底部就會出現相關搜索，如表1所示。

表1　“江南大學”相關搜索推薦

在表中可以看到除了其他大學外(而這些大學我們假設經過用戶點擊過的并給予預測的推薦查詢)，與“江南大學”相似的或者說是擴展的推薦查詢詞占了較高比率，用戶可能想查詢與“江南大學”有直接關系的信息。而通過融合文本相似度可以增強這一相關性，在這里采用簡單有效的Jaccard相關系數來計算當前用戶提交的查詢和用戶歷史查詢的文本相似性，公式如下：

(6)

在點擊日志中，時間因素是一個重要的上下文信息。一般來說，用戶當前的查詢和用戶歷史中最近的點擊行為關系更大[12]?，F在假設用戶在時間t發出一個查詢q，點擊歷史數據中的URL和其對應查詢中的時間，記為：t0,t1,t2,t3,t4,t5，如圖4所示，這樣圖中后面的四個查詢的點擊時間分別包括：q1(t0,t2)，q2(t1)，q3(t3,t4)，q4(t5)?？梢钥吹揭粋€查詢對應多個不同的URL，會有不同的點擊時間，所以不能簡單地采用最近時間作為標準衡量時間。對此，使用式(7)計算相關時間因子。該式綜合了當前時間和所有歷史時間差的和的均值作為衡量因素。

圖4　查詢點擊時間

(7)

其中：α是時間衰減參數，可以根據不同的數據集選擇合適的參數，如果用戶查詢意圖變化快，就選擇較大的值，相反需要取較小值。tq是用戶當前查詢時間，tqi是不同的查詢點擊時間，分母是點擊次數。這樣就可以根據時間的變化來優化預測推薦。

為了舉例說明，現假設用戶發出一個查詢q時間為9:40，在用戶歷史點擊數據中，查詢q1的時間為8:40、10:40和q2的時間為7:40、11:40、13:40。按式(7)計算相關時間因子t(q,q1)和t(q,q2)(這里α取1，時間為小時)。所以不論從時間上的直觀性來看，還是計算后的數值大小比較上，q和q1更具有明顯的時間相關性。

≈0.27

在最終的推薦中，整合式(5)、式(6)和式(7)，如式(8)：

(8)

通過計算，對qi的相關值進行降值排序，按Top-N推薦給用戶。

3　實驗與結果分析

3.1實驗數據

本實驗采用的數據來自搜狗實驗室提供的2008年6月份查詢日志中的一天數據，共1 724 264條查詢。該日志中包括每條查詢的時間、用戶ID、查詢串、URL返回的排名、點擊順序以及點擊的URL。經過預處理，選擇用戶查詢數在200條以上的點擊數據，在這里選取了10名用戶，共2803條查詢。每名用戶中點擊數據的80%用作訓練，另外一部分用來測試。實驗平臺使用Intel? CoreTMDuo T2450 @ 2.00 GHz雙核處理器，2 GB內存，Windows XP 32位操作系統，算法使用Java語言編寫，分詞工具使用來自輕量級中文分詞包IKAnalyzer2012_u6.jar[13]。

3.2實驗設計及結果分析

盡管在國內外關于查詢推薦的相關研究已有不少成果，但總體上仍然缺乏統一和客觀的評價方法，尤其是針對中文的查詢推薦的研究，仍然比較欠缺。由于對于一個查詢來說并不存在某種標準的推薦結果，在考慮基于用戶意圖的查詢推薦時，更是無法把握用戶的真實想法。因此，一般的查詢推薦評價都采用信息檢索里的評價指標[14]。本文采用Top-N的精度P@N(Precision at N)和平均精度均值MAP(Mean Average Precision)作為評價指標。由于在所有候選推薦中，很難得到所有相關查詢數目，因而召回率(Recall)很少作為評價指標[15]。實驗對于一個給定的查詢qi，系統推薦出m個查詢，這m個查詢中的P@N精度為：

(9)

(10)

其中K是查詢測試集，這里選取每個用戶的20個查詢作為測試集，N為5，然后由人工進行判斷產生的查詢推薦是否相關。對于單個查詢qi的平均精度，定義為：

(11)

(12)

在實驗中，選取文獻[8]中基于查詢日志的查詢聚類方法和文獻[16]的基于用戶興趣的Apriori方法進行對比實驗(在實驗中分別稱為查詢聚類法和Apriori法。)本文方法的時間參數α需要根據不同用戶點擊數據集的時間分布進行選擇，這里α取1。在P@5和MAP上的對比結果如表2。

表2　三種算法在P@5和MAP上的對比結果

本文在P@3、 P@5、P@7、P@9上進一步對這三種算法在不同P@N上的變化進行測試對比。從10名用戶中選取用戶1和用戶2作參考，圖5、圖6為對比結果，從中可以看出本文方法在P@N上的精準度要優于前兩種方法。

圖5　用戶1三種算法在不同P@N上的比較

圖6　用戶2三種算法在不同P@N上的比較

為了比較直觀地觀察推薦效果，現列出部分查詢推薦示例如表3所示，從中可以看到，本文的算法在推薦的相關查詢上取得了較好效果。由于本算法關注的是用戶查詢的相關性和意圖性，忽略了查詢間的冗余性，從而在一定程序上，推薦的查詢有一定的重復率。另外，由于用戶查詢的稀疏問題，也造成了一定的推薦不明確性。

表3　部分查詢推薦示例

續表3

4　結　語

查詢推薦作為個性化搜索引擎的一項重要研究課題，其改善和提升了用戶的搜索體驗，它可以為不同的用戶提供多樣性和個性化的查詢推薦。本文在前人的研究基礎上，首先采用基于樸素貝葉斯模型預測用戶查詢點擊URL的值，然后使用反向點擊圖將每個URL預測值作為用戶查詢意圖傳播給日志中與其對應的查詢項，再結合文本匹配度和時間相關因子作出Top-N相關查詢推薦。實驗結果表明了該方法的有效性以及在一定程度上表達了用戶的查詢意圖。在下一階段的研究中，將會考慮查詢的稀疏問題以及將基于用戶的協同推薦理論用到查詢推薦上。

[1] 李亞楠,王斌,李錦濤.搜索引擎查詢推薦技術綜述[J].中文信息學報,2010,24(6):75-84.

[2] 董志安,呂學強.基于百度搜索日志的用戶行為分析[J].計算機應用與軟件,2013,30(7):17-20.

[3] 張俊林.這就是搜索引擎:核心技術詳解[M].北京:電子工業出版社,2012:146-258.

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

[5]FonsecaBM,GolghePB,MoursaESDe,etal.DiscoveringSearchEngineRelatedQueriesUsingAssociationRules[J].JournalofWebEngineering,2004,2(4):215-227.

[6]SadikovE,MadhavanJ,WangL,etal.Clusteringqueryrefinementsbyuserintent[C]//Proceedingsofthe19thinternationalconferenceonWorldWideWeb.Raleigh,NorthCarolina,USA:ACM,2010:841-850.

[7] 王棲,段雙艷.一種改進的基于二部圖網絡結構的推薦算法[J].計算機應用研究,2013,30(3):771-774.

[8]HamadaMZahera,GamalFElHady,WaielFAbdEl-Wahed.QueryRecommendationforImprovingSearchEngineResults[J].InternationalJournalofInformationRetrievalResearch,2011,1(1):45-52.

[9] 劉鈺鋒,李仁發.基于Term-Query-URL異構信息網絡的查詢推薦[J].湖南大學學報:自然科學版,2014,41(5):106-112.

[10]HuanhuanCao,DaxinJiang,JianPei,etal.Context-AwareQuerySuggestionbyMiningClick-ThroughandSessionData[C]//Proceedingsofthe14thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.NewYork:ACM,2008:875-883.

[11]RishI.Anempiricalstudyofthena?veBayesclassifier[EB/OL].IBMResearchReport,RC22230 (W0111-014),2001:41-46.http://www.cc.gatech.edu/～isbell/classes/reading/papers/Rish.pdf.

[12] 項亮.推薦系統實戰[M].北京:人民郵電出版社,2012:130-132.

[13] 林良益.基于Java語言開發的輕量級的中文分詞工具包[EB/OL].(2015-1).http://git.oschina.net/wltea/IK-Analyzer-2012FF/tree/master.

[14]RicardoBaeza-Yates,BerthierRibeiro-Neto.現代信息檢索[M].黃萱菁,張奇,邱錫鵬,譯.2版.北京:機械工業出版社,2012:98-103.

[15] 廖振.基于查詢點擊核心圖的查詢推薦問題研究[D].天津:南開大學,2013.

[16] 石林,徐飛,徐守坤.基于用戶興趣建模的個性化推薦[J].計算機應用與軟件,2013,30(12):211-214,264.

QUERY RECOMMENDATION BASED ON NAIVE BAYES CLICK PREDICTION

Shi YanLi Chaofeng

(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,Jiangsu,China)

Query recommendation, as an important way to improve user-query experience and efficiency, can help users to filter and offer more accurate query descriptions. Many of the current query recommendation methods mainly focus on popular recommendation or the recommendation based on similarity matching, but neglect user’s query intention, thus are unable to effectively provide the personalised recommendation. Therefore, on the basis of analysing and mining users’ query-click logs, we have trained a Naive Bayes model. Aiming at the queries inputted by the user, the model predicts CTR (click-through rate) between these queries and URL according to historical data, then uses bipartite graph to averagely assign the predicted CTR of URL to each corresponding query, and at last it combines the Jaccard similarity with time correlation factor to comprehensively analyse the relevance between the query currently inputted by the user and the historical queries, and provides the recommendations. In subsequent experiment it is proved the feasibility of this method, as well as the better recommendation effect achieved.

Query recommendationUser logClick-through predictionNa?ve bayesBipartite graphJaccard similarity

2015-07-07。國家自然科學基金項目(61170120)。石雁，碩士，主研領域：信息檢索，推薦系統。李朝鋒，教授。

TP391

A

10.3969/j.issn.1000-386x.2016.10.005