關聯分析的基本概念
關聯分析（Association Analysis）：在大規模數據集中尋找有趣的關係。
頻繁項集（Frequent Item Sets）：經常出現在一塊的物品的集合，即包含0個或者多個項的集合稱為項集。
支持度（Support）：數據集中包含該項集的記錄所佔的比例，是針對項集來說的。
置信度（Confidence）：出現某些物品時，另外一些物品必定出現的概率，針對規則而言。
關聯規則（Association Rules）：暗示兩個物品之間可能存在很強的關係。形如A->B的表達式，規則A->B的度量包括支持度和置信度
項集支持度：一個項集出現的次數與數據集所有事物數的百分比稱為項集的支持度
eg:support(A⇒B)=support_count(A∪B)/N
支持度反映了A和B同時出現的概率，關聯規則的支持度等於頻繁集的支持度。
項集置信度：包含A的數據集中包含B的百分比
eg:confidence(A⇒B)=supportcount(A∪B)/supportcount(A)
置信度反映瞭如果交易中包含A，則交易包含B的概率。也可以稱為在A發生的條件下，發生B的概率，成為條件概率。
只有支持度和置信度(可信度)較高的關聯規則才是用戶感興趣的。
關聯分析步驟
1、發現頻繁項集，即計算所有可能組合數的支持度，找出不少於人為設定的最小支持度的集合。
2、發現關聯規則，即計算不小於人為設定的最小支持度的集合的置信度，找到不小於認為設定的最小置信度規則。
關聯分析的兩種關係：簡單關聯關係和序列關聯關係
簡單關聯關係：
簡單關聯關係可以從經典的購物中進行分析，購買麵包的顧客80%都會購買牛奶，由於麵包和牛奶是早餐搭配的必需品，二者搭配構成了早餐的組成部分，這就是一種簡單的關聯關係。
序列關聯關係：
當購買一款新手機後，就會考慮去購買手機膜等手機配件，這就是一種序列關係，不會先買手機膜再買手機的，先後關係是非常明顯的，這種關係是一種順序性的關係，也就是一種序列關聯關係。
關聯規則：規則就是一種衡量事物的標準，也就是一個算法。
簡單關聯規則算法
算法思想基礎
如果某個項集是頻繁的，那麼它的所有子集也是頻繁的。更常用的是它的逆否命題，即如果一個項集是非頻繁的，那麼它的所有超集也是非頻繁的。
簡單關聯規則是無指導的學習方法，著重探索內部結構。簡單關聯規則也是使用最多的技術，主要算法包括：Apriori、GRI、Carma，其中Apriori和Carma主要是如何提高關聯規則的分析效率，而GRI注重如何將單一概念層次的關聯推廣到更多概念層次的關聯，進而揭示事物內在結構。
簡單關聯規則的數據存儲形式：一種是交易數據格式，一種是表格數據格式。
序列關聯規則算法
序列關聯規則的核心就是找到事物發展的前後關聯性，研究序列關聯可以來推測事物未來的發展情況，並根據預測的發展情況進行事物的分配和安排。
如何設定合理的支持度和置信度？
對於某條規則：（A=a）−>（B=b）
（support=30%,confident=60%）；其中support=30%表示在所有的數據記錄中，同時出現A=a和B=b的概率為30%；confident=60%表示在所有的數據記錄中，在出現A=a的情況下出現B=b的概率為60%，也就是條件概率。支持度揭示了A=a和B=b同時出現的概率，置信度揭示了當A=a出現時，B=b是否會一定出現的概率。
（1）如果支持度和置信度閉值設置的過高，雖然可以減少挖掘時間，但是容易造成一些隱含在數據中非頻繁特徵項被忽略掉，難以發現足夠有用的規則；
（2）如果支持度和置信度閉值設置的過低，又有可能產生過多的規則，甚至產生大量冗餘和無效的規則，同時由於算法存在的固有問題，會導致高負荷的計算量，大大增加挖掘時間。
關聯分析的應用
(1)：購物籃分析，通過查看那些商品經常在一起出售，可以幫助商店瞭解用戶的購物行為，這種從數據的海洋中抽取只是可以用於商品定價、市場促銷、存貨管理等環節
(2)：在Twitter源中發現一些公共詞。對於給定的搜索詞，發現推文中頻繁出現的單詞集合
(3)：從新聞網站點擊流中挖掘新聞流行趨勢，挖掘哪些新聞廣泛被用戶瀏覽到
(4)：搜索引擎推薦，在用戶輸入查詢時推薦同時相關的查詢詞項
(5)：發現毒蘑菇的相似特徵。這裡只對包含某個特徵元素（有毒素）的項集感興趣，從中尋找毒蘑菇中的一些公共特徵，利用這些特徵來避免遲到哪些有毒的蘑菇
(6)：圖書館信息的書籍推薦，對於學生的借書信息，不同專業學生的借書情況，來挖掘不同學生的借書情況，進行數目的推薦。
(7)：校園網新聞通知信息的推薦，在對校園網新聞通知信息進行挖掘的過程中，分析不同部門，不同學院的新聞信息的不同，在進行新聞信息瀏覽的過程中進行新聞的推薦。
Apriori算法
假設我們有一家經營著4種商品（商品0，商品1，商品2和商品3）的雜貨店，2圖顯示了所有商品之間所有的可能組合：
對於單個項集的支持度，我們可以通過遍歷每條記錄並檢查該記錄是否包含該項集來計算。對於包含N中物品的數據集共有2
N
−1
種項集組合，重複上述計算過程是不現實的。
研究人員發現一種所謂的Apriori原理，可以幫助我們減少計算量。Apriori原理是說如果某個項集是頻繁的，那麼它的所有子集也是頻繁的。更常用的是它的逆否命題，即如果一個項集是非頻繁的，那麼它的所有超集也是非頻繁的。
注意：這裡的子集不是傳統數學中的子集，而是子項的項集。例如一個頻繁項集包含3個項，則這三個項的子集組成的項集一定是頻繁項集。
在圖3中，已知陰影項集{2,3}是非頻繁的。利用這個知識，我們就知道項集{0,2,3}，{1,2,3}以及{0,1,2,3}也是非頻繁的。也就是說，一旦計算出了{2,3}的支持度，知道它是非頻繁的後，就可以緊接著排除{0,2,3}、{1,2,3}和{0,1,2,3}。
Apriori算法是發現頻繁項集的一種方法。
Apriori算法的兩個輸入參數分別是最小支持度和數據集。該算法首先會生成所有單個元素的項集列表。接著掃描數據集來查看哪些項集滿足最小支持度要求，那些不滿足最小支持度的集合會被去掉。然後，對剩下來的集合進行組合以生成包含兩個元素的項集。接下來，再重新掃描交易記錄，去掉不滿足最小支持度的項集。該過程重複進行直到所有項集都被去掉。
該算法需要不斷尋找候選集，然後剪枝即去掉非頻繁子集的候選集，時間複雜度由暴力枚舉所有子集的指數級別O（n2）將為多項式級別，多項式具體系數是底層實現情況而定的。
Ariori算法有兩個主要步驟：
1、連接：（將項集進行兩兩連接形成新的候選集）利用已經找到的k個項的頻繁項集Lk，通過兩兩連接得出候選集Ck+1，注意進行連接的Lk[i]，Lk[j]，必須有k-1個屬性值相同，然後另外兩個不同的分別分佈Lk[i]，Lk[j]，這樣的求出的Ck+1為Lk+1的候選集。
2、剪枝：（去掉非頻繁項集）候選集 Ck+1中的並不都是頻繁項集，必須剪枝去掉，越早越好以防止所處理的數據無效項越來越多。只有當子集都是頻繁集的候選集才是頻繁集，這是剪枝的依據。
算法實現
<code>from numpy import *def loadDataSet():return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]# 獲取候選1項集，dataSet為事務集。返回一個list，每個元素都是set集合def createC1(dataSet): C1 = [] # 元素個數為1的項集（非頻繁項集，因為還沒有同最小支持度比較）for transaction in dataSet: for item in transaction: if not [item] in C1: C1.append([item]) C1.sort() # 這裡排序是為了，生成新的候選集時可以直接認為兩個n項候選集前面的部分相同# 因為除了候選1項集外其他的候選n項集都是以二維列表的形式存在，所以要將候選1項集的每一個元素都轉化為一個單獨的集合。return list(map(frozenset, C1)) #map(frozenset, C1)的語義是將C1由Python列表轉換為不變集合（frozenset，Python中的數據結構）# 找出候選集中的頻繁項集# dataSet為全部數據集，Ck為大小為k（包含k個元素）的候選項集，minSupport為設定的最小支持度def scanD(dataSet, Ck, minSupport): ssCnt = {} # 記錄每個候選項的個數for tid in dataSet: for can in Ck: if can.issubset(tid): ssCnt[can] = ssCnt.get(can, 0) + 1 # 計算每一個項集出現的頻率 numItems = float(len(dataSet)) retList = [] supportData = {} for key in ssCnt: support = ssCnt[key] / numItems if support >= minSupport: retList.insert(0, key) #將頻繁項集插入返回列表的首部 supportData[key] = support return retList, supportData #retList為在Ck中找出的頻繁項集（支持度大於minSupport的），supportData記錄各頻繁項集的支持度# 通過頻繁項集列表Lk和項集個數k生成候選項集C(k+1)。def aprioriGen(Lk, k): retList = [] lenLk = len(Lk) for i in range(lenLk): for j in range(i + 1, lenLk): # 前k-1項相同時，才將兩個集合合併，合併後才能生成k+1項 L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2] # 取出兩個集合的前k-1個元素 L1.sort(); L2.sort() if L1 == L2: retList.append(Lk[i] | Lk[j]) return retList# 獲取事務集中的所有的頻繁項集# Ck表示項數為k的候選項集，最初的C1通過createC1()函數生成。Lk表示項數為k的頻繁項集，supK為其支持度，Lk和supK由scanD()函數通過Ck計算而來。def apriori(dataSet, minSupport=0.5): C1 = createC1(dataSet) # 從事務集中獲取候選1項集 D = list(map(set, dataSet)) # 將事務集的每個元素轉化為集合 L1, supportData = scanD(D, C1, minSupport) # 獲取頻繁1項集和對應的支持度 L = [L1] # L用來存儲所有的頻繁項集 k = 2while (len(L[k-2]) > 0): # 一直迭代到項集數目過大而在事務集中不存在這種n項集 Ck = aprioriGen(L[k-2], k) # 根據頻繁項集生成新的候選項集。Ck表示項數為k的候選項集 Lk, supK = scanD(D, Ck, minSupport) # Lk表示項數為k的頻繁項集，supK為其支持度 L.append(Lk);supportData.update(supK) # 添加新頻繁項集和他們的支持度 k += 1return L, supportDataif __name__=='__main__': dataSet = loadDataSet() # 獲取事務集。每個元素都是列表# C1 = createC1(dataSet) # 獲取候選1項集。每個元素都是集合# D = list(map(set, dataSet)) # 轉化事務集的形式，每個元素都轉化為集合。# L1, suppDat = scanD(D, C1, 0.5)# print(L1,suppDat) L, suppData = apriori(dataSet,minSupport=0.7) print(L,suppData)/<code> FP-growth算法來高效發現頻繁項集
FP樹：用於編碼數據集的有效方式
FP-growth算法將數據存儲在一種稱為FP樹的緊湊數據結構中。FP代表頻繁模式（Frequent Pattern）。一棵FP樹看上去與計算機科學中的其他樹結構類似，但是它通過鏈接（link）來連接相似元素，被連起來的元素項可以看成一個鏈表。
與搜索樹不同的是，一個元素項可以在一棵FP樹種出現多次。FP樹會存儲項集的出現頻率，而每個項集會以路徑的方式存儲在數中。 樹節點上給出集合中的單個元素及其在序列中的出現次數，路徑會給出該序列的出現次數。
相似項之間的鏈接稱為節點鏈接（node link），用於快速發現相似項的位置。
下圖給出了FP樹的一個例子。
事務集
事務ID 事務中的元素項
001 r, z, h, j, p
002 z, y, x, w, v, u, t, s
003 z
004 r, x, n, o, s
005 y, r, x, z, q, t, p
006 y, z, x, e, q, s, t, m
生成的FP樹為
對FP樹的解讀：
圖中，元素項z出現了5次，集合{r, z}出現了1次。於是可以得出結論：z一定是自己本身或者和其他符號一起出現了4次。集合{t, s, y, x, z}出現了2次，集合{t, r, y, x, z}出現了1次，z本身單獨出現1次。就像這樣，FP樹的解讀方式是讀取某個節點開始到根節點的路徑。路徑上的元素構成一個頻繁項集，開始節點的值表示這個項集的支持度。根據圖5，我們可以快速讀出項集{z}的支持度為5、項集{t, s, y, x, z}的支持度為2、項集{r, y, x, z}的支持度為1、項集{r, s, x}的支持度為1。FP樹中會多次出現相同的元素項，也是因為同一個元素項會存在於多條路徑，構成多個頻繁項集。但是頻繁項集的共享路徑是會合並的，如圖中的{t, s, y, x, z}和{t, r, y, x, z}
和之前一樣，我們取一個最小閾值，出現次數低於最小閾值的元素項將被直接忽略。圖中將最小支持度設為3，所以q和p沒有在FP中出現。
FP-growth算法的工作流程如下。首先構建FP樹，然後利用它來挖掘頻繁項集。為構建FP樹，需要對原始數據集掃描兩遍。第一遍對所有元素項的出現次數進行計數。數據庫的第一遍掃描用來統計出現的頻率，而第二遍掃描中只考慮那些頻繁元素。
FP-growth算法發現頻繁項集的基本過程如下：
構建FP樹
從FP樹中挖掘頻繁項集
頭指針表
FP-growth算法還需要一個稱為頭指針表的數據結構，其實很簡單，就是用來記錄各個元素項的總出現次數的數組，再附帶一個指針指向FP樹中該元素項的第一個節點。這樣每個元素項都構成一條單鏈表。圖示說明：
這裡使用Python字典作為數據結構，來保存頭指針表。以元素項名稱為鍵，保存出現的總次數和一個指向第一個相似元素項的指針。
第一次遍歷數據集會獲得每個元素項的出現頻率，去掉不滿足最小支持度的元素項，生成這個頭指針表。
元素項排序
上文提到過，FP樹會合並相同的頻繁項集（或相同的部分）。因此為判斷兩個項集的相似程度需要對項集中的元素進行排序（不過原因也不僅如此，還有其它好處）。排序基於元素項的絕對出現頻率（總的出現次數）來進行。在第二次遍歷數據集時，會讀入每個項集（讀取），去掉不滿足最小支持度的元素項（過濾），然後對元素進行排序（重排序）。
構建FP樹
在對事務記錄過濾和排序之後，就可以構建FP樹了。從空集開始，將過濾和重排序後的頻繁項集一次添加到樹中。如果樹中已存在現有元素，則增加現有元素的值；如果現有元素不存在，則向樹添加一個分支。對前兩條事務進行添加的過程：
實現流程
輸入：數據集、最小值尺度
輸出：FP樹、頭指針表
\\1. 遍歷數據集，統計各元素項出現次數，創建頭指針表
\\2. 移除頭指針表中不滿足最小值尺度的元素項
\\3. 第二次遍歷數據集，創建FP樹。對每個數據集中的項集：
3.1 初始化空FP樹
3.2 對每個項集進行過濾和重排序
3.3 使用這個項集更新FP樹，從FP樹的根節點開始：
3.3.1 如果當前項集的第一個元素項存在於FP樹當前節點的子節點中，則更新這個子節點的計數值
3.3.2 否則，創建新的子節點，更新頭指針表
3.3.3 對當前項集的其餘元素項和當前元素項的對應子節點遞歸3.3的過程
從一棵FP樹種挖掘頻繁項集
從FP樹中抽取頻繁項集的三個基本步驟如下：
從FP樹中獲得條件模式基；
利用條件模式基，構建一個條件FP樹；
迭代重複步驟1步驟2，直到樹包含一個元素項為止。
其中“條件模式基”是以所查找元素項為結尾的路徑集合。每一條路徑其實都是一條前綴路徑（prefix path）。簡而言之，一條前綴路徑是介於所查找元素項與樹根節點之間的所有內容。
例如
則每一個頻繁元素項的條件模式基為：
頻繁項 前綴路徑
z {}: 5
r {x, s}: 1, {z, x, y}: 1, {z}: 1
x {z}: 3, {}: 1
y {z, x}: 3
s {z, x, y}: 2, {x}: 1
t {z, x, y, s}: 2, {z, x, y, r}: 1
發現規律了嗎，z存在於路徑{z}中，因此前綴路徑為空，另添加一項該路徑中z節點的計數值5構成其條件模式基；r存在於路徑{r, z}、{r, y, x, z}、{r, s, x}中，分別獲得前綴路徑{z}、{y, x, z}、{s, x}，另添加對應路徑中r節點的計數值（均為1）構成r的條件模式基；以此類推。
創建條件FP樹
對於每一個頻繁項，都要創建一棵條件FP樹。可以使用剛才發現的條件模式基作為輸入數據，並通過相同的建樹代碼來構建這些樹。例如，對於r，即以“{x, s}: 1, {z, x, y}: 1, {z}: 1”為輸入，調用函數createTree()獲得r的條件FP樹；對於t，輸入是對應的條件模式基“{z, x, y, s}: 2, {z, x, y, r}: 1”。
遞歸查找頻繁項集
有了FP樹和條件FP樹，我們就可以在前兩步的基礎上遞歸得查找頻繁項集。
遞歸的過程是這樣的：
輸入：我們有當前數據集的FP樹（inTree，headerTable）
\\1. 初始化一個空列表preFix表示前綴
\\2. 初始化一個空列表freqItemList接收生成的頻繁項集（作為輸出）
\\3. 對headerTable中的每個元素basePat（按計數值由小到大），遞歸：
3.1 記basePat + preFix為當前頻繁項集newFreqSet
3.2 將newFreqSet添加到freqItemList中
3.3 計算t的條件FP樹（myCondTree、myHead）
3.4 當條件FP樹不為空時，繼續下一步；否則退出遞歸
3.4 以myCondTree、myHead為新的輸入，以newFreqSet為新的preFix，外加freqItemList，遞歸這個過程
實現代碼
<code># FP樹類class treeNode:def __init__(self, nameValue, numOccur, parentNode):self.name = nameValue #節點元素名稱，在構造時初始化為給定值 self.count = numOccur # 出現次數，在構造時初始化為給定值 self.nodeLink = None # 指向下一個相似節點的指針，默認為None self.parent = parentNode # 指向父節點的指針，在構造時初始化為給定值 self.children = {} # 指向子節點的字典，以子節點的元素名稱為鍵，指向子節點的指針為值，初始化為空字典 # 增加節點的出現次數值def inc(self, numOccur): self.count += numOccur # 輸出節點和子節點的FP樹結構def disp(self, ind=1): print(' ' * ind, self.name, ' ', self.count) for child in self.children.values(): child.disp(ind + 1)# =======================================================構建FP樹==================================================# 對不是第一個出現的節點，更新頭指針塊。就是添加到相似元素鏈表的尾部def updateHeader(nodeToTest, targetNode):while (nodeToTest.nodeLink != None): nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode# 根據一個排序過濾後的頻繁項更新FP樹def updateTree(items, inTree, headerTable, count):if items[0] in inTree.children: # 有該元素項時計數值+1 inTree.children[items[0]].inc(count) else: # 沒有這個元素項時創建一個新節點 inTree.children[items[0]] = treeNode(items[0], count, inTree) # 更新頭指針表或前一個相似元素項節點的指針指向新節點if headerTable[items[0]][1] == None: # 如果是第一次出現，則在頭指針表中增加對該節點的指向 headerTable[items[0]][1] = inTree.children[items[0]] else: updateHeader(headerTable[items[0]][1], inTree.children[items[0]]) if len(items) > 1: # 對剩下的元素項迭代調用updateTree函數 updateTree(items[1::], inTree.children[items[0]], headerTable, count)# 主程序。創建FP樹。dataSet為事務集，為一個字典，鍵為每個事物，值為該事物出現的次數。minSup為最低支持度def createTree(dataSet, minSup=1):# 第一次遍歷數據集，創建頭指針表 headerTable = {} for trans in dataSet: for item in trans: headerTable[item] = headerTable.get(item, 0) + dataSet[trans] # 移除不滿足最小支持度的元素項 keys = list(headerTable.keys()) # 因為字典要求在迭代中不能修改，所以轉化為列表for k in keys: if headerTable[k] del(headerTable[k]) # 空元素集，返回空 freqItemSet = set(headerTable.keys()) if len(freqItemSet) == 0: return None, None# 增加一個數據項，用於存放指向相似元素項指針for k in headerTable: headerTable[k] = [headerTable[k], None] # 每個鍵的值，第一個為個數，第二個為下一個節點的位置 retTree = treeNode('Null Set', 1, None) # 根節點# 第二次遍歷數據集，創建FP樹for tranSet, count in dataSet.items(): localD = {} # 記錄頻繁1項集的全局頻率，用於排序for item in tranSet: if item in freqItemSet: # 只考慮頻繁項 localD[item] = headerTable[item][0] # 注意這個[0]，因為之前加過一個數據項if len(localD) > 0: orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 排序 updateTree(orderedItems, retTree, headerTable, count) # 更新FP樹return retTree, headerTable# =================================================查找元素條件模式基===============================================# 直接修改prefixPath的值，將當前節點leafNode添加到prefixPath的末尾，然後遞歸添加其父節點。# prefixPath就是一條從treeNode（包括treeNode）到根節點（不包括根節點）的路徑def ascendTree(leafNode, prefixPath):if leafNode.parent != None: prefixPath.append(leafNode.name) ascendTree(leafNode.parent, prefixPath)# 為給定元素項生成一個條件模式基（前綴路徑）。basePet表示輸入的頻繁項，treeNode為當前FP樹中對應的第一個節點# 函數返回值即為條件模式基condPats，用一個字典表示，鍵為前綴路徑，值為計數值。def findPrefixPath(basePat, treeNode): condPats = {} # 存儲條件模式基while treeNode != None: prefixPath = [] # 用於存儲前綴路徑 ascendTree(treeNode, prefixPath) # 生成前綴路徑if len(prefixPath) > 1: condPats[frozenset(prefixPath[1:])] = treeNode.count # 出現的數量就是當前葉子節點的數量 treeNode = treeNode.nodeLink # 遍歷下一個相同元素return condPats# =================================================遞歸查找頻繁項集===============================================# 根據事務集獲取FP樹和頻繁項。# 遍歷頻繁項，生成每個頻繁項的條件FP樹和條件FP樹的頻繁項# 這樣每個頻繁項與他條件FP樹的頻繁項都構成了頻繁項集# inTree和headerTable是由createTree()函數生成的事務集的FP樹。# minSup表示最小支持度。# preFix請傳入一個空集合（set([])），將在函數中用於保存當前前綴。# freqItemList請傳入一個空列表（[]），將用來儲存生成的頻繁項集。def mineTree(inTree, headerTable, minSup, preFix, freqItemList):# 對頻繁項按出現的數量進行排序進行排序 sorted_headerTable = sorted(headerTable.items(), key=lambda p: p[1][0]) #返回重新排序的列表。每個元素是一個元組，[（key,[num,treeNode],()） bigL = [v[0] for v in sorted_headerTable] # 獲取頻繁項for basePat in bigL: newFreqSet = preFix.copy() # 新的頻繁項集 newFreqSet.add(basePat) # 當前前綴添加一個新元素 freqItemList.append(newFreqSet) # 所有的頻繁項集列表 condPattBases = findPrefixPath(basePat, headerTable[basePat][1]) # 獲取條件模式基。就是basePat元素的所有前綴路徑。它像一個新的事務集 myCondTree, myHead = createTree(condPattBases, minSup) # 創建條件FP樹 if myHead != None: # 用於測試 print('conditional tree for:', newFreqSet) myCondTree.disp() mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) # 遞歸直到不再有元素# 生成數據集def loadSimpDat(): simpDat = [['r', 'z', 'h', 'j', 'p'], ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'], ['z'], ['r', 'x', 'n', 'o', 's'], ['y', 'r', 'x', 'z', 'q', 't', 'p'], ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']] return simpDat# 將數據集轉化為目標格式def createInitSet(dataSet): retDict = {} for trans in dataSet: retDict[frozenset(trans)] = 1return retDictif __name__=='__main__': minSup =3 simpDat = loadSimpDat() # 加載數據集 initSet = createInitSet(simpDat) # 轉化為符合格式的事務集 myFPtree, myHeaderTab = createTree(initSet, minSup) # 形成FP樹# myFPtree.disp() # 打印樹 freqItems = [] # 用於存儲頻繁項集 mineTree(myFPtree, myHeaderTab, minSup, set([]), freqItems) # 獲取頻繁項集 print(freqItems) # 打印頻繁項集/<code> FP-growth算法總結
FP-growth算法是一種用於發現數據集中頻繁模式的有效方法。FP-growth算法利用Apriori原則，執行更快。Apriori算法產生候選項集，然後掃描數據集來檢查它們是否頻繁。由於只對數據集掃描兩次，因此FP-growth算法執行更快。在FP-growth算法中，數據集存儲在一個稱為FP樹的結構中。FP樹構建完成後，可以通過查找元素項的條件基及構建條件FP樹來發現頻繁項集。該過程不斷以更多元素作為條件重複進行，直到FP樹只包含一個元素為止。
優缺點：
優點：一般要快於Apriori。
缺點：實現比較困難，在某些數據集上性能會下降。
適用數據類型：離散型數據。
關聯規則不一定都是有趣
例如，一個穀類早餐的零售商對 5000 名 學生的調查的案例。 用來研究是否在學生打完籃球后向學生推薦早餐。
數據表明：
60%的學生早上會先打籃球，
75%的學生吃這類早餐（包含打籃球后吃早餐的和不打籃球直接吃早餐的）
40% 的學生既打籃球又吃這類早餐。
假設支持度閾值 s=0.4，置信度閾值 c=60%。基於上面數據和假設我們可挖掘出強關聯規則“(打籃球)→(吃早餐)”， 因為其(打籃球) 和(吃早餐)的支持度都大於支持度閾值，都是頻繁項，而規則的置信度 c=40%
60%
=66.6%
也大於置信度閾值。
然而，以上的關聯規則很容易產生誤解，因為吃早餐的比例為 75%，大於 66%。
也就是說，本來不打籃球先選擇吃這種早餐的概率大於75%，但是打完籃球的學生就不想吃這種早餐或者不吃早餐了。因為打球后的學生吃這種早餐的概率降到了66%。
所以打籃球與吃早餐實際上是負關聯的。
所以強關聯不一定是有趣的。
我們應該使用相關性度量（這裡使用提升讀度量）來表徵關聯提升。
也就是P(B/A)/P(B)
來表示在A出現的情況下推薦B是否比沒出現A之前推薦B更好。
公式等價於lift(A,B)=P(A⋃B)
P(A)P(B)
閱讀更多 程序猿南鶴 的文章
