矩阵压缩Apriori算法分析

Analysis of matrix compression Apriori algorithm

Apriori算法在处理较大的数据集时存在着不足:1)会产生数量庞大的候选项集,对算法运算时间和主存空间来说挑战巨大;2)多次扫描事务数据库会产生巨大的I/O负载。针对上述问题,提出了基于聚类和矩阵压缩的Apriori算法——KCCM算法。首先,通过K-means算法对大型数据集进行预处理,将其划分为若干个较小的数据集,并给出了合理性分析和证明;然后,将各个小数据集转化为布尔矩阵的形式,通过矩阵压缩的运算方式进行关联规则挖掘;最后,通过Matlab软件对算法进行了多组实验仿真,分别对Apriori算法和KCCM算法从运算时间、运行结果上进行了分析对比,实验结果表明,相比Apriori算法,KCCM算法的运行效率提高了近46.1%。

As the most important algorithm of association rule, Apriori algorithm is widely used in all walks of life. However,Apriori algorithm exists some problems when dealing with large data sets： 1） Apriori algorithm produces a large number of candidate items, which brings great challenge to operation time and storage space; 2） scanning the data set for many times produces a great I/O load. In view of these problems, an Apriori algorithm based on K-means algorithm and matrix compression was proposed, which named KCCM algorithm. Firstly, K-means algorithm was used to divide a large data set into several small data sets, and the rationality analysis and proof were given. Then, each small data set was converted to a Boolean matrix, and association rules were mined through matrix compression. At last, the operation step was simulated by Matlab software, and Apriori algorithm and KCCM algorithm were analyzed in operation time and running results. The experimental results show that, compared with Apriori algorithm,KCCM algorithm increased the run efficiency by nearly 46. 1%.