邱 磊，吳志兵

(江南計(jì)算技術(shù)研究所，江蘇 無錫 214083)

0 引 言

隨著傳感器技術(shù)和定位技術(shù)的發(fā)展，基于位置的服務(wù)應(yīng)用越來越廣泛。人類活動(dòng)通過智能手機(jī)APP應(yīng)用軟件進(jìn)行位置分享、簽到等；車輛安裝GPS或北斗定位系統(tǒng)，周期性地上報(bào)位置信息；動(dòng)物學(xué)家記錄動(dòng)物的遷徙路徑等等。在這些活動(dòng)中產(chǎn)生了一系列軌跡數(shù)據(jù)，隨著時(shí)間的推移，數(shù)據(jù)規(guī)模愈加龐大。

對于海量軌跡數(shù)據(jù)的挖掘，可以獲得大量有價(jià)值信息。例如，對車輛軌跡數(shù)據(jù)分析研究獲取駕駛行為與交通路網(wǎng)之間的相關(guān)性[1]；對智能手機(jī)定位軌跡數(shù)據(jù)分析得到用戶的移動(dòng)特點(diǎn)和生活規(guī)律[2]；對旅行軌跡數(shù)據(jù)分析向用戶推薦滿足不同需求的路徑[3]。軌跡數(shù)據(jù)挖掘常常依賴于大量的軌跡查詢行為。軌跡查詢分為KNN(k-nearest neighbor)查詢和范圍查詢，而KNN查詢又分為軌跡點(diǎn)查詢和整條軌跡的查詢。查詢的第一步是定義兩條軌跡的距離，也就是軌跡之間的相似度[4]。

傳統(tǒng)的海量軌跡數(shù)據(jù)查詢基于樹結(jié)構(gòu)進(jìn)行索引，當(dāng)軌跡較短，即維度較少時(shí)性能良好，但是隨著維度的增加(比如20維以上)，檢索效率會(huì)急劇下降，在性能上甚至還不如對整個(gè)數(shù)據(jù)集合進(jìn)行順序檢索，這就是高維空間數(shù)據(jù)處理都會(huì)遇到的“維數(shù)災(zāi)難”[5]問題，從而導(dǎo)致難以實(shí)現(xiàn)軌跡的快速查詢。局部敏感哈希技術(shù)[6](locality sensitive hashing，LSH)是解決高維數(shù)據(jù)近鄰查詢的有效方法。傳統(tǒng)的LSH采用漢明距離來實(shí)現(xiàn)近鄰數(shù)據(jù)的快速查詢，所以在實(shí)際應(yīng)用中需要首先將數(shù)據(jù)嵌入到漢明空間，大大增加了計(jì)算的復(fù)雜度。目前在大規(guī)模數(shù)據(jù)高維近鄰索引中，一般采用LSH在歐氏空間中的一種隨機(jī)化方法，被稱為精確局部敏感哈希(exact Euclidean locality sensitive hashing，E2LSH)[7]。LSH技術(shù)在很多領(lǐng)域獲得了成功應(yīng)用，例如大規(guī)模網(wǎng)頁的去重、海量圖片搜索以及相似音視頻的檢索等等。

綜上，文中提出了一種支持海量軌跡數(shù)據(jù)的KNN查詢算法(trajectory E2LSH-based KNN query，TRA-EKNN)。首先研究軌跡大數(shù)據(jù)的向量空間建模問題，并結(jié)合特定領(lǐng)域的興趣點(diǎn)(point of interest，POI)進(jìn)行了初步降維，進(jìn)而采用E2LSH算法實(shí)現(xiàn)軌跡數(shù)據(jù)的索引構(gòu)建，并在合成數(shù)據(jù)以及實(shí)際數(shù)據(jù)集上進(jìn)行KNN查詢，最后對實(shí)驗(yàn)結(jié)果進(jìn)行了分析和總結(jié)，并展望了后續(xù)工作。

1 相關(guān)工作

對于軌跡數(shù)據(jù)的KNN查詢算法，根據(jù)查詢結(jié)果的可靠性，可以分為兩類：基于時(shí)空數(shù)據(jù)庫索引的窮舉算法和基于哈希的近似算法。

目前，對于軌跡數(shù)據(jù)的查詢研究多基于窮舉算法。時(shí)空數(shù)據(jù)庫[8](spatio-temporal databases，STDB)將時(shí)間和空間有機(jī)結(jié)合，實(shí)現(xiàn)對時(shí)空對象的有效管理。由于R樹以及改進(jìn)樹[9]在空間索引的巨大優(yōu)勢，被大多時(shí)空索引結(jié)構(gòu)所采用。近似算法在允許一定誤差的前提下，可以大大提高檢索性能。在海量數(shù)據(jù)日益增多的情況下，近似算法受到研究者的廣泛關(guān)注。在近似算法中，應(yīng)用最為廣泛的是基于哈希的檢索技術(shù)。Athitsos等[10]定義并實(shí)現(xiàn)了一種全新的基于距離的哈希算法(distance-based hashing，DBH)。Sanchez等[11]提出了一種基于LSH算法的軌跡聚類算法。這兩種算法都將軌跡視為連續(xù)的軌跡點(diǎn)，即一條曲線，因此計(jì)算過程中均沒有考慮時(shí)間因素，不適應(yīng)于嚴(yán)格定義的軌跡數(shù)據(jù)。

國內(nèi)學(xué)者對LSH技術(shù)在軌跡數(shù)據(jù)分析中的應(yīng)用也做了大量相關(guān)研究。趙家石等[12]采用局部敏感哈希技術(shù)尋找在一定時(shí)間內(nèi)都相似的移動(dòng)對象，從而避免傳統(tǒng)方法的交集運(yùn)算過程，實(shí)現(xiàn)軌跡相似度的快速估計(jì)。廖律超等[13]利用譜哈希實(shí)現(xiàn)對交通路網(wǎng)的快速聚類，挖掘出交通軌跡大數(shù)據(jù)的潛在特性，為交通規(guī)劃提供了科學(xué)依據(jù)。印桂生等[14]將文本相似領(lǐng)域比較廣泛應(yīng)用的相似哈希(simhash)[15]技術(shù)應(yīng)用到用戶軌跡的相似性比較中，取得了較好效果。

2 TRA-EKNN算法

2.1 相關(guān)定義

文中所研究的問題是在海量的軌跡大數(shù)據(jù)中，根據(jù)一條軌跡數(shù)據(jù)查詢找出距離最近，也就是最相似的k條軌跡。

定義1：軌跡是由移動(dòng)對象在增量時(shí)間的一系列軌跡點(diǎn)組成，記為：

TR={P1,P2,…,Pn}

其中Pi是移動(dòng)對象在t時(shí)刻的位置(用經(jīng)緯度表示)，即pi=(lat,lng,t)。

定義2：網(wǎng)格空間是指對參與計(jì)算的地理空間進(jìn)行劃分編碼形成的網(wǎng)格集合，記為：

G={gid1,gid2,…,gidm}

其中g(shù)idi表示編號(hào)為i的網(wǎng)格。地理空間可以是一個(gè)國家、一個(gè)城市，也可以是結(jié)合特定領(lǐng)域知識(shí)和含義進(jìn)行篩選之后區(qū)域范圍。

定義3：網(wǎng)格序列[16-17]是指一條軌跡將經(jīng)過的網(wǎng)格順序排列之后的集合，記為：

GS={g1,g2,…,gm}

其中g(shù)i=(gid,t)，即在網(wǎng)格gid停留時(shí)間為t。

2.2 算法思想

TRA-EKNN算法主要包括網(wǎng)格索引建立、軌跡向量建模和KNN查詢實(shí)現(xiàn)等過程，具體流程如圖1所示。

2.2.1 網(wǎng)格建立

網(wǎng)格索引建立是針對特定領(lǐng)域的POI集合計(jì)算每個(gè)地理位置的網(wǎng)格編號(hào)，然后合并形成一個(gè)網(wǎng)格空間G。

文中采用GeoHash技術(shù)實(shí)現(xiàn)網(wǎng)格的編碼。GeoHash通過使用一個(gè)字符串同時(shí)表示經(jīng)度和緯度兩個(gè)坐標(biāo)，是一種通用的地址編碼方案，具有如下特點(diǎn)：將二維空間的經(jīng)緯度編碼成一個(gè)字符串，在傳統(tǒng)的數(shù)據(jù)庫中做到一維的高效索引；每一個(gè)GeoHash表示的不是一個(gè)點(diǎn)，而是一個(gè)矩形的區(qū)域；GeoHash編碼的前綴可以用來表示更大范圍的區(qū)域。

GeoHash的計(jì)算方法主要分為三步：

(1)經(jīng)緯度轉(zhuǎn)換為二進(jìn)制。首先將全部的緯度范圍(-90,90)平均分為區(qū)間(-90,0)和(0,90)，如果目標(biāo)維度位于第一個(gè)區(qū)間，則編碼為0，否則為1，例如39.923 24屬于(0,90)，取編碼為1。然后再將(0,90)分為區(qū)間(0,45)和(45,90)，而39.923 24位于(0,45)，編碼為0。以此類推，直到精度符合要求為止，最終得到緯度的編碼1011 1000 1100 0111 1001。經(jīng)度也采用同樣算法得到編碼。

圖1 TRA-EKNN算法框架

(2)按照經(jīng)緯度的二進(jìn)制合并。按照緯度在奇數(shù)位，經(jīng)度在偶數(shù)位的規(guī)則進(jìn)行合并。

(3)進(jìn)行Base32編碼。編碼字符使用0-9和b-z(其中去掉a,i,l,o四個(gè)字母)。

由以上的GeoHash計(jì)算過程，可以知道精度取決于編碼長度，根據(jù)實(shí)際需求采用不同長度的編碼，二者的對應(yīng)關(guān)系如表1所示。

表1 GeoHash編碼長度與精度

通過將地理位置編碼，實(shí)現(xiàn)了對地理空間的網(wǎng)格索引。在此過程中，根據(jù)不同的應(yīng)用場景采用不同的編碼長度，實(shí)現(xiàn)效率與精度的統(tǒng)一。將所有特定領(lǐng)域的POI數(shù)據(jù)經(jīng)過GeoHash編碼，可以得到網(wǎng)格空間G，相比于直接將所有的空間都進(jìn)行編碼，此方法利用了數(shù)據(jù)融合的思想，從而大大減少了網(wǎng)格數(shù)量，實(shí)現(xiàn)初步降維，在后續(xù)的計(jì)算過程中也更具實(shí)際意義。

2.2.2 軌跡向量建模

借鑒文本分類中向量空間模型(VSM)[18]的思想，將網(wǎng)格空間G視為n維向量的維度，本小節(jié)基于此，將軌跡向量化，然后再進(jìn)行軌跡的距離計(jì)算。

軌跡網(wǎng)格序列化算法是向量建模的關(guān)鍵。將原始軌跡數(shù)據(jù)轉(zhuǎn)換為網(wǎng)格序列，可以在保證一定精度的前提下，簡化軌跡的處理過程。

算法1：軌跡網(wǎng)格化。

輸入：軌跡TR={P1,P2,…,Pn}

網(wǎng)格空間G={gid1,gid2,…,gidm}

輸出：網(wǎng)格序列GS={g1,g2,…,gm}

其中g(shù)i=(gid,t)

詳細(xì)過程：

1.foreachPiin TR

2.if(i==1)

3.last_time=Pi.t

4.last_geo=geohash(pi.lat,pi.lng)

5.continue

6.g.gid=geohash(Pi.lat,Pi.lng)

7.t_interval=Pi.t-last_time //時(shí)間差

8.if(g.gid inG)//只處理位于網(wǎng)格空間的數(shù)據(jù)

9.if(g.gid==last_geo)

10.t_stay=t_stay+t_interval

11.else//進(jìn)入另一網(wǎng)格

12.if(g.gid in GS)

13.Break// 截?cái)嗵幚?/p>

14.g.t=t_stay+t_interval/2

15.GS.append(g) //當(dāng)前點(diǎn)加入序列

16.t_stay=t_interval/2

17.OUTPUT(GS)

算法1描述了軌跡轉(zhuǎn)換為網(wǎng)格序列的全過程。最終的輸出包含軌跡所經(jīng)過的網(wǎng)格編碼和相應(yīng)的停留時(shí)間。由于采樣時(shí)間的差異，導(dǎo)致在同一個(gè)區(qū)域可能出現(xiàn)多個(gè)軌跡點(diǎn)。停留時(shí)間的計(jì)算需要考慮兩種情況：(1)兩個(gè)軌跡點(diǎn)位于同一個(gè)網(wǎng)格時(shí)，間隔時(shí)間直接累加；(2)前后兩個(gè)軌跡點(diǎn)位于不同網(wǎng)格，則停留時(shí)間按時(shí)間間隔的一半累加。從后續(xù)工作中可以看到，軌跡的向量化意味著軌跡網(wǎng)格不允許出現(xiàn)重復(fù)，所以算法1進(jìn)行了簡單處理即軌跡截?cái)?，另外一種方法是將后續(xù)軌跡點(diǎn)當(dāng)作另一條軌跡繼續(xù)處理。

經(jīng)過算法1的處理，軌跡轉(zhuǎn)換為在選定領(lǐng)域(網(wǎng)格空間)的網(wǎng)格序列?；诖?，可以構(gòu)建軌跡的向量矩陣[13]，其中矩陣的行對應(yīng)于全部的網(wǎng)格空間，列對應(yīng)于每條軌跡。假設(shè)軌跡數(shù)據(jù)經(jīng)過算法1的計(jì)算，提取出了r條軌跡，相應(yīng)的網(wǎng)格空間大小為n，則構(gòu)成一個(gè)n×r的“網(wǎng)格-軌跡”矩陣T，每個(gè)元素的值定義為軌跡點(diǎn)在對應(yīng)網(wǎng)格停留時(shí)間。

將軌跡進(jìn)行以上處理之后，可以據(jù)此定義兩條軌跡向量的距離：

(1)

軌跡的網(wǎng)格空間可以理解為針對特定領(lǐng)域所關(guān)心的所有位置，也就是在軌跡的距離(相似)公式中參與計(jì)算的位置，其他非必要的位置不參與計(jì)算。相比于通過聚類方法提取POI(興趣點(diǎn))的方法，大大降低了數(shù)據(jù)預(yù)處理過程的難度和時(shí)間消耗。

2.2.3 E2LSH算法索引構(gòu)建

E2LSH是LSH在歐氏空間的一種隨機(jī)化實(shí)現(xiàn)方案。基本的思路是：采用基于p穩(wěn)定分布的局部敏感函數(shù)對原始的高維數(shù)據(jù)進(jìn)行降維映射?？梢钥闯?，E2LSH繼承了LSH的特點(diǎn)，即在原始空間相鄰的數(shù)據(jù)，經(jīng)過哈希之后，在新的空間上存在很大的概率也相近，具體哈希函數(shù)如下：

(2)

其中，a是獨(dú)立隨機(jī)選擇的d維向量，b為范圍[0,w]的一個(gè)隨機(jī)數(shù)。函數(shù)h將一個(gè)d維向量映射到一個(gè)整數(shù)集，然后以w為寬度進(jìn)行等距離劃分。E2LSH將k個(gè)哈希函數(shù)聯(lián)合使用，稱之為函數(shù)族：

(3)

函數(shù)族g對應(yīng)于L個(gè)哈希表，隨機(jī)獨(dú)立選取的k個(gè)h函數(shù)又構(gòu)成了每個(gè)g函數(shù)，函數(shù)的值對應(yīng)具體的哈希桶。

從算法思想的本質(zhì)上看，LSH是不確定的，概率性的，可以歸結(jié)為近似算法。隨著數(shù)據(jù)規(guī)模越來越大，數(shù)據(jù)處理的時(shí)效性要求面臨很大挑戰(zhàn)，這時(shí)通過犧牲一定精度以獲得更快的處理速度，在一些領(lǐng)域是可行而有效的。本節(jié)將此算法應(yīng)用于軌跡數(shù)據(jù)索引的構(gòu)建，具體過程如下：

(1)對于數(shù)據(jù)庫中的軌跡，經(jīng)過算法1得到一條包含停留時(shí)間的網(wǎng)格序列；

(2)對于每條網(wǎng)格序列，由式(3)得到長度為k的哈希桶，計(jì)算L次，組成L個(gè)哈希表；

(3)對哈希表中的每個(gè)桶生成一個(gè)索引文件。

2.2.4 KNN查詢實(shí)現(xiàn)

KNN查詢的目標(biāo)是在軌跡數(shù)據(jù)中找到與查詢軌跡TR距離最近的k條軌跡。傳統(tǒng)的線性算法通過計(jì)算待查詢TR與所有的軌跡的距離，然后從中選出最近的k條軌跡，顯然在這過程中計(jì)算量十分的巨大。雖然可以采用R-Tree、KD-Tree等樹結(jié)構(gòu)進(jìn)行優(yōu)化，但是“維數(shù)災(zāi)難”的問題，使得軌跡點(diǎn)數(shù)較多時(shí)，存在著大量的回溯計(jì)算，導(dǎo)致樹結(jié)構(gòu)不能發(fā)揮作用，這時(shí)退化成線性運(yùn)算。

本算法在上一節(jié)構(gòu)建好軌跡數(shù)據(jù)的E2LSH索引的基礎(chǔ)上進(jìn)行查詢，具體流程如下：

(1)運(yùn)用算法1得到所要查詢的軌跡對應(yīng)的網(wǎng)格序列；

(2)計(jì)算待查詢網(wǎng)格序列的L個(gè)哈希表索引；

(3)遍歷哈希表，找到對應(yīng)的哈希桶，對桶內(nèi)的軌跡，利用式(1)計(jì)算對應(yīng)的距離，返回最近的k條軌跡。

本算法使用E2LSH技術(shù)，首先將所有的軌跡數(shù)據(jù)按照距離劃分到不同的哈希桶，同一個(gè)哈希桶的軌跡距離較近，所以KNN查詢只需要根據(jù)不同哈希值比較同一個(gè)或者相近桶內(nèi)的軌跡，從而極大地減少了需要計(jì)算比較的軌跡數(shù)量，使得海量軌跡的KNN查詢效率得到有效提升。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)采用兩個(gè)數(shù)據(jù)集：合成數(shù)據(jù)用來檢測算法的時(shí)間效率，并與傳統(tǒng)查詢算法進(jìn)行對比；上海出租車軌跡數(shù)據(jù)用來證明算法在實(shí)際應(yīng)用中的有效性。實(shí)驗(yàn)環(huán)境為單機(jī)，處理器為Intel(R) Core(TM) i3 M 380 @ 2.53 GHz，內(nèi)存6 G，操作系統(tǒng)為Windows7 64位 SP1，采用python語言編程實(shí)現(xiàn)。

3.1 合成數(shù)據(jù)實(shí)驗(yàn)

本實(shí)驗(yàn)的合成軌跡數(shù)據(jù)，根據(jù)網(wǎng)格數(shù)量和軌跡停留時(shí)間隨機(jī)生成。假設(shè)網(wǎng)格數(shù)量為m，軌跡數(shù)量為n，根據(jù)m和n的不同取值，查詢某條軌跡的最近10條軌跡，消耗時(shí)間如圖2所示。

其中10 000*10 000表示10 000條軌跡對應(yīng)于10 000個(gè)網(wǎng)格空間?？梢钥闯鰰r(shí)間消耗與二者的乘積大致是一個(gè)線性關(guān)系，隨著網(wǎng)格空間的增大和軌跡數(shù)量的增多，計(jì)算所消耗的時(shí)間成線性增長。

圖2 窮舉消耗時(shí)間對比

采用TRA-EKNN算法對上述數(shù)據(jù)進(jìn)行KNN查詢，根據(jù)文獻(xiàn)[6]中的建議值，算法中w取值為4，k取80，L取10，此時(shí)獲得的準(zhǔn)確率大于95%，時(shí)間消耗如圖3所示。

圖3 TRA-EKNN消耗時(shí)間對比

從圖3可知，TRA-EKNN算法中，時(shí)間消耗主要分索引建立和軌跡查詢兩部分，而且索引的建立時(shí)間遠(yuǎn)大于查詢時(shí)間，而且當(dāng)網(wǎng)格空間固定即軌跡的維度相同時(shí)，軌跡的數(shù)量只影響索引的建立時(shí)間，而查詢時(shí)間基本相同。

在實(shí)際的應(yīng)用中，一般要先將海量的軌跡建立索引，圖1所示的查詢算法框架也體現(xiàn)了這一點(diǎn)。在后續(xù)的KNN查詢時(shí)間一般指的就是圖3中的查詢時(shí)間，也就是說在進(jìn)行軌跡查詢之前索引已經(jīng)建立完畢，查詢過程中無需關(guān)心E2LSH索引的建立時(shí)間。對比圖2可以看出，本算法的查詢時(shí)間消耗明顯小于窮舉算法。

3.2 上海出租車軌跡數(shù)據(jù)實(shí)驗(yàn)

上海市出租車數(shù)據(jù)集，采集了2007年2月20日當(dāng)天4 316臺(tái)出租車的GPS記錄信息，包括出租車標(biāo)識(shí)、時(shí)間戳、經(jīng)緯度、瞬時(shí)速度、順時(shí)針角度以及載客情況等。本實(shí)驗(yàn)只取標(biāo)識(shí)、時(shí)間戳和經(jīng)緯度三個(gè)信息。

根據(jù)采集到的上海市交通相關(guān)的POI數(shù)據(jù)共計(jì)242 556條，考慮到實(shí)驗(yàn)數(shù)據(jù)是出租車GPS軌跡結(jié)合表1的GeoHash長度與精度關(guān)系，哈希長度設(shè)定為7，誤差約為76米，將POI數(shù)據(jù)中的經(jīng)緯度計(jì)算GeoHash，去重后，共計(jì)有71 495個(gè)網(wǎng)格。上海面積約為6 340平方公里，如果全部進(jìn)行7位的GeoHash編碼，大約一百萬個(gè)網(wǎng)格(由于行政區(qū)劃的不規(guī)則，數(shù)據(jù)不準(zhǔn)確，在此僅進(jìn)行估算)?？梢钥闯鲇捎诮Y(jié)合了交通領(lǐng)域的POI數(shù)據(jù)，使得網(wǎng)格空間大幅壓縮。

對出租車軌跡采用算法1進(jìn)行處理，共提取有效軌跡對應(yīng)的網(wǎng)格序列1 896條，由于出租車行駛過程中會(huì)出現(xiàn)司機(jī)休息和等待乘客等情況，停留時(shí)間會(huì)比較長，為了體現(xiàn)軌跡比較的實(shí)際意義，將停留時(shí)間大于二十分鐘的軌跡截?cái)?，然后將其余軌跡的停留時(shí)間作歸一化處理。

采用TRA-EKNN算法，對所有的軌跡數(shù)據(jù)建立E2LSH索引，經(jīng)過多次試驗(yàn)，此算法可以在較短的時(shí)間內(nèi)查詢出KNN結(jié)果，并有較高的準(zhǔn)確率。

3.3 算法分析

正如前文所述，時(shí)空軌跡數(shù)據(jù)的KNN算法主要是基于傳統(tǒng)的窮舉算法，即采用一一匹配的暴力搜索的方式進(jìn)行，此時(shí)時(shí)間復(fù)雜度是線性的，即○(N)。隨著數(shù)據(jù)規(guī)模越來越大，這種方式會(huì)消耗大量的時(shí)間。

文中提出的TRA-EKNN算法，首先建立了LSH索引，雖然帶來了空間消耗增加的問題，但檢索的時(shí)間復(fù)雜度降為了○(logN)，這對于一些時(shí)效性要求較高的場景是完全適用的。

4 結(jié)束語

將在海量文本、音頻、視頻數(shù)據(jù)處理廣泛應(yīng)用的E2LSH算法引入到軌跡數(shù)據(jù)的KNN查詢中。首先針對不同的應(yīng)用場景，結(jié)合特定領(lǐng)域POI數(shù)據(jù)建立網(wǎng)格空間；然后對軌跡數(shù)據(jù)進(jìn)行預(yù)處理，構(gòu)造出軌跡的網(wǎng)格向量，利用E2LSH算法實(shí)現(xiàn)索引。從圖1算法的實(shí)現(xiàn)框架來看，對于增量的軌跡只需要計(jì)算哈希值，然后插入索引即可，計(jì)算簡單。實(shí)驗(yàn)結(jié)果表明，在保證一定的準(zhǔn)確率的情況下，該算法有效降低了軌跡KNN查詢時(shí)間。下一步將繼續(xù)對軌跡的特征提取方法進(jìn)行探索，找出更適合軌跡數(shù)據(jù)處理的向量空間構(gòu)建方案，使此方法能夠在海量的軌跡數(shù)據(jù)挖掘中得到更廣泛的應(yīng)用。