丁家满(1974-), 男, 教授, CCF专业会员, 主要研究领域为数据挖掘, 云计算, 大数据
李海滨(1995-), 男, 硕士生, 主要研究领域为数据挖掘, 云计算, 大数据
邓斌(1997-), 男, 硕士生, 主要研究领域为数据挖掘, 软件工程
贾连印(1978-), 男, 博士, 副教授, CCF专业会员, 主要研究领域为数据库. 数据挖掘
游进国(1977-), 男, 博士, 副教授, CCF高级会员, 主要研究领域为大数据分析, 数据仓库, 图数据
如何在海量数据集中提高频繁项集的挖掘效率是目前研究的热点. 随着数据量的不断增长, 使用传统算法产生频繁项集的计算代价依然很高. 为此, 提出一种基于Spark的频繁项集快速挖掘算法(fast mining algorithm of frequent itemset based on spark, Fmafibs), 利用位运算速度快的特点, 设计了一种新颖的模式增长策略. 该算法首先采用位串表达项集, 利用位运算来快速生成候选项集; 其次, 针对超长位串计算效率低的问题, 考虑将事务垂直分组处理, 将同一事务不同组之间的频繁项集通过连接获得候选项集, 最后进行聚合筛选得到最终频繁项集. 算法在Spark环境下, 以频繁项集挖掘领域基准数据集进行实验验证. 实验结果表明所提方法在保证挖掘结果准确的同时, 有效地提高了挖掘效率.
Improving the efficiency of frequent itemset mining in big data is a hot research topic at present. With the continuous growth of data volume, the computing costs of traditional frequent itemset generation algorithms remain high. Therefore, this study proposes a fast mining algorithm of frequent itemset based on Spark (Fmafibs in short). Taking advantage of bit-wise operation, a novel pattern growth strategy is designed. Firstly, the algorithm converts itemset into BitString and exploits bit-wise operation to generate candidate itemset. Secondly, to improve the processing efficiency of long BitString, a vertical grouping strategy is designed and the candidate itemset are obtained by joining the frequent itemset between different groups of same transaction, and then aggregating and filtering them to get the final frequent itemset. Fmafibs is implemented in Spark environment. The experimental results on benchmark datasets show that the proposed method is correct and it can significantly improve the mining efficiency.
随着大数据时代的到来, 各行各业产生的数据量呈爆炸式增长, 人们迫切希望可以快速获取到有价值的信息[
Apriori[
随着数据量的不断增长, 传统单机版算法产生频繁项集的效率愈来愈低下. 频繁项集挖掘由于其迭代计算的特点, 加之众多分布式计算框架的出现, 为并行挖掘提供了可能. Spark[
本文的主要贡献如下.
(1) 针对候选项集生成速度过慢以及重复扫描数据库统计项集支持度计数的问题, 利用位运算速度快的特点, 设计了一种新颖的模式增长策略, 采用位串表达项集, 通过相关位运算一次性生成候选项集, 项集的计数无需通过扫描数据库来获得, 而是等候选项集生成后对所有项集进行聚合得到其计数值.
(2) 针对项集映射为位串可能出现超长位串的问题, 提出事务垂直分组的策略, 对属于同一条事务不同组包含的位串利用位运算首先生成组内频繁项集, 不同组之间通过笛卡尔积产生组间频繁项集, 最后合并得到全部频繁项集.
(3) 结合Spark计算框架, 提出了一种频繁项集的快速挖掘算法——Fmafibs算法;
(4) 利用频繁项集挖掘领域的基准数据集, 在Spark计算环境下进行了详细的实验验证. 验证了本文所提出算法的有效性、运算速率及可扩展性.
为提高频繁项集的挖掘效率, 一些学者提出用二进制位运算来改善候选项集的生成速率和支持度计数的获取方式. BitTable是由文献[
随着数据量的不断增长, 近年来大量基于分布式计算平台的频繁项集挖掘算法被提出. 文献[
挖掘频繁项集就是找出事务型数据库中所有出现频率不小于用户给定支持度阈值的项集. 相关定义如下.
给定
定义
定义
定义
定义
定义
定义
例如,
样例数据库
TID | Item | TID | Item | TID | Item | TID | Item | TID | Item | ||||
1 | 3 | 5 | 7 | 9 | |||||||||
2 | 4 | 6 | 8 | 10 |
频繁项集满足以下性质[
性质
性质
Fmafibs算法的整体示意图如
Fmafibs算法示意图
(1) 生成频繁1项集. 抽取出数据库中所有不同的项, 根据最小支持度计数剪枝非频繁的1项集, 得到频繁1项集, 也即全集.
(2) 位串表达. 根据得到的频繁1项集将事务映射为位串.
(3) 模式增长. 利用位运算方法产生给定位串的所有子集.
(4) 位串分组. 借鉴分治的思想, 对超长位串进行分组, 每组同样用位运算方法生成候选项集.
(5) 位串连接. 对已经分组的位串, 不同组之间可能还存在频繁项集, 通过位串连接生成组间频繁项集.
(6) 挖掘所有频繁项集. 对所有位串进行聚合并解析, 得到全部频繁项集.
传统的产生频繁
第1阶段. 由两个前
第2阶段. 扫描数据库统计候选
上述两阶段过程通常会耗费大量时间. 许多改进的算法在候选
定义
例如, 事务4为{
定义
例如, 给定位串为10101100, 则
项集-位串关系映射
如果一个项集不为空, 则其一定包含确定个数的非空子集. 根据定义7和定义8可知, 当全集确定时, 全集的任一非空子集都可以映射为位串, 并且非空子集对应的位串是其超集对应位串的子串.
定义
例如, 位串01100010, 则其子集为{00000010, 00100000, 00100010, 01000000, 01000010, 01100000, 01100010}, 对应的项集为{
根据上述定义, 我们使用位串的模式增长来代替由频繁
步骤1. 将输入的位串与该位串对应整数的相反数的位串进行“按位与”运算;
步骤2. 将步骤1中的结果对应的整数与最开始输入位串对应的整数相减;
步骤3. 将最开始输入的位串与步骤2的结果进行“按位与”运算, 重复步骤2和3, 直到所得位串各个位全为0.
采用位串模式增长的策略可以加快频繁项集的生成, 但如果一个位串比较密集, 即对应项集中包含的项较多, 直接使用位串模式增长策略, 其整体计算效率会降低. 通过在本文所设实验条件下多次实验发现, 当位串中包含的1的个数超过27 (不同实验条件可能会不同)时会出现上述问题, 本文将包含1的个数超过27的位串称为超长位串. 在求解超长位串的子集时, 我们提出了一种基于事务垂直分组的策略. 首先对全集进行分割, 然后将事务按照全集的分割结果进行投影, 从而将一条事务划分为若干条子事务.
定义
例如, 将全集
定义
例如,
得到全集
事务分组过程
得到组内频繁位串后, 需要将同一事务不同组产生的频繁位串进行连接, 得到组间的频繁位串. 以
位串连接及解析过程
定理
证明: 不失一般性, 假设将某一位串分为2组, 多个组的情形可将2个组连接结果再和第3组连接依次推出.
给定位串
(1) 证明
对任意的元素
(2) 证明
对任意的元素
故二者等价, 定理得证.
算法的第1阶段主要是将存储在HDFS上的数据集载入内存以RDD的形式存储, 统计数据库中包含的所有不同的项, 并对其进行计数, 过滤掉计数值不满足最小支持度计数的1项集, 筛选出频繁1项集, 并将频繁1项集进行分组. 其在Spark中的计算流程图如
频繁1项集的计算过程
步骤1. 初始化SparkContext对象, 使用textFile算子读取存储在HDFS上的原始数据集, 设置RDD分区数, 得到初始RDD:<
步骤2. 计算求得总的事务数量, 与用户设置的支持度阈值
步骤3. 应用flatMap算子和map算子将RDD:<
步骤4. 应用aggregateByKey算子对相同的
步骤5. 应用数组的sliding方法对频繁1项集进行分组, 得到
算法
输入: 事务数据库
输出: 分组后的频繁1项集
1.
2.
3. map(
4.
5. end map
6.
7. map(
8.
9. end map
10.
11.
12.
13. return
算法的第2阶段首先根据频繁1项集将每条事务转换为对应的位串, 然后判断位串是否是超长位串. 如果是超长位串, 则根据频繁1项集的分组结果将超长位串进行分组, 然后对不同组的位串应用模式增长的策略产生子位串集合; 如果某一位串不是超长位串, 则直接使用位串模式增长策略产生位串子集. 流程图如
位串模式增长及分组连接解析过程
步骤1. 应用zipWithIndex算子对每条事务进行编号.
步骤2. 应用map算子将每条事务根据频繁1项集转换为对应的位串.
步骤3. 应用map算子对RDD中的超长位串根据分组后的频繁1项集进行分组.
步骤4. 应用map算子对非超长位串使用BitwiseOperate方法, 产生由位串集合表示的候选项集的集合.
步骤5. 应用map算子对超长位串的不同组中的位串使用BitwiseOperate方法, 产生各组内的候选位串.
步骤6. 应用aggregateByKey算子对相同的位串进行聚合, 应用filter算子过滤掉所有支持度计数值小于最小支持度计数的位串, 得到各组内的频繁位串.
算法
输入: 事务
输出: 非超长位串子集
1. zipWithIndex(
2.
3. end zipWithIndex
4. map(
5.
6.
7.
8.
9. end map
10. map(
11.
12. end map
13. map(
14.
15.
16. end map
17.
18. map(
19.
20.
21. end map
22.
23.
24.
25. return
算法的第2阶段得到了非超长位串的所有子集以及超长位串分组后不同组内产生的位串子集, 本阶段通过对属于同一条事务不同组的位串做连接操作, 生成组间频繁位串, 最后通过聚合、筛选、解析获得全部频繁项集. 流程图如
步骤1. 对同一条事务各组内产生的位串应用join算子做连接操作, 产生组间的候选位串.
步骤2. 应用union和aggregateByKey算子对产生的所有候选位串进行聚合, 应用filter算子过滤掉所有支持度计数值小于最小支持度计数的位串, 得到全部的频繁位串.
步骤3. 将位串根据全集解析为频繁项集.
算法
输入: 位串集合
输出: 全部频繁项集
1. map(
2. if
3. then
4. end if
5. end map
6.
7.
8.
9.
10.
11. return
假设数据库中包含的事务数量为
为了更好地理解本文所提出的算法, 我们将以
事务分组
Group1 (TID, GID, Item) | Group2 (TID, GID, Item) |
(1, 1, |
(1, 2, |
(2, 1, |
(2, 2, |
(3, 1, null) | (3, 2, |
(4, 1, |
(4, 2, |
(5, 1, |
(5, 2, |
(6, 1, |
(6, 2, |
(7, 1, |
(7, 2, |
(8, 1, |
(8, 2, |
(9, 1, |
(9, 2, |
(10, 1, |
(10, 2, |
接下来对每条事务的各组应用BitwiseOperate方法, 根据子全集生成候选项集对应的位串, 例如第一组对应的子全集为{(
项集的位串表达
Group1 (TID, GID, BitString) | Group2 (TID, GID, BitString) |
(1, 1, 001, 010, 011, 100, 101, 110, 111) | (1, 2, 010) |
(2, 1, 001, 100, 101) | (2, 2, 001, 010, 011, 100, 101, 110, 111) |
(3, 1, null) | (3, 2, 001, 100, 101) |
(4, 1, 010) | (4, 2, 010, 100, 110) |
(5, 1, 001, 010, 011) | (5, 2, 100) |
(6, 1, 001, 100, 101) | (6, 2, 001, 100, 101) |
(7, 1, 100) | (7, 2, 001, 010, 011, 100, 101, 110, 111) |
(8, 1, 001, 100, 101) | (8, 2, 010, 100, 110) |
(9, 1, 001, 010, 011, 100, 101, 110, 111) | (9, 2, 100) |
(10, 1, 001, 010, 011, 100, 101, 110, 111) | (10, 2, 001) |
对属于同一组的位串使用aggregateByKey算子进行聚合, filter算子过滤掉每条事务中计数值小于最小支持度计数的位串, 形成的结果如
位串表达的频繁项集
Group1 (TID, GID, BitString) | Group2 (TID, GID, BitString) |
(1, 1, 001, 010, 100, 101) | (1, 2, 010) |
(2, 1, 001, 100, 101) | (2, 2, 001, 010, 100) |
(3, 1, null) | (3, 2, 001, 100) |
(4, 1, 010) | (4, 2, 010, 100) |
(5, 1, 001, 010) | (5, 2, 100) |
(6, 1, 001, 100, 101) | (6, 2, 001, 100) |
(7, 1, 100) | (7, 2, 001, 010, 100) |
(8, 1, 001, 100, 101) | (8, 2, 010, 100) |
(9, 1, 001, 010, 100, 101) | (9, 2, 100) |
(10, 1, 001, 010, 100, 101) | (10, 2, 001) |
得到部分频繁位串后, 使用join算子对同一条事务不同组包含的频繁位串进行连接, 生成各组之间的候选位串, 结果如
各组连接后的位串
(TID, Joined BitString) |
(1, 001010, 010010, 100010, 101010) |
(2, 001001, 001010, 001100, 100001, 100010, 100100,
|
(3, null) |
(4, 010010, 010100) |
(5, 001100, 010100) |
(6, 001001, 001100, 100001, 100100, 101001, 101100) |
(7, 100001, 100010, 100100) |
(8, 001010, 001100, 100010, 100100, 101010, 101100) |
(9, 001100, 010100, 100100, 101100) |
(10, 001100, 010100, 100100, 101100) |
使用aggregateByKey算子进行聚合, filter算子过滤掉非频繁的位串, 得到的频繁位串为(001100, 100100).
至此, Fmafibs算法生成的全部的频繁位串为(001, 010, 100, 101, 001, 010, 100, 001100, 100100), 转换为对应项集为(
Spark计算集群由5个节点构成, 包含1个主节点, 4个计算节点. 每个节点CPU核数均为4, 主节点运行内存为6 GB, 硬盘容量为2 TB, 计算节点运行内存为4 GB, 硬盘容量为2 TB. 每个节点均安装CentOS 6.5, Spark 2.4.5, JDK 1.8.0. 实验程序采用Scala 2.11.5编写, 数据存储平台为HDFS (Hadoop 2.6.0). 实验所用数据集均为频繁项集挖掘领域的基准数据集[
不同数据集的基本特征
数据集 | 不同项的数量 | 事务的数量 | 密集程度 |
Mushroom | 119 | 8124 | 密集 |
Chess | 75 | 3196 | 密集 |
T10I4D100K | 870 | 100000 | 稀疏 |
Kosarak | 41270 | 990002 | 稀疏 |
PAMP | 141 | 1000000 | 密集 |
Chainstore | 46086 | 1112949 | 稀疏 |
为验证Fmafibs算法生成结果的正确性, 实验方案设计如下.
方案1: 验证Fmafibs算法在6个数据集上产生的频繁
方案2: 验证Fmafibs算法在6个数据集上产生的频繁项集的数量是否与FP-Growth产生的结果相同.
之所以这样设计, 是因为当支持度阈值设置较低时, 会挖掘出大量的频繁项集, 不易于直观比对. 所以我们先设置较高的支持度阈值来验证方案1, 当方案1的结果得到正确验证后, 再减小支持度阈值, 验证方案2.
方案1的实验结果如
The frequent itemsets on Mushroom(
Mushroom的频繁项集(
频繁 |
Fmafibs | FP-Growth |
频繁1项集 | [34]:7914 [85]:8124
|
[34]:7914 [85]:8124
|
频繁2项集 | [34-85]:7914
|
[34-85]:7914
|
频繁3项集 | [34-85-86]:7906 | [34-85-86]:7906 |
The frequent itemsets on Chess(
Chess的频繁项集(
频繁 |
Fmafibs | FP-Growth |
频繁2
|
[29-52]:3170 [29-58]:3180
|
[29-52]:3170 [29-58]:3180
|
频繁3
|
[29-52-58]:3169
|
[29-52-58]:3169
|
频繁4项集 | [29-40-52-58]:3143 | [29-40-52-58]:3143 |
The frequent itemsets on T10I4D100K(
T10I4D100K的频繁项集(
频繁 |
Fmafibs | FP-Growth |
频繁2项集 | [368-829]:1194 [529-598]:943
|
[368-829]:1194 [529-598]:943
|
频繁3项集 | [227-390-722]:907
|
[227-390-722]:907
|
The frequent itemsets on Kosarak(
Kosarak的频繁项集(
频繁 |
Fmafibs | FP-Growth |
频繁1项集 | [3]:450031 [6]:601374
|
[3]:450031 [6]:601374
|
频繁2项集 | [3-6]:265180
|
[3-6]:265180
|
频繁3项集 | [3-6-11]:143682 | [3-6-11]:143682 |
The frequent itemsets on PAMP(
PAMP的频繁项集(
频繁 |
Fmafibs | FP-Growth |
频繁1项集 | [44]:927546 [53]:925210
|
[44]:927546 [53]:925210
|
频繁2项集 | [63-134]:892992
|
[63-134]:892992
|
The frequent itemsets on Chainstore(
Chainstore的频繁项集(
频繁 |
Fmafibs | FP-Growth |
频繁2项集 | [16967-16977]:7801 [16967-39684]:4155
|
[16967-16977]:7801 [16967-39684]:4155
|
方案2的实验结果如
Fmafibs与FP-Growth生成的频繁项集个数比较
方案1和方案2的实验结果证明了Fmafibs算法的正确性.
为验证Fmafibs算法的执行效率, 采用运行时间作为性能评价指标, 比对3种算法在6个数据集上的运行时间. 实验结果如
不同算法在4个数据集上的运行时间比较
定义
其中,
Fmafibs算法在不同节点个数下的加速比
从
为验证算法的数据可扩展性, 通过记录3种算法在不同规模数据集上的运行时间来观察对比其性能. 各数据集支持度阈值设置如下: Mushroom: 35%, Chess: 80%, T10I4D100K: 0.3%, Kosarak: 0.6%, PAMP: 20%, Chainstore: 0.1%. 实验结果如
Fmafibs算法的扩展性分析
从
为了提高海量数据中频繁项集的挖掘效率, 本文提出一种基于Spark的频繁项集快速挖掘算法Fmafibs. Fmafibs算法采用位串表达项集, 利用位运算快速生成候选频繁项集. 其次, 通过对事务进行垂直分组可以有效避免超长位串计算效率低的问题, 对分组后的位串采用连接策略生成同一事务不同组之间的候选频繁项集. 最后, 将所有项集进行聚合过滤得到最终频繁项集. 通过位串表达项集, 可以充分压缩事务集, 而位运算可以减少频繁项集的挖掘时间. 实验结果表明本文方法在保证挖掘结果准确的同时, 有效地提高了挖掘效率. 下一步我们将会重点研究事务分组之后是否会发生数据倾斜以及如何合理设置Spark分区数来加快执行速率, 进一步提高算法性能.
Nguyen TL, Vo B, Snasel V. Efficient algorithms for mining colossal patterns in high dimensional databases. Knowledge-Based Systems, 2017, 122: 75–89. [doi: 10.1016/j.knosys.2017.01.034]
http://www.jos.org.cn/1000-9825/5419.htm]]>
http://www.jos.org.cn/1000-9825/5419.htm]]>
Chee CH, Jaafar J, Aziz IA, Hasan MH, Yeoh W. Algorithms for frequent itemset mining: A literature review. Artificial Intelligence Review, 2019, 52(4): 2603–2621. [doi: 10.1007/s10462-018-9629-z]
张春, 周静. 动车组运维效率关联规则挖掘优化算法. 计算机研究与发展, 2017, 54(9): 1958–1965. [doi: 10.7544/issn1000-1239.2017.20160498]
Zhang C, Zhou J. Optimization algorithm of association rule mining for EMU operation and maintenance efficiency. Journal of Computer Research and Development, 2017, 54(9): 1958–1965 (in Chinese with English abstract). [doi: 10.7544/issn1000-1239.2017.20160498]
N-Gram的错误参数检测方法. 软件学报, 2018, 29(8): 2243−2257. http://www.jos.org.cn/1000-9825/5531.htm]]>
N-Gram based detection of incorrect arguments. Ruan Jian Xue Bao/Journal of Software, 2018, 29(8): 2243−2257 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5531.htm]]>
Zaki MJ. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 2000, 12(3): 372–390. [doi: 10.1109/69.846291]
Zhang R, Chen WG, Hsu TC, Yang HJ, Chung YC. ANG: A combination of Apriori and graph computing techniques for frequent itemsets mining. The Journal of Supercomputing, 2019, 75(2): 646–661. [doi: 10.1007/s11227-017-2049-z]
Alghyaline S, Hsieh JW, Lai JZC. Efficiently mining frequent itemsets in transactional databases. Journal of Marine Science and Technology, 2016, 24(2): 184–191. [doi: 10.6119/JMST-015-0709-1]
Zhu XL, Liu YG. An efficient frequent pattern mining algorithm using a highly compressed prefix tree. Intelligent Data Analysis, 2019, 23(S1): 153–173. [doi: 10.3233/IDA-192645]
Zhang CK, Tian PB, Zhang XD, Liao Q, Jiang ZL, Wang X. HashEclat: An efficient frequent itemset algorithm. International Journal of Machine Learning and Cybernetics, 2019, 10(11): 3003–3016. [doi: 10.1007/s13042-018-00918-x]
张鹏, 段磊, 秦攀, 左劼, 唐常杰, 元昌安, 彭舰. 基于Spark的Top-
Zhang P, Duan L, Qin P, Zuo J, Tang CJ, Yuan CA, Peng J. Mining Top-
Dong J, Han M. BitTableFI: An efficient mining frequent itemsets algorithm. Knowledge-Based Systems, 2007, 20(4): 329–335. [doi: 10.1016/j.knosys.2006.08.005]
Song W, Yang BR, Xu ZY. Index-BitTableFI: An improved algorithm for mining frequent itemsets. Knowledge-Based Systems, 2008, 21(6): 507–513. [doi: 10.1016/j.knosys.2008.03.011]
傅向华, 陈冬剑, 王志强. 基于倒排索引位运算的深度优先频繁项集挖掘. 小型微型计算机系统, 2012, 33(8): 1747–1751. [doi: 10.3969/j.issn.1000-1220.2012.08.023]
Fu XH, Chen DJ, Wang ZQ. Depth first frequent itemset mining based on bittable and inverted index. Journal of Chinese Computer Systems (in Chinese with English abstract), 2012, 33(8): 1747–1751. [doi: 10.3969/j.issn.1000-1220.2012.08.023]
Vo B, Hong TP, Le B. DBV-Miner: A Dynamic Bit-Vector approach for fast mining frequent closed itemsets. Expert Systems with Applications, 2012, 39(8): 7196–7206. [doi: 10.1016/j.eswa.2012.01.062]
http://www.jos.org.cn/1000-9825/5341.htm]]>
http://www.jos.org.cn/1000-9825/5341.htm]]>
Raj S, Ramesh D, Sethi KK. A Spark-based Apriori algorithm with reduced shuffle overhead. The Journal of Supercomputing, 2021, 77(1): 133–151. [doi: 10.1007/s11227-020-03253-7]
Rathee S, Kashyap A. Adaptive-Miner: An efficient distributed association rule mining algorithm on Spark. Journal of Big Data, 2018, 5(1): 6. [doi: 10.1186/s40537-018-0112-0]
Sethi KK, Ramesh D. HFIM: A Spark-based hybrid frequent itemset mining algorithm for big data processing. The Journal of Supercomputing, 2017, 73(8): 3652–3668. [doi: 10.1007/s11227-017-1963-4]
Raj S, Ramesh D, Sreenu M, Sethi KK. EAFIM: Efficient apriori-based frequent itemset mining algorithm on Spark for big transactional data. Knowledge and Information Systems, 2020, 62(9): 3565–3583. [doi: 10.1007/s10115-020-01464-1]