第十三章關聯(lián)規(guī)則數(shù)據(jù)挖掘原理、算法與應用（Python語言描述）關聯(lián)規(guī)則的定義?關聯(lián)規(guī)則（AssociationRules）是反映一個事物與其他事物之間的相互依存性和關聯(lián)性，如果兩個或多個事物之間存在一定的關聯(lián)關系，那么，其中一個事物就能通過其他事物預測到。關聯(lián)規(guī)則挖掘的經(jīng)典案例是沃爾瑪超市啤酒與尿布的故事，沃爾瑪利用關聯(lián)規(guī)則對顧客放入購物籃中不同商品之間的關系來分析顧客的購物習慣，發(fā)現(xiàn)與尿布一同購買的最多的商品是啤酒。目前關聯(lián)規(guī)則不僅應用于購物推薦，還廣泛應用于新聞推薦、音樂推薦、精準營銷、用戶投資推薦等領域。學習目標（1）熟悉關聯(lián)規(guī)則的基本概念。（2）掌握關聯(lián)規(guī)則的評價方法。（3）掌握關聯(lián)規(guī)則算法Apriori。（4）掌握關聯(lián)規(guī)則算法FPGrowth。目錄基本概念項與項集事務頻繁項集關聯(lián)規(guī)則評價準則關聯(lián)規(guī)則算法案例Apriori：超市購物籃分析案例FP-Growth：超市購物籃分析13.1.1項與項集數(shù)據(jù)庫中不可分割的最小單位信息，稱為項，用符號

i

表示。項的集合{i1,i2,...,ik}稱為項集，若項集中項的個數(shù)k，則項集稱為k-項集。13.1.2事務設I={i1,i2,...,ik}是由數(shù)據(jù)庫中所有項目構(gòu)成的集合，一次處理（交易）所含項目的集合用T表示，T={t1,t2,...,tn}，T就是一次事務，其中ti屬于I。13.1.3事務設U={u1,u2,...,un}為項目的集合，且ui，U≠?，項集U在所有事務中出現(xiàn)的比例也稱支持度support(U)，對于給定的最小支持度min_sup，如果support(U)大于等于min_sup，則稱U為頻繁項集，否則，U為非頻繁項集。13.1.4關聯(lián)規(guī)則關聯(lián)規(guī)則是形如X=>Y的蘊含式，其中X、Y分別是I的真子集，并且X∩Y=?，X和Y分別稱為關聯(lián)規(guī)則的先導（antecedent）和后繼（consequent）。關聯(lián)規(guī)則反映X中的項目出現(xiàn)時，Y中的項目也跟著出現(xiàn)的規(guī)律。目錄基本概念評價準則支持度置信度強關聯(lián)規(guī)則與弱關聯(lián)規(guī)則杠桿率確信度提升度關聯(lián)規(guī)則算法案例Apriori：超市購物籃分析

案例FP-Growth：超市購物籃分析13.2評價準則關聯(lián)規(guī)則的好壞通常用支持度、置信度來評價，通常好的關聯(lián)規(guī)則的支持度以及置信度都比較高。13.2.1支持度對于關聯(lián)規(guī)則R：X→Y，其中X∈I,Y∈I?，并且X∩Y=??。規(guī)則R的支持度（Support）是事務集中同時包含X和Y的事務數(shù)與所有事務數(shù)之比。

其中：|D|為數(shù)據(jù)集所有的事務數(shù)；count(X∪Y)為同時包含X和Y的事務數(shù)。關聯(lián)規(guī)則的最小支持度也就是衡量頻繁集的最小支持度(MinimumSupport)，記為min_sup，用于衡量關聯(lián)規(guī)則需要滿足的最低頻繁度。通常也將count(X∪Y)記為支持度計數(shù)。13.2.2置信度設條件項的集合為X，結(jié)果項的集合為Y。置信度是計算在X中同時也含有Y的概率，即Confidence(X→Y)=P(Y|X)，表示這條規(guī)則有多大程度上可信。關聯(lián)規(guī)則的最小置信度（MinimumConfidence），表示關聯(lián)規(guī)則需要滿足的最低可靠性。13.2.3強關聯(lián)規(guī)則與弱關聯(lián)規(guī)則如果規(guī)則R:X→Y滿足support(X→Y)>sup_min且confidence(X→Y)大于conf_min，稱關聯(lián)規(guī)則X→Y為強關聯(lián)規(guī)則，否則稱關聯(lián)規(guī)則X→Y為弱關聯(lián)規(guī)則。在挖掘關聯(lián)規(guī)則時，通常認為強關聯(lián)規(guī)則更能用于指導商務決策；但弱關聯(lián)規(guī)則有時也能起到很好的指導商務決策，如對小眾商品的推薦，雖然支持度不高，很高的提升度，也體現(xiàn)該規(guī)則的商業(yè)價值。13.2.4杠桿率杠桿率是用來衡量X和Y的關系密切程度的。其值越小說明X和Y越獨立，反之，說明X和Y的關系越密切。杠桿率的計算公式如下。13.2.5確信度確信度用來衡量X和Y的獨立性。確信度conviction越大，先導項與后繼項的關聯(lián)性越強。確信度的具體計算公式如下。13.2.6提升度提升度是指相對于不用規(guī)則，使用規(guī)則置信度提高多少。在對非頻繁項集的關聯(lián)規(guī)則的評價特別有意義。具體計算公式如下。目錄基本概念評價準則關聯(lián)規(guī)則算法Apriori算法FPGrowth算法案例Apriori：超市購物籃分析案例FP-Growth：超市購物籃分析

13.3關聯(lián)規(guī)則算法關聯(lián)規(guī)則挖掘算法最常用的是R.Agrawal提出的Apriori算法以及在此基礎上修改搜索算法的FP-Growth，本書詳細介紹這兩種算法的原理以及實現(xiàn)方法。關聯(lián)規(guī)則挖掘過程主要包含兩個階段：第一階段必須先從數(shù)據(jù)集中找出所有的頻繁項集（FrequentItemsets），第二階段再由這些頻繁項集組中產(chǎn)生關聯(lián)規(guī)則（AssociationRules）。第一階段，找出所有的頻繁項集（FrequentItemsets）。（1）找出滿足支持度的單個商品；（2）將以上商品兩兩組合，找出滿足支持度的兩兩組合；（3）依次在以上商品中找到三個，四個....滿足條件的組合；第二階段，產(chǎn)生關聯(lián)規(guī)則(AssociationRules)。（4）在滿足條件的組合中找置信度滿足條件的規(guī)則。13.3.1

Apriori算法輸入：數(shù)據(jù)集D，支持度閾值??輸出：最大的頻繁k項集1.掃描整個數(shù)據(jù)集，得到所有出現(xiàn)過的項集，作為候選頻繁項集。2.挖掘頻繁k項集：（1）?掃描數(shù)據(jù)計算候選頻繁k項集的支持度；（2）?去除候選頻繁k項集中支持度低于閾值的數(shù)據(jù)集，得到頻繁k項集。如果得到的頻繁k項集為空，則直接返回頻繁k-1項集的集合作為算法結(jié)果，算法結(jié)束。如果得到的頻繁k項集只有一項，則直接返回頻繁k項集的集合作為算法結(jié)果，算法結(jié)束；（3）?基于頻繁k項集，連接生成候選頻繁k+1項集。3.令k=k+1，轉(zhuǎn)入步驟2。13.3.1

Apriori算法例13-1Apriori算法現(xiàn)有數(shù)據(jù)集如表13-1所示，為某商店單日交易數(shù)據(jù)集的子集，已做脫敏處理，用字母代替商品名，找出支持度與置信度都大于等于50%的強關聯(lián)規(guī)則。13.3.1

Apriori算法（1）搜索頻繁項集并計算支持度①計算1-項集的支持度

②計算2-項集的支持度：考慮，頻繁項集的子集一定是頻繁項集，非頻繁項集的超集一定不是頻繁項集。B、F、G、H的支持度都小于50%，不可能出現(xiàn)包含B、F、G、H的商品組合的支持度大于等于50%，因此2-項集不考慮包含這些商品的組合。

13.3.1

Apriori算法③計算3項集的支持度將2項集支持度大于等于50%的再次兩兩組合，得到3項集，組合產(chǎn)生的4項集不考慮（如果該4項集為頻繁項集，一定有對應的3項集都為頻繁項集）。

3項集中，僅{A、C、E}滿足支持度大于等50%的要求，因此不存在4項集為頻繁項集。如果有某4項集為頻繁項集，則該4項集對應的4個3項子集應該都為頻繁項集，而此例只有一個3項集為頻繁項集。通過計算得到滿足支持度大于等于50%的k-項集（K>=2），如下表所示。13.3.1

Apriori算法（2）計算規(guī)則的置信度：支持度大于等于50%的頻繁項集，對所有的組合規(guī)則計算置信度如下表所示。由表可見：購買C商品的顧客100%購買A、E商品；購買A、E商品的顧客100%購買C商品；購買A商品的顧客100%購買C商品；購買D商品的顧客100%購買E商品；而購買E商品的顧客只有2/3購買D商品。13.3.1

Apriori算法Apriori算法缺點：1.可能產(chǎn)生大量的候選集，計算過程中，通過排列組合的方式將所有可能的項集都組合出來。2.每次計算需要重新掃描數(shù)據(jù)集，來計算每個項集的支持度。Apriori算法目前比較常用的包為mlxtend，案例1將使用該包實現(xiàn)Apriori算法。13.3.2

FPGrowth算法FPGrowth（頻繁模式增長）算法對Apriori算法上的缺點進行了改進，生成一個頻繁模式而不需要生成候選模式。FPGrowth將提供頻繁項集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹（FP-Tree），但仍保留項集關聯(lián)信息。無論多少數(shù)據(jù)，只需要掃描兩次數(shù)據(jù)，大大提高效率。FP-Tree由以下三部分構(gòu)成：項頭表：存儲所有頻繁1項集出現(xiàn)的次數(shù)，并按次數(shù)降序排列；FPTree：將原始數(shù)據(jù)集映射到了內(nèi)存中的一顆FP樹；節(jié)點鏈表：項頭表中所有頻繁1項集都是節(jié)點鏈表的頭，并依次指向FP樹中該頻繁1項集出現(xiàn)的位置。13.3.2

FPGrowth算法FPTree算法流程：輸入：數(shù)據(jù)集合D，支持度閾值??輸出：最大的頻繁k項集1.掃描數(shù)據(jù)，得到所有1項集的計數(shù)，然后刪除支持度低于閾值的項，將頻繁1項集放入項頭表，并按照支持度降序排列；2.掃描數(shù)據(jù)，對數(shù)據(jù)集合D中的每個事務，去除非頻繁項，并按項支持度的降序排列；3.構(gòu)建FP樹。初始化FP樹，根節(jié)點為空節(jié)點。依次讀入排序后的數(shù)據(jù)集，插入FP樹，插入時按照排序后的順序插入到FP樹中，排序靠前的節(jié)點是祖先節(jié)點，而靠后的是子孫節(jié)點。如果有共用的祖先，則對應的共用祖先節(jié)點計數(shù)加1。插入后，如果有新節(jié)點出現(xiàn)，則項頭表對應的節(jié)點會通過節(jié)點鏈表鏈接上新節(jié)點。直到所有的數(shù)據(jù)都插入到FP樹后，F(xiàn)P樹的建立完成；13.3.2

FPGrowth算法FPTree算法流程：4.從項頭表底部依次向上找到項頭表項對應的條件模式基，即項頭表項為葉節(jié)點的所有前綴路徑的集合，是項頭表項作為葉子節(jié)點所對應的FP子樹；將FP子樹中每個節(jié)點的計數(shù)設置為葉子節(jié)點的計數(shù)，并刪除計數(shù)低于支持度的節(jié)點；5.組合子樹上非葉節(jié)點與葉節(jié)點（項頭表項），形成K項集，K項集的支持度為葉節(jié)點的計數(shù)，遞歸遍歷所有的K項集（K=2,…,n，n為子樹的深度），從條件模式基遞歸挖掘得到項頭表項的頻繁項集。13.3.2

FPGrowth算法例13-2FP-Growth算法示例

算法數(shù)據(jù)集如下表所示：13.3.2

FPGrowth算法（1）掃描數(shù)據(jù)集，得到所有1-項集的計數(shù)，然后刪除支持度低于閾值的項，本例設置閾值為20%，將頻繁1-項集放入項頭表，并按照支持度降序排列；根據(jù)數(shù)據(jù)集計算1-項集計數(shù)，結(jié)果如下表所示：刪除F、G、H、I、J、K節(jié)點，余下節(jié)點排序放入項頭表，如下表所示：13.3.2

FPGrowth算法（2）掃描數(shù)據(jù)集，對數(shù)據(jù)集合D中的每個事務，去除非頻繁項，對每一個交易中的項按其支持度的降序排列；如下表第1個交易中由于C的支持度大于B，所以C排在B的前面，其他交易同樣排序；至此，已兩次讀取數(shù)據(jù)集，不需要再讀原數(shù)據(jù)集。13.3.2

FPGrowth算法（3）構(gòu)建FP樹基于項頭表和排序后的數(shù)據(jù)集，構(gòu)建FP樹。初始FP樹為空，置根節(jié)點為“null”，然后讀入排序后的數(shù)據(jù)集中的一個交易，插入FP樹，插入時按照排序后的順序，插入FP樹中，排序靠前的節(jié)點是祖先節(jié)點，而靠后的是子孫節(jié)點，直到所有的交易讀入完成。如果有共用的祖先，則對應的公用祖先節(jié)點計數(shù)加1。插入后，如果有新節(jié)點出現(xiàn)，則項頭表對應的節(jié)點會通過節(jié)點鏈表鏈接上新節(jié)點。直到所有的數(shù)據(jù)都插入到FP樹后，F(xiàn)P樹的建立完成。13.3.2

FPGrowth算法13.3.2

FPGrowth算法13.3.2

FPGrowth算法13.3.2

FPGrowth算法13.3.2

FPGrowth算法13.3.2

FPGrowth算法（4）遞歸挖掘頻繁項集取項頭表底部的項D，從FP樹中取D的子樹，根據(jù)支持度閾值裁剪，由該子樹生成包含D的頻繁項集。依次取E、B、C、A，從對應的子樹生成包含該項的頻繁項集。具體過程如下圖所示。13.3.2

FPGrowth算法13.3.2

FPGrowth算法13.3.2

FPGrowth算法FP-Growth挖掘的頻繁項集如下表所示。在Python3.x中可用pyfpgrowth包實現(xiàn)FP-Growth算法，案例FP-Growth采用pyfpgrowth實現(xiàn)該算法。Python2.x可以使用fp-growth實現(xiàn)。目錄基本概念評價準則關聯(lián)規(guī)則算法案例Apriori：超市購物籃分析目標數(shù)據(jù)集介紹實現(xiàn)代碼案例FP-Growth：超市購物籃分析

13.4.1目標通過關聯(lián)規(guī)則分析找到不同商品的關聯(lián)關系，為超市進一步的決策提供支持。13.4.2數(shù)據(jù)集介紹數(shù)據(jù)集來源阿里天池，某超市一段時間的銷售記錄。13.4.3實現(xiàn)代碼1.定義函數(shù)讀取購物籃數(shù)據(jù)defread_file_apriori(filename):k=[]withopen(filename)asf:foriinf:k.append(i.split())returnkdata=read_file_apriori("d:/datasets/basket.txt")2.導入必要的包frommlxtend.preprocessingimportTransactionEncoderfrommlxtend.frequent_patternsimportaprioriimportpandasaspdte=TransactionEncoder()13.4.3實現(xiàn)代碼3.對購物籃商品進行編碼te_ary=te.fit(data).transform(data)類似onehot編碼，所有的商品都是特征，樣本中對應商品特征為True的，表示樣本中包含了此商品，為False表示未包含。如下圖：13.4.3實現(xiàn)代碼4.找出滿足最小支持度的商品df=pd.DataFrame(te_ary,columns=te.columns_)freq=apriori(df,min_support=0.05,use_colnames=True)#找出滿足最小支持度0.05的商品。freq#輸出freqfreq的內(nèi)容如下：13.4.3實現(xiàn)代碼5.找出滿足條件的規(guī)則#導入關聯(lián)規(guī)則包frommlxtend.frequent_patternsimportassociation_rules#查找滿足條件的規(guī)則result=association_rules(freq,metric="confidence",min_threshold=0.4)#找出滿足置信度大于0.4的規(guī)則其中：metric參數(shù)指定考察的指標。如：'support','confidence','lift','leverage','conviction'等。結(jié)果如下：13.4.3實現(xiàn)代碼其中：第一列為前因，第二列為后果，第三列為前因的支持度，第四列為后果的支持度，第五列為規(guī)則的支持度，第六列為規(guī)則的置信度，后面依次為提升度、杠桿率以及確信度。第一行表示購買“cannedveg”的客戶購買“beer”的置信度為0.569966，規(guī)則的支持度（同時購買這兩個商品）為0.177660?！癱annedveg”的支持度為0.322340，“beer”的支持度為0.311702。?目錄基本概念評價準則關聯(lián)規(guī)則算法案例Apriori：超市購物籃分析案例FP-Growth：超市購物籃分析目標數(shù)據(jù)集介紹實現(xiàn)代碼13.5.1目標通過關聯(lián)規(guī)則分析找到不同商品的關聯(lián)關系，為超市進一步的決策提供支持。13.5.2數(shù)據(jù)集介紹數(shù)據(jù)集為用戶單次超市的購物數(shù)據(jù)集，僅包含不同商品的名稱，不含數(shù)量。13.5.3實現(xiàn)代碼1.定義函數(shù)讀取購物籃數(shù)據(jù)defread_file_apriori(filename):k=[]withopen(filename)asf:foriinf:k.append(i.split(