文章目录
关联规则挖掘过程Apriori算法1. Apriori算法的基本思想2. Apriori算法产生频繁项集的过程3. Apriori算法的主要步骤4. 举例及代码实现关联规则挖掘过程
关联规则挖掘问题可以分解为以下两个子问题
找频繁项集
找出事务集T中所有大于或等于用户指定最小支持度的项集，即频繁项集。（项集的支持度可简单用包含该项集的事务数来表示）利用频繁项集生成所需要的关联规则
对每一频繁项集A，找到A的所有非空子集a，如果support(A) / support(a) >= min_confidence，则a=>（A-a）称为强关联规则。
Apriori算法
通过对数据库的多次扫描来计算项集的支持度，并发现所有的频繁项集从而生成关联规则。1. Apriori算法的基本思想
对数据集进行多次扫描，第一次扫描得到频繁1-项集的集合L1，第k次扫描首先利用第k-1次扫描的结果Lk-1产生候选k-项集Ck，在扫描过程中计算Ck的支持度，在扫描结束后计算频繁k-项集Lk，算法当候选k-项集的集合Ck为空的时候结束。
2. Apriori算法产生频繁项集的过程
（1）连接步 （2）剪枝步
3. Apriori算法的主要步骤
（1） 扫描全部数据，产生候选1-项集的集合C1
（2） 根据最小支持度，由候选1-项集的集合C1产生频繁1-项集的集合L1
（3） 对k>1，重复步骤（4）（5）（6）
（4） 由Lk执行连接和剪枝操作，产生候选（k+1）-项集Ck+1
（5） 根据最小支持度，由候选（k+1）-项集的集合Ck+1产生频繁（k+1）-项集的集合Lk+1
（6） 若L不为空集，则k = k+1，跳往步骤（4），否则跳往步骤（7）
（7） 根据最小置信度，由频繁项集产生强关联规则
4. 举例及代码实现
举例
实现
def load_data_set():"""加载事务集"""data_set = [['l1','l2','l5'],['l2','l4'],['l2','l3'],['l1','l2','l4'],['l1','l3'],['l2','l3'],['l1','l3'],['l1','l2','l3','l5'],['l1','l2','l3']]#data_set = [['l1', 'l2'], ['l1', 'l3', 'l4', 'l5'], ['l2', 'l3', 'l4', 'l6'],# ['l1', 'l2', 'l3', 'l4'], ['l1', 'l2', 'l3','l6']]return data_setdef create_C1(data_set):"""遍历事务集获得候选1-项集C1"""C1 = set() # 集合对象for t in data_set:for item in t:# 将事务集中的每个项集的项转换为不可变的集合item_set = frozenset([item])# print(item_set)C1.add(item_set)return C1def is_apriori(Ck_item,Lksub1):"""对候选k-项集Ck中的每个项进行剪枝判断"""for item in Ck_item:sub_Ck = Ck_item - frozenset([item])if sub_Ck not in Lksub1: # 候选k-项集中的项的子集中存在于非频繁k-1 -项集中return False # 则该项在非频繁k-项集中return Truedef create_Ck(Lksub1,k):"""通过Lk-1的连接运算构建候选k-项集Ck，k应该大于2Lksub1：Lk-1，频繁k-1 -项集"""Ck = set()list_Lksub1 = list(Lksub1)for i in range(len(Lksub1)):for j in range(1,len(Lksub1)):l1 = list(list_Lksub1[i])l2 = list(list_Lksub1[j])l1.sort()l2.sort()if l1[0:k-2] == l2[0:k-2]: # 排序后做连接运算Ck_item = list_Lksub1[i] | list_Lksub1[j]if is_apriori(Ck_item,Lksub1): # 判断是否应该剪枝，是则不加入频繁k-项集Ck.add(Ck_item)return Ckdef generate_Lk_by_Ck(data_set,Ck,min_support,support_data):"""在Ck中执行删除操作，生成频繁k-项集Lksupport_data: 频繁k-项集对应的支持度"""Lk = set()item_count = {}for t in data_set:for item in Ck: # 对Ck中的每个项计算支持度计数if item.issubset(t):if item in item_count:item_count[item] += 1else:item_count[item] = 1t_num = float(len(data_set)) for item in item_count: # 计算每个项的支持度if(item_count[item]/t_num >= min_support): # 和最小支持度进行比较判断是否为频繁项Lk.add(item)support_data[item] = item_count[item] / t_num return Lkdef generate_L(data_set,min_support):"""计算所有的频繁项集"""support_data = {}C1 = create_C1(data_set)L1 = generate_Lk_by_Ck(data_set,C1,min_support,support_data) # 单独计算C1和L1Lksub1 = L1.copy()L = []L.append(Lksub1)i = 2while(True): # 计算CkCi = create_Ck(Lksub1,i)Li = generate_Lk_by_Ck(data_set,Ci,min_support,support_data)if len(Li) == 0: # 当Li为空集时退出循环break;Lksub1 = Li.copy()L.append(Lksub1)i+=1return L,support_datadef generate_big_rules(L,support_data,min_conf):"""找出满足最小置信度的频繁项集"""big_rules_list = [] # 强关联规则的列表sub_set_list = [] # 子集列表for i in range(0,len(L)): # 对于每个频繁项要产生其非空子集并计算置信度，大于最小置信度则将该强关联规则加入强关联规则的列表中for freq_set in L[i]: # 频繁1项集里没有强关联for sub_set in sub_set_list: # 频繁项集的子集一定也是频繁项集if(sub_set.issubset(freq_set)): # 遍历生成频繁项集freq_set的每个子集conf = support_data[freq_set] / support_data[sub_set]big_rule = (sub_set,freq_set - sub_set,conf)if conf >= min_conf and big_rule not in big_rules_list:big_rules_list.append(big_rule)sub_set_list.append(freq_set) # 频繁项集本身也是其子集return big_rules_listif __name__ == "__main__":data_set = load_data_set()L,support_data = generate_L(data_set,min_support=2/9)big_rules_list = generate_big_rules(L,support_data,min_conf=0.7)# 输出for Lk in L:print("="*50)print("frequent " + str(len(list(Lk)[0])) + "-itemsets\tsupport")print("="*50)for freq_set in Lk:print(freq_set,support_data[freq_set])print("Big Rules：")for item in big_rules_list:print(item[0],"==>",item[1]," conf:",item[2])
运行结果
实现参考：Apriori算法介绍（Python实现）
