數(shù)據(jù)挖掘課件教程.ppt

關(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)頁挖掘、科學(xué)數(shù)據(jù)分析等,Rules Discovered: Diaper Beer,定義: 頻繁項(xiàng)集（Frequent Itemset）,項(xiàng)集（Itemset） 包含0個(gè)或多個(gè)項(xiàng)的集合 例子: Milk, Bread, Diaper k-項(xiàng)集 如果一個(gè)項(xiàng)集包含k個(gè)項(xiàng) 支持度計(jì)數(shù)（Support count ）() 包含特定項(xiàng)集的事務(wù)個(gè)數(shù) 例如： (Milk, Bread,Diaper) = 2 支持度（Support） 包含項(xiàng)集的事務(wù)數(shù)與總事務(wù)數(shù)的比值 例如： s(Milk, Bread, Diaper) = 2/5 頻繁項(xiàng)集（Frequent Itemset） 滿足最小支持度閾值（ minsup ）的所有項(xiàng)集,定義: 關(guān)聯(lián)規(guī)則（Association Rule）,Example:,關(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ī)則的強(qiáng)度 支持度 Support (s) 確定項(xiàng)集的頻繁程度 置信度 Confidence (c) 確定Y在包含X的事 務(wù)中出現(xiàn)的頻繁程度,關(guān)聯(lián)規(guī)則挖掘問題,關(guān)聯(lián)規(guī)則挖掘問題：給定事務(wù)的集合 T, 關(guān)聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于 minsup并且置信度大于等于minconf的所有規(guī)則, minsup和minconf是對應(yīng)的支持度和置信度閾值 挖掘關(guān)聯(lián)規(guī)則的一種原始方法是：Brute-force approach: 計(jì)算每個(gè)可能規(guī)則的支持度和置信度 這種方法計(jì)算代價(jià)過高，因?yàn)榭梢詮臄?shù)據(jù)集提取的規(guī)則的數(shù)量達(dá)指數(shù)級 從包含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è)主要的子任務(wù): 頻繁項(xiàng)集產(chǎn)生（Frequent Itemset Generation） 其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集，這些項(xiàng)集稱作頻繁項(xiàng)集。 規(guī)則的產(chǎn)生（Rule Generation） 其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取所有高置信度的規(guī)則，這些規(guī)則稱作強(qiáng)規(guī)則（strong rule）。,頻繁項(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)集的支持度計(jì)數(shù)。 時(shí)間復(fù)雜度 O(NMw)，這種方法的開銷可能非常大。,降低產(chǎn)生頻繁項(xiàng)集計(jì)算復(fù)雜度的方法,減少候選項(xiàng)集的數(shù)量 (M) 先驗(yàn)(apriori)原理 減少比較的次數(shù) (NM) 替代將每個(gè)候選項(xiàng)集與每個(gè)事務(wù)相匹配，可以使用更高級的數(shù)據(jù)結(jié)構(gòu)，或存儲(chǔ)候選項(xiàng)集或壓縮數(shù)據(jù)集，來減少比較次數(shù),先驗(yàn)原理（ Apriori principle）,先驗(yàn)原理: 如果一個(gè)項(xiàng)集是頻繁的，則它的所有子集一定也是頻繁的 相反，如果一個(gè)項(xiàng)集是非頻繁的，則它的所有超集也一定是非頻繁的: 這種基于支持度度量修剪指數(shù)搜索空間的策略稱為基于支持度的剪枝（support-based pruning） 這種剪枝策略依賴于支持度度量的一個(gè)關(guān)鍵性質(zhì)，即一個(gè)項(xiàng)集的支持度決不會(huì)超過它的子集的支持度。這個(gè)性質(zhì)也稱為支持度度量的反單調(diào)性（anti-monotone）。,例子,被剪枝的超集,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)生 6C1 + 6C2 + 6C3 = 41個(gè)候選 而使用先驗(yàn)原理，將較少為 6 + 6 + 1 = 13,Apriori 算法,Apriori 算法,Apriori算法的頻繁項(xiàng)集產(chǎn)生的部分有兩個(gè)重要的特點(diǎn)： 它是一個(gè)逐層算法。即從頻繁1-項(xiàng)集到最長的頻繁項(xiàng)集，它每次遍歷項(xiàng)集格中的一層 它使用產(chǎn)生-測試策略來發(fā)現(xiàn)頻繁項(xiàng)集。在每次迭代，新的候選項(xiàng)集由前一次迭代發(fā)現(xiàn)的頻繁項(xiàng)集產(chǎn)生，然后對每個(gè)候選的支持度進(jìn)行計(jì)數(shù)，并與最小支持度閾值進(jìn)行比較。 該算法需要的總迭代次數(shù)是kmax+1，其中kmax是頻繁項(xiàng)集的最大長度,候選的產(chǎn)生與剪枝(構(gòu)造apriori-gen函數(shù)),蠻力方法 蠻力方法把所有的k-項(xiàng)集都看作可能的候選，然后使用候選剪枝除去不必要的候選 第k層產(chǎn)生的候選項(xiàng)集的數(shù)目為 雖然候選產(chǎn)生是相當(dāng)簡單的，但是候選剪枝的開銷極大，因?yàn)楸仨毧疾斓捻?xiàng)集數(shù)量太大。 設(shè)每一個(gè)候選項(xiàng)集所需的計(jì)算量為O（k），這種方法 的總復(fù)雜度為,候選的產(chǎn)生與剪枝,Items (1-itemsets),Pairs (2-itemsets),Triplets (3-itemsets),支持度閾值=60% 最小支持度計(jì)數(shù) = 3,枚舉所有項(xiàng)集將產(chǎn)生 6C1 + 6C2 + 6C3 = 41個(gè)候選 而使用先驗(yàn)原理，將較少為 6 + 6 + 1 = 13,候選的產(chǎn)生與剪枝,這種方法用其他頻繁項(xiàng)來擴(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)集的一部分。 然而，這種方法很難避免重復(fù)地產(chǎn)生候選項(xiàng)集。 如：面包，尿布，牛奶不僅可以由合并項(xiàng)集面包，尿布和牛奶得到，而且還可以由合并面包，牛奶和尿布得到，或由合并尿布，牛奶和面包得到。,候選的產(chǎn)生與剪枝,候選的產(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)生大量不必要的候選。 例如，通過合并啤酒，尿布和牛奶而得到的候選是不必要的。因?yàn)樗淖蛹【疲Ｄ淌欠穷l繁的。,候選的產(chǎn)生與剪枝,這種方法合并一對頻繁（k-1）-項(xiàng)集，僅當(dāng)它們的前k-2個(gè)項(xiàng)都相同。 如頻繁項(xiàng)集面包，尿布和面包，牛奶合并，形成了候選3-項(xiàng)集面包，尿布，牛奶。算法不會(huì)合并項(xiàng)集啤酒，尿布和尿布，牛奶，因?yàn)樗鼈兊牡谝粋€(gè)項(xiàng)不相同。 然而，由于每個(gè)候選都由一對頻繁（k-1）-項(xiàng)集合并而成，因此，需要附加的候選剪枝步驟來確保該候選的其余k-2個(gè)子集是頻繁的。,候選的產(chǎn)生與剪枝,支持度計(jì)數(shù),支持度計(jì)數(shù)過程確定在apriori-gen函數(shù)的候選項(xiàng)剪枝步驟保留下來的每個(gè)候選項(xiàng)集出現(xiàn)的頻繁程度。計(jì)算支持度的主要方法: 一種方法是將每個(gè)事務(wù)與所有的候選項(xiàng)集進(jìn)行比較，并且更新包含在事務(wù)中的候選項(xiàng)集的支持度計(jì)數(shù)。這種方法是計(jì)算昂貴的，尤其當(dāng)事務(wù)和候選項(xiàng)集的數(shù)目都很大時(shí)。 另一種方法是枚舉每個(gè)事務(wù)所包含的項(xiàng)集，并且利用它們更新對應(yīng)的候選項(xiàng)集的支持度。,枚舉事務(wù)t的所有包含3個(gè)項(xiàng)的子集,產(chǎn)生Hash樹,Hash函數(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 6 8,Hash樹結(jié)構(gòu),1,4,7,2,5,8,3,6,9,Hash Function,Candidate Hash Tree,Hash on 1, 4 or 7,Hash樹結(jié)構(gòu),1,4,7,2,5,8,3,6,9,Hash Function,Candidate Hash Tree,Hash on 2, 5 or 8,Hash樹結(jié)構(gòu),1,4,7,2,5,8,3,6,9,Hash Function,Candidate Hash Tree,Hash on 3, 6 or 9,使用Hash樹進(jìn)行支持度計(jì)數(shù),transaction,使用Hash樹進(jìn)行支持度計(jì)數(shù),1 5 9,1 3 6,3 4 5,transaction,使用Hash樹進(jìn)行支持度計(jì)數(shù),1 5 9,1 3 6,3 4 5,transaction,15個(gè)項(xiàng)集中的9個(gè)與事務(wù)進(jìn)行比較,存放在被訪問的葉結(jié)點(diǎn)中的候選項(xiàng)集與事務(wù)進(jìn)行比較，如果候選項(xiàng)集是該事務(wù)的子集，則增加它的支持度計(jì)數(shù)。 在該例子中 ，訪問了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)集的最大長度將增加，導(dǎo)致算法需要掃描數(shù)據(jù)集的次數(shù)也將增多 項(xiàng)數(shù) 隨著項(xiàng)數(shù)的增加，需要更多的空間來存儲(chǔ)項(xiàng)的支持度計(jì)數(shù)。如果頻繁項(xiàng)集的數(shù)目也隨著數(shù)據(jù)項(xiàng)數(shù)增加而增長，則由于算法產(chǎn)生的候選項(xiàng)集更多，計(jì)算量和I/O開銷將增加 事務(wù)數(shù) 由于Apriori算法反復(fù)掃描數(shù)據(jù)集，因此它的運(yùn)行時(shí)間隨著事務(wù)數(shù)增加而增加 事務(wù)的平均寬度 頻繁項(xiàng)集的最大長度隨事務(wù)平均寬度增加而增加 隨著事務(wù)寬度的增加，事務(wù)中將包含更多的項(xiàng)集，這將增加支持度計(jì)數(shù)時(shí)Hash樹的遍歷次數(shù),規(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滿足置信度閾值。 如果 A,B,C,D 是頻繁項(xiàng)集, 候選項(xiàng)集為: ABC D, ABD C, ACD B, BCD A, A BCD, B ACD, C ABD, D ABC AB CD, AC BD, AD BC, BC AD, BD AC, CD AB, 這樣的規(guī)則必然已經(jīng)滿足支持度閾值，因?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不滿足置信度閾值，則形如XY-X的規(guī)則一定也不滿足置信度閾值，其中X是X的子集。 例如：c(ABC D) c(AB CD) c(A BCD) 因?yàn)?AB) (ABC)，則(ABCD)/ (ABC) (ABCD)/ (AB) ，則c(ABC D) c(AB CD),Apriori 算法中規(guī)則的產(chǎn)生,低置信度規(guī)則,頻繁項(xiàng)集的緊湊表示,由事務(wù)數(shù)據(jù)集產(chǎn)生的頻繁項(xiàng)集的數(shù)量可能非常大。因此，從中識別出可以推導(dǎo)出其他所有的頻繁項(xiàng)集的，較小的，具有代表性的項(xiàng)集是有用的。,最大頻繁項(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)集的緊湊表示。 換句話說，最大頻繁項(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ù)。 換句話說，如果至少存在一個(gè)X的直接超集，其支持度計(jì)數(shù)與X相同，X就不是閉的。 頻繁閉項(xiàng)集: 一個(gè)項(xiàng)集是頻繁閉項(xiàng)集，如果它是閉的，并且它的支持度大于或等于最小支持度閾值。,頻繁閉項(xiàng)集,Transaction Ids,Not supported by any transactions,頻繁閉項(xiàng)集,minsup = 40%,# Closed Frequent Itemset = 9 # Maximal Frequent itemset = 4,頻繁項(xiàng)集、最大頻繁項(xiàng)集和頻繁閉項(xiàng)集之間的關(guān)系,產(chǎn)生頻繁項(xiàng)集的其他方法,項(xiàng)集格遍歷 一般到特殊 vs 特殊到一般。 一般到特殊：適合于頻繁項(xiàng)集的最大長度不是太長的時(shí)候。 特殊到一般：適合于處理頻繁項(xiàng)集的最大長度較長的時(shí)候,產(chǎn)生頻繁項(xiàng)集的其他方法,項(xiàng)集格遍歷 等價(jià)類：將格劃分為兩個(gè)不相交的節(jié)點(diǎn)組（或等價(jià)類）。頻繁項(xiàng)集產(chǎn)生算法依次在每個(gè)等價(jià)類內(nèi)搜索頻繁項(xiàng)集 Apriori算法采用的逐層策略可以看作根據(jù)項(xiàng)集的大小劃分格。等價(jià)類也可以根據(jù)項(xiàng)集的前綴或后綴來定義。,產(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）,FP增長算法（FP-growth Algorithm）,該算法采用完全不同的方法來發(fā)現(xiàn)頻繁項(xiàng)集。 該算法不同于Apriori算法的“產(chǎn)生-測試”范型。而是使用一種稱作FP樹的緊湊數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)，并直接從該結(jié)構(gòu)中提取頻繁項(xiàng)集。 FP樹是一種輸入數(shù)據(jù)的壓縮表示，它通過逐個(gè)讀入事務(wù)，并把每個(gè)事務(wù)映射到FP樹中的一條路徑來構(gòu)造。,構(gòu)造FP樹,掃描一次數(shù)據(jù)集，確定每個(gè)項(xiàng)的支持度計(jì)數(shù)。丟棄非頻繁項(xiàng)，而將頻繁項(xiàng)按照支持度的遞減排序 算法第二次掃描數(shù)據(jù)集，構(gòu)建FP樹。讀入第一個(gè)事務(wù)a，b之后，創(chuàng)建標(biāo)記為a和b的結(jié)點(diǎn)。然后形成null-a-b路徑，對該事務(wù)編碼。該路徑上的所有結(jié)點(diǎn)的頻度計(jì)數(shù)為1. 讀入第二個(gè)事務(wù)b，c，d之后，為項(xiàng)b，c和d創(chuàng)建新的結(jié)點(diǎn)集。然后，連接結(jié)點(diǎn)null-b-c-d，形成一條代表該事務(wù)的路徑。該路徑上的每個(gè)結(jié)點(diǎn)的頻度計(jì)數(shù)也等于1.盡管前兩個(gè)事務(wù)具有一個(gè)共同項(xiàng)b，但是它們的路徑不相交，因?yàn)檫@兩個(gè)事務(wù)沒有共同的前綴。,構(gòu)造FP樹,null,A:1,B:1,null,A:1,B:1,B:1,C:1,D:1,讀入事務(wù) TID=1后:,讀入事務(wù) TID=2后:,第三個(gè)事務(wù)a，c，d，e與第一個(gè)事務(wù)共享一個(gè)共同的前綴項(xiàng)a，所以第三個(gè)事務(wù)的路徑null-a-c-d-e與第一個(gè)事務(wù)的路徑null-a-b部分重疊。因?yàn)樗鼈兊穆窂街丿B，所以結(jié)點(diǎn)a的頻度計(jì)數(shù)增加為2. 繼續(xù)該過程，直到每個(gè)事務(wù)都映射到FP樹的一條路徑。,構(gòu)造FP樹,D:1,E:1,null,A:1,B:1,B:1,C:1,D:1,讀入事務(wù) TID=3后:,C:1,構(gòu)造FP樹,null,A:8,B:5,B:2,C:2,D:1,C:1,D:1,C:3,D:1,D:1,E:1,E:1,D:1,E:1,構(gòu)造FP樹,通常，F(xiàn)P樹的大小比未壓縮的數(shù)據(jù)小，因?yàn)橘徫锘@數(shù)據(jù)的事務(wù)常常共享一些共同項(xiàng)。如果共同項(xiàng)較少，F(xiàn)P樹對存儲(chǔ)空間的壓縮效果將不明顯。 FP樹的大小也依賴于項(xiàng)如何排序。一般按照支持度計(jì)數(shù)遞減序可以導(dǎo)致較小的FP樹。但也有一些例外。 FP樹還包含一個(gè)連接具有相同項(xiàng)的結(jié)點(diǎn)的指針列表。這些指針有助于方便快捷地訪問樹中的項(xiàng)。,構(gòu)造FP樹,FP增長（FP-growth）算法,FP增長是一種以自底向上方式探索樹，由FP樹產(chǎn)生頻繁項(xiàng)集的算法。 由于每一個(gè)事務(wù)都映射到FP樹中的一條路徑，因而通過僅考察包含特定結(jié)點(diǎn)（例如e）的途徑，就可以發(fā)現(xiàn)以e結(jié)尾的頻繁項(xiàng)集。使用與結(jié)點(diǎn)e相關(guān)聯(lián)的指針，可以快速訪問這些路徑。,FP增長（FP-growth）算法,FP增長（FP-growth）算法,FP增長（FP-growth）算法,關(guān)聯(lián)模式的評估（Pattern Evaluation）,關(guān)聯(lián)分析算法往往產(chǎn)生大量的規(guī)則，而其中很大一部分可能是不感興趣的。 因此，建立一組廣泛接受的評價(jià)關(guān)聯(lián)模式質(zhì)量的標(biāo)準(zhǔn)是非常重要的。 第一組標(biāo)準(zhǔn)可以通過統(tǒng)計(jì)論據(jù)建立。涉及相互獨(dú)立的項(xiàng)或覆蓋少量事務(wù)的模式被認(rèn)為是不令人感興趣的，因?yàn)樗鼈兛赡芊从硵?shù)據(jù)中的偽聯(lián)系。 這些令人感興趣的模式可以使用客觀興趣度度量來排除。,第二組標(biāo)準(zhǔn)可以通過主觀論據(jù)建立。一個(gè)模式被主觀認(rèn)為是無趣的，除非它能夠揭示料想不到的信息或提供導(dǎo)致有益的行動(dòng)的有用信息。 例如：黃油 面包可能不是有趣的，盡管有很高的支持度和置信度，但是它表示的關(guān)系顯而易見。另一方面，規(guī)則尿布 啤酒是有趣的，因?yàn)檫@種聯(lián)系十分出乎意料，并且可能為零售商提供新的交叉銷售機(jī)會(huì)。 將主觀知識加入到模式的評價(jià)中是一項(xiàng)困難的任務(wù)，因?yàn)樾枰獊碜灶I(lǐng)域?qū)＜业拇罅肯闰?yàn)信息。下面是一些將主觀信息加入到模式發(fā)現(xiàn)任務(wù)中的方法。,興趣度客觀度量（objective interestingness measure）,客觀興趣度度量使用從數(shù)據(jù)推導(dǎo)出的統(tǒng)計(jì)量來確定模式是否是有趣的。 客觀興趣度度量的例子包括支持度、置信度、相關(guān)性。 給定一個(gè)規(guī)則 X Y, 我們可以構(gòu)建一個(gè)相依表（contingency table）。,Contingency table for X Y,支持度-置信度框架的局限性,現(xiàn)有的關(guān)聯(lián)規(guī)則的挖掘算法依賴于支持度和置信度來除去沒有意義的模式。 例子：假定希望分析愛喝咖啡和愛喝茶的人之間的關(guān)系。收集一組人關(guān)于飲料偏愛的信息，并匯總到下表6-8。,支持度-置信度框架的局限性,可以使用表中給出的信息來評估關(guān)系規(guī)則茶 咖啡。 似乎喜歡喝茶的人也喜歡喝咖啡，因?yàn)樵撘?guī)則的支持度（15%）和置信度（75%）都相當(dāng)高。 但是所有人中，不管他是否喝茶，喝咖啡的人的比例為80%。這意味著，一個(gè)人如果喝茶，則他喝咖啡的可能性由80%減到了75%。 置信度的缺點(diǎn)在于該度量忽略了規(guī)則后件中項(xiàng)集的支持度。,由于支持度-置信度框架的局限性，各種客觀度量已經(jīng)用來評估關(guān)聯(lián)模式。下面，簡略介紹這些度量并解釋它們的優(yōu)點(diǎn)和局限性。 興趣因子 相關(guān)分析 IS度量,興趣因子,茶和咖啡的例子表明，由于置信度度量忽略了規(guī)則后件中出現(xiàn)的項(xiàng)集的支持度，高置信度的規(guī)則有時(shí)存在誤導(dǎo)。 解決這個(gè)問題的一種方法是使用稱作提升度（lift）的度量： 它計(jì)算規(guī)則置信度和規(guī)則后件中項(xiàng)集的支持度之間的比率 對于二元變量，提升度等價(jià)于另一種稱作興趣因子（interest factor）的客觀度量，其定義如下：,對于相互獨(dú)立的兩個(gè)變量，I(A,B)=1。如果A和B是正相關(guān)的,則I(A,B)1。對于表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-9,相關(guān)分析,對于二元變量，相關(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)通過表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)視為同等重要。因此，它更適合于分析對稱的二元變量。 這種度量的另一個(gè)局限性是，當(dāng)樣本大小成比例變化時(shí)，它不能夠保持不變。,IS度量,IS是另一種度量，用于處理非對稱二元變量。該度量定義如下： 表6-9中顯示的詞對p,q和r,s的IS值分別是0.946和0.286.IS度量暗示p,q之間的關(guān)聯(lián)強(qiáng)于r,s，這與期望的文檔中詞的關(guān)聯(lián)一致。 可以證明IS數(shù)學(xué)上等價(jià)于二元變量的余弦變量,IS度量也可以表示為從一對二元變量中提取出的關(guān)聯(lián)規(guī)則的置信度的幾何平均值： IS度量的局限性 一對相互獨(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-10,其他客觀興趣度度量,不同度量間的比較,客觀度量的性質(zhì),反演性 客觀度量M在反演操作下是不變的，如果交換頻度計(jì)數(shù)f11和f00、f10和f01它的值保持不變.,在反演操作下保持不變的度量有系數(shù)、幾率、k和集體強(qiáng)度。 這些度量可能不適合于分析非對稱的二元數(shù)據(jù)。 一些非反演不變的度量包括興趣因子、IS、PS、Jaccard系數(shù)。,零加性 客觀度量M在零加操作下是不變的，如果增加f00而保持相依表中所有其他的頻度不變并不影響M的值. 對文檔分析或購物籃分析這樣的應(yīng)用，期望度量多在零加操作下保持不變。滿足零加性的度量包括余弦（IS）和Jaccard度量，而不滿足該性質(zhì)的度量包括興趣因子、PS、幾率和系數(shù)。 縮放性 客觀度量M在行/列縮放操作下是不變的，如果M（T）=M（T），其中T是頻度計(jì)數(shù)為f11,f00,f10,f01的相依表。T是頻度計(jì)數(shù)為k1k3f11, k2k3f10, k1k4f01, k2k4f00的