頻繁模式挖掘與關(guān)聯(lián)規(guī)則挖掘

1、2022-3-31數(shù) 據(jù) 挖 掘1數(shù) 據(jù) 挖 掘第六章 挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則孫玉芬武漢理工大學計算機科學與技術(shù)學院計算機科學系2022-3-31數(shù) 據(jù) 挖 掘2挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則n 6.1 關(guān)聯(lián)規(guī)則挖掘n 6.2 由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則n 6.3 由事務數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則n 6.4 由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則n 6.5 由關(guān)聯(lián)挖掘到相關(guān)分析n 6.6 基于約束的關(guān)聯(lián)挖掘n 6.7 小結(jié)2022-3-31數(shù) 據(jù) 挖 掘36.1 關(guān)聯(lián)規(guī)則挖掘n由Agrawal，Imielinski，與Swami AIS93首次提出頻繁項集（frequent itemsets

2、）與關(guān)聯(lián)規(guī)則挖掘（association rule mining）n動機：找出數(shù)據(jù)中存在的規(guī)則 A Bn哪些產(chǎn)品總是被同時購買？啤酒與尿布？！n顧客購買PC后，還會購買哪些商品？n哪種DNA會對某種新藥敏感？n先挖掘頻繁模式，然后挖掘關(guān)聯(lián)規(guī)則n頻繁模式：在一個數(shù)據(jù)集中頻繁出現(xiàn)的模式 （數(shù)據(jù)項集，子序列，子結(jié)構(gòu)，等）2022-3-31數(shù) 據(jù) 挖 掘4基本概念：頻繁模式與關(guān)聯(lián)規(guī)則n項集 X = x1, , xkn找出所有置信度與支持度超過閾值的規(guī)則 X Yn支持度（support），s，包含X Y的事務出現(xiàn)的概率n置信度（confidence），c，事務包含X時，也包含Y的條件概率置supmin

3、= 50%， confmin = 50%頻繁模式： A:3, B:3, D:4, E:3, AD:3關(guān)聯(lián)規(guī)則：A D (60%, 100%)D A (60%, 75%)購買尿布的購買尿布的顧客顧客兩樣都買兩樣都買的顧客的顧客購買啤酒的顧客購買啤酒的顧客事務號事務號購買的項購買的項10A, B, D20A, C, D30A, D, E40B, E, F50B, C, D, E, F2022-3-31數(shù) 據(jù) 挖 掘5為什么頻繁模式挖掘是重要的？n能發(fā)現(xiàn)數(shù)據(jù)集中內(nèi)在的特性n是許多重要的數(shù)據(jù)挖掘任務的基礎(chǔ)n關(guān)聯(lián)分析，相關(guān)分析，與因果分析n序列模式，結(jié)構(gòu)模式（如：子圖）n時空數(shù)據(jù)、多媒體數(shù)據(jù)、時序數(shù)據(jù)、

4、流數(shù)據(jù)中的模式分析n分類：關(guān)聯(lián)分類n聚類：基于頻繁模式的聚類n數(shù)據(jù)倉庫：冰山數(shù)據(jù)立方 n語義數(shù)據(jù)壓縮n廣泛的應用n購物籃數(shù)據(jù)分析，Web點擊流分析，打折銷售分析，DNA序列分析2022-3-31數(shù) 據(jù) 挖 掘6關(guān)聯(lián)規(guī)則的分類n布爾關(guān)聯(lián)規(guī)則與量化關(guān)聯(lián)規(guī)則n計算機 財務管理軟件n年齡（X，”3039”） 收入（X，”42k48k”） 購買（X，”高清晰電視”）n單維關(guān)聯(lián)規(guī)則與多維關(guān)聯(lián)規(guī)則n單層關(guān)聯(lián)規(guī)則與多層關(guān)聯(lián)規(guī)則n年齡（X， ”3039” ） 購買（X，”筆記本”）n年齡（X， ”3039” ） 購買（X，”計算機”）n閉模式與最大模式2022-3-31數(shù) 據(jù) 挖 掘7閉模式與最大模式n一個長模

5、式包含大量子模式。例如：a1, , a100 包含 C1001 + C1002 + + C110000 = 2100 1 = 1.27*1030子模式！n解決方法：挖掘閉模式（ closed patterns ）與最大模式（ max-patterns）n一個項集X是閉模式，如果X是頻繁的，且不存在超模式 Y ? X具有與X同樣的支持度（Pasquier，ICDT99）n一個項集X是一個最大模式，如果X是頻繁的，并且不存在頻繁超模式 Y ? X （Bayardo，SIGMOD98）n閉模式是頻繁模式集的無損壓縮n壓縮了模式與規(guī)則的數(shù)目2022-3-31數(shù) 據(jù) 挖 掘8閉模式與最大模式n例子：DB

6、 = , n最小支持度 = 1n有哪些閉模式?n: 1n: 2n有哪些最大模式？n: 1n所有模式n!2022-3-31數(shù) 據(jù) 挖 掘9挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則n 6.1 關(guān)聯(lián)規(guī)則挖掘n 6.2 由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則n 6.3 由事務數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則n 6.4 由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則n 6.5 由關(guān)聯(lián)挖掘到相關(guān)分析n 6.6 基于約束的關(guān)聯(lián)挖掘n 6.7 小結(jié)2022-3-31數(shù) 據(jù) 挖 掘106.2 由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則n挖掘最簡單形式的關(guān)聯(lián)規(guī)則：n單維n單層n布爾n兩個主要方法nApriori（Agrawal & SrikantVLD

7、B94）n頻繁模式增長方法（FPgrowthHan, Pei & Yin SIGMOD00）2022-3-31數(shù) 據(jù) 挖 掘116.2.1 Apriori：一個基于候選集的方法nApriori性質(zhì)：n一個頻繁項集的所有非空子集都必定是頻繁的n如果 啤酒，尿布，堅果 是頻繁的，則 啤酒，尿布必定是頻繁的n每個包含 啤酒，尿布，堅果 的事務，必定包含 啤酒，尿布 n反單調(diào)nApriori 修剪原則: 如果某個項集是不頻繁的，則它的超集不需要被考慮2022-3-31數(shù) 據(jù) 挖 掘12Apriori 方法n逐層搜索：由 K項集到 k+1候選項集n方法：n掃描數(shù)據(jù)集一次，得到所有長度為1的頻繁項

8、集n基于長度為 K 的頻繁項集，生成長度為 k+1 的候選項集n掃描數(shù)據(jù)集，檢測候選項集是否頻繁n當沒有頻繁項集或候選項集生成時，中止算法。2022-3-31數(shù) 據(jù) 挖 掘13例子：Apriori 算法 事務數(shù)據(jù)庫第一遍掃描C1L1L2C2C2第二遍掃描C3L3第三遍掃描事務號事務號項項10A, C, D20B, C, E30A, B, C, E40B, E項集項集SA2B3C3D1E3項集項集SA2B3C3E3項集項集A, BA, CA, EB, CB, EC, E項集項集SA, B1A, C2A, E1B, C2B, E3C, E2項集項集SA, C2B, C2B, E3C, E2項集項集

9、B, C, E項集項集SB, C, E2Smin = 22022-3-31數(shù) 據(jù) 挖 掘14Apriori 算法n偽碼：Ck ：長度為 k 的候選項集Lk ： 長度為 k 的頻繁項集L1 = 頻繁項;for (k = 1; Lk !=; k+) do begin Ck+1 = 由 Lk 生成的候選項集； 對對數(shù)據(jù)庫中的每個事務 t do 將 Ck+1 中所有在 t 中出現(xiàn)的候選項集的計數(shù)分別加 1 Lk+1 = Ck+1 中所有計數(shù)超過支持度閾值的候選項集 endreturn k Lk;2022-3-31數(shù) 據(jù) 挖 掘15Apriori 中的重要細節(jié)n如何生成候選項集？n第一步：self-jo

10、ining Lkn第二步：修剪n生成候選項集的例子nL3=abc, abd, acd, ace, bcdnSelf-joining: L3*L3n由 abc 與 abd 得到 abcdn由 acd 與 ace 得到 acden修剪：n由于 ade 不在 L3 中，acde 被刪除nC4=abcd2022-3-31數(shù) 據(jù) 挖 掘16如何生成候選項集？n假設(shè) Lk-1 中的項按某個次序排列n第一步：self-joining Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhe

11、re p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 = 3n產(chǎn)生候選 select P.cust_ID select P.item_ID from Purchases P from Purchases P group by P.cust_ID group by P.item_ID having SUM(P.qty) = 3 having SUM(P.qty) = 32022-3-31數(shù) 據(jù) 挖 掘36挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則n6.1 關(guān)聯(lián)規(guī)則挖掘n6.2 由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則n6.3 由事務數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則n6.4 由關(guān)

12、系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則n6.5 由關(guān)聯(lián)挖掘到相關(guān)分析n6.6 基于約束的關(guān)聯(lián)挖掘n6.7 小結(jié)2022-3-31數(shù) 據(jù) 挖 掘376.3.1 多層關(guān)聯(lián)規(guī)則n數(shù)據(jù)庫中的項經(jīng)常形成層次關(guān)系n多層關(guān)聯(lián)規(guī)則：由具有概念分層的關(guān)聯(lián)規(guī)則挖掘產(chǎn)生的規(guī)則n為什么要挖掘多層關(guān)聯(lián)規(guī)則n在低層/原始層的數(shù)據(jù)項之間很難找出強關(guān)聯(lián)規(guī)則n用戶的需求n例子：2022-3-31數(shù) 據(jù) 挖 掘386.3.2 挖掘多層關(guān)聯(lián)規(guī)則的方法n通常采用自頂向下的策略n對于所有層使用一致的最小支持度n遞減的支持度閾值設(shè)置 n較低層次的項通常具有較低的支持度統(tǒng)一的支持度閾值computer支持度支持度 = 10%laptop 支持

13、度支持度 = 6%desktop 支持度支持度 = 4%層層 1支持度閾值 = 5%層層 2支持度閾值= 5%層層 1支持度閾值 = 5%層層 2支持度閾值= 3%不統(tǒng)一的支持度閾值2022-3-31數(shù) 據(jù) 挖 掘39頻繁項集搜索策略n逐層獨立n沒有剪枝n層交叉單項過濾n一個第 i 層的項被考察，當且僅當它在第（i-1）層的父節(jié)點是頻繁的computer支持度支持度 = 10%laptop （未考察）未考察）desktop （未考察）未考察）層層 1支持度閾值 = 12%層層 2支持度閾值= 3%2022-3-31數(shù) 據(jù) 挖 掘40頻繁項集搜索策略n層交叉 k-項集過濾n一個第 i 層的 k-

14、項集被考察，當且僅當它在第（i-1）層的對應父節(jié)點 k-項集是頻繁的Computer and printer支持度支持度 = 7%Laptop computer and b/w printer 支持度支持度 = 1%Desktop computer and b/w printer 支持度支持度 = 1%層層 1支持度閾值 = 5%層層 2支持度閾值= 2%Laptop computer and color printer 支持度支持度 = 2%Desktop computer and b/w printer 支持度支持度 = 3%2022-3-31數(shù) 據(jù) 挖 掘41頻繁項集搜索策略n受控的層交

15、叉單項過濾策略n層傳遞閾值n下一層的最小支持度閾值與當前層的最小支持度閾值之間的值computer支持度支持度 = 10%laptop 支持度支持度 = 6%desktop 支持度支持度 = 4%層層 1支持度閾值 = 12%層傳遞閾值 = 8% 層層 2支持度閾值= 3%2022-3-31數(shù) 據(jù) 挖 掘426.3.3 檢查冗余的多層關(guān)聯(lián)規(guī)則n由于項之間的層次關(guān)系，一些規(guī)則之間可能存在冗余n例子nDesktop computer b/w printer 支持度 = 8%， 置信度 = 70%nIBM desktop computer b/w printer 支持度 = 2%， 置信度 = 72

16、%n我們稱第一個規(guī)則是第二個規(guī)則的祖先n若一個規(guī)則的支持度與基于其祖先規(guī)則推導出的期望的支持度相似，則稱這個規(guī)則是冗余的2022-3-31數(shù) 據(jù) 挖 掘43挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則n6.1 關(guān)聯(lián)規(guī)則挖掘n6.2 由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則n6.3 由事務數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則n6.4 由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則n6.5 由關(guān)聯(lián)挖掘到相關(guān)分析n6.6 基于約束的關(guān)聯(lián)挖掘n6.7 小結(jié)2022-3-31數(shù) 據(jù) 挖 掘446.4.1 多維關(guān)聯(lián)規(guī)則n單維規(guī)則：購買（X，”desktop computer”） 購買（X，”b/w printer”）n多維關(guān)聯(lián)規(guī)則: 2 維或謂詞n維間

17、關(guān)聯(lián)規(guī)則（沒有重復的謂詞）年齡（X，”19-25”） 職業(yè)（X，“學生”） 購買（X， “可樂”）n混合維關(guān)聯(lián)規(guī)則（有重復出現(xiàn)的謂詞）年齡（X，”19-25”） 購買（X，”爆米花”） 購買（X，”可樂”）n單維關(guān)聯(lián)規(guī)則挖掘：搜索頻繁項集n多維關(guān)聯(lián)規(guī)則挖掘：搜索頻繁謂詞集n分類屬性：具有有限數(shù)目的可能取值，值之間無次序關(guān)系n量化屬性：數(shù)值型數(shù)據(jù)，值之間存在次序關(guān)系2022-3-31數(shù) 據(jù) 挖 掘45對量化屬性的處理1. 使用預定義的概念分層將量化屬性離散化（靜態(tài)離散化）2. 根據(jù)數(shù)據(jù)的分布，將量化屬性離散化到“箱”（動態(tài)離散化）3. 基于數(shù)據(jù)點之間的距離將量化屬性離散化（使用聚類方法）2022

18、-3-31數(shù) 據(jù) 挖 掘466.4.2 使用量化屬性的靜態(tài)離散化挖掘多維關(guān)聯(lián)規(guī)則n在挖掘前，使用概念層次將屬性離散化n數(shù)值型屬性的取值用取值區(qū)間表示n在關(guān)系數(shù)據(jù)庫中，找出所有 k-謂詞頻繁集需要 k 或 k+1次掃描n數(shù)據(jù)立方體適合于關(guān)聯(lián)規(guī)則挖掘nn-維立方體中的節(jié)點表示謂詞集 n在數(shù)據(jù)立方體上挖掘可以 減少挖掘所需時間(收入)(年齡)()(購買)(年齡，收入)(年齡，購買) (收入，購買)(年齡，收入，購買)2022-3-31數(shù) 據(jù) 挖 掘476.4.3 挖掘量化關(guān)聯(lián)規(guī)則n分箱：n等寬分箱n等深分箱n基于同質(zhì)的分箱n找頻繁謂詞集n關(guān)聯(lián)規(guī)則聚類2022-3-31數(shù) 據(jù) 挖 掘486.4.4 挖

19、掘基于距離的關(guān)聯(lián)規(guī)則n考慮數(shù)據(jù)點之間或區(qū)間之間的相對距離，緊扣區(qū)間數(shù)據(jù)的語義，并允許數(shù)據(jù)值的近似n兩遍算法：n使用聚類找出區(qū)間或簇n搜索頻繁地一起出現(xiàn)的簇的集合，得到基于距離的關(guān)聯(lián)規(guī)則2022-3-31數(shù) 據(jù) 挖 掘49挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則n6.1 關(guān)聯(lián)規(guī)則挖掘n6.2 由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則n6.3 由事務數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則n6.4 由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則n6.5 由關(guān)聯(lián)挖掘到相關(guān)分析n6.6 基于約束的關(guān)聯(lián)挖掘n6.7 小結(jié)2022-3-31數(shù) 據(jù) 挖 掘506.5.1 強關(guān)聯(lián)規(guī)則不一定是有趣的n打籃球 吃谷類食品 40%, 66.7% 產(chǎn)生誤導n在所有

20、學生中，有 75% 吃谷類食品，高于 66.7%。n打籃球 不吃谷類食品 20%, 33.3% 更為準確，盡管它的支持度與置信度都很低n規(guī)則 A B 的置信度有一定的欺騙性，它只給出了A，B的條件概率估計，并沒有度量A和B之間的相關(guān)性。2022-3-31數(shù) 據(jù) 挖 掘516.5.2 由關(guān)聯(lián)分析到相關(guān)分析n事件之間相關(guān)性的度量： corr打籃球不打籃球總和吃谷類食品200017503750不吃谷類食品10002501250總和300020005000()( |)( ) ( )( )ABP A BP B AcorrP A P BP B2022-3-31數(shù) 據(jù) 挖 掘52挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則n

21、6.1 關(guān)聯(lián)規(guī)則挖掘n6.2 由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則n6.3 由事務數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則n6.4 由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則n6.5 由關(guān)聯(lián)挖掘到相關(guān)分析n6.6 基于約束的關(guān)聯(lián)挖掘n6.7 小結(jié)2022-3-31數(shù) 據(jù) 挖 掘536.6 基于約束的關(guān)聯(lián)挖掘n自動找到數(shù)據(jù)庫中的所有模式 不現(xiàn)實！n模式數(shù)目可能非常大，但大部分是不需要的n數(shù)據(jù)挖掘應該是一個交互式過程n用戶使用數(shù)據(jù)挖掘查詢語言或圖形用戶界面指導挖掘過程n基于約束的挖掘n用戶：給出約束或指明需要挖掘什么n系統(tǒng)優(yōu)化：利用約束進行有效挖掘基于約束的挖掘2022-3-31數(shù) 據(jù) 挖 掘546.6 基于約束的關(guān)聯(lián)挖掘

22、n知識類型約束： n指定要挖掘的知識類型，如分類模型，關(guān)聯(lián)規(guī)則，等等n數(shù)據(jù)約束n指定與任務相關(guān)的數(shù)據(jù)集n維/層約束n指定所用的維或概念分層結(jié)構(gòu)中的層n規(guī)則約束n指定要挖掘的規(guī)則形式，如規(guī)則前件或后件中謂詞的個數(shù)n興趣度約束n指定規(guī)則興趣度閾值或統(tǒng)計度量，如支持度閾值與置信度閾值2022-3-31數(shù) 據(jù) 挖 掘556.6.1 關(guān)聯(lián)規(guī)則的元規(guī)則制導挖掘n元規(guī)則使得用戶可以說明他們感興趣的規(guī)則的語法形式n例子：n元規(guī)則：n與元規(guī)則匹配的規(guī)則：) ,(),(),(21softwareleducationaXbuysWXPYXP) ,()60.41 ,()39.30 ,(softwareleducati

23、onaXbuysKKXincomeXage2022-3-31數(shù) 據(jù) 挖 掘566.6.2 用附加的規(guī)則約束制導的挖掘n規(guī)則約束n反單調(diào)的n單調(diào)的n簡潔的n可轉(zhuǎn)變的n不可轉(zhuǎn)變的2022-3-31數(shù) 據(jù) 挖 掘57反單調(diào)約束n反單調(diào)性n若項集 S 不滿足約束，那么它的所有超集都不滿足約束n求和(S.價格) v 是反單調(diào)的n求和(S.價格) v 不是反單調(diào)的n例子：約束C：求和(S.價格) 15 是反單調(diào)的n項集 ab 不滿足 Cnab的任何超集也不滿足CTID事務事務10a, b, c, d, f20b, c, d, f, g, h30a, c, d, e, f40c, e, f, g事務數(shù)據(jù)庫

24、(min_sup=2)項項價格價格a40b10c20d10e30f30g20h102022-3-31數(shù) 據(jù) 挖 掘58單調(diào)約束n單調(diào)性n若項集 S 滿足約束，則它的任意超集都滿足約束n求和(S.價格) v 是單調(diào)的n最小(S.價格) v 是單調(diào)的n例子：約束C：求和(S.價格) 15n項集 ab 滿足 Cnab的所有超集都滿足CTID事務事務10a, b, c, d, f20b, c, d, f, g, h30a, c, d, e, f40c, e, f, g事務數(shù)據(jù)庫 (min_sup=2)項項價格價格a40b10c20d10e30f30g20h102022-3-31數(shù) 據(jù) 挖 掘59簡潔性

25、約束n簡潔性：n設(shè) A1 為滿足簡潔性約束C 的項的集合，則所有滿足 C 的集 S 都是基于A1的，即 S 必包含一個屬于 A1 的子集n可以直接精確地產(chǎn)生滿足簡潔性約束的項集集合 n最小(S.價格) v 是簡潔的n和(S.價格) v 不是簡潔的2022-3-31數(shù) 據(jù) 挖 掘60例子Apriori 算法TID項100 1 3 4200 2 3 5300 1 2 3 5400 2 5數(shù)據(jù)庫 D項集支持度計數(shù)1223334153項集 支持度計數(shù)12233353掃描 DC1L1項集1 21 31 52 32 53 5項集 支持度計數(shù)1 211 321 512 322 533 52項集 支持度計數(shù)1

26、 322 322 533 52L2C2C2掃描 DC3L3項集2 3 5掃描 D項集支持度計數(shù)2 3 522022-3-31數(shù) 據(jù) 挖 掘61Apriori + 約束 TID項100 1 3 4200 2 3 5300 1 2 3 5400 2 5數(shù)據(jù)庫 D項集 支持度計數(shù)1223334153項集支持度計數(shù)12233353掃描 DC1L1項集1 21 31 52 32 53 5項集支持度計數(shù)1 211 321 512 322 533 52項集支持度計數(shù)1 322 322 533 52L2C2C2掃描 DC3L3項集2 3 5掃描 D項集支持度計數(shù)2 3 52約束：約束：求和求和S.價格價格 52022-3-31數(shù) 據(jù) 挖 掘62基于約束的Apriori算法：集成反單調(diào)約束TID項100 1 3 4200 2 3 5300 1 2 3 5400 2 5數(shù)據(jù)庫 D項集 支持度計數(shù)1223334153項集 支持度計數(shù)12233353掃描 DC1L1項集