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

时间:2021-07-22 16:50:23

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

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


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

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


一、原理


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

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

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

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

超集:就是指包含这个集合中所以元素的集合(不包括自身),比如集合ABC就是集合AB的超集。

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

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


二、算法构成


有了上面这个原理,那么就可以利用这个原理去减少我们寻找频繁集的计算量。因为,只要我们找到一个项集,其支持度低于给定的值,那么这个项集的所有超集就可以直接忽略不计了。如上图,项集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/