单调和反单调约束条件下关联规则的挖掘算法分析  

Algorithm Analysis for Anti-monotone and Monotone Constraints Association Rules Mining

作　　者：杜剑峰[1] 李宏[1] 陈松乔[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机科学》2005年第6期142-144,166,共4页Computer Science

基　　金：国家杰出青年自然科学基金(69928201)

摘　　要：本文充分利用了 Eclat算法的概念格理论和等价类划分方法,将约束条件融入基于垂直数据分布的关联规则挖掘算法中。提出了一种新的反单调和单调约束条件下关联规则的挖掘算法,分别为EclatA算法和EclatM算法。算法采用自底向上的搜索方法,在发现频繁项集的同时进行约束条件的检验。数据库的扫描次数较少,无需对候选项集进行剪枝,占用内存较小。实验证明:该算法的执行效率比已有算法有显著提高。Anti-monotone and monotone constraints are integrated into the algorithm of association rules mining based on vertical data layout by utilizing the lattices theory and the decomposing method of equivalence classes suffi- ciently. Two new algorithms are also presented. One is based on anti-monotone constraint named EclatA. The other is based on monotone constraint named EclatM. A bottom-up search method is put forward and the constraints are checked at the process of calculating frequent itemsets.The new algorithms scan the database few times and have no need of pruning candidate itemsets. At the same time,they can be solved in memory. Results from our experiments show that the performance of the new algorithms is unmatched by any previous algorithms

关 键 词：约束条件 算法分析 单调 调和 关联规则挖掘算法 划分方法 充分利用 数据分布 搜索方法 自底向上 频繁项集 扫描次数 候选项集 实验证明 等价类 概念格 A算法 数据库 效率比 内存 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O221.1[自动化与计算机技术—计算机科学与技术]