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

數(shù)據(jù)挖掘

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

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

{A:3,B:3,D:4,E:3,AD:3}關(guān)聯(lián)規(guī)則：AD(60%,100%)DA(60%,75%)購買尿布的顧客兩樣都買的顧客購買啤酒的顧客事務(wù)號(hào)購買的項(xiàng)10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F2023/2/14數(shù)據(jù)挖掘?yàn)槭裁搭l繁模式挖掘是重要的？能發(fā)現(xiàn)數(shù)據(jù)集中內(nèi)在的特性是許多重要的數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)關(guān)聯(lián)分析，相關(guān)分析，與因果分析序列模式，結(jié)構(gòu)模式（如：子圖）時(shí)空數(shù)據(jù)、多媒體數(shù)據(jù)、時(shí)序數(shù)據(jù)、流數(shù)據(jù)中的模式分析分類：關(guān)聯(lián)分類聚類：基于頻繁模式的聚類數(shù)據(jù)倉庫：冰山數(shù)據(jù)立方語義數(shù)據(jù)壓縮廣泛的應(yīng)用購物籃數(shù)據(jù)分析，Web點(diǎn)擊流分析，打折銷售分析，DNA序列分析2023/2/15數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則的分類布爾關(guān)聯(lián)規(guī)則與量化關(guān)聯(lián)規(guī)則計(jì)算機(jī)

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

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

）與最大模式（

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

的事務(wù)，必定包含{啤酒，尿布}

反單調(diào)Apriori

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

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

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

：長度為k的候選項(xiàng)集Lk：長度為k的頻繁項(xiàng)集L1={頻繁項(xiàng)};for

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

Ck+1=由Lk

生成的候選項(xiàng)集；

對(duì)數(shù)據(jù)庫中的每個(gè)事務(wù)t

do

將Ck+1中所有在t中出現(xiàn)的候選項(xiàng)集的計(jì)數(shù)分別加1

Lk+1=Ck+1

中所有計(jì)數(shù)超過支持度閾值的候選項(xiàng)集

endreturn

k

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

與abd

得到

abcd由acd

與ace得到acde修剪：由于

ade

不在L3

中，acde

被刪除C4={abcd}2023/2/115數(shù)據(jù)挖掘如何生成候選項(xiàng)集？假設(shè)Lk-1

中的項(xiàng)按某個(gè)次序排列第一步：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項(xiàng)集

cinCk

doForall(k-1)-子集

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

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

abcd，不用檢查

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

中的局部頻繁項(xiàng)abcd

是一個(gè)頻繁模式2023/2/124數(shù)據(jù)挖掘構(gòu)建事務(wù)數(shù)據(jù)庫的FP-tree{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1項(xiàng)頭表項(xiàng)的支持度計(jì)數(shù)f 4c 4a 3b 3m 3p 3min_support=3事務(wù)號(hào)

購買的項(xiàng)

（有序）頻繁項(xiàng)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}掃描數(shù)據(jù)庫1遍，找出所有頻繁項(xiàng)將頻繁項(xiàng)按它們支持度計(jì)數(shù)的降序排列，f-list重新掃描數(shù)據(jù)庫，構(gòu)建FP-treeF-list=f-c-a-b-m-p2023/2/125數(shù)據(jù)挖掘FP-tree結(jié)構(gòu)的優(yōu)點(diǎn)完全性保留了頻繁項(xiàng)挖掘所需的所有信息沒有將事務(wù)中的長模式打斷壓縮性減少不相關(guān)信息—?jiǎng)h掉了不頻繁項(xiàng)項(xiàng)按支持度計(jì)數(shù)的降序排列：出現(xiàn)次數(shù)越多的項(xiàng)，越可能被多個(gè)模式所共享永遠(yuǎn)不可能比原數(shù)據(jù)庫大（不計(jì)節(jié)點(diǎn)間的連接與計(jì)數(shù)域）2023/2/126數(shù)據(jù)挖掘劃分模式與數(shù)據(jù)庫可以根據(jù)f-list

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

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

條件模式集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項(xiàng)頭表項(xiàng)的支持度計(jì)數(shù)f 4c 4a 3b 3m 3p 32023/2/128數(shù)據(jù)挖掘由條件模式集生成條件FP-樹

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

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

2維或謂詞維間關(guān)聯(lián)規(guī)則（沒有重復(fù)的謂詞）年齡（X，”19-25”）職業(yè)（X，“學(xué)生”）購買（X，“可樂”）混合維關(guān)聯(lián)規(guī)則（有重復(fù)出現(xiàn)的謂詞）年齡（X，”19-25”）購買（X，”爆米花”）購買（X，”可樂”）單維關(guān)聯(lián)規(guī)則挖掘：搜索頻繁項(xiàng)集多維關(guān)聯(lián)規(guī)則挖掘：搜索頻繁謂詞集分類屬性：具有有限數(shù)目的可能取值，值之間無次序關(guān)系量化屬性：數(shù)值型數(shù)據(jù)，值之間存在次序關(guān)系2023/2/144數(shù)據(jù)挖掘?qū)α炕瘜傩缘奶幚硎褂妙A(yù)定義的概念分層將量化屬性離散化（靜態(tài)離散化）根據(jù)數(shù)據(jù)的分布，將量化屬性離散化到“箱”（動(dòng)態(tài)離散化）基于數(shù)據(jù)點(diǎn)之間的距離將量化屬性離散化（使用聚類方法）2023/2/145數(shù)據(jù)挖掘6.4.2使用量化屬性的靜態(tài)離散化挖掘多維關(guān)聯(lián)規(guī)則在挖掘前，使用概念層次將屬性離散化數(shù)值型屬性的取值用取值區(qū)間表示在關(guān)系數(shù)據(jù)庫中，找出所有k-謂詞頻繁集需要k

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

吃谷類食品[40%,66.7%]產(chǎn)生誤導(dǎo)在所有學(xué)生中，有75%吃谷類食品，高于66.7%。打籃球

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

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

是反單調(diào)的求和(S.價(jià)格)v

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

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

是單調(diào)的最小(S.價(jià)格)

v是單調(diào)的例子：約束C：求和(S.價(jià)格)15項(xiàng)集ab

滿足C