Aether_Q

當集合中項的個數大於0時  
	構建一個k個項組成的候選項集的列表  
	檢查數據以確認每個項集都是頻繁的  
		對數據集中的每條交易記錄tran  
		對每個候選項集can： 
			檢查一下can是否是tran的子集： 
				如果是，則增加can的計數值  
		對每個候選項集： 
		如果其支持度不低於最小值，則保留該項集 
		返回所有頻繁項集列表
	保留頻繁項集並構建k+1項組成的候選項集的列表
		頻繁項集第二定理：非頻繁項集的超集一定也是非頻繁的

# Apriori算法中的輔助函數

def loadDataSet():
    """
    創建一個用於測試的簡單數據集
    """
    return [[1,3,4], [2,3,5], [1,2,3,5], [2,5]]

def creatC1(dataSet):
    """
    輸入：數據集dataSet
    輸出：C1是大小為1的所有候選項集的集合
    过程：首先創建一個空列表C1，它用來存儲所有不重複的項值。接下來遍歷數據集中的所有交易記錄。對每一條記錄，遍歷記錄中的每一個項。如果某個物品項沒有在C1中出現，則將其添加到C1中。這裡並不是簡單地添加每個物品項，而是添加只包含該物品項的一個列表。這樣做的目的是為每個物品項構建一個集合。因為在Apriori算法的後續處理中，需要做集合操作。Python不能創建只有一個整數的集合，因此這裡實現必須使用列表（有興趣的讀者可以試一下）。這就是我們使用一個由單物品列表組成的大列表的原因。最後，對大列表進行排序並將其中的每個單元素列表映射到frozenset()，最後返回frozenset的列表
    細節：由於算法一開始是從輸入數據中提取候選項集列表，所以這裡需要一個特殊的函數來處理，而後續的項集列表則是按一定的格式存放的。這裡使用的格式就是Python中的frozenset類型。frozenset是指被“冰凍”的集合，就是說它們是不可改變的，即用户不能修改它們。這裡必須要使用frozenset而不是set類型，因為之後必須要將這些集合作為字典鍵值使用，使用frozenset可以實現這一點，而set卻做不到
    """
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
                
    C1.sort()
    return map(frozenset, C1)

def scanD(D, Ck, minSupport):
    """
    輸入：數據集，候選項集列表Ck，感興趣項集的最小支持度minSupport
    輸出：該函數用於從Ck生成Lk，另外，該函數會返回一個 包含支持度值的字典以備後用
    过程：函數首先創建一個空字典ssCnt，然後遍歷數據集中的所有交易記錄以及C1中的所有候選集。如果C1中的集合是記錄的一部分，那麼增加字典中對應的計數值。這裡字典的鍵就是集合。當掃描完數據集中的所有項以及所有候選集時，就需要計算支持度。不滿足最小支持度要求的集合不會輸出。函數也會先構建一個空列表，該列表包含滿足最小支持度要求的集合。下個循環遍歷字典中的每個元素並且計算支持度。如果支持度滿足最小支持度要求，則將字典元素添加到retList中，函數最後返回最頻繁項集的支持度supportData
    細節：可以使用語句retList.insert(0,key) 在列表的首部插入任意新的集合。當然也不一定非要在首部插入，這只是為了讓列表看起來有組織
    """
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if not ssCnt.has_key(can): 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


# Apriori算法

def aprioriGen(Lk, k):
    """
    輸入：頻繁項集列表Lk，項集元素個數k
    輸出：候選項集Ck
    舉例：以{0}、{1}、{2}作為輸入，會生成{0,1}、{0,2}以及{1,2}
    过程：首先創建一個空列表，然後計算Lk中的元素數目。接下來，比較Lk中的每一個元素與其他元素，這可以通過兩個for循環來實現。緊接著，取列表中的兩個集合進行比較。如果這兩個集合的前面k-2個元素都相等，那麼就將這兩個集合合成一個大小為k的集合
    細節：k-2有點讓人疑惑。接下來再進一步討論細節。當利用{0}、{1}、{2}構建{0,1}、{0,2}、{1,2}時，這實際上是將單個項組合到一塊。現在如果想利用{0,1}、{0,2}、{1,2}來創建三元素項集，應該怎麼做？如果將每兩個集合合併，就會得到{0,1,2}、{0,1,2}、{0,1,2}。也就是說，同樣的結果集合會重複3次。接下來需要掃描三元素項集列表來得到非重複結果，我們要做的是確保遍歷列表的次數最少。現在，如果比較集合{0,1}、{0,2}、{1,2}的第1個元素並只對第1個元素相同的集合求並操作，又會得到什麼結果？{0,1,2}，而且只有一次操作！這樣就不需要遍歷列表來尋找非重複值
    """
    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:
                retList.append(Lk[i] | Lk[j])
    return retList

def apriori(dataSet, minSupport = 0.5):
    """
    輸入：數據集dataSet，支持度minSupport
    輸出：L包含滿足最小支持度的頻繁項集列表，suppData是包含項集的支持度值字典
    过程：函數會生成候選項集的列表，這通過首先創建C1然後讀入數據集將其轉化為D（集合列表）來完成。程序中使用map函數將set()映射到dataSet列表中的每一項。接下來，使用scanD()函數來創建L1，並將L1放入列表L中。L會包含L1、L2、L3…。現在有了L1，後面會繼續找L2，L3…，這可以通過while循環來完成，它創建包含更大項集的更大列表，直到下個大的項集為空。如果這聽起來讓人有點困惑的話，那麼等一下你會看到它的工作流程。首先使用aprioriGen()來創建Ck，然後使用scanD()基於Ck來創建Lk。Ck是一個候選項集列表，然後scanD()會遍歷Ck，丟掉不滿足最小支持度要求的項集。Lk列表被添加到L，同時增加k的值，重複上述過程。最後，當Lk為空時，程序返回L並退出。
    """
    C1 = creatC1(dataSet)
    D = 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)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData


# 關聯規則生成函數

def generateRules(L, supportData, minConf=0.7):
    """
    輸入：頻繁項集列表、包含那些頻繁項集支持數據的字典、最小可信度閾值
    輸出：生成一個包含可信度的規則列表，後面可以基於可信度對它們進行排序
    过程：該函數遍歷L中的每一個頻繁項集並對每個頻繁項集創建只包含單個元素集合的列表H1。因為無法從單元素項集中構建關聯規則，所以要從包含兩個或者更多元素的項集開始規則構建過程。如果從集合{0,1,2}開始，那麼H1應該是[{0},{1},{2}]。如果頻繁項集的元素數目超過2，那麼會考慮對它做進一步的合併。具體合併可以通過函數rulesFromConseq()來完成，後面會詳細討論合併過程。如果項集中只有兩個元素，那麼使用函數calcConf()來計算可信度值
    """
    bigRuleList = []
    for i in range(1, len(L)):
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            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。接下來，遍歷H中的所有項集並計算它們的可信度值。可信度計算時使用supportData中的支持度數據。通過導入這些支持度數據，可以節省大量計算時間。如果某條規則滿足最小可信度值，那麼將這些規則輸出到螢幕顯示。通過檢查的規則也會被返回，並被用在下個函數rulesFromConseq()中。同時也需要對列表brl進行填充，而brl是前面通過檢查的bigRuleList
    """
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet]/supportData[freqSet-conseq]
        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):
    """
    作用：生成候選規則集合
    过程：為從最初的項集中生成更多的關聯規則，可以使用rulesFromConseq()函數。該函數有2個參數：一個是頻繁項集，另一個是可以出現在規則右部的元素列表H。函數先計算H中的頻繁集大小m。接下來查看該頻繁項集是否大到可以移除大小為m的子集。如果可以的話，則將其移除。可以使用函數aprioriGen()來生成H中元素的無重複組合。該結果會存儲在Hmp1中，這也是下一次迭代的H列表。Hmp1包含所有可能的規則。可以利用calcConf()來測試它們的可信度以確定規則是否滿足要求。如果不止一條規則滿足要求，那麼使用Hmp1迭代調用函數rulesFromConseq()來判斷是否可以進一步組合這些規則
    """
    m = len(H[0])
    if (len(freqSet) > (m+1)):
        Hmpl = aprioriGen(H, m+1)
        Hmpl = calcConf(freqSet, Hmpl, supportData, brl, minConf)
        if (len(Hmpl) > 1):
            rulesFromConseq(freqSet, Hmpl, supportData, brl, minConf)