基于布尔矩阵约简的Apriori算法改进研究

计算机工程与科学

基于布尔矩阵约简的Apriori算法改进研究

廖纪勇，吴晟，刘爱莲

（昆明理工大学信息工程与自动化学院,云南昆明 650500）

收稿日期:2019-01-25 修回日期:2019-04-08 出版日期:2019-12-25 发布日期:2019-12-25

An improved Apriori algorithm

based on Boolean matrix reduction

LIAO Ji-yong,WU Sheng,LIU Ai-lian

（School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China）

Received:2019-01-25 Revised:2019-04-08 Online:2019-12-25 Published:2019-12-25

摘要/Abstract

摘要：

针对关联规则中Apriori算法存在的缺点，提出了一种基于布尔矩阵约简的Apriori改进算法。在该算法中，将事务数据库转换为布尔矩阵，并在矩阵最后增加1行2列，用来记录相同事务的个数和矩阵行与列中“1”的个数。将矩阵各列元素按支持数升序排列，使得算法在压缩过程中减少了扫描矩阵各列的次数，缩短了算法的运行时间。另外，为了提高算法的存储空间利用率，增加了删除非频繁项集的操作。实验结果和性能分析表明，相比现有的算法，改进后的算法具有更好的性能，能够有效地提高算法执行效率。

关键词: Apriori算法, 频繁项集, 关联规则, 矩阵约简

Abstract:

Aiming at the shortcomings of Apriori algorithm in association rules, an improved Apriori algorithm based on Boolean matrix reduction is proposed.In this algorithm, the transaction database is converted into a Boolean matrix, and one row and two columns are added at the end of the matrix to record the number of the same transactions and the number of 1 in the matrix row and column.According to the number of supports, the elements of each matrix column are arranged in ascending order, so the number of scanning matrix columns is reduced in the process of compressing the matrix and the time efficiency of the algorithm is improved. In addition, in order to improve the spatial efficiency of the algorithm, the operation of deleting infrequent itemsets is added.Experimental results and performance analysis prove that the improved algorithm has better performance than the existing Apriori algorithm, and can effectively improve the computational efficiency of the algorithm.

Key words: Apriori algorithm, frequent itemset, association rule, matrix reduction

廖纪勇，吴晟，刘爱莲. 基于布尔矩阵约简的Apriori算法改进研究[J]. 计算机工程与科学.

LIAO Ji-yong,WU Sheng,LIU Ai-lian.

An improved Apriori algorithm

based on Boolean matrix reduction

[J]. Computer Engineering & Science.

[1]	熊中敏, 汪博, 陶然, 郑宗生, 陈明, . 一种基于主属性判定的关联规则挖掘约简算法[J]. 计算机工程与科学, 2021, 43(04): 738-745.
[2]	文凯, 耿小海, 朱璐伟, 许萌萌, . 基于AO算法的数据流频繁项集挖掘[J]. 计算机工程与科学, 2020, 42(12): 2259-2264.
[3]	杨岚雁, 靳敏, 张迎春, 张珣. 一种基于关联规则的MLKNN多标签分类算法[J]. 计算机工程与科学, 2020, 42(07): 1309-1317.
[4]	杨青1,2,3，张亚文1,2，张琴1，袁佩玲1. 基于Hadoop的多维关联规则挖掘算法研究及应用[J]. 计算机工程与科学, 2019, 41(12): 2127-2133.
[5]	肖文，胡娟. 稀疏数据频繁项集挖掘算法研究综述[J]. 计算机工程与科学, 2019, 41(05): 780-787.
[6]	秦铭，蔡明. 基于分类融合和关联规则挖掘的图像语义标注[J]. 计算机工程与科学, 2018, 40(05): 950-956.
[7]	贾俊杰，陈菲. 数字图书馆个性化匿名发布方法[J]. 计算机工程与科学, 2017, 39(11): 2109-2114.
[8]	张稳，罗可. 一种基于Spark框架的并行FP-Growth挖掘算法[J]. 计算机工程与科学, 2017, 39(08): 1403-1409.
[9]	薛红，张鹏，李伟男，郑作文. 全渠道消费者行为协同决策研究[J]. 计算机工程与科学, 2017, 39(08): 1570-1575.
[10]	邢长征，安维国，王星. 垂直数据格式挖掘频繁项集算法的改进[J]. 计算机工程与科学, 2017, 39(07): 1365-1370.
[11]	郭瑞，钱晓东. 基于一阶谓词公式去除商务数据冗余关联规则的研究[J]. 计算机工程与科学, 2017, 39(03): 593-598.
[12]	徐春，李广原，王玄，田换. 一种基于倒排索引树的增量更新关联挖掘算法[J]. J4, 2016, 38(05): 1039-1045.
[13]	丁建立，王曼. 一种面向航班准点率保障的航班协同调度评价模型[J]. J4, 2016, 38(04): 686-692.
[14]	王卫平,周忠眉,郑艺峰. 基于支持度和增比率的改进关联分类算法[J]. J4, 2016, 38(02): 370-375.
[15]	张晓，王红. 一种改进的基于大数据集的混合聚类算法[J]. J4, 2015, 37(09): 1621-1626.