基于频繁模式图的多维关联规则挖掘算法研究

关联规则挖掘是数据挖掘领域中重要的研究分支,频繁项集或频繁谓词集的计算是其中的关键问题.本文针对包括多值属性的关系数据库,以多维关联规则挖掘为目标,研究频繁谓词集的计算方法,提出了MPG算法及IMPG增量算法.MPG算法通过构建频繁模式图MP-graph,按照深度优先搜索方法,动态挖掘频繁谓词集,只需扫描数据库一次.此外,该方法至多增加一次数据库扫描,就能扩展为IMPG算法,进行增量关联规则挖掘.文章分析了算法时间和空间性能,用实验说明了算法的有效性.

Research of Algorithms Based on a Frequent Pattern Graph for Mining Multidimensional Association Rules

Association rule mining is an important research branch of data mining, and computing frequent itemsets or frequent predicate sets is the main problem. The paper aims at mining multidimensional association rules on a relational database which includes multi-value attributes,and studies a computing method for frequent predicate sets.It presents MPG algorithm and IMPG incremental algorithm.By constructing a frequent pattern graph and applying the depth-first-search method,MPG can find all frequent predicate sets and only scans database once.In addition,the method can be expanded into IMPG algorithm which is used for incremental association rules mining by increasing once database scan at most. The paper analyzes temporal and space performance of the algorithms,and proves their effectiveness by experiments.