python數(shù)據(jù)挖掘Apriori算法實(shí)現(xiàn)關(guān)聯(lián)分析

更新時間：2022年05月12日 10:13:26 作者：hhy518518

這篇文章主要為大家介紹了python數(shù)據(jù)挖掘Apriori算法實(shí)現(xiàn)關(guān)聯(lián)分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

摘要：

主要是講解一些數(shù)據(jù)挖掘中頻繁模式挖掘的Apriori算法原理應(yīng)用實(shí)踐

當(dāng)我們買東西的時候，我們會發(fā)現(xiàn)物品展示方式是不同，購物以后優(yōu)惠券以及用戶忠誠度也是不同的，但是這些來源都是大量數(shù)據(jù)的分析，為了從顧客身上獲得盡可能多的利潤，所以需要用各種技術(shù)來達(dá)到目的。

通過查看哪些商品一起購物可以幫助商店了解客戶的購買行為。這種從大規(guī)模數(shù)據(jù)集中尋找物品間的隱含關(guān)系被稱為關(guān)聯(lián)分析或者關(guān)聯(lián)規(guī)則學(xué)習(xí)。尋找物品的不同組合用蠻力算法的話效率十分底下，所以需要用智能的方法在時間范圍內(nèi)尋找頻繁項(xiàng)集。

關(guān)聯(lián)分析

關(guān)聯(lián)規(guī)則學(xué)習(xí)是在大規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的任務(wù)。這些關(guān)系可以有兩種形式：頻繁項(xiàng)集或者關(guān)聯(lián)規(guī)則。頻繁項(xiàng)是經(jīng)常出線一起物品集合，而關(guān)聯(lián)規(guī)則暗示兩種物品之間存在很強(qiáng)的關(guān)系。

{葡萄酒，尿布，豆奶}就是頻繁項(xiàng)集，而尿布->葡萄酒就是關(guān)聯(lián)規(guī)則。

商家可以更好的理解顧客。

而頻繁的定義是什么？就是支持度和可信度

支持度是：數(shù)據(jù)集中包含這個項(xiàng)的比例。{豆奶} 支持度4/5 {豆奶，尿布}支持度為3/5

可信度：是針對關(guān)聯(lián)規(guī)則定義的。{尿布]->{葡萄酒} 為支持度（{A,B}）/支持度({A})。根據(jù)這兩種衡量方法，但是當(dāng)物品成千上萬的時候如何計(jì)算這種組合清單呢？

Apriori原理

比如四種商品，我們考慮商品的組合問題：

我們目標(biāo)是尋找一起購買的商品集合。我們使用集合的支持度來度量出現(xiàn)的頻率。隨著物品數(shù)目的增加我們比如有N種商品那么就有2^N-1種項(xiàng)集的組合。為了降低計(jì)算時間，發(fā)現(xiàn)了一種Apriori原理。

Apriori原理：如果某個項(xiàng)集是頻繁的，那么它所有的子集也是頻繁的。

推論：如果一個項(xiàng)集是非頻繁的，那么所i有超集也是非頻繁的。

我們用圖來表示就是：

陰影{2,3}是非頻繁的，那么{0,2,3},{1,2,3},{0,1,2,3}也是非頻繁的。一旦計(jì)算出{2,3}的支持度，知道是非頻繁的了。就不用計(jì)算{0,2,3],{1,2,3},{0,1,2,3}避免了指數(shù)增長。

算法實(shí)現(xiàn)

Apriori算法是發(fā)現(xiàn)頻繁項(xiàng)集的一種方法，對于兩個輸出參數(shù)分別是最小支持度和數(shù)據(jù)集。首先生成所有單個物品的項(xiàng)目列表，然后查看那個項(xiàng)目集滿足最小支持度。接下把不滿足的去掉。將剩下的合并成為2個兩素項(xiàng)集。重復(fù)繼續(xù)去掉不滿足最小支持度的項(xiàng)集。

對于數(shù)據(jù)集的每條交易記錄tran

對于每個候選can:

檢查can是否是tran子集
增加計(jì)數(shù)

對每個候選can:

如果支持度不小于最小保留

返回所有頻繁項(xiàng)集

代碼如下：

我們先實(shí)現(xiàn)兩個函數(shù)。一個是最開始生成C1候選集的函數(shù)。另外一個是從候選集中選出滿足支持度的頻繁集

def createC1(dataset):
    C1=[]
    for transaction in dataset:
        for item in transaction:
            if not [item] in C1:#如果不在項(xiàng)集中
                C1.append([item])
    C1.sort()
    #可以作為key值
    return map(frozenset,C1)#每個元素是一個frozenset
#滿足要求的構(gòu)成L1,然后L1組合成為C2。進(jìn)一步過濾成為L2
#frozenset可以作為key值
def scanD(D,Ck,minSupport):
    #先在記錄中查看所有候選集的次數(shù)
    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)#記錄的總數(shù)
    #記錄每個項(xiàng)集的支持度
    supportData={}
    retList=[]
    for key in ssCnt.iterkeys():
        support = float(ssCnt[key]*1.0/numCount)
        if support>=minSupport:
            retList.insert(0,key)#加入滿足條件的項(xiàng)集合的序列
        supportData[key] = support
    return retList,supportData

測試這兩個函數(shù)如下：

x = apriori.loadDataSet()
C1 = apriori.createC1(x)#frozenset每個元素
print C1
#構(gòu)建事物集
D = map(set,x)#每個元素是集合
L1,supportData0 = apriori.scanD(D,C1,0.5)
print L1

得到如下結(jié)果：

[frozenset([1]), frozenset([2]), frozenset([3]), frozenset([4]), frozenset([5])][frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])]

而整體算法如下：

當(dāng)集合項(xiàng)個數(shù)大于0時候

構(gòu)建一個K個項(xiàng)組成的候選列表
檢查是否每個項(xiàng)集是頻繁的
保留頻繁的并且構(gòu)建K+1項(xiàng)的候選項(xiàng)列表

#前面K-1x項(xiàng)目相同的時候可以生成Lk
def aprioriGen(Lk,k):
    #前面k-1項(xiàng)目相同就可以合成
    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#項(xiàng)集為2
    #頻繁n-1項(xiàng)目總數(shù)為
    while(len(L[k-2])>0):#因?yàn)轫?xiàng)集存的位置是0
        Ck = aprioriGen(L[k-2],k)
        Lk,supK = scanD(D,Ck,minSupport)
        supportData.update(supK)#加入字典更新
        L.append(Lk)#L+1
        k+=1#當(dāng)空集的時候退出
    return L,supportData

測試如下：

dataSet = apriori.loadDataSet()
L,supportData = apriori.apriori(dataSet,minSupport=0.7)
print L

我們可以獲得如下的頻繁項(xiàng)集

[[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], []]

挖掘關(guān)聯(lián)規(guī)則

要找到關(guān)聯(lián)規(guī)則。首先需要從頻繁項(xiàng)集開始。我們知道集合中元素是不重復(fù)的，但是我們想基于這些元素獲得其他內(nèi)容。某個元素或者某個元素的集合可以推導(dǎo)另外一個元素。

關(guān)聯(lián)規(guī)則也可以想頻繁項(xiàng)集一樣量化。頻繁項(xiàng)集是需要滿足最小支持度的要求。

對于關(guān)聯(lián)規(guī)則我們就可以用可信度來衡量。一條規(guī)則的可信度為P->H定義為support{P|h}/support(P)其實(shí)也就是P條件下H的概率滿足最小可信度就是關(guān)聯(lián)規(guī)則

如果某條規(guī)則不滿足最小可信度的要求。假設(shè){0,1,2}->{3}不滿足最小可信度的要求。

那么任何{0,1,2}的子集也不會滿足最小可信度的要求?？梢岳眠@個規(guī)則來減少需要測試的規(guī)則數(shù)目。利用Apriori算法，進(jìn)行首先從一個頻繁項(xiàng)集合開始，創(chuàng)建一個規(guī)則列表。

規(guī)則右部包含一個元素，然后對這些規(guī)則測試。接下來合并所有剩余規(guī)則來創(chuàng)建一個新的規(guī)則列表，其中規(guī)則的右部包含兩個元素。這種方法稱為分級法。

#規(guī)則生成函數(shù)
def generateRules(L,supportData,minConf=0.7):
    bigRuleList=[]
    for i in range(1,len(L)):#只獲取兩個或者更多的頻繁項(xiàng)集合
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]#將每個元素拆出來這個是右邊被推出的項(xiàng)集
            if (i>1):
                rulesFromConseq()
            else:
                calcConf(freqSet,H1,supportData,bigRuleList,minConf)
    return bigRuleList
#計(jì)算可信度
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)#為后面準(zhǔn)備。因?yàn)槿舨粷M足規(guī)則右邊該元素基礎(chǔ)下添加也不會滿足
    return prunedH
#最初的規(guī)則生成更多的規(guī)則
def rulesFromConseq(freqSet,H,supportData,brl,minConf=0.7):
    m = len(H[0])
    if (len(freqSet)>(m+1)):#一直到該頻繁項(xiàng)集能包含的右邊推出等于項(xiàng)的個數(shù)-1為止例如{1，2，3，4}當(dāng){1}-{2,3,4}以后此時H[0]長度為3
        Hmp1 = aprioriGen(H,m+1)#右邊推出過程類似生成過程
        Hmp1 = calcConf(freqSet,Hmp1,supportData,brl,minConf)#過濾過程返回被推出的右邊的項(xiàng)集的集合
        if (len(Hmp1)>1):#若有新規(guī)則生成繼續(xù)遞歸處理
            rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)

測試如下：

#生成所有頻繁項(xiàng)集合
dataSet = apriori.loadDataSet()
L,supportData =  apriori.apriori(dataSet,minSupport=0.5)
#生成規(guī)則
rules = apriori.generateRules(L,supportData,minConf=0.5)

calcConf中輸出的結(jié)果如下：

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算法解決實(shí)際問題

發(fā)現(xiàn)國會投票的模式

加州大學(xué)的機(jī)器學(xué)習(xí)數(shù)據(jù)集合有一個1984年起的國會投票記錄的數(shù)據(jù)集：這個數(shù)據(jù)集合比較老?？梢試L試一些新的數(shù)據(jù)。其中一個組織是投票工程。提供了一個公共的API。

下面是如何收集數(shù)據(jù)的過程而數(shù)據(jù)獲取過程比較繁瑣。以及鍵值對映射可以看《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》這本書。

我們主要針對已經(jīng)獲取的txt文本來進(jìn)行挖掘

構(gòu)建投票記錄的數(shù)據(jù)集：

我們希望最后的數(shù)據(jù)集合格式是每一行代表美國國會的一個成員，每一列是投票的對象。

from votesmart import votesmartvotesmart.apikey = 'a7fa40adec6f4a77178799fae4441030'#votesmart.apikey = 'get your api key first'

現(xiàn)在假設(shè)將議案的標(biāo)題以及ID號保存為recent100bills.txt文件，可以通過getBill來獲取每條議案的內(nèi)容。

如果要獲取每條議案的投票信息用getBillActionVotes() 上面都是該API提供的功能。我們主要是針對數(shù)據(jù)的預(yù)處理階段。我們需要將BillId轉(zhuǎn)換成actionID

#只保留包含投票數(shù)據(jù)的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這樣的信息。我們需要頻繁模式挖掘的話，需要將上面信息轉(zhuǎn)換成項(xiàng)集或者交易數(shù)據(jù)庫的東西。一條交易記錄只有一個項(xiàng)出線還是沒出現(xiàn)的信息，并不包含出現(xiàn)的次數(shù)。

美國有兩個主要政黨：共和和民主。我們可以將這個特征編碼為0和1.然后對投票.

#基于投票數(shù)據(jù)的事物列表填充函數(shù)
def getTransList(actionIdList,billTitleList):
    itemMeaning = ['Republican','Democratic']
    for billTitle in billTitleList:
        itemMeaning.append('%s -- Nay'%billTitle)
        itemMeaning.append('%s -- Yea' % billTitle)
    #創(chuàng)建事務(wù)字典
    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

其實(shí)就是獲取的事物集。每一條事物集是[0/1,哪條具體規(guī)則]

就是將所有必要信息離散化編號然后統(tǒng)計(jì)整個投票過程

最后得到類似的結(jié)果：

Prohibiting Federal Funding of National Public Radio -- Yea
           -------->
Republican
Repealing the Health Care Bill -- Yea
confidence: 0.995614

發(fā)現(xiàn)毒蘑菇的相似特征

有時候不是想要尋找所有的頻繁項(xiàng)集合，只是隊(duì)某個特征元素項(xiàng)集感興趣。我們尋找毒蘑菇的公共特征，利用這些特征就能避免遲到有毒的蘑菇。

UCI數(shù)據(jù)集合重有蘑菇的23種特征的數(shù)據(jù)集，每一個特征是標(biāo)稱數(shù)據(jù)。而我們需要將樣本轉(zhuǎn)換成特征的集合，枚舉每個特征所有可能的舉止，如果某個樣本包含特征，那么特征對應(yīng)的整數(shù)應(yīng)該被包含在數(shù)據(jù)集中 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可能值，用整數(shù)3-8表示

相當(dāng)于把需要的特征維度都進(jìn)行排列離散化。最終只有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'])

那么可以給我們的提示就是如果有特征編號是這些的就不要吃這種蘑菇了