數(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) 估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）或頻繁）或頻繁項(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)目的集合，包含的集合，包含k個(gè)項(xiàng)的項(xiàng)集稱為個(gè)項(xiàng)的項(xiàng)集稱

2、為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)滿足最小支持度閾頻繁項(xiàng)集產(chǎn)生（支持度測(cè)試）。其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集，即頻繁項(xiàng)集。值的所有項(xiàng)集，即頻繁項(xiàng)集。規(guī)則產(chǎn)生（置信度測(cè)試）。

3、其目標(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)枚舉所有可能的項(xiàng)集。圖）常常被用來(lái)枚舉所有可能的項(xiàng)集。圖中中顯示顯

4、示的的是是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)集，不包括空集?？占?.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，Bread 出現(xiàn)在事務(wù)出現(xiàn)在事務(wù)1，4，5中，其支持度計(jì)數(shù)將增加中，其支持度計(jì)數(shù)

5、將增加3次次。這種比較開銷大。這種比較開銷大。7.2頻繁項(xiàng)集產(chǎn)生57.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。這樣，如果。這樣，如果c，d，e是頻繁的，則它的所有子集一定也是頻繁是頻繁的，則它的所有子集一定

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

7、規(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í)，即Apriori性質(zhì)。性質(zhì)。Apriori性質(zhì)的內(nèi)容是：頻繁項(xiàng)集的所有非空子集也必須是頻繁性質(zhì)的內(nèi)容是：頻繁項(xiàng)集的所有非空子集也必須是頻繁的。該性質(zhì)通過減少搜索空間來(lái)提高頻繁項(xiàng)集逐層產(chǎn)生的效率。的。該性質(zhì)通過減少搜索空間來(lái)提高頻繁項(xiàng)集逐層產(chǎn)生的效率。 Apriori算法利用算法利用Apriori性質(zhì)，通過逐層搜索的迭代方法，將性質(zhì)，通過逐層搜索的迭代方法，將k-項(xiàng)集用項(xiàng)集用于探索（于探索（k+1）-項(xiàng)集，來(lái)窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集。項(xiàng)集，來(lái)窮盡數(shù)據(jù)集中的所有頻繁

8、項(xiàng)集。7.2頻繁項(xiàng)集產(chǎn)生87.2.2Apriori算法的頻繁項(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ù)據(jù)庫(kù)掃描；它使用產(chǎn)生它使用產(chǎn)生-測(cè)試策略來(lái)發(fā)現(xiàn)頻繁項(xiàng)集。在每次迭代之后，新的候選測(cè)試策略來(lái)發(fā)現(xiàn)頻繁項(xiàng)集。在每次迭代之后，新的候選項(xiàng)集由前一次迭

9、代發(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)生97.2.2Apriori算法的頻繁項(xiàng)集產(chǎn)生 AprioriApriori算法的主要步驟由連接步和剪枝步組成。算法的主要步驟由連接步和剪枝步組成。連接步連接步。為找出為找出Lk，通過，通過Lk-1與自身連接產(chǎn)生候選與自身連接產(chǎn)生候選k-項(xiàng)集的項(xiàng)集的集合集合，記記作作Ck。設(shè)。設(shè)l

10、1和和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） . （l1k-2l2k-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)

11、生的結(jié)果項(xiàng)集是l11，l12，.l1k-1，l2k-1。7.2頻繁項(xiàng)集產(chǎn)生107.2.2Apriori算法的頻繁項(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ù)，從而確定Lk（即根據(jù)定義，計(jì)數(shù)值不小于最（即根據(jù)定義，計(jì)數(shù)值不小于最小支持度計(jì)數(shù)的所有候選都是頻繁的，從而屬于小支持度計(jì)數(shù)的所有候選都是頻繁的，從而屬于Lk）。然而，）。然而，Ck可可能很大，因此所涉

12、及的計(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è)試可使用可使用所有頻繁項(xiàng)集的散列樹快速完成。所有頻繁項(xiàng)集的散列樹快速完成。7.2頻繁項(xiàng)集產(chǎn)生117.2.2Apriori算法的頻繁項(xiàng)集產(chǎn)生 下面下面舉舉一個(gè)具體例子。該例基于表中的一個(gè)具體例子。該例基于表中的AllE

13、lectronics的事務(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)生127.2.2Apriori算法的頻繁項(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)生137.2.2Apriori算法的頻繁項(xiàng)集產(chǎn)生 挖掘布爾關(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ù)

14、庫(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）；）； /得到得到t的子集，它們是候選的子集，它們是候選 for each 候選候選cCt c.count+； Lk=cCk | c.countmin_sup；return L=k Lk；7.2頻繁項(xiàng)集產(chǎn)生147.2.2Apriori算法

15、的頻繁項(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)生候選 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知識(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)生157.2.3支持度計(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)行比較，

17、并且更新包含在事務(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)集，并利用并利用其其更新更新對(duì)應(yīng)的候選項(xiàng)集的支持度。對(duì)應(yīng)的候選項(xiàng)集的支持度。7.2頻繁項(xiàng)集產(chǎn)生167.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)都

18、以遞增的字典次序排列，則項(xiàng)集可以這樣枚舉：先指定最小項(xiàng)，其后跟隨較大的項(xiàng)。其后跟隨較大的項(xiàng)。7.2頻繁項(xiàng)集產(chǎn)生177.2.3支持度計(jì)數(shù) 如如，給定，給定t=1，2，3，5，6，所有，所有3-項(xiàng)集一定以項(xiàng)項(xiàng)集一定以項(xiàng)1、2或或3開始。不開始。不必構(gòu)造以必構(gòu)造以5或或6開始的開始的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開始，后隨兩個(gè)開始，后隨兩個(gè)取自集合取自集合2，3，5，6的項(xiàng)的項(xiàng)。確定第一項(xiàng)后。確定第一項(xiàng)后，第二層的前綴結(jié)構(gòu)表示選擇，第

19、二層的前綴結(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)集。如。如，以，以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)生187.2.3支持度計(jì)數(shù) 在在Apriori算法中，候選項(xiàng)集劃分為不同的桶，并存放在算法中，候選項(xiàng)集劃分為不同的桶，并存放在Hash樹中。樹中。在支持度計(jì)數(shù)期間，包含

20、在事務(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)行匹配一桶內(nèi)候選項(xiàng)集進(jìn)行匹配。7.2頻繁項(xiàng)集產(chǎn)生197.2.3支持度計(jì)數(shù) 上圖是一棵上圖是一棵Hash樹結(jié)構(gòu)的例子。樹的每個(gè)內(nèi)部結(jié)點(diǎn)都使用樹結(jié)構(gòu)的例子。樹的每個(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)槌?/p>

21、應(yīng)當(dāng)散列到相同的分支（即最左分支），因?yàn)槌?之后它們都具有相之后它們都具有相同的余數(shù)。所有的候選項(xiàng)集都存放在同的余數(shù)。所有的候選項(xiàng)集都存放在Hash樹的葉結(jié)點(diǎn)中。圖中顯示的樹的葉結(jié)點(diǎn)中。圖中顯示的Hash樹包含樹包含15個(gè)候選個(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)生207.2.3支持度計(jì)數(shù) 考慮一個(gè)事務(wù)考慮一個(gè)事務(wù)t=1，2，3，5，6。為了更新候選項(xiàng)集的支持度計(jì)數(shù)，。為

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

23、持度度閾值閾值影響影響頻繁項(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ù)。如頻繁如頻繁項(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開銷將增加。開銷將增加。事務(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ù)的平均寬度可能很大

24、，這將影響將影響Apriori算法的復(fù)雜度。算法的復(fù)雜度。7.2頻繁項(xiàng)集產(chǎn)生227.2.4計(jì)算復(fù)雜度7.2頻繁項(xiàng)集產(chǎn)生23 因?yàn)橛深l繁項(xiàng)集的項(xiàng)組成的關(guān)聯(lián)規(guī)則的支持度大于等于最小支持度因?yàn)橛深l繁項(xiàng)集的項(xiàng)組成的關(guān)聯(lián)規(guī)則的支持度大于等于最小支持度閾值，所以規(guī)則產(chǎn)生過程就是在由頻繁項(xiàng)集的項(xiàng)組成的所有關(guān)聯(lián)規(guī)則閾值，所以規(guī)則產(chǎn)生過程就是在由頻繁項(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)生最多

25、項(xiàng)集能產(chǎn)生最多2k-2個(gè)關(guān)聯(lián)規(guī)則。個(gè)關(guān)聯(lián)規(guī)則。7.3規(guī)則產(chǎn)生247.3.1基本步驟 規(guī)則產(chǎn)生的基本步驟如下：規(guī)則產(chǎn)生的基本步驟如下：（1）對(duì)于每個(gè)頻繁項(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)生257.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

26、，I2，I1，I5，I2，I5，I1，I2和和I5。結(jié)果關(guān)聯(lián)規(guī)則如下，每個(gè)都列出置信度。結(jié)果關(guān)聯(lián)規(guī)則如下，每個(gè)都列出置信度。 如果最小置信度閾值為如果最小置信度閾值為70，則只有，則只有2、3和最后一個(gè)規(guī)則可以輸出，和最后一個(gè)規(guī)則可以輸出，因?yàn)橹挥羞@些是強(qiáng)的因?yàn)橹挥羞@些是強(qiáng)的。7.3規(guī)則產(chǎn)生267.3.1Apriori算法中規(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ī)

27、則來(lái)產(chǎn)生新的候選規(guī)則。使用這些規(guī)則來(lái)產(chǎn)生新的候選規(guī)則。7.3規(guī)則產(chǎn)生277.3.1Apriori算法中規(guī)則的產(chǎn)生 例如，例如， acdb和和abdc是兩個(gè)高置信度的規(guī)則，則通過合并是兩個(gè)高置信度的規(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ī)則，包

28、括的所有規(guī)則，包括cdab，bdac，bcad和和dabc等等。Apriori算法中規(guī)則產(chǎn)生過程與頻繁項(xiàng)集產(chǎn)生過程類似，二算法中規(guī)則產(chǎn)生過程與頻繁項(xiàng)集產(chǎn)生過程類似，二者唯一的不同是，在規(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)集的、較小的

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

30、而位于邊界下方的項(xiàng)集（陰影結(jié)點(diǎn)）都是非頻繁的。在邊界邊界下方的項(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)集的緊

31、湊表示集的緊湊表示。最大。最大頻繁項(xiàng)集形成了頻繁項(xiàng)集形成了可導(dǎo)出可導(dǎo)出所有頻繁項(xiàng)集的最小的項(xiàng)集的所有頻繁項(xiàng)集的最小的項(xiàng)集的集合。集合。7.4頻繁項(xiàng)集的緊湊表示317.4.2閉頻繁項(xiàng)集 閉項(xiàng)集閉項(xiàng)集：直接：直接超集都不具有和它相同的支持度計(jì)數(shù)超集都不具有和它相同的支持度計(jì)數(shù)。閉閉頻繁項(xiàng)集頻繁項(xiàng)集：支：支持持度大于或等于最小支持度度大于或等于最小支持度閾值閾值的閉項(xiàng)集的閉項(xiàng)集。7.4頻繁項(xiàng)集的緊湊表示327.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)

32、（項(xiàng)集）都標(biāo)出了與它相關(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ù)與它的任何超

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

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

35、，合并兩個(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)集的邊界靠近格的底部，如上圖（邊界靠近格的

36、底部，如上圖（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)集的其它方法367.5.1項(xiàng)集格遍歷等價(jià)類等價(jià)類 該方法是先將格劃分為兩個(gè)不相交的結(jié)點(diǎn)組（或等價(jià)類）。頻繁項(xiàng)該方法是先將格劃分為兩個(gè)不相交的結(jié)點(diǎn)

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

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

39、繁項(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)集的其它方法397.5.1項(xiàng)集格遍歷 比如說，算法可以從圖中的結(jié)點(diǎn)比如說，算法可以從圖中的結(jié)點(diǎn)a開始，計(jì)算其支持度計(jì)數(shù)并判斷它是開始，計(jì)算其支持度計(jì)數(shù)并判斷它是否頻繁。如果是，算法漸增地?cái)U(kuò)展下層結(jié)點(diǎn)，即否頻繁。如果是，算法漸增地?cái)U(kuò)展下層結(jié)點(diǎn)，即ab，abc，等等，直到到達(dá)，等等，直到到達(dá)一個(gè)非頻繁結(jié)點(diǎn)，如一個(gè)非頻繁結(jié)點(diǎn)，如abcd。然后，回溯到下一個(gè)分支，比如說。然后

40、，回溯到下一個(gè)分支，比如說abce，并且繼，并且繼續(xù)搜索。續(xù)搜索。7.5產(chǎn)生頻繁項(xiàng)集的其它方法407.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)集，則算法就不必訪問以是最大頻繁項(xiàng)集，則算法就不必訪問以bd，be，c，d和和e為根的子樹，因?yàn)樗鼈儾豢赡馨魏巫畲箢l繁項(xiàng)集。然而，為根的子樹，因?yàn)樗鼈儾豢赡馨魏巫畲?/p>

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

42、法。左邊的表示法稱作購(gòu)物籃事務(wù)的兩種不同方法。左邊的表示法稱作水平數(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列表），這種表示法稱作列表），這種表示法稱作垂直垂直數(shù)據(jù)布局?jǐn)?shù)據(jù)布局。候選項(xiàng)集的支持度通過取其子項(xiàng)集。候選項(xiàng)集的支持度通過取其子項(xiàng)集TID列表的交得到。列表的交得到。7.5產(chǎn)生頻繁項(xiàng)集的其它方法427.6FP-growth算法 FP-growth（Frequent-Pattern growth

43、，頻繁模式增長(zhǎng)）算法的，頻繁模式增長(zhǎng)）算法的基本思基本思想想是是采用分采用分治策略：首先，將代表頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵治策略：首先，將代表頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵FP樹（樹（Frequent-Pattern tree，頻繁模式樹），該樹仍保留項(xiàng)集的關(guān)聯(lián)信息。，頻繁模式樹），該樹仍保留項(xiàng)集的關(guān)聯(lián)信息。其其次次，將這種壓縮后的數(shù)據(jù)庫(kù)劃分成一組條件數(shù)據(jù)庫(kù)（一種特殊類型的投影，將這種壓縮后的數(shù)據(jù)庫(kù)劃分成一組條件數(shù)據(jù)庫(kù)（一種特殊類型的投影數(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è)“

44、模式片段模式片段”，只需要考察與它相關(guān)聯(lián)數(shù)據(jù)集，只需要考察與它相關(guān)聯(lián)數(shù)據(jù)集。隨著。隨著被考察的模式的被考察的模式的“增長(zhǎng)增長(zhǎng)”，可以，可以顯著地壓縮被搜索的數(shù)據(jù)集的大小。顯著地壓縮被搜索的數(shù)據(jù)集的大小。437.6.1FP樹構(gòu)造 利用利用FP-growthFP-growth算法構(gòu)造頻繁模式樹的過程如下：算法構(gòu)造頻繁模式樹的過程如下： （1）按）按Apriori算法，第一次掃描事務(wù)數(shù)據(jù)庫(kù)算法，第一次掃描事務(wù)數(shù)據(jù)庫(kù)D，導(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ù)的降序

45、排序。結(jié)果集或表記作按支持度計(jì)數(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é)點(diǎn)，并標(biāo)記為）創(chuàng)建樹的根結(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ì)每個(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，I

46、5，導(dǎo)致構(gòu)造樹的第一個(gè)分枝，導(dǎo)致構(gòu)造樹的第一個(gè)分枝。該分枝具有。該分枝具有3個(gè)結(jié)點(diǎn)，其中個(gè)結(jié)點(diǎn)，其中I2作為根的子女鏈接到根，作為根的子女鏈接到根，I1鏈接到鏈接到I2，I5鏈鏈接到接到I1，如圖所示。，如圖所示。7.6FP-growth算法457.6.1FP樹構(gòu)造 第二個(gè)事務(wù)第二個(gè)事務(wù)T200按按L的次序包含的次序包含I2和和I4，它導(dǎo)致一個(gè)分枝，其中，它導(dǎo)致一個(gè)分枝，其中I2鏈鏈接到根，接到根，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:

47、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算法467.6.1FP樹構(gòu)造 為了方便樹的遍歷，創(chuàng)建一個(gè)項(xiàng)頭表，使每項(xiàng)通過一個(gè)結(jié)點(diǎn)鏈指向它為了方便樹的遍歷，創(chuàng)建一個(gè)項(xiàng)頭表，使每項(xiàng)通過一個(gè)結(jié)點(diǎn)鏈指向它在樹中的位置。掃描所有的事務(wù)后得到的樹在樹中的位置。掃描所有的事務(wù)后得到的樹如圖所示如圖所示，帶有相關(guān)的結(jié)點(diǎn)鏈。，帶有相關(guān)的結(jié)點(diǎn)鏈。這樣，數(shù)

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

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

50、造的條件模式基。使用這些條件模式基作為事務(wù)數(shù)據(jù)庫(kù)，構(gòu)造I5的條件的條件FP樹，它只包含單個(gè)路徑樹，它只包含單個(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:2。對(duì)于。對(duì)于I4，它的兩個(gè)前綴形成條件模式基，它的兩個(gè)前綴形成條件模式基(I2 I1:1）,（I2:1)，產(chǎn)，產(chǎn)生一個(gè)單結(jié)點(diǎn)的條件生一個(gè)單結(jié)點(diǎn)的條件FP樹樹，并導(dǎo)出一個(gè)頻繁模式，并導(dǎo)出一個(gè)頻繁模式I2 I4:2。7.6FP-growth算法497.6.2頻繁項(xiàng)集產(chǎn)生

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

52、次數(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)換成遞歸地挖掘短模式的問選用了分治策略，把挖掘的長(zhǎng)頻繁模式轉(zhuǎn)換成遞歸地挖掘短模式的問題，再與后綴相連；題，再與后綴相連；挖掘長(zhǎng)頻繁模式與短的頻繁模式時(shí)，有效性與可伸縮性都是該算法的挖掘長(zhǎng)頻繁模式與短的頻繁模式時(shí)，有效性與可伸縮性都是該算法的特點(diǎn)，特點(diǎn)，所用所用挖掘時(shí)間會(huì)比挖掘時(shí)間會(huì)比Apriori算法的挖掘時(shí)間少得多。算法的挖掘時(shí)間少得多。

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

54、業(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ì)量的標(biāo)準(zhǔn)是非常重要的。第一組標(biāo)準(zhǔn)第一組標(biāo)準(zhǔn)可通過可通過統(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)可通過可通過主觀論據(jù)建立，即模式被主觀地認(rèn)為是無(wú)趣的，除

55、主觀論據(jù)建立，即模式被主觀地認(rèn)為是無(wú)趣的，除非它能夠揭示料想不到的信息或提供導(dǎo)致有益的行動(dòng)的有用信息非它能夠揭示料想不到的信息或提供導(dǎo)致有益的行動(dòng)的有用信息。 547.7.1興趣度客觀度量 客觀度量常?；诹新?lián)表中列出的頻度計(jì)數(shù)來(lái)計(jì)算。一對(duì)二元變量客觀度量常常基于列聯(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ù)，f

56、01表示包含表示包含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)估557.7.1興趣度客觀度量 支持度置信度框架的局限性支持度置信度框架的局限性?，F(xiàn)有關(guān)聯(lián)規(guī)則的挖掘算法依賴于支持?，F(xiàn)有關(guān)聯(lián)規(guī)則的挖掘算法依賴于支持度和置信度來(lái)除去沒有意義的模式。支持度的缺點(diǎn)在于許多潛在的有意義度和置信度來(lái)除去沒有意義的模式。支持度的缺點(diǎn)在于許多潛在的有意義的模式由于包含支持度小的項(xiàng)而被刪去。置信度的缺點(diǎn)的模式由于包含支持度小的項(xiàng)而被刪去。置信度的缺點(diǎn)更微妙更微妙，最適合用，最適合用下面的例

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

58、的度量）的度量： 它計(jì)算規(guī)則置信度和規(guī)則后件中項(xiàng)集的支持度之間的比率。對(duì)于二元它計(jì)算規(guī)則置信度和規(guī)則后件中項(xiàng)集的支持度之間的比率。對(duì)于二元變量，提升度等價(jià)變量，提升度等價(jià)于興趣于興趣因子的客觀因子的客觀度量：度量： 對(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)估587.7.1興趣度客觀度量 興趣因子的局限性興趣因子的局限性。兩個(gè)詞兩個(gè)詞 p,q和和r,s 出現(xiàn)的頻率出現(xiàn)的頻率如表所示如表所示。使用公。使用公式式得出得出p,q和和r,s

59、 的興趣因子分別為的興趣因子分別為1.02和和4.08。這些結(jié)果有點(diǎn)。這些結(jié)果有點(diǎn)問題：雖然問題：雖然p和和q同時(shí)出現(xiàn)在同時(shí)出現(xiàn)在88%的文檔中，的文檔中，但它們但它們的興趣因子的興趣因子接近接近1，表明二者是相互，表明二者是相互獨(dú)立的；另一方面，獨(dú)立的；另一方面， r,s 的興趣因子比的興趣因子比p,q 高高，盡管，盡管r和和s很少同時(shí)出現(xiàn)在很少同時(shí)出現(xiàn)在同一個(gè)文檔中。這種情況下，置信度可能同一個(gè)文檔中。這種情況下，置信度可能是更好是更好的選擇，因?yàn)橹眯哦缺砻鞯倪x擇，因?yàn)橹眯哦缺砻鱬和和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)評(píng)估597.7.1興趣度客觀度量7.7關(guān)聯(lián)評(píng)估607.7.1興趣度客觀度量7.7關(guān)聯(lián)評(píng)估617.7.1興趣度客觀度量 IS IS度量度量。IS是另一種度量，用于處理非對(duì)稱二元變量是另一種度量，用于處理非對(duì)稱二元變量。定義。定義如下如下： 如如，前面表中顯示的詞對(duì)，前面表中顯示的詞對(duì)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é)上等價(jià)于二元變量的余弦變量數(shù)學(xué)上等價(jià)于二元變量的余弦變量： IS度量也可以表示為從一對(duì)二元