基于Hadoop的频繁项集挖掘算法在图书借阅数据中的应用
2017-07-05彭增焰吴东张立敏
彭增焰++吴东++张立敏
摘 要针对挖掘图书借阅记录中蕴含价值的问题，以图书分类号作为图书特征，给出了结合Apriori的频繁项集挖掘算法。针对海量图书借阅记录难以处理的问题，将频繁项集挖掘算法融入Hadoop大数据平台，设计了基于Hadoop的频繁项集挖掘算法，有效解决了数据存储和并行处理的问题。实验结果表明，部分图书之间的关联程度高。
【关键词】频繁项集 图书 Hadoop Apriori MapReduce
1 引言
随着数字化校园不断发展，高校图书馆积累了海量的信息，如图书入库、读者信息、图书借阅信息和图书书架排列等信息。面对海量图书数据，虽然给图书馆管理工作带来了一定的挑战，但其蕴含的大数据价值高，若能够从中有效挖掘图书间的内在关系，既能提高管理效率，又能方便读者查阅图书。
学者们对挖掘图书信息蕴含的内在关系进行了大量研究，文献[1]和文献[2]主要采用关联规则的Apriori算法分析读者借阅的图书之间的关联度，文献[3]直接使用SPSS的关联规则模块挖掘深圳大学图书馆一学年的流通数据。
学者们侧重于挖掘图书之间的蕴含关系，但随着大数据时代的到来，现在的数据处理方式逐渐不能适应图书借阅记录剧增的情况，迫切需要寻找一种有效应对海量图书数据处理的方法。Hadoop[4]是一种大数据离线处理技术，非常适合对海量的图书数据进行处理。本文先介绍基于Apriori的频繁项集挖掘算法，以及Hadoop大数据技术基本原理，通过结合两者设计出基于Hadoop的频繁项集挖掘算法。
2 频繁项集挖掘算法
频繁项集挖掘，需收集并清洗原始数据集，该数据集称为事务数据；针对事务数据，统计各项集之间出现的次数，一般可取出现频率靠前的项集作为频繁项集。为提高频繁项集的求解效率，常采用Apriori算法进行优化。结合Apriori的频繁项集挖掘算法包括事务数据清洗、1项集求解、k项集迭代求解的过程。
2.1 事务数据清洗
过滤不符合格式的数据，根据实际场景生成新的事务数据。
2.2 1项集求解
扫描每条事务数据记录，分解出每一项，并计数1，最后统计每一项出现的总次数，取靠前的项集作为频繁1-项集。
2.3 k项集的求解
k项集的生成依赖k-1项集，若k-1项集完全自连接，生成的候选k项集组合庞大，且容易生成部分无效k项集，降低算法效率，常采用Apriori算法对候选k项集生成过程进行优化。Apriori算法优化的基本原理[4]如下：
（1）频繁项集的任何非空子集都是频繁的。
（2）非频繁项集的任何超集都是非频繁的。
生成k项集阶段，包括了连接和剪枝过程，其中两个k-1项集进行连接的条件是：它们至少有k-2项相同。
3 Hadoop大数据技术
Hadoop是一门已应用于实际生产环境的大数据离线处理技术。Hadoop生态系统成熟完善，包含数据收集、数据存储、数据管理与数据处理分析等组件。其中数据存储使用分布式文件系统（HDFS）、数据处理使用分布式并行计算编程模型（MapReduce）。
3.1 HDFS
HDFS[4]是Hadoop默认的分布式文件系统，包括一个NameNode和多个DataNode。NameNode是负责元数据管理的主节点，DataNode是数据存储的从节点。文件在HDFS上存储时，是以数据块的方式存储管理的，一个数据块大小为64MB（Hadoop1.0），每个数据块采用保存3个副本的策略，保证了系统的高可靠性。
3.2 MapReduce
MapReduce[4]是Hadoop的并行处理计算模型，包括两个重要的阶段：Map和Reduce阶段。MapReduce编程模型如图1所示。
3.2.1 Map阶段
针对每个InputFormat定义的split逻辑数据块，系统会启动一个map任务，通过RecordReader将字节流数据转为一条条的记录，默认记录为一个键值对<当前行偏移量，一行内容>。每个键值对将会被用户重写的map函数处理，该函数往往是数据处理中需重点设计的地方，经过map函数后会发射出一个新的键值对，待下一阶段处理。
3.2.2 Reduce阶段
首先远程获取map任务节点中特定分区的数据，然后对数据进行排序，归并具有相同键的键值对。针对每个归并后的键值对将会被用户重写的reduce函数处理，该函数的逻辑关系也是需要被重点设计，最后将新的键值对输出到HDFS文件系统上。
map函数和reduce函数的设计是MapReduce并行处理数据的重点，但仅仅设计这两函数是不够的，一般还需要做一些初始化操作，往往通过重写setup函数来实现。setup函数在每个map任务中只执行一次，执行后再循环执行map函数或reduce函数。
4 基于Hadoop的频繁项集挖掘算法设计
Hadoop大数据技术能解决图书馆海量借阅记录有效被处理的难题，下面详细阐述借助Hadoop技术，实现频繁项集挖掘算法的基本设计流程。
该算法由两大部分组成，一是频繁1项集的求解，二是频繁k项集的求解。
4.1 頻繁1项集求解
算法具体实现步骤如下：
第1步：按行读取清洗后的借阅记录事务数据，由系统生成键值对
第2步：map函数中提取出图书分类号，生成键值对<图书分类号， 1>；
第3步：Combiner函数汇总当前map任务的键值对，生成新键值对<图书分类号， 出现次数>；
第4步：Reduce函数中汇总相同图书分类号的出现次数，生成<图书分类号，出现总次数>的键值对，并将其写入HDFS中。
经过以上步骤即可统计出1-项集，一般选取频率高的项作为频繁1-项集。
4.2 频繁k项集求解
本部分以第一部分求解的频繁1项集为基础，输入为图书借阅记录事务数据。算法具体实现步骤如下：
第1步：设定k大小和临时变量i=2。
第2步：加载频繁i-1项集。将i-1项集通过分布式缓存文件的方式发送给每个map任务，在setup函数里加载该文件。
第3步：连接剪枝生成候选i-项集。在setup函数中根据Apriori优化算法对频繁i-1项集进行连接并剪枝，并将生成的候选i-项集保存于全局变量中。
第4步：map函数计算候选i-项集的有效性。遍历候选i-项集，比对当前图书借阅记录事务数据，如果该事务数据包含候选i-项集，则将<当前候选i-项集，1>的键值对发射出去。
第5步：reduce函数根据设定条件生成正式的i-项集。汇总当前候选i-项集出现次数，判断是否大于设定的支持度，若是则将<当前候选i-项集，出现总次数>键值对写入HDFS中。
第6步：如果不存在频繁i-项集，则结束。
第7步：i=i+1，i是否小于等于k，若是返回第2步执行，否则结束。
5 实验
图书分类号采用文献[5]中设定的图书分类方式，在Hadoop平台上分别针对1级图书分类号和2级图书分类号进行频繁项集挖掘。Hadoop平台由4台虚拟机组成，其中1台为主节点，3台为从节点。实验的数据集来源于本校图书馆2010级至2013级的图书借阅记录。
5.1 图书1级分类号的频繁项集
图书1级分类号的频繁1项集和2项集如表1，表中数据是支持度大于100000频繁1项集和支持度大于10000的频繁2项集。
从表1中可以得知，本校图书馆对I类图书需求量最大，在购买图书时，经费可适当往该类倾斜；H类与I类图书、G类与I类图书支持度较高，说明这两组中两个类别的图书被同一读者借阅的可能性较大，在图书分类上架时，可适当考虑将这些图书摆放在相邻位置，方便读者借阅。
5.2 图书2级分类号的频繁项集
由于T类图书的1项集支持度较靠前，因此选择T类图书的2級图书分类号进行频繁2项集挖掘，如表2所示，其中表中列出支持度靠前的5个频繁2项集。
从表2中可以得知，T类2级分类号的图书中，TS类与TP类、TN与TP类图书的支持度都较高，并且TP类图书跟其他T类图书支持度相对较高，合理安排TP类图书的位置有利于提高图书馆的人性化服务程度和服务质量。
6 总结
本文介绍了频繁项集挖掘算法和Hadoop大数据技术，为应对海量图书借阅记录，借助Hadoop技术，实现频繁项集挖掘算法。实验结果清晰表明I、H、G、T、J、K、B类别的图书是比较受读者欢迎，尤其是I类图书；从T类图书的频繁2项集看出，TP类图书是T类图书的核心。图书关联关系不仅对图书管理工作有很大的帮助，还利于提高图书馆的服务质量，也能从一定程度增加读者的借阅次数，更能为图书推荐工作提供支持。
（通讯作者：彭增焰）
参考文献
[1]苟元琴，王钧玉.关联规则在图书馆读者借阅记录中的挖掘应用[J].科技信息，2009（17）：356-357.
[2]何欢.图书流通关联规则分析[J].图书馆杂志，2011（07）：63-68.
[3]侯贺.基于关联规则的图书馆流通数据挖掘——以深圳大学城图书馆为例[J].图书馆学刊，2017（02）.
[4]黄宜华.深入理解大数据——大数据处理与编程实践[M].机械工业出版社，2014：13-122.
[5]彭增焰，吴东.基于协同过滤的高校图书个性化推荐算法研究[J].岭南师范学院学报，2016，376）：103-108.
作者简介
彭增焰（1987-），男，广东省化州市人。硕士学问。岭南师范学院信息工程学院助教，从事大数据技术研究。
作者单位
岭南师范学院信息工程学院 广东省湛江市 524048
