基于Python的機(jī)器學(xué)習(xí)實戰(zhàn)：Apriori

1.關(guān)聯(lián)分析

關(guān)聯(lián)分析是一種在大規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的任務(wù)。這種關(guān)系表現(xiàn)為兩種形式：

1.頻繁項集(frequency item sets)：經(jīng)常同時出現(xiàn)的一些元素的集合；

2.關(guān)聯(lián)規(guī)則(association rules): 意味著兩種元素之間存在很強(qiáng)的關(guān)系。

下面舉例來說明上面的兩個概念：

頻繁項集是指經(jīng)常出現(xiàn)在一起的元素的集合，上表中的集合 {葡萄酒，尿布，豆奶} 就是頻繁項集的一個例子。同樣可以找到如 “尿布 –> 葡萄酒”的關(guān)聯(lián)規(guī)則，意味著如果有人買了尿布，就很可能也會買葡萄酒。使用頻繁項集和關(guān)聯(lián)規(guī)則，商家可以更好地理解顧客的消費行為，所以大部分關(guān)聯(lián)規(guī)則分析示例來自零售業(yè)。
理解關(guān)聯(lián)分析首先需要搞清楚下面三個問題：
    1.如何定義這些有用的關(guān)系？
    2.這些關(guān)系的強(qiáng)弱程度又是如何定義？
    3.頻繁的定義是什么？
要回答上面的問題，最重要的是理解兩個概念：支持度和可信度。
   支持度：一個項集的支持度(support)被定義為數(shù)據(jù)集中包含該項集的記錄占總記錄的比例。從表1 可以看出 項集 {豆奶} 的支持度為 4/5; 而在 5 條交易記錄中 3 條包含 {豆奶，尿布}，因此 {豆奶，尿布} 的支持度為 3/5.
    可信度或置信度(confidence)：是針對一條諸如尿布??>葡萄酒的關(guān)聯(lián)規(guī)則來定義的，這條規(guī)則的可信度被定義為“ 支持度({尿布,葡萄酒})  /  支持度({尿布})”。在表1 中可以發(fā)現(xiàn)  {尿布,葡萄酒} 的支持度是 3/5, {尿布} 的支持度為 4/5, 所以關(guān)聯(lián)規(guī)則 “尿布 –> 葡萄酒”的可信度為 3/4=0.75, 意思是對于所有包含 “尿布”的記錄中，該關(guān)聯(lián)規(guī)則對其中的 75% 記錄都適用。
2. Apriori 原理
假設(shè)經(jīng)營了一家雜貨店，于是我們對那些經(jīng)常在一起購買的商品非常感興趣。假設(shè)我們只有 4 種商品：商品0，商品1，商品 2，商品3. 那么如何得可能被一起購買的商品的組合？

上圖顯示了物品之間所有可能的組合，從上往下一個集合是 ??，表示不包含任何物品的空集，物品集合之間的連線表明兩個或者更多集合可以組合形成一個更大的集合。
我們的目標(biāo)是找到經(jīng)常在一起購買的物品集合。這里使用集合的支持度來度量其出現(xiàn)的頻率。一個集合出現(xiàn)的支持度是指有多少比例的交易記錄包含該集合。例如，對于上圖，要計算 0,3 的支持度，直接的想法是遍歷每條記錄，統(tǒng)計包含有 0 和 3 的記錄的數(shù)量，使用該數(shù)量除以總記錄數(shù)，就可以得到支持度。而這只是針對單個集合 0,3. 要獲得每種可能集合的支持度就需要多次重復(fù)上述過程。對于上圖，雖然僅有4中物品，也需要遍歷數(shù)據(jù)15次。隨著物品數(shù)目的增加，遍歷次數(shù)會急劇增加，對于包含 N 種物品的數(shù)據(jù)集共有 2N?1 種項集組合。所以即使只出售 100  種商品的商店也會有 1.26×1030 中可能的組合。計算量太大。
為了降低計算時間，研究人員發(fā)現(xiàn)了Apriori 原理，可以幫我們減少感興趣的頻繁項集的數(shù)目。
    Apriori 的原理：如果某個項集是頻繁項集，那么它所有的子集也是頻繁的。
    即如果 {0,1} 是頻繁的，那么 {0}, {1} 也一定是頻繁的。
這個原理直觀上沒有什么用，但是反過來看就有用了，也就是說如果一個項集是非頻繁的，那么它的所有超集也是非頻繁的。如下圖所示：

 

3. 使用 Apriori 算法來發(fā)現(xiàn)頻繁集
上面提到，關(guān)聯(lián)分析的兩個目標(biāo)：發(fā)現(xiàn)頻繁項集和發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。首先需要找到頻繁項集，然后根據(jù)頻繁項集獲得關(guān)聯(lián)規(guī)則。首先來討論發(fā)現(xiàn)頻繁項集。Apriori 是發(fā)現(xiàn)頻繁項集的一種方法。
    首先會生成所有單個物品的項集列表；
    掃描交易記錄來查看哪些項集滿足最小支持度要求，那些不滿足最小支持度的集合會被去掉；
    對剩下的集合進(jìn)行組合以生成包含兩個元素的項集；
    接下來重新掃描交易記錄，去掉不滿足最小支持度的項集，重復(fù)進(jìn)行直到所有項集都被去掉。
數(shù)據(jù)集掃描的偽代碼：
    對數(shù)據(jù)集中的每條交易記錄tran:
    對每個候選項集can:
    檢查一下can是否是tran的子集：
    如果是，則增加can的計數(shù)值
    對每個候選項集：
    如果其支持度不低于最低值，則保留
    返回所有頻繁項集列表
有上面的偽代碼寫出代碼如下：
# -*- coding: utf-8 -*-
"""
Apriori exercise.
Created on Fri Nov 27 11:09:03 2015

@author: 90Zeng
"""

def loadDataSet():
    '''創(chuàng)建一個用于測試的簡單的數(shù)據(jù)集'''
    return [ [ 1, 3, 4 ], [ 2, 3, 5 ], [ 1, 2, 3, 5 ], [ 2, 5 ] ]

def createC1( dataSet ):
    '''
    構(gòu)建初始候選項集的列表，即所有候選項集只包含一個元素，
    C1是大小為1的所有候選項集的集合
    '''
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if [ item ] not in C1:
                C1.append( [ item ] )
    C1.sort()
    return map( frozenset, C1 )

def scanD( D, Ck, minSupport ):
    '''
    計算Ck中的項集在數(shù)據(jù)集合D(記錄或者transactions)中的支持度,
    返回滿足最小支持度的項集的集合，和所有項集支持度信息的字典。
    '''
    ssCnt = {}
    for tid in D:
        # 對于每一條transaction
        for can in Ck:
            # 對于每一個候選項集can，檢查是否是transaction的一部分
            # 即該候選can是否得到transaction的支持
            if can.issubset( tid ):
                ssCnt[ can ] = ssCnt.get( can, 0) + 1
    numItems = float( len( D ) )
    retList = []
    supportData = {}
    for key in ssCnt:
        # 每個項集的支持度
        support = ssCnt[ key ] / numItems
        
        # 將滿足最小支持度的項集，加入retList
        if support >= minSupport:
            retList.insert( 0, key )
            
        # 匯總支持度數(shù)據(jù)
        supportData[ key ] = support
    return retList, supportData

注：關(guān)于上面代碼中 “frozenset”，是為了凍結(jié)集合，使集合由“可變”變?yōu)?“不可變”，這樣，這些集合就可以作為字典的鍵值。

首先來測試一下上面代碼，看看運(yùn)行效果：
 

if __name__ == '__main__':
    # 導(dǎo)入數(shù)據(jù)集
    myDat = loadDataSet()
    # 構(gòu)建第一個候選項集列表C1
    C1 = createC1( myDat )
    
    # 構(gòu)建集合表示的數(shù)據(jù)集 D
    D = map( set, myDat )
    # 選擇出支持度不小于0.5 的項集作為頻繁項集
    L, suppData = scanD( D, C1, 0.5 )
   
    print u"頻繁項集L：", L
    print u"所有候選項集的支持度信息：", suppData

運(yùn)行結(jié)果：

>>> runfile(‘E:/Python/PythonScripts/Apriori.py’, wdir=r’E:/Python/PythonScripts’)
頻繁項集L： [frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])]
所有候選項集的支持度信息： {frozenset([4]): 0.25, frozenset([5]): 0.75, frozenset([2]): 0.75, frozenset([3]): 0.75, frozenset([1]): 0.5}

可以看出，只有支持度不小于 0.5 的項集被選中到 L 中作為頻繁項集，根據(jù)不同的需求，我們可以設(shè)定最小支持度的值，從而得到我們想要的頻繁項集。

上面的示例只是選擇出來了項集中只包含一個元素的頻繁項集，下面需要整合上面的代碼，選擇出包含 2個，3個直至個數(shù)據(jù)等于所有候選元素個數(shù)的頻繁項集，
從而形成完整的 Apriori 的算法，首先給出偽代碼：
    當(dāng)集合中的元素個數(shù)大于 0 時：
    構(gòu)建一個 k 個項組成的候選項集列表
    檢查數(shù)據(jù)，確認(rèn)每個項集都是頻繁項集
    保留頻繁項集，并構(gòu)建 k+1 項組成的候選項集的列表
程序清單：
# Aprior算法
def aprioriGen( Lk, k ):
    '''
    由初始候選項集的集合Lk生成新的生成候選項集，
    k表示生成的新項集中所含有的元素個數(shù)
    '''
    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 ):
    # 構(gòu)建初始候選項集C1
    C1 = createC1( dataSet )
    
    # 將dataSet集合化，以滿足scanD的格式要求
    D = map( set, dataSet )
    
    # 構(gòu)建初始的頻繁項集，即所有項集只有一個元素
    L1, suppData = scanD( D, C1, minSupport )
    L = [ L1 ]
    # 最初的L1中的每個項集含有一個元素，新生成的
    # 項集應(yīng)該含有2個元素，所以 k=2
    k = 2
    
    while ( len( L[ k - 2 ] ) > 0 ):
        Ck = aprioriGen( L[ k - 2 ], k )
        Lk, supK = scanD( D, Ck, minSupport )
        
        # 將新的項集的支持度數(shù)據(jù)加入原來的總支持度字典中
        suppData.update( supK )
        
        # 將符合最小支持度要求的項集加入L
        L.append( Lk )
        
        # 新生成的項集中的元素個數(shù)應(yīng)不斷增加
        k += 1
    # 返回所有滿足條件的頻繁項集的列表，和所有候選項集的支持度信息
    return L, suppData
關(guān)于上面程序 函數(shù) aprioriGen 中的 k?2的說明：當(dāng)利用 {0}, {1}, {2} 這些只含有一個元素的候選項集構(gòu)建含有 2 個元素的候選項集時，就是兩兩合并得到 {0,1}, {0,2}, {1,2}; 如果進(jìn)一步用包含連個元素的候選項集來構(gòu)建包含 3 個元素的候選項集，同樣兩兩合并，就會得到 {0,1,2},{0,1,2},{0,1,2}. 就是說會出現(xiàn)重復(fù)的項集，接下來就需要掃描三元素項集得到非重復(fù)結(jié)果，顯然增加了計算時間?，F(xiàn)在，如果比較 {0,1}, {0,2}, {1,2} 的第 0 個元素并只對第 0 個元素相同的集合求并，就會得到 {0,1,2}, 而且只有一次操作，這樣就不需要遍歷列表來尋找非重復(fù)值。

測試上面代碼：

if __name__ == '__main__':
    # 導(dǎo)入數(shù)據(jù)集
    myDat = loadDataSet()    
    # 選擇頻繁項集
    L, suppData = apriori( myDat, 0.5 )
    print u"頻繁項集L：", L
    print u"所有候選項集的支持度信息：", suppData

運(yùn)行結(jié)果（最小支持度 0.5） ：

>>> runfile('E:/Python/PythonScripts/Apriori.py', wdir=r'E:/Python/PythonScripts')
頻繁項集L： [[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])], [frozenset([2, 3, 5])], []]
所有候選項集的支持度信息： {frozenset([5]): 0.75, frozenset([3]): 0.75, frozenset([2, 3, 5]): 0.5, frozenset([1, 2]): 0.25, frozenset([1, 5]): 0.25, frozenset([3, 5]): 0.5, frozenset([4]): 0.25, frozenset([2, 3]): 0.5, frozenset([2, 5]): 0.75, frozenset([1]): 0.5, frozenset([1, 3]): 0.5, frozenset([2]): 0.75}

在測試一下最小支持度為 0.7 時的情況：

>>> runfile('E:/Python/PythonScripts/Apriori.py', wdir=r'E:/Python/PythonScripts')
頻繁項集L： [[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], []]
所有候選項集的支持度信息： {frozenset([5]): 0.75, frozenset([3]): 0.75, frozenset([3, 5]): 0.5, frozenset([4]): 0.25, frozenset([2, 3]): 0.5, frozenset([2, 5]): 0.75, frozenset([1]): 0.5, frozenset([2]): 0.75}
頻繁項集相比最小支持度 0.5 時要少，符合預(yù)期。
4.從頻繁集中挖掘關(guān)聯(lián)規(guī)則
要找到關(guān)聯(lián)規(guī)則，先從一個頻繁集開始，我們想知道對于頻繁項集中的元素能否獲取其它內(nèi)容，即某個元素或者某個集合可能會推導(dǎo)出另一個元素。從表1 可以得到，如果有一個頻繁項集 {豆奶，萵苣}，那么就可能有一條關(guān)聯(lián)規(guī)則 “豆奶 –> 萵苣”，意味著如果有人購買了豆奶，那么在統(tǒng)計上他會購買萵苣的概率較大。但是這一條反過來并不一定成立。
從一個頻繁項集可以產(chǎn)生多少條關(guān)聯(lián)規(guī)則呢？可以基于該頻繁項集生成一個可能的規(guī)則列表，然后測試每條規(guī)則的可信度，如果可信度不滿足最小值要求，則去掉該規(guī)則。類似于前面討論的頻繁項集生成，一個頻繁項集可以產(chǎn)生許多可能的關(guān)聯(lián)規(guī)則，如果能在計算規(guī)則可信度之前就減少規(guī)則的數(shù)目，就會很好的提高計算效率。
這里有一條規(guī)律就是：如果某條規(guī)則并不滿足最小可信度要求，那么該規(guī)則的所有子集也不會滿足最小可信度要求，例如下圖的解釋：

 

所以，可以利用上圖所示的性質(zhì)來減少測試的規(guī)則數(shù)目。

關(guān)聯(lián)規(guī)則生成函數(shù)清單：

# 規(guī)則生成與評價   
def calcConf( freqSet, H, supportData, brl, minConf=0.7 ):
    '''
    計算規(guī)則的可信度，返回滿足最小可信度的規(guī)則。
    
    freqSet(frozenset):頻繁項集
    H(frozenset):頻繁項集中所有的元素
    supportData(dic):頻繁項集中所有元素的支持度
    brl(tuple):滿足可信度條件的關(guān)聯(lián)規(guī)則
    minConf(float):最小可信度
    '''
    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 ):
    '''
    對頻繁項集中元素超過2的項集進(jìn)行合并。
    
    freqSet(frozenset):頻繁項集
    H(frozenset):頻繁項集中的所有元素，即可以出現(xiàn)在規(guī)則右部的元素
    supportData(dict):所有項集的支持度信息
    brl(tuple):生成的規(guī)則
    
    '''
    m = len( H[ 0 ] )
    
    # 查看頻繁項集是否大到移除大小為 m　的子集
    if len( freqSet ) > m + 1:
        Hmp1 = aprioriGen( H, m + 1 )
        Hmp1 = calcConf( freqSet, Hmp1, supportData, brl, minConf )
        
        # 如果不止一條規(guī)則滿足要求，進(jìn)一步遞歸合并
        if len( Hmp1 ) > 1:
            rulesFromConseq( freqSet, Hmp1, supportData, brl, minConf )

def generateRules( L, supportData, minConf=0.7 ):
    '''
    根據(jù)頻繁項集和最小可信度生成規(guī)則。
    
    L(list):存儲頻繁項集
    supportData(dict):存儲著所有項集（不僅僅是頻繁項集）的支持度
    minConf(float):最小可信度
    '''
    bigRuleList = []
    for i in range( 1, len( L ) ):
        for freqSet in L[ i ]:
            # 對于每一個頻繁項集的集合freqSet
            H1 = [ frozenset( [ item ] ) for item in freqSet ]
            
            # 如果頻繁項集中的元素個數(shù)大于2，需要進(jìn)一步合并
            if i > 1:
                rulesFromConseq( freqSet, H1, supportData, bigRuleList, minConf )
            else:
                calcConf( freqSet, H1, supportData, bigRuleList, minConf )
    return bigRuleList

測試：

if __name__ == '__main__':
    # 導(dǎo)入數(shù)據(jù)集
    myDat = loadDataSet()    
    # 選擇頻繁項集
    L, suppData = apriori( myDat, 0.5 )
    
    rules = generateRules( L, suppData, minConf=0.7 )
    print 'rules:\n', rules

運(yùn)行結(jié)果：

>>> runfile('E:/Python/PythonScripts/Apriori.py', wdir=r'E:/Python/PythonScripts')
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 1.0
frozenset([2]) --> frozenset([5]) conf: 1.0
rules:
[(frozenset([1]), frozenset([3]), 1.0), (frozenset([5]), frozenset([2]), 1.0), (frozenset([2]), frozenset([5]), 1.0)]

將可信度降為 0.5 之后：

>>> runfile('E:/Python/PythonScripts/Apriori.py', wdir=r'E:/Python/PythonScripts')
frozenset([3]) --> frozenset([1]) conf: 0.666666666667
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 1.0
frozenset([2]) --> frozenset([5]) conf: 1.0
frozenset([3]) --> frozenset([2]) conf: 0.666666666667
frozenset([2]) --> frozenset([3]) conf: 0.666666666667
frozenset([5]) --> frozenset([3]) conf: 0.666666666667
frozenset([3]) --> frozenset([5]) conf: 0.666666666667
frozenset([5]) --> frozenset([2, 3]) conf: 0.666666666667
frozenset([3]) --> frozenset([2, 5]) conf: 0.666666666667
frozenset([2]) --> frozenset([3, 5]) conf: 0.666666666667
rules:
[(frozenset([3]), frozenset([1]), 0.6666666666666666), (frozenset([1]), frozenset([3]), 1.0), (frozenset([5]), frozenset([2]), 1.0), (frozenset([2]), frozenset([5]), 1.0), (frozenset([3]), frozenset([2]), 0.6666666666666666), (frozenset([2]), frozenset([3]), 0.6666666666666666), (frozenset([5]), frozenset([3]), 0.6666666666666666), (frozenset([3]), frozenset([5]), 0.6666666666666666), (frozenset([5]), frozenset([2, 3]), 0.6666666666666666), (frozenset([3]), frozenset([2, 5]), 0.6666666666666666), (frozenset([2]), frozenset([3, 5]), 0.6666666666666666)]
一旦降低可信度閾值，就可以獲得更多的規(guī)則。
5. 總結(jié)
有上面分析可以看出 Apriori 算法易編碼，缺點是在大數(shù)據(jù)集上可能較慢。