大數據挖掘導論與案例課件-第6章 關聯(lián)分析概念與方法

第1章緒論第2章數據分析與可視化技術第3章認識數據第4章數據預處理第5章分類概念與方法第6章關聯(lián)分析概念與方法第7章聚類分析概念與方法第8章大數據挖掘關鍵技術第9章案例分析第6章關聯(lián)分析概念與方法大數據挖掘導論與案例學習目標/Target掌握Apriori算法挖掘關聯(lián)規(guī)則的基本步驟,，了解Apriori算法的優(yōu)缺點，了解提升算法效率的方法。理解FP樹挖掘頻繁項集的原理,

熟悉挖掘頻繁項集的其他方法。了解關聯(lián)模式評估的指標,

熟悉各指標的應用場景。掌握關聯(lián)分析的基本概念，理解頻繁項集和關聯(lián)規(guī)則的內容，掌握先驗原理。引言/Introduction關聯(lián)分析（associationanalysis）從大量數據中發(fā)現項集之間有趣的聯(lián)系，被用于發(fā)現隱藏在大型數據集中的有意義的關聯(lián)。通常將所發(fā)現的聯(lián)系表示為關聯(lián)規(guī)則（associationrule）或頻繁項集（frequentitemset）。目錄/Contents01基本概念02關聯(lián)分析的方法03關聯(lián)模式評估基本概念6.16.1.1購物籃分析關聯(lián)分析的目的是發(fā)現被顧客放入購物籃中的不同商品之間的聯(lián)系，從而分析顧客的購買習慣，了解哪些商品經常被顧客連帶購買，為制定方便顧客選取的貨架擺放方案和合理的營銷策略提供依據，也被稱為購物籃分析。完整的購物籃數據至少包含兩方面的信息：一方面是顧客的購買行為序號，一個顧客可能會發(fā)生多次購買行為，每次購買行為均被記錄下來，這個序號也就是超市或者商店的交易流水號；另一方面是顧客在每次購物過程中交易的商品列表，此處商品列表只涉及顧客購買的不同商品的名稱。6.1.1購物籃分析購物籃數據涉及關聯(lián)分析的兩個基本術語：事務（transaction）和項集（itemset）。事務是關聯(lián)分析的研究對象，一個事務包含一個唯一標識TID和對應顧客購買的商品的集合。項目（item）是事務中的單個對象。一次交易中的商品通常是若干個項目的集合，叫作項集。購物籃分析的目的是找到所有購物籃中不同商品之間的關聯(lián)關系，從而了解哪些商品頻繁地被顧客同時購買，幫助零售商制定合理的營銷策略。6.1.1購物籃分析在對購物籃數據進行關聯(lián)分析時，需要處理兩個關鍵問題：第一，計算復雜度問題。從大型事務數據集中發(fā)現有意義的規(guī)則在計算上要付出很高的代價；第二，規(guī)則的篩選問題。所發(fā)現的某些規(guī)則可能是虛假的或不令人感興趣的，因為它們可能是偶然發(fā)生的或者是已經被研究者所熟知的。除了購物籃分析外，關聯(lián)分析也被應用于公共管理、生物信息學、醫(yī)療診斷、網頁挖掘和推薦系統(tǒng)等領域。例如，關聯(lián)分析可以幫助公安機關從已有的案件中找到各屬性之間的隱含關系，發(fā)現其中的犯罪行為規(guī)律，為新案件的偵破提供線索；在移動通信行業(yè)，關聯(lián)分析可以幫助運營商發(fā)現不同業(yè)務之間的關聯(lián)關系，從而推進新業(yè)務的發(fā)展；關聯(lián)分析也可以用來分析保險行業(yè)的客戶數據，找到各險種可能被購買的人群特征，進而進行精準營銷。6.1.2頻繁項集和關聯(lián)規(guī)則

6.1.2頻繁項集和關聯(lián)規(guī)則

6.1.2頻繁項集和關聯(lián)規(guī)則

6.1.2頻繁項集和關聯(lián)規(guī)則實際應用中的關聯(lián)規(guī)則有許多類型，可以根據不同的標準對關聯(lián)規(guī)則進行分類。根據處理的數據類型，關聯(lián)規(guī)則可以分為布爾關聯(lián)規(guī)則和量化關聯(lián)規(guī)則。布爾型關聯(lián)規(guī)則是指處理的數據類型都是離散屬性或分類屬性，量化關聯(lián)規(guī)則則是指處理的數據類型包含連續(xù)屬性。根據處理的數據維度，關聯(lián)規(guī)則可以分為單維關聯(lián)規(guī)則和多維關聯(lián)規(guī)則。單維關聯(lián)規(guī)則通常從事務數據中挖掘，涉及到數據的只有一個維度，處理的是單個維內的關系。根據數據的抽象層次，關聯(lián)規(guī)則可以分為單層關聯(lián)規(guī)則和多層關聯(lián)規(guī)則。在單層關聯(lián)規(guī)則中，沒有考慮現實數據的多層次性。多層關聯(lián)規(guī)則是指在規(guī)則挖掘中，對數據的多層性進行了充分考慮。關聯(lián)分析的方法6.2

6.2關聯(lián)分析的方法6.2.1先驗原理

6.2.1先驗原理即，一旦發(fā)現一個非頻繁項集，那么包含該項集的所有超集都可以被剪枝，這樣的方法被稱為基于支持度的剪枝（support-basedpruning）?；谥С侄鹊募糁σ蕾囉谥С侄榷攘康男再|，即一個項集的支持度決不會超過它的子集的支持度，這個性質也被稱為支持度度量的反單調性（anti-monotone）。任何具有反單調性的度量都能夠直接結合到挖掘算法中，對候選項集的指數搜索空間有效地進行剪枝，以降低生成頻繁項集的計算代價。6.2.2Apriori算法產生頻繁項集Apriori算法是關聯(lián)規(guī)則挖掘的經典算法，它開創(chuàng)性地使用了基于支持度的剪枝技術來控制候選項集的指數增長。此處以下表所示的事務數據集為例，展示Apriori算法挖掘頻繁項集產生強關聯(lián)規(guī)則的基本過程。TID商品集合1牛奶，雞蛋，面包，薯片2雞蛋，爆米花，薯片，啤酒3雞蛋，面包，薯片4牛奶，雞蛋，面包，爆米花，薯片，啤酒5牛奶，面包，啤酒6雞蛋，面包，啤酒7牛奶，面包，薯片8牛奶，雞蛋，面包，黃油，薯片9牛奶，雞蛋，黃油，薯片6.2.2Apriori算法產生頻繁項集

項集支持度計數{爆米花}2{黃油}2{雞蛋}7{面包}7{牛奶}6{薯片}7{啤酒}46.2.2Apriori算法產生頻繁項集

項集支持度計數{雞蛋}7{面包}7{牛奶}6{薯片}7{啤酒}46.2.2Apriori算法產生頻繁項集

項集支持度計數{雞蛋，面包}5{雞蛋，薯片}6{雞蛋，啤酒}3{面包，薯片}5{面包，啤酒}3{牛奶，雞蛋}4{牛奶，面包}5{牛奶，薯片}5{牛奶，啤酒}2{薯片，啤酒}26.2.2Apriori算法產生頻繁項集

項集支持度計數{雞蛋，面包}5{雞蛋，薯片}6{雞蛋，啤酒}3{面包，薯片}5{面包，啤酒}3{牛奶，雞蛋}4{牛奶，面包}5{牛奶，薯片}56.2.2Apriori算法產生頻繁項集

6.2.2Apriori算法產生頻繁項集

項集支持度計數{雞蛋，面包，薯片}4{雞蛋，面包，啤酒}2{牛奶，雞蛋，面包}3{牛奶，雞蛋，薯片}4{牛奶，面包，薯片}46.2.2Apriori算法產生頻繁項集

項集支持度計數{雞蛋，面包，薯片}4{牛奶，雞蛋，面包}3{牛奶，雞蛋，薯片}4{牛奶，面包，薯片}46.2.2Apriori算法產生頻繁項集

項集支持度計數{牛奶，雞蛋，面包，薯片}36.2.2Apriori算法產生頻繁項集

6.2.2Apriori算法產生頻繁項集

項集支持度計數6.2.2Apriori算法產生頻繁項集

6.2.2Apriori算法產生頻繁項集

產生候選項集6.2.2Apriori算法產生頻繁項集

產生候選項集6.2.2Apriori算法產生頻繁項集

6.2.2Apriori算法產生頻繁項集候選項集剪枝

6.2.2Apriori算法產生頻繁項集計算支持度計數

6.2.2Apriori算法產生頻繁項集計算支持度計數

6.2.2Apriori算法產生頻繁項集計算支持度計數

6.2.2Apriori算法產生頻繁項集計算支持度計數

6.2.2Apriori算法產生頻繁項集計算支持度計數6.2.2Apriori算法產生頻繁項集計算支持度計數首先進行第一層散列，首項為1的項集，應該散列在左邊，而首項為2的散列在中間，首項為3的散列在右邊，如下圖所示：6.2.2Apriori算法產生頻繁項集計算支持度計數按同樣方式進行第二層散列，第1項為1的3-項集中第2項為2、3和5，其中第2項為2和5的3-項集被散列到第二層的中間結點，其第2項為3的3-項集被散列到第二層的右結點，結果如下圖。6.2.2Apriori算法產生頻繁項集計算支持度計數同理進行第三層散列，結果如右。圖中灰色葉子結點表示候選Hash樹上事務3-項集被散列的桶。6.2.2Apriori算法產生頻繁項集計算支持度計數

6.2.3Apriori算法生成關聯(lián)規(guī)則

6.2.3Apriori算法生成關聯(lián)規(guī)則

6.2.3Apriori算法生成關聯(lián)規(guī)則6.2.3Apriori算法生成關聯(lián)規(guī)則

基于置信度的剪枝6.2.3Apriori算法生成關聯(lián)規(guī)則基于置信度的剪枝6.2.4Apriori算法效率提升

事務壓縮技術

6.2.4Apriori算法效率提升

劃分技術6.2.4Apriori算法效率提升劃分技術6.2.4Apriori算法效率提升

選樣技術6.2.5模式增長算法頻繁項集的挖掘是關聯(lián)分析的關鍵步驟，Apriori算法通過多次掃描事務數據庫產生候選項集，再由候選項集得到頻繁項集。JiaweiHan等人在2000年提出了一種關聯(lián)分析方法——頻繁模式增長算法（FP-growthalgorithm），這是一種不通過產生候選項集來挖掘全部頻繁項集的方法。FP-growth算法采取分治的策略，首先將頻繁項集的數據庫壓縮為一棵頻繁模式樹（frequentpatterntree），簡稱FP樹，該樹仍保留項集的關聯(lián)信息。然后在FP樹中通過遞歸直接挖掘頻繁項集。即算法分為兩個步驟：第一步構建FP樹，第二步從FP樹中挖掘頻繁模式。6.2.5模式增長算法FP樹是輸入數據集的一種壓縮表示，它通過逐一讀取事務數據，并把每個事務映射到FP樹的一條路徑來構造。由于不同的事務中可能會存在部分相同的項目，因此FP樹的路徑會有部分重疊，重疊的部分越多，說明使用FP樹壓縮的效果越好。如果FP樹足夠小，可以把FP樹存放在內存中，從中直接提取頻繁項集，而不需要一遍遍地掃描事務數據庫，從而提高計算的效率。創(chuàng)建FP樹6.2.5模式增長算法創(chuàng)建FP樹TIDItems12345678910

6.2.5模式增長算法

創(chuàng)建FP樹6.2.5模式增長算法

創(chuàng)建FP樹6.2.5模式增長算法重復該過程，直到將所有的事務讀入完畢，每個事務都映射到了FP樹上的一條路徑中，如右圖（d）所示。創(chuàng)建FP樹6.2.5模式增長算法通過以上方法構造的FP樹具有以下幾個特點。（1）在FP樹中，事務通過共享前綴項得到了壓縮。如果數據集中所有事務的項目都相同，那么FP樹只包含一條結點路徑；如果數據集中每個事務中均不存在相同的項目，那么構造的FP樹的大小和原數據集的大小一樣。（2）FP樹的大小與項目按支持度計數的排序方式有關。當第一步事務中的項目按支持度的增序排列時，則根結點上的分支數目由2個增加到了5個，并且包含高支持度項目a和b的結點數目由3個增加到了12個，也就是說構造的FP樹顯得更加茂盛，如下圖所示。需要注意的是，按支持度計數降序排列并非總是能夠得到最小的樹。（3）FP樹中還包含了連接相同項目結點的指針列表。這些指針在圖中用虛線表示，有助于方便快速地訪問樹中的項目。創(chuàng)建FP樹6.2.5模式增長算法創(chuàng)建FP樹6.2.5模式增長算法

從FP樹中挖掘頻繁模式6.2.5模式增長算法從FP樹中挖掘頻繁模式6.2.5模式增長算法

從FP樹中挖掘頻繁模式6.2.5模式增長算法

從FP樹中挖掘頻繁模式6.2.5模式增長算法

從FP樹中挖掘頻繁模式6.2.5模式增長算法

從FP樹中挖掘頻繁模式6.2.5模式增長算法

從FP樹中挖掘頻繁模式6.2.5模式增長算法從FP樹中挖掘頻繁模式6.2.5模式增長算法

從FP樹中挖掘頻繁模式后綴頻繁項集edcba6.2.5模式增長算法FP-growth算法使用了事務數據集的壓縮表示有效地生成頻繁項集。需要注意的是，FP-growth算法只能用來發(fā)現頻繁項集，不能用來尋找關聯(lián)規(guī)則。與Apriori算法相比，FP-growth算法發(fā)現頻繁項集的效率較高，只需要對事務數據集進行兩次掃描，執(zhí)行速度快于Apriori算法。6.2.6使用垂直數據格式挖掘頻繁項集事務數據集的表示方法有很多，最常見的是列表表示方法，在實際運用中還會用到二元表格形式的矩陣表示方法，還有將數據庫壓縮為樹狀結構的表示方法等，與列表表示方法相對應的垂直數據結構表示方法也可用于表示事務數據集。列表表示法將一個事務數據集用兩列來表示，第一列是交易流水號，用來標識每一個事務，記為事務標識符TID；第二列是每個事務中交易的商品集合，記為TID中的項集，如下表1所示，也把這樣的表示方法稱為水平數據布局。將一個水平數據布局的事務數據集轉換為垂直數據布局，可以看作是將水平數據布局的數據集進行了一次轉置，記錄的是每個項目出現的事務集合，如下表2所示。6.2.6使用垂直數據格式挖掘頻繁項集ItemsTID集合a{1,4,5,6,7,8,9}b{1,2,5,7,8,10}c{2,3,4,5,8,9}d{2,4,5,9}e{3,9}TIDItems12345678910表1表26.2.6使用垂直數據格式挖掘頻繁項集下面使用垂直數據格式有效地挖掘頻繁項集。（1）掃描一次事務數據集，將水平數據格式的數據集轉換成垂直數據格式。（2）計算每個項目的TID集合的長度，即為該項目的支持度計數。設定支持度計數的閾值為3，將每個項目的支持度計數和支持度閾值進行對比，得到頻繁1-項集，如下表所示。ItemTID集合支持度計數是否頻繁1-項集a{1,4,5,6,7,8,9}7是b{1,2,5,7,8,10}6是c{2,3,4,5,8,9}6是d{2,4,5,9}4是e{3,9}2否6.2.6使用垂直數據格式挖掘頻繁項集（3）使用頻繁1-項集構造候選2-項集，通過項目TID集合的交集運算得到每個候選2-項集的TID集合，進而得到頻繁2-項集，如下表所示。ItemTID集合支持度計數是否頻繁2-項集{1,5,7,8}4是{4,5,8,9}4是{4,5,9}3是{2,5,8}3是{2,5}2否{2,4,5,9}4是6.2.6使用垂直數據格式挖掘頻繁項集

ItemTID集合支持度計數是否頻繁3-項集{5,8}2否{4,5,9}3是（5）由于（4）中只產生了一個頻繁3-項集，無法構造候選4-項集，算法結束。采用垂直數據格式挖掘頻繁項集，算法在執(zhí)行整個過程中只掃描了一次事務數據庫，比水平數據格式在時間效率上有一定的優(yōu)越性，節(jié)省了多次掃描數據庫的時間開銷。但是實際工作中TID集合可能很長，此時不僅需要大量存儲空間而且交集運算也需要大量的計算資源。因此使用垂直數據格式挖掘頻繁項集的方法仍然具有很大的改進空間。6.2.7頻繁項集的緊湊表示

6.2.7頻繁項集的緊湊表示如果某個項集的直接超集都不是頻繁項集，則稱該項集為極大頻繁項集（maximalfrequentitemset）。極大頻繁項集是一種十分有效的頻繁項集的緊湊表示。極大頻繁項集的任意一個子集都是頻繁的，即從一個極大頻繁項集中可以導出所有的頻繁項集，又由于極大頻繁項集的超集都不是頻繁的，所以極大頻繁項集是能完成這一任務的最小的項集。盡管極大頻繁項集能夠導出所有的頻繁項集，但是它無法提供其子集的支持度信息，這就需要再掃描一遍數據集來確定這些子集的支持度計數，此時能提供保持支持度信息的頻繁項集的最小表示是有用的。極大頻繁項集6.2.7頻繁項集的緊湊表示閉頻繁項集（closedfrequentitemset）提供了頻繁項集的一種最小表示，該表示不會丟失支持度信息。如果一個項集的直接超集的支持度計數都不等于該項集本身的支持度計數，則稱該項集為閉項集（closeditemset）。也就是說，如果一個項集不是閉的，那么至少存在一個它的直接超集，該超集的支持度計數和它本身的支持度計數相等。如果一個項集是閉項集，同時其支持度滿足支持度閾值，則稱該項集為閉頻繁項集。閉頻繁項集6.2.7頻繁項集的緊湊表示

閉頻繁項集6.2.7頻繁項集的緊湊表示閉頻繁項集使用極大頻繁項集和閉頻繁項集進行頻繁項集的緊湊表示可以減少頻繁項集中的冗余，降低算法計算的復雜度。需要注意的是，要使用極大頻繁項集和閉頻繁項集的緊湊表示，前提是能夠有效地從事務數據集中快速識別極大頻繁項集和閉頻繁項集。關聯(lián)模式評估6.36.3.1模式興趣度度量在商業(yè)數據集中挖掘關聯(lián)規(guī)則時，盡管有支持度閾值和置信度閾值的限制，但仍然會挖掘出大量的關聯(lián)規(guī)則，其中有很大一部分是商業(yè)決策者們不感興趣的，因為這些規(guī)則沒有實際的應用價值。因此，需要建立一組能被廣泛接受的評估關聯(lián)模式質量的標準來對關聯(lián)規(guī)則進行評價和篩選。目前認可度較高的關聯(lián)模式評估標準有以下兩種。第一種是通過統(tǒng)計論據建立的，被稱為客觀興趣度度量（objectiveinterestingnessmeasure）?？陀^興趣度度量是從數據中推導統(tǒng)計量，用統(tǒng)計量來判斷關聯(lián)模式是否有趣。這時，相互獨立的模式或者覆蓋少量事務的模式被認為是沒有意義的，可以排除。支持度和置信度都是客觀興趣度度量。6.3.1模式興趣度度量

6.3.1模式興趣度度量

支持度-置信度框架的局限性

6.3.1模式興趣度度量

支持度-置信度框架的局限性6.3.1模式興趣度度量支持度的缺點：由于支持度閾值是由主觀經驗人為設定，如果閾值過低，會產生大量的頻繁項集，增加算法的計算復雜度；如果閾值過高，會導致一些潛在的有意義的規(guī)則被刪除。例如，在商場的購物記錄中購買奢侈品的人數是比較少的，那么奢侈品的購買模式就有可能因為達不到支持度閾值而被過濾掉。置信度的缺點：計算置信度時并沒有考慮規(guī)則前后件的關系，當規(guī)則的前后件是兩個完全獨立的事件時，就有可能生成誤導性的規(guī)則。下面通過一個實例來說明。支持度-置信度框架的局限性6.3.1模式興趣度度量一個谷類早餐的零售商對一所學校學生每天早上所從事的活動進行了一次調查。該所學校共有5000名學生。數據表明：60%的學生（即3000名學生）打籃球，75%的學生（即3750名學生）吃該零售商售賣的谷類早餐，40%的學生（即2000名學生）既打籃球也吃這種谷類早餐。假設關聯(lián)規(guī)則挖掘的支持度閾值40%，置信度閾值為60%。得到相依表如下。實例

吃谷類早餐不吃谷類早餐打籃球200010003000不打籃球175025020003750125050006.3.1模式興趣度度量

支持度-置信度框架的局限性6.3.1模式興趣度度量

支持度-置信度框架的局限性6.3.1模式興趣度度量

提升度（lift）6.3.1模式興趣度度量

提升度（lift）6.3.1模式興趣度度量

提升度（lift）6.3.1模式興趣度度量

卡方度量（chi-squaremeasures）6.3.1模式興趣度度量卡方度量（chi-squaremeasures）

吃谷類早餐不吃谷類早餐打籃球2000（2250）1000（750）3000不打籃球1750（1500）250（500）20003750125050006.3.1模式興趣度度量

卡方度量（chi-squaremeasures）6.3.1模式興趣度度量

全置信度6.3.1模式興趣度度量

最大置信度

Kulczynski度量6.3.1模式興趣度度量

余弦度量6.3.2關聯(lián)模式評估度量比較

6.3.2關聯(lián)模式評估度量比較數據集提升度全置信度最大置信度Kulc余弦10000100010001000009.2690556.760.910.910.910.9110000100010001001.000.000.910.910.910.91100100010001000008.44670.010.090.090.090.0910001000100010000025.7524740.300.500.500.500.501000100100001000009.188172.830.090.910.500.291000101000001000001.97965.540.010.990.500.106.3.2關聯(lián)模式評估度量比較

6.3.2關聯(lián)模式評估度量比較

6.3.2關聯(lián)模式評估度量比較度量方法定義取值