基于map-reduce的移动目标连续轨迹模式挖掘的研究

《基于map-reduce的移动目标连续轨迹模式挖掘的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、模式；数据挖掘中图分类号：TP311文献标识码：A文章编号：2095-1302（2014）10-00-020引言近些年，随着传感器技术在功能、体积和数据传输方式上的不断革新，已得到广泛应用，现在人们身边随处可见各种传感设备在收集信息，一些大型企业和国有单位日收集信息量都已接近TB级。这些收集起来的海量数据中蕴含了很多对企业和社会有巨大价值的信息，如何及时准确地挖掘出这些有利信息成为了一项极富挑战的课题。8首先是如何进行分类和预处理，这些数据资源规模庞大且以指数级形式进行动态变化，对此传统的单一节点的计算能力已捉襟见肘，扩展性差，使得数据挖掘系统的挖掘能

3、力受到了极大的限制。此时需要依靠并行处理，旨在提高整个系统的处理能力，将耗费大量计算资源的计算分散到网络中的多个节点上进行并行处理，处理能力随着节点数目的增长可以近乎无限的扩充。其次是挖掘算法，其关键在于如何从给定的轨迹中挖掘出目标的典型运动模式，目前已有的序列模式挖掘算法并不能满足轨迹模式挖掘的要求，因为其只对序列的前后顺序敏感，无法保证挖掘出的频繁序列是挨个连续的。本文从MAP/REDUCE并行处理的角度出发，结合经过改进的PrefixSpan算法，提出一种基于并行计算的频繁轨迹模式挖掘算法。1MAP/REDUCE模型简述8MAP/REDUCE是G

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

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

6、子任务和R个Reduce子任务）。若某个worker节点被分配Map子任务，则输入已分割好的文件片段，处理成键值对（KEY/VALUE）并调用用户自定的Map函数将输入的键值对转换成中间结果（键值对）。8Map函数生成的中间结果缓存在内存中并会周期性的写入本地硬盘，在分区函数的作用下分成了R个区块，并将它们在硬盘中的位置信息发送给MASTER节点，MASTER节点在收到后会将位置信息转发给那些承接了Reduce任务的WORKER节点。然后这些WORKER节点调用远程程序从负责Map任务的本地计算机的硬盘里读取之前缓存的中间键值对，当读取所有缓存完成后，

7、利用中间结果的KEY值进行排序，将具有相同键的键值对合并，再传递给用户自定的REDUCE函数，生成R个REDUCE结果。最后MASTER节点将这R个结果返回应用程序，由应用程序将其合并形成最终结果。图1Map/Reduce执行过程2连续轨迹模式挖掘算法在以往关于序列模式挖掘的问题上，考虑到性能和效率，普遍采用的是Han等人提出的PrefixSpan算法，但这种序列模式挖掘算法并不能直接运用到轨迹模式挖掘中，本文里使用袁和金提出的改进型PrefixSpan算法。Han等人在2004年发表了基于前缀投影的PrefixSpan算法。该算法的核心思路是：首先扫

8、描一次序列数据库，得到频繁1项集，并产生对应的投影数据库，然后每个投影数据库进行单独的递归挖掘