An Efficient Algorithm Based on Multi-subtrees for Mining Multi-dimensional Association Rules

摘要

Mining multi-dimensional association rules has been researched much later than mining single-dimensional association rules, it mainly tackles the analysis of attributes and frequent patterns mining problems.The corresponding mining algorithms are apriori-like mining methods, matrix and bit-mapped methods and intelligent optimization algorithms, etc.Apriorilike mining methods require so many database scans as to add the I/O burden and may generate large candidate sets.Intelligent optimization algorithms have good robustness, but they're random and easy to get into the partial optimal solution.In this study, a modified algorithm named Upper Triangular MatrixTree Union (UTMTU) is proposed to solve multidimensional association rules problem (MARP).This algorithm adopts the two important properties of association rules and makes good use of upper triangular matrix(UTM) and multi-subtrees algorithm. UTMTU only requires one database scan and gets rid of the usage of candidate item sets.Additionally, the paper introduces the notion of the effective layers of attributes which help to raise the utilization ratio of memory and I/O.UTMTU has broken the two bottlenecks of original algorithm.This paper compares UTMTU with IApriori, a previous improved multidimensional oriented algorithm and demonstrates a substantial performance gain of UTMTU over IApriori.Consequently, the UTMTU algorithm is more suitable for multi-layer or multi-attribute MARP.