第八 關(guān)聯(lián)規(guī)則

會計學(xué)1第八關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的主要技術(shù)之一，也是在無指導(dǎo)學(xué)習(xí)系統(tǒng)中挖掘本地模式的最普遍形式。本章除了重點介紹關(guān)聯(lián)規(guī)則挖掘的Apriori技術(shù)外，還將討論一些和Web挖掘、文本挖掘相關(guān)的數(shù)據(jù)挖掘方法。第1頁/共28頁8.1購物籃分析購物籃是顧客在一次事務(wù)中所購買項的集合，所謂事務(wù)是一個明確定義的商業(yè)行為。事務(wù)數(shù)據(jù)庫研究的一個最普通的例子就是尋找項的集合，或叫做項集。包含i個項的項集被稱為i-項集。包含該項集的事務(wù)的百分?jǐn)?shù)叫做該項集的支持度。支持度超過指定閾值的項集叫做頻繁項集。第2頁/共28頁基本概念：設(shè)I={i1,i2,…im}是項的集合，DB為事務(wù)集合，其中每個事務(wù)T是項的集合，且有。每一個事務(wù)有一個標(biāo)識符，稱作TID。設(shè)X為一個項集，當(dāng)且僅當(dāng)時，即T包含X。關(guān)聯(lián)規(guī)則是形如的蘊涵式，其中,

,且。規(guī)則在事務(wù)集DB中成立，具有支持度s，其中s是DB中事務(wù)包含X和Y兩者的百分比。規(guī)則在事務(wù)集DB中具有置信度c，如果DB中包含X的事務(wù)同時也包含Y的百分比是c。第3頁/共28頁支持度是概率。置信度是概率。置信度可以表示規(guī)則的可信性，支持度表示模式在規(guī)則中出現(xiàn)的頻率。具有高置信度和強(qiáng)支持度的規(guī)則被稱為強(qiáng)規(guī)則。挖掘關(guān)聯(lián)規(guī)則的問題可以分兩個階段：

1.發(fā)掘大項集，也就是事務(wù)支持度s大于預(yù)先給定的最小閾值的項的集合。

2.使用大項集來產(chǎn)生數(shù)據(jù)庫中置信度c大于預(yù)先給定的最小閾值的關(guān)聯(lián)規(guī)則。Apriori算法是解決這個問題的常用方法。第4頁/共28頁8.2APRIORI算法Apriori算法利用幾次迭代來計算數(shù)據(jù)庫中的頻繁項集。第i次迭代計算出所有頻繁i項集(包含i個元素的項集)。每一次迭代有兩個步驟：產(chǎn)生候選集；計算和選擇候選集。在第一次迭代中，產(chǎn)生的候選集包含所有1-項集，并計算其支持度s，s大于閾值的1-項集被選為頻繁1-項集。第二次迭代時，Apriori算法首先去除非頻繁1-項集，在頻繁1-項集的基礎(chǔ)上進(jìn)行產(chǎn)生頻繁2-項集。原理是：如果一個項集是頻繁，那么它的所有子集也是頻繁的。第5頁/共28頁例如，以表8-1中的數(shù)據(jù)為例。假設(shè)smin=50%。第6頁/共28頁在第一次迭代的第一步中，所有單項集都作為候選集，產(chǎn)生一個候選集列表。在下一步中，計算每一項的支持度，然后在smin的基礎(chǔ)上選擇頻繁項集。圖8-1中給出第一次迭代的結(jié)果。第7頁/共28頁在挖掘2-項集時，因為2-項集的任何子集都是頻繁項集，所以Apriori算法使用L1*L1來產(chǎn)生候選集。*運算通常定義為：

Lk*Lk={X∪Y其中X,Y∈Lk,|X∩Y|=k+1}

注:|X∩Y|=k+1即X和Y合取容量為k+1當(dāng)k=1時，因此，C2包含在第二次迭代中作為候選集由運算|L1|·|L1-1|/2所產(chǎn)生的2-項集。本例中為：4·3/2=6。用該列表來掃描DB，計算每一個候選集的s，并與smin比較2-項集L2。圖8-2給出了所有這些步驟和第二次迭代的結(jié)果。第8頁/共28頁候選集C3

運用L2*L2來產(chǎn)生，運算結(jié)果得到{A,B,C},{A,C,E},{B,C,E}，但只有{B,C,E}的所有子集是頻繁項集，成為候選的3-項集。然后掃描DB，并且挖掘出頻繁3-項集，見圖8-3所示。第9頁/共28頁因為本例的L3無法產(chǎn)生候選的4-項集，所以算法停止迭代過程。第10頁/共28頁該算法不僅計算所有頻繁集的s，也計算那些沒有被刪除的非頻繁候選集的s。所有非頻繁但被算法計算s的候選項集的集合被稱為負(fù)邊界。因此，如果項集非頻繁的，但它的子集都是頻繁的，那么它就在負(fù)邊界之中。在本例中，負(fù)邊界由項集{D},{A,B},{A,E}組成。負(fù)邊界在一些Apriori的改進(jìn)算法中更為重要，例如生成大項集或?qū)С鲐?fù)關(guān)聯(lián)規(guī)則時提高了有效性。第11頁/共28頁8.3從頻繁項集得到關(guān)聯(lián)規(guī)則第二階段的工作是在第一階段的基礎(chǔ)上，來挖掘關(guān)聯(lián)規(guī)則。如果規(guī)則為{x1,x2,x3}→x4，那么項集{x1,x2,x3,x4}和{x1,x2,x3}都必須是頻繁的。然后，規(guī)則置信度c=P({x4}|{x1,x2,x3})=s(x1,x2,x3,x4)/s(x1,x2,x3)。

置信度c大于給定的閾值的規(guī)則就是強(qiáng)規(guī)則。第12頁/共28頁例如，檢驗表8-1DB中的關(guān)聯(lián)規(guī)則{B,C}→{E}是否為強(qiáng)關(guān)聯(lián)規(guī)則。由圖8-2和圖8-3可得支持度：

s(B,C)=2,s(B,C,E)=2

由支持度得置信度：c({B,C}→{E})=s(B,C,E)/s(B,C)=2/2=1(100%)

可見，無論閾值為多少，該規(guī)則都能通過，也就是說，如果事務(wù)包含B和C，那么它也將包含E。我們現(xiàn)在有目標(biāo)是在DB頻繁集中得到所有的強(qiáng)關(guān)聯(lián)規(guī)則。第13頁/共28頁請注意:并不是所有的強(qiáng)關(guān)聯(lián)規(guī)則都是有用的或者有意義的。例如，一個谷類早餐的零售商對5000名學(xué)生的調(diào)查的案例。數(shù)據(jù)表明：60%的學(xué)生打籃球，75%的學(xué)生吃這類早餐，40%的學(xué)生即打籃球吃這類早餐。假設(shè)支持度閾值s=0.4，置信度閾值c=60%?；谏厦鏀?shù)據(jù)和假設(shè)我們可挖掘出強(qiáng)關(guān)聯(lián)規(guī)則“(打籃球)→(吃早餐)”，因為其(打籃球)和(吃早餐)的支持度都大于支持度閾值，都是頻繁項，而規(guī)則的置信度c=40%/60%=66.6%也大于置信度閾值。第14頁/共28頁然而，以上的關(guān)聯(lián)規(guī)則很容易產(chǎn)生誤解，因為吃早餐的比例為75%，大于66%。也就是說，打籃球與吃早餐實際上是負(fù)關(guān)聯(lián)的。為了消除這種誤導(dǎo)的規(guī)則，應(yīng)該在關(guān)聯(lián)規(guī)則A→B的置信度超過某個特定的度量標(biāo)準(zhǔn)時，定義它為有意義的。因此挖掘關(guān)聯(lián)規(guī)則的正確方法是：

s(A,B)/s(A)-s(B)>d或者：

s(A,B)-s(A)·s(B)>k式中d或k是適當(dāng)?shù)某Ａ?。（計算上例）?5頁/共28頁8.4提高Apriori算法的效率因為挖掘頻繁項集時所處理的數(shù)據(jù)量越來越大，所以很有必要提高算法的效率。Apriori算法掃描DB的次數(shù)完全依賴于最大的頻繁項集中項的數(shù)量。為了解決這個問題，該算法作了一些改進(jìn)?；趧澐值腁priori算法只需要對DB進(jìn)行兩次掃描。DB被劃分成若干個非重疊的分區(qū)，分區(qū)與內(nèi)存相匹配。第16頁/共28頁在第一次掃描時，算法讀取每一個分區(qū)，每個分區(qū)內(nèi)計算局部頻繁項集。在第二次掃描時，算法計算整個DB中所有局部頻繁集的支持度。如果項集對于整個數(shù)據(jù)庫來說是頻繁的，那么它至少需要在一個分區(qū)中是頻繁的。因此，第二次掃描完成計算所有潛在的頻繁項集的超集。隨著數(shù)據(jù)庫大小的增加，取樣成為數(shù)據(jù)挖掘的一個不可多得的有效途徑，基于取樣的算法需要以數(shù)據(jù)庫進(jìn)行兩次掃描。第17頁/共28頁第一次掃描，從DB中選擇一個樣本，并且產(chǎn)生一個在整個DB中很可能為頻繁的候選項集的集合。第二次掃描，算法計算這些項集的實際支持度和它們的負(fù)邊界的支持度。如果在負(fù)邊界中沒有項集是頻繁的，那么說明已挖掘出所有頻繁項集。否則，負(fù)邊界中的項集的一些超集可能就是頻繁的，但它的支持度還沒有計算出來。取樣算法在隨后的掃描時，會產(chǎn)生并計算所有這些潛在有頻繁項集。第18頁/共28頁圖8-4是實際應(yīng)用的一個例子，該例揭示這樣一個問題，事務(wù)數(shù)據(jù)庫中的購買模式在最低層上不會顯示任何規(guī)則，但在一些高的概念層可能會顯示一些有意義的規(guī)則。第19頁/共28頁Apriori算法的一個擴(kuò)展在DB項上涉及到is-a層次，它包含數(shù)據(jù)庫結(jié)構(gòu)中已經(jīng)存在的多抽象層的信息。is-a層次定義哪些項是其他項的一般化或?qū)ｉT化。除了明確列出的項以外，事務(wù)還以分類的方式包含了它們的祖先，這樣就可以發(fā)掘出高層次的關(guān)系。第20頁/共28頁8.5頻繁模式增長方法(FP-增長方法）一個Apriori算法的可伸縮的問題。如果生成一個長度100的頻繁模式，例如{a1,a2,…,a100}，那么所產(chǎn)生的候選集的數(shù)量至少為：計算的復(fù)雜性成指數(shù)增長，這是影響一些新關(guān)聯(lián)規(guī)則挖掘算法發(fā)展的一個主要因素。第21頁/共28頁頻繁模式增長(FP-growth)方法是在大型數(shù)據(jù)中挖掘頻繁項集的一個有效算法。算法進(jìn)行中不存在產(chǎn)生候選集的繁瑣過程，當(dāng)DB很大時，F(xiàn)P-增長算法首先進(jìn)行數(shù)據(jù)庫投影，得到頻繁集，然后通過構(gòu)造一個壓縮的數(shù)據(jù)庫結(jié)構(gòu)---FP-樹再進(jìn)行挖掘。第22頁/共28頁例如，表8-3給出DB，它的最小支持度閾值為3。第23頁/共28頁第一步，掃描T，得到頻繁集的列表L:L={(f,4),(c,4),(a,3),(b,3),(m,3),(p,3)}

按支持度大小遞減排列。第二步，創(chuàng)建樹的根部(ROOT)，第二次掃描T。對第一個事務(wù)的掃描得樹的第一個分枝:{(f,1),(c,1),(a,1),(b,1),(m,1),(p,1)}。分枝中節(jié)點的計數(shù)(都是1)代表了樹中該節(jié)點項所出現(xiàn)的次數(shù)，并按Ｌ中順序排列。對第二個事務(wù)，與第一事務(wù)有相同項f,c,a，所有有同一個前綴(f,c,a)，得到一個新的分枝{(f,2),(c,2),(a,2),(b,1),(m,1)}，見圖8-5a。第24頁/共28頁其他事務(wù)按同樣的方式插入到FP-樹中，圖8-5b給出了最后的FP-樹。第25頁/共28頁按照頻繁項的表L，整個頻繁項的集合被劃分為幾個沒有重疊的子集:1)含有p的頻繁項集；2)含有m但不含有p的頻繁項集；3)含有b但不含有m,p的頻繁項集；…；6)只含有f的大項集。1)有兩個路徑{(f,4),(c,3),(a,3),(m,2),(p,2)}和{(c,1),(b,1),(p,1)},根據(jù)閾值產(chǎn)生新的頻繁項集(c,p)2)有兩個路徑{(f,4),(c,3),(a,3),(m,2)}和{(f,4),