2023 美賽(美國大學生數學建模)思路解析

2023美賽ABCDEF賽題思路解析：

https://blog.csdn.net/dc_sinor/article/details/128779911

1 啤酒和尿布

Apriori算法是一種用于挖掘數據集內部關聯規則的算法，“apriori”在拉丁語中翻譯為“來自以前”，聽意思你應該就能猜到了，這個算法是用先驗知識來預測數據的關聯規則的。

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

那么，啤酒與尿布的關系是如何被發現的呢？當然是通過關聯算法，我們從Apriori算法開始吧，利用Apriori進行關聯分析。

2 Apriori原理

先介紹兩個概念

• 支持度support：數據集中包含該項集的數據所占數據集的比例，度量一個集合在原始數據中出現的頻率
• 置信度confidence：是針對一條關聯規則來定義的，a->b的置信度=支持度{a|b}/支持度{a}，a|b表示ab的并集

關聯分析有兩個目標：

• 發現頻繁項集（頻繁項集是滿足最小支持度要求的項集，它給出經常在一起出現的元素項）
• 發現關聯規則（關聯規則意味著元素項之間“如果…那么…”的關系）

Apriori原理

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

3 Apriori代碼實現

3.1 挖掘頻繁項集

挖掘頻繁項集的邏輯如下圖

#加載數據集 def loadDataSet():return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]#選取數據集的非重復元素組成候選集的集合C1 def createC1(dataSet):C1=[]for transaction in dataSet: #對數據集中的每條購買記錄for item in transaction: #對購買記錄中的每個元素if [item] not in C1: #注意，item外要加上[]，便于與C1中的[item]對比C1.append([item])C1.sort()return list(map(frozenset,C1)) #將C1各元素轉換為frozenset格式，注意frozenset作用對象為可迭代對象#由Ck產生Lk：掃描數據集D，計算候選集Ck各元素在D中的支持度，選取支持度大于設定值的元素進入Lk def scanD(D,Ck,minSupport):ssCnt={}for tid in D: #對數據集中的每條購買記錄for can in Ck: #遍歷Ck所有候選集if can.issubset(tid): #如果候選集包含在購買記錄中，計數+1ssCnt[can]=ssCnt.get(can,0)+1numItems=float(len(D)) #購買記錄數retList=[] #用于存放支持度大于設定值的項集supportData={} #用于記錄各項集對應的支持度for key in ssCnt.keys():support=ssCnt[key]/numItemsif support>=minSupport:retList.insert(0,key)supportData[key]=supportreturn retList,supportData#由Lk產生Ck+1 def aprioriGen(Lk,k): #Lk的k和參數k不是同一個概念，Lk的k比參數k小1retList=[]lenLk=len(Lk)for i in range(lenLk):for j in range(i+1,lenLk): #比較Lk中的每一個元素與其他元素L1=list(Lk[i])[:k-2];L2=list(Lk[j])[:k-2]L1.sort();L2.sort()if L1==L2: #若前k-2項相同，則合并這兩項retList.append(Lk[i]|Lk[j])return retList#Apriori算法主函數 def apriori(dataSet,minSupport=0.5):C1=createC1(dataSet)D=list(map(set,dataSet))L1,supportData=scanD(D,C1,minSupport)L=[L1]k=2while len(L[k-2])>0: #當L[k]為空時，停止迭代Ck=aprioriGen(L[k-2],k) #L[k-2]對應的值是Lk-1Lk,supK=scanD(D,Ck,minSupport)supportData.update(supK)L.append(Lk)k+=1return L,supportData

我們來測試一下

dataset=loadDataSet() C1=createC1(dataset) D=list(map(set,dataset)) L1,supportData0=scanD(D,C1,0.5) L,supportData=apriori(dataset,minSupport=0.5)

可以看到，頻繁項集如上圖，{1,2,3,5,{2,3},{3,5},{2,5},{1,3},{2,3,5}}都是頻繁項集。得到了頻繁項集，接下來我們看看頻繁項集之間的關聯規則。

3.2 從頻繁項集挖掘關聯規則

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

# 主函數，由頻繁項集以及對應的支持度，得到各條規則的置信度，選擇置信度滿足要求的規則為關聯規則 # 為了避免將所有數據都對比一遍，采用與上述相同的邏輯減少計算量——一層一層計算篩選 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是頻繁項集單元素列表，是關聯規則中a->b的b項if i>1:rulesFromConseq(freqSet,H1,supportData,bigRuleList,minConf)else:calConf(freqSet,H1,supportData,bigRuleList,minConf)return bigRuleList# 置信度計算函數 def calConf(freqSet,H,supportData,brl,minConf=0.7):prunedH=[] # 用于存放置信度滿足要求的關聯規則的b項，即“提純后的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# 關聯規則合并函數 def rulesFromConseq(freqSet,H,supportData,brl,minConf=0.7):m=len(H[0])if len(freqSet)>(m+1): #查看頻繁項集freqSet是否大到可以移除大小為m的子集Hmp1=aprioriGen(H,m+1) # 從Hm合并Hm+1Hmp1=calConf(freqSet,Hmp1,supportData,brl,minConf)if len(Hmp1)>1: #若合并后的Hm+1的元素大于1個，則繼續合并rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)

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

3.3 總結

本文簡述關聯分析算法Apriori算法的原理，然后用python3進行了實操，需要注意的是，Apriori算法的缺點——每次增加頻繁項集大小時(即Ck->Lk時)，算法需要重新掃描整個數據集，當數據集很大時，算法效率很低。

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

2023 美賽(美國大學生數學建模)思路解析

2023美賽ABCDEF賽題思路解析：

https://blog.csdn.net/dc_sinor/article/details/128779911

總結

以上是生活随笔為你收集整理的2023美国大学生数学建模思路 - 案例：Apriori-关联规则挖掘算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。