Apriori算法進(jìn)行數(shù)據(jù)關(guān)聯(lián)分析

從大規(guī)模數(shù)據(jù)集中尋找物品間的隱含關(guān)系被稱作關(guān)聯(lián)分析或者關(guān)聯(lián)規(guī)則學(xué)習(xí)。這里的主要問題在于，尋找物品的不同組合是一項(xiàng)十分耗時(shí)的任務(wù)，所需的計(jì)算代價(jià)很高，蠻力搜索方法并不能解決這個(gè)問題，所以需要用更智能的方法在合理的時(shí)間范圍內(nèi)找到頻繁項(xiàng)集。

為了快速明確概念，從例子出發(fā)，現(xiàn)在面對(duì)一沓超市購物單，我們要從中分析出哪些物品與哪些物品的關(guān)聯(lián)度特別高，換句話說，當(dāng)顧客買了商品A后，有多大的幾率會(huì)購買B商品。通過關(guān)聯(lián)分析可以幫助超市擺放不同商品之間就有了隱形的規(guī)則，比如葡萄酒旁邊擺著尿布明顯提升了兩者的銷量。

a.解釋幾個(gè)概念

1、數(shù)據(jù)對(duì)象：

假如對(duì)超市購物單進(jìn)行分析，用0，1，2，3代替一種物品，列表如[[1,2],[1,3,0],[0,1],[0,2],[1,2,3,0]]就是一組由5個(gè)購物單組成的數(shù)據(jù)對(duì)象，其中每個(gè)子列表代替一個(gè)購物單（如[1,2]），目標(biāo)就是分析通過以上的數(shù)據(jù)分析每種物品的關(guān)聯(lián)關(guān)系。

2、支持度定義

支持度是衡量某個(gè)物品或物品組合是否頻繁的有效指標(biāo)，計(jì)算公式為

支持度=該物品或物品組合出現(xiàn)次數(shù)/總購物單數(shù)

3、可信度定義

可信度是衡量?jī)蓚€(gè)物品或物品組合之間的關(guān)聯(lián)程度的有效指標(biāo)

如衡量A與B的關(guān)聯(lián)程度 A->B，簡(jiǎn)單理解就是買了A的顧客會(huì)不會(huì)買B的關(guān)聯(lián)率

可信度=同時(shí)包含AB的支持度/A的支持度（{A,B}/{A}）

b.創(chuàng)建頻繁項(xiàng)集的apriori算法

1、什么是頻繁項(xiàng)集？簡(jiǎn)單理解就是滿足它的支持度大于最小支持度的集合，比如集合[1,2]的支持度是0.8，它大于最小支持度是0.7，那么它就是一個(gè)頻繁項(xiàng)集，由這樣的頻繁項(xiàng)集組合而成的集合，也可以大體理解為這個(gè)項(xiàng)目的所有頻繁項(xiàng)集的集。那么超市購物單這個(gè)頻繁項(xiàng)集有多少呢？假如我們只有{0，1，2，3}這四個(gè)商品，那么一共有15種，具體見下圖。

發(fā)現(xiàn)什么不爽的事了嗎？那就是僅僅4個(gè)商品就有15種集合，假如5種商品那就是31種集合，商品數(shù)越多帶來的集合數(shù)越大，就會(huì)影響計(jì)算機(jī)計(jì)算性能了。這里apriori算法的作用就來了。Apriori原理是說如果某個(gè)項(xiàng)集是頻繁的，那么它的所有子集也是頻繁的。更常用的是它的逆否命題，即如果一個(gè)項(xiàng)集是非頻繁的，那么它的所有超集也是非頻繁的。我們記住最后一句話，假如[2,3]是非頻繁的話，那么就可以直接排除{0，2，3}，{1，2，3}，{0，1，2，3}等集合了。具體的程序怎么解釋這個(gè)算法呢，就像上圖一樣，一層一層地計(jì)算是否頻繁集，下一層頻繁集來自于上一層頻繁集的合并，具體實(shí)現(xiàn)見下面代碼。

from numpy import *
def dataset():
    return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
dataset=dataset()
def createC1(dataset):
    sub=[]
    for line in dataset:
        for i in line:
            if [i] not in sub:
                sub.append([i])
    sub.sort()
    return map(frozenset,sub)
 
def scanD(D,C1,minsupport=0.7):
    ssdict={}
    L=[]
    supportData={}
    for tid in D:
        for i in C1:
            if i.issubset(tid):
                if i not in ssdict:
                    ssdict[i] = 1
                else:
                    ssdict[i] += 1
    num=float(len(D))
    for key in ssdict:
        support=ssdict[key]/num
        if support >= minsupport:
            L.insert(0,key)
            supportData[key] = support
    return L,supportData
 
def apriorizuhe(lk,k):
    lenlk=len(lk)
    readlist=[]
    for i in range(lenlk):
        for j in range(i+1,lenlk):
            L1=list(lk[i])[:k-2];L2=list(lk[j])[:k-2]
            if L1 == L2:
                readlist.append(lk[i]|lk[j])
    return readlist
 
def main(dataset,minsupport=0.7):
    D=map(set,dataset)
    C1=createC1(dataset)
    L,supportData=scanD(D,C1,minsupport)
    L=[L]
    k=2
    while(len(L[k-2])>0):
        ck=apriorizuhe(L[k-2],k)
        L1,supportdata=scanD(D,ck,minsupport)
        L.append(L1)
        supportData.update(supportdata)
        k += 1
    return L,supportData

解析apriorizuhe函數(shù)實(shí)現(xiàn)過程：假設(shè)以上都是滿足最小支持度的頻繁項(xiàng)集，從第一層到第二層的計(jì)算，依據(jù)apriorizuhe函數(shù)的過程，先找前k-2數(shù)，第一層前k-2數(shù)是空集，那么第一層所有的頻繁項(xiàng)集都可以排列組合進(jìn)行合并成第二層。但是到了第二層，前k-2個(gè)數(shù)相等的只有{0,1}和{0,2}了，所以只能這倆合并，減少了多余計(jì)算。根據(jù)apriori算法原則，不符合最小支持度的頻繁項(xiàng)集在計(jì)算支持度時(shí)直接被過濾了，所以能進(jìn)行這步運(yùn)算的都是過

濾完符合最小支持度的頻繁項(xiàng)集。

c.關(guān)聯(lián)規(guī)則apriori進(jìn)行關(guān)聯(lián)分析

頻繁項(xiàng)集已經(jīng)搭建好了，接下來才是數(shù)據(jù)挖掘的主場(chǎng)部分，開啟挖掘機(jī)模式。為了簡(jiǎn)潔地表達(dá)挖掘方式，這里用一個(gè)頻繁項(xiàng)集{0，1，2，3}作為示例。我們依舊用遍歷的方法計(jì)算所有符合最小可信度的關(guān)聯(lián)關(guān)系，與計(jì)算頻繁項(xiàng)集一樣，挖掘依然采用分層方式，見下圖。

從圖中可以發(fā)現(xiàn)：假設(shè)規(guī)則{0,1,2} ? {3}并不滿足最小可信度要求，那么就知道任何左部為{0,1,2}子集的規(guī)則也不會(huì)滿足最小可信度要求。如果{0,1,2}?{3}是一條低可信度規(guī)則，那么所有其他以3作為后件（箭頭右部包含3）的規(guī)則均為低可信度的。當(dāng)然這兩條規(guī)則是重復(fù)的，我們按照第二條規(guī)則編寫代碼（只用可用后件的并集或‘子集’）。

def generateRules(L,supportData,minconf=0.7):  #minconf為可信度
    bigrulelist=[]   #新建列表用于儲(chǔ)存關(guān)聯(lián)信息
    for i in range(1,len(L)):   #從第二個(gè)開始遍歷每一個(gè)由頻繁項(xiàng)集組成的列表
        for freqset in L[i]:   #從列表里遍歷每一個(gè)頻繁項(xiàng)集
            H1=[frozenset([item]) for item in freqset]   #對(duì)頻繁項(xiàng)集里的每個(gè)項(xiàng)提出來化為frozenset的形式儲(chǔ)存在列表中，如[frozenset([1]),frozenset([2])]
            print 'H1:',H1
            if (i > 1):   #因?yàn)榈诙械念l繁項(xiàng)集里的項(xiàng)都只有2個(gè)，所以選擇大于二行的進(jìn)行迭代求解，第一行只有一個(gè)直接忽略
                H1=clacconf(freqset,H1,supportData,bigrulelist,minconf)   #先算第二層匹配
                rulesfromconseq(freqset,H1,supportData,bigrulelist,minconf)              
            else:
                clacconf(freqset,H1,supportData,bigrulelist,minconf)   #直接求每個(gè)頻繁項(xiàng)作為后項(xiàng)的可信度，并保留可信度符合要求的項(xiàng)
    return bigrulelist
 
def clacconf(freqset,H,supportData,bigrulelist,minconf):   #輸入頻繁項(xiàng)集如frozenset([0,1])，H值作為后項(xiàng)，形式如[frozenset([0]),frozenset([1])]
    returnlist=[]
    for conseq in H:   #對(duì)頻繁項(xiàng)集里的每個(gè)項(xiàng)都假設(shè)是后項(xiàng)，計(jì)算該可信度
        a=supportData[freqset]/supportData[freqset-conseq]
        if a >= minconf:   #若該可信度符合要求，則輸出該后項(xiàng)
            print freqset-conseq,'-->',conseq, 'conf:',a
            bigrulelist.append((freqset-conseq,conseq,a))
            returnlist.append(conseq)
    return returnlist
    
def rulesfromconseq(freqset,H,supportData,bigrulelist,minconf):   #當(dāng)頻繁項(xiàng)集的內(nèi)容大于1時(shí)，如frozenset([0,1,2,3]),其H值為[frozenset([0]),frozenset([1]),...frozenset([3])]
    if len(H) == 0:   #如果上一層沒有匹配上則H為空集
        pass
    else:
        m=len(H[0])   #計(jì)算H值的第一個(gè)值的長度
        if (len(freqset) > (m+1)):   #若freqset的長度大于m+1的長度，則繼續(xù)迭代
            hmp=apriorigen(H,m+1)   #將單類別加類別，如{0,1,2}轉(zhuǎn)化為{0,1},{1,2}等
            print 'hmp:',hmp
            hmp=clacconf(freqset,hmp,supportData,bigrulelist,minconf)   #計(jì)算可信度
            if (len(hmp) > 1):   #如果后項(xiàng)的數(shù)量大于1，則還有合并的可能，繼續(xù)遞歸
                rulesfromconseq(freqset,hmp,supportData,bigrulelist,minconf)