國防科學技術大學機電工程與自動化學院 張魯斌

基于空間填充曲線的軌跡熱點區(qū)域挖掘算法研究

國防科學技術大學機電工程與自動化學院 張魯斌

針對傳統(tǒng)的數(shù)據(jù)挖掘算法在處理海量的、復雜多樣且變化迅速的軌跡數(shù)據(jù)方面已不適用，難以對數(shù)據(jù)進行有效挖掘的問題，提出了一種基于空間填充曲線的軌跡熱點區(qū)域挖掘算法。首先研究了空間填充曲線，然后采用Z曲線把指定平面空間劃分成網(wǎng)格，在此基礎上將移動目標軌跡映射為網(wǎng)格序列，并以移動目標軌跡經(jīng)過網(wǎng)格的頻率標識網(wǎng)格的熱度，最后采用網(wǎng)格聚類的方法挖掘出熱點區(qū)域。該算法具有計算量低、靈活、可擴展等優(yōu)點，能有效勝任對海量軌跡數(shù)據(jù)的挖掘分析。

軌跡；網(wǎng)格；空間曲線；熱點區(qū)域

1.引言

隨著多種定位技術的快速發(fā)展和定位裝置的迅速普及，基于位置信息的軌跡數(shù)據(jù)爆發(fā)式增長。這些數(shù)據(jù)具有體量大、類型多樣、變化迅速等特點，要發(fā)揮這些數(shù)據(jù)的效用，挖掘其中蘊含的豐富信息，必須對大數(shù)據(jù)進行分析處理?，F(xiàn)有的軌跡數(shù)據(jù)挖掘研究包括頻繁模式挖掘[1]、伴隨模式挖掘[2]、軌跡聚類、分類[3]等，其中一項比較有現(xiàn)實意義的就是熱點區(qū)域挖掘[4]。熱點區(qū)域能反映目標在移動過程中對某地理區(qū)域的關注程度或依賴程度，也能一定地揭示目標的移動規(guī)律或行為模式?，F(xiàn)有研究往往通過已有的復雜聚類算法發(fā)現(xiàn)熱點區(qū)域，很少考慮大數(shù)據(jù)量分析時的計算效率，難以在實際中應用。

為了克服傳統(tǒng)算法的缺點，本文提出了一種基于空間填充曲線的網(wǎng)格聚類算法。該算法采用空間填充曲線將指定區(qū)域有序地劃分為若干不重疊的網(wǎng)格，在此基礎上將移動對象的軌跡映射為其經(jīng)過的網(wǎng)格，并以移動目標軌跡經(jīng)過網(wǎng)格的頻率標識網(wǎng)格的熱度，最后采用網(wǎng)格聚類的方法挖掘出熱點區(qū)域。

2.空間填充曲線劃分網(wǎng)格

圖1 Hilbert、Gray、Z曲線

空間填充曲線自1891年由希爾伯特正式提出之后得到了深入的研究和廣泛的應用[5～6]。從數(shù)學的角度講空間填充曲線是一類可以將高維數(shù)據(jù)空間映射成一維數(shù)據(jù)空間的方法，就像一條曲線一樣通過高維數(shù)據(jù)空間中的每一個離散的網(wǎng)格，且僅僅穿過每個網(wǎng)格一次。在高維空間向一維空間映射方法中最突出的包括Hilbert曲線、Z曲線和Gray曲線，如圖1所示。在3種空間填充曲線中，Hilbert空間填充曲線的數(shù)據(jù)聚類特性是最優(yōu)秀的，Z空間填充曲線的數(shù)據(jù)聚類特性是最差的；Hilbert空間填充曲線的映射算法的執(zhí)行過程是最復雜的，Z空間填充曲線的映射算法的執(zhí)行過程是最簡單的[7～9]。為了滿足大數(shù)據(jù)量對計算效率的要求，本算法采用Z曲線對目標區(qū)域進行劃分。

定義1：Z曲線網(wǎng)格劃分：指定平面區(qū)域，將其表達為二維空間S，采用Z空間填充曲線對其進行第1次逼近操作劃分為22個等份網(wǎng)格；進行第2次逼近操作即把第1次逼近生成的每個網(wǎng)格分成22個，共24個網(wǎng)格；依此類推，進行第k次逼近操作劃分為22k個等份網(wǎng)格，則S={G0,G1,…,Gn-1},n=22k，k≥1。網(wǎng)格序號沿著緯度經(jīng)度增長方向從0開始編號，與網(wǎng)格一一對應。將有鄰邊或對角相接的網(wǎng)格定義為相鄰的網(wǎng)格，稱為網(wǎng)格的鄰域。

從Z空間填充曲線的映射過程可以推導出其具有網(wǎng)格之間是層層嵌套和網(wǎng)格的標識符是由其對應的上層網(wǎng)格的標識符逐層串聯(lián)在一起產生的兩個特點[10]。這就決定了Z曲線在算法生成、鄰域計算等方面具有良好的性能。

3.熱點區(qū)域提取

3.1 軌跡網(wǎng)格化

定義2：軌跡網(wǎng)格序列：在計算空間S中，由于任意位置P都有唯一的網(wǎng)格G與之對應，因此軌跡可以映射為一系列連續(xù)的網(wǎng)格，稱為網(wǎng)格序列，記作Trff=(G1,…,Gn)。

由于軌跡數(shù)據(jù)是離散采樣的，需要計算相鄰離散點之間的網(wǎng)格序列。對于飛機、船舶和車輛等采樣間隔較小且通常直線運動的目標，可將兩軌跡點連線經(jīng)過的單元格視為其網(wǎng)格序列。假設移動對象在二維坐標中給定的兩個連續(xù)的軌跡點Pk和Pt，對應的網(wǎng)格序號分別是Gk和Gt。計算點Pk與Pt間子軌跡段網(wǎng)格序列Trffi（PkPt）算法設計如下：（1）計算軌跡點Pk所在單元格Gk的4個頂點的經(jīng)緯度坐標Pk1（x1，y1）、Pk2（x2，y2）、Pk3（x3，y3）、Pk4（x4，y4）。（2）依次判斷線段PkPt與Gk的4個邊Pk1Pk2、Pk2Pk3、Pk3Pk4、Pk4Pk1是否相交，沒有交點則可判定Gk等于Gt，計算停止；有交點,若交點是Gk的頂點，如圖2（a）所示，則計算以此頂點與Gk相鄰的網(wǎng)格，若交點不是頂點，如圖2（b）所示，計算出以此交點所在邊與Gk相鄰的網(wǎng)格，記作Gm，則可判斷Gm∈Trffi（PkPt）。（3）以Gm代替Gn重復步驟1、2，計算出Gm與PnPn+1另一個交點對應的相鄰網(wǎng)格Gm+1∈Trffi（PkPt）。（4）重復步驟3直至結束。

圖2 計算網(wǎng)格序列的兩種情況

經(jīng)過以上步驟可計算出子軌跡PkPt的網(wǎng)格序列Trffi（PkPt），對每一段子軌跡做同樣操作獲取其網(wǎng)格序列，則整條軌跡的網(wǎng)格序列就是各個子軌跡網(wǎng)格序列的并集。

3.2 頻繁訪問單元格匯聚

定義3：單元格被訪問頻率Freq（G）：單位時間內單元格G被所有移動目標的軌跡經(jīng)過的次數(shù)，可表示為：

定義4：核心單元格：若某個單元格被訪問的頻率大于等于設置的閾值δ1，則稱該單元格為核心單元格；重要單元格：若某個單元格被訪問的頻率大于等于設置的閾值δ2且小于δ1，則稱該單元格為重要單元格。以此來表示單元格的等級Flag(G)。

在實際過程中，某個區(qū)域往往由幾個單元格組成，而單元格本身只是由Z曲線劃分獲得的不重疊的子區(qū)域，需要對符合條件的單元格進行聚類，組合成熱點區(qū)域。本文熱點區(qū)域聚類的原則如下：（1）若核心網(wǎng)格的鄰域中含有核心網(wǎng)格，那么該熱點區(qū)域為包含這些核心網(wǎng)格的最小外接矩形；（2）若重要網(wǎng)格的鄰域中存在不相鄰的若干核心網(wǎng)格或熱門區(qū)域，那么更新后的熱點區(qū)域應為包含上述網(wǎng)格的最小外接矩形；（3）若兩個熱點區(qū)域存在相交區(qū)域，更新后的熱點區(qū)域為包含上述區(qū)域的最小外接矩形。

每個步驟重復執(zhí)行，直到?jīng)]有更新再執(zhí)行下一步驟。通過最小外接矩形框定熱門區(qū)域符合使用習慣，也可以通過最小區(qū)域或其他圖形來框定。本算法具有較好的數(shù)據(jù)累加性，增加新數(shù)據(jù)不需要重新計算，只需要在上次執(zhí)行結果上作計算。

4.測試

采用本文算法對舊金山車輛GPS軌跡數(shù)據(jù)的實驗結果如圖3所示。