Apriori算法進行數據關聯分析

從大規模數據集中尋找物品間的隱含關系被稱作關聯分析或者關聯規則學習。這里的主要問題在于，尋找物品的不同組合是一項十分耗時的任務，所需的計算代價很高，蠻力搜索方法并不能解決這個問題，所以需要用更智能的方法在合理的時間范圍內找到頻繁項集。

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

a.解釋幾個概念

1、數據對象：

假如對超市購物單進行分析，用0，1，2，3代替一種物品，列表如[[1,2],[1,3,0],[0,1],[0,2],[1,2,3,0]]就是一組由5個購物單組成的數據對象，其中每個子列表代替一個購物單（如[1,2]），目標就是分析通過以上的數據分析每種物品的關聯關系。

2、支持度定義

支持度是衡量某個物品或物品組合是否頻繁的有效指標，計算公式為

支持度=該物品或物品組合出現次數/總購物單數

3、可信度定義

可信度是衡量兩個物品或物品組合之間的關聯程度的有效指標

如衡量A與B的關聯程度 A->B，簡單理解就是買了A的顧客會不會買B的關聯率

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

b.創建頻繁項集的apriori算法

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

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

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

濾完符合最小支持度的頻繁項集。

c.關聯規則apriori進行關聯分析

頻繁項集已經搭建好了，接下來才是數據挖掘的主場部分，開啟挖掘機模式。為了簡潔地表達挖掘方式，這里用一個頻繁項集{0，1，2，3}作為示例。我們依舊用遍歷的方法計算所有符合最小可信度的關聯關系，與計算頻繁項集一樣，挖掘依然采用分層方式，見下圖。

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

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