基于MAPREDUCE并行处理的轨迹模式挖掘算法的研究

李伟亮　马传香　彭茗菁

摘 要：关联规则算法中FP-Growth算法虽不产生候选集，但由于算法高度依赖于内存空间，阻碍了算法在大数据领域的发挥，因此，改进了经典的FP-Growth算法，首先创建支持度计数表，避免了算法对条件模式基的第一次遍历，减少了对数据库的扫描次数；其次利用剪枝策略删去了大量沉余的非频繁项集；最后将算法并行化，利用 Hadoop平台优势极大提高数据处理的效率，同时解决了算法占用内存的瓶颈问题。实验结果表明，改进型FP-Growth算法挖掘和预测轨迹的效率明显高于经典算法。

关键词：改进型FP-Growth；Map-Reduce；Hadoop；轨迹预测

中图分类号：TP391 文献标志码：A 文章编号：2095-1302（2014）10-00-03

0 引 言

随着我国经济社会的稳步推进，各大城市的发展取得了令人瞩目的成就。与此同时，大城市的机动车保有量与日俱增，交通拥挤的问题日益严重。尽管市政和交通管理部门投入了大量的人力、物力和财力建设，但城市交通拥堵现象仍然不能有效解决。要做到合理分布交通流，使单位时间的道路通行量最大且使用效率高，就需要做到合理规划和预测路网中车辆轨迹和车辆路径。本文提出基于改进FP-Growth算法的车辆预测方法，利用Map/Reduce编程进行大数据的并行计算，提高了算法效率，解决了交通管理部门监测当前时间车流量信息的目的，为交通管理部门和相关车辆及时发布预警信息提供了决策支持。

1 FP-Growth算法概述

J.W.Han[1，2]等人克服了Apriori算法产生基数庞大的候选集和在计算支持度时多次扫描数据库的弱点，提出FP-Growth算法。其思想是通过扫描2次数据库构造FP-Tree和Header Table，从而得到用于频繁项集挖掘的压缩的数据库映射，然后对每个频繁项构造其条件FP-Tree进行频繁项集的挖掘，最终得到频繁项集。与Apriori算法比较FP-Growth算法不产生候选集，采用FP-Tree压缩所有能够提供频繁项信息的项集，节省了时间和空间的消耗，相对Apriori算法的执行速度和内存消耗已经有了一个数量级的改善。

1.1 FP-Growth改进

由于FP-Growth是基于内存驻留的算法，在频繁项挖掘时递归生成大量条件FP-Tree，当数据库达到一定规模时，基于内存的FP-Tree已经无法有效应对，极容易造成内存溢出，这正是FP-Growth算法的瓶颈所在。因而，FP-Growth算法在挖掘大数据问题上有较大扩展空间。

针对当前交通的大数据背景，传统FP-Growth算法和以上改进算法的优势不足以处理大规模交通数据问题。因此，本文就针对交通大数据给出FP-Growth算法改进的解决方案：

（1）建立支持度计数表。在第一次遍历事务集合T的同时创建二维向量，记录每个事务中各个项两两组合出现的支持度计数；利用递归方式创建后缀模式S（ S ≠{Null}）条件下的条件FP子树，此时，第一次遍历条件模式基得到支持度计数列表，第二次遍历条件模式基插入树节点从而创建FP树；遍历条件模式基，创建FP子树的同时创建新的支持度计数二维向量表。

（2）非频繁项的剪枝策略。假设项集k在某一个路径上是非频繁的；若项集k在 FP-tree 中存在前缀路径集合A与集合B，并且满足集合B包含于集合A，那么集合A中的项集k就可以被剪枝与短路径集合B合并。

1.2 Map-Reduce 并行处理

Map-Reduce最初是由Google提出的，它是一种可以处理海量数据的并行编程模型。该模型把所有的数据问题抽象成Map和Reduce两个函数。以可靠的并行方式处理大规模数据集，其中Map函数把问题进行分解，Reduce函数负责把分解的任务进行规约处理。

利用Map-Reduce编程模型，经统计频繁1-项和递归挖掘频繁项集的两次并行处理，对改进后的FR-Growth算法步骤并行化。其描述为：首先，对频繁1-项集的频率统计；再利用频繁1-项集的频率统计结果建立一个哈希表，按照哈希表对数据进行分组，把数据分成了若干个部分；然后对分解后的数据进行关联规则挖掘；最后，汇总最终的频繁模式。

图1 Map-Reduce任务处理流程

图2 基于Map-Reduce的频繁轨迹挖掘

2 基于模式匹配的轨迹预测

根据基于Map/Reduce的频繁轨迹挖掘得到的序列模式进行轨迹预测。通过Map/Reduce并行计算获得频繁模式集合后，就可以计算出与查询轨迹最为相似的频繁模式，用该模式就可以预测轨迹的未来走向。

对于移动对象数据库D，存储的是海量移动对象在各时间采样点的位置信息。位置信息在时间上的有序集合为轨迹，用D={T1，T2，…，Tn）表示，则|D|表示数据库中包含的轨迹数量。在三维X×Y×T空间里，轨迹T是移动对象在空间内位置信息的有序组合，可以表示为T=（t1，x1，y1），（t2，x2，y2），…，（tn，xn，yn）。其中ti表示时间戳，（xi，yi）表示移动对象的空间位置坐标。

轨迹匹配，是从频繁模式中找出与查询轨迹片段匹配权重最高的模式。假设用户的查询轨迹片段为Q=，轨迹频繁模式为P=，则Q的预测由Q和P=的匹配程度进行反映。轨迹片段在时间上最靠近当前的元素是优先考虑的，当i1，w1默认为1，因此轨迹Q、P的相似度计算公式为：

如查询轨迹片段Q=，频繁模式为P，Q和P的公共元素有，c和d的权重分别是100和10，假设k=10，因此Q和P似度为Sim（Q，P）=10+100/1+10+100，表明f极有可能为轨迹Q的未来轨迹。

3 算法与实验

本文实验环境采用4台PC机做分布式环境。操作系统为Ubuntu 14.04 -32bit，Hadoop 2.4.0，CPU为Inter Core i7处理器，主频2.1 GHz，单机内存为512 MB。

3.1 频繁1-项统计

其Map-Reduce算法伪代码如下：

map（key，value）{ //value为事务Ti

for each ki∈Ti do

output；

end

}

reduce（key，value）{//key为一个1-项集，value为其支持数列表[1，1，…，1]

C=0；

for each v in value do

C+=1；

end

ifC/|D|minsup then

output；//输出频繁1-项集及其支持数

end

}

3.2 FP-Growth并行化

其Map-Reduce算法伪代码如下：

map（key，value）{ //value为事务Ti

insert_build_fptree（LFPTree，Ti）；//更新局部FP树LFPTree

}

cleanup（）{

LocalFPGrowth（LFPTree，LFPSet）；//将局部频繁项目集及其支持数放入LFPSet中

for each lfp∈LFPSet do

output；//sup（lfp）为局部频繁项目集lfp的支持数

end

}

reduce（key，value）{//key为项目集，value为其支持数列表

C=0；

for each vi in value do

C+=vi；

end

if C/|D|≥minsup then

output；//输出全局频繁项目集及其支持数

else if

write key into a distribute file；//若暂不确定是否全局频繁，则将其写入分布式文件

end

}

4 结 语

本文结合历史车辆轨迹数据利用改进型的关联规则算法FP-Growth挖掘出轨迹模式索引，并提出基于Map/Reduce算法的轨迹预测方案。在路网中利用索引树对车辆未来轨迹进行预测，预判出车流趋势，为交通管理部门及时做出交通疏导方案的决策提供了支持。

参考文献

[1] J.W.Han， JianPen， Yin YiWen.Mining frequent patterns without candidate generation[C].In the proceedingsof ACM SIGMOD International Conference on Management of Data，Dallas， Texas：2000：1-12.

[2] J. G.LEE， J. W.HAN， WHANG K. Y. Trajectory clustering： a partition-and-group framework [A]. ICMD2007：Proceedings of the ACM SIGMOD International Conference on Management ofData[C]. Beijing， China， 2007， 593-604.

[3]袁冠，夏士雄，张磊. 基于结构相似度的轨迹聚类算法[J]. 通信学报.2011（9）：103-110.

[4]赵越，刘衍珩，余雪岗，等. 基于模式挖掘与匹配的移动轨迹预测方法[J]. 吉林大学学报. 2008，38（5）：1125-1130.

[5]章志刚，吉根林. 一种基于FP-Growth的频繁项目集并行化挖掘算法[J]. 计算机工程与应用2014，50（2）：107-110.

[6] CHEN L.， LV M. Q.， CHEN G. C. A system for destination and future route prediction based on trajectory mining[J]. Journal of Pervasive and Mobile Computing， 2010，6（6）：657-676.

[7] ZhouLe， LiJunjie， HuangZhexue， FengShenzhong. Balanced Parallel FP-Growth withMapReduce[J]. Bulletin of advanced technology reseach，2011（6）：47-50.

3 算法与实验

本文实验环境采用4台PC机做分布式环境。操作系统为Ubuntu 14.04 -32bit，Hadoop 2.4.0，CPU为Inter Core i7处理器，主频2.1 GHz，单机内存为512 MB。

3.1 频繁1-项统计

其Map-Reduce算法伪代码如下：

map（key，value）{ //value为事务Ti

for each ki∈Ti do

output；

end

}

reduce（key，value）{//key为一个1-项集，value为其支持数列表[1，1，…，1]

C=0；

for each v in value do

C+=1；

end

ifC/|D|minsup then

output；//输出频繁1-项集及其支持数

end

}

3.2 FP-Growth并行化

其Map-Reduce算法伪代码如下：

map（key，value）{ //value为事务Ti

insert_build_fptree（LFPTree，Ti）；//更新局部FP树LFPTree

}

cleanup（）{

LocalFPGrowth（LFPTree，LFPSet）；//将局部频繁项目集及其支持数放入LFPSet中

for each lfp∈LFPSet do

output；//sup（lfp）为局部频繁项目集lfp的支持数

end

}

reduce（key，value）{//key为项目集，value为其支持数列表

C=0；

for each vi in value do

C+=vi；

end

if C/|D|≥minsup then

output；//输出全局频繁项目集及其支持数

else if

write key into a distribute file；//若暂不确定是否全局频繁，则将其写入分布式文件

end

}

4 结 语

本文结合历史车辆轨迹数据利用改进型的关联规则算法FP-Growth挖掘出轨迹模式索引，并提出基于Map/Reduce算法的轨迹预测方案。在路网中利用索引树对车辆未来轨迹进行预测，预判出车流趋势，为交通管理部门及时做出交通疏导方案的决策提供了支持。

参考文献

[1] J.W.Han， JianPen， Yin YiWen.Mining frequent patterns without candidate generation[C].In the proceedingsof ACM SIGMOD International Conference on Management of Data，Dallas， Texas：2000：1-12.

[2] J. G.LEE， J. W.HAN， WHANG K. Y. Trajectory clustering： a partition-and-group framework [A]. ICMD2007：Proceedings of the ACM SIGMOD International Conference on Management ofData[C]. Beijing， China， 2007， 593-604.

[3]袁冠，夏士雄，张磊. 基于结构相似度的轨迹聚类算法[J]. 通信学报.2011（9）：103-110.

[4]赵越，刘衍珩，余雪岗，等. 基于模式挖掘与匹配的移动轨迹预测方法[J]. 吉林大学学报. 2008，38（5）：1125-1130.

[5]章志刚，吉根林. 一种基于FP-Growth的频繁项目集并行化挖掘算法[J]. 计算机工程与应用2014，50（2）：107-110.

[6] CHEN L.， LV M. Q.， CHEN G. C. A system for destination and future route prediction based on trajectory mining[J]. Journal of Pervasive and Mobile Computing， 2010，6（6）：657-676.

[7] ZhouLe， LiJunjie， HuangZhexue， FengShenzhong. Balanced Parallel FP-Growth withMapReduce[J]. Bulletin of advanced technology reseach，2011（6）：47-50.

3 算法与实验

本文实验环境采用4台PC机做分布式环境。操作系统为Ubuntu 14.04 -32bit，Hadoop 2.4.0，CPU为Inter Core i7处理器，主频2.1 GHz，单机内存为512 MB。

3.1 频繁1-项统计

其Map-Reduce算法伪代码如下：

map（key，value）{ //value为事务Ti

for each ki∈Ti do

output；

end

}

reduce（key，value）{//key为一个1-项集，value为其支持数列表[1，1，…，1]

C=0；

for each v in value do

C+=1；

end

ifC/|D|minsup then

output；//输出频繁1-项集及其支持数

end

}

3.2 FP-Growth并行化

其Map-Reduce算法伪代码如下：

map（key，value）{ //value为事务Ti

insert_build_fptree（LFPTree，Ti）；//更新局部FP树LFPTree

}

cleanup（）{

LocalFPGrowth（LFPTree，LFPSet）；//将局部频繁项目集及其支持数放入LFPSet中

for each lfp∈LFPSet do

output；//sup（lfp）为局部频繁项目集lfp的支持数

end

}

reduce（key，value）{//key为项目集，value为其支持数列表

C=0；

for each vi in value do

C+=vi；

end

if C/|D|≥minsup then

output；//输出全局频繁项目集及其支持数

else if

write key into a distribute file；//若暂不确定是否全局频繁，则将其写入分布式文件

end

}

4 结 语

本文结合历史车辆轨迹数据利用改进型的关联规则算法FP-Growth挖掘出轨迹模式索引，并提出基于Map/Reduce算法的轨迹预测方案。在路网中利用索引树对车辆未来轨迹进行预测，预判出车流趋势，为交通管理部门及时做出交通疏导方案的决策提供了支持。

参考文献

[1] J.W.Han， JianPen， Yin YiWen.Mining frequent patterns without candidate generation[C].In the proceedingsof ACM SIGMOD International Conference on Management of Data，Dallas， Texas：2000：1-12.

[2] J. G.LEE， J. W.HAN， WHANG K. Y. Trajectory clustering： a partition-and-group framework [A]. ICMD2007：Proceedings of the ACM SIGMOD International Conference on Management ofData[C]. Beijing， China， 2007， 593-604.

[3]袁冠，夏士雄，张磊. 基于结构相似度的轨迹聚类算法[J]. 通信学报.2011（9）：103-110.

[4]赵越，刘衍珩，余雪岗，等. 基于模式挖掘与匹配的移动轨迹预测方法[J]. 吉林大学学报. 2008，38（5）：1125-1130.

[5]章志刚，吉根林. 一种基于FP-Growth的频繁项目集并行化挖掘算法[J]. 计算机工程与应用2014，50（2）：107-110.

[6] CHEN L.， LV M. Q.， CHEN G. C. A system for destination and future route prediction based on trajectory mining[J]. Journal of Pervasive and Mobile Computing， 2010，6（6）：657-676.

[7] ZhouLe， LiJunjie， HuangZhexue， FengShenzhong. Balanced Parallel FP-Growth withMapReduce[J]. Bulletin of advanced technology reseach，2011（6）：47-50.