智慧旅游中基于語義軌跡的高效最近鄰查詢方法研究

孫一格 馬 昂 吳 雷, 潘 曉 郭景峰(石家莊鐵道大學經濟管理學院 河北 石家莊 05004)(河北省高校人文社會科學重點研究基地(石家莊鐵道大學) 河北 石家莊 05004)(燕山大學信息科學與工程學院 河北 秦皇島 066004)

0 引 言

智慧旅游是隨著云計算、下一代通信、數據挖掘等技術發展起來的一種新型旅游形態。其以移動終端應用為核心，實現用戶和互聯網的實時交互，使旅行安排更加個性化，并且便捷、高效，從而具有很大的研究價值。手機等各種電子移動設備以及GPS定位系統的發展，使得人們出行的地理位置信息很容易獲取[1-3]。一方面，出行者在外出過程中停留形成的空間點連接起來形成了具有時空信息的軌跡；另一方面，伴隨社交媒體應用的流行普及，例如，微博、微信等應用，地理位置與文本數據的融合變得非常普遍。軌跡中蘊含的豐富語義信息，如道路狀況、天氣條件、鄰近朋友等為智慧旅游中越來越多應用和研究提供了助力。例如，在旅游系統中，用戶除了記錄自己的位置信息以外，還包括感興趣點類型、地理環境、用戶評價、圖片、視頻等數據。通過將軌跡中的時空信息與文本數據融合可以得到帶有語義標簽的軌跡，被稱為語義軌跡[5-6]。例如用戶A在a點購物，在b點住宿，那么購物、住宿等活動就是與空間點相對應的語義信息。由于軌跡的數量是相當龐大的，如何有效地對海量軌跡進行查詢，獲取最能滿足客戶需求的軌跡具有重要的應用價值。

在軌跡數據上進行查詢處理已有大量的研究工作[4-16]。然而，現有大部分工作僅考慮軌跡上的時空信息，忽略了軌跡上的語義信息。例如，某驢友希望從歷史旅游軌跡線路中尋找滿足一定要求的軌跡作參考。倘若只考慮地理位置的因素，則可以通過布爾查詢[11]、skyline查詢[14]或最近鄰kNN[15]查詢等得到合適的匹配路線。然而，現實中很多情況下用戶不僅對地理位置有要求，同時對語義也有要求。如驢友期望在自己預設的地點附近進行餐飲、參觀和購物等需求。以圖1為例，用戶想在q1點附近進行{a,c}兩項活動，在q2點附近進行{e}活動。Tr1、Tr2、Tr3是系統中的原有的旅行軌跡，當用戶向系統輸入他想進行的活動及地點后，系統應返回包含用戶所需要的全部活動{a,c,e}且從空間位置上距離查詢點最近的k條軌跡，即語義軌跡的kNN查詢。表1給出查詢點到軌跡點的距離。

表1 示例中Tr1、Tr2軌跡點到查詢點的距離

本文正是針對智慧旅游中語義軌跡上的k最近鄰查詢問題進行研究。基于R-tree融合位置上的文本信息提出了ITS-tree索引結構(包括IT-tree和S-樹兩個部分)，索引了原始軌跡特征點的空間信息和語義信息，可同時從空間和文本兩個方面對軌跡進行剪枝。利用最小最佳優先原則，首先遍歷IT-tree，從原始的語義軌跡中先獲取候選軌跡集，然后對候選軌跡利用S-樹進行軌跡結果的求精。

1 相關工作

現有在軌跡數據上的查詢工作，按照查詢點的個數的不同可分為兩類：一類是單點查詢，即查詢滿足用戶當前位置和語義需求的軌跡數據；另一類是多點查詢，即查詢中包括的位置可以是一個點集合，語義可以是用于描述整條軌跡亦可以是描述每一個位置采樣點的關鍵字集合。文獻[11]給定用戶查詢位置和語義集合，返回包含用戶語義并且匹配距離最短的k條軌跡。文獻[6]提出的近似關鍵字查詢 AKQST與傳統空間語義查詢不同，在查詢集合中僅指定語義集合，但并沒有涉及位置信息。該方法返回k條包含最相關語義且旅行代價最小的k條子軌跡。文獻[7]中，每一條軌跡上帶有一個文本關鍵字集合，提出了面向用戶的軌跡查詢UOTS。該方法返回距離查詢點最近的軌跡，并且查詢點的集合可以是有序序列，也可以是無序序列。文獻[16]在位置空間、語義信息的基礎上，增加了一個衡量標準即打分信息。在用戶給定起點、終點以及語義信息下，該方法返回包含查詢中所有語義信息、以及軌跡長度滿足距離要求并且評分最高的軌跡段。文獻[5]提出一種GAT新型網格索引結構，以層次的方式組織軌跡片段及其活動信息。利用best-first搜索框架，通過空間鄰近和活動遏制同時修剪大量不合格的軌跡，有效地處理了空間文本查詢。但由于為每一個語義構建一棵樹，當需查詢的語義較多時，會導致對HICL進行多次遍歷，查詢代價較高。

2 問題的形式化描述

方便起見，本文將游客在某地點上進行的活動，如住宿、餐飲、購物等，作為該位置的語義信息，其全集用A表示，小寫字母表示語義實例。語義軌跡是一系列被賦予活動語義的點序列，用Tr表示，軌跡上的點用p來表示，即Tr={p1，p2，p3，…}，軌跡上的點p同時具有位置和語義兩方面信息，形式化的表示為pi=(x,y,φ)，其中φ={x|x∈A}表示該點附著的語義信息。用戶輸入的查詢點集用Q{q1，q2，q3，…}表示，其中每一個查詢點亦是語義位置點。

定義1(點匹配[5]) 給定某一查詢點q，若軌跡上點子集的語義組成的并集是查詢點語義集的超集，即q.φ?∪pi∈Trpi.φ，則稱該點集是查詢點q到軌跡Tr的點匹配，用pm表示。

很明顯，針對某一個查詢，軌跡上的點匹配存在多個。

繼續圖1的例子，{p1,1,p1,2}、{p1,2,p1,3}、{p1,1,p1,2,p1,3}等都是查詢點q1到軌跡Tr1的點匹配，其點匹配距離分別為3.2、5.0、6.0，最短點匹配距離為D(p1,1,q1)+D(p1,2,q1)=3.2。

本文的查詢是點集合。因此，軌跡匹配距離定義與文獻[5]相同。

從定義3可以看出，軌跡匹配距離是所有查詢點到該軌跡的任意一個點匹配距離的和。軌跡的最短匹配距離是所有匹配距離中的最小值。例如，針對Q={q1,q2}來說，軌跡Tr1的軌跡匹配距離為Dpm(q1,Tr1)+Dpm(q2,Tr1)。Tr1的最短軌跡匹配距離Dmm(Q,Tr1)為Dmpm(q1,Tr1) +Dmpm(q2,Tr1) =3.2+4.8=8.0。

本文的目標即從語義軌跡集合D中，根據查詢點集合Q，尋找包含Q中所有關鍵字集合并且軌跡匹配距離最小的k條軌跡。具體來講，查詢結果需要滿足空間與語義兩方面要求：從語義的角度講，查詢結果中的點集合應包含所有查詢點語義，示例中查詢點語義集合是{a,c,e},則軌跡Tr2、Tr3不會出現在結果集中；從空間的角度講，查詢點到軌跡的軌跡匹配距離最短，以滿足空間上軌跡興趣點接近預設地點的要求。

3 ITS-樹索引結構

為提高查詢效率，本文提出了一個新的ITS-tree (即IT-tree+S-tree)索引結構。該索引結構分為兩部分：(1) IT-tree，索引空間中的語義軌跡，融合了軌跡的空間信息、語義信息以及軌跡標識，便于查找候選軌跡集。(2) S-tree查找樹，以語義詞頻為標準為軌跡標識號建立分段樹，便于確定軌跡是否包含查詢中的全部語義。

IT-tree：在R-tree的基礎上融合了關鍵字到軌跡的倒排信息。為提高查找速率，在IT-tree中存儲的是所有語義在整個數據庫的詞頻，方便對語義進行比較和剪枝。在軌跡的所有點上建立R-tree，在葉子結點上建立詞頻到軌跡標識的倒排表，在中間結點上存儲詞頻區間。具體來講，葉子結點中的倒排表以該區域內覆蓋的位置點所帶的語義詞頻為關鍵字，指向一個軌跡標識列表，該列表中存儲的是包含該語義信息的軌跡標識。中間結點存儲該結點覆蓋語義的降序詞頻區間，區間個數可由內存大小決定[5]。進行查詢時，通過判斷查詢語義的詞頻區間與結點詞頻區間的是否存在交集，對IT-tree的結點進行剪枝(詳見4.1節方法1)。表2是圖1中的軌跡所帶語義對應的詞頻，圖2是這3條軌跡構建的IT-tree，圖3是圖2的樹型結構示意圖，圖4示例了葉子結點N5中存儲的倒排表。

表2 詞頻映射表

圖2 IT-tree構建示例

圖3 IT-tree示意圖

圖4 葉子結點N5存儲的倒排表

S-tree：在IT-tree上進行查詢時，得到的是候選軌跡集。為進一步判斷候選軌跡是否包含查詢所需要的全部語義，需要對候選軌跡進一步求精，這正是S-tree的作用。S-tree的創建方法如下：通過從高到低排列的語義詞頻將連續的軌跡id劃分為若干不相交的區間段，各區間所攜帶的語義信息用bitmap表來表示。這里假設軌跡id均是數字類型，如果軌跡id不是數字類型可以先將其數字化。具體劃分方法如下：首先以是否包含最高語義詞頻為標準將軌跡id分為若干區間。例如，假設軌跡集包含10條軌跡，軌跡標識號為1～10，a為詞頻最高的語義，若Tr1-Tr3、Tr7-Tr10包含語義a，Tr4-Tr6不含語義a，則通過是否包含語義a可將軌跡標識號劃分為[1,3], [4,6], [7,10]三個區間。接著使用詞頻次高的語義進行劃分，與上述過程類似，若次高語義詞頻為b,則用b在由a劃分好的區間的基礎上再次進行劃分，可得含a、b，含a但不含b，不含a但含b以及不含a、b的多個軌跡段。區間劃分時，當語義詞頻總和達到90%時，劃分停止。為每個劃分好的區間建立bitmap表，按區間劃分時語義由高到低的次序，每一位置1表示該位代表的語義存在，置0表示該位代表的語義存在，由bitmap表可知軌跡中包含的語義，如圖5所示。所劃分軌跡區間作為輸入，根據線段樹建立的方法，建成平衡的二分線段樹，即S-tree。當從IT-tree中得到候選軌跡集后，以候選軌跡標識作為關鍵字搜索S-tree，鎖定軌跡id所在葉子結點區間。通過查看該區間的bitmap表，可知該軌跡是否包含全部詞頻在90%以內查詢語義。若查詢中包含詞頻小于10%的關鍵字，則在計算最短軌跡匹配距離之前查看軌跡活動列表結構，若所有詞頻小于10%的語義均有對應點，則進行下一步計算[5]。若候選軌跡包含所有查詢語義則進一步計算查詢點到候選軌跡的最短軌跡匹配距離。詳見4.1節方法2。

圖5 S-tree示例

4 k最近鄰查詢方法

方法遍歷ITS-tree獲取候選結果集，并計算候選結果集中軌跡的最短軌跡匹配距離。為防止出現查詢結果遺漏，進一步對可能符合要求的軌跡進行驗證，最終返回含有k條軌跡的結果集。

4.1 遍歷ITS-tree獲取候選軌跡集

方法利用best-first思想，首先在IT-tree上進行遍歷獲取滿足到某一個查詢點空間位置較近的k條軌跡。具體遍歷方法如下：遍歷過程維護隊列seq，seq中的元素以結點到各查詢點距離的最小值為排序關鍵字進行升序排序。首先將IT-tree的根結點放入隊列seq。當seq不為空時，取出隊頭。判斷是否存在查詢點的語義關鍵字對應的詞頻落入該結點的語義區間中，如果沒有則將這個結點及其分支過濾，否則，計算其孩子結點到各查詢點的空間最短距離，將其孩子結點按最短距離升序插入隊列中。當隊頭中取出的是葉子結點時，取出具體軌跡放入軌跡集中。持續進行遍歷，直至軌跡集中包含k條軌跡，具體見方法1。

接下來，利用S-tree檢查這k條軌跡是否滿足查詢語義的要求。針對每一條候選軌跡，若其包含查詢要求的所有語義則進一步計算最短匹配距離。具體來講，針對每一條候選軌跡，根據該軌跡的標識存在的葉子結點bitmap表，根據查詢Q中的每一個查詢語義在bitmap中對應位置是否為1判斷該軌跡是否包含該語義。若發現軌跡未包含全部查詢語義，則將該軌跡從軌跡集中刪去。當然，該方法無法判斷軌跡是否包含詞頻小于10%的查詢語義，可以遍歷軌跡活動列表，通過軌跡中是否有詞頻小于10%語義的對應點進行進一步判斷。然而，由于這些語義出現的概率較低，并不影響查詢方法的性能。對于滿足語義要求的軌跡計算最短軌跡匹配距離[5]，并插入候選結果集。

方法1遍歷IT-tree

1 輸入：IT-tree，seq

2 輸出：軌跡集

3 維護隊列seq存儲結點編號以及結點到查詢點距離

4 When 遍歷IT-tree

5 Node N=seq.pop()

6 檢查是否有查詢語義詞頻落在結點N的詞頻區間

7 if Y，計算孩子結點到當前查詢點距mD(cni,q)

8 將cni按當前查詢點距離的升序插入seq

9 else 刪除N

10 if (cn==null)

11 取出軌跡Tri

12 if (Tri未經過求精)

13 將Tri插入軌跡集

14 if (軌跡集軌跡數+候選集軌跡數=k)

15 return 軌跡集

若候選結果集中軌跡數i

方法2軌跡求精結果

1 輸入：軌跡集Q，k

2 輸出：top-k Tr

3 用方法1遍歷IT-Tree

4 When 取得軌跡集TR

5 if (所查詢語義均在90%詞頻范圍內)

6 遍歷TR中Tri的S-tree查看該軌跡是否包含全部查詢語義

7 else 遍歷TR中Tri的S-tree和APL結構確定軌跡包含全部查詢語義

8 if(Tri包含全部查詢語義)

9 計算該軌跡最短匹配距離Dmm(Q，Tri)

10 將Tri插入候選結果集CRS，刪除TR中的Tri

11 else 刪除Tri

12 if (CRS軌跡數i

13 得到候選結果集CRS

14 驗證并更新CRS，得到RS

15 return RS

4.2 候選軌跡求精及得到top-k軌跡

在4.1節中僅獲得的是距離某一個查詢點較近軌跡，包含距離一個查詢點最近鄰的軌跡不一定是距離所有查詢點的距離和最小的軌跡。因此，僅經過4.1節方法計算獲得的結果并不能覆蓋全部解。為確保沒有遺漏可行解，本節對當前未出現在候選結果集，但可能成為查詢結果的軌跡進行進一步求證。具體方法如下：以每個查詢點為圓心，以當前候選結果集中最大的軌跡匹配距離為半徑，在IT-tree上執行范圍查詢，查詢獲得的結果且未在現有候選結果集中出現的軌跡即是被遺漏的可行解。該可行解進行驗證，其驗證方法是：計算該軌跡與查詢的最短匹配距離，若該距離小于當前結果集中最大值，則將其依升序插入當前結果集，并刪去結果集中最后一條軌跡。重復這個過程直至最終得到含有top-k條軌跡的結果集。

5 示例分析

圖2為上文中的實例，設置k值為2，原始軌跡集中有Tr1,Tr2,Tr3三條軌跡，有2個查詢點q1，q2，查詢語義是{a,c,e}，其中q1查詢語義為{a,c}，q2查詢語義為{e}。建立圖3所示IT-tree。

計算出的IT-tree中各結點到查詢點的最短距離如表3所示。

表3 計算得各結點到查詢點的最短距離

查詢語義為{a,c,e}，其中c語義為語義詞頻小于10%的語義。首先將N1壓入隊列中，隨后取出隊列中第一個結點N1，所有查詢語義均在N1內，得到其三個子結點N2,N3,N4。計算其子結點到查詢點的距離插入隊列中，再取頭結點N2，由于{a,c}語義詞頻落入N2詞頻區間內，取N2孩子結點計算距離后插入隊列中。取隊頭結點N5，得到軌跡Tr1，Tr2插入候選軌跡集。此時候選軌跡數i=k,返回對軌跡進行求精。

遍歷S-tree至葉子結點可得Tr1的Bitmap表11111，包含語義{a,e}和Tr2的Bitmap表11110，不包含語義e，因此將Tr2刪除。用文獻[5]中計算Tr1的最短軌跡匹配距離，參照表1可知最短軌跡匹配距離為1.0+2.2+1.5+4.8=9.5，將Tr1插入結果集中。此時結果集中軌跡數為1，小于k，返回遍歷IT-tree。

取隊頭結點N3，語義{a,c,e}的詞頻落入的N3的詞頻區間，計算孩子結點N7、N8到各查詢點的距離插入隊列中。接著取隊頭結點N6，語義a的詞頻落入N6詞頻區間中，取出軌跡Tr1、Tr2，由于已經過遍歷，不對候選結果集進行更新。接下來取隊頭N7，語義c的詞頻落入N7的詞頻區間，取出軌跡Tr1，不對軌跡集進行更新。取隊頭N4，語義{a,e}落入其詞頻區間，取N4的孩子結點，計算距離插入隊列中。如此進行下去，可在 取到軌跡Tr3，返回Tr3進行驗證，在S-tree葉子結點中3所在區間可得Bitmap表11111，由軌跡活動列表不含c，將其刪除。由于遍歷結束，候選結果集中僅有Tr1。

檢驗：以q1、q2為圓心，當前結果集中軌跡Tr1的最短匹配距離8.0為半徑進行范圍查詢，檢驗從查詢范圍內覆蓋的葉子結點中取得的軌跡是否有未出現在結果集中的情況。重復求精過程，對結果集進行更新。由于本例中軌跡數量較少，因此僅有{Tr1}滿足要求。

本例中只針對每個查詢點對IT-tree進行一次遍歷。若使用文獻[5]工作提供的方法，則要分別針對語義a、c、e對索引結構進行多次遍歷，查詢代價較高。

時間代價分析：查詢方法主要分為兩個部分：第一部分是利用IT-tree和S-tree索引結構找出候選結果集。假設查詢點個數為|q|，n為軌跡數據集中點的個數，|D|為語義的值域中值的個數，算法的時間復雜度為O(|q||D|n2)。第二部分為根據候選結果集求解精確匹配距離，在該部分中，我們利用文獻[1]的匹配算法，所以時間代價與文獻[1]一致。

本文提出的方法可以進一步從下面兩個問題進行提高與改進。一是IT-tree是基于軌跡中的離散點來構建的，從IT-tree中得到候選軌跡存在重復計算的情況。此點增加軌跡訪問數組visit[]解決。二是雖然S-tree索引結構是基于語義詞頻占總詞頻的前90%的語義構建，但S-tree的高度依然是語義信息集合的值域|D|，當語義很多時，S-tree可能過高。此點可利用語義信息的詞頻分布降低S-tree索引結構的樹高，對查詢算法的效率做進一步優化提升。

6 結 語

本文針對旅游系統中的kNN語義軌跡查詢問題,介紹了相關背景及工作，提出ITS-tree索引以期通過改進索引結構和方法提高查詢的效率。IT-tree在R-tree索引空間信息的基礎上存儲區域點的語義信息，并通過葉子結點中的倒排表獲取候選軌跡；用S-tree結構來檢查軌跡是否滿足語義要求，提高了語義檢查的精確性。在進行查詢時通過同時考慮查詢點的所有語義，減少查找次數；使用查詢語義詞頻與中間結點詞頻區間是否存在交集，對IT-tree結點進行剪枝，提高查找效率。接下來的工作將進一步對索引及方法進行優化，驗證方法的有效性。

[1] 劉曉樂,李博. 隱私保護下的組最近鄰查詢算法研究[J]. 計算機應用與軟件,2016,33(5):302- 306.

[2] 林娜,鄭亞男. 基于出租車軌跡數據的路徑規劃方法[J]. 計算機應用與軟件,2016,33(1):68- 72.

[3] 肖艷麗,張振宇,楊文忠. 基于GPS軌跡的用戶移動行為挖掘算法[J]. 計算機應用與軟件,2015,32(11):83- 87.

[4] 李萬高. 路網中基于最短路徑的最近鄰查詢算法研究[J]. 計算機應用與軟件,2014,31(7):59- 61,68.

[5] Zheng K, Shang S, Yuan N J, et al. Towards efficient search for activity trajectories[C]//IEEE International Conference on Data Engineering. IEEE Computer Society, 2013:230- 241.

[6] Zheng B, Yuan N J, Zheng K, et al. Approximate keyword search in semantic trajectory database[C]//IEEE, International Conference on Data Engineering. IEEE, 2015:975- 986.

[7] Shang S, Ding R, Yuan B, et al. User oriented trajectory search for trip recommendation[C]//Proceedings of the 15th International Conference on Extending Database Technology—EDBT ’12. 2012:156- 167.

[8] 李晨, 申德榮, 朱命冬,等. 一種對時空信息的kNN查詢處理方法[J]. 軟件學報, 2016, 27(9):2278- 2289.

[9] 丁治明. 一種適合于頻繁位置更新的網絡受限移動對象軌跡索引[J]. 計算機學報, 2012, 35(7):1448- 1461.

[10] 宋曉宇, 許鴻斐, 孫煥良,等. 基于簽到數據的短時間體驗式路線搜索[J]. 計算機學報, 2013, 36(8):1693- 1703.

[11] Gao C, Lu H, Ooi B C, et al. Efficient Spatial Keyword Search in Trajectory Databases[DB]. eprint arXiv:1205.2880, 2012.

[12] Chen Y, Jiang K, Zheng Y, et al. Trajectory simplification method for location-based social networking services[C]//International Workshop on Location Based Social Networks, Lbsn 2009, November 3, 2009, Seattle, Washington, Usa, Proceedings. DBLP, 2009:33- 40.

[13] 趙苗苗. 基于出租車軌跡數據挖掘的推薦模型研究[D].北京:首都經濟貿易大學, 2015.

[14] Aljubayrin S, He Z, Zhang R. Skyline Trips of Multiple POIs Categories[C]//International Conference on Database Systems for Advanced Applications. Springer International Publishing, 2015:189- 206.

[15] Zheng B, Zheng K, Xiao X, et al. Keyword-aware continuous kNN query on road networks[C]//IEEE, International Conference on Data Engineering. IEEE, 2016:871- 882.

[16] Chen W, Zhao L, Xu J J, et al. Trip Oriented Search on Activity Trajectory[J]. Journal of Computer Science & Technology, 2015, 30(4):745- 761.