第
3
章
关联规则模型与应用
【内容提要】关联规则模型算法作为快速知识发现的重要算法之一,最早流
行于大型数据库中快速发现知识的应用中,后来在多个领域得到应用和拓宽研
究。本章重点描述的内容是:①关联规则形成的相关理论,如候选项集、项集、强
项集、支持度、可信度、规则产生式;②关联分析算法的逻辑步骤;③关联规则的
应用。
【学习要求】了解Apriori(即快速发现知识)算法的核心内容,能够通过一个
实际小样本应用例子的手算过程,来掌握产生规则的全部模拟过程。同时,通过
对关联分析算法的应用,密切关注关联规则的创新应用。
..3.1
关联规则的解释、理论与相关术语
关联规则(AsociationRules)的含义是指在大型的数据库系统中,迅速找出
各事物之间潜在的、有价值的关联,用规则表示出来,经过推理、积累形成知识后,
得出重要的相关联的结论,从而为当前市场经济提供准确的决策手段。
关联规则的应用已经比较广泛,早在20世纪90年代率先应用于条形码中,使
大型零售商品的合理组织的复杂问题成为现实,也在决策领域到通信报警等系统
得到应用;到了21世纪初,关联分析普遍用于医疗中的病因分析和诊断;在交通运
输领域中用于安全运输的相关因素分析、道路交通安全的路段事故成因和风险分
析;2010年至今,专家们还将研究和应用的重点集中在大数据的分析的应用研究
中,如基于并行计算环境的词频统计、基于Hadoop环境下的并行关联分析算法的
应用、交通肇事逃逸案的关联分析、传染病或疑难病因的关联分析等相关分析及
应用研究,目前关联规则的应用研究已经渗透到多个研究领域。
1.关联规则的解释
3.1
关联规则的研究和应用是数据挖掘中最活跃和比较深入的分支,目前,已经
提出了许多关联规则挖掘的理论和算法。最为著名的是R.Agrawal等学者提出
的Apriori及其改进算法。
在Apriori算法中提到:为了发现有意义的关联规则,需要给定两个阈值:最
小支持度(MinimumSupport,min-sup)和最小可信度(MinimumConfidence,
min-conf)。min-sup和min-conf的解释是:①挖掘出的关联规则必须满足用户
第3章关联规则模型与应用125
规定的最小支持度,它表示了一组项目关联在一起需要满足的最低联系程度;②挖掘出的
关联规则也必须满足用户规定的最小可信度,它反映了一个关联规则的最低可靠度。因此,
求关联规则的最终目的在于:可以快速从大型数据库中挖掘出同时满足最小支持度和最小
可信度的关联规则即知识。另外,规则作为知识的最直接的、最简单的表达形式,这也是多
数科学研究者选用关联规则挖掘知识的原因。
3.1.2关联规则的理论及相关术语
关联规则的基础理论与方法概括如下。
(1)项目集格空间理论。
(2)模糊理论。
(3)快速查询。
(4)散列存储。
(5)层次树的数据结构。
(6)规则的表示与形成、知识的产生与描述方法。
1.项集或候选项集
项集是ItemSet的统称,一般简称为Items;候选项集是CandidateItemSet的统称,一
般简称为C。
项集Items={Item1,Item2,…,Itemm};TR 是事物的集合,TR.Items,并且TR 是
一个{0,1}属性的集合。
例如,表3.
1给出了一个事务数据库例子。
其中,表3.tem1,tiem5 分别代表事务1, 事务5。也就是
1中的iiem2,…,t事务2,……,
说,表3.行” 在数据结构中也叫作数据元素,它是数据的
1中的“ 代表数据库中的一条记录(
基本单位); 表3.列” 数据库即二维表中的列)或者叫作字段(在
1中的“ 代表数据库的属性(
数据结构中也叫作数据项,它是数据的最小单位,即不能再分割的数据)。
表3.事务数据库(例子
1
DB)
Tid
Item1
Item2
Item3
Item4
Item5
1 1 1 0 0 1
2 0 1 0 1 0
3 0 1 1 0 0
4 1 1 0 1 0
5 1 0 1 0 0
6 0 1 1 0 0
7 1 0 1 0 0
8 1 1 1 0 1
9 1 1 1 0 0
方便起见,约定将表3.项集1即item1) 将表3.
1中的事务1( 简称为I1, 1中的事务2
1 26 大数据模型与应用(微课版)
(项集2即item2)简称为I2,……,将表3.1中的事务5(项集5即item5)简称为I5。如果将
表3.1增加1列,其单元格内容存放每行包含的项集总数,例如,第一行中含有三个1,即第
1行的第1列即I1,第1行的第2列即I2,第1行的第5列即I5,因此,该行的项集总数是
{I1,I2,I5},共三个项集。其他行按照该计算方法得出结果如表3.2所示。
表3.2 事务数据库例子对应的项集总数的例子
Tid
事务1
I1
Item1
事务2
I2
Item2
事务3
I3
Item3
事务4
I4
Item4
事务5
I5
Item5
(每行包含的项集总数)
Items
1 1 1 0 0 1 {I1,I2,I5}
2 0 1 0 1 0 {I2,I4}
3 0 1 1 0 0 {I2,I3}
4 1 1 0 1 0 {I1,I2,I4}
5 1 0 1 0 0 {I1,I3}
6 0 1 1 0 0 {I2,I3}
7 1 0 1 0 0 {I1,I3}
8 1 1 1 0 1 {I1,I2,I3,I5}
9 1 1 1 0 0 {I1,I2,I3}
集合k_Item={Item1,Item2,…,Itemk}称为k 项集,或者k 项候选项集。
例如,表3.2的第5行及行编号Tid-5,对应的项集总数为Items={I1,I3},即k=2,属
于长度为2的项集,可以表示为2_Item={Itemi,Itemj },其中,k≥i,j≥1。
假设DB包含m 个属性(A ,B,…,M );1项集即长度为1的项集1_Item={{A },
{B},…,{M }},共有m 个候选项集;2项集即长度为2的项集2_Item={{A ,B },{A ,
C},…,{A ,M },{B,C},…,{B,M },{C,D },…,{L,M }},共有[m ′(m -1)/2]个项
集;以此类推,m 项集m_Item={A ,B,C,…,M },只有1个项集。
2.支持度
支持度sup指的是某条规则的前件或后件对应的支持数与记录总数的百分比。
假设A 的支持度是sup(A),sup(A)=|{TR|TR.A }/| n| |;A .B 的支持度sup(A .
B)=sup(A ∪B)=|{TR|TR.A ∪B}|/|n|,其中,n 是DB中的总的记录数目。
3.可信度
规则A .B 具有可信度conf(A .B )表示DB中包含A 的事物同时也包含B 的百分
比,是A ∪B 的支持度sup(A ∪B)与前件A 的支持度sup(A)的百分比。
conf(A .B)=sup(A ∪B)/sup(A)
4.强项集和非频繁项集
如果某k 项候选项集的支持度大于或等于所设定的最小支持度阈值,则称该k 项候选
项集为k 项强项集(Largek-itemset)或者k 项频繁项集(Frequentk-itemset)。
同时,对于支持度小于最小支持度的k 项候选项集称为k 项非频繁项集。
第3章 关联规则模型与应用1 27
定理(频繁项集的反单调性):设A ,B 是数据集DB中的项集,若A 包含B,则A 的支
持度大于B 的支持度;若A 包含于B,且A 是非频繁项集,则B 也是非频繁项集;若A 包
含于B,且B 是频繁项集,则A 也是频繁项集。
5.产生关联规则
若A ,B 为项集,A .Item,B.Item 并且A ∩B=.,一个关联规则是形如A .B 的蕴
含式。
(1)当前关联规则算法普遍基于Support-Confidence模型。
支持度是项集中包含A 和B 的记录数与所有记录数之比,描述了A 和B 这两个物品
集的并集C 在所有的事务中出现的概率,能够说明规则的有用性。
(2)规则A .B 在项集中的可信度,是指在出现了物品集A 的事务T 中,物品集B 也
同时出现的概率,能够说明规则的确定性。产生关联规则,即是从强项集中产生关联规则。
在最小可信度的条件门槛下,若强项集的可信度满足最小可信度,称此k 项强项集为
关联规则。
例如,若{A ,B}为2项强项集,同时conf(A .B)大于或等于最小可信度,即sup(A ∪
B)≥min_sup且conf(A .B)≥min_conf,则称A .B 为关联规则。
3.1.3 Apriori算法介绍
R.Agrawal等学者在1993年设计了一个Apriori算法,它是一种最有影响力的挖掘布
尔关联规则频繁项集的算法。其核心是基于两阶段的频集思想的递推算法。该关联规则在
分类上属于单维、单层、布尔关联规则。该算法将关联规则挖掘分解为两个子问题:①找出
存在于事务数据库中所有的频繁项目集,即那些支持度大于用户给定支持度阈值的项目集;
②在找出的频繁项目集的基础上产生强关联规则,即产生那些支持度和可信度分别大于或
等于用户给定的支持度和可信度阈值的关联规则。
在上述两步中,第二步相对容易些,因为它只需要在已经找出的频繁项目集的基础上列
出所有可能的关联规则,同时,满足支持度和可信度阈值要求的规则被认为是有趣的关联规
则。但由于所有的关联规则都是在频繁项目集的基础上产生的,已经满足了支持度阈值的
要求,只需要考虑可信度阈值的要求,只有那些大于用户给定的最小可信度的规则才被留下
来。第一个步骤是挖掘关联规则的关键步骤,挖掘关联规则的总体性能由第一个步骤决定,
因此,所有挖掘关联规则的算法都是着重于研究第一个步骤。
Apriori算法在寻找频繁项集时,利用了频繁项集的向下封闭性(反单调性),即频繁项
集的子集必须是频繁项集,采用逐层搜索的迭代方法,由候选项集生成频繁项集,最终由频
繁项集得到关联规则,这些操作主要是由连接和剪枝来完成。下面是Apriori算法的伪
代码。
Begin
//算法的初始化(为各个参与运算的参数赋初值等描述)
L1={Large1-itemsets} //扫描所有事务,计算每项出现次数,产生频繁项集长度为
//1的项集集合即1-项集集合L1
for (k=2;Lk-11.;k++) do //进行迭代循环,根据前一次的Lk-1得到频繁k-项集集合Lk
128
大数据模型与应用(微课版)
begin
Ck'=join(Lkm,Lkn) //join对每两个有k-1个共同项目的长度为k的模式Lkm和Lkn进行连接
Ck=prune(Ck') //pe根据频繁项集的反单调性,对Ck'进行剪枝,得到Ck
Ck=apriori-gen(Lk-1) //产生(r) k(n) 项候选项集Ck(u)
foraltransactionst∈Ddo
//扫描数据库一
遍
begin
Ct=ust(t) //确定每个事务t所含k-候选项集的sust(t)
sbeCk,beCk,
foralcandidatesc∈Ctdo
c.on//对候选项集的计数存放在hs
cut++ ah表中
nd
Lk={c(e) ∈Ct.ounmnsup}//删除候选项集中小于最小支持度的,
|cct≥i_得到k频繁项集Lk
end
foralsbsets.Lk
//对于每个频繁项集Lk,产生Lk 的所有非空子集s f((u) ps)f//可信度大于最小可信度的强项集为关联规则
Ifcons.Lk->=mi
ThenOutut(s.Lk-(_) (n) s)(c) //由频繁项集产生关联规则(n) (o)
end
end //得到所有的关联规则
Apriori算法最大的问题是产生大量的候选项集,可能需要频繁重复扫描大型数据库,
非常浪费扫描数据库的时间和大量候选项的存储空间,因此为候选项集合理分配内存,实现
对大型数据库系统快速扫描的技术和方法是提高管理规则效率的重要途径。面向大型数据
库,从海量数据中高效提取关联规则是非常重要的。
..3.关联规则举例
2
例3.i关联规则方法的实例。
1
Aprior
通过关联规则分析受过高等教育与性别、工资收入、职业、年龄等之间的潜在关联。给
出一个简单的数据库的例子,如表3.
3所示。
表3.一个简单的数据库的例子
3
记录号性别年龄学历职业收入
00 男46 博士高校教师7500
00 女32 硕士高校教师6500
00 男35 学士技术员4900
00 男40 硕士高校教师6000
00 男37 博士高校教师7000
00 男25 学士技术员4000
1.将实际的DBS问题转换成对应的逻辑值
对性别二元化(1:男,2:女);对年龄离散化(若年龄≥40,3:40岁以上;若年龄<40,
第3章关联规则模型与应用129
4:40 岁以下); 对是否受过研究生教育学历离散化(若学历为博士或者硕士,5:高学历;若
学历为本科和本科以下,6:低学历); 对职业进行二元化处理(7:高校教师,8:技术员); 对
收入进行二元化处理(若每月平均收入大于5000 元,9:收入5000 元以上;若每月平均收入
小于5000 元,10:收入5000 元以下)。通过以上的数据规约,4给出了与表3.
表3.3相对应
的逻辑表格。
表3.数据库对应的逻辑库
4
记录号
性别年龄学历职业收入
1 2 3 4 5 6 7 8 9
10
100 1 0 1 0 1 0 1 0 1 0
200 0 1 0 1 1 0 1 0 1 0
300 1 0 0 1 0 1 0 1 0 1
400 1 0 1 0 1 0 1 0 1 0
500 1 0 0 1 1 0 1 0 1 0
600 1 0 0 1 0 1 0 1 0 1
用关联规则算法找出表3.4中各属性之间有价值的、潜在的关联的信息即规则,希望最
终可以获得高等教育与工资、性别与职业、职务与工资等属性之间的关联。经过检索逻辑库
(参见表3.4)得到每条记录中各个It如表3.
em 的取值,5所示。
表3.数据库中记录的属性项取值集合
5
记录号项集
100 1,3,5,7,9
200 2,4,5,7,9
300 1,4,6,8,10
400 1,3,5,7,9
500 1,4,5,7,9
600 1,4,6,8,10
2.
设最小支持度m_p5,最小置信度m_7,求得关联规则
insu=0.if=0.
通过数据库查询(参见表3.得到k项候选集和k(n) 项(c) 强项集((n) (o) 及关联规则。5)
如表3.
Lk
)
(1)求1项集和1项强项集,6所示。
表3.
61
项集和1项强项集
Item
Sum
sup(I) L1
{1} 5 5/6 √
{2} 1 1/6
{3} 2 2/6
130
大数据模型与应用(微课版)
续表
Item
Sum
sup(I) L1
{4} 4 4/6 √
{5} 4 4/6 √
{6} 2 2/6
{7} 4 4/6 √
{8} 2 2/6
{9} 4 4/6 √
{10} 2 2/6
所以,1项强项集L1={{1},{4},{5},{7},{9}}。
7
所示。
(2)通过1项强项集得到2项候选集,再计算2项集的支持度得到2项强项集,如表3.
表3.
72
项集和2项强项集
Items
Sum
sup(Im
∪In
) L2
{1,4} 3 3/6 √
{1,5} 3 3/6 √
{1,7} 3 3/6 √
{1,9} 3 3/6 √
{4,5} 2 2/6
{4,7} 2 2/6
{4,9} 2 2/6
{5,7} 4 4/6 √
{5,9} 4 4/6 √
{7,9} 4 4/6 √
所以,2项强项集L2={{1,4},{1,5},{1,7},{1,9},{5,7},{5,9},{7,9}}。
(3)通过1项(即长度为k=1)强项集的支持度sup(A), 来计算2项(即长度为k=2)
强项集的可信度cf()=p()/p(), 得到2项(即规则长度为k=2)
onIm
.In
suIm
∪In
suIm
关联规则,如表3.
8所示。
表3.
82
项强项集的可信度和2项关联规则
Items
Im
(前件) In
(后件) sup(Im
∪In
) sup(Im
) conf(Im
.In
) 2项关联规则
{1,4} 1 4 3/6 5/6 3/5
4 1 3/6 4/6 3/4 √
第3章关联规则模型与应用131
续表
Items
Im
(前件) In
(后件) sup(Im
∪In
) sup(Im
) conf(Im
.In
) 2项关联规则
{1,5} 1 5 3/6 5/6 3/5
5 1 3/6 4/6 3/4 √
{1,7} 1 7 3/6 5/6 3/5
7 1 3/6 4/6 3/4 √
{1,9} 1 9 3/6 5/6 3/5
9 1 3/6 4/6 3/4 √
{5,7} 5 7 4/6 4/6 1 √
7 5 4/6 4/6 1 √
{5,9} 5 9 4/6 4/6 1 √
9 5 4/6 4/6 1 √
{7,9} 7 9 4/6 4/6 1 √
9 7 4/6 4/6 1 √
产生的2项关联规则为I(1),1),1),1)
,
I(7).I(I(5).I(I(9).I(I(7).I(I(9).I(
4).I(I(5).I(I(7).I(I(9).I(I(5).
I
(7),5),9),5),9),7)。
9
所示。
(4)通过2项强项集得到3项候选集,再计算3项集的支持度得到3项强项集,如表3.
表3.
93
项集和3项强项集
Items
Sum
sup(Im
∪In
∪Ip
) L3
{1,4,5} 1 1/6
{1,4,7} 1 1/6
{1,4,9} 1 1/6
{1,5,7} 3 3/6 √
{1,5,9} 3 3/6 √
{1,7,9} 3 3/6 √
{5,7,9} 4 4/6 √
所以,3项强项集L3={{1,5,7},{1,5,9},{1,7,9},{5,7,9}}。
(5)计算3项强项集的可信度,得到3项关联规则, 10 所示。
如表3.
表3.
10 3
项强项集的可信度和3项关联规则
Items
Im
(前件) In
(后件) sup(Im
) conf(Im
.In
) 3项关联规则
{1,5,7}
sup(Im
∪In
)=3/6
1 5,7 5/6 3/5
5 1,7 4/6 3/4 √
132
大数据模型与应用(微课版)
续表
Items
Im
(前件) In
(后件) sup(Im
) conf(Im
.In
) 3项关联规则
7 1,5 4/6 3/4 √
{1,5,7}
sup(Im
∪In
)=3/6
1,5 7 3/6 1 √
1,7 5 3/6 1 √
5,7 1 4/6 3/4 √
1 5,9 5/6 3/5
5 1,9 4/6 3/4 √
{1,5,9}
sup(Im
∪In
)=3/6
9 1,5 4/6 3/4 √
1,5 9 3/6 1 √
1,9 5 3/6 1 √
5,9 1 4/6 3/4 √
1 7,9 5/6 3/5
7 1,9 4/6 3/4 √
{1,7,9}
sup(Im
∪In
)=3/6
9 1,7 4/6 3/4 √
1,7 9 3/6 1 √
1,9 7 3/6 1 √
7,9 1 4/6 3/4 √
5 7,9 4/6 1 √
7 5,9 4/6 1 √
{5,7,9}
sup(Im
∪In
)=4/6
9 5,7 4/6 1 √
5,7 9 4/6 1 √
5,9 7 4/6 1 √
7,9 5 4/6 1 √
产生的3项关联规则(即长度为3的关联规则) 5).I(7),7).I(5),1,
为I(1,I(1,I(
7),5),1),9),5),9),
5).I(I(1,7).I(I(5,7).I(I(5).I(1,I(9).I(1,I(1,5).I(
5),1),9),7),9),
I(1,9).I(I(5,9).I(I(7).I(1,I(9).I(1,I(1,7).I(I(1,9).
I(7),7,.I(1),5).I(9),7).I(9),9).I(7),5,.I(9),5,.
I(9)I(7,I(5,I(5,I(7)I(9)
I(I(9).I(
7),7,5)。
(6)通过3项强项集L3={{1,5,7},{1,5,9},{1,7,9},{5,7,9}}, 来计算长度为4的
关联规则即4项集,4项集只有一个{5,9}, 11 所示。
1,7,如表3.
表3.
11 4
项集和4项强项集
Items
Sum
sup(Im
∪In
∪Ip
) L4
{1,5,7,9} 3 3/6 √
第3章关联规则模型与应用133
(7)计算4项强项集的可信度, 如表3.
得到4项关联规则, 12 所示。
表3.计算4项强项集的可信度和4项关联规则
12
Items
Im
(前件) In
(后件) sup(Im
) conf(Im
.In
) 4项关联规则
1 5,7,9 5/6 3/5
5 1,7,9 4/6 3/4 √
7 1,5,9 4/6 3/4 √
9 1,5,7 4/6 3/4 √
1,5 7,9 3/6 1 √
1,7 5,9 3/6 1 √
{1,5,7,9}
sup(Im
∪In
)=3/6
1,9 5,7 3/6 1 √
5,7 1,9 4/6 3/4 √
5,9 1,7 4/6 3/4 √
7,9 1,5 4/6 3/4 √
1,5,7 9 4/6 3/4 √
1,5,9 7 3/6 1 √
1,7,9 5 3/6 1 √
5,7,9 1 4/6 3/4 √
产生的4项关联规则为I(5)1,9),7)1,9),9)1,7),1,.
.I(7,I(.I(5,I(.I(5,I(5)
I(7,I(1,7).I(5,I(1,9).I(5,I(5,7).I(1,I(5,9).I(1,I(7,9).
9),9),7),9),7),
I(1,I(5,.I(9),1,9).I(I(7,.I(5),5,9).I(1)。
5),1,7)I(5,7),1,9)I(7,
(8)对获得的关联规则进行解释和可视化处理。
也就是将已经规约离散化的数据返回到原始的含义,进行有含义的解释,使得使用关联
规则的用户知道以上计算过程所得到的结论代表的实际含义。下面对得到的部分关联规则
的含义加以说明。
(1)I(7).I(9)表示:在最小支持度为0.7的水平下,
5和最小可信度为0.一名高校教
师.月收入大于5000 元。
(2)I(.I(7) 5和最小可信度为0.有博士和
5)1,表示:在最小支持度为0.7的水平下,
硕士学位的.性别为男士并且可以成为一名高校教师。
(3)I(.I(表示:在最小支持度为0.7的水平下,
1,5,7)9) 5和最小可信度为0.性别
为男士并且有博士和硕士学位的并且是一名高校教师.月收入大于5000 元。
从上述结果得出,高等教育与性别、高等教育与工资、大学教师与性别、职业与工资、高
工资与教育、高等教育与年龄等的潜在关联。
若将上例的最小支持度改为0.候选项集、我
们通过以下计算加以说明。
3, 强项集以及关联规则会否发生变化呢?
3.
设最小支持度mip3,
13 所示。
i_of0.求得关联规则集=,(u)
_0.最小置信度mncn=7,
(1)求1项集和1项强(n) 项(s) 如表3.
134
大数据模型与应用(微课版)
表3.
13 1
项集和1项强项集
Item
Sum
sup(I) L1
{1} 5 5/6 √
{2} 1 1/6
{3} 2 2/6 √
{4} 4 4/6 √
{5} 4 4/6 √
{6} 2 2/6 √
{7} 4 4/6 √
{8} 2 2/6 √
{9} 4 4/6 √
{10} 2 2/6 √
所以,1项强项集L1={{1},{3},{4},{5},{6},{7},{8},{9},{10 }}。
14
所示。
(2)通过1项强项集得到2项候选集,再计算2项集的支持度得到2项强项集,如表3.
表3.
14 2
项集和2项强项集
Items
Sum
sup(Im
∪In
) L2
Items
Sum
sup(Im
∪In
) L2
{1,3} 2 2/6 √ {3,10} 0 0/6
{1,4} 3 3/6 √ {4,5} 2 2/6 √
{1,5} 3 3/6 √ {4,6} 2 2/6 √
{1,6} 2 2/6 √ {4,7} 2 2/6 √
{1,7} 3 3/6 √ {4,8} 2 2/6 √
{1,8} 2 2/6 √ {4,9} 2 2/6 √
{1,9} 3 3/6 √ {4,10} 2 2/6 √
{1,10} 2 2/6 √ {5,6} 0 0/6
{3,4} 0 0/6 {5,7} 4 4/6 √
{3,5} 2 2/6 √ {5,8} 0 0/6
{3,6} 0 0/6 {5,9} 4 4/6 √
{3,7} 2 2/6 √ {5,10} 0 0/6
{3,8} 0 0/6 {6,7} 0 0/6
{3,9} 2 2/6 √ {6,8} 2 2/6 √
{6,9} 0 0/6 {7,10} 0 0/6
{6,10} 2 2/6 √ {8,9} 0 0/6
第3章关联规则模型与应用135
续表
Items
Sum
sup(Im
∪In
) L2
Items
Sum
sup(Im
∪In
) L2
{7,8} 0 0/6 {8,10} 2 2/6 √
{7,9} 4 4/6 √ {9,10} 0 0/6
所以,2项强项集L2={{1,3},{1,4},{1,5},{1,6},{1,7},{1,8},{1,9},{1,10},{3,
5},{3,7},{3,9},{4,5},{4,6},{4,7},{4,8},{4,9},{4,10},{5,7},{5,9},{6,8},{6,10},
{7,9},{8,10 }}。
得到2项关联规则, 15 所示。
(3)计算2项强项集的可信度, 如表3.
表3.
15 2
项强项集的可信度和2项关联规则
Items
sup(Im
∪In
) sup(Im
) sup(In
) conf(Im
.In
) 2项关联规则
{1,3} 2/6 5/6 2/6 2/5
{1,4} 3/6 5/6 4/6 3/5
{1,5} 3/6 5/6 4/6 3/5
{1,6} 2/6 5/6 2/6 2/5
{1,7} 3/6 5/6 4/6 3/5
{1,8} 2/6 5/6 2/6 2/5
{1,9} 3/6 5/6 4/6 3/5
{1,10} 2/6 5/6 2/6 2/5
{3,5} 2/6 2/6 4/6 1 √
{3,7} 2/6 2/6 4/6 1 √
{3,9} 2/6 2/6 4/6 1 √
{4,5} 2/6 4/6 4/6 1/2
{4,6} 2/6 4/6 2/6 1/2
{4,7} 2/6 4/6 4/6 1/2
{4,8} 2/6 4/6 2/6 1/2
{4,9} 2/6 4/6 4/6 1/2
{4,10} 2/6 4/6 2/6 1/2
{5,7} 4/6 4/6 4/6 1 √
{5,9} 4/6 4/6 4/6 1 √
{6,8} 2/6 2/6 2/6 1 √
{6,10} 2/6 2/6 2/6 1 √
{7,9} 4/6 4/6 4/6 1 √
{8,10} 2/6 2/6 2/6 1 √
1 36 大数据模型与应用(微课版)
产生的关联规则为I(3).I(5),I(3).I(7),I(3).I(9),I(5).I(7),I(5).I(9),
I(6).I(8),I(6).I(10),I(7).I(9),I(8).I(10)。
同理,按照上述算法,可以求出3项、4项候选集、强项集和关联规则等,在此不再做详
细计算。通过这两个例子可以发现,设定不同的最小支持度,相应求出的强项集也会发生变
化,产生的关联规则也将有差异。
4.使用Python语言实现关联规则算法
当最小支持度min_sup=0.5,最小置信度min_conf=0.7时,实现本实例的Python示
例代码如下。
Python示例代码:
(1) #加载数据
(2) def loadDataSet():
(3) return [["男", "40 岁以上", "高学历","高校教师", "收入5000 以上"],
(4) ["女", "40 岁以下", "高学历", "高校教师", "收入5000 以上"],
(5) ["男", "40 岁以下", "低学历", "非高校教师", "收入5000 以下"],
(6) ["男", "40 岁以上", "高学历", "高校教师", "收入5000 以上"],
(7) ["男", "40 岁以下", "高学历", "高校教师", "收入5000 以上"],
(8) ["男", "40 岁以下", "低学历", "非高校教师", "收入5000 以下"]]
(9) #生成候选集
(10) def createC1(dataSet):
(11) C1=[]
(12) for transaction in dataSet:
(13) for item in transaction:
(14) if not [item] in C1:
(15) C1.append([item])
(16) C1.sort()
(17) return list(map(frozenset,C1))
(18) #扫描数据,返回频繁项集和支持度
(19) def scanD(D,CK,minSupport):
(20) ssCnt = {}
(21) for tid in D:
(22) for can in CK:
(23) if can.issubset(tid):
(24) if not can in ssCnt:ssCnt[can]=1
(25) else:ssCnt[can]+=1
(26) numItems = float(len(D))
(27) retList = []
(28) supportData={}
(29) for key in ssCnt:
(30) support = ssCnt[key]/numItems
(31) if support>=minSupport:
(32) retList.insert(0,key)
(33) supportData[key]=support
(34) return retList,supportData
(35) #频繁项集两两组合
第3章 关联规则模型与应用1 37
(36) def aprioriGen(Lk,k):
(37) retList=[]
(38) lenLk = len(Lk)
(39) for i in range(lenLk):
(40) for j in range(i+1,lenLk):
(41) L1=list(Lk[i])[:k-2];L2=list(Lk[j])[:k-2]
(42) L1.sort();L2.sort()
(43) if L1==L2:
(44) retList.append(Lk[i]|Lk[j])
(45) return retList
(46) #生成频繁项集主函数,返回频繁项集和支持度
(47) def apriori(dataSet,minSupport):
(48) C1=createC1(dataSet)
(49) D=list(map(set,dataSet))
(50) L1,supportData =scanD(D,C1,minSupport)
(51) L=[L1]
(52) k=2
(53) while(len(L[k-2])>0):
(54) CK = aprioriGen(L[k-2],k)
(55) Lk,supK = scanD(D,CK,minSupport)
(56) supportData.update(supK)
(57) L.append(Lk)
(58) k+=1
(59) return L,supportData
(60) #规则计算的主函数
(61) def generateRules(L,supportData,minConf):
(62) bigRuleList = [] #关联规则
(63) for i in range(1,len(L)):
(64) for freqSet in L[i]:
(65) H1 = [frozenset([item]) for item in freqSet]
(66) if(i>1):
(67) rulesFromConseq(freqSet,H1,supportData,bigRuleList,minConf)
#如果有频繁2 项集以上,计算规则
(68) else:
(69) calcConf(freqSet,H1,supportData,bigRuleList,minConf)
#如果只有频繁1 项集,直接计算最小置信度
(70) return bigRuleList
(71) #大于最小支持度的规则进行输出
(72) def calcConf(freqSet,H,supportData,brl,minConf):
(73) prunedH=[]
(74) for conseq in H:
(75) conf = supportData[freqSet]/supportData[freqSet-conseq]
(76) if conf>=minConf:
(77) print (freqSet-conseq,'--->',conseq,'置信度:',conf)
(78) brl.append((freqSet-conseq,conseq,conf))
(79) prunedH.append(conseq)
1 38 大数据模型与应用(微课版)
(80) return prunedH
(81) #生成规则
(82) def rulesFromConseq(freqSet,H,supportData,brl,minConf):
(83) m = len(H[0])
(84) if (len(freqSet)>(m+1)):
(85) Hmp1 = aprioriGen(H,m+1)
(86) Hmp1 = calcConf(freqSet,Hmp1,supportData,brl,minConf)
(87) if(len(Hmp1)>1):
(88) rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)
(89) #主函数
(90) if __name__=='__main__':
(91) dataSet=loadDataSet()
(92) L,supportData=apriori(dataSet,minSupport=0.5)
(93) rules = generateRules(L,supportData,minConf=0.7)
运行结果如下:
frozenset({'40 岁以下'}) ---> frozenset({'男'}) 置信度: 0.75
frozenset({'收入5000 以上'}) ---> frozenset({'男'}) 置信度: 0.75
frozenset({'收入5000 以上'}) ---> frozenset({'高学历'}) 置信度: 1.0
frozenset({'高学历'}) ---> frozenset({'收入5000 以上'}) 置信度: 1.0
frozenset({'高学历'}) ---> frozenset({'男'}) 置信度: 0.75
frozenset({'收入5000 以上'}) ---> frozenset({'高校教师'}) 置信度: 1.0
frozenset({'高校教师'}) ---> frozenset({'收入5000 以上'}) 置信度: 1.0
frozenset({'高校教师'}) ---> frozenset({'男'}) 置信度: 0.75
frozenset({'高学历'}) ---> frozenset({'高校教师'}) 置信度: 1.0
frozenset({'高校教师'}) ---> frozenset({'高学历'}) 置信度: 1.0
frozenset({'高学历'}) ---> frozenset({'高校教师', '男'}) 置信度: 0.75
frozenset({'高校教师'}) ---> frozenset({'高学历', '男'}) 置信度: 0.75
frozenset({'收入5000 以上'}) ---> frozenset({'高校教师', '高学历'}) 置信度: 1.0
frozenset({'高学历'}) ---> frozenset({'高校教师', '收入5000 以上'}) 置信度: 1.0
frozenset({'高校教师'}) ---> frozenset({'高学历', '收入5000 以上'}) 置信度: 1.0
frozenset({'收入5000 以上'}) ---> frozenset({'高校教师', '男'}) 置信度: 0.75
frozenset({'高校教师'}) ---> frozenset({'收入5000 以上', '男'}) 置信度: 0.75
frozenset({'收入5000 以上'}) ---> frozenset({'高学历', '男'}) 置信度: 0.75
frozenset({'高学历'}) ---> frozenset({'收入5000 以上', '男'}) 置信度: 0.75
frozenset({'高学历', '收入5000 以上'}) ---> frozenset({'高校教师', '男'}) 置信度:
0.75
frozenset({'高学历', '男'}) ---> frozenset({'高校教师', '收入5000 以上'}) 置信度:
1.0
frozenset({'收入5000 以上', '男'}) ---> frozenset({'高校教师', '高学历'}) 置信度:
1.0
frozenset({'高校教师', '高学历'}) ---> frozenset({'收入5000 以上', '男'}) 置信度:
0.75
frozenset({'高校教师', '收入5000 以上'}) ---> frozenset({'高学历', '男'}) 置信度:
0.75
frozenset({'高校教师', '男'}) ---> frozenset({'高学历', '收入5000 以上'}) 置信度:
1.0
frozenset({'高学历'}) ---> frozenset({'高校教师', '收入5000 以上', '男'}) 置信度:
0.75
frozenset({'收入5000 以上'}) ---> frozenset({'高校教师', '高学历', '男'}) 置信度:
0.75
第3章 关联规则模型与应用1 39
frozenset({'高校教师'}) ---> frozenset({'收入5000 以上', '高学历', '男'}) 置信度:
0.75
代码运行结果如上,其中,frozenset为Python语言中的“冻结集合”数据类型,冻结集
合中的元素代表相应项集。例如,“frozenset({'40岁以下'})--->frozenset({'男'})置
信度:0.75”代表年龄<40,在置信度为75%的情况下可以推出其性别为男性;“frozenset
({'高校教师','高学历'})--->frozenset({'收入5000以上','男'})置信度:0.5”代表学
历为博士或者硕士,同时为高校教师,在置信度为75%的情况下可以推出在其性别为男性,
同时工资在5000元以上。
例3.2 Apriori算法举例。
表3.16给出了每个客户(记录ID编号)交易各类商品的记录情况。
表3.16 每个客户交易各类商品的记录情况
交易ID 商品A 商品B 商品C 商品D 商品E 商品F
1000 A C
2000 A B C
4000 A D
5000 B E F
假设表3.16交易商品对应的项集、满足最小支持度与最小可信度为50%的频繁项集分
别如表3.17和表3.18所示。
表3.17 购买商品(对应的项集)
交易ID 购买商品(对应的项集)
1000 A ,C
2000 A ,B,C
4000 A ,D
5000 B,E,F
表3.18 频繁项集和支持度
频繁项集支 持 度
{A} sup(A)=3/4=75%
{B} sup(B)=2/4=50%
{C} sup(C)=2/4=50%
{A,C} sup(A ,C)=2/4=50%
对表3.17的解释如下。
(1)由于交易总的记录为4,因此n=4。
(2)由于在“购买商品”属性中,A 商品有3次,B 和C 商品分别有2次,{A ,C}即同时
140
大数据模型与应用(微课版)
购买A,
C
商品也是2次,因此,{A}的支持度=3/4=0.=B}的支持度=2/4=
0.=50% …。
7575%,{
5(3)由于事先已经(假设)定义好其支持数为2,即用2除以(总的记录数)4得50% 为最
小支持度,后面的计算规则中只有满足其最小支持度才有可能产生规则即知识。
su==
对于A,
C
而言,p({A,C})2/450% 。
因此,f({C})p({C})/66% 。
conA,=suA,sup(A)=50%/75%=66.
例3.现有A,C,
E
五种商品的交易记录表如表3.试找出三种商品关
3
B,D,19 所示
,
联销售情况(
K
=3), 假设最小支持度≥50%
。
表3.五种商品的交易记录表对应的项集
19
交易ID
商品代码(对应的项集)
100 A,C,
D
200 A,C,
E
300 A,B,C,
E
400 B,
E
解答:该问题的实质是要求我们运用表3.求出其长度为3的强项集
19 中的已知数据,
即L3。
可以根据表3.19 的已知条件,分别计算其KL1),和
K
的结果。
对应的项集与候选项集如表3.
=1(
K
=2(L2) =3(L3)
当
K
=1时, 20 所示。
表3.当K=1时,对应的项集与候选项集
20
K=1(长度为1的候选项集) 候选项集支持度
C1 {A} 2/4=0.5=50%
C1 {B} 3/4=0.75
C1 {C} 3/4=0.75
C1 {D} 1/4=0.25==25%
因支持度<50%,将其剔除
C1 {E} 3/4=0.75
通过表3.20 满足条件的结果,再求出当
K
=1时,其支持度≥50% 对应的强项集,如
表3.
21 所示。
表3.当K=1时,其支持度≥50%
对应的强项集
21
K=1(长度为1的候选项集) 候选项集支持度
C1 {A} 2/4=0.5=50%
C1 {B} 3/4=0.75
C1 {C} 3/4=0.75
C1 {E} 3/4=0.75
第3章关联规则模型与应用141
再根据表32.1的结果作为计算K=2的基础条件,求出K=2对应的支持度,如表3.所示。
2
表3.当K=2时,其候选项集对应的支持度
22
K=2(长度为2的候选项集) 候选项集支持度
C2 {A,B}
-
1 1/4=0.25=25%
C2 {A,C}
-
2 2/4=0.5=50%
C2 {A,D}
-
1 1/4=0.25=25%
C2 {B,C}
-
2 2/4=0.5=50%
C2 {B,E}
-
3 3/4=0.75=75%
C2 {C,D}
-
1 1/4=0.25=25%
C2 {C,E}
-
2 2/4=0.5=50%
将表3.22中不满足最小支持度<50%的候选项集剔除,如表3.
23所示。
表3.将不满足最小支持度的候选项集剔除
23
K=2(长度为2的候选项集) 候选项集支持度
C2 {A,B}
-
1 1/4=0.25=25%
因支持度<50%,将其剔除
C2 {A,C}
-
2 2/4=0.5=50%
C2 {A,D}
-
1 1/4=0.25=25%
因支持度<50%,将其剔除
C2 {B,C}
-
2 2/4=0.5=50%
C2 {B,E}
-
3 3/4=0.75=75%
C2 {C,D}
-
1 1/4=0.25=25%
因支持度<50%,将其剔除
C2 {C,E}
-
2 2/4=0.5=50%
剔除不满足最小支持度后的情况如表3.
24所示。
表3.剔除不满足最小支持度后的情况
24
K=2(长度为2的项集) 项集支持度
C2 {A,C}
-
2 2/4=0.5=50%
C2 {B,C}
-
2 2/4=0.5=50%
C2 {B,E}
-
3 3/4=0.75=75%
C2 {C,E}
-
2 2/4=0.5=50%
因此,根据表3.=2对应的强项集L2 结果如表3.
24计算
K
25所示。
表3.2对应的强项集L2
25
K=
K=2(长度为2的强项集L2) 强项集支持度
L2 {A,C}
-
2 2/4=0.5=50%
L2 {B,C}
-
2 2/4=0.5=50%
续表
142大数据模型与应用(微课版)
K=2(长度为2的强项集L2) 强项集支持度
L2 {B,E}--3 3/4=0.75=75%
L2 {C,E}--2 2/4=0.5=50%
即将表3.25缩写成L2 的表示形式,如表3.26所示。
表3.26将表3.25缩写成L2的表示形式
L2
{A,C} 50%
{B,C} 50%
{B,E} 75%
{C,E} 50%
再按照表3.26计算K=3的强项集,如表3.27所示。
表3.27K=3对应的强项集L3K=3(长度为3的强项集) 强项集支持度
C3 {A,B,C}--1 sup(A,B,C)=1/4=0.25=25%
C3 {A,C,E}--1 sup(A,B,C)=1/4=0.25=25%
C3 {B,C,E}--2 sup(A,B,C)=2/4=0.5=50%
**满足K=3的强项集条件
表3.27缩写成L3 的表示形式,如表3.
28所示。
表3.长度为3的强项集L3
28
L3 {B,C,E} 50%
归纳起来,求解表3.即求
K
=的整个计算过程,
可以用图3.19的三种关联销售情况(3的强项集)
1表示。
图3.按照表3.3的强项集L3
的图示
1
19计算K=
第3章关联规则模型与应用143
基于Hadoop
的词频统
计方法
..3.3关联规则的创新应用研究
3.3.1基于Hadoop环境下Map-Reduce流程的应用
Hadoop环境下执行Map-Reduce流程的一个例子,如图3.2所示。
图3.2
Hadop环境下执行Map-Reduce流程的一个例子
在图3.2的机制下,可以完成基于Hadoop环境下的并行词频统计,例如,可以将I1 到I5
称为一个文本,假设是由英语单词构成的文本(语句或词组,或英语词组等内容),英语文本内
trfiI2=“iI3=“aatxI5=“iigo
容是I1=“,(”) ,(”) ,(”) ,(”) ”;经过Hadp环境下Map
acbgdtI4=“etmnnodce处理流程(统计单词)后,其输出结果分别为:tac”(总数为6),bg”(总数R
为
e7u),”(总数为6),”(总数为2),
I1=“rfi”(总数为2)。
I2=“i
I3=“dtI4=“etmnn
aatxI5=“iig
通过Hadoop机制下的词频统计例子,可以得知:Map-Reduce是目前处理并行计算的
非常优秀的解决方法。也可以运用这种机制来解决其他相关领域的并行统计机制的算法,
例如,通过对网络环境下的某领域的热点词和热点话题内容的统计与分析,来判断物流企业
的管理与决策领域关注的重点业务需求如何;通过某大型超市商品种类的新需求来决定并
及时调整进货的数量。
3.3.2
基于FP-tre
的频繁项集的挖掘方法
韩家伟等学者在2000年提出了分而治之策略的FP-tre
递归增长频繁项集。具体的
方法是:①对每个项(item)生成其条件模式库,再作为其条件FP-tre;②对每个新生成的
条件FP-tre,重复执行其步骤;③如果FP-tre
为空,或者仅含有一个路径(此路径对应的
每个子路径都是频繁项集)则结束。
下面通过表3.-r的过程。
29的举例来解释构造FPte