基于矩阵约简的Apriori算法改进

摘要

During the search for frequent itemsets of the Apriori algorithm, the database is scanned repetitively and generates a large number of useless candidate sets. For this problem, a kind of improved Apriori algorithm based on the matrix reduction is put forward. The algorithm scans the database only once, converts the database information to Boolean matrix, and reduces the data structure according to the conclusion drawn from the nature of the frequent k-itemsets, which lowers the generation scale of the invalid candidate itemsets effectively. By comparing with the existing algorithms, it is validated that this algorithm can im-prove the efficiency of mining frequent itemsets effectively.%Apriori算法在搜索频繁项集过程中，通常需要对数据库进行多次的重复扫描和产生大量无用的候选集，针对此问题提出一种基于矩阵约简的Apriori改进算法。该算法只需扫描一次数据库，将数据库信息转换成布尔矩阵，根据频繁k-项集的性质推出的结论来约简数据结构，有效地降低无效候选项集的生成规模。通过对已有算法的对比，验证该算法能有效地提高挖掘频繁项集的效率。