DATA MINING AND APPLICATION: BÀI TOÁN KHAI THÁC

Chia sẻ: Abcdef_14 Abcdef_14 | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

185
lượt xem 52
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

QUI TRÌNH B0 : cây FP B1 : (conditional pattern bases) cho nút trên cây FP). B2 : cây FP (conditional FP tree) B3 : Khai thác qui cây FP và phát cho khi cây FP 1 duy ra các

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: DATA MINING AND APPLICATION: BÀI TOÁN KHAI THÁC

KHAI THÁC (DATA MINING) 1 BÀ I 3 - PH N 2 KHAI THÁC T P PH BI N & LU T K T H P 2 1
N I DUNG 1. 2. 3. 3 Bài toán khai thác là bài toán quan KTDL : ra tính quan DL các con là bao Bài toán khai thác LKH là bài toán X Y (X, Y I và X Y ={}) supp (X Y ) minsupp conf (X Y ) minconf 4 2
Bài toán khai thác là bài toán tìm các các S (hay S) có mãn minsupp supp(S) minsupp Cách : trên tính Tìm theo : toán Apriori (1994) Phát : toán FP-Growth (2000) Tìm trên CSDL hàng : toán 5 Charm (2002) CSDL Khi khai thác các dài CSDL và viên Ví : tìm i1 i2 i100 : 100-1 = 1.27*1030 ! : viên và tra 6 3
N I DUNG 1. 2. -Growth 3. 7 -GROWTH 1. Khai thác không hàm viên. Nén CSDL thành trúc cây FP (Frequent Patern) qui cây FP 8 4
-GROWTH 2. QUI TRÌNH B0 : cây FP B1 : (conditional pattern bases) cho nút trên cây FP). B2 : cây FP (conditional FP tree) B3 : Khai thác qui cây FP và phát cho khi cây FP 1 duy - ra các 9 B0) TID Items bought (ordered) frequent items {f, a, c, d, g, i, m, p} {f, c, a, m, p} 100 {a, b, c, f, l, m, o} {f, c, a, b, m} 200 minsupp = 60% {b, f, h, j, o, w} {f, b} 300 {b, c, k, s, p} {c, b, p} 400 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 500 1. Tìm 1- Header Table CSDL 1 Item frequency head 2. f 4 vào trong F-list c 4 a 3 F-list=f-c-a-b-m-p b 3 m 3 3. CSDL theo F- p 3 list. CSDL và cây FP 10 5
(B0) TID Items bought (ordered) frequent items minsupp = 3 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 100 {a, b, c, f, l, m, o} {f, c, a, b, m} 200 {b, f, h, j, o, w} {f, b} 300 {b, c, k, s, p} {c, b, p} 400 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 500 {} 1. Tìm 1- Header Table CSDL 1 f:1 Item frequency head f 4 c:1 2. c 4 vào trong F- a 3 a:1 b 3 list m 3 F-list=f-c-a-b-m-p p 3 m:1 3. p:1 11 (B0) TID Items bought (ordered) frequent items minsupp = 3 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 100 {a, b, c, f, l, m, o} {f, c, a, b, m} 200 {b, f, h, j, o, w} {f, b} 300 {b, c, k, s, p} {c, b, p} 400 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 500 {} 1. Tìm 1- Header Table CSDL 1 f:2 Item frequency head f 4 c:2 2. c 4 vào trong F- a 3 a:2 b 3 list m 3 F-list=f-c-a-b-m-p p 3 m:1 b:1 3. p:1 m:1 12 6
(B0) TID Items bought (ordered) frequent items minsupp = 3 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 100 {a, b, c, f, l, m, o} {f, c, a, b, m} 200 {b, f, h, j, o, w} {f, b} 300 {b, c, k, s, p} {c, b, p} 400 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 500 {} 1. Tìm 1- Header Table CSDL 1 f:3 Item frequency head f 4 c:2 b:1 2. c 4 vào trong F- a 3 a:2 b 3 list m 3 F-list=f-c-a-b-m-p p 3 m:1 b:1 3. p:1 m:1 13 (B0) TID Items bought (ordered) frequent items minsupp = 3 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 100 {a, b, c, f, l, m, o} {f, c, a, b, m} 200 {b, f, h, j, o, w} {f, b} 300 {b, c, k, s, p} {c, b, p} 400 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 500 {} 1. Tìm 1- Header Table CSDL 1 f:4 c:1 Item frequency head f 4 2. c:3 b:1 b:1 c 4 vào trong F- a 3 list a:3 p:1 b 3 m 3 F-list=f-c-a-b-m-p p 3 m:2 b:1 3. p:2 m:1 14 7
gian : 10 TID Items 1 {B,A,K} Trình bày ra . 2 {K, B,C,A} 3 {A,D,M, B} Yêu : 4 {D,A,B,E} 5 {A,K,C} 1.Xây cây FP CSDL 6 {A,B,C} bên minsupp = 25% 7 {M,B,C,E} 8 {B,C,D} 2. Minsupp = 40% thì cây 9 {B,E} 10 {A,E,M,K} FP thay nào ? 11 {A,C,E,M} 12 {A,D,E} 15 Tên nhóm : ý: bài làm theo nhóm 16 8
B1 Xây (Conditional pattern base) cây FP cây FP theo . Gom (transformed prefix) 17 . transformed prefix) p p {} Header Table f:4 c:1 Item frequency head f 4 item cond. pattern base c:3 b:1 c 4 b:1 a 3 p fcam:2, cb:1 b 3 a:3 p:1 m 3 p 3 m:2 b:1 18 m:1 p:2 9
transformed prefix) m m {} Header Table f:4 c:1 Item frequency head f 4 item cond. pattern base c:3 b:1 c 4 b:1 a 3 m fca:2, fcab:1 b 3 a:3 p:1 p fcam:2, cb:1 m 3 p 3 m:2 b:1 p:2 m:1 19 pattern base) FP {} Header Table item cond. pattern base f:4 c:1 Item frequency head f 4 c f:3 c:3 b:1 c 4 b:1 a 3 a fc:3 b 3 a:3 p:1 b fca:1, f:1, c:1 m 3 p 3 m fca:2, fcab:1 m:2 b:1 p fcam:2, cb:1 m:1 p:2 20 10
B2: Xây cây FP- : trong . Xác Xây cây FP cho B0) 21 - cho p là : {fcam:2, cb:1} -> c:3 p-conditional FP-tree {} minsupp = 3 Header Table c:3 Item frequency head c 3 22 11
- cho m là : {fca:2, fcab:1} -> f:3, c:3, a:3 là m-conditional FP-tree {} minsupp = 3 Header Table f:3 Item frequency head f 3 c:3 c 3 a 3 23 a:3 Conditional pattern-base Conditional FP-tree Item p { (fcam:2), (cb:1) } { (c:3) } | p m { (fca:2), (fcab:1) } { (f:3, c:3, a:3) } | m b { (fca:1), (f:1), (c:1) } {} a { (fc:3) } { (f:3, c:3) } | a c { (f:3) } { (f:3) } | c f {} {} 24 12
B3 D là trong CSDL, B là và là các trong B. Khi là trong CSDL khi và khi là trong B. abcdef abcde f là trong các giao abcde 25 B3 T - P. - p-conditional FP-tree {} liên quan Header Table p là : c:3 Item frequency head p :3, c 3 cp :3 26 13
B3 Xem xét các cây FP có và các cây FP nhánh cách riêng : phân chia cây nhánh thành cây có toán qui : FP_Growth(FP- tree, null) 27 B3 -tree, null) procedure FP_growth(Tree, ) If cây FP 1 then For supp = suppmin trong ); Else for i = i); i và cây FP tree ) cho If tree tree , ) 28 14
- m-conditional FP-tree {} Header Table m là : f:3 m : 3, Item frequency head fm :3, cm :3, am:3, f 3 c:3 c 3 fcm:3, fam:3, a 3 cam:3, a:3 fcam:3 29 Item Conditional FP-Tree Frequent Patterns p { (c:3) } | p p, cp m { (f:3, c:3, a:3) } | m m, fm, cm, am, fcm, fam, cam, fcam b {} b a { (f:3, c:3) } | a a, fa, ca, fca c { (f:3) } | c c, fc f {} f 30 15
TT FP-GROWN & TT APRIORI Data set T25I20D10K 100 D1 FP-grow th runtime 90 D1 Apriori runtime 80 70 Run time(sec.) 60 50 40 30 20 10 0 0 0.5 1 1.5 2 2.5 3 Support threshold(%) 31 32 16
33 N I DUNG 1. 2. 3. 34 17
trên DL : {SQL Server} {DM Book} {DBMiner} (0.2%, 60%) [30,39] [42000,48000] Mua (PC) (1%, 75%) trên DL : {Tã lót} {Bia} (0.5%, 60%) [30,39] [42000,48000] Mua (PC) 35 (1%, 75%) : trên phân khái [30,34] Mua (PC) (1%, 75%) [30,32] Mua (laptop C) (0.5%, 80%) [30,34] Mua (PC) (1%, 75%) 36 18
nào là hay, lý thú ? 1. toán khai thác có xu sinh ra quá . Trong có không hay tính lý thú khách quan : 2. o (supp) và tin (conf) o Còn 20 khác quan : 3. o LKH là lý thú là gây nhiên / và o Có 37 1: Trong 5000 sinh viên [40%, 66.7%] basketball not basketball sum(row) cereal 2000 1750 3750 not cereal 1000 250 1250 38 sum(col.) 3000 2000 5000 19
Coffee Coffee Tea 15 5 20 Tea 75 5 80 90 10 100 Coffee Conf= P(Coffee|Tea) = 15/20 = 0.75 0.9 dù tin cao làm cho 39 P(Coffee|Tea) = 75/80= 0.9375 hay quan các P(Y | X ) Lift P(Y ) P( X , Y ) Interest P( X ) P(Y ) PS P( X , Y ) P( X ) P(Y ) P( X , Y ) P( X ) P(Y ) coefficien t P( X )[1 P( X )]P(Y )[1 P(Y )] 40 20