先验原则
简单地说，先验原则是指，如果某个项集出现得不频繁，那么包含它的任何更大的项集必定也出现得不频繁。这就是说，如果{啤酒}是非频繁项集，那么{啤酒，比萨}也必定是非频繁项集。因此，在整理频繁项集列表时，既不需要考虑{啤酒，比萨}，也不需要考虑其他任何包含啤酒的项集。
随后就会引入最小支持度和最小置信度的概念
步骤1：列出只包含一个元素的项集，比如{苹果}和{梨}。
步骤2：计算每个项集的支持度，保留那些满足最小支持度阈值条件的项集，淘汰不满足的项集。
步骤3：向候选项集(淘汰步骤2不满足的项集后的结果）中增加一个元素，并利用在步骤2中保留下来的项集产生所有可能的组合。
步骤4：重复步骤2和步骤3，为越来越大的项集确定支持度，直到没有待检查的新项集。
举个例子，假设我们的任务是找到具有高置信度的关联规则。如果{啤酒，薯片→苹果}规则的置信度很低，那么所有包含相同元素并且箭头右侧有苹果的规则都有很低的置信度，包括{啤酒→苹果，薯片}和{薯片→苹果，啤酒}。如前所述，根据先验原则，这些置信度较低的规则会被移除。这样一来，待检查的候选规则就更少了。
这样对计算的复杂度和效率就会有很大的提升空间
实际案例
🍝下面给出一个具体的关联规则的案例🍝
代码实战
频繁项集和支持度
from numpy import * # 构造数据 def loadDataSet(): return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]] # 将所有元素转换为frozenset型字典，存放到列表中 def createC1(dataSet): C1 = [] for transaction in dataSet: for item in transaction: if not [item] in C1: C1.append([item]) C1.sort() # 使用frozenset是为了后面可以将这些值作为字典的键 return list(map(frozenset, C1)) # frozenset一种不可变的集合，set可变集合 # 过滤掉不符合支持度的集合 # 返回 频繁项集列表retList 所有元素的支持度字典 def scanD(D, Ck, minSupport): ssCnt = {} for tid in D: for can in Ck: if can.issubset(tid): # 判断can是否是tid的《子集》 （这里使用子集的方式来判断两者的关系） if can not in ssCnt: # 统计该值在整个记录中满足子集的次数（以字典的形式记录，frozenset为键） ssCnt[can] = 1 else: ssCnt[can] += 1 numItems = float(len(D)) retList = [] # 重新记录满足条件的数据值（即支持度大于阈值的数据） supportData = {} # 每个数据值的支持度 for key in ssCnt: support = ssCnt[key] / numItems if support >= minSupport: retList.insert(0, key) supportData[key] = support return retList, supportData # 排除不符合支持度元素后的元素 每个元素支持度 # 生成所有可以组合的集合 # 频繁项集列表Lk 项集元素个数k [frozenset({2, 3}), frozenset({3, 5})] -> [frozenset({2, 3, 5})] def aprioriGen(Lk, k): retList = [] lenLk = len(Lk) for i in range(lenLk): # 两层循环比较Lk中的每个元素与其它元素 for j in range(i+1, lenLk): L1 = list(Lk[i])[:k-2] # 将集合转为list后取值 L2 = list(Lk[j])[:k-2] L1.sort(); L2.sort() # 这里说明一下：该函数每次比较两个list的前k-2个元素，如果相同则求并集得到k个元素的集合 if L1==L2: retList.append(Lk[i] | Lk[j]) # 求并集 return retList # 返回频繁项集列表Ck # 封装所有步骤的函数 # 返回 所有满足大于阈值的组合 集合支持度列表 def apriori(dataSet, minSupport = 0.5): D = list(map(set, dataSet)) # 转换列表记录为字典 [{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}] C1 = createC1(dataSet) # 将每个元素转会为frozenset字典 [frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})] L1, supportData = scanD(D, C1, minSupport) # 过滤数据 L = [L1] k = 2 while (len(L[k-2]) > 0): # 若仍有满足支持度的集合则继续做关联分析 Ck = aprioriGen(L[k-2], k) # Ck候选频繁项集 Lk, supK = scanD(D, Ck, minSupport) # Lk频繁项集 supportData.update(supK) # 更新字典（把新出现的集合:支持度加入到supportData中） L.append(Lk) k += 1 # 每次新组合的元素都只增加了一个，所以k也+1（k表示元素个数） return L, supportData dataSet = loadDataSet() L,suppData = apriori(dataSet) print(L) print(suppData)
也可以直接调用包：
from efficient_apriori import apriori # 挖掘频繁项集和频繁规则 itemsets, rules = apriori(transactions, min_support=0.5, min_confidence=1) print("频繁项集：", itemsets) print("关联规则：", rules)
置信度调用
#!/usr/bin/python # -*- coding:utf-8 -*- from itertools import combinations #读取数据 def readdata(filename): data = [] with open(filename, 'r') as f: while True: line = f.readline() if not line: break data.append([int(_) for _ in line.split()]) return data def subtract_item_set(pre_discard_itemset, candidate_set): ''' 首先去除候选集中不符合非频繁项集的那些元素， 在当前候选集中去掉上一轮删除的项集， 比如{2, 3}是非频繁项集，那么就将删除candidate_set中的{2, 3, x}这些项集 Parameters: ----------- pre_discard_itemset: 上一轮删除的项集 candidate_set: 上一次产生的候选集 Returns: -------- 返回经过pre_discard_itemset筛选后的项集列表 ''' saved_item_set = set() discard_item_set = set() for item in candidate_set: is_discard = False for d_item in pre_discard_itemset: if d_item.issubset(item): is_discard = True if is_discard: discard_item_set.add(tuple(item)) else: saved_item_set.add(tuple(item)) # saved_item_set, discard_item_set return [set(i) for i in saved_item_set], [set(i) for i in discard_item_set] def scan_data_set(data_set, candidate_set, min_support): ''' 扫描一遍数据集，从候选集中挑出满足支持度的频繁项集， 同时记录每个项集的支持度（供后面置信度计算） ''' data_set = [set(i) for i in data_set] data_set_size = len(data_set) candidate_set_size = len(candidate_set) cand_set_count = [0 for i in range(candidate_set_size)] # 对候选集中的元素通过遍历数据集得到他们出现的次数 for i in range(candidate_set_size): for ds in data_set: if candidate_set[i].issubset(ds): cand_set_count[i] += 1 saved_item_set = [] discard_item_set = [] support_data = [] # 删除不满足支持度的 for i in range(candidate_set_size): support = cand_set_count[i] * 1.0 / data_set_size if support >= min_support: saved_item_set.append(candidate_set[i]) support_data.append(support) else: discard_item_set.append(candidate_set[i]) return saved_item_set, discard_item_set, support_data def gen_cand_set(data_set, previous_freq_set, k): ''' 从上一次生成的候选集中产生本次的候选集（未经过支持度筛选处理的）， 只是单纯生成下一轮的组合集 Parameters: ----------- data_set: 数据集，用以生成k为1的项集 previous_freq_set: 上一次产生的候选集 k: 本次产生的候选集中项目的大小 Returns: -------- 返回列表存储的项集，每个项集是一个集合set, [{0}, {1}, {2}, {3}, {4}...] ''' if k == 1: # 列表解析 item_set = set([item for sublist in data_set for item in sublist]) # 或者item_set = set(sum(data_set, [])) return [set([i]) for i in item_set] elif k > 1: cur_freq_set = set() pre_fre_set_len = len(previous_freq_set) for i in range(pre_fre_set_len): for j in range(i + 1, pre_fre_set_len): # 遍历所有的两两组合，并将其加入到集合中 # {(1, 2, 3), (1, 3, 5), (2, 3, 4)} s = previous_freq_set[i] | previous_freq_set[j] if len(s) == k: cur_freq_set.add(tuple(s)) return [set(i) for i in cur_freq_set] def gen_frequecy_set(data_set, min_support): ''' 生成频繁项集 Returns: -------- freq_item_set: [[set(item1), set(item2)..]...] 存储频繁项集 item_set_support: [[support_score1, s_score2..]] 每个项集对应的支持度分值 ''' freq_item_set = [] item_set_support = [] discard_item_set = None cur_dis_item_set_1, cur_dis_item_set_2 = [], [] cur_item_set_size = 0 while True: # 循环产生项集大小为1, 2...的项集 cur_item_set_size += 1 if cur_item_set_size == 1: # 产生初始的候选集 cur_candiate_set = gen_cand_set(data_set, [], cur_item_set_size) # 将候选集分成要满足支持度的集合和不满足支持度的集合，同时记录满足支持度集合对应的支持度分值 saved_item_set, cur_dis_item_set_1, support_data = scan_data_set(data_set, cur_candiate_set, min_support) else: # 生成该轮候选集 cur_candiate_set = gen_cand_set(data_set, freq_item_set[-1], cur_item_set_size) # 去除候选集中不符合非频繁项集的那些元素 cur_candiate_set, cur_dis_item_set_1 = subtract_item_set(discard_item_set, cur_candiate_set) # 对剩下的候选集，进行遍历数据集，得到保存、丢弃、支持度集合 saved_item_set, cur_dis_item_set_2, support_data = scan_data_set(data_set, cur_candiate_set, min_support) if saved_item_set == []: # 如果该轮没有产生任何频繁项集，则下一轮也不会产生新的频繁项集了，退出 break freq_item_set.append(saved_item_set) # freq_item_set存储每一轮产生的频繁项集 discard_item_set = cur_dis_item_set_1 # discard_item_set存储每一轮产生的要丢弃的项集 discard_item_set.extend(cur_dis_item_set_2) item_set_support.append(support_data) # item_set_support存储每一轮产生的频繁项集对应的支持度值 return freq_item_set, item_set_support def gen_association_rules(freq_item_set, support_data, min_confd): ''' 生成关联规则 Returns: -------- association_rules: [(set(item1, item2, ...), itemx, confidence_score), ..] 存储关联规则，list存储，每个元素都是一个3元组，分别表示item1 和 item2.. 推出 itemx，置信度为confidence_score ''' association_rules = [] for i in range(1, len(freq_item_set)): for freq_item in freq_item_set[i]: # 对频繁项集的每一项尝试生成关联规则 gen_rules(freq_item, support_data, min_confd, association_rules) return association_rules def gen_rules(freq_item, support_data, min_confd, association_rules): ''' 生成关联规则，然后存储到association_rules中 ''' if len(freq_item) >= 2: # 遍历二阶及以上的频繁项集 for i in range(1, len(freq_item)): # 生成多种关联规则 for item in combinations(freq_item, i): # 遍历长度为1的item的组合 conf = support_data[frozenset(freq_item)] / float(support_data[frozenset(freq_item) - frozenset(item)]) if conf >= min_confd: association_rules.append((freq_item - set(item), item, conf)) gen_rules(freq_item - set(item), support_data, min_confd, association_rules) def support_map(freq_item_set, item_set_support): ''' 将生成的频繁项集和每个项集对应的支持度对应起来 Returns: -------- support_data: {frozenset(item1, item2..): support_score, ..} ''' support_data = {} for i in range(len(freq_item_set)): for j in range(len(freq_item_set[i])): support_data[frozenset(freq_item_set[i][j])] = item_set_support[i][j] return support_data def apriori_gen_rules(data_set, min_support, min_confd): ''' 利用apriori算法生成关联规则分为两步： Step1：生成频繁项集 Step2：生成关联规则 Parameters: ----------- data_set: item list min_support: 项集需要满足的最小支持度，|X U Y| / |All| min_confd: 项集之间关系需要满足的最小置信度，|X U Y| / |X| Returns: -------- rules: 通过apriori算法挖掘出的关联规则 ''' freq_item_set, item_set_support = gen_frequecy_set(data_set, min_support) # 利用Apriori算法生成频繁项集和对应的支持度 support_data = support_map(freq_item_set, item_set_support) # 将频繁项集和支持度联系起来 rules = gen_association_rules(freq_item_set, support_data, min_confd) # 利用频繁项集、对应的支持度和置信度生成关联规则 return rules if __name__ == '__main__': data_set = readdata("DATA.txt") min_support = 0.2 # 最小支持度 min_confd = 0.4 # 可信度或支持度 rules = apriori_gen_rules(data_set=data_set, min_support=min_support, min_confd=min_confd) print(sorted(rules, key=lambda x: x[2], reverse=True))
