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

An improved Apriori algorithm based on Boolean matrix reduction

作　　者：廖纪勇 吴晟[1] 刘爱莲[1] LIAO Ji-yong;WU Sheng;LIU Ai-lian(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

机构地区：[1]昆明理工大学信息工程与自动化学院

出　　处：《计算机工程与科学》2019年第12期2231-2238,共8页Computer Engineering & Science

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

关 键 词：APRIORI算法 频繁项集 关联规则 矩阵约简 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]