数据科学之机器学习14: 关联分析之apriori算法

“文章原创，转载请注明出处”

---

在上一篇中，我们介绍了关联分析相关的概念，这一节来看看如何使用Apriori算法去寻找满足条件的项集。

首先回顾一个概念，一个项集的支持度就是数据集中该项集所占的比例。Apriori算法就是用于寻找数据集中，支持度和可信度超过某一给定值的项集和关联规则。

---

一、原理

---

在介绍算法之前，首先了解一个集合论中的性质定理：集合的向下封闭性。

我们通过一个例子来看看这个定理，见下图：

集合的向下封闭性，在这边解释的话，也就是说，如果一个项集的支持度低于某一个值，那么该项集超集的支持度也必定低于这个值。如果一个项集的支持度高于某一个值，那么该项集子集的支持度也必定高于某一个值。

超集：就是指包含这个集合中所以元素的集合（不包括自身），比如集合ABC就是集合AB的超集。

那么这个定理放在上一个图当中，就有这样的含义：

---

二、算法构成

---

有了上面这个原理，那么就可以利用这个原理去减少我们寻找频繁集的计算量。因为，只要我们找到一个项集，其支持度低于给定的值，那么这个项集的所有超集就可以直接忽略不计了。如上图，项集A的支持度低于指定的值，那么其超集就都不用再考虑了。

Apriori算法由两部分构成：

1. 找到满足最小支持度的项集；
2. 找到可信度超过最小可信度的关联规则。

下面，我们一个一个地解决：

---

2.1. 寻找频繁项集

---

利用上面所讲的原理，我们来整理一下这个步骤的流程：

1. 从数据集中构造集合C1，C1满足：大小为1的所有候选项集的集合，例如上图中的：C1 = {A, B, C};
2. 计算C1中所有项集（单元素项集）是否满足最小支持度，满足的项集构成集合L1，例如上图中的：L1 = {B, C};
3. 利用L1生成新的候选项集C2，C2满足：大小为2的所有候选项集的集合，例如上图中得：C2 = {BC};
4. 计算C2中所有项集（双元素项集）是否满足最小支持度，满足的项集构成集合L2；
5. 重复直到Lk中得元素个数为1。

---

2.2. 寻找关联规则

---

在得到频繁项集之后，要寻找关联规则就容易多了。可以直接从频繁项集中构造初始的关联规则，计算该关联规则的可信度，然后与给定的最小可信度作比较，若值大于最小可信度，则记录该关联规则。

在实际编程时，需要注意使用集合的向下封闭性！！！想想看，在关联规则中，这个性质应该怎样去实现？(可以到Machine Learning in Action中找答案！)

三、R语言实现

1. 使用自带的程序

在R语言的arules这个包里面，提供了一个实现Apriori算法的函数：apriori()：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

# 构造数据集 dataSet <- matrix(0, 5, 3) rownames(dataSet) <- paste("item", 1:5, sep='') colnames(dataSet) <- c("A", "B", "C") dataSet[1,] <- c(1, 1, 0) dataSet[2,] <- c(1, 0, 1) dataSet[3,] <- c(1, 0, 1) dataSet[4,] <- c(1, 1, 1) dataSet[5,] <- c(0, 1, 1) dataSet # 转换数据格式(可以?apriori查看数据格式) dataSet_class <- as(dataSet,"transactions") # 构造频繁项集 rules<-apriori(dataSet_class,parameter=list(supp=0.5,conf=0.6,target="rules")) # 查看结果 summary(rules) # 构造关联规则 inspect(rules)

2. 自定义函数解决

相对而言，Apriori算法的函数比较难以编写，原因可想而知，肯定是因为数据结构的问题！但是也只是比其他函数难编一点，毕竟其自带的数据结构功能还是非常强大的。我在我的项目中给出的一种编写方式，是利用R语言的list来实现的。不过，我想，利用Matrix或者data.frame，当然如果你还懂data.table的话，那么肯定也是可以编写的，而且我想应该会比用list简单！(没有亲手编写，只是猜想！)

详见我的项目

转自：http://jackycode.github.io/blog/2014/05/07/apriori/