2022 高教社杯(國賽數學模組化)思路解析
2022高教社杯ABCD賽題思路解析:
https://blog.51cto.com/u_15734606/5574428
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): #如果候選集包含在購買記錄中,計數+1
ssCnt[can]=ssCnt.get(can,0)+1
numItems=float(len(D)) #購買記錄數
retList=[] #用于存放支援度大于設定值的項集
supportData={} #用于記錄各項集對應的支援度
for key in ssCnt.keys():
support=ssCnt[key]/numItems
if support>=minSupport:
retList.insert(0,key)
supportData[key]=support
return retList,supportData
#由Lk産生Ck+1
def aprioriGen(Lk,k): #Lk的k和參數k不是同一個概念,Lk的k比參數k小1
retList=[]
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=2
while len(L[k-2])>0: #當L[k]為空時,停止疊代
Ck=aprioriGen(L[k-2],k) #L[k-2]對應的值是Lk-1
Lk,supK=scanD(D,Ck,minSupport)
supportData.update(supK)
L.append(Lk)
k+=1
return 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+1
Hmp1=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時),算法需要重新掃描整個資料集,當資料集很大時,算法效率很低。