數(shù)據(jù)挖掘教程：關聯(lián)規(guī)則

關聯(lián)

報告人：熊赟

內(nèi)容概要

基本概念

其他

Apriori算法

關聯(lián)規(guī)則分類FP-Growth算法第3章關聯(lián)

3.1基本概念3.2原理3.3核心算法3.4其他

自然界中某種事物發(fā)生時其他事物也會發(fā)生的這樣一種聯(lián)系稱之為關聯(lián)。反映事件之間依賴或關聯(lián)的知識稱為關聯(lián)型知識（又稱依賴關系）。(?)定義3.1：關聯(lián)是兩個或多個變量取值之間存在的一類重要的可被發(fā)現(xiàn)的某種規(guī)律性。關聯(lián)可分為簡單關聯(lián)、時序關聯(lián)、因果關聯(lián)。

基本概念

關聯(lián)分析目的是尋找給定數(shù)據(jù)記錄集中數(shù)據(jù)項之間隱藏的關聯(lián)關系，描述數(shù)據(jù)之間的密切度。關聯(lián)分析的結果常有兩種：

關聯(lián)規(guī)則和序列模式。關聯(lián)規(guī)則用于尋找在同一個事件中出現(xiàn)的不同項的相關性；序列模式與此類似，但它尋找的是事件之間時間上的相關性。

關聯(lián)分析

關聯(lián)規(guī)則發(fā)現(xiàn)的主要對象是交易型數(shù)據(jù)庫，一個交易一般由交易處理時間，一組顧客購買的物品，有時也有顧客標識號(如信用卡號)組成。定義3.2：關聯(lián)規(guī)則是描述在一個交易中物品之間同時出現(xiàn)的規(guī)律的知識模式，更確切的說，關聯(lián)規(guī)則是通過量化的數(shù)字描述物品X的出現(xiàn)對物品Y的出現(xiàn)有多大的影響。

關聯(lián)規(guī)則

以零售業(yè)為例，體育用品商場通過對銷售數(shù)據(jù)進行關聯(lián)分析通?？梢园l(fā)現(xiàn)這些數(shù)據(jù)中常常隱含形式如下的規(guī)律——“購買籃球的顧客中有70%的人同時購買籃球運動服，所有交易中有40%的人同時購買籃球和籃球運動服”等等。這些規(guī)律即關聯(lián)規(guī)則。

關聯(lián)規(guī)則定義3.3：關聯(lián)規(guī)則挖掘的交易數(shù)據(jù)集記為D（一般為交易數(shù)據(jù)庫），D＝｛T1，T2，…，Tk，…,Tn｝，Tk（k＝1,2,…，n）稱為交易，對應每一個交易有唯一的標識，記作TID。元素im（m＝1,2,…，p）稱為項。設I={i1，i2，…，im}是D中全體項組成的集合，且Tk

I。交易號（TID）

項集合（Itemsets）

T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3設X是一個I中項的集合，如果X

Tk，那么稱交易Tk包含項集X。若X,Y為項集，X

I,Y

I，并且X

Y=

，則形如X==>Y的表達式稱為關聯(lián)規(guī)則。

關聯(lián)規(guī)則形式化定義置信度支持度

關聯(lián)規(guī)則度量規(guī)則X

Y在交易數(shù)據(jù)集D中的置信度是對關聯(lián)規(guī)則準確度的衡量。度量關聯(lián)規(guī)則的強度。即在所有出現(xiàn)了X的活動中出現(xiàn)Y的頻率，即規(guī)則X

Y的必然性有多大。記為confidence(X

Y)。計算方法：包含X和Y的交易數(shù)與包含X的交易數(shù)之比：confidence(X

Y)=P(Y∣X)=|{T:X

Y

T，T

D}|/|{T:X

T，T

D}|×100%規(guī)則X

Y在交易數(shù)據(jù)集D中的支持度是對關聯(lián)規(guī)則重要性的衡量，反映關聯(lián)是否是普遍存在的規(guī)律，說明這條規(guī)則在所有交易中有多大的代表性。即在所有交易中X與Y同時出現(xiàn)的頻率記為：support(X

Y)。計算方法：交易數(shù)據(jù)集中同時包含X和Y的交易數(shù)與所有交易數(shù)之比：support(X

Y)=P(X∪Y)=|{T:X

Y

T，T

D}|/|D|×100%（其中|D|是交易數(shù)據(jù)集D中的所有交易數(shù)）最小置信度閾值最小支持度閾值同時滿足最小置信度閾值和最小支持度閾值的關聯(lián)規(guī)則為強關聯(lián)規(guī)則，是有意義有價值。

關聯(lián)規(guī)則度量

在給定一個交易數(shù)據(jù)集D，挖掘關聯(lián)規(guī)則問題就是產(chǎn)生支持度和置信度分別大于用戶給定的最小支持度閾值和最小置信度閾值的關聯(lián)規(guī)則。

關聯(lián)規(guī)則度量經(jīng)常使用的“支持度-可信度”的框架。這樣的結構有時會產(chǎn)生一些錯誤的結果。例：假設體育類用品零售商調查了10000名顧客在購買什么商品，得到的結果是6000名顧客購買籃球，7500名顧客購買足球，4000名顧客購買籃球、足球。設最小支持度為30%，最小置信度為60%，可得到如下的關聯(lián)規(guī)則：籃球足球（支持度＝40%，置信度為66%）

這條規(guī)則其實是錯誤的，因為購買足球的比例是75%，甚至大于66%。

關聯(lián)規(guī)則度量描述了對于關聯(lián)規(guī)則（X==>Y）在沒有任何條件影響時，Y在所有交易中出現(xiàn)的頻率有多大。即沒有X的作用下，Y本身的支持度。

期望可信度改善度描述X的出現(xiàn)對Y的出現(xiàn)影響多大，是置信度與期望可信度的比值。

P(Y|X)/P(Y)

關聯(lián)規(guī)則度量興趣度？(置信度－支持度)/Max{置信度，支持度}一條規(guī)則的興趣度大于0，實際利用價值越大；小于0則實際利用價值越小。名稱描述公式置信度X出現(xiàn)的前提下，Y出現(xiàn)的頻率P(Y|X)支持度X、Y同時出現(xiàn)的頻率

P(X∩Y)期望可信度

Y出現(xiàn)的頻率

P(Y)改善度

置信度對期望可信度的比值

P(Y|X)/P(Y)

關聯(lián)規(guī)則度量找出所有具有最小支持度的項集(頻繁項集)。用Apriori、FP-Growth等算法來找出頻繁項集。使用頻繁項集生成期望的關聯(lián)規(guī)則對于每一個頻繁項集l，找出其中所有的非空子集；然后，對于每一個這樣的子集a，如果support(l)與support(a)的比值大于最小可信度，則存在規(guī)則a==>(l-a)。挖掘交易數(shù)據(jù)庫D中所有關聯(lián)規(guī)則的問題可以被劃分為兩個子問題：找出頻繁項集－－Apriori算法

Apriori性質

Apriori算法基本思想交易號項集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3表1交易數(shù)據(jù)庫D

例：找出頻繁項集－－Apriori算法項集支持度計數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2項集支持度計數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2C1L1掃描D，對每個候選計數(shù)比較候選支持度計數(shù)與最小支持度計數(shù)找出頻繁1－項集的集合L1找出頻繁項集－－Apriori算法例：最小支持度閾值為2項集支持度計數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2項集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝L1C2由L1產(chǎn)生候選C2Lk-1用于產(chǎn)生候選Ck

找出頻繁項集－－Apriori算法連接&剪枝項集支持度計數(shù)｛I1，I2｝4｛I1，I3｝4｛I1，I4｝1｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2｛I3，I4｝0｛I3，I5｝1｛I4，I5｝0項集支持度計數(shù)｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2C2L2比較候選支持度計數(shù)與最小支持度計數(shù)掃描D，對每個候選計數(shù)項集支持度計數(shù)｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2L2項集｛I1，I2，I3｝｛I1，I2，I5｝由L2產(chǎn)生候選C3C3連接&剪枝連接：C3＝L2∞L2＝{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}∞{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}={{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}剪枝：{I1,I2,I3}的2-項子集是{I1,I2},{I1,I3}和{I2,I3}。{I1,I2,I3}的所有2-項子集都是L2的元素。因此，保留{I1,I2,I3}在C3中。{I2,I3,I5}的2-項子集是{I2,I3},{I2,I5}和{I3,I5}。{I3,I5}不是L2的元素，因而不是頻繁的。因此，由C3中刪除{I2,I3,I5}。剪枝后C3＝{{I1,I2,I3},{I1,I2,I5}}。

項集支持度計數(shù)｛I1，I2，I3｝2｛I1，I2，I5｝2C3掃描D，對每個候選計數(shù)比較候選支持度計數(shù)與最小支持度計數(shù)項集支持度計數(shù)｛I1，I2，I3｝2｛I1，I2，I5｝2L3對每個交易，使用subset函數(shù)找出交易中是候選的所有子集，并對每個這樣的候選累加計數(shù)，所有滿足最小支持度的候選形成頻繁項集L。

輸入：交易數(shù)據(jù)庫D；最小支持度閾值min_sup。輸出：D中的頻繁項集L。方法：(1)找頻繁項集1-項集;(2)apriori_gen(Lk-1,min_sup)函數(shù)做兩個動作：連接和剪枝。用于在第k-1次遍歷中生成的Lk-1生成Ck(3)由Ck生成Lk

Apriori算法詳述

子集函數(shù)Subset

？子集函數(shù)Subset用于確定在一個給定的交易t中包含了哪些Ck中的項。候選集Ck被存放在一棵hash樹中，hash樹中的結點分為兩類：一類包含一個項集列表(葉結點)，另一類包含一張hash表(內(nèi)部結點)。在內(nèi)部結點上，hash表中的每一個桶都指向另一個結點。假定hash樹的根結點的深度等于1，則一個深度為d的內(nèi)部結點指向深度為d＋1的結點。項集都存放在葉子結點，當需要添加一個項集c的時候，就從根結點出發(fā)直到葉子結點。在一個深度為d的內(nèi)部結點，對該項集的第d項應用hash函數(shù)來確定下一步遍歷的分支。所有的結點最初都被創(chuàng)建為葉子結點。當一個葉子結點的項集數(shù)目超出某一個閾值時，該結點將會轉化為一個內(nèi)部結點。從根結點開始，子集函數(shù)按照如下的方式找出包含在交易t中的所有的候選集。如果在葉子結點，找出該葉子結點中所有包含在交易t中的項集，并且為它們添加一個指向結果集的索引；如果通過散列第i項到達某個內(nèi)部結點，則散列交易t中第i項后的每一項，并且將這個過程遞歸地應用于相應的桶。對于根結點，則散列交易t中的每一項。子集函數(shù)能夠返回所需要的候選集的索引，對于任何交易t中包含的項集c，c的第一個項一定出現(xiàn)在t中。在根結點，通過散列交易t中的每一項，我們能夠確定只忽略那些不是從t中的某一項開始的項集。同樣的結論也適用于hash樹中位于其他層次的結點。由于在每一個項集中的項都經(jīng)過排序，如果我們通過散列項i到達當前的結點，則以后只需要考慮交易t中出現(xiàn)在項i后的項。

Apriori算法詳述（續(xù)）1.基于劃分的方法2.基于散列的方法3.基于采樣的方法4.交易壓縮方法

（不包含任何k項集的交易不可能包含k+1項集）

Apriori算法優(yōu)化D中交易將D劃分成n部分找出局部每一部分頻繁項集（1次掃描）結合局部頻繁項集形成候選項集第1遍在候選項集中找出全局頻繁項集（1次掃描）D中頻繁項集第2遍基于劃分的方法桶地址0123456桶記數(shù)2242244桶內(nèi)容{I1,I4}{I3,I5}{I1,I5}{I1,I5}{I2,I3}{I2,I3}{I2,I3}{I2,I3}{I2,I4}{I2,I4}{I2,I5}{I2,I5}{I1,I2}{I1,I2}{I1,I2}{I1,I2}{I1,I3}{I1,I3}{I1,I3}{I1,I3}基于散列技術壓縮候選k－項集Ck使用散列函數(shù)h(x,y)=(orderofx)*10+(orderofy))mod7創(chuàng)建散列表候選2項集的散列表步驟：a.

對于每個頻繁項集l，找出l的所有非空子集；b.對于l的每個非空子集a，如果

support_count(l)/support_count(a)≥min_conf，則輸出規(guī)則“a＝>（l－a）”。頻繁項集產(chǎn)生強關聯(lián)規(guī)則例：假定數(shù)據(jù)包含頻繁集l＝{I1,I2,I5}，L的非空子集有{I1,I2},{I1,I5},{I2,I5},{I1},{I2},和{I5}。可以由l產(chǎn)生的關聯(lián)規(guī)則：

I1

I2

I5，confidence＝2/4＝50%；

I1

I5

I2，confidence＝2/2＝100%；

I2

I5

I1，confidence＝2/2＝100%；

I1

I2

I5，confidence＝2/6＝33%；

I2

I1

I5，confidence＝2/7＝29%；

I5

I1

I2,confidence＝2/2＝100%；若最小置信度閾值為70%，則只有I1

I5

I2，I2

I5

I1，I5

I1

I2可輸出，是強關聯(lián)規(guī)則不需要生成大量候選項集的頻繁項集挖掘。算法采用分而治之的策略。頻繁模式增長（FP-Growth）算法例：最小支持度閾值為3交易編號所有購物項（排序后的）頻繁項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,pFP-Growth算法例null{}b:1f:3c:1b:1p:1f:1c:1m:1p:1a:1a:2b:1m:1f:2c:2a:3f:4c:3m:2p:21.f,c,a,m,p2.f,c,a,b,m3.f,b4.c,b,p5.f,c,a,m,pFP-Growth算法例生成的FP樹

FP-Growth算法例節(jié)點鏈性質對任意頻繁項ai，順著ai的節(jié)點鏈，從ai的頭開始，可以找到包含ai的所有頻繁模式。項條件模式庫條件FP樹p{(f:2,c:2,a:2,m:2),(c:1,b:1)}{(c:3)}|pm{(f:4,c:3,a:3,m:2),(f:4,c:3,a:3,b:1,m:1)}{(f:3,c:3,a:3)}|mb{(f:4,c:3,a:3,b:1),(f:4,b:1),(c:1,b:1)}φa{(f:3,c:3)}{(f:3,c:3)}|ac{(f:3)}{(f:3)}|cfφφ包含m的所有頻繁模式的集合有：{(m:3),(am:3),(cm:3),(fm:3),(cam:3),(fam:3),(fcam:3),(fcm:3)}。這表明對一個單獨路徑的FP樹進行挖掘時，可以通過輸出該路徑上所有項的組合來實現(xiàn)。FP-Growth算法例前綴路徑性質為計算路徑p上的一個節(jié)點ai的頻繁模式，只需要計算p中ai的前綴子樹，并且前綴子樹中的每個節(jié)點的頻繁數(shù)和節(jié)點ai相同。

FP-Growth算法詳述引理：片段增長假設α是DB中的一個項集，B是α的一個條件模式庫，β是B中的一個項集，那么，α∪β在DB中的支持度和β在B中的支持度是相同的。推論：模式增長假設α是DB中的一個頻繁項集，B是α的條件模式庫，β是B中的一個項集。當且僅當β在B中是頻繁時，α∪β在DB中才是頻繁的。

FP-Growth算法詳述引理單路徑FP樹的模式生成假設一個FP樹T，只有一條路徑P，通過列舉P的子路徑的所有組合，可以得到T的頻繁模式全集，它們的支持度等價于子路徑中的所有項的最小支持度。

FP-Growth算法詳述算法2：在FP樹中挖掘頻繁模式輸入：用DB根據(jù)算法1構造的FP樹和最小支持度閾值ξ；輸出：所有的頻繁模式的集合；方法：調用FP-Growth(FP-Tree,null)；

ProcedureFP-Growth(Tree,α){(1)if(Tree只包含單路徑P)then(2) 對路徑P中節(jié)點的每個組合（記為β）(3) 生成模式β∪α，支持數(shù)＝β中所有節(jié)點的最小支持度(4)else對Tree頭上的每個ai，do{(5) 生成模式β=ai∪α，支持度＝ai.support；(6) 構造β的條件模式庫和β的條件FP樹Treeβ；(7) ifTreeβ≠φ(8)

thencallFP-Growth(Treeβ,β)}}FP-Growth算法詳述1.簡單關聯(lián)規(guī)則單維、單層、布爾型關聯(lián)規(guī)則2.量化關聯(lián)規(guī)則3.多維關聯(lián)規(guī)則4.跨層關聯(lián)規(guī)則關聯(lián)規(guī)則分類籃球=>籃球服，只涉及到用戶購買的物品性別=“女”=>平均收入=2300，涉及的收入是數(shù)值類型性別=“男”=>購買＝“籃球”，涉及兩個維

Adidas籃球=>Nike籃球服同層關聯(lián)規(guī)則層間關聯(lián)規(guī)則籃球=>Nike籃球服挖掘量化關聯(lián)規(guī)則數(shù)值字段根據(jù)數(shù)據(jù)的分布分成布爾字段每個布爾字段都表示一個數(shù)值字段的區(qū)間，落在其中則為1，反之為0。這種分法是動態(tài)的。得出的規(guī)則稱布爾量化關聯(lián)規(guī)則。使用預定義的概念分層對量化屬性離散化如年齡的概念分層可以分為區(qū)間，“20..24”，“25..29”，“35..39”等替換原來的數(shù)值。得出的規(guī)則也叫做靜態(tài)量化關聯(lián)規(guī)則。數(shù)值字段被分成一些能體現(xiàn)含義的區(qū)間，緊扣區(qū)間數(shù)據(jù)的語義?？紤]數(shù)據(jù)點之間的距離因素。得出的規(guī)則稱基于距離的關聯(lián)規(guī)則。直接用數(shù)值字段中的原始數(shù)據(jù)進行分析根據(jù)數(shù)據(jù)的分布對數(shù)值字段的值進行分析，數(shù)值屬性動態(tài)離散化，以滿足某種挖掘標準，如最大化所挖掘的規(guī)則的置信度。該策略將數(shù)值屬性的值處理成量，而不是預定義的區(qū)間或分類。得出的規(guī)則稱量化關聯(lián)規(guī)則。

挖掘量化關聯(lián)規(guī)則挖掘量化關聯(lián)規(guī)則體育類商品球類運動服類輔助用品類籃球足球Adidas………Nike………籃球服足球服……