高級大數據人才培養叢書之一，大數據挖掘技術與應用數據挖掘（第二版）第六章關聯規則of642高級大數據人才培養叢書之一，大數據挖掘技術與應用

關聯規則是一種描述性的而非預測性的方法，經常用于發現隱藏在大型數據集背后的，項集之間的有趣關聯或相互關系。20世紀60年代，Hajek等人在早期研究中介紹了許多關聯規則學習的關鍵概念和方法，但是主要關注的是數學表達，而不是算法。20世紀90年代初，IBM公司Almaden研究中心的Agrawal等人將關聯規則學習架構引入數據庫社區，在超市內的銷售終端系統記錄的客戶交易大型數據庫中尋找商品之間的聯系規則，這些規則刻畫了客戶購買行為模式，可以用來指導商家科學地安排進貨、庫存以及貨架設計等。More應用市場：購物籃分析、交叉銷售（CrossingSale）、點擊流分析、推薦系統、醫療診斷，以及通信、互聯網、電子商務······6.1基本概念第六章關聯規則6.2

Apriori算法6.3

FP-growth算法3.1數據挖掘概述6.5實戰：購物籃關聯規則挖掘習題6.4其他關聯規則算法of643高級大數據人才培養叢書之一，大數據挖掘技術與應用

早在20世紀80年代，沃爾瑪超市就已經將關聯規則應用到了商品管理之中。沃爾瑪曾經對數據倉庫中一年多的原始交易數據進行了詳細的分析，發現許多美國家庭都是妻子在家照顧嬰兒，丈夫去超市為嬰兒買尿布。丈夫們在購買尿布時往往會順便買兩瓶啤酒來犒勞自己。這一現象引起了沃爾瑪的重視，沃爾瑪調整了貨架的位置，把尿布和啤酒擺在相鄰的位置，以便于年輕的爸爸們能順利地同時找到這兩種商品。這一故事中的“啤酒”與“尿布”的關系即為所謂的“關聯性”，而“關聯性”的發掘和利用則是本章所要討論的“關聯規則挖掘”。6.1.1購物籃分析：啤酒與尿布的經典案例of6446.1基本概念第六章關聯規則

關聯規則挖掘是指從一個大型的數據集（dataset）中發現有趣的關聯或相關關系，即從數據集中識別出頻繁出現的屬性值集，也稱為頻繁項集，然后利用這些頻繁項集創建描述關聯關系規則的過程。關聯規則相關定義如下：1.項集(itemset)

設I={i1,i2,…,im}，是m個不同的項目的集合，每個ij稱為一個項目。項目的集合I稱為項集。其元素的個數稱為項集的長度，長度為k的項集稱為k-項集。下表中每個商品就是一個項目，項集I={面包，牛奶，尿布，啤酒，茶}，I的長度|I|=6。6.1.2關聯規則的概念of6456.1基本概念第六章關聯規則

6.1.2關聯規則的概念of6466.1基本概念第六章關聯規則

6.1.2關聯規則的概念of6476.1基本概念第六章關聯規則

6.1.2關聯規則的概念of6486.1基本概念第六章關聯規則

6.1.2關聯規則的概念of6496.1基本概念第六章關聯規則

6.1.2關聯規則的概念of64106.1基本概念第六章關聯規則

6.1.2關聯規則的概念of64116.1基本概念第六章關聯規則

6.1.2關聯規則的概念of64126.1基本概念第六章關聯規則

6.1.3頻繁項集的產生of64136.1基本概念第六章關聯規則

6.1.3頻繁項集的產生of64146.1基本概念第六章關聯規則6.1基本概念第六章關聯規則6.2

Apriori算法6.3

FP-growth算法3.1數據挖掘概述6.5實戰：購物籃關聯規則挖掘習題6.4其他關聯規則算法of6415高級大數據人才培養叢書之一，大數據挖掘技術與應用

Apriori算法是Agrawal和R.Srikant于1994年提出的，為布爾關聯規則挖掘頻繁項集的原創性算法。Apriori算法的核心是使用候選項集尋找頻繁項集。6.2.1Apriori算法的頻繁項集產生of64166.2Apriori算法第六章關聯規則

Apriori使用一種稱為逐層搜索的迭代方法，k項集用于搜索（k+1）項集。首先，找出所有頻繁1項集的集合L1，然后用L1生成候選2項集的集合C2，最后，通過探查候選2項集的集合來形成頻繁2項集的集合L2。以此類推，使用L2尋找L3。如此迭代，直至不能找到頻繁k項集為止。Apriori算法中提高頻繁項集逐層搜索效率的方法是減少頻繁項集產生時需要探查的候選項集的個數，該方法基于先驗性質（Aprioriproperty），從而達到壓縮搜索空間的目的。6.2.1Apriori算法的頻繁項集產生of64176.2Apriori算法第六章關聯規則先驗性質：頻繁項集的所有非空子集也一定是頻繁項集。該先驗性質可引申出兩個結論：結論1：若X為頻繁項集，則X的所有子集都是頻繁項集。結論2：若X為非頻繁項集，則X的所有超集均為非頻繁項集。6.2.1Apriori算法的頻繁項集產生of64186.2Apriori算法第六章關聯規則

利用先驗性質，我們在使用頻繁(k-1)項集的集合Lk-1尋找頻繁k項集的集合Lk時分兩個過程：連接步和剪枝步。（1）連接步:Lk-1與其自身進行連接，產生候選k項集的集合Ck。Lk-1中某個元素與其中另一個元素可以執行連接操作的前提是它們中有(k-2)個項是相同的，也就是只有一個項是不同的。例如：項集{I1,I2}與{I1,I5}有共同的I1，連接之后產生的項集是{I1,I2,I5}，反之，項集{I1,I2}與{I3,I4}，沒有1個共同的項集，不能進行連接操作。（2）剪枝步：

候選k項集的集合Ck中的元素可以是頻繁項集，也可以不是。但所有的頻繁k項集一定包含在Ck中，所以，Ck是Lk的超集。掃描事務集D，計算Ck中每個候選k項集出現的次數，所有出現次數大于等于最小支持度計數的候選k項集的集合便組成頻繁k項集的集合Lk。

最小支持度計數是最小支持度閾值與事務集D中事務總數的乘積，有些書上也稱最小支持度閾值為相對最小支持度，最小支持度計數為絕對最小支持度。6.2.1Apriori算法的頻繁項集產生of64196.2Apriori算法第六章關聯規則例6.1Apriori算法。以下表的某超市交易數據為例，用Apriori算法發現該超市交易的頻繁項集，設定最小支持度計數為3（相對支持度minsup=30%）。6.2.1Apriori算法的頻繁項集產生of64206.2Apriori算法第六章關聯規則例6.1Apriori算法。（1）第一次迭代時，每個項都是候選1項集的集合C1的成員。算法掃描一次所有的事務，對每個項的出現頻次計數。（2）由滿足最小支持度的候選1項集組成頻繁1項集的集合L1。注意，由于候選項集{茶}的支持度計數小于3，因此，生成的頻繁1項集的集合L1不包含候選項集{茶}。6.2.1Apriori算法的頻繁項集產生of64216.2Apriori算法第六章關聯規則

6.2.1Apriori算法的頻繁項集產生of64226.2Apriori算法第六章關聯規則

6.2.2Apriori算法描述of64236.2Apriori算法第六章關聯規則Apriori算法的具體實現如下：寬度優先搜索整個項集空間，從k=0開始，迭代產生長度為k+1的候選項集的集合Ck+1。候選項集是其所有子集都是頻繁項集的項集。C1由I0中所有的項構成，在第k層產生所有長度為k+1的項集。這由兩步完成：第一步，Lk自連接。將Lk中具有相同(k-1)前綴的項集連接成長度為k+1的(候選)項集。第二步是剪枝，如果項集的所有長度為k的子集都在Lk中，該項集才能作為候選項集被加入Ck+1中。為了計算所有長度為k的候選項集的支持度，在數據庫水平表示方式下，需要掃描數據庫一遍。在每次掃描中，對數據庫中的每條交易記錄，為其中所包含的所有候選k-項集的支持度計數加1。所有頻繁k項集被加入Lk中。此過程直至Ck+1等于空集時結束。

對于海量數據，Apriori算法的時空復雜度都不容忽視。空間復雜度：如果L1數量達到104的量級，那么C2中的候選項將達到107的量級。時間復雜度：每計算一次Ck就需要掃描一遍數據庫。6.1基本概念第六章關聯規則6.2

Apriori算法6.3

FP-growth算法3.1數據挖掘概述6.5實戰：購物籃關聯規則挖掘習題6.4其他關聯規則算法of6424高級大數據人才培養叢書之一，大數據挖掘技術與應用of64256.3FP-growth算法第六章關聯規則

在許多情況下，Apriori算法顯著地壓縮了候選項集的規模，并產生很好的性能。但是，該算法存在以下不足：

（1）可能產生大量頻繁項集。例如，如果有104個頻繁1項集，則Apriori算法需要產生多達107個候選2項集。

（2）可能需要重復地掃描整個數據庫，通過模式匹配檢查一個很大的候選集合。檢查數據庫中每個事務來確定候選項集支持度的開銷很大。FP-growth算法采取分而治之的思路：首先，將代表頻繁項集的數據庫壓縮到一棵頻繁模式樹（FrequentPatterntree，簡稱FP樹）中，該樹仍然保留項集的關聯信息。然后，把這種壓縮后的數據庫劃分成一組條件數據庫（一種特殊類型的投影數據庫），每個數據庫關聯一個頻繁段或“模式段”，并分別挖掘每個條件數據庫。對于每個“模式片段”，只需要考察與它相關聯數據集。因此，隨著被考察的模式的“增長”，這種方法可以顯著地壓縮被搜索的數據集的大小。由上可知，FP-growth算法包含兩個步驟：第一步，構造FP樹；第二步，在FP樹上挖掘頻繁項集。6.3.1構造FP樹of64266.3FP-growth算法第六章關聯規則

右表所示為某事務集合，以此小案例說明FP樹的生成過程。事務數據集排序：掃描該事務數據集，確定該事務數據集中包含的所有項的集合I及每個項的支持度計數I&S={a:3，b:3，c:4，d:1，e:1，f:4，g:1，h:1，i:1，j:1，k:1，l:2，m:3，n:1，o:2，p:3，s:1}。針對得到的集合I，丟棄非頻繁項，并將頻繁項按照支持度的遞減排序，結果集或表記為L，有L={f:4，c:4，a:3，b:3，m:3，p:3，l:2，o:2}。最后，對事務數據集中的項集逐一掃描，每個項集剔除非頻繁項后，余下的頻繁項按照L的降序重新排列（見右表第三列）。6.3.1構造FP樹of64276.3FP-growth算法第六章關聯規則

6.3.1構造FP樹of64286.3FP-growth算法第六章關聯規則

（1）（2）6.3.1構造FP樹of64296.3FP-growth算法第六章關聯規則

（1）（2）（3）6.3.1構造FP樹of64306.3FP-growth算法第六章關聯規則

（1）（2）（3）（4）6.3.1構造FP樹of64316.3FP-growth算法第六章關聯規則

（4）（5）6.3.1構造FP樹of64326.3FP-growth算法第六章關聯規則

為了方便樹的遍歷，創建一個項頭表，使每項通過一個結點鏈指向它在樹中的位置。掃描所有的事務，得到的FP樹顯示在下圖，帶有相關的結點鏈。6.3.2挖掘FP樹of64336.3FP-growth算法第六章關聯規則FP樹的挖掘過程為：從長度為1的頻繁模式（初始后綴模式）開始，構造它的條件模式基（一個“子數據庫”，由FP樹中與該后綴模式一起出現的前綴路徑集組成）。然后，構造它的（條件）FP樹，并遞歸地在該樹上進行挖掘。模式增長通過后綴模式與條件FP樹產生的頻繁模式連接實現。6.3.2挖掘FP樹of64346.3FP-growth算法第六章關聯規則

（1）對FP樹的項頭表從表尾向表頭逆序逐一掃描，當掃描到某個頻繁1項ij時，由其結點鏈得到FP樹中以ij結尾的前綴路徑。

例如，下圖中，對于項頭表的頻繁1項o，由FP樹可得到以o結尾的前綴路徑。見圖（a)。6.3.2挖掘FP樹of64356.3FP-growth算法第六章關聯規則

（2）以頻繁項ij在該路徑上的支持度計數為依據，更新前綴路徑上結點的支持度計數。根據已更新支持度計數的前綴路徑，可以得到頻繁項ij的條件模式基。如圖(b)所示，首先依據結點o在該路徑上的支持度更新前綴路徑上結點的支持度計數。在此基礎上，得到結點o的條件模式基{f,c,a,b,m,l}，{f,b}。

（3）構建條件FP樹。對頻繁項ij的條件模式基，按照上一節的構造FP樹的方法來構造條件FP樹。如圖(c)所示，得到結點o的條件FP樹。該樹只有一條路徑。

6.3.2挖掘FP樹of64366.3FP-growth算法第六章關聯規則

（4）構建頻繁項集。如果該條件FP樹有多條路徑，則繼續迭代，構造條件FP樹（詳細說明見步驟（5））。否則，如果該條件FP樹只有一條路徑，則直接求以該結點結尾的頻繁項集。如圖（c）所示，結點o的條件FP樹只有一條路徑<f:2,b:2>。由結點o與{f,b}進行連接，產生頻繁模式{f,o:2}，{b,o:2}，{f,b,o:2}。6.3.2挖掘FP樹of64376.3FP-growth算法第六章關聯規則

（5）如果該條件FP樹有多條路徑，則繼續迭代，構造條件FP樹。

以結點b為例，其條件FP樹有路徑null->f->c和null->c，需要繼續迭代。迭代思路如下：采用分治策略將一個問題劃分為較小的子問題，從而發現某個特定后綴結尾的所有頻繁項集。對于結點b，則分別考慮以cb為后綴的條件FP樹和以fb為后綴的條件FP樹。

以cb為后綴的條件FP樹構造如下：以結點b的FP樹為基礎，考慮以cb為后綴的前綴路徑，如圖（d）。處理c的前綴路徑后，只發現項集{c,b}是頻繁的，也即cb為后綴的條件FP樹為空。

以fb為后綴的條件FP樹構造如下：以結點b的FP樹為基礎，考慮以fb為后綴的前綴路徑，如圖6-7（e）。處理f的前綴路徑后，只發現項集{f,b}是頻繁的，也即fb為后綴的條件FP樹為空。6.3.3FP-growth算法of64386.3FP-growth算法第六章關聯規則

（1）構造項頭表：掃描數據庫一遍，得到頻繁項的集合F和每個頻繁項的支持度。把F按支持度遞降排序，記為L。

（2）構造原始FP-Tree：把數據庫中每個事務的頻繁項按照L中的順序進行重排。并按照重排之后的順序把每個事務的每個頻繁項插入以null為根的FP-Tree中。如果插入時頻繁項節點已經存在了，則把該頻繁項節點支持度加1；如果該節點不存在，則創建支持度為1的節點，并把該節點鏈接到項頭表中。（3）調用FP-growth(Tree，null)開始進行挖掘。偽代碼如下：procedure

FP_growth(Tree,

a)if

Tree含單個路徑Pthen

for

路徑P中結點的每個組合（記作b）

產生模式bUa，其支持度support=b中結點的最小支持度；else

foreach

ai在Tree的頭部(按照支持度由低到高順序進行掃描){

產生一個模式b=aiUa，其支持度support=ai.support；

構造b的條件模式基，然后構造b的條件FP-tree；

ifTree不為空then

調用FP-growth(Tree,b)；}6.1基本概念第六章關聯規則6.2

Apriori算法6.3

FP-growth算法3.1數據挖掘概述6.5實戰：購物籃關聯規則挖掘習題6.4其他關聯規則算法of6439高級大數據人才培養叢書之一，大數據挖掘技術與應用6.4.1約束性關聯規則of64406.4其它關聯規則算法第六章關聯規則

1.相關概念及定義設I={i1,i2,i3,…,in}是所有項目(items)的集合，設D為一個事務數據庫，其中的每個務T為一個項集，且T?1。定義：基于項約束條件C的關聯規則就是形如X≥Y的蘊涵式，其中X?I，Y?I，X∩Y=Φ，且X≥Y成立的條件是：1）它具有支持度s，即交易數據庫中至少有s%的記錄包含X∪Y；2）它具有置信度c，即在交易數據庫中包含X的記錄至少有c%同時也包含Y；3）它必須滿足項約束條件C。設C為I上的一個布爾表達式，將C轉化為DNF形式，形如：d1∨d2∨d3∨…∨dm，其中每個di形如：di=ai1∧ai2∧…∧aim，aij∈I。6.4.1約束性關聯規則of64416.4其它關聯規則算法第六章關聯規則

2.相關算法及改進MultipleJoins、Recorder和Direct算法[7-8]是最早提出的項約束算法，這些算法在生成頻繁項集的過程中，利用項的約束條件對項集進行篩選，得出關聯規則。在此基礎上，后來的研究者利用頻繁項集和非頻繁項集的性質，將項約束條件劃分為單調性約束、反單調性約束以及簡潔約束等幾類，運用遞歸的思想進行剪枝得出所需的頻繁項集，如ElcatA[9]、AMMC[10]、FICA[11]、CSAR[12]等算法。隨著項約束算法研究的深入，更多的約束方法和思想加入了項約束算法中，如DFTFH[13]、VCM[14]、MSEB[15]等算法。這些算法利用FP-tree或概念格的思想，采用垂直數據形式表示數據集和深度優先的挖掘策略得出關聯規則[16-17]。此外，還有基于二進制約束的關聯規則算法、基于權重和時序約束的關聯規則算法[18-19]等。6.4.2增量式關聯規則of64426.4其它關聯規則算法第六章關聯規則

1.相關概念及定義根據實際應用需求，關聯規則的更新問題可以分為以下幾種情況：(1)事務數據庫不變，最小支持度發生變化時，關聯規則的高效更新問題；(2)最小支持度不變，一個事務數據集d1。添加到事務數據庫D中去時，如何生成最新事務數據庫D∪d1中的關聯規則；(3)最小支持度不變，從事務數據庫D中刪除一個事務數據集d2(d2?D)后，如何高效地生成事務數據庫D-d2中的關聯規則。至于其它情況，可由上述三種情況組合而成，因此，這三種情況是更新問題的基礎和核心。6.4.2增量式關聯規則of64436.4其它關聯規則算法第六章關聯規則2.相關算法及改進Cheung[20]提出了FUP算法，在此基礎上Cheung又提出了改進算法FUP2算法，可以處理數據集減少是的頻繁項挖掘，而面向增量數據集時，算法和FUP相似。UWEP算法[21]與FUP算法類似，但此算法采用提前對原頻繁項集剪枝的策略，在k頻繁項集挖掘時，候選集在增量數據集上產生。而針對在每個時間節點，都有新數據產生的問題，文獻[22]提出了YAMI算法。針對支持度變小時，頻繁模式也將增加，馮玉才[23]提出了IUA算法。周海巖[24]最早論證了IUA算法存在誤剪枝問題，提出了改進算法NEWIUA。以上這些算法都是基于Apriori算法提出的，還有一些算法則是基于FP-growth算法。比較典型的有Koh[25]提出的AFPIM算法，對增加的數據集調整樹的結構。朱玉全[26]提出基于FP樹的，面向支持度變化的FIUA1算法和數據量增加的FIUA2算法。易彤[27]提出的IFP-Growth算法整合了支持度變化和數據集變化情況，提出的IFP樹在調整時通過調整子樹來完成。IACAI算法[28]采用提前縮減數據集的策略，即將不含任何頻繁項的空事務提前剪去。6.4.3多層關聯規則of64446.4其它關聯規則算法第六章關聯規則1.多層關聯規則的定義

設I={i1,i2,…,im}是由稱作項(Item)的ik(k=1,2,…,m)構成的項的集合，項的集合上的概括層次關系用概念層次樹T表示，結點表示項或項的概括。若從結點P到Q之間有弧，則稱P是Q的祖先(P是Q的概括)，Q是P的子孫。祖先、子孫關系具有傳遞性，如果B是D的祖先，A是B的祖先，則A是D的祖先。

6.4.3多層關聯規則of64456.4其它關聯規則算法第六章關聯規則2.多層關聯規則挖掘步驟給定一個事務數據庫D和項集合上的概括層次樹T，多層關聯規則挖掘的任務就是產生支持度和置信度分別大于用戶給定的最小支持度(minsup)和最小可信度(minconf)的關聯規則。多層關聯規則挖掘一般包含三個基本的步驟：

（1）根據事務數據庫D和D上的概念層次樹T，挖掘出所有的頻繁模式FP={X|X?I,support(X)≥minsup}；

（2）由頻繁模式產生強關聯規則，由頻繁模式產生關聯規則的方法如下:①對于每個頻繁項集t，產生t的所有非空子集。②對于t的每個非空子集s，如果support(t)/support(s)≥minconf，則輸出規則"s?(t-s)"。其中，minconf是最小置信度閾值。（3）從所有的多層關聯規則中刪除用戶不感興趣的、冗余的規則。在這三個步驟中，第二步和第三步相對容易，多層關聯規則挖掘的總體性能由第一步決定。6.4.3多層關聯規則of64466.4其它關聯規則算法第六章關聯規則3.常用算法及改進在用于多層關聯規則挖掘的經典算法中，以Cumulate[29]和ML-T2L1[30]最為著名。Cumulate算法能進行多層及跨層次頻繁模式的挖掘，但該算法僅是將源數據放在同一層次級別上考慮的普遍化關聯規則挖掘算法；ML-T2L1算法采用自頂向下方式進行逐層挖掘，但不支持跨層次的挖掘。這2種算法都基于Apriori算法思想，因此存在著與Apriori算法相同的缺陷。MLAR-FP[31]算法是以FP-growth算法為基礎而構建的，通過把每個事務中每個項的全部祖先加入到該條事務中，并刪除重復的祖先，從而保證了算法能夠發現多層關聯規則。Ada-FP[32]是基于FP-growth算法的多層多維頻繁模式挖掘算法，采用了多支持度約束。但如果原始數據只是最低抽象層的項，則無法挖掘出隱藏在層間的關聯規則。研究者們還提出了許多其他的改進算法，文獻[33]提出了一種多支持度挖掘算法；文獻[34]提出了一種加權的關聯規則挖掘方法；文獻[35]提出了基于遺傳算法的多層關聯規則改進算法；文獻[36]則提出了一種并行化挖掘多層關聯規則的算法。6.1基本概念第六章關聯規則6.2

Apriori算法6.3

FP-growth算法3.1數據挖掘概述6.5實戰：購物籃關聯規則挖掘習題6.4其他關聯規則算法of6447高級大數據人才培養叢書之一，大數據挖掘技術與應用6.5.1背景與挖掘目標of64486.5實戰：購物籃關聯規則挖掘第六章關聯規則關聯規則作為數據挖掘中一個重要的組成部分，能夠有效地發現大量數據中相關屬性集之間有趣的關聯關系，從而為政策或規則的制定提供參考依據。近年來，關聯規則分析已經被廣泛應用于物流、零售、信用卡營銷及其風險管理等眾多領域。本案例通過Python語言，分別采用Apriori算法和FP-growth算法實現購物籃關聯規則挖掘，有效地挖掘超市商品之間的關聯關系，為商品捆綁銷售、貨架商品陳列等分析提供有用的信息。6.5.2分析方法與過程of64496.5實戰：購物籃關聯規則挖掘第六章關聯規則本案例通過調用Python的mlxtend庫，對購物籃數據進行關聯規則分析。購物籃包含fruitveg、freshmeat、dairy、cannedveg、cannedmeat、frozenmeal、beer、wine、softdrink、fish、confectionery11種商品。本案例數據源于大數據實驗課程，對于原始數據的數據抽取、數據預處理、數據轉換等步驟省略。6.5.2分析方法與過程of64506.5實戰：購物籃關聯規則挖掘第六章關聯規則1.Apriori算法實現第一步：引入相應的函數庫資源，讀入完整數據，并進行數據初步了解。#引入pandas庫文件讀取、Matplotlib作圖準備、Numpy庫科學計算、mlxtend庫模型集成、Seaborn庫統計制圖importpandasaspdimportmatplotlib.pyplotaspltimportnumpyasnpfrommlxtend.frequent_patternsimportaprioriimportseabornassnsfrommlxtend.frequent_patternsimportassociation_rules,apriori#讀出文件數據，并展示Scart=pd.read_csv(r'路徑\ShopCT.csv')Scart6.5.2分析方法與過程of64516.5實戰：購物籃關聯規則挖掘第六章關聯規則1.Apriori算法實現第一步：引入相應的函數庫資源，讀入完整數據，并進行數據初步了解。購物籃數據集6.5.2分析方法與過程of64526.5實戰：購物籃關聯規則挖掘第六章關聯規則1.Apriori算法實現第二步：發現規則。#進行Apriori分析，設置最小支持度閾值

為0.01，獲得頻繁項集集合frequent_items_sum=apriori(Scart,min_support=0.01,use_colnames=True)#設置最小提升度閾值

為1，獲得關聯規則集合rules_sum=association_rules(frequent_items_sum,metric="lift",min_threshold=1)#按照置信度值降序排序關聯規則集合，并顯示rules_sum.sort_values('confidence',ascending=False,inplace=True)rules_sum6.5.2分析方法與過程of64536.5實戰：購物籃關聯規則挖掘第六章關聯規則1.Apriori算法實現第二步：發現規則。6.5.2分析方法與過程of64546.5實戰：購物籃關聯規則挖掘第六章關聯規則2.FP-Growth算法實現第一步：引入相應的函數庫資源，讀入完整數據，并進行數據初步了解。#引入pandas庫文件讀取、Matplotlib作圖準備、NumPy庫科學計算、mlxtend庫模型集成、Seaborn庫統計制圖importpandasaspdimportmatplotlib.pyplotaspltimportnumpyasnpfrommlxtend.frequent_patternsimportfpgrowthimportseabornassnsfrommlxtend.frequent_patternsimportassociation_rules,fpgrowth#讀出文件數據，并展示Scart=pd.read_csv(r'路徑\ShopCT.csv')Scart6.5.2分析方法與過程of64556.5實戰：購物籃關聯規則挖掘第六章關聯規則2.FP-Growthi算法實現第二步：發現規則。6.5.2分析方法與過程of64566.5實戰：購物籃關聯規則挖掘第六章關聯規則

由于Apriori關聯分析只能處理離散型的數據屬性（若需要分析年齡、收入屬性，則需事先進行離散處理），故在此選擇性別（sex）、區域（region）、婚姻狀況（married）、是否生育（children）、是否有車（car）、按揭時是否有抵押(mortage)、是否有股權計劃(pep)等樣本屬性，以及所有樣本數據，進行相關性分析。數據截圖如下圖6.5.2分析方法與過程of64576.5實戰：購物籃關聯規則挖掘第六章關聯規則2.FP-Growth算法實現第二步：發現規則。#進行FP-growth分析，設置最小支持度閾值為0.01，獲得頻繁項集集合frequent_items_sum=fpgrowth(Scart,min_support=0.01,use_colnames=True)#調用association_rules函數，設置最小提升度

閾值為1，獲得關聯規則集合rules_sum=association_rules(frequent_items_sum,metric="lift",min_threshold=1)#按照置信度值降序關聯規則集合，并顯示rules_sum.sort_values('confidence',ascending=False,inplace=True)rules_sum6.5.3總結of64586.5實戰：購物籃關聯規則挖掘第六章關聯規則從以上分析我們可以幫助超市賣場推薦堆頭、或者捆綁商品的組合，再或者近距離貨架擺放策略，如beer和cannedveg、frozenmeal、wine、fruitveg等擺放在一起，或者beer和fruitveg、fish、frozenmeal、cannedveg等組合陳列，再或者cannedveg和beer、cannedmeat、fish等捆綁銷售。1．給出一個小例子表明強關聯規則中的項實際上可能是負相關的。2．假定大型事務數據庫DB的頻繁項集已經存儲，討論：如果新的事務集△DB加入，在相同的最小支持度閾值下，如何有效的挖掘全局關聯規則？3．考慮下面的頻繁-3項集的集合：{1,2,3}，{1,2,4}，{1,2,5}，{1,3,4}，{1,3,5}，{2,3,4}，{2,3,5}，{3,4,5}假定數據集中只有5個項。列出Apriori算法的候選產生過程得到的所有候選4-項集，以及剪枝步后剩下的所有候選4-項集。4．下表為某超市事務數據，其中hotdog表示含熱狗的事務，hotdog表示不包含熱狗的事務，hamburger表示包含漢堡包的事務，hamburger表示不包含漢堡包的事務。of4359習題第六章關聯規則of4360習題第六章關聯規則5．證明從包含d個項的數據集提取的可能規則總數是：R=3d-2d+1+1提示：首先，計算創建形成規則左部項集的方法數，然后對每個選定為規則左部的k項集，計算選擇剩下的d-k個項形成規則右部的方法數。假設最小支持度閾值minsup=20%，最小置信度閾值mincon=70%，試問熱狗和漢堡包的關聯性如何？感謝聆聽高級大數據人才培養叢書之一，大數據挖掘技術與應用數據挖掘（第二版）第七章集成學習of6463高級大數據人才培養叢書之一，大數據挖掘技術與應用

集成學習是數據挖掘算法的一種，本質上是將多個基學習器通過有效融合集成為一個強學習器，從而提高泛化精度。在人臉識別、NLP等領域有廣泛應用。圖像識別自然語言處理7.1集成學習的概念第七章集成學習7.2

Bagging算法與隨機森林算法7.3

Boosting算法3.1數據挖掘概述7.5多樣性習題7.4結合策略of6464高級大數據人才培養叢書之一，大數據挖掘技術與應用7.6實戰案例

集成學習是在建立基學習器的基礎上進行有效融合集成形成強學習器，其中包括3個主要階段性工作：一是基學習器的構建設計；二是基學習器的集成方法；三是基學習器結果的整合。7.1.1集成學習的構建of64657.1集成學習的概念第七章集成學習

集成學習的兩個主要工作一般可以劃分為訓練和檢驗兩個階段。訓練階段是訓練形成集成模型，主要針對訓練樣本數據集，劃分多個基學習器按照一定的融合集成規則形成一個強學習器；檢驗階段是驗證調整集成模型，主要針對測試樣本數據集，對多個基學習器的預測結果按照一定的集成整合規則形成集成預測結果。7.1.1集成學習的構建of64667.1集成學習的概念第七章集成學習7.1.1集成學習的構建of64677.1集成學習的概念第七章集成學習同質集成學習同質集成學習是指基學習器的類型為同一類學習器，如都是決策樹的基分類器集成為強決策樹異質集成學習異質集成學習是不同類型的基學習器的集成，如決策樹與神經網絡的集成，如疊加法（Sta按照基學習器的類型異同7.1.1集成學習的構建of64687.1集成學習的概念第七章集成學習根據基學習器的生成順序串行組合經典的集成學習方法Boosting及其改進的AdaBoosting、GDBT（GradientBoostingDecisionTree）并行組合Bagging及在此基礎上的隨機森林算法混合拓撲組合兩階段集成學習（Two-PhasesEnsembleLeaming，TPEL）是一種先串行后并行7.1.2集成學習的優勢of64697.1集成學習的概念第七章集成學習兼聽則明，偏聽則暗三個臭皮匠，賽過諸葛亮7.1.2集成學習的優勢of64707.1集成學習的概念第七章集成學習集成學習在統計上的有效性7.1.2集成學習的優勢of64717.1集成學習的概念第七章集成學習集成學習在計算上的有效性7.1.2集成學習的優勢of64727.1集成學習的概念第七章集成學習集成學習在表示上的有效性7.1.2集成學習的優勢of64737.1集成學習的概念第七章集成學習集成學習的準確性二分類問題集成學習分類正確集成學習分類不正確的概率根據霍夫丁不等式，集成學習誤差7.1.2集成學習的優勢of64747.1集成學習的概念第七章集成學習集成學習的準確性根據霍夫丁不等式，集成學習誤差集成學習誤差上限受到基學習器數量N和基學習器誤差

決定，當基學習器數量N越多時，誤差上限越小；當基學習器誤差

時，基學習器誤差越小，集成學習誤差上限越小。結論7.1.2集成學習的優勢of64757.1集成學習的概念第七章集成學習集成學習的多樣性結論基學習器從數據集正確率樣本1樣本2樣本3C1√√×66.67%C2×√√66.67%C3√×√66.67%C4×√√66.67%集成學習EL1={C1、C2、C3}，EL2={C2、C3、C4}，觀察EL1中的C1、C2、C3，兩兩之間的相似度為33.33%，EL2中的C2、C3、C4中，C2與C4的相似度為100%，與C1的相似度為33.33%。

按照大數原則進行集成，EL1在數據集的分類精度（正確率）為100%，集成比基學習器精度都要高。然而，EL2在數據集的分類精度（正確率）為66.67%，與基學習器相當，集成并沒有提高預測效果。7.2Bagging算法與隨機森林算法第七章集成學習7.1集成學習的概念7.3

Boosting算法3.1數據挖掘概述7.5多樣性習題7.4結合策略of6476高級大數據人才培養叢書之一，大數據挖掘技術與應用7.6實戰案例of64777.2Bagging算法與隨機森林算法第七章集成學習Bagging算法是指通過引導程序使用一個訓練集的多個版本，即放回抽樣，每一個數據集都來訓練一個不同的模型，對訓練模型通過整合輸出形成一個最終的預測結果。1.基本概念

Bagging算法（引導聚集算法），又稱為裝袋算法。Bagging算法可與其他分類、回歸算法結合，在提高其在確率、穩定性的同時，通過降低結果的方差，避免過擬合的發生。7.2.1Bagging算法基本思想of64787.2Bagging算法與隨機森林算法第七章集成學習2.數據樣本

對于M個樣本的數據集，按照有放回抽樣方式（BootstrapSample）隨機抽取m（m≤M）個樣本，經過N次抽樣形成不同的數據集，每個數據集按照學習算法構建基學習器，最后按照結合策略形成強學習器，這種強學習器就是將基學習器的學習結果組合形成最終學習結果。

有放回抽樣方式就是從我們的訓練集中采集固定個數的樣本，但是每采集一個樣本后，都將樣本放回。也就是說，之前采集到的樣本在放回后有可能繼續被采集到。對于Bagging算法，一般會隨機采集和訓練集樣本數M一樣個數的樣本m，即設定m=M。這樣得到的采樣集和訓練集樣本的個數相同，但是樣本內容不同。如果我們對有m個樣本訓練集做N次的隨機采樣，則由于隨機性，N個采樣集各不相同。

7.2.1Bagging算法基本思想of64797.2Bagging算法與隨機森林算法第七章集成學習2.數據集劃分

對于M個樣本數據集，會存在36.8%的樣本不會被抽取到，這類數據可以作為包外數據（OutOfBag），可用作驗證集對泛化性能進行“包外估計”。7.2.1Bagging算法基本思想of64807.2Bagging算法與隨機森林算法第七章集成學習被抽到的訓練數據包外數據數據集36.8%1.算法流程

對于M個樣本數據集，會存在36.8%的樣本不會被抽取到，這類數據可以作為包外數據（OutOfBag），可用作驗證集對泛化性能進行“包外估計”。7.2.2Bagging算法流程of64817.2Bagging算法與隨機森林算法第七章集成學習2.算法特點

Bagging算法具有控制方差、性能高效、應用廣泛等優點，通過多個基學習器在樣本抽樣上的多樣性，實現集成上的方差變小，提升泛化能力；通過并行對訓練數據集進行抽樣構建基學習器，實現基學習器的并行構建，提升集成學習模型的構建效率，減少構建消耗時間；Bagging算法中多個基學習器學習結果進行有效組合，可直接適用于分類問題和回歸預測，具有廣泛應用場景。從“偏差-方差分解”的角度看，Bagging算法主要關注降低方差，因此它在不剪枝決策樹、神經網絡等易受樣本擾動的學習器上效用更為明顯。7.2.2Bagging算法流程of64827.2Bagging算法與隨機森林算法第七章集成學習1.算法概述

隨機森林（RandomForest，RF）算法是Bagging算法的一個擴展變體，是在以決策樹為基學習器構建Bagging集成的基礎上，在決策樹的訓練過程中進一步引入了隨機屬性選擇。7.2.3隨機森林算法of64837.2Bagging算法與隨機森林算法第七章集成學習2.算法特點

隨機森林算法結構簡單、容易實現、計算開銷小，并且在很多現實任務中展現出強大的性能，被譽為“代表集成學習技術水平的方法”。可以看出，隨機森林算法對Bagging集成學習只做了小改動，但是與Bagging算法中基學習器的“多樣性”僅通過樣本擾動（通過對初始訓練集采樣）而來不同，隨機森林算法中基學習器的多樣性不僅來自樣本擾動，還來自屬性擾動，這就使得最終集成的泛化性能可通過個體學習器之間差異度的增加而進一步提升。隨機森林算法可以處理高維數據，模型的泛化能力較強，訓練模型時速度快、并行化，可以處理不平衡數據，有包外數據（OOB）作為驗證數據集，對缺失值、異常值不敏感，模型訓練結果準確度高，具有Bagging算法能夠收斂于更小的泛化誤差等優點。當數據噪聲比較大時，隨機森林算法會產生過擬合現象。7.2.3隨機森林算法of64847.2Bagging算法與隨機森林算法第七章集成學習7.3Boosting算法第七章集成學習7.1集成學習的概念7.2Bagging算法與隨機森林算法3.1數據挖掘概述7.5多樣性習題7.4結合策略of6485高級大數據人才培養叢書之一，大數據挖掘技術與應用7.6實戰案例

Boosting算法也是一種基于數據集重抽樣算法，與Bagging算法主要區別在于，需要動態調整訓練樣本中各數據權重，每一次迭代增加不能正確學習樣本權重，相對地降低了能被正確學習的樣本權重，從而提升在整個訓練樣本數據集上的學習正確率。of64867.3Boosting算法第七章集成學習1.算法流程

Boosting算法第一次構建基學習器時給每一個訓練數據樣本賦予動態權重，加強分類錯誤樣本權重。在下一次，基學習器采用新的樣本權重進行隨機抽樣構建新的基學習器并以此類推構建多個基學習器，直到遞進生成的基學習器精度不再明顯提升或滿足精度需求，最后這多個基學習器形成一個精度較高的強學習器。7.3.1Boosting算法流程of64877.3Boosting算法第七章集成學習1.算法流程Boosting算法最典型的是Adaptive

Boosting算法，簡稱AdaBoost算法，其基本流程描述如下。強學習器。7.3.1Boosting算法流程of64887.3Boosting算法第七章集成學習2.算法特點為了提升集成模型的差異化，Boosting算法是一個逐步遞進的方法，每一個學習器都是前一個的通過調整樣本權重的改進模型，不存在兩個相同的基學習器。從“偏差-方差分解”的角度看，Boosting算法主要提升基學習器的準確率，降低偏差，因此，Boosting算法能基于泛化性能相當弱的學習器構建出很強的集成。Boosting算法問題在于更多關注不能正確分類樣本數據，對于邊界樣本會導致權重失衡，產生“退化問題”。7.3.1Boosting算法流程of64897.3Boosting算法第七章集成學習1．BoostingTree算法

BoostingTree算法是以分類樹或回歸樹為基本分類器的提升方法。該方法實際采用加法模型（基函數的線性組合）與前向分步算法。對分類問題決策樹是二叉分類樹，對回歸問題決策樹是二叉回歸樹。

對于二分類問題，提升樹分類算法只需將AdaBoost算法中的基本分類器限制為二類分類樹即可，這時的提升樹分類算法可以說是AdaBoost算法的特殊情況。7.3.2Boosting系列算法of64907.3Boosting算法第七章集成學習2．GBDT算法

GBDT（GradientBoostingDecisionTree）又叫MART（MultipleAdditiveRegressionTree），是一種迭代的決策樹算法，該算法由多棵決策樹組成，所有樹的預測結果集成后得到結論，是Boosting系列算法之一。它在被提出之初就和支持向量機一起被認為是泛化能力較強的算法。

作為GBDT基學習器的決策樹是回歸樹，而不是分類樹，GBDT用來做回歸預測，調整后也可以用于分類。

GBDT的核心思想在于，每一棵決策樹學的是之前所有決策樹結論和的殘差，這個殘差就是一個加預測值后能得真實值的累加量。7.3.2Boosting系列算法of64917.3Boosting算法第七章集成學習3．XGBoost算法

XGBoost（eXtremeGradientBoosting）是經過優化的分布式梯度提升庫，旨在高效、靈活且可移植。XGBoost是大規模并行BoostingTree的工具，它是目前最快最好的開源BoostingTree工具包，比常見的工具包快10倍以上。

XGBoost算法和GBDT算法兩者都是Boosting算法，除工程實現、解決問題上的一些差異外，最大的不同就是目標函數的定義。XGBoost算法的改進是在求解損失函數極值時使用了牛頓法，將損失函數泰勒展開到二階，另外損失函數中加入了正則化項。訓練時的目標函數由兩部分構成，第一部分為梯度提升算法損失，第二部分為正則化項。7.3.2Boosting系列算法of64927.3Boosting算法第七章集成學習7.4結合策略第七章集成學習7.1集成學習的概念7.2Bagging算法與隨機森林算法7.5多樣性習題7.3Boosting算法of6493高級大數據人才培養叢書之一，大數據挖掘技術與應用7.6實戰案例

典型集成學習描述了如何通過訓練樣本數據得到基學習器，下面我們關注集成學習的檢驗階段，即如何將各基學習器的預測結果進行有效整合集成形成集成學習預測結果并進行檢驗。基學習器的整合方式可以分為3個層次，即決策層次輸出、排序層次輸出和度量層次輸出。基學習器結果集成屬于決策層次集成，一般包括兩大類集成方法，即投票方法（Voting）和疊加方法（Stacking）。of64947.4結合策略第七章集成學習

投票方法是指對各基學習器的分類結果按照某種原則進行投票表決，得到集成預測分類結果。投票方法可分為普通投票和貝葉斯投票兩種。普通投票方法可以分為均等投票和賦權投票兩類，賦權投票是給投票專家賦予不同權重，均等投票則是以相同權重進行投票，可以將均等投票視作各專家投票權重的特殊情況。根據應用背景需求，按投票原則又可以分為一票否決、一致表決、大數原則和閥值表決等。對于回歸問題，可以通過平均值、加權求和、中位數、最大數等方式進行整合。貝葉斯投票是根據每個基學習器的歷史分類表現通過貝葉斯定理賦予不同的權重，根據各基學習器的權重進行投票。由于不能覆蓋各基學習器的所有樣本空間，且不能正確給出各基學習器的先驗概率，貝葉斯投票的效能不及普通投票的效能。7.4.1投票方法Votingof64957.4結合策略第七章集成學習

Stacking算法是1992年Worlpert提出的StackedGeneralization的學習模型，對基學習器的學習結果進行再集成得到集成模型預測結果。往往采用Leave-One-Out的交叉驗證（CrossValidation，CV）方法訓練基學習器，將各基學習器的訓練結果和原數據集D中的樣本x綜合起來，作為強學習器的輸入訓練實例，訓練學習得到最終預測結果。7.4.2疊加方法Stackingof64967.4結合策略第七章集成學習7.5多樣性第七章集成學習7.1集成學習的概念7.2Bagging算法與隨機森林算法7.4結合策略習題7.3Boosting算法of6497高級大數據人才培養叢書之一，大數據挖掘技術與應用7.6實戰案例

基學習器的準確性和相互之間的多樣性，對于集成學習的泛化精度（泛化能力和預測精度）具有重要意義。基學習器的準確性高于隨機猜想（精度高于0.5）即可通過集成得到較好預測效果，如何度量和構建基學習器之間的多樣性則是提升集成學習泛化能力的重要途徑和方式。of6498