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

1、基本概念與解決方法 經(jīng)典的頻繁項(xiàng)目集生成算法分析 Apriori算法的性能瓶頸問(wèn)題Apriori的改進(jìn)算法對(duì)項(xiàng)目集格空間理論的發(fā)展關(guān)聯(lián)規(guī)則挖掘中的一些更深入的問(wèn)題第三章 關(guān)聯(lián)規(guī)則挖掘理論和算法基本概念與解決方法 第三章 關(guān)聯(lián)規(guī)則挖掘理論和算法關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的基礎(chǔ)關(guān)聯(lián)規(guī)則挖掘（Association Rule Mining）是數(shù)據(jù)挖掘中研究較早而且至今仍活躍的研究方法之一。最早是由Agrawal等人提出的（1993）。最初提出的動(dòng)機(jī)是針對(duì)購(gòu)物籃分析（Basket Analysis）問(wèn)題提出的，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫(kù)（Transaction Database）中不同商品之間的聯(lián)系規(guī)

2、則。關(guān)聯(lián)規(guī)則的挖掘工作成果頗豐。例如，關(guān)聯(lián)規(guī)則的挖掘理論、算法設(shè)計(jì)、算法的性能以及應(yīng)用推廣、并行關(guān)聯(lián)規(guī)則挖掘（Parallel Association Rule Mining）以及數(shù)量關(guān)聯(lián)規(guī)則挖掘（Quantitive Association Rule Mining）等。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的其他研究分支的基礎(chǔ)。 基本概念與解決方法關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的基礎(chǔ)關(guān)聯(lián)規(guī)則挖掘（Associa事務(wù)數(shù)據(jù)庫(kù) 設(shè)I= i1，i2，im 是一個(gè)項(xiàng)目(Item)集合，事務(wù)數(shù)據(jù)庫(kù)D= t1，t2，tn 是由一系列具有唯一標(biāo)識(shí)TID(事務(wù)號(hào))的事務(wù)組成，每個(gè)事務(wù)ti（i=1，2，n）都對(duì)應(yīng) I 上的一個(gè)子集

3、。一個(gè)事務(wù)數(shù)據(jù)庫(kù)可以用來(lái)刻畫(huà)：購(gòu)物記錄： I是全部物品集合， D是購(gòu)物清單，每個(gè)元組 ti 是一次購(gòu)買物品的集合（它當(dāng)然是 I 的一個(gè)子集）。如I= 物品1，物品2，物品m ;事務(wù)數(shù)據(jù)庫(kù)D= t1，t2，tn 是事務(wù)數(shù)據(jù)庫(kù)中關(guān)聯(lián)規(guī)則的挖掘 t1物品2物品6物品9 t2物品3物品8物品16 tn物品1物品12物品34 事務(wù)數(shù)據(jù)庫(kù) 設(shè)I= i1，i2，im 是一個(gè)項(xiàng)目(I支持度、頻繁項(xiàng)目集、可信度、強(qiáng)關(guān)聯(lián)規(guī)則 定義（項(xiàng)目集的支持度） 給定一個(gè)全局項(xiàng)目集I和數(shù)據(jù)庫(kù)D，一個(gè)項(xiàng)目集 I1I 在D上的支持度（Support）是包含 I1 的事務(wù)在D中所占的百分比： support（ I1 ）=| t D

4、| I1 t | / | D|定義（頻繁項(xiàng)目集） 給定全局項(xiàng)目集I和數(shù)據(jù)庫(kù)D ，D中所有滿足用戶指定的最小支持度（Minsupport）的項(xiàng)目集，即大于或等于最小支持度的 I 的非空子集，稱為頻繁項(xiàng)目集（Frequent Itemsets）。在頻繁項(xiàng)目集中挑選出所有不被其他元素包含的頻繁項(xiàng)目集稱為最大頻繁項(xiàng)目集（ Maximum Frequent Itemsets）。支持度、頻繁項(xiàng)目集、可信度、強(qiáng)關(guān)聯(lián)規(guī)則 定義（項(xiàng)目集的支持度定義（規(guī)則的可信度） 一個(gè)定義在I和D上的形如 I1I2 的關(guān)聯(lián)規(guī)則通過(guò)滿足一定的可信度(Confidence)來(lái)給出。所謂規(guī)則的可信度是指包含 I1 和I2的事務(wù)與包含

5、 I1 的事務(wù)之比： Confidence(I1I2)=| Support(I1I2) / Support(I1) 其中I1 ,I2 I ; I1I2=定義（強(qiáng)關(guān)聯(lián)規(guī)則）。D 在 I 上滿足最小支持度和最小可信度的關(guān)聯(lián)規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則。 通常所說(shuō)的關(guān)聯(lián)規(guī)則一般指上面定義的強(qiáng)關(guān)聯(lián)規(guī)則。定義（規(guī)則的可信度） 一個(gè)定義在I和D上的形如 I1I2關(guān)聯(lián)規(guī)則挖掘基本過(guò)程關(guān)聯(lián)規(guī)則挖掘問(wèn)題就是根據(jù)用戶指定的最小支持度和最小可信度來(lái)尋找強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘問(wèn)題可以劃分成兩個(gè)子問(wèn)題：1.發(fā)現(xiàn)頻繁項(xiàng)目集:通過(guò)用戶給定最小支持度，尋找所有頻繁項(xiàng)目集或者最大頻繁項(xiàng)目集。2.生成關(guān)聯(lián)規(guī)則:通過(guò)用戶給定最小可信度，在

6、頻繁項(xiàng)目集中，尋找關(guān)聯(lián)規(guī)則。第1個(gè)子問(wèn)題是近年來(lái)關(guān)聯(lián)規(guī)則挖掘算法研究的重點(diǎn)。關(guān)聯(lián)規(guī)則挖掘基本過(guò)程關(guān)聯(lián)規(guī)則挖掘問(wèn)題就是根據(jù)用戶指定的最小支項(xiàng)目集格空間理論 Agrawal等人建立了用于事務(wù)數(shù)據(jù)庫(kù)挖掘的項(xiàng)目集格空間理論（1993, Appriori 屬性）。其理論核心的原理是：頻繁項(xiàng)目集的所有非空子集都是頻繁項(xiàng)目集非頻繁項(xiàng)目集的所有超集都是非頻繁項(xiàng)目集（相關(guān)定理及其證明略。）經(jīng)典的頻繁項(xiàng)目集生成算法分析項(xiàng)目集格空間理論 Agrawal等人建立了用于事務(wù)數(shù)據(jù)庫(kù)挖掘Apriori算法是通過(guò)項(xiàng)目集元素?cái)?shù)目不斷增長(zhǎng)來(lái)完成頻繁項(xiàng)目集發(fā)現(xiàn)的。首先產(chǎn)生1_頻繁項(xiàng)目集L1，然后產(chǎn)生2_頻繁項(xiàng)目集L2，直到不能再擴(kuò)

7、展頻繁項(xiàng)目集的元素?cái)?shù)目為止。下面給出一個(gè)樣本事務(wù)數(shù)據(jù)庫(kù)，并對(duì)它實(shí)施Apriori算法。TIDItemset1001，3，42002，3，53001，2，3，54002，5經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集算法 1994年，Agrawal 等人提出了著名的Apriori 算法。Apriori算法是通過(guò)項(xiàng)目集元素?cái)?shù)目不斷增長(zhǎng)來(lái)完成頻繁項(xiàng)目Apriori算法例子Database DC1L1L2C2Scan DL3Scan DC3Scan DC4Scan DScan DL4Minsupport=50% C1：1-候選集 L1：1-頻繁項(xiàng)目集C2：2-候選集 L2：2-頻繁項(xiàng)目集C3：3-候選集 L3：3-頻繁項(xiàng)目集

8、C4：4-候選集 L4：4-頻繁項(xiàng)目集L3是最大頻繁項(xiàng)目集Apriori算法例子Database DC1L1L2C2SApriori算法（發(fā)現(xiàn)頻繁項(xiàng)目集）（1） L1 = large 1-itemsets; /所有1-項(xiàng)目頻集（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包含的候選集元素（6） FOR all candidates c Ct DO（7） c.count+;（8）

9、 END（9） Lk=cCk |c.countminsup_count（10） END（11） L= Lk; （1） L1 = large 1-itemsets;Apriori-gen過(guò)程算法Apriori中調(diào)用了Apriori-gen(Lk-1)，是為了通過(guò)(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=q.item1， ， p.itemk-2=q.itemk-2， p.

10、itemk-1 1） THEN /generate rules with subsets of xm-1 as antecedents（7） genrules（lk， xm-1）;（8） END（9）END； 算法-遞歸測(cè)試一個(gè)頻集中的關(guān)聯(lián)規(guī)則genrules（lk: Rule-generate算法例子Minconfidence=80%序號(hào)lkxm-1ConfidenceSupport規(guī)則（是否是強(qiáng)規(guī)則）1235267%50%235（否）2235367%50%325（否）3235567%50%523（否）423523100%50%235（是）52352567%50%253（否）62353510

11、0%50%352（是）包含2,35的事務(wù)與包含2的事務(wù)的比值,即2:3同時(shí)滿足支持度和可信度Rule-generate算法例子MinconfidenceApriori作為經(jīng)典的頻繁項(xiàng)目集生成算法，在數(shù)據(jù)挖掘中具有里程碑的作用。Apriori算法有兩個(gè)致命的性能瓶頸:1多次掃描事務(wù)數(shù)據(jù)庫(kù)，需要很大的I/O負(fù)載對(duì)每次k循環(huán)，侯選集Ck中的每個(gè)元素都必須通過(guò)掃描數(shù)據(jù)庫(kù)一次來(lái)驗(yàn)證其是否加入Lk。假如有一個(gè)頻繁大項(xiàng)目集包含10個(gè)項(xiàng)的話，那么就至少需要掃描事務(wù)數(shù)據(jù)庫(kù)10遍。2可能產(chǎn)生龐大的侯選集由Lk-1產(chǎn)生k-侯選集Ck是指數(shù)增長(zhǎng)的，例如104個(gè)1-頻繁項(xiàng)目集就有可能產(chǎn)生接近107個(gè)元素的2-侯選集。如

12、此大的侯選集對(duì)時(shí)間和主存空間都是一種挑戰(zhàn)。Apriori算法的性能瓶頸Apriori作為經(jīng)典的頻繁項(xiàng)目集生成算法，在數(shù)據(jù)挖掘中具有 一些算法雖然仍然遵循Apriori 屬性，但由于引入了相關(guān)技術(shù)，在一定程度上改善了Apriori算法適應(yīng)性和效率。主要的改進(jìn)方法有：基于數(shù)據(jù)分割（Partition）的方法：基本原理是“在一個(gè)劃分中的支持度小于最小支持度的k-項(xiàng)集不可能是全局頻繁的”?；谏⒘校℉ash）的方法：基本原理是“在一個(gè)hash桶內(nèi)支持度小于最小支持度的k-項(xiàng)集不可能是全局頻繁的”?；诓蓸樱⊿ampling）的方法：基本原理是“通過(guò)采樣技術(shù)，評(píng)估被采樣的子集中，并依次來(lái)估計(jì)k-項(xiàng)集的全

13、局頻度”。其它方法，如動(dòng)態(tài)刪除沒(méi)有用的事務(wù)：“不包含任何Lk的事務(wù)對(duì)未來(lái)的掃描結(jié)果不會(huì)產(chǎn)生影響，因而可以刪除”。Apriori算法的改進(jìn)技術(shù) 一些算法雖然仍然遵循Apriori 屬基于數(shù)據(jù)分割的方法Apriori算法在執(zhí)行過(guò)程中是先生成候選集再剪枝，可是生成的候選集并不都是有效的。候選集的產(chǎn)生需要花費(fèi)很大的代價(jià)。把數(shù)據(jù)分割技術(shù)應(yīng)用到關(guān)聯(lián)規(guī)則挖掘中，可以改善關(guān)聯(lián)規(guī)則挖掘在大數(shù)據(jù)集中的適應(yīng)性。其基本思想：首先將大數(shù)據(jù)集從邏輯上分成互不相交的塊，每塊應(yīng)用挖掘算法（如Apriori算法）生成局部的頻繁項(xiàng)目集，然后將這些局部的頻繁項(xiàng)目集作為全局候選頻繁項(xiàng)目集，通過(guò)測(cè)試他們的支持度來(lái)得到最終的全局頻繁項(xiàng)目

14、集。其可在以下兩方面改善Apriori關(guān)聯(lián)規(guī)則挖掘算法的性能：1合理利用主存空間：數(shù)據(jù)分割將大數(shù)據(jù)集分成小的塊，為塊內(nèi)數(shù)據(jù)一次性導(dǎo)入主存提供機(jī)會(huì)。2支持并行挖掘算法：每個(gè)分塊的局部頻繁項(xiàng)目集是獨(dú)立生成的，因此提供了開(kāi)發(fā)并行數(shù)據(jù)挖掘算法的良好機(jī)制。基于數(shù)據(jù)分割的方法Apriori算法在執(zhí)行過(guò)程中是先生成候選定理 設(shè)數(shù)據(jù)集D被分割成分塊D1， D2， ， Dn，全局最小支持度為minsupport，假設(shè)對(duì)應(yīng)的全局最小支持?jǐn)?shù)為minsup_count。如果一個(gè)數(shù)據(jù)分塊Di 的局部最小支持?jǐn)?shù)記為minsup_counti (i=1，2，n)，則局部最小支持?jǐn)?shù)minsup_counti按照如下方法生成：

15、 minsup_counti = minsup_count *|Di| / |D|可以保證所有的局部頻繁項(xiàng)目集涵蓋全局頻繁項(xiàng)目集。定理 設(shè)數(shù)據(jù)集D被分割成分塊D1， D2， ， Dn，全基于散列的方法1995，Park等發(fā)現(xiàn)尋找頻繁項(xiàng)目集的主要計(jì)算是在生成2-頻繁項(xiàng)目集上。因此，Park等利用了這個(gè)性質(zhì)引入散列技術(shù)來(lái)改進(jìn)產(chǎn)生2-頻繁項(xiàng)目集的方法。例：桶地址 =（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

16、，I3L2=(I2，I3) ，(I1，I2) ，(I1，I3) 桶地址 0 1 2 3 4 5 6桶計(jì)數(shù) 2 2 4 2 2 4 4桶 I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 內(nèi) 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，I3基于散列的方法1995，Park等發(fā)現(xiàn)尋找頻繁項(xiàng)目集的主要計(jì)隨著數(shù)據(jù)庫(kù)容量的增大，重復(fù)訪問(wèn)數(shù)據(jù)庫(kù)（外存）將導(dǎo)致性能低下。因此，探索新的理論和算法來(lái)減少數(shù)據(jù)庫(kù)的掃描次數(shù)和侯選集空間占用，已經(jīng)成為近年來(lái)關(guān)聯(lián)規(guī)則挖掘研究的熱點(diǎn)

17、之一。兩個(gè)典型的方法：Close算法 FP-tree算法 項(xiàng)目集格空間理論的發(fā)展隨著數(shù)據(jù)庫(kù)容量的增大，重復(fù)訪問(wèn)數(shù)據(jù)庫(kù)（外存）將導(dǎo)致性能低下。Close算法對(duì)應(yīng)的原理一個(gè)頻繁閉合項(xiàng)目集的所有閉合子集一定是頻繁的；一個(gè)非頻繁閉合項(xiàng)目集的所有閉合超集一定是非頻繁的。什么是一個(gè)閉合的項(xiàng)目集？一個(gè)項(xiàng)目集C是閉合的，當(dāng)且僅當(dāng)對(duì)于在C中的任何元素，不可能在C中存在小于或等于它的支持度的子集。例如，C1=AB3，ABC2是閉合的； C2=AB2，ABC2不是閉合的； Close算法對(duì)應(yīng)的原理一個(gè)頻繁閉合項(xiàng)目集的所有閉合子集一定CLOSS算法的基本思路：利用頻繁閉合i_項(xiàng)目集FCi，生成頻繁閉合i+1 _項(xiàng)目集

18、FCi+1（i1）。 首先找出候選頻繁閉合1_項(xiàng)目集FCC1，通過(guò)掃描數(shù)據(jù)庫(kù)得到候選閉合項(xiàng)目集，再經(jīng)修剪得到頻繁閉合項(xiàng)目集FC1項(xiàng)目集。用FC1產(chǎn)生候選頻繁閉合2_項(xiàng)目集FCC2，再經(jīng)修剪得到頻繁閉合項(xiàng)目集FC2項(xiàng)目集。在用FC2推出FC3 ，如此繼續(xù)直到某個(gè)FCCr 為空時(shí)停止。CLOSS算法的基本思路：利用頻繁閉合i_項(xiàng)目集FCi，生成Close算法的例子掃描數(shù)據(jù)庫(kù)得到:FCC1=(A,3), (B,5), (C,4), (D,3), (E,3)； 相應(yīng)閉合項(xiàng)目集為: FCl(A)=ABC,3(計(jì)算A的閉合過(guò)程:第一項(xiàng)包含A,首先得到A的閉合為ABCD,第三項(xiàng)也包含A, 故取ABCD與第三

19、項(xiàng)的交ABC作為A的閉合，第五項(xiàng)也包含A, 故取ABC與第五項(xiàng)的交ABC作為A的閉合,這時(shí)到了最后一項(xiàng),計(jì)算完畢)。同理，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)； 相應(yīng)閉合項(xiàng)目集為:FC2 (AB)=ABC,3, FC2 (AC)=ABC,3 ； L3，L4，L5不用測(cè)，于是頻繁大項(xiàng)集為ABC 。下面是Close算法作用到右表數(shù)據(jù)集的執(zhí)行過(guò)程（假如minsup_count=3）：TIDItemset1A，B，C，D2B，C，E3A，B，C，E4B，D，

20、E5A，B，C，D樣本數(shù)據(jù)庫(kù)Close算法的例子掃描數(shù)據(jù)庫(kù)得到:下面是Close算法作用FP-tree算法的基本原理 2000年Han等提出了一個(gè)稱為FP-Tree（頻繁模式樹(shù)）的算法，該算法只進(jìn)行 2 次數(shù)據(jù)庫(kù)掃描，不使用侯選集，直接壓縮數(shù)據(jù)庫(kù)成一個(gè)FP-Tree ，然后通過(guò)該樹(shù)生成關(guān)聯(lián)規(guī)則。構(gòu)造FP-Tree的過(guò)程如下 ：按Apriori算法，掃描數(shù)據(jù)庫(kù)一次生成1-頻繁項(xiàng)目集，并按頻度降序排序，放入L列表中；創(chuàng)建根結(jié)點(diǎn)，標(biāo)志為null，掃描數(shù)據(jù)庫(kù)一次，當(dāng)?shù)玫綌?shù)據(jù)庫(kù)的一個(gè)項(xiàng)目（元組）時(shí)，就把其中的元素按L表中的次序排列，然后通過(guò)遞歸實(shí)現(xiàn)FP-Tree的增長(zhǎng)；FP-tree算法的基本原理 20

21、00年HanFP-tree算法的基本原理樣本數(shù)據(jù)庫(kù)下面看一個(gè)例子來(lái)說(shuō)明FP-Tree的增長(zhǎng)過(guò)程,最小支持度閾值為3。TIDItemset1f,a,c,d,g,i,m,p2a,b,c,f,l,m,o3b,f,h,j,o4b,c,k,s,p5a,f,c,e,l,m,p, nItemfrequencyf4c4a3b3m3p3L掃描數(shù)據(jù)庫(kù)一次生成1-頻繁項(xiàng)目集（在數(shù)據(jù)庫(kù)中出現(xiàn)3次或3次以上的），并按頻度降序排序，放入L列表中；TIDItemset1f,c,a,m,p2f,c,a,b,m3f,b4c,b,p5f,c,a,m,p(1-頻繁項(xiàng)目集)FP-tree算法的基本原理樣本數(shù)據(jù)庫(kù)下面看一個(gè)例子來(lái)說(shuō)明F

22、FP-tree算法的基本原理樣本數(shù)據(jù)庫(kù)TIDItemset1f,c,a,m,p2f,c,a,b,m3f,b4c,b,p5f,c,a,m,pItem(fre)f4c4a3b3m3p3LT1T2T3T4掃描數(shù)據(jù)庫(kù),依次增長(zhǎng)FP-tree，并改變支持?jǐn)?shù)f:1c:1a:1m:1NULLp:1f:2c:2a:2m:1NULLb:1p:1m:1f:3c:2a:2m:1NULLb:1p:1m:1b:1f:3c:2a:2m:1NULLb:1p:1m:1b:1c:1b:1p:1f:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5FP-tree算法的基本原理樣本數(shù)據(jù)庫(kù)TIDItemset

23、1FP-tree算法的基本原理Item(fre)f4c4a3b3m3p3L建立索引f:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5FP-tree算法的基本原理Item(fre)f4c4a3b 用FP-Tree挖掘頻繁集的基本思想是分而制之，即使用FP-Tree 遞歸增長(zhǎng)頻繁集的方法：對(duì)每個(gè)項(xiàng)，生成其條件模式庫(kù)，然后生成其條件FP-Tree；對(duì)每個(gè)新生成的條件FP-Tree，重復(fù)此步驟；直到結(jié)果FP-Tree為空，或只含唯一的一個(gè)路徑，此路徑的每個(gè)子路徑對(duì)應(yīng)的項(xiàng)目集都是頻繁集。 用FP-Tree挖掘頻繁集的基本思想是分而制從FP-Tree建立條件模式庫(kù)對(duì)應(yīng)的條件模式

24、庫(kù)Item條件模式庫(kù)cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1FP-treeItem(fre)f4c4a3b3m3p3Lf:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5從FP-Tree建立條件模式庫(kù)對(duì)應(yīng)的條件模式庫(kù)Item條件模用條件模式庫(kù)建立對(duì)應(yīng)的條件FP-Treem-條件模式庫(kù)Item條件模式庫(kù)cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:3c:3a:3NULLm-條件FP-TreeItem(fre)f4c4a3b3m3p3Lf:4c:3

25、a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5用條件模式庫(kù)建立對(duì)應(yīng)的條件FP-Treem-條件Item條件Item條件模式庫(kù)條件FP-Treep(fcam:2),(cb:1)(c:3)|pm(fca:2),(fcab:1)(f:3,c:3,a:3)|mb(fca:1),(f:1),(c:1)Emptyafc:3(f:3,c:3)|acf:3(f:3|cfEmptyEmptym-條件FP-Treec:3NULLf:3c:3a:3NULLNULLf:3c:3NULLf:3NULLp-條件FP-Treec-條件FP-Treea-條件FP-Treeb-條件FP-TreeNULLf-

26、條件FP-TreeItem條件模式庫(kù)條件FP-Treep(fcam:2),(用條件FP-Tree挖掘頻繁項(xiàng)集m-條件FP-Treec:3NULLf:3c:3a:3NULLNULLf:3c:3NULLf:3NULLp-條件FP-Treec-條件FP-Treea-條件FP-Treeb-條件FP-TreeNULLf-條件FP-Tree得到的頻繁項(xiàng)目集合，用條件FP-Tree挖掘頻繁項(xiàng)集m-條件FP-Treec:3多層次關(guān)聯(lián)規(guī)則挖掘根據(jù)規(guī)則中涉及到的層次，多層次關(guān)聯(lián)規(guī)則可以分為：同層關(guān)聯(lián)規(guī)則：如果一個(gè)關(guān)聯(lián)規(guī)則對(duì)應(yīng)的項(xiàng)目是同一個(gè)粒度層次，那么它是同層關(guān)聯(lián)規(guī)則。如“牛奶面包”和“羽絨服酸奶”都是同層關(guān)聯(lián)規(guī)

27、則;關(guān)聯(lián)規(guī)則挖掘中的一些更深入的問(wèn)題日用品服裝食品夏季服裝冬季服裝面包牛奶羽絨服大衣品牌1品牌2鮮奶酸奶品牌3品牌4層間關(guān)聯(lián)規(guī)則：如果在不同的粒度層次上考慮問(wèn)題，那么可能得到的是層間關(guān)聯(lián)規(guī)則。如“夏季服裝酸奶”都是層間關(guān)聯(lián)規(guī)則;多層次關(guān)聯(lián)規(guī)則挖掘根據(jù)規(guī)則中涉及到的層次，多層次關(guān)聯(lián)規(guī)則可以多層次關(guān)聯(lián)規(guī)則挖掘多層次關(guān)聯(lián)規(guī)則挖掘的度量方法可以沿用 “支持度-可信度”的框架。不過(guò)，多層次關(guān)聯(lián)規(guī)則挖掘有兩種基本的設(shè)置支持度的策略：統(tǒng)一的最小支持度：算法實(shí)現(xiàn)容易，而且很容易支持層間的關(guān)聯(lián)規(guī)則生成。但是弊端也是顯然的：不同層次可能考慮問(wèn)題的精度不同、面向的用戶群不同對(duì)于一些用戶，可能覺(jué)得支持度太小，產(chǎn)生了過(guò)多不感興趣的規(guī)則。而對(duì)于另外的用戶來(lái)說(shuō)，又認(rèn)為支持度太大，有用信息丟失過(guò)多。多層次關(guān)聯(lián)規(guī)則挖掘多層次關(guān)聯(lián)規(guī)則挖掘的度量方法可以沿用 “支不同層次使用不同的最小支持度：每個(gè)層次都有自己的最小支持度。較低層次的最小支持度相對(duì)較小，而較高層次的最小支持度相對(duì)較大。這種方法增加了挖掘的靈活性。但是，也留下了許多相關(guān)問(wèn)題需要解決：首先，不同層次間的支持度應(yīng)