Apriori的python3版本實作

參考以下一片寫的很詳細的文章：

https://blog.csdn.net/sinat_17196995/article/details/71124284

其中把舊代碼在python3中報錯的都改過來了！良心~~

(比如報錯has_key(), map對象無len())

以下的連結是圖解整個過程，個人覺得清晰明了：

https://www.cnblogs.com/bigmonkey/p/7405555.html

Apriori算法不适用于非重複項集數元素較多的案例，建議分析的商品種類10左右。

輸入：

dataset的類型應該是list形式：

dataSet=[['豆奶','莴苣'],
     ['莴苣','尿布','葡萄酒','甜菜'],
     ['豆奶','尿布','葡萄酒','橙汁'],
     ['莴苣','豆奶','尿布','葡萄酒'],
     ['莴苣','豆奶','尿布','橙汁']]
           

裝入黑盒：

L,suppData=apriori(dataSet,0.5)
rules=generateRules(L,suppData,0.7)
           

輸出：

L：頻繁項集

suppData:支援度

rules：規則的置信度

以下是“黑盒”

Apriori.py:

def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item]) #store all the item unrepeatly

    C1.sort()
    #return map(frozenset, C1)#frozen set, user can't change it.
    return list(map(frozenset, C1))

def scanD(D,Ck,minSupport):
#參數：資料集、候選項集清單 Ck以及感興趣項集的最小支援度 minSupport
    ssCnt={}
    for tid in D:#周遊資料集
        for can in Ck:#周遊候選項
            if can.issubset(tid):#判斷候選項中是否含資料集的各項
                #if not ssCnt.has_key(can): # python3 can not support
                if not can in ssCnt:
                    ssCnt[can]= #不含設為1
                else: ssCnt[can]+=#有則計數加1
    numItems=float(len(D))#資料集大小
    retList = []#L1初始化
    supportData = {}#記錄候選項中各個資料的支援度
    for key in ssCnt:
        support = ssCnt[key]/numItems#計算支援度
        if support >= minSupport:
            retList.insert(,key)#滿足條件加入L1中
        supportData[key] = support
    return retList, supportData

def aprioriGen(Lk, k): #組合，向上合并
    #creates Ck 參數：頻繁項集清單 Lk 與項集元素個數 k
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i+, lenLk): #兩兩組合周遊
            L1 = list(Lk[i])[:k-]; L2 = list(Lk[j])[:k-]
            L1.sort(); L2.sort()
            if L1==L2: #若兩個集合的前k-2個項相同時,則将兩個集合合并
                retList.append(Lk[i] | Lk[j]) #set union
    return retList


def apriori(dataSet, minSupport = ):
    C1 = createC1(dataSet)
    D = list(map(set, dataSet)) #python3
    L1, supportData = scanD(D, C1, minSupport)#單項最小支援度判斷 0.5，生成L1
    L = [L1]
    k = 
    while (len(L[k-]) > ):#建立包含更大項集的更大清單,直到下一個大的項集為空
        Ck = aprioriGen(L[k-], k)#Ck
        Lk, supK = scanD(D, Ck, minSupport)#get Lk
        supportData.update(supK)
        L.append(Lk)
        k += 
    return L, supportData

def generateRules(L, supportData, minConf=):
    #頻繁項集清單、包含那些頻繁項集支援資料的字典、最小可信度門檻值
    bigRuleList = [] #存儲所有的關聯規則
    for i in range(, len(L)):  #隻擷取有兩個或者更多集合的項目，從1,即第二個元素開始，L[0]是單個元素的
        # 兩個及以上的才可能有關聯一說，單個元素的項集不存在關聯問題
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            #該函數周遊L中的每一個頻繁項集并對每個頻繁項集建立隻包含單個元素集合的清單H1
            if (i > ):
            #如果頻繁項集元素數目超過2,那麼會考慮對它做進一步的合并
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:#第一層時，後件數為1
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)# 調用函數2
    return bigRuleList

def calcConf(freqSet, H, supportData, brl, minConf=):
    #針對項集中隻有兩個元素時，計算可信度
    prunedH = []#傳回一個滿足最小可信度要求的規則清單
    for conseq in H:#後件，周遊 H中的所有項集并計算它們的可信度值
        conf = supportData[freqSet]/supportData[freqSet-conseq] #可信度計算，結合支援度資料
        if conf >= minConf:
            print (freqSet-conseq,'-->',conseq,'conf:',conf)
            #如果某條規則滿足最小可信度值,那麼将這些規則輸出到螢幕顯示
            brl.append((freqSet-conseq, conseq, conf))#添加到規則裡，brl 是前面通過檢查的 bigRuleList
            prunedH.append(conseq)#同樣需要放入清單到後面檢查
    return prunedH


def rulesFromConseq(freqSet, H, supportData, brl, minConf=):
    #參數:一個是頻繁項集,另一個是可以出現在規則右部的元素清單 H
    m = len(H[])
    if (len(freqSet) > (m + )): #頻繁項集元素數目大于單個集合的元素數
        Hmp1 = aprioriGen(H, m+)#存在不同順序、元素相同的集合，合并具有相同部分的集合
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)#計算可信度
        if (len(Hmp1) > ):    
        #滿足最小可信度要求的規則清單多于1,則遞歸來判斷是否可以進一步組合這些規則
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)