基于矩阵的Apriori算法改进  

Improved Apriori Algorithm Based on Matrix

作　　者：宋文慧[1] 高建瓴[1] 

机构地区：[1]贵州大学大数据与信息工程学院,贵州贵阳550025

出　　处：《计算机技术与发展》2016年第6期62-64,68,共4页Computer Technology and Development

基　　金：贵州省科学技术基金项目(黔科合J字[2015]2045)

摘　　要：文中介绍了经典Apriori算法的原理、思想和步骤,以及基于矩阵的Apriori算法。针对Apriori算法需要多次扫描数据库和产生大量候选项集的缺点,提出了一种基于矩阵的Apriori算法的改进方法。该方法的不同之处在于矩阵的构建方法,通过对事务数据库的一次整体扫描,把事务数据库中的数据转换成一个上三角矩阵,然后通过访问上三角矩阵中的元素就可直接得到频繁1项集和频繁2项集,再根据经典的Apriori算法,利用频繁2项集得到频繁3项集,依此进行下去。该算法因为有上三角矩阵的引入,故可以适当地减少访问事务数据库的次数,同时还减少了大量候选项集的产生,尤其是二次候选项集,节约了存储空间。实验结果表明,该改进算法是有效的,减少了使用扫描数据库的函数的次数,并且保证了频繁项集的准确性。It introduces the principles,ideas and steps of the classical Apriori algorithm, as well as the Apriori algorithm based on matrix in this paper. In view of the shortcomings for traditional Apriori algorithm of requiring multiple scanning database and producing a large number of candidate itemsets, an improved Apriori algorithm based on matrix is proposed. The difference of this method is the method to construct a matrix, through a whole scan of the transaction database, the transaction data in the database into a upper triangular matrix, and then by accessing the elements in the upper triangular matrix can obtain frequent itemsets 1 and frequent itemsets 2 directly. According to the classical Apriori algorithm,using the frequent itemsets 2 get frequent itemsets 3 ,proceeding accordingly. Because of the introduction of Ilpper triangular matrix,the improved algorithm can reduce the number of accessing database and the incidence of a large number of candidate itemsets,especially the candidate itemsets 2, saving storage space. The experiment shows that the improved algorithm is effective to reduce the number of functions used to scan the database and to ensure the accuracy of the frequent itemsets.

关 键 词：关联规则 APRIORI算法 矩阵 M-Apriori算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]