《数据挖掘原理与应用 第2版 》课件 5.6关联分析-生成规则

关联分析产生关联规则关联规则

2关联规则产生事务TIDITEMS1I1,I2,I32I2,I3,I43I1,I3,I5,...………关联规则{I1,I2}{I3}{Ii,Ij}{Ik}……c≥minConf“候选”关联规则{I1,I2}{I3}{I1,I3}{I2}

{I1,I5}

{I2}{Ii,Ij}{Ik}……频繁项集+支持度{I1}，7

{I2}，6{I3}，5{I1,I2}，5{I1,I3}，4{I1,I2,I3}，4……，…s≥minSup3方法：对于频繁k-项集Z，

将集合Z

划分为

X

和Y

两个不重叠子集，

由X

和Y

生成“候选”的关联规则。

若候选规则X

Y

的置信度满足阈值，

则X

Y

为关联规则。

Z

X

Y

这样的规则必然已经满足支持度阈值，因为它们是由频繁项集产生的那么产生关联规则，是对于所产生出的频繁k-项集Z，关联规则产生从频繁项集产生候选的关联规则例：频繁项集{ABCD}，候选规则有：{ABC}{D}，{ABD}{C}，{ACD}{B}，{BCD}{A}{AB}{CD}，{AC}{BD}，{AD}{BC}，{BC}{AD}，{BD}{AC}，{CD}{AB}{A}{BCD}，{B}{ACD}，{C}{ABD}，{D}{ABC}4前件3，后件1前件2，后件2前件1，后件3还可以产生ABCD、关联规则产生关联规则X

Y的强度的度量指标：支持度

s：确定规则可以用于给定数据集的频繁程度置信度c：确定

Y在包含

X的事务中出现的频繁程度计算关联规则的置信度并不需要再次扫描事务数据集5

生成“候选”规则6暴力破解法基于Apriori的方法暴力破解法(Brute-forceapproach）

计算代价过高7fk

h

fk-h

h

fk-hApriori原理8支持度度量的单调性按照Apriori原理置信度也遵循“先验”规则被剪枝的规则低置信度规则9

按照Apriori原理如果规则X

Y

不满足置信度阈值，则形如X-

Y+

的规则一定也不满足置信度阈值，其中

是X

的子集。例如：10

大家可以看到，前件中项的数量逐渐变少，后件中项的数量逐渐变多…算法针对每一个不同大小的频繁项集，依次处理。根据频繁项集

fk和后件Sm，计算规则(fk-Sm)→Sm的置信度，若满足阈值要求，则确认该规则并输出；基于后件Sm，产生增加了一个项的后件Sm+1的集合{Sm+1}，对其中的每各后件Sm+1，结合频繁项集fk，递归调用gen_rules()，处理所有的规则组合。11如果它满足阈值要求，则确认该规则并输出{1237}

{}{123}{7}{127}{3}{137}{2}{12}

{37}{13}

{27}{23}{17}{1}-{237}{7}-{123}{3}-{127}{17}{23}{27}-{13}{237}{1}{37}-{12}{2}-{137}12{I7I3I2I1}

{}{I7I3I2}{I1}{I7I3I1}{I2}{I7I2I1}{I3}{I7I3}{I2I1}{I7I2}{I3I1}{I3I2}{I7I1}{I7}-{I3I2I1}{I1}-{I7I3I2}{I2}-{I7I3I1}{I7I1}{I3I2}{I3I1}-{I7I2}{I3I2I1}{I7}{I2I1}-{I7I3}{I3}-{I7I2I1}13【例】购物篮分析支持度计数≥4转换为二元数据去除非频繁项组合产生候选2-项集，并计数按列求和，统计各数据项计数去除非频繁项14【例】购物篮分析支持度计数≥4组合产生候选3-项集（Fk-1

Fk-1）去除非频繁2-项集超集和非频繁项组合产生候选4-项集（Fk-1

Fk-1）去除非频繁2-项集超集和非频繁项15【例】购物篮分析支持度计数≥4置信度≥0.85生成规则提取关联规则16从频繁2-项集和频繁1-项集以及它们的支持度计数，【例】购物篮分析支持度计数≥4置信度≥0.85生成规则提取时，可先提取前件为2-项集，后件为1-项集的规则，如果置信度不满足要求，则不再提取前件为1-项集后件为2-项集的规则。17【例】购物篮分析支持度计数≥4置信度≥0.85生成规则提取时，可先提取前件为3-项集，后件为1-项集的规则，若置信度满足要求，才继续提取22形式的规则，否则向下剪枝；如果22形式的规则满足要求，才继续提取13形式的规则。18【例】购物篮分析支持度计数≥4置信度≥0.8519{I1,I2,I3,I7}{I1,I2,I3}→{I7}{I1,I2,I7}→{I3}{I1,I3,I7}→{I2}{I2,I3,I7}→{I1}{I3,I7}→{I1,I2}{I2,I7}→{I1,I3}{I1,I7}→{I2,I3}{I2,I3}→{I1,I7}{I1,I3}→{I2,I7}{I1,I2}→{I3,I7}{I7}→{I1,I2,I3}{I3}→{I1,I2,I7}{I2}→{I1,I2,I7}{I1}→{I2,I3,I7}

在格结构中，由这些关联规则向下衍生出来的规则，需要进行置信度阈值检验；【例】购物篮分析支持度计数≥4置信度≥0.85关联规则：

{I7}{I1}，1.0

{I7}{I2}，1.0{I1I2I3}

{I7}，1.0{I1I3I7}{I2}，1.0{I3I7}{I1I2}，1.0{I2I3I7}{I1}，1.0{I1I7}

{I2}，1.0{I7}

{I1I2}，1.0{I2I7}

{I1}，1.0{I3I7}

{I1}，1.0{I3I7}

{I2}，1.020【例】购物篮分析WEKA运行结果1.I7/5==>I1/5<conf:(1)>lift:(1.38)lev:(0.12)[1]conv:(1.36)2.I7/5==>I2/5<conf:(1)>lift:(1.22)lev:(0.08)[0]conv:(0.91)3.I2/I7/5==>I1/5<conf:(1)>lift:(1.38)lev:(0.12)[1]conv:(1.36)4.I1/I7/5==>I2/5<conf:(1)>lift:(1.22)lev:(0.08)[0]conv:(0.91)5.I7/5==>I1/I2/5<conf:(1)>lift:(1.83)lev:(0.21)[2]conv:(2.27)6.I3/I7/4==>I1/4<conf:(1)>lift:(1.38)lev:(0.1)[1]conv:(1.09)7.I3/I7/4==>I2/4<conf:(1)>lift:(1.22)lev:(0.07)[0]conv:(0.73)8.I2/I3/I7/4==>I1/4<conf:(1)>lift:(1.38)lev:(0.1)[1]conv:(1.09)9.I1/I3/I7/4==>I2/4<conf:(1)>lift:(1.22)lev:(0.07)[0]conv:(0.73)10.I1/I2/I3/4==>I7/4<conf:(1)>lift:(2.2)lev:(0.2)[2]conv:(2.18)11.I3/I7/4==>I1/I2/4<conf:(1)>lift:(1.83)lev:(0.17)[1]conv