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

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

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

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

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

軌跡；網格；空間曲線；熱點區域

1.引言

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

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

2.空間填充曲線劃分網格

圖1 Hilbert、Gray、Z曲線

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

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

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

3.熱點區域提取

3.1 軌跡網格化

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

由于軌跡數據是離散采樣的，需要計算相鄰離散點之間的網格序列。對于飛機、船舶和車輛等采樣間隔較小且通常直線運動的目標，可將兩軌跡點連線經過的單元格視為其網格序列。假設移動對象在二維坐標中給定的兩個連續的軌跡點Pk和Pt，對應的網格序號分別是Gk和Gt。計算點Pk與Pt間子軌跡段網格序列Trffi（PkPt）算法設計如下：（1）計算軌跡點Pk所在單元格Gk的4個頂點的經緯度坐標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相鄰的網格，若交點不是頂點，如圖2（b）所示，計算出以此交點所在邊與Gk相鄰的網格，記作Gm，則可判斷Gm∈Trffi（PkPt）。（3）以Gm代替Gn重復步驟1、2，計算出Gm與PnPn+1另一個交點對應的相鄰網格Gm+1∈Trffi（PkPt）。（4）重復步驟3直至結束。

圖2 計算網格序列的兩種情況

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

3.2 頻繁訪問單元格匯聚

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

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

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

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

4.測試

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