Apriori算法如何進行關聯分析

這篇文章給大家介紹Apriori算法如何進行關聯分析，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

從大規模數據集中尋找物品間的隱 含關系被稱作關聯分析(associationanalysis)或者關聯規則學習(associationrulelearning)

1、Apriori算法

（1）關聯分析

      關聯分析是一種在大規模數據集中尋找有趣關系的任務。這些關系可以有兩種形式:頻繁項集或者關聯規則。頻繁項集(frequentitemsets)是經常出現在一塊的物品的集合，關聯規則 (associationrules)暗示兩種物品之間可能存在很強的關系

樣本舉例：

       一個項集的支持度(support)被定義為數據集中包含該項集的記錄所占的比例，{豆奶)的支持度為4/5。而在5條交易記錄中有3條包含{豆奶，尿布},因此{豆奶，尿布}的支持度為3/5。支持度是針對項集來說的，因此可以定義一個最小支持度，而只保留滿足最小支持度的項集。

      可信度或置信度(confidence)是針對一條諸如{尿布}->{葡萄酒}的關聯規則來定義的。這條規則的可信度被定義為“支持度({尿布，葡萄酒})/支持度({尿布})”。從上述表格可以看到，由于{尿布，葡萄酒}的支持度為3/5,尿布的支持度為4/5,所以“尿布—>葡萄酒”的可信度為3/4=0.75。 這意味著對于包含“尿布”的所有記錄，我們的規則對其中75%的記錄都適用。

      非頻繁項集定義：就是項目里面沒有這個商品，然后就一定不會有此商品的頻繁項集合。也就是沒有小項目商品，就不會有包含它的集合。

       Apriori算法是發現頻繁項集的一種方法。Apriori算法的兩個輸人參數分別是最小支持度和數據集。該算法首先會生成所有單個物品的項集列表。接著掃描交易記錄來查看哪些項集滿足最小支持度要求，那些不滿足最小支持度的集合會被去掉。然后，對剩下來的集合進行組合以生成包含兩個元素的項集。接下來，再重新掃描交易記錄，去掉不滿足最小支持度的項集。該過程重復進行直到所有項集都被去掉。

偽代碼如下：
對數據集中的每條交易記錄tran
對每個候選項集can:
    檢查一下can是否是tran的子集:
        如果是，則增加can的計數值
對每個候遙項集:
如果其支持度不低于最小值，則保留該項集
返回所有頻繁項集列表

（1）構建第一個候選項集集合

def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
                
    C1.sort()
    return list(map(frozenset, C1))

（2）構建大于最小支持度的頻繁項集

def scanD(D, Ck, minSupport):
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if can not in ssCnt:
                    ssCnt[can]=1
                else: ssCnt[can] += 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key]/numItems
        if support >= minSupport:
            retList.insert(0,key)
        supportData[key] = support
    return retList, supportData#返回符合支持度的子項，以及所有項目計算的支持度

當集合中項的個數大于0時
    構建一個k個項組成的候選項集的列表
    檢查數據以確認每個項集都是頻繁的
    保留頻繁項集并構建k+1項組成的候選項集的列表

#構建多項的頻繁項目集
def aprioriGen(Lk, k): #creates Ck
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i+1, lenLk):
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()
            if L1==L2: #if first k-2 elements are equal
                retList.append(Lk[i] | Lk[j]) #set union
    return retList
#整體Apriori函數代碼,得到所有頻繁項集和符合最小支持度要求的集合
def apriori(dataSet, minSupport = 0.5):
    C1 = createC1(dataSet)
    D = list(map(set, dataSet))
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)#scan DB to get Lk
        supportData.update(supK)#update() 函數把字典dict2的鍵/值對更新到dict里
        L.append(Lk)
        k += 1
    return L, supportData

(2) 從頻繁項集中挖掘關聯規則

      對于關聯規則，我們也有類似的量化方法，這種量化指標稱為可信度。一條規則P—>H的可信度定義為Support(P|H)/support(P),在python中操作符丨表示集合的并操作，而數學上集合并的符號是U。P|H是指所有出現在集合P或者集合H中的元素。前面一節已經計算了所有頻繁項集支持度?，F在想獲得可信度，所需要做的只是取出那些支持度值做一次除法運算。

      如果某條規則并不滿足最小可信度要求，那么該規則的所有子集也不會滿足最小可信度要求

def generateRules(L, supportData, minConf=0.7):  #supportData is a dict coming from scanD
    bigRuleList = []
    for i in range(1, len(L)):#only get the sets with two or more items
        for freqSet in L[i]:
            print(L[i],freqSet)
            H1 = [frozenset([item]) for item in freqSet]
            print("i",i,"H1",H1)
            if (i > 1):
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)
    return bigRuleList

def calcConf(freqSet, H, supportData, brl, minConf=0.7):
    prunedH = [] #create new list to return
    for conseq in H:
        conf = supportData[freqSet]/supportData[freqSet-conseq] #calc confidence
        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):
    print("freqSet:",freqSet)
    m = len(H[0])
    if (len(freqSet) > (m + 1)): #try further merging
        Hmp1 = aprioriGen(H, m+1)#create Hm+1 new candidates
        print("Hmp1:",Hmp1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        print("Hmp1:",Hmp1)
        if (len(Hmp1) > 1):    #need at least two sets to merge
            print("len(Hmp1):",len(Hmp1))
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
            print("__")

關于Apriori算法如何進行關聯分析就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。