关联规则挖掘算法: Aprior算法和Fpgrowth算法
关联规则挖掘的目的是挖掘不同物品(item)之前的相关性，啤酒和尿布的故事就是一个典型的成功例子。关联规则挖掘思想简单高效，在广告推荐领域也有较多的应用，主要用于推荐模型落地前的流量探索以及构建规则引擎探寻高价值流量等。本文主要介绍关联规则挖掘常用的两种算法，即Aprior算法和Fpgrowth算法。
正式开始介绍这两种算法前，先简单讲述一下关联规则挖掘常用的几个概念。
a: 几个重要的概念
- 支持度: 某个物品组合出现的次数与总次数的比例；
- 置信度: 表示A物品出现时，会有多大的概率出现B，假如物品A出现了Na次，AB同时出现了Nab次，那么置信度（A–>B）=Nab/Na
- 提升度: 物品A出现对物品B出现概率的提升程度，也就是B在A集合中出现的概率与B在整体集合出现概率的比值，提升度 (A→B)= 置信度 (A→B)/ 支持度 (B)。
a. 提升度 (A→B)>1：代表有提升; 正向规则
b. 提升度 (A→B)=1：代表有没有提升，也没有下降; 无效规则
c. 提升度 (A→B)<1：代表有下降; 负向规则
Apriori算法
Apriori算法的原理一言以蔽之，就是不断查找频繁项集的过程，而频繁项集就是我们需要界定的参数，我们界定一个支持度阈值S，当该物品组合的出现频率高于S时，我们认为该物品组合为频繁项集，对小于S的物品组合算法会忽略。
搞清楚频繁项集的含义之后，Apriori算法的实现原理就非常简单了，这里在介绍一个补充概念，规则包括的物品数量n，大致如下：
- 当n=1时，计算每一个物品的支持度Si1，保留Si1>S的物品集合F1;
- 当n=2时，将F1中的物品两两组合，计算每个组合的支持度Si2，保留Si2>S的物品集合F2;
- 当n=3时，将F2中的物品两两组合（组合后去重），仅保留长度为3的组合，计算每个组合的支持度Si3，保留Si3>S的物品集合F3;
- …以此类推，直到Fn集合为空;
如果某个物品的支持度不满足阈值，那么其任一两两组合也必不能满足条件；同理，如果某两两组合的支持度不满足阈值，那么其构成的任一三物品组合也必不能满足条件。这就是可以将每一次计算的结果建立在上一次结果的基础上的原因，大大减少计算量。
Apriori算法的python包很多，这里不给源码了，调用代码如下:
from efficient_apriori import apriori
data = [
('牛奶', '面包'),
('牛奶', '面包', '火腿'),
('面包', '火腿', '可乐'),
('火腿', '可乐', '方便面'),
('面包', '火腿', '可乐', '方便面')
]
itemsets, rules = apriori(data, min_support=0.6, min_confidence=0.3, verbosity=0)
print(itemsets, rules)
- 该包的调用结果不显示支持度的信息，需要修改源码，这里省略该过程。
- 程序运行结果如下:
({1: {('面包',): 4, ('火腿',): 4, ('可乐',): 3},
2: {('可乐', '火腿'): 3, ('火腿', '面包'): 3}},
[{火腿} -> {可乐} (conf: 0.750, supp: 0.600, lift: 1.250, conv: 1.600),
{可乐} -> {火腿} (conf: 1.000, supp: 0.600, lift: 1.250, conv: 200000000.000),
{面包} -> {火腿} (conf: 0.750, supp: 0.600, lift: 0.938, conv: 0.800),
{火腿} -> {面包} (conf: 0.750, supp: 0.600, lift: 0.938, conv: 0.800)])
- conf: 置信度，supp: 支持度，lift: 提升度。
- conv(A—>B)表示，B物品在总集合中不出现的概率与B物品在A存在集合中不出现概率的比值。
Fp-growth算法
Fp-growth算法是Apriori算法的改进版本，本质上没啥区别。Fp-growth算法的原理很简单，该算法使用了一种称为频繁模式树的数据结构。FP-tree是一种特殊的前缀树，由频繁项头表和项前缀树构成，大致过程如下:
- 扫描数据库一遍.得到频繁项的集合F和每个频繁项的支持度.把F按支持度递降排序,结果记为L(A-val=6、B-val=5、C-val=4、D-val=4)（有序的F1）.
- 创建FP-tree的根节点,记为T,并且标记为’root’，然后L的每项做如下的步骤:
a. 根据L中的顺序，将A作为第一个节点，在数据库中扫描，如果出现AB，那么从A延伸出一个节点B，B对应的val+1（val初始为0），如果出现AC，那么从A延伸出一个节点C，C对应的val+1；
b. 从A节点的子节点B出发，假如出现ABC，从那么从B延伸出一个节点C，C对应的val+1；
c. …以此类推，直到该路径对应子节点不在满足条件（支持度阈值）;
Fp-growth算法的原理相对比较复杂，开源的python包比较少，这里附上对应的源码:
# -*- coding: utf-8 -*-
from tqdm import tqdm
import time
import psutil
import os
def load_data(): # 根据路径加载数据集
ans = [] # 将数据保存到该数组
reader = [
('牛奶', '面包'),
('牛奶', '面包', '火腿'),
('面包', '火腿', '可乐'),
('火腿', '可乐', '方便面'),
('面包', '火腿', '可乐', '方便面')
]
for row in reader:
row = list(set(row)) # 去重，排序
row.sort()
ans.append(row) # 将添加好的数据添加到数组
return ans # 返回处理好的数据集，为二维数组
def show_confidence(rule):
index = 1
for item in rule:
s = " {:<4d} {:.3f} {}=>{}".format(index, item[2], str(list(item[0])), str(list(item[1])))
index += 1
print(s)
class Node:
def __init__(self, node_name, count, parentNode):
self.name = node_name
self.count = count
self.nodeLink = None # 根据nideLink可以找到整棵树中所有nodename一样的节点
self.parent = parentNode # 父亲节点
self.children = {} # 子节点{节点名字:节点地址}
class Fp_growth_plus():
def data_compress(self, data_set):
data_dic = {}
for i in data_set:
if frozenset(i) not in data_dic:
data_dic[frozenset(i)] = 1
else:
data_dic[frozenset(i)] += 1
return data_dic
def update_header(self, node, targetNode): # 更新headertable中的node节点形成的链表
while node.nodeLink != None:
node = node.nodeLink
node.nodeLink = targetNode
def update_fptree(self, items, count, node, headerTable): # 用于更新fptree
if items[0] in node.children:
# 判断items的第一个结点是否已作为子结点
node.children[items[0]].count += count
else:
# 创建新的分支
node.children[items[0]] = Node(items[0], count, node)
# 更新相应频繁项集的链表，往后添加
if headerTable[items[0]][1] == None:
headerTable[items[0]][1] = node.children[items[0]]
else:
self.update_header(headerTable[items[0]][1], node.children[items[0]])
# 递归
if len(items) > 1:
self.update_fptree(items[1:], count, node.children[items[0]], headerTable)
def create_fptree(self, data_dic, min_support, flag=False): # 建树主函数
item_count = {} # 统计各项出现次数
for t in data_dic: # 第一次遍历，得到频繁一项集
for item in t:
if item not in item_count:
item_count[item] = data_dic[t]
else:
item_count[item] += data_dic[t]
headerTable = {}
for k in item_count: # 剔除不满足最小支持度的项
if item_count[k] >= min_support:
headerTable[k] = item_count[k]
freqItemSet = set(headerTable.keys()) # 满足最小支持度的频繁项集
if len(freqItemSet) == 0:
return None, None
for k in headerTable:
headerTable[k] = [headerTable[k], None] # element: [count, node]
tree_header = Node('head node', 1, None)
if flag:
ite = tqdm(data_dic)
else:
ite = data_dic
for t in ite: # 第二次遍历，建树
localD = {}
for item in t:
if item in freqItemSet: # 过滤，只取该样本中满足最小支持度的频繁项
localD[item] = headerTable[item][0] # element : count
if len(localD) > 0:
# 根据全局频数从大到小对单样本排序
order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
# 用过滤且排序后的样本更新树
self.update_fptree(order_item, data_dic[t], tree_header, headerTable)
return tree_header, headerTable
def find_path(self, node, nodepath):
'''
递归将node的父节点添加到路径
'''
if node.parent != None:
nodepath.append(node.parent.name)
self.find_path(node.parent, nodepath)
def find_cond_pattern_base(self, node_name, headerTable):
'''
根据节点名字，找出所有条件模式基
'''
treeNode = headerTable[node_name][1]
cond_pat_base = {} # 保存所有条件模式基
while treeNode != None:
nodepath = []
self.find_path(treeNode, nodepath)
if len(nodepath) > 1:
cond_pat_base[frozenset(nodepath[:-1])] = treeNode.count
treeNode = treeNode.nodeLink
return cond_pat_base
def create_cond_fptree(self, headerTable, min_support, temp, freq_items, support_data):
# 最开始的频繁项集是headerTable中的各元素
freqs = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])] # 根据频繁项的总频次排序
for freq in freqs: # 对每个频繁项
freq_set = temp.copy()
freq_set.add(freq)
freq_items.add(frozenset(freq_set))
if frozenset(freq_set) not in support_data: # 检查该频繁项是否在support_data中
support_data[frozenset(freq_set)] = headerTable[freq][0]
else:
support_data[frozenset(freq_set)] += headerTable[freq][0]
cond_pat_base = self.find_cond_pattern_base(freq, headerTable) # 寻找到所有条件模式基
# 创建条件模式树
cond_tree, cur_headtable = self.create_fptree(cond_pat_base, min_support)
if cur_headtable != None:
self.create_cond_fptree(cur_headtable, min_support, freq_set, freq_items, support_data) # 递归挖掘条件FP树
def generate_L(self, data_set, min_support):
data_dic = self.data_compress(data_set)
freqItemSet = set()
support_data = {}
tree_header, headerTable = self.create_fptree(data_dic, min_support, flag=True) # 创建数据集的fptree
# 创建各频繁一项的fptree，并挖掘频繁项并保存支持度计数
self.create_cond_fptree(headerTable, min_support, set(), freqItemSet, support_data)
max_l = 0
for i in freqItemSet: # 将频繁项根据大小保存到指定的容器L中
if len(i) > max_l: max_l = len(i)
L = [set() for _ in range(max_l)]
for i in freqItemSet:
L[len(i) - 1].add(i)
for i in range(len(L)):
print("frequent item {}:{}".format(i + 1, L[i]))
return L, support_data
def generate_R(self, data_set, min_support, min_conf):
L, support_data = self.generate_L(data_set, min_support)
rule_list = []
sub_set_list = []
for i in range(0, len(L)):
for freq_set in L[i]:
for sub_set in sub_set_list:
if sub_set.issubset(
freq_set) and freq_set - sub_set in support_data: # and freq_set-sub_set in support_data
conf = support_data[freq_set] / support_data[freq_set - sub_set]
big_rule = (freq_set - sub_set, sub_set, conf)
if conf >= min_conf and big_rule not in rule_list:
rule_list.append(big_rule)
sub_set_list.append(freq_set)
rule_list = sorted(rule_list, key=lambda x: (x[2]), reverse=True)
return rule_list
if __name__ == "__main__":
begin_time = time.time()
min_support = 3 # 最小支持度，不是比率，是出现次数
min_conf = 0.2 # 最小置信度
data_set = load_data()
print(data_set)
fp = Fp_growth_plus()
rule_list = fp.generate_R(data_set, min_support, min_conf)
print("confidence:")
show_confidence(rule_list)
end_time = time.time()
timeget = end_time - begin_time
print("程序开始时间:",begin_time)
print("程序结束时间：",end_time)
print("程序花费时间：",timeget)
print(u'当前进程的内存使用：%.4f GB' % (psutil.Process(os.getpid()).memory_info().rss / 1024 / 1024 / 1024))
- 程序运行结果如下:
[['牛奶', '面包'], ['火腿', '牛奶', '面包'], ['可乐', '火腿', '面包'], ['可乐', '方便面', '火腿'], ['可乐', '方便面', '火腿', '面包']]
100%|██████████████████████████████████████████| 5/5 [00:00<00:00, 46294.75it/s]
frequent item 1:{frozenset({'可乐'}), frozenset({'面包'}), frozenset({'火腿'})}
frequent item 2:{frozenset({'火腿', '可乐'}), frozenset({'火腿', '面包'})}
confidence:
1 1.000 ['可乐']=>['火腿']
2 0.750 ['火腿']=>['可乐']
3 0.750 ['火腿']=>['面包']
4 0.750 ['面包']=>['火腿']
程序开始时间: 1671694715.27943
程序结束时间： 1671694715.282612
程序花费时间： 0.0031821727752685547
当前进程的内存使用：0.0648 GB
- 参考文章: Fp-growth算法python实现