本章目錄01

關聯規則概述02Apriori算法03FP-Growth算法1.關聯規則概述01

關聯規則概述02Apriori算法03FP-Growth算法1.關聯規則概述關聯規則關聯規則（AssociationRules）反映一個事物與其他事物之間的相互依存性和關聯性。如果兩個或者多個事物之間存在一定的關聯關系，那么，其中一個事物就能夠通過其他事物預測到。關聯規則可以看作是一種IF-THEN關系。假設商品A被客戶購買，那么在相同的交易ID下，商品B也被客戶挑選的機會就被發現了。1.關聯規則概述有沒有發生過這樣的事：你出去買東西，結果卻買了比你計劃的多得多的東西？這是一種被稱為沖動購買的現象，大型零售商利用機器學習和Apriori算法，讓我們傾向于購買更多的商品。1.關聯規則概述購物車分析是大型超市用來揭示商品之間關聯的關鍵技術之一。他們試圖找出不同物品和產品之間的關聯，這些物品和產品可以一起銷售，這有助于正確的產品放置。買面包的人通常也買黃油。零售店的營銷團隊應該瞄準那些購買面包和黃油的顧客，向他們提供報價，以便他們購買第三種商品，比如雞蛋。因此，如果顧客買了面包和黃油，看到雞蛋有折扣或優惠，他們就會傾向于多花些錢買雞蛋。這就是購物車分析的意義所在。1.關聯規則概述置信度：

表示你購買了A商品后，你還會有多大的概率購買B商品。支持度：

指某個商品組合出現的次數與總次數之間的比例，支持度越高表示該組合出現的幾率越大。提升度：

提升度代表商品A的出現，對商品B的出現概率提升了多少，即“商品A的出現，對商品B的出現概率提升的”程度。

1.關聯規則概述

=3/42.Apriori算法01

關聯規則概述02Apriori算法03FP-Growth算法2.Apriori算法Apriori算法利用頻繁項集生成關聯規則。它基于頻繁項集的子集也必須是頻繁項集的概念。頻繁項集是支持值大于閾值（support）的項集。Apriori算法就是基于一個先驗：如果某個項集是頻繁的，那么它的所有子集也是頻繁的。2.Apriori算法

2.Apriori算法算法案例

第一次迭代：假設支持度閾值為2，創建大小為1的項集并計算它們的支持度。訂單編號項目T1134T2235T31235T425T5135項集支持度{1}3{2}3{3}4{4}1{5}4C12.Apriori算法算法案例

可以看到，第4項的支持度為1，小于最小支持度2。所以我們將在接下來的迭代中丟棄{4}。我們得到最終表F1。項集支持度{1}3{2}3{3}4{4}1{5}4C1項集支持度{1}3{2}3{3}4{5}4F12.Apriori算法算法案例

第2次迭代：接下來我們將創建大小為2的項集，并計算它們的支持度。F1中設置的所有項項集支持度{1,2}1{1,3}3{1,5}2{2,3}2{2,5}3{3,5}3F2項集支持度{1,3}3{1,5}2{2,3}2{2,5}3{3,5}3C2訂單編號項目T1134T2235T31235T425T51352.Apriori算法算法案例

項集支持度{1,2}1{1,3}3{1,5}2{2,3}2{2,5}3{3,5}3F2項集支持度{1,3}3{1,5}2{2,3}2{2,5}3{3,5}3C2再次消除支持度小于2的項集。在這個例子中{1，2}。現在，讓我們了解什么是剪枝，以及它如何使Apriori成為查找頻繁項集的最佳算法之一。訂單編號項目T1134T2235T31235T425T51352.Apriori算法算法案例

剪枝:我們將C3中的項集劃分為子集，并消除支持值小于2的子集。項集在F2里？{1,2,3},{1,2},{1,3},{2,3}否{1,2,5},{1,2},{1,5},{2,5}否{1,3,5},{1,5},{1,3},{3,5}是{2,3,5},{2,3},{2,5},{3,5}是C3訂單編號項目T1134T2235T31235T425T51352.Apriori算法算法案例

第三次迭代：我們將丟棄{1,2,3}和{1,2,5}，因為它們都包含{1,2}。F3項集支持度{1,3,5}2{2,3,5}2訂單編號項目T1134T2235T31235T425T51352.Apriori算法算法案例

第四次迭代：使用F3的集合，我們將創建C4。F3項集支持度{1,3,5}2{2,3,5}2C4項集支持度{1,2,3,5}1訂單編號項目T1134T2235T31235T425T51352.Apriori算法算法案例

因為這個項集的支持度小于2，所以我們就到此為止，最后一個項集是F3。注：到目前為止，我們還沒有計算出置信度。使用F3，我們得到以下項集：對于I={1,3,5}，子集是{1,3}，{1,5}，{3,5}，{1}，{3}，{5}對于I={2,3,5}，子集是{2,3}，{2,5}，{3,5}，{2}，{3}，{5}項集支持度{1,3,5}2{2,3,5}22.Apriori算法算法案例

應用規則：我們將創建規則并將它們應用于項集F3。現在假設最小置信值是60%。對于I的每個子集S，輸出規則S–>（I-S）（表示S推薦I-S）如果：支持度(l)/支持度(S)>=最小配置值2.Apriori算法算法案例

{1,3,5}規則1:{1,3}–>（{1,3,5}–{1,3}）表示1&3–>5置信度=支持度(1,3,5)/支持度(1,3)=2/3=66.66%>60%因此選擇了規則1規則2:{1,5}–>（{1,3,5}–{1,5}）表示1&5–>3置信度=支持度(1,3,5)/支持度(1,5)=2/2=100%>60%因此選擇了規則2項集支持度{1,3,5}2{2,3,5}22.Apriori算法算法案例

規則3:{3,5}–>({1,3,5}–{3,5})表示3&5–>1置信度=支持度(1,3,5)/支持度(3,5)=2/3=66.66%>60%因此選擇規則3規則4:{1}–>({1,3,5}–{1})表示1–>3&5置信度=支持度(1,3,5)/支持度(1)=2/3=66.66%>60%因此選擇規則4這就是在Apriori算法中創建規則的方法。可以為項集{2,3,5}實現相同的步驟。2.Apriori算法算法案例

規則5:{3}–>({1,3,5}–{3})表示3–>1和5置信度=支持度(1,3,5)/支持度(3)=2/4=50%<60%規則5被拒絕規則6:{5}–>({1,3,5}–{5})表示5–>1和3置信度=支持度(1,3,5)/支持度(5)=2/4=50%<60%規則6被拒絕2.Apriori算法Apriori算法缺點

Apriori在計算的過程中有以下幾個缺點：可能產生大量的候選集。因為采用排列組合的方式，把可能的項集都組合出來了；每次計算都需要重新掃描數據集，來計算每個項集的支持度。3.FP-Growth算法01

關聯規則概述02Apriori算法03FP-Growth算法3.FP-Growth算法FP-growth（FrequentPatternGrowth）算法思想

FP-growth(頻繁模式增長)算法是韓家煒老師在2000年提出的關聯分析算法，它采取如下分治策略：將提供頻繁項集的數據庫壓縮到一棵頻繁模式樹（FP-Tree），但仍保留項集關聯信息。該算法是對Apriori方法的改進。生成一個頻繁模式而不需要生成候選模式。FP-growth算法以樹的形式表示數據庫，稱為頻繁模式樹或FP-tree。此樹結構將保持項集之間的關聯。數據庫使用一個頻繁項進行分段。這個片段被稱為“模式片段”。分析了這些碎片模式的項集。因此，該方法相對減少了頻繁項集的搜索。3.FP-Growth算法FP-growth算法思想

FP-growth算法是基于Apriori原理的，通過將數據集存儲在FP（FrequentPattern)樹上發現頻繁項集，但不能發現數據之間的關聯規則。FP-growth算法只需要對數據庫進行兩次掃描，而Apriori算法在求每個潛在的頻繁項集時都需要掃描一次數據集，所以說Apriori算法是高效的。其中算法發現頻繁項集的過程是：(1)構建FP樹；(2)從FP樹中挖掘頻繁項集。3.FP-Growth算法FP-growth算法思想

該算法和Apriori算法最大的不同有兩點：第一，不產生候選集第二，只需要兩次遍歷數據庫，大大提高了效率。3.FP-Growth算法FP-Tree（FrequentPatternTree）FP樹(FP-Tree)是由數據庫的初始項集組成的樹狀結構。FP樹的目的是挖掘最頻繁的模式。FP樹的每個節點表示項集的一個項。根節點表示null，而較低的節點表示項集。在形成樹的同時，保持節點與較低節點（即項集與其他項集）的關聯。3.FP-Growth算法算法步驟FP-growth算法的流程為：首先構造FP樹，然后利用它來挖掘頻繁項集。在構造FP樹時，需要對數據集掃描兩遍，第一遍掃描用來統計頻率，第二遍掃描至考慮頻繁項集。3.FP-Growth算法FP-Tree（FrequentPatternTree）FP樹(FP-Tree)是由數據庫的初始項集組成的樹狀結構。FP樹的目的是挖掘最頻繁的模式。FP樹的每個節點表示項集的一個項。根節點表示null，而較低的節點表示項集。在形成樹的同時，保持節點與較低節點（即項集與其他項集）的關聯。3.FP-Growth算法算法案例設置支持度閾值為50%，置信度閾值為60%交易編號項目T1I1,I2,I3T2I2,I3,I4T3I4,I5T4I1,I2,I4T5I1,I2,I3,I5T6I1,I2,I3,I4項目數量I14I25I34I44I52項目數量I25I14I34I44項集數量排序統計每個項目的數量支持度閾值=50%=>0.5*6=3=>最小子項目數量=33.FP-Growth算法構建FP樹1.考慮到根節點為空(null)。Null①創建樹的根。根由null表示。3.FP-Growth算法構建FP樹1.考慮到根節點為空(null)。2.T1:I1、I2、I3的第一次掃描包含三個項目{I1:1}、{I2:1}、{I3:1}，其中I2作為子級鏈接到根，I1鏈接到I2，I3鏈接到I1。(這里根據項集的數量排序成I2、I1、I3)Nulll2:1l1:1l3:1②再次掃描數據庫并檢查事務。檢查第一個事務并找出其中的項集。計數最大的項集在頂部，計數較低的下一個項集，以此類推。這意味著樹的分支是由事務項集按計數降序構造的。3.FP-Growth算法構建FP樹1.考慮到根節點為空(null)。2.T1:I1、I2、I3的第一次掃描包含三個項目{I1:1}、{I2:1}、{I3:1}，其中I2作為子級鏈接到根，I1鏈接到I2，I3鏈接到I1。3.T2:包含I2、I3和I4，其中I2鏈接到根，I3鏈接到I2，I4鏈接到I3。但是這個分支將共享I2節點，就像它已經在T1中使用一樣。將I2的計數增加1，I3作為子級鏈接到I2，I4作為子級鏈接到I3。計數是{I2:2}，{I3:1}，{I4:1}。Nulll2:2l1:1l3:1l3:1l4:1③3.FP-Growth算法構建FP樹4.T3:I4、I5。類似地，在創建子級時，一個帶有I5的新分支鏈接到I4。5.T4:I1、I2、I4。順序為I2、I1和I4。I2已經鏈接到根節點，因此它將遞增1。同樣地，I1將遞增1，因為它已經鏈接到T1中的I2，因此{I2:3}，{I1:2}，{I4:1}。6.T5:I1、I2、I3、I5。順序為I2、I1、I3和I5。因此{I2:4}，{I1:3}，{I3:2}，{I5:1}。7.T6:I1、I2、I3、I4。順序為I2、I1、I3和I4。因此{I2:5}，{I1:4}，{I3:3}，{I41}。Nulll4:1l2:5l1:4l3:1l5:1l3:3l4:1l5:1l4:13.FP-Growth算法FP-tree的挖掘總結如下：1.不考慮最低節點項I5，因為它沒有達到最小支持計數，因此將其刪除。2.下一個較低的節點是I4。I4出現在兩個分支中，{I2,I1,I3,I4:1}，{I2,I3,I4:1}。因此，將I4作為后綴，前綴路徑將是{I2,I1,I3:1}，{I2,I3:1}。這形成了條件模式基。3.將條件模式基視為事務數據庫，構造FP樹。這將包含{I2:2,I3:2}，不考慮I1，因為它不滿足最小支持計數。Nulll4:1l2:5l1:4l3:1l5:1l3:3l4:1l5:1l4:1“條件模式基”指的是以要挖掘的節點為葉子節點，自底向上求出FP子樹，然后將FP子樹的祖先節點設置為葉子節點之和。3.FP-Growth算法4.此路徑將生成所有頻繁模式的組合：{I2,I4:2}，{I3,I4:2}，{I2,I3,I4:2}5.對于I3，前綴路徑將是：{I2,I1:3}，{I2:1}，這將生成一個2節點FP樹：{I2:4,I1:3}，并生成頻繁模式：{I2,I3:4}，{I1:I3:3}，{I2,I1,I3:3}。6.對于I1，前綴路徑是：{I2:4}這將生成一個單節點FP樹：{I2:4}，并生成頻繁模式：{I2,I1:4}。Nulll4:1l2:5l1:4l3:1l5:1l3:3l4:1l5:1l4:13.FP-Growth算法項目條件模式基條件FP樹生成的頻繁集I4{I2,I1,I3:1},{I2,I3:1}{I2:2,I3:2}{I2,I4:2},{I3,I4:2},{I2,I3,I4:2}I3{I2,I1:3},{I2:1}{I2:4,I1:3}{I2,I3:4},{I1:I3:3},{I2,I1,I3:3}I1{I2:4}{I2:4}{I2,I1:4}下面給出的圖描繪了與條件節點l3相關聯的條件FP樹。項目支持度鏈表l24l13Nulll1:3l2:3,1根據條件FP樹，我們可以進行全排列組合，得到挖掘出來的頻繁模式（這里要將商品本身，如I4也算進去，每個商品挖掘出來的頻繁模式必然包括這商品本身）3.FP-Growth算法FP-Growth算法的優點1.與Apriori算法相比，該算法只需對數據庫進行兩次掃描2.該算法不需要對項目進行配對，因此速度更快。3.數據庫存儲在內存中的壓縮版本中。4.對長、短頻繁模式的挖掘具有高效性和可擴展性。FP-Growth算法的缺點1.FP-Tree比Apriori更麻煩，更難構建。2.可能很耗資源。3.當數據庫較大時，算法可能不適合共享內存1FP-Growth算法演示二-------構造FP樹TidItems1I1,I2.I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3事務數據庫的建立掃描事務數據庫得到頻繁項目集FI1I2I3I4I567622定義minsup=20%,即最小支持度為2,重新排列FI2I1I3I4I5766223.FP-Growth算法TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3重新調整事務數據庫3.FP-Growth算法構建FP樹

TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3rootI2:1I1:2I5:11I4:13I3:142I4:1I1:1I3:1522263I3:1I5:17423.FP-Growth算法rootI2:I1:I5:14I4:1I3:2I4:1I1:2I3:2I3:2I5:17FP樹1FP-Growth算法演示----FP-樹挖掘挖掘從表頭header的最后一個項開始I2I1I3I4I5766223.FP-Growth算法rootI2:I1:I5:14I4:1I3:2I4:1I1:2I3:2I3:2I5:17挖掘I5FP樹在FP樹中可以看到，從根節點到I5:1的路徑有兩條：I2:7-->I1:4-->I5:1I2:7-->I14-->I3:2-->