用R语言进行关联分析

用R语言进行关联分析

关联是两个或多个变量取值之间存在的一类重要的可被败枣发现的某种规律性。关联分析目的是寻找给定数据记录集中数据项之间隐藏的关联关系，描述数据之间的密切度。

几个基本概念

1. 项集

这是一个集合的概念，在一篮子商品中仿轮的一件消费品即为一项（Item），则若干项的集合为项集，如{啤酒，尿布}构成一个二元项集。

2. 关联规则

一般记为的形式，X为先决条件，Y为相应的关联结果，用于表示数据内隐含的关联性。如：，表示购买了尿布的消费者往往也会购买啤酒。

关联性强度如何，由三个概念——支持度、置信度、提升度来控制和评价。

例：有10000个消费者购买了商品，其中购买尿布1000个，购买啤酒2000个，购买面包500个，同时购买尿布和面包800个，同时购买尿布和面包100个。

3. 支持度（Support）

支持度是指在所有项集中{X, Y}出现的可能性，即项集中同时含有X和Y的概率：

该指标作为建立强关联规则的第一个门槛，衡量了所考察关联规则在“量”上的多少。通过设定最小阈值（minsup），剔除“出镜率”较低的无意义规则，保留出现较为频繁备枯信的项集所隐含的规则。

设定最小阈值为5%，由于{尿布，啤酒}的支持度为800/10000=8%，满足基本输了要求，成为频繁项集，保留规则；而{尿布，面包}的支持度为100/10000=1%，被剔除。

4. 置信度（Confidence）

置信度表示在先决条件X发生的条件下，关联结果Y发生的概率：

这是生成强关联规则的第二个门槛，衡量了所考察的关联规则在“质”上的可靠性。相似的，我们需要对置信度设定最小阈值（mincon）来实现进一步筛选。

具体的，当设定置信度的最小阈值为70%时，置信度为800/1000=80%，而的置信度为800/2000=40%，被剔除。

5. 提升度（lift）

提升度表示在含有X的条件下同时含有Y的可能性与没有X这个条件下项集中含有Y的可能性之比：

该指标与置信度同样衡量规则的可靠性，可以看作是置信度的一种互补指标。

R中Apriori算法

算法步骤：

1. 选出满足支持度最小阈值的所有项集，即频繁项集；

2. 从频繁项集中找出满足最小置信度的所有规则。

>library(arules) #加载arules包

>click_detail =read.transactions("click_detail.txt",format="basket",sep=",",cols=c(1)) #读取txt文档（文档编码为ANSI）

>rules <- apriori(click_detail, parameter =list(supp=0.01,conf=0.5,target="rules")) #调用apriori算法

>rules

set of419 rules

>inspect(rules[1:10]) #查看前十条规则

解释

1)library(arules)：加载程序包arules，当然如果你前面没有下载过这个包，就要先install.packages(arules)

2)click_detail =read.transactions("click_detail.txt",format="basket",sep=",",cols=c(1))：读入数据

read.transactions(file, format =c("basket", "single"), sep = NULL,

cols = NULL, rm.duplicates =FALSE, encoding = "unknown")

file:文件名，对应click_detail中的“click_detail.txt”

format:文件格式，可以有两种，分别为“basket”,“single”，click_detail.txt中用的是basket。

basket: basket就是篮子，一个顾客买的东西都放到同一个篮子，所有顾客的transactions就是一个个篮子的组合结果。如下形式，每条交易都是独立的。

文件形式：

item1,item2

item1

item2,item3

读入后：

items

1 {item1,

item2}

2 {item1}

3 {item2,

item3}

single: single的意思，顾名思义，就是单独的交易，简单说，交易记录为：顾客1买了产品1， 顾客1买了产品2，顾客2买了产品3……(产品1，产品2，产品3中可以是单个产品，也可以是多个产品)，如下形式：

trans1 item1

trans2 item1

trans2 item2

读入后：

items transactionID

1 {item1}trans1

2 {item1,

item2}trans2

sep:文件中数据是怎么被分隔的，默认为空格，click_detail里面用逗号分隔

cols:对basket, col=1,表示第一列是数据的transaction ids(交易号)，如果col=NULL，则表示数据里面没有交易号这一列；对single，col=c(1,2)表示第一列是transaction ids，第二列是item ids

rm.duplicates:是否移除重复项，默认为FALSE

encoding:写到这里研究了encoding是什么意思，发现前面txt可以不是”ANSI”类型，如果TXT是“UTF-8”，写encoding=”UTF-8”，就OK了.

3)rules <- apriori(click_detail,parameter = list(supp=0.01,conf=0.5,target="rules"))：apriori函数

apriori(data, parameter = NULL, appearance = NULL, control = NULL)

data:数据

parameter：设置参数，默认情况下parameter=list(supp=0.1,conf=0.8,maxlen=10,minlen=1,target=”rules”)

supp:支持度（support）

conf:置信度（confidence）

maxlen,minlen:每个项集所含项数的最大最小值

target:“rules”或“frequent itemsets”（输出关联规则/频繁项集）

apperence:对先决条件X（lhs），关联结果Y（rhs）中具体包含哪些项进行限制，如：设置lhs=beer，将仅输出lhs含有beer这一项的关联规则。默认情况下，所有项都将无限制出现。

control：控制函数性能，如可以设定对项集进行升序sort=1或降序sort=-1排序，是否向使用者报告进程（verbose=F/T）

补充

通过支持度控制：rules.sorted_sup = sort(rules, by=”support”)

通过置信度控制：rules.sorted_con = sort(rules, by=”confidence”)

通过提升度控制：rules.sorted_lift = sort(rules, by=”lift”)

Apriori算法

两步法：

1. 频繁项集的产生：找出所有满足最小支持度阈值的项集，称为频繁项集；

2. 规则的产生：对于每一个频繁项集l，找出其中所有的非空子集；然后，对于每一个这样的子集a，如果support(l)与support(a)的比值大于最小可信度，则存在规则a==>(l-a)。

频繁项集产生所需要的计算开销远大于规则产生所需的计算开销

频繁项集的产生

几个概念：

1， 一个包含K个项的数据集，可能产生2^k个候选集

2，先验原理：如果一个项集是频繁的，则它的所有子集也是频繁的（理解了频繁项集的意义，这句话很容易理解的）；相反，如果一个项集是非频繁的，则它所有子集也一定是非频繁的。

3基于支持度（SUPPORT）度量的一个关键性质：一个项集的支持度不会超过它的子集的支持度（很好理解，支持度是共同发生的概率，假设项集{A,B,C}，{A,B}是它的一个自己，A,B,C同时发生的概率肯定不会超过A,B同时发生的概率）。

上面这条规则就是Apriori中使用到的，如下图，当寻找频繁项集时，从上往下扫描，当遇到一个项集是非频繁项集（该项集支持度小于Minsup），那么它下面的项集肯定就是非频繁项集，这一部分就剪枝掉了。

一个例子（百度到的一个PPT上的）：

当我在理解频繁项集的意义时，在R上简单的复现了这个例子，这里采用了eclat算法，跟apriori应该差不多：

代码：

item <- list(

c("bread","milk"),

c("bread","diaper","beer","eggs"),

c("milk","diaper","beer","coke"),

c("bread","milk","diaper","beer"),

c("bread","milk","diaper","coke")

)

names(item) <- paste("tr",c(1:5),sep = "")

item

trans <- as(item,"transactions") #将List转为transactions型

rules = eclat(trans,parameter = list(supp = 0.6,

target ="frequent itemsets"),control = list(sort=1))

inspect(rules) #查看频繁项集

运行后结果：

>inspect(rules)

items support

1{beer,

diaper}0.6

2{diaper,

milk} 0.6

3{bread,

diaper}0.6

4{bread,

milk} 0.6

5{beer} 0.6

6{milk} 0.8

7{bread} 0.8

8{diaper} 0.8

以上就是该例子的所有频繁项集，然后我发现少了{bread,milk,diaper}这个项集，回到例子一看，这个项集实际上只出现了两次，所以是没有这个项集的。

规则的产生

每个频繁k项集能产生最多2k-2个关联规则

将项集Y划分成两个非空的子集X和Y-X，使得X ->Y-X满足置信度阈值

定理：如果规则X->Y-X不满足置信度阈值，则X’->Y-X’的规则一定也不满足置信度阈值，其中X’是X的子集

Apriori按下图进行逐层计算，当发现一个不满足置信度的项集后，该项集所有子集的规则都可以剪枝掉了。

关联分析，顾名思义就是找出哪几项之间是有关联关系的，举个例子：

以上是五个购物记录，从中我们可以发现，购买了尿布的人其中有3个购买了啤酒，那么久我们可以推测，尿布和啤酒之间有较强的关联关系，尽管他们之间看起来并没有什么联余橘宏系，也就是能得到规则：

因为购物分析能较好地描述关联分析，所以又被叫做 购物篮分析 。

为了较好的描述这个分析的各种名词，我们把上面的表格重新设计一下：

把每一个购物订单中，涉及到的商品都变成1，没涉及到的变成0，也就是将各个商品的购买记录 二元化 。

当然肯定也有多个分类的情况。

那么面包，牛奶这些就叫数据集的 项 ，而他们组合起来的子集就叫做 项集 。可以为空，空集是不包含任何项的项集，如果一个项集包含k个子项，就叫做k-项集。

订单12345叫做 事务 ，某个项集在所有事务中出现多少次，叫做项集的 支持度计数 。

在上面的表格中，项集{啤酒、尿布、牛奶}的支持度计数为2，因为有两个事务（3、4）包含这一项集。

用 支持度 和 置信度 来衡量，假定存在规则 ，其中X和Y是 不相交 的项集，则支持度为：

其中N是数据集中的事务个数，相当于表示该规则在数据集中出现了多少次。

置信度为：

置信度的意思就是，在出现X的情况下，有多少次同时出现了Y，代表这个关联规则的频繁程度。

注意置信度的分母是 ，因此这个评价可能会存在一定的问题。

关联分析的核心目标就是找出支持度大于等于某个阈值， 同时 置信度大于等于某个阈值的所有规则，这两个阈值记为 和 。

为了更有效率的完成这个过程，通常把关联规则算法分为两步：

可以看出来，首先要求得频繁项集，这步骤的开销很大，但是只需要考虑支持度就可以了，第二步只考虑置信度就可以了。

下面就可以分两步来解析算法：

首先我们可以把项集联想成一个树形结构，每层代表着不同的k-项集，依层递增，非叶子节点来自于他的几个父节点的并集，如图：

我们肯定不能通过传统的方式，遍竖册历这些节点，算出支持度，然后筛选掉不满足最小支持度的那些，这样开销太大，因此我们引入先验原理，来辅助剪枝。

这个原伍指理不难想象，假如一个项集{a,b}是非频繁项集，那么{a,b,c}肯定也是，因为ab是，在{a,b,c}中与之关联的c必须在ab出现之后才存在，因此他的支持度肯定不会大于{a,b}。

频繁的就是支持度大于等于最小支持度的项集，非频繁就是小于的。

我们可以利用这一定理，把非频繁项集的超集一并从树中减去，这样就能大大的降低计算次数，如图：

虚线圈上的，就是在{a,b}确定是非频繁项集之后，剪掉的超集，这些是不用计算的。

根据这个原理，可以说一下Apriori算法。

根据上面说的先验原理，Apriori算法先从项集宽度最低的1开始，遍历所有的项集支持度，找出频繁项集（因为第一层在找出支持度之前），之后根据先验原理，挑选任意两个频繁项集组成2-频繁项集（很简单，如果挑非频繁的，那组成的项集就不是频繁项集了），再用2-项集挑选3-项集，直到挑选不出更高层次的项集为止，把这些项集作为 候选项集 ，如图：

图中1-项集中，啤酒，面包，尿布，牛奶的支持度大于等于3（设 为3），则由他们组成2-项集，继续筛选满足支持度不小于3的项集，再由2-项集生成3-项集，这就是 Apriori 算法筛选频繁项集的基本步骤。总结如下：

上面提到了用k-1项集生成k-项集，那么如何才能最有效率的产生k-项集呢，这里用了 的方法，也就是找到一对（k-1）-项集，当他们的前（k-2）项都相同时，进行合并，合并之后的结果就是{ }，因为前k-2项是相同的。

举个例子：

上面说了如何产生候选项集，接下来就是如何更有效率的确定支持度计数了，同样，如果遍历一个一个查的话效率是很低的，我们可以用枚举的方法遍历每个事务包含的项集，以查找3-项集为例，如图：

因为我们要查3-项集，因此树状结构就分到3-项集为止。

因为3-项集的开头第一个项肯定在1，2，3之间，我们就设定这三个数为三个分支，无论到哪个节点，都严格按照这个来分（1在左，2在中，3在右），在下面的层次中如何碰到比123更大的，则再向右分，就可以得到图中的关于事务t的所有3-项集。

有了所有项集的列表，我们可以用候选项集去匹配这些项集，从而看t中是否包含候选项集，如果包含，则支持度+1。

可以使用Hash树来进行匹配，从而实现支持度计数。

如下图，就是一个Hash树的例子，每个内部节点都使用Hash函数 来确定应当沿着当前节点的哪个分支向下，所以1，4，7就到了同一分支。

我们对于单个事务，可以遍历Hash树，设事务为t，则保证所有包含属于事务t的候选3-项集的叶节点至少访问一次。

由于我们之前已经通过树的方式枚举出了t中所有的3-项集，那么我们跟这个Hash一走分支，找到对应3-项集的就+1支持度，即可算出每个候选项集的支持度。

提取规则相应的比较简单，设有 频繁项集Y ，我们忽略前件为空和后件为空的规则，每个频繁项集能产生 个关联规则，提取方法就是将Y划分为两个 非空 的子集X和Y-X，使得 满足 置信度阈值 也就是最小置信度。

同样的，提取规则也有一个原理：

参考频繁项集的寻找过程，我们可以利用树形结构对规则进行剪枝。

树的每层对应规则后件中的项数，如图：

假设规则{ } { }不满足置信度阈值的要求，那么可以丢弃后件包含{a}的所有规则，如上图所示。

至此我们经历了寻找频繁项集和提取规则的过程，基本Apriori算法就算完成了，不过还有一些需要考虑的细节。

在实际应用过程中，往往频繁项集产生的数量可能很大，所以很难表示，我们需要寻找一种方法，找到一些有代表性的频繁项集，以保证其描述性。

通常有如下两种方法：

如图：

这种表示很明显降低了需要表示项集的个数，我们需要别的候选项集，直接取极大频繁项集的子集就行，任意一个肯定都是。

但是这么做，表示不出他们子集的支持度，所以就需要再遍历数据集，确定非极大频繁项集的支持度，不是很方便。

所以我们还可以用闭频繁项集来表示。

先来看闭项集的概念：

那么闭频繁项集的概念就很好理解了：

如图，我们假设 是40%。

这种做法可以保证支持度和描述性。

之前举的例子都是二元分类的，要么1要么0，下面看多分类的，我们很容易想到可以用独热编码解决这个问题，把所有分类二元化，但是这样就存在一个问题，有的属性值可能会不够频繁，没办法成为频繁项集。

所以最好是把多分类的项根据实际情况进行分类化，不要针对每个属性都设置独热编码。

或者将不太频繁的属性值合并为一个称作其他的类别。

所以面对多分类属性，我们要做的就是：

独热编码二元化-针对这些值进行一定的合并，或者分类或者并为其他 - 删除冗余的项 - 避免包含多个来自同一属性的项的候选集（例如{ }，被写到了一个候选集中，但是实际上这种情况不可能发生，由于独热编码进行的二元化而产生了这种情况，需要避免。）

我们也会遇到一些连续属性，可以通过以下几种方式处理：

这种做法有一个问题就是分类的效果取决于区间的个数和跨度，如果取不好很难得到理想的结果。

如果要验证统计出的值是否具有统计意义，可以参考假设检验中针对不同比较的不同公式，这里不再举例。

把mini-Apriori算法中的支持度代入到Apriori算法的支持度中即可。

举个例子：

想要衡量模型的好与坏，肯定要有一个评估指标，我们可以根据业务实际去评价，这是主管评价，叫做 主观兴趣度度量 ，这个显然要结合业务，所以我们要看看一些客观指标。

指标的评价往往依赖于相依表，这个相依表有点类似于混淆矩阵：

其中A，B代表在事务中出现，!A,!B代表没有在事务中出现，空列空行例如 代表A的支持度计数， 表示包含B但是不包含A的事务的个数。

最基本的就是置信度和支持度了，但是这两种指标都很难做到客观评价模型，会受到多种因素的影响。

我们可以用 兴趣因子 来衡量模型：

首先我们引入 提升度 的概念，它用于计算规则置信度和 规则后件 中项集的支持度之间的比率，

对于二元变量，提升度等价于另一种称作兴趣因子的客观度量，定义为：

其中N是事务个数。

如果

但是兴趣因子有一定局限性，看上图，{p,q}和{r,s}的兴趣因子分别为1.02和4.08，虽然p和q同时出现在88%的文档中，但是他们的兴趣因子接近于1，表明他们相互独立，另一方面，{r,s}的兴趣因子闭{p,q}的高，但是r和s很少出现在一个文档中，这种情况下，置信度要比兴趣因子更可信，置信度表明p和q之间的联系94.6%远高于r和s之间。

另外还可以引入 相关系数 ，逻辑类似于向量的相关系数：

相关度的值从-1到1，如果变量相互独立，则Φ=0。

他的局限性在于在食物中把同时出现和同时不出现视为同等重要，这往往不符合实际规律，同时对于倾斜的变量很难度量。

IS度量 可以用于处理非对称二元变量，定义如下：

IS数学上等价于二元变量的余弦度量。

但是IS取决于A和B的支持度，所以存在与置信度度量类似的问题——即使是不相关或者负相关的模式，度量值也可能相当大。

支持度，全置信度，可以应用于较大的项集，兴趣因子，IS、PS、Jaccard系数等使用多维相依表中的频率，可以扩展到多个变量。

针对大多数项具有较低或中等的频率，但是少数项具有很高频率的数据集。

交叉支持模式是一个项集 ，他的支持度比率是：

小于用户指定的阈值 。

需要保证全置信度小于上面的支持度比率，而全置信度是：

其中 .

全置信度能够确保项集中的项之间是强关联的，例如，假定一个项集X的全置信度是80%，如果X中的一个项出现在某个事物中，则X中其他的项至少也有80%的几率属于同一个事务，这种强关联模式又称 超团模式 。

关联, 指的是关联分析, 这里引用百度百科的定义.

通过关联分析, 可以挖掘出"由于某些事件的发生而引起另外一些事件的发生"之类的规则, 比如说"面包=>牛奶", 其中面包被称为规则的前项, 而牛奶则被称为规则的后项.

常用于关联分析的算法有Apriori算法, FP-growth算法, Eclat算法, 灰色关联法等, 下面将着重介绍Apriori算法.

在介绍Apriori算法之前, 我们先来了解几个概念:

1.事务: 一条交易记录称为一个事务

2.项: 交易中的每一个物品称为一个项

3.项集: 包含0个或多个项的集合

4.支持度计数: 项集在所有事务中出现的次数.

5.支持度: 支持度计数除于总的事务数.

6.频繁项集: 支持度大于等于某个阀值的项集.

关联规则的挖掘通常分为两步: 第一步, 找出所有的频繁项集第二步, 由频繁项集产没判答生强关联规则. 而Apriori算法则是挖掘频繁项集的基本算法.

可以看到以上每个过程均需要扫描一次数据, 为了提高频繁项集逐层迭代产生的效率, 需要利用一条重要性质, 其称为先验性质:

当然, 非频繁项集的所有超集也一定是非频繁的.

将先验性质应用到Apriori算法中就是将之枯慧前的过程分为两大部分, 连接步和剪枝步.

连接步: 连接步的目的是产生候选项集.

剪枝步: 应用先验性质对候选项集进行筛选, 将不满足先验性质的候选项集剔除, 再进而根据最小支持度找出频繁项集, 这样可以有效缩短计算量.

关联分析的目标是找出强关联规则, 因此这里的关联规则是指强关联规则, 我们把满足最小支持度和最小置信度的规则称为强关联规则.

对于规则A=>冲敏B, 置信度的计算公式就是项集{A, B}的支持度计数除于项集{A}的支持度计数.

优点: 简单, 易理解, 对数据要求低

缺点: 容易产生过多的候选项集, I/O负载大.

---