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

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

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

XY支持度（support），s，包含XY的事務出現(xiàn)的概率置信度（confidence），c，事務包含X時，也包含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%)購買尿布的顧客兩樣都買的顧客購買啤酒的顧客事務號購買的項10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F2023/2/14數(shù)據(jù)挖掘為什么頻繁模式挖掘是重要的？能發(fā)現(xiàn)數(shù)據(jù)集中內(nèi)在的特性是許多重要的數(shù)據(jù)挖掘任務的基礎關(guān)聯(lián)分析，相關(guān)分析，與因果分析序列模式，結(jié)構(gòu)模式（如：子圖）時空數(shù)據(jù)、多媒體數(shù)據(jù)、時序數(shù)據(jù)、流數(shù)據(jù)中的模式分析分類：關(guān)聯(lián)分類聚類：基于頻繁模式的聚類數(shù)據(jù)倉庫：冰山數(shù)據(jù)立方語義數(shù)據(jù)壓縮廣泛的應用購物籃數(shù)據(jù)分析，Web點擊流分析，打折銷售分析，DNA序列分析2023/2/15數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則的分類布爾關(guān)聯(lián)規(guī)則與量化關(guān)聯(lián)規(guī)則計算機

財務管理軟件年齡（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，”計算機”）閉模式與最大模式2023/2/16數(shù)據(jù)挖掘閉模式與最大模式一個長模式包含大量子模式。例如：{a1,…,a100}包含

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

）與最大模式（

max-patterns）一個項集X是閉模式，如果X是頻繁的，且不存在超模式Y(jié)?X具有與X同樣的支持度（Pasquier，ICDT’99）一個項集X是一個最大模式，如果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由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則6.3由事務數(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由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則挖掘最簡單形式的關(guān)聯(lián)規(guī)則：單維單層布爾兩個主要方法Apriori（Agrawal&Srikant@VLDB’94）頻繁模式增長方法（FPgrowth—Han,Pei&Yin@SIGMOD’00）2023/2/110數(shù)據(jù)挖掘6.2.1Apriori：一個基于候選集的方法Apriori性質(zhì)：一個頻繁項集的所有非空子集都必定是頻繁的如果{啤酒，尿布，堅果}是頻繁的，則{啤酒，尿布}必定是頻繁的每個包含{啤酒，尿布，堅果}

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

反單調(diào)Apriori

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

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

事務數(shù)據(jù)庫第一遍掃描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數(shù)據(jù)挖掘Apriori算法偽碼：Ck

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

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

Ck+1=由Lk

生成的候選項集；

對數(shù)據(jù)庫中的每個事務t

do

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

Lk+1=Ck+1

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

endreturn

k

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

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

abcd，不用檢查

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

中的局部頻繁項abcd

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

，將頻繁模式劃分為多個子集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-樹的項頭表為起點沿著頻繁項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項頭表項的支持度計數(shù)f 4c 4a 3b 3m 3p 32023/2/128數(shù)據(jù)挖掘由條件模式集生成條件FP-樹

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

b/wprinter[支持度=2%，置信度=72%]我們稱第一個規(guī)則是第二個規(guī)則的祖先若一個規(guī)則的支持度與基于其祖先規(guī)則推導出的期望的支持度相似，則稱這個規(guī)則是冗余的2023/2/142數(shù)據(jù)挖掘挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則6.1關(guān)聯(lián)規(guī)則挖掘6.2由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則6.3由事務數(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ī)則（沒有重復的謂詞）年齡（X，”19-25”）職業(yè)（X，“學生”）購買（X，“可樂”）混合維關(guān)聯(lián)規(guī)則（有重復出現(xiàn)的謂詞）年齡（X，”19-25”）購買（X，”爆米花”）購買（X，”可樂”）單維關(guān)聯(lián)規(guī)則挖掘：搜索頻繁項集多維關(guān)聯(lián)規(guī)則挖掘：搜索頻繁謂詞集分類屬性：具有有限數(shù)目的可能取值，值之間無次序關(guān)系量化屬性：數(shù)值型數(shù)據(jù)，值之間存在次序關(guān)系2023/2/144數(shù)據(jù)挖掘?qū)α炕瘜傩缘奶幚硎褂妙A定義的概念分層將量化屬性離散化（靜態(tài)離散化）根據(jù)數(shù)據(jù)的分布，將量化屬性離散化到“箱”（動態(tài)離散化）基于數(shù)據(jù)點之間的距離將量化屬性離散化（使用聚類方法）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é)點表示謂詞集在數(shù)據(jù)立方體上挖掘可以減少挖掘所需時間(收入)(年齡)()(購買)(年齡，收入)(年齡，購買)(收入，購買)(年齡，收入，購買)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ù)點之間或區(qū)間之間的相對距離，緊扣區(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由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則6.3由事務數(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強關(guān)聯(lián)規(guī)則不一定是有趣的打籃球

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

不吃谷類食品[20%,33.3%]更為準確，盡管它的支持度與置信度都很低規(guī)則AB的置信度有一定的欺騙性，它只給出了A，B的條件概率估計，并沒有度量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由事務數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則6.3由事務數(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)挖掘自動找到數(shù)據(jù)庫中的所有模式—不現(xiàn)實！模式數(shù)目可能非常大，但大部分是不需要的數(shù)據(jù)挖掘應該是一個交互式過程用戶使用數(shù)據(jù)挖掘查詢語言或圖形用戶界面指導挖掘過程基于約束的挖掘用戶：給出約束或指明需要挖掘什么系統(tǒng)優(yōu)化：利用約束進行有效挖掘—基于約束的挖掘2023/2/153數(shù)據(jù)挖掘6.6基于約束的關(guān)聯(lián)挖掘知識類型約束：

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

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

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

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

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

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

滿足C