數(shù)據(jù)挖掘課件第3章關聯(lián)規(guī)則挖掘理論和算法(new)

1、基本概念與解決方法 經典的頻繁項目集生成算法分析 Apriori算法的性能瓶頸問題Apriori的改進算法對項目集格空間理論的發(fā)展關聯(lián)規(guī)則挖掘中的一些更深入的問題,關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的基礎,關聯(lián)規(guī)則挖掘（Association Rule Mining）是數(shù)據(jù)挖掘中研究較早而且至今仍活躍的研究方法之一。最早是由Agrawal等人提出的（1993）。最初提出的動機是針對購物籃分析（Basket Analysis）問題提出

2、的，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫（Transaction Database）中不同商品之間的聯(lián)系規(guī)則。關聯(lián)規(guī)則的挖掘工作成果頗豐。例如，關聯(lián)規(guī)則的挖掘理論、算法設計、算法的性能以及應用推廣、并行關聯(lián)規(guī)則挖掘（Parallel Association Rule Mining）以及數(shù)量關聯(lián)規(guī)則挖掘（Quantitive Association Rule Mining）等。關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的其他研究分支的基礎。,基本概念與解決方法,事

3、務數(shù)據(jù)庫,設I={ i1，i2，…，im }是一個項目(Item)集合，事務數(shù)據(jù)庫D={ t1，t2，…，tn }是由一系列具有唯一標識TID(事務號)的事務組成，每個事務ti（i=1，2，…，n）都對應 I 上的一個子集。一個事務數(shù)據(jù)庫可以用來刻畫：購物記錄： I是全部物品集合， D是購物清單，每個元組 ti 是一次購買物品的集合（它當然是 I 的一個子集）。如I={ 物品1，物品2，…，物品m };事務數(shù)據(jù)庫D={ t1，t2

4、，…，tn }是,事務數(shù)據(jù)庫中關聯(lián)規(guī)則的挖掘,支持度、頻繁項目集、可信度、強關聯(lián)規(guī)則,定義（項目集的支持度） 給定一個全局項目集I和數(shù)據(jù)庫D，一個項目集 I1?I 在D上的支持度（Support）是包含 I1 的事務在D中所占的百分比： support（ I1 ）=|| { t? D | I1 ? t }|| / || D||定義（頻繁項目集） 給定全局項目集I和數(shù)據(jù)庫D ，D中所有滿足用戶指定的最小

5、支持度（Minsupport）的項目集，即大于或等于最小支持度的 I 的非空子集，稱為頻繁項目集（Frequent Itemsets）。在頻繁項目集中挑選出所有不被其他元素包含的頻繁項目集稱為最大頻繁項目集（ Maximum Frequent Itemsets）。,定義（規(guī)則的可信度） 一個定義在I和D上的形如 I1?I2 的關聯(lián)規(guī)則通過滿足一定的可信度(Confidence)來給出。所謂規(guī)則的可信度是指包含 I1 和I2的事務與包含

6、 I1 的事務之比： Confidence(I1?I2)=|| Support(I1∪I2) / Support(I1) 其中I1 ,I2 ?I ; I1∩I2=Ø定義（強關聯(lián)規(guī)則）。D 在 I 上滿足最小支持度和最小可信度的關聯(lián)規(guī)則稱為強關聯(lián)規(guī)則。 通常所說的關聯(lián)規(guī)則一般指上面定義的強關聯(lián)規(guī)則。,,關聯(lián)規(guī)則挖掘基本過程,關聯(lián)規(guī)則挖掘問題就是根據(jù)用戶指定的最小支持度和最小可信度來尋找強關

7、聯(lián)規(guī)則。關聯(lián)規(guī)則挖掘問題可以劃分成兩個子問題：1.發(fā)現(xiàn)頻繁項目集:通過用戶給定最小支持度，尋找所有頻繁項目集或者最大頻繁項目集。2.生成關聯(lián)規(guī)則:通過用戶給定最小可信度，在頻繁項目集中，尋找關聯(lián)規(guī)則。第1個子問題是近年來關聯(lián)規(guī)則挖掘算法研究的重點。,項目集格空間理論,Agrawal等人建立了用于事務數(shù)據(jù)庫挖掘的項目集格空間理論（1993, Appriori 屬性）。其理論核心的原理是：頻繁項目集的所有非空子集都是頻繁項目集

8、非頻繁項目集的所有超集都是非頻繁項目集（相關定理及其證明略。）,經典的頻繁項目集生成算法分析,經典的發(fā)現(xiàn)頻繁項目集算法,1994年，Agrawal 等人提出了著名的Apriori 算法。Apriori算法（發(fā)現(xiàn)頻繁項目集）,（1） L1 = {large 1-itemsets}; //所有1-項目頻集（2） FOR （k=2; Lk-1??; k++） DO BEGIN（3） Ck=apriori-gen（L

9、k-1）; // Ck是k-候選集（4） FOR all transactions t?D DO BEGIN（5） Ct=subset（Ck，t）; // Ct是所有t包含的候選集元素（6） FOR all candidates c? Ct DO（7） c.count++;（8） END（9） Lk={c?Ck |c.count?mins

10、up_count}（10） END（11） L= ∪Lk;,Apriori-gen過程,算法Apriori中調用了Apriori-gen(Lk-1)，是為了通過(k-1)-頻集產生K-侯選集。has_infrequent_subset（c， Lk-1），判斷c是否加入到k-侯選集中。,（1） FOR all itemset p? Lk-1 DO （2） FOR all itemset q?Lk-1 D

11、O （3） IF p.item1=q.item1， …， p.itemk-2=q.itemk-2， p.itemk-1 < q.itemk-1 THEN BEGIN（4） c= p∞q;//把q的第k-1個元素連到p后（5） IF has_infrequent_subset（c， Lk-1） THEN（6） delete c;//刪除含有非頻繁項目子

12、集的侯選元素（7） ELSE add c to Ck;（8） END（9） Return Ck;,,Apriori算法是通過項目集元素數(shù)目不斷增長來完成頻繁項目集發(fā)現(xiàn)的。首先產生1_頻繁項目集L1，然后產生2_頻繁項目集L2，直到不能再擴展頻繁項目集的元素數(shù)目為止。下面給出一個樣本事務數(shù)據(jù)庫，并對它實施Apriori算法。,Apriori算法例子,Database D,C1,L1,L2,C2,Sc

13、an D,L3,Scan D,,,,C3,,Scan D,C4,,Scan D,,,,Scan D,Ø,L4,Minsupport=50% C1：1-候選集 L1：1-頻繁項目集C2：2-候選集 L2：2-頻繁項目集C3：3-候選集 L3：3-頻繁項目集C4：4-候選集 L4：4-頻繁項目集,L3是最大頻繁項目集,關聯(lián)規(guī)則的生成問題,根據(jù)上面介紹的

14、關聯(lián)規(guī)則挖掘的兩個步驟，在得到了所有頻繁項目集后，可以按照下面的步驟生成關聯(lián)規(guī)則：對于每一個頻繁項目集 l ，生成其所有的非空子集；對于l 的每一個非空子集x，計算Conference（x），如果Confidence（x）≥minconfidence，那么“ x?(l-x) ”成立。關聯(lián)規(guī)則生成算法: 從給定的頻繁項目集中生成強關聯(lián)規(guī)則該算法的核心是genrules遞歸過程，它實現(xiàn)一個頻繁項目集中所有強關聯(lián)規(guī)則的生成。,

15、Rule-generate（L，minconf）（1） FOR each frequent itemset lk in L（2） genrules（ lk ， lk）;,算法-遞歸測試一個頻集中的關聯(lián)規(guī)則,genrules（lk: frequent k-itemset， xm: frequent m-itemset）（1）X={（m-1）-itemsets xm-1 | xm-1 in xm }；（2）FOR eac

16、h xm-1 in X BEGIN（3） conf = support（lk）/support（xm-1）;（4） IF （conf ≥?minconf） THEN BEGIN（5） print the rule “xm-1?（ lk-xm-1），with support = support（lk）， confidence=conf”;（6） IF （m-1 > 1） THEN //generate

17、 rules with subsets of xm-1 as antecedents（7） genrules（lk， xm-1）;（8） END（9）END；,Rule-generate算法例子,Minconfidence=80%,Apriori作為經典的頻繁項目集生成算法，在數(shù)據(jù)挖掘中具有里程碑的作用。Apriori算法有兩個致命的性能瓶頸:1．多次掃描事務數(shù)據(jù)庫，需要很大的I/O負載對每次k循環(huán)，侯選集

18、Ck中的每個元素都必須通過掃描數(shù)據(jù)庫一次來驗證其是否加入Lk。假如有一個頻繁大項目集包含10個項的話，那么就至少需要掃描事務數(shù)據(jù)庫10遍。2．可能產生龐大的侯選集由Lk-1產生k-侯選集Ck是指數(shù)增長的，例如104個1-頻繁項目集就有可能產生接近107個元素的2-侯選集。如此大的侯選集對時間和主存空間都是一種挑戰(zhàn)。,Apriori算法的性能瓶頸,一些算法雖然仍然遵循Apriori 屬性，但由于引入了相關技術，在一定程度上改善了Apr

19、iori算法適應性和效率。主要的改進方法有：基于數(shù)據(jù)分割（Partition）的方法：基本原理是“在一個劃分中的支持度小于最小支持度的k-項集不可能是全局頻繁的”?；谏⒘校℉ash）的方法：基本原理是“在一個hash桶內支持度小于最小支持度的k-項集不可能是全局頻繁的”。基于采樣（Sampling）的方法：基本原理是“通過采樣技術，評估被采樣的子集中，并依次來估計k-項集的全局頻度”。其它方法，如動態(tài)刪除沒有用的事務：“不包

20、含任何Lk的事務對未來的掃描結果不會產生影響，因而可以刪除”。,Apriori算法的改進技術,基于數(shù)據(jù)分割的方法,Apriori算法在執(zhí)行過程中是先生成候選集再剪枝，可是生成的候選集并不都是有效的。候選集的產生需要花費很大的代價。把數(shù)據(jù)分割技術應用到關聯(lián)規(guī)則挖掘中，可以改善關聯(lián)規(guī)則挖掘在大數(shù)據(jù)集中的適應性。其基本思想：首先將大數(shù)據(jù)集從邏輯上分成互不相交的塊，每塊應用挖掘算法（如Apriori算法）生成局部的頻繁項目集，然后將這些局部的

21、頻繁項目集作為全局候選頻繁項目集，通過測試他們的支持度來得到最終的全局頻繁項目集。其可在以下兩方面改善Apriori關聯(lián)規(guī)則挖掘算法的性能：1．合理利用主存空間：數(shù)據(jù)分割將大數(shù)據(jù)集分成小的塊，為塊內數(shù)據(jù)一次性導入主存提供機會。2．支持并行挖掘算法：每個分塊的局部頻繁項目集是獨立生成的，因此提供了開發(fā)并行數(shù)據(jù)挖掘算法的良好機制。,定理 設數(shù)據(jù)集D被分割成分塊D1， D2， …， Dn，全局最小支持度為minsupport，假設對應

22、的全局最小支持數(shù)為minsup_count。如果一個數(shù)據(jù)分塊Di 的局部最小支持數(shù)記為minsup_counti (i=1，2，…，n)，則局部最小支持數(shù)minsup_counti按照如下方法生成： minsup_counti = minsup_count *||Di|| / ||D||可以保證所有的局部頻繁項目集涵蓋全局頻繁項目集。,,基于散列的方法,1995，Park等發(fā)現(xiàn)尋找頻繁項目集的主要計算是在生成2-頻繁項

23、目集上。因此，Park等利用了這個性質引入散列技術來改進產生2-頻繁項目集的方法。例：桶地址 =（10x + y）mod 7；minsupport_count=3,TID Items1 I1，I2，I52 I2，I43 I2，I34 I1，I2，I45 I1，I36 I2，I37 I1，I38 I1，I2，I3，I59

24、 I1，I2，I3,L2={(I2，I3) ，(I1，I2) ，(I1，I3)},隨著數(shù)據(jù)庫容量的增大，重復訪問數(shù)據(jù)庫（外存）將導致性能低下。因此，探索新的理論和算法來減少數(shù)據(jù)庫的掃描次數(shù)和侯選集空間占用，已經成為近年來關聯(lián)規(guī)則挖掘研究的熱點之一。兩個典型的方法：Close算法 FP-tree算法,項目集格空間理論的發(fā)展,Close算法對應的原理,一個頻繁閉合項目集的所有閉合子集一定是頻繁的；一個非頻繁閉合項目集的所有閉合超集一

25、定是非頻繁的。什么是一個閉合的項目集？一個項目集C是閉合的，當且僅當對于在C中的任何元素，不可能在C中存在小于或等于它的支持度的子集。例如，C1={AB3，ABC2}是閉合的； C2={AB2，ABC2}不是閉合的；,CLOSS算法的基本思路：利用頻繁閉合i_項目集FCi，生成頻繁閉合i+1 _項目集FCi+1（i≥1）。 首先找出候選頻繁閉合1_項目集FCC1，通過掃描數(shù)據(jù)庫得到候選閉合項目集，再經修剪得到

26、頻繁閉合項目集FC1項目集。用FC1產生候選頻繁閉合2_項目集FCC2，再經修剪得到頻繁閉合項目集FC2項目集。在用FC2推出FC3 ，如此繼續(xù)直到某個FCCr 為空時停止。,,Close算法的例子,掃描數(shù)據(jù)庫得到:FCC1={(A,3), (B,5), (C,4), (D,3), (E,3)}； 相應閉合項目集為: FCl(A)={ABC,3}(計算A的閉合過程:第一項包含{A},首先得到A的閉合為{ABCD},第

27、三項也包含{A}, 故取{ABCD}與第三項的交{ABC}作為A的閉合，第五項也包含{A}, 故取{ABC}與第五項的交{ABC}作為A的閉合,這時到了最后一項,計算完畢)。同理，F(xiàn)Cl(B)={B,5}，F(xiàn)Cl(C)={BC,4}，F(xiàn)Cl(D)={BD,3}，F(xiàn)Cl(E)={BE,3} ；FCC2={(AB,3), (AC,3), (BC,4), (BD,3), (BE,3)}； 相應閉合項目集為:FC2 (AB)={ABC

28、,3}, FC2 (AC)={ABC,3} ； L3，L4，L5不用測，于是頻繁大項集為{ABC }。,,,下面是Close算法作用到右表數(shù)據(jù)集的執(zhí)行過程（假如minsup_count=3）：,樣本數(shù)據(jù)庫,FP-tree算法的基本原理,2000年Han等提出了一個稱為FP-Tree（頻繁模式樹）的算法，該算法只進行 2 次數(shù)據(jù)庫掃描，不使用侯選集，直接壓縮數(shù)據(jù)庫成一個FP-Tree ，然后通過該樹生成關聯(lián)規(guī)則。構造FP-Tree的過程

29、如下 ：按Apriori算法，掃描數(shù)據(jù)庫一次生成1-頻繁項目集，并按頻度降序排序，放入L列表中；創(chuàng)建根結點，標志為null，掃描數(shù)據(jù)庫一次，當?shù)玫綌?shù)據(jù)庫的一個項目（元組）時，就把其中的元素按L表中的次序排列，然后通過遞歸實現(xiàn)FP-Tree的增長；,FP-tree算法的基本原理,樣本數(shù)據(jù)庫,下面看一個例子來說明FP-Tree的增長過程,最小支持度閾值為3。,L,,掃描數(shù)據(jù)庫一次生成1-頻繁項目集（在數(shù)據(jù)庫中出現(xiàn)3次或3次以上的），并按

30、頻度降序排序，放入L列表中；,,(1-頻繁項目集),FP-tree算法的基本原理,樣本數(shù)據(jù)庫,L,,T1,T2,T3,T4,,掃描數(shù)據(jù)庫,依次增長FP-tree，并改變支持數(shù),T5,FP-tree算法的基本原理,L,建立索引,用FP-Tree挖掘頻繁集的基本思想是分而制之，即使用FP-Tree 遞歸增長頻繁集的方法：對每個項，生成其條件模式庫，然后生成其條件FP-Tree；對每個新生成的條件FP-Tree，重復此步驟；直到結果FP

31、-Tree為空，或只含唯一的一個路徑，此路徑的每個子路徑對應的項目集都是頻繁集。,從FP-Tree建立條件模式庫,對應的條件模式庫,FP-tree,,L,用條件模式庫建立對應的條件FP-Tree,m-條件模式庫,,m-條件FP-Tree,L,m-條件FP-Tree,,用條件FP-Tree挖掘頻繁項集,m-條件FP-Tree,得到的頻繁項目集合｛｛ｃ，ｐ｝，｛ｆ，ｃ，ａ，ｍ｝｝,多層次關聯(lián)規(guī)則挖掘,根據(jù)規(guī)則中涉及到的層次，多層次關聯(lián)規(guī)則

32、可以分為：同層關聯(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ī)則挖掘,多層次關聯(lián)規(guī)則挖掘的度量方法可以沿用 “支持度-可信度”的框架。不過，多層次關聯(lián)規(guī)則挖掘有兩種基本的設置支持度的策略：統(tǒng)一

33、的最小支持度：算法實現(xiàn)容易，而且很容易支持層間的關聯(lián)規(guī)則生成。但是弊端也是顯然的：不同層次可能考慮問題的精度不同、面向的用戶群不同對于一些用戶，可能覺得支持度太小，產生了過多不感興趣的規(guī)則。而對于另外的用戶來說，又認為支持度太大，有用信息丟失過多。,不同層次使用不同的最小支持度：每個層次都有自己的最小支持度。較低層次的最小支持度相對較小，而較高層次的最小支持度相對較大。這種方法增加了挖掘的靈活性。但是，也留下了許多相關問題需要解決：

34、首先，不同層次間的支持度應該有所關聯(lián)，只有正確地刻畫這種聯(lián)系或找到轉換方法，才能使生成的關聯(lián)規(guī)則相對客觀。其次，由于具有不同的支持度，層間的關聯(lián)規(guī)則挖掘也是必須解決的問題。例如，有人提出層間關聯(lián)規(guī)則應該根據(jù)較低層次的最小支持度來定。,對于多層關聯(lián)規(guī)則挖掘的策略，可靈活掌握：自上而下方法：先找高層規(guī)則，如“冬季服裝?牛奶” ，再找其下層規(guī)則，如“羽絨服?鮮奶”。如此逐層自上而下挖掘。不同層次的支持度可以一樣，也可以根據(jù)上層的支持度動

35、態(tài)生成下層的支持度。自下而上方法：先找低層規(guī)則，再找其上層規(guī)則，如“羽絨服?鮮奶”。不同層次的支持度可以動態(tài)生成。在同一固定層次上挖掘：用戶可根據(jù)情況，在一個固定層次上挖掘，如果需要查看其他層次的數(shù)據(jù)，可通過上鉆和下鉆等操作來獲得相應數(shù)據(jù)。,多維關聯(lián)規(guī)則挖掘,多維關聯(lián)規(guī)則可以有：維內的關聯(lián)規(guī)則：例如，“年齡（X，20~30）^職業(yè)（X，學生）?購買（X，筆記本電腦）”。這里我們就涉及到三個維：年齡、職業(yè)、購買。混合維關聯(lián)規(guī)則：這

36、類規(guī)則允許同一個維重復出現(xiàn)。例如，“年齡（X，20~30）? 購買（X，筆記本電腦） ? 購買（X，打印機）”。由于同一個維“購買”在規(guī)則中重復出現(xiàn)，因此為挖掘帶來難度。但是，這類規(guī)則更具有普遍性，具有更好的應用價值，因此近年來得到普遍關注。,數(shù)量關聯(lián)數(shù)規(guī)則的挖掘,主要解決連續(xù)的數(shù)值型數(shù)據(jù)挖掘問題，它與布爾關聯(lián)規(guī)則挖掘不同。主要涉及的關鍵問題有：連續(xù)數(shù)值屬性的處理，一般有對數(shù)值屬性進行離散化處理，包括：數(shù)值屬性的靜態(tài)離散化；數(shù)值