基于二分法的改进Apriori关联算法研究

Research on improved Apriori association algorithm based on dichotomy

经典Apriori算法通过逐层迭代的方式产生备选项集,使得算法效率不高。针对该问题,提出一种基于二分法的改进关联规则算法:Dichotomy Apriori算法(D_Apriori算法)。D_Apriori算法利用逐步逼近的思想越级产生频繁K-项集,引入二分法获取每次需要产生频繁项集中集合的长度,结合排列算法或者取并集算法直接产生频繁K-项集。通过算例分析与实验验证结果表明,在数据量、支持度和事物长度分别不同的情况下,改进算法能有效减少频繁项集的迭代过程和运算时间,使算法的平均效率至少提高了12%。

The classical Apriori algorithm generates alternative sets by layer-by-layer iteration,which makes the algorithm inefficient.Aiming at this problem,an improved association rule algorithm based on dichotomy is proposed:Dichotomy Apriori algorithm(D_Apriori algorithm).The D_Apriori algorithm uses the idea of stepwise approximation to generate frequent K-itemsets,introduces the dichotomy method to obtain the length of the set of frequent itemsets each time,and combines the permutation algorithm or the union algorithm to directly generate frequent K-itemsets.The results of numerical examples and experimental verification show that the improved algorithm can effectively reduce the iterative process and operation time of frequent itemsets,and the average efficiency of the algorithm is increased by at least 12%under different data volumes,different support degrees and different lengths of things.