基于Hadoop 的车位空闲模式挖掘方法

2021-02-28张艺琼王海青王锁柱高琳琦

天津师范大学学报（自然科学版） 2021年1期

张艺琼，王海青，王锁柱，高琳琦

（1.首都师范大学信息工程学院，北京100048；2.首都师范大学管理学院，北京100048；3.天津师范大学管理学院，天津300387）

近些年，停车市场日益突出的供需矛盾为城市交通发展带来了极大的困扰，静态交通服务设施供给不足导致的停车难、交通拥堵和环境污染等一系列问题逐渐显现.随着相关技术的成熟，智慧社区共享停车服务的兴起，为缓解社区及其周边的停车压力，解决城市交通停车问题提供了更大的发展空间.实现智慧社区共享停车服务的首要问题是有效刻画社区业主的车位空闲模式，其核心是对车位空闲时刻频繁项集的挖掘.

Apriori 算法[1]作为一种经典的数据挖掘算法，在对频繁项集挖掘的问题中展现出很强的优势，它不仅可以在杂乱无章的数据中挖掘出数据之间实际存在的关系，而且还可以给予每种关系准确的支持度.但是，随着数据量的增加，Apriori 算法需要多次反复扫描事务集并记录大量的候选集，容易导致I/O 负载过重，不能及时完成计算任务.为了解决这个问题，相关学者利用其扩展性较好的特点，尝试利用并行和分布式平台来进行频繁模式的挖掘[2].

本文借助Hadoop[3-4]的MapReduce 并行计算框架[5-7]，基于Apriori 算法设计一种车位空闲模式的挖掘方法，并设计实验完成了对社区业主车位空闲模式的挖掘.实验表明，该方法不仅可以有效解决内存溢出的问题，而且，随着数据集的不断扩大，该方法的执行效率明显优于传统方法.

1 问题描述

1.1 车位空闲模式描述

通常，社区停车需求时间一般与附近的商业、办公、医疗等其他类型场所具有明显的互补性.社区大多数业主“朝出夕归”的日常出行行为使得社区停车位在部分时段出现明显闲置，因此具备良好的对外共享条件.本文对停车场管理中心的业主车辆出行行为数据进行分析，从海量业主出行数据中发现闲置车位资源，为实现车位资源对外共享提供基础数据支持.

利用Apriori 算法的思想根据业主的历史出行数据挖掘每个业主相应的闲置车位资源，需要将一天24 h 等间隔 ΔT（可以为10 min，15 min 等）离散化为T 个时段，T=（24×60）/ΔT.设ti表示第（ii=1，2，…，T）个时段Ii=[0：00+（i-1）ΔT，0：00+iΔT]的车位空闲状况，车位闲置时，ti=1，车位占用时，ti=0.由此，使用离散化后的数据构造一个社区业主出行事务集，ti是事务集中的最小计算单元，在挖掘车位空闲模式时，只需利用频繁项集挖掘方法对事务集中的ti进行计算处理.

频繁项集主要通过项的连接和剪枝得到[8-10].连接步骤利用项与项之间遍历组合的方式生成项集；剪枝步骤通过预定义的支持度阈值裁剪掉不满足条件的项集，从而得到满足条件的频繁项集.

利用频繁项集挖掘车位空闲模式时，ti是每条事务中需要进行连接的项，项与项进行连接、剪枝后得到的频繁项集则为业主提供了共享服务的车位空闲模式，每个模式表示对应业主私人车位可以提供共享服务的开始时段Istart和结束时段Iend.

1.2 Hadoop 平台

Hadoop 是一种大数据计算平台，由分布式文件系统HDFS、并行计算框架MapReduce 和资源管理器Yarn构成.Hadoop 具有高可靠、高扩展和高容错等特性，以及对海量数据的高容存储和高速计算等优势[11-13].Spark 是在Hadoop MapReduce 基础上发展形成的一种大数据计算框架，其核心是基于内存的计算.在执行任务时，Spark 将中间数据缓存到内存中，而Hadoop 将中间数据存储在磁盘中.因此，Spark 相对于Hadoop 具有速度优势[14].但是，当数据量超过T 级时，Spark 会出现OOM 内存溢出，导致程序无法运行.Hadoop 集群易于搭建维护，在执行任务时需要更多的磁盘，而Spark 则需要更专业的专家团队维护，在执行任务时需要更多的RAM.所以，Hadoop 的运行成本和开销更低[15-16].

针对本文的问题，在利用频繁项集算法挖掘车位空闲模式时，业主出行数据越多，挖掘到的模式就越准确，所以，需要长期不断采集业主出行数据，根据历史数据挖掘得到具有准确支持度的车位空闲模式，从而为后续车位分配和管理等提供数据支持，这个过程是相对独立的，适合离线计算，而且对实时性要求不高.因此，从数据量计算需求、平台开发成本以及实时性需求等方面考虑，Hadoop 平台更适用于本文问题.

2 车位空闲模式挖掘方法

2.1 频繁项集挖掘方法的改进

在Hadoop 上直接利用Apriori 的方法（HApriori方法）虽然相较于单机方式可以提高计算效率，但在进行项之间的连接时会产生大量冗余的候选集，以致消耗更多的时空资源.为减少冗余候选集的生成，进一步提高运行效率，本文通过引入0-1 矩阵改进HApriori 方法，记为HMApriori 方法. 该方法基于Apriori 算法的思想，将日常车位占用行为数据转换成一个0-1 二维矩阵，矩阵的列向量表示事务集中参与运算的项，行向量表示事务集中的一条数据. 与HApriori 方法不同，HMApriori 方法不需要存储实际项元素，只需用0 和1 表示该项的存在情况. 同时，在矩阵的每行每列最后增加1 位标记位，用于标记不满足下次扫描条件的数据.

2.2 HMApriori 方法

业主出行数据事务集记为S={S1，S2，…，SN}，Si为S 中的第i 个事务，项目集为I={I1，I2，…，IT}.将日常车位占用行为数据事务集转换成0-1 矩阵MN×T，

mi，j表示事务Si中Ij项的对应值，若Ij⊆[Tuplea，Tuparr]，则mi，j=1，否则mi，j=0，其中：Tuplea为业主u 离开车位p的时刻，Tuparr为业主u 到达车位p 的时刻.

1 项集定义为C1={Ix；x=1，2，…，T}；k 项集定义为Ck={Ix，Iy，…，Iz；x，y，…，z=1，2，…，T，x，y，…，z 互不相等，|{x，y，…，z}| = k}. k 项集的支持度为SupCk=定的最小支持度，则此k 项集称为频繁k 项集.

若事务Si包含的项目总数为L（L≤k），则该事务中的项在进行连接时，最大可生成k 项集，所以，在生成k 项集之前可以先删除项目总数小于k 的事务.此外，因为频繁集的子集一定是频繁集，所以在进行项连接之前，可以先删除非频繁项所对应的列.基于上述考虑，在原矩阵MN×T中增加行标记和列标记，形成矩阵M（N+1）×（T+1），

其中：mi，T+1记录每行事务包含项目的总数，即第i 行中元素为1 的数量；mN+1，j的值是0 或1，0 表示该列对应的项是非频繁项，1 表示该列对应的项是频繁项.

若行标记mi，T+1＜k，则该行事务进行项连接后不可能生成k 项集，所以直接删去该行的事务数据.列标记值mN+1，j=0 对应的项不需要参与到下一步项集的连接，为此，依次统计2 个值为0 的标记位区间的项目总数Q.若Q≥k，则可以生成k 项集；否则不可能生成k 项集，所以直接略过该区间，跳入下一区间进行判断连接.上述项集连接过程伪码见表1.

表1 HMApriori 的项集连接伪码Tab.1 Pseudo code of itemset connects by HMApriori

HMApriori 的算法流程见图1.

图1 HMApriori 方法流程Fig.1 Flowchart of HMApriori

3 车位空闲模式的MapReduce 设计

MapReduce 是Hadoop 的一个编程模型，主要应用于大规模数据并行计算，由Map 和Reduce 函数组成[17-18].

3.1 频繁1 项集的MapReduce

第1 阶段的MapReduce 用来生成频繁1 项集，同时将结果保存至HDFS 中.首先，根据本地数据建立矩阵，执行Map 函数OneFrequentMapper（Key，Value0）计算频繁1 项集，将每行数据转换成键值对的形式，此时默认输入的键值对为[Key，Value]，Key 为输入文件的编号，Value 为该文件记录的矩阵；经过中间处理后，得到Map 函数的中间键值对[item，IntWritable]，item 为1 项集，IntWritable 为初始计数，默认值为1；接下来执行Reduce 函数，Reduce 的输入为每个Map函数输出的中间键值对[item，IntWritable]，其中item和IntWritable 分别对应Reduce 的Key*和Value*；然后利用OneFrequentReducer（Key*，Value*）整合相同的键，得到每个1 项集的支持度；最后，利用最小支持度minSup 的约束，得到频繁1 项集Key*及其支持度Sup.频繁1 项集的MapReduce 伪码见表2.

表2 频繁1 项集的MapReduce 伪码Tab.2 Pseudo code of MapReduce for frequent 1 itemsets

3.2 频繁k 项集的MapReduce

第2 阶段的MapReduce 用来生成频繁k 项集，同时将结果保存至HDFS 中.在第1 阶段的MapReduce处理后，判断矩阵M 中是否存有数据，若没有数据，则任务停止，否则，执行生成频繁k 项集的MapReduce.首先，执行Map 函数KFrequentMapper（Key，Value），Key 为数据文件的编号，Value 为文件的数据内容；经过中间处理后，得到Map 函数的中间键值对[kitem，IntWritable]，kitem 为k 项集；最后，执行KFrequent-Reducer（Key*，Value*）对中间键值对进行归约处理，得到频繁k 项集Key*及其支持度Sup.频繁k 项集的MapReduce 伪码见表3.

表3 频繁k 项集的MapReduce 伪码Tab.3 Pseudo code of MapReduce for frequent k itemsets

4 车位空闲模式挖掘方法的实现

4.1 实验环境

Hadoop 集群由4 台PC 构成，分别为Master、Slave1、Slave2 和Slave3. Master（172.19.205.158）为NameNode，负责整个任务的分工和数据存储空间的分配，Slave1（172.19.205.159）、Slave2（172.19.205.160）和Slave3（172.19.205.161）为DataNode，负责存储数据，执行任务响应客户端，以及执行NameNode 的读写请求等操作命令.集群架构如图2 所示.

图2 Hadoop 集群架构Fig.2 Hadoop cluster architecture

在Hadoop 集群中，各节点始终通过心跳机制Heart-Beats 保持通信，确保每个节点的基本生命情况和数据的正常读写.此外，采用Hadoop 的Yarn[19-20]框架实现全局资源管理和作业调度.

4.2 实验数据预处理

基于业主的出行行为，社区停车位空闲情况呈现一定的规律性.在业主授权的情况下，可直接从社区物业停车场管理部门获取业主出行数据，这些数据记录了业主基本身份信息和每天出入停车场的时间.为了在这些数据中挖掘到每个业主相应车位的空闲时段，需要对原始数据进行预处理.首先隐去身份信息，统一编码；其次，将原始数据按等间隔ΔT 划分并取值，生成业主出行事务集，事务集包含业主车位ID、日期以及每个时段车位空闲状态取值.

4.3 实验结果分析

采用某社区2014 年到2019 年的停车场出入数据，使用HMApriori 方法对预处理后的数据进行计算，得到每个业主的车位空闲模式. 以集群节点数为4、ΔT=15 min、支持度为80%为例，计算得到车位空闲模式的部分结果见表4.

表4 车位空闲模式部分结果Tab.4 Part of result of parking space idle pattern

实验1 考察不同T 值下，3 种方法Apriori、HApriori 和HMApriori 的执行时间.T=（24×60）/ΔT，时间间隔ΔT 对程序的执行效率有很大影响.选用3×105条业主出行数据，固定支持度为10%，集群节点数为4，图3 给出了不同T 值下3 种方法的执行时间.

由图3 可见，随着T 值增加，3 种方法的执行时间均逐渐变长.当T≤10 时，HApriori 和HMApriori 方法的执行时间高于单机方式的Apriori 方法，这是因为当T 值较小时，传统单机方式进行的项连接步数较少，所以可以在较短时间内得出结果，而HApriori 和HMApriori 除进行项集的连接外，还要多次涉及Hadoop 文件的读写及任务的分配，导致执行时间较长.当10 ＜T≤15 时，Apriori 的执行时间明显高于另2种方法，这是因为单机下Apriori 会生成大量候选集（2T个），造成内存消耗严重，当T ＞15 时，Apriori 方法出现内存溢出，程序无法继续进行.由图3 还可发现，对于不同的T 值，HMApriori 始终比HApriori 耗时少，这是因为HMApriori 利用矩阵压缩了事务集和项集，减少了事务集的扫描次数和项集的连接次数，避免了冗余候选集生成，进而缩短整个程序的执行时间.

图3 不同T 值下3 种方法的执行时间Fig.3 Execution time of 3 methods for different T

实验2 考察HApriori 和HMApriori 在不同支持度下的的执行时间.选用3×105条业主出行数据，固定T = 96，集群节点数为4，图4 给出了支持度为70%、80%和90%，2 种方法的执行时间.由图4 可见，2 种方法的执行时间均随支持度的提高而减少，这是因为支持度上升，频繁项集的规模下降，产生的候选项集数量下降.另外，由图4 还可见，在相同的支持度下，HMApriori 比HApriori 的执行效率更高.

图4 不同支持度下2 种方法的执行时间Fig.4 Execution time of 2 methods for different supports

实验3 考察不同节点数对HMApriori 执行时间的影响.固定T=96，支持度为60%，选用3 个数据集，图5 给出了节点数为1、2、3 和4 的HMApriori 的执行时间，其中：数据集Data1=207 110 kB，Data2=1 191 952 kB，Data3= 7 912 754 kB. 由图5 可见，对于Data1，程序执行时间随节点数的变化不大，这是因为数据量较小时，单个节点的MapReduce 任务就可以完成数据处理，不需要等待其他节点MapReduce任务结束再启动下一个任务.所以，对于数据量较小的数据集，增加节点不会减少执行时间，节点数越多，反而会增加数据存储、任务分配和节点通信等额外开销.对于Data2 和Data3，随着节点数增加，程序执行时间逐渐减少，这是因为节点数的增加可以增加MapReduce 任务的数量，多个任务并行进行显著提高了集群处理数据的效率.