文档介绍：关关联联规规则则挖挖掘掘黎都 2004-12-21 基本概念( 基本概念( 1 1) ) ?数据,数据集?项目,项目集?事务 t 包含项目集 X ?支持数,频繁项目集(频集) ? Support (X) = a(x) / |D| ?置信度基本概念( 基本概念( 2 2) ) ?关联规则: ?若项目集 X与Y交集为空,则 X=>Y 为关联规则,其中: ? Support(X=>Y) = Support(X 并Y) ? Confidence ( X=>Y ) ?= Suppose(X 并Y) / Suppose(X) 关联规则的目的关联规则的目的?对于指定的 minsupport 和 minconfidence ?使得 support(X) >= minsupport ? Confidence(X ) >= minconfidence ?则称关联规则 X=>Y 为强规则?关联规则挖掘的就是挖掘出事务集 D中的强规则关联规则挖掘关联规则挖掘?关联规则挖掘分为两个子问题: ?1,根据最小支持度找出数据集 D中的所有频集; ?2,根据频集和最小置信度产生关联规则; 关联规则的发现算法关联规则的发现算法?发现算法解决的是关联规则挖掘的第一个问题?关联规则分为布尔关联规则和多值规则?多值关联规则都转化为布尔关联规则来解决,因此先介绍布尔关联规则算法? Apriori , AprioriTid , AprioriHybrid Apriori Apriori 算法算法? Agrawal 等人在 1993 年提出的 AIS 和 SETM 的基础上在 1994 年提出 Apriori 和 AprioriTi ? Apriori 和 AprioriTid 算法利用前次过程中的数据项目集来生成新的候选数据项目集,减少了中间不必要的数据项目集的生成,提高了效率 Apriori Apriori 算法算法?L 1 = { 大项目集 1项目集} ? For(k=2; L k -1非空; k++) do begin ? C k = apriori - gen (L k -1 ); ? for 所有事务 t do begin ? C t = subset(C k , t) ? for 所有候选 c(属于 C t)do ? ++; Apriori Apriori 算法算法? End ?L k = { c 属于 C k | >= minsupp } ? End ? Apriori 算法得到的频集为 L k的并集 Apriori Apriori 算法分析算法分析?分为第一次遍历和第 k次遍历?第一次遍历计算每个项目的具体值,确定大项目集 1项目集 L 1 ?第k次遍历利用前一次找到的大项集 L k -1 和 Apriori - gen 函数产生候选集 C k,然后扫描数据库,得到 C k中候选的支持度, 剔除了不合格的候选后 C k作为 L k