时空同现挖掘算法及应用研究

张奕　张永梅　郭莎　降爱莲　邬小燕

摘 要： 在隐藏于历史轨迹数据集的众多模式中，同现模式的挖掘尤其引人关注。文章将时空同现的数据挖掘算法与Hadoop平台相结合，实现了并行处理，对轨迹数据进行预处理，并设计了时空同现模式挖掘算法。实验结果表明，该算法能够挖掘乘客集中地，为出租车司机提供合理有效的载客路径。

关键词： 时空同现； 并行处理； 出租车轨迹数据； 数据挖掘

中图分类号：TP311 文献标志码：A 文章编号：1006-8228（2016）11-05-02

Spatiotemporal co-occurrence mining algorithm and the application

Zhang Yi1， Zhang Yongmei2， Guo Sha2， Jiang Ailian3， Wu Xiaoyan2

（1. College of Software， Taiyuan University of Technology， Shanxi， Taiyuan 030600， China； 2. College of Computer， North China University of Technology； 3. College of Computer Science and Technology， Taiyuan University of Technology）

Abstract： Among the many modes hidden in the historical trajectory data set， mining the co-occurrence modes is particularly concerned. In this paper， combining the spatiotemporal co-occurrence data mining algorithm with Hadoop platform， the parallel processing is realized to pre-process the trajectory data， and the spatiotemporal co-occurrence mining algorithm is designed. The experiment results show that the algorithm can mining concentrated areas of passengers， and provide reasonable and effective paths for taxi drivers.

Key words： spatiotemporal co-occurrence； parallel processing； taxi trajectory data； data mining

0 引言

时空同现模式就是在时空维度下，不同对象类型子集的实例在一些时间段内，在空间上是相互邻近的，或符合某种空间关系的对象集合。在许多应用领域如：环境监测、抢险救灾、基于位置的服务等，数据都随着时间变化而变化。然而，大多数数据库都不能有效地处理数据的时间维度。当数据发生变化时，无法对数据变化的趋势进行分析，更无法预测未来的趋势。因此，从这些大量的数据中挖掘出有价值的信息变得更加重要，时空同现模式挖掘成为研究热点。

随着移动电话、GPS（Global Positioning System，全球定位系统）等具备定位功能的设备普及，产生了大量基于时间和空间的移动对象历史轨迹数据。在地理信息系统中，移动对象的历史位置信息日益重要，在这一背景下，针对移动对象历史轨迹的数据挖掘研究成为当前研究热点之一[1-2]。与传统事务性数据集相比，从空间数据集中识别感兴趣的模式更为困难和复杂，因为空间数据集具有复杂的数据类型和关系，而且数据总量庞大。在隐藏于历史轨迹数据集的众多模式中，同现模式的挖掘尤其引人关注。空间数据集的同现模式直观地反映了移动过程中移动对象之间相互接触的情况，所以快速准确地挖掘时空数据中的同现模式有利于推动众多领域的研究，如生态、电力系统故障分析、军事等。

虽然时空同现模式挖掘已经取得了一些令人欣慰的研究成果，但总体来说还处于起步阶段。随着空间数据采集效率的提高，空间数据逐渐增大。在时空同现模式挖掘研究领域中，MeteCelik等人提出的混合驱动的时空同现模式挖掘最具有代表性。为了挖掘时空同现模式，他们提出了混合时空同现模式挖掘算法。该挖掘算法是基于连接操作的，会消耗大量时间生成候选模式集，随着对象类型的增多，需要生成的候选模式集数量呈指数级增长，这意味着需要消耗的计算时间迅速增长，计算效率无法随着对象类型的增加而迅速增长，不能处理庞大的时空数据；同时该算法是基于内存的，无法处理大量时空数据[3-5]。本文对出租车轨迹数据进行分析与挖掘，将时空同现的数据挖掘算法与Hadoop平台相结合，可以有效解决数据存储和运行慢的问题，同时又能高效获取潜在信息。

1 时空同现挖掘算法的设计及实现

1.1 并行处理方法的实现

本文采用云计算理念，促进资源管理和高效利用，提升系统构建的速度和灵活性。构建基于云计算的数据环境，改善传统的应用与硬件绑定、不易维护、难以扩展等问题。大数据批处理需求主要针对复杂分布式编程，通过先存储后计算的模式，允许对存储单元的内容进行多次操作，从而为复杂计算提供支撑。当前，大数据批处理计算技术主要包括MapReduce、Dryad和spark等。

MapReduce是Google开发的一种简洁抽象的分布式计算模型，在处理T级别以上巨量数据的业务上具有明显优势。在MapReduce中，应用的原始数据被划分为多个用于并行计算的数据分片split，以显式地挖掘应用中的并行性。为了更好地描述问题的并行求解，split 被定义为数据域、属性域和状态描述域三部分。MapReduce 运行时系统是无状态的，各个split保存自身状态信息，便于将来checkpoint等功能的实现。MapReduce还提供了对数据分片的map和reduce计算。MapReduce已有多种实现，最著名的是Hadoop，Hadoop灵活易用、可靠高效，已成为目前分布式海量数据处理的首选工具。

本文选择Apache的Hadoop作为整个系统的底层计算平台，主要使用Hadoop的分布式文件存储系统HDFS和并行计算系统MapReduce。Hadoop环境搭建在vmware安装好ubuntu的条件下。本文采用HDFS分布架构系统，把需处理的任务分布到多个计算机上，把一台计算机作为NameNode结点，再选另外几台计算机作为DataNode，提高运算效率，同时也采用了MapReduce，利用它的并行处理功能，提高运算速度。

1.2 数据的预处理方法

本文采用的数据是网上下载的轨迹数据，该数据是微软亚洲研究院在Geolife 项目中收集的北京市出租车轨迹数据，收集时间段：2008年2月2日-2月8日。数据平均采样间隔约177秒，距离约623米。本文的数据预处理主要包括：计算速度、出租车停靠点的分析。计算速度是根据数据文件里所给的同一车辆在不同时间点上处于不同的经纬度，经过转换和计算获得两点间的欧氏距离，利用距离除以相隔时间，得到在每个时间间隔内的出租车速度。出租车停靠点的分析是结合出租车速度和时间空间，进行出租车停靠点的分析，即筛选出出租车载客的地点，过滤掉造成干扰的点。

1.3 时空同现模式挖掘算法具体步骤及实现

本文根据空间邻近距离R计算出所有时间槽内的空间邻近模式，对于所有时间槽内的空间邻近模式计算各模式的实例支持度，与空间频繁阈值进行比较，挖掘出满足阈值的空间同位模式集，再纵向考虑所有时间槽，统计各个空间同位模式的时间频繁度，找出满足时间频繁阈值的时空同现模式，进行时空同现模式的挖掘计算。时空同现模式挖掘算法具体步骤如下。

⑴ 初始化各个时间槽实例之间的空间关系，对时空数据集建立时空网络模型STCOPG；

⑵ 设置k=1；

⑶ 根据STCOPG图，生成k+1元候选时空同现模式；

⑷ 通过查询STCOPG获得候选时空同现模式的实例集，计算时空频繁度，生成k+l元时空同现模式；

⑸ 重复生成候选同现模式操作，直到无新的候选同现模式或新的时空同现模式生成，算法结束；

⑹ 合并得到所有符合时空阈值的时空同现模式集。

根据大量实验结果，本文的时空邻近距离、空间频繁阈值、时间频繁阈值分别为4km、0.5和0.4。图1给出了2008年2月4日下午2点出租车位于北京交通大学，相对于出租车所处位置来说，在空间上邻近的时空同现挖掘结果。

在图1中，出租车位于北京交通大学，也就是标识为TAXI的位置，相对于出租车所处位置来说，在空间上邻近的一些热点的分布图，也就是出租车司机在下午2点时，开车去如图1所示的热点分布的地方最容易载到乘客。

2 结束语

时空同现模式挖掘从其产生至今，就一直受到各界研究人员的关注。挖掘时空模式是非常有意义的，并且具有挑战性，它可以应用于军事、道路的交通管制、灾情分析、案件侦破、国防、生态等领域。本文研究了时空同现挖掘算法及应用，可以有效挖掘乘客集中地，为出租车司机提供合理有效的载客路径。进一步需要研究时空邻近距离、空间频繁阈值、时间频繁阈值的自适应选取。

参考文献（References）：

[1] 齐林.基于GPS数据的出租车交通运行特性研究及应用[D].

哈尔滨工业大学硕士学位论文，2013.

[2] 丛湘香.大数据下时空同现模式挖掘算法研究[D].华东理工

大学硕士学位论文，2012.

[3] 陈延平.基于局部时空共现特征的人体行为识别方法研究[D].

厦门大学硕士学位论文，2012.

[4] 黄照鹤，戴健.基于时空同现挖掘技术的FNRB-Tree[J].小型

微型计算机系统，2012.33（12）：2636-2641

[5] 许强，罗泽，魏颖，阎保平.一种检测时空数据中重要同现模式的

快速算法[J].科研信息化技术与应用，2013.4（3）：23-31