關聯分析（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 = 3 d ? 2 d + 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?
當 kle項的個數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=0.5):'''input:dataSet:training data,type:listoutput:freqSet:a list of all the k-itemset.each element is frozensetsupport: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]=0unique_value[item]+=1for item in unique_value.keys():supp=float(unique_value[item])/mif supp>=minSupp:I1.append(frozenset([item]))  #frozeset can serve as a key to dictionarysupport[frozenset([item])]=supp #only record the support of frequent itemsetI1.sort();freqSet.append(I1)k=2Lk=[]while k<=m:Lk=generateLk(freqSet[k-2],k)Lk,LkSupp=filterLk(dataSet,Lk,minSupp)freqSet.append(Lk)support.update(LkSupp)k+=1return freqSet,supportdef generateLk(freq,k):'''input:freq:  the itemset in freq is k-1 itemsetk:  create k-itemset from k-1_itemsetoutput:Lk:a list of k-itemset,frequent and infrequent'''Lk=[]for i in range(0,len(freq)-1):for j in range(i+1,len(freq)):if list(freq[i])[0:k-2]==list(freq[j])[0:k-2]:#fore k-1 item is identityLk.append(frozenset(freq[i]|freq[j]))return Lkdef filterLk(dataSet,Lk,minSupp=0.5):'''input:  Lk: all the k-itemset that need to be prunedoutput:filteredLk: frequent k-itemset which satisfy the minimum supportLkSupp: the support of frequent k-itemset'''LkSupp={}filteredLk=[]for itemset in Lk:supp=calcSupport(dataSet,itemset)if supp>=minSupp:LkSupp[frozenset(itemset)]=suppfilteredLk.append(frozenset(itemset))return filteredLk,LkSuppdef calcSupport(dataSet,Lk):'''calculate the support of Lk,Lk is a frozenset'''# Lk=list(Lk)[0]dataSet=map(set,dataSet)m=len(dataSet)num=0for tran in dataSet:if Lk.issubset(tran):num+=1return float(num)/m

測試

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

從頻繁項集中提取強規則

修剪

從頻繁項集中提取規則保證了這些規則的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=0.5):'''input:  freq   : the frequent k-itemset,k=1,2,...nsupport:  corresponding support  outpur:bigRuleList: a list of all the rule that satisfy min confidence'''bigRuleList=[]m=len(freq)for i in range(1,m):genRules(freq[i],support,bigRuleList,minConf)return bigRuleListdef genRules(freq,support,brl,minConf=0.5):'''extract rules that satisfy min confidence from a list of k-itemset(k>1)put the eligible rules in the brl'''if len(freq)==0:returnif len(freq[0])==2: #handle 2-itemsetfor itemset in freq:for conseq in itemset:conseq=frozenset([conseq])conf=support[itemset]/support[itemset-conseq]if conf>=minConf:print itemset-conseq, '-->',conseq,'conf:',confbrl.append((itemset-conseq,conseq,conf))elif len(freq[0])>2:H=[]for itemset in freq:# first generate 1-consequence listfor conseq in itemset:conseq=frozenset([conseq])conf=support[itemset]/support[itemset-conseq]if conf>=minConf:print itemset-conseq, '-->',conseq,'conf:',confbrl.append((itemset-conseq,conseq,conf))H.append(conseq)m=2#  generate 2,...,k-1 consequencewhile m<len(freq[0]):H=generateLk(H,m)for conseq in H:conf=support[itemset]/support[itemset-conseq]if conf>=minConf:print itemset-conseq, '-->',conseq,'conf:',confbrl.append((itemset-conseq,conseq,conf))m+=1

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

>>> 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)]