2023美國大學(xué)生數(shù)學(xué)建模競(jìng)賽思路分析

資料思路分享群：323126572

1 啤酒和尿布

Apriori算法是一種用于挖掘數(shù)據(jù)集內(nèi)部關(guān)聯(lián)規(guī)則的算法，“apriori”在拉丁語中翻譯為“來自以前”，聽意思你應(yīng)該就能猜到了，這個(gè)算法是用先驗(yàn)知識(shí)來預(yù)測(cè)數(shù)據(jù)的關(guān)聯(lián)規(guī)則的。

說到關(guān)聯(lián)規(guī)則，有一個(gè)很有名的案例——啤酒與尿布。說，美國一家連鎖店發(fā)現(xiàn)很多男性會(huì)在周四購買尿布和啤酒，這兩種看似不相干的商品之間顯現(xiàn)出強(qiáng)相關(guān)性，于是商家可以將啤酒貨架放在尿布貨架旁邊以增加收益。

那么，啤酒與尿布的關(guān)系是如何被發(fā)現(xiàn)的呢？當(dāng)然是通過關(guān)聯(lián)算法，我們從Apriori算法開始吧，利用Apriori進(jìn)行關(guān)聯(lián)分析。

2 Apriori原理

先介紹兩個(gè)概念

支持度support：數(shù)據(jù)集中包含該項(xiàng)集的數(shù)據(jù)所占數(shù)據(jù)集的比例，度量一個(gè)集合在原始數(shù)據(jù)中出現(xiàn)的頻率

置信度confidence：是針對(duì)一條關(guān)聯(lián)規(guī)則來定義的，a->b的置信度=支持度{a|b}/支持度{a}，a|b表示ab的并集

關(guān)聯(lián)分析有兩個(gè)目標(biāo)：

發(fā)現(xiàn)頻繁項(xiàng)集（頻繁項(xiàng)集是滿足最小支持度要求的項(xiàng)集，它給出經(jīng)常在一起出現(xiàn)的元素項(xiàng)）

發(fā)現(xiàn)關(guān)聯(lián)規(guī)則（關(guān)聯(lián)規(guī)則意味著元素項(xiàng)之間“如果…那么…”的關(guān)系）

Apriori原理

如果某個(gè)項(xiàng)集是頻繁的，那么它的所有子集也是頻繁的 如果某個(gè)項(xiàng)集是非頻繁的，那么它的所有超集也是非頻繁的 基于此，Apriori算法從單元素項(xiàng)集開始，通過組合滿足最小支持度的項(xiàng)集來形成更大的集合 其實(shí)Apriori就是通過排除法來選擇頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則，下面我們根據(jù)這樣的原理用python實(shí)現(xiàn)算法。

3 Apriori代碼實(shí)現(xiàn)

3.1 挖掘頻繁項(xiàng)集

挖掘頻繁項(xiàng)集的邏輯如下圖

#加載數(shù)據(jù)集

def loadDataSet():

? ?return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]

#選取數(shù)據(jù)集的非重復(fù)元素組成候選集的集合C1

def createC1(dataSet):

? ?C1=[]

? ?for transaction in dataSet: #對(duì)數(shù)據(jù)集中的每條購買記錄

? ? ? ?for item in transaction: #對(duì)購買記錄中的每個(gè)元素

? ? ? ? ? ?if [item] not in C1: #注意，item外要加上[]，便于與C1中的[item]對(duì)比

? ? ? ? ? ? ? ?C1.append([item])

? ?C1.sort()

? ?return list(map(frozenset,C1)) #將C1各元素轉(zhuǎn)換為frozenset格式，注意frozenset作用對(duì)象為可迭代對(duì)象

#由Ck產(chǎn)生Lk：掃描數(shù)據(jù)集D，計(jì)算候選集Ck各元素在D中的支持度，選取支持度大于設(shè)定值的元素進(jìn)入Lk

def scanD(D,Ck,minSupport):

? ?ssCnt={}

? ?for tid in D: #對(duì)數(shù)據(jù)集中的每條購買記錄

? ? ? ?for can in Ck: #遍歷Ck所有候選集

? ? ? ? ? ?if can.issubset(tid): #如果候選集包含在購買記錄中，計(jì)數(shù)+1

? ? ? ? ? ? ? ?ssCnt[can]=ssCnt.get(can,0)+1

? ?numItems=float(len(D)) #購買記錄數(shù)

? ?retList=[] #用于存放支持度大于設(shè)定值的項(xiàng)集

? ?supportData={} #用于記錄各項(xiàng)集對(duì)應(yīng)的支持度

? ?for key in ssCnt.keys():

? ? ? ?support=ssCnt[key]/numItems

? ? ? ?if support>=minSupport:

? ? ? ? ? ?retList.insert(0,key)

? ? ? ?supportData[key]=support

? ?return retList,supportData

#由Lk產(chǎn)生Ck+1

def aprioriGen(Lk,k): #Lk的k和參數(shù)k不是同一個(gè)概念，Lk的k比參數(shù)k小1

? ?retList=[]

? ?lenLk=len(Lk)

? ?for i in range(lenLk):

? ? ? ?for j in range(i+1,lenLk): #比較Lk中的每一個(gè)元素與其他元素

? ? ? ? ? ?L1=list(Lk[i])[:k-2];L2=list(Lk[j])[:k-2]

? ? ? ? ? ?L1.sort();L2.sort()

? ? ? ? ? ?if L1==L2: #若前k-2項(xiàng)相同，則合并這兩項(xiàng)

? ? ? ? ? ? ? ?retList.append(Lk[i]|Lk[j])

? ?return retList

#Apriori算法主函數(shù)

def apriori(dataSet,minSupport=0.5):

? ?C1=createC1(dataSet)

? ?D=list(map(set,dataSet))

? ?L1,supportData=scanD(D,C1,minSupport)

? ?L=[L1]

? ?k=2

? ?while len(L[k-2])>0: #當(dāng)L[k]為空時(shí)，停止迭代

? ? ? ?Ck=aprioriGen(L[k-2],k) #L[k-2]對(duì)應(yīng)的值是Lk-1

? ? ? ?Lk,supK=scanD(D,Ck,minSupport)

? ? ? ?supportData.update(supK)

? ? ? ?L.append(Lk)

? ? ? ?k+=1

? ?return L,supportData

我們來測(cè)試一下

dataset=loadDataSet()

C1=createC1(dataset)

D=list(map(set,dataset))

L1,supportData0=scanD(D,C1,0.5)

L,supportData=apriori(dataset,minSupport=0.5)

可以看到，頻繁項(xiàng)集如上圖，{1,2,3,5,{2,3},{3,5},{2,5},{1,3},{2,3,5}}都是頻繁項(xiàng)集。得到了頻繁項(xiàng)集，接下來我們看看頻繁項(xiàng)集之間的關(guān)聯(lián)規(guī)則。

3.2 從頻繁項(xiàng)集挖掘關(guān)聯(lián)規(guī)則

挖掘關(guān)聯(lián)規(guī)則原理如下：若某條規(guī)則不滿足最小置信度要求，則該規(guī)則的所有子集也不滿足最小置信度要求

# 主函數(shù)，由頻繁項(xiàng)集以及對(duì)應(yīng)的支持度，得到各條規(guī)則的置信度，選擇置信度滿足要求的規(guī)則為關(guān)聯(lián)規(guī)則

# 為了避免將所有數(shù)據(jù)都對(duì)比一遍，采用與上述相同的邏輯減少計(jì)算量——一層一層計(jì)算篩選

def generateRules(L,supportData,minConf=0.7):

? ?bigRuleList=[]

? ?for i in range(1,len(L)):

? ? ? ?for freqSet in L[i]:

? ? ? ? ? ?H1=[frozenset([item]) for item in freqSet] # H1是頻繁項(xiàng)集單元素列表，是關(guān)聯(lián)規(guī)則中a->b的b項(xiàng)

? ? ? ? ? ?if i>1:

? ? ? ? ? ? ? ?rulesFromConseq(freqSet,H1,supportData,bigRuleList,minConf)

? ? ? ? ? ?else:

? ? ? ? ? ? ? ?calConf(freqSet,H1,supportData,bigRuleList,minConf)

? ?return bigRuleList

# 置信度計(jì)算函數(shù)

def calConf(freqSet,H,supportData,brl,minConf=0.7):

? ?prunedH=[] # 用于存放置信度滿足要求的關(guān)聯(lián)規(guī)則的b項(xiàng)，即“提純后的H”

? ?for conseq in H:

? ? ? ?conf=supportData[freqSet]/supportData[freqSet-conseq]

? ? ? ?if conf>=minConf:

? ? ? ? ? ?print (freqSet-conseq,'-->',conseq,'conf:',conf)

? ? ? ? ? ?brl.append([freqSet-conseq,conseq,conf])

? ? ? ? ? ?prunedH.append(conseq)

? ?return prunedH

# 關(guān)聯(lián)規(guī)則合并函數(shù)

def rulesFromConseq(freqSet,H,supportData,brl,minConf=0.7):

? ?m=len(H[0])

? ?if len(freqSet)>(m+1): #查看頻繁項(xiàng)集freqSet是否大到可以移除大小為m的子集

? ? ? ?Hmp1=aprioriGen(H,m+1) # 從Hm合并Hm+1

? ? ? ?Hmp1=calConf(freqSet,Hmp1,supportData,brl,minConf)

? ? ? ?if len(Hmp1)>1: #若合并后的Hm+1的元素大于1個(gè)，則繼續(xù)合并

? ? ? ? ? ?rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)

可以看到，如果有5那么必定有2，如果有3，那么66.7%的可能性有2,5……

3.3 總結(jié)

本文簡(jiǎn)述關(guān)聯(lián)分析算法Apriori算法的原理，然后用python3進(jìn)行了實(shí)操，需要注意的是，Apriori算法的缺點(diǎn)——每次增加頻繁項(xiàng)集大小時(shí)(即Ck->Lk時(shí))，算法需要重新掃描整個(gè)數(shù)據(jù)集，當(dāng)數(shù)據(jù)集很大時(shí)，算法效率很低。

解決方法是FP-Growth算法，這個(gè)算法我們下一次講解。

美賽思路獲?。篞群：323126572