利用Apriori算法对交通路况的研究

首先简单描述一下Apriori算法:Apriori算法分为频繁项集的产生和规则的产生。

Apriori算法频繁项集的产生:

令ck为候选k-项集的集合,而Fk为频繁k-项集的集合.

1.首先通过单遍扫描数据集,确定每个项的支持度。一旦完成这一步,就可以得到所有频繁1-项集的集合F1

2.接下来,该算法将使用上一次迭代的发现的频繁(k-1)-项集,产生新的候选k-项集。候选的产生使用apriori-gen函数实现。

3.为了对候选项的支持度的计算,需要再扫描一遍数据集。使用子集函数确定包含在每一个事务t中的ck中的所有候选k-项集。

4.候选项的支持度计数后,算法将删除支持度计数小于minsup的所有候选项集

5.在没有新的频繁项集产生的时候,即Fk为空时,算法结束。

目前,针对行程时间最短的动态路径导航算法已是很多,可以把他们大致分为三类。

第一类是根据路段的不同时间段,提出基于分时段的路径导航算法。该类算法在路网更新后,以车辆当前所在的路段的下游结点为起点,重新进行规划。但其所分时段由于跨越时间太长,当发生交通事故、交通阻塞是不能及时在导航算法中的到体现,从而使得到的导航路径缺乏实时性。

第二类是实时路径导航,就是将实时的交通数据反馈回来然后进行路径的选择。这类导航算法由于具有随意性,所有很难选择整体的最优路径,相反,还可能花费更长的时间。

第三类将路网看成时间的依赖网络,利用SPTDN算法采用多步预测数据进行路径导航。但是,目前多步预测导航由于步数有限,且预测的步数越多,精度越低。

在这里,基于hadoop中MapReduce的Apriori算法的改进

Mapreduce技术结合HDFS的存储情况,在Map阶段将实验交通数据样本划分成n个数据模块分布在hadoop节点上,每个节点扫描各自节点上的数据块,产生自己的频繁项集。在Reduce阶段将所有的局部频繁项集合起来,产生全局候选频繁k-项集。将每个候选频繁项集的置信度、支持度与定义的两项进行对比,筛选出有效的候选频繁项集,并排序输出,产生关联规则。

在交通车流量分析中,与之相关联的数据为点位编号、经过时间、行驶方向;在车辆超速分析中,与之相关的数据信息为点位编号、行驶方向、车辆速度。通过多车流量分析,来分析某个车道的拥挤情况;对超速数据分析,确定某车道车辆超速情况。

上一篇:IDF实验室:牛刀小试


下一篇:Apriori算法在购物篮分析中的运用