关联规则反映事物与其他事物之间的关联性，是数据挖掘领域研究的一个重要方面，关键概念包括支持度，置信度，提升度。在关联规则中，Apriori算法是其重要组成部分。传统的Apriori算法存在如多次扫描数据库，需要很大的I/O负载，以及产生大量冗余性的候选项集等瓶颈问题。因此，对Apriori算法进行改进，通过布尔矩阵进行行列压缩来减少扫描数据的规模，通过引用索引表的形式来替代生成候选项集，并且以Tried树的形式来对最后所生成的所有频繁项集进行查找，从而加快了计算置信度的时间，以此来解决其瓶颈问题。最终实验结果表明，改进后的算法相比于传统的算法，大大提高了Apriori算法的时间及空间效率。
Association rules reflect the association between things and other things, which is an important aspect of data mining research. The key concepts include support, confidence and promotion. Apriori algorithm is an important part of association rules. The traditional Apriori algorithm has some bottleneck problems, such as scanning the database many times, requiring a lot of I/O load, and producing a large number of redundant candidate itemsets. Therefore, the Apriori algorithm is improved. The scale of scanning data is reduced by row and column compression of Boolean matrix. The candidate itemsets are generated by using index table instead. All frequent itemsets are searched in the form of tried tree, which speeds up the calculation time of confidence, so as to solve the bottleneck problem. The final experimental results show that the improved algorithm greatly improves the time and space efficiency of Apriori algorithm compared with the traditional algorithm.
References
[1]
Zhong, R. and Wang, H. (2011) Research of Commonly Used Association Rules Mining Algorithm in Data Mining. 2011 International Conference on Internet Computing and Information Services, Hong Kong, 17-18 September 2011, 219-222. https://doi.org/10.1109/ICICIS.2011.63
[2]
Li, G-Z., Wang, H.C. and Li, S.-G. (2013) An Improved Apriori Algorithm for Association Rules. Telkomnika Indonesian Journal of Electrical Engineering, 11, 942-946. https://doi.org/10.11591/telkomnika.v11i11.3491
[3]
Agrawal, R., Imieliński, T. and Swami, A.N. (1993) Mining Association Rules between Sets of Items in Large Databases. ACM SIGMOD Record, 22, 207-216. https://doi.org/10.1145/170035.170072
[4]
Oruganti, S., Ding, Q. and Tabrizi, N. (2013) Exploring HADOOP as a Platform for Distributed Association Rule Mining.
