《機(jī)器學(xué)習(xí)與Python實(shí)踐》課件-07-關(guān)聯(lián)規(guī)則

本章目錄01

關(guān)聯(lián)規(guī)則概述02Apriori算法03FP-Growth算法1.關(guān)聯(lián)規(guī)則概述01

關(guān)聯(lián)規(guī)則概述02Apriori算法03FP-Growth算法1.關(guān)聯(lián)規(guī)則概述關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則（AssociationRules）反映一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個(gè)或者多個(gè)事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個(gè)事物就能夠通過(guò)其他事物預(yù)測(cè)到。關(guān)聯(lián)規(guī)則可以看作是一種IF-THEN關(guān)系。假設(shè)商品A被客戶購(gòu)買，那么在相同的交易ID下，商品B也被客戶挑選的機(jī)會(huì)就被發(fā)現(xiàn)了。1.關(guān)聯(lián)規(guī)則概述有沒(méi)有發(fā)生過(guò)這樣的事：你出去買東西，結(jié)果卻買了比你計(jì)劃的多得多的東西？這是一種被稱為沖動(dòng)購(gòu)買的現(xiàn)象，大型零售商利用機(jī)器學(xué)習(xí)和Apriori算法，讓我們傾向于購(gòu)買更多的商品。1.關(guān)聯(lián)規(guī)則概述購(gòu)物車分析是大型超市用來(lái)揭示商品之間關(guān)聯(lián)的關(guān)鍵技術(shù)之一。他們?cè)噲D找出不同物品和產(chǎn)品之間的關(guān)聯(lián)，這些物品和產(chǎn)品可以一起銷售，這有助于正確的產(chǎn)品放置。買面包的人通常也買黃油。零售店的營(yíng)銷團(tuán)隊(duì)?wèi)?yīng)該瞄準(zhǔn)那些購(gòu)買面包和黃油的顧客，向他們提供報(bào)價(jià)，以便他們購(gòu)買第三種商品，比如雞蛋。因此，如果顧客買了面包和黃油，看到雞蛋有折扣或優(yōu)惠，他們就會(huì)傾向于多花些錢買雞蛋。這就是購(gòu)物車分析的意義所在。1.關(guān)聯(lián)規(guī)則概述置信度：

表示你購(gòu)買了A商品后，你還會(huì)有多大的概率購(gòu)買B商品。支持度：

指某個(gè)商品組合出現(xiàn)的次數(shù)與總次數(shù)之間的比例，支持度越高表示該組合出現(xiàn)的幾率越大。提升度：

提升度代表商品A的出現(xiàn)，對(duì)商品B的出現(xiàn)概率提升了多少，即“商品A的出現(xiàn)，對(duì)商品B的出現(xiàn)概率提升的”程度。

1.關(guān)聯(lián)規(guī)則概述

=3/42.Apriori算法01

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

2.Apriori算法算法案例

第一次迭代：假設(shè)支持度閾值為2，創(chuàng)建大小為1的項(xiàng)集并計(jì)算它們的支持度。訂單編號(hào)項(xiàng)目T1134T2235T31235T425T5135項(xiàng)集支持度{1}3{2}3{3}4{4}1{5}4C12.Apriori算法算法案例

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

第2次迭代：接下來(lái)我們將創(chuàng)建大小為2的項(xiàng)集，并計(jì)算它們的支持度。F1中設(shè)置的所有項(xiàng)項(xiàng)集支持度{1,2}1{1,3}3{1,5}2{2,3}2{2,5}3{3,5}3F2項(xiàng)集支持度{1,3}3{1,5}2{2,3}2{2,5}3{3,5}3C2訂單編號(hào)項(xiàng)目T1134T2235T31235T425T51352.Apriori算法算法案例

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

剪枝:我們將C3中的項(xiàng)集劃分為子集，并消除支持值小于2的子集。項(xiàng)集在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訂單編號(hào)項(xiàng)目T1134T2235T31235T425T51352.Apriori算法算法案例

第三次迭代：我們將丟棄{1,2,3}和{1,2,5}，因?yàn)樗鼈兌及瑊1,2}。F3項(xiàng)集支持度{1,3,5}2{2,3,5}2訂單編號(hào)項(xiàng)目T1134T2235T31235T425T51352.Apriori算法算法案例

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

因?yàn)檫@個(gè)項(xiàng)集的支持度小于2，所以我們就到此為止，最后一個(gè)項(xiàng)集是F3。注：到目前為止，我們還沒(méi)有計(jì)算出置信度。使用F3，我們得到以下項(xiàng)集：對(duì)于I={1,3,5}，子集是{1,3}，{1,5}，{3,5}，{1}，{3}，{5}對(duì)于I={2,3,5}，子集是{2,3}，{2,5}，{3,5}，{2}，{3}，{5}項(xiàng)集支持度{1,3,5}2{2,3,5}22.Apriori算法算法案例

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

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

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

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

Apriori在計(jì)算的過(guò)程中有以下幾個(gè)缺點(diǎn)：可能產(chǎn)生大量的候選集。因?yàn)椴捎门帕薪M合的方式，把可能的項(xiàng)集都組合出來(lái)了；每次計(jì)算都需要重新掃描數(shù)據(jù)集，來(lái)計(jì)算每個(gè)項(xiàng)集的支持度。3.FP-Growth算法01

關(guān)聯(lián)規(guī)則概述02Apriori算法03FP-Growth算法3.FP-Growth算法FP-growth（FrequentPatternGrowth）算法思想

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

FP-growth算法是基于Apriori原理的，通過(guò)將數(shù)據(jù)集存儲(chǔ)在FP（FrequentPattern)樹上發(fā)現(xiàn)頻繁項(xiàng)集，但不能發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則。FP-growth算法只需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行兩次掃描，而Apriori算法在求每個(gè)潛在的頻繁項(xiàng)集時(shí)都需要掃描一次數(shù)據(jù)集，所以說(shuō)Apriori算法是高效的。其中算法發(fā)現(xiàn)頻繁項(xiàng)集的過(guò)程是：(1)構(gòu)建FP樹；(2)從FP樹中挖掘頻繁項(xiàng)集。3.FP-Growth算法FP-growth算法思想

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