基于MAP/REDUCE的移动目标连续轨迹模式挖掘的研究

彭茗菁　马传香　李伟亮

摘 要：针对传统序列模式挖掘算法都是针对单机环境、静态实例以及非连续轨迹的不足，提出了Map/Reduce系统与经过优化的PrefixSpan序列模式挖掘算法相结合的改进型算法。该算法在生成投影数据库时，只有当待投影序列的第一个元素和前缀的最后一个元素相同时才会被选中，保证了挖掘出的都是连续轨迹片段。同时采用并行处理的方法，使用Map函数构建每个频繁序列前缀对应的投影数据库，使用Reduce函数整合所有的中间键值对得到需要的结果。

关键词：Map/Reduce模型；改进型PrefixSpan算法；轨迹模式；数据挖掘

中图分类号：TP311 文献标识码：A 文章编号：2095-1302（2014）10-00-02

0 引 言

近些年，随着传感器技术在功能、体积和数据传输方式上的不断革新，已得到广泛应用，现在人们身边随处可见各种传感设备在收集信息，一些大型企业和国有单位日收集信息量都已接近TB级。这些收集起来的海量数据中蕴含了很多对企业和社会有巨大价值的信息，如何及时准确地挖掘出这些有利信息成为了一项极富挑战的课题。

首先是如何进行分类和预处理，这些数据资源规模庞大且以指数级形式进行动态变化，对此传统的单一节点的计算能力已捉襟见肘，扩展性差，使得数据挖掘系统的挖掘能力受到了极大的限制。此时需要依靠并行处理，旨在提高整个系统的处理能力，将耗费大量计算资源的计算分散到网络中的多个节点上进行并行处理，处理能力随着节点数目的增长可以近乎无限的扩充。其次是挖掘算法，其关键在于如何从给定的轨迹中挖掘出目标的典型运动模式，目前已有的序列模式挖掘算法并不能满足轨迹模式挖掘的要求，因为其只对序列的前后顺序敏感，无法保证挖掘出的频繁序列是挨个连续的。

本文从MAP/REDUCE并行处理的角度出发，结合经过改进的PrefixSpan算法，提出一种基于并行计算的频繁轨迹模式挖掘算法。

1 MAP/REDUCE模型简述

MAP/REDUCE是Google开发的一种并行分布式编程模型，已在处理海量数据领域取得了广泛应用，它通过运用Map/Reduce将输入的整片数据以键/值对的形式进行分割和处理，其中Map负责将整片数据拆分为数据片段，并将每一个片段分配给一个计算节点运行产生中间键值对，Reduce则相反，负责将散布在大量不同节点上的数据片段整合，按键来合并键值对，最后汇总并输出。在Map/Reduce模型中，每个计算节点可同时运行Map任务和Reduce任务，它将所承接的计算任务均匀分散到网络中大量计算机组成的计算池中，使模型上运行的应用程序能及时得到足够的存储空间和计算能力来完成相应任务。

Map/Reduce的核心思想是将要执行的问题进行分割并以键值对的方式来处理数据。Map/Reduce的执行由master和worker两种不同类型的节点负责，worker负责数据处理，master负责掌控全局的任务调度及不同节点之间的数据共享，执行过程如图1所示。数据被分割成大小相等的M个任务，每一个任务为大小16～64 MB的片段，并在集群里其他节点上随机执行数据片段的备份，这样可以解决在集群挖掘中普遍存在的存储容量扩展和服务器突发故障所产生的数据丢失问题。随后主节点master负责找到状态为闲置的worker节点并为它们分配子任务（一共有M个Map子任务和R个Reduce子任务）。若某个worker节点被分配Map子任务，则输入已分割好的文件片段，处理成键值对（KEY/VALUE）并调用用户自定的Map函数将输入的键值对转换成中间结果（键值对）。

Map函数生成的中间结果缓存在内存中并会周期性的写入本地硬盘，在分区函数的作用下分成了R个区块，并将它们在硬盘中的位置信息发送给MASTER节点，MASTER节点在收到后会将位置信息转发给那些承接了Reduce任务的WORKER节点。然后这些WORKER节点调用远程程序从负责Map任务的本地计算机的硬盘里读取之前缓存的中间键值对，当读取所有缓存完成后，利用中间结果的KEY值进行排序，将具有相同键的键值对合并，再传递给用户自定的REDUCE函数，生成R个REDUCE结果。最后MASTER节点将这R个结果返回应用程序，由应用程序将其合并形成最终结果。

图1 Map/Reduce执行过程

2 连续轨迹模式挖掘算法

在以往关于序列模式挖掘的问题上，考虑到性能和效率，普遍采用的是Han等人提出的PrefixSpan算法，但这种序列模式挖掘算法并不能直接运用到轨迹模式挖掘中，本文里使用袁和金提出的改进型PrefixSpan算法。

Han等人在2004年发表了基于前缀投影的PrefixSpan算法。该算法的核心思路是：首先扫描一次序列数据库，得到频繁1项集，并产生对应的投影数据库，然后每个投影数据库进行单独的递归挖掘。算法构造前缀模式，它与后缀模式相连得到频繁模式，从而避免生成候选项集，但是该算法允许挖掘出的频繁项在其序列里是跳跃、非连续的。对此，改进型的PrefixSpan算法修改了子序列、前缀、后缀、投影的定义。

首先将子序列定义改为对序列a=和b=，p≤q，如果存在整数i，使得a1=bi，a2=bi+1，ap=bi+p-1 ，则称a是b的子序列，或b包含a，这样一来就对包含关系进行了限制。

在上面定义的包含关系的基础上给出了对应的前缀、后缀、投影的概念，给定两个轨迹序列a=和b=，p≤q，只有当a1=b1，a2=b2，ap=bp时，a才是b的前缀。

对于投影，给定序列a和b（b∈a），只有当b是a'前缀且a'是a的最大子序列时，被称为b在a上的投影。

根据上面前缀和投影的定义，设a的投影a'=，前缀b=，可得序列为a对应b的后缀。

在以上新定义的基础上，设a是一个轨迹模式，那么a-投影数据库为以a为前缀的轨迹序列对应a的后缀组成的集合。可以看出，加入了这个新定义后，只有当待投影序列的第一个元素和前缀的最后一个元素相同时才会被投影数据库选中，这样就能保证挖掘出的都是连续轨迹片段。

改进后的PrefixSpan算法执行顺序如下：首先挖掘所有的频繁-1序列模式，再从所给出的原始序列里将频繁-1序列后面的所有元素加入到频繁1序列对应的子集里。然后针对前面所产生的所有子集，用基于改进后的子序列及前、后缀的定义来递归的投影和模式增长进行挖掘，直到不能增长出更长的频繁序列为止。举例来说，给定原始序列数据库SD={<1，2，3，6，7>，<2，3，6，7>，<4，5，3，8，9>，<1，2，3，6>，<4，5，3，9>，<5，3，8，9>}，其中1到9是项的集合，最小支持度是2/6=33%，表1是使用改进型PrefixSpan算法和原始算法结果的对比。

表1 改进型算法和原始算法结果对比

改进型算法 原始算法

前缀 频繁模式

<3> <3，6，7>，<3，8，9> <3，7>，<3，9>，<3，6，7>，<3，8，9>

<2> <2，3，6，7> <2，7>，<2，3，7>，<2，3，6，7>

<5> <5，3，8，9> <5，3，8，9>，<5，3，9>

<6> <6，7> <6，7>

<9> <9> <9>

<1> <1，2，3，6> <1，6>，<1，2，6>，<1，2，3，6>

<4> <4，5，3> <4，9>，<4，5，9>，<4，5，3，9>

<7> <7> <7>

<8> <8，9> <8，9>

3 基于Map/Reduce的改进PrefixSpan算法。

整个算法分成两个阶段，第一阶段用户给定目标序列数据库SD和最小支持度minimum_s，Master节点将数据库SD分割成n个块，并交由负责Map任务的节点将所有块完整遍历一次，输出的中间键值对的形式是，a指的是SD中任意一个项，1指的是出现了一次。Map任务每扫描一个项，就输出一个对应的。在遍历结束后，Reduce节点将所有的中间结果键值对汇总、统计，生成形式为的键值对，n指的是汇总后项a出现的全部次数。与此同时Reduce节点将n小于minimun_s的键值对丢弃，最后输出的结果就是频繁-1序列，至此第一阶段结束。整体过程如图2所示。

图2 算法执行过程

第二阶段开始后，将之前第一阶段输出的所有频繁-1序列进行分割存储，交由Map任务分配给空闲worker节点，每个节点对应一个频繁-1序列，并针对每个节点对应的频繁-1序列并行构造其投影数据库，即从所给出的原始序列里将以频繁-1序列为前缀的后续所有序列加入其中，并计算支持度。Map任务生成的中间键值对是以的形式存在，p指的是前缀，support指的是对应的前缀的支持度。Map任务结束后，负责Reduce的节点会扫描全部的中间键值对并按照支持度进行取舍，最后得到全局范围的频繁轨迹序列模式。

4 结 语

本文针对传统串行数据挖掘方法无法满足现今海量数据的缺点，提出了一种将Map/Reduce与经过修改的传统数据挖掘相结合的新型并行算法，理论上可通过扩充数据节点的数量来增强单位时间的处理能力。今后的研究方向是将本文的算法进行优化，使效率更高，以及如何对海量数据在进行数据挖掘前进行必要的预处理。

参考文献

[1]袁和金. 视频目标轨迹分析的改进PrefixSpan方法[J].计算机工程与应用，2011，47（32）：7-10.

[2]刘骞，陈明.基于Map/Reduce集群上的模式空间划分的序列模式挖掘[J].微电子学与计算机，2012（9）：149-151.

[3] Pei J，Han J，Mortazavi-Asl B，et al.Mining sequential patterns by pattern-growth：the PrefixSpan approach[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（11）：1424-1440.

[4] JEFFREYD，SANJAYG.Map/Reduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

根据上面前缀和投影的定义，设a的投影a'=，前缀b=，可得序列为a对应b的后缀。

在以上新定义的基础上，设a是一个轨迹模式，那么a-投影数据库为以a为前缀的轨迹序列对应a的后缀组成的集合。可以看出，加入了这个新定义后，只有当待投影序列的第一个元素和前缀的最后一个元素相同时才会被投影数据库选中，这样就能保证挖掘出的都是连续轨迹片段。

改进后的PrefixSpan算法执行顺序如下：首先挖掘所有的频繁-1序列模式，再从所给出的原始序列里将频繁-1序列后面的所有元素加入到频繁1序列对应的子集里。然后针对前面所产生的所有子集，用基于改进后的子序列及前、后缀的定义来递归的投影和模式增长进行挖掘，直到不能增长出更长的频繁序列为止。举例来说，给定原始序列数据库SD={<1，2，3，6，7>，<2，3，6，7>，<4，5，3，8，9>，<1，2，3，6>，<4，5，3，9>，<5，3，8，9>}，其中1到9是项的集合，最小支持度是2/6=33%，表1是使用改进型PrefixSpan算法和原始算法结果的对比。

表1 改进型算法和原始算法结果对比

改进型算法 原始算法

前缀 频繁模式

<3> <3，6，7>，<3，8，9> <3，7>，<3，9>，<3，6，7>，<3，8，9>

<2> <2，3，6，7> <2，7>，<2，3，7>，<2，3，6，7>

<5> <5，3，8，9> <5，3，8，9>，<5，3，9>

<6> <6，7> <6，7>

<9> <9> <9>

<1> <1，2，3，6> <1，6>，<1，2，6>，<1，2，3，6>

<4> <4，5，3> <4，9>，<4，5，9>，<4，5，3，9>

<7> <7> <7>

<8> <8，9> <8，9>

3 基于Map/Reduce的改进PrefixSpan算法。

整个算法分成两个阶段，第一阶段用户给定目标序列数据库SD和最小支持度minimum_s，Master节点将数据库SD分割成n个块，并交由负责Map任务的节点将所有块完整遍历一次，输出的中间键值对的形式是，a指的是SD中任意一个项，1指的是出现了一次。Map任务每扫描一个项，就输出一个对应的。在遍历结束后，Reduce节点将所有的中间结果键值对汇总、统计，生成形式为的键值对，n指的是汇总后项a出现的全部次数。与此同时Reduce节点将n小于minimun_s的键值对丢弃，最后输出的结果就是频繁-1序列，至此第一阶段结束。整体过程如图2所示。

图2 算法执行过程

第二阶段开始后，将之前第一阶段输出的所有频繁-1序列进行分割存储，交由Map任务分配给空闲worker节点，每个节点对应一个频繁-1序列，并针对每个节点对应的频繁-1序列并行构造其投影数据库，即从所给出的原始序列里将以频繁-1序列为前缀的后续所有序列加入其中，并计算支持度。Map任务生成的中间键值对是以的形式存在，p指的是前缀，support指的是对应的前缀的支持度。Map任务结束后，负责Reduce的节点会扫描全部的中间键值对并按照支持度进行取舍，最后得到全局范围的频繁轨迹序列模式。

4 结 语

本文针对传统串行数据挖掘方法无法满足现今海量数据的缺点，提出了一种将Map/Reduce与经过修改的传统数据挖掘相结合的新型并行算法，理论上可通过扩充数据节点的数量来增强单位时间的处理能力。今后的研究方向是将本文的算法进行优化，使效率更高，以及如何对海量数据在进行数据挖掘前进行必要的预处理。

参考文献

[1]袁和金. 视频目标轨迹分析的改进PrefixSpan方法[J].计算机工程与应用，2011，47（32）：7-10.

[2]刘骞，陈明.基于Map/Reduce集群上的模式空间划分的序列模式挖掘[J].微电子学与计算机，2012（9）：149-151.

[3] Pei J，Han J，Mortazavi-Asl B，et al.Mining sequential patterns by pattern-growth：the PrefixSpan approach[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（11）：1424-1440.

[4] JEFFREYD，SANJAYG.Map/Reduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

根据上面前缀和投影的定义，设a的投影a'=，前缀b=，可得序列为a对应b的后缀。

在以上新定义的基础上，设a是一个轨迹模式，那么a-投影数据库为以a为前缀的轨迹序列对应a的后缀组成的集合。可以看出，加入了这个新定义后，只有当待投影序列的第一个元素和前缀的最后一个元素相同时才会被投影数据库选中，这样就能保证挖掘出的都是连续轨迹片段。

改进后的PrefixSpan算法执行顺序如下：首先挖掘所有的频繁-1序列模式，再从所给出的原始序列里将频繁-1序列后面的所有元素加入到频繁1序列对应的子集里。然后针对前面所产生的所有子集，用基于改进后的子序列及前、后缀的定义来递归的投影和模式增长进行挖掘，直到不能增长出更长的频繁序列为止。举例来说，给定原始序列数据库SD={<1，2，3，6，7>，<2，3，6，7>，<4，5，3，8，9>，<1，2，3，6>，<4，5，3，9>，<5，3，8，9>}，其中1到9是项的集合，最小支持度是2/6=33%，表1是使用改进型PrefixSpan算法和原始算法结果的对比。

表1 改进型算法和原始算法结果对比

改进型算法 原始算法

前缀 频繁模式

<3> <3，6，7>，<3，8，9> <3，7>，<3，9>，<3，6，7>，<3，8，9>

<2> <2，3，6，7> <2，7>，<2，3，7>，<2，3，6，7>

<5> <5，3，8，9> <5，3，8，9>，<5，3，9>

<6> <6，7> <6，7>

<9> <9> <9>

<1> <1，2，3，6> <1，6>，<1，2，6>，<1，2，3，6>

<4> <4，5，3> <4，9>，<4，5，9>，<4，5，3，9>

<7> <7> <7>

<8> <8，9> <8，9>

3 基于Map/Reduce的改进PrefixSpan算法。

整个算法分成两个阶段，第一阶段用户给定目标序列数据库SD和最小支持度minimum_s，Master节点将数据库SD分割成n个块，并交由负责Map任务的节点将所有块完整遍历一次，输出的中间键值对的形式是，a指的是SD中任意一个项，1指的是出现了一次。Map任务每扫描一个项，就输出一个对应的。在遍历结束后，Reduce节点将所有的中间结果键值对汇总、统计，生成形式为的键值对，n指的是汇总后项a出现的全部次数。与此同时Reduce节点将n小于minimun_s的键值对丢弃，最后输出的结果就是频繁-1序列，至此第一阶段结束。整体过程如图2所示。

图2 算法执行过程

第二阶段开始后，将之前第一阶段输出的所有频繁-1序列进行分割存储，交由Map任务分配给空闲worker节点，每个节点对应一个频繁-1序列，并针对每个节点对应的频繁-1序列并行构造其投影数据库，即从所给出的原始序列里将以频繁-1序列为前缀的后续所有序列加入其中，并计算支持度。Map任务生成的中间键值对是以的形式存在，p指的是前缀，support指的是对应的前缀的支持度。Map任务结束后，负责Reduce的节点会扫描全部的中间键值对并按照支持度进行取舍，最后得到全局范围的频繁轨迹序列模式。

4 结 语

本文针对传统串行数据挖掘方法无法满足现今海量数据的缺点，提出了一种将Map/Reduce与经过修改的传统数据挖掘相结合的新型并行算法，理论上可通过扩充数据节点的数量来增强单位时间的处理能力。今后的研究方向是将本文的算法进行优化，使效率更高，以及如何对海量数据在进行数据挖掘前进行必要的预处理。

参考文献

[1]袁和金. 视频目标轨迹分析的改进PrefixSpan方法[J].计算机工程与应用，2011，47（32）：7-10.

[2]刘骞，陈明.基于Map/Reduce集群上的模式空间划分的序列模式挖掘[J].微电子学与计算机，2012（9）：149-151.

[3] Pei J，Han J，Mortazavi-Asl B，et al.Mining sequential patterns by pattern-growth：the PrefixSpan approach[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（11）：1424-1440.

[4] JEFFREYD，SANJAYG.Map/Reduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.