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

2、為k-項集；項集；支持度（支持度（support）：數據庫：數據庫中含有這個項集的所有項目在中含有這個項集的所有項目在事事務務集中集中所占的比例。所占的比例。置信度（置信度（confidence）：出現：出現項集項集A的事務集的事務集D中，項集中，項集B出現出現的概率。的概率。頻繁項集頻繁項集：支持：支持度大于或等于度大于或等于min_sup的的項集。項集。2 關聯規則挖掘的兩個步驟：關聯規則挖掘的兩個步驟：頻繁項集產生（支持度測試）。其目標是發現滿足最小支持度閾頻繁項集產生（支持度測試）。其目標是發現滿足最小支持度閾值的所有項集，即頻繁項集。值的所有項集，即頻繁項集。規則產生（置信度測試）。

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

4、示的的是是I=a，b，c，d，e的項集格的項集格。包含。包含k個項的數據個項的數據集最多產生集最多產生2k-1 個頻繁個頻繁項集，不包括項集，不包括空集。空集。7.2頻繁項集產生4 發現頻繁項集的一種原始方法是確定格結構中每個候選項集的支持度發現頻繁項集的一種原始方法是確定格結構中每個候選項集的支持度計數計數。這必須這必須比較每個比較每個候選項集與每個候選項集與每個事務。如候選事務。如候選項集包含在事務中，項集包含在事務中，則候選項集的支持度計數增加則候選項集的支持度計數增加。如。如，由于項集，由于項集 Milk，Bread 出現在事務出現在事務1，4，5中，其支持度計數將增加中，其支持度計數

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

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

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

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

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

10、l1和和l2是是Lk-1中的項集中的項集。lij表示表示li的第的第j項。假定項。假定事務或項集中事務或項集中的項按字典次序的項按字典次序排序，排序，使得使得li1li2.lik-1。執行連接。執行連接Lk-1 Lk-1；其中其中Lk-1的元素是可連接的，的元素是可連接的，如它們如它們前（前（k-2）個項相同）個項相同，即即Lk-1的元的元素素l1和和l2是可連接的，是可連接的，如（如（l11=l21） （l12=l22） . （l1k-2l2k-2） （l1k-1l2k-1）。條件）。條件l1k-1l2k-1是簡單地確保不產生是簡單地確保不產生重復。連接重復。連接l1和和l2產生的結果項集是

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

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

13、Electronics的事務數據庫的事務數據庫D。該數據庫有該數據庫有9個事務個事務，假定事務中的項按字典次序存放。假定事務中的項按字典次序存放。7.2頻繁項集產生127.2.2Apriori算法的頻繁項集產生 使用圖使用圖來來解釋解釋Apriori算法發現算法發現D中的頻繁項集。中的頻繁項集。7.2頻繁項集產生137.2.2Apriori算法的頻繁項集產生 挖掘布爾關聯規則發現頻繁項集的挖掘布爾關聯規則發現頻繁項集的AprioriApriori算法如下。算法如下。 算法算法：Apriori。使用逐層迭代方法基于候選產生找出頻繁項集。使用逐層迭代方法基于候選產生找出頻繁項集。 輸入輸入：事務數

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

15、法的頻繁項集產生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； /連接步：產生候選連接步：產生候選 if has_infrequent_subset（c，Lk-1） then delete c； /剪枝步：刪除非頻繁的候選剪枝步：刪除非頻繁的候選 else add c to Ck；return Ck；procedure has_infrequent_su

16、bset(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頻繁項集產生157.2.3支持度計數 支持度計數用以支持度計數用以確定在確定在apriori-gen函數的候選項剪枝步驟保留下來的函數的候選項剪枝步驟保留下來的每個候選項集出現的頻繁程度。每個候選項集出現的頻繁程度。 計算支持度的主要方法有計算支持度的主要方法有兩種兩種：一是一是將每個事務與所有候選項集進行比較

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

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

19、第二層的前綴結構表示選擇第二項的方法第二項的方法。如。如：1 2 3 5 6表示以表示以1，2為前綴，后隨項為前綴，后隨項3、5或或6的項集。的項集。最后，第三層的前綴結構顯示了事務最后，第三層的前綴結構顯示了事務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頻繁項集產生187.2.3支持度計數 在在Apriori算法中，候選項集劃分為不同的桶，并存放在算法中，候選項集劃分為不同的桶，并存放在Hash樹中。樹中。在支持度計數期間，包

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

21、以應當散列到相同的分支（即最左分支），因為除以3之后它們都具有相之后它們都具有相同的余數。所有的候選項集都存放在同的余數。所有的候選項集都存放在Hash樹的葉結點中。圖中顯示的樹的葉結點中。圖中顯示的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個葉結點中。個葉結點中。7.2頻繁項集產生207.2.3支持度計數 考慮一個事務考慮一個事務t=1，2，3，5，6。為了更新候選項集的支持度計數，。

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

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

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

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

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

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

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

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

30、，而位于邊界下方的項集（陰影結點）都是非頻繁的。在邊界邊界下方的項集（陰影結點）都是非頻繁的。在邊界附近結點附近結點中，中，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、緊湊表示集的緊湊表示。最大。最大頻繁項集形成了頻繁項集形成了可導出可導出所有頻繁項集的最小的項集的所有頻繁項集的最小的項集的集合。集合。7.4頻繁項集的緊湊表示317.4.2閉頻繁項集 閉項集閉項集：直接：直接超集都不具有和它相同的支持度計數超集都不具有和它相同的支持度計數。閉閉頻繁項集頻繁項集：支：支持持度大于或等于最小支持度度大于或等于最小支持度閾值閾值的閉項集的閉項集。7.4頻繁項集的緊湊表示327.4.2閉頻繁項集 閉頻繁項集示例如閉頻繁項集示例如上上圖。為了更好地解釋每個項集的支持度計數，格圖。為了更好地解釋每個項集的支持度計數，格中每個結點（項集）都標出了與它相關聯的事務的中每個結

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

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

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

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

36、的底部，如上圖（b）所示。可以使用先驗原理剪掉最大頻繁項）所示。可以使用先驗原理剪掉最大頻繁項集的所有子集。另一種策略是結合集的所有子集。另一種策略是結合“一般到特殊一般到特殊”和和“特殊到一般特殊到一般”的搜的搜索策略，盡管這種雙向搜索方法需要更多的空間存儲候選項集，但是上圖索策略，盡管這種雙向搜索方法需要更多的空間存儲候選項集，但是上圖（c）所示的布局，該方法有助于加快確定頻繁項集邊界。）所示的布局，該方法有助于加快確定頻繁項集邊界。7.5產生頻繁項集的其它方法367.5.1項集格遍歷等價類等價類 該方法是先將格劃分為兩個不相交的結點組（或等價類）。頻繁項該方法是先將格劃分為兩個不相交的結

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

38、中，算法首先的相同前綴或后綴。在基于前綴的方法中，算法首先搜索以前綴搜索以前綴a開始的頻繁項集，然后是以前綴開始的頻繁項集，然后是以前綴b等開始的頻繁項集，然后等開始的頻繁項集，然后中中c，如此下去。基于前綴和基于后綴的等價類都可以使用，如此下去。基于前綴和基于后綴的等價類都可以使用上上圖中所示的圖中所示的類似于樹的結構來演示。類似于樹的結構來演示。7.5產生頻繁項集的其它方法387.5.1項集格遍歷寬度優先與深度優先寬度優先與深度優先 Apriori算法采用寬度優先的方法遍歷格，如圖（算法采用寬度優先的方法遍歷格，如圖（a）所示。它首先發）所示。它首先發現所有頻繁現所有頻繁1-項集，接下來是

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

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

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

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

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

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

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

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

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

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

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

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

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

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

53、 7.6FP-growth算法527.6.2頻繁項集產生 缺點：缺點：建立建立FP樹時，會占用大量的內存空間。如果數據庫的規模很大，要樹時，會占用大量的內存空間。如果數據庫的規模很大，要建立的建立的FP樹也會很巨大；樹也會很巨大；在遞歸構建在遞歸構建FP樹時，每生成一個頻繁模式就會出現一個條件樹。當樹時，每生成一個頻繁模式就會出現一個條件樹。當生成與釋放海量的條件樹時，生成與釋放海量的條件樹時，該算法該算法將占用很多的運算時間與計算將占用很多的運算時間與計算機空間。機空間。7.6FP-growth算法537.7關聯評估 在實際情況中，商業數據庫的數據量和維數都非常大，運用關聯分析在實際情況中，

54、商業數據庫的數據量和維數都非常大，運用關聯分析算法往往產生大量的規則，而其中很大一部分可能是不感興趣的。因此，算法往往產生大量的規則，而其中很大一部分可能是不感興趣的。因此，建立一組廣泛接受的評價關聯模式質量的標準是非常重要的。建立一組廣泛接受的評價關聯模式質量的標準是非常重要的。第一組標準第一組標準可通過可通過統計論據建立。涉及相互獨立的項或覆蓋少量事務統計論據建立。涉及相互獨立的項或覆蓋少量事務的模式被認為是不令人感興趣的，因為它們可能反映數據中的偽聯系。的模式被認為是不令人感興趣的，因為它們可能反映數據中的偽聯系。第二組標準第二組標準可通過可通過主觀論據建立，即模式被主觀地認為是無趣的，

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

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

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

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

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

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