的步骤直到找到k+1项集
Apriori实现步骤
在得到全部频繁项集L后，算法根据这些频繁项集产生关联规则： ① 对于L中的每一个频繁项集l，产生l的所有非空子集； ② 对于l中的每个非空子集A，如果满足设定的评估标准 （如置信度大于等于最小置信度阀值）。
置信度
关联规则度量e
度量名称 规则置信度 置信度差 置信度比率
闭频繁项集： 频繁项集的支持度和所有包含
这个频繁项集的超项集的支持度计数 不同
极大频繁项集： 项集不存在超项集，并且该项集
是频繁的
项集关系
频繁项集 闭频繁项集
极大频 繁项集
频繁模式挖掘种类
根据完全性分类：频繁项集完全集、闭频繁项集、极大频繁项集、被约束的
频繁项集、近似的频繁项集、接近匹配的频繁项集、最频繁的k个项集…….
奶}=3/5
频繁项集 满足最小支持度阀值的项集，如这里把最
小支持度阀值设置为3，则频繁2项集有{面包, 牛奶}、 {尿布, 啤酒}
记录编号 1 2 3 4 5
购物清单 面包、牛奶 面包、尿布、啤酒、鸡蛋 牛奶、尿布、啤酒、可口可乐 面包、牛奶、尿布、啤酒 面包、牛奶、尿布、可口可乐
关联规则
关联规则： 根据一个项集里面的物品可以推测出另一
Apriori性质图示
null
A
B
C
D
E
非频繁项集
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
ABCD
ABCE
ABDE
ACDE
BCDE
ABCDE
Apriori实现步骤
① 根据频繁k-1项集组成的集合Lk-1 产生全部候选k项集Ck; ② 对Ck进行修剪； ③ 计算Ck中每一个项集w的支持度； ④ 将支持度大于最小支持度阀值的项集添加到频繁k项集Lk中； ⑤ 只能够找到频繁k项集，并且k小于用户预先定义的最大值kmax,重复上面
① 扫描数据库，计算出每个项的计数，收集满足最小支持 度的项，找出频繁1项集的集合，记为L1；
② 使用L1寻找2项频繁集的集合L2，L2又用来寻找L3，如 此下去直到不能再找到频繁k项集。
找每个Lk都需要一次全库扫描
Apriori性质
Apriori性质表现
如果项集I不满足最小支持度阀值min_sup，则 I不是频繁的，即P(I)<min_sup； 此时项A添加到项集I，组成一个新的项集(IUA) 也是不频繁的，即P(IUA)<min_sup
个包含不同物品的项集，如 {啤酒, 面包} {牛奶},
规则度量标准 --支持度(s)
规则中前后两个项集在整个事务集中同时 出现的概率 --置信度(c)
在前项集发生的情况下，由前项推出后项 的概率 --提升度(l)
在含有前项的条件下后项发生的概率，与 不包含前项这个条件下后项发生的概率对比
记录编号 1 2 3 4 5
数据挖掘课程培训
关联规则
广度优 先算法
• 自底向上地搜索整个空间，首先 生成候选集，然后提取其中的频 繁项集
• 算法代表有Apriori、AprioriTid 和AprioriHybrid
• AprioriHybrid的效率高于 Apriori和AprioriTid
深度优 先算法
• 利用模式增长的方式
根据抽象层分类：单层关联规则、多层关联规则(如：{电脑}{打印机}， {台
式机}{打印机})
根据数据维度分类：一维关联规则、多维关联规则 根据处理值类型分类：布尔关联规则、量化关联规则
Apriori算法
翻译： Apriori：先验的、推测的
方法： 步骤： 特征：
Apriori使用逐层搜索的迭代方法，k项集用于探索k+1项集
{尿布} {啤酒}, {面包, 牛奶} {鸡蛋,可口可乐}, {啤酒, 面包} {牛奶}
频繁项集
项集： 项的集合，可以包含1项或多项，如{面包,
牛奶}；项集中有K项就称为K项集，如上为2项 集
支持度计数（绝对支持度） 项集在事务集中出现的频率，如{面包, 牛
奶}=3
支持度（相对支持度） 项集在事务集中出现的概率，如{面包, 牛
• 算法代表有FP-growth、Eclat和 H-Mine
• FP-growth以分而治之的策略， 在经过第一次扫描过后，把数据 库中的频繁项集压缩进一颗频繁 模式树
关联规则
记录编号 1 2 3 4 5
购物清单 面包、牛奶 面包、尿布、啤酒、鸡蛋 牛奶、尿布、啤酒、可口可乐 面包、牛奶、尿布、啤酒 面包、牛奶、尿布、可口可乐
② 由频繁项集产生强关联规则
支持度 ≥ 最小支持度阀值 置信度 ≥ 最小置信度阀值 提升度 ≥ 最小提升度阀值
项集生成
null
A
B
C

E
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
ABCD
ABCE
ABDE
ACDE
BCDE
ABCDE
闭频繁项集和极大频繁项集
信息差 标准化卡方
描述
公式
直接使用置信度表示，默认评估度 量
前、后置信度差的绝对值
前、后置信度的比例
基于信息增益的度量方法
基于独立的离散型数据的卡方统计 检验
信息差公式
购物清单 面包、牛奶 面包、尿布、啤酒、鸡蛋 牛奶、尿布、啤酒、可口可乐 面包、牛奶、尿布、啤酒 面包、牛奶、尿布、可口可乐
设前项为X，后项为Y： S=P(XUY)/P(I) C=P(XUY)/P(X) L=P(XUY)/P(X)P(Y)
关联规则挖掘
① 找出所有的频繁项集
支持度(项集) ≥ 最小支持度阀值