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

引言

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

1 FP-Growth算法概述

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

FP-Growth 改进

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

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

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

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

Map-Reduce 并行处理

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

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

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

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

对于移动对象数据库D，存储的是海量移动对象在各 时间采样点的位置信息。位置信息在时间上的有序集合为轨 迹，用D={Ti，T2,…,T.）表示，则|D|表示数据库中包含的 轨迹数量。在三维XXYXT空间里，轨迹T是移动对象在空 间内位置信息的有序组合，可以表示为T= （ti，xi，yi），J X2, 乃），…，（tn，x„，yn）„其中t表示时间戳，（Xj，y）表示移动对 象的空间位置坐标。

轨迹匹配，是从频繁模式中找出与查询轨迹片段匹配权 重最高的模式。假设用户的查询轨迹片段为Q = <gq1，gq2,…, gq,>，轨迹频繁模式为P = <gp1，gp2, -，gps>，则Q的预测由 Q和P' =<gp1，gp2，…，gp«>的匹配程度进行反映。轨迹 片段在时间上最靠近当前的元素是优先考虑的，当i<j时,gqj 的权重要小于gq,这里将Wi+1=k*W, k>1, W1默认为1,因此 轨迹Q、P的相似度计算公式为：

如查询轨迹片段Q=<b, c,d>,频繁模式为P<a, c, d, f>, Q和P的公共元素有<c, d>, 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 为事务 T

for each ki (E Ti do

output<ki, 1> ；

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<key, C> ； //输出频繁1-项集及其支持数

end

}

FP-Growth 并行化

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

map (key, value) { //value 为事务 T}

insert_build_fptree (LFPTree, Ti) ； // 更新局部 FP 树 LFPTree

}

cleanup() {

LocalFPGrowth (LFPTree, LFPSet) ； // 将局部频繁项目集及其 支持数放入LFPSet中

for each lfp ( LFPSet do

output<lfp, sup (lfp) > ； //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<key, C> ； //输出全局频繁项目集及其支持数

else if

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

end

}

4结语

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

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