在實際生産生活我們經常會遇到一些“關聯分析”(Association Analyse)的任務。舉幾個實際例子。
1.人們的購物清單裡面的各個商品有沒有什麼關聯呢？就像下面這個購物清單寫的那樣子，右邊是各個顧客所買的東西。
有的時候我們想問，顧客購買商品的時候會不會多個商品組合起來買呢？顧客會不會傾向于豆奶和尿布這兩樣商品一起買？我們怎麼從一份購物清單裡面發現這種往往會一起出現的商品組合呢？
2.現在幾乎人人都有自己的PC，都會在自己的電腦上安裝自己喜歡的軟體。現在給出不同工作領域的使用者的軟體清單，我們能不能發現同種身份的人一般都會按照那些共性的軟體呢？這樣或許我們就可以給使用者推薦他所在領域的受歡迎的軟體。
能不能通過計算得到學生群體的共性軟體呢？
3.總結疾病的特征。給我們一些疾病的特征，我們如何從這些資料總結出某種疾病的普遍特征呢？比如，給一些患流行性感冒的病人的生理特征資料，我們如何從這些資料發現患流行性感冒的普遍症狀呢？
以上這些問題都是關系分析的問題，這些問題希望在資料集中發現其中蘊含的關系，企圖發現裡面存在的頻繁出現的組合（比如學生會經常按照那些軟體）或者項與項之間的關系（比如一般安裝微信的人也會順帶安裝QQ）。發現頻繁出現的組合叫做發現頻繁項集（frequent item set)，而找出項與項之間的相關關系叫做關聯規則學習(association rule analyse)。
#如何量化？
我們如何衡量一個組合是不是頻繁出現的呢？頻繁是中文含義就是出現的次數多，那麼頻繁的衡量标準肯定和出現的頻數有關。如何計算某個組合的頻數？例如：
那麼｛豆奶，尿布｝的頻數就是3，因為這個組合出現在第2，3，4條樣本出現過。
但是，我們也知道頻數這個名額是和樣本數量的有關的。假如我們規定頻數大于5的組合就是頻繁的。那這樣子假如某個組合在10條随機資料集中的頻數為1，這個組合是不頻繁的；但是在100條随機資料集中頻數為10，該組合變的頻繁了。這就會導緻頻繁性的判斷不穩定。是以實際上我們使用頻率這個名額。
實際上一個組合A的頻率又叫組合A在這個資料集T上的支援度（support degree）,意思就是組合A在資料集T上出現的機率。
那麼我們如何定義關聯規則可信呢？已知一個人已經買了豆奶，那麼他有多大機率也買尿布嘞？這個就要使用到條件機率了。
這個條件機率的直覺解釋就是：在所有出現豆奶的樣本裡，有多少個還出現了尿布。如果這個條件機率特别大，那麼我們可以認為**“買了 豆奶 一般也會買 尿布 ”**這條規則是可信任的。規則 “買了 豆奶 一般也會買 尿布” 記作：豆奶——>尿布。但是這條關聯規則不具備自反性。也就是說 豆奶——>尿布，并不能推出 尿布——>豆奶，本質上是因為他們的條件機率都不同：
直覺上的了解也是一樣的。比如 人們一般上完廁所就會洗手，規則：上廁所——>洗手 是可信的；但是并不意味着 洗了手就一定是在上廁所，因為也可能是吃了飯再洗手。
同樣的，在關聯分析中，與某條規則相對應的條件機率也有另外一個名稱：置信度。
規則A->B的置信度計算公式為：
有了這兩個量化名額，那我們就可以在一個資料集上尋找頻繁項集和關聯規則啦。
最原始的做法就是，生成所有可能的組合方式，然後我們枚舉計算這些所有的組合方式的支援度（頻率），那些達到支援度名額的就是我們想到找到的頻繁項集啦。這種枚舉法當然可以解決問題，但是我們想也想的到這個複雜度特别高！
比如上面購物的例子中基礎元素共有6個，這6個元素可以一個一個組合，也可以兩個兩個組合，也可以三個三個來•••那麼這6個基本元素組合起來就一共有：
種可能的組合方式。如此，我們需要計算63種組合出現的頻率，每次計算需要周遊整個資料集。emmmmm…這個時間複雜度O(2^N)要GG。那麼一個自然的思路就是剪枝。
#使用Apriori 原理進行剪枝
Apriori原理特别簡單！有一些公理化機率論基礎都會輕松了解。
設A,B是兩個事件，則
積事件的機率小于等于各個因子的機率。直覺的解釋就是A和B同時發生的機率當然要小于等于他們單獨分别發生的機率。
ok.我們來使用這個性質對上面尋找頻繁項集的過程進行剪枝。
上圖顯示了基礎元素集為｛0，1，2，3｝時，所有可能的組合。這實際顯示了一種生成所有組合的階層化的方法：先一一組合，然後再二二組合，再三三組合•••每一層的組合都可以在上一層的基礎上進行。具體方法為：
設第i層是所有含i個元素的組合，每個組合都有i+1個不同的元素。現在需要生成所有含i+1個元素的組合。
i+1個元素的組合就是每個組合含有i+1個不同的元素；那麼隻要在原來第i層的基礎上進行兩兩合并，生成含且隻含i+1個元素的組合。
為了讓第i層兩個組合CA,CB組合後生成隻含i+1個元素，需要CA,CB有且隻有一個元素不同。否則合并後的組合将不隻i個元素。
是以我們可以讓所有組合按基礎元素升序的方式排列，比較CA,CB前i-1個元素.如果CA和CB的前i-1個元素相同的話，CA和CB就隻有第i個元素不同了（如01和02），這樣合并後才能隻含有i+1個元素。如果CA和CB的前i-1個元素不等，那至少CA與CB會有兩個元素不一緻（如01 和23 組合生成0123 就包含4個基本元素）。 （此方法存在問題，感謝@weixin_39799208指正）
正确的做法應該是對CA和CB内的各元素做交集，看交集内的元素個數是否為i-1。
現在 我們假設{23}組合的支援度為P({23})，它小于容許的最小支援度p’,即P(23) < p’,此時｛23｝這種組合就是不頻繁的了。
由圖可知，｛23｝參與了組合｛023｝和｛123｝的生成，那麼：
#Apriori的實作代碼：
__author__ = 'jmh081701'
import numpy as np
def loadDataset():
return [{1,3,4},{2,3,5},{1,2,3,5},{2,5}]
def createC1(dataset,minsupport=0.6):
C1=[]
for t in dataset:
for s in t:
if({s} in C1):
continue
else:
C1.append({s})
C1.sort()
return map(frozenset,C1)
def scan(dataset,minisupport=0.6,Ck=None):
rst=[]
cutset=[]
supportData={}
for c in Ck:
for t in dataset:
if c.issubset(t):
if c in supportData:
supportData[c]+=1
else:
supportData[c]=1
lenD=float(len(dataset))
for key in supportData:
supportData[key]=supportData[key]/lenD
if(supportData[key]>=minisupport):
rst.append(key)
else:
cutset.append(key)
return rst,supportData,cutset
def genCj(Ck,k,Cutset={}):
#2019年04.10 此實作有問題，應該是取l1,l2交集然後判斷交集元素個數是否符合要求。
lenCk=len(Ck)
Cj=set()
for i in range(lenCk):
for j in range(i+1,lenCk):
l1=list(Ck[i])[:k-1]
l2=list(Ck[j])[:k-1]
l1.sort()
l2.sort()
if(l1==l2):
t=Ck[i]|Ck[j]
f=0
for each in Cutset:
if set(each).issubset(t):
f=1
break
if(f==0):
Cj.add(t)
return Cj
def apriori(dataset,minisupport=0.6):
#from number i layer frequent item set generate i+1 th frequent item set.
C1=createC1(dataset)
Ck=C1
k=1
supportData={}
CutSet=[]
rstC=[]
while Ck!=set():
rst,support,cutset=scan(dataset,minisupport,Ck)
rstC.append([rst])
supportData.update(support)
CutSet.append(cutset)
Cj=genCj(rst,k,CutSet)
k+=1
Ck=Cj
return rstC,supportData
data=loadDataset()
rstC,supportData=apriori(data)
print(rstC)
print(supportData)
運作結果：
[[[frozenset({3}), frozenset({2}), frozenset({5})]], [[frozenset({2, 5})]]]
{frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({2, 3}): 0.5, frozenset({3, 5}): 0.5, frozenset({2, 5}): 0.75}
#代碼解釋
def loadDataset():
return [{1,3,4},{2,3,5},{1,2,3,5},{2,5}]
該函數用于生成資料集。輸入資料集是一個list of set.清單裡面的每一個元素都是集合。在關聯分析中，需要将原始資料轉化為這種資料形式。尤其是每個樣本的特征向量其實是一個無序的集合。
def createC1(dataset,minsupport=0.6):
C1=[]
for t in dataset:
for s in t:
if({s} in C1):
continue
else:
C1.append({s})
C1.sort()
return map(frozenset,C1)
該函數周遊整個資料集，将各個基礎元素抽離出來。注意最後的map{frozenset,C1}
map(func, seq1[, seq2,…])
第一個參數接受一個函數名，後面的參數接受一個或多個可疊代的序列，傳回的是一個集合。 Python函數程式設計中的map()函數是将func作用于seq中的每一個元素，并将所有的調用的結果作為一個list傳回。
map(frozenset,C1)其實就是将C1的每一個元素都轉化為frozenset類型。這麼做是為了讓元素組合能夠做字典的key.
def scan(dataset,minisupport=0.6,Ck=None):
rst=[]
cutset=[]
supportData={}
for c in Ck:
for t in dataset:
if c.issubset(t):
if c in supportData:
supportData[c]+=1
else:
supportData[c]=1
lenD=float(len(dataset))
for key in supportData:
supportData[key]=supportData[key]/lenD
if(supportData[key]>=minisupport):
rst.append(key)
else:
cutset.append(key)
return rst,supportData,cutset
上述代碼在計算各個組合的頻率。
對于Ck裡面的每一個組合c,周遊整個資料集，看這個c在資料集中出現了多少次。按照定義，c是t的子集說明 c在t出現了。
rst是滿足Ck内所有滿足最小支援度要求的組合；同時supportData傳回了Ck内所有組合的支援度，supportData是一個字典，key是基本元素的組合，而value是這個組合出現的頻率。cutset用于傳回Ck内那些被剪枝的組合。
def genCj(Ck,k,Cutset={}):
lenCk=len(Ck)
Cj=set()
for i in range(lenCk):
for j in range(i+1,lenCk):
l1=list(Ck[i])[:k-1]
l2=list(Ck[j])[:k-1]
l1.sort()
l2.sort()
if(l1==l2):
t=Ck[i]|Ck[j]
f=0
for each in Cutset:
if set(each).issubset(t):
f=1
break
if(f==0):
Cj.add(t)
return Cj
genCj用于輸入隻含k個元素的若幹組合Ck，以及已确定被剪枝的組合清單Cutset,輸出含k+1個元素的所有可能的組合Cj。注意要先把前k-1個元素提取出來，然後排序，比較、如果相等後t不含有cutset的元素 再把合并後的加入。
def apriori(dataset,minisupport=0.6):
#from number i layer frequent item set generate i+1 th frequent item set.
C1=createC1(dataset)
Ck=C1
k=1
supportData={}
CutSet=[]
rstC=[]
while Ck!=set():
rst,support,cutset=scan(dataset,minisupport,Ck)
rstC.append([rst])
supportData.update(support)
CutSet.append(cutset)
Cj=genCj(rst,k,CutSet)
k+=1
Ck=Cj
return rstC,supportData
當第k層一直不空的時候，不斷尋找新的組合。
注意：關聯分析的輸入資料集中，每個樣本的特征向量是一個集合，是無序的、确定的、互斥的。