數(shù)據(jù)挖掘關聯(lián)規(guī)則

1、1關聯(lián)規(guī)則 Association Rules2內(nèi)容提要內(nèi)容提要 n引言引言nApriori Apriori 算法算法nFrequent-pattern tree Frequent-pattern tree 和和FP-growth FP-growth 算法算法n多維關聯(lián)規(guī)則挖掘多維關聯(lián)規(guī)則挖掘n相關規(guī)則相關規(guī)則n基于約束的關聯(lián)規(guī)則挖掘基于約束的關聯(lián)規(guī)則挖掘n總結總結3 關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則挖掘n在事務數(shù)據(jù)庫,關系數(shù)據(jù)庫和其它信息庫中的項或對象的集合之間,發(fā)現(xiàn)頻繁模式,關聯(lián),相關,或因果關系的結構.n頻繁模式: 數(shù)據(jù)庫中出現(xiàn)頻繁的模式(項集,序列,等等)4基本概念基本概念n項集項集n事務事務n關

2、聯(lián)規(guī)則關聯(lián)規(guī)則n事務數(shù)據(jù)集事務數(shù)據(jù)集 ( (例如右圖例如右圖) )n事務標識事務標識 TIDTID： 每一個事務關聯(lián)著一個標識每一個事務關聯(lián)著一個標識IT ,.,21miiiI BAIBIABA,D5基本概念基本概念n支持度支持度s snD D中包含中包含A A和和 B B 的事務數(shù)與總的事務數(shù)的比的事務數(shù)與總的事務數(shù)的比值值規(guī)則規(guī)則 A AB B 在數(shù)據(jù)集在數(shù)據(jù)集D D中的支持度為中的支持度為s, s, 其中其中s s 表表示示D D中包含中包含A A B B ( (即同時包含即同時包含A A和和B)B)的事務的百的事務的百分率分率. .|)(DTBADTBAs6基本概念基本概念n支持度支持

3、度s snD D中包含中包含A A和和 B B 的事務數(shù)與總的事務數(shù)的比的事務數(shù)與總的事務數(shù)的比值值規(guī)則規(guī)則 A AB B 在數(shù)據(jù)集在數(shù)據(jù)集D D中的支持度為中的支持度為s, s, 其中其中s s 表表示示D D中包含中包含A A B B ( (即同時包含即同時包含A A和和B)B)的事務的百的事務的百分率分率. .|)(DTBADTBAs7基本概念基本概念n可信度可信度 c cnD D中同時包含中同時包含A A和和B B的事務數(shù)與只包含的事務數(shù)與只包含A A的事務的事務數(shù)的比值數(shù)的比值|)(TADTTBADTBAc規(guī)則規(guī)則 A AB B 在數(shù)據(jù)集在數(shù)據(jù)集D D中的中的可信可信度為度為c,c,

4、 其中其中c c表示表示D D中包含中包含A A的事務中也包含的事務中也包含B B的百分率的百分率. .即可用條件概率即可用條件概率P(B|A)P(B|A)表示表示. . confidence( confidence(A A B )=P(B|A)B )=P(B|A) 條件概率條件概率 P(B|A) P(B|A) 表示表示A A發(fā)生的條件下發(fā)生的條件下B B也發(fā)生也發(fā)生的概率的概率. .8關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則挖掘n兩個基本步驟兩個基本步驟nStep one:Step one:找出所有的頻繁項集找出所有的頻繁項集n滿足最小支持度滿足最小支持度nStep two:Step two:找出所有的強關聯(lián)規(guī)

5、則找出所有的強關聯(lián)規(guī)則n由頻繁項集生成關聯(lián)規(guī)則由頻繁項集生成關聯(lián)規(guī)則n保留滿足最小可信度的規(guī)則保留滿足最小可信度的規(guī)則9Apriori Apriori 性質性質n定理定理(Apriori (Apriori 性質性質): ): 若若A A是一個頻繁項集是一個頻繁項集, ,則則A A的的每一個子集都是一個頻繁項集每一個子集都是一個頻繁項集. .n證明證明: :設設n n為事務數(shù)為事務數(shù). .假設假設A A是是l l個事務的子集個事務的子集, ,若若 A A A A , , 則則A A 為為l l (l (l l ) l )個事務的子集個事務的子集. .因此因此, , l/n s(l/n s(最小支

6、持度最小支持度), l), l/n s/n s也成立也成立. .10Apriori Apriori 算法算法nAprioriApriori算法是一種經(jīng)典的生成布爾型關聯(lián)規(guī)則的頻算法是一種經(jīng)典的生成布爾型關聯(lián)規(guī)則的頻繁項集挖掘算法繁項集挖掘算法. .算法名字是緣于算法使用了頻繁項算法名字是緣于算法使用了頻繁項集的性質這一先驗知識集的性質這一先驗知識. .n思想思想: Apriori : Apriori 使用了一種稱作使用了一種稱作level-wiselevel-wise搜索的搜索的迭代方法迭代方法, ,其中其中k-k-項集被用作尋找項集被用作尋找(k+1)-(k+1)-項集項集. .首先首先,

7、,找出頻繁找出頻繁1-1-項集項集, ,以以L1L1表示表示.L1.L1用來尋找用來尋找L2,L2,即即頻繁頻繁2-2-項集的集合項集的集合.L2.L2用來尋找用來尋找L3,L3,以此類推以此類推, ,直至沒直至沒有新的頻繁有新的頻繁k-k-項集被發(fā)現(xiàn)項集被發(fā)現(xiàn). .每個每個LkLk都要求對數(shù)據(jù)庫作都要求對數(shù)據(jù)庫作一次完全掃描一次完全掃描.11生成頻繁項集生成頻繁項集n中心思想中心思想: : 由頻繁由頻繁(k-1)-(k-1)-項集構建候選項集構建候選k-k-項集項集n方法方法n找到所有的頻繁找到所有的頻繁1-1-項集項集n擴展頻繁擴展頻繁(k-1)-(k-1)-項集得到候選項集得到候選k-k

8、-項集項集n剪除不滿足最小支持度的候選項集剪除不滿足最小支持度的候選項集12Apriori: Apriori: 一種候選項集生成一種候選項集生成- -測試方法測試方法nApriori Apriori 剪枝原理剪枝原理: : 若任一項集是不頻繁的若任一項集是不頻繁的, ,則其超則其超集不應該被生成集不應該被生成/ /測試測試! !n方法方法: : n由頻繁由頻繁k-k-項集生成候選項集生成候選(k+1)-(k+1)-項集項集, ,并且并且n在在DBDB中測試候選項集中測試候選項集n性能研究顯示了性能研究顯示了AprioriApriori算法是有效的和可伸縮算法是有效的和可伸縮(scalablil

9、ity)(scalablility)的的. .13The Apriori The Apriori 算法算法一個示例一個示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scan14頻繁模式挖掘的挑戰(zhàn)頻繁模式挖掘的挑戰(zhàn)n挑戰(zhàn)n多次掃描事務數(shù)據(jù)庫n巨大數(shù)量的候選項集n繁重的計算候選項集的支持度工作n改進 Apriori: 大體的思路n減少事務數(shù)據(jù)庫的掃描次數(shù)n縮減候選項集的數(shù)量n使候選項集的支持度計算更加方便15內(nèi)容提要內(nèi)容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多維關聯(lián)規(guī)則挖掘n相關

10、規(guī)則n基于約束的關聯(lián)規(guī)則挖掘n總結16頻繁模式挖掘的瓶頸n多次掃描數(shù)據(jù)庫是高代價的n長模式的挖掘需要多次掃描數(shù)據(jù)庫以及生成許多的候選項集n找出頻繁項集 i1i2i100n掃描次數(shù): 100n候選項集的數(shù)量: (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 !n瓶頸:候選項集-生成-測試n我們能否避免生成候選項集?17不生成候選項集的頻繁模式挖掘n利用局部頻繁的項由短模式增長為長模式n“abc” 是一個頻繁模式n得到所有包含 “abc”的事務: DB|abcn“d” 是 DB|abc 的一個局部頻繁的項 abcd 是一個頻繁模式18FP Gro

11、wth算法 (Han, Pei, Yin 2000)nApriori算法的一個有問題的方面是其候選項集的生成n指數(shù)級增長的來源n另一種方法是使用分而治之的策略(divide and conquer)n思想思想: : 將數(shù)據(jù)庫的信息壓縮成一個描述頻繁項相關信息的頻繁模式樹19利用FP-樹進行頻繁模式挖掘n思想: 頻繁模式增長n遞歸地增長頻繁模式借助模式和數(shù)據(jù)庫劃分n方法 n對每個頻繁項,構建它的條件模式基,然后構建它的條件FP-樹.n對每個新創(chuàng)建的條件FP-樹重復上述過程n直至結果FP-樹為空,或者它僅包含一個單一路徑.該路徑將生成其所有的子路徑的組合,每個組合都是一個頻繁模式.20頻繁 1-項

12、集n最小支持度為20% (計數(shù)為 2) 事務數(shù)據(jù)庫 支持度計數(shù) 頻繁1-項集21FP-樹 構建按支持度降序排列22FP-樹 構建 創(chuàng)建根結點null 掃描數(shù)據(jù)庫 事務1: I1, I2, I5 排序: I2, I1, I5 處理事務 以項的順序增加結點 標注項及其計數(shù)(I2,1)(I1,1)(I5,1)1I50I40I31I11I2 維護索引表23FP-樹 構建null(I2,2)(I1,1)(I5,1)0I51I40I30I12I2(I4,1)24FP-樹 構建null(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)(I3,2)(I3,2)(I1,2)(I3,2

13、)(I4,1)(I5,1)25FP-樹 構建n掃描事務數(shù)據(jù)庫D一次,得到頻繁項的集合F及它們的支持度.將F按支持度降序排列成L,L是頻繁項的列表.n創(chuàng)建FP-樹的根, 標注其為NULL.對D中的每個事務進行以下操作:n根據(jù) L中的次序對事務中的頻繁項進行選擇和排序. 設事務中的已排序的頻繁項列表為p|P,其中p表示第一個元素,P表示剩余的列表.調用insert_Tree(p|P,T).26挖掘 FP-treen從索引表中的最后一個項開始n找到所有包含該項的路徑n沿著結點-鏈接(node-links)n確定條件模式n路徑中符合頻度要求的模式n構建 FP-tree Cn添加項至C中所有路徑,生成頻

14、繁模式n遞歸地挖掘C (添加項)n從索引表和樹中移除項27挖掘 FP-Treenull(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)(I3,2)(I3,2)(I4,1)(I5,1)(I1,2)(I3,2) 前綴路徑(I2 I1,1)(I2 I1 I3, 1)條件路徑(I2 I1, 2) 條件 FP-tree (I2 I1 I5, 2), (I2 I5, 2), (I1 I5, 2)null(I2,2)(I1,2)28挖掘 FP-Tree29由事務數(shù)據(jù)庫構建FP-樹f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem

15、frequency head f4c4a3b3m3p3min_support = 3TIDItems bought (ordered) frequent items100f, a, c, d, g, i, m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, o, wf, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, p掃描DB一次,找到頻繁1項 (單一項模式)按支持度降序對頻繁項排序為 F-list再次掃描DB,構建FP-treeF

16、-list=f-c-a-b-m-p30劃分模式和數(shù)據(jù)庫n頻繁模式根據(jù)F-list可以被劃分為若干子集nF-list=f-c-a-b-m-pn包含 p的模式n包含 m 但包含 p的模式nn包含 c 但不包含 a ,b, m, p的模式n模式 fn完整性 和 非冗余性31從P的條件數(shù)據(jù)庫找出包含P的模式n從 FP-tree的索引表的頻繁項開始n沿著每個頻繁項p的鏈接遍歷 FP-treen累積項p的所有轉換前綴路徑來形成的p的條件模式基條件模式基條件模式基項項 條件模式基條件模式基cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:

17、1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p332遞歸: 挖掘每個條件FP-treef:3c:3a:3m-條件條件 FP-tree“am”的條件模式基: (fc:3)f:3c:3am-條件條件 FP-tree“cm”的條件模式基: (f:3)f:3cm-條件條件 FP-tree“cam”的條件模式基: (f:3)f:3cam-條件條件 FP-tree33一個特例: FP-tree中的單一前綴路徑n假定 (條件的) FP-tree T 有一個共享的單一前綴路徑 Pn挖掘可以分為兩部分n將單一前綴路徑約簡為

18、一個結點n將兩部分的挖掘結果串聯(lián)a2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=34通過 DB 投影(Projection)使FP-growth可伸縮nFP-tree 不能全放入內(nèi)存?DB 投影n首先將一個數(shù)據(jù)庫劃分成一個由若干投影(Projected)數(shù)據(jù)庫組成的集合n然后對每個投影數(shù)據(jù)庫構建和挖掘 FP-treenParallel projection vs. Partition projection 技術nParallel projection is space costly35Par

19、tition-based ProjectionnParallel projection 需要很多磁盤空間nPartition projection 節(jié)省磁盤空間Tran. DB fcampfcabmfbcbpfcampp-proj DB fcamcbfcamm-proj DB fcabfcafcab-proj DB fcba-proj DBfcc-proj DBff-proj DB am-proj DB fcfcfccm-proj DB fff36改進途徑n使用哈希表存儲候選k-項集的支持度計數(shù)n移除不包含頻繁項集的事務n對數(shù)據(jù)采樣n劃分數(shù)據(jù)n若一個項集是頻繁的,則它必定在某個數(shù)據(jù)分區(qū)中是頻繁

20、的.37FP-tree 結構的優(yōu)點n完整性 n保持了頻繁項集挖掘的完整信息n沒有打斷任何事務的長模式n緊密性n減少不相關的信息不頻繁的項沒有了n項按支持度降序排列: 越頻繁出現(xiàn),越可能被共享n決不會比原數(shù)據(jù)庫更大 (不計結點鏈接和計數(shù)域)n對 Connect-4 數(shù)據(jù)庫, 壓縮比率可以超過10038內(nèi)容提要內(nèi)容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多維關聯(lián)規(guī)則挖掘n相關規(guī)則n基于約束的關聯(lián)規(guī)則挖掘n總結39挖掘多種規(guī)則或規(guī)律n多層(Multi-level),量化(quantitative)關聯(lián)規(guī)則, 相關(correlati

21、on)和因果(causality), 比率(ratio)規(guī)則, 序列 (sequential) 模式,浮現(xiàn)(emerging)模式, temporal associations, 局部周期(partial periodicity)n分類(classification),聚類(clustering),冰山立方體( iceberg cubes), 等等.40多層關聯(lián)規(guī)則n項常常構成層次n可伸縮的(flexible)支持度設置: 在較低層的項預期有較低的支持度.n事務數(shù)據(jù)庫可以基于維度和層次編碼n探尋共享多層挖掘統(tǒng)一支持度Milksupport = 10%2% Milk support = 6%Sk

22、im Milk support = 4%Level 1min_sup = 5%Level 2min_sup = 5%Level 1min_sup = 5%Level 2min_sup = 3%減少的支持度41可伸縮的支持度約束的多層/多維(ML/MD)關聯(lián)規(guī)則n為什么設置可伸縮的支持度?n實際生活中項的出現(xiàn)頻率變化巨大n在一個商店購物籃中的鉆石,手表,鋼筆n統(tǒng)一的支持度未必是一個有趣的模型n一個可伸縮模型n較低層的,較多維的組合以及長模式通常具有較小的支持度n總體規(guī)則應該要容易說明和理解n特殊的項和特殊的項的組合可以特別設定(最小支持度)以及擁有更高的優(yōu)先級42多維關聯(lián)規(guī)則n單維規(guī)則:buys

23、(X, “milk”) buys(X, “bread”)n多維規(guī)則: 2 個維度或謂詞( predicates)n跨維度(Inter-dimension)關聯(lián)規(guī)則 (無重復謂詞)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)n混合維度(hybrid-dimension)關聯(lián)規(guī)則 (重復謂詞)age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)n分類(Categorical)屬性n有限的幾個可能值,值之間不可排序n數(shù)量(Quantitative)屬性n數(shù)值的,值之間有固有的排序43多層關聯(lián)規(guī)

24、則:冗余濾除n根據(jù)項之間的”先輩” (ancestor)關系,一些規(guī)則可能是冗余的. n示例nmilk wheat bread support = 8%, confidence = 70%n2% milk wheat bread support = 2%, confidence = 72%n我們說第1個規(guī)則是第2個規(guī)則的先輩.n一個規(guī)則是冗余的,當其支持度接近基于先輩規(guī)則的”預期”(expected)值.44多層關聯(lián)規(guī)則:逐步深化(Progressive Deepening)n一個自上而下的,逐步深化的方法:n 首先挖掘高層的頻繁項: milk (15%), bread (10%)n 然后挖掘

25、它們的較低層”較弱” (weaker)頻繁項: 2% milk (5%), wheat bread (4%)n多層之間不同的最小支持度閾值導致了不同的算法:n如果在多個層次間采用了相同的最小支持度,若t的任何一個先輩都是非頻繁的則扔棄(toss)t.n如果在較低層采用了減少的最小支持度，則只檢驗那些先輩的支持度是頻繁的不可忽略的派生（descendents）即可45多維關聯(lián)規(guī)則挖掘的技術n搜索頻繁 k-謂詞集(predicate set):n示例: age, occupation, buys是一個 3-謂詞集n以age處理的方式,技術可以如下分類1. 利用數(shù)量屬性的統(tǒng)計離散(static di

26、scretization)方法 利用預先確定的概念層次對數(shù)量屬性進行統(tǒng)計離散化2. 量化關聯(lián)規(guī)則n基于數(shù)據(jù)的分布,數(shù)量屬性被動態(tài)地離散化到不同的容器空間(bins)3. 基于距離(Distance-based)的關聯(lián)規(guī)則n這是一個動態(tài)離散化的過程,該過程考慮數(shù)據(jù)點之間的距離46數(shù)量屬性的統(tǒng)計離散化n挖掘之前利用概念層次離散化n數(shù)值被范圍(ranges)替代.n關系數(shù)據(jù)庫中,找出所有的頻繁k-謂詞(predicate)集要求 k 或 k+1次表掃描.n數(shù)據(jù)立方體(data cube)非常適合數(shù)據(jù)挖掘.nN-維立方體的 cells 與謂詞集( predicate sets)相對應.n通過數(shù)據(jù)立方體

27、挖掘會非常快速.(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)47量化關聯(lián)規(guī)則age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high resolution TV”)n數(shù)值屬性動態(tài)離散化n這樣挖掘的規(guī)則的可信度或緊密度最大化n2-維 量化關聯(lián)規(guī)則: Aquan1 Aquan2 Acatn示例48量化關聯(lián)規(guī)則nARCS: Association Rule Clustering System (關聯(lián)規(guī)則聚類系統(tǒng)) 借鑒了圖像處理中的思想. 本質上, 這種

28、方法映射一對數(shù)量屬性到滿足給定的分類屬性條件的2-維元組格. 然后對柵格搜索找到聚類點,由其生成關聯(lián)規(guī)則. nARCS 步驟: 裝箱(Binning)找出頻繁謂詞集(predicate sets) 聚類關聯(lián)規(guī)則 49量化關聯(lián)規(guī)則n裝箱(Binning): 劃分 過程被認為是裝箱,即稱作間隔為箱柜(bins). 三種常用裝箱策略是: Equiwidth binning, where the intervalsize of each bin is the same Equidepth: where each bin has approximately the same number of tupl

29、es assigned to it Homogeneity-based binning, where bin size is determined so that the tuples in each bin are uniformly distributed.50量化關聯(lián)規(guī)則n找出頻繁謂詞集: Once the 2-D array containing the count distribution for each category is set up, this can be scanned in order to find the frequent predicate sets that

30、 also satisfy minimum confidence.n聚類關聯(lián)規(guī)則: age(X,”34-35”) income(X,”31K - 50K”) buys(X,”high resolution TV”)51ARCS (Association Rules Clustering System)ARCS 1. Binning2. Frequent Items Set3. Clustering4. Optimization52nARCS: n成功的應用聚類的概念到分類中. n但僅限于基于2-維規(guī)則的分類,如A B Classi 的格式所示n利用裝箱(Binning)方法將數(shù)據(jù)屬性值離散化,

31、因此ACRS的準確度與使用的離散化程度強烈相關. 53內(nèi)容提要內(nèi)容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多維關聯(lián)規(guī)則挖掘n相關規(guī)則n基于約束的關聯(lián)規(guī)則挖掘n總結54相關規(guī)則(Correlation Rules)n“Beyond Market Baskets,” Brin et al.n假設執(zhí)行關聯(lián)規(guī)則挖掘tea = coffee20% support80% confidencebut 90% of the people buy coffee anyway!55相關規(guī)則n一種度量是計算相關性n若兩個隨機變量 A 和 B 是統(tǒng)計

32、獨立的n對tea 和 coffee:1)()()(BPAPBAP89.0)()()(cPtPctP56相關規(guī)則n利用 2 統(tǒng)計檢驗來測試獨立性n設n為購物籃的總數(shù)n設k為考慮的項的總數(shù)n設 r 為一個包含項 (ij, ij)的規(guī)則n設O(r) 表示包含規(guī)則r的購物籃的數(shù)量 (即頻率)n對單個項ij,設 Eij = O(ij) (反過來即為 n - Eij)nEr = n * Er1/n * * Erk / n57相關規(guī)則n2 統(tǒng)計量定義為nLook up for significance value in a statistical textbooknThere are k-1 degrees of freedomnIf test fails cannot reject independence, otherwise contigency table represents dependence.RrrErErO)(2258示例nBack to tea and coffeenEt = 25, Et=75, Ec=90, Ec=10nEtc=100 * 25/100 * 90 /100=22.5nO(tc) = 20nContrib. to 2 = (20 - 22.5)2 / 22.5 = 0.278nCalculate for the rest to get 2=2.204nN