基于空间填充曲线的轨迹热点区域挖掘算法研究

国防科学技术大学机电工程与自动化学院 张鲁斌

基于空间填充曲线的轨迹热点区域挖掘算法研究

国防科学技术大学机电工程与自动化学院 张鲁斌

针对传统的数据挖掘算法在处理海量的、复杂多样且变化迅速的轨迹数据方面已不适用，难以对数据进行有效挖掘的问题，提出了一种基于空间填充曲线的轨迹热点区域挖掘算法。首先研究了空间填充曲线，然后采用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所示。