機(jī)器學(xué)習(xí)-Apriori算法

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