數據挖掘

第六章挖掘大型數據庫中的關聯規則孫玉芬yufen@武漢理工大學計算機科學與技術學院計算機科學系2023/2/11數據挖掘挖掘大型數據庫中的關聯規則6.1關聯規則挖掘6.2由事務數據庫挖掘單維布爾關聯規則6.3由事務數據庫挖掘多層關聯規則6.4由關系數據庫和數據倉庫挖掘多維關聯規則6.5由關聯挖掘到相關分析6.6基于約束的關聯挖掘6.7小結2023/2/12數據挖掘6.1關聯規則挖掘由Agrawal，Imielinski，與Swami[AIS93]首次提出頻繁項集（frequentitemsets）與關聯規則挖掘（associationrulemining）動機：找出數據中存在的規則AB哪些產品總是被同時購買？—啤酒與尿布？！顧客購買PC后，還會購買哪些商品？哪種DNA會對某種新藥敏感？先挖掘頻繁模式，然后挖掘關聯規則頻繁模式：在一個數據集中頻繁出現的模式（數據項集，子序列，子結構，等）2023/2/13數據挖掘基本概念：頻繁模式與關聯規則項集X={x1,…,xk}找出所有置信度與支持度超過閾值的規則

XY支持度（support），s，包含XY的事務出現的概率置信度（confidence），c，事務包含X時，也包含Y的條件概率置supmin=50%，confmin=50%頻繁模式：

{A:3,B:3,D:4,E:3,AD:3}關聯規則：AD(60%,100%)DA(60%,75%)購買尿布的顧客兩樣都買的顧客購買啤酒的顧客事務號購買的項10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F2023/2/14數據挖掘為什么頻繁模式挖掘是重要的？能發現數據集中內在的特性是許多重要的數據挖掘任務的基礎關聯分析，相關分析，與因果分析序列模式，結構模式（如：子圖）時空數據、多媒體數據、時序數據、流數據中的模式分析分類：關聯分類聚類：基于頻繁模式的聚類數據倉庫：冰山數據立方語義數據壓縮廣泛的應用購物籃數據分析，Web點擊流分析，打折銷售分析，DNA序列分析2023/2/15數據挖掘關聯規則的分類布爾關聯規則與量化關聯規則計算機

財務管理軟件年齡（X，”30…39”）收入（X，”42k…48k”）購買（X，”高清晰電視”）單維關聯規則與多維關聯規則單層關聯規則與多層關聯規則年齡（X，”30…39”）購買（X，”筆記本”）年齡（X，”30…39”）購買（X，”計算機”）閉模式與最大模式2023/2/16數據挖掘閉模式與最大模式一個長模式包含大量子模式。例如：{a1,…,a100}包含

C1001+C1002+…+C110000=2100–1=1.27*1030子模式！解決方法：挖掘閉模式（closedpatterns

）與最大模式（

max-patterns）一個項集X是閉模式，如果X是頻繁的，且不存在超模式Y?X具有與X同樣的支持度（Pasquier，ICDT’99）一個項集X是一個最大模式，如果X是頻繁的，并且不存在頻繁超模式Y?X（Bayardo，SIGMOD’98）閉模式是頻繁模式集的無損壓縮壓縮了模式與規則的數目2023/2/17數據挖掘閉模式與最大模式例子：DB={<a1,…,a100>,<a1,…,a50>}最小支持度=1有哪些閉模式?<a1,…,a100>:1<a1,…,a50>:2有哪些最大模式？<a1,…,a100>:1所有模式!!2023/2/18數據挖掘挖掘大型數據庫中的關聯規則6.1關聯規則挖掘6.2由事務數據庫挖掘單維布爾關聯規則6.3由事務數據庫挖掘多層關聯規則6.4由關系數據庫和數據倉庫挖掘多維關聯規則6.5由關聯挖掘到相關分析6.6基于約束的關聯挖掘6.7小結2023/2/19數據挖掘6.2由事務數據庫挖掘單維布爾關聯規則挖掘最簡單形式的關聯規則：單維單層布爾兩個主要方法Apriori（Agrawal&Srikant@VLDB’94）頻繁模式增長方法（FPgrowth—Han,Pei&Yin@SIGMOD’00）2023/2/110數據挖掘6.2.1Apriori：一個基于候選集的方法Apriori性質：一個頻繁項集的所有非空子集都必定是頻繁的如果{啤酒，尿布，堅果}是頻繁的，則{啤酒，尿布}必定是頻繁的每個包含{啤酒，尿布，堅果}

的事務，必定包含{啤酒，尿布}

反單調Apriori

修剪原則:如果某個項集是不頻繁的，則它的超集不需要被考慮2023/2/111數據挖掘Apriori方法逐層搜索：由K－項集到

k+1－候選項集方法：掃描數據集一次，得到所有長度為1的頻繁項集基于長度為K的頻繁項集，生成長度為k+1的候選項集掃描數據集，檢測候選項集是否頻繁當沒有頻繁項集或候選項集生成時，中止算法。2023/2/112數據挖掘例子：Apriori算法

事務數據庫第一遍掃描C1L1L2C2C2第二遍掃描C3L3第三遍掃描事務號項10A,C,D20B,C,E30A,B,C,E40B,E項集S{A}2{B}3{C}3{D}1{E}3項集S{A}2{B}3{C}3{E}3項集{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}項集S{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2項集S{A,C}2{B,C}2{B,E}3{C,E}2項集{B,C,E}項集S{B,C,E}2Smin=22023/2/113數據挖掘Apriori算法偽碼：Ck

：長度為k的候選項集Lk：長度為k的頻繁項集L1={頻繁項};for

(k=1;Lk!=;k++)dobegin

Ck+1=由Lk

生成的候選項集；

對數據庫中的每個事務t

do

將Ck+1中所有在t中出現的候選項集的計數分別加1

Lk+1=Ck+1

中所有計數超過支持度閾值的候選項集

endreturn

k

Lk;2023/2/114數據挖掘Apriori中的重要細節如何生成候選項集？第一步：self-joiningLk第二步：修剪生成候選項集的例子L3={abc,abd,acd,ace,bcd}Self-joining:L3*L3由abc

與abd

得到

abcd由acd

與ace得到acde修剪：由于

ade

不在L3

中，acde

被刪除C4={abcd}2023/2/115數據挖掘如何生成候選項集？假設Lk-1

中的項按某個次序排列第一步：self-joiningLk-1

insertinto

Ckselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1第二步：修剪Forall項集

cinCk

doForall(k-1)-子集

sofcdoif(sisnotinLk-1)thendeletecfromCk2023/2/116數據挖掘6.2.2由頻繁項集產生關聯規則強關聯規則：滿足支持度閾值和置信度閾值的規則基于頻繁項集生成關聯規則對每個頻繁項集L，產生L的所有非空子集對于L的每個非空子集S，如果支持度（L）/支持度（S）大于或等于置信度閾值，則輸出規則“S(L-S)”例子：支持度閾值為2，置信度閾值為70％BCE事務號項10A,C,D20B,C,E30A,B,C,E40B,E2023/2/117數據挖掘6.2.3提高Apriori的有效性挑戰多遍事務數據庫掃描候選頻繁項集的數目巨大候選項集的計數工作量較大改進Apriori：思路減少事務數據庫掃描次數減少候選項集數目有效支持候選項集的計數2023/2/118數據挖掘提高Apriori的有效性基于散列的技術對于一個長度為k的項集，若它所對應的哈希桶計數小于閾值，則它不可能是頻繁的可有效減少守候選項集的數目例子：候選項集：a,b,c,d,e哈希桶：{ab,ad,ae}{bd,be,de}…長度為1的頻繁項集：a,b,d,e如果{ab,ad,ae}的計數之和小于支持度閾值，則ab

不是長度為2的候選項集2023/2/119數據挖掘提高Apriori的有效性事務壓縮不包含任何k－項集的事務不可能包含任何（k+1）－項集劃分方法：僅掃描數據庫兩次將數據庫中的數據劃分為幾個子集，原數據庫中任意一個頻繁項集至少在一個子集中是頻繁的第一遍掃描：劃分數據庫，并找到各個子集中的頻繁項第二遍掃描：計算全局頻繁項2023/2/120數據挖掘提高Apriori的有效性選樣從原數據庫中選取一個樣本，使用Apriori算法挖掘此樣本中的頻繁項集（使用較小的支持度閾值）掃描數據庫，驗證樣本中的頻繁項集在原數據庫中是否頻繁。僅驗證頻繁項集閉包的邊界例子：僅檢查

abcd，不用檢查

ab,ac,…,等重新掃描數據庫，找出遺漏的頻繁項集2023/2/121數據挖掘提高Apriori的有效性ABCDABCABDACDBCDABACBCADBDCDABCD{}項集網動態項集計數：減少掃描次數一旦A與D都被確定是頻繁的，馬上開始對AD的計數一旦項集BCD的所有長度為2的子集都被確定是頻繁的，馬上開始對BCD的計數事務1-項集2-項集…Apriori1-項集2-項集3-項集DIC2023/2/122數據挖掘6.2.4不產生候選挖掘頻繁項集對數據庫的多遍掃描代價昂貴（costly）挖掘長模式需要對數據庫的多遍掃描，并會產生大量候選項集為找到頻繁項集i1i2…i100掃描遍數：100產生的候選項集數目：C1001+C1002+…+C110000=2100-1=1.27*1030!瓶頸：候選的產生與驗證能否不生成候選項集？2023/2/123數據挖掘無候選生成的頻繁模式挖掘基于短模式，使用局部頻繁項得到長模式“abc”是一個頻繁模式找出所有包含“abc”的事務:DB|abc“d”是DB|abc

中的局部頻繁項abcd

是一個頻繁模式2023/2/124數據挖掘構建事務數據庫的FP-tree{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1項頭表項的支持度計數f 4c 4a 3b 3m 3p 3min_support=3事務號

購買的項

（有序）頻繁項100 {f,a,c,d,g,i,m,p}

{f,c,a,m,p}200 {a,b,c,f,l,m,o}

{f,c,a,b,m}300

{b,f,h,j,o,w}

{f,b}400

{b,c,k,s,p}

{c,b,p}500

{a,f,c,e,l,p,m,n}

{f,c,a,m,p}掃描數據庫1遍，找出所有頻繁項將頻繁項按它們支持度計數的降序排列，f-list重新掃描數據庫，構建FP-treeF-list=f-c-a-b-m-p2023/2/125數據挖掘FP-tree結構的優點完全性保留了頻繁項挖掘所需的所有信息沒有將事務中的長模式打斷壓縮性減少不相關信息—刪掉了不頻繁項項按支持度計數的降序排列：出現次數越多的項，越可能被多個模式所共享永遠不可能比原數據庫大（不計節點間的連接與計數域）2023/2/126數據挖掘劃分模式與數據庫可以根據f-list

，將頻繁模式劃分為多個子集F-list=f-c-a-b-m-p模式包含p模式包含m，但不包含p…模式包含c，但不包含a，b，m，p模式f完全且無冗余2023/2/127數據挖掘從P-條件模式集中找出所有包含P的模式以FP-樹的項頭表為起點沿著頻繁項p

的鏈接橫穿FP-樹基于項p在樹中的前綴生成p的條件模式集條件模式集項

條件模式集c f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1項頭表項的支持度計數f 4c 4a 3b 3m 3p 32023/2/128數據挖掘由條件模式集生成條件FP-樹

對每個模式集計算集中每個項的支持度計數為模式集中的頻繁項構建FP-樹m-條件模式集fca:2,fcab:1{}f:3c:3a:3m-條件

FP-樹所有包含

m的頻繁模式m,fm,cm,am,fcm,fam,cam,fcam{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1項頭表項的支持度計數f 4c 4a 3b 3m 3p 32023/2/129數據挖掘遞歸：挖掘每個條件FP-tree{}f:3c:3a:3m-條件

FP-樹“am”的條件模式集：(fc:3){}f:3c:3am-條件

FP-樹“cm”的條件模式集：(f:3){}f:3cm-條件

FP-樹“cam”的條件模式集：(f:3){}f:3cam-條件

FP-樹2023/2/130數據挖掘特殊情況：FP-樹中的單條前綴路徑假設一個（條件）FP-樹T中有一條共享的前綴路徑P可以將挖掘分解為兩部分將單條前綴路徑壓縮為一個節點綜合此條前綴路徑與壓縮后FP-樹的挖掘結果a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=2023/2/131數據挖掘基于FP-樹挖掘頻繁模式思路：頻繁模式增長通過數據庫劃分，遞歸增長頻繁模式方法對每個頻繁項，構建它的條件模式集與條件FP-樹在新構建的條件FP-樹上重復上述步驟直到結果FP-樹為空，或者僅包含一條路徑—這條路徑的所有子路徑都代表一個頻繁模式2023/2/132數據挖掘FP-增長vs.Apriori：對支持度閾值的可伸縮性數據集T25I20D10K2023/2/133數據挖掘為什么FP-增長的性能更好？分而治之：基于當前得到的頻繁模式分解挖掘任務與數據庫只需仔細搜索較小的數據庫其他因素無候選項集（模式）生成，無候選項集驗證數據庫壓縮：FP-樹結構不需要對整個數據庫進行重復掃描只需計算局部頻繁項，并構建條件FP-樹，不需要模式搜索與匹配2023/2/134數據挖掘6.2.5冰山查詢冰山查詢：在一個屬性或屬性集上計算一個聚集函數，以找出大于某個指定閾值的聚集值。例子：selectP.cust_ID,P.item_ID,SUM(P.qty)fromPurchasesPgroupbyP.cust_ID,P.item_IDhavingSUM(P.qty)>=3產生候選selectP.cust_IDselectP.item_IDfromPurchasesPfromPurchasesPgroupbyP.cust_IDgroupbyP.item_IDhavingSUM(P.qty)>=3havingSUM(P.qty)>=32023/2/135數據挖掘挖掘大型數據庫中的關聯規則6.1關聯規則挖掘6.2由事務數據庫挖掘單維布爾關聯規則6.3由事務數據庫挖掘多層關聯規則6.4由關系數據庫和數據倉庫挖掘多維關聯規則6.5由關聯挖掘到相關分析6.6基于約束的關聯挖掘6.7小結2023/2/136數據挖掘6.3.1多層關聯規則數據庫中的項經常形成層次關系多層關聯規則：由具有概念分層的關聯規則挖掘產生的規則為什么要挖掘多層關聯規則在低層/原始層的數據項之間很難找出強關聯規則用戶的需求例子：2023/2/137數據挖掘6.3.2挖掘多層關聯規則的方法通常采用自頂向下的策略對于所有層使用一致的最小支持度遞減的支持度閾值設置較低層次的項通常具有較低的支持度統一的支持度閾值computer[支持度=10%]laptop[支持度=6%]desktop[支持度=4%]層1支持度閾值=5%層2支持度閾值=5%層1支持度閾值=5%層2支持度閾值=3%不統一的支持度閾值2023/2/138數據挖掘頻繁項集搜索策略逐層獨立沒有剪枝層交叉單項過濾一個第i層的項被考察，當且僅當它在第（i-1）層的父節點是頻繁的computer[支持度=10%]laptop（未考察）desktop（未考察）層1支持度閾值=12%層2支持度閾值=3%2023/2/139數據挖掘頻繁項集搜索策略層交叉k-項集過濾一個第i層的k-項集被考察，當且僅當它在第（i-1）層的對應父節點k-項集是頻繁的Computerandprinter[支持度=7%]Laptopcomputerandb/wprinter[支持度=1%]Desktopcomputerandb/wprinter[支持度=1%]層1支持度閾值=5%層2支持度閾值=2%Laptopcomputerandcolorprinter[支持度=2%]Desktopcomputerandb/wprinter[支持度=3%]2023/2/140數據挖掘頻繁項集搜索策略受控的層交叉單項過濾策略層傳遞閾值下一層的最小支持度閾值與當前層的最小支持度閾值之間的值computer[支持度=10%]laptop[支持度=6%]desktop[支持度=4%]層1支持度閾值=12%層傳遞閾值=8%層2支持度閾值=3%2023/2/141數據挖掘6.3.3檢查冗余的多層關聯規則由于項之間的層次關系，一些規則之間可能存在冗余例子Desktopcomputerb/wprinter[支持度=8%，置信度=70%]IBMdesktopcomputer

b/wprinter[支持度=2%，置信度=72%]我們稱第一個規則是第二個規則的祖先若一個規則的支持度與基于其祖先規則推導出的期望的支持度相似，則稱這個規則是冗余的2023/2/142數據挖掘挖掘大型數據庫中的關聯規則6.1關聯規則挖掘6.2由事務數據庫挖掘單維布爾關聯規則6.3由事務數據庫挖掘多層關聯規則6.4由關系數據庫和數據倉庫挖掘多維關聯規則6.5由關聯挖掘到相關分析6.6基于約束的關聯挖掘6.7小結2023/2/143數據挖掘6.4.1多維關聯規則單維規則：購買（X，”desktopcomputer”）購買（X，”b/wprinter”）多維關聯規則:

2維或謂詞維間關聯規則（沒有重復的謂詞）年齡（X，”19-25”）職業（X，“學生”）購買（X，“可樂”）混合維關聯規則（有重復出現的謂詞）年齡（X，”19-25”）購買（X，”爆米花”）購買（X，”可樂”）單維關聯規則挖掘：搜索頻繁項集多維關聯規則挖掘：搜索頻繁謂詞集分類屬性：具有有限數目的可能取值，值之間無次序關系量化屬性：數值型數據，值之間存在次序關系2023/2/144數據挖掘對量化屬性的處理使用預定義的概念分層將量化屬性離散化（靜態離散化）根據數據的分布，將量化屬性離散化到“箱”（動態離散化）基于數據點之間的距離將量化屬性離散化（使用聚類方法）2023/2/145數據挖掘6.4.2使用量化屬性的靜態離散化挖掘多維關聯規則在挖掘前，使用概念層次將屬性離散化數值型屬性的取值用取值區間表示在關系數據庫中，找出所有k-謂詞頻繁集需要k

或k+1次掃描數據立方體適合于關聯規則挖掘n-維立方體中的節點表示謂詞集在數據立方體上挖掘可以減少挖掘所需時間(收入)(年齡)()(購買)(年齡，收入)(年齡，購買)(收入，購買)(年齡，收入，購買)2023/2/146數據挖掘6.4.3挖掘量化關聯規則分箱：等寬分箱等深分箱基于同質的分箱找頻繁謂詞集關聯規則聚類2023/2/147數據挖掘6.4.4挖掘基于距離的關聯規則考慮數據點之間或區間之間的相對距離，緊扣區間數據的語義，并允許數據值的近似兩遍算法：使用聚類找出區間或簇搜索頻繁地一起出現的簇的集合，得到基于距離的關聯規則2023/2/148數據挖掘挖掘大型數據庫中的關聯規則6.1關聯規則挖掘6.2由事務數據庫挖掘單維布爾關聯規則6.3由事務數據庫挖掘多層關聯規則6.4由關系數據庫和數據倉庫挖掘多維關聯規則6.5由關聯挖掘到相關分析6.6基于約束的關聯挖掘6.7小結2023/2/149數據挖掘6.5.1強關聯規則不一定是有趣的打籃球

吃谷類食品[40%,66.7%]產生誤導在所有學生中，有75%吃谷類食品，高于66.7%。打籃球

不吃谷類食品[20%,33.3%]更為準確，盡管它的支持度與置信度都很低規則AB的置信度有一定的欺騙性，它只給出了A，B的條件概率估計，并沒有度量A和B之間的相關性。2023/2/150數據挖掘6.5.2由關聯分析到相關分析事件之間相關性的度量：corr打籃球不打籃球總和吃谷類食品200017503750不吃谷類食品10002501250總和3000200050002023/2/151數據挖掘挖掘大型數據庫中的關聯規則6.1關聯規則挖掘6.2由事務數據庫挖掘單維布爾關聯規則6.3由事務數據庫挖掘多層關聯規則6.4由關系數據庫和數據倉庫挖掘多維關聯規則6.5由關聯挖掘到相關分析6.6基于約束的關聯挖掘6.7小結2023/2/152數據挖掘6.6基于約束的關聯挖掘自動找到數據庫中的所有模式—不現實！模式數目可能非常大，但大部分是不需要的數據挖掘應該是一個交互式過程用戶使用數據挖掘查詢語言或圖形用戶界面指導挖掘過程基于約束的挖掘用戶：給出約束或指明需要挖掘什么系統優化：利用約束進行有效挖掘—基于約束的挖掘2023/2/153數據挖掘6.6基于約束的關聯挖掘知識類型約束：

指定要挖掘的知識類型，如分類模型，關聯規則，等等數據約束指定與任務相關的數據集維/層約束指定所用的維或概念分層結構中的層規則約束指定要挖掘的規則形式，如規則前件或后件中謂詞的個數興趣度約束指定規則興趣度閾值或統計度量，如支持度閾值與置信度閾值2023/2/154數據挖掘6.6.1關聯規則的元規則制導挖掘元規則使得用戶可以說明他們感興趣的規則的語法形式例子：元規則：與元規則匹配的規則：2023/2/155數據挖掘6.6.2用附加的規則約束制導的挖掘規則約束反單調的單調的簡潔的可轉變的不可轉變的2023/2/156數據挖掘反單調約束反單調性若項集S不滿足約束，那么它的所有超集都不滿足約束求和(S.價格)v

是反單調的求和(S.價格)v

不是反單調的例子：約束C：求和(S.價格)15是反單調的項集ab

不滿足Cab的任何超集也不滿足CTID事務10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,g事務數據庫(min_sup=2)項價格a40b10c20d10e30f30g20h102023/2/157數據挖掘單調約束單調性若項集S滿足約束，則它的任意超集都滿足約束求和(S.價格)v

是單調的最小(S.價格)

v是單調的例子：約束C：求和(S.價格)15項集ab

滿足C