•1.關聯分析概念
關聯分析是從大量資料中發現項集之間有趣的關聯和相關聯系。
•定義：
1、事務：每一條交易稱為一個事務，如上圖包含5個事務。
2、項：交易的每一個物品稱為一個項，例如豆奶，啤酒等。
3、項集：包含零個或多個項的集合叫做項集，例如{尿布，啤酒}。
4、k−項集：包含k個項的項集叫做k-項集，例如 {豆奶，橙汁}叫做2-項集。
5、支援度計數：一個項集出現在幾個事務當中，它的支援度計數就是幾。例如{尿布, 啤酒}出現在事務002、003和005中，是以 它的支援度計數是3。
6、支援度：支援度計數除于總的事務數。例如上例中總的事務數為5，{尿布, 啤酒}的支援度計數為3，是以它的支援度是 3÷5=60%，說明有60%的人同時買了尿布, 啤酒。
7、頻繁項集：支援度大于或等于某個門檻值的項集就叫做頻繁項集。例如門檻值設為50%時，因為{尿布,啤酒}的支援度是60%，是以 它是頻繁項集。
8、前件和後件：對于規則{尿布}→{啤酒}，{Diaper}叫做前件，{啤酒}叫做後件。
9、置信度：對于規則{尿布}→{啤酒}，{尿布,啤酒}的支援度計數除于{尿布}的支援度計數，為這個規則的置信度。
例如規則{尿布}→{啤酒}的置信度為3÷3=100%。說明買了尿布的人100%也買了 啤酒。
10、強關聯規則：大于或等于最小支援度門檻值和最小置信度門檻值的規則叫做強關聯規則。
•頻繁項集（frequent item sets）是經常出現在一塊兒的物品的集合.
•關聯規則（association rules）暗示兩種物品之間可能存在很強的關系。
•1）支援度
•Surpport(A->B)= P(AB) ，支援度表示事件A 和事件B 同時出現的機率。
•2）置信度
•Confidence(A->B) = P(B/A) = P(AB)/ P(A) ,置信度表示 A 事件出現時，B 事件出現的機率。
•關聯分析的最終目标就是要找出強關聯規則。
•2.Apriori算法原理
•Apriori算法是一種最有影響的挖掘布爾關聯規則頻繁項集的算法。算法的名字基于這樣的事實：算法使用頻繁項集性質的先驗知識，正如我們将看到的。Apriori使用一種稱作逐層搜尋的疊代方法，k-項集用于探索(k+1)-項集。首先，找出頻繁1-項集的集合。該集合記作L1。L1 用于找頻繁2-項集的集合L2，而L2 用于找L3，如此下去，直到不能找到頻繁k-項集。找每個Lk需要一次資料庫掃描。
先驗定理：如果一個項集是頻繁的，則它的所有子集一定也是頻繁的。
如圖所示，假定｛c,d,e｝是頻繁項集。顯而易見，任何包含項集{c,d,e}的事務一定包含它的子集{c,d},{c,e},{d,e},{c},{d}和{e}。這樣，如果{c,d,e}是頻繁的，則它的所有子集一定也是頻繁的。
如果項集{a,b}是非頻繁的，則它的所有超集也一定是非頻繁的。即一旦發現{a,b}是非頻繁的，則整個包含{a,b}超集的子圖可以被立即剪枝。這種基于支援度度量修剪指數搜尋空間的政策稱為基于支援度的剪枝。
這種剪枝政策依賴于支援度度量的一個關鍵性質，即一個項集的支援度絕不會超過它的子集的支援度。這個性質也稱支援度度量的反單調性。
參考部落格有很詳細的例子。
Apriori算法
優點：易編碼實作。’
缺點：在大資料集上可能較慢。
适用資料類型：數值型或者标稱型資料。
3.算法實作：
#coding=gbk
# apriori算法的實作
def load_dataset(): #定義資料集
return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
def create_C1(dataSet): #得到資料集中的每個資料，且進行排序
C1 =[]
for transantion in dataSet:
for item in transantion:
if not [item] in C1:
C1.append([item]) #儲存 I1, I2,。。需要使其不重複
C1.sort()
#use frozen set so we can use it as a key in a dict
#應該輸出 1,2,3,4,5
return list(map(frozenset, C1)) # 将C1中的每個集合映射為frozenset,之後可以作為字典的鍵,
dataSet = load_dataset()
ck = create_C1(dataSet)
print(ck) # 輸出：[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
#測試代碼
# # map(function, sequence)
# c2 = [[2,4],[5,8],[3]]
# c2.sort()
# a = list(map(frozenset, c2))
# print(a) #[frozenset({2, 4}), frozenset({3}), frozenset({8, 5})]
# print(a[0]) # frozenset({2, 4})
# Apriori算法首先建構集合 C1 ,然後掃描資料集判斷這些隻有一個元素的項集是否滿足最小支援度的要求。那些滿足最低要求的項集構成集合 L1 。
# 而 L1 中的元素互相組合構成 C2 , C2 再進一步過濾變為 L2 。
#該函數使 C1 生成L1,ck為全部的資料項
def scanD(D, Ck, minSupport): #參數D 為資料集， Ck為候選項清單， 最小支援度
ssCnt= {} #存儲資料項1,2，。。及其出現的次數
for tid in D: #周遊資料集
for can in Ck: #周遊候選項 1,2,3,4,5,
if can.issubset(tid): #判斷候選項是否含資料集中的各項
if not can in ssCnt:
ssCnt[can] =1
else:
ssCnt[can]+=1 #有則進行加一操作， 1,2,3,4,5 的資料項的個數， 為了計算支援度
numItems = float(len(D)) #計算資料集大小
retList = [] #使L1 初始化， 儲存大于最小支援度的資料項
supportData = {} #使用字典記錄支援度
for key in ssCnt:
support = ssCnt[key]/ numItems #求得支援度
if support >= minSupport: #如果支援度大于使用者給的最小支援度， 對小于的資料項進行去除。
retList.insert(0, key) #儲存到清單中
else:
supportData[key]= support #輸出去除項的支援度
return retList, supportData
#測試：
r, s = scanD(dataSet, ck, 0.5)
print(r) #[frozenset({1}), frozenset({3}), frozenset({2}), frozenset({5})]
print(s) #{frozenset({4}): 0.25}
資料集為：總共有4 分
| 1， 3， 4 |
| 2， 3， 5 |
| 1， 2， 3， 5 |
| 2， 5 |
| C1 | 出現次數 |
| 1） | 2 |
| 2） | 3 |
| 3） | 3 |
| 4） | 1 |
| 5） | 3 |
4）的支援度為 1/4 為 0.25 < 0.5 = minSupport ，是以将其舍去
整個Apriori算法的僞代碼如下:
當集合中項的個數大于0時:
建構一個k個項組成的候選項集的清單
檢查資料以确認每個項集都是頻繁的
保留頻繁項集并建構k+1項組成的候選項集的清單(向上合并)
#Apriori 算法實作
# 輸入參數為 頻繁項集清單 Lk 與 項集元素個數 k , 輸出為 Ck
def aprioriGen(Lk, k):
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i+1, lenLk): #兩兩組合周遊 （1,2,3，5）
L1 = list(Lk[i])[:k-2]
L2 = list(Lk[j])[:k-2] #用清單儲存 k-2 項的項集
L1.sort(); L2.sort()
if L1 == L2:
retList.append(Lk[i] | Lk[j]) #若2個集合的前 k-2 個項相同時， 則将兩個集合合并
return retList
def apriori(dataSet, minSupport =0.5):
C1 = create_C1(dataSet)
D = list(map(set, dataSet))
L1, supportData = scanD(D, C1, minSupport) #生成L1
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) #在1 -項集上增加 2-項集
k +=1
return L, supportData
a= [1,2,3]
a.append([[12],[13],[16]])
print(a) #[1, 2, 3, [[12], [13], [16]]]
#apriori 測試
print('------apriori test -------')
dataSet = load_dataset()
L, supportData = apriori(dataSet)
print(L)#[[frozenset({1}), frozenset({3}), frozenset({2}), frozenset({5})], [frozenset({3, 5}), frozenset({1, 3}),
# frozenset({2, 5}), frozenset({2, 3})], [frozenset({2, 3, 5})], []]
print(L[0]) # [frozenset({1}), frozenset({3}), frozenset({2}), frozenset({5})]
print(L[1]) # [frozenset({3, 5}), frozenset({1, 3}), frozenset({2, 5}), frozenset({2, 3})]
print(L[2]) #[frozenset({2, 3, 5})]
print(L[3]) # [] 頻繁項集為空， 是以的出頻繁項集 為{2,3,5}
#檢視全部項集的支援度
print(supportData) # 部分輸出：{frozenset({5}): 0.75, frozenset({3}): 0.75, frozenset({2, 3, 5}): 0.5,
函數 aprioriGen() 的輸入參數為頻繁項集清單 Lk 與項集元素個數 k ,輸出為 Ck 。舉例來說,該函數以{0}、{1}、{2}作為輸入,會生成{0,1}、{0,2}以及{1,2}。要完成這一點,首先建立一個空清單,然後計算 Lk 中的元素數目。通過循環來比較 Lk 中的每一個元素與其他元素，緊接着,取清單中的兩個集合進行比較。如果這兩個集合的前面 k-2 個元素都相等,那麼就将這兩個集合合成一個大小為 k 的集合 。這裡使用集合的并操作來完成。
apriori函數首先建立 C1 然後讀入資料集将其轉化為 D (集合清單)來完
成。程式中使用 map 函數将 set() 映射到 dataSet 清單中的每一項。scanD() 函數來建立 L1 ,并将 L1 放入清單 L 中。 L 會包含 L1 、 L2 、 L3 …。現在有了 L1 ,後面會繼續找 L2 , L3 …,這可以通過 while 循環來完成,它建立包含更大項集的更大清單,直到下一個大的項集為空。Lk 清單被添加到 L ,同時增加 k 的值,增大項集個數，重複上述過程。最後,當 Lk 為空時,程式傳回 L 并退出。
參考blog
從頻繁項中挖掘關聯規則
#從頻繁項集中挖掘關聯規則
#産生關聯規則
#參數為 L 為頻繁項集， supportData 為全部項集的支援度， mincof 設定最小的置信度為 0.7
def generateRules(L, supportData, minconf = 0.7):
bigRuleList = [] #存儲所有的關聯規則
for i in range(1,len(L)): #隻擷取2 個或更多項集
for freqSet in L[i]:
#周遊L 中每一個頻繁項集，對每個項集建立值包含單個元素的 清單
H1 = [frozenset([item]) for item in freqSet]
#如果頻繁項集數目超過2 個， 就對其進行進一步的合并
if (i>1 ):
rulesFromConseq(freqSet, H1, supportData, bigRuleList, minconf)
else:
#第一層時， 後件數為1
calcConf(freqSet, H1, supportData, bigRuleList, minconf)
return bigRuleList
#生成候選規則集合： 計算規則的置信度，以及找到滿足最小置信度的規則
def calcConf(freqSet, H1, supportData, brl, minconf=0.7):
#針對項集隻有2 個元素時， 計算置信度
prunedH = [] #傳回一個滿足最小置信度的規則清單
for conseq in H1: #周遊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, H1, supportData, brl, minconf = 0.7):
#參數：freqSet是頻繁項， H 是可以出現在規則右邊的清單
m = len(H1[0])
if (len(freqSet) > (m+1)): #如果 頻繁項集元素數目大于單個集合的元素數
Hmp1 = aprioriGen(H1, m+1) # 合并具有相同部分的集合
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minconf) #計算置信度
if (len(Hmp1) > 1):
#使用遞歸進一步組合
rulesFromConseq(freqSet, Hmp1, supportData, brl, minconf)
#測試關聯規則輸出
print()
print('-------generateRules test-------')
rules = generateRules(L, supportData, minconf=0.5)
print(rules)
# -------generateRules test-------
# frozenset({5}) --> frozenset({3}) conf: 0.6666666666666666
# frozenset({3}) --> frozenset({5}) conf: 0.6666666666666666
# frozenset({3}) --> frozenset({1}) conf: 0.6666666666666666
# 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.6666666666666666
# frozenset({2}) --> frozenset({3}) conf: 0.6666666666666666
# frozenset({5}) --> frozenset({2, 3}) conf: 0.6666666666666666
# frozenset({3}) --> frozenset({2, 5}) conf: 0.6666666666666666
# frozenset({2}) --> frozenset({3, 5}) conf: 0.6666666666666666
# [(frozenset({5}), frozenset({3}), 0.6666666666666666),。。。。。。。
4.FP-growth 算法原理：
相比于apriori 算法， FP-growth 算法可高效發現 頻繁項集 。
FP-growth 算法例子可檢視。
python代碼參考
參考：https://blog.csdn.net/zhazhayaonuli/article/details/53322541
https://www.cnblogs.com/qwertWZ/p/4510857.html
項目推薦：
2000多G的計算機各行業電子資源分享（持續更新）
2020年微信小程式全棧項目之喵喵交友【附課件和源碼】
Spring Boot開發小而美的個人部落格【附課件和源碼】
Java微服務實戰296集大型視訊-谷粒商城【附代碼和課件】
Java開發微服務暢購商城實戰【全357集大項目】-附代碼和課件
最全最詳細資料結構與算法視訊-【附課件和源碼】