智慧城市大数据中的关联规则挖掘研究
2020-07-09姜群田立伟李蓉蓉黄欣欣
姜群 田立伟 李蓉蓉 黄欣欣
摘 要：為了解决传统关联规则算法在数据存储、挖掘效率和算法的扩展性等方面无法满足智慧城市大数据挖掘需求的问题，采用Hadoop及MapReduce计算框架，实现了数据的分布式存储以及Apriori算法的并行化计算。在此基础上，通过进一步的实验，证明了Apriori算法的挖掘效率及可扩展性。
关键词：关联规则;挖掘;算法
中图分类号：TP311.13;TP393 文献标识码：A 文章编号：2096-4706（2020）02-0020-03
Abstract：In order to solve the problem of the traditional association rule algorithm unable to meet the needs of mining smart city big data in terms of data storage，mining efficiency and algorithm scalability，this paper uses Hadoop and MapReduce computing frameworks to implement distributed storage of data and parallelized Apriori algorithm. On this basis，through further experiments，the efficiency and scalability of Apriori algorithm are proved.
Keywords：association rule;mining;algorithm
0 引 言
智慧城市利用多种现代技术提高医疗、交通、能源、教育和生活服务的质量及效率。随着城市智能化的广泛开展，所产生的数据量越来越大，这些数据往往是TB甚至PB级的、异构的和多学科的，很难直接被使用[1]。怎样从这些数据中提取有价值的信息，发现信息之间的联系，进一步为智慧城市的决策和维护提供支持，成为当前亟待解决的问题。数据挖掘中的关联规则挖掘是解决此类问题潜力最大的现代技术之一，它能够发现隐藏在大数据集中的关联链接。然而，传统的关联规则算法Apriori算法需要多次搜索事务库，容易造成很大的I/O开销、时间开销及可能的内存溢出等问题。因此，应用大数据平台并行化算法成为解决智慧城市大数据挖掘的关键问题。笔者在广东科技学院高校重点平台建设跃升计划类基金项目的子项目“数据学科与大数据技术专业——数据分析、数据挖掘与机器学习方向科研支撑项目”的支持下，对算法的并行化进行了研究，本文是该研究的成果。
1 关联规则挖掘
1.1 关联规则
数据挖掘也称为KDD，指的是从数据库中挖掘大量数据以揭示隐含的、未知的和可能有用的信息。关联规则挖掘是数据挖掘的重要分支[2]。关联规则挖掘用于发现隐藏在大数据集中的关联链接。
1.1.1 基本概念
关联规则挖掘是一种基于规则的机器学习方法，用于发现大型数据库中项集之间的相互关系，旨在使用支持度及置信度技术来识别数据库中的强关联。在事务数据库中，项的集合称为项集，包含K个项的项集称为K-项集。设有项集X和项集Y，支持度support（X->Y）=（同时包含项集X和项集Y的事务数/事务总数）×100%，即支持度为X，Y同时出现的概率;置信度confidence（X->Y）=（同时包含项集X和项集Y的事务数/包含项集X的事务数）×100%，即置信度为条件概率P（Y|X）。如果支持度和置信度均大于给定的阈值，即：support（X->Y）≥最小支持度阈值，并且confidence（X->Y）≥最小置信度阈值的关联规则称为强关联规则。关联规则挖掘主要是通过对强关联规则的挖掘发现数据之间的关联程度。
1.1.2 关联规则挖掘过程
关联规则的挖掘过程主要包含两步[3]：首先，找出支持度大于或等于所设定的最小支持度的所有项集，即找到数据库中所有频繁项集;然后对频繁项集应用最小置信度限制条件产生强关联规则。虽然第二步比较直接，但要找到数据库中所有的频繁项集，需要搜索数据库中所有可能的项集是很难的，而Apriori算法采用广度优先搜索，很好地解决了问题。
1.2 Apriori算法
Apriori算法是挖掘布尔关联规则频繁项集的算法，它有效地采用了广度优先逐层搜索的迭代方法，使搜索过程快速完成。算法流程如下：
（1）找出频繁项：数据库中所有出现频率大于或等于最小支持度阈值的项。
（2）找出频繁项集：由频繁项产生候选项集，并剪枝。
（3）找出强关联规则：由频繁项集中满足最小支持度阈值和最小置信度阈值的规则产生。
Apriori算法核心伪代码：
Ck as a candidate itemset of size k.
Lk as a frequent itemset of size k.
L1= {frequent items};
For （k= 2; Lk-1！ = ?; k++） do begin
Ck= candidates generated from Lk-1;
For each transaction t in database D do
Incrementing the count of all candidates in Ck that are contained in t
Lk = candidates in Ck with min_sup
End
return ∪K LK //all frequent itemsets;
由于算法需要多次扫描事务数据库进行候选计数，导致Apriori算法的效率相对较低。在最坏的情况下，会产生相当多的非频繁候选项集，并且计算成本较高，特别是当候选集相对较长的时候，时间和空间受到挑战。本文采用MapReduce编程框架并行化Apriori算法，由于MapReduce数据分片，降低了时间成本，提高了挖掘效率。
2 MapReduce
MapReduce[4]是Hadoop的核心计算框架，用于支持计算机集群上大型数据集的分布式计算。MapReduce将复杂的、大规模集群上的并行计算过程抽象到Map函数和Reduce函数上，其核心思想是“分而治之”——把用户的原始数据源进行分块，分发给由一个主节点管理下的各个分节点共同并行处理完成。
2.1 Map函数
Map函数的输入来自HDFS的文件块，文件块是一系列元素的集合，Map函数对以键值对形式的输入元素根据需求进行处理，转换成新的
2.2 Reduce函数
Reduce函数根据key值进行排序，将具有相同key值的键值对组织在一起，输出Reduce函数处理后的键值对，所有输出结果会合并成一个文件。
在MapReduce模型中，程序员不需要关心数据通信的细节，因此在MapReduce模型中，
3 实验过程
3.1 实验运行环境
实验基于具有以下硬件配置的PC：Intel（R）Core（TM）i7-6500U，CPU @ 2.50 GHz * 4，8.00 GB RAM和1 TB硬盘，64位操作系统。软件环境使用相同的配置：Linux操作系统（Ubuntu 16.04），Cloudera–QuickStart-VM，选用VirtualBox虚拟机。
3.2 数据集
本实验使用的大数据来自网站[7]，该数据是比利时法兰德斯地区的智能交通事故数据集，共包含340 184个交通事故记录，572个不同的属性值，平均每个事故包含45个属性。交通事故数据包含有关事故发生的不同情况的大量信息：事故过程（碰撞类型、道路使用者、受伤情况……）、交通状况（最大速度、优先规则……）、环境条件（天气、光照条件、事故发生时间……）、道路状况（路面状况、障碍物……）和地理状况（地点、物理特征……）等。
3.3 实验结果
Apriori算法用Java实现，最小支持度设定为30%，其运行结果如表1所示。
从表1中可以看出有用的关联，比如高速公路（HIW）附近地区（COL）的交叉口（INT）比非高速公路（NHW）地区更容易发生两轮车事故（1）。高速公路上多车道（MVHNLT）和固定物/分隔物（FO）撞击事故多发生在夜间（T6），并且高速公路上的交叉口是发生此类撞击事故的一个道路特征。此外，晚上在森林地带（FOR）和农业区域（AGL）附近的道路易发生车辆翻车事故（TWH）……
基于MapReduce的并行Apriori算法用于从大数据集中提取频繁项集，并获取有助于决策的关联规则，但为了进一步提高挖掘效率，下面比较当数据集的大小增加时的运行时间效率。
3.4 不同数据集及节点数的运行效果比较
该实验在两个不同数据集上测试算法的性能，两个数据集分别包含150 000个事务和340 000个事务，并且在具有不同数量节点的Hadoop集群上运行。Apriori算法在两个数据集的第1～第6个节点上运行，以便比较运行算法所需的时间。获得的结果如图2所示。
本文使用速度增加作为标准来测量基于MapReduce的并行Apriori算法的性能。当节点数量增加时，计算和传输并行执行，在这种情况下，速度随着数据数量的增加而增加，这证明并行计算Apriori算法可以提高大规模数据集的挖掘速度，并且具有可扩展性。
4 结 论
本文使用MapReduce模型并行化Apriori算法。实验结果证明：当节点数量增加，Apriori的并行化运行速度增加;当节点数不变，数据量成倍增加，不会导致并行化运行速度成倍减少。因此，Apriori的并行化不仅能够解决智慧城市大数据的关联挖掘难题，还能提高数据挖掘效率，且扩展性良好。未来的工作是优化算法设计，以减少扫描事务数据库和保存数量庞大的频繁项候选集的开销。
参考文献：
[1] 覃雄派，王会举，杜小勇，等.大数据分析——RDBMS与MapReduce的竞争与共生 [J].软件学报，2012，23（1）：32-45.
[2] HIPP J，G?NTZER U，NAKHAEIZADEH G. Algorithms for association rule mining——a general survey and comparison [J]. ACM SIGKDD Explorations Newsletter，2000，2（1）：58-64.
[3] 何小东，刘卫国.数据挖掘中关联规则挖掘算法比较研究 [J].计算机工程与设计，2005（5）：1265-1268.
[4] 姜群，傅瑜，李文生，等.基于谓词的大数据抽样技术研究 [J].重庆理工大学学报（自然科学），2017，31（8）：120-124+203.
[5] Lars Vogel. MapReduce Introduction-Tutorial [EB/OL]. [2016-10-10].http：//www.vogella.com/tutorials/MapReduce/article.html.
[6] 孟小峰，慈祥.大数据管理：概念、技术与挑战 [J].计算机研究与发展，2013，50（1）：146-169.
[7] NIS. Frequent Itemset Mining Implementations Repository [EB/OL].[2012-04-06].http：//fimi.ua.ac.be/data/.
作者简介：姜群（1959-），女，汉族，重庆人，副教授，双硕士学位，主要研究方向：大数据挖掘、智能计算研究;田立伟（1979-），男，汉族，山东潍坊人，副教授，博士，主要研究方向：云计算大数据。
