數(shù)據(jù)關(guān)聯(lián)分析

1、第7章 數(shù)據(jù)關(guān)聯(lián)分析7.1基 本 概 念7.2頻繁項集產(chǎn)生7.3規(guī)則產(chǎn)生7.4頻繁項集的緊湊表示7.5產(chǎn)生頻繁項集的其他方法7.6FP-growth算法7.7關(guān) 聯(lián) 評 估17.1基本概念 關(guān)聯(lián)分析關(guān)聯(lián)分析（association analysis）用于發(fā)現(xiàn)隱藏在大型數(shù)據(jù)集中的令人）用于發(fā)現(xiàn)隱藏在大型數(shù)據(jù)集中的令人感興趣的聯(lián)系，所發(fā)現(xiàn)的模式通常用關(guān)聯(lián)規(guī)則（感興趣的聯(lián)系，所發(fā)現(xiàn)的模式通常用關(guān)聯(lián)規(guī)則（association rule）或頻繁）或頻繁項集的形式表示項集的形式表示。關(guān)于。關(guān)于關(guān)聯(lián)規(guī)則的幾個概念：關(guān)聯(lián)規(guī)則的幾個概念：項集項集：項目：項目的集合，包含的集合，包含k個項的項集稱為個項的項集稱

2、為k-項集；項集；支持度（支持度（support）：數(shù)據(jù)庫：數(shù)據(jù)庫中含有這個項集的所有項目在中含有這個項集的所有項目在事事務(wù)務(wù)集中集中所占的比例。所占的比例。置信度（置信度（confidence）：出現(xiàn)：出現(xiàn)項集項集A的事務(wù)集的事務(wù)集D中，項集中，項集B出現(xiàn)出現(xiàn)的概率。的概率。頻繁項集頻繁項集：支持：支持度大于或等于度大于或等于min_sup的的項集。項集。2 關(guān)聯(lián)規(guī)則挖掘的兩個步驟：關(guān)聯(lián)規(guī)則挖掘的兩個步驟：頻繁項集產(chǎn)生（支持度測試）。其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾頻繁項集產(chǎn)生（支持度測試）。其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項集，即頻繁項集。值的所有項集，即頻繁項集。規(guī)則產(chǎn)生（置信度測試）。

3、其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項集中規(guī)則產(chǎn)生（置信度測試）。其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項集中提取所有高置信度（大于等于最小置信度閾值）的關(guān)聯(lián)規(guī)則，即提取所有高置信度（大于等于最小置信度閾值）的關(guān)聯(lián)規(guī)則，即強(qiáng)關(guān)聯(lián)規(guī)則。強(qiáng)關(guān)聯(lián)規(guī)則。 在上述兩個步驟中，第一步驟是關(guān)鍵，它將影響整個關(guān)聯(lián)規(guī)則挖掘在上述兩個步驟中，第一步驟是關(guān)鍵，它將影響整個關(guān)聯(lián)規(guī)則挖掘算法的效率。因此，關(guān)聯(lián)規(guī)則挖掘算法的核心是頻繁項集產(chǎn)生。算法的效率。因此，關(guān)聯(lián)規(guī)則挖掘算法的核心是頻繁項集產(chǎn)生。7.1基本概念3 格結(jié)構(gòu)（格結(jié)構(gòu)（lattice structure）常常被用來枚舉所有可能的項集。圖）常常被用來枚舉所有可能的項集。圖中中顯示顯

4、示的的是是I=a，b，c，d，e的項集格的項集格。包含。包含k個項的數(shù)據(jù)個項的數(shù)據(jù)集最多產(chǎn)生集最多產(chǎn)生2k-1 個頻繁個頻繁項集，不包括項集，不包括空集?？占?。7.2頻繁項集產(chǎn)生4 發(fā)現(xiàn)頻繁項集的一種原始方法是確定格結(jié)構(gòu)中每個候選項集的支持度發(fā)現(xiàn)頻繁項集的一種原始方法是確定格結(jié)構(gòu)中每個候選項集的支持度計數(shù)計數(shù)。這必須這必須比較每個比較每個候選項集與每個候選項集與每個事務(wù)。如候選事務(wù)。如候選項集包含在事務(wù)中，項集包含在事務(wù)中，則候選項集的支持度計數(shù)增加則候選項集的支持度計數(shù)增加。如。如，由于項集，由于項集 Milk，Bread 出現(xiàn)在事務(wù)出現(xiàn)在事務(wù)1，4，5中，其支持度計數(shù)將增加中，其支持度計數(shù)

5、將增加3次次。這種比較開銷大。這種比較開銷大。7.2頻繁項集產(chǎn)生57.2.1先驗原理 先驗原理先驗原理是減少候選項集的數(shù)量（是減少候選項集的數(shù)量（M）的方法之一。）的方法之一。 其基本思想是其基本思想是：如果一個項集是頻繁的，則它的所有子集一定也是：如果一個項集是頻繁的，則它的所有子集一定也是頻繁的。例如，頻繁的。例如，假定假定 c，d，e是頻繁項是頻繁項集，顯然任何包含項集集，顯然任何包含項集c，d，e的事務(wù)一定包含它的子集的事務(wù)一定包含它的子集c，d ， c，e ， d，e， c ， d和和e。這樣，如果。這樣，如果c，d，e是頻繁的，則它的所有子集一定也是頻繁是頻繁的，則它的所有子集一定

6、也是頻繁的。的。 反之，反之，如項集如項集是非頻繁的，則它的所有超集也一定是非頻繁的。是非頻繁的，則它的所有超集也一定是非頻繁的。7.2頻繁項集產(chǎn)生67.2.1先驗原理 如圖所示，一旦發(fā)現(xiàn)如圖所示，一旦發(fā)現(xiàn)a，b是非頻繁的，則整個包含是非頻繁的，則整個包含a，b超集的子超集的子圖可以被立即剪枝。這種基于支持度度量修剪指數(shù)搜索空間的策略稱為基圖可以被立即剪枝。這種基于支持度度量修剪指數(shù)搜索空間的策略稱為基于支持度的剪枝。于支持度的剪枝。7.2頻繁項集產(chǎn)生77.2.2Apriori算法的頻繁項集產(chǎn)生 Apriori算法算法是一種最具影響力的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算是一種最具影響力的挖掘布爾關(guān)聯(lián)

7、規(guī)則頻繁項集的算法。法。Apriori的命名由來是因為使用了頻繁項集性質(zhì)的先驗知識，即的命名由來是因為使用了頻繁項集性質(zhì)的先驗知識，即Apriori性質(zhì)。性質(zhì)。Apriori性質(zhì)的內(nèi)容是：頻繁項集的所有非空子集也必須是頻繁性質(zhì)的內(nèi)容是：頻繁項集的所有非空子集也必須是頻繁的。該性質(zhì)通過減少搜索空間來提高頻繁項集逐層產(chǎn)生的效率。的。該性質(zhì)通過減少搜索空間來提高頻繁項集逐層產(chǎn)生的效率。 Apriori算法利用算法利用Apriori性質(zhì)，通過逐層搜索的迭代方法，將性質(zhì)，通過逐層搜索的迭代方法，將k-項集用項集用于探索（于探索（k+1）-項集，來窮盡數(shù)據(jù)集中的所有頻繁項集。項集，來窮盡數(shù)據(jù)集中的所有頻繁

8、項集。7.2頻繁項集產(chǎn)生87.2.2Apriori算法的頻繁項集產(chǎn)生 特點特點：它是一個逐層算法，即從頻繁它是一個逐層算法，即從頻繁1-項集到最長的頻繁項集，它每次遍項集到最長的頻繁項集，它每次遍歷項集格中的一層。先找到頻繁歷項集格中的一層。先找到頻繁1-項集集合項集集合Ll，然后用，然后用Ll找到頻繁找到頻繁2-項集集合項集集合L2，接著用，接著用L2找找L3，直到找不到頻繁，直到找不到頻繁k-項集，找每個項集，找每個Lk需要需要一次數(shù)據(jù)庫掃描；一次數(shù)據(jù)庫掃描；它使用產(chǎn)生它使用產(chǎn)生-測試策略來發(fā)現(xiàn)頻繁項集。在每次迭代之后，新的候選測試策略來發(fā)現(xiàn)頻繁項集。在每次迭代之后，新的候選項集由前一次迭

9、代發(fā)現(xiàn)的頻繁項集產(chǎn)生，然后對每個候選的支持度項集由前一次迭代發(fā)現(xiàn)的頻繁項集產(chǎn)生，然后對每個候選的支持度進(jìn)行計數(shù)，并與最小支持度閾值進(jìn)行比較。該算法需要的總迭代次進(jìn)行計數(shù)，并與最小支持度閾值進(jìn)行比較。該算法需要的總迭代次數(shù)是數(shù)是kmax+1，其中，其中kmax是頻繁項集的最大長度。是頻繁項集的最大長度。7.2頻繁項集產(chǎn)生97.2.2Apriori算法的頻繁項集產(chǎn)生 AprioriApriori算法的主要步驟由連接步和剪枝步組成。算法的主要步驟由連接步和剪枝步組成。連接步連接步。為找出為找出Lk，通過，通過Lk-1與自身連接產(chǎn)生候選與自身連接產(chǎn)生候選k-項集的項集的集合集合，記記作作Ck。設(shè)。設(shè)l

10、1和和l2是是Lk-1中的項集中的項集。lij表示表示li的第的第j項。假定項。假定事務(wù)或項集中事務(wù)或項集中的項按字典次序的項按字典次序排序，排序，使得使得li1li2.lik-1。執(zhí)行連接。執(zhí)行連接Lk-1 Lk-1；其中其中Lk-1的元素是可連接的，的元素是可連接的，如它們?nèi)缢鼈兦埃ㄇ埃╧-2）個項相同）個項相同，即即Lk-1的元的元素素l1和和l2是可連接的，是可連接的，如（如（l11=l21） （l12=l22） . （l1k-2l2k-2） （l1k-1l2k-1）。條件）。條件l1k-1l2k-1是簡單地確保不產(chǎn)生是簡單地確保不產(chǎn)生重復(fù)。連接重復(fù)。連接l1和和l2產(chǎn)生的結(jié)果項集是產(chǎn)

11、生的結(jié)果項集是l11，l12，.l1k-1，l2k-1。7.2頻繁項集產(chǎn)生107.2.2Apriori算法的頻繁項集產(chǎn)生剪枝步。剪枝步。 Ck是是Lk的超集的超集，即即Ck的成員可以是頻繁的，也可以不是頻的成員可以是頻繁的，也可以不是頻繁的，但所有頻繁繁的，但所有頻繁k-項集都包含在項集都包含在Ck中。掃描數(shù)據(jù)庫，確定中。掃描數(shù)據(jù)庫，確定Ck中每中每個候選的支持度計數(shù)，從而確定個候選的支持度計數(shù)，從而確定Lk（即根據(jù)定義，計數(shù)值不小于最（即根據(jù)定義，計數(shù)值不小于最小支持度計數(shù)的所有候選都是頻繁的，從而屬于小支持度計數(shù)的所有候選都是頻繁的，從而屬于Lk）。然而，）。然而，Ck可可能很大，因此所涉

12、及的計算量就很大。為了壓縮能很大，因此所涉及的計算量就很大。為了壓縮Ck，可以，可以用用Apriori性質(zhì)，性質(zhì)，即即非非頻繁的（頻繁的（k-1）-項集都不是頻繁項集都不是頻繁k-項集的項集的子集，如候選子集，如候選k-項集的（項集的（k-1）-子集不在子集不在Lk-1中，則該候選也不可能是頻繁的，中，則該候選也不可能是頻繁的，從而從而從從Ck中刪除。這種子集測試中刪除。這種子集測試可使用可使用所有頻繁項集的散列樹快速完成。所有頻繁項集的散列樹快速完成。7.2頻繁項集產(chǎn)生117.2.2Apriori算法的頻繁項集產(chǎn)生 下面下面舉舉一個具體例子。該例基于表中的一個具體例子。該例基于表中的AllE

13、lectronics的事務(wù)數(shù)據(jù)庫的事務(wù)數(shù)據(jù)庫D。該數(shù)據(jù)庫有該數(shù)據(jù)庫有9個事務(wù)個事務(wù)，假定事務(wù)中的項按字典次序存放。假定事務(wù)中的項按字典次序存放。7.2頻繁項集產(chǎn)生127.2.2Apriori算法的頻繁項集產(chǎn)生 使用圖使用圖來來解釋解釋Apriori算法發(fā)現(xiàn)算法發(fā)現(xiàn)D中的頻繁項集。中的頻繁項集。7.2頻繁項集產(chǎn)生137.2.2Apriori算法的頻繁項集產(chǎn)生 挖掘布爾關(guān)聯(lián)規(guī)則發(fā)現(xiàn)頻繁項集的挖掘布爾關(guān)聯(lián)規(guī)則發(fā)現(xiàn)頻繁項集的AprioriApriori算法如下。算法如下。 算法算法：Apriori。使用逐層迭代方法基于候選產(chǎn)生找出頻繁項集。使用逐層迭代方法基于候選產(chǎn)生找出頻繁項集。 輸入輸入：事務(wù)數(shù)據(jù)

14、庫：事務(wù)數(shù)據(jù)庫D；最小支持度閾值；最小支持度閾值min_sup。 輸出輸出：D中的頻繁項集中的頻繁項集L。 方法方法：L1=find_frequent_1_itemsets（D）；）；for（k=2；Lk-1；k+） Ck=apriori_gen（Lk-1）；）； for each 事務(wù)事務(wù)tD /掃描掃描D，進(jìn)行計數(shù)，進(jìn)行計數(shù) Ct=subset（Ck，t）；）； /得到得到t的子集，它們是候選的子集，它們是候選 for each 候選候選cCt c.count+； Lk=cCk | c.countmin_sup；return L=k Lk；7.2頻繁項集產(chǎn)生147.2.2Apriori算法

15、的頻繁項集產(chǎn)生procedure apriori_gen（Lk-1：frequent（k-1）-itemsets）for each 項集項集l1 Lk-1 for each 項集項集l2 Lk-1 if（l11=l21） . （l1k-2l2k-2） （l1k-1l2k-2）then c= l1 l2； /連接步：產(chǎn)生候選連接步：產(chǎn)生候選 if has_infrequent_subset（c，Lk-1） then delete c； /剪枝步：刪除非頻繁的候選剪枝步：刪除非頻繁的候選 else add c to Ck；return Ck；procedure has_infrequent_sub

16、set(c：candidate k-itemsets；Lk-1：frequent(k-1)-itemsets)/使用使用Apriori知識知識for each（k-1）-subset s of c if s Lk-1 then return TRUE； return FALSE；7.2頻繁項集產(chǎn)生157.2.3支持度計數(shù) 支持度計數(shù)用以支持度計數(shù)用以確定在確定在apriori-gen函數(shù)的候選項剪枝步驟保留下來的函數(shù)的候選項剪枝步驟保留下來的每個候選項集出現(xiàn)的頻繁程度。每個候選項集出現(xiàn)的頻繁程度。 計算支持度的主要方法有計算支持度的主要方法有兩種兩種：一是一是將每個事務(wù)與所有候選項集進(jìn)行比較，

17、并且更新包含在事務(wù)中的將每個事務(wù)與所有候選項集進(jìn)行比較，并且更新包含在事務(wù)中的候選項集的支持度計數(shù)。這種方法的計算候選項集的支持度計數(shù)。這種方法的計算成本很高成本很高，尤其當(dāng)事務(wù)和候，尤其當(dāng)事務(wù)和候選項集的數(shù)目都很大時。選項集的數(shù)目都很大時。或或枚舉枚舉每個每個事務(wù)包含事務(wù)包含的項集，的項集，并利用并利用其其更新更新對應(yīng)的候選項集的支持度。對應(yīng)的候選項集的支持度。7.2頻繁項集產(chǎn)生167.2.3支持度計數(shù) 如圖顯示的是枚舉事務(wù)如圖顯示的是枚舉事務(wù)t中所有中所有3-項集的系統(tǒng)的方法。假定每個項集項集的系統(tǒng)的方法。假定每個項集中的項都以遞增的字典次序排列，則項集可以這樣枚舉：先指定最小項，中的項都

18、以遞增的字典次序排列，則項集可以這樣枚舉：先指定最小項，其后跟隨較大的項。其后跟隨較大的項。7.2頻繁項集產(chǎn)生177.2.3支持度計數(shù) 如如，給定，給定t=1，2，3，5，6，所有，所有3-項集一定以項項集一定以項1、2或或3開始。不開始。不必構(gòu)造以必構(gòu)造以5或或6開始的開始的3-項集。項集。圖中第一層的前綴結(jié)構(gòu)描述了指定包含在事圖中第一層的前綴結(jié)構(gòu)描述了指定包含在事務(wù)務(wù)t中的中的3-項集的第一項的方法項集的第一項的方法。如。如1 2 3 5 6的的3-項集項集，以，以1開始，后隨兩個開始，后隨兩個取自集合取自集合2，3，5，6的項的項。確定第一項后。確定第一項后，第二層的前綴結(jié)構(gòu)表示選擇，第

19、二層的前綴結(jié)構(gòu)表示選擇第二項的方法第二項的方法。如。如：1 2 3 5 6表示以表示以1，2為前綴，后隨項為前綴，后隨項3、5或或6的項集。的項集。最后，第三層的前綴結(jié)構(gòu)顯示了事務(wù)最后，第三層的前綴結(jié)構(gòu)顯示了事務(wù)t包含的所有的包含的所有的3-項集項集。如。如，以，以1，2為前綴的為前綴的3-項集是項集是1，2，3，1，2，5和和1，2，6；而以；而以2，3為前綴為前綴的的3-項集是項集是2，3，5和和2，3，6。7.2頻繁項集產(chǎn)生187.2.3支持度計數(shù) 在在Apriori算法中，候選項集劃分為不同的桶，并存放在算法中，候選項集劃分為不同的桶，并存放在Hash樹中。樹中。在支持度計數(shù)期間，包含

20、在事務(wù)中的項集也散列到相應(yīng)的桶中。這種方在支持度計數(shù)期間，包含在事務(wù)中的項集也散列到相應(yīng)的桶中。這種方法不是將事務(wù)中的每個項集與所有的候選項集進(jìn)行比較，而是將它與同法不是將事務(wù)中的每個項集與所有的候選項集進(jìn)行比較，而是將它與同一桶內(nèi)候選項集進(jìn)行匹配一桶內(nèi)候選項集進(jìn)行匹配。7.2頻繁項集產(chǎn)生197.2.3支持度計數(shù) 上圖是一棵上圖是一棵Hash樹結(jié)構(gòu)的例子。樹的每個內(nèi)部結(jié)點都使用樹結(jié)構(gòu)的例子。樹的每個內(nèi)部結(jié)點都使用Hash函數(shù)函數(shù)h(p)=p mod 3來確定應(yīng)當(dāng)沿著當(dāng)前結(jié)點的哪個分支向下來確定應(yīng)當(dāng)沿著當(dāng)前結(jié)點的哪個分支向下。如。如，項，項1，4和和7應(yīng)當(dāng)散列到相同的分支（即最左分支），因為除以

21、應(yīng)當(dāng)散列到相同的分支（即最左分支），因為除以3之后它們都具有相之后它們都具有相同的余數(shù)。所有的候選項集都存放在同的余數(shù)。所有的候選項集都存放在Hash樹的葉結(jié)點中。圖中顯示的樹的葉結(jié)點中。圖中顯示的Hash樹包含樹包含15個候選個候選3-項集，即項集，即1，4，5，1，2，4，4，5，7，1，2，5，4，5，8，1，5，9，1，3，6，2，3，4，5，6，7，3，4，5，3，5，6，3，5，7，6，8，9，3，6，7，3，6，8，分，分布在布在9個葉結(jié)點中。個葉結(jié)點中。7.2頻繁項集產(chǎn)生207.2.3支持度計數(shù) 考慮一個事務(wù)考慮一個事務(wù)t=1，2，3，5，6。為了更新候選項集的支持度計數(shù)，。為

22、了更新候選項集的支持度計數(shù)，必須這樣遍歷必須這樣遍歷Hash樹：所有包含屬于事務(wù)樹：所有包含屬于事務(wù)t的候選的候選3-項集的葉結(jié)點至少訪項集的葉結(jié)點至少訪問一次。例如，在根結(jié)點散列項問一次。例如，在根結(jié)點散列項1之后，散列事務(wù)的項之后，散列事務(wù)的項2，3和和5。項。項2和和5散散列到中間子女，而列到中間子女，而3散列到右子女，如圖所示。繼續(xù)該過程，直至到達(dá)散列到右子女，如圖所示。繼續(xù)該過程，直至到達(dá)Hash樹的葉結(jié)點。樹的葉結(jié)點。7.2頻繁項集產(chǎn)生217.2.4計算復(fù)雜度 AprioriApriori算法的計算復(fù)雜度受如下因素影響：算法的計算復(fù)雜度受如下因素影響：支持度閾值支持度閾值。支持。支

23、持度度閾值閾值影響影響頻繁項集數(shù)量。頻繁項集數(shù)量。項數(shù)（維數(shù)）。隨著項數(shù)的增加，需要更多的空間來存儲項的支持項數(shù)（維數(shù)）。隨著項數(shù)的增加，需要更多的空間來存儲項的支持度計數(shù)。度計數(shù)。如頻繁如頻繁項集的數(shù)目也隨著數(shù)據(jù)項數(shù)增加而增長，則由于算項集的數(shù)目也隨著數(shù)據(jù)項數(shù)增加而增長，則由于算法產(chǎn)生的候選項集更多，計算量和法產(chǎn)生的候選項集更多，計算量和I/O開銷將增加。開銷將增加。事務(wù)數(shù)事務(wù)數(shù)。算法。算法反復(fù)掃描數(shù)據(jù)集反復(fù)掃描數(shù)據(jù)集，運行時間，運行時間隨著事務(wù)數(shù)增加而增加。隨著事務(wù)數(shù)增加而增加。事務(wù)的平均寬度。對于密集數(shù)據(jù)集，事務(wù)的平均寬度可能很大，這事務(wù)的平均寬度。對于密集數(shù)據(jù)集，事務(wù)的平均寬度可能很大

24、，這將影響將影響Apriori算法的復(fù)雜度。算法的復(fù)雜度。7.2頻繁項集產(chǎn)生227.2.4計算復(fù)雜度7.2頻繁項集產(chǎn)生23 因為由頻繁項集的項組成的關(guān)聯(lián)規(guī)則的支持度大于等于最小支持度因為由頻繁項集的項組成的關(guān)聯(lián)規(guī)則的支持度大于等于最小支持度閾值，所以規(guī)則產(chǎn)生過程就是在由頻繁項集的項組成的所有關(guān)聯(lián)規(guī)則閾值，所以規(guī)則產(chǎn)生過程就是在由頻繁項集的項組成的所有關(guān)聯(lián)規(guī)則中，找出所有置信度大于等于最小置信度閾值的強(qiáng)關(guān)聯(lián)規(guī)則。中，找出所有置信度大于等于最小置信度閾值的強(qiáng)關(guān)聯(lián)規(guī)則。 計算關(guān)聯(lián)規(guī)則的置信度并不需要再次掃描事務(wù)數(shù)據(jù)庫。每個頻繁計算關(guān)聯(lián)規(guī)則的置信度并不需要再次掃描事務(wù)數(shù)據(jù)庫。每個頻繁k-項集能產(chǎn)生最多

25、項集能產(chǎn)生最多2k-2個關(guān)聯(lián)規(guī)則。個關(guān)聯(lián)規(guī)則。7.3規(guī)則產(chǎn)生247.3.1基本步驟 規(guī)則產(chǎn)生的基本步驟如下：規(guī)則產(chǎn)生的基本步驟如下：（1）對于每個頻繁項集）對于每個頻繁項集l，產(chǎn)生，產(chǎn)生l的所有非空子集；的所有非空子集；（2）對于）對于l的每個非空子集的每個非空子集s，如果，如果則輸出規(guī)則則輸出規(guī)則“ ”。其中。其中min_conf是最小置信度閾值。是最小置信度閾值。7.3規(guī)則產(chǎn)生257.3.1基本步驟 例如例如，AllElectronics事務(wù)事務(wù)數(shù)據(jù)庫數(shù)據(jù)庫，包含包含頻繁項集頻繁項集X=I1，I2，I5，可可由由X產(chǎn)生產(chǎn)生6個候選關(guān)聯(lián)規(guī)則，即個候選關(guān)聯(lián)規(guī)則，即X的非空子集：的非空子集：I1

26、，I2，I1，I5，I2，I5，I1，I2和和I5。結(jié)果關(guān)聯(lián)規(guī)則如下，每個都列出置信度。結(jié)果關(guān)聯(lián)規(guī)則如下，每個都列出置信度。 如果最小置信度閾值為如果最小置信度閾值為70，則只有，則只有2、3和最后一個規(guī)則可以輸出，和最后一個規(guī)則可以輸出，因為只有這些是強(qiáng)的因為只有這些是強(qiáng)的。7.3規(guī)則產(chǎn)生267.3.1Apriori算法中規(guī)則的產(chǎn)生 Apriori算法使用一種逐層方法來產(chǎn)生關(guān)聯(lián)規(guī)則，其中每層對應(yīng)于規(guī)算法使用一種逐層方法來產(chǎn)生關(guān)聯(lián)規(guī)則，其中每層對應(yīng)于規(guī)則后件中的項數(shù)。則后件中的項數(shù)。首先首先，提取規(guī)則后件只含一個項的所有高置信度規(guī)則，提取規(guī)則后件只含一個項的所有高置信度規(guī)則，其次其次使用這些規(guī)

27、則來產(chǎn)生新的候選規(guī)則。使用這些規(guī)則來產(chǎn)生新的候選規(guī)則。7.3規(guī)則產(chǎn)生277.3.1Apriori算法中規(guī)則的產(chǎn)生 例如，例如， acdb和和abdc是兩個高置信度的規(guī)則，則通過合并是兩個高置信度的規(guī)則，則通過合并這兩個規(guī)則的后件產(chǎn)生候選規(guī)則這兩個規(guī)則的后件產(chǎn)生候選規(guī)則adbc。圖。圖中中顯示了由頻繁項集產(chǎn)生顯示了由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則的格結(jié)構(gòu)。如果格中的任意結(jié)點具有低置信度，則關(guān)聯(lián)規(guī)則的格結(jié)構(gòu)。如果格中的任意結(jié)點具有低置信度，則可立即可立即剪掉剪掉該結(jié)點生成的整個子圖。假設(shè)規(guī)則該結(jié)點生成的整個子圖。假設(shè)規(guī)則bcda具有低置信度，則可以丟棄具有低置信度，則可以丟棄后件包含后件包含a的所有規(guī)則，包

28、括的所有規(guī)則，包括cdab，bdac，bcad和和dabc等等。Apriori算法中規(guī)則產(chǎn)生過程與頻繁項集產(chǎn)生過程類似，二算法中規(guī)則產(chǎn)生過程與頻繁項集產(chǎn)生過程類似，二者唯一的不同是，在規(guī)則產(chǎn)生時，不必再次掃描數(shù)據(jù)者唯一的不同是，在規(guī)則產(chǎn)生時，不必再次掃描數(shù)據(jù)集計算集計算候選規(guī)則的候選規(guī)則的置信度，置信度，而使用而使用頻繁項集產(chǎn)生時計算的支持度計數(shù)來頻繁項集產(chǎn)生時計算的支持度計數(shù)來確定規(guī)則確定規(guī)則的置信度的置信度。7.3規(guī)則產(chǎn)生28 實踐中，由事務(wù)數(shù)據(jù)集產(chǎn)生的頻繁項集的數(shù)量可能非常大。因此，實踐中，由事務(wù)數(shù)據(jù)集產(chǎn)生的頻繁項集的數(shù)量可能非常大。因此，從中識別出可以推導(dǎo)出其他所有的頻繁項集的、較小的

29、、具有代表性的從中識別出可以推導(dǎo)出其他所有的頻繁項集的、較小的、具有代表性的項集是非常有用的。項集是非常有用的。 下面介紹兩種具有代表性的項集：下面介紹兩種具有代表性的項集：最大頻繁項集最大頻繁項集閉頻繁項集閉頻繁項集7.4頻繁項集的緊湊表示297.4.1最大頻繁項集 最大頻繁項集：直接超集都不是頻繁的。7.4頻繁項集的緊湊表示307.4.1最大頻繁項集 上上圖所示是圖所示是項集格。格中的項集分為兩組：頻繁項集和非頻繁項集。項集格。格中的項集分為兩組：頻繁項集和非頻繁項集。虛線表示頻繁項集的邊界。位于邊界上方的每個項集都是頻繁的，而位于虛線表示頻繁項集的邊界。位于邊界上方的每個項集都是頻繁的，

30、而位于邊界下方的項集（陰影結(jié)點）都是非頻繁的。在邊界邊界下方的項集（陰影結(jié)點）都是非頻繁的。在邊界附近結(jié)點附近結(jié)點中，中，a，d，a，c，e和和b，c，d，e都是最大頻繁項集，因為它們的直接超集都是非頻都是最大頻繁項集，因為它們的直接超集都是非頻繁的繁的。如。如，項集，項集a，d是最大頻繁的，因為它的所有直接超集是最大頻繁的，因為它的所有直接超集a，b，d ，a，c，d和和a，d，e都是非頻繁的；相反，項集都是非頻繁的；相反，項集a，c不是最大的，因為不是最大的，因為它的一個直接超集它的一個直接超集a，c，e是頻繁的是頻繁的。最大。最大頻繁項集有效地提供了頻繁項頻繁項集有效地提供了頻繁項集的緊

31、湊表示集的緊湊表示。最大。最大頻繁項集形成了頻繁項集形成了可導(dǎo)出可導(dǎo)出所有頻繁項集的最小的項集的所有頻繁項集的最小的項集的集合。集合。7.4頻繁項集的緊湊表示317.4.2閉頻繁項集 閉項集閉項集：直接：直接超集都不具有和它相同的支持度計數(shù)超集都不具有和它相同的支持度計數(shù)。閉閉頻繁項集頻繁項集：支：支持持度大于或等于最小支持度度大于或等于最小支持度閾值閾值的閉項集的閉項集。7.4頻繁項集的緊湊表示327.4.2閉頻繁項集 閉頻繁項集示例如閉頻繁項集示例如上上圖。為了更好地解釋每個項集的支持度計數(shù)，格圖。為了更好地解釋每個項集的支持度計數(shù)，格中每個結(jié)點（項集）都標(biāo)出了與它相關(guān)聯(lián)的事務(wù)的中每個結(jié)點

32、（項集）都標(biāo)出了與它相關(guān)聯(lián)的事務(wù)的ID。例如，由于結(jié)點。例如，由于結(jié)點b，c與與事務(wù)事務(wù)ID 1，2和和3相關(guān)聯(lián)，因此它的支持度計數(shù)為相關(guān)聯(lián)，因此它的支持度計數(shù)為3。從給定的事務(wù)可以。從給定的事務(wù)可以看出，包含看出，包含b的每個事務(wù)也包含的每個事務(wù)也包含c，因此，由于，因此，由于b和和b，c的支持度是相同的支持度是相同的，所以的，所以b不是閉項集。同樣，由于不是閉項集。同樣，由于c出現(xiàn)在所有包含出現(xiàn)在所有包含a和和d的事務(wù)中，所的事務(wù)中，所以項集以項集a，d不是閉的。另一方面，不是閉的。另一方面， b，c是閉項集，因為它的支持度計是閉項集，因為它的支持度計數(shù)與它的任何超集都不同。數(shù)與它的任何超

33、集都不同。7.4頻繁項集的緊湊表示33 Apriori算法通過使用先驗原理對指數(shù)搜索空間進(jìn)行剪枝，成功地處理算法通過使用先驗原理對指數(shù)搜索空間進(jìn)行剪枝，成功地處理了頻繁項集產(chǎn)生的組合爆炸問題。雖然顯著提高了性能，但該算法還是會了頻繁項集產(chǎn)生的組合爆炸問題。雖然顯著提高了性能，但該算法還是會導(dǎo)致不可低估的導(dǎo)致不可低估的I/O開銷，因為它需要多次掃描事務(wù)數(shù)據(jù)集。此外，對于稠開銷，因為它需要多次掃描事務(wù)數(shù)據(jù)集。此外，對于稠密數(shù)據(jù)集，由于事務(wù)數(shù)據(jù)寬度的增加，密數(shù)據(jù)集，由于事務(wù)數(shù)據(jù)寬度的增加，Apriori算法的性能顯著降低。為了算法的性能顯著降低。為了克服這些局限性和提高克服這些局限性和提高Aprio

34、ri算法的效率，已開發(fā)了一些替代方法。算法的效率，已開發(fā)了一些替代方法。7.5產(chǎn)生頻繁項集的其它方法347.5.1項集格遍歷 概念上，可以將頻繁項集的搜索看作遍歷項集格。算法使用的搜索策概念上，可以將頻繁項集的搜索看作遍歷項集格。算法使用的搜索策略指明了頻繁項集產(chǎn)生過程中如何遍歷格結(jié)構(gòu)。根據(jù)頻繁項集在格中的布略指明了頻繁項集產(chǎn)生過程中如何遍歷格結(jié)構(gòu)。根據(jù)頻繁項集在格中的布局，某些搜索策略優(yōu)于其他策略。局，某些搜索策略優(yōu)于其他策略。一般到特殊與特殊到一般一般到特殊與特殊到一般7.5產(chǎn)生頻繁項集的其它方法357.5.1項集格遍歷 Apriori算法使用了算法使用了“一般到特殊一般到特殊”的搜索策略

35、，合并兩個頻繁（的搜索策略，合并兩個頻繁（k-1）-項集得到候選項集得到候選k-項集。使用這種策略效果最好的頻繁項集的布局顯示在上項集。使用這種策略效果最好的頻繁項集的布局顯示在上圖（圖（a）中，其中較黑的結(jié)點代表非頻繁項集。相反，）中，其中較黑的結(jié)點代表非頻繁項集。相反，“特殊到一般特殊到一般”的搜的搜索策略在發(fā)現(xiàn)更一般的頻繁項集之前，先尋找更特殊的頻繁項集。這種策索策略在發(fā)現(xiàn)更一般的頻繁項集之前，先尋找更特殊的頻繁項集。這種策略對于發(fā)現(xiàn)稠密事務(wù)中的最大頻繁項集是有用的。稠密事務(wù)中頻繁項集的略對于發(fā)現(xiàn)稠密事務(wù)中的最大頻繁項集是有用的。稠密事務(wù)中頻繁項集的邊界靠近格的底部，如上圖（邊界靠近格的

36、底部，如上圖（b）所示?？梢允褂孟闰炘砑舻糇畲箢l繁項）所示?？梢允褂孟闰炘砑舻糇畲箢l繁項集的所有子集。另一種策略是結(jié)合集的所有子集。另一種策略是結(jié)合“一般到特殊一般到特殊”和和“特殊到一般特殊到一般”的搜的搜索策略，盡管這種雙向搜索方法需要更多的空間存儲候選項集，但是上圖索策略，盡管這種雙向搜索方法需要更多的空間存儲候選項集，但是上圖（c）所示的布局，該方法有助于加快確定頻繁項集邊界。）所示的布局，該方法有助于加快確定頻繁項集邊界。7.5產(chǎn)生頻繁項集的其它方法367.5.1項集格遍歷等價類等價類 該方法是先將格劃分為兩個不相交的結(jié)點組（或等價類）。頻繁項該方法是先將格劃分為兩個不相交的結(jié)點

37、組（或等價類）。頻繁項集產(chǎn)生算法依次在每個等價類內(nèi)搜索頻繁項集。集產(chǎn)生算法依次在每個等價類內(nèi)搜索頻繁項集。7.5產(chǎn)生頻繁項集的其它方法377.5.1項集格遍歷 Apriori算法采用的逐層策略可以看作根據(jù)項集的大小劃分格，即在算法采用的逐層策略可以看作根據(jù)項集的大小劃分格，即在處理較大項集之前，首先找出所有的頻繁處理較大項集之前，首先找出所有的頻繁1-項集。等價類也可以根據(jù)項集項集。等價類也可以根據(jù)項集的前綴或后綴來定義。在這種情況下，兩個項集屬于同一個等價類，如的前綴或后綴來定義。在這種情況下，兩個項集屬于同一個等價類，如果它們共享長度為果它們共享長度為k的相同前綴或后綴。在基于前綴的方法中

38、，算法首先的相同前綴或后綴。在基于前綴的方法中，算法首先搜索以前綴搜索以前綴a開始的頻繁項集，然后是以前綴開始的頻繁項集，然后是以前綴b等開始的頻繁項集，然后等開始的頻繁項集，然后中中c，如此下去?；谇熬Y和基于后綴的等價類都可以使用，如此下去。基于前綴和基于后綴的等價類都可以使用上上圖中所示的圖中所示的類似于樹的結(jié)構(gòu)來演示。類似于樹的結(jié)構(gòu)來演示。7.5產(chǎn)生頻繁項集的其它方法387.5.1項集格遍歷寬度優(yōu)先與深度優(yōu)先寬度優(yōu)先與深度優(yōu)先 Apriori算法采用寬度優(yōu)先的方法遍歷格，如圖（算法采用寬度優(yōu)先的方法遍歷格，如圖（a）所示。它首先發(fā)）所示。它首先發(fā)現(xiàn)所有頻繁現(xiàn)所有頻繁1-項集，接下來是頻

39、繁項集，接下來是頻繁2-項集，如此下去直到?jīng)]有新的頻繁項項集，如此下去直到?jīng)]有新的頻繁項集產(chǎn)生為止。也可以以用深度優(yōu)先的方式遍歷項集格，如圖（集產(chǎn)生為止。也可以以用深度優(yōu)先的方式遍歷項集格，如圖（b）所示。）所示。7.5產(chǎn)生頻繁項集的其它方法397.5.1項集格遍歷 比如說，算法可以從圖中的結(jié)點比如說，算法可以從圖中的結(jié)點a開始，計算其支持度計數(shù)并判斷它是開始，計算其支持度計數(shù)并判斷它是否頻繁。如果是，算法漸增地擴(kuò)展下層結(jié)點，即否頻繁。如果是，算法漸增地擴(kuò)展下層結(jié)點，即ab，abc，等等，直到到達(dá)，等等，直到到達(dá)一個非頻繁結(jié)點，如一個非頻繁結(jié)點，如abcd。然后，回溯到下一個分支，比如說。然后

40、，回溯到下一個分支，比如說abce，并且繼，并且繼續(xù)搜索。續(xù)搜索。7.5產(chǎn)生頻繁項集的其它方法407.5.1項集格遍歷 通常，深度優(yōu)先搜索方法用于發(fā)現(xiàn)最大頻繁項集通常，深度優(yōu)先搜索方法用于發(fā)現(xiàn)最大頻繁項集。比寬度優(yōu)先更。比寬度優(yōu)先更快快地檢測到頻繁項集邊界。一旦發(fā)現(xiàn)一個最大頻繁項集，就地檢測到頻繁項集邊界。一旦發(fā)現(xiàn)一個最大頻繁項集，就可在可在它的子集它的子集上剪枝。如上剪枝。如，上圖中的結(jié)點，上圖中的結(jié)點bcde是最大頻繁項集，則算法就不必訪問以是最大頻繁項集，則算法就不必訪問以bd，be，c，d和和e為根的子樹，因為它們不可能包含任何最大頻繁項集。然而，為根的子樹，因為它們不可能包含任何最大

41、頻繁項集。然而，如如abc是最大頻繁項集，則只有是最大頻繁項集，則只有ac和和bc這樣的結(jié)點不是最大頻繁項集，但這樣的結(jié)點不是最大頻繁項集，但以它們?yōu)楦淖訕溥€可能包含最大頻繁項集。深度優(yōu)先方法還允許使用以它們?yōu)楦淖訕溥€可能包含最大頻繁項集。深度優(yōu)先方法還允許使用不同的基于項集支持度的剪枝方法不同的基于項集支持度的剪枝方法。如。如，假定項集，假定項集 a，b，c和和a，b具具有相同的支持度，則有相同的支持度，則可跳可跳過以過以abd和和abe為根的子樹為根的子樹，不，不包含最大頻繁項集。包含最大頻繁項集。7.5產(chǎn)生頻繁項集的其它方法417.5.2事務(wù)數(shù)據(jù)集的表示表示表示購物籃事務(wù)的兩種不同方

42、法。左邊的表示法稱作購物籃事務(wù)的兩種不同方法。左邊的表示法稱作水平數(shù)據(jù)布局水平數(shù)據(jù)布局，許多，許多關(guān)聯(lián)規(guī)則挖掘算法（包括關(guān)聯(lián)規(guī)則挖掘算法（包括Apriori）都采用這種表示法；）都采用這種表示法；右右邊的表示法是存邊的表示法是存儲與每一個項相關(guān)聯(lián)的事務(wù)標(biāo)識符列表（儲與每一個項相關(guān)聯(lián)的事務(wù)標(biāo)識符列表（TID列表），這種表示法稱作列表），這種表示法稱作垂直垂直數(shù)據(jù)布局?jǐn)?shù)據(jù)布局。候選項集的支持度通過取其子項集。候選項集的支持度通過取其子項集TID列表的交得到。列表的交得到。7.5產(chǎn)生頻繁項集的其它方法427.6FP-growth算法 FP-growth（Frequent-Pattern growth

43、，頻繁模式增長）算法的，頻繁模式增長）算法的基本思基本思想想是是采用分采用分治策略：首先，將代表頻繁項集的數(shù)據(jù)庫壓縮到一棵治策略：首先，將代表頻繁項集的數(shù)據(jù)庫壓縮到一棵FP樹（樹（Frequent-Pattern tree，頻繁模式樹），該樹仍保留項集的關(guān)聯(lián)信息。，頻繁模式樹），該樹仍保留項集的關(guān)聯(lián)信息。其其次次，將這種壓縮后的數(shù)據(jù)庫劃分成一組條件數(shù)據(jù)庫（一種特殊類型的投影，將這種壓縮后的數(shù)據(jù)庫劃分成一組條件數(shù)據(jù)庫（一種特殊類型的投影數(shù)據(jù)庫），每個數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項或數(shù)據(jù)庫），每個數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項或“模式段模式段”，并分別挖掘每個條，并分別挖掘每個條件數(shù)據(jù)庫。對于每個件數(shù)據(jù)庫。對于每個“

44、模式片段模式片段”，只需要考察與它相關(guān)聯(lián)數(shù)據(jù)集，只需要考察與它相關(guān)聯(lián)數(shù)據(jù)集。隨著。隨著被考察的模式的被考察的模式的“增長增長”，可以，可以顯著地壓縮被搜索的數(shù)據(jù)集的大小。顯著地壓縮被搜索的數(shù)據(jù)集的大小。437.6.1FP樹構(gòu)造 利用利用FP-growthFP-growth算法構(gòu)造頻繁模式樹的過程如下：算法構(gòu)造頻繁模式樹的過程如下： （1）按）按Apriori算法，第一次掃描事務(wù)數(shù)據(jù)庫算法，第一次掃描事務(wù)數(shù)據(jù)庫D，導(dǎo)出頻繁，導(dǎo)出頻繁1-項集，并項集，并得到它們的支持度計數(shù)（頻度）。設(shè)最小支持度計數(shù)為得到它們的支持度計數(shù)（頻度）。設(shè)最小支持度計數(shù)為2 ，頻繁項的集合，頻繁項的集合按支持度計數(shù)的降序

45、排序。結(jié)果集或表記作按支持度計數(shù)的降序排序。結(jié)果集或表記作L。這樣有。這樣有L=I2:7，I1:6，I3:6，I4:2，I5:2，如圖所示。，如圖所示。7.6FP-growth算法447.6.1FP樹構(gòu)造 （2）創(chuàng)建樹的根結(jié)點，并標(biāo)記為）創(chuàng)建樹的根結(jié)點，并標(biāo)記為“null”。第二次掃描數(shù)據(jù)庫。第二次掃描數(shù)據(jù)庫D。每個。每個事務(wù)中的項都按事務(wù)中的項都按L中的次序處理（即按支持度計數(shù)降序排序），并對每個事中的次序處理（即按支持度計數(shù)降序排序），并對每個事務(wù)創(chuàng)建一個分枝。例如，第一個事務(wù)務(wù)創(chuàng)建一個分枝。例如，第一個事務(wù)“T100：I1，I2，I5”按按L的次序包含的次序包含三個項三個項I2，I1，I

46、5，導(dǎo)致構(gòu)造樹的第一個分枝，導(dǎo)致構(gòu)造樹的第一個分枝。該分枝具有。該分枝具有3個結(jié)點，其中個結(jié)點，其中I2作為根的子女鏈接到根，作為根的子女鏈接到根，I1鏈接到鏈接到I2，I5鏈鏈接到接到I1，如圖所示。，如圖所示。7.6FP-growth算法457.6.1FP樹構(gòu)造 第二個事務(wù)第二個事務(wù)T200按按L的次序包含的次序包含I2和和I4，它導(dǎo)致一個分枝，其中，它導(dǎo)致一個分枝，其中I2鏈鏈接到根，接到根，I4鏈接到鏈接到I2。然而，該分枝。然而，該分枝應(yīng)與應(yīng)與T100已存在的路徑共享前綴已存在的路徑共享前綴。因此將因此將結(jié)點結(jié)點I2的計數(shù)增加的計數(shù)增加1，并創(chuàng)建一個新結(jié)點（，并創(chuàng)建一個新結(jié)點（I4:

47、1），它作為（），它作為（I2:2）子女鏈接，如圖所示。一般地，當(dāng)為一個事務(wù)考慮增加分枝時，沿共同前子女鏈接，如圖所示。一般地，當(dāng)為一個事務(wù)考慮增加分枝時，沿共同前綴上的每個結(jié)點的計數(shù)增加綴上的每個結(jié)點的計數(shù)增加1，為隨在前綴之后的項創(chuàng)建結(jié)點并鏈接。，為隨在前綴之后的項創(chuàng)建結(jié)點并鏈接。7.6FP-growth算法467.6.1FP樹構(gòu)造 為了方便樹的遍歷，創(chuàng)建一個項頭表，使每項通過一個結(jié)點鏈指向它為了方便樹的遍歷，創(chuàng)建一個項頭表，使每項通過一個結(jié)點鏈指向它在樹中的位置。掃描所有的事務(wù)后得到的樹在樹中的位置。掃描所有的事務(wù)后得到的樹如圖所示如圖所示，帶有相關(guān)的結(jié)點鏈。，帶有相關(guān)的結(jié)點鏈。這樣，數(shù)

48、據(jù)庫頻繁模式的挖掘問題就轉(zhuǎn)換成挖掘這樣，數(shù)據(jù)庫頻繁模式的挖掘問題就轉(zhuǎn)換成挖掘FP樹的問題。樹的問題。7.6FP-growth算法477.6.2頻繁項集產(chǎn)生 FP FP樹的挖掘過程為：樹的挖掘過程為： 由長度為由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基（一個（一個“子數(shù)據(jù)庫子數(shù)據(jù)庫”，由，由FP樹中與該后綴模式一起出現(xiàn)的前綴路徑集組樹中與該后綴模式一起出現(xiàn)的前綴路徑集組成）。然后，構(gòu)造它的（條件）成）。然后，構(gòu)造它的（條件）FP樹，并遞歸地在該樹上進(jìn)行挖掘。模式樹，并遞歸地在該樹上進(jìn)行挖掘。模式增長通過后綴模式與條件增長通過后綴

49、模式與條件FP樹產(chǎn)生的頻繁模式連接實現(xiàn)。樹產(chǎn)生的頻繁模式連接實現(xiàn)。7.6FP-growth算法487.6.2頻繁項集產(chǎn)生 該該FP樹的挖掘過程總結(jié)如樹的挖掘過程總結(jié)如上上表所示。首先考慮表所示。首先考慮I5，它是，它是L中的最后一項，中的最后一項，而不是第一項而不是第一項。I5出現(xiàn)在出現(xiàn)在FP樹的兩個分枝中（樹的兩個分枝中（I5的出現(xiàn)容易通過沿它的結(jié)的出現(xiàn)容易通過沿它的結(jié)點鏈找到）。這些路徑由分枝點鏈找到）。這些路徑由分枝和和形成。因此，形成。因此，考慮以考慮以I5為后綴，它的兩個對應(yīng)前綴路徑是為后綴，它的兩個對應(yīng)前綴路徑是和和，形，形成成I5的條件模式基。使用這些條件模式基作為事務(wù)數(shù)據(jù)庫，構(gòu)

50、造的條件模式基。使用這些條件模式基作為事務(wù)數(shù)據(jù)庫，構(gòu)造I5的條件的條件FP樹，它只包含單個路徑樹，它只包含單個路徑；不包含；不包含I3，因為它的支持，因為它的支持度度1，小，小于最小支持度計數(shù)。該單個路徑產(chǎn)生頻繁模式的所有組合：于最小支持度計數(shù)。該單個路徑產(chǎn)生頻繁模式的所有組合：I2 I5:2，I1 I5:2，I2 I1 I5:2。對于。對于I4，它的兩個前綴形成條件模式基，它的兩個前綴形成條件模式基(I2 I1:1）,（I2:1)，產(chǎn)，產(chǎn)生一個單結(jié)點的條件生一個單結(jié)點的條件FP樹樹，并導(dǎo)出一個頻繁模式，并導(dǎo)出一個頻繁模式I2 I4:2。7.6FP-growth算法497.6.2頻繁項集產(chǎn)生

51、類似于以上分析，類似于以上分析，I3的條件模式基是的條件模式基是(I2 I1:2）,（I2:2）,（I1:2)。它。它的條件的條件FP樹有兩個分枝樹有兩個分枝和和，如圖所示，它產(chǎn)生模式集：，如圖所示，它產(chǎn)生模式集：I2 I3:4，I1 I3:4，I2 I1 I3:2。最后，。最后，I1的條件模式基是的條件模式基是(I2:4)，它的，它的FP樹樹只包含一個結(jié)點只包含一個結(jié)點，只產(chǎn)生一個頻繁模式，只產(chǎn)生一個頻繁模式I2 I1:4。7.6FP-growth算法507.6.2頻繁項集產(chǎn)生7.6FP-growth算法517.6.2頻繁項集產(chǎn)生 優(yōu)點：優(yōu)點：FP-growth算法僅僅遍歷了算法僅僅遍歷了2

52、次數(shù)據(jù)庫，第一次是為了產(chǎn)生次數(shù)據(jù)庫，第一次是為了產(chǎn)生L1，第二，第二次是為了對項目排序。由于不用多次掃描數(shù)據(jù)庫，次是為了對項目排序。由于不用多次掃描數(shù)據(jù)庫，因而因而大大節(jié)省了掃大大節(jié)省了掃描數(shù)據(jù)庫的時間；描數(shù)據(jù)庫的時間；選用了分治策略，把挖掘的長頻繁模式轉(zhuǎn)換成遞歸地挖掘短模式的問選用了分治策略，把挖掘的長頻繁模式轉(zhuǎn)換成遞歸地挖掘短模式的問題，再與后綴相連；題，再與后綴相連；挖掘長頻繁模式與短的頻繁模式時，有效性與可伸縮性都是該算法的挖掘長頻繁模式與短的頻繁模式時，有效性與可伸縮性都是該算法的特點，特點，所用所用挖掘時間會比挖掘時間會比Apriori算法的挖掘時間少得多。算法的挖掘時間少得多。

53、7.6FP-growth算法527.6.2頻繁項集產(chǎn)生 缺點：缺點：建立建立FP樹時，會占用大量的內(nèi)存空間。如果數(shù)據(jù)庫的規(guī)模很大，要樹時，會占用大量的內(nèi)存空間。如果數(shù)據(jù)庫的規(guī)模很大，要建立的建立的FP樹也會很巨大；樹也會很巨大；在遞歸構(gòu)建在遞歸構(gòu)建FP樹時，每生成一個頻繁模式就會出現(xiàn)一個條件樹。當(dāng)樹時，每生成一個頻繁模式就會出現(xiàn)一個條件樹。當(dāng)生成與釋放海量的條件樹時，生成與釋放海量的條件樹時，該算法該算法將占用很多的運算時間與計算將占用很多的運算時間與計算機(jī)空間。機(jī)空間。7.6FP-growth算法537.7關(guān)聯(lián)評估 在實際情況中，商業(yè)數(shù)據(jù)庫的數(shù)據(jù)量和維數(shù)都非常大，運用關(guān)聯(lián)分析在實際情況中，商

54、業(yè)數(shù)據(jù)庫的數(shù)據(jù)量和維數(shù)都非常大，運用關(guān)聯(lián)分析算法往往產(chǎn)生大量的規(guī)則，而其中很大一部分可能是不感興趣的。因此，算法往往產(chǎn)生大量的規(guī)則，而其中很大一部分可能是不感興趣的。因此，建立一組廣泛接受的評價關(guān)聯(lián)模式質(zhì)量的標(biāo)準(zhǔn)是非常重要的。建立一組廣泛接受的評價關(guān)聯(lián)模式質(zhì)量的標(biāo)準(zhǔn)是非常重要的。第一組標(biāo)準(zhǔn)第一組標(biāo)準(zhǔn)可通過可通過統(tǒng)計論據(jù)建立。涉及相互獨立的項或覆蓋少量事務(wù)統(tǒng)計論據(jù)建立。涉及相互獨立的項或覆蓋少量事務(wù)的模式被認(rèn)為是不令人感興趣的，因為它們可能反映數(shù)據(jù)中的偽聯(lián)系。的模式被認(rèn)為是不令人感興趣的，因為它們可能反映數(shù)據(jù)中的偽聯(lián)系。第二組標(biāo)準(zhǔn)第二組標(biāo)準(zhǔn)可通過可通過主觀論據(jù)建立，即模式被主觀地認(rèn)為是無趣的，除

55、主觀論據(jù)建立，即模式被主觀地認(rèn)為是無趣的，除非它能夠揭示料想不到的信息或提供導(dǎo)致有益的行動的有用信息非它能夠揭示料想不到的信息或提供導(dǎo)致有益的行動的有用信息。 547.7.1興趣度客觀度量 客觀度量常常基于列聯(lián)表中列出的頻度計數(shù)來計算。一對二元變量客觀度量常?；诹新?lián)表中列出的頻度計數(shù)來計算。一對二元變量A和和B的列聯(lián)表的列聯(lián)表如表所示如表所示。使用記號。使用記號 A（B）表示）表示A（B）不在事務(wù)中出現(xiàn)。在這）不在事務(wù)中出現(xiàn)。在這個個22的表中，每個的表中，每個fij都代表一個頻度計數(shù)都代表一個頻度計數(shù)。如。如，f11表示表示A和和B同時出現(xiàn)在一同時出現(xiàn)在一個事務(wù)中的次數(shù)，個事務(wù)中的次數(shù)，f

56、01表示包含表示包含B但不包含但不包含A的事務(wù)的個數(shù)。行和的事務(wù)的個數(shù)。行和f1+表示表示A的支的支持度計數(shù)，而列和持度計數(shù)，而列和f+1表示表示B的支持度計數(shù)。的支持度計數(shù)。7.7關(guān)聯(lián)評估557.7.1興趣度客觀度量 支持度置信度框架的局限性支持度置信度框架的局限性?，F(xiàn)有關(guān)聯(lián)規(guī)則的挖掘算法依賴于支持?，F(xiàn)有關(guān)聯(lián)規(guī)則的挖掘算法依賴于支持度和置信度來除去沒有意義的模式。支持度的缺點在于許多潛在的有意義度和置信度來除去沒有意義的模式。支持度的缺點在于許多潛在的有意義的模式由于包含支持度小的項而被刪去。置信度的缺點的模式由于包含支持度小的項而被刪去。置信度的缺點更微妙更微妙，最適合用，最適合用下面的例

57、子進(jìn)行說明下面的例子進(jìn)行說明。假定。假定希望分析愛喝咖啡和愛喝茶的人之間的關(guān)系。希望分析愛喝咖啡和愛喝茶的人之間的關(guān)系。收集一組人關(guān)于飲料偏愛的信息，并匯總在表中。收集一組人關(guān)于飲料偏愛的信息，并匯總在表中。7.7關(guān)聯(lián)評估567.7.1興趣度客觀度量7.7關(guān)聯(lián)評估577.7.1興趣度客觀度量 興趣因子興趣因子。茶和咖啡的例子表明，由于置信度度量忽略了規(guī)則后件中。茶和咖啡的例子表明，由于置信度度量忽略了規(guī)則后件中出現(xiàn)的項集的支持度，高置信度的規(guī)則有時存在誤導(dǎo)。解決這個問題的一出現(xiàn)的項集的支持度，高置信度的規(guī)則有時存在誤導(dǎo)。解決這個問題的一種方法是使用稱作提升度（種方法是使用稱作提升度（lift）

58、的度量）的度量： 它計算規(guī)則置信度和規(guī)則后件中項集的支持度之間的比率。對于二元它計算規(guī)則置信度和規(guī)則后件中項集的支持度之間的比率。對于二元變量，提升度等價變量，提升度等價于興趣于興趣因子的客觀因子的客觀度量：度量： 對于相互獨立的兩個變量，對于相互獨立的兩個變量，I(A,B)=1 ；如果如果A和和B是正相關(guān)的，則是正相關(guān)的，則I(A,B)1；如果；如果A和和B是負(fù)相關(guān)的是負(fù)相關(guān)的，則，則 I(A,B)1 。7.7關(guān)聯(lián)評估587.7.1興趣度客觀度量 興趣因子的局限性興趣因子的局限性。兩個詞兩個詞 p,q和和r,s 出現(xiàn)的頻率出現(xiàn)的頻率如表所示如表所示。使用公。使用公式式得出得出p,q和和r,s

59、 的興趣因子分別為的興趣因子分別為1.02和和4.08。這些結(jié)果有點。這些結(jié)果有點問題：雖然問題：雖然p和和q同時出現(xiàn)在同時出現(xiàn)在88%的文檔中，的文檔中，但它們但它們的興趣因子的興趣因子接近接近1，表明二者是相互，表明二者是相互獨立的；另一方面，獨立的；另一方面， r,s 的興趣因子比的興趣因子比p,q 高高，盡管，盡管r和和s很少同時出現(xiàn)在很少同時出現(xiàn)在同一個文檔中。這種情況下，置信度可能同一個文檔中。這種情況下，置信度可能是更好是更好的選擇，因為置信度表明的選擇，因為置信度表明p和和q之間的關(guān)聯(lián)（之間的關(guān)聯(lián)（94.6%）遠(yuǎn)遠(yuǎn)強(qiáng)于）遠(yuǎn)遠(yuǎn)強(qiáng)于r和和s之間的關(guān)聯(lián)（之間的關(guān)聯(lián)（28.6%）。）。

60、7.7關(guān)聯(lián)評估597.7.1興趣度客觀度量7.7關(guān)聯(lián)評估607.7.1興趣度客觀度量7.7關(guān)聯(lián)評估617.7.1興趣度客觀度量 IS IS度量度量。IS是另一種度量，用于處理非對稱二元變量是另一種度量，用于處理非對稱二元變量。定義。定義如下如下： 如如，前面表中顯示的詞對，前面表中顯示的詞對p,q和和r,s的的IS值分別是值分別是0.946和和0.286。IS度量暗示度量暗示p,q之間的關(guān)聯(lián)強(qiáng)于之間的關(guān)聯(lián)強(qiáng)于r,s ，這與期望的文檔中詞的關(guān)聯(lián)一致。，這與期望的文檔中詞的關(guān)聯(lián)一致。 可以證明可以證明IS數(shù)學(xué)上等價于二元變量的余弦變量數(shù)學(xué)上等價于二元變量的余弦變量： IS度量也可以表示為從一對二元