1、第三章 關聯(lián)規(guī)則挖掘理論和算法 內(nèi)容提要基本概念與解決方法 經(jīng)典的頻繁項目集生成算法分析 Apriori算法的性能瓶頸問題Apriori的改進算法30 八月 20221關聯(lián)規(guī)則挖掘（Association Rule Mining）是數(shù)據(jù)挖掘中研究較早而且至今仍活躍的研究方法之一。最早是由Agrawal等人提出的（1993）。最初提出的動機是針對購物籃分析（Basket Analysis）問題提出的，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫（Transaction Database）中不同商品之間的聯(lián)系規(guī)則。關聯(lián)規(guī)則的挖掘工作成果頗豐。例如，關聯(lián)規(guī)則的挖掘理論、算法設計、算法的性能以及應用推廣、并行關聯(lián)規(guī)則挖

2、掘（Parallel Association Rule Mining）以及數(shù)量關聯(lián)規(guī)則挖掘（Quantitive Association Rule Mining）等。關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的其他研究分支的基礎。3.1 基本概念與解決方法30 八月 202223.1 基本概念與解決方法事務數(shù)據(jù)庫設I= i1，i2，im 是一個項目集合，事務數(shù)據(jù)庫D= t1，t2，tn 是由一系列具有唯一標識TID的事務組成，每個事務ti（i=1，2，n）都對應I上的一個子集。一個事務數(shù)據(jù)庫可以用來刻畫：購物記錄： I是全部物品集合， D是購物清單，每個元組ti是一次購買物品的集合（它當然是I的一個子集）。其它應

3、用問題30 八月 20223支持度與頻繁項目集 定義3-1（項目集的支持度）. 給定一個全局項目集I和數(shù)據(jù)庫D，一個項目集I1I在D上的支持度（Support）是包含I1的事務在D中所占的百分比：support（ I1 ）=| t D | I1 t| / | D|。定義3-2（頻繁項目集）.給定全局項目集I和數(shù)據(jù)庫D ，D中所有滿足用戶指定的最小支持度（Minsupport）的項目集，即大于或等于minsupport的I的非空子集，稱為頻繁項目集（頻集：Frequent Itemsets）或者大項目集（Large Iitemsets）。在頻繁項目集中挑選出所有不被其他元素包含的頻繁項目集稱為最

4、大頻繁項目集（最大頻集： Maximum Frequent Itemsets）或最大大項目集（Maximum Large Iitemsets）。30 八月 20224可信度與關聯(lián)規(guī)則定義3-3（關聯(lián)規(guī)則與可信度）.給定一個全局項目集I和數(shù)據(jù)庫D，一個定義在I和D上的關聯(lián)規(guī)則形如I1I2，并且它的可信度或信任度或置信度（Confidence）是指包含I1和I2的事務數(shù)與包含I1的事務數(shù)之比，即Confidence（I1I2）= support（I1I2）/ support（I1），其中I1，I2I，I1I2=。定義3-4（強關聯(lián)規(guī)則）. D在I上滿足最小支持度和最小信任度（Minconfiden

5、ce）的關聯(lián)規(guī)則稱為強關聯(lián)規(guī)則（Strong Association Rule）。30 八月 20225關聯(lián)規(guī)則挖掘基本過程關聯(lián)規(guī)則挖掘問題可以劃分成兩個子問題：1. 發(fā)現(xiàn)頻繁項目集:通過用戶給定Minsupport ，尋找所有頻繁項目集或者最大頻繁項目集。2生成關聯(lián)規(guī)則:通過用戶給定Minconfidence ，在頻繁項目集中，尋找關聯(lián)規(guī)則。第1個子問題是近年來關聯(lián)規(guī)則挖掘算法研究的重點。30 八月 202263.2 經(jīng)典的頻繁項目集生成算法分析項目集空間理論經(jīng)典的發(fā)現(xiàn)頻繁項目集算法關聯(lián)規(guī)則生成算法30 八月 202273.2.1 項目集空間理論 Agrawal等人建立了用于事務數(shù)據(jù)庫挖掘的

6、項目集格空間理論（1993, Appriori 屬性）。定理3-1（ Appriori 屬性1）. 如果項目集X 是頻繁項目集，那么它的所有非空子集都是頻繁項目集。證明 設X是一個項目集，事務數(shù)據(jù)庫T 中支持X 的元組數(shù)為s。對X的任一非空子集為Y，設T中支持Y的元組數(shù)為s1。根據(jù)項目集支持數(shù)的定義，很容易知道支持X 的元組一定支持Y，所以s1 s，即support（Y） support（X）。按假設：項目集X 是頻繁項目集，即support(X) minsupport，所以support（Y） support（X） minsupport，因此Y是頻繁項目集。定理3-2（ Appriori 屬

7、性2）.如果項目集X 是非頻繁項目集，那么它的所有超集都是非頻繁項目集。證明 （略）30 八月 202283.2.2 經(jīng)典的發(fā)現(xiàn)頻繁項目集算法1994年，Agrawal 等人提出了著名的Apriori 算法。算法3-1 Apriori（發(fā)現(xiàn)頻繁項目集）（1） L1 = large 1-itemsets; /所有1-項目頻集（2） FOR （k=2; Lk-1; k+） DO BEGIN（3） Ck=apriori-gen（Lk-1）; / Ck是k-候選集（4） FOR all transactions tD DO BEGIN（5） Ct=subset（Ck，t）; / Ct是所有t包含的候選

8、集元素（6） FOR all candidates c Ct DO（7） c.count+;（8） END（9） Lk=cCk |c.countminsup_count（10） END（11） L= Lk; 30 八月 20229apriori-gen過程算法apriori中調(diào)用了apriori-gen（Lk-1），是為了通過（k-1）-頻集產(chǎn)生K-侯選集。has_infrequent_subset（c， Lk-1），判斷c是否加入到k-侯選集中。（1） FOR all itemset p Lk-1 DO （2） FOR all itemset qLk-1 DO （3） IF p.item1=

9、q.item1， ， p.itemk-2=q.itemk-2， p.itemk-1 1） THEN /generate rules with subsets of xm-1 as antecedents（7） genrules（lk， xm-1）;（8） END（9）END； 30 八月 202216Rule-generate算法例子Minconfidence=80%序號lkxm-1confidencesupport規(guī)則（是否是強規(guī)則）123523100%50%235（是）2235267%50%235（否）3235367%50%325（否）42352567%50%253（否）5235567%5

10、0%523（否） 623535100%50%352（是）30 八月 2022173.3 Apriori算法的性能瓶頸問題Apriori作為經(jīng)典的頻繁項目集生成算法，在數(shù)據(jù)挖掘中具有里程碑的作用。Apriori算法有兩個致命的性能瓶頸:1多次掃描事務數(shù)據(jù)庫，需要很大的I/O負載對每次k循環(huán)，侯選集Ck中的每個元素都必須通過掃描數(shù)據(jù)庫一次來驗證其是否加入Lk。假如有一個頻繁大項目集包含10個項的話，那么就至少需要掃描事務數(shù)據(jù)庫10遍。2可能產(chǎn)生龐大的侯選集由Lk-1產(chǎn)生k-侯選集Ck是指數(shù)增長的，例如104個1-頻繁項目集就有可能產(chǎn)生接近107個元素的2-侯選集。如此大的侯選集對時間和主存空間都是

11、一種挑戰(zhàn)。30 八月 2022183.4 Apriori的改進算法基于數(shù)據(jù)分割的方法基于散列的方法30 八月 2022193.4 提高Apriori算法效率的技術一些算法雖然仍然遵循Apriori 屬性，但是由于引入了相關技術，在一定程度上改善了Apriori算法適應性和效率。主要的改進方法有：基于數(shù)據(jù)分割（Partition）的方法：基本原理是“在一個劃分中的支持度小于最小支持度的k-項集不可能是全局頻繁的”?；谏⒘校℉ash）的方法：基本原理是“在一個hash桶內(nèi)支持度小于最小支持度的k-項集不可能是全局頻繁的”。基于采樣（Sampling）的方法：基本原理是“通過采樣技術，評估被采樣的

12、子集中，并依次來估計k-項集的全局頻度”。其他：如，動態(tài)刪除沒有用的事務：“不包含任何Lk的事務對未來的掃描結(jié)果不會產(chǎn)生影響，因而可以刪除”。30 八月 202220基于數(shù)據(jù)分割的方法定理3-5 設數(shù)據(jù)集D被分割成分塊D1， D2， ， Dn，全局最小支持數(shù)為minsup_count。如果一個數(shù)據(jù)分塊Di 的局部最小支持數(shù)minsup_counti （i=1，2，n），按著如下方法生成：minsup_counti= minsup_count *|Di| / |D|則所有的局部頻繁項目集涵蓋全局頻繁項目集。作用：1合理利用主存空間：數(shù)據(jù)分割將大數(shù)據(jù)集分成小的塊，為塊內(nèi)數(shù)據(jù)一次性導入主存提供機會。

13、2支持并行挖掘算法：每個分塊的局部頻繁項目集是獨立生成的，因此提供了開發(fā)并行數(shù)據(jù)挖掘算法的良好機制。30 八月 202221基于散列的方法1995，Park等發(fā)現(xiàn)尋找頻繁項目集的主要計算是在生成2-頻繁項目集上。因此，Park等利用了這個性質(zhì)引入雜湊技術來改進產(chǎn)生2-頻繁項目集的方法。例子：桶地址 =（10 x+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 I1，I2，I3桶地址 0 1 2 3 4 5 6桶計數(shù) 2 2 4 2

14、2 4 4桶內(nèi) I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I3，I5 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3L2=I2，I3 ， I1，I2 ， I1，I3 30 八月 202222第三章 關聯(lián)規(guī)則挖掘理論和算法 內(nèi)容提要3.5 對項目集格空間理論的發(fā)展Close算法FP-tree算法30 八月 202223探索新的理論隨著數(shù)據(jù)庫容量的增大，重復訪問數(shù)據(jù)庫（外存）將導致性能低下。因此，探索新的理論和算法來減少數(shù)據(jù)庫的掃描次數(shù)和侯選集空間占用，已經(jīng)成為

15、近年來關聯(lián)規(guī)則挖掘研究的熱點之一。兩個典型的方法：Close算法 FP-tree算法 30 八月 202224Close算法對應的原理一個頻繁閉合項目集的所有閉合子集一定是頻繁的；一個非頻繁閉合項目集的所有閉合超集一定是非頻繁的。什么是一個閉合的項目集？一個項目集C是閉合的，當且僅當對于在C中的任何元素，不可能在C中存在小于或等于它的支持度的子集。例如，C1=AB3，ABC2是閉合的； C2=AB2，ABC2不是閉合的； 30 八月 202225Close算法的例子下面是Close算法作用到表4-1數(shù)據(jù)集的執(zhí)行過程（假如minsup_count=3）：掃描數(shù)據(jù)庫得到L1=(A,3), (B,5

16、), (C,4), (D,3), (E,3)；相應關閉項目集為 Cl (A)=ABC,3，Cl (B)=B,5，Cl (C)=BC,4，Cl (D)=BD,3，Cl(E)=BE,3 ；L2=(AB,3), (AC,3), (BC,4), (BD,3), (BE,3)；相應關閉集為C2 (AB)=ABC,3； L3，L4，L5不用測，于是頻繁大項集為ABC 。樣本數(shù)據(jù)庫TIDItemset1 A，B，C，D2B，C，E3A，B，C，E4B，D，E5A，B，C，D30 八月 202226FP-tree算法的基本原理進行2次數(shù)據(jù)庫掃描：一次對所有1-項目的頻度排序；一次將數(shù)據(jù)庫信息轉(zhuǎn)變成緊縮內(nèi)存結(jié)構(gòu)

17、。不使用侯選集，直接壓縮數(shù)據(jù)庫成一個頻繁模式樹，通過頻繁模式樹可以直接得到頻集?；静襟E是：兩次掃描數(shù)據(jù)庫，生成頻繁模式樹FP-Tree：掃描數(shù)據(jù)庫一次，得到所有1-項目的頻度排序表T；依照T，再掃描數(shù)據(jù)庫，得到FP-Tree。使用FP-Tree，生成頻集：為FP-tree中的每個節(jié)點生成條件模式庫；用條件模式庫構(gòu)造對應的條件FP-tree；遞歸挖掘條件FP-trees同時增長其包含的頻繁集：如果條件FP-tree只包含一個路徑，則直接生成所包含的頻繁集。 30 八月 202227生成頻繁模式樹FP-Treef:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1TItem freq

18、uency head f4c4a3b3m3p3min_support = 0.5TIDOriginal Items (ordered) frequent items100f, a, c, d, g, i, m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, of, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, p30 八月 202228挖掘頻集步驟1：生成條件模式庫為每個節(jié)點， 尋找它的所有前綴路徑并記錄其頻度，形成CPBCPBitemcond. pattern basecf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1TItem frequency head f4c4a3b3m3p330 八月 202229挖掘頻集步驟2：構(gòu)造C-FP-tree為每一個節(jié)點，通過FP-tree構(gòu)造一個C-FP-tree例如，m節(jié)點的C-FP-tree為：m-CPB:fca:2, fcab:1f: