機器學習-Apriori算法

機器學習一Apriori算法一、基本原理手機微信關注公眾號：datadw學習數(shù)據(jù)挖掘，研究大數(shù)據(jù)，關注你想了解的，分享你需要的。關聯(lián)分析(associationanalysis)就是從大規(guī)模數(shù)據(jù)集中尋找物品間的隱含關系。這里的主要問題是，尋找物品的不同組合是一項十分耗時的任務，所需計算代價很高，蠻力搜索方法并不能解決這個問題，所以需要用更智能的方法在合理的時間內找到頻繁項集。Apriori算法正是基于該原理得到的關聯(lián)分析是一種在大規(guī)模數(shù)據(jù)集中尋找有趣關系的任務。這些關系分為兩種形式：頻繁項集和關聯(lián)規(guī)則。頻繁項集(frequentitemsets)是經(jīng)常出現(xiàn)在一起的物品的集合。其中頻繁的概念可以用支持度來定義。支持度(support)被定義為數(shù)據(jù)集中包含該項集的記錄所占的比例，保留滿足最小支持度的項集。關聯(lián)規(guī)則(associationrules)暗示兩種物品之間可能存在很強的關系。關聯(lián)的概念可用置信度或可信度來定義。我們的目標是找到經(jīng)常在一起購買的物品集合，通過使用集合的支持度來度量其出現(xiàn)的頻率。一個集合的支持度是指有多少比例的交易記錄包含該集合。假如有N種物品，那么這些物品就有2AN-1種項集組合。即使只出售100種物品，它們之間的組合數(shù)對于現(xiàn)有的計算機也是吃不消的。為了降低這種復雜度，有人提出了Apriori算法。Apriori原理是說如果某個項集是頻繁的，那么它的所有子集也是頻繁的。反過來，如果某一項集是非頻繁集，那么它的所有超集（包含該集的集合）也是非頻繁的。二、算法流程對數(shù)據(jù)集的每條交易記錄transaction對每個候選項集can：檢查一下can是否是transaction的子集：如果是，則增加can的計數(shù)值對每個候選項集：如果其支持度不低于最小值，則保留該項集返回所有頻繁項集列表三、算法的特點優(yōu)點：易編碼實現(xiàn)缺點：在大規(guī)模數(shù)據(jù)集上可能較慢。適用數(shù)據(jù)范圍：數(shù)值型或標稱型。四、python代碼實現(xiàn)1、創(chuàng)建簡單數(shù)據(jù)集##############################功能：創(chuàng)建一個簡單的測試數(shù)據(jù)集#說明：數(shù)字1、2、3、4、5代表物品1、、、物品5，#每個子集代表顧客的交易記錄#輸入變量：空#輸出變量：數(shù)據(jù)集#############################defload_data_set():return[[1,3,4],[2,3,5],[1,2,3,5],[2,5]]2、創(chuàng)建大小為1的不重復項集###################################功能：構建一個大小為1的不重復候選項集#輸入變量：測試數(shù)據(jù)集#輸出變量：候選項集合#############################defcreate_c1(data_set):cl=[]fortransactionindata_set:#遍歷數(shù)據(jù)集中所有的交易記錄foritemintransaction:#遍歷每條記錄的每一項if[item]notinc1:#如果該物品沒有在cl中c1.append([item])c1.sort()set和frozenset皆為無序唯一值序列。set和frozenset最本質的區(qū)別是前者是可變的、后者是不可變的。frozenset的不變性，可以作為字典的鍵值使用。returnmap(frozenset,c1)3、保留滿足最小支持度的項集#####################################功能：掃描候選集集合，把支持度大于最小支持度的元素留下來,#通過去掉小于支持度的元素，可以減少后面查找的工作量。#輸入變量：數(shù)據(jù)集，候選項集列表，最小支持度#data_set,ck,min_support#輸出變量：大于最小支持度的元素列表，包含支持度的字典#ret_list,support_data####################################defscan_d(data_set,ck,min_support):D=map(set,data_set)ss_cnt={}fortidinD:#遍歷數(shù)據(jù)集中所有交易forcaninck:#遍歷候選項集#判斷候選集中該集合是數(shù)據(jù)集中交易記錄的子集#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#輸入變量：頻繁項集，項集元素個數(shù)lk,k#輸出變量：每個子集個數(shù)為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算法#####################################偽代碼如下：#當集合中項的個數(shù)大于0時構建一個k個項組成的候選項集的列表檢查數(shù)據(jù)以確認每個項集都是頻繁的保留頻繁項集并構建k+1項組成的候選項集的列表#功能：構建頻繁項集列表#輸入變量：原始數(shù)據(jù)集，最小支持度data_set,min_support#輸出變量：頻繁項集列表，大于最小支持度的元素列表#l,ret_list####################################defapriori(data_set,min_support=0.5):cl=create_c1(data_set)##掃描數(shù)據(jù)集，由C1得到L1l1,support_data=scan_d(data_set,c1,min_support)l=[l1]#構建L列表，其中第一個元素為L1列表k=2#前面已經(jīng)生成L1,所以這里從2開始whilelen(l[k-2])>0:ck=apriori_gen(l[k-2],k)#由L(k-1)生成Ckprint'ck=',ck#掃描數(shù)據(jù)集，由Ck得到Lklk,support_k=scan_d(data_set,ck,min_support)support_data.update(support_k)l.append(lk)k+=1returnl,support_data6、關聯(lián)規(guī)則生成函數(shù)#####################################功能：生成一個包含可信度的規(guī)則列表#輸入變量：#頻繁項集列表l#包含那些頻繁項集支持數(shù)據(jù)的字典support_data#最小可信度閾值min_conf#輸出變量：包含可信度的規(guī)則列表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、計算規(guī)則可信度#####################################功能：計算規(guī)則的可信度#輸入變量：#頻繁項集freq_set#每個頻繁項集轉換成的列表h#包含那些頻繁項集支持數(shù)據(jù)的字典support_data#關聯(lián)規(guī)則brl#輸出變量：包含可信度的規(guī)則列表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#####################################功能：頻繁項集中元素多于兩個用這個函數(shù)生成關聯(lián)規(guī)則#輸入變量：#頻繁項集freq_set#每個頻繁項集轉換成的列表h#包含那些頻繁項集支持數(shù)據(jù)的字典support_data#關聯(lián)規(guī)則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