关于关联规则的一些资料
关联规则
经典案例导入
• 在一家超市中,人们发现了一个特别有趣的现象:尿布与啤酒这两种风马牛不相及的商品居然摆在一起。但这一奇怪的举措居然使尿布和啤酒的销量大幅增加了。这可不是一个笑话,而是一直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实案例。原来,美国的妇女通常在家照顾孩子,所以她们经常会嘱咐丈夫在下班回家的路上为孩子买尿布,而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。这个发现为商家带来了大量的利润,但是如何从浩如烟海却又杂乱无章的数据中,发现啤酒和尿布销售之间的联系呢?这又给了我们什么样的启示呢?
• 这就是我们所说的——关联规则!
关联规则引论
• 关联式规则(Association Rules, AR),又称关联规则,是数据挖掘的一个重要课题,用于从大量数据中挖掘出有价值的数据项之间的相关关系。关联规则解决的常见问题如:“如果一个消费者购买了产品A,那么他有多大机会购买产品B?”以及“如果他购买了产品C和D,那么他还将购买什么产品?”正如大多数数据挖掘技术一样,关联规则的任务在于减少潜在的大量杂乱无章的数据,使之成为少量的易于观察理解的静态资料。关联式规则多不考虑项目的次序,而仅考虑其组合。
• 关联规则一个经典的实例是购物篮分析(Market Basket Analysis)。超市对顾客的购买记录数据库进行关联规则挖掘,可以发现顾客的购买习惯,例如,购买产品X的同时也购买产品Y,于是,超市就可以调整货架的布局,比如将X产品和Y产品放在一起,增进销量。
关联规则的基本概念
根据韩家炜等,关联规则定义为:
假设 是项的集合。给定一个交易数据库 ,其中每个事务(Transaction)t是I的非空子集,即t是 I的非空子集,即 ,每一个交易都与一个唯一的标识符TID(Transaction ID)对应。关联规则是形如 的蕴涵式,其中 且 , X和Y分别称为关联规则的先导(antecedent或left-hand-side,LHS)和后继(consequent或right-hand-side,RHS) 。关联规则 在D中的支持度(support)是D中事务包含 的百分比,即概率 ;置信度(confidence)是包含X的事务中同时包含Y的百分比,即条件概率P ( Y | X)。如果同时满足最小支持度阈值和最小置信度阈值,则认为关联规则是有趣的。这些阈值由用户或者专家设定。
关联规则的基本量
• 支持度:
支持度指的是A和B 同时出现的概率。
• 置信度:
置信度表示在A出现的情况下,B出现的概率。
• 提升度:
提升度是一种简单的相关性度量,定义如下。项集A的出现独立于项集B的出现,如果 ;否则作为事件,项集A和B是依赖的和相关的。若lift <1,则A的出现于B的出现是负相关的,意味着一个出现将会导致另一个不出现;若lift >1,则A的出现于B的出现是正相关的,意味着一个的出现将蕴含着另一个的出现;若lift=1,则A,B之间相互独立,不存在相关性。
案例
用一个简单的例子说明。表1是顾客购买记录的数据库D,包含6个事务。项集I={网球拍,网球,运动鞋,羽毛球}。考虑关联规则:网球拍网球,事务1,2,3,4,6包含网球拍,事务1,2,6同时包含网球拍和网球,支持度support= 3/6= 0.5,置信度confident= 3/5=0.6。若给定最小支持度 ,最小置信度 ,关联规则 是有趣的,认为购买网球拍和购买网球之间存在强关联.
表1:关联规则的简单例子 | ||||
TID | 网球拍 | 网 球 | 运动鞋 | 羽毛球 |
1 | 1 | 1 | 1 | 0 |
2 | 1 | 1 | 0 | 0 |
3 | 1 | 0 | 0 | 0 |
4 | 1 | 0 | 1 | 0 |
5 | 0 | 0 | 1 | 1 |
6 | 1 | 1 | 0 | 0 |
关联规则的分类
根据关联规则所处理的值的类型
如果考虑关联规则中的数据项是否出现,则这种关联规则是布尔关联规则(Boolean associationrules)。例如上面的例子。
如果关联规则中的数据项是数量型的,这种关联规则是数量关联规则(quantitativeassociation rules)。例如年龄("20-25")购买("网球拍"),年龄是一个数量型的数据项。在这种关联规则中,一般将数量离散化(discretize)为区间。
根据关联规则所涉及的数据维数
如果关联规则各项只涉及一个维,则它是单维关联规则(single-dimensionalassociation rules),例如购买("网球拍")购买("网球")只涉及“购买”一个维度。
如果关联规则涉及两个或两个以上维度,则它是多维关联规则(multi-dimensionalassociation rules),例如年龄("20-25")购买("网球拍")涉及“年龄”和“购买”两个维度。
根据关联规则所涉及的抽象层次
如果不涉及不同层次的数据项,得到的是单层关联规则(single-levelassociation rules)。
在不同抽象层次中挖掘出的关联规则称为广义关联规则(generalizedassociation rules)。例如年龄(“20-25”)购买(“HEAD网球拍”)和年龄(“20-25”)购买(“网球拍”)是广义关联规则,因为“HEAD网球拍”和“网球拍”属于不同的抽象层次。
算法
Apriori 算法
F-P算法
Eclat算法
算法
Apriori 算法[
Apriori算法是种最有影响的挖掘布尔关联规则频繁项集的算法。它的核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集(简称频集),也常称为最大项目集。
在Apriori算法中,寻找最大项目集(频繁项集)的基本思想是:算法需要对数据集进行多步处理。第一步,简单统计所有含一个元素项目集出现的频数,并找出那些不小于最小支持度的项目集,即一维最大项目集。从第二步开始循环处理直到再没有最大项目集生成。循环过程是:第k步中,根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集,然后对数据库进行搜索,得到侯选项目集的项集支持度,与最小支持度进行比较,从而找到k维最大项目集。
下面以图例的方式说明该算法的运行过程:假设有一个数据库D,其中有4个事务记录,分别表示为:
TID | Items |
T1 | I1,I3,I4 |
T2 | I2,I3,I5 |
T3 | I1,I2,I3,I5 |
T4 | I2,I5 |
这里预定最小支持度minSupport=2,下面用图例说明算法运行的过程:
TID | Items |
T1 | I1,I3,I4 |
T2 | I2,I3,I5 |
T3 | I1,I2,I3,I5 |
T4 | I2,I5 |
扫描D,对每个候选项进行支持度计数得到表C1:
项集 | 支持度计数 |
{I1} | 2 |
{I2} | 3 |
{I3} | 3 |
{I4} | 1 |
{I5} | 3 |
比较候选项支持度计数与最小支持度minSupport,产生1维最大项目集L1:
项集 | 支持度计数 |
{I1} | 2 |
{I2} | 3 |
{I3} | 3 |
{I5} | 3 |
由L1产生候选项集C2:
项集 |
{I1,I2} |
{I1,I3} |
{I1,I5} |
{I2,I3} |
{I2,I5} |
{I3,I5} |
扫描D,对每个候选项集进行支持度计数:
项集 | 支持度计数 |
{I1,I2} | 1 |
{I1,I3} | 2 |
{I1,I5} | 1 |
{I2,I3} | 2 |
{I2,I5} | 3 |
{I3,I5} | 2 |
比较候选项支持度计数与最小支持度minSupport,产生2维最大项目集L2:
项集 | 支持度计数 |
{I1,I3} | 2 |
{I2,I3} | 2 |
{I2,I5} | 3 |
{I3,I5} | 2 |
由L2产生候选项集C3:
项集 |
{I2,I3,I5} |
比较候选项支持度计数与最小支持度minSupport,产生3维最大项目集L3:
项集 | 支持度计数 |
{I2,I3,I5} | 2 |
算法终止。
从算法的运行过程,我们可以看出该Apriori算法的优点:简单、易理解、数据要求低,然而我们也可以看到Apriori算法的缺点:(1)在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;(2)每次计算项集的支持度时,都对数据库D中的全部记录进行了一遍扫描比较,如果是一个大型的数据库的话,这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法,如下面要介绍的F-P算法。
F-P算法[编辑]
针对Apriori算法的性能瓶颈问题-需要产生大量候选项集和需要重复地扫描数据库,2000年Jiawei Han等人提出了基于FP树生成频繁项集的FP-growth算法。该算法只进行2次数据库扫描且它不使用侯选集,直接压缩数据库成一个频繁模式树,最后通过这棵树生成关联规则。研究表明它比Apriori算法大约快一个数量级。
FP-growth算法是一种不产生候选模式而采用频繁模式增长的方法挖掘频繁模式的算法。算法只需要扫描2次数据库:第一次扫描数据库,得到1维频繁项集;第二次扫描数据库,利用1维频繁项集过滤数据库中的非频繁项,同时生成FP树。由于FP树蕴涵了所有的频繁项集,其后的频繁项集的挖掘只需要在FP树上进行。FP树挖掘由两个阶段组成:第一阶段建立FP树,即将数据库中的事务构造成一棵FP树;第二阶段为挖掘FP树,即针对FP树挖掘频繁模式和关联规则。
FP-growth算法描述:
输入:事务数据库D,最小支持度minSupport。
输出:频繁模式的完全集。
方法:
1 构建FP树:
1.1 扫描事务数据库,收集频繁项集F并统计支持度,对F按支持度降序排序,得到频率排序好的项表L。
1.2 创建FP树的根节点,用“null”标记它。对于D中每个事务T,执行:选择T中的频繁项,并按L中的次序排序。设排序后的频繁项表为[p|P],其中p是第一个元素,而P是剩余元素的表。调用insert_tree([p|P],T)。该过程执行情况如下:如果T有子女N使得N.itemName=p.itemName,则N的计数增加1;否则创建一个新节点N,将其计数设置为1,链接到它的父节点T,并且通过节点链结构将其链接到具有相同itemName的节点。如果P非空,递归地调用insert_tree(P,N)。
2 FP树的规则挖掘(通过FP-growth(Tree,α)函数来实现,初始调用FP-growth(Tree,null)):
if Tree含单个路径P then {
for 路径P中节点的每个组合(记作β)
产生模式β∪α,其支持度support=β中节点的最小支持度; }
else for each αi 在Tree的头部 do {
产生模式β=αi ∪ α,其支持度support=αi.support;
构造β的条件模式基,然后构造β的条件FP树Treeβ;
if Treeβ≠空集 then
调用FP_growth(Treeβ,β) }
end
F-P算法实现[编辑]
Bash版本:请参考文章FP-growth算法实现
Eclat算法[编辑]
与fp-growth 和apriori算法不同,Eclat算法加入了倒排的思想,具体就是将事务数据中的项作为key,每个项对应的事务ID作为value。
原输入数据为
tid | item |
1 | A,B |
2 | B,C |
3 | A,C |
4 | A,B,C |
转换后为:
item | tids |
A | 1,3,4 |
B | 1,2,4 |
C | 2,3,4 |
通过转换后的倒排表可以加快频繁集生成速度。其算法思想是由频繁k项集求交集,生成候选k+1项集。对候选k+1项集做裁剪,生成频繁k+1项集,再求交集生成候选k+2项集。如此迭代,直到项集归一。根据上述数据的情况,具体计算过程为
算法过程:
1.计算频繁1项集,结果为:
item | freq |
A | 3 |
B | 3 |
C | 3 |
2.由频繁1项集生成频繁2项集
item | freq |
A,B | 2 |
A,C | 2 |
B,C | 2 |
3.由频繁2项集生成频繁3项集
item | freq |
A,B,C | 1 |
频繁k项集生成频繁k+1项集的过程与由1项集生成2项集的过程完全一致。
这里有个隐含的条件是,两个频繁k项集生成k+1项集时,前k-1项是一致的,A,B+A,C==>A,B,C
Apriori 算法 在R中的使用
我们采用最经典的购物篮数据(Groceries)
属性说明:transactions in sparse format with 9835 transactions (rows) and 169 items (columns)
CODE:
library(arules) #加载arules程序包
## Warning: package 'arules' was builtunder R version 3.1.1
## Loading required package: Matrix
## Warning: package 'Matrix' was builtunder R version 3.1.1
##
## Attaching package: 'arules'
##
## 下列对象被屏蔽了from 'package:base':
##
## %in%, write
data(Groceries) #调用数据文件
frequentsets=eclat(Groceries,parameter=list(support=0.05,maxlen=10)) #求频繁项集
##
## parameter specification:
## tidLists support minlenmaxlen target ext
## FALSE 0.05 1 10 frequent itemsets FALSE
##
## algorithmic control:
## sparse sort verbose
## 7 -2 TRUE
##
## eclat - find frequent item sets with the eclat algorithm
## version 2.6 (2004.08.16) (c) 2002-2004 Christian Borgelt
## create itemset ...
## set transactions ...[169 item(s), 9835 transaction(s)] done[0.00s].
## sorting and recoding items ... [28 item(s)] done [0.00s].
## creating sparse bit matrix ... [28 row(s), 9835 column(s)] done[0.00s].
## writing ... [31 set(s)] done[0.02s].
## Creating S4 object ... done[0.00s].
inspect(frequentsets[1:10]) #察看求得的频繁项集
## items support
## 1 {whole milk,
## yogurt} 0.05602
## 2 {whole milk,
## rolls/buns} 0.05663
## 3 {other vegetables,
## whole milk} 0.07483
## 4 {whole milk} 0.25552
## 5 {other vegetables} 0.19349
## 6 {rolls/buns} 0.18393
## 7 {yogurt} 0.13950
## 8 {soda} 0.17438
## 9 {root vegetables} 0.10900
## 10 {tropical fruit} 0.10493
inspect(sort(frequentsets,by="support")[1:10]) #根据支持度对求得的频繁项集排序并察看(等价于inspect(sort(frequentsets)[1:10])
## items support
## 1 {whole milk} 0.25552
## 2 {other vegetables} 0.19349
## 3 {rolls/buns} 0.18393
## 4 {soda} 0.17438
## 5 {yogurt} 0.13950
## 6 {bottled water} 0.11052
## 7 {root vegetables} 0.10900
## 8 {tropical fruit} 0.10493
## 9 {shopping bags} 0.09853
## 10 {sausage} 0.09395
rules=apriori(Groceries,parameter=list(support=0.01,confidence=0.01)) #求关联规则
##
## parameter specification:
## confidence minval smaxarem aval originalSupport support minlenmaxlen
## 0.01 0.1 1 none FALSE TRUE 0.01 1 10
## target ext
## rules FALSE
##
## algorithmic control:
## filter tree heap memopt loadsort verbose
## 0.1 TRUE TRUE FALSE TRUE 2 TRUE
##
## apriori - find association rules with the apriori algorithm
## version 4.21 (2004.05.09) (c) 1996-2004 Christian Borgelt
## set item appearances ...[0 item(s)] done [0.00s].
## set transactions ...[169 item(s), 9835 transaction(s)] done[0.00s].
## sorting and recoding items ... [88 item(s)] done [0.00s].
## creating transaction tree ... done [0.02s].
## checking subsets of size 1 2 3 4 done [0.01s].
## writing ... [610 rule(s)] done [0.00s].
## creating S4 object ... done[0.00s].
summary(rules) #察看求得的关联规则之摘要
## set of 610 rules
##
## rule length distribution (lhs + rhs):sizes
## 1 2 3
## 88 426 96
##
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 1.00 2.00 2.00 2.01 2.00 3.00
##
## summary of quality measures:
## support confidence lift
## Min. :0.0101 Min. :0.0103 Min. :0.79
## 1st Qu.:0.0116 1st Qu.:0.0889 1st Qu.:1.15
## Median :0.0146 Median :0.1590 Median :1.49
## Mean :0.0214 Mean :0.1910 Mean :1.56
## 3rd Qu.:0.0223 3rd Qu.:0.2618 3rd Qu.:1.83
## Max. :0.2555 Max. :0.5862 Max. :3.37
##
## mining info:
## data ntransactionssupport confidence
## Groceries 9835 0.01 0.01
x=subset(rules,subset=rhs%in%"whole milk"&lift>=1.2) #求所需要的关联规则子集
inspect(sort(x,by="support")[1:5]) #根据支持度对求得的关联规则子集排序并察看
## lhs rhs support confidence lift
## 1 {other vegetables} => {whole milk} 0.07483 0.3868 1.514
## 2 {rolls/buns} =>{whole milk} 0.05663 0.3079 1.205
## 3 {yogurt} =>{whole milk} 0.05602 0.4016 1.572
## 4 {root vegetables} =>{whole milk} 0.04891 0.4487 1.756
## 5 {tropical fruit} =>{whole milk} 0.04230 0.4031 1.578
Eclat()函数:
function (data, parameter = NULL, control =NULL)
{
data <- as(data, "transactions")
items <- data@data
parameter <- as(parameter, "ECparameter")
control <- as(control, "ECcontrol")
if (control@verbose) {
cat("\nparameter specification:\n")
print(parameter)
cat("\nalgorithmic control:\n")
print(control)
cat("\n")
}
abs_supp <- as.integer(parameter@support * length(data))
if (abs_supp < 2)
课后习题
1912年4月15日,载着1316号乘客和891名船员的豪华巨轮“泰坦尼克号”与冰山相撞而沉没,这场海难被认为是20世纪人间十大灾难之一。有人丧生,有人生还,请以此数据为例进行人员生还与丧生的关联分析。(此数据为R内置数据集Titanic)
解答:
Answer1:
使用数据:Titanic
# look for data
str(Titanic)
# transform table into data frame
df <- as.data.frame(Titanic)
head(df)
> head(df)
Class Sex AgeSurvivedFreq
1 1st MaleChild No 0
2 2nd MaleChild No 0
3 3rd MaleChild No 35
4 Crew MaleChild No 0
titanic.raw <- NULL
# 如果频率字段大于0,将该行记录按列追加到变量中,Freq=0,当然就不追加
for(iin1:4) {
titanic.raw <- cbind(titanic.raw, rep(as.character(df[,i]),
df$Freq))
}
# 前35行都是一样的
]]]]> titanic.raw[1:36,]
[,1] [,2] [,3] [,4]
[1,]"3rd""Male" "Child""No"
[2,]"3rd""Male" "Child""No"
[3,]"3rd""Male" "Child""No"
[4,]"3rd""Male" "Child""No"
...
[35,]"3rd""Male" "Child""No"
[36,]"3rd""Female""Child""No"
# transform to data frame
titanic.raw <- as.data.frame(titanic.raw)
> head(titanic.raw)
V1 V2 V3V4
1 3rd MaleChildNo
2 3rd MaleChildNo
3 3rd MaleChildNo
4 3rd MaleChildNo
5 3rd MaleChildNo
6 3rd MaleChildNo
# 生成数据框后添加属性名称
names(titanic.raw) <- names(df)[1:4];dim(titanic.raw);
summary(titanic.raw)
# 转换后:每一行代表了一个人,可以用于关联规则。转换前是什么类型的数据? (按照class、sex、年龄汇总的生存人数的数据)
With the function, the default settings are:1) supp=0.1, which is the minimum support ofrules;2) conf=0.8, which is the minimum confidence ofrules; and 3) maxlen=10, which is the maximum length ofrules.
library(arules)
rules <- apriori(titanic.raw) # apriori可以直接传递非transactions类型的对象,内部自动转换
rules # 根据最小的 (supp=0.1,conf=0.8),返回的规则的最多个数 10个
summary(rules);
inspect(rules);
quality(rules) <- quality(rules)
inspect(rules)
翻译:
关联规则挖掘一个常见的现象是,很多产生的规则并不是有趣的。考虑到我们只关心规则的右件(rhs)表示是否生存,
所以我们参数 appearance 中设置 rhs=c("Survived=No","Survived=Yes") 并确定只有这两种情况出现在规则右件中(rhs).
其它的项集可以出现在规则左件(lhs),使用default="lhs"设置。
上面的结果也可以看到,第一个规则的lhs 是个空集,为了排除这样的规则,可以使用minlen=2。
而且,算法处理的过程被压缩(简化)是通过verbose=F设置的。
关联规则挖掘结束后,规则将会以lift提升度按照从大到小的排序方式进行排序
rules.better <- apriori(titanic.raw,
parameter
=list(minlen
= 2,
supp =0.005,
conf =0.8),
appearance
= list(rhs
=c("Survived=No",
"Survived=Yes"), default
="lhs"),
control
= list(verbose=F)
)
# base on lift sorted
rules.sorted <- sort(rules.better, by="lift")
inspect(rules.sorted)
> inspect(rules.sorted)
lhs rhs supportconfidence lift
1 {Class=2nd,
Age=Child} => {Survived=Yes} 0.010904134 1.00000003.095640
2 {Class=2nd,
Sex=Female,
Age=Child} => {Survived=Yes} 0.005906406 1.00000003.095640
3 {Class=1st,
Sex=Female} => {Survived=Yes} 0.064061790 0.97241383.010243
4 {Class=1st,
Sex=Female,
Age=Adult} => {Survived=Yes} 0.063607451 0.97222223.009650
5 {Class=2nd,
Sex=Female} => {Survived=Yes} 0.042253521 0.87735852.715986
6 {Class=Crew,
Sex=Female} => {Survived=Yes} 0.009086779 0.86956522.691861
7 {Class=Crew,
Sex=Female,
Age=Adult} => {Survived=Yes} 0.009086779 0.86956522.691861
8 {Class=2nd,
Sex=Female,
Age=Adult} => {Survived=Yes} 0.036347115 0.86021512.662916
9 {Class=2nd,
Sex=Male,
Age=Adult} => {Survived=No} 0.069968196 0.91666671.354083
10 {Class=2nd,
Sex=Male} => {Survived=No} 0.069968196 0.86033521.270871
11 {Class=3rd,
Sex=Male,
Age=Adult} => {Survived=No} 0.175829169 0.83766231.237379
12 {Class=3rd,
Sex=Male} => {Survived=No} 0.191731031 0.82745101.222295
翻译:
当其它设置不发生变化的情况下,越小的支持度会产生更多的规则。这种产生的规则中项集之间的关联看起来更像是随机的。
在上例中,最小支持度为0.005,那么每一个规则至少有 支持度*交易数(记录数) 个案例 是满足支持度为0.005的。(2201 * 0.005 = 12)
支持度,置信度,提升度是选择兴趣规则的三个方法。还有一切其它的衡量方法,包括卡方,gini等。有多余20中这样的计算方法在interestMeasure()方法中
### 规则的剪枝
从上面的例子中,我们能够发现一些规则与其它规则相比没有提供额外的信息。(提供的信息少)。
比如第二个规则给出的信息,在第一个规则中已经都阐述明白了。因为规则1告诉我们 所有的 2nd-class的孩子都幸存了。
(即 Class=2nd,Age=Child 所有的都幸存了,置信度和lift都是一致的,再增加一个sex的判断是冗余的)
我们以这个例子来阐述何种情况定义为redundant(冗余)
总体来说,规则2 是 规则1 的衍生规则,如果规则2 和 规则1 有相同的 提升度或者 比 规则1 更低的提升度,那么规则2 就被认为是冗余的。
总结 :规则2 比 规则1 lhs多了sex的条件,同时lift ,两者相同,所以规则2冗余
lhs rhs support confidence lift
1 {Class=2nd,
Age=Child} =>{Survived=Yes}0.010904134 1.0000000 3.095640
2 {Class=2nd,
Sex=Female,
Age=Child} =>{Survived=Yes}0.005906406 1.0000000 3.095640
代码:
函数解释:
is.subset(r1, r2): 检查r1是否为r2的子集
lower.tri():返回一个逻辑以TRUE为下三角的matrix;diag=T表示包含主对角线
# redundant
subset.matrix <- is.subset(rules.sorted, rules.sorted) #
# 使得下三角包含主对角线设置为NA
subset.matrix[lower.tri(subset.matrix, diag=T)] <- NA
# 计算列TRUE的数量
redundant <- colSums(subset.matrix, na.rm=T) >= 1; #
which(redundant) # 冗余规则的下标
# 删除冗余规则
rules.pruned <- rules.sorted[!redundant]
inspect(rules.pruned)
> inspect(rules.pruned)
lhs rhs support confidence lift
1 {Class=2nd,
Age=Child} => {Survived=Yes} 0.010904134 1.0000000 3.095640
2 {Class=1st,
Sex=Female} => {Survived=Yes} 0.064061790 0.9724138 3.010243
3 {Class=2nd,
Sex=Female} => {Survived=Yes} 0.042253521 0.8773585 2.715986
4 {Class=Crew,
Sex=Female} => {Survived=Yes} 0.009086779 0.8695652 2.691861
5 {Class=2nd,
Sex=Male,
Age=Adult} => {Survived=No} 0.069968196 0.9166667 1.354083
6 {Class=2nd,
Sex=Male} => {Survived=No} 0.069968196 0.8603352 1.270871
7 {Class=3rd,
Sex=Male,
Age=Adult} => {Survived=No} 0.175829169 0.8376623 1.237379
8 {Class=3rd,
Sex=Male} => {Survived=No} 0.191731031 0.8274510 1.222295
规则的解释:(解释规则)
很容易就能找到高提升度的数据,但是理解识别出来的规则并不是一件容易的事情。
关联规则在寻找商业意义上被误解读是很常见的。
比如,第一个规则,{Class=2nd,Age=Child} => {Survived=Yes}
规则的置信度为1,提升度为3,并且没有规则揭示age=Child时,class=c("1nd","3nd").
因此,这样可能就会被分析师解释为:类别为2的孩子比其它类别的孩子(1,3)有更高的生存几率。
这种解释是完全的错误的!!!!
这个规则仅表示所有类别为2的孩子幸存下来了,但是没有提供任何信息来进行比较不同的类别的孩子的生存率
为了研究以上的问题,我们可以通过找到规则右件为存活的,即rhs为 Survived=Yes,
规则左件lhs 仅仅包括 Class=1st,2nd,3rd, Age=Child,Adult;不包括其它项集(如default="none")
我们对支持度和置信度使用较之前拟合模型这两个参数较低的阈值,去找出所有孩子不同类别的规则。
为了方便,先将原来计算的规则写出来,好做比较
# former rules set
rules.better <- apriori(titanic.raw,
parameter
=list(minlen
= 2,
supp =0.005,
conf =0.8),
appearance
= list(rhs
=c("Survived=No",
"Survived=Yes"), default
="lhs"),
control
= list(verbose=F)
)
# compare rules set
rules <- apriori(titanic.raw,
parameter
=list(minlen=3,supp=0.002,
conf=0.2),
appearance
= list(rhs=c("Survived=Yes"),
lhs=c("Class=1st",
"Class=2nd", "Class=3rd",
"Age=Child",
"Age=Adult"),
default="none"),
control
= list(verbose
= F)
);
rules.sorted <- sort(rules, by = "confidence")
inspect(rules.sorted)
lhs rhs support confidence lift
1{Class=2nd,
Age=Child}=>{Survived=Yes}0.010904134 1.0000000 3.0956399
2{Class=1st,
Age=Child}=>{Survived=Yes}0.002726034 1.0000000 3.0956399
3{Class=1st,
Age=Adult}=>{Survived=Yes}0.089504771 0.6175549 1.9117275
4{Class=2nd,
Age=Adult}=>{Survived=Yes}0.042707860 0.3601533 1.1149048
5{Class=3rd,
Age=Child}=>{Survived=Yes}0.012267151 0.3417722 1.0580035
6{Class=3rd,
Age=Adult}=>{Survived=Yes}0.068605179 0.2408293 0.7455209
根据结果,前两个规则中,1类和2类的孩子有相同的幸存率并且都幸存了下来(置信度为1)。
那么1类的孩子的规则没有出现在之前的规则列表中,是因为支持度阈值低于设定的阈值(0.005),1类此时supp为0.002.
规则5与规则4相比,3类的孩子存活率只有很低的34%,(此处只是比较的conf,无法按照class和age比较),
而和规则3(1类的成年人)比较,存活率(置信度)就更低了
Answer2:
关联算法现象的应用我们可能听的比较多。像沃尔玛的尿布和啤酒的故事。
其最核心的概念是可信度和支持度,另外还有一个可靠度(lift),这里不再详述。
· 首先我们准备这样一个数据集。
如下
> str(Titanic) |
· 关联规则挖掘
一个经典的关联算法即是APRIORI。它是一个面向层级的,广度优先算法,通过找到对交易进行计次来找到频繁项集而后推演出关联规则。arule中的apriori()即是其实现。
另外还有一个算法是ECLAT算法。它是深度优先的,并且不是通过计数,而是集合的交集来实现,arule中的eclat()实现了该算法。
下面我们来通过apriori()来显示关联规则。该函数默认的设置是:1)supp=0.1 2)conf=0.8 3)maxlen=10
> library(arules) |
通过上面得到的规则有很多是没有意义或者不感兴趣的。假如我们只对右边rhs是survival特征感兴趣,那么通过在appearance中设置rhs=c("Survived=No", "Survived=Yes")即可,另外default="lhs",其他所有的项将会出现在左边lhs。
上面的得到的规则集中第一个规则的lhs是空,这种情况可以通过设置minlen=2来排除。最后通过lift将高可靠度的规则置前。
> rules <- apriori(titanic.raw, control = list(verbose=F), |
· 消除冗余
上面产生的规则中,rule2是rule1的子集,没有提供更多的知识,这种情况下rule2可考虑消除。
> subset.matrix <- is.subset(rules.sorted, rules.sorted) |
· 解释规则
找到规则很容易,但得要看你怎么去理解这些规则了。比如像上面的第一个规则{Class=2nd, Age=Child} => {Survived=Yes},具有高可信度1和可靠度3,而并没有class 1st 和3rd 孩子的幸存记录,这种情况是否说明了class 2nd比其他有更高的存活率呢?不是,因为根本就没有提供相关的数据用于比较。为了这个话题,我们将lhs设置为仅包含"Class=1st", "Class=2nd","Class=3rd", "Age=Child"和"Age=Adult",rhs是"Survived=Yes"。为了获取更多的记录,我们降低支持度和可信度参数。
> rules <- apriori(titanic.raw, |
可见,头等舱和二等舱的儿童具有相同的幸存率。而三等舱的幸存率明显较低。
· 关联规则的可视化
> library(arulesViz) |
关于关联规则的一些资料
关联规则
经典案例导入
• 在一家超市中,人们发现了一个特别有趣的现象:尿布与啤酒这两种风马牛不相及的商品居然摆在一起。但这一奇怪的举措居然使尿布和啤酒的销量大幅增加了。这可不是一个笑话,而是一直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实案例。原来,美国的妇女通常在家照顾孩子,所以她们经常会嘱咐丈夫在下班回家的路上为孩子买尿布,而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。这个发现为商家带来了大量的利润,但是如何从浩如烟海却又杂乱无章的数据中,发现啤酒和尿布销售之间的联系呢?这又给了我们什么样的启示呢?
• 这就是我们所说的——关联规则!
关联规则引论
• 关联式规则(Association Rules, AR),又称关联规则,是数据挖掘的一个重要课题,用于从大量数据中挖掘出有价值的数据项之间的相关关系。关联规则解决的常见问题如:“如果一个消费者购买了产品A,那么他有多大机会购买产品B?”以及“如果他购买了产品C和D,那么他还将购买什么产品?”正如大多数数据挖掘技术一样,关联规则的任务在于减少潜在的大量杂乱无章的数据,使之成为少量的易于观察理解的静态资料。关联式规则多不考虑项目的次序,而仅考虑其组合。
• 关联规则一个经典的实例是购物篮分析(Market Basket Analysis)。超市对顾客的购买记录数据库进行关联规则挖掘,可以发现顾客的购买习惯,例如,购买产品X的同时也购买产品Y,于是,超市就可以调整货架的布局,比如将X产品和Y产品放在一起,增进销量。
关联规则的基本概念
根据韩家炜等,关联规则定义为:
假设 是项的集合。给定一个交易数据库 ,其中每个事务(Transaction)t是I的非空子集,即t是 I的非空子集,即 ,每一个交易都与一个唯一的标识符TID(Transaction ID)对应。关联规则是形如 的蕴涵式,其中 且 , X和Y分别称为关联规则的先导(antecedent或left-hand-side,LHS)和后继(consequent或right-hand-side,RHS) 。关联规则 在D中的支持度(support)是D中事务包含 的百分比,即概率 ;置信度(confidence)是包含X的事务中同时包含Y的百分比,即条件概率P ( Y | X)。如果同时满足最小支持度阈值和最小置信度阈值,则认为关联规则是有趣的。这些阈值由用户或者专家设定。
关联规则的基本量
• 支持度:
支持度指的是A和B 同时出现的概率。
• 置信度:
置信度表示在A出现的情况下,B出现的概率。
• 提升度:
提升度是一种简单的相关性度量,定义如下。项集A的出现独立于项集B的出现,如果 ;否则作为事件,项集A和B是依赖的和相关的。若lift <1,则A的出现于B的出现是负相关的,意味着一个出现将会导致另一个不出现;若lift >1,则A的出现于B的出现是正相关的,意味着一个的出现将蕴含着另一个的出现;若lift=1,则A,B之间相互独立,不存在相关性。
案例
用一个简单的例子说明。表1是顾客购买记录的数据库D,包含6个事务。项集I={网球拍,网球,运动鞋,羽毛球}。考虑关联规则:网球拍网球,事务1,2,3,4,6包含网球拍,事务1,2,6同时包含网球拍和网球,支持度support= 3/6= 0.5,置信度confident= 3/5=0.6。若给定最小支持度 ,最小置信度 ,关联规则 是有趣的,认为购买网球拍和购买网球之间存在强关联.
表1:关联规则的简单例子 | ||||
TID | 网球拍 | 网 球 | 运动鞋 | 羽毛球 |
1 | 1 | 1 | 1 | 0 |
2 | 1 | 1 | 0 | 0 |
3 | 1 | 0 | 0 | 0 |
4 | 1 | 0 | 1 | 0 |
5 | 0 | 0 | 1 | 1 |
6 | 1 | 1 | 0 | 0 |
关联规则的分类
根据关联规则所处理的值的类型
如果考虑关联规则中的数据项是否出现,则这种关联规则是布尔关联规则(Boolean associationrules)。例如上面的例子。
如果关联规则中的数据项是数量型的,这种关联规则是数量关联规则(quantitativeassociation rules)。例如年龄("20-25")购买("网球拍"),年龄是一个数量型的数据项。在这种关联规则中,一般将数量离散化(discretize)为区间。
根据关联规则所涉及的数据维数
如果关联规则各项只涉及一个维,则它是单维关联规则(single-dimensionalassociation rules),例如购买("网球拍")购买("网球")只涉及“购买”一个维度。
如果关联规则涉及两个或两个以上维度,则它是多维关联规则(multi-dimensionalassociation rules),例如年龄("20-25")购买("网球拍")涉及“年龄”和“购买”两个维度。
根据关联规则所涉及的抽象层次
如果不涉及不同层次的数据项,得到的是单层关联规则(single-levelassociation rules)。
在不同抽象层次中挖掘出的关联规则称为广义关联规则(generalizedassociation rules)。例如年龄(“20-25”)购买(“HEAD网球拍”)和年龄(“20-25”)购买(“网球拍”)是广义关联规则,因为“HEAD网球拍”和“网球拍”属于不同的抽象层次。
算法
Apriori 算法
F-P算法
Eclat算法
算法
Apriori 算法[
Apriori算法是种最有影响的挖掘布尔关联规则频繁项集的算法。它的核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集(简称频集),也常称为最大项目集。
在Apriori算法中,寻找最大项目集(频繁项集)的基本思想是:算法需要对数据集进行多步处理。第一步,简单统计所有含一个元素项目集出现的频数,并找出那些不小于最小支持度的项目集,即一维最大项目集。从第二步开始循环处理直到再没有最大项目集生成。循环过程是:第k步中,根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集,然后对数据库进行搜索,得到侯选项目集的项集支持度,与最小支持度进行比较,从而找到k维最大项目集。
下面以图例的方式说明该算法的运行过程:假设有一个数据库D,其中有4个事务记录,分别表示为:
TID | Items |
T1 | I1,I3,I4 |
T2 | I2,I3,I5 |
T3 | I1,I2,I3,I5 |
T4 | I2,I5 |
这里预定最小支持度minSupport=2,下面用图例说明算法运行的过程:
TID | Items |
T1 | I1,I3,I4 |
T2 | I2,I3,I5 |
T3 | I1,I2,I3,I5 |
T4 | I2,I5 |
扫描D,对每个候选项进行支持度计数得到表C1:
项集 | 支持度计数 |
{I1} | 2 |
{I2} | 3 |
{I3} | 3 |
{I4} | 1 |
{I5} | 3 |
比较候选项支持度计数与最小支持度minSupport,产生1维最大项目集L1:
项集 | 支持度计数 |
{I1} | 2 |
{I2} | 3 |
{I3} | 3 |
{I5} | 3 |
由L1产生候选项集C2:
项集 |
{I1,I2} |
{I1,I3} |
{I1,I5} |
{I2,I3} |
{I2,I5} |
{I3,I5} |
扫描D,对每个候选项集进行支持度计数:
项集 | 支持度计数 |
{I1,I2} | 1 |
{I1,I3} | 2 |
{I1,I5} | 1 |
{I2,I3} | 2 |
{I2,I5} | 3 |
{I3,I5} | 2 |
比较候选项支持度计数与最小支持度minSupport,产生2维最大项目集L2:
项集 | 支持度计数 |
{I1,I3} | 2 |
{I2,I3} | 2 |
{I2,I5} | 3 |
{I3,I5} | 2 |
由L2产生候选项集C3:
项集 |
{I2,I3,I5} |
比较候选项支持度计数与最小支持度minSupport,产生3维最大项目集L3:
项集 | 支持度计数 |
{I2,I3,I5} | 2 |
算法终止。
从算法的运行过程,我们可以看出该Apriori算法的优点:简单、易理解、数据要求低,然而我们也可以看到Apriori算法的缺点:(1)在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;(2)每次计算项集的支持度时,都对数据库D中的全部记录进行了一遍扫描比较,如果是一个大型的数据库的话,这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法,如下面要介绍的F-P算法。
F-P算法[编辑]
针对Apriori算法的性能瓶颈问题-需要产生大量候选项集和需要重复地扫描数据库,2000年Jiawei Han等人提出了基于FP树生成频繁项集的FP-growth算法。该算法只进行2次数据库扫描且它不使用侯选集,直接压缩数据库成一个频繁模式树,最后通过这棵树生成关联规则。研究表明它比Apriori算法大约快一个数量级。
FP-growth算法是一种不产生候选模式而采用频繁模式增长的方法挖掘频繁模式的算法。算法只需要扫描2次数据库:第一次扫描数据库,得到1维频繁项集;第二次扫描数据库,利用1维频繁项集过滤数据库中的非频繁项,同时生成FP树。由于FP树蕴涵了所有的频繁项集,其后的频繁项集的挖掘只需要在FP树上进行。FP树挖掘由两个阶段组成:第一阶段建立FP树,即将数据库中的事务构造成一棵FP树;第二阶段为挖掘FP树,即针对FP树挖掘频繁模式和关联规则。
FP-growth算法描述:
输入:事务数据库D,最小支持度minSupport。
输出:频繁模式的完全集。
方法:
1 构建FP树:
1.1 扫描事务数据库,收集频繁项集F并统计支持度,对F按支持度降序排序,得到频率排序好的项表L。
1.2 创建FP树的根节点,用“null”标记它。对于D中每个事务T,执行:选择T中的频繁项,并按L中的次序排序。设排序后的频繁项表为[p|P],其中p是第一个元素,而P是剩余元素的表。调用insert_tree([p|P],T)。该过程执行情况如下:如果T有子女N使得N.itemName=p.itemName,则N的计数增加1;否则创建一个新节点N,将其计数设置为1,链接到它的父节点T,并且通过节点链结构将其链接到具有相同itemName的节点。如果P非空,递归地调用insert_tree(P,N)。
2 FP树的规则挖掘(通过FP-growth(Tree,α)函数来实现,初始调用FP-growth(Tree,null)):
if Tree含单个路径P then {
for 路径P中节点的每个组合(记作β)
产生模式β∪α,其支持度support=β中节点的最小支持度; }
else for each αi 在Tree的头部 do {
产生模式β=αi ∪ α,其支持度support=αi.support;
构造β的条件模式基,然后构造β的条件FP树Treeβ;
if Treeβ≠空集 then
调用FP_growth(Treeβ,β) }
end
F-P算法实现[编辑]
Bash版本:请参考文章FP-growth算法实现
Eclat算法[编辑]
与fp-growth 和apriori算法不同,Eclat算法加入了倒排的思想,具体就是将事务数据中的项作为key,每个项对应的事务ID作为value。
原输入数据为
tid | item |
1 | A,B |
2 | B,C |
3 | A,C |
4 | A,B,C |
转换后为:
item | tids |
A | 1,3,4 |
B | 1,2,4 |
C | 2,3,4 |
通过转换后的倒排表可以加快频繁集生成速度。其算法思想是由频繁k项集求交集,生成候选k+1项集。对候选k+1项集做裁剪,生成频繁k+1项集,再求交集生成候选k+2项集。如此迭代,直到项集归一。根据上述数据的情况,具体计算过程为
算法过程:
1.计算频繁1项集,结果为:
item | freq |
A | 3 |
B | 3 |
C | 3 |
2.由频繁1项集生成频繁2项集
item | freq |
A,B | 2 |
A,C | 2 |
B,C | 2 |
3.由频繁2项集生成频繁3项集
item | freq |
A,B,C | 1 |
频繁k项集生成频繁k+1项集的过程与由1项集生成2项集的过程完全一致。
这里有个隐含的条件是,两个频繁k项集生成k+1项集时,前k-1项是一致的,A,B+A,C==>A,B,C
Apriori 算法 在R中的使用
我们采用最经典的购物篮数据(Groceries)
属性说明:transactions in sparse format with 9835 transactions (rows) and 169 items (columns)
CODE:
library(arules) #加载arules程序包
## Warning: package 'arules' was builtunder R version 3.1.1
## Loading required package: Matrix
## Warning: package 'Matrix' was builtunder R version 3.1.1
##
## Attaching package: 'arules'
##
## 下列对象被屏蔽了from 'package:base':
##
## %in%, write
data(Groceries) #调用数据文件
frequentsets=eclat(Groceries,parameter=list(support=0.05,maxlen=10)) #求频繁项集
##
## parameter specification:
## tidLists support minlenmaxlen target ext
## FALSE 0.05 1 10 frequent itemsets FALSE
##
## algorithmic control:
## sparse sort verbose
## 7 -2 TRUE
##
## eclat - find frequent item sets with the eclat algorithm
## version 2.6 (2004.08.16) (c) 2002-2004 Christian Borgelt
## create itemset ...
## set transactions ...[169 item(s), 9835 transaction(s)] done[0.00s].
## sorting and recoding items ... [28 item(s)] done [0.00s].
## creating sparse bit matrix ... [28 row(s), 9835 column(s)] done[0.00s].
## writing ... [31 set(s)] done[0.02s].
## Creating S4 object ... done[0.00s].
inspect(frequentsets[1:10]) #察看求得的频繁项集
## items support
## 1 {whole milk,
## yogurt} 0.05602
## 2 {whole milk,
## rolls/buns} 0.05663
## 3 {other vegetables,
## whole milk} 0.07483
## 4 {whole milk} 0.25552
## 5 {other vegetables} 0.19349
## 6 {rolls/buns} 0.18393
## 7 {yogurt} 0.13950
## 8 {soda} 0.17438
## 9 {root vegetables} 0.10900
## 10 {tropical fruit} 0.10493
inspect(sort(frequentsets,by="support")[1:10]) #根据支持度对求得的频繁项集排序并察看(等价于inspect(sort(frequentsets)[1:10])
## items support
## 1 {whole milk} 0.25552
## 2 {other vegetables} 0.19349
## 3 {rolls/buns} 0.18393
## 4 {soda} 0.17438
## 5 {yogurt} 0.13950
## 6 {bottled water} 0.11052
## 7 {root vegetables} 0.10900
## 8 {tropical fruit} 0.10493
## 9 {shopping bags} 0.09853
## 10 {sausage} 0.09395
rules=apriori(Groceries,parameter=list(support=0.01,confidence=0.01)) #求关联规则
##
## parameter specification:
## confidence minval smaxarem aval originalSupport support minlenmaxlen
## 0.01 0.1 1 none FALSE TRUE 0.01 1 10
## target ext
## rules FALSE
##
## algorithmic control:
## filter tree heap memopt loadsort verbose
## 0.1 TRUE TRUE FALSE TRUE 2 TRUE
##
## apriori - find association rules with the apriori algorithm
## version 4.21 (2004.05.09) (c) 1996-2004 Christian Borgelt
## set item appearances ...[0 item(s)] done [0.00s].
## set transactions ...[169 item(s), 9835 transaction(s)] done[0.00s].
## sorting and recoding items ... [88 item(s)] done [0.00s].
## creating transaction tree ... done [0.02s].
## checking subsets of size 1 2 3 4 done [0.01s].
## writing ... [610 rule(s)] done [0.00s].
## creating S4 object ... done[0.00s].
summary(rules) #察看求得的关联规则之摘要
## set of 610 rules
##
## rule length distribution (lhs + rhs):sizes
## 1 2 3
## 88 426 96
##
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 1.00 2.00 2.00 2.01 2.00 3.00
##
## summary of quality measures:
## support confidence lift
## Min. :0.0101 Min. :0.0103 Min. :0.79
## 1st Qu.:0.0116 1st Qu.:0.0889 1st Qu.:1.15
## Median :0.0146 Median :0.1590 Median :1.49
## Mean :0.0214 Mean :0.1910 Mean :1.56
## 3rd Qu.:0.0223 3rd Qu.:0.2618 3rd Qu.:1.83
## Max. :0.2555 Max. :0.5862 Max. :3.37
##
## mining info:
## data ntransactionssupport confidence
## Groceries 9835 0.01 0.01
x=subset(rules,subset=rhs%in%"whole milk"&lift>=1.2) #求所需要的关联规则子集
inspect(sort(x,by="support")[1:5]) #根据支持度对求得的关联规则子集排序并察看
## lhs rhs support confidence lift
## 1 {other vegetables} => {whole milk} 0.07483 0.3868 1.514
## 2 {rolls/buns} =>{whole milk} 0.05663 0.3079 1.205
## 3 {yogurt} =>{whole milk} 0.05602 0.4016 1.572
## 4 {root vegetables} =>{whole milk} 0.04891 0.4487 1.756
## 5 {tropical fruit} =>{whole milk} 0.04230 0.4031 1.578
Eclat()函数:
function (data, parameter = NULL, control =NULL)
{
data <- as(data, "transactions")
items <- data@data
parameter <- as(parameter, "ECparameter")
control <- as(control, "ECcontrol")
if (control@verbose) {
cat("\nparameter specification:\n")
print(parameter)
cat("\nalgorithmic control:\n")
print(control)
cat("\n")
}
abs_supp <- as.integer(parameter@support * length(data))
if (abs_supp < 2)
课后习题
1912年4月15日,载着1316号乘客和891名船员的豪华巨轮“泰坦尼克号”与冰山相撞而沉没,这场海难被认为是20世纪人间十大灾难之一。有人丧生,有人生还,请以此数据为例进行人员生还与丧生的关联分析。(此数据为R内置数据集Titanic)
解答:
Answer1:
使用数据:Titanic
# look for data
str(Titanic)
# transform table into data frame
df <- as.data.frame(Titanic)
head(df)
> head(df)
Class Sex AgeSurvivedFreq
1 1st MaleChild No 0
2 2nd MaleChild No 0
3 3rd MaleChild No 35
4 Crew MaleChild No 0
titanic.raw <- NULL
# 如果频率字段大于0,将该行记录按列追加到变量中,Freq=0,当然就不追加
for(iin1:4) {
titanic.raw <- cbind(titanic.raw, rep(as.character(df[,i]),
df$Freq))
}
# 前35行都是一样的
]]]]> titanic.raw[1:36,]
[,1] [,2] [,3] [,4]
[1,]"3rd""Male" "Child""No"
[2,]"3rd""Male" "Child""No"
[3,]"3rd""Male" "Child""No"
[4,]"3rd""Male" "Child""No"
...
[35,]"3rd""Male" "Child""No"
[36,]"3rd""Female""Child""No"
# transform to data frame
titanic.raw <- as.data.frame(titanic.raw)
> head(titanic.raw)
V1 V2 V3V4
1 3rd MaleChildNo
2 3rd MaleChildNo
3 3rd MaleChildNo
4 3rd MaleChildNo
5 3rd MaleChildNo
6 3rd MaleChildNo
# 生成数据框后添加属性名称
names(titanic.raw) <- names(df)[1:4];dim(titanic.raw);
summary(titanic.raw)
# 转换后:每一行代表了一个人,可以用于关联规则。转换前是什么类型的数据? (按照class、sex、年龄汇总的生存人数的数据)
With the function, the default settings are:1) supp=0.1, which is the minimum support ofrules;2) conf=0.8, which is the minimum confidence ofrules; and 3) maxlen=10, which is the maximum length ofrules.
library(arules)
rules <- apriori(titanic.raw) # apriori可以直接传递非transactions类型的对象,内部自动转换
rules # 根据最小的 (supp=0.1,conf=0.8),返回的规则的最多个数 10个
summary(rules);
inspect(rules);
quality(rules) <- quality(rules)
inspect(rules)
翻译:
关联规则挖掘一个常见的现象是,很多产生的规则并不是有趣的。考虑到我们只关心规则的右件(rhs)表示是否生存,
所以我们参数 appearance 中设置 rhs=c("Survived=No","Survived=Yes") 并确定只有这两种情况出现在规则右件中(rhs).
其它的项集可以出现在规则左件(lhs),使用default="lhs"设置。
上面的结果也可以看到,第一个规则的lhs 是个空集,为了排除这样的规则,可以使用minlen=2。
而且,算法处理的过程被压缩(简化)是通过verbose=F设置的。
关联规则挖掘结束后,规则将会以lift提升度按照从大到小的排序方式进行排序
rules.better <- apriori(titanic.raw,
parameter
=list(minlen
= 2,
supp =0.005,
conf =0.8),
appearance
= list(rhs
=c("Survived=No",
"Survived=Yes"), default
="lhs"),
control
= list(verbose=F)
)
# base on lift sorted
rules.sorted <- sort(rules.better, by="lift")
inspect(rules.sorted)
> inspect(rules.sorted)
lhs rhs supportconfidence lift
1 {Class=2nd,
Age=Child} => {Survived=Yes} 0.010904134 1.00000003.095640
2 {Class=2nd,
Sex=Female,
Age=Child} => {Survived=Yes} 0.005906406 1.00000003.095640
3 {Class=1st,
Sex=Female} => {Survived=Yes} 0.064061790 0.97241383.010243
4 {Class=1st,
Sex=Female,
Age=Adult} => {Survived=Yes} 0.063607451 0.97222223.009650
5 {Class=2nd,
Sex=Female} => {Survived=Yes} 0.042253521 0.87735852.715986
6 {Class=Crew,
Sex=Female} => {Survived=Yes} 0.009086779 0.86956522.691861
7 {Class=Crew,
Sex=Female,
Age=Adult} => {Survived=Yes} 0.009086779 0.86956522.691861
8 {Class=2nd,
Sex=Female,
Age=Adult} => {Survived=Yes} 0.036347115 0.86021512.662916
9 {Class=2nd,
Sex=Male,
Age=Adult} => {Survived=No} 0.069968196 0.91666671.354083
10 {Class=2nd,
Sex=Male} => {Survived=No} 0.069968196 0.86033521.270871
11 {Class=3rd,
Sex=Male,
Age=Adult} => {Survived=No} 0.175829169 0.83766231.237379
12 {Class=3rd,
Sex=Male} => {Survived=No} 0.191731031 0.82745101.222295
翻译:
当其它设置不发生变化的情况下,越小的支持度会产生更多的规则。这种产生的规则中项集之间的关联看起来更像是随机的。
在上例中,最小支持度为0.005,那么每一个规则至少有 支持度*交易数(记录数) 个案例 是满足支持度为0.005的。(2201 * 0.005 = 12)
支持度,置信度,提升度是选择兴趣规则的三个方法。还有一切其它的衡量方法,包括卡方,gini等。有多余20中这样的计算方法在interestMeasure()方法中
### 规则的剪枝
从上面的例子中,我们能够发现一些规则与其它规则相比没有提供额外的信息。(提供的信息少)。
比如第二个规则给出的信息,在第一个规则中已经都阐述明白了。因为规则1告诉我们 所有的 2nd-class的孩子都幸存了。
(即 Class=2nd,Age=Child 所有的都幸存了,置信度和lift都是一致的,再增加一个sex的判断是冗余的)
我们以这个例子来阐述何种情况定义为redundant(冗余)
总体来说,规则2 是 规则1 的衍生规则,如果规则2 和 规则1 有相同的 提升度或者 比 规则1 更低的提升度,那么规则2 就被认为是冗余的。
总结 :规则2 比 规则1 lhs多了sex的条件,同时lift ,两者相同,所以规则2冗余
lhs rhs support confidence lift
1 {Class=2nd,
Age=Child} =>{Survived=Yes}0.010904134 1.0000000 3.095640
2 {Class=2nd,
Sex=Female,
Age=Child} =>{Survived=Yes}0.005906406 1.0000000 3.095640
代码:
函数解释:
is.subset(r1, r2): 检查r1是否为r2的子集
lower.tri():返回一个逻辑以TRUE为下三角的matrix;diag=T表示包含主对角线
# redundant
subset.matrix <- is.subset(rules.sorted, rules.sorted) #
# 使得下三角包含主对角线设置为NA
subset.matrix[lower.tri(subset.matrix, diag=T)] <- NA
# 计算列TRUE的数量
redundant <- colSums(subset.matrix, na.rm=T) >= 1; #
which(redundant) # 冗余规则的下标
# 删除冗余规则
rules.pruned <- rules.sorted[!redundant]
inspect(rules.pruned)
> inspect(rules.pruned)
lhs rhs support confidence lift
1 {Class=2nd,
Age=Child} => {Survived=Yes} 0.010904134 1.0000000 3.095640
2 {Class=1st,
Sex=Female} => {Survived=Yes} 0.064061790 0.9724138 3.010243
3 {Class=2nd,
Sex=Female} => {Survived=Yes} 0.042253521 0.8773585 2.715986
4 {Class=Crew,
Sex=Female} => {Survived=Yes} 0.009086779 0.8695652 2.691861
5 {Class=2nd,
Sex=Male,
Age=Adult} => {Survived=No} 0.069968196 0.9166667 1.354083
6 {Class=2nd,
Sex=Male} => {Survived=No} 0.069968196 0.8603352 1.270871
7 {Class=3rd,
Sex=Male,
Age=Adult} => {Survived=No} 0.175829169 0.8376623 1.237379
8 {Class=3rd,
Sex=Male} => {Survived=No} 0.191731031 0.8274510 1.222295
规则的解释:(解释规则)
很容易就能找到高提升度的数据,但是理解识别出来的规则并不是一件容易的事情。
关联规则在寻找商业意义上被误解读是很常见的。
比如,第一个规则,{Class=2nd,Age=Child} => {Survived=Yes}
规则的置信度为1,提升度为3,并且没有规则揭示age=Child时,class=c("1nd","3nd").
因此,这样可能就会被分析师解释为:类别为2的孩子比其它类别的孩子(1,3)有更高的生存几率。
这种解释是完全的错误的!!!!
这个规则仅表示所有类别为2的孩子幸存下来了,但是没有提供任何信息来进行比较不同的类别的孩子的生存率
为了研究以上的问题,我们可以通过找到规则右件为存活的,即rhs为 Survived=Yes,
规则左件lhs 仅仅包括 Class=1st,2nd,3rd, Age=Child,Adult;不包括其它项集(如default="none")
我们对支持度和置信度使用较之前拟合模型这两个参数较低的阈值,去找出所有孩子不同类别的规则。
为了方便,先将原来计算的规则写出来,好做比较
# former rules set
rules.better <- apriori(titanic.raw,
parameter
=list(minlen
= 2,
supp =0.005,
conf =0.8),
appearance
= list(rhs
=c("Survived=No",
"Survived=Yes"), default
="lhs"),
control
= list(verbose=F)
)
# compare rules set
rules <- apriori(titanic.raw,
parameter
=list(minlen=3,supp=0.002,
conf=0.2),
appearance
= list(rhs=c("Survived=Yes"),
lhs=c("Class=1st",
"Class=2nd", "Class=3rd",
"Age=Child",
"Age=Adult"),
default="none"),
control
= list(verbose
= F)
);
rules.sorted <- sort(rules, by = "confidence")
inspect(rules.sorted)
lhs rhs support confidence lift
1{Class=2nd,
Age=Child}=>{Survived=Yes}0.010904134 1.0000000 3.0956399
2{Class=1st,
Age=Child}=>{Survived=Yes}0.002726034 1.0000000 3.0956399
3{Class=1st,
Age=Adult}=>{Survived=Yes}0.089504771 0.6175549 1.9117275
4{Class=2nd,
Age=Adult}=>{Survived=Yes}0.042707860 0.3601533 1.1149048
5{Class=3rd,
Age=Child}=>{Survived=Yes}0.012267151 0.3417722 1.0580035
6{Class=3rd,
Age=Adult}=>{Survived=Yes}0.068605179 0.2408293 0.7455209
根据结果,前两个规则中,1类和2类的孩子有相同的幸存率并且都幸存了下来(置信度为1)。
那么1类的孩子的规则没有出现在之前的规则列表中,是因为支持度阈值低于设定的阈值(0.005),1类此时supp为0.002.
规则5与规则4相比,3类的孩子存活率只有很低的34%,(此处只是比较的conf,无法按照class和age比较),
而和规则3(1类的成年人)比较,存活率(置信度)就更低了
Answer2:
关联算法现象的应用我们可能听的比较多。像沃尔玛的尿布和啤酒的故事。
其最核心的概念是可信度和支持度,另外还有一个可靠度(lift),这里不再详述。
· 首先我们准备这样一个数据集。
如下
> str(Titanic) |
· 关联规则挖掘
一个经典的关联算法即是APRIORI。它是一个面向层级的,广度优先算法,通过找到对交易进行计次来找到频繁项集而后推演出关联规则。arule中的apriori()即是其实现。
另外还有一个算法是ECLAT算法。它是深度优先的,并且不是通过计数,而是集合的交集来实现,arule中的eclat()实现了该算法。
下面我们来通过apriori()来显示关联规则。该函数默认的设置是:1)supp=0.1 2)conf=0.8 3)maxlen=10
> library(arules) |
通过上面得到的规则有很多是没有意义或者不感兴趣的。假如我们只对右边rhs是survival特征感兴趣,那么通过在appearance中设置rhs=c("Survived=No", "Survived=Yes")即可,另外default="lhs",其他所有的项将会出现在左边lhs。
上面的得到的规则集中第一个规则的lhs是空,这种情况可以通过设置minlen=2来排除。最后通过lift将高可靠度的规则置前。
> rules <- apriori(titanic.raw, control = list(verbose=F), |
· 消除冗余
上面产生的规则中,rule2是rule1的子集,没有提供更多的知识,这种情况下rule2可考虑消除。
> subset.matrix <- is.subset(rules.sorted, rules.sorted) |
· 解释规则
找到规则很容易,但得要看你怎么去理解这些规则了。比如像上面的第一个规则{Class=2nd, Age=Child} => {Survived=Yes},具有高可信度1和可靠度3,而并没有class 1st 和3rd 孩子的幸存记录,这种情况是否说明了class 2nd比其他有更高的存活率呢?不是,因为根本就没有提供相关的数据用于比较。为了这个话题,我们将lhs设置为仅包含"Class=1st", "Class=2nd","Class=3rd", "Age=Child"和"Age=Adult",rhs是"Survived=Yes"。为了获取更多的记录,我们降低支持度和可信度参数。
> rules <- apriori(titanic.raw, |
可见,头等舱和二等舱的儿童具有相同的幸存率。而三等舱的幸存率明显较低。
· 关联规则的可视化
> library(arulesViz) |