數據挖掘課件教程.ppt

關聯分析: 基本概念和算法,第6章 關聯分析: 基本概念和算法,定義:關聯分析（association analysis）,關聯分析用于發(fā)現隱藏在大型數據集中的令人感興趣的聯系，所發(fā)現的模式通常用關聯規(guī)則或頻繁項集的形式表示。 關聯分析可以應用于生物信息學、醫(yī)療診斷、網頁挖掘、科學數據分析等,Rules Discovered: Diaper Beer,定義: 頻繁項集（Frequent Itemset）,項集（Itemset） 包含0個或多個項的集合 例子: Milk, Bread, Diaper k-項集 如果一個項集包含k個項 支持度計數（Support count ）() 包含特定項集的事務個數 例如： (Milk, Bread,Diaper) = 2 支持度（Support） 包含項集的事務數與總事務數的比值 例如： s(Milk, Bread, Diaper) = 2/5 頻繁項集（Frequent Itemset） 滿足最小支持度閾值（ minsup ）的所有項集,定義: 關聯規(guī)則（Association Rule）,Example:,關聯規(guī)則 關聯規(guī)則是形如 X Y的蘊含表達式, 其中 X 和 Y 是不相交的項集 例子: Milk, Diaper Beer 關聯規(guī)則的強度 支持度 Support (s) 確定項集的頻繁程度 置信度 Confidence (c) 確定Y在包含X的事 務中出現的頻繁程度,關聯規(guī)則挖掘問題,關聯規(guī)則挖掘問題：給定事務的集合 T, 關聯規(guī)則發(fā)現是指找出支持度大于等于 minsup并且置信度大于等于minconf的所有規(guī)則, minsup和minconf是對應的支持度和置信度閾值 挖掘關聯規(guī)則的一種原始方法是：Brute-force approach: 計算每個可能規(guī)則的支持度和置信度 這種方法計算代價過高，因為可以從數據集提取的規(guī)則的數量達指數級 從包含d個項的數據集提取的可能規(guī)則的總數R=3d-2d+1+1，如果d等于6，則R=602,挖掘關聯規(guī)則（Mining Association Rules）,大多數關聯規(guī)則挖掘算法通常采用的一種策略是，將關聯規(guī)則挖掘任務分解為如下兩個主要的子任務: 頻繁項集產生（Frequent Itemset Generation） 其目標是發(fā)現滿足最小支持度閾值的所有項集，這些項集稱作頻繁項集。 規(guī)則的產生（Rule Generation） 其目標是從上一步發(fā)現的頻繁項集中提取所有高置信度的規(guī)則，這些規(guī)則稱作強規(guī)則（strong rule）。,頻繁項集產生（Frequent Itemset Generation）,格結構（lattice structure）,頻繁項集產生（Frequent Itemset Generation）,Brute-force 方法: 把格結構中每個項集作為候選項集 將每個候選項集和每個事務進行比較，確定每個候選項集的支持度計數。 時間復雜度 O(NMw)，這種方法的開銷可能非常大。,降低產生頻繁項集計算復雜度的方法,減少候選項集的數量 (M) 先驗(apriori)原理 減少比較的次數 (NM) 替代將每個候選項集與每個事務相匹配，可以使用更高級的數據結構，或存儲候選項集或壓縮數據集，來減少比較次數,先驗原理（ Apriori principle）,先驗原理: 如果一個項集是頻繁的，則它的所有子集一定也是頻繁的 相反，如果一個項集是非頻繁的，則它的所有超集也一定是非頻繁的: 這種基于支持度度量修剪指數搜索空間的策略稱為基于支持度的剪枝（support-based pruning） 這種剪枝策略依賴于支持度度量的一個關鍵性質，即一個項集的支持度決不會超過它的子集的支持度。這個性質也稱為支持度度量的反單調性（anti-monotone）。,例子,被剪枝的超集,Apriori算法的頻繁項集產生,Apriori算法的頻繁項集產生,Items (1-itemsets),Pairs (2-itemsets),Triplets (3-itemsets),支持度閾值=60% 最小支持度計數 = 3,枚舉所有項集將產生 6C1 + 6C2 + 6C3 = 41個候選 而使用先驗原理，將較少為 6 + 6 + 1 = 13,Apriori 算法,Apriori 算法,Apriori算法的頻繁項集產生的部分有兩個重要的特點： 它是一個逐層算法。即從頻繁1-項集到最長的頻繁項集，它每次遍歷項集格中的一層 它使用產生-測試策略來發(fā)現頻繁項集。在每次迭代，新的候選項集由前一次迭代發(fā)現的頻繁項集產生，然后對每個候選的支持度進行計數，并與最小支持度閾值進行比較。 該算法需要的總迭代次數是kmax+1，其中kmax是頻繁項集的最大長度,候選的產生與剪枝(構造apriori-gen函數),蠻力方法 蠻力方法把所有的k-項集都看作可能的候選，然后使用候選剪枝除去不必要的候選 第k層產生的候選項集的數目為 雖然候選產生是相當簡單的，但是候選剪枝的開銷極大，因為必須考察的項集數量太大。 設每一個候選項集所需的計算量為O（k），這種方法 的總復雜度為,候選的產生與剪枝,Items (1-itemsets),Pairs (2-itemsets),Triplets (3-itemsets),支持度閾值=60% 最小支持度計數 = 3,枚舉所有項集將產生 6C1 + 6C2 + 6C3 = 41個候選 而使用先驗原理，將較少為 6 + 6 + 1 = 13,候選的產生與剪枝,這種方法用其他頻繁項來擴展每個頻繁（k-1）-項集 這種方法將產生 個候選k-項集，其中|Fj|表示頻繁j-項集的個數。這種方法總復雜度是 這種方法是完全的，因為每一個頻繁k-項集都是由一個頻繁（k-1）-項集和一個頻繁1-項集組成的。因此，所有的頻繁k-項集是這種方法所產生的候選k-項集的一部分。 然而，這種方法很難避免重復地產生候選項集。 如：面包，尿布，牛奶不僅可以由合并項集面包，尿布和牛奶得到，而且還可以由合并面包，牛奶和尿布得到，或由合并尿布，牛奶和面包得到。,候選的產生與剪枝,候選的產生與剪枝,避免產生重復的候選項集的一種方法是確保每個頻繁項集中的項以字典序存儲，每個頻繁（k-1）-項集X只用字典序比X中所有的項都大的頻繁項進行擴展 如：項集面包，尿布可以用項集牛奶擴展，因為“牛奶”（milk）在字典序下比“面包”（Bread）和“尿布”（Diapers）都大。 盡管這種方法比蠻力方法有明顯改進，但是仍然產生大量不必要的候選。 例如，通過合并啤酒，尿布和牛奶而得到的候選是不必要的。因為它的子集啤酒，牛奶是非頻繁的。,候選的產生與剪枝,這種方法合并一對頻繁（k-1）-項集，僅當它們的前k-2個項都相同。 如頻繁項集面包，尿布和面包，牛奶合并，形成了候選3-項集面包，尿布，牛奶。算法不會合并項集啤酒，尿布和尿布，牛奶，因為它們的第一個項不相同。 然而，由于每個候選都由一對頻繁（k-1）-項集合并而成，因此，需要附加的候選剪枝步驟來確保該候選的其余k-2個子集是頻繁的。,候選的產生與剪枝,支持度計數,支持度計數過程確定在apriori-gen函數的候選項剪枝步驟保留下來的每個候選項集出現的頻繁程度。計算支持度的主要方法: 一種方法是將每個事務與所有的候選項集進行比較，并且更新包含在事務中的候選項集的支持度計數。這種方法是計算昂貴的，尤其當事務和候選項集的數目都很大時。 另一種方法是枚舉每個事務所包含的項集，并且利用它們更新對應的候選項集的支持度。,枚舉事務t的所有包含3個項的子集,產生Hash樹,Hash函數h(p)=p mod 3 假設有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,Hash樹結構,1,4,7,2,5,8,3,6,9,Hash Function,Candidate Hash Tree,Hash on 1, 4 or 7,Hash樹結構,1,4,7,2,5,8,3,6,9,Hash Function,Candidate Hash Tree,Hash on 2, 5 or 8,Hash樹結構,1,4,7,2,5,8,3,6,9,Hash Function,Candidate Hash Tree,Hash on 3, 6 or 9,使用Hash樹進行支持度計數,transaction,使用Hash樹進行支持度計數,1 5 9,1 3 6,3 4 5,transaction,使用Hash樹進行支持度計數,1 5 9,1 3 6,3 4 5,transaction,15個項集中的9個與事務進行比較,存放在被訪問的葉結點中的候選項集與事務進行比較，如果候選項集是該事務的子集，則增加它的支持度計數。 在該例子中 ，訪問了9個葉子結點中的5個。 15個項集中的9個與事務進行比較,計算復雜性,支持度閾值 降低支持度閾值通常將導致更多的項集是頻繁的。計算復雜度增加 隨著支持度閾值的降低，頻繁項集的最大長度將增加，導致算法需要掃描數據集的次數也將增多 項數 隨著項數的增加，需要更多的空間來存儲項的支持度計數。如果頻繁項集的數目也隨著數據項數增加而增長，則由于算法產生的候選項集更多，計算量和I/O開銷將增加 事務數 由于Apriori算法反復掃描數據集，因此它的運行時間隨著事務數增加而增加 事務的平均寬度 頻繁項集的最大長度隨事務平均寬度增加而增加 隨著事務寬度的增加，事務中將包含更多的項集，這將增加支持度計數時Hash樹的遍歷次數,規(guī)則產生,忽略那些前件或后件為空的規(guī)則，每個頻繁k-項集能夠產生多達2k-2個關聯規(guī)則 關聯規(guī)則的提?。簩⒁粋€項集 Y劃分成兩個非空的子集 X 和Y-X，使得X Y X滿足置信度閾值。 如果 A,B,C,D 是頻繁項集, 候選項集為: 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ī)則必然已經滿足支持度閾值，因為它們是由頻繁項集產生的。,規(guī)則產生,怎樣有效的從頻繁項集中產生關聯規(guī)則? 一般，計算關聯規(guī)則的置信度并不需要再次掃描事務數據集。規(guī)則A,B,C D的置信度為(ABCD)/ (ABC)。 因為這兩個項集的支持度計數已經在頻繁項集產生時得到，因此不必再掃描整個數據集. 如果規(guī)則X Y-X不滿足置信度閾值，則形如XY-X的規(guī)則一定也不滿足置信度閾值，其中X是X的子集。 例如：c(ABC D) c(AB CD) c(A BCD) 因為(AB) (ABC)，則(ABCD)/ (ABC) (ABCD)/ (AB) ，則c(ABC D) c(AB CD),Apriori 算法中規(guī)則的產生,低置信度規(guī)則,頻繁項集的緊湊表示,由事務數據集產生的頻繁項集的數量可能非常大。因此，從中識別出可以推導出其他所有的頻繁項集的，較小的，具有代表性的項集是有用的。,最大頻繁項集（Maximal Frequent Itemset）,頻繁項集的邊界,不頻繁項集,最大頻繁項集,最大頻繁項集是這樣的頻繁項集，它的直接超集都不是頻繁的,非頻繁的,頻繁的,最大頻繁項集的特點,優(yōu)點：最大頻繁項集有效地提供了頻繁項集的緊湊表示。 換句話說，最大頻繁項集形成了可以導出所有頻繁項集的最小的項集的集合。 從圖中，可以看出，所有的頻繁項集是最大頻繁項集 A,D, A,C,E, B,C,D,E的子集 缺點：盡管最大頻繁項集提供了一種緊湊表示，但是它卻不包含它們子集的支持度信息。,頻繁閉項集（Closed Frequent Itemset）,閉項集（Closed Itemset）：項集X是閉的，如果它的直接超集都不具有和它相同的支持度計數。 換句話說，如果至少存在一個X的直接超集，其支持度計數與X相同，X就不是閉的。 頻繁閉項集: 一個項集是頻繁閉項集，如果它是閉的，并且它的支持度大于或等于最小支持度閾值。,頻繁閉項集,Transaction Ids,Not supported by any transactions,頻繁閉項集,minsup = 40%,# Closed Frequent Itemset = 9 # Maximal Frequent itemset = 4,頻繁項集、最大頻繁項集和頻繁閉項集之間的關系,產生頻繁項集的其他方法,項集格遍歷 一般到特殊 vs 特殊到一般。 一般到特殊：適合于頻繁項集的最大長度不是太長的時候。 特殊到一般：適合于處理頻繁項集的最大長度較長的時候,產生頻繁項集的其他方法,項集格遍歷 等價類：將格劃分為兩個不相交的節(jié)點組（或等價類）。頻繁項集產生算法依次在每個等價類內搜索頻繁項集 Apriori算法采用的逐層策略可以看作根據項集的大小劃分格。等價類也可以根據項集的前綴或后綴來定義。,產生頻繁項集的其他方法,項集格遍歷 寬度優(yōu)先與深度優(yōu)先 通常，深度優(yōu)先搜索方法是用于發(fā)現最大頻繁項集的算法,產生頻繁項集的其他方法,事務數據集的表示 水平數據分布（horizontal data layout） 垂直（vertical data layout）,FP增長算法（FP-growth Algorithm）,該算法采用完全不同的方法來發(fā)現頻繁項集。 該算法不同于Apriori算法的“產生-測試”范型。而是使用一種稱作FP樹的緊湊數據結構組織數據，并直接從該結構中提取頻繁項集。 FP樹是一種輸入數據的壓縮表示，它通過逐個讀入事務，并把每個事務映射到FP樹中的一條路徑來構造。,構造FP樹,掃描一次數據集，確定每個項的支持度計數。丟棄非頻繁項，而將頻繁項按照支持度的遞減排序 算法第二次掃描數據集，構建FP樹。讀入第一個事務a，b之后，創(chuàng)建標記為a和b的結點。然后形成null-a-b路徑，對該事務編碼。該路徑上的所有結點的頻度計數為1. 讀入第二個事務b，c，d之后，為項b，c和d創(chuàng)建新的結點集。然后，連接結點null-b-c-d，形成一條代表該事務的路徑。該路徑上的每個結點的頻度計數也等于1.盡管前兩個事務具有一個共同項b，但是它們的路徑不相交，因為這兩個事務沒有共同的前綴。,構造FP樹,null,A:1,B:1,null,A:1,B:1,B:1,C:1,D:1,讀入事務 TID=1后:,讀入事務 TID=2后:,第三個事務a，c，d，e與第一個事務共享一個共同的前綴項a，所以第三個事務的路徑null-a-c-d-e與第一個事務的路徑null-a-b部分重疊。因為它們的路徑重疊，所以結點a的頻度計數增加為2. 繼續(xù)該過程，直到每個事務都映射到FP樹的一條路徑。,構造FP樹,D:1,E:1,null,A:1,B:1,B:1,C:1,D:1,讀入事務 TID=3后:,C:1,構造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,構造FP樹,通常，FP樹的大小比未壓縮的數據小，因為購物籃數據的事務常常共享一些共同項。如果共同項較少，FP樹對存儲空間的壓縮效果將不明顯。 FP樹的大小也依賴于項如何排序。一般按照支持度計數遞減序可以導致較小的FP樹。但也有一些例外。 FP樹還包含一個連接具有相同項的結點的指針列表。這些指針有助于方便快捷地訪問樹中的項。,構造FP樹,FP增長（FP-growth）算法,FP增長是一種以自底向上方式探索樹，由FP樹產生頻繁項集的算法。 由于每一個事務都映射到FP樹中的一條路徑，因而通過僅考察包含特定結點（例如e）的途徑，就可以發(fā)現以e結尾的頻繁項集。使用與結點e相關聯的指針，可以快速訪問這些路徑。,FP增長（FP-growth）算法,FP增長（FP-growth）算法,FP增長（FP-growth）算法,關聯模式的評估（Pattern Evaluation）,關聯分析算法往往產生大量的規(guī)則，而其中很大一部分可能是不感興趣的。 因此，建立一組廣泛接受的評價關聯模式質量的標準是非常重要的。 第一組標準可以通過統計論據建立。涉及相互獨立的項或覆蓋少量事務的模式被認為是不令人感興趣的，因為它們可能反映數據中的偽聯系。 這些令人感興趣的模式可以使用客觀興趣度度量來排除。,第二組標準可以通過主觀論據建立。一個模式被主觀認為是無趣的，除非它能夠揭示料想不到的信息或提供導致有益的行動的有用信息。 例如：黃油 面包可能不是有趣的，盡管有很高的支持度和置信度，但是它表示的關系顯而易見。另一方面，規(guī)則尿布 啤酒是有趣的，因為這種聯系十分出乎意料，并且可能為零售商提供新的交叉銷售機會。 將主觀知識加入到模式的評價中是一項困難的任務，因為需要來自領域專家的大量先驗信息。下面是一些將主觀信息加入到模式發(fā)現任務中的方法。,興趣度客觀度量（objective interestingness measure）,客觀興趣度度量使用從數據推導出的統計量來確定模式是否是有趣的。 客觀興趣度度量的例子包括支持度、置信度、相關性。 給定一個規(guī)則 X Y, 我們可以構建一個相依表（contingency table）。,Contingency table for X Y,支持度-置信度框架的局限性,現有的關聯規(guī)則的挖掘算法依賴于支持度和置信度來除去沒有意義的模式。 例子：假定希望分析愛喝咖啡和愛喝茶的人之間的關系。收集一組人關于飲料偏愛的信息，并匯總到下表6-8。,支持度-置信度框架的局限性,可以使用表中給出的信息來評估關系規(guī)則茶 咖啡。 似乎喜歡喝茶的人也喜歡喝咖啡，因為該規(guī)則的支持度（15%）和置信度（75%）都相當高。 但是所有人中，不管他是否喝茶，喝咖啡的人的比例為80%。這意味著，一個人如果喝茶，則他喝咖啡的可能性由80%減到了75%。 置信度的缺點在于該度量忽略了規(guī)則后件中項集的支持度。,由于支持度-置信度框架的局限性，各種客觀度量已經用來評估關聯模式。下面，簡略介紹這些度量并解釋它們的優(yōu)點和局限性。 興趣因子 相關分析 IS度量,興趣因子,茶和咖啡的例子表明，由于置信度度量忽略了規(guī)則后件中出現的項集的支持度，高置信度的規(guī)則有時存在誤導。 解決這個問題的一種方法是使用稱作提升度（lift）的度量： 它計算規(guī)則置信度和規(guī)則后件中項集的支持度之間的比率 對于二元變量，提升度等價于另一種稱作興趣因子（interest factor）的客觀度量，其定義如下：,對于相互獨立的兩個變量，I(A,B)=1。如果A和B是正相關的,則I(A,B)1。對于表6-8中的例子，I=0.15/(0.2*0.8)=0.9375, 這表明存在負相關。 興趣因子的局限性 表6-9顯示了兩個詞p,q和r,s出現的頻率。p,q和r,s的興趣因子分別為1.02和4.08. 這表明雖然p和q同時出現在88%的文檔中，但是它們的興趣因子接近于1，表明二者是相互獨立的。另一方面，r,s的興趣因子比p,q的高，盡管r和s很少同時出現在同一個文檔中。 這種情況下，置信度可能是一個更好的選擇，因為置信度表明p和q之間的關聯（94.6%）遠遠強于r和s之間的關聯（28.6%）.,表6-9,相關分析,對于二元變量，相關度可以用以下公式表示。 相關度的值從-1（完全負相關）到+1（完全正相關）。如果變量是統計獨立的，則值為0.例如：在表6-8中給出的飲茶者和喝咖啡者之間的相關度為-0.0625。,相關分析的局限性 相關性的缺點通過表6-9所給出詞的關聯可以看出.雖然p和q同時出現的次數比r和s更多，但是它們的系數是相同的，都等于0.232。 這是因為，這種方法把項在事務中出現和同時不出現視為同等重要。因此，它更適合于分析對稱的二元變量。 這種度量的另一個局限性是，當樣本大小成比例變化時，它不能夠保持不變。,IS度量,IS是另一種度量，用于處理非對稱二元變量。該度量定義如下： 表6-9中顯示的詞對p,q和r,s的IS值分別是0.946和0.286.IS度量暗示p,q之間的關聯強于r,s，這與期望的文檔中詞的關聯一致。 可以證明IS數學上等價于二元變量的余弦變量,IS度量也可以表示為從一對二元變量中提取出的關聯規(guī)則的置信度的幾何平均值： IS度量的局限性 一對相互獨立的項集A和B的IS值是： 盡管表6-10中所顯示的項p和q之間的IS值相當大（0.889），當項統計獨立時它仍小于期望值（ISindep=0.9）。,表6-10,其他客觀興趣度度量,不同度量間的比較,客觀度量的性質,反演性 客觀度量M在反演操作下是不變的，如果交換頻度計數f11和f00、f10和f01它的值保持不變.,在反演操作下保持不變的度量有系數、幾率、k和集體強度。 這些度量可能不適合于分析非對稱的二元數據。 一些非反演不變的度量包括興趣因子、IS、PS、Jaccard系數。,零加性 客觀度量M在零加操作下是不變的，如果增加f00而保持相依表中所有其他的頻度不變并不影響M的值. 對文檔分析或購物籃分析這樣的應用，期望度量多在零加操作下保持不變。滿足零加性的度量包括余弦（IS）和Jaccard度量，而不滿足該性質的度量包括興趣因子、PS、幾率和系數。 縮放性 客觀度量M在行/列縮放操作下是不變的，如果M（T）=M（T），其中T是頻度計數為f11,f00,f10,f01的相依表。T是頻度計數為k1k3f11, k2k3f10, k1k4f01, k2k4f00的