關聯規則課程目錄5.1.關聯規則綜述

5.1.1關聯規則的基本概念

5.1.2關聯規則提出的背景

5.1.3關聯規則的原理

5.1.4關聯規則的應用場景

5.1.5關聯規則的分類5.2.關聯規則挖掘常用算法5.3.關聯規則實驗5.4.本章小結5.5本章習題關聯規則的基本概念數據集合關聯分析全部或者某些元素之間的關聯關系輸入輸出關聯分析用于描述多個變量之間的關聯，如果兩個或者多個變量之間存在一定的關聯，那么其中一個變量的狀態就能通過其他變量進行預測。關聯規則基本概念自然界中某種事物發生時其他事物也會發生，則這種聯系稱之為關聯。反映事件之間依賴或關聯的知識稱為關聯型知識（又稱依賴關系）。關聯分析的目的是找出數據集合中隱藏的關聯網，是離散變量因果分析的基礎。牛奶和面包應該分別放在哪兒？才能使銷售利潤最大？市場組合分析套裝產品分析目錄設計交叉銷售關聯規則的基本概念課程目錄5.1.關聯規則綜述

5.1.1關聯規則的基本概念

5.1.2關聯規則提出的背景

5.1.3關聯規則的原理

5.1.4關聯規則的應用場景

5.1.5關聯規則的分類5.2.關聯規則挖掘常用算法5.3.關聯規則實驗5.4.本章小結5.5本章習題關聯規則提出的背景1993年，Agrawal等人首先提出關聯規則概念，同時給出了相應的挖掘算法AIS，但是性能較差。1994年，他們建立了項目集格空間理論，并依據上述兩個定理，提出了著名的Apriori算法，至今Apriori仍然作為關聯規則挖掘的經典算法被廣泛討論，以后諸多的研究人員對關聯規則的挖掘問題進行了大量的研究。關聯規則挖掘在數據挖掘中是一個重要的課題，最近幾年已被業界所廣泛研究。關聯規則最初提出的動機是針對購物籃分析(MarketBasketAnalysis)問題提出的。假設分店經理想更多的了解顧客的購物習慣。特別是，想知道哪些商品顧客可能會在一次購物時同時購買？為回答該問題，可以對商店的顧客事物零售數量進行購物籃分析。該過程通過發現顧客放入“購物籃”中的不同商品之間的關聯，分析顧客的購物習慣。這種關聯的發現可以幫助零售商了解哪些商品頻繁的被顧客同時購買，從而幫助他們開發更好的營銷策略。課程目錄5.1.關聯規則綜述

5.1.1關聯規則的基本概念

5.1.2關聯規則提出的背景

5.1.3關聯規則的原理

5.1.4關聯規則的應用場景

5.1.5關聯規則的分類5.2.關聯規則挖掘常用算法5.3.關聯規則實驗5.4.本章小結5.5本章習題支持度與置信度設關聯規則：A=>B，{A}或{B}為項集，項集{A}可以認為為前因，項集{B}可以認為為后果。支持度表示的是兩個事件同時發生的概率，也就是表示同時包含A、B事務占總事務的百分比。置信度是預測性指標，是在前因發生的條件下，后果發生的概率，表示同時發生A、B事務的概率占事務A發生概率的百分比。支持度為對稱指標，即{A,B}的支持度與{B,A}的支持度都

一樣，而置信度為非對稱指標，二者不同，即置信度(A=>B)與置信度(B=>A)不一樣。支持度與置信度案例茶和咖啡的案例某調研機構，調查統計了1000個用戶的喝茶及喝咖啡的情況，1000個調研對象中，喝茶的用戶有200人，喝咖啡的用戶有800人，喝茶且喝咖啡的用戶有150人，不喝茶也不喝咖啡的用戶有150人，基于此些數據，查看{喝茶}->{喝咖啡}的支持度、置信度。喝咖啡（A）不喝咖啡（－A）合計喝茶（B）15050200不喝茶（－B）650150800合計8002001000支持度（{喝茶}->{喝咖啡}）＝150/1000=15%；置信度（{喝茶}->{喝咖啡}）＝150/200=75%；即一個人喝茶那么他75%可能喝咖啡課程目錄5.1.關聯規則綜述

5.1.1關聯規則的基本概念

5.1.2關聯規則提出的背景

5.1.3關聯規則的原理

5.1.4關聯規則的應用場景

5.1.5關聯規則的分類5.2.關聯規則挖掘常用算法5.3.關聯規則實驗5.4.本章小結5.5本章習題關聯規則的應用場景關聯規則應用場景類別價格預測類氣象預測類精準營銷類內容推薦類成因分析類其他類別穿衣搭配推薦地點推薦系統基于興趣的實時新聞推薦電子商務搭配購買推薦交通事故成因分析互聯網情緒指標和生豬價格的關聯關系挖掘和預測依據用戶軌跡的商戶精準營銷銀行金融客戶交叉銷售分析氣象關聯分析銀行營銷方案推薦課程目錄5.1.關聯規則綜述

5.1.1關聯規則的基本概念

5.1.2關聯規則提出的背景

5.1.3關聯規則的原理

5.1.4關聯規則的應用場景

5.1.5關聯規則的分類5.2.關聯規則挖掘常用算法5.3.關聯規則實驗5.4.本章小結5.5本章習題關聯規則的分類關聯規則類型可分為下列幾種類型：基于規則中處理的變量的類別布爾型：學歷=“本科”=>職業=“軟件開發工程師”數值型：學歷=“本科”=>平均收入=8000基于規則中數據的抽象層次單層關聯規則：蘋果筆記本電腦=>XGIMI投影儀多層關聯規則：筆記本電腦=>XGIMI投影儀基于規則中涉及到的數據的維數單維：啤酒=>尿布多維：性別=“女”=>職業=“秘書”課程目錄5.1.關聯規則綜述5.2.關聯規則挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.關聯規則實驗5.4.本章小結5.5本章習題Apriori算法概述Apriori算法是一種以概率為基礎的具有影響的挖掘布爾型關聯規則頻繁項集的算法。其利用循序漸進的方式，找出數據庫中項目的關系，以形成規則。核心思想：項集的反單調性：如果一個項集是非頻繁的，那么它的超集（superset）也一定是非頻繁的。所謂頻繁項集是指發生頻率超過最小支持度的項集。Apriori算法的適用場景Apriori是一種‘先驗’算法，通過該算法我們可以對數據集做關聯分析，也就是可以在大規模的數據中尋找有趣關系的任務。這些關系可以有兩種形式，分別是頻繁項集和關聯規則。頻繁項集：經常出現在一塊的物品的集合；關聯規則：暗示兩種物品之間可能存在很強的關系。從這些數據中能發現它們彼此之間有什么關系呢？Apriori算法原理及步驟Apriori的原理：如果某個項集是頻繁項集，那么它所有的子集也是頻繁的。即如果{0,1}是頻繁的，那么{0},{1}也一定是頻繁的。φ01230102031213230120130231230123230231230123非頻繁圖中給出了所有可能的項集，其中非頻繁項集用灰色表示。由于集合{2,3}是非頻繁的，因此{0,2,3}、{1,2,3}和{0,1,2,3}也是非頻繁的，它們的支持度根本不需要計算。頻繁項集的主要步驟：首先會生成所有單個物品的項集列表；

掃描交易記錄來查看哪些項集滿足最小支持度要求，那些不滿足最小支持度的集合會被去掉；

對剩下的集合進行組合以生成包含兩個元素的項集；

接下來重新掃描交易記錄，去掉不滿足最小支持度的項集，重復進行直到所有項集都被去掉。Apriori算法原理及步驟Apriori關聯算法計算步驟計算步驟12345首先描述數據庫，找出項數為1的頻繁項集（即頻繁的單項集），此時k=1從k頻繁項集中生成k+1候選頻繁項集掃描數據集，計算出每個候選頻繁項集的支持度根據最小支持度要求，從中篩選出k+1頻繁項集直到k+1達到用戶指定的最大項數，或者k+1頻繁項集為空迭代進行如果指定的最大項數為Kmax，則Apriori算法最多掃描數據集Kmax+1次Apriori算法python實現python實現算法示例：發現頻繁項集找出關聯規則阿里云DSW-Notebook建模環境的Apriori算法實現阿里云提供DSW-Notebook建模的環境，在這個環境里可以自己寫python代碼來實現Apriori算法。課程目錄5.1.關聯規則綜述5.2.關聯規則挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.關聯規則實驗5.4.本章小結5.5本章習題Partition算法概述雖然Apriori算法自身已經進行了一定的優化，但是在實際的應用中，還是存在不令人滿意的地方，于是人們相繼提出了一些優化的方法。Partition算法——一種基于劃分的方法Partition算法本質上是基于頻集算法的一種優化方法Partition算法背景Apriori關聯算法的特點對數據庫的掃描次數過多

每次計算項集的支持度時，都對數據庫中的全部記錄進行了一遍掃描比較，這種掃描比較會大大增加計算機系統的I/O開銷會產生大量的中間項集

在每一步產生侯選項目集時循環產生的組合過多，沒有排除不應該參與組合的元素Partition算法原理及步驟幾個基本概念項集：“屬性-值”對的集合，一般情況下在實際操作中會省略屬性。候選項集：用來獲取頻繁項集的候選項集，候選項集中滿足支持度條件的項集保留，不滿足條件的舍棄。頻繁項集：在所有訓練元組中同時出現的次數超過人工定義的閾值的項集稱為頻繁項集。極大頻繁項集：不存在包含當前頻繁項集的頻繁超集，則當前頻繁項集就是極大頻繁項集。支持度：項集在所有訓練元組中同時出現的次數。置信度：形如A->B，置信度為60%表示60%的A出現的同時也出現B。k項集：項集中的每個項有k個“屬性-值”對的組合。Partition算法原理及步驟Partition算法的基本步驟（1）ACB先把數據庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊并對它生成所有的頻集。對數據庫從邏輯上進行劃分例如劃分為塊A，生成塊Ａ所有的頻集例如劃分為塊B，生成塊Ｂ所有的頻集例如劃分為塊C，生成塊Ｃ所有的頻集Partition算法原理及步驟Partition算法的基本步驟（2）ACB對數據庫從邏輯上進行劃分把產生的頻集合并，用來生成所有可能的頻集塊A的頻集塊Ｂ的頻集塊Ｃ的頻集……所有可能的頻集……Partition算法原理及步驟Partition算法的基本步驟（3）ACB對數據庫從邏輯上進行劃分所有可能的頻集……最后計算這些項集的支持度計算這些項集的支持度課程目錄5.1.關聯規則綜述5.2.關聯規則挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.關聯規則實驗5.4.本章小結5.5本章習題DHP算法概述

DHP算法是Apriori算法的一種改進算法，其中使用的哈希算法選取很關鍵，一種簡單的處理方法是將哈希表的大小設置為候選項集的數量，即每個候選項集都唯一對應一個哈希表地址，可以直接根據統計數判斷候選項集是否為頻繁項集。DHP算法背景盡管Partition算法相對Apriori有一定優化，但也存在一些不足：（1）由于各區段中產生頻繁項集,并不表示在整個數據庫中亦為頻繁項集,因此會產生過多的頻繁項集,導致第二次掃描數據庫I/O次數頻繁效率不佳。（2）為了減少在不同區段中重復產生頻繁項集,而且為了能利用估計的方式提早結束挖掘,在系統做挖掘前必須先將數據庫作排序。（3）由于分段對各區段數據庫做挖掘,因此計算量會比Apriori算法更大。DHP算法原理及步驟算法設計思路

DHP算法描述算法描述1)D1=D;2)Addonecolumi_counttoD13)foreachtransactionst∈D14)t．i_count=countoft5)L1=search_frequent_l－itemset(D1);6)D2=apriori_d(D1);7)useDHPtogetL28)D3=apriori_d(D2);9)for(k=3;Lk－1≠φ;k++)10){Ck=new_apriori_gen(Dk);11)Lk={c∈Ck|c．countminsup;}12)Dk－1=apriori_d(Dk);}13)Answer=Uk;LkProcedureapriori_d(Dk)1)foreachtransactionst∈Dk2){ift．i_count＜kthen3){deletetfromDk}4)foreacht．item<>Lk5){deletet．itemfromt;6)t．i_count－－;}}7)returnDk;Procedurenew_apriori_gen(Dk)1)Ck=Φ2)foreachtransactionst∈Dk{3)forallksubsetscoft{4)ifc∈Ckthenc．count++;5)elsethen6){addctoCk;7)c．count=1;}}8)returnCk;}DHP算法特點優化了Apriori算法的性能瓶頸問題。

減少事務數據庫的內容。減少數據庫掃描，降低對磁盤的1/0訪問。DHP算法減少了處理的候選集，是以附加一個Hash表的計算和數據庫表的存儲空間(為了進行數據庫的修剪)為代價，換取執行時間的快速。生成候選集的個數，從而提高了查找每個事務中候選項目集的速度通過剪技技術減少整個數據庫中事務的數量(即行數)和每個事務項中的個數(即每行包含的項目數量)，顯著減少后面迭代計算量。候選集小可使更多內容在內存中進行，同時可以節省某些數據庫掃描，通過推遲頻繁項目集的確定減少磁盤1/0訪問。課程目錄5.1.關聯規則綜述5.2.關聯規則挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.關聯規則實驗5.4.本章小結5.5本章習題MSApriori算法概述MsApriori算法是另一種優化辦法。它的基本思想是設置多個支持度值，每個種類項都有一個最小支持度閾值，然后一個頻繁項的最小支持度閾值取其中項集元素中的最小支持度值作為該項集的最小支持度值。這樣，如果一個頻繁項中出現了稀有項集，則這個項集的最小支持度值就會被拉低，如果又有某個項都是出現頻率很高的項構成的話，則支持度閾值又會被拉高。當mis最小支持度閾值數組的個數只有1個的時候MSApriori算法就退化成了Apriori算法了。課程目錄5.1.關聯規則綜述5.2.關聯規則挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.關聯規則實驗5.4.本章小結5.5本章習題FP-Growth算法概述FP-growth算法不產生候選集而直接生成頻繁集的頻繁模式增長算法，該算法采用分而治之的策略：第一次掃描數據庫，把數據庫中的頻繁項目集壓縮到一棵頻繁模式樹中，形成投影數據庫，同時保留其中的關聯信息；第二次掃描數據庫，將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關，然后再對這些條件庫分別進行挖掘。FP-Growth算法原理及步驟FP樹的構建交易編號所有購物項（排序后的）頻繁項100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p其中，最小支持度閾值為3FP-tree的構建1.f,c,a,m,p2.f,c,a,b,m3.f,b4.c,b,p5.f,c,a,m,pnull{}c:1

b:1

p:1f:3b:1f:1c:1a:1m:1p:1f:4c:3a:3m:2p:2f:2c:2a:2b:1m:1項頭表購物項

頻率

f 4c 4a 3b 3m 3p 3FP-Growth算法原理及步驟創建樹的根節點，用nul