数据挖掘[6-5]Cluster-HierMeth-24

1、Association and Correlations,Association and Correlations Efficient and Scalable Frequent Itemset Mining Methods Mining Various Kinds of Association Rules From Association Mining to Correlation Analysis Constraint-based Association Mining,基于约束的关联挖掘,自动的找到数据库里的所有模式? 不现实 模式太多并且不集中! 数据挖掘应该是一个互动的过程 用一种挖掘

2、查询语言（或者图形用户界面），用户可以指示挖掘什么 基于约束的挖掘 用户灵活性: 为挖掘的内容提供约束 系统优化:为高效的挖掘 探寻约束基于约束的挖掘,数据挖掘中的约束,知识类型约束 分类，关联，等. 数据约束用像SQL的查询 找到12月2号芝加哥成双销售的产品 维度/层次约束 在相关地区，价格，品牌，客户分类 规则（或模式）约束 小的销售引发(price $200) 兴趣度约束 强规则: min_support 3%, min_confidence 60% 基于约束的挖掘使得挖掘有效和高效,关联规则的元规则制导挖掘,制定他们在挖掘中感兴趣的规则的语法形式. 元规则可以用来作为约束，以帮助提高

3、挖掘过程的效率. 元规则是基于分析师的实验，期望，或有关数据的直觉 元规则 P1(X, W) P2(X, V) buys(X, “educational software”) 匹配的规则: age(X, “30.39”) income(x, “42.48K”) buys (X, “educational software”) 判断变量和属性变量,关联规则的元规则制导挖掘,A 规则模板 (维际关联规则)： Pi, and Qi: instantiated predicates, predicate variables, plr: 元规则中predicate的数量， 找到所有频繁的p判断, Lp

4、得到LP的子集中I-pedicate的计数，以此来计算从LP派生出的规则的可信度 数据立方： : p-D 立方和l-D 立方,规则推进：规则约束制导的挖掘,混合维关联规则挖掘 连续启动和聚合函数 一个例子 找到2004年芝加哥客户的购物分类中，什么便宜的条目售卖可以提高什么贵的条目的售卖 销售(客户名字，条目名字，TID) 生活 (客户名字，地区，城市) 条目(条目名称，组，价格) 交易 (TID,天，月，年),规则推进：规则约束制导的挖掘,(1) mine associations as (2) lives in(C; ; “Chicago) sales+(C; ?I; S) ) sales

5、+(C; ?J; T) (metarule) (3) from sales (4) where S.year = 2004 and T.year = 2004 and I.group = J.group (5) group by C, I.group (dimension level constraints) (6) having sum(I.price) =500 (constraint pushing? Rule constraints) (7) with support threshold = 1% (interestingness constraints) (8) with confi

6、dence threshold = 50% lives in(C; ; “Chicago) sales(C; “Census_CD; ) sales(C; “MS=Office; )=sales(C; “MS=SQLServer; ); 1:5%; 68%,规则推进：规则约束制导的挖掘,我们怎么利用规则约束去修正搜索空间? 什么样的约束规则可以被“推入”挖掘过程，并且还能保证挖掘查询返回的回答是完整的? 规则约束的分类 Antimonotonic (反单调的) Monotonic (单调的) Succinct (简洁的) Convertible (可转变的) Inconvertible (不可

7、转变的),规则约束中的反单调性,反单调的 当一个项集s违反了约束，那么它的任何子集也是 sum(S.Price) v 是反单调的 sum(S.Price) v 不是反单调的 例. C: range(S.profit) 15 是反单调的 项集ab 违反了 C ab的每个子集也是,TDB (min_sup=2),规则约束中的单调性,单调的 当一个项集s满足了约束，那么它的任何子集也是 sum(S.Price) v is monotone min(S.Price) v is monotone 例. C: range(S.profit) 15 项集ab 满足了 C ab的每个子集也是,TDB (min

8、_sup=2),简洁性,简洁: 给定A1，满足简明约束C的项目集，那么任何满足C的集合S都基于A1，集S包含一个属于A1的子集 念：不看交易数据库，根据项目的选择，可以决定一个项集S是否满足约束C min(S.Price) v i是简洁的 sum(S.Price) v 不是简洁的 优化: 如果C是简洁，C是预先计算的,The Apriori Algorithm Example,Database D,Scan D,C1,L1,L2,C2,C2,Scan D,C3,L3,Scan D,Nave Algorithm: Apriori + Constraint,Database D,Scan D,C1

9、,L1,L2,C2,C2,Scan D,C3,L3,Scan D,Constraint: SumS.price 5,The Constrained Apriori Algorithm: Push an Anti-monotone Constraint Deep,Database D,Scan D,C1,L1,L2,C2,C2,Scan D,C3,L3,Scan D,Constraint: SumS.price 5,The Constrained Apriori Algorithm: Push a Succinct Constraint Deep,Database D,Scan D,C1,L1,

10、L2,C2,C2,Scan D,C3,L3,Scan D,Constraint: minS.price = 1,not immediately to be used,Converting “Tough” Constraints,通过恰当的命令条目，将硬约束转换成反单调的或单调的 例 C: avg(S.profit) 25 按价值降序排序的命令条目 如果一个项集违反 C 那么afbh, afb*也是 它变成反单调的,TDB (min_sup=2),可转变约束,avg(X) 25 is convertible anti-monotone w.r.t. item value descending o

11、rder R: If 如果一个项集af违反了一个约束C，那么以af为前缀的每个项集都是，例如afd avg(X) 25 is convertible monotone w.r.t. item value ascending order R-1: If an itemset d satisfies a constraint C, so does itemsets df and dfa, which having d as a prefixIf 如果一个项集d满足了一个约束C，那么以d为前缀的每个项集都是，例如df和dfa 因此, avg(X) 25 是可交换的,Apriori能处理可转变约束吗?,一个可交换的，不是单调的，不是反单调的，也不是简洁的约束，是不能被推入Apriori挖掘算法的深处的 在水平智慧框架内，基于约束的修正是做不到的 项集df违反了约束 C: avg(X)=25 既然adf 满足 C, Apriori需要df去 集合adf, df 不能被修正 但是它可以被推入频繁模式生长框架!,使用可转变约束进行挖掘,C: avg(X) = 25, min_sup=2 List items in every transaction in value descending order R: C 是可交换反单调的w.r.t. R 扫描 TDB一次 掉非频繁