關聯分析之Apriori學習筆記

關聯分析（Association analysis）

簡介

大量資料中隐藏的關系可以以‘關聯規則’和‘頻繁項集’的形式表示。rules：｛Diapers｝–>{Beer}說明兩者之間有很強的關系，購買Diapers的消費者通常會購買Beer。

除了應用在市場籃子資料（market basket data）中，關聯分析（association analysis）也可以應用在其他領域像bioinfomatic（分析複雜生物知識的學科）、medical diagnosis、Web mining和scientific data analysis。

在關聯分析中有兩個問題需要解決：1，從大量交易資料中發現隐藏的模式需要大量運算；2，有些模式可能隻是剛好發生，是以這些模式是虛假的。是以以下内容包括兩點：1，利用某種算法高效的挖掘這種模式；2，通過評估這些模式避免産生虛假結果。1

下面以market basket data分析為例：

幾個概念：

• Itemset

  令 I=i1,i2,⋯,id 是所有項的集合。在association analysis中，0或更多項的集合稱為itemset,具有 k 項的itemset稱為k-itemset。

• support count

  包含某個特定的Itemset的交易數目。在表6.1中2-itemset｛Bread,Milk｝的support count:σ({Bread,Milk})=3(1)

• rule

  規則，不難了解， X→Y(X∩Y=∅) ，箭頭左邊稱為先決條件（antecedent），箭頭右邊稱為結果（consequent）

• support

  某一項集或規則發生次數占總交易次數的百分比。 s(X→Y)=s({X,Y})=σ(X∪Y)N(2)

  例如：項集{Bread,Milk}的support為 35

• confidence

  X發生時Y發生的機率，也即條件機率。

  Confidence,c(X→Y)=σ(X∪Y)σ(X)(3)

尋找關聯規則的兩個步驟

給定一個交易集合 T ，尋找所有的滿足support≥minsup，并且confidence ≥ minconf的規則，minsup和minconf是相應的support和confidence的門檻值。

一種尋找關聯規則的方法是計算每一條可能規則的support和confidence，也就是我們說的蠻力法。這種方法需要大量的運算，因為規則的個數是呈指數增長的。一個包含 d 個項的資料集可以提取出的規則的數目是

R=3d−2d+1+1(自己證明？)

既然我們不想使用蠻力法，那麼應該使用什麼方法來尋找關聯規則呢？從上式(1)可以看出規則 X→Y 的support僅僅依賴于相應的項集 X∪Y 的support。例如，下面的規則的support完全相同，因為他們有相同的項集{Beer,Diapers,Milk}:

{Beer,Diapers} → {Milk}，{Beer,Milk} → {Diapers}，{Diapers,Milk} → {Beer}，{Beer} → {Diapers,Milk}，{Milk} → {Beer,Diapers}，{Diapers} → {Beer,Milk}

如果項集{Beer,Diapers,Milk}不是頻繁的，那麼可以直接裁剪掉以上所有6個候選規則。

是以，許多關聯規則挖掘算法将這個問題分解成兩個主要子任務：

- 産生頻繁項集：尋找所有達到support門檻值的項集。

- 産生規則：從頻繁項集中提取具有高置信度的規則，這些規則稱為強規則。2

産生頻繁項集

Apriori原理

我們可以使用枚舉法列舉出所有可能的k-itemset，然後計算每個項集的support。一個具有 m 項的資料集可以産生2m−1個項集，而其中滿足support門檻值的項集可能很少。顯然，當資料集很大時，枚舉法并不是個高效的方法。從下圖可以看出，有4個項的資料集，共有15個項集。

為了提高尋找頻繁項集的效率，我們應該把那些不可能滿足support門檻值的項集裁剪掉。

Apriori原理：如果一個項集是頻繁的，那麼它的子項集也一定是頻繁的

反過來說，如果一個項集不是頻繁的，那麼它的父項集也一定不是頻繁的。下圖加了陰影的項集被裁剪掉。

來自 機器學習實戰

根據以上原理，我們可以從上往下尋找頻繁項集。也就是，首先尋找頻繁項集：1-itemset，然後再由1-itemset組合成2-itemset…..（其實上圖的例子并沒有減少需要計算support的項集個數（這個是不是程式需要改進？？怎麼隻有1-itemset是infrequent的時候才能減少需要計算的項集數），如果 3 是infrequent的，那麼以下包含3的項集可以全部忽略）

僞代碼

1. 計算得到頻繁項集1-itemset的集合: Ii，i=1

2. k=2

當 k le 項的個數 N 時：

Ik=generateIk(D,Ii) …從I_i中産生頻繁項集的集合 Ii+1

i=k,k++

其中，generateIk函數是從k-itemset産生(k+1)-itemset

這個函數包含兩個過程：連接配接和篩選。

- 連接配接

當确定了一個頻繁項集k-itemset的全部集合後，它需要和自身連接配接，生成k+1-itemset。所謂連接配接，就是兩個不同的頻繁項集k-itemset，當它們的前（k-1）項都相同時，就進行合并。

- 篩選

從上面的定理我們得知，當子項不是頻繁項集時，父項也一定不是頻繁項集。但當子項都是頻繁項集時，其父項卻不一定是頻繁項集。是以，在連接配接得到(k+1)-itemset後，還需要計算它的support，如果不滿足support的門檻值，那麼就删去。

python程式

下面的程式和 機器學習實戰 中的程式思想基本相同，但我個人感覺書中的程式有些難以了解，是以自己寫了一個。 感謝 機器學習實戰 作者

'''産生頻繁項集'''
def genFreqItemset(dataSet,minSupp=):
    '''
    input:
            dataSet:training data,type:list
    output:
            freqSet:a list of all the k-itemset.each element is frozenset
            support:a dict,the support of frequent itemset
    '''
    unique_value={}
    I1=[]
    support={}
    freqSet=[]
    m=len(dataSet)
    for tran in dataSet:
        for item in tran:
            if item not in unique_value.keys():
                unique_value[item]=
            unique_value[item]+=

    for item in unique_value.keys():
        supp=float(unique_value[item])/m
        if supp>=minSupp:
            I1.append(frozenset([item]))  #frozeset can serve as a key to dictionary
            support[frozenset([item])]=supp #only record the support of frequent itemset
    I1.sort();
    freqSet.append(I1)
    k=
    Lk=[]
    while k<=m:
        Lk=generateLk(freqSet[k-],k)
        Lk,LkSupp=filterLk(dataSet,Lk,minSupp)
        freqSet.append(Lk)
        support.update(LkSupp)
        k+=
    return freqSet,support

def generateLk(freq,k):
    '''
    input:

            freq:  the itemset in freq is k-1 itemset
               k:  create k-itemset from k-1_itemset
    output:
            Lk:a list of k-itemset,frequent and infrequent
    '''
    Lk=[]
    for i in range(,len(freq)-):
        for j in range(i+,len(freq)):
            if list(freq[i])[:k-]==list(freq[j])[:k-]:#fore k-1 item is identity
                Lk.append(frozenset(freq[i]|freq[j]))
    return Lk

def filterLk(dataSet,Lk,minSupp=):
    '''
    input:  
            Lk: all the k-itemset that need to be pruned
    output:
            filteredLk: frequent k-itemset which satisfy the minimum support
                LkSupp: the support of frequent k-itemset
    '''
    LkSupp={}
    filteredLk=[]
    for itemset in Lk:
        supp=calcSupport(dataSet,itemset)
        if supp>=minSupp:
            LkSupp[frozenset(itemset)]=supp
            filteredLk.append(frozenset(itemset))
    return filteredLk,LkSupp

def calcSupport(dataSet,Lk):
    '''
        calculate the support of Lk,
        Lk is a frozenset
    '''
   # Lk=list(Lk)[0]
    dataSet=map(set,dataSet)
    m=len(dataSet)
    num=
    for tran in dataSet:
        if Lk.issubset(tran):
            num+=
    return float(num)/m
           

測試

>>> dataSet
[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
>>> Lk,support=apriori_f.genFreqItemset(dataSet,)
>>> Lk[]
[frozenset([]), frozenset([]), frozenset([]), frozenset([])]
>>> Lk[]
[frozenset([, ]), frozenset([, ]), frozenset([, ]), frozenset([, ])]
>>> Lk[]
[frozenset([, , ])]
>>> Lk[]
[]
>>> support
{frozenset([]): , frozenset([]): , frozenset([, , ]): , frozenset([, ]): , frozenset([, ]): , frozenset([, ]): , frozenset([]): , frozenset([, ]): , frozenset([]): }
           

從頻繁項集中提取強規則

修剪

從頻繁項集中提取規則保證了這些規則的support一定滿足minsupport，接下來就是置信度的計算。同樣，我們可以使用蠻力列舉所有可能的規則，并計算其置信度，但這樣我們會做許多無用功。一個包含 n 項的頻繁項集，可能産生的規則數是2n−1（自己證明）。

為了提高效率，我們采用同前面Apriori算法類似的裁剪方法：

如果 X→Y−X 不滿足最小置信度，那麼 X′→Y−X′(X′⊆X) 也一定不滿足最小置信度。

證明： c(X→Y−X)=support(Y)support(X)<minConfidence

c(X′→Y−X′)=support(Y)support(X′) ，其中， support(X′)≥support(X) ，是以有 c(X′→Y−X′)<minConfidence

如下圖：

圖中添加陰影的規則全部被裁剪掉。

python程式

def getBigRule(freq,support,minConf=):
    '''
    input:  
            freq   : the frequent k-itemset,k=1,2,...n
            support:  corresponding support  
    outpur:
            bigRuleList: a list of all the rule that satisfy min confidence
    '''
    bigRuleList=[]
    m=len(freq)
    for i in range(,m):
        genRules(freq[i],support,bigRuleList,minConf)
    return bigRuleList

def genRules(freq,support,brl,minConf=):
    '''
    extract rules that satisfy min confidence from a list of k-itemset(k>1)
    put the eligible rules in the brl
    '''
    if len(freq)==:return
    if len(freq[])==: #handle 2-itemset
        for itemset in freq:
            for conseq in itemset:
                conseq=frozenset([conseq])
                conf=support[itemset]/support[itemset-conseq]
                if conf>=minConf:
                    print itemset-conseq, '-->',conseq,'conf:',conf
                    brl.append((itemset-conseq,conseq,conf))
    elif len(freq[])>:
        H=[]
        for itemset in freq:
            # first generate 1-consequence list
            for conseq in itemset:
                conseq=frozenset([conseq])
                conf=support[itemset]/support[itemset-conseq]
                if conf>=minConf:
                    print itemset-conseq, '-->',conseq,'conf:',conf
                    brl.append((itemset-conseq,conseq,conf))
                    H.append(conseq)
            m=
            #  generate 2,...,k-1 consequence
            while m<len(freq[]):
                H=generateLk(H,m)
                for conseq in H:
                    conf=support[itemset]/support[itemset-conseq]
                    if conf>=minConf:
                        print itemset-conseq, '-->',conseq,'conf:',conf
                        brl.append((itemset-conseq,conseq,conf))
                m+=
           

利用以上得到的頻繁項集測試：

>>> brl=apriori_f.getBigRule(freqSet,support,0.7)
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 1.0
frozenset([2]) --> frozenset([5]) conf: 1.0
frozenset([3, 5]) --> frozenset([2]) conf: 1.0
frozenset([2, 3]) --> frozenset([5]) conf: 1.0
>>> brl
[(frozenset([1]), frozenset([3]), 1.0), (frozenset([5]), frozenset([2]), 1.0), (frozenset([2]), frozenset([5]), 1.0), (frozenset([3, 5]), frozenset([2]), 1.0), (frozenset([2, 3]), frozenset([5]), 1.0)]
           

參考資料：

[1] 機器學習實戰

[2] 使用Apriori算法和FP-growth算法進行關聯分析

1. Introduction to data mining Ch6 ↩
2. Introduction to data mining Ch6 ↩