概述
- 优点：易编码实现
- 缺点：在大数据集上可能较慢
- 适用数据类型：数值型或标称型数据
关联分析
从大规模数据集中寻找物品间的隐含关系被称作关联分析（association analysis）或者关联规则学习（association rule learning）。
这些隐含关系可以有两种形式：频繁项集和关联规则。
- 频繁项集（frequent item sets）：经常出现在一起的物品的集合。
- 关联规则（association rules）：暗示两种物品之间可能存在很强的关系。
可以用支持度和可信度来衡量定义这种关系。
一个项集的支持度（support）被定义为数据集中包含该项集的记录所占的比例。
可信度或置信度（confidence）是针对一条诸如{尿布} -> {葡萄酒}的关联规则来定义的。这条规则的可信度被定义为支持度（{尿布，葡萄酒}）/支持度（{尿布}）。
Apriori原理
假设我们只有4种商品在卖，商品0，商品1，商品2，商品3。顾客可能购买的商品组合如下图所示。
可能的商品组合
我们的目标是找到经常在一起购买的物品集合，使用支持度来度量其出现的频率。例如计算{0,3}的支持度，我们需要遍历所有记录，找到同时包含0和3的记录，就将计数值加1，最后用计数值除以总记录数。
对于我们只有4种商品的集合，需要遍历数据集15次（观察上图一共有15种可能组合），对于包含N种物品的数据集一共有种组合。计算量相当庞大。
我们可以用Apriori原理来减少项集，降低所需计算时间。
Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。反过来说就是，如果一个项集是非频繁的，那么它的所有超集也是非频繁的。
例如我们计算{2,3}的支持度，知道它是非频繁的，那么就不再需要计算{0,2,3}、{1,2,3}和{0,1,2,3}了。
使用Apriori原理可以避免项集数目的指数增长，从而在合理时间内计算出频繁项集。
使用Apriori算法发现频繁集
生成候选项集
# 构建数据集
def createData():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
# 构建C1候选项集
def createC1(dataSet):
C1 = []
for transaction in dataSet:
for item in transaction:
if [item] not in C1:
C1.append([item])
C1.sort()
return list(map(frozenset, C1))
def scanD(D, Ck, minSupport):
ssCnt = {}
# 遍历所有记录，计数各项集出现次数
for tid in D:
for can in Ck:
if can.issubset(tid):
if can not in ssCnt:
ssCnt[can] = 1
else:
ssCnt[can] += 1
numItems = float(len(D))
retList = []
supportData = {}
for key in ssCnt:
support = ssCnt[key]/numItems # 计算支持度
if support >= minSupport:
retList.append(key)
supportData[key] = support
return retList, supportData
函数createC1()构建大小为1的所有候选项集的集合C1。Apriori算法首先构建集合C1，然后扫描数据集来找到满足最小支持度的频繁项集构成集合L1，而L1中的元素相互组合构成C2，C2再进一步过滤得到L2，以此类推。
所以Apriori算法需要函数createC1()来构建第一个候选项集的列表C1。由于列表中的项集后面需要被当作字典的key，所以返回时用map()函数将各项集转化为frozenset类型。
scanD()函数用于从Ck生成Lk，另外还会返回一个包含支持度值的字典以备后用。
下面看下实际运行效果。
data = createData()
C1 = createC1(data)
D = list(map(set, data))
L1, supportData = scanD(D, C1, 0.5)
第一个候选项集C1，数据集D和L1的值如下。
完整的Apriori算法
整个Apriori算法的伪代码如下：
当集合中项的个数大于0时：
构建一个k个项组成的候选项集的列表
检查数据以确认每个项集都是频繁的
保留频繁项集并构建k+1项组成的候选项集的列表
代码如下：
def aprioriGen(Lk, k):
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i+1, lenLk):
L1 = list(Lk[i])[:k-2]
L2 = list(Lk[j])[:k-2]
L1.sort()
L2.sort()
# 前k-2项相同时，将两个项集合并
if L1 == L2:
retList.append(Lk[i] | Lk[j])
return retList
def apriori(dataSet, minSupport = 0.5):
C1 = createC1(dataSet)
D = list(map(set, dataSet))
L1, supportData = scanD(D, C1, minSupport)
L = [L1]
k = 2
while (len(L[k-2]) > 0):
Ck = aprioriGen(L[k-2], k)
Lk, supK = scanD(D, Ck, minSupport)
supportData.update(supK)
L.append(Lk)
k += 1
return L, supportData
函数aprioriGen()的输入参数为频繁项集列表Lk与项集元素个数k，输出为Ck。
apriori()为主函数。首先调用createC1()创建第一个候选项集，然后scanD()生成L1，接着循环调用aprioriGen()和scanD()生成Ck和Lk，最后当Lk为空时退出。
下面是执行效果。
这是最小支持度为50%的情况，下面试一下75%的支持度。
下面画出的简陋流程图用于加深对Apriori算法找出频繁集的工作流程的理解。
Apriori算法流程简易版
到此，我们就用Apriori算法找出频繁集了。后面就是要从频繁项集中挖掘关联规则。
都看到最后了，要不~点个赞？加波关注？
网友评论