apriori
简介
在介绍Apriori算法之前我们需要先了解一下“关联分析”。关联分析指的是在大数据集中发现物品之间隐含关系，关联分析的一个著名案例就是“尿布与啤酒”。这些关系可以有两种形式：频繁项集和关联规则，频繁项集是经常出现在一块的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。而关联分析的目的就是发现频繁项集和发现关联规则
| 交易号码 | 商品 |
|---|---|
| 0 | 牛奶，莴笋 |
| 1 | 莴笋，尿布，啤酒，甜菜 |
| 2 | 牛奶，尿布，啤酒，橙汁 |
| 3 | 莴笋，牛奶，尿布，啤酒 |
| 4 | 莴笋，牛奶，尿布，橙汁 |
上面的交易清单中，集合{啤酒，尿布，牛奶}就是频繁项集的一个例子，也可以找到“尿布 -> 啤酒”的关联规则。
关联规则还可以应用于网站流量分析，电商商品推荐，流媒体音乐推荐等。
那么如何定义这些隐含关系？为此我们引入支持度和可信度的概念。
一个项集的支持度被定义为数据集中包含该项集的记录所占比例。例如，{尿布}的支持度为4/5，{尿布，啤酒}的支持度为3/5。
可信度是针对例如{尿布} -> {啤酒}的关联规则来定义的，这条规则的可信度定义为“支持度（{尿布，啤酒}）/ 支持度（尿布）”，则其可信度为3/4=0.75，这意味着对于包含“尿布”的所有记录，我们的规则对其中75%的记录都适用。
原理
假设有商品0、1、2、3，如何对给定的集合{0，3}，计算其支持度？
先列一下所有可能的项集组合： {0，1，2，3，01，02，03，12，13，23，012，013，023，123，0123}，共有15种组合方式。对于包含N种物品的数据集共有“2的N次方 - 1”种项集组合，对于现代计算机而言，这种呈指数爆炸增长的数据规模，即便007也要很长时间才能完成运算。
为了降低计算时间，研究人员发现一种 Apriori原理，即如果某个项集是频繁的，那么它的所有子集也是频繁的，反过来说，如果一个项集是非频繁集，那么它的所有超集也是非频繁的。借助Apriori原理，我们就可以减少关系不大的项集。
比如，已知{2，3}是非频繁的，借助Apriori原理，那么{0，2，3}，{1，2，3}以及{0，1，2，3}也是非频繁的，所以这三个项集的支持度就不需要计算了。
基本计算步骤
- 首先生成所有单个物品的项集列表；
- 扫描交易记录，计算单物品项集的支持度；
- 查看哪些单物品项集支持度满足要求所需的最小支持度；
- 去掉不满足最小支持度的项集；
- 对剩下的集合组合生成两元素的项集；
- 再重新扫描交易记录，去掉不满足最小支持度的项集；
- 重复，直到所有项集都被去掉。
python实现
生成一个候选项集
from numpy import *
def loadDataSet():
'''创建一个用于测试的简单数据集'''
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
def createC1(dataSet):
C1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
return map(frozenset, C1)
这第一部分的代码中，定义了loadDataSet()函数和createC1()函数，loadDataSet()函数返回一个二维列表，createC1()函数返回一个包含所有单个物品的项集列表，此列表使用了Python中的frozenset类型，目的是使其不可改变。
def scanD(D, Ck, minSupport):
'''
三个参数分别是：数据集、候选项集列表以及最小支持度
'''
ssCnt = {}
for tid in D:
for can in Ck:
if can.issubset(tid):
if not can in ssCnt.keys():
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.insert(0,key)
supportData[key] = support
return retList, supportData
此处定义的scanD()函数用于扫描交易记录并返回满足最小支持度的项集。简单运行测试一下：
dataSet = loadDataSet()
print(dataSet)
C1 = list(createC1(dataSet))
print(C1)
D = list(map(set,dataSet))
print(D)
# 有了集合形式的数据，就可以去掉那些不满足最小支持度的项集了。这里使用0.5作为最小支持度。
L1, suppData0 = scanD(D,C1,0.5)
print(L1)
# 打印结果：
[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
[{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]
[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
L1的结果表明，L1列表中的每个单物品项集至少出现在50%以上的交易记录中，而物品4并没有达到最小支持度。
组织完整的Apriori算法
def aprioriGen(Lk, k):
'''
参数为：频繁项集列表Lk，项集个数k
输出候选项集Ck
'''
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i+1, lenLk):
# 前k个项相同时，将两个集合合并
L1 = list(Lk[i])[:k-2]
L2 = list(Lk[j])[:k-2]
L1.sort()
L2.sort()
if L1==L2: #if first k-2 elements are equal
retList.append(Lk[i] | Lk[j]) #set union
return retList
def apriori(dataSet, minSupport = 0.5):
C1 = list(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)#scan DB to get Lk
supportData.update(supK)
L.append(Lk)
k += 1
return L, supportData
此处定义两个函数：apriori()和aprioriGen()，其中主函数是apriori()，它会调用aprioriGen()来创建候选项集Ck。给apriori()函数传递一个数据集以及一个支持度，函数会生成候选项集的列表。执行一下试试：
L,suppData = apriori(dataSet)
print(L)
# 打印结果
[[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})],
[frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})],
[frozenset({2, 3, 5})],
[]]
L的结果表明列表中的项出现在50%的交易记录中。
从频繁项集中挖掘关联规则
我们得到频繁项集“{尿布，啤酒}”，可能存在关联规则“尿布 -> 啤酒”，但“啤酒 -> 尿布”就不一定成立，所以我们需要将关联规则给挖出来。
def generateRules(L, supportData, minConf=0.7):
'''
参数为：频繁项集列表、包括那些频繁项集支持数据的字典、最小可信度阈值
支持度数据来自scanD返回的suppDara字典
函数生成一个包含可信度的规则列表
'''
bigRuleList = []
for i in range(1, len(L)):
# 只获取有两个或更多元素的集合
for freqSet in L[i]:
H1 = [frozenset([item]) for item in freqSet]
if (i > 1):
rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
else:
calcConf(freqSet, H1, supportData, bigRuleList, minConf)
return bigRuleList
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
prunedH = []
for conseq in H:
conf = supportData[freqSet]/supportData[freqSet-conseq] #计算可信度
if conf >= minConf:
print(freqSet-conseq,'-->',conseq,'conf:',conf)
brl.append((freqSet-conseq, conseq, conf))
prunedH.append(conseq)
return prunedH
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
m = len(H[0])
if (len(freqSet) > (m + 1)): #尝试进一步合并
Hmp1 = aprioriGen(H, m+1)#创建Hm+1条新候选规则
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
if (len(Hmp1) > 1): #至少需要两个集合合并
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
代码源自《机器学习实战》，修改了一些Python2与Python3之间的兼容问题后直接复制粘贴了。执行一下：
rules = generateRules(L,suppData,minConf=0.7)
print(rules)
# 打印结果
frozenset({5}) --> frozenset({2}) conf: 1.0
frozenset({2}) --> frozenset({5}) conf: 1.0
frozenset({1}) --> frozenset({3}) conf: 1.0
[(frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({1}), frozenset({3}), 1.0)]
示例: 发现毒蘑菇的相似特征
我们现在有一个关于野生蘑菇的数据集，寻找毒蘑菇的一些公共特征。
数据集的前几行如下：
1 3 9 13 23 25 34 36... 2 3 9 14 23 26 34 36... 2 4 9 15 23 27 34 36...
第一个特征表示有毒或者可食用。如果有毒则为2，可食用则为1.下一个特征是蘑菇伞的形状，有六种可能的值，分别用整数3~8表示。
mushDatSet = [line.split() for line in open('mushroom.dat').readlines()]
L,suppData = apriori(mushDatSet,minSupport=0.3)
# 在结果中可以搜索包含有毒特征值2的频繁项集
for item in L[1]:
if item.intersection('2'):
print(item)
# 打印结果
frozenset({'28', '2'})
frozenset({'2', '53'})
frozenset({'23', '2'})
frozenset({'34', '2'})
frozenset({'36', '2'})
frozenset({'2', '59'})
frozenset({'2', '63'})
frozenset({'67', '2'})
frozenset({'2', '76'})
frozenset({'85', '2'})
frozenset({'2', '86'})
frozenset({'90', '2'})
frozenset({'93', '2'})
frozenset({'39', '2'})
也可以在更大项集，比如 L[3]中重复上述过程。
在这个例子，我们并没有寻找关联规则，因为有时候我们只需要找到一些相关的特征，比如毒蘑菇的特征。