面向时空数据的多粒度结构化表示

夏增刚 丁夏蕾 王亮

摘要：针对时空感知数据在时间、空间维度分布不均衡所导致的问题，本文提出了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