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

更新時(shí)間：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)我們買東西的時(shí)候，我們會(huì)發(fā)現(xiàn)物品展示方式是不同，購(gòu)物以后優(yōu)惠券以及用戶忠誠(chéng)度也是不同的，但是這些來(lái)源都是大量數(shù)據(jù)的分析，為了從顧客身上獲得盡可能多的利潤(rùn)，所以需要用各種技術(shù)來(lái)達(dá)到目的。

通過(guò)查看哪些商品一起購(gòu)物可以幫助商店了解客戶的購(gòu)買行為。這種從大規(guī)模數(shù)據(jù)集中尋找物品間的隱含關(guān)系被稱為關(guān)聯(lián)分析或者關(guān)聯(lián)規(guī)則學(xué)習(xí)。尋找物品的不同組合用蠻力算法的話效率十分底下，所以需要用智能的方法在時(shí)間范圍內(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ù)集中包含這個(gè)項(xiàng)的比例。{豆奶} 支持度4/5 {豆奶，尿布}支持度為3/5

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

Apriori原理

比如四種商品，我們考慮商品的組合問(wèn)題：

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

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

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

我們用圖來(lá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ù)增長(zhǎng)。

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

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

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

對(duì)于每個(gè)候選can:

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

對(duì)每個(gè)候選can:

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

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

代碼如下：

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

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)#每個(gè)元素是一個(gè)frozenset
#滿足要求的構(gòu)成L1,然后L1組合成為C2。進(jìn)一步過(guò)濾成為L(zhǎng)2
#frozenset可以作為key值
def scanD(D,Ck,minSupport):
    #先在記錄中查看所有候選集的次數(shù)
    ssCnt = {}
    for td in D:
        for can in Ck:
            if can.issubset(td):#如果是那個(gè)集合的子集
                if not ssCnt.has_key(can):ssCnt[can]=1
                else:ssCnt[can]+=1
    numCount = len(D)#記錄的總數(shù)
    #記錄每個(gè)項(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

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

x = apriori.loadDataSet()
C1 = apriori.createC1(x)#frozenset每個(gè)元素
print C1
#構(gòu)建事物集
D = map(set,x)#每個(gè)元素是集合
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)個(gè)數(shù)大于0時(shí)候

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

#前面K-1x項(xiàng)目相同的時(shí)候可以生成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個(gè)元素的時(shí)候是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)空集的時(shí)候退出
    return L,supportData

測(cè)試如下：

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)集開(kāi)始。我們知道集合中元素是不重復(fù)的，但是我們想基于這些元素獲得其他內(nèi)容。某個(gè)元素或者某個(gè)元素的集合可以推導(dǎo)另外一個(gè)元素。

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

對(duì)于關(guān)聯(lián)規(guī)則我們就可以用可信度來(lái)衡量。一條規(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}的子集也不會(huì)滿足最小可信度的要求。可以利用這個(gè)規(guī)則來(lái) 減少需要測(cè)試的規(guī)則數(shù)目。利用Apriori算法，進(jìn)行首先從一個(gè)頻繁項(xiàng)集合開(kāi)始，創(chuàng)建一個(gè)規(guī)則列表。

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

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

測(cè)試如下：

#生成所有頻繁項(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í)際問(wèn)題

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

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

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

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

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

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

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

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

如果要獲取每條議案的投票信息用getBillActionVotes() 上面都是該API提供的功能。我們主要是針對(duì)數(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)#獲取議案對(duì)象
            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ù)庫(kù)的東西。一條交易記錄只有一個(gè)項(xiàng)出線還是沒(méi)出現(xiàn)的信息，并不包含出現(xiàn)的次數(shù)。

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

#基于投票數(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開(kāi)始是被第幾次投票
    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ī)則]

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

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

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

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

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

UCI數(shù)據(jù)集合重有蘑菇的23種特征的數(shù)據(jù)集，每一個(gè)特征是標(biāo)稱數(shù)據(jù)。而我們需要將樣本轉(zhuǎn)換成特征的集合，枚舉每個(gè)特征所有可能的舉止，如果某個(gè)樣本包含特征，那么特征對(duì)應(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 每一個(gè)樣本都是這樣的特征集合。

如果第一個(gè)特征有毒就是2，如果能食用就是1，下一個(gè)特征是形狀有6可能值，用整數(shù)3-8表示

相當(dāng)于把需要的特征維度都進(jìn)行排列離散化。最終只有1個(gè)大維特征

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'])

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