数据挖掘十大算法(七)：Apriori算法
发布时间
阅读量：
阅读量
一，基本原理和Python实现
1.关联分析
关联挖掘是处理海量数据时发现有价值关系模式的一种技术手段。具体表现为以下两种典型的模式：
1.frequent item sets: 那些经常同时出现的元素集合；
2.association rules: 表示两者之间的强关联。
高频项目组即指那些在数据集中反复出现在一起的关键要素所构成的合作团体。在表格中列出的例子{葡萄酒、尿布、豆奶}则是一个典型的高频项目组实例。同样能够寻找到诸如"尿布→葡萄酒"这样的关联规律,这意味著若某人已购买了尿布,那么很有可能也会选择购买葡萄酒。通过利用高频项目组与关联规律,从而帮助商家更深入地了解顾客的行为模式,因此大部分关于关联规律分析的实际案例都源自零售行业领域。
理解两个重要的概念：
2. Apriori 原理
假定经营一家杂货店后，在采购行为中我们特别关注那些常有共同购物的物品。因此我们对于那些常有共同购物的物品十分关注。
如果我们只有 4 种商品：编号分别为0号、1号、2号和3号商品. 那么我们需要确定哪些商品可能会同时被顾客购买？
该图表展示了物品之间所有的组合情况，在最上面是一个空集Ø表示没有任何物品被包含；各个物品集合之间的连接线则表明两个或更多个这样的集合能够结合起来形成一个更大的集合体。
3. 使用 Apriori 算法来发现频繁集
如前所述，在数据挖掘领域中进行关联分析时，默认有两个主要目标：识别那些在数据集中频繁出现的一组项目（即所谓 frequent itemsets）以及挖掘出这些项目之间存在的相关联规则（ association rules）。具体来说，在执行关联分析的过程中，则需要依次完成两个关键步骤——首先确定哪些项目组合是高频出现的（ frequent itemsets），并在此基础上进一步提取出具有强相关性的关联规则（ association rules）。我们先探讨如何确定这些高频项目组合——其中一种常用的方法就是 Apriori 算法
Apriori算法的核心参数包括最小支持度和数据集特征。
首先，在算法运行之前，系统会创建一个仅包含单一商品的项集列表。通过遍历所有的交易记录，系统识别出满足最小支持度条件的所有单商品集合，并将不满足条件的一一排除。 然后将剩下的单商品集合两两组合，形成双商品项集。接着系统再次遍历交易记录，剔除那些不达标的新双商品项集，并不断重复上述过程直至所有可能的项集都被筛选完毕。
伪代码：
对数据集中的每条交易记录tran:
对每个候选项集can:
检查一下can是否是tran的子集：
如果是，则增加can的计数值
对每个候选项集：
如果其支持度不低于最低值，则保留
返回所有频繁项集列表 """
Apriori exercise.
Created on Fri Nov 27 09:16:03 2019
@author: NanShan
"""
def loadDataSet():
'''创建一个用于测试的简单的数据集'''
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
def createC1(dataSet):
'''
构建初始候选项集的列表，即所有候选项集只包含一个元素，
C1是大小为1的所有候选项集的集合
'''
C1 = []
for transaction in dataSet:
for item in transaction:
if [item] not in C1:
C1.append([item])
C1.sort()
return list(map(frozenset, C1)) # frozenset就是不可变集合
def scanD(D, C1, minSupport):
'''
计算C1中的项集在数据集合D(记录或者transactions)中的支持度,
返回满足最小支持度的项集的集合，和所有项集支持度信息的字典。
'''
ssCnt = {}
# 对于每一条transaction
for tid in D:
# 对于每一个候选项集can，检查是否是transaction的一部分
# 即该候选can是否得到transaction的支持
for can in C1:
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
# 将满足最小支持度的项集，加入retList
if support >= minSupport:
retList.append(key)
# 汇总支持度数据
supportData[key] = support
return retList, supportData
if __name__ == '__main__':
# 导入数据集
myDat = loadDataSet()
# 构建第一个候选项集列表C1
C1 = createC1(myDat)
print('第一个候选集列表：', C1)
# 构建集合表示的数据集 D
data = list(map(set, myDat)) # 现在的map函数，如果外面没有list返回的是一个对象
print('原始数据：', data)
# 选择出支持度不小于0.5 的项集作为频繁项集
L1, suppData = scanD(data, C1, 0.5)
print("频繁项集L1：", L1)
print("所有候选项集的支持度信息：", suppData)输出结果：
完整的 Apriori 的算法，首先给出伪代码：（通过code好理解一点）
# -*- coding: utf-8 -*-
"""
Apriori exercise.
Created on Fri Nov 27 09:16:03 2019
@author: NanShan
"""
def loadDataSet():
'''创建一个用于测试的简单的数据集'''
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
def createC1(dataSet):
'''
构建初始候选项集的列表，即所有候选项集只包含一个元素，
C1是大小为1的所有候选项集的集合
'''
C1 = []
for transaction in dataSet:
for item in transaction:
if [item] not in C1:
C1.append([item])
C1.sort()
return list(map(frozenset, C1)) # frozenset就是不可变集合
def scanD(D, C1, minSupport):
'''
计算C1中的项集在数据集合D(记录或者transactions)中的支持度,
返回满足最小支持度的项集的集合，和所有项集支持度信息的字典。
'''
ssCnt = {}
# 对于每一条transaction
for tid in D:
# 对于每一个候选项集can，检查是否是transaction的一部分
# 即该候选can是否得到transaction的支持
for can in C1:
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
# 将满足最小支持度的项集，加入retList
if support >= minSupport:
retList.append(key)
# 汇总支持度数据
supportData[key] = support
return retList, supportData
# Aprior算法
def aprioriGen(Lk, k):
'''
:param Lk: 上一层候选集
:param k: 每个候选集的元素个数
:return: 下一层候选集
'''
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()
if L1 == L2:
retList.append(Lk[i] | Lk[j])
return retList
def apriori(dataSet, minSupport=0.5):
# 构建初始候选项集C1
C1 = createC1(dataSet)
# 将dataSet集合化，以满足scanD的格式要求
data = list(map(set, dataSet))
# 构建初始的频繁项集，即所有项集只有一个元素
L1, suppData = scanD(data, C1, minSupport)
L = [L1] # 这里为什么要再加一层列表？
# 最初的L1中的每个项集含有一个元素，新生成的项集应该含有2个元素，所以 k=2
k = 2
while (len(L[k - 2]) > 0):
Ck = aprioriGen(L[k - 2], k)
Lk, supK = scanD(data, Ck, minSupport)
# 将新的项集的支持度数据加入原来的总支持度字典中
suppData.update(supK)
# 将符合最小支持度要求的项集加入L
L.append(Lk)
# 新生成的项集中的元素个数应不断增加
k += 1
# 返回所有满足条件的频繁项集的列表，和所有候选项集的支持度信息
return L, suppData
if __name__ == '__main__':
# 导入数据集
myDat = loadDataSet()
print('当支持度为0.5时：')
# 选择频繁项集
L, suppData = apriori(myDat, 0.5)
print("频繁项集L：", L)
print("所有候选项集的支持度信息：", suppData)
print('\n')
print('当支持度为0.7时：')
# 选择频繁项集
L, suppData = apriori(myDat, 0.7)
print("频繁项集L：", L)
print("所有候选项集的支持度信息：", suppData)这里重点解释一下aprioriGen原理：
关于上面程序函数 aprioriGen 中的 k−2 的说明：基于只含有一个元素的候选项集{0}、{1}、{2}生成含有两个元素的候选项集时（即通过合并两个集合），会分别生成{0,1}、{0,2}、{1,2}；继续使用这些两位数目的项集来生成三位数目的项集时（即再进行一次合并），从而会得到三个相同的三位数项集{0,1,2}；显然这会导致大量的重复项出现。因此，在处理三位数项集时需要去重以获得非重复的结果，在这种情况下计算时间会有所增加。当前的方法是检查每个两位数组的第一个数字（即索引为零的部分），对于具有相同第一个数字的部分进行合并操作即可直接生成{0,1,2}；这种方式只需要执行一次操作即可完成，并不需要遍历整个列表寻找非重复值的情况发生。
输出结果：
4.从频繁集中挖掘关联规则
为了获取关联规则, 我们可以从一个高频项集中出发, 探讨在该高频项集中是否存在能够推导出其他内容的情况。即我们可以考察是否存在这样一种情况:某一项或某一项集合能够推导出另一项。根据表1的数据分析可知, 如果有一个包含{豆奶, 营销部}的高频项集, 那么就会有一条潜在的关联规则 '豆奶 → 莴苣', 这意味着在统计意义上来说, 在购买了豆奶的情况下顾客倾向于也会购买莴苣。然而这条规律反过来并不一定成立
基于该频繁项集能生成多少条关联规则吗？可以通过该频繁项集生成一系列潜在的关联规则列表，并通过逐一检验这些关联规则的有效性来确定哪些是有效的。如果检测到任何一条关联规则的有效性低于设定阈值，则将其排除。与之前讨论的一致，在计算每条关联规则的有效性之前就进行筛选的话，在处理大量数据时能够显著提升效率。
**存在这样一条规律：当某条规则未达到最小可信度标准时，则其所有子集同样不会达到该标准。例如如图所示的情况：
完整code： 下面的 demo 存在明显缺陷：当元素数量超过两个时，在识别模式时仅识别了一对多关系，并未识别多对一以及多对多的关系。
# -*- coding: utf-8 -*-
"""
Apriori exercise.
Created on Fri Nov 27 09:16:03 2019
@author: NanShan
"""
def loadDataSet():
'''创建一个用于测试的简单的数据集'''
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
def createC1(dataSet):
'''
构建初始候选项集的列表，即所有候选项集只包含一个元素，
C1是大小为1的所有候选项集的集合
'''
C1 = []
for transaction in dataSet:
for item in transaction:
if [item] not in C1:
C1.append([item])
C1.sort()
return list(map(frozenset, C1)) # frozenset就是不可变集合
def scanD(D, C1, minSupport):
'''
计算C1中的项集在数据集合D(记录或者transactions)中的支持度,
返回满足最小支持度的项集的集合，和所有项集支持度信息的字典。
'''
ssCnt = {}
# 对于每一条transaction
for tid in D:
# 对于每一个候选项集can，检查是否是transaction的一部分
# 即该候选can是否得到transaction的支持
for can in C1:
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
# 将满足最小支持度的项集，加入retList
if support >= minSupport:
retList.append(key)
# 汇总支持度数据
supportData[key] = support
return retList, supportData
# Aprior算法
def aprioriGen(Lk, k):
'''
:param Lk: 上一层候选集
:param k: 每个候选集的元素个数
:return: 下一层候选集
'''
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()
if L1 == L2:
retList.append(Lk[i] | Lk[j])
return retList
def apriori(dataSet, minSupport=0.5):
# 构建初始候选项集C1
C1 = createC1(dataSet)
# 将dataSet集合化，以满足scanD的格式要求
data = list(map(set, dataSet))
# 构建初始的频繁项集，即所有项集只有一个元素
L1, suppData = scanD(data, C1, minSupport)
L = [L1] # 这里为什么要再加一层列表？
# 最初的L1中的每个项集含有一个元素，新生成的项集应该含有2个元素，所以 k=2
k = 2
while (len(L[k - 2]) > 0):
Ck = aprioriGen(L[k - 2], k)
Lk, supK = scanD(data, Ck, minSupport)
# 将新的项集的支持度数据加入原来的总支持度字典中
suppData.update(supK)
# 将符合最小支持度要求的项集加入L
L.append(Lk)
# 新生成的项集中的元素个数应不断增加
k += 1
# 返回所有满足条件的频繁项集的列表，和所有候选项集的支持度信息
return L, suppData
# 规则生成与评价
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
'''
计算规则的可信度，返回满足最小可信度的规则。
freqSet(frozenset):频繁项集
H(frozenset):频繁项集中所有的元素
supportData(dic):频繁项集中所有元素的支持度
brl(tuple):满足可信度条件的关联规则
minConf(float):最小可信度
'''
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):
'''
对频繁项集中元素超过2的项集进行合并。
freqSet(frozenset):频繁项集
H(frozenset):频繁项集中的所有元素，即可以出现在规则右部的元素
supportData(dict):所有项集的支持度信息
brl(tuple):生成的规则
'''
m = len(H[0])
# 查看频繁项集是否大到移除大小为 m 的子集
if len(freqSet) > m + 1:
Hmp1 = aprioriGen(H, m + 1)
print(Hmp1)
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
# 如果不止一条规则满足要求，进一步递归合并
if len(Hmp1) > 1:
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
def generateRules(L, supportData, minConf=0.7):
'''
根据频繁项集和最小可信度生成规则。
L(list):存储频繁项集
supportData(dict):存储着所有项集（不仅仅是频繁项集）的支持度
minConf(float):最小可信度
'''
bigRuleList = []
for i in range(1, len(L)):
for freqSet in L[i]: # 直接掉过元素为1的第一个频繁项集合
# 对于每一个频繁项集的集合freqSet
H1 = [frozenset([item]) for item in freqSet]
# 如果频繁项集中的元素个数大于2，需要进一步合并
if i > 1:
rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
else:
calcConf(freqSet, H1, supportData, bigRuleList, minConf)
return bigRuleList
# if __name__ == '__main__':
# # 导入数据集
# myDat = loadDataSet()
# print('当支持度为0.5时：')
# # 选择频繁项集
# L, suppData = apriori(myDat, 0.5)
# print("频繁项集L：", L)
# print("所有候选项集的支持度信息：", suppData)
#
# print('\n')
# print('当支持度为0.7时：')
# # 选择频繁项集
# L, suppData = apriori(myDat, 0.7)
# print("频繁项集L：", L)
# print("所有候选项集的支持度信息：", suppData)
if __name__ == '__main__':
# 导入数据集
myDat = loadDataSet()
# 选择频繁项集
L, suppData = apriori(myDat, 0.5) # 支持度
print('=============频繁项集=============')
print(L)
print('=============所有集合的支持度=============')
print(suppData)
print('=============关联关系=============')
rules = generateRules(L, suppData, minConf=0.7) # 置信度
print('rules:\n', rules)输出结果：
二、sklearn实现关联算法
本来想写一下的 但是好像没有Apriori的API~~~
全部评论 (0)
还没有任何评论哟~