8.关联分析-50.ppt-大数据资源.ppt

Hash樹結構 1 5 9 1 4 5 1 3 6 3 4 5 3 6 7 3 6 8 3 5 6 3 5 7 6 8 9 2 3 4 5 6 7 1 2 4 4 5 7 1 2 5 4 5 8 1,4,7 2,5,8 3,6,9 Hash Function Candidate Hash Tree Hash on 3, 6 or 9 使用Hash樹進行支持度計數 1 5 9 1 4 5 1 3 6 3 4 5 3 6 7 3 6 8 3 5 6 3 5 7 6 8 9 2 3 4 5 6 7 1 2 4 4 5 7 1 2 5 4 5 8 1 2 3 5 6 1 + 2 3 5 6 3 5 6 2 + 5 6 3 + 1,4,7 2,5,8 3,6,9 Hash Function transaction 使用Hash樹進行支持度計數 1 5 9 1 4 5 1 3 6 3 4 5 3 6 7 3 6 8 3 5 6 3 5 7 6 8 9 2 3 4 5 6 7 1 2 4 4 5 7 1 2 5 4 5 8 1,4,7 2,5,8 3,6,9 Hash Function 1 2 3 5 6 3 5 6 1 2 + 5 6 1 3 + 6 1 5 + 3 5 6 2 + 5 6 3 + 1 + 2 3 5 6 transaction 使用Hash樹進行支持度計數 1 5 9 1 4 5 1 3 6 3 4 5 3 6 7 3 6 8 3 5 6 3 5 7 6 8 9 2 3 4 5 6 7 1 2 4 4 5 7 1 2 5 4 5 8 1,4,7 2,5,8 3,6,9 Hash Function 1 2 3 5 6 3 5 6 1 2 + 5 6 1 3 + 6 1 5 + 3 5 6 2 + 5 6 3 + 1 + 2 3 5 6 transaction 15個項集中的9個與事務進行比較 存放在被訪問的葉結點中的候選項集與事務進行比較，如果候選項集是該事務的子集，則增加它的支持度計數； 在該例子中 ，訪問了9個葉子結點中的5個； 15個項集中的9個與事務進行比較。 使用Hash樹進行支持度計數 計算複雜性 支持度閾值 降低支持度閾值通常將導致更多的項集是頻繁的。計算複雜度增加 隨著支持度閾值的降低，頻繁項集的最大長度將增加，導致演算法需要掃描數據集的次數也將增多 項數 隨著項數的增加，需要更多的空間來存儲項的支持度計數。如果頻繁項集的數目也隨著數據項目數增加而增長，則由於演算法產生的候選項集更多，計算量和I/O開銷將增加 事務數 由於Apriori演算法反復掃描數據集，因此它的執行時間隨著事務數增加而增加 事務的平均寬度 頻繁項集的最大長度隨事務平均寬度增加而增加 隨著事務寬度的增加，事務中將包含更多的項集，這將增加支持度計數時Hash樹的遍歷次數 規則產生 忽略那些前件或後件為空的規則，每個頻繁k-項集能夠產生多達2k-2個關聯規則 關聯規則的提取：將一個項集 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 ?ABCAB ?CD, AC ? BD, AD ? BC, BC ?AD, BD ?AC, CD ?AB,  這樣的規則必然已經滿足支持度閾值，因為它們是由頻繁項集產生的。 規則產生 怎樣有效的從頻繁項集中產生關聯規則? 一般，計算關聯規則的置信度並不需要再次掃描交易數據集。規則{A,B,C} ?{D}的置信度為σ(ABCD)/ σ(ABC)。 因為這兩個項集的支持度計數已經在頻繁項集產生時得到，因此不必再掃描整個數據集 如果規則X ?Y-X不滿足置信度閾值，則形如X‘?Y-X’的規則一定也不滿足置信度閾值，其中X‘是X的子集。 例如：c(ABC ? D) ? c(AB ? CD) ? c(A ? BCD) 因為σ(AB) ?σ(ABC)，則σ(ABCD)/ σ(ABC) ? σ(ABCD)/ σ(AB) ，則c(ABC ? D) ? c(AB ? CD) 規則產生的Apriori演算法 規則格 剪掉的規則 低置信度規則 Apriori偽代碼（三） Apriori偽代碼（四） 假如有項目集合I={1，2，3，4，5}，有事務集T： 關聯分析：舉例 Tid Items 1 1,2,3 2 1,2,4 3 1,3,4 4 1,2,3,5 5 1,3,5 6 2,4,5 7 1,2,3,4 設定minsup=3/7，misconf=5/7。 首先：生成頻繁項目集： 　　1-