python數據挖掘Apriori算法實現關聯分析
摘要：
主要是講解一些數據挖掘中頻繁模式挖掘的Apriori算法原理應用實踐
當我們買東西的時候，我們會發現物品展示方式是不同，購物以後優惠券以及用戶忠誠度也是不同的，但是這些來源都是大量數據的分析，為瞭從顧客身上獲得盡可能多的利潤，所以需要用各種技術來達到目的。
通過查看哪些商品一起購物可以幫助商店瞭解客戶的購買行為。這種從大規模數據集中尋找物品間的隱含關系被稱為關聯分析或者關聯規則學習。尋找物品的不同組合用蠻力算法的話效率十分底下，所以需要用智能的方法在時間范圍內尋找頻繁項集。
關聯分析
關聯規則學習是在大規模數據集中尋找有趣關系的任務。這些關系可以有兩種形式：頻繁項集或者關聯規則。頻繁項是經常出線一起物品集合，而關聯規則暗示兩種物品之間存在很強的關系。
{葡萄酒，尿佈，豆奶}就是頻繁項集，而尿佈->葡萄酒就是關聯規則。商傢可以更好的理解顧客。而頻繁的定義是什麼？就是支持度和可信度
支持度是：數據集中包含這個項的比例。{豆奶} 支持度4/5 {豆奶，尿佈}支持度為3/5
可信度：是針對關聯規則定義的。{尿佈]->{葡萄酒} 為 支持度（{A,B}）/支持度({A})。根據這兩種衡量方法，但是當物品成千上萬的時候如何計算這種組合清單呢？
Apriori原理
比如四種商品，我們考慮商品的組合問題：
我們目標是尋找一起購買的商品集合。我們使用集合的支持度來度量出現的頻率。隨著物品數目的增加我們比如有N種商品那麼就有2^N-1種項集的組合。為瞭降低計算時間，發現瞭一種Apriori原理。
Apriori原理：如果某個項集是頻繁的，那麼它所有的子集也是頻繁的。
推論：如果一個項集是非頻繁的，那麼所i有超集也是非頻繁的。
我們用圖來表示就是：
陰影{2,3}是非頻繁的，那麼{0,2,3},{1,2,3},{0,1,2,3}也是非頻繁的。一旦計算出{2,3}的支持度，知道是非頻繁的瞭。就不用計算{0,2,3],{1,2,3},{0,1,2,3}避免瞭指數增長。
算法實現
Apriori算法是發現頻繁項集的一種方法，對於兩個輸出參數分別是最小支持度和數據集。首先生成所有單個物品的項目列表，然後查看那個項目集滿足最小支持度。接下把不滿足的去掉。將剩下的合並成為2個兩素項集。重復繼續去掉不滿足最小支持度的項集。
對於數據集的每條交易記錄tran
對於每個候選can:
- 檢查can是否是tran子集
- 增加計數
對每個候選can:
- 如果支持度不小於最小保留
返回所有頻繁項集
代碼如下：
我們先實現兩個函數。一個是最開始生成C1候選集的函數。另外一個是從候選集中選出滿足支持度的頻繁集
def createC1(dataset):
C1=[]
for transaction in dataset:
for item in transaction:
if not [item] in C1:#如果不在項集中
C1.append([item])
C1.sort()
#可以作為key值
return map(frozenset,C1)#每個元素是一個frozenset
#滿足要求的構成L1,然後L1組合成為C2。進一步過濾成為L2
#frozenset可以作為key值
def scanD(D,Ck,minSupport):
#先在記錄中查看所有候選集的次數
ssCnt = {}
for td in D:
for can in Ck:
if can.issubset(td):#如果是那個集合的子集
if not ssCnt.has_key(can):ssCnt[can]=1
else:ssCnt[can]+=1
numCount = len(D)#記錄的總數
#記錄每個項集的支持度
supportData={}
retList=[]
for key in ssCnt.iterkeys():
support = float(ssCnt[key]*1.0/numCount)
if support>=minSupport:
retList.insert(0,key)#加入滿足條件的項集合的序列
supportData[key] = support
return retList,supportData
x = apriori.loadDataSet() C1 = apriori.createC1(x)#frozenset每個元素 print C1 #構建事物集 D = map(set,x)#每個元素是集合 L1,supportData0 = apriori.scanD(D,C1,0.5) print L1
得到如下結果：
[frozenset([1]), frozenset([2]), frozenset([3]), frozenset([4]), frozenset([5])]
[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])]
而整體算法如下：
當集合項個數大於0時候
構建一個K個項組成的候選列表
檢查是否每個項集是頻繁的
保留頻繁的並且構建K+1項的候選項列表
#前面K-1x項目相同的時候可以生成Lk
def aprioriGen(Lk,k):
#前面k-1項目相同就可以合成
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i+1,lenLk):
L1 = list(Lk[i])[:k-2]#可以考慮1個元素的時候是0直接合並
L2 = list(Lk[j])[:k-2]
L1.sort()
L2.sort()
if L1==L2:
retList.append(Lk[i]|Lk[j])
return retList
def apriori(dataset,minSupport=0.5):
C1 = createC1(dataset)
D = map(set,dataset)
L1,supportData = scanD(D,C1,minSupport)
L = [L1]
k = 2#項集為2
#頻繁n-1項目總數為
while(len(L[k-2])>0):#因為項集存的位置是0
Ck = aprioriGen(L[k-2],k)
Lk,supK = scanD(D,Ck,minSupport)
supportData.update(supK)#加入字典更新
L.append(Lk)#L+1
k+=1#當空集的時候退出
return L,supportData
測試如下：
dataSet = apriori.loadDataSet() L,supportData = apriori.apriori(dataSet,minSupport=0.7) print L
我們可以獲得如下的頻繁項集
[[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], []]
挖掘關聯規則
要找到關聯規則。首先需要從頻繁項集開始。我們知道集合中元素是不重復的，但是我們想基於這些元素獲得其他內容。某個元素或者某個元素的集合可以推導另外一個元素。
關聯規則也可以想頻繁項集一樣量化。頻繁項集是需要滿足最小支持度的要求。對於關聯規則我們就可以用可信度來衡量。一條規則的可信度為P->H定義為support{P|h}/support(P)其實也就是P條件下H的概率滿足最小可信度就是關聯規則
如果某條規則不滿足最小可信度的要求。假設{0,1,2}->{3}不滿足最小可信度的要求。
那麼任何{0,1,2}的子集也不會滿足最小可信度的要求。可以利用這個規則來 減少需要測試的規則數目。利用Apriori算法，進行首先從一個頻繁項集合開始，創建一個規則列表。
規則右部包含一個元素，然後對這些規則測試。接下來合並所有剩餘 規則來創建一個新的規則列表，其中規則的右部包含兩個元素。這種方法稱為分級法。
#規則生成函數
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]#將每個元素拆出來這個是右邊被推出的項集
if (i>1):
rulesFromConseq()
else:
calcConf(freqSet,H1,supportData,bigRuleList,minConf)
return bigRuleList
#計算可信度
def calcConf(freqSet,H,supportData,brl,minConf=0.7):
prunedH = []
for conseq in H:
conf = supportData[freqSet]/supportData[freqSet-conseq]#獲得條件概率（freq-conseq) -> 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)):#一直到該頻繁項集能包含的右邊推出等於項的個數-1為止例如{1，2，3，4}當{1}-{2,3,4}以後此時H[0]長度為3
Hmp1 = aprioriGen(H,m+1)#右邊推出過程類似生成過程
Hmp1 = calcConf(freqSet,Hmp1,supportData,brl,minConf)#過濾過程返回被推出的右邊的項集的集合
if (len(Hmp1)>1):#若有新規則生成繼續遞歸處理
rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)
測試如下：
#生成所有頻繁項集合 dataSet = apriori.loadDataSet() L,supportData = apriori.apriori(dataSet,minSupport=0.5) #生成規則 rules = apriori.generateRules(L,supportData,minConf=0.5)
calcConf中輸出的結果如下：
frozenset([3]) ---> frozenset([1]) conf: 0.666666666667 frozenset([1]) ---> frozenset([3]) conf: 1.0 frozenset([5]) ---> frozenset([2]) conf: 1.0 frozenset([2]) ---> frozenset([5]) conf: 1.0 frozenset([3]) ---> frozenset([2]) conf: 0.666666666667 frozenset([2]) ---> frozenset([3]) conf: 0.666666666667 frozenset([5]) ---> frozenset([3]) conf: 0.666666666667 frozenset([3]) ---> frozenset([5]) conf: 0.666666666667 frozenset([5]) ---> frozenset([2, 3]) conf: 0.666666666667 frozenset([3]) ---> frozenset([2, 5]) conf: 0.666666666667 frozenset([2]) ---> frozenset([3, 5]) conf: 0.666666666667
利用Apriori算法解決實際問題
發現國會投票的模式 加州大學的機器學習數據集合有一個1984年起的國會投票記錄的數據集： 這個數據集合比較老。可以嘗試一些新的數據。其中一個組織是投票工程。提供瞭一個公共的API。
下面是如何收集數據的過程 而數據獲取過程比較繁瑣。以及鍵值對映射可以看《機器學習實戰》這本書。
我們主要針對已經獲取的txt文本來進行挖掘
構建投票記錄的數據集：
我們希望最後的數據集合格式是每一行代表美國國會的一個成員，每一列是投票的對象。
from votesmart import votesmart
votesmart.apikey = 'a7fa40adec6f4a77178799fae4441030'
#votesmart.apikey = 'get your api key first'
現在假設將議案的標題以及ID號保存為recent100bills.txt文件，可以通過getBill來獲取每條議案的內容。如果要獲取每條議案的投票信息用getBillActionVotes() 上面都是該API提供的功能。我們主要是針對數據的預處理階段。我們需要將BillId轉換成actionID
#隻保留包含投票數據的actionId
def getActionIds():
fr = open('recent20bills.txt')
actionIdList=[];billTitleList=[]
for line in fr.readlines():
billNum = int(line.split('\t')[0])
try:
billDetail = votesmart.votes.getBill(billNum)#獲取議案對象
for action in billDetail.actions:
if action.level=='House' and \
(action.stage=='Passage' or \
action.stage=='Amendment Vote'):
actionId = int(action.actionId)
actionIdList.append(actionId)
billTitleList.append(line.strip().split('\t')[1])
except:
print "problem gettin bill %d"%billNum
sleep(1)
return actionIdList,billTitleList
我們獲得的是類似Bill:12939 has actionId:34089這樣的信息。我們需要頻繁模式挖掘的話，需要將上面信息轉換成項集或者交易數據庫的東西。一條交易記錄隻有一個項出線還是沒出現的信息，並不包含出現的次數。
美國有兩個主要政黨：共和和民主。我們可以將這個特征編碼為0和1.然後對投票.
#基於投票數據的事物列表填充函數
def getTransList(actionIdList,billTitleList):
itemMeaning = ['Republican','Democratic']
for billTitle in billTitleList:
itemMeaning.append('%s -- Nay'%billTitle)
itemMeaning.append('%s -- Yea' % billTitle)
#創建事務字典
transDict = {}
voteCount = 2# 0,1是所屬黨派。2開始是被第幾次投票
for actionId in actionIdList:
sleep(3)
print 'getting votes for actionId: %d' %actionId
try:
voteList = votesmart.votes.getBillActionVotes(actionId)
for vote in voteList:
if not transDict.has_key(vote.candidateName):
transDict[vote.candidateName] = []
if vote.officeParties =='Democratic':
transDict[vote.candidateName].append(1)
elif vote.officeParties=='Republican':
transDict[vote.candidateName].append(0)
if vote.action=='Nay':
transDict[vote.candidateName].append(voteCount)
elif vote.action=='Yea':
transDict[vote.candidateName].append(voteCount+1)
except:
print "problem getting actionId:%d" %actionId
voteCount+=2
return transDict,itemMeaning
其實就是獲取的事物集。每一條事物集是[0/1,哪條具體規則]
就是將所有必要信息離散化編號然後統計整個投票過程
最後得到類似的結果：
Prohibiting Federal Funding of National Public Radio -- Yea
-------->
Republican
Repealing the Health Care Bill -- Yea
confidence: 0.995614
發現毒蘑菇的相似特征
有時候不是想要尋找所有的頻繁項集合，隻是隊某個特征元素項集感興趣。我們尋找毒蘑菇的公共特征，利用這些特征就能避免遲到有毒的蘑菇。
UCI數據集合重有蘑菇的23種特征的數據集，每一個特征是標稱數據。而我們需要將樣本轉換成特征的集合，枚舉每個特征所有可能的舉止，如果某個樣本 包含特征，那麼特征對應的整數應該被包含在數據集中 1 3 9 13 23 25 34 36 38 40 52 54 59 63 67 76 85 86 90 93 98 107 113 每一個樣本都是這樣的特征集合。
如果第一個特征有毒就是2，如果能食用就是1，下一個特征是形狀有6可能值，用整數3-8表示
相當於把需要的特征維度都進行排列離散化。最終隻有1個大維特征
mushDatSet = [line.split() for line in open('mushroom.dat').readlines()]
L,suppData = apriori.apriori(mushDatSet,minSupport=0.3)
#尋找毒的公共特征
for item in L[1]:
if item.intersection('2'):print item
frozenset(['2', '59']) frozenset(['39', '2']) frozenset(['2', '67']) frozenset(['2', '34']) frozenset(['2', '23']) frozenset(['2', '86']) frozenset(['76', '2']) frozenset(['90', '2']) frozenset(['2', '53']) frozenset(['93', '2']) frozenset(['63', '2']) frozenset(['2', '28']) frozenset(['2', '85']) frozenset(['2', '36'])
那麼可以給我們的提示就是如果有特征編號是這些的就不要吃這種蘑菇瞭
總結：
關聯分析是發現大數據集合元素間關系的工具集。可以用在不同的物品上，主要是在樣本處理上需要將樣本轉換成特征集合。也就是將所有維的特征統一編碼。
以上就是python數據挖掘Apriori算法實現關聯分析的詳細內容，更多關於Apriori算法關聯分析的資料請關註LevelAH其它相關文章！
推薦閱讀：
- python–字典(dict)和集合(set)詳解
- 詳解Python 關聯規則分析
- Python中使用Frozenset對象的案例詳解
- 總結分析python數據化運營關聯規則
- 詳細介紹Python中的set集合