用戶相關反饋下的空間關鍵字語義查詢方法

孟祥福，趙路路，張霄雁,李 盼

(遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105)

1 引 言

隨著GPS等定位服務技術的出現，獲得地理空間維度信息變得容易，Web上因此也出現了越來越多具位置信息的空間對象，如酒店、咖啡廳和旅游景點等，這些空間對象通常被稱為興趣點(Point of Interest，POI).一個空間對象o主要包含空間信息和文本信息兩部分，空間信息通常由經緯度表示，文本信息是對空間對象的文本描述.空間關鍵字查詢q是以地理位置和關鍵字作為參數，目的是從空間對象集合中獲取位置相近和文本相似的空間對象.一個空間關鍵字查詢q的形式為：q(loc，keywords，k，α)，其中q.loc代表查詢位置，q.keywords是查詢關鍵字集合，k是指定返回的結果個數，α∈[0，1]是一個權重系數.

目前，普遍采用的空間對象o與查詢q的相關度計算方法是將空間相近度和文本相似度加權組合.然而，該類方法存在兩個方面的不足：

1)僅從文本形式上匹配查詢關鍵字，而普通用戶的查詢意圖通常是不明確的，因此需要語義層面的查詢匹配；

2)查詢關鍵字的權重僅根據關鍵字在空間對象文本信息中的出現頻率評估，沒有考慮用戶對不同查詢關鍵字的偏好程度，這很可能導致返回結果與用戶期望之間的偏差較大，因此，需要依據用戶的相關反饋來挖掘用戶隱式偏好并以此來調整查詢關鍵字的權重.

來看一個例子.圖1給出了一個空間關鍵字查詢和5個空間對象.空間關鍵字查詢條件為：

q：(location，{beefsteak，music})

該查詢表達的含義是：用戶想要在其位置附近尋找提供beefsteak和music服務的餐廳.o1～o5是附近的餐廳和茶館，每個對象包含了查詢q與其之間的規范化歐式距離以及該對象包含的文本信息.如果按照目前普遍采用的相關度計算方法，o2、o5和o1將是查詢結果(其中，α=0.5，k=3).然而，實際上并不一定所有的用戶都對上述查詢結果滿意，或許某些用戶為了方便不愿意到遠地方而選擇o3，即o3也可能是某個或某些用戶的top-3選擇之中.也就是說，上述方法并沒有體現用戶的個性化和語義查詢需求.

圖1 空間關鍵字查詢的例子Fig.1 An example of spatial keyword query

針對上述問題，本文提出一種基于用戶相關反饋的空間關鍵字個性化語義查詢方法.該方法分為兩個階段：第一階段，在離線處理過程中，采用Gibbs方法和LDA主題模型對空間對象的文本信息進行語義擴展，使得數據庫中的每個空間對象都在原來文本信息基礎上增加了語義相關的文本描述.第二階段，對于一個給定的空間關鍵字查詢，先采用IR-tree索引到語義擴展后的空間數據庫中獲取包含k個對象的候選查詢結果集，并要求用戶從中明確標注出自己感興趣的空間對象(即相關反饋)；然后，根據用戶的反饋信息，采用改進的Rocchio算法對查詢關鍵字的權重進行更新，形成新的查詢條件；接下來，利用更新后的查詢條件對數據庫進行檢索，重復執行上述過程，直到結果令用戶滿意為止.

2 相關工作

近年來，Internet上興趣點的大量增加以及移動設備的普遍應用，網絡上出現大量的空間對象，因此空間關鍵字查詢的研究已成為當前數據庫查詢領域的研究熱點.根據文獻[1]，空間關鍵字查詢大致分為4類：(1)布爾范圍查詢(2)布爾KNN(k近鄰)查詢[20](3)top-k范圍查詢[3](4)top-kKNN(k近鄰)查詢[4].該查詢通過興趣點與查詢點之間的空間距離以及興趣點的文本描述和查詢關鍵字之間的文本相似度的加權組合來度量.空間對象o與查詢q的位置相近性計算方法使用歐式距離，文本相似度方法使用余弦相似度方法計算.

然而，需要指出的是，現有的空間關鍵字查詢僅在形式上匹配關鍵字，只考慮文本相似度而未考慮查詢與文本的語義相關度以及用戶對不同查詢關鍵字的偏好程度.

對于文本間的相似度研究已有很多工作，主要可分為2大類：一是余弦相似度，二是基于主題模型.

Salton等人提出的向量空間模型的計算方法，將文本信息轉化為文本向量，然后使用余弦相似度計算文本間相似度.

Chris H.Q.Ding等人提出隱性語義標引(LSI)模型，將高維向量空間中的文本向量映射低維潛在語義空間中，再計算其文本間相似度[26].Blei,Ng，Jordan使用LDA模型，進行文本建模，通過文本中詞項(term)的共現特征發現文本的主題結構.LDA比VSM增加了概率的信息，更側重語義的挖掘.

與現有方法相比，為了理解空間對象文本信息反映的語義信息，本文使用Markov-Chain Monte Carlo算法中的一個特例Gibbs Sampling算法，同時為了快速有效的獲得空間關鍵字查詢結果，使用IR-tree進行檢索.并且本文進一步研究用戶相關反饋來了解用戶查詢的需求.

3 空間對象的語義擴展和候選集生成

本節主要描述基于LDA-Gibbs模型的空間數據庫的語義擴展方法，以及基于IR-tree索引的候選查詢結果集生成方法.

3.1 相關定義

給定一組空間對象集合O={o1,o2,...,on}，空間對象o∈O包含了位置信息o.loc和文本信息o.doc.一個空間關鍵字查詢q的形式為：q(loc，keywords，k，α)，其中q.loc代表查詢位置，q.keywords是查詢關鍵字集合，k是指定返回的結果個數，α∈[0，1]是一個權重系數.目前，普遍使用的空間對象o與查詢q的相關度計算方法為：

Score(o,q)=α·Sspatial(o.loc,q.loc)+(1-α)·
Stext(o.doc,q.keywords)

(1)

其中，Sspatial和Stext分別代表o與q之間歸一化的位置接近度和文本相似度[4，14，19，21，23].

空間對象o與查詢q的位置相近性計算方法如下：

(2)

其中，dist(o.loc，q.loc)表示o與q之間的歐式距離，MaxDist表示o與所有空間對象的最大距離.

空間對象o與查詢q的文本相似度評估的基本思想是，先將空間對象文本和查詢關鍵字進行向量化處理，分別用Vo和Vq表示(向量的維度是所有空間對象文本信息中包含的不同關鍵字總數)，再利用余弦相似度方法計算文本相似性，計算方法如下：

(3)

3.2 利用 LDA-Gibbs模型對空間數據庫進行語義擴展

對空間數據庫進行語義擴展的基本思想是，(1)先將數據庫中的所有空間對象文本信息集成到一個文檔中(假設該文檔包含了K個主題)；(2)然后利用LDA模型生成該文檔的主題分布，再針對某個主題生成相應的詞分布，在某個主題的詞分布中隨機選擇一個詞，重復該過程，直到某個主題下擁有若干個詞；(3)將空間對象o的文本信息o.doc中的關鍵字與生成的主題-詞分布中的詞進行比較，若相同，則將該詞對應的主題下的詞(該詞的φk，t應大于給定的閾值)加入o.doc中，生成新的文本信息，從而使得新的文本信息體現了原有信息的語義.

3.2.1 LDA主題分布

圖2為LDA概率模型圖.其中，α是文檔中主題的多項分布的Dirichlet先驗參數；β為主題下的詞的多項分布的Dirichlet先驗參數；zn為文檔第n個詞的主題；wn為該文檔第n個詞；K是主題數；N為該文檔中詞的個數.θ和φk都是需要求解的未知隱含變量，θ表示該文檔下的主題分布，φk為第k個主題的詞分布.

圖2 LDA概率模型圖Fig.2 LDA probability model diagram

假設空間數據庫中所有空間對象的文本信息構成的文檔為D，wn是可以觀察到的已知變量，α和β是根據經驗給定的先驗概率，本文取α=0.5，β=0.1.根據圖2的LDA的概率模型圖，主題和單詞的聯合概率分布可表示為：

(4)

3.2.2 基于Gibbs Sampling的LDA學習過程

本文采用Gibbs Sampling算法來學習未知隱含變量是θ和φk.Gibbs Sampling的執行方法為每次選取概率向量中的一個維度，給定其他維度的變量值隨機選取當前維度的值.不斷迭代，直到收斂輸出待估計的參數.圖3給出了基于Gibbs Sampling的LDA學習過程.

圖3 基于Gibbs Sampling算法的LDA學習過程Fig.3 LDA learning process based on Gibbs Sampling algorithm

該過程首先初始化文檔D中的每個詞，并且隨機分配主題，然后統計每個主題z下出現詞w的數量和該文檔下出現主題z中的關鍵字的數量，即n(w|z)和n(z|D).每一輪計算p(zi|z-i，d，w)，根據其他詞的主題分配來估計當前詞的主題屬于各個主題的概率.根據當前詞屬于所有主題z的概率分布為該詞隨機選取一個新的主題.循環執行更新下一個詞的主題，當θ和φk收斂時，算法停止，輸出估計的參數θ和φk.其中p(zi|z-i，d，w)是Gibbs updating規則，計算公式如下：

(5)

當Gibbs sampling 收斂后，根據文檔D中所有單詞的主題分配來計算θ和φk.文檔D上主題的后驗分布和每個主題下的詞后驗分布計算方法如下：

p(θ|z,α)=Dir(θ|nDOC+α)

(6)

p(φk|z,w,β)=Dir(φk|nk+β)

(7)

然后，使用Dirichlet分布的期望計算公式

=ai/∑iai

就可得到兩個Multinomial分布的參數θ和φk的計算公式：

(8)

(9)

3.2.3 空間對象文本信息的語義擴展

將空間數據庫中每個空間對象的文本信息根據LDA-Gibbs模型學習到主題-詞分布進行隱式語義分析，將原空間數據集擴展成具有語義的新的空間數據集.即將空間對象o的文本信息o.doc中的關鍵字與主題-詞分布中的詞進行比較，若相同，則將該詞對應的主題下的詞(該詞的(k，t大于0.07)加入o.doc，生成新的文本信息，使得新的文本信息更全面表達了原有文本信息的語義.

下面利用圖1說明使用Gibbs Sampling算法對空間對象文本進行語義擴展.將圖1中興趣點的文本信息集成到一個文檔，并且假設主題數為2，然后LDA模型得到主題-詞分布，如下：

Topic0：beefsteak 0.25 pizza 0.745454

Topic1：tea 0.598125 music 0.396975

最后將o1～o5中關鍵字與主題-詞分布中的詞進行匹配，匹配相同且參數值大于0.5的加入o1～o5，擴展成新的空間對象集合為：

o1：(0.25，beefsteak，tea，pizza)

o2：(0.3，beefsteak，pizza)

o3：(0.1，pizza，tea)

o4：(0.3，tea，music)

o5：(0.2，beefsteak，music，pizza，tea)

3.3 候選集獲取

本節主要研究基于IR-tree索引的空間關鍵字查詢選取候選集.IR-tree 本質上是一棵 R-tree，每一個節點都參照一個倒置文件來豐富包含在該節點的子樹中的對象.IR-tree是由R-tree空間索引和文本索引倒排列表Inverted file組成.R- tree將空間對象及索引空間用最小邊界矩形(Minimum Bounding Rectangle)來近似表示，將空間相鄰的對象組織到同一結點或同一分支， 并將一個結點對應成一個或者多個磁盤頁.該索引策略大大減少了I/O 訪問.倒排索引是一種簡單高效的文本索引， 它列出了每個關鍵詞以及包含該關鍵詞的所有對象.

IR-tree的每個節點包含兩種類型的信息，即子樹的最小邊界距離和包含關鍵字的倒排列表.圖4和圖5分別給出了根據圖1中的空間對象構建的IR-tree.

圖4 最小外接矩形Fig.4 Minimum external rectangle

圖4為最小外接矩形，其中o1～o5對應圖1中的5個空間對象，R1～R5對應為最小外接矩形.圖5是根據圖4構建的IR-tree結構，根節點是R5，中間節點是R3和R4，葉子節點是R2和R1.每個節點記錄了以該節點為根的子樹中所有對象的文本信息(關鍵字集合)及指針.并且每個節點的信息分為兩個部分指針和條目集合(entries)，指針指向包含該節點所有關鍵字的到排文件(InvFile).葉節點的每個條目包含一些形式為(oi，rectangle，oi.di)的條目，其中oi表示空間對象集合O中的對象，rectangle(矩形)是對象oi的邊界矩形，oi.di是對象oi的文本信息的標識符.非葉節點包含多個形式的條目(cp，rectangle，cp.di)，其中cp是非葉節點的子節點的地址，rectangle是子節點條目中所有矩形的最小邊界矩形 ，并且cp.di是文本信息的標識符.

圖5 IR-tree結構Fig.5 IR-tree structure

利用IR-tree索引獲得位置文本匹配結果的過程為：

1)初始化優先隊列U和一個列表V，U存儲IR-tree中已訪問的條目(entry)，列表V用來存儲候選集，e為帶有關鍵字集合的倒排列表和矩陣的條目.

2)給定一個查詢q，以迭代方式從U中刪除頂部條目給e，若e為空間對象，則添加到V中，若e為非葉子節點，則判斷查詢q與節點矩形之間的最小距離是否小于e與查詢q間的距離，若有小于，則判斷查詢q中的關鍵字集合和節點e的子條目中的關鍵字集合是否有交集，有交集則e的子條目添加到U中；否則，若e為葉子節點，那么獲得查詢q和空間對象之間距離，若該距離比e與查詢點間的距離小，則判斷查詢q中的關鍵字集合和節點e包含的對象中的關鍵字集合是否有交集，若有交集則將e包含的對象添加到U中.如果U為空，則中止上面的進程.

3)根據score函數將檢索到的結果集V進行top-k排序，獲得得分最高的前k個對象作為用戶反饋的候選集.

在圖1所給的實例中，使用IR-tree檢索到與查詢相關的結果為o5和o1.

上述利用IR-tree索引進行空間關鍵字查詢處理的過程如算法1所示.

算法1.生成候選集

輸入：數據集D，查詢q，k

輸出：候選集S

1.初始化一個空列表V

2.初始化一個優先隊列U

3.將tr的根節點加入U

4.whileU是否為空 do

5.e←U中頂部條目

6.ife是空間對象othen

7.e添加到V中

8. break;

9.else

10. ife為非葉子節點 then

11. for 每個子條目eiinedo

12.if(他們之間距離小于e與查詢間的距離

13. and 每個子條目包含關查詢鍵字)

14.ei添加到U中

15. else

16. for 每個空間對象oiinedo

17.if(他們之間距離小于e與查詢間的距離

18. and每個空間對象包含關查詢鍵字)

19.oi添加到U中

20.S←使用score函數從V中選出前k個空間對象

空間數據庫中存在大量的空間對象.在反饋過程中，每個回合中通過整個空間數據庫進行用戶反饋是不現實的.因此這個階段的目的是通過生成一個較小的候選集合，將其提供給用戶來進行反饋.算法1為第4節相關反饋的個性化查詢做準備.

算法1中第1、2行是初始化過程，3～19行是進行IR-tree的初始檢索，第20行是使用score函數選出檢索結果的前k個空間對象作為候選集.使用IR-tree進行初次檢索獲取候選集，其時間復雜度為O(|q.φ|·log|O|).其中|q.φ|為查詢q中關鍵字數，|O|為空間數據庫中空間對象數量，使用score函數的KNN的時間復雜度為log|O|.

4 基于用戶相關反饋的個性化查詢方法

4.1 相關反饋基本思想

圖6 基于Rocchio算法的相關反饋過程Fig.6 Related feedback process based on Rocchio algorithm

通過用戶的相關反饋，目的是增強語義相關文本信息中的出現的關鍵字的權重，降低在非相關文本信息中出現的關鍵字的權重，進而用戶可以逐漸接近其實際需求，最終得到用戶滿意的結果.基于Rocchio算法的相關反饋過程如圖6所示.

4.2 基于Rocchio算法評估關鍵字權重

現有方法通常采用式(3)衡量查詢關鍵字與空間對象文本之間的相似度，其中Vo和Vq是維度相同的向量，令Vo={d1，d2，…，dn}，Vq={q1，q2，…，qn}.其中，di和qi分別為空間對象和查詢中包含的關鍵字權重，n代表空間對象集合的文本信息與查詢條件中包含的所有不同關鍵字總數.

關鍵字的權重使用tf-idf方法計算，公式如下：

wti=tf(ti,o.doc)*idf(ti,O)

(10)

其中詞頻tf(ti，o.doc)為關鍵字ti出現在o.doc的頻率，逆文檔頻率idf(ti，O)=log(1/f(ti，O))，f(ti，O)表示包含關鍵字ti的對象個數.

在進行基于用戶相關反饋的查詢擴展時，查詢中的關鍵字的權重使用基于Rocchio算法進行重新計算，得到

(11)

(12)

其中，β部分為正反饋，γ部分為負反饋，α、β、γ取值為了調整原查詢、相關和不相關對象中文本信息之間的相對重要性.lton和Buckley的實驗發現，一般取α=1，β=0.75，γ=0.25時，Rocchio算法實現的效果最好[11，24].其中wti權重使用公式(10)計算.

結合圖1是空間關鍵字查詢的例子，對于空間關鍵字查詢q，假設認為o1、o2、o5是相關的，o3、o4是不相關的.利用Rocchio公式計算擴展后的查詢q′：

=(1.09028,1.00000,0.05208,0.00521)

表1 查詢和對象的文本信息中關鍵字權重Table 1 Keyword weights in query and object text information

根據表1和式(3)計算后，得到表2，如下：

表2 查詢與對象間的文本相似度Table 2 Text similarity between queries and objects

由表2可以看出，盡管對象o3與查詢無關，但反饋后的新查詢與對象o3具有語義相關性，原因是與查詢相關的對象o1、o2和o5包含對象o3文本信息中的關鍵字.在查詢過程中，查詢關鍵字出現的越少，越可能出現此情況.總體而言，基于Rocchio算法的相關反饋，提高了相關對象的語義相關度，提高了查詢的用戶滿意度.

基于用戶反饋的空間關鍵字查詢的具體過程如算法2.

算法2.基于Rocchio算法的反饋過程

輸入：候選集S，查詢q

輸出：結果集P

1.向量化候選集S中對象的文本信息d

2.向量化查詢q的文本信息q.t

3.初始化空列表P，rel，norrel

4.whiletruedo

5. 將S中的對象呈現給用戶

6.rel←用戶從S中選擇喜歡的對象oi

7.norrel←用戶從S中選擇不喜歡的對象oi

8. 基于Rocchio公式計算q′.t

9.S←利用IR-tree對查詢條件q′.t檢索

10. if terminate is true then

11.P←S

12. break;

13.returnP;

基于Rocchio算法的反饋過程中IR-tree檢索的時間復雜度為O(|q.φ|·log|O|).其中|q.φ|為查詢q中關鍵字數，|O|為空間數據庫中空間對象數量.

4.3 用戶反饋終止條件

用戶相關反饋的中止方法有兩種：一是用戶自己判斷最終結果是否滿意；二是系統自動計算中止閾值.本節給出一種系統自動判斷中止閾值的方法.

令fm和fm-1分別表示第m輪和m-1輪用戶反饋得到的結果，兩個集合相交，如果交集到達一定數量，則終止用戶反饋，計算方法見公式(13)：

(13)

terminate的取值越小用戶反饋越容易終止，但查詢的結果集不理想.最后將查詢結果集中的對象與新查詢的距離相近性和文本相似性用公式(1)將查詢結果集進行排序，score越大與查詢越相關.

5 效果與性能實驗評價

5.1 實驗設置

數據集：本文使用從Yelp商戶點評網站上抓取的真實的POI數據集來進行實驗研究.Yelp是美國著名商戶點評網站，其網站包含了各地餐館、購物中心、酒店等各個領域的商戶信息以及用戶評價和購物體驗等.將這些真實POI數據進行處理174567個興趣點，使得每個POI興趣點都有一個ID、位置(以經緯度的形式表示)和用戶評論.使用位置作為空間信息，用戶評論作為文本信息.

查詢集：在數據集中隨機選擇10個對象作為查詢條件，將其空間位置作為查詢位置，從文本信息中隨機選擇一定數量的單詞作為查詢關鍵字.在進行空間關鍵字查詢過程中，將該對象從數據集中排除.查詢關鍵字數量分別是2、4、6和8.

5.2 實驗結果與分析

5.2.1 用戶滿意度調查實驗

用戶滿意度分析：該實驗目的是測試現有計算位置相近度和文本相似度方法(即公式(1)，且α=0.5)與本文方法在用戶滿意度方面的差別.其方法使用如下公式：

(14)

其中，{relevant}表示用戶標注的與給定查詢相關的10個對象，{top-10retrieved}表示本文提出的空間關鍵字查詢方法得到的前10個對象.

實驗設置：參加測試的用戶數量多少會對查詢結果產生影響，用戶測試數量在5～8個左右，就幾乎能得到所有結果，更多的測試用戶和使用5個用戶的結果是相同的.

邀請5名用戶，對于每一個測試查詢條件q，每位用戶使用本文方法獲得前5個相關對象，然后再用文本相似度方法(公式(1))獲得前5個對象，這樣可以得到30個空間對象(如果有重復對象，則去重并從空間數據庫隨機選取對象加入，使其生成為30個空間對象的集合).

另外邀請1名用戶，令其在每個查詢對應的30個對象構成的測試集中，分別選取他認為與給定查詢最相關的前10個對象，這10個對象作為評價查準率的標準.

然后分別利用文本相似度方法(公式(1))和本文方法獲得前10個對象，進而利用公式(14)計算查詢的準確性(即標準的10個對象與不同方法檢索到的10個對象的重疊度).圖7給出了同一個用戶在不同查詢條件下獲得的查詢結果的準確性.

圖7 不同查詢條件下文本相似度方法和使用用戶反饋獲得結果集的準確性Fig.7 Text similarity method under different query conditions and the accuracy of the result set obtained by user feedback

邀請10名用戶(分別是導師、研究生同學和部分本科生)，在測試集中選取與某個查詢最相關的前10個對象.然后在利用文本相似度方法(公式(1))和本文方法分別獲得與該查詢相關的前10個對象，查看用戶的滿意程度.圖8給出了不同用戶在相同查詢條件下獲得的滿意度對比.

根據圖7、圖8分別計算平均準確性，不同查詢條件下，同一個用戶使用文本相似度方法獲得結果集的準確性為0.38，使用用戶反饋方法的準確性為0.73.不同用戶使用文本相似度方法獲得結果集的準確性為0.41，使用用戶反饋方法的準確性為0.79.由此可見，本文方法獲得的查詢結果的用戶滿意度較高，這是因為經過空間對象文本信息的語義擴展和用戶相關反饋，本文方法能夠獲得更能滿足用戶語義需求和偏好的結果.

圖8 不同用戶使用文本相似度方法和使用用戶反饋獲得結果集的準確性Fig.8 Different users use text similarity method and use user feedback to obtain the accuracy of result set

5.2.2 反饋終止

該實驗目的是評價終止閾值τ對基于Rocchio算法的用戶反饋的收斂速度的影響.我們將最多的輪數限制為10，以避免很難達到的情況.其中，取候選集的數量k=10,20,關鍵字數量n=8,τ的取值為0.2,0.4,0.6,0.8.圖9是終止閾值τ的影響.

圖9 終止閾值τ的影響Fig.9 Impact of the termination threshold

從圖9可以看出隨著k值得變大，其該輪得到的結果集和上一輪相交所得的交集越大，收斂速度變慢，反饋的輪數增加.當τ值設置過高時，用戶反饋過程甚至不能終止.

一般情況下用戶反饋7輪就能得到滿意結果.

6 結 論

為了更好的理解用戶的查詢意圖，本文提出基于用戶相關反饋的空間關鍵字個性化語義查詢方法.將空間數據集進行語義擴展，使得新生成的文本信息體現了原有信息的語義.然后進行相關反饋，得到最終的結果集，此結果集最接近用戶查詢，最能滿足用戶的查詢需求.通過實驗，可以看出使用用戶反饋比文本相識的方法的準確率高，說明基于用戶反饋的空間關鍵字查詢獲得的結果集更加接近查詢，更符合用戶的查詢意圖.

本文與現有方法的不同之處在于體現了原有信息的語義并且使用用戶反饋體現了個性化查詢，在空間關鍵字查詢的檢索實驗中，發現本文提出的方法對于提高用戶效率以及滿足用戶的查詢需求是有效的.