基于位置的個性化關(guān)鍵詞查詢推薦

梁耀培，吳定明

深圳大學(xué)計算機(jī)與軟件學(xué)院，廣東深圳 518060

在信息檢索系統(tǒng)中，關(guān)鍵詞查詢推薦技術(shù)是利用用戶提交的關(guān)鍵詞，向其推薦若干相關(guān)關(guān)鍵詞，用戶再用這些推薦的關(guān)鍵詞去檢索，找到所需信息．現(xiàn)有的關(guān)鍵詞查詢推薦方法大多是基于搜索日志中的點(diǎn)擊信息[1-3]和查詢會話記錄[4]，主要分為基于帶重啟的隨機(jī)漫步(random walk with restart, RWR)方法[5]、排列學(xué)習(xí)方法[6]和基于聚類的方法[2]．近年來，也有學(xué)者使用神經(jīng)網(wǎng)絡(luò)進(jìn)行基于位置的查詢推薦[7]．在基于位置的信息檢索中，用戶不僅希望找到與所查詢關(guān)鍵詞相關(guān)的信息，還希望返回的信息在用戶位置附近．這個需求來自于空間關(guān)鍵詞搜索的增多[8]．個性化的推薦模型在計算的過程中會考慮用戶的偏好，因此不同偏好的用戶即使提交相同的關(guān)鍵詞，也會得到不同的推薦關(guān)鍵詞查詢.推薦算法需要解決兩個問題：一是如何在有效地衡量關(guān)鍵詞查詢語義相似度的同時，兼顧用戶位置與文檔之間空間距離的鄰近性．關(guān)鍵詞-文檔(keyword-document)二部圖(簡稱K-D圖)是經(jīng)典的不考慮位置的關(guān)鍵詞推薦方法[3-5,8-10]．本研究構(gòu)造的K-D圖，可將關(guān)鍵詞查詢和與其相關(guān)的文檔連接起來，通過調(diào)整K-D圖中邊的權(quán)重，使之不僅反映關(guān)鍵詞查詢之間的語義相關(guān)性，還能反映文檔位置與用戶位置λq的空間距離．通過在K-D圖上采用個性化的PageRank(persoralized PageRank, PPR)，即帶重啟的隨機(jī)漫步模型[11]，計算與用戶提交的關(guān)鍵詞kq最相似的m個查詢，使推薦的查詢關(guān)鍵詞可檢索到λq附近的信息．二是如何使推薦的查詢符合用戶偏好．本研究對用戶提交過的關(guān)鍵詞進(jìn)行分類，將用戶提交最多的類別作為用戶的偏好．在用戶提交關(guān)鍵詞時，將屬于偏好的歷史查詢也加入到推薦方法的計算中．

本研究旨在設(shè)計一個基于位置的個性化關(guān)鍵詞查詢推薦框架，以獲取與用戶信息需求相關(guān)，且符合用戶偏好的推薦關(guān)鍵詞，這些關(guān)鍵詞能夠檢索用戶位置附近的文檔．真實(shí)數(shù)據(jù)集上的測試結(jié)果證明，基于位置的個性化關(guān)鍵詞查詢推薦可行．

1 基于位置的個性化關(guān)鍵詞查詢推薦

給定一個用戶提交的查詢關(guān)鍵詞kq(單詞或短語)和用戶位置λq， 本研究提出的推薦算法需滿足3個要求：① 基于kq， 推薦的關(guān)鍵詞能滿足用戶信息需求，與提交的查詢關(guān)鍵詞具有語義相似性；② 推薦的關(guān)鍵詞能夠檢索與λq在空間上鄰近的文檔；③ 推薦的關(guān)鍵詞符合用戶偏好．

1.1 初始K-D圖

在一個查詢?nèi)罩局校頓表示帶有位置信息的文檔集合，D中每個文檔di都有一對經(jīng)緯度坐標(biāo)di.λ，K為查詢?nèi)罩局兴胁樵冴P(guān)鍵詞kj的集合．首先，構(gòu)建初始K-D圖，這是一個有向的加權(quán)二部圖G=(K,D,E)， 可反映關(guān)鍵詞查詢與文檔之間的語義相關(guān)性，以及不同查詢之間的相似度，能滿足①的要求．假設(shè)用戶提交查詢kj， 并點(diǎn)擊文檔di， 則E包含一條從kj到di的邊e和一條從di到kj的邊e′． 其中，e和e′的權(quán)重相同，是在日志中提交查詢kj后di的點(diǎn)擊次數(shù)[1]．因此，一個查詢和一個被點(diǎn)擊文檔的聯(lián)系度通過邊上權(quán)重來體現(xiàn)．兩個查詢的語義相關(guān)性則通過它們在G上的相似性來體現(xiàn)．查詢?nèi)罩旧系娜我飧露寄鼙粦?yīng)用到K-D圖上：一個新的查詢或文檔，可在圖上增加一個新結(jié)點(diǎn)；一個新的點(diǎn)擊，可更新相應(yīng)的邊的權(quán)重．圖1是一個有2個文檔d1、d2和2個查詢k1、k2所對應(yīng)的二部圖．為演示方便，在此對邊上的權(quán)重進(jìn)行了歸一化處理(在關(guān)鍵詞-文檔對中，將點(diǎn)擊次數(shù)除以最大點(diǎn)擊次數(shù))．

圖1 K-D圖示例Fig.1 Keyword-document bipartite graph

1.2 對邊權(quán)重進(jìn)行基于位置的調(diào)整

為讓推薦的關(guān)鍵詞能夠檢索到用戶位置附近(即文檔位置與用戶位置的歐氏距離較小)的文檔，本研究基于用戶位置和K-D圖中結(jié)點(diǎn)的地理位置關(guān)系，調(diào)整K-D圖中邊的權(quán)重．

用戶提交的查詢q包含2個參數(shù)：關(guān)鍵詞kq和用戶查詢位置λq． 其查詢結(jié)點(diǎn)ki到文檔結(jié)點(diǎn)dj的邊的權(quán)重w(e)按照式(1)進(jìn)行調(diào)整為

(1)

其中， dist(λq,dj.λ)是λq和dj的位置的歸一化歐氏距離；β為邊權(quán)重調(diào)整參數(shù) ， 用于平衡原始權(quán)重和dj與λq之間的距離權(quán)重，β越小，用戶的位置對推薦結(jié)果的影響越大，β∈[0,1]．

令D(ki)表示在K-D圖中與關(guān)鍵詞查詢ki連接的文檔集合，它可能包含多個文檔．通過計算λq與D(ki)的最短距離，可調(diào)整指向ki的邊的權(quán)重，如式(2)．此調(diào)整偏向于推薦與λq至少有1個地理位置相近的文檔的關(guān)鍵詞結(jié)點(diǎn)．

(1-min(dist(λq,D(ki))))

(2)

其中， min(dist(λq,D(ki)))是λq到文檔集合D(ki)中所有文檔的最短歐氏距離．

設(shè)文檔d1和d2距離用戶位置λq的歐氏距離分別是1.0和0.9 ，β=0.5． 圖2(a)是從關(guān)鍵詞節(jié)點(diǎn)到文檔節(jié)點(diǎn)的邊權(quán)重調(diào)整．從k1到d1， dist(λq,dj.λ)=1.0． 從k1到d2， dist(λq,dj.λ)=0.9． 圖2(b)是從文檔節(jié)點(diǎn)到關(guān)鍵詞節(jié)點(diǎn)的邊權(quán)重調(diào)整，k1與{d1,d2}相連， min(dist(λq,D(k1)))=0.9．

圖2 基于位置的二部圖權(quán)重調(diào)整Fig.2 Weight adjustment based in bipartite graph

1.3 基于位置的個性化關(guān)鍵詞查詢推薦

1.3.1 在關(guān)鍵詞查詢推薦中考慮位置

用Gq表示K-D圖G的邊的權(quán)重在調(diào)整后的圖．為找到推薦的關(guān)鍵詞查詢集合，基于RWR算法[5]，計算與kq相關(guān)的查詢的分?jǐn)?shù)．圖Gq中結(jié)點(diǎn)v的RWR分?jǐn)?shù)表示一個隨機(jī)漫步者從kq到達(dá)v的可能性．在漫步過程中的每一步，漫步者要么以1-α的概率移動到相鄰的點(diǎn)，要么以α的概率跳轉(zhuǎn)到kq， 即α為RWR開始的概率． 在Gq中，排除kq得分最高的前m個查詢結(jié)點(diǎn)，就是算法得到的推薦查詢．

設(shè)Ψ為記錄了Gq中K的所有查詢分?jǐn)?shù)的列向量，其計算式為

Ψ=(1-α)MTDKMTKDΨ+αΨq

(3)

其中，MDK是一個文檔量×查詢量矩陣；MKD是一個查詢量×文檔量矩陣，兩者存儲了Gq中邊的權(quán)重．

1.3.2 在關(guān)鍵詞查詢推薦中考慮個性化

令Ψq為原始的分?jǐn)?shù)向量．為在推薦中考慮用戶偏好，將屬于用戶偏好的m個歷史查詢記錄，在矩陣Ψ中賦值為(1-γ)/m， 并設(shè)用戶新輸入的查詢關(guān)鍵詞kq=γ． 如圖3，q1到q5是用戶的查詢記錄，使用Topics文本分類器(https://uclassify.com/browse/uclassify/topics)分類為類別C1和C2． 將查詢次數(shù)最多的類別作為用戶偏好類別C2． 在本算法中，用戶新提交的查詢q6的初值是γ，q3～q5屬于用戶偏好類別，初值是(1-γ)/3． 其中，q1～q5是K-D圖的關(guān)鍵詞節(jié)點(diǎn)，分別對應(yīng)k1～k5．

圖3 對歷史查詢和現(xiàn)有查詢的權(quán)重分配Fig.3 Weight allocation to history queries and current query

2 基于位置的個性化關(guān)鍵詞查詢推薦算法

通過擴(kuò)展Bookmark-Coloring算法[12](BCA)，計算基于RWR算法的m個推薦查詢．本算法的K-D圖Gq有2種結(jié)點(diǎn)：查詢結(jié)點(diǎn)和文檔結(jié)點(diǎn)．與BCA不同的是，本算法只對查詢結(jié)點(diǎn)評分，查詢結(jié)點(diǎn)保留α部分的活躍墨水，然后向與其相連的結(jié)點(diǎn)散播1-α部分的活躍墨水；而文檔結(jié)點(diǎn)將它所有的活躍墨水散播到與其相連的結(jié)點(diǎn)．算法的偽代碼請掃描論文末頁右下角二維碼查看．優(yōu)先隊(duì)列Q按照活躍墨水量的降序處理結(jié)點(diǎn)，最初包含m+1個結(jié)點(diǎn)．其中，m個屬于用戶偏好的歷史查詢的關(guān)鍵詞結(jié)點(diǎn)，墨水量為(1-γ)/m； 1個為用戶提交的關(guān)鍵詞結(jié)點(diǎn)，墨水量為γ． 優(yōu)先隊(duì)列C初始為空，按保留墨水量降序存儲推薦查詢的候選者．出現(xiàn)以下任一情況，算法結(jié)束：①C中第m個結(jié)點(diǎn)的活躍墨水量，比第m+1個結(jié)點(diǎn)的活躍墨水量加上剩余的活躍墨水量多；② 每個結(jié)點(diǎn)的活躍墨水量低于ε(ε=1×10-3)． 所有結(jié)點(diǎn)的活躍墨水的總和被設(shè)成1．對查詢結(jié)點(diǎn)的處理是：保留α部分的活躍墨水，然后向與它相連的文檔結(jié)點(diǎn)的散發(fā)(1-α)部分的活躍墨水．最后，對活躍墨水的總量作對應(yīng)的修改，查詢結(jié)點(diǎn)已保留墨水，則進(jìn)入C． 對文檔結(jié)點(diǎn)的處理是：根據(jù)調(diào)整后邊的權(quán)重，向與它相連的關(guān)鍵詞結(jié)點(diǎn)散播其全部活躍墨水．算法返回C中除kq外前m個關(guān)鍵詞查詢．

3 基于真實(shí)數(shù)據(jù)的測試結(jié)果及分析

3.1 數(shù)據(jù)預(yù)處理

使用AOL數(shù)據(jù)集(https://jeffhuang.com/search_query_logs.html)對所提方法進(jìn)行檢驗(yàn)．AOL數(shù)據(jù)集是一個基于AOL搜索引擎的真實(shí)查詢?nèi)罩?，每條記錄包含用戶的ID、提交的查詢和點(diǎn)擊的URL．為使日志數(shù)據(jù)適于使用，需進(jìn)行以下處理：① 通過Freegeoip項(xiàng)目(https://freegeoip.io/)獲得URL定位，確保獲取位置的可靠性；② 使用基于開放目錄項(xiàng)目(Open Directory Project)的分類器對用戶的查詢記錄分類，將查詢次數(shù)最多的類別作為用戶的偏好．當(dāng)一條記錄中包含用戶ui、 查詢kq和文檔dj時，在ui和kq之間添加邊，其權(quán)重是ui對kq的點(diǎn)擊次數(shù)除以用戶的總查詢次數(shù)．在kq和dj添加邊，其權(quán)重是包含kq和dj的記錄條數(shù)除以kq的記錄條數(shù)．最終構(gòu)建的K-D圖有187 050個查詢，79 376個文檔，126 889個用戶．

3.2 算法衡量指標(biāo)

本研究采用以下4個標(biāo)準(zhǔn)來衡量算法性能．

衡量標(biāo)準(zhǔn)1 使用推薦的關(guān)鍵詞進(jìn)行檢索，返回屬于用戶偏好且距其位置0.1歐氏距離內(nèi)的文檔數(shù)量．使用Lucene工具包對所有文檔索引，將推薦返回關(guān)鍵詞作為查詢關(guān)鍵詞，確定檢索返回符合衡量標(biāo)準(zhǔn)1的文檔數(shù)量．

衡量標(biāo)準(zhǔn)2 計算原始查詢和推薦查詢檢索的屬于用戶偏好，且距用戶位置0.1歐氏距離內(nèi)的文檔的相似性．令{do}表示原始查詢檢索返回的在查詢位置0.1歐代距離內(nèi)，且屬于用戶偏好的前10個文檔，令{ds}表示推薦的關(guān)鍵詞檢索返回的在查詢位置0.1歐氏距離內(nèi)，且屬于用戶偏好的前10個文檔．計算{do}和{ds}的返回列表在同一位置的文檔之間的余弦相似度，通過nDCG(normalized discounted cumulative gain)方法[12]來聚合這些余弦的相似度，計算式為

(4)

衡量標(biāo)準(zhǔn)3 衡量推薦查詢的類別與用戶偏好的相關(guān)性．使用分類器對關(guān)鍵詞查詢分類，計算關(guān)鍵詞的共同前綴，根據(jù)共同前綴確定關(guān)鍵詞與用戶偏好的相關(guān)性，計算式為

(5)

其中，P(C1,C2)為分類C1和C2的共同前綴數(shù).

本研究使用分類器對兩個推薦算法返回的前5個關(guān)鍵詞進(jìn)行分類，計算這些關(guān)鍵詞類別與用戶偏好的相似度的平均值．

衡量標(biāo)準(zhǔn)4 記錄算法的運(yùn)行時間．

3.3 測試結(jié)果及分析

3.3.1 算法運(yùn)行參數(shù)

設(shè)α為0.20、0.35、0.50、0.65和0.80時，β和γ的默認(rèn)值為0.50；β為0、0.25、0.50、0.75和1.00時，α和γ的默認(rèn)值為0.50；γ為用戶偏好對推薦結(jié)果的影響權(quán)重，依次設(shè)置為0.10、0.30、0.50、0.70和0.90，α和β的默認(rèn)值為0.50．

3.3.2 結(jié)果分析

圖4展示了不同參數(shù)設(shè)置對算法運(yùn)行結(jié)果的影響．其中，baseline表示只考慮用戶位置，不考慮用戶偏好的推薦算法；personalized是本算法，即考慮用戶偏好和位置的推薦算法．

圖4(a)—(c)顯示了α對檢索結(jié)果的影響，結(jié)果發(fā)現(xiàn)，personalized算法在衡量標(biāo)準(zhǔn)1、2和3中的表現(xiàn)都優(yōu)于baseline方法，這是因?yàn)榍罢叩某跏缄?duì)列中包含更多的查詢關(guān)鍵詞．在時間性能方面(圖4(j))，personalized算法運(yùn)行時間較baseline方法長，但兩種算法的運(yùn)行時間都隨著α的增大而縮短．這是因?yàn)棣猎酱?，留在關(guān)鍵詞節(jié)點(diǎn)中的墨水越多，活躍墨水的總量下降越快，使終止條件更早被滿足．當(dāng)α=1.00時所有墨水被保留在關(guān)鍵詞節(jié)點(diǎn)中，算法結(jié)束，返回結(jié)果為空．當(dāng)α=0時，每一步都無墨水被保留，因此墨水總是被重新分配，直到隨機(jī)漫步過程達(dá)到穩(wěn)定狀態(tài)．在這種情況下，節(jié)點(diǎn)的最終得分依賴于圖的結(jié)構(gòu)，而非開始節(jié)點(diǎn)(關(guān)鍵詞節(jié)點(diǎn))，即無論輸入什么關(guān)鍵詞，最終結(jié)果都相同．因此，α=0或1.00不能給出有效的結(jié)果．

圖4 不同參數(shù)設(shè)置對算法運(yùn)行結(jié)果Fig.4 Algorithm running results based on various parameters setting

圖4(d)—(f)顯示了β對檢索結(jié)果的影響．β是對用戶提交的查詢關(guān)鍵詞具有語義相似性的關(guān)鍵詞分配的權(quán)重， 1-β表示與查詢位置相近的關(guān)鍵詞分配的權(quán)重．當(dāng)β接近0或1.00時，只有與查詢位置相近的或與用戶提交的關(guān)鍵詞語義相似度較高的關(guān)鍵詞才會參與計算．但當(dāng)β∈(0, 1.00)時，與查詢位置稍遠(yuǎn)但與查詢具有高語義相似度的文檔，或與查詢位置相近但語義相似度低的文檔都被考慮到了．對于不同的β， 在衡量標(biāo)準(zhǔn)1中，personalized算法的表現(xiàn)優(yōu)于baseline算法；在衡量標(biāo)準(zhǔn)2中，β=1.00時baseline算法表現(xiàn)好于personalized算法，原因是此時兩個算法都只考慮與用戶提交查詢相似度高的文檔，未考慮位置信息；在衡量標(biāo)準(zhǔn)3中，β=1.00時，兩個算法表現(xiàn)相近，原因同衡量標(biāo)準(zhǔn)2．在時間性能方面，personalized算法運(yùn)行時間比baseline算法長(圖4(k))，原因與α的相同，且在β=0.75時，算法運(yùn)行時間最長．

圖4(g)—(i)顯示了γ對檢索結(jié)果的影響．γ為對用戶提交的關(guān)鍵詞查詢分配的墨水量， 1-γ為對屬于用戶偏好的歷史查詢分配的墨水量．因?yàn)閎aseline算法不需要參數(shù)γ， 所以在3個衡量標(biāo)準(zhǔn)中baseline算法的表現(xiàn)沒有變化．對于衡量標(biāo)準(zhǔn)1和2，personalized算法的表現(xiàn)優(yōu)于baseline算法，對于衡量標(biāo)準(zhǔn)3，personalized算法只有在γ=0.90時表現(xiàn)優(yōu)于baseline算法．在時間性能方面(圖4(l))，personalized算法的運(yùn)行時間較baseline算法長，原因與α的相同，且在γ=0.50時，算法運(yùn)行時間最長．

結(jié) 語

為推薦考慮了位置信息和用戶偏好信息的關(guān)鍵詞，本研究基于K-D圖，使用帶重啟的隨機(jī)漫步算法，計算關(guān)鍵詞查詢之間的語義相關(guān)性，以及檔位置與用戶位置的空間距離．在AOL數(shù)據(jù)集上對算法進(jìn)行測試，得到較好結(jié)果．但是，用戶的偏好會隨時間發(fā)生變化，因此下一步我們將加入時間因素，研究用戶偏好變化時的關(guān)鍵詞查詢推薦．