一、关联规则
关联规则，顾名思义，就是寻找事物之间的关联关系。比如《啤酒与尿布》中，在某个特定时间段，会出现啤酒与尿布同时出现在购物篮中的现象，且出现频率非常高。调研发现这是一群爱喝啤酒的奶爸群体。如果可以通过类似的方式挖掘更多特定的群体需求，就可以进行交叉销售或捆绑销售来提升销售额和利润。Apriori算法就是经典的寻找物品的关联算法。
二、Apriori算法原理
1、基础概念
项集 ：包含0个或者多个项的集合称为项集
频繁项集：那些经常一起出现的物品集合
2、关联规则
规则A->B的度量包括支持度，置信度
支持度：项集A、B同时发生的概率 —P(A∩B)
置信度：当A发生时发生B的概率—P(B|A) = P(A∩B)/P(A)
两者都会有一个阈值，支持度低于阈值说明A,B同时出现的概率低，两者有没有关联关系都对实际业务没啥帮助；置信度低于阈值说明A在发生情况下B的发生可能性小，我们想要挖掘的是在A发生时B有很大可能也会发生的情况。
举例：
方便面 -> 火腿肠：{支持度：0.2， 置信度：0.8}
说明方便面和火腿肠同时出现的概率20%，这个概率已经相当高了，而当购买了方便面时，有80%的可能性会购买火腿肠，如果两者分开陈列都能达到这样的效果，那交叉陈列或者捆绑销售肯定会进一步提升置信度。
一般支持度和置信度的阈值设定有2种方法：1是听取行业专家的意见，2是求所有项集的平均值或中位数
3、自连接和剪枝原理
自连接是保证除掉最后一个元素后相同的情况下，将两者求并集得到新的项集。
剪枝步
① 支持度：是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。比如{A},{B}都是不频繁的，那么{A,B}也是不频繁的，因为单个都发生的可能性极低了，那组合在一起不是更低了吗？（剪枝法是算法科学中一种比较重要的思路，是利用数据特性或一些其余技巧过滤掉那些没必要计算的情况，降低算法的时间复杂度）
单品组合也可以使用笛卡尔积：两个集合中的元素做一对一的循环匹配，再去掉重复的
② 置信度：如果{A,B,C}->{D}是置信度低的，那么{A,B}->{C,D},{A}->{B,C,D},{B}->{A,C,D}都是低的
4、Apriori算法流程
思路：
通过迭代，检索出所有频繁项集；利用频繁项集构造出关联规则
具体做法：
首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”
算法步骤：
① 发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集 重复步骤（1）~（5）直到不能发现更大的频集
② 产生关联规则:
<> 对于每个频繁项集L，产生L的所有非空子集；
<> 对于L的每个非空子集S，如果
P（L）/P（S）≧min_conf
则输出规则“SàL-S”
5、关联规则价值
通过Apriori算法得到了满足最小支持度和最小置信度的关联关系，但是否就能直接用了呢？
一般还会增加以下考量：
① 提升度
提升度：衡量A的发生是否促进了B的发生—P(B|A) / P(B)
前者是A发生时B发生的概率，后者是在全样本空间中B发生的概率，如果大于1，说明A发生时B发生的概率要列高，有提升作用；如果等于1，说明没有影响；如果小于1，说明A发生能抑制B的发生。
② 是否去除热门商品影响
热门商品是活跃度较高的商品，基本上热门商品之间的支持度和置信度都会很高，但这样的关系是没有太大意义的，因为不做任何处理，他们都已经卖得相当好了。
④ 是否新颖
所谓新颖就是要寻找一些平常想不到但是确实又有这样的需求的群体存在的组合，才能对业务有较大帮助。像鲜奶和酸奶，啤酒和葡萄酒这种司空见惯的组合模式，也没有太大价值
6、稀有模式
当A,B各自的支持度很高，但是AB的支持度却非常非常低，那么AB就是稀有模式，说明A,B之间存在负相关关系。一般来说，P(A∩B) 远远小于 P(A)*P(B)，就能说明A和B是强负相关
挖掘负相关的场景，可以用来预测用户在某一领域的预算规模和购物规律，比如买了电脑的，可能就不会再买PAD；也可以用来发现有关联的疾病，比如在得过A疾病的病患，患B疾病的比例要比普通人小很多等
三、Apriori算法的Python实现
这里借鉴博主-gamer_gyt的代码
from numpy import *
def loadDataSet():
return [[1, 2, 3, 4], [2, 3, 4, 5], [1, 2, 3, 5], [1, 2, 4, 5]]
# 创建L1项集
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) # frozenset是不可变集合，相对集合来说，好处是可以做为字典的键
#计算支持度
def scanD(D, Ck, minSupport):
ssCnt = {}
for tid in D:
for can in Ck:
if can.issubset(tid): # 集合用法：检查是否是子集
ssCnt[can] = ssCnt.get(can, 0) + 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
# 由Lk频繁项集生成LK+1项集
def aprioriGen(Lk, k):
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i + 1, lenLk):
# 前k-2项相同时，将两个集合合并
L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
L1.sort(); L2.sort()
if L1 == L2:
retList.append(Lk[i] | Lk[j]) # 集合用法：并集
return retList
# 输出所有频繁项集和支持度
def apriori(dataSet, minSupport=0.5):
C1 = list(createC1(dataSet))
D = list(map(frozenset, 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)
if len(Lk)>0:
L.append(Lk)
supportData.update(supK)
k += 1
else:
break
return L, supportData
def conf(freqset,H,support,br1,min_f = 0.5):
p = []
i = 1
for con in H:
print(i)
i += 1
print(type(con))
conf = support[freqset]/support[freqset-con]
if conf>=min_f:
print(freqset-con,con)
br1.append(((freqset-con),con,conf))
p.append(con)
return p
def rules(freqset, H, support, br1, min_f=0.5):
m = len(H[0])
while (len(freqset)>m):
H = conf(freqset, H, support, br1, min_f)
if (len(H)>1):
H = apriori(H, m+1)
m += 1
else:
break
def generator(L,support,min_f=0.5):
bigrules = []
print(len(L))
for i in range(1, len(L)-1):
for freqset in L[i]:
H1 = [frozenset([item]) for item in freqset]
rules(freqset, H1, support, bigrules, min_f)
return bigrules
dataSet = loadDataSet()
C1 = list(createC1(dataSet))
D = list(map(frozenset, dataSet))
L1, suppData = scanD(D, C1, 0.5)
L, support = apriori(dataSet)
print(L)
g = generator(L, support, min_f=0.3)
print(g)
