面向時空數據的多粒度結構化表示

夏增剛 丁夏蕾 王亮

摘要：針對時空感知數據在時間、空間維度分布不均衡所導致的問題，本文提出了3DTree的時空多粒度結構。進而以不同平臺、不同類型、不同地域的數據集實驗驗證了所提出的時空多粒度結構化表示方法的穩定性、有效性及普適性。

關鍵詞：時空數據;多粒度;數據表示

中圖分類號：TP302 文獻標識碼：A 文章編號：1007-9416（2020）03-0232-01

0 引言

在現實場景中，由于人口分布、區域功能定位等原因，導致所獲取到的時空數據在時間-空間上具有極強的分布不均衡性[1]。不均衡的時空數據若是采用等粒度的時空結構表示索引[2]，會造成索引效率的低下、所挖掘到的知識/模式精度往往不高等問題。而多粒度的數據表示方法可以很好的解決上述問題。

1 時空多粒度數據表示研究現狀

目前，空間數據多粒度結構化表示方法的研究與應用已有部分成果。Chao C等[2]將出租車軌跡轉化為空間等網格序列檢測異常軌跡。Yu W等[3]以等網格為基礎實現出行模式挖掘。王亮等[4]提出彈性多尺度空間劃分方法。Andy Y X等[5]比較了空間等網格，Q網格及空間KDTree在目的地預測中的影響。考慮到時間-空間三維度上的復雜特性，本文提出時空多粒度結構化數據表示方法。

2 3Dtree時空多粒度描述

時空多粒度是將經度、緯度、時間統一分析，3DTree劃分步驟如下：

算法1.3DTree時空多粒度劃分，如圖1所示。

輸入：3維時空數據集，其中 劃分深度dep;

輸出：個空間長方體的坐標。

步驟1.劃分維度的選擇。在（lon，lat，t）中選擇一個維度。

步驟2.以為坐標軸，以T中所有實例的坐標對數據集快速排序，將數據長度1/2位置的點作為切分點，將數據集劃分為左子區域和右子區域。

步驟3.將左子區域和右子區域分別作為數據集，重復Step1-2遞歸地實現時空多粒度的劃分。

步驟4.保存深度為dep的個空間長方體的坐標。

3 實驗驗證

本文數據集：成都市滴滴打車平臺一個月的訂單數據，成都市出13606輛租車一天軌跡數據，深圳市13698輛出租車一天軌跡數據。

（1）時空多粒度表示結構的統計量分布實驗。二維劃分方法深度取10，三維方法深度取14。實驗結果如表1。

從表1可以看出三維多粒度表示結構比二維結構的信息熵和方差小，劃分的區域分辨率更高。

（2）不同平臺、不同類型、不同地域實驗。

從表2、3可以看出：三維方法構建的多粒度結構更穩定，時空多粒度表示結構的確定性和對數據分布表示的能力更強。

4 結語

本文針對傳統時空數據表示對時間屬性考慮不足的問題，從數據的時空分布出發提出了3DTree方法，并且實驗驗證了本文方法的有效性、穩定性和普適性。

參考文獻

[1] Piotr S.Maciag.Efficient Discovery of Sequential Patterns from Event-Based Spatio-Temporal Data by Applying Microclustering Approach[M]//Intelligent Methods and Big Data in Industrial Applications，2019.

[2] Chen C，Zhang D，Castro P S，et al.iBOAT：Isolation-Based Online Anomalous Trajectory Detection[J].IEEE Transactions on Intelligent Transportation Systems，2013，14（2）：806-818.

[3] Yu W.Discovering Frequent Movement Paths From Taxi Trajectory Data Using Spatially Embedded Networks and Association Rules[J].IEEE Transactions on Intelligent Transportation Systems，2018（99）：1-12.

[4] 王亮，胡琨元，庫濤，等.基于多尺度空間劃分與路網建模的城市移動軌跡模式挖掘[J].自動化學報，2015，41（1）：47-58.

[5] Xue A Y，Qi J，Xie X，et al.Solving the data sparsity problem in destination prediction[J].Vldb Journal，2015，24（2）：219-243.

Abstract：In view of the problems caused by the unbalanced distribution of spatiotemporal sensing data in time and space dimensions， this paper proposes spatiotemporal multi-granularity structure： 3DTree. Furthermore， the stability， validity and universality of the proposed spatiotemporal multi-granularity structured representation method are verified by data set experiments on different platforms， different types and different regions.

Key words：spatiotemporal data; multi-granularity;data representation