关联

什么是频繁模式分析? 频繁模式: 在数据集中频繁出现的模式(项集, 子序列, 子结构等) 动机: 找出数据中的内在规律性 哪些产品经常被一起购买?— Beer and diapers?! 购买了PC之后下一个会买什么? 何种DNA对这个新药敏感? 能否自动分类web文档? 应用 购物篮分析, cross-marketing, 商品目录设计, 促销活动分析, Web日志(点击流)分析, DNA序列分析

基本概念: 频繁模式和关联规则 项集X = {x1, …, xk} 找出满足最小支持度和置信度的所有规则X  Y Transaction-id Items bought 10 A, B, D 20 A, C, D 30 A, D, E 40 B, E, F 50 B, C, D, E, F 项集X = {x1, …, xk} 找出满足最小支持度和置信度的所有规则X  Y 支持度 s, 一笔交易包含XY的概率 置信度 c, 一笔包含X的交易也包含Y的条件概率 买尿布的客户 两者都买的客户 买啤酒的客户 令 supmin = 50%, confmin = 50% 频繁模式: {A:3, B:3, D:4, E:3, AD:3} 关联规则: A  D (60%, 100%) D  A (60%, 75%)

频繁模式挖掘: 路线图(1) 基于挖掘的模式的完备性 频繁模式的完备集合 闭频繁项集 极大频繁项集 约束频繁项集 近似频繁项集 邻近匹配频繁项集 top-k 频繁项集 基于规则中涉及的抽象层次 单层关联规则 多层关联规则 基于规则中涉及的数据维数 单维关联规则 多维关联规则

频繁模式挖掘: 路线图(2) 基于规则处理的值的类型 布尔型关联规则 定量关联规则 基于挖掘的规则种类 关联规则 相关性规则 强梯度联系 基于挖掘的模式的种类 频繁项集挖掘 序列模式挖掘 结构模式挖掘

挖掘频繁模式的可扩展方法 频繁模式的向下封闭性质 频繁项集的任何子集必是频繁的 若{beer, diaper, nuts}是频繁的, 则{beer, diaper}也是 因为: 任何包含{beer, diaper, nuts}的交易也包含{beer, diaper} 可扩展挖掘方法: 三个主要方法 Apriori (Agrawal & Srikant@VLDB’94) 频繁模式增长(FPgrowth—Han, Pei & Yin @SIGMOD’00) 垂直数据格式方法(Charm—Zaki & Hsiao @SDM’02)

Apriori: 候选生成与检验方法 Apriori剪枝原则: 如果发现任何项集是非频繁的, 则其超集就不必生成/检验! 方法: 初始步, 扫描一次DB, 得到频繁1-项集 从长度为k的频繁项集生成长度为(k+1)的候选项集 在DB中检验候选项集 不能生成频繁或候选项集时终止

Apriori算法—一个例子 Supmin = 2 Database TDB L1 C1 1st scan C2 C2 L2 Itemset sup {A} 2 {B} 3 {C} {D} 1 {E} Database TDB Itemset sup {A} 2 {B} 3 {C} {E} L1 C1 Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E 1st scan C2 Itemset sup {A, B} 1 {A, C} 2 {A, E} {B, C} {B, E} 3 {C, E} C2 Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} L2 2nd scan Itemset sup {A, C} 2 {B, C} {B, E} 3 {C, E} C3 L3 Itemset {B, C, E} 3rd scan Itemset sup {B, C, E} 2

Apriori算法 伪代码: Ck : 大小为k 的候选项集 Lk :大小为k 的频繁项集 L1 = {频繁项(即频繁1-项集)}; for (k = 2; Lk-1 !=; k++) { Ck = 从Lk-1 生成的候选项集; for each 交易t do 将被t 包含的所有Ck 中候选项集的计数加1 Lk = Ck 中至少具有min_support的候选项集 } return k Lk

Apriori算法细节 如何生成候选项集Ck? Step 1: 自连接Lk-1 Step 2: 剪枝 如何计数候选项集的支持度?

如何生成候选项集Ck:Step-1 假设Lk-1 中的项有序排列 步骤-1:自连接 Lk-1 insert into Ck select p.item1 , p.item2 , …, p.itemk-1 , q.itemk-1 from Lk-1 as p, Lk-1 as q where p.item1=q.item1 and … and p.itemk-2=q.itemk-2 and p.itemk-1 < q.itemk-1

如何生成候选项集Ck:Step-2 步骤-2: 剪枝 for each c in Ck do for each (k-1)-subsets s of c do if (s is not in Lk-1) then delete c from Ck 12

例:候选项集生成 由:L3 = {abc, abd, acd, ace, bcd } Step-1:自连接L3*L3 abcd from abc 和abd acde from acd 和ace Step-2: 剪枝 由于ade 不在L3 中, acde 被删除 得:C4 = {abcd }

频繁模式挖掘中的挑战 挑战 多次扫描交易数据库 大量的候选项集,尤其是挖掘长模式(较大的k项集) 对候选项集支持度的计数带来冗长的工作负担 改进Apriori 减少扫描交易数据库的遍数 减少候选的个数 避免候选生成: FP-Growth 使候选支持度计数便利

挖掘各种关联规则 挖掘多层关联 挖掘多维关联 挖掘定量关联 挖掘有意义的相关模式

挖掘多层关联规则 项常常形成不同抽象层次 例如:牛奶;低脂牛奶,脱脂牛奶 较低层的项一般具有较低的支持度,因为数据稀疏 难以挖掘出有意义的关联规则 支持度设定 一致支持度 Milk [support = 10%] 2% Milk [support = 6%] Skim Milk [support = 4%] Level 1 min_sup = 5% Level 2 min_sup = 3% 递减支持度

多层关联: 冗余过滤 由于项间“祖先”联系的存在, 某些规则可能是冗余的. 例如 milk  wheat bread [support = 8%, confidence = 70%] 2% milk  wheat bread [support = 2%, confidence = 72%] 我们说第一条规则是第二条规则的祖先. 如果一条规则基于其祖先算出的支持度接近“期望”值, 则这条规则是冗余的.

挖掘多维关联 单维规则: 多维规则:  2 个维度或谓词 维间关联规则(没有重复的谓词) 混合维关联规则(有重复谓词) buys(X, “milk”)  buys(X, “bread”) 多维规则:  2 个维度或谓词 维间关联规则(没有重复的谓词) age(X,”19-25”)  occupation(X,“student”)  buys(X, “coke”) 混合维关联规则(有重复谓词) age(X,”19-25”)  buys(X, “popcorn”)  buys(X, “coke”) 类别值属性: 有限数目的可取值, 值间无序—数据立方体方法 定量属性: 数值型, 值间有隐含的序—离散化, 聚类, 梯度方法

挖掘定量关联 可以根据数值属性(如age或salary)是如何处理的来划分技术 基于预定义的概念层次(数据立方体方法)的静态离散化 基于数据分布的动态离散化(定量规则, e.g., Agrawal & Srikant@SIGMOD96) 聚类: 基于距离的关联(e.g., Yang & Miller@SIGMOD97) 一维聚类, 然后关联 偏差: (如Aumann and Lindell@KDD99) Sex = female => Wage: mean=$7/hr (overall mean = $9)

数量属性的静态离散化 利用概念层次在挖掘之前离散化 用范围替代数值 关系数据库中, 找出所有频繁k-谓词集需要k 或k+1次表扫描 数据立方体很适合挖掘 一个n-维方体的单元格对应于谓词集 从数据立方体挖掘可能快很多 (income) (age) () (buys) (age, income) (age,buys) (income,buys) (age,income,buys)

Data Mining: Concepts and Techniques 定量关联规则 由Lent, Swami and Widom ICDE’97提出 数值属性动态离散化 使得所挖掘的规则的可信度或紧凑度最大化 2-维定量关联规则: Aquan1  Aquan2  Acat 利用2-维网格聚类 “相邻”关联规则 以形成一般规则 例如: age(X,”34-35”)  income(X,”30-50K”)  buys(X,”high resolution TV”) Data Mining: Concepts and Techniques

规则是否有意义的度量: 相关性 度量独立性/相关性事件: lift 例1: (Aggarwal & Yu, PODS98) 在5000个学生中 3000 人早晨打篮球 3750 早餐吃麦片 2000 既打篮球又吃麦片 打篮球  吃麦片 [40%, 66.7%] 有点误导, 因为吃麦片学生的总比例为75%, 高于66.7%. 打篮球  不吃麦片 [20%, 33.3%] 更准确, 尽管具有较低支持度和可信度 度量独立性/相关性事件: lift Basketball Not basketball Sum (row) Cereal 2000 1750 3750 Not cereal 1000 250 1250 Sum(col.) 3000 5000

 (observed-expected)2/expected all_confidence 规则是否有意义的度量: 相关性 chi-square  (observed-expected)2/expected all_confidence all_conf(X) = sup(X)/max{sup(Xi)} cosine cosine(A,B) = P(AB)/sqrt(P(A)P(B)) 23