机器学习-Apriori算法

机器学习一Apriori算法一、基本原理手机微信关注公众号：datadw学习数据挖掘，研究大数据，关注你想了解的，分享你需要的。关联分析(associationanalysis)就是从大规模数据集中寻找物品间的隐含关系。这里的主要问题是，寻找物品的不同组合是一项十分耗时的任务，所需计算代价很高，蛮力搜索方法并不能解决这个问题，所以需要用更智能的方法在合理的时间内找到频繁项集。Apriori算法正是基于该原理得到的关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系分为两种形式：频繁项集和关联规则。频繁项集(frequentitemsets)是经常出现在一起的物品的集合。其中频繁的概念可以用支持度来定义。支持度(support)被定义为数据集中包含该项集的记录所占的比例，保留满足最小支持度的项集。关联规则(associationrules)暗示两种物品之间可能存在很强的关系。关联的概念可用置信度或可信度来定义。我们的目标是找到经常在一起购买的物品集合，通过使用集合的支持度来度量其出现的频率。一个集合的支持度是指有多少比例的交易记录包含该集合。假如有N种物品，那么这些物品就有2AN-1种项集组合。即使只出售100种物品，它们之间的组合数对于现有的计算机也是吃不消的。为了降低这种复杂度，有人提出了Apriori算法。Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。反过来，如果某一项集是非频繁集，那么它的所有超集（包含该集的集合）也是非频繁的。二、算法流程对数据集的每条交易记录transaction对每个候选项集can：检查一下can是否是transaction的子集：如果是，则增加can的计数值对每个候选项集：如果其支持度不低于最小值，则保留该项集返回所有频繁项集列表三、算法的特点优点：易编码实现缺点：在大规模数据集上可能较慢。适用数据范围：数值型或标称型。四、python代码实现1、创建简单数据集##############################功能：创建一个简单的测试数据集#说明：数字1、2、3、4、5代表物品1、、、物品5，#每个子集代表顾客的交易记录#输入变量：空#输出变量：数据集#############################defload_data_set():return[[1,3,4],[2,3,5],[1,2,3,5],[2,5]]2、创建大小为1的不重复项集###################################功能：构建一个大小为1的不重复候选项集#输入变量：测试数据集#输出变量：候选项集合#############################defcreate_c1(data_set):cl=[]fortransactionindata_set:#遍历数据集中所有的交易记录foritemintransaction:#遍历每条记录的每一项if[item]notinc1:#如果该物品没有在cl中c1.append([item])c1.sort()set和frozenset皆为无序唯一值序列。set和frozenset最本质的区别是前者是可变的、后者是不可变的。frozenset的不变性，可以作为字典的键值使用。returnmap(frozenset,c1)3、保留满足最小支持度的项集#####################################功能：扫描候选集集合，把支持度大于最小支持度的元素留下来,#通过去掉小于支持度的元素，可以减少后面查找的工作量。#输入变量：数据集，候选项集列表，最小支持度#data_set,ck,min_support#输出变量：大于最小支持度的元素列表，包含支持度的字典#ret_list,support_data####################################defscan_d(data_set,ck,min_support):D=map(set,data_set)ss_cnt={}fortidinD:#遍历数据集中所有交易forcaninck:#遍历候选项集#判断候选集中该集合是数据集中交易记录的子集#set().issubset()判断是否是其子集ifcan.issubset(tid):#判断该集合是否在空字典ss_cntifcannotinss_cnt.keys():ss_cnt[can]=1else:ss_cnt[can]+=1num_items=float(len(D))ret_list=[]#存放大于最小支持度的元素support_data={}forkeyinss_cnt:#遍历字典中每个键值support=ss_cnt[key]/num_items#计算支持度ifsupport>=min_support:ret_list.insert(0,key)support_data[key]=supportreturnret_list,support_data4、生成候选项集#####################################功能：生成候选项集ck#输入变量：频繁项集，项集元素个数lk,k#输出变量：每个子集个数为k的不重复集ret_list####################################defapriori_gen(lk,k):print'lk=',lkprint'k=',kret_list=[]len_lk=len(lk)foriinxrange(len」k-1):forjinxrange(i+1,len_lk):iflen(lk[i]|lk[j])==k:ret_list.append(lk[i]|lk[j])#各个子集进行组合ret_list=set(ret_list)#去除重复的组合，构建不重复的集合returnret_list5、组织完整的Apriori算法#####################################伪代码如下：#当集合中项的个数大于0时构建一个k个项组成的候选项集的列表检查数据以确认每个项集都是频繁的保留频繁项集并构建k+1项组成的候选项集的列表#功能：构建频繁项集列表#输入变量：原始数据集，最小支持度data_set,min_support#输出变量：频繁项集列表，大于最小支持度的元素列表#l,ret_list####################################defapriori(data_set,min_support=0.5):cl=create_c1(data_set)##扫描数据集，由C1得到L1l1,support_data=scan_d(data_set,c1,min_support)l=[l1]#构建L列表，其中第一个元素为L1列表k=2#前面已经生成L1,所以这里从2开始whilelen(l[k-2])>0:ck=apriori_gen(l[k-2],k)#由L(k-1)生成Ckprint'ck=',ck#扫描数据集，由Ck得到Lklk,support_k=scan_d(data_set,ck,min_support)support_data.update(support_k)l.append(lk)k+=1returnl,support_data6、关联规则生成函数#####################################功能：生成一个包含可信度的规则列表#输入变量：#频繁项集列表l#包含那些频繁项集支持数据的字典support_data#最小可信度阈值min_conf#输出变量：包含可信度的规则列表big_rule_list####################################defgenerate_rules(l,support_data,min_conf=0.7):big_rule_list=[]foriinxrange(1,len(l)):forfreq_setinl[i]:hl=[frozenset([item])foriteminfreq_set]print"h1=",hlifi>1:rules_from_conseq(freq_set,hi,support_data,big_rule_list,min_conf)else:calc_conf(freq_set,h1,support_data,big_rule_list,min_conf)returnbig_rule_list7、计算规则可信度#####################################功能：计算规则的可信度#输入变量：#频繁项集freq_set#每个频繁项集转换成的列表h#包含那些频繁项集支持数据的字典support_data#关联规则brl#输出变量：包含可信度的规则列表pruned_h####################################defcalc_conf(freq_set,h,support_data,brl,min_conf=0.7):pruned」=[]forconseqinh:conf=support_data[freq_set]/support_data[freq_set-conseq]print'freq_set:',freq_setprint'conseq:',conseqprint'freq_set-conseq:',freq_set-conseqifconf>=min_conf:printfreq_set-conseq,'-->',conseq,'conf:',confbrl.append((freq_set-conseq,conseq,conf))pruned_h.append(conseq)returnpruned_h#####################################功能：频繁项集中元素多于两个用这个函数生成关联规则#输入变量：#频繁项集freq_set#每个频繁项集转换成的列表h#包含那些频繁项集支持数据的字典support_data#关联规则brl#输出变量：空####################################defrules_from_conseq(freq_set,h,support_data,brl,min_conf=0.7):m=len(h[0])iflen(freq_set)>(m+1):hmp1=apriori_gen(h,m+1)hmp1=calc_conf(freq_set,hmp1,support_data,brl,min_conf)iflen(hmp1)>1:rules_from_conseq(freq_set,hmp1,support_data,brl,min_conf)代码测试:defmain():data_set=load_data_set()print'data_set=',data_setcl=create_c1(data_set)print'c1=',cl1