關(guān)聯(lián)規(guī)則挖掘理論和算法PPT學(xué)習(xí)教案

1、會計學(xué)1關(guān)聯(lián)規(guī)則挖掘理論和算法關(guān)聯(lián)規(guī)則挖掘理論和算法 t1物品物品2物品物品6物品物品9 t2物品物品3物品物品8物品物品16 tn物品物品1物品物品12物品物品34 第2頁/共38頁第1頁/共38頁第3頁/共38頁第2頁/共38頁第4頁/共38頁第3頁/共38頁第5頁/共38頁第4頁/共38頁第6頁/共38頁第5頁/共38頁TIDItemset1001，3，42002，3，53001，2，3，54002，5 1994年，年，Agrawal 等人提出了著名的等人提出了著名的Apriori 算法。算法。第7頁/共38頁第6頁/共38頁TID Items100 1 3 4200 2 3 5300

2、1 2 3 5400 2 5Database DC1L1L2C2Scan DL3Scan DC3Scan DC4Scan DScan DL4 C1：1-候選集候選集 L1：1-頻繁項(xiàng)目集頻繁項(xiàng)目集C2：2-候選集候選集 L2：2-頻繁項(xiàng)目集頻繁項(xiàng)目集C3：3-候選集候選集 L3：3-頻繁項(xiàng)目集頻繁項(xiàng)目集C4：4-候選集候選集 L4：4-頻繁項(xiàng)目集頻繁項(xiàng)目集L3是最大頻繁項(xiàng)目集是最大頻繁項(xiàng)目集第8頁/共38頁第7頁/共38頁（1） L1 = large 1-itemsets; /所有所有1-項(xiàng)目頻集項(xiàng)目頻集（2） FOR （k=2; Lk-1; k+） DO BEGIN（3） Ck=aprior

3、i-gen（Lk-1）; / Ck是是k-候選集候選集（4） FOR all transactions t D DO BEGIN（5） Ct=subset（Ck，t）; / Ct是所有是所有t包含的候選集元素包含的候選集元素（6） FOR all candidates c Ct DO（7） c.count+;（8） END（9） Lk=c Ck |c.count minsup_count（10） END（11） L= Lk; 第9頁/共38頁第8頁/共38頁（1） FOR all itemset p Lk-1 DO （2） FOR all itemset q Lk-1 DO （3） IF p.

4、item1=q.item1， ， p.itemk-2=q.itemk-2， p.itemk-1 q.itemk-1 THEN BEGIN（4） c= pq;/把把q的第的第k-1個元素連到個元素連到p后后（5） IF has_infrequent_subset（c， Lk-1） THEN（6） delete c;/刪除含有非頻繁項(xiàng)目子集的侯選元素刪除含有非頻繁項(xiàng)目子集的侯選元素（7） ELSE add c to Ck;（8） END（9） Return Ck; 第10頁/共38頁第9頁/共38頁Rule-generate（L，minconf）（1） FOR each frequent item

5、set lk in L（2） genrules（ lk ， lk）;第11頁/共38頁第10頁/共38頁第12頁/共38頁第11頁/共38頁序號序號lkxm-1ConfidenceSupport規(guī)則（是否是強(qiáng)規(guī)則）規(guī)則（是否是強(qiáng)規(guī)則）1235267%50%235（否）（否）2235367%50%325（否）（否）3235567%50%523（否）（否）423523100%50%235（是）（是）52352567%50%253（否）（否）623535100%50%352（是）（是）包含包含2,35的事務(wù)與包含的事務(wù)與包含2的事務(wù)的比值的事務(wù)的比值,即即2:3同時滿足支持度和可信度同時滿足支持度和

6、可信度第13頁/共38頁第12頁/共38頁第14頁/共38頁第13頁/共38頁第15頁/共38頁第14頁/共38頁第16頁/共38頁第15頁/共38頁第17頁/共38頁第16頁/共38頁TID Items1 I1，I2，I52 I2，I43 I2，I34 I1，I2，I45 I1，I36 I2，I37 I1，I38 I1，I2，I3，I59 I1，I2，I3L2=(I2，I3) ，(I1，I2) ，(I1，I3) 桶地址桶地址 0 1 2 3 4 5 6桶計數(shù)桶計數(shù) 2 2 4 2 2 4 4桶桶 I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 內(nèi)內(nèi) I3，

7、I5 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3容容 I2，I3 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3第18頁/共38頁第17頁/共38頁第19頁/共38頁第18頁/共38頁第20頁/共38頁第19頁/共38頁第21頁/共38頁第20頁/共38頁下面是下面是Close算法作用到右表數(shù)據(jù)集的算法作用到右表數(shù)據(jù)集的執(zhí)行過程（假如執(zhí)行過程（假如minsup_count=3）：TIDItemset1A，B，C，D2B，C，E3A，B，C，E4B，D，E5A，B，C，D樣本數(shù)據(jù)庫樣本數(shù)據(jù)庫第22頁/共38頁第21頁/共38頁第23頁/共38頁第22頁/共

8、38頁樣本數(shù)據(jù)庫樣本數(shù)據(jù)庫下面看一個例子來說明下面看一個例子來說明FP-Tree的增長過程的增長過程,最小支持度閾值為最小支持度閾值為3。TIDItemset1f,a,c,d,g,i,m,p2a,b,c,f,l,m,o3b,f,h,j,o4b,c,k,s,p5a,f,c,e,l,m,p, nItem frequencyf4c4a3b3m3p3L掃描數(shù)據(jù)庫一次生成掃描數(shù)據(jù)庫一次生成1-頻繁項(xiàng)目集（在數(shù)據(jù)庫中出現(xiàn)頻繁項(xiàng)目集（在數(shù)據(jù)庫中出現(xiàn)3次或次或3次以上的），并按頻度降序排序，放入次以上的），并按頻度降序排序，放入L列表中；列表中；TIDItemset1f,c,a,m,p2f,c,a,b,m3f

9、,b4c,b,p5f,c,a,m,p(1-頻繁項(xiàng)目集頻繁項(xiàng)目集)第24頁/共38頁第23頁/共38頁樣本數(shù)據(jù)庫樣本數(shù)據(jù)庫TIDItemset1f,c,a,m,p2f,c,a,b,m3f,b4c,b,p5f,c,a,m,pItem(fre)f4c4a3b3m3p3LT1T2T3T4掃描數(shù)據(jù)庫掃描數(shù)據(jù)庫,依次依次增長增長FP-tree，并并改變支持?jǐn)?shù)改變支持?jǐn)?shù)f:1c:1a:1m:1NULLp:1f:2c:2a:2m:1NULLb:1p:1m:1f:3c:2a:2m:1NULLb:1p:1m:1b:1f:3c:2a:2m:1NULLb:1p:1m:1b:1c:1b:1p:1f:4c:3a:3m:2

10、NULLb:1p:2m:1b:1c:1b:1p:1T5第25頁/共38頁第24頁/共38頁Item(fre)f4c4a3b3m3p3L建立索引建立索引f:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5第26頁/共38頁第25頁/共38頁第27頁/共38頁第26頁/共38頁對應(yīng)的條件模式庫對應(yīng)的條件模式庫Item條件模式庫條件模式庫cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1FP-treeItem(fre)f4c4a3b3m3p3Lf:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5

11、第28頁/共38頁第27頁/共38頁m-條件條件模式庫模式庫Item條件模式庫條件模式庫cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:3c:3a:3NULLItem(fre)f4c4a3b3m3p3Lf:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5第29頁/共38頁第28頁/共38頁Item條件模式庫條件模式庫p(fcam:2),(cb:1)(c:3)|pm(fca:2),(fcab:1)(f:3,c:3,a:3)|mb(fca:1),(f:1),(c:1)Emptyafc:3(f:3,c:3)|acf:3(f:3|cfEmptyEmptyc:3NULLf:3c:3a:3NULLNULLf:3c:3NULLf:3NULLNULL第30頁/共38頁第29頁/共38頁c:3NULLf:3c:3a:3NULLNULLf:3c:3NULLf:3NULLNULL第31頁/共38頁第30頁/共38頁日用品服裝食品夏季服裝冬季服裝面包牛奶羽絨服大衣品牌1品牌2鮮奶酸奶品牌3品牌4層間關(guān)聯(lián)規(guī)則：如果層間關(guān)聯(lián)規(guī)則：如果在不同的粒度層次上考在不同的粒度層次上考慮問題，那么可能得到慮問題，那么可能得到的是層間關(guān)聯(lián)規(guī)則。的是層間關(guān)聯(lián)規(guī)則。如如“夏季服裝夏