“1+X”(中級)05-關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則課程目錄5.1.關(guān)聯(lián)規(guī)則綜述

5.1.1關(guān)聯(lián)規(guī)則的基本概念

5.1.2關(guān)聯(lián)規(guī)則提出的背景

5.1.3關(guān)聯(lián)規(guī)則的原理

5.1.4關(guān)聯(lián)規(guī)則的應用場景

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

5.1.1關(guān)聯(lián)規(guī)則的基本概念

5.1.2關(guān)聯(lián)規(guī)則提出的背景

5.1.3關(guān)聯(lián)規(guī)則的原理

5.1.4關(guān)聯(lián)規(guī)則的應用場景

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

5.1.1關(guān)聯(lián)規(guī)則的基本概念

5.1.2關(guān)聯(lián)規(guī)則提出的背景

5.1.3關(guān)聯(lián)規(guī)則的原理

5.1.4關(guān)聯(lián)規(guī)則的應用場景

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

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

5.1.1關(guān)聯(lián)規(guī)則的基本概念

5.1.2關(guān)聯(lián)規(guī)則提出的背景

5.1.3關(guān)聯(lián)規(guī)則的原理

5.1.4關(guān)聯(lián)規(guī)則的應用場景

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

5.1.1關(guān)聯(lián)規(guī)則的基本概念

5.1.2關(guān)聯(lián)規(guī)則提出的背景

5.1.3關(guān)聯(lián)規(guī)則的原理

5.1.4關(guān)聯(lián)規(guī)則的應用場景

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

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

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

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

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

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

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

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算法特點優(yōu)化了Apriori算法的性能瓶頸問題。

減少事務數(shù)據(jù)庫的內(nèi)容。減少數(shù)據(jù)庫掃描，降低對磁盤的1/0訪問。DHP算法減少了處理的候選集，是以附加一個Hash表的計算和數(shù)據(jù)庫表的存儲空間(為了進行數(shù)據(jù)庫的修剪)為代價，換取執(zhí)行時間的快速。生成候選集的個數(shù)，從而提高了查找每個事務中候選項目集的速度通過剪技技術(shù)減少整個數(shù)據(jù)庫中事務的數(shù)量(即行數(shù))和每個事務項中的個數(shù)(即每行包含的項目數(shù)量)，顯著減少后面迭代計算量。候選集小可使更多內(nèi)容在內(nèi)存中進行，同時可以節(jié)省某些數(shù)據(jù)庫掃描，通過推遲頻繁項目集的確定減少磁盤1/0訪問。課程目錄5.1.關(guān)聯(lián)規(guī)則綜述5.2.關(guān)聯(lián)規(guī)則挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.關(guān)聯(lián)規(guī)則實驗5.4.本章小結(jié)5.5本章習題MSApriori算法概述MsApriori算法是另一種優(yōu)化辦法。它的基本思想是設(shè)置多個支持度值，每個種類項都有一個最小支持度閾值，然后一個頻繁項的最小支持度閾值取其中項集元素中的最小支持度值作為該項集的最小支持度值。這樣，如果一個頻繁項中出現(xiàn)了稀有項集，則這個項集的最小支持度值就會被拉低，如果又有某個項都是出現(xiàn)頻率很高的項構(gòu)成的話，則支持度閾值又會被拉高。當mis最小支持度閾值數(shù)組的個數(shù)只有1個的時候MSApriori算法就退化成了Apriori算法了。課程目錄5.1.關(guān)聯(lián)規(guī)則綜述5.2.關(guān)聯(lián)規(guī)則挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.關(guān)聯(lián)規(guī)則實驗5.4.本章小結(jié)5.5本章習題FP-Growth算法概述FP-growth算法不產(chǎn)生候選集而直接生成頻繁集的頻繁模式增長算法，該算法采用分而治之的策略：第一次掃描數(shù)據(jù)庫，把數(shù)據(jù)庫中的頻繁項目集壓縮到一棵頻繁模式樹中，形成投影數(shù)據(jù)庫，同時保留其中的關(guān)聯(lián)信息；第二次掃描數(shù)據(jù)庫，將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關(guān)，然后再對這些條件庫分別進行挖掘。FP-Growth算法原理及步驟FP樹的構(gòu)建交易編號所有購物項（排序后的）頻繁項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的構(gòu)建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算法原理及步驟創(chuàng)建樹的根節(jié)點，用nul