用Numpy实现高效的Apriori算法
By 苏剑林 | 2018-05-10 | 92453位读者 |三年前笔者曾写了《用Pandas实现高效的Apriori算法》,里边给出了Apriori算法的Python实现,并得到了一些读者的认可。然而,笔者当时的Python还学得并不好,所以现在看来那个实现并不优雅(但速度还过得去),而且还不支持变长的输入数据。而之前承诺过会重写这个算法,把上述问题解决掉,而现在总算完成了~
关于Apriori算法就不重复介绍了,直接放出代码:
#! -*- coding: utf-8 -*-
import numpy as np
class Apriori:
def __init__(self, min_support, min_confidence):
self.min_support = min_support # 最小支持度
self.min_confidence = min_confidence # 最小置信度
def count(self, filename='apriori.txt'):
self.total = 0 # 数据总行数
items = {} # 物品清单
# 统计得到物品清单
with open(filename) as f:
for l in f:
self.total += 1
for i in l.strip().split(','): # 以逗号隔开
if i in items:
items[i] += 1.
else:
items[i] = 1.
# 物品清单去重,并映射到ID
self.items = {i:j/self.total for i,j in items.items() if j/self.total > self.min_support}
self.item2id = {j:i for i,j in enumerate(self.items)}
# 物品清单的0-1矩阵
self.D = np.zeros((self.total, len(items)), dtype=bool)
# 重新遍历文件,得到物品清单的0-1矩阵
with open(filename) as f:
for n,l in enumerate(f):
for i in l.strip().split(','):
if i in self.items:
self.D[n, self.item2id[i]] = True
def find_rules(self, filename='apriori.txt'):
self.count(filename)
rules = [{(i,):j for i,j in self.items.items()}] # 记录每一步的频繁项集
l = 0 # 当前步的频繁项的物品数
while rules[-1]: # 包含了从k频繁项到k+1频繁项的构建过程
rules.append({})
keys = sorted(rules[-2].keys()) # 对每个k频繁项按字典序排序(核心)
num = len(rules[-2])
l += 1
for i in range(num): # 遍历每个k频繁项对
for j in range(i+1,num):
# 如果前面k-1个重叠,那么这两个k频繁项就可以组合成一个k+1频繁项
if keys[i][:l-1] == keys[j][:l-1]:
_ = keys[i] + (keys[j][l-1],)
_id = [self.item2id[k] for k in _]
support = 1. * sum(np.prod(self.D[:, _id], 1)) / self.total # 通过连乘获取共现次数,并计算支持度
if support > self.min_support: # 确认是否足够频繁
rules[-1][_] = support
# 遍历每一个频繁项,计算置信度
result = {}
for n,relu in enumerate(rules[1:]): # 对于所有的k,遍历k频繁项
for r,v in relu.items(): # 遍历所有的k频繁项
for i,_ in enumerate(r): # 遍历所有的排列,即(A,B,C)究竟是 A,B -> C 还是 A,B -> C 还是 A,B -> C ?
x = r[:i] + r[i+1:]
confidence = v / rules[n][x] # 不同排列的置信度
if confidence > self.min_confidence: # 如果某种排列的置信度足够大,那么就加入到结果
result[x+(r[i],)] = (confidence, v)
return sorted(result.items(), key=lambda x: -x[1][0]) # 按置信度降序排列
使用方法:
from pprint import pprint
# 测试文件来自 https://kexue.fm/archives/3380
model = Apriori(0.06, 0.75)
pprint(model.find_rules('apriori.txt'))
输出结果:
[(('A3', 'F4', 'H4'), (0.8795180722891566, 0.07849462365591398)),
(('C3', 'F4', 'H4'), (0.875, 0.07526881720430108)),
(('B2', 'F4', 'H4'), (0.7945205479452054, 0.06236559139784946)),
(('C2', 'E3', 'D2'), (0.7543859649122807, 0.09247311827956989)),
(('D2', 'F3', 'H4', 'A2'), (0.7532467532467533, 0.06236559139784946))]
结果的含义是前n-1项推出第n项,也就是A3 + F4 --> H4、 D2 + F3 + H4 --> A2等。
这次的实现相对简洁一点,去掉了Pandas库的依赖,只用到了Numpy库,变量命名也更清晰一些,编程思路没有变化,所以理论上效率不会降低,甚至有可能会提升。应该兼容Python 2.x和3.x,如果有问题欢迎继续指出。
转载到请包括本文地址:https://www.spaces.ac.cn/archives/5525
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (May. 10, 2018). 《用Numpy实现高效的Apriori算法 》[Blog post]. Retrieved from https://www.spaces.ac.cn/archives/5525
@online{kexuefm-5525,
title={用Numpy实现高效的Apriori算法},
author={苏剑林},
year={2018},
month={May},
url={\url{https://www.spaces.ac.cn/archives/5525}},
}
October 21st, 2020
苏神您好!有两个问题想请教一下:
第一个是为什么挖掘出来的关联规则都是右边有1项的形式呢?左右应该都可以有任意多项吧?
第二个是50~51行既然要二重for循环,那sort的意义在哪里呢?