夏增剛 丁夏蕾 王亮

摘要：針對(duì)時(shí)空感知數(shù)據(jù)在時(shí)間、空間維度分布不均衡所導(dǎo)致的問(wèn)題，本文提出了3DTree的時(shí)空多粒度結(jié)構(gòu)。進(jìn)而以不同平臺(tái)、不同類型、不同地域的數(shù)據(jù)集實(shí)驗(yàn)驗(yàn)證了所提出的時(shí)空多粒度結(jié)構(gòu)化表示方法的穩(wěn)定性、有效性及普適性。

關(guān)鍵詞：時(shí)空數(shù)據(jù);多粒度;數(shù)據(jù)表示

中圖分類號(hào)：TP302 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2020）03-0232-01

0 引言

在現(xiàn)實(shí)場(chǎng)景中，由于人口分布、區(qū)域功能定位等原因，導(dǎo)致所獲取到的時(shí)空數(shù)據(jù)在時(shí)間-空間上具有極強(qiáng)的分布不均衡性[1]。不均衡的時(shí)空數(shù)據(jù)若是采用等粒度的時(shí)空結(jié)構(gòu)表示索引[2]，會(huì)造成索引效率的低下、所挖掘到的知識(shí)/模式精度往往不高等問(wèn)題。而多粒度的數(shù)據(jù)表示方法可以很好的解決上述問(wèn)題。

1 時(shí)空多粒度數(shù)據(jù)表示研究現(xiàn)狀

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

2 3Dtree時(shí)空多粒度描述

時(shí)空多粒度是將經(jīng)度、緯度、時(shí)間統(tǒng)一分析，3DTree劃分步驟如下：

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

輸入：3維時(shí)空數(shù)據(jù)集，其中 劃分深度dep;

輸出：個(gè)空間長(zhǎng)方體的坐標(biāo)。

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

步驟2.以為坐標(biāo)軸，以T中所有實(shí)例的坐標(biāo)對(duì)數(shù)據(jù)集快速排序，將數(shù)據(jù)長(zhǎng)度1/2位置的點(diǎn)作為切分點(diǎn)，將數(shù)據(jù)集劃分為左子區(qū)域和右子區(qū)域。

步驟3.將左子區(qū)域和右子區(qū)域分別作為數(shù)據(jù)集，重復(fù)Step1-2遞歸地實(shí)現(xiàn)時(shí)空多粒度的劃分。

步驟4.保存深度為dep的個(gè)空間長(zhǎng)方體的坐標(biāo)。

3 實(shí)驗(yàn)驗(yàn)證

本文數(shù)據(jù)集：成都市滴滴打車平臺(tái)一個(gè)月的訂單數(shù)據(jù)，成都市出13606輛租車一天軌跡數(shù)據(jù)，深圳市13698輛出租車一天軌跡數(shù)據(jù)。

（1）時(shí)空多粒度表示結(jié)構(gòu)的統(tǒng)計(jì)量分布實(shí)驗(yàn)。二維劃分方法深度取10，三維方法深度取14。實(shí)驗(yàn)結(jié)果如表1。

從表1可以看出三維多粒度表示結(jié)構(gòu)比二維結(jié)構(gòu)的信息熵和方差小，劃分的區(qū)域分辨率更高。

（2）不同平臺(tái)、不同類型、不同地域?qū)嶒?yàn)。

從表2、3可以看出：三維方法構(gòu)建的多粒度結(jié)構(gòu)更穩(wěn)定，時(shí)空多粒度表示結(jié)構(gòu)的確定性和對(duì)數(shù)據(jù)分布表示的能力更強(qiáng)。

4 結(jié)語(yǔ)

本文針對(duì)傳統(tǒng)時(shí)空數(shù)據(jù)表示對(duì)時(shí)間屬性考慮不足的問(wèn)題，從數(shù)據(jù)的時(shí)空分布出發(fā)提出了3DTree方法，并且實(shí)驗(yàn)驗(yàn)證了本文方法的有效性、穩(wěn)定性和普適性。

參考文獻(xiàn)

[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] 王亮，胡琨元，庫(kù)濤，等.基于多尺度空間劃分與路網(wǎng)建模的城市移動(dòng)軌跡模式挖掘[J].自動(dòng)化學(xué)報(bào)，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