基于频繁项集挖掘算法的伴随车应用与实现

陈 瑶 桂 峰 卢 超 王 华

1(上海市计算技术研究所 上海 200040)2(同济大学电子与信息工程学院 上海 201800)

基于频繁项集挖掘算法的伴随车应用与实现

陈 瑶1桂 峰2卢 超1王 华1

1(上海市计算技术研究所 上海 200040)2(同济大学电子与信息工程学院 上海 201800)

随着大数据技术的发展和交通数据量迅速膨胀的挑战，对海量交通数据进行伴随车挖掘已然成为研究热点。提出一种基于Spark计算框架的频繁项集挖掘算法应用于伴随车挖掘模块当中，对海量的卡口交通数据进行Hadoop分布式文件存储(HDFS)，并将伴随车挖掘结果可视化地展示在集成系统当中。以实际项目为依托，从而验证该伴随车模块的实现具有实际意义，并可为交通管理者提供科学的辅助决策。

HDFS Spark计算框架 频繁项集挖掘 伴随车

0 引 言

随着交通系统中硬件设施的逐年更新和完善以及道路卡口识别系统的广泛应用，使得前端卡口设备采集的数据量越来越庞大。据统计，在北京、上海、广州等这些交通繁忙的一线城市中，一些交通要道卡口位置的平均车流量为3 000辆/小时，一个交通卡口一天的数据采集量可达到6万条。以上海某区为例，该区有42个卡口位置，每天该区卡口过车数据采集量可达100万条。由此可见，卡口设备采集数据已经进入大数据时代。

由于车辆相关的刑事案件和治安案件的发现呈现逐年上升的趋势，如何从多源动态的海量交通数据中挖掘有价值的信息，为治安管理者提供决策支持的方案，已成为当前交通领域研究的热点和重点，其中对伴随车挖掘已然成为一个重要的应用方向。方艾芬等提出一种基于FP-Tree关联规则的伴随车挖掘算法，该方法在内存中构造FP-Tree，当数据规模庞大时，会对内存造成较大压力[1]。曹波等提到基于Spark框架的FP-Growth算法进行伴随车挖掘，相较于方艾芬提出的方法，尽管缓解了内存压力，然而其产生频繁子集的效率不高[2]。张笑达等提到一种矩阵剪枝的频繁项集挖掘算法，该算法根据预判条件，有效地避免产生冗余候选频繁项集[3]。然而对于数据集庞大的事务数据库，无法进行分布式算法的运算，从而降低了算法的效率。

综上所述，本文旨在探讨伴随车功能的应用与实现，将一种改进的关联规则算法——基于Spark的频繁项集挖掘算法应用于伴随车的挖掘，并结合Hadoop大数据平台对海量交通卡口数据采用分布式文件系统的方式存储，最后将伴随车挖掘结果以直观、简洁的可视化方式呈现。本文针对数据、算法、视图这几个层次，分别从伴随车分析、设计、实现、以及成果展示几个部分，阐述了伴随车功能的应用实现，并最终以实际项目为依托，验证了该设计方法的可行性与实际意义。

1 伴随车分析

伴随车是一个交通术语，是指在规定的时间段内，与追查车辆存在伴随关系的车辆以一定概率存在时，且该概率大于设定的概率阈值，则该具有伴随关系的车辆即为追查车辆的伴随车[2]。由伴随车的定义可知，要判断两辆车之间是否有伴随关系，首先要根据卡口设备识别出来的车牌信息，规定在一定的时间范围内(既定义中的时间阈值)，经过相同监测地点的车辆集合，均视为存在伴随关系。例如车辆A，规定的时间阈值为5分钟，如果A经过某一个方向的路口的时间是18:00，那么在17:55到18:05之间经过相同方向、相同路口的车B视为一次伴随关系。当车辆A和车辆B存在伴随关系次数的频次达到一定高度时，可确定A和B是嫌疑伴随车辆。

所以，伴随车的查找实际上可以转化为数据挖掘中频繁项集挖掘的问题[4]。从海量的原始过车数据中查找出频繁出现的车辆集合，通过设定的最小支持数(即是最少伴随次数)，从而筛查出嫌疑伴随的车辆集合。

2 伴随车应用的设计

伴随车的挖掘模块是基于Hadoop平台实现的，因此将原始卡口交通数据的文本文件以Hadoop分布式文件系统HDFS的方式保存，做为底层的数据服务层支持分布式运算。基于对引言中前人对频繁项集算法的研究，并以实际课题项目的海量卡口数据为基础，本方案中算法层采用基于Spark的矩阵剪枝频繁项集挖掘算法。因为Spark计算框架的并行化机制，可以使算法结果缓存于集群的内存当中，有效地避免大量磁盘I/O操作。矩阵剪枝的频繁子集挖掘可以减少冗余候选频繁项集产生，缓解内存压力，提高算法效率[5]。最后通过异构平台的结果解析，反馈伴随车挖掘结果。因此伴随车应用的设计方案如图1所示。

图1 伴随车模块设计

3 伴随车应用的实现

3.1 数据预处理

本文基于实际课题项目，以上海某区的卡口数据为基础示范数据。该原始卡口交通数据存储在Oracle数据库当中，包括过车信息表、卡口位置表、卡口设备信息表等27张表，其中最主要的过车信息表是一张动态表，包括车牌信息、车辆颜色、过车时间、过车速度、卡口编号、卡口方向、等20多个字段。该表实时接受并存储前端卡口设备采集的过车信息[6]。

1) 数据清洗

车牌识别技术是伴随车挖掘的基础，由于前端设备受天气等各方面因素的影响，无法保证百分之百正确识别车牌，因此将对过车信息表中一些无用车辆信息从数据库中清洗掉。在原始数据库中，车牌号为“000000”以及“无车牌”的过车数据均视为无效数据，如图2所示，方框内的数据均是无效的过车数据。

图2 过车信息表中的无效数据

2) 数据规约

伴随车挖掘过程中，只需要过车信息表中车牌号码、卡口编号和过车时间这三个字段，因此需将这三个字段从过车信息表中提取出来，以空格分隔，并将数据保存在文件中。

3) 数据转换

基于Spark的伴随车挖掘算法要求将原始的一条条过车数据转换成原始事务数据库中的事务。转换规则是：对于任意某辆车，将与其经过同一个卡口和相同方向的前后1 min内的车辆集合做为一条事务。在Spark平台下生成的原始事务数据库流程如图3所示。

图3 基于Spark的事务数据库生成流程

首先通过调用textFile()函数读取HDFS上的原始过车数据，得到一个弹性分布式数据RDD(Resilient Distributed Datasets)，该RDD中的每个元素是由车牌号码、卡口编号和过车时间组成的三元组(id,n,t)；其次通过调用map()函数，将上述三元组转换成一个key-value键值对，其中key对应三元组中的卡口编号n，value值是由车牌号码和过车时间组成的二元组(id,t)，从而获得一个包含键值对的RDD；然后通过groupByKey()函数的调用，将上一步中得到的键值对RDD按照key值(即卡口编号)进行分组，得到另一个包含键值对的RDD，该键值对中的key值即为卡口编号，value值为该卡口编号方向的所有车牌号码n及其过车时间t所组成的二元组；最后调用mapPratitions()函数，按照转换规则，最终得到一个事务RDD，该事务RDD中的每个元素即为一个伴随关系的车辆集合。至此便完成了原始过车数据到事务数据的转换。

3.2 算法应用

伴随车的挖掘算法采用基于Spark的矩阵剪枝频繁项集挖掘算法，该算法依据传统关联规则Apriori算法进行改进[7]。为降低内存占用，本方案使用BitSet数据结构表示事务数据库中每个项目的支持数，同时结合矩阵剪枝的挖掘特点，在产生候选频繁k-项集矩阵M时(k>1)，采用HashMap数据结构代替矩阵M右上角的元素。算法的挖掘过程分为两步：

(1) 计算频繁1-项集和2-项集矩阵。如图4所示为伴随车挖掘算法的步骤一。

a.首先读取HDFS中的原始事务数据库，该原始事务数据库就是3.1节中由原始数据转换得到。通过调用cache()函数将事务数据库缓存在Spark集群内存。

b.调用flatmap()函数，可以得到一个存储项目的RDD，这个RDD逻辑上包含事务数据库的全部事务。

c.通过调用reduceByKey()函数可以计算每个项目在原始事务数据库中的支持数，得到一个存储的RDD，其中value值为项目在事务数据库中实际的支持数，得到了键值对的RDD。

d.对上一步中的RDD执行filter()函数，该函数通过value值与最小支持数s对比，找出符合要求的键值对，并按照value值升序排列获得一个有序的RDD。

e.提取上一步RDD中的key值即为频繁1-项集，通过调用cache()函数，将其保存在集群内存中，同时将计算所得频繁1-项集对应的Bitset数据广播到集群的节点上。

f.根据上一步中广播的Bitset数据，计算2-项集矩阵M，如前文中讨论的，此处的矩阵M采用HashMap数据结构形式存储其上三角的数据。该HashMap键值对是一个嵌套的HashMap结构，其中的key值为频繁1-项集，value值仍是一个HashMap数据，内部这个HashMap的键值对中，key为可能组合成为频繁2-项集的候选频繁1-项集，value为这个候选频繁2-项集的支持度计数[8]。最后将该嵌套HashMap数据结构的Bitset广播到集群节点，以支持后续计算使用。

图4 伴随车挖掘算法步骤(一)

(2) 由频繁k-项集集合迭代计算出频繁(k+1)-项集集合(k≥1)，直到算法停止。如图5为伴随车挖掘算法的步骤二。

a.首先判断频繁k-项集集合Lk中的个数是否大于等于k+1，此为计算频繁(k+1)-项集的前提条件。若判断成立，则算法继续执行，否则算法过程终止，算法结束。

b.根据(1)中广播出去的数据结构，此时在Spark集群内存节点中存在频繁k-项集的HashMap和相应的Bitset的只读数据变量，对频繁k-项集的RDD调用map()函数，计算得到候选频繁(k+1)-项集和其相应的Bitset数据，并返回一个键值对RDD，其中key为频繁(k+1)-项集候选集，value是其对应的Bitset。

c.对上一步中产生的候选(k+1)-项集RDD调用filter函数和map函数，筛选出支持数不小于最小支持数s的频繁项，这里通过计算Bitset中“1”的个数大于等于s即可，最终得到逻辑上存储频繁(k+1)-项集的RDD。

图5 伴随车挖掘算法步骤(二)

4 成果展示

4.1 运行环境

伴随车的挖掘所需要的Spark集群环境由3台高配置的PC机组成。部署模式为Standalone，即ClusterManager为Standalone模式。部署过程中我们将Master节点的PC机同时赋予其Worker节点角色，可以使得集群中增加一个Worker工作节点。每套机器的配置如表1所示。

表1 Spark集群的PC机配置

伴随车的挖掘算法需要Hadoop组件中的HDFS提供数据存储，因此还需搭建Hadoop集群，算法挖掘集群的软件配置如表2所示。

表2 集群软件配置

伴随车数据文件存放在本地电脑根目录下的文件夹“AccompanyCar”中，该文件夹中一共有82个数据文本，对应某区的82个交通卡口数据采集设备。在客户端通过Hadoop命令“hadoop fs -mkdir /accompanycar_input”在HDFS文件系统下建立一个伴随车输入文件夹，然后利用“hadoop fs-copyFromLocal/AccompanyCar/* /accompanycar_input”将本地伴随车输入数据上传到HDFS文件系统中[9]。

4.2 运行效果

伴随车挖掘的结果集是保存在本地的一个文件当中，其挖掘结果如图6所示。

图6 伴随车挖掘结果

该伴随车结果集中的每条数据格式如下：

车牌号car1：([与car1形成伴随关系的车辆集合]+伴随次数)

即以车牌“京GS3006”为例，伴随车的结果为([沪FU6527，沪B52710，…沪DK5578，京GS3006]，7)时，则表示车牌为沪FU6527和沪DK5578等车辆集与“京GS3006”的车辆有7次伴随关系，故被检索为具有伴随嫌疑的车辆。

在对伴随车结果进行可视化时，我们采用B/S结构，使用Java语言在Eclipse平台进行开发，对伴随车挖掘结果文件进行解析，解析的关键代码如下：

BufferedReader br=null;

try{

br = new BufferedReader(new InputStreamReader(new

FileInputStream(request.getSession().getServletContext().

getRealPath(″″)+″/upload/car.txt″), ″UTF-8″));

while(br.ready()){

line=br.readLine();

_carName=_line.substring(0,_line.indexOf(″([″));

followcar=_line.substring(_line.indexOf(″([″)).split

(″),([″);

for(i=0;i

followcars=followcar[i].replace(″([″, ″″).split(″],″);

_c+=″″+

followcars[0]+″″+followcars[1].replace(″)″,

″″)+″″;

}

}

br.close();

}finally{

if(br!=null){

br.close();

br=null;

}

}

解析后的结果以表格的形式显示在伴随车的系统模块当中，伴随车功能实现的效果如图7所示。

图7 伴随车功能展示

5 结 语

本文中提出的伴随车功能的实现，以海量的卡口交通数据为基础，对海量数据采用HDFS的方式进行分布式存储，并采用基于Spark计算框架的频繁项集挖掘算法，高效地从海量数据中进行伴随车功能的挖掘。最终以直观友好的界面展示在系统的伴随车模块当中，为交通运输的管理者提供辅助决策的功能。由于伴随车的挖掘结果与伴随车功能实现实行异构平台的交互，因此文中的方案具有良好的可扩展性。下一步将对伴随结果的可视化工作做进一步研究，或采用processing等可视化工具进行结果展示，以丰富大数据挖掘的成果呈现。

[1] 方艾芬,李先通,蔄世明,等.基于关联规则挖掘的伴随车辆发现算法[J].计算机应用与软件,2012,29(2):94-96,144.

[2] 曹波,韩燕波,王桂玲.基于车牌识别大数据的伴随车辆组发现方法[J].计算机应用,2015,35(11):3203-3207.

[3] 张笑达,徐立臻.一种改进的基于矩阵的频繁项集挖掘算法[J].计算机技术与发展,2010,20(4):93-96.

[4] 陈慧萍,王建东,王煜.一种高效的最大频繁项集挖掘算法DFMFI-Miner[J].计算机仿真,2006,23(7):79-83.

[5] 吴湘华,张祖平.Apriori算法中频繁项集求法的改进[J].科技创新与应用,2013(15):58.

[6] 蔡昌理.郫县公安局机动车缉查布控系统设计与实现[D].成都:电子科技大学,2014.

[7] 张忠平,李岩,杨静.基于矩阵的频繁项集挖掘算法[J].计算机工程,2009,35(1):84-86.

[8] 郑志娴.基于云计算的Apriori算法设计[J].莆田学院学报,2014,21(5):61-64.

[9] 刘亚光.实时同步云存储客户端的设计与实现[D].大连:大连理工大学,2014.

APPLICATION AND REALIZATION OF ESCORT VEHICLE BASED ON FIM ALGORITHM

Chen Yao1Gui Feng2Lu Chao1Wang Hua1

1(ShanghaiInstituteofComputingTechnology,Shanghai200040,China)2(SchoolofElectronicsandInformationEngineering,TongjiUniversity,Shanghai201800,China)

With the development of big data technology and the challenge of the rapid expansion of traffic data, escort vehicle data mining to the massive traffic data has become a hot research area. In this paper, a frequent itemset mining (FIM) algorithm based on Spark computing framework is proposed, which is applied to the escort vehicle mining module, using HDFS to store the massive traffic bayonet data and visualization display the result of escort vehicle mining in the integrated system. Based on the actual project, this paper proves that the verification of the escort vehicle mining module has practical significance, and can provide scientific auxiliary decision for the traffic management.

HDFS Spark computing framework FIM Escort vehicle

2016-03-31。上海市科学技术委员会应用技术开发专项(2014-104)。陈瑶，硕士，主研领域：应用软件开发。桂峰，硕士。卢超，工程师。王华，教授级高工。

TP3

A

10.3969/j.issn.1000-386x.2017.04.011