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

1、第7章 數(shù)據(jù)關(guān)聯(lián)分析 7.1基 本 概 念 7.2頻繁項(xiàng)集產(chǎn)生 7.3規(guī)則產(chǎn)生 7.4頻繁項(xiàng)集的緊湊表示 7.5 產(chǎn)生頻繁項(xiàng)集的 其他方法 7.6FP-growth算法 7.7關(guān) 聯(lián) 評(píng) 估 1 7.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）或頻繁）或頻繁 項(xiàng)集的形式表示項(xiàng)集的形式表示。關(guān)于。關(guān)于關(guān)聯(lián)規(guī)則的幾個(gè)概念：關(guān)聯(lián)規(guī)則的幾個(gè)概念： 項(xiàng)集項(xiàng)集：項(xiàng)目：項(xiàng)目的集合，包含的集合，包

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

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

4、可能的項(xiàng)集。圖）常常被用來(lái)枚舉所有可能的項(xiàng)集。圖中中顯示顯示 的的是是I=a，b，c，d，e的項(xiàng)集格的項(xiàng)集格。包含。包含k個(gè)項(xiàng)的數(shù)據(jù)個(gè)項(xiàng)的數(shù)據(jù)集最多產(chǎn)生集最多產(chǎn)生2k-1 個(gè)頻繁個(gè)頻繁 項(xiàng)集，不包括項(xiàng)集，不包括空集。空集。 7.2 頻繁項(xiàng)集產(chǎn)生 4 發(fā)現(xiàn)頻繁項(xiàng)集的一種原始方法是確定格結(jié)構(gòu)中每個(gè)候選項(xiàng)集的支持度發(fā)現(xiàn)頻繁項(xiàng)集的一種原始方法是確定格結(jié)構(gòu)中每個(gè)候選項(xiàng)集的支持度 計(jì)數(shù)計(jì)數(shù)。這必須這必須比較每個(gè)比較每個(gè)候選項(xiàng)集與每個(gè)候選項(xiàng)集與每個(gè)事務(wù)。如候選事務(wù)。如候選項(xiàng)集包含在事務(wù)中，項(xiàng)集包含在事務(wù)中， 則候選項(xiàng)集的支持度計(jì)數(shù)增加則候選項(xiàng)集的支持度計(jì)數(shù)增加。如。如，由于項(xiàng)集，由于項(xiàng)集 Milk，Brea

5、d 出現(xiàn)在事務(wù)出現(xiàn)在事務(wù) 1，4，5中，其支持度計(jì)數(shù)將增加中，其支持度計(jì)數(shù)將增加3次次。這種比較開(kāi)銷(xiāo)大。這種比較開(kāi)銷(xiāo)大。 7.2 頻繁項(xiàng)集產(chǎn)生 5 7.2.1 先驗(yàn)原理 先驗(yàn)原理先驗(yàn)原理是減少候選項(xiàng)集的數(shù)量（是減少候選項(xiàng)集的數(shù)量（M）的方法之一。）的方法之一。 其基本思想是其基本思想是：如果一個(gè)項(xiàng)集是頻繁的，則它的所有子集一定也是：如果一個(gè)項(xiàng)集是頻繁的，則它的所有子集一定也是 頻繁的。例如，頻繁的。例如，假定假定 c，d，e是頻繁項(xiàng)是頻繁項(xiàng)集，顯然任何包含項(xiàng)集集，顯然任何包含項(xiàng)集c，d， e的事務(wù)一定包含它的子集的事務(wù)一定包含它的子集c，d ， c，e ， d，e， c ， d和和 e。這樣，

6、如果。這樣，如果c，d，e是頻繁的，則它的所有子集一定也是頻繁是頻繁的，則它的所有子集一定也是頻繁 的。的。 反之，反之，如項(xiàng)集如項(xiàng)集是非頻繁的，則它的所有超集也一定是非頻繁的。是非頻繁的，則它的所有超集也一定是非頻繁的。 7.2 頻繁項(xiàng)集產(chǎn)生 6 7.2.1 先驗(yàn)原理 如圖所示，一旦發(fā)現(xiàn)如圖所示，一旦發(fā)現(xiàn)a，b是非頻繁的，則整個(gè)包含是非頻繁的，則整個(gè)包含a，b超集的子超集的子 圖可以被立即剪枝。這種基于支持度度量修剪指數(shù)搜索空間的策略稱(chēng)為基圖可以被立即剪枝。這種基于支持度度量修剪指數(shù)搜索空間的策略稱(chēng)為基 于支持度的剪枝。于支持度的剪枝。 7.2 頻繁項(xiàng)集產(chǎn)生 7 7.2.2 Apriori算

7、法的頻繁項(xiàng)集產(chǎn)生 Apriori算法算法是一種最具影響力的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算是一種最具影響力的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算 法。法。Apriori的命名由來(lái)是因?yàn)槭褂昧祟l繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)，即的命名由來(lái)是因?yàn)槭褂昧祟l繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)，即Apri ori性質(zhì)。性質(zhì)。Apriori性質(zhì)的內(nèi)容是：頻繁項(xiàng)集的所有非空子集也必須是頻繁性質(zhì)的內(nèi)容是：頻繁項(xiàng)集的所有非空子集也必須是頻繁 的。該性質(zhì)通過(guò)減少搜索空間來(lái)提高頻繁項(xiàng)集逐層產(chǎn)生的效率。的。該性質(zhì)通過(guò)減少搜索空間來(lái)提高頻繁項(xiàng)集逐層產(chǎn)生的效率。 Apriori算法利用算法利用Apriori性質(zhì)，通過(guò)逐層搜索的迭代方法，將性質(zhì)，通過(guò)逐層搜索

8、的迭代方法，將k-項(xiàng)集用項(xiàng)集用 于探索（于探索（k+1）-項(xiàng)集，來(lái)窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集。項(xiàng)集，來(lái)窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集。 7.2 頻繁項(xiàng)集產(chǎn)生 8 7.2.2 Apriori算法的頻繁項(xiàng)集產(chǎn)生 特點(diǎn)特點(diǎn)： 它是一個(gè)逐層算法，即從頻繁它是一個(gè)逐層算法，即從頻繁1-項(xiàng)集到最長(zhǎng)的頻繁項(xiàng)集，它每次遍項(xiàng)集到最長(zhǎng)的頻繁項(xiàng)集，它每次遍 歷項(xiàng)集格中的一層。先找到頻繁歷項(xiàng)集格中的一層。先找到頻繁1-項(xiàng)集集合項(xiàng)集集合Ll，然后用，然后用Ll找到頻繁找到頻繁2- 項(xiàng)集集合項(xiàng)集集合L2，接著用，接著用L2找找L3，直到找不到頻繁，直到找不到頻繁k-項(xiàng)集，找每個(gè)項(xiàng)集，找每個(gè)Lk需要需要 一次數(shù)據(jù)庫(kù)掃描；一次數(shù)

9、據(jù)庫(kù)掃描； 它使用產(chǎn)生它使用產(chǎn)生-測(cè)試策略來(lái)發(fā)現(xiàn)頻繁項(xiàng)集。在每次迭代之后，新的候選測(cè)試策略來(lái)發(fā)現(xiàn)頻繁項(xiàng)集。在每次迭代之后，新的候選 項(xiàng)集由前一次迭代發(fā)現(xiàn)的頻繁項(xiàng)集產(chǎn)生，然后對(duì)每個(gè)候選的支持度項(xiàng)集由前一次迭代發(fā)現(xiàn)的頻繁項(xiàng)集產(chǎn)生，然后對(duì)每個(gè)候選的支持度 進(jìn)行計(jì)數(shù)，并與最小支持度閾值進(jìn)行比較。該算法需要的總迭代次進(jìn)行計(jì)數(shù)，并與最小支持度閾值進(jìn)行比較。該算法需要的總迭代次 數(shù)是數(shù)是kmax+1，其中，其中kmax是頻繁項(xiàng)集的最大長(zhǎng)度。是頻繁項(xiàng)集的最大長(zhǎng)度。 7.2 頻繁項(xiàng)集產(chǎn)生 9 7.2.2 Apriori算法的頻繁項(xiàng)集產(chǎn)生 Apriori Apriori算法的主要步驟由連接步和剪枝步組成。算法的主

10、要步驟由連接步和剪枝步組成。 連接步連接步。為找出為找出Lk，通過(guò)，通過(guò)Lk-1與自身連接產(chǎn)生候選與自身連接產(chǎn)生候選k-項(xiàng)集的項(xiàng)集的集合集合，記記 作作Ck。設(shè)。設(shè)l1和和l2是是Lk-1中的項(xiàng)集中的項(xiàng)集。lij表示表示li的第的第j項(xiàng)。假定項(xiàng)。假定事務(wù)或項(xiàng)集中事務(wù)或項(xiàng)集中 的項(xiàng)按字典次序的項(xiàng)按字典次序排序，排序，使得使得li1li2.lik-1。執(zhí)行連接。執(zhí)行連接Lk-1 Lk-1； 其中其中Lk-1的元素是可連接的，的元素是可連接的，如它們?nèi)缢鼈兦埃ㄇ埃╧-2）個(gè)項(xiàng)相同）個(gè)項(xiàng)相同，即即Lk-1的元的元 素素l1和和l2是可連接的，是可連接的，如（如（l11=l21） （l12=l22） .

11、 （l1k-2 l2k-2） （l1k-1l2k-1）。條件）。條件l1k-1l2k-1是簡(jiǎn)單地確保不產(chǎn)生是簡(jiǎn)單地確保不產(chǎn)生 重復(fù)。連接重復(fù)。連接l1和和l2產(chǎn)生的結(jié)果項(xiàng)集是產(chǎn)生的結(jié)果項(xiàng)集是l11，l12，.l1k-1，l2k-1。 7.2 頻繁項(xiàng)集產(chǎn)生 10 7.2.2 Apriori算法的頻繁項(xiàng)集產(chǎn)生 剪枝步。剪枝步。 Ck是是Lk的超集的超集，即即Ck的成員可以是頻繁的，也可以不是頻的成員可以是頻繁的，也可以不是頻 繁的，但所有頻繁繁的，但所有頻繁k-項(xiàng)集都包含在項(xiàng)集都包含在Ck中。掃描數(shù)據(jù)庫(kù)，確定中。掃描數(shù)據(jù)庫(kù)，確定Ck中每中每 個(gè)候選的支持度計(jì)數(shù)，從而確定個(gè)候選的支持度計(jì)數(shù)，從而確定

12、Lk（即根據(jù)定義，計(jì)數(shù)值不小于最（即根據(jù)定義，計(jì)數(shù)值不小于最 小支持度計(jì)數(shù)的所有候選都是頻繁的，從而屬于小支持度計(jì)數(shù)的所有候選都是頻繁的，從而屬于Lk）。然而，）。然而，Ck可可 能很大，因此所涉及的計(jì)算量就很大。為了壓縮能很大，因此所涉及的計(jì)算量就很大。為了壓縮Ck，可以，可以用用Apriori 性質(zhì)，性質(zhì)，即即非非頻繁的（頻繁的（k-1）-項(xiàng)集都不是頻繁項(xiàng)集都不是頻繁k-項(xiàng)集的項(xiàng)集的子集，如候選子集，如候選k- 項(xiàng)集的（項(xiàng)集的（k-1）-子集不在子集不在Lk-1中，則該候選也不可能是頻繁的，中，則該候選也不可能是頻繁的，從而從而 從從Ck中刪除。這種子集測(cè)試中刪除。這種子集測(cè)試可使用可使用

13、所有頻繁項(xiàng)集的散列樹(shù)快速完成。所有頻繁項(xiàng)集的散列樹(shù)快速完成。 7.2 頻繁項(xiàng)集產(chǎn)生 11 7.2.2 Apriori算法的頻繁項(xiàng)集產(chǎn)生 下面下面舉舉一個(gè)具體例子。該例基于表中的一個(gè)具體例子。該例基于表中的AllElectronics的事務(wù)數(shù)據(jù)庫(kù)的事務(wù)數(shù)據(jù)庫(kù) D。該數(shù)據(jù)庫(kù)有該數(shù)據(jù)庫(kù)有9個(gè)事務(wù)個(gè)事務(wù)，假定事務(wù)中的項(xiàng)按字典次序存放。假定事務(wù)中的項(xiàng)按字典次序存放。 7.2 頻繁項(xiàng)集產(chǎn)生 12 7.2.2 Apriori算法的頻繁項(xiàng)集產(chǎn)生 使用圖使用圖來(lái)來(lái)解釋解釋Apriori算法發(fā)現(xiàn)算法發(fā)現(xiàn)D中的頻繁項(xiàng)集。中的頻繁項(xiàng)集。 7.2 頻繁項(xiàng)集產(chǎn)生 13 7.2.2 Apriori算法的頻繁項(xiàng)集產(chǎn)生 挖掘布

14、爾關(guān)聯(lián)規(guī)則發(fā)現(xiàn)頻繁項(xiàng)集的挖掘布爾關(guān)聯(lián)規(guī)則發(fā)現(xiàn)頻繁項(xiàng)集的AprioriApriori算法如下。算法如下。 算法算法：Apriori。使用逐層迭代方法基于候選產(chǎn)生找出頻繁項(xiàng)集。使用逐層迭代方法基于候選產(chǎn)生找出頻繁項(xiàng)集。 輸入輸入：事務(wù)數(shù)據(jù)庫(kù)：事務(wù)數(shù)據(jù)庫(kù)D；最小支持度閾值；最小支持度閾值min_sup。 輸出輸出：D中的頻繁項(xiàng)集中的頻繁項(xiàng)集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)行計(jì)數(shù)，進(jìn)行計(jì)數(shù) Ct=subset（Ck，t）

15、；）； /得到得到t的子集，它們是候選的子集，它們是候選 for each 候選候選cCt c.count+； ； Lk=cCk | c.countmin_sup； return L=k Lk； 7.2 頻繁項(xiàng)集產(chǎn)生 14 7.2.2 Apriori算法的頻繁項(xiàng)集產(chǎn)生 procedure apriori_gen（Lk-1：frequent（k-1）-itemsets） for each 項(xiàng)集項(xiàng)集l1 Lk-1 for each 項(xiàng)集 項(xiàng)集l2 Lk-1 if（ （l11=l21） . （l1k-2l2k-2） （l1k-1l2k-2） then c= l1 l2； /連接步：產(chǎn)生候選連接步：產(chǎn)

16、生候選 if has_infrequent_subset（c，Lk-1） then delete c； /剪枝步：刪除非頻繁的候選剪枝步：刪除非頻繁的候選 else add c to Ck； return Ck； procedure has_infrequent_subset(c：candidate k-itemsets；Lk- 1： ：frequent(k-1)-itemsets) /使用使用Apriori知識(shí)知識(shí) for each（k-1）-subset s of c if s Lk-1 then return TRUE； return FALSE； 7.2 頻繁項(xiàng)集產(chǎn)生 15 7.2.3

17、 支持度計(jì)數(shù) 支持度計(jì)數(shù)用以支持度計(jì)數(shù)用以確定在確定在apriori-gen函數(shù)的候選項(xiàng)剪枝步驟保留下來(lái)的函數(shù)的候選項(xiàng)剪枝步驟保留下來(lái)的 每個(gè)候選項(xiàng)集出現(xiàn)的頻繁程度。每個(gè)候選項(xiàng)集出現(xiàn)的頻繁程度。 計(jì)算支持度的主要方法有計(jì)算支持度的主要方法有兩種兩種： 一是一是將每個(gè)事務(wù)與所有候選項(xiàng)集進(jìn)行比較，并且更新包含在事務(wù)中的將每個(gè)事務(wù)與所有候選項(xiàng)集進(jìn)行比較，并且更新包含在事務(wù)中的 候選項(xiàng)集的支持度計(jì)數(shù)。這種方法的計(jì)算候選項(xiàng)集的支持度計(jì)數(shù)。這種方法的計(jì)算成本很高成本很高，尤其當(dāng)事務(wù)和候，尤其當(dāng)事務(wù)和候 選項(xiàng)集的數(shù)目都很大時(shí)。選項(xiàng)集的數(shù)目都很大時(shí)。 或或枚舉枚舉每個(gè)每個(gè)事務(wù)包含事務(wù)包含的項(xiàng)集，的項(xiàng)集，并利用

18、并利用其其更新更新對(duì)應(yīng)的候選項(xiàng)集的支持度。對(duì)應(yīng)的候選項(xiàng)集的支持度。 7.2 頻繁項(xiàng)集產(chǎn)生 16 7.2.3 支持度計(jì)數(shù) 如圖顯示的是枚舉事務(wù)如圖顯示的是枚舉事務(wù)t中所有中所有3-項(xiàng)集的系統(tǒng)的方法。假定每個(gè)項(xiàng)集項(xiàng)集的系統(tǒng)的方法。假定每個(gè)項(xiàng)集 中的項(xiàng)都以遞增的字典次序排列，則項(xiàng)集可以這樣枚舉：先指定最小項(xiàng)，中的項(xiàng)都以遞增的字典次序排列，則項(xiàng)集可以這樣枚舉：先指定最小項(xiàng)， 其后跟隨較大的項(xiàng)。其后跟隨較大的項(xiàng)。 7.2 頻繁項(xiàng)集產(chǎn)生 17 7.2.3 支持度計(jì)數(shù) 如如，給定，給定t=1，2，3，5，6，所有，所有3-項(xiàng)集一定以項(xiàng)項(xiàng)集一定以項(xiàng)1、2或或3開(kāi)始。不開(kāi)始。不 必構(gòu)造以必構(gòu)造以5或或6開(kāi)始的開(kāi)

19、始的3-項(xiàng)集。項(xiàng)集。圖中第一層的前綴結(jié)構(gòu)描述了指定包含在事圖中第一層的前綴結(jié)構(gòu)描述了指定包含在事 務(wù)務(wù)t中的中的3-項(xiàng)集的第一項(xiàng)的方法項(xiàng)集的第一項(xiàng)的方法。如。如1 2 3 5 6的的3-項(xiàng)集項(xiàng)集，以，以1開(kāi)始，后隨兩個(gè)開(kāi)始，后隨兩個(gè) 取自集合取自集合2，3，5，6的項(xiàng)的項(xiàng)。確定第一項(xiàng)后。確定第一項(xiàng)后，第二層的前綴結(jié)構(gòu)表示選擇，第二層的前綴結(jié)構(gòu)表示選擇 第二項(xiàng)的方法第二項(xiàng)的方法。如。如：1 2 3 5 6表示以表示以1，2為前綴，后隨項(xiàng)為前綴，后隨項(xiàng)3、5或或6的項(xiàng)集。的項(xiàng)集。 最后，第三層的前綴結(jié)構(gòu)顯示了事務(wù)最后，第三層的前綴結(jié)構(gòu)顯示了事務(wù)t包含的所有的包含的所有的3-項(xiàng)集項(xiàng)集。如。如，以，以

20、1，2 為前綴的為前綴的3-項(xiàng)集是項(xiàng)集是1，2，3，1，2，5和和1，2，6；而以；而以2，3為前綴為前綴 的的3-項(xiàng)集是項(xiàng)集是2，3，5和和2，3，6。 7.2 頻繁項(xiàng)集產(chǎn)生 18 7.2.3 支持度計(jì)數(shù) 在在Apriori算法中，候選項(xiàng)集劃分為不同的桶，并存放在算法中，候選項(xiàng)集劃分為不同的桶，并存放在Hash樹(shù)中。樹(shù)中。 在支持度計(jì)數(shù)期間，包含在事務(wù)中的項(xiàng)集也散列到相應(yīng)的桶中。這種方在支持度計(jì)數(shù)期間，包含在事務(wù)中的項(xiàng)集也散列到相應(yīng)的桶中。這種方 法不是將事務(wù)中的每個(gè)項(xiàng)集與所有的候選項(xiàng)集進(jìn)行比較，而是將它與同法不是將事務(wù)中的每個(gè)項(xiàng)集與所有的候選項(xiàng)集進(jìn)行比較，而是將它與同 一桶內(nèi)候選項(xiàng)集進(jìn)行匹

21、配一桶內(nèi)候選項(xiàng)集進(jìn)行匹配。 7.2 頻繁項(xiàng)集產(chǎn)生 19 7.2.3 支持度計(jì)數(shù) 上圖是一棵上圖是一棵Hash樹(shù)結(jié)構(gòu)的例子。樹(shù)的每個(gè)內(nèi)部結(jié)點(diǎn)都使用樹(shù)結(jié)構(gòu)的例子。樹(shù)的每個(gè)內(nèi)部結(jié)點(diǎn)都使用Hash函數(shù)函數(shù) h(p)=p mod 3來(lái)確定應(yīng)當(dāng)沿著當(dāng)前結(jié)點(diǎn)的哪個(gè)分支向下來(lái)確定應(yīng)當(dāng)沿著當(dāng)前結(jié)點(diǎn)的哪個(gè)分支向下。如。如，項(xiàng)，項(xiàng)1，4和和7 應(yīng)當(dāng)散列到相同的分支（即最左分支），因?yàn)槌詰?yīng)當(dāng)散列到相同的分支（即最左分支），因?yàn)槌?之后它們都具有相之后它們都具有相 同的余數(shù)。所有的候選項(xiàng)集都存放在同的余數(shù)。所有的候選項(xiàng)集都存放在Hash樹(shù)的葉結(jié)點(diǎn)中。圖中顯示的樹(shù)的葉結(jié)點(diǎn)中。圖中顯示的 Hash樹(shù)包含樹(shù)包含15個(gè)候選

22、個(gè)候選3-項(xiàng)集，即項(xiàng)集，即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個(gè)葉結(jié)點(diǎn)中。個(gè)葉結(jié)點(diǎn)中。 7.2 頻繁項(xiàng)集產(chǎn)生 20 7.2.3支持度計(jì)數(shù) 考慮一個(gè)事務(wù)考慮一個(gè)事務(wù)t=1，2，3，5，6。為了更新候選項(xiàng)集的支持度計(jì)數(shù)，。為了更新候選項(xiàng)集的支持度計(jì)數(shù)， 必須這樣遍歷必須這樣遍歷Hash樹(shù)：所有包含屬于事務(wù)樹(shù)：所有包含屬于事務(wù)t的候選的候選3-項(xiàng)集的葉結(jié)點(diǎn)至少訪(fǎng)項(xiàng)集的葉結(jié)點(diǎn)至少訪(fǎng) 問(wèn)一次。例如，在根結(jié)點(diǎn)散列項(xiàng)問(wèn)一次。例如，在根結(jié)點(diǎn)散列項(xiàng)

23、1之后，散列事務(wù)的項(xiàng)之后，散列事務(wù)的項(xiàng)2，3和和5。項(xiàng)。項(xiàng)2和和5散散 列到中間子女，而列到中間子女，而3散列到右子女，如圖所示。繼續(xù)該過(guò)程，直至到達(dá)散列到右子女，如圖所示。繼續(xù)該過(guò)程，直至到達(dá) Hash樹(shù)的葉結(jié)點(diǎn)。樹(shù)的葉結(jié)點(diǎn)。 7.2 頻繁項(xiàng)集產(chǎn)生 21 7.2.4 計(jì)算復(fù)雜度 AprioriApriori算法的計(jì)算復(fù)雜度受如下因素影響：算法的計(jì)算復(fù)雜度受如下因素影響： 支持度閾值支持度閾值。支持。支持度度閾值閾值影響影響頻繁項(xiàng)集數(shù)量。頻繁項(xiàng)集數(shù)量。 項(xiàng)數(shù)（維數(shù)）。隨著項(xiàng)數(shù)的增加，需要更多的空間來(lái)存儲(chǔ)項(xiàng)的支持項(xiàng)數(shù)（維數(shù)）。隨著項(xiàng)數(shù)的增加，需要更多的空間來(lái)存儲(chǔ)項(xiàng)的支持 度計(jì)數(shù)。度計(jì)數(shù)。如頻繁如

24、頻繁項(xiàng)集的數(shù)目也隨著數(shù)據(jù)項(xiàng)數(shù)增加而增長(zhǎng)，則由于算項(xiàng)集的數(shù)目也隨著數(shù)據(jù)項(xiàng)數(shù)增加而增長(zhǎng)，則由于算 法產(chǎn)生的候選項(xiàng)集更多，計(jì)算量和法產(chǎn)生的候選項(xiàng)集更多，計(jì)算量和I/O開(kāi)銷(xiāo)將增加。開(kāi)銷(xiāo)將增加。 事務(wù)數(shù)事務(wù)數(shù)。算法。算法反復(fù)掃描數(shù)據(jù)集反復(fù)掃描數(shù)據(jù)集，運(yùn)行時(shí)間，運(yùn)行時(shí)間隨著事務(wù)數(shù)增加而增加。隨著事務(wù)數(shù)增加而增加。 事務(wù)的平均寬度。對(duì)于密集數(shù)據(jù)集，事務(wù)的平均寬度可能很大，這事務(wù)的平均寬度。對(duì)于密集數(shù)據(jù)集，事務(wù)的平均寬度可能很大，這 將影響將影響Apriori算法的復(fù)雜度。算法的復(fù)雜度。 7.2 頻繁項(xiàng)集產(chǎn)生 22 7.2.4 計(jì)算復(fù)雜度 7.2 頻繁項(xiàng)集產(chǎn)生 23 因?yàn)橛深l繁項(xiàng)集的項(xiàng)組成的關(guān)聯(lián)規(guī)則的支持度大

25、于等于最小支持度因?yàn)橛深l繁項(xiàng)集的項(xiàng)組成的關(guān)聯(lián)規(guī)則的支持度大于等于最小支持度 閾值，所以規(guī)則產(chǎn)生過(guò)程就是在由頻繁項(xiàng)集的項(xiàng)組成的所有關(guān)聯(lián)規(guī)則閾值，所以規(guī)則產(chǎn)生過(guò)程就是在由頻繁項(xiàng)集的項(xiàng)組成的所有關(guān)聯(lián)規(guī)則 中，找出所有置信度大于等于最小置信度閾值的強(qiáng)關(guān)聯(lián)規(guī)則。中，找出所有置信度大于等于最小置信度閾值的強(qiáng)關(guān)聯(lián)規(guī)則。 計(jì)算關(guān)聯(lián)規(guī)則的置信度并不需要再次掃描事務(wù)數(shù)據(jù)庫(kù)。每個(gè)頻繁計(jì)算關(guān)聯(lián)規(guī)則的置信度并不需要再次掃描事務(wù)數(shù)據(jù)庫(kù)。每個(gè)頻繁k- 項(xiàng)集能產(chǎn)生最多項(xiàng)集能產(chǎn)生最多2k-2個(gè)關(guān)聯(lián)規(guī)則。個(gè)關(guān)聯(lián)規(guī)則。 7.3 規(guī)則產(chǎn)生 24 7.3.1 基本步驟 規(guī)則產(chǎn)生的基本步驟如下：規(guī)則產(chǎn)生的基本步驟如下： （1）對(duì)于每個(gè)頻

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

27、最小置信度閾值為如果最小置信度閾值為70，則只有，則只有2、3和最后一個(gè)規(guī)則可以輸出，和最后一個(gè)規(guī)則可以輸出， 因?yàn)橹挥羞@些是強(qiáng)的因?yàn)橹挥羞@些是強(qiáng)的。 7.3 規(guī)則產(chǎn)生 26 7.3.1 Apriori算法中規(guī)則的產(chǎn)生 Apriori算法使用一種逐層方法來(lái)產(chǎn)生關(guān)聯(lián)規(guī)則，其中每層對(duì)應(yīng)于規(guī)算法使用一種逐層方法來(lái)產(chǎn)生關(guān)聯(lián)規(guī)則，其中每層對(duì)應(yīng)于規(guī) 則后件中的項(xiàng)數(shù)。則后件中的項(xiàng)數(shù)。首先首先，提取規(guī)則后件只含一個(gè)項(xiàng)的所有高置信度規(guī)則，提取規(guī)則后件只含一個(gè)項(xiàng)的所有高置信度規(guī)則， 其次其次使用這些規(guī)則來(lái)產(chǎn)生新的候選規(guī)則。使用這些規(guī)則來(lái)產(chǎn)生新的候選規(guī)則。 7.3 規(guī)則產(chǎn)生 27 7.3.1 Apriori算法中規(guī)

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

29、程與頻繁項(xiàng)集產(chǎn)生過(guò)程類(lèi)似，二算法中規(guī)則產(chǎn)生過(guò)程與頻繁項(xiàng)集產(chǎn)生過(guò)程類(lèi)似，二 者唯一的不同是，在規(guī)則產(chǎn)生時(shí)，不必再次掃描數(shù)據(jù)者唯一的不同是，在規(guī)則產(chǎn)生時(shí)，不必再次掃描數(shù)據(jù)集計(jì)算集計(jì)算候選規(guī)則的候選規(guī)則的 置信度，置信度，而使用而使用頻繁項(xiàng)集產(chǎn)生時(shí)計(jì)算的支持度計(jì)數(shù)來(lái)頻繁項(xiàng)集產(chǎn)生時(shí)計(jì)算的支持度計(jì)數(shù)來(lái)確定規(guī)則確定規(guī)則的置信度的置信度。 7.3 規(guī)則產(chǎn)生 28 實(shí)踐中，由事務(wù)數(shù)據(jù)集產(chǎn)生的頻繁項(xiàng)集的數(shù)量可能非常大。因此，實(shí)踐中，由事務(wù)數(shù)據(jù)集產(chǎn)生的頻繁項(xiàng)集的數(shù)量可能非常大。因此， 從中識(shí)別出可以推導(dǎo)出其他所有的頻繁項(xiàng)集的、較小的、具有代表性的從中識(shí)別出可以推導(dǎo)出其他所有的頻繁項(xiàng)集的、較小的、具有代表性的 項(xiàng)集

30、是非常有用的。項(xiàng)集是非常有用的。 下面介紹兩種具有代表性的項(xiàng)集：下面介紹兩種具有代表性的項(xiàng)集： 最大頻繁項(xiàng)集最大頻繁項(xiàng)集 閉頻繁項(xiàng)集閉頻繁項(xiàng)集 7.4 頻繁項(xiàng)集的緊湊表示 29 7.4.1 最大頻繁項(xiàng)集 最大頻繁項(xiàng)集：直接超集都不是頻繁的。 7.4 頻繁項(xiàng)集的緊湊表示 30 7.4.1 最大頻繁項(xiàng)集 上上圖所示是圖所示是項(xiàng)集格。格中的項(xiàng)集分為兩組：頻繁項(xiàng)集和非頻繁項(xiàng)集。項(xiàng)集格。格中的項(xiàng)集分為兩組：頻繁項(xiàng)集和非頻繁項(xiàng)集。 虛線(xiàn)表示頻繁項(xiàng)集的邊界。位于邊界上方的每個(gè)項(xiàng)集都是頻繁的，而位于虛線(xiàn)表示頻繁項(xiàng)集的邊界。位于邊界上方的每個(gè)項(xiàng)集都是頻繁的，而位于 邊界下方的項(xiàng)集（陰影結(jié)點(diǎn)）都是非頻繁的。在邊界

31、邊界下方的項(xiàng)集（陰影結(jié)點(diǎn)）都是非頻繁的。在邊界附近結(jié)點(diǎn)附近結(jié)點(diǎn)中，中，a，d， a，c，e和和b，c，d，e都是最大頻繁項(xiàng)集，因?yàn)樗鼈兊闹苯映际欠穷l都是最大頻繁項(xiàng)集，因?yàn)樗鼈兊闹苯映际欠穷l 繁的繁的。如。如，項(xiàng)集，項(xiàng)集a，d是最大頻繁的，因?yàn)樗乃兄苯映亲畲箢l繁的，因?yàn)樗乃兄苯映痑，b，d ， a，c，d和和a，d，e都是非頻繁的；相反，項(xiàng)集都是非頻繁的；相反，項(xiàng)集a，c不是最大的，因?yàn)椴皇亲畲蟮模驗(yàn)?它的一個(gè)直接超集它的一個(gè)直接超集a，c，e是頻繁的是頻繁的。最大。最大頻繁項(xiàng)集有效地提供了頻繁項(xiàng)頻繁項(xiàng)集有效地提供了頻繁項(xiàng) 集的緊湊表示集的緊湊表示。最大。最大頻繁項(xiàng)集形成

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

33、與它相關(guān)聯(lián)的事務(wù)的ID。例如，由于結(jié)點(diǎn)。例如，由于結(jié)點(diǎn)b， c與與事務(wù)事務(wù)ID 1，2和和3相關(guān)聯(lián)，因此它的支持度計(jì)數(shù)為相關(guān)聯(lián)，因此它的支持度計(jì)數(shù)為3。從給定的事務(wù)可以。從給定的事務(wù)可以 看出，包含看出，包含b的每個(gè)事務(wù)也包含的每個(gè)事務(wù)也包含c，因此，由于，因此，由于b和和b，c的支持度是相同的支持度是相同 的，所以的，所以b不是閉項(xiàng)集。同樣，由于不是閉項(xiàng)集。同樣，由于c出現(xiàn)在所有包含出現(xiàn)在所有包含a和和d的事務(wù)中，所的事務(wù)中，所 以項(xiàng)集以項(xiàng)集a，d不是閉的。另一方面，不是閉的。另一方面， b，c是閉項(xiàng)集，因?yàn)樗闹С侄扔?jì)是閉項(xiàng)集，因?yàn)樗闹С侄扔?jì) 數(shù)與它的任何超集都不同。數(shù)與它的任何超集都不

34、同。 7.4 頻繁項(xiàng)集的緊湊表示 33 Apriori算法通過(guò)使用先驗(yàn)原理對(duì)指數(shù)搜索空間進(jìn)行剪枝，成功地處理算法通過(guò)使用先驗(yàn)原理對(duì)指數(shù)搜索空間進(jìn)行剪枝，成功地處理 了頻繁項(xiàng)集產(chǎn)生的組合爆炸問(wèn)題。雖然顯著提高了性能，但該算法還是會(huì)了頻繁項(xiàng)集產(chǎn)生的組合爆炸問(wèn)題。雖然顯著提高了性能，但該算法還是會(huì) 導(dǎo)致不可低估的導(dǎo)致不可低估的I/O開(kāi)銷(xiāo)，因?yàn)樗枰啻螔呙枋聞?wù)數(shù)據(jù)集。此外，對(duì)于稠開(kāi)銷(xiāo)，因?yàn)樗枰啻螔呙枋聞?wù)數(shù)據(jù)集。此外，對(duì)于稠 密數(shù)據(jù)集，由于事務(wù)數(shù)據(jù)寬度的增加，密數(shù)據(jù)集，由于事務(wù)數(shù)據(jù)寬度的增加，Apriori算法的性能顯著降低。為了算法的性能顯著降低。為了 克服這些局限性和提高克服這些局限性和提高A

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

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

37、集的 邊界靠近格的底部，如上圖（邊界靠近格的底部，如上圖（b）所示。可以使用先驗(yàn)原理剪掉最大頻繁項(xiàng)）所示?？梢允褂孟闰?yàn)原理剪掉最大頻繁項(xiàng) 集的所有子集。另一種策略是結(jié)合集的所有子集。另一種策略是結(jié)合“一般到特殊一般到特殊”和和“特殊到一般特殊到一般”的搜的搜 索策略，盡管這種雙向搜索方法需要更多的空間存儲(chǔ)候選項(xiàng)集，但是上圖索策略，盡管這種雙向搜索方法需要更多的空間存儲(chǔ)候選項(xiàng)集，但是上圖 （c）所示的布局，該方法有助于加快確定頻繁項(xiàng)集邊界。）所示的布局，該方法有助于加快確定頻繁項(xiàng)集邊界。 7.5 產(chǎn)生頻繁項(xiàng)集的其它方法 36 7.5.1 項(xiàng)集格遍歷 等價(jià)類(lèi)等價(jià)類(lèi) 該方法是先將格劃分為兩個(gè)不相交的

38、結(jié)點(diǎn)組（或等價(jià)類(lèi)）。頻繁項(xiàng)該方法是先將格劃分為兩個(gè)不相交的結(jié)點(diǎn)組（或等價(jià)類(lèi)）。頻繁項(xiàng) 集產(chǎn)生算法依次在每個(gè)等價(jià)類(lèi)內(nèi)搜索頻繁項(xiàng)集。集產(chǎn)生算法依次在每個(gè)等價(jià)類(lèi)內(nèi)搜索頻繁項(xiàng)集。 7.5 產(chǎn)生頻繁項(xiàng)集的其它方法 37 7.5.1 項(xiàng)集格遍歷 Apriori算法采用的逐層策略可以看作根據(jù)項(xiàng)集的大小劃分格，即在算法采用的逐層策略可以看作根據(jù)項(xiàng)集的大小劃分格，即在 處理較大項(xiàng)集之前，首先找出所有的頻繁處理較大項(xiàng)集之前，首先找出所有的頻繁1-項(xiàng)集。等價(jià)類(lèi)也可以根據(jù)項(xiàng)集項(xiàng)集。等價(jià)類(lèi)也可以根據(jù)項(xiàng)集 的前綴或后綴來(lái)定義。在這種情況下，兩個(gè)項(xiàng)集屬于同一個(gè)等價(jià)類(lèi)，如的前綴或后綴來(lái)定義。在這種情況下，兩個(gè)項(xiàng)集屬于同一個(gè)等

39、價(jià)類(lèi)，如 果它們共享長(zhǎng)度為果它們共享長(zhǎng)度為k的相同前綴或后綴。在基于前綴的方法中，算法首先的相同前綴或后綴。在基于前綴的方法中，算法首先 搜索以前綴搜索以前綴a開(kāi)始的頻繁項(xiàng)集，然后是以前綴開(kāi)始的頻繁項(xiàng)集，然后是以前綴b等開(kāi)始的頻繁項(xiàng)集，然后等開(kāi)始的頻繁項(xiàng)集，然后 中中c，如此下去?；谇熬Y和基于后綴的等價(jià)類(lèi)都可以使用，如此下去?；谇熬Y和基于后綴的等價(jià)類(lèi)都可以使用上上圖中所示的圖中所示的 類(lèi)似于樹(shù)的結(jié)構(gòu)來(lái)演示。類(lèi)似于樹(shù)的結(jié)構(gòu)來(lái)演示。 7.5 產(chǎn)生頻繁項(xiàng)集的其它方法 38 7.5.1 項(xiàng)集格遍歷 寬度優(yōu)先與深度優(yōu)先寬度優(yōu)先與深度優(yōu)先 Apriori算法采用寬度優(yōu)先的方法遍歷格，如圖（算法采用寬度

40、優(yōu)先的方法遍歷格，如圖（a）所示。它首先發(fā)）所示。它首先發(fā) 現(xiàn)所有頻繁現(xiàn)所有頻繁1-項(xiàng)集，接下來(lái)是頻繁項(xiàng)集，接下來(lái)是頻繁2-項(xiàng)集，如此下去直到?jīng)]有新的頻繁項(xiàng)項(xiàng)集，如此下去直到?jīng)]有新的頻繁項(xiàng) 集產(chǎn)生為止。也可以以用深度優(yōu)先的方式遍歷項(xiàng)集格，如圖（集產(chǎn)生為止。也可以以用深度優(yōu)先的方式遍歷項(xiàng)集格，如圖（b）所示。）所示。 7.5 產(chǎn)生頻繁項(xiàng)集的其它方法 39 7.5.1項(xiàng)集格遍歷 比如說(shuō)，算法可以從圖中的結(jié)點(diǎn)比如說(shuō)，算法可以從圖中的結(jié)點(diǎn)a開(kāi)始，計(jì)算其支持度計(jì)數(shù)并判斷它是開(kāi)始，計(jì)算其支持度計(jì)數(shù)并判斷它是 否頻繁。如果是，算法漸增地?cái)U(kuò)展下層結(jié)點(diǎn)，即否頻繁。如果是，算法漸增地?cái)U(kuò)展下層結(jié)點(diǎn)，即ab，abc，

41、等等，直到到達(dá)，等等，直到到達(dá) 一個(gè)非頻繁結(jié)點(diǎn)，如一個(gè)非頻繁結(jié)點(diǎn)，如abcd。然后，回溯到下一個(gè)分支，比如說(shuō)。然后，回溯到下一個(gè)分支，比如說(shuō)abce，并且繼，并且繼 續(xù)搜索。續(xù)搜索。 7.5 產(chǎn)生頻繁項(xiàng)集的其它方法 40 7.5.1 項(xiàng)集格遍歷 通常，深度優(yōu)先搜索方法用于發(fā)現(xiàn)最大頻繁項(xiàng)集通常，深度優(yōu)先搜索方法用于發(fā)現(xiàn)最大頻繁項(xiàng)集。比寬度優(yōu)先更。比寬度優(yōu)先更快快 地檢測(cè)到頻繁項(xiàng)集邊界。一旦發(fā)現(xiàn)一個(gè)最大頻繁項(xiàng)集，就地檢測(cè)到頻繁項(xiàng)集邊界。一旦發(fā)現(xiàn)一個(gè)最大頻繁項(xiàng)集，就可在可在它的子集它的子集 上剪枝。如上剪枝。如，上圖中的結(jié)點(diǎn)，上圖中的結(jié)點(diǎn)bcde是最大頻繁項(xiàng)集，則算法就不必訪(fǎng)問(wèn)以是最大頻繁項(xiàng)集，則算

42、法就不必訪(fǎng)問(wèn)以bd， be，c，d和和e為根的子樹(shù)，因?yàn)樗鼈儾豢赡馨魏巫畲箢l繁項(xiàng)集。然而，為根的子樹(shù)，因?yàn)樗鼈儾豢赡馨魏巫畲箢l繁項(xiàng)集。然而， 如如abc是最大頻繁項(xiàng)集，則只有是最大頻繁項(xiàng)集，則只有ac和和bc這樣的結(jié)點(diǎn)不是最大頻繁項(xiàng)集，但這樣的結(jié)點(diǎn)不是最大頻繁項(xiàng)集，但 以它們?yōu)楦淖訕?shù)還可能包含最大頻繁項(xiàng)集。深度優(yōu)先方法還允許使用以它們?yōu)楦淖訕?shù)還可能包含最大頻繁項(xiàng)集。深度優(yōu)先方法還允許使用 不同的基于項(xiàng)集支持度的剪枝方法不同的基于項(xiàng)集支持度的剪枝方法。如。如，假定項(xiàng)集，假定項(xiàng)集 a，b，c和和a，b具具 有相同的支持度，則有相同的支持度，則可跳可跳過(guò)以過(guò)以abd和和abe為根的子樹(shù)為

43、根的子樹(shù)，不，不包含最大頻繁項(xiàng)集。包含最大頻繁項(xiàng)集。 7.5 產(chǎn)生頻繁項(xiàng)集的其它方法 41 7.5.2 事務(wù)數(shù)據(jù)集的表示 表示表示購(gòu)物籃事務(wù)的兩種不同方法。左邊的表示法稱(chēng)作購(gòu)物籃事務(wù)的兩種不同方法。左邊的表示法稱(chēng)作水平數(shù)據(jù)布局水平數(shù)據(jù)布局，許多，許多 關(guān)聯(lián)規(guī)則挖掘算法（包括關(guān)聯(lián)規(guī)則挖掘算法（包括Apriori）都采用這種表示法；）都采用這種表示法；右右邊的表示法是存邊的表示法是存 儲(chǔ)與每一個(gè)項(xiàng)相關(guān)聯(lián)的事務(wù)標(biāo)識(shí)符列表（儲(chǔ)與每一個(gè)項(xiàng)相關(guān)聯(lián)的事務(wù)標(biāo)識(shí)符列表（TID列表），這種表示法稱(chēng)作列表），這種表示法稱(chēng)作垂直垂直 數(shù)據(jù)布局?jǐn)?shù)據(jù)布局。候選項(xiàng)集的支持度通過(guò)取其子項(xiàng)集。候選項(xiàng)集的支持度通過(guò)取其子項(xiàng)集TI

44、D列表的交得到。列表的交得到。 7.5 產(chǎn)生頻繁項(xiàng)集的其它方法 42 7.6FP-growth算法 FP-growth（Frequent-Pattern growth，頻繁模式增長(zhǎng)）算法的，頻繁模式增長(zhǎng)）算法的基本思基本思 想想是是采用分采用分治策略：首先，將代表頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵治策略：首先，將代表頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵FP樹(shù)（樹(shù)（F requent-Pattern tree，頻繁模式樹(shù)），該樹(shù)仍保留項(xiàng)集的關(guān)聯(lián)信息。，頻繁模式樹(shù)），該樹(shù)仍保留項(xiàng)集的關(guān)聯(lián)信息。其其 次次，將這種壓縮后的數(shù)據(jù)庫(kù)劃分成一組條件數(shù)據(jù)庫(kù)（一種特殊類(lèi)型的投影，將這種壓縮后的數(shù)據(jù)庫(kù)劃分成一組條件數(shù)據(jù)庫(kù)（一種特殊

45、類(lèi)型的投影 數(shù)據(jù)庫(kù)），每個(gè)數(shù)據(jù)庫(kù)關(guān)聯(lián)一個(gè)頻繁項(xiàng)或數(shù)據(jù)庫(kù)），每個(gè)數(shù)據(jù)庫(kù)關(guān)聯(lián)一個(gè)頻繁項(xiàng)或“模式段模式段”，并分別挖掘每個(gè)條，并分別挖掘每個(gè)條 件數(shù)據(jù)庫(kù)。對(duì)于每個(gè)件數(shù)據(jù)庫(kù)。對(duì)于每個(gè)“模式片段模式片段”，只需要考察與它相關(guān)聯(lián)數(shù)據(jù)集，只需要考察與它相關(guān)聯(lián)數(shù)據(jù)集。隨著。隨著 被考察的模式的被考察的模式的“增長(zhǎng)增長(zhǎng)”，可以，可以顯著地壓縮被搜索的數(shù)據(jù)集的大小。顯著地壓縮被搜索的數(shù)據(jù)集的大小。 43 7.6.1 FP樹(shù)構(gòu)造 利用利用FP-growthFP-growth算法構(gòu)造頻繁模式樹(shù)的過(guò)程如下：算法構(gòu)造頻繁模式樹(shù)的過(guò)程如下： （1）按）按Apriori算法，第一次掃描事務(wù)數(shù)據(jù)庫(kù)算法，第一次掃描事務(wù)數(shù)據(jù)庫(kù)D，

46、導(dǎo)出頻繁，導(dǎo)出頻繁1-項(xiàng)集，并項(xiàng)集，并 得到它們的支持度計(jì)數(shù)（頻度）。設(shè)最小支持度計(jì)數(shù)為得到它們的支持度計(jì)數(shù)（頻度）。設(shè)最小支持度計(jì)數(shù)為2 ，頻繁項(xiàng)的集合，頻繁項(xiàng)的集合 按支持度計(jì)數(shù)的降序排序。結(jié)果集或表記作按支持度計(jì)數(shù)的降序排序。結(jié)果集或表記作L。這樣有。這樣有L=I2:7，I1:6， I3:6，I4:2，I5:2，如圖所示。，如圖所示。 7.6FP-growth算法 44 7.6.1 FP樹(shù)構(gòu)造 （2）創(chuàng)建樹(shù)的根結(jié)點(diǎn)，并標(biāo)記為）創(chuàng)建樹(shù)的根結(jié)點(diǎn)，并標(biāo)記為“null”。第二次掃描數(shù)據(jù)庫(kù)。第二次掃描數(shù)據(jù)庫(kù)D。每個(gè)。每個(gè) 事務(wù)中的項(xiàng)都按事務(wù)中的項(xiàng)都按L中的次序處理（即按支持度計(jì)數(shù)降序排序），并對(duì)每

47、個(gè)事中的次序處理（即按支持度計(jì)數(shù)降序排序），并對(duì)每個(gè)事 務(wù)創(chuàng)建一個(gè)分枝。例如，第一個(gè)事務(wù)務(wù)創(chuàng)建一個(gè)分枝。例如，第一個(gè)事務(wù)“T100：I1，I2，I5”按按L的次序包含的次序包含 三個(gè)項(xiàng)三個(gè)項(xiàng)I2，I1，I5，導(dǎo)致構(gòu)造樹(shù)的第一個(gè)分枝，導(dǎo)致構(gòu)造樹(shù)的第一個(gè)分枝。該分枝具有。該分枝具有3個(gè)結(jié)點(diǎn)，其中個(gè)結(jié)點(diǎn)，其中I2作為根的子女鏈接到根，作為根的子女鏈接到根，I1鏈接到鏈接到I2，I5鏈鏈 接到接到I1，如圖所示。，如圖所示。 7.6FP-growth算法 45 7.6.1 FP樹(shù)構(gòu)造 第二個(gè)事務(wù)第二個(gè)事務(wù)T200按按L的次序包含的次序包含I2和和I4，它導(dǎo)致一個(gè)分枝，其中，它導(dǎo)致一個(gè)分枝，其中I2鏈鏈

48、 接到根，接到根，I4鏈接到鏈接到I2。然而，該分枝。然而，該分枝應(yīng)與應(yīng)與T100已存在的路徑共享前綴已存在的路徑共享前綴。 因此將因此將結(jié)點(diǎn)結(jié)點(diǎn)I2的計(jì)數(shù)增加的計(jì)數(shù)增加1，并創(chuàng)建一個(gè)新結(jié)點(diǎn)（，并創(chuàng)建一個(gè)新結(jié)點(diǎn)（I4:1），它作為（），它作為（I2:2） 子女鏈接，如圖所示。一般地，當(dāng)為一個(gè)事務(wù)考慮增加分枝時(shí)，沿共同前子女鏈接，如圖所示。一般地，當(dāng)為一個(gè)事務(wù)考慮增加分枝時(shí)，沿共同前 綴上的每個(gè)結(jié)點(diǎn)的計(jì)數(shù)增加綴上的每個(gè)結(jié)點(diǎn)的計(jì)數(shù)增加1，為隨在前綴之后的項(xiàng)創(chuàng)建結(jié)點(diǎn)并鏈接。，為隨在前綴之后的項(xiàng)創(chuàng)建結(jié)點(diǎn)并鏈接。 7.6FP-growth算法 46 7.6.1 FP樹(shù)構(gòu)造 為了方便樹(shù)的遍歷，創(chuàng)建一個(gè)項(xiàng)頭

49、表，使每項(xiàng)通過(guò)一個(gè)結(jié)點(diǎn)鏈指向它為了方便樹(shù)的遍歷，創(chuàng)建一個(gè)項(xiàng)頭表，使每項(xiàng)通過(guò)一個(gè)結(jié)點(diǎn)鏈指向它 在樹(shù)中的位置。掃描所有的事務(wù)后得到的樹(shù)在樹(shù)中的位置。掃描所有的事務(wù)后得到的樹(shù)如圖所示如圖所示，帶有相關(guān)的結(jié)點(diǎn)鏈。，帶有相關(guān)的結(jié)點(diǎn)鏈。 這樣，數(shù)據(jù)庫(kù)頻繁模式的挖掘問(wèn)題就轉(zhuǎn)換成挖掘這樣，數(shù)據(jù)庫(kù)頻繁模式的挖掘問(wèn)題就轉(zhuǎn)換成挖掘FP樹(shù)的問(wèn)題。樹(shù)的問(wèn)題。 7.6FP-growth算法 47 7.6.2 頻繁項(xiàng)集產(chǎn)生 FP FP樹(shù)的挖掘過(guò)程為：樹(shù)的挖掘過(guò)程為： 由長(zhǎng)度為由長(zhǎng)度為1的頻繁模式（初始后綴模式）開(kāi)始，構(gòu)造它的條件模式基的頻繁模式（初始后綴模式）開(kāi)始，構(gòu)造它的條件模式基 （一個(gè)（一個(gè)“子數(shù)據(jù)庫(kù)子數(shù)據(jù)庫(kù)”，由，

50、由FP樹(shù)中與該后綴模式一起出現(xiàn)的前綴路徑集組樹(shù)中與該后綴模式一起出現(xiàn)的前綴路徑集組 成）。然后，構(gòu)造它的（條件）成）。然后，構(gòu)造它的（條件）FP樹(shù)，并遞歸地在該樹(shù)上進(jìn)行挖掘。模式樹(shù)，并遞歸地在該樹(shù)上進(jìn)行挖掘。模式 增長(zhǎng)通過(guò)后綴模式與條件增長(zhǎng)通過(guò)后綴模式與條件FP樹(shù)產(chǎn)生的頻繁模式連接實(shí)現(xiàn)。樹(shù)產(chǎn)生的頻繁模式連接實(shí)現(xiàn)。 7.6FP-growth算法 48 7.6.2 頻繁項(xiàng)集產(chǎn)生 該該FP樹(shù)的挖掘過(guò)程總結(jié)如樹(shù)的挖掘過(guò)程總結(jié)如上上表所示。首先考慮表所示。首先考慮I5，它是，它是L中的最后一項(xiàng)，中的最后一項(xiàng)， 而不是第一項(xiàng)而不是第一項(xiàng)。I5出現(xiàn)在出現(xiàn)在FP樹(shù)的兩個(gè)分枝中（樹(shù)的兩個(gè)分枝中（I5的出現(xiàn)容易通

51、過(guò)沿它的結(jié)的出現(xiàn)容易通過(guò)沿它的結(jié) 點(diǎn)鏈找到）。這些路徑由分枝點(diǎn)鏈找到）。這些路徑由分枝和和形成。因此，形成。因此， 考慮以考慮以I5為后綴，它的兩個(gè)對(duì)應(yīng)前綴路徑是為后綴，它的兩個(gè)對(duì)應(yīng)前綴路徑是和和，形，形 成成I5的條件模式基。使用這些條件模式基作為事務(wù)數(shù)據(jù)庫(kù)，構(gòu)造的條件模式基。使用這些條件模式基作為事務(wù)數(shù)據(jù)庫(kù)，構(gòu)造I5的條件的條件 FP樹(shù)，它只包含單個(gè)路徑樹(shù)，它只包含單個(gè)路徑；不包含；不包含I3，因?yàn)樗闹С?，因?yàn)樗闹С侄榷?，小，小 于最小支持度計(jì)數(shù)。該單個(gè)路徑產(chǎn)生頻繁模式的所有組合：于最小支持度計(jì)數(shù)。該單個(gè)路徑產(chǎn)生頻繁模式的所有組合：I2 I5:2，I1 I5:2， I2 I1 I5:

52、2。對(duì)于。對(duì)于I4，它的兩個(gè)前綴形成條件模式基，它的兩個(gè)前綴形成條件模式基(I2 I1:1）,（I2:1)，產(chǎn)，產(chǎn) 生一個(gè)單結(jié)點(diǎn)的條件生一個(gè)單結(jié)點(diǎn)的條件FP樹(shù)樹(shù)，并導(dǎo)出一個(gè)頻繁模式，并導(dǎo)出一個(gè)頻繁模式I2 I4:2。 7.6FP-growth算法 49 7.6.2 頻繁項(xiàng)集產(chǎn)生 類(lèi)似于以上分析，類(lèi)似于以上分析，I3的條件模式基是的條件模式基是(I2 I1:2）,（I2:2）,（I1:2)。它。它 的條件的條件FP樹(shù)有兩個(gè)分枝樹(shù)有兩個(gè)分枝和和，如圖所示，它產(chǎn)生模式集：，如圖所示，它產(chǎn)生模式集： I2 I3:4，I1 I3:4，I2 I1 I3:2。最后，。最后，I1的條件模式基是的條件模式基是(

53、I2:4)，它的，它的FP樹(shù)樹(shù) 只包含一個(gè)結(jié)點(diǎn)只包含一個(gè)結(jié)點(diǎn)，只產(chǎn)生一個(gè)頻繁模式，只產(chǎn)生一個(gè)頻繁模式I2 I1:4。 7.6FP-growth算法 50 7.6.2 頻繁項(xiàng)集產(chǎn)生 7.6FP-growth算法 51 7.6.2 頻繁項(xiàng)集產(chǎn)生 優(yōu)點(diǎn)：優(yōu)點(diǎn)： FP-growth算法僅僅遍歷了算法僅僅遍歷了2次數(shù)據(jù)庫(kù)，第一次是為了產(chǎn)生次數(shù)據(jù)庫(kù)，第一次是為了產(chǎn)生L1，第二，第二 次是為了對(duì)項(xiàng)目排序。由于不用多次掃描數(shù)據(jù)庫(kù)，次是為了對(duì)項(xiàng)目排序。由于不用多次掃描數(shù)據(jù)庫(kù)，因而因而大大節(jié)省了掃大大節(jié)省了掃 描數(shù)據(jù)庫(kù)的時(shí)間；描數(shù)據(jù)庫(kù)的時(shí)間； 選用了分治策略，把挖掘的長(zhǎng)頻繁模式轉(zhuǎn)換成遞歸地挖掘短模式的問(wèn)選用了分治

54、策略，把挖掘的長(zhǎng)頻繁模式轉(zhuǎn)換成遞歸地挖掘短模式的問(wèn) 題，再與后綴相連；題，再與后綴相連； 挖掘長(zhǎng)頻繁模式與短的頻繁模式時(shí)，有效性與可伸縮性都是該算法的挖掘長(zhǎng)頻繁模式與短的頻繁模式時(shí)，有效性與可伸縮性都是該算法的 特點(diǎn)，特點(diǎn)，所用所用挖掘時(shí)間會(huì)比挖掘時(shí)間會(huì)比Apriori算法的挖掘時(shí)間少得多。算法的挖掘時(shí)間少得多。 7.6FP-growth算法 52 7.6.2 頻繁項(xiàng)集產(chǎn)生 缺點(diǎn)：缺點(diǎn)： 建立建立FP樹(shù)時(shí)，會(huì)占用大量的內(nèi)存空間。如果數(shù)據(jù)庫(kù)的規(guī)模很大，要樹(shù)時(shí)，會(huì)占用大量的內(nèi)存空間。如果數(shù)據(jù)庫(kù)的規(guī)模很大，要 建立的建立的FP樹(shù)也會(huì)很巨大；樹(shù)也會(huì)很巨大； 在遞歸構(gòu)建在遞歸構(gòu)建FP樹(shù)時(shí)，每生成一個(gè)頻繁

55、模式就會(huì)出現(xiàn)一個(gè)條件樹(shù)。當(dāng)樹(shù)時(shí)，每生成一個(gè)頻繁模式就會(huì)出現(xiàn)一個(gè)條件樹(shù)。當(dāng) 生成與釋放海量的條件樹(shù)時(shí)，生成與釋放海量的條件樹(shù)時(shí)，該算法該算法將占用很多的運(yùn)算時(shí)間與計(jì)算將占用很多的運(yùn)算時(shí)間與計(jì)算 機(jī)空間。機(jī)空間。 7.6FP-growth算法 53 7.7關(guān)聯(lián)評(píng)估 在實(shí)際情況中，商業(yè)數(shù)據(jù)庫(kù)的數(shù)據(jù)量和維數(shù)都非常大，運(yùn)用關(guān)聯(lián)分析在實(shí)際情況中，商業(yè)數(shù)據(jù)庫(kù)的數(shù)據(jù)量和維數(shù)都非常大，運(yùn)用關(guān)聯(lián)分析 算法往往產(chǎn)生大量的規(guī)則，而其中很大一部分可能是不感興趣的。因此，算法往往產(chǎn)生大量的規(guī)則，而其中很大一部分可能是不感興趣的。因此， 建立一組廣泛接受的評(píng)價(jià)關(guān)聯(lián)模式質(zhì)量的標(biāo)準(zhǔn)是非常重要的。建立一組廣泛接受的評(píng)價(jià)關(guān)聯(lián)模式質(zhì)

56、量的標(biāo)準(zhǔn)是非常重要的。 第一組標(biāo)準(zhǔn)第一組標(biāo)準(zhǔn)可通過(guò)可通過(guò)統(tǒng)計(jì)論據(jù)建立。涉及相互獨(dú)立的項(xiàng)或覆蓋少量事務(wù)統(tǒng)計(jì)論據(jù)建立。涉及相互獨(dú)立的項(xiàng)或覆蓋少量事務(wù) 的模式被認(rèn)為是不令人感興趣的，因?yàn)樗鼈兛赡芊从硵?shù)據(jù)中的偽聯(lián)系。的模式被認(rèn)為是不令人感興趣的，因?yàn)樗鼈兛赡芊从硵?shù)據(jù)中的偽聯(lián)系。 第二組標(biāo)準(zhǔn)第二組標(biāo)準(zhǔn)可通過(guò)可通過(guò)主觀論據(jù)建立，即模式被主觀地認(rèn)為是無(wú)趣的，除主觀論據(jù)建立，即模式被主觀地認(rèn)為是無(wú)趣的，除 非它能夠揭示料想不到的信息或提供導(dǎo)致有益的行動(dòng)的有用信息非它能夠揭示料想不到的信息或提供導(dǎo)致有益的行動(dòng)的有用信息。 54 7.7.1 興趣度客觀度量 客觀度量常?；诹新?lián)表中列出的頻度計(jì)數(shù)來(lái)計(jì)算。一對(duì)二元變

57、量客觀度量常常基于列聯(lián)表中列出的頻度計(jì)數(shù)來(lái)計(jì)算。一對(duì)二元變量A和和 B的列聯(lián)表的列聯(lián)表如表所示如表所示。使用記號(hào)。使用記號(hào) A（B）表示）表示A（B）不在事務(wù)中出現(xiàn)。在這）不在事務(wù)中出現(xiàn)。在這 個(gè)個(gè)22的表中，每個(gè)的表中，每個(gè)fij都代表一個(gè)頻度計(jì)數(shù)都代表一個(gè)頻度計(jì)數(shù)。如。如，f11表示表示A和和B同時(shí)出現(xiàn)在一同時(shí)出現(xiàn)在一 個(gè)事務(wù)中的次數(shù)，個(gè)事務(wù)中的次數(shù)，f01表示包含表示包含B但不包含但不包含A的事務(wù)的個(gè)數(shù)。行和的事務(wù)的個(gè)數(shù)。行和f1+表示表示A的支的支 持度計(jì)數(shù)，而列和持度計(jì)數(shù)，而列和f+1表示表示B的支持度計(jì)數(shù)。的支持度計(jì)數(shù)。 7.7關(guān)聯(lián)評(píng)估 55 7.7.1 興趣度客觀度量 支持度置信

58、度框架的局限性支持度置信度框架的局限性。現(xiàn)有關(guān)聯(lián)規(guī)則的挖掘算法依賴(lài)于支持?，F(xiàn)有關(guān)聯(lián)規(guī)則的挖掘算法依賴(lài)于支持 度和置信度來(lái)除去沒(méi)有意義的模式。支持度的缺點(diǎn)在于許多潛在的有意義度和置信度來(lái)除去沒(méi)有意義的模式。支持度的缺點(diǎn)在于許多潛在的有意義 的模式由于包含支持度小的項(xiàng)而被刪去。置信度的缺點(diǎn)的模式由于包含支持度小的項(xiàng)而被刪去。置信度的缺點(diǎn)更微妙更微妙，最適合用，最適合用 下面的例子進(jìn)行說(shuō)明下面的例子進(jìn)行說(shuō)明。假定。假定希望分析愛(ài)喝咖啡和愛(ài)喝茶的人之間的關(guān)系。希望分析愛(ài)喝咖啡和愛(ài)喝茶的人之間的關(guān)系。 收集一組人關(guān)于飲料偏愛(ài)的信息，并匯總在表中。收集一組人關(guān)于飲料偏愛(ài)的信息，并匯總在表中。 7.7關(guān)聯(lián)評(píng)

59、估 56 7.7.1 興趣度客觀度量 7.7關(guān)聯(lián)評(píng)估 57 7.7.1 興趣度客觀度量 興趣因子興趣因子。茶和咖啡的例子表明，由于置信度度量忽略了規(guī)則后件中。茶和咖啡的例子表明，由于置信度度量忽略了規(guī)則后件中 出現(xiàn)的項(xiàng)集的支持度，高置信度的規(guī)則有時(shí)存在誤導(dǎo)。解決這個(gè)問(wèn)題的一出現(xiàn)的項(xiàng)集的支持度，高置信度的規(guī)則有時(shí)存在誤導(dǎo)。解決這個(gè)問(wèn)題的一 種方法是使用稱(chēng)作提升度（種方法是使用稱(chēng)作提升度（lift）的度量）的度量： 它計(jì)算規(guī)則置信度和規(guī)則后件中項(xiàng)集的支持度之間的比率。對(duì)于二元它計(jì)算規(guī)則置信度和規(guī)則后件中項(xiàng)集的支持度之間的比率。對(duì)于二元 變量，提升度等價(jià)變量，提升度等價(jià)于興趣于興趣因子的客觀因子的客

60、觀度量：度量： 對(duì)于相互獨(dú)立的兩個(gè)變量，對(duì)于相互獨(dú)立的兩個(gè)變量，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)評(píng)估 58 7.7.1 興趣度客觀度量 興趣因子的局限性興趣因子的局限性。兩個(gè)詞兩個(gè)詞 p,q和和r,s 出現(xiàn)的頻率出現(xiàn)的頻率如表所示如表所示。使用公。使用公 式式得出得出p,q和和r,s 的興趣因子分別為的興趣因子分別為1.02和和4.08。這些結(jié)果有點(diǎn)。這些結(jié)果有點(diǎn)問(wèn)題：雖然問(wèn)題：雖然 p和和q同時(shí)出現(xiàn)在同時(shí)出現(xiàn)在88%的文檔中，的文檔中，但它們但它們的興趣因子的興趣因