【正文】 關(guān)聯(lián)規(guī)則 90 多層關(guān)聯(lián)規(guī)則 :逐步深化 (Progressive Deepening) ? 一個(gè)自上而下的 ,逐步深化的方法 : ? 首先挖掘高層的頻繁項(xiàng) : milk (15%), bread (10%) ? 然后挖掘它們的較低層 ”較弱 ” (weaker)頻繁項(xiàng) : 2% milk (5%), wheat bread (4%) ? 多層之間不同的最小支持度閾值導(dǎo)致了不同的算法 : ? 如果在多個(gè)層次間采用了相同的最小支持度 ,若 t的任何一個(gè)先輩都是非頻繁的則扔棄 (toss)t. ? 如果在較低層采用了減少的最小支持度，則只檢驗(yàn)?zāi)切┫容叺闹С侄仁穷l繁的／不可忽略的派生（ descendents）即可． 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 91 多維關(guān)聯(lián)規(guī)則挖掘的技術(shù) ? 搜索頻繁 k謂詞集 (predicate set): ? 示例 : {age, occupation, buys}是一個(gè) 3謂詞集 以 age處理 的方式 ,技術(shù)可以如下分類 1. 利用數(shù)量屬性的統(tǒng)計(jì)離散 (static discretization)方法 利用預(yù)先確定的概念層次對(duì)數(shù)量屬性進(jìn)行統(tǒng)計(jì)離散化 2. 量化關(guān)聯(lián)規(guī)則 ? 基于數(shù)據(jù)的分布 ,數(shù)量屬性被動(dòng)態(tài)地離散化到不同的容器空間(bins) 3. 基于距離 (Distancebased)的關(guān)聯(lián)規(guī)則 ? 這是一個(gè)動(dòng)態(tài)離散化的過(guò)程 ,該過(guò)程考慮數(shù)據(jù)點(diǎn)之間的距離 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 92 數(shù)量屬性的統(tǒng)計(jì)離散化 ? 挖掘之前利用概念層次離散化 ? 數(shù)值被范圍 (ranges)替代 . ? 關(guān)系數(shù)據(jù)庫(kù)中 ,找出所有的頻繁 k謂詞 (predicate)集要求 k 或 k+1次表掃描 . ? 數(shù)據(jù)立方體 (data cube)非常適合數(shù)據(jù)挖掘 . ? N維立方體的 cells 與謂詞集 ( predicate sets)相對(duì)應(yīng) . ? 通過(guò)數(shù)據(jù)立方體挖掘會(huì)非?？焖?. (ine) (age) () (buys) (age, ine) (age,buys) (ine,buys) (age,ine,buys) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 93 量化關(guān)聯(lián)規(guī)則 age(X,”3034”) ? ine(X,”24K 48K”) ? buys(X,”high resolution TV”) ? 數(shù)值屬性動(dòng)態(tài)離散化 ? 這樣挖掘的規(guī)則的可信度或緊密度最大化 ? 2維 量化關(guān)聯(lián)規(guī)則 : Aquan1 ? Aquan2 ? Acat ? 示例 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 94 Mining Distancebased Association Rules ? Binning methods do not capture the semantics of interval data ? Distancebased partitioning, more meaningful discretization considering: ? density/number of points in an interval ? “closeness” of points in an interval P ric e($ )Eq uiw idt h(w idt h $1 0)Eq uid ep t h(de pt h 2)D is t an c eba s ed7 [ 0 , 1 0 ] [ 7 , 2 0 ] [ 7 , 7 ]20 [ 1 1 , 2 0 ] [ 2 2 , 5 0 ] [ 2 0 , 2 2 ]22 [ 2 1 , 3 0 ] [ 5 1 , 5 3 ] [ 5 0 , 5 3 ]50 [ 3 1 , 4 0 ]51 [ 4 1 , 5 0 ]53 [ 5 1 , 6 0 ]2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 95 Interestingness Measure: Correlations (Lift) ? play basketball ? eat cereal [40%, %] is misleading ? The overall percentage of students eating cereal is 75% which is higher than %. ? play basketball ? not eat cereal [20%, %] is more accurate, although with lower support and confidence ? Measure of dependent/correlated events: lift Basketball Not basketball Sum (row) Cereal 2020 1750 3750 Not cereal 1000 250 1250 Sum(col.) 3000 2020 5000 )()()(, BPAPBAPc or rBA??2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 96 內(nèi)容提要 ? 引言 ? Apriori 算法 ? FPgrowth 算法 ? 并行關(guān)聯(lián)規(guī)則挖掘 ? 多維關(guān)聯(lián)規(guī)則挖掘 ? 相關(guān)規(guī)則 ? 關(guān)聯(lián)規(guī)則改進(jìn) ? 總結(jié) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 97 相關(guān)規(guī)則 (Correlation Rules) ? “ Beyond Market Baskets,” Brin et al. ? 假設(shè)執(zhí)行關(guān)聯(lián)規(guī)則挖掘 c c row t 20 5 25 t 70 5 75 col 90 10 100 tea = coffee 20% support 80% confidence but 90% of the people buy coffee anyway! 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 98 相關(guān)規(guī)則 ? 一種度量是計(jì)算相關(guān)性 ? 若兩個(gè)隨機(jī)變量 A 和 B 是統(tǒng)計(jì)獨(dú)立的 ? 對(duì) tea 和 coffee: 1)()( )( ?? BPAP BAP)()( )( ?? cPtP ctP2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 99 相關(guān)規(guī)則 ? 利用 ?2 統(tǒng)計(jì)檢驗(yàn)來(lái)測(cè)試獨(dú)立性 ? 設(shè) n為購(gòu)物籃的總數(shù) ? 設(shè) k為考慮的項(xiàng)的總數(shù) ? 設(shè) r 為一個(gè)包含項(xiàng) (ij, ij)的規(guī)則 ? 設(shè) O(r) 表示包含規(guī)則 r的購(gòu)物籃的數(shù)量 (即頻率 ) ? 對(duì)單個(gè)項(xiàng) ij,設(shè) E[ij] = O(ij) (反過(guò)來(lái)即為 n E[ij]) ? E[r] = n * E[r1]/n * … * E[rk] / n 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 100 相關(guān)規(guī)則 ? ?2 統(tǒng)計(jì)量定義為 ? Look up for significance value in a statistical textbook ? There are k1 degrees of freedom ? If test fails cannot reject independence, otherwise contigency table represents dependence. ????Rr rErErO][])[)(( 22?2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 101 示例 ? Back to tea and coffee ? E[t] = 25, E[t]=75, E[c]=90, E[c]=10 ? E[tc]=100 * 25/100 * 90 /100= ? O(tc) = 20 ? Contrib. to ?2 = (20 )2 / = ? Calculate for the rest to get ?2= ? Not significant at 95% level ( for k=2) ? Cannot reject independence assumption c c row t 20 5 25 t 70 5 75 col 90 10 100 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 102 興趣度（ Interest） ? If ?2 test shows significance, then want to find most interesting cell(s) in table ? I(r) = O(r)/E[r] ? Look for values far away from 1 ? I(tc) = 20/ = ? I(tc) = 5/ = 2 ? I(tc) = 70/ = ? I(tc) = 5/ = 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 103 ?2 統(tǒng)計(jì)量的性質(zhì) ? 上封閉性 (Upward closed) ? 若一個(gè) k項(xiàng)集是相關(guān)的 ,則其所有的超集也是相關(guān)的 . ? 尋找最小的相關(guān)的項(xiàng)集 ? 沒(méi)有子集是相關(guān)的 ? 能否將 apriori and ?2 統(tǒng)計(jì)量有效地結(jié)合 ? No generate and prune as in supportconfidence 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 104 其它度量 (Measures) ??l ( A ? B ) ? P ( A , B )P ( A ) P ( B )TID Items 1 。 return FALSE. 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 28 Apriori 算法 ? 如何生成候選項(xiàng)集 ? ? 步驟 1: 自連接 Lk ? 步驟 2: 剪枝 ? 如何計(jì)算候選項(xiàng)集的支持度 ? ? 候選項(xiàng)庥生成的示例 ? L3={ abc, abd, acd, ace, bcd } ? 自連接 : L3*L3 ? 由 abc 和 abd 連接得到 abcd ? 由 acd 和 ace 連接得到 acde ? 剪枝 : ? 因?yàn)?ade 丌在 L3中 acde 被剪除 ? C4={abcd} 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 29 如何生成候選項(xiàng)集 ? ? 假定 Lk1中的項(xiàng)以一定順序排列 ? 步驟 1: 自連接 Lk1 insert into Ck select , , … , , from Lk1 p, Lk1 q where =, … , =, ? 步驟 2: 剪枝 forall itemsets c in Ck do forall (k1)subsets s of c do if (s is not in Lk1) then delete c from Ck 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 30 如何計(jì)算候選項(xiàng)集的支持度 ? ? 為何候選項(xiàng)集的支持度的計(jì)算是一個(gè)問(wèn)題 ? ? 候選項(xiàng)集的總數(shù)可能是巨大的 ? 一個(gè)事務(wù)可能包含多個(gè)候選項(xiàng)集 ? 方法 : ? 候選項(xiàng)集被存儲(chǔ)在一個(gè)哈希樹(shù) ? 哈希樹(shù)的 葉子結(jié)點(diǎn) 包含一個(gè)項(xiàng)集和計(jì)數(shù)的列表 ? 內(nèi)部結(jié)點(diǎn) 包含一個(gè)哈希表 ? 子集函數(shù) : 找出包含在一個(gè)事務(wù)中的所有候選項(xiàng)集 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 31 頻繁模式挖掘的挑戰(zhàn) ? 挑戰(zhàn) ? 多次掃描事務(wù)數(shù)據(jù)庫(kù) ? 巨大數(shù)量的候選項(xiàng)集 ? 繁重的計(jì)算候選項(xiàng)集的支持度工作 ? 改進(jìn) Apriori: 大體的思路 ? 減少事務(wù)數(shù)據(jù)庫(kù)的掃描次數(shù) ? 縮減候選項(xiàng)集的數(shù)量 ? 使候選項(xiàng)集的支持度計(jì)算更加方便 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 32 AprioriTid算法 ? AprioriTid算法由 Apriori算法改進(jìn) ? 優(yōu)點(diǎn)：只和數(shù)據(jù)庫(kù)做一次交互，無(wú)須頻繁訪問(wèn)數(shù)據(jù)庫(kù) ? 將 Apirori中的 Ck 擴(kuò)展，內(nèi)容由 {c}變?yōu)?{TID， c}，TID用于唯一標(biāo)識(shí)事務(wù) ? 引入 Bk ， 使得 Bk 對(duì)于事務(wù)的項(xiàng)目組織集合，而不是被動(dòng)的等待 Ck 來(lái)匹配 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 33 AprioriTid算法 ? 舉例： minsupp = 2 ? 數(shù)據(jù)庫(kù)： TID 項(xiàng)目 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 34 AprioriTid算法 示例 TID 項(xiàng)目集 100 {1} {3} {4} 200 {2} {3} {5} 300 {1} {2} {3} {5} 400 {2} {5} 項(xiàng)集 支持度 {1} 2 {2} 3 {3} 3 {5} 3 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 35 ApioriTid算法示例