Apriori 算法原理以及python实现详解
2021/10/4 14:12:50
本文主要是介绍Apriori 算法原理以及python实现详解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
Apriori 算法原理以及python实现
Apriori算法是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类
矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。（节选自百科）
1. Apriori 算法原理介绍
设想场景如下：有一商场，记录对比每位顾客每次购买商品的清单，会发现购买了某类商品的顾客很大概率还会购买另外一类商品，为了更好的布局商品货架和进行捆绑促销的活动，需要统计分析不同种类商品的关联性。
进一步假定商场仅有四类商品0、1、2、3，为了统计分析商品的关联性，会自然去逐个计算不同商品组合出现的概率，1、2、3、4、01、02、03、12、13、23、012、013、023、123、1234 ，这些组合在Apriori中称为项集。
引入具体概念如下：
-
项与项集：设itemset={item1, item_2, …, item_m}是所有项的集合，其中，item_k(k=1,2,…,m)成为项。项的集合称为项集（itemset），包含k个项的项集称为k项集(k-itemset)。
-
关联规则：关联规则是形如A=>B的蕴涵式，其中A、B均为itemset的子集且均不为空集，而A交B为空。
-
支持度(support)：关联规则的支持度定义如下：
即项集A、B同时发生的概率。
- 置信度(confidence)：关联规则的置信度定义如下：
即项集A发生的情况下，则项集B发生的概率为关联规则的置信度。
- 项集的出现频度(support count)：相应项集的出现次数，简称为项集的频度、支持度计数或计数。
- 频繁项集(frequent itemset)：满足最小支持度的所有项集。
- 强关联规则：满足最小支持度和最小置信度的关联规则，即待挖掘的关联规则。
为了便于理解，假定有有5份购物清单，总计5类商品，1表示购买，0表示未买。
| id | item0 | item1 | item2 | item3 | item4 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 1 | 1 |
| 3 | 0 | 1 | 1 | 1 | 0 |
| 4 | 1 | 1 | 1 | 1 | 0 |
| 5 | 1 | 1 | 1 | 0 | 0 |
其中，项包含item0、item1、item2、item3、item4，项集为每个id对应的item。
现在想研究{item1、item2}与item3的关联性。
支持度：{item1、item2、item3}同时发生概率为2/5。
置信度：{item1、item2}发生情况下，item3发生概率，即计算{item1、item2、item3}出现的次数所占{item1、item2}发生次数的比重，为2/3 。
若最小支持度为1/5而最小置信度为1/2，则此关联规则为强规则，其为频繁项集中的一个子集。
针对这些商品，我们的目标是：从大量购买数据中找到经常一起被购买的
商品。在寻找频繁项集（即经常出现的商品组合）的过程，我们采用支持度
和置信度来过滤商品组合来获得频繁项集。针对四钟商品，我们要在整体数
据集上进行15次轮询，才可以统计出每个频繁项集的支持度和置信度。试想，如果数据量较大，且商品种类不止四种的情况下，依旧采用逐个轮询的方式进行统计，带来的运算量是巨大的，并且随着商品种类的增加，频繁项集的组合种类也将变为2^N - 1种，随着种类的增加，那么带来的运算代价呈现指数型增加。为了解决这个问题，研究人员便在Apriori原理的基础上设计了Apriori算法。具体原理如下：如果某个项集是频繁的，那么它的所有子集也是频繁的。毫无疑问是正确的，则其逆否命题，如果一个项集是非频繁集，那么它的所有超集（包含该非频繁集的父集）也是非频繁的也是正确的。
假定阴影项集{2,3}是非频繁的，那么它的所有超集，也都是非频繁的，如上图灰色所示。在实际计算过程中，一旦计算出{2,3}的支持度不满足最小支持度，那么就不需要再计算{0,2,3}、{1,2,3}和{0,1,2,3}的支持度，因为它们也都是非频繁集。
2. Apriori 算法实现
设定最小支持度与置信度
MIN_Support = 0.5 MIN_Conf = 0.7
2.1项集构造及频繁项集获取
首先载入数据集
def loadDataSet():
return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
createOneitmeset(...)函数生成对应数据集内所有一项集
def createOneitmeset(dataSet):
one_itmeset = []
for transaction in dataSet: #循环遍历dataset中所有元素，未在列表中则添加
for item in transaction:
if not [item] in one_itmeset:
one_itmeset.append([item])
one_itmeset.sort()
return list(map(frozenset, one_itmeset))
filter_itmeset(...)函数依据Apriori算法（一个项集是非频繁集，那么它的所有超集（包含该非频繁集的父集）也是非频繁的）来进
行滤除
def filter_itmeset(Data, itmeset):
item_frequency = {}
for item in Data: #循环遍历项集中元素，并记录出现次数至item_frequency字典中
for element in itmeset:
if element.issubset(item): #issubset方法:若item包含element中所有元素则返回True
if not element in item_frequency: item_frequency[element] = 1
else:item_frequency[element] += 1
numItems = float(len(Data)) #数据集中总的项集个数
item_filtered = [] #频繁项集
itemSupprotData={} #项集中各项支持度
for key in item_frequency:
support = item_frequency[key]/numItems #支持度计算：元素出现次数 / 总项集数
if support>=MIN_Support: #满足最小支持度添加到频繁项集列表中
item_filtered.insert(0, key)
itemSupprotData[key] = support
return item_filtered, itemSupprotData
接着依照一项集构造未滤除的二项集，滤除之后得到二项集，再依据二项集构造三项集，循环往复得到直到K项集。具体函数实现为K_itemsetGenerator(...)函数，二项集及其之后的项集构造函数，滤除函数仍使用 filter_itmeset(Data, itmeset)
def K_itemsetGenerator(K_itemset_prev, K):
K_itemset = [] #K-项集
len_prev = len(K_itemset_prev) #前一项集项数
for i in range(len_prev): #二重循环两两组合生成生成新项集
for j in range(i+1, len_prev):
L1=list(K_itemset_prev[i])[:K-2];L2=list(K_itemset_prev[j])[:K-2]
L1.sort();L2.sort()
if L1==L2:
K_itemset.append(K_itemset_prev[i]|K_itemset_prev[j])
return K_itemset
这里用了一个简单的优化来减少遍历次数和确保项集合成不超K，即输入的两个项集有k-2项相同才合并。以二项集生成三项集举例，只有{0、1}和{0、2}才会合并成为三项集，而{0、1}和{1、2}并不会合并。
2.2 获取关联信息
关联信息获取的主函数如下：
def findRelatedItemGroup(K_itemset_freq,itemSupprotData):
RelatedItemGroup = []
K = len(K_itemset_freq)
for i in range(1, K):
for itemset in K_itemset_freq[i]:
itemWaitjudge = [frozenset([element]) for element in itemset]
if(i > 1):
reunionAcalcConf(itemset,itemWaitjudge,itemSupprotData,RelatedItemGroup)
else:
calcConf(itemset,itemWaitjudge,itemSupprotData,RelatedItemGroup)
return RelatedItemGroup
findRelatedItemGroup(...)函数具体流程如下，获取二项集{A、B}，对其进行分割，获得两个一项集A、B，由于是一项集不需要进行再组合，可以直接计算（A⇒B）以及（B⇒A）的置信度通过calcConf(...)是否达到需求，达到要求则会添加到RelatedItemGroup列表变量中，不满足则舍去，遍历完二项集之后，如若存在三项集，开始遍历三项集{A、B、C}，首先进行分割，获得三个一项集A、B、C，此时需要在组合以便计算{(AUB)⇒C}、{(AUC)⇒B}等等组合的置信度。如此逐层循环获取频繁项集中所包含的强关联规则。三项集及以上的再组合与置信度计算均包含在reunionAcalcConf(...)函数中。
以下是两个函数的具体实现，首先来看reunionAcalcConf(...)函数：
def reunionAcalcConf(itemset, itemWaitjudge, itemSupprotData, RelatedItemGroup):
K = len(itemWaitjudge[0]) #K:当前项集的项数
if (len(itemset) > (K + 1)): #当当前项集项数已经组合到(父项集项数 - 1)时无需再次递归组合，否则继续在组合
itemset_reunion = K_itemsetGenerator(itemWaitjudge, K + 1) #项集包含项再组合，项数为当前项数 + 1
itemset_reunion_filtered = calcConf(itemset, itemset_reunion, itemSupprotData, RelatedItemGroup) #计算置信度并进行滤除
if(len(itemset_reunion_filtered) > 1): #如果没有强关联规则存在，后续的也无须递归再组合计算置信度
reunionAcalcConf(itemset, itemset_reunion_filtered, itemSupprotData, RelatedItemGroup) #存在强关联规则，递归在组合计算置信度
reunionAcalcConf(...)为递归函数，第一次进入时，此时 itemWaitjudge 为一项集，故K = 1 ， 必定小于父项集项数， 满足len(itemset) > (K + 1)，可以进行再组合、计算置信度，此时如果再组和计算后发现了多组强规则的存在，即满足len(itemset_reunion) > 1，那么对这些强规则进行再组和判断是否有进一步的强规则情况存在。如此递归，边界条件为 len(itemset) > (K + 1) ，即当当前项集项数已经组合到 (父项集项数 - 1) 时。
接下来看 calcConf(...)的具体细节
def calcConf(itemset, itemWaitjudge, itemSupprotData, RelatedItemGroup):
item_realted = [] #存储itemWaitjudge中项间强关联规则
for item in itemWaitjudge:
conf = itemSupprotData[itemset] / itemSupprotData[itemset - item] #计算置信度
if conf >= MIN_Conf: #满足条件 存储并输出
print (itemset-item,'--->',item,'conf:',conf)
RelatedItemGroup.append((itemset - item, item, conf))
item_realted.append(item)
return item_realted
其中 itemSupprotData[itemset]为事件(AUB)发生概率，itemSupprotData[itemset - item]为事件A发生概率，两者相除即为支持度，如果所得支持度满足最小支持度存储并输出，最后返回该项集内强关联规则。
3.完整实验代码
MIN_Support = 0.5
MIN_Conf = 0.6
def loadDataSet():
return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
def createOneitmeset(dataSet):
one_itmeset = []
for transaction in dataSet: #循环遍历dataset中所有元素，未在列表中则添加
for item in transaction:
if not [item] in one_itmeset:
one_itmeset.append([item])
one_itmeset.sort()
return list(map(frozenset, one_itmeset))
def K_itemsetGenerator(K_itemset_prev, K):
K_itemset = [] #K-项集
len_prev = len(K_itemset_prev) #前一项集项数
for i in range(len_prev): #二重循环两两组合生成生成新项集
for j in range(i+1, len_prev):
L1=list(K_itemset_prev[i])[:K-2];L2=list(K_itemset_prev[j])[:K-2]
L1.sort();L2.sort()
if L1==L2:
K_itemset.append(K_itemset_prev[i]|K_itemset_prev[j])
return K_itemset
def filter_itmeset(Data, itmeset):
item_frequency = {}
for item in Data: #循环遍历项集中元素，并记录出现次数至item_frequency字典中
for element in itmeset:
if element.issubset(item): #issubset方法:若item包含element中所有元素则返回True
if not element in item_frequency: item_frequency[element] = 1
else:item_frequency[element] += 1
numItems = float(len(Data)) #数据集中总的项集个数
item_filtered = [] #频繁项集
itemSupprotData={} #项集中各项支持度
for key in item_frequency:
support = item_frequency[key]/numItems #支持度计算：元素出现次数 / 总项集数
if support>=MIN_Support: #满足最小支持度添加到频繁项集列表中
item_filtered.insert(0, key)
itemSupprotData[key] = support
return item_filtered, itemSupprotData
def itemset_exhaustion(dataSet):
one_itmeset = createOneitmeset(dataSet)
Data = list(map(set, dataSet))
one_itmeset_filtered, itemSupprotData_union = filter_itmeset(Data, one_itmeset)
itemset_union = [one_itmeset_filtered]
K = 2
while(len(itemset_union[K - 2]) > 0):
K_itemset = K_itemsetGenerator(itemset_union[K-2], K)
K_itemset_filtered, K_itemSupprotData = filter_itmeset(Data, K_itemset)
itemSupprotData_union.update(K_itemSupprotData)
itemset_union.append(K_itemset_filtered)
K += 1
return itemset_union, itemSupprotData_union
def findRelatedItemGroup(K_itemset_freq,itemSupprotData):
RelatedItemGroup = []
K = len(K_itemset_freq)
for i in range(1, K):
for itemset in K_itemset_freq[i]:
itemWaitjudge = [frozenset([element]) for element in itemset]
if(i > 1):
reunionAcalcConf(itemset,itemWaitjudge,itemSupprotData,RelatedItemGroup)
else:
calcConf(itemset,itemWaitjudge,itemSupprotData,RelatedItemGroup)
return RelatedItemGroup
def calcConf(itemset, itemWaitjudge, itemSupprotData, RelatedItemGroup):
item_realted = [] #存储itemWaitjudge项中强关联规则
for item in itemWaitjudge:
conf = itemSupprotData[itemset] / itemSupprotData[itemset - item] #计算置信度
if conf >= MIN_Conf: #满足条件 存储并输出
print (itemset-item,'--->',item,'conf:',conf)
RelatedItemGroup.append((itemset - item, item, conf))
item_realted.append(item)
return item_realted
def reunionAcalcConf(itemset, itemWaitjudge, itemSupprotData, RelatedItemGroup):
K = len(itemWaitjudge[0]) #K:当前项集的项数
if (len(itemset) > (K + 1)): #当当前项集项数已经组合到(父项集项数 - 1)时无需再次递归组合，否则继续在组合
itemset_reunion = K_itemsetGenerator(itemWaitjudge, K + 1) #项集包含项再组合，项数为当前项数 + 1
itemset_reunion_filtered = calcConf(itemset, itemset_reunion, itemSupprotData, RelatedItemGroup) #计算置信度并进行滤除
if(len(itemset_reunion_filtered) > 1): #如果没有强关联规则存在，后续的也无须递归再组合计算置信度
reunionAcalcConf(itemset, itemset_reunion_filtered, itemSupprotData, RelatedItemGroup) #存在强关联规则，递归在组合计算置信度
if __name__=='__main__':
dataSet=loadDataSet()
L,supportData=itemset_exhaustion(dataSet)
rules = findRelatedItemGroup(L,supportData)
实验输出如下：
MIN_Support = 0.5 MIN_Conf = 0.7
MIN_Support = 0.5 MIN_Conf = 0.6
（部分图片来源网络）
参考文章：
【机器学习】Apriori算法——原理及代码实现（Python版）
这篇关于Apriori 算法原理以及python实现详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-14获取参数学习：Python编程入门教程
- 2024-11-14Python编程基础入门
- 2024-11-14Python编程入门指南
- 2024-11-13Python基础教程
- 2024-11-12Python编程基础指南
- 2024-11-12Python基础编程教程
- 2024-11-08Python编程基础与实践示例
- 2024-11-07Python编程基础指南
- 2024-11-06Python编程基础入门指南
- 2024-11-06怎么使用python 计算两个GPS的距离功能-icode9专业技术文章分享
