在上篇文章数据挖掘之Apriori频繁项集挖掘中我们用代码手工实现了Apriori算法, 用《数据挖掘概念与技术》中的数据做检验,和书中结果一致。本篇文章， 我们基于一个更大数据集，使用Apriori算法做关于购物篮分析的频繁项集挖掘和关联规则的生成。另外本文在频繁项集挖掘和关联规则生成时,同时使用调包和手工两种方法，以检验手工实现的结果是否正确,并了解学习现成包的用法,后续实际场景使用时肯定是直接调包,不太可能手动将过程全部写一遍。
本文是对《数据挖掘概念与技术》第六章内容的通俗理解和代码实现,更详细的理论知识请参考书中内容, 本文涉及的数据集和完整jupyter代码, 可以在我们的 "数据臭皮匠" 中输入"第六章2" 拿到
一、Apriori频繁项集挖掘
1.数据集介绍：
本文使用到的数据集只有一个文件 【purchase.csv】, 有53704行,13列.但使用到的只有两列,"交易号"和"商品大类" ， 所以我们的目标是看， 购买了一种大类的商品后是否会继续购买其他大类的商品。其中：
① 商品编号代表具体的商品，每个商品都有自己的归类——商品小类和商品大类，商品大类包含商品小类；例如，商品编号为40165961是一款“28x28 厘米灰色煎锅”，其商品小类为141，即Cookware，其商品大类为14，即Cooking
② 表purchase.csv每一行为一个顾客（主卡）购买一种商品（商品编号）的交易记录；
③ POS.ID为店内POS收银机的编号
④ 主卡为会员卡号
⑤ 交易号为一笔交易的唯一编号
⑥ 小票序号该商品在小票上的序号(一个交易号可以对应多个小票序号)
⑦ 其他字段意义明确，不做赘述。
2.手工实现Apriori频繁项集挖掘
刚才说过，之前的文章中我们手工实现了Apriori算法, 但为保持与书中结论一致, 最小支持度使用的是绝对数字, 实际使用中根据相对支持度判断频繁项集的方法更常用, 本文对上篇文章的代码做了优化, 使函数支持相对支持度, 并且为与mlxtend.frequent_pattern.apriori 包的结果展示形式一致, 对结果展示做了加工,具体代码如下:
def aprioriGen(Lk_1, k): #creates Ck
""" 根据k-1项集产生候选k项集
Lk_1: k-1项集的列表
k: k项集的k
"""
retList = []
lenLk_1 = len(Lk_1) # k-1项集的长度
for i in range(lenLk_1):
for j in range(i+1, lenLk_1):
L1 = sorted(list(Lk_1[i])) # k等于2时, 1项集取空, k等于3时,2项集取第一个元素, k等于4时,3项集取前两个元素
L2 = sorted(list(Lk_1[j])) # k等于2时, 1项集取空, k等于3时,2项集取第一个元素, k等于4时,3项集取前两个元素
if L1[:k-2]==L2[:k-2]: # 如果前k减2个元素相等 , 就将两几何求并
retList.append(Lk_1[i] | Lk_1[j]) #set union
return retList
def get_subset(ss):
"""求一个k项集的所有k-1项集子集"""
ls = list(ss)
res = []
for i in range(len(ls)):
res.append(set(ls[:i] + ls[(i+1):]))
return res
def check_in(Lk_1,ck):
""" 返回布尔值,
检验候选k项集的所有k-1项集子集 是否都在L_(k-1)中
"""
i = 0
# 取出候选k项集的一个k-1项集子集
for ss_sub in get_subset(ck):
# 如果该k-1项集子集在在L_(k-1)中, 加1
if ss_sub in Lk_1:
i+= 1
# 返回候选k项集的所有k-1项集子集 是否都在L_(k-1)中
return i == len(ck)
def cut_branch(Ck,Lk_1):
"""剪枝,
只保留候选K项集集合中, 所有k-1项集都在L_(k-1) 的候选k项集
"""
Ck_res = []
# 取出一个候选k项集
for ck in Ck:
# 判断候选k项集的所有k-1项集子集 是否都在L_(k-1)中
flag = check_in(Lk_1,ck)
# 如果是, 保留该候选k项集
if flag :
Ck_res.append(ck)
return Ck_res
def createC1(dataSet):
"""从数据集中构建一项集候选集,
将每个一项集都以frozenset的数据类型保存
因为frozenset可以作为字典的key, 常规的set不可以, 方便后续对候选项集计数
"""
C1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
# frozenset 可以作为字典的key, set 不可以
return [frozenset(i) for i in C1]
def scanD(D, Ck, minSupport):
"""
D:数据集
Ck:候选k项集
minSupport:最小支持度阈值
"""
# 扫描数据集,确定Ck中每个候选的计数
ssCnt = {}
for tid in D:
for can in Ck:
if can.issubset(tid):
ssCnt[can] = ssCnt.get(can,0)+1
# 根据最小支持度阈值筛选出频繁k项集
retList = []
supportData = {}
for key in ssCnt:
# 计算备选k项集的支持度
if (minSupport>0)&(minSupport<=1) :
support = ssCnt[key]/len(D)
else:
support = ssCnt[key]
# 如果支持度大于阈值, insert进k项集的结果列表
if support >= minSupport:
retList.insert(0,key)
# 不管支持度是否大于阈值, 都记录下该备选k项集的支持度
supportData[key] = support
return retList, supportData
def apriori_manul(dataSet, minSupport):
C1 = createC1(dataSet)
# print('C1:',C1)
D = [set(i) for i in dataSet]
# 检查C1中每个备选1项集的支持度, L1为筛选出的1项集, supportData为每个备选1项集的支持度
L1, supportData = scanD(D, C1, minSupport)
# print(f'L1:{L1}','\n')
L = [L1] # 将1项集列表插入频繁k项集的结果列表
k = 2 # 2项集
# k项集为空的时候停止
while (len(L[k-2]) > 0):
Ck = aprioriGen(L[k-2], k) # 连接步,产生备选k项集
# print('过滤前:',len(Ck),Ck,'\n')
Ck = cut_branch(Ck,L[k-2]) # 剪枝
# print('过滤后:',len(Ck),Ck,'\n')
Lk, supK = scanD(D, Ck, minSupport)#scan DB to get Lk 扫描数据集,确认C_k中的每个候选k项集是否为频繁项集
# print('筛选后:',len(Lk),Lk,'\n')
supportData.update(supK)
L.append(Lk)
k += 1
return L, supportData
def trans_data(df):
"""将数据转换成函数需要的样子, 有订单物品组成的元组为一行"""
data_ls = []
for i in range(len(df)):
# 拿出一行数据
ss = df.iloc[i,:]
# 将该行中值为非空的列的名称拿出来, 即该笔订单买的商品大类的清单
ss2 = ss[ss!=0].index.tolist()
data_ls.append(ss2)
return data_ls
def trans_res(L,supportData):
"""将结果转换成跟mlxtend.frequent_patterns.apriori 相同的格式"""
res = {}
# 从supportData中将频繁项集的支持度拿出来
for items in L:
for item in items:
res[item] = supportData[item]
# 调整展示格式
df_res = pd.DataFrame(res,index=[0]).T
df_res.reset_index(inplace=True,drop=False)
df_res.columns = ['itemsets','support']
df_res = df_res[['support','itemsets']]
return df_res
# 读取数据
df = pd.read_csv('purchase.csv',encoding='gbk')
df['times'] = 1
df2 = df.pivot_table(index='交易号',columns='商品大类',values='times').fillna(0).astype('int')
# 手写函数apriori_manul 的结果
data_ls = trans_data(df2)
L,supportData = apriori_manul(data_ls,minSupport=0.6)
df_res =trans_res(L,supportData)
df_res.sort_values('support',inplace=True)
df_res
3.调包实现Apriori的频繁项集挖掘
# 读取数据
df = pd.read_csv('purchase.csv',encoding='gbk')
df['times'] = 1
df2 = df.pivot_table(index='交易号',columns='商品大类',values='times').fillna(0).astype('int')
# 调用mlxtend.frequent_patterns.apriori 结果
frequent_itemsets = apriori(df2,
min_support=0.6,
use_colnames=True,
max_len=None)
frequent_itemsets.sort_values('support',inplace=True)
4.对比结果
可以看到两者的结果完全一致， 均生成了61个频繁项集， 且对应频繁项集的支持度一致
二、根据频繁项集得到关联规则
1.理论部分
一旦找到频繁项集,根据频繁项集得到关联规则就只差简单的一步.规则只要满足最小支持度和最小置信度就称为强规则(即我们需要的结果)
Confidence(A==>B) = P(A|B) = support_count(A U B) / support_count(A)
其中, support_count(A U B)是同时包含项集A,B的行数, support_count(A) 是包含项集A的行数
所以关联规则产生只需两步:
对于每个频繁项集l,产生l的所有非空子集
对于l的每个非空子集s, 如果support_count(l) / support_count(s) >=min_conf , 则输出规则"s-->(l-s)" , 其中min_conf 是最小置信度阈值。(书中的公式为support_count(t) / support_count(s) 应该是有错误)
由于规则从频繁项集产生， 因此每个规则都自动的满足最小支持度，这里只要再计算是否大于最小阈值，即可知道能否产生新的关联规则。
2.手工实现挖掘关联规则
# 找出频繁项集的所有子集
def find_sub_set(ss):
"""找出一个集合的所有非空真子集"""
if len(ss)==1:
return [ss,]
res = []
# 找到ss的所有k-1项的子集合
ls_sub = get_subset(ss)
res.extend(ls_sub)
# 递归调用自身, 直到集合的长度为1
for s_sub in ls_sub:
res_sub = find_sub_set(s_sub)
# 将res中没有的集合append进结果列表
res.extend([i for i in res_sub if i not in res])
return res
def gene_rules(ss,supportData,min_conf):
"""由频繁项集生成关联规则"""
res = []
# 如果是频繁1项集， 直接返回空list
if len(ss)==1:
return res
# 找到该频繁项集的所有非空子集
sub_sets = find_sub_set(ss)
# 将集合转换为frozenset， 因为frozenset可以作为字典的key
sub_sets = [frozenset(i) for i in sub_sets]
for sub_set in sub_sets:
# 计算subset -->(ss-subset) 的置信度
support_ss = supportData.get(ss,0)
suport_subset = supportData.get(sub_set,np.inf)
confidence = support_ss/suport_subset
# 如果置信度大于最小支持度,就留下该条规则
if confidence > min_conf:
res.append([sub_set,ss-sub_set,confidence])
return res
res = []
# 将df_res 中的频繁项集, 一个一个按出来,生成关联规则
for i in range(len(df_res)):
ss = df_res.iloc[i,1]
rules = gene_rules(ss,supportData,min_conf=0.5)
res.extend(rules)
df_rules = pd.DataFrame(res,columns=['antecedents','consequents','confidence'])
3.调包实现挖掘关联规则
association_rule = association_rules(
frequent_itemsets,
metric='confidence',
min_threshold=0.5)
association_rule.sort_values(
by='confidence',
ascending=False,
inplace=True)
4.对比结果
三、使用书中数据挖掘关联规则
构造书中数据后, 直接调用上文已定义的函数, 产生关联规则, 可以看到, 结果与书中完全一致
# 构造书中数据
data_ls =[['I1','I2','I5'],
['I2','I4'],
['I2','I3'],
['I1','I2','I4'],
['I1','I3'],
['I2','I3'],
['I1','I3'],
['I1','I2','I3','I5'],
['I1','I2','I3']]
# 产生频繁项集和每个项集的支持度
L, supportData =apriori_manul(data_ls,minSupport = 2)
df_res =trans_res(L,supportData)
# 根据频繁项集得到关联规则
res = []
for i in range(len(df_res)):
ss = df_res.iloc[i,1]
rules = gene_rules(ss,supportData,min_conf=0.1)
res.extend(rules)
df_rules = pd.DataFrame(res,columns=['antecedents','consequents','confidence'])
df_rules.sort_values('antecedents')
四、Ending
从上文可以看到， 调包实现的代码量非常少，且能够完美实现Apriori算法， 后续实际应用时笔者更可能直接调包实现， 但笔者认为，如果能自己实现一遍Apriori，是非常有意义的，它让我们更加了解技术细节，同时更能总结出算法的优缺点。
更多精彩内容，请关注：数据臭皮匠 共中号
参考资料:
数据和分析思路来自文章: 《机器学习｜关联规则与购物篮分析实战》
算法原理来自: 《数据挖掘概念与技术》 第六章
作者：范小匠
审核：灰灰匠
编辑：森匠
