數(shù)據(jù)挖掘-第6章-關(guān)聯(lián)分析基本概念和算法

1、關(guān)聯(lián)分析: 基本概念和算法第6章關(guān)聯(lián)分析: 基本概念和算法定義:關(guān)聯(lián)分析(association analysis)關(guān)聯(lián)分析用于發(fā)現(xiàn)隱藏在大型數(shù)據(jù)集中的令人感興趣的聯(lián)系，所發(fā)現(xiàn)的模式通常用關(guān)聯(lián)規(guī)則或頻繁項(xiàng)集的形式表示。關(guān)聯(lián)分析可以應(yīng)用于生物信息學(xué)、醫(yī)療診斷、網(wǎng)頁(yè)挖掘、科學(xué)數(shù)據(jù)分析等Rules Discovered: Diaper - Beer6.1 問(wèn)題定義項(xiàng)集（Itemset）包含0個(gè)或多個(gè)項(xiàng)的集合例子: Milk, Bread, Diaperk-項(xiàng)集如果一個(gè)項(xiàng)集包含k個(gè)項(xiàng)支持度計(jì)數(shù)（Support count ）()包含特定項(xiàng)集的事務(wù)個(gè)數(shù)例如： (Milk, Bread,Diaper) =

2、 2 支持度（Support）包含項(xiàng)集的事務(wù)數(shù)與總事務(wù)數(shù)的比值例如： s(Milk, Bread, Diaper) = 2/5頻繁項(xiàng)集（Frequent Itemset）滿(mǎn)足最小支持度閾值（ minsup ）的所有項(xiàng)集定義: 關(guān)聯(lián)規(guī)則（Association Rule）關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則是形如 X Y的蘊(yùn)含表達(dá)式, 其中 X 和 Y 是不相交的項(xiàng)集例子:Milk, Diaper Beer 定義: 關(guān)聯(lián)規(guī)則（Association Rule）Example:關(guān)聯(lián)規(guī)則的強(qiáng)度支持度 Support (s)確定項(xiàng)集的頻繁程度置信度 Confidence (c)確定Y在包含X的事 務(wù)中出現(xiàn)的頻繁程度關(guān)聯(lián)規(guī)

3、則挖掘問(wèn)題關(guān)聯(lián)規(guī)則挖掘問(wèn)題：給定事務(wù)的集合 T, 關(guān)聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于 minsup并且置信度大于等于minconf的所有規(guī)則, minsup和minconf是對(duì)應(yīng)的支持度和置信度閾值挖掘關(guān)聯(lián)規(guī)則的一種原始方法是：Brute-force approach:計(jì)算每個(gè)可能規(guī)則的支持度和置信度這種方法計(jì)算代價(jià)過(guò)高，因?yàn)榭梢詮臄?shù)據(jù)集提取的規(guī)則的數(shù)量達(dá)指數(shù)級(jí)從包含d個(gè)項(xiàng)的數(shù)據(jù)集提取的可能規(guī)則的總數(shù)R=3d-2d+1+1，如果d等于6，則R=602挖掘關(guān)聯(lián)規(guī)則（Mining Association Rules）大多數(shù)關(guān)聯(lián)規(guī)則挖掘算法通常采用的一種策略是，將關(guān)聯(lián)規(guī)則挖掘任務(wù)分解為如下兩個(gè)主要的

4、子任務(wù): 頻繁項(xiàng)集產(chǎn)生（Frequent Itemset Generation）其目標(biāo)是發(fā)現(xiàn)滿(mǎn)足最小支持度閾值的所有項(xiàng)集，這些項(xiàng)集稱(chēng)作頻繁項(xiàng)集。規(guī)則的產(chǎn)生（Rule Generation）其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取所有高置信度的規(guī)則，這些規(guī)則稱(chēng)作強(qiáng)規(guī)則（strong rule）。6.2 頻繁項(xiàng)集產(chǎn)生(Frequent Itemset Generation)格結(jié)構(gòu)（lattice structure）頻繁項(xiàng)集產(chǎn)生（Frequent Itemset Generation）Brute-force 方法: 把格結(jié)構(gòu)中每個(gè)項(xiàng)集作為候選項(xiàng)集將每個(gè)候選項(xiàng)集和每個(gè)事務(wù)進(jìn)行比較，確定每個(gè)候選項(xiàng)集的支持

5、度計(jì)數(shù)。時(shí)間復(fù)雜度 O(NMw)，這種方法的開(kāi)銷(xiāo)可能非常大。降低產(chǎn)生頻繁項(xiàng)集計(jì)算復(fù)雜度的方法減少候選項(xiàng)集的數(shù)量 (M)先驗(yàn)(apriori)原理減少比較的次數(shù) (NM)替代將每個(gè)候選項(xiàng)集與每個(gè)事務(wù)相匹配，可以使用更高級(jí)的數(shù)據(jù)結(jié)構(gòu)，或存儲(chǔ)候選項(xiàng)集或壓縮數(shù)據(jù)集，來(lái)減少比較次數(shù)先驗(yàn)原理（ Apriori principle）先驗(yàn)原理:如果一個(gè)項(xiàng)集是頻繁的，則它的所有子集一定也是頻繁的相反，如果一個(gè)項(xiàng)集是非頻繁的，則它的所有超集也一定是非頻繁的:這種基于支持度度量修剪指數(shù)搜索空間的策略稱(chēng)為基于支持度的剪枝（support-based pruning）這種剪枝策略依賴(lài)于支持度度量的一個(gè)關(guān)鍵性質(zhì)，即一個(gè)項(xiàng)

6、集的支持度決不會(huì)超過(guò)它的子集的支持度。這個(gè)性質(zhì)也稱(chēng)為支持度度量的反單調(diào)性（anti-monotone）。非頻繁項(xiàng)集例子被剪枝的超集Apriori算法的頻繁項(xiàng)集產(chǎn)生Apriori算法的頻繁項(xiàng)集產(chǎn)生Items (1-itemsets)Pairs (2-itemsets)Triplets (3-itemsets)支持度閾值=60%最小支持度計(jì)數(shù) = 3枚舉所有項(xiàng)集將產(chǎn)生 個(gè)候選而使用先驗(yàn)原理，將減少為6 + 6 + 1 = 13Apriori 算法Apriori 算法Apriori算法的頻繁項(xiàng)集產(chǎn)生的部分有兩個(gè)重要的特點(diǎn)：它是一個(gè)逐層算法。即從頻繁1-項(xiàng)集到最長(zhǎng)的頻繁項(xiàng)集，它每次遍歷項(xiàng)集格中的一層它

7、使用產(chǎn)生-測(cè)試策略來(lái)發(fā)現(xiàn)頻繁項(xiàng)集。在每次迭代，新的候選項(xiàng)集由前一次迭代發(fā)現(xiàn)的頻繁項(xiàng)集產(chǎn)生，然后對(duì)每個(gè)候選的支持度進(jìn)行計(jì)數(shù)，并與最小支持度閾值進(jìn)行比較。該算法需要的總迭代次數(shù)是kmax+1，其中kmax是頻繁項(xiàng)集的最大長(zhǎng)度候選的產(chǎn)生與剪枝(構(gòu)造apriori-gen函數(shù))候選項(xiàng)集的產(chǎn)生候選項(xiàng)集的剪枝蠻力方法蠻力方法把所有的k-項(xiàng)集都看作可能的候選，然后使用候選剪枝除去不必要的候選第k層產(chǎn)生的候選項(xiàng)集的數(shù)目為雖然候選產(chǎn)生是相當(dāng)簡(jiǎn)單的，但是候選剪枝的開(kāi)銷(xiāo)極大，因?yàn)楸仨毧疾斓捻?xiàng)集數(shù)量太大。設(shè)每一個(gè)候選項(xiàng)集所需的計(jì)算量為O（k），這種方法 的總復(fù)雜度為候選的產(chǎn)生與剪枝Items (1-itemsets)

8、Pairs (2-itemsets)Triplets (3-itemsets)支持度閾值=60%最小支持度計(jì)數(shù) = 3枚舉所有項(xiàng)集將產(chǎn)生 個(gè)候選而使用先驗(yàn)原理，將減少為6 + 6 + 1 = 13候選的產(chǎn)生與剪枝 這種方法用其他頻繁項(xiàng)來(lái)擴(kuò)展每個(gè)頻繁（k-1）-項(xiàng)集這種方法將產(chǎn)生 個(gè)候選k-項(xiàng)集，其中|Fj|表示頻繁j-項(xiàng)集的個(gè)數(shù)。這種方法總復(fù)雜度是這種方法是完全的，因?yàn)槊恳粋€(gè)頻繁k-項(xiàng)集都是由一個(gè)頻繁（k-1）-項(xiàng)集和一個(gè)頻繁1-項(xiàng)集組成的。因此，所有的頻繁k-項(xiàng)集是這種方法所產(chǎn)生的候選k-項(xiàng)集的一部分。候選的產(chǎn)生與剪枝候選的產(chǎn)生與剪枝 然而，這種方法很難避免重復(fù)地產(chǎn)生候選項(xiàng)集。 如：面包，尿

9、布，牛奶不僅可以由合并項(xiàng)集面包，尿布和牛奶得到，而且還可以由合并面包，牛奶和尿布得到，或由合并尿布，牛奶和面包得到。候選的產(chǎn)生與剪枝避免產(chǎn)生重復(fù)的候選項(xiàng)集的一種方法是確保每個(gè)頻繁項(xiàng)集中的項(xiàng)以字典序存儲(chǔ)，每個(gè)頻繁（k-1）-項(xiàng)集X只用字典序比X中所有的項(xiàng)都大的頻繁項(xiàng)進(jìn)行擴(kuò)展 如：項(xiàng)集面包，尿布可以用項(xiàng)集牛奶擴(kuò)展，因?yàn)椤芭Ｄ獭保╩ilk）在字典序下比“面包”（Bread）和“尿布”（Diapers）都大。盡管這種方法比蠻力方法有明顯改進(jìn)，但是仍然產(chǎn)生大量不必要的候選。 例如，通過(guò)合并啤酒，尿布和牛奶而得到的候選是不必要的。因?yàn)樗淖蛹【?，牛奶是非頻繁的。候選的產(chǎn)生與剪枝 這種方法合并一對(duì)頻繁（k

10、-1）-項(xiàng)集，僅當(dāng)它們的前k-2個(gè)項(xiàng)都相同。 如頻繁項(xiàng)集面包，尿布和面包，牛奶合并，形成了候選3-項(xiàng)集面包，尿布，牛奶。算法不會(huì)合并項(xiàng)集啤酒，尿布和尿布，牛奶，因?yàn)樗鼈兊牡谝粋€(gè)項(xiàng)不相同。然而，由于每個(gè)候選都由一對(duì)頻繁（k-1）-項(xiàng)集合并而成，因此，需要附加的候選剪枝步驟來(lái)確保該候選的其余k-2個(gè)子集是頻繁的。候選的產(chǎn)生與剪枝支持度計(jì)數(shù)支持度計(jì)數(shù)過(guò)程確定在apriori-gen函數(shù)的候選項(xiàng)剪枝步驟保留下來(lái)的每個(gè)候選項(xiàng)集出現(xiàn)的頻繁程度。計(jì)算支持度的主要方法:一種方法是將每個(gè)事務(wù)與所有的候選項(xiàng)集進(jìn)行比較，并且更新包含在事務(wù)中的候選項(xiàng)集的支持度計(jì)數(shù)。這種方法是計(jì)算昂貴的，尤其當(dāng)事務(wù)和候選項(xiàng)集的數(shù)目都很

11、大時(shí)。另一種方法是枚舉每個(gè)事務(wù)所包含的項(xiàng)集，并且利用它們更新對(duì)應(yīng)的候選項(xiàng)集的支持度。枚舉事務(wù)t的所有包含3個(gè)項(xiàng)的子集產(chǎn)生Hash樹(shù)2 3 45 6 71 4 51 3 61 2 44 5 71 2 54 5 81 5 93 4 53 5 63 5 76 8 93 6 73 6 81,4,72,5,83,6,9Hash functionHash函數(shù)h(p)=p mod 3假設(shè)有15個(gè)候選3-項(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

12、6 8Hash樹(shù)結(jié)構(gòu)1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash FunctionCandidate Hash TreeHash on 1, 4 or 7Hash樹(shù)結(jié)構(gòu)1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash FunctionCandidate Hash TreeHash on 2, 5 or 8Hash樹(shù)

13、結(jié)構(gòu)1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash FunctionCandidate Hash TreeHash on 3, 6 or 9使用Hash樹(shù)進(jìn)行支持度計(jì)數(shù)1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81 2 3 5 61 +2 3 5 63 5 62 +5 63 +1,4,72,5,83,6,9Hash Functiontransacti

14、on使用Hash樹(shù)進(jìn)行支持度計(jì)數(shù)1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash Function1 2 3 5 63 5 61 2 +5 61 3 +61 5 +3 5 62 +5 63 +1 +2 3 5 6transaction使用Hash樹(shù)進(jìn)行支持度計(jì)數(shù)1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash Func

15、tion1 2 3 5 63 5 61 2 +5 61 3 +61 5 +3 5 62 +5 63 +1 +2 3 5 6transaction15個(gè)項(xiàng)集中的9個(gè)與事務(wù)進(jìn)行比較存放在被訪(fǎng)問(wèn)的葉結(jié)點(diǎn)中的候選項(xiàng)集與事務(wù)進(jìn)行比較，如果候選項(xiàng)集是該事務(wù)的子集，則增加它的支持度計(jì)數(shù)。在該例子中 ，訪(fǎng)問(wèn)了9個(gè)葉子結(jié)點(diǎn)中的5個(gè)。15個(gè)項(xiàng)集中的9個(gè)與事務(wù)進(jìn)行比較計(jì)算復(fù)雜性支持度閾值 降低支持度閾值通常將導(dǎo)致更多的項(xiàng)集是頻繁的。計(jì)算復(fù)雜度增加隨著支持度閾值的降低，頻繁項(xiàng)集的最大長(zhǎng)度將增加，導(dǎo)致算法需要掃描數(shù)據(jù)集的次數(shù)也將增多項(xiàng)數(shù) 隨著項(xiàng)數(shù)的增加，需要更多的空間來(lái)存儲(chǔ)項(xiàng)的支持度計(jì)數(shù)。如果頻繁項(xiàng)集的數(shù)目也隨著數(shù)據(jù)項(xiàng)

16、數(shù)增加而增長(zhǎng)，則由于算法產(chǎn)生的候選項(xiàng)集更多，計(jì)算量和I/O開(kāi)銷(xiāo)將增加事務(wù)數(shù) 由于A(yíng)priori算法反復(fù)掃描數(shù)據(jù)集，因此它的運(yùn)行時(shí)間隨著事務(wù)數(shù)增加而增加事務(wù)的平均寬度頻繁項(xiàng)集的最大長(zhǎng)度隨事務(wù)平均寬度增加而增加隨著事務(wù)寬度的增加，事務(wù)中將包含更多的項(xiàng)集，這將增加支持度計(jì)數(shù)時(shí)Hash樹(shù)的遍歷次數(shù)6.3 規(guī)則產(chǎn)生忽略那些前件或后件為空的規(guī)則，每個(gè)頻繁k-項(xiàng)集能夠產(chǎn)生多達(dá)2k-2個(gè)關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則的提取：將一個(gè)項(xiàng)集 Y劃分成兩個(gè)非空的子集 X 和Y-X，使得X Y X滿(mǎn)足置信度閾值。如果 A,B,C,D 是頻繁項(xiàng)集, 候選項(xiàng)集為:ABC D, ABD C, ACD B, BCD A, A BCD,B A

17、CD,C ABD, D ABCAB CD,AC BD, AD BC, BC AD, BD AC, CD AB,這樣的規(guī)則必然已經(jīng)滿(mǎn)足支持度閾值，因?yàn)樗鼈兪怯深l繁項(xiàng)集產(chǎn)生的。規(guī)則產(chǎn)生怎樣有效的從頻繁項(xiàng)集中產(chǎn)生關(guān)聯(lián)規(guī)則?一般，計(jì)算關(guān)聯(lián)規(guī)則的置信度并不需要再次掃描事務(wù)數(shù)據(jù)集。規(guī)則A,B,C D的置信度為(ABCD)/ (ABC)。 因?yàn)檫@兩個(gè)項(xiàng)集的支持度計(jì)數(shù)已經(jīng)在頻繁項(xiàng)集產(chǎn)生時(shí)得到，因此不必再掃描整個(gè)數(shù)據(jù)集如果規(guī)則X Y-X不滿(mǎn)足置信度閾值，則形如XY-X的規(guī)則一定也不滿(mǎn)足置信度閾值，其中X是X的子集。 例如：c(ABC D) c(AB CD) c(A BCD) 因?yàn)?AB) (ABC)，則(ABC

18、D)/ (ABC) (ABCD)/ (AB) ，則c(ABC D) c(AB CD) Apriori 算法中規(guī)則的產(chǎn)生被剪枝的規(guī)則低置信度規(guī)則Apriori 算法中規(guī)則的產(chǎn)生6.4 頻繁項(xiàng)集的緊湊表示由事務(wù)數(shù)據(jù)集產(chǎn)生的頻繁項(xiàng)集的數(shù)量可能非常大。因此，從中識(shí)別出可以推導(dǎo)出其他所有的頻繁項(xiàng)集的，較小的，具有代表性的項(xiàng)集是有用的。頻繁項(xiàng)集的數(shù)量需要緊湊的表示最大頻繁項(xiàng)集（Maximal Frequent Itemset）頻繁項(xiàng)集的邊界不頻繁項(xiàng)集最大頻繁項(xiàng)集最大頻繁項(xiàng)集是這樣的頻繁項(xiàng)集，它的直接超集都不是頻繁的非頻繁的頻繁的最大頻繁項(xiàng)集的特點(diǎn)優(yōu)點(diǎn)：最大頻繁項(xiàng)集有效地提供了頻繁項(xiàng)集的緊湊表示。 換句話(huà)說(shuō)

19、，最大頻繁項(xiàng)集形成了可以導(dǎo)出所有頻繁項(xiàng)集的最小的項(xiàng)集的集合。從圖中，可以看出，所有的頻繁項(xiàng)集是最大頻繁項(xiàng)集 A,D, A,C,E, B,C,D,E的子集缺點(diǎn)：盡管最大頻繁項(xiàng)集提供了一種緊湊表示，但是它卻不包含它們子集的支持度信息。頻繁閉項(xiàng)集（Closed Frequent Itemset）閉項(xiàng)集（Closed Itemset）：項(xiàng)集X是閉的，如果它的直接超集都不具有和它相同的支持度計(jì)數(shù)。換句話(huà)說(shuō)，如果至少存在一個(gè)X的直接超集，其支持度計(jì)數(shù)與X相同，X就不是閉的。頻繁閉項(xiàng)集: 一個(gè)項(xiàng)集是頻繁閉項(xiàng)集，如果它是閉的，并且它的支持度大于或等于最小支持度閾值。頻繁閉項(xiàng)集Transaction IdsNo

20、t supported by any transactions頻繁閉項(xiàng)集minsup = 40%# Closed Frequent Itemset = 9# Maximal Frequent itemset = 4頻繁項(xiàng)集、最大頻繁項(xiàng)集和頻繁閉項(xiàng)集之間的關(guān)系使用頻繁閉項(xiàng)集進(jìn)行支持度計(jì)數(shù)6.5 產(chǎn)生頻繁項(xiàng)集的其他方法項(xiàng)集格遍歷一般到特殊 vs 特殊到一般。一般到特殊：適合于頻繁項(xiàng)集的最大長(zhǎng)度不是太長(zhǎng)的時(shí)候。特殊到一般：適合于處理頻繁項(xiàng)集的最大長(zhǎng)度較長(zhǎng)的時(shí)候產(chǎn)生頻繁項(xiàng)集的其他方法項(xiàng)集格遍歷等價(jià)類(lèi)：將格劃分為兩個(gè)不相交的節(jié)點(diǎn)組（或等價(jià)類(lèi)）。頻繁項(xiàng)集產(chǎn)生算法依次在每個(gè)等價(jià)類(lèi)內(nèi)搜索頻繁項(xiàng)集Apriori

21、算法采用的逐層策略可以看作根據(jù)項(xiàng)集的大小劃分格。等價(jià)類(lèi)也可以根據(jù)項(xiàng)集的前綴或后綴來(lái)定義。產(chǎn)生頻繁項(xiàng)集的其他方法項(xiàng)集格遍歷寬度優(yōu)先與深度優(yōu)先通常，深度優(yōu)先搜索方法是用于發(fā)現(xiàn)最大頻繁項(xiàng)集的算法產(chǎn)生頻繁項(xiàng)集的其他方法事務(wù)數(shù)據(jù)集的表示水平數(shù)據(jù)分布（horizontal data layout）垂直（vertical data layout）6.6 FP增長(zhǎng)算法（FP-growth Algorithm）不產(chǎn)生候選項(xiàng)集的算法該算法采用完全不同的方法來(lái)發(fā)現(xiàn)頻繁項(xiàng)集。該算法不同于A(yíng)priori算法的“產(chǎn)生-測(cè)試”范型。而是使用一種稱(chēng)作FP樹(shù)的緊湊數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)，并直接從該結(jié)構(gòu)中提取頻繁項(xiàng)集。FP樹(shù)是一種輸入

22、數(shù)據(jù)的壓縮表示，它通過(guò)逐個(gè)讀入事務(wù)，并把每個(gè)事務(wù)映射到FP樹(shù)中的一條路徑來(lái)構(gòu)造。 構(gòu)造FP樹(shù)掃描一次數(shù)據(jù)集，確定每個(gè)項(xiàng)的支持度計(jì)數(shù)。丟棄非頻繁項(xiàng)，將頻繁項(xiàng)按照支持度的遞減排序算法第二次掃描數(shù)據(jù)集，構(gòu)建FP樹(shù)：創(chuàng)建根節(jié)點(diǎn)，用null標(biāo)記；將每個(gè)事務(wù)中的項(xiàng)按遞減支持度計(jì)數(shù)排列，并對(duì)每個(gè)事務(wù)創(chuàng)建一個(gè)分支；當(dāng)為一個(gè)事務(wù)考慮增加分支時(shí)，沿共同前綴上的每個(gè)節(jié)點(diǎn)的計(jì)數(shù)加1，為跟隨前綴后的項(xiàng)創(chuàng)建節(jié)點(diǎn)并連接。繼續(xù)該過(guò)程,直到每個(gè)事務(wù)都映射到FP樹(shù)的一條路徑。創(chuàng)建一個(gè)項(xiàng)頭表，以方便遍歷，每個(gè)項(xiàng)通過(guò)一個(gè)節(jié)點(diǎn)鏈指向它在樹(shù)中的出現(xiàn)。構(gòu)造FP樹(shù)nullA:1B:1nullA:1B:1B:1C:1D:1讀入事務(wù) TID=1

23、后:讀入事務(wù) TID=2后:構(gòu)造FP樹(shù)D:1E:1nullA:2B:1B:1C:1D:1讀入事務(wù) TID=3后:C:1構(gòu)造FP樹(shù)nullA:8B:5B:2C:2D:1C:1D:1C:3D:1D:1E:1E:1D:1E:1Header table構(gòu)造FP樹(shù)通常，F(xiàn)P樹(shù)的大小比未壓縮的數(shù)據(jù)小，因?yàn)橘?gòu)物籃數(shù)據(jù)的事務(wù)常常共享一些共同項(xiàng)。如果共同項(xiàng)較少，F(xiàn)P樹(shù)對(duì)存儲(chǔ)空間的壓縮效果將不明顯。FP樹(shù)的大小也依賴(lài)于項(xiàng)如何排序。一般按照支持度計(jì)數(shù)遞減序可以導(dǎo)致較小的FP樹(shù)。但也有一些例外。FP樹(shù)還包含一個(gè)連接具有相同項(xiàng)的結(jié)點(diǎn)的指針列表。這些指針有助于方便快捷地訪(fǎng)問(wèn)樹(shù)中的項(xiàng)。構(gòu)造FP樹(shù)FP增長(zhǎng)（FP-growth

24、）算法FP增長(zhǎng)是一種以自底向上方式探索樹(shù)，由FP樹(shù)產(chǎn)生頻繁項(xiàng)集的算法。由于每一個(gè)事務(wù)都映射到FP樹(shù)中的一條路徑，因而通過(guò)僅考察包含特定結(jié)點(diǎn)（例如e）的途徑，就可以發(fā)現(xiàn)以e結(jié)尾的頻繁項(xiàng)集。使用與結(jié)點(diǎn)e相關(guān)聯(lián)的指針，可以快速訪(fǎng)問(wèn)這些路徑。FP增長(zhǎng)（FP-growth）算法FP增長(zhǎng)（FP-growth）算法FP增長(zhǎng)（FP-growth）算法發(fā)現(xiàn)以e結(jié)尾的頻繁項(xiàng)集的任務(wù)：收集包含e結(jié)點(diǎn)的所有路徑。前綴路徑通過(guò)把與e相關(guān)聯(lián)的支持度計(jì)數(shù)相加得到e的支持度計(jì)數(shù)。如果e是頻繁的，則解決發(fā)現(xiàn)以de、ce、be和ae結(jié)尾頻繁項(xiàng)集的子問(wèn)題。先將前綴路徑轉(zhuǎn)化為條件FP樹(shù),步驟如下：更新前綴路徑上的支持度計(jì)數(shù)。刪除e的

25、結(jié)點(diǎn)，修剪前綴路徑。刪除不頻繁項(xiàng)。FP增長(zhǎng)使用e的條件FP樹(shù)來(lái)解決發(fā)現(xiàn)以de,ce,be和ae結(jié)尾的頻繁項(xiàng)集的子問(wèn)題。FP增長(zhǎng)（FP-growth）算法6.7 關(guān)聯(lián)模式的評(píng)估（Pattern Evaluation）關(guān)聯(lián)分析算法往往產(chǎn)生大量的規(guī)則，而其中很大一部分可能是不感興趣的。 因此，建立一組廣泛接受的評(píng)價(jià)關(guān)聯(lián)模式質(zhì)量的標(biāo)準(zhǔn)是非常重要的。第一組標(biāo)準(zhǔn)可以通過(guò)統(tǒng)計(jì)論據(jù)建立。涉及相互獨(dú)立的項(xiàng)或覆蓋少量事務(wù)的模式被認(rèn)為是不令人感興趣的，因?yàn)樗鼈兛赡芊从硵?shù)據(jù)中的偽聯(lián)系。這些令人感興趣的模式可以使用客觀(guān)興趣度度量來(lái)排除。第二組標(biāo)準(zhǔn)可以通過(guò)主觀(guān)論據(jù)建立。一個(gè)模式被主觀(guān)認(rèn)為是無(wú)趣的，除非它能夠揭示料想不到的

26、信息或提供導(dǎo)致有益的行動(dòng)的有用信息。例如：黃油 面包可能不是有趣的，盡管有很高的支持度和置信度，但是它表示的關(guān)系顯而易見(jiàn)。另一方面，規(guī)則尿布 啤酒是有趣的，因?yàn)檫@種聯(lián)系十分出乎意料，并且可能為零售商提供新的交叉銷(xiāo)售機(jī)會(huì)。將主觀(guān)知識(shí)加入到模式的評(píng)價(jià)中是一項(xiàng)困難的任務(wù)，因?yàn)樾枰獊?lái)自領(lǐng)域?qū)＜业拇罅肯闰?yàn)信息。興趣度客觀(guān)度量(objective interestingness measure)客觀(guān)興趣度度量使用從數(shù)據(jù)推導(dǎo)出的統(tǒng)計(jì)量來(lái)確定模式是否是有趣的?？陀^(guān)興趣度度量的例子包括支持度、置信度、相關(guān)性。給定一個(gè)規(guī)則 X Y, 我們可以構(gòu)建一個(gè)相依表（contingency table）。YY Xf11f1

27、0f1+X f01f00fo+f+1f+0|T|Contingency table for X Y支持度-置信度框架的局限性現(xiàn)有的關(guān)聯(lián)規(guī)則的挖掘算法依賴(lài)于支持度和置信度來(lái)除去沒(méi)有意義的模式。例子：假定希望分析愛(ài)喝咖啡和愛(ài)喝茶的人之間的關(guān)系。收集一組人關(guān)于飲料偏愛(ài)的信息，并匯總到下表6-8。CoffeeCoffeeTea15050200Tea6501508008002001000支持度-置信度框架的局限性可以使用表中給出的信息來(lái)評(píng)估關(guān)系規(guī)則茶 咖啡。似乎喜歡喝茶的人也喜歡喝咖啡，因?yàn)樵撘?guī)則的支持度（15%）和置信度（75%）都相當(dāng)高。但是所有人中，不管他是否喝茶，喝咖啡的人的比例為80%。這意味

28、著，一個(gè)人如果喝茶，則他喝咖啡的可能性由80%減到了75%。置信度的缺點(diǎn)在于該度量忽略了規(guī)則后件中項(xiàng)集的支持度。由于支持度-置信度框架的局限性，各種客觀(guān)度量已經(jīng)用來(lái)評(píng)估關(guān)聯(lián)模式。下面，簡(jiǎn)略介紹這些度量并解釋它們的優(yōu)點(diǎn)和局限性。興趣因子相關(guān)分析IS度量興趣因子茶和咖啡的例子表明，由于置信度度量忽略了規(guī)則后件中出現(xiàn)的項(xiàng)集的支持度，高置信度的規(guī)則有時(shí)存在誤導(dǎo)。解決這個(gè)問(wèn)題的一種方法是使用稱(chēng)作提升度（lift）的度量： 它計(jì)算規(guī)則置信度和規(guī)則后件中項(xiàng)集的支持度之間的比率對(duì)于二元變量，提升度等價(jià)于另一種稱(chēng)作興趣因子（interest factor）的客觀(guān)度量，其定義如下：對(duì)于相互獨(dú)立的兩個(gè)變量，I(A,

29、B)=1。如果A和B是正相關(guān)的,則I(A,B)1。對(duì)于表6-8中的例子，I=0.15/(0.2*0.8)=0.9375, 這表明存在負(fù)相關(guān)。興趣因子的局限性表6-9顯示了兩個(gè)詞p,q和r,s出現(xiàn)的頻率。p,q和r,s的興趣因子分別為1.02和4.08.這表明雖然p和q同時(shí)出現(xiàn)在88%的文檔中，但是它們的興趣因子接近于1，表明二者是相互獨(dú)立的。另一方面，r,s的興趣因子比p,q的高，盡管r和s很少同時(shí)出現(xiàn)在同一個(gè)文檔中。這種情況下，置信度可能是一個(gè)更好的選擇，因?yàn)橹眯哦缺砻鱬和q之間的關(guān)聯(lián)（94.6%）遠(yuǎn)遠(yuǎn)強(qiáng)于r和s之間的關(guān)聯(lián)（28.6%）.表6-9ppq88050930q50207093070

30、1000rrs205070s50880930709301000相關(guān)分析對(duì)于二元變量，相關(guān)度可以用以下公式表示。相關(guān)度的值從-1（完全負(fù)相關(guān)）到+1（完全正相關(guān)）。如果變量是統(tǒng)計(jì)獨(dú)立的，則值為0.例如：在表6-8中給出的飲茶者和喝咖啡者之間的相關(guān)度為-0.0625。相關(guān)分析的局限性相關(guān)性的缺點(diǎn)通過(guò)表6-9所給出詞的關(guān)聯(lián)可以看出.雖然p和q同時(shí)出現(xiàn)的次數(shù)比r和s更多，但是它們的系數(shù)是相同的，都等于0.232。這是因?yàn)?，這種方法把項(xiàng)在事務(wù)中出現(xiàn)和同時(shí)不出現(xiàn)視為同等重要。因此，它更適合于分析對(duì)稱(chēng)的二元變量。這種度量的另一個(gè)局限性是，當(dāng)樣本大小成比例變化時(shí)，它不能夠保持不變。IS度量IS是另一種度量，用

31、于處理非對(duì)稱(chēng)二元變量。該度量定義如下：表6-9中顯示的詞對(duì)p,q和r,s的IS值分別是0.946和0.286.IS度量暗示p,q之間的關(guān)聯(lián)強(qiáng)于r,s，這與期望的文檔中詞的關(guān)聯(lián)一致?？梢宰C明IS數(shù)學(xué)上等價(jià)于二元變量的余弦變量IS度量也可以表示為從一對(duì)二元變量中提取出的關(guān)聯(lián)規(guī)則的置信度的幾何平均值：IS度量的局限性一對(duì)相互獨(dú)立的項(xiàng)集A和B的IS值是：盡管表6-10中所顯示的項(xiàng)p和q之間的IS值相當(dāng)大（0.889），當(dāng)項(xiàng)統(tǒng)計(jì)獨(dú)立時(shí)它仍小于期望值（ISindep=0.9）。表6-10ppq800100900q10001009001001000其他客觀(guān)興趣度度量不同度量間的比較客觀(guān)度量的性質(zhì)反演性客觀(guān)度

32、量M在反演操作下是不變的，如果交換頻度計(jì)數(shù)f11和f00、f10和f01它的值保持不變.在反演操作下保持不變的度量有系數(shù)、幾率、k和集體強(qiáng)度。這些度量可能不適合于分析非對(duì)稱(chēng)的二元數(shù)據(jù)。一些非反演不變的度量包括興趣因子、IS、PS、Jaccard系數(shù)。零加性客觀(guān)度量M在零加操作下是不變的，如果增加f00而保持相依表中所有其他的頻度不變并不影響M的值.對(duì)文檔分析或購(gòu)物籃分析這樣的應(yīng)用，期望度量多在零加操作下保持不變。滿(mǎn)足零加性的度量包括余弦（IS）和Jaccard度量，而不滿(mǎn)足該性質(zhì)的度量包括興趣因子、PS、幾率和系數(shù)。縮放性客觀(guān)度量M在行/列縮放操作下是不變的，如果M（T）=M（T），其中T是頻度計(jì)數(shù)為f11,f00,f10,f01的相依表。T是頻度計(jì)數(shù)為k1k3f11, k2k3f10, k1k4f01, k2k4f00的相依表。MaleFemaleHigh302050Low4010507030100MaleFemaleHigh6060120Low803011014090230表6-16顯示了