Xây dựng cây quyết định sử dụng phụ thuộc hàm xấp xỉ

Chia sẻ: Nguyễn Minh Vũ | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

36
lượt xem 2
download

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

In this paper, we introduce in brief on the concepts of Approximate Functional Dependency (AFD), of Approximate Functionally Cross-Characteristic Dependency known as type II AFD and describe an adoption of AFD to a constructing method of decisson tree for databases mining purposes.

Chủ đề:

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

Lưu

Nội dung Text: Xây dựng cây quyết định sử dụng phụ thuộc hàm xấp xỉ

’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.23, S.2 (2007), 179–186 ı e e . . a ` . . ´ ’. ´ ’ ˆ ˆ ˆ ˆ ` ˆ XAY DU NG CAY QUYET DINH SU DUNG PHU THUOC HAM XAP XI . . . . . ˆ ˆ ˜ ´. A VU DU C THI, TR` N QUANG DIEU . Viˆn Cˆng nghˆ thˆng tin, Viˆn Khoa hoc v` Cˆng nghˆ Viˆt Nam e o e o e e e . . . . a o . . Abstract. In this paper, we introduce in brief on the concepts of Approximate Functional Dependency (AFD), of Approximate Functionally Cross-Characteristic Dependency known as type II AFD and describe an adoption of AFD to a constructing method of decisson tree for databases mining purposes. ´ ´ e a e o a a ’ e T´m t˘t. Trong b`i b´o n`y, ch´ ng tˆi gi´.i thiˆu so. lu.o.c vˆ kh´i niˆm phu thuˆc h`m xˆ p xı, phu o a a a a u o o . ` . . . . . ´ ´ ´ a o u a o ınh ’ o e o e thuˆc h`m xˆ p xı liˆn quan dˆn tu.o.ng quan h`m sˆ gi˜.a c´c thuˆc t´ cua mˆt quan hˆ (Phu thuˆc o a a ’ e . . . . . . ´ ´ ´ h`m xˆ p xı loai hai) v` u.ng dung phu thuˆc h`m xˆ p xı nh˘ m xˆy du.ng cˆy quyˆt dinh trong khai a a ’ . a´ a e . o a a ’ ` a a . . . . ph´ d˜. liˆu. a u e . ˆ ´. 1. GIO I THIEU . ´ a a Phu thuˆc h`m xˆ p xı (Approximate Functional Dependency AFD) v` phu.o.ng ph´p ph´t o a a ’ a . . .o.c nhiˆu t´c gia dˆ cˆp v` u.ng dung trong nhiˆu b`i ` a ` ´ ’ ` a a´ e e a e . hiˆn c´c phu thuˆc h`m xˆ p xı d˜ du . e a o a a ’ a . . . . . liˆu ([1,3]). Phu thuˆc h`m xˆ p xı l` mˆt phu thuˆc h`m c´ t´ chˆ t gˆn ´ ’ a o ´ a to´n khai ph´ d˜ e a a u . o a a o a o ınh a ` . . . . . .i mˆt quan hˆ r v` du.o.c dinh ngh˜ nhu. sau. ´ d´ng dˆi v´ o u o o ıa e a . . . . ´ Dinh ngh˜ 1. Phu thuˆc h`m xˆ p xı (Approximate Functional Dependency - AFD) ıa o a a ’ . . . ´ ’ e ´ Cho ε, 0 ε 1, X → Y l` phu thuˆc h`m xˆ p xı nˆu: approx(X → Y ) a o a a ε, v´.i o . . ’ a r v` X → Y d´ng trˆn s}/|r|). u e approx(X → Y ) = 1 (max {|s|, s l` tˆp con cu a a a . ’ . dˆy, |s|, |r| l` sˆ phˆn tu. cua s v` r. ´ ` ’ ’ a a o a O a ´ ’ y . e ’ Trong c´c b`i to´n quan l´ thu.c tˆ, thu.`.ng xay ra c´c nh´m thuˆc t´ c´ su. liˆn quan a a a o a o o ınh o . e . .´.i dang h`m sˆ v´.i nhau (tuyˆn t´ ho˘c phi tuyˆn). Dˆi v´.i c´c tru.`.ng ho.p n`y, ta ´ ´ ´ ´ a o o e ınh a e o a du o . o o a . . ´n phu thuˆc h`m xˆ p xı loai hai - phu thuˆc h`m xˆ p xı liˆn quan dˆn tu.o.ng quan ´ ’ . ´ ’ e ´ x´t dˆ e e o a a o a a e . . . . ´ o ınh ’ o e h`m sˆ gi˜.a c´c thuˆc t´ cua mˆt quan hˆ. a o u a . . . ´ ` a ´ ’ ` a e a e . e a u e a e . Viˆc xˆy du.ng cˆy quyˆt dinh trong khai ph´ d˜. liˆu d˜ du.o.c nhiˆu t´c gia dˆ cˆp dˆn e a . . . . .o.ng ph´p khai ph´ d˜. liˆu nh˘ m kˆt xuˆ t c´c thˆng tin h˜.u ´ tiˆm ˆ n trong ’ ` ´ ´ a ` a trong c´c phu a a a u e a e a o u ıch e . ’ ´ ’ u e o a e . ıa a o e o ınh . a c´c co. so. d˜. liˆu l´.n. Cˆy quyˆt dinh l` mˆt kiˆ u mˆ h` du. b´o (predictive model), ngh˜ a . . . c´c quan s´t vˆ mˆt su. vˆt/hiˆn tu.o.ng t´.i c´c kˆt luˆn vˆ gi´ tri muc tiˆu ` o . a ´ a ` a . . a e . e e e o a e l` mˆt ´nh xa t` a a o a . . . . . . u ´ ´ ’ ’ a e a e . o a u ınh a a a o . cua su. vˆt/hiˆn tu.o.ng. Cˆy quyˆt dinh c´ cˆ u tr´c h` cˆy v` l` mˆt su. tu.o.ng tru.ng cua . . . . . . .o.ng th´.c quyˆt dinh cho viˆc x´c dinh l´.p c´c su. kiˆn d˜ cho. Mˆi n´t cua cˆy chı ˜ u ’ a ´ . ’ u e e a . o a . e a o mˆt phu o . . . ’ ’ . e ’ a a o e e o a u e . u ra mˆt tˆn l´.p ho˘c mˆt ph´p thu. cu thˆ , ph´p thu. n`y chia khˆng gian c´c d˜. liˆu tai n´t o e o . . . . ’ ˜ . ´ ’ o e . ’ ’ d´ th`nh c´c kˆt qua c´ thˆ dat du.o.c cua ph´p thu.. Mˆi tˆp con du.o.c chia ra l` khˆng o a a e o a e a o . . ´ e ’ . ’ a u e ´ o a ` a o a a gian con cua c´c d˜. liˆu du.o.c tu.o.ng u.ng v´.i vˆ n dˆ con cua su. phˆn l´.p. Su. phˆn chia n`y . . . ˜ ´. ˆ ˆ VU DU C THI, TR` N QUANG DIEU A . 180 ’ ´ thˆng qua mˆt cˆy con tu.o.ng u.ng. Qu´ tr` xˆy du.ng cˆy quyˆt dinh c´ thˆ xem nhu. l` o o a ´ a ınh a a a e . o e . . . phˆn l´.p dˆi tu.o.ng ([4–6]). Mˆt cˆy quyˆt dinh c´ thˆ ’ ’ ´ ´ ´ a o o a e . e . o o e mˆt chiˆn thuˆt chia dˆ tri cho su o e a . . . . . ` ng c´c kh´i niˆm n´t v` du.`.ng nˆi c´c n´t trong cˆy. Viˆc nghiˆn c´.u xˆy du.ng ´ a u o o a e e u a mˆ ta b˘ o ’ a a a e u a . . . ´ ´ ’ o a e o a e e a u e cˆy quyˆt dinh mang lai hiˆu qua tˆt cho viˆc l`m trong sach d˜. liˆu, ph´t hiˆn sai s´t v` a e . . . . . . . ’ ´ ´ ’ ’ du.a ra quyˆt dinh ph` ho.p trong t`.ng ho`n canh v` chiˆn lu.o.c cu thˆ cua b`i to´n quan u . e . u a a e a a . . e ’ l´. y ´ ` ´ ´ ’ a e u a e a ıch, e e Phu thuˆc h`m (FDs) d˜ du.o.c nghiˆn c´.u rˆ t nhiˆu trong khi phˆn t´ thiˆt kˆ co. so. o a . . . . liˆu. Phu thuˆc h`m gi˜.a c´c thuˆc t´ quan hˆ cho ph´p x´c dinh ch´ x´c c´c mˆi ´ o a u a o ınh e e a . d˜ e u . ınh a a o . . . . ` ’ u e a a o o a o quan hˆ trong co. so. d˜. liˆu ([2]). C´c r`ng buˆc do phu thuˆc h`m quy dinh trong so. dˆ e . . . . . . ´ ´ . . ’ . e a a e . o o o a o u e quan hˆ tu.o.ng dˆi dˆc lˆp v´.i d˜. liˆu. Viˆc xˆy du.ng cˆy quyˆt dinh su. dung phu thuˆc e . . . . . . ´ ´ ’ o h`m s˜ mang lai hiˆu qua tˆt do c´c t´ chˆ t r`ng buˆc ch˘t cua phu thuˆc h`m. a e e a ınh a a o a ’ o a . . . . . . ´ Trong b`i b´o n`y, ch´ng tˆi tr` b`y vˆ kh´i niˆm phu thuˆc h`m xˆ p xı, phu thuˆc a a a u o ınh a ` e a e o a a ’ o . . . . . ´ ´ ´ ´ h`m xˆ p xı loai hai, mˆt sˆ t´ chˆ t cua phu thuˆc h`m xˆ p xı v` u.ng dung v`o viˆc xˆy a a ’ . o o ınh a ’ o a a ’ a´ a e a . . . . . ´ a e . a u e du.ng cˆy quyˆt dinh trong khai ph´ d˜. liˆu. . . ´ ’ ˆ ` ˆ 2. PHU THUOC HAM XAP XI LOAI HAI . . . Cho r l` mˆt quan hˆ trˆn tˆp thuˆc t´ R = {A1, A2, ...An} trong d´ c´c thuˆc t´ a o e e a o ınh o a o ınh . . . . . .i rac ho˘c liˆn tuc. Dˆi v´.i nh˜.ng thuˆc t´ ’ ´ a e . u o ınh o o o A1 ,A2, ...An c´ thˆ l` thuˆc t´ dinh danh, r` . o e a o ınh . . . . ’ ´ ´ ´ e a a . o e o o a a o e dinh danh, ta tiˆn h`nh thu.c hiˆn ´nh xa tˆ t ca c´c gi´ tri c´ thˆ t´.i mˆt tˆp c´c sˆ nguyˆn e a . . . a ’ a . . . .o.ng liˆn kˆ. ` ` du e e ’ Dinh ngh˜ 2. (Khoang c´ch gi˜.a 2 bˆ gi´ tri trˆn tˆp thuˆc t´ ıa a u o a . e a o ınh) . . . . ’ o y e a a u a e a o V´.i 2 bˆ t1 , t2 ∈ r, ta k´ hiˆu ρ(t1(X), t2(X)) l` khoang c´ch gi˜.a t1 v` t2 trˆn tˆp thuˆc o . . . . .o.c x´c dinh nhu. sau t´ X ⊆ R, du . a . ınh ρ(t1 (X), t2(X)) = max(|t1 (Ai ) − t2 (Ai )|)/max(|t1(Ai ), t2(Ai )|), Ai ∈ X). ´ ´ ´ a o H`m max(x, y) l` h`m chon ra sˆ l´.n nhˆ t trong 2 sˆ x,y. a a a o o . o u ı o Tru.`.ng ho.p max(|t1 (Ai )|, |t2(Ai )|) = 0, t´.c t1 (Ai ) = t2 (Ai ) = 0 th` ta qui u.´.c . |t1(Ai ) − t2 (Ai)|/max(|t1 (Ai )|, |t2(Ai )|) = 0. ’ ´ ´ ´ ’ o a . e a o ınh o e a a o ’ a o o a Khoang c´ch gi˜.a 2 bˆ gi´ tri trˆn tˆp thuˆc t´ c´ thˆ coi l` h`m sˆ cua c´c dˆi sˆ l` a u . . . c´c bˆ gi´ tri cua quan hˆ v` tˆp c´c thuˆc t´ a o a . ’ e a a a o ınh. . . . . ´ t´ chˆ t cua h`m khoang c´ch ρ(t1 (X), t2(X)). ´ ’ ’ Mˆt sˆ ınh a o o a a . ´ ’ ’ ’ Dinh ngh˜ khoang c´ch ρ(t1 (X), t2(X)) nˆu trˆn thoa m˜n c´c t´ chˆ t cua h`m khoang ıa a e e a a ınh a ’ a . c´ch: a 1. ρ(t1(X), t2(X)) u y 0 v´.i t1 , t2 , X t`y ´ o 2. ρ(t1(X), t2(X)) = 0 ⇔ t1 (X) = t2 (X) 3. ρ(t1(X), t2(X)) ρ(t1 (X), t3(X)) + ρ(t3(X), t2(X)) ´ 4. Nˆu X ⊆ Y th` ρ(t1 (X), t2(X)) e ı ρ(t1 (Y ), t2(Y )) 5. ρ(t1(XY ), t2(XY )) = max(ρ(t1(X), t2(X)), ρ(t1(Y ), t2 (Y ))). . ´ ’. ´ ’ ˆ ˆ ˆ ˆ ` ˆ XAY DU NG CAY QUYET DINH SU DUNG PHU THUO C HAM XAP XI . . . . . 181 ´ Dinh ngh˜ 3. (Phu thuˆc h`m xˆ p xı loai hai - Type II Approximate Functional Depenıa o a a ’ . . . . dency) ` ’ ’ o o o o a a . a o a Gia su. X, Y ⊆ R v` v´.i mˆt sˆ δ cho tru.´.c, 0 δ < 1, ta n´i r˘ ng X x´c dinh h`m Y . ´ .c δ (ho˘c n´i r˘ ng X, Y c´ phu thuˆc h`m xˆ p xı loai hai m´.c δ), k´ hiˆu l` X ≈> Y ` ´ a o a o o a a ’ . u y e a m´ u δ . . . . ´ nˆu v´.i moi c˘p bˆ t1 , t2 ∈ r, m` ρ(t1 (X), t2(X)) ε th` ta c˜ng c´ ρ(t1 (Y ), t2 (Y )) ε. e o a ı u o . a o . . ’ ` ` ´ ´ e e e e o a a ’ a o a a ’ . Mˆnh dˆ 1. (Diˆu kiˆn dˆ phu thuˆc h`m xˆ p xı l` phu thuˆc h`m xˆ p xı loai hai) e . . . . . . . approx(X → Y ) l` mˆt phu thuˆc h`m xˆ p xı v´.i dˆ xˆ p xı ε. Phu thuˆc h`m ´ ’ o o a ’ ´ ’ ’ a o o a a o a Gia su . . . . . . ´ ´ a ’ xˆ p xı approx(X → Y ) l` phu thuˆc h`m xˆ p xı loai hai m´.c δ = ε(X ≈>δ Y ) khi v` chı khi a ’ a . o a a ’ . u . u ´.ng v´.i ε v´.i moi c˘p bˆ t1 , t2 ∈ r , m` ρ(t1 (X), t2(X)) ε. o o a . a o . . ´ ` e ´ Ta thˆ y mˆnh dˆ trˆn ho`n to`n d´ng v´.i theo dinh ngh˜ v` c´c t´ chˆ t cua phu a e e a a u o ıa a a ınh a ’ . . . ´ thuˆc h`m xˆ p xı loai hai. o a a ’ . . ’ ´ Thuˆt to´n 1. Kiˆ m tra phu thuˆc h`m xˆ p xı loai hai a a e o a a ’ . . . . .´.c 1: Xˆy du.ng hˆ xˆ p xı m´.c δ cua r: E . ’ a e a ’ u Bu o rδ . . ´ .´.c 2: V´.i mˆi E(δ)i,j ∈ Erδ (v´.i 1 i < j m) lˆn lu.o.t kiˆ m tra diˆu kiˆn ˜ ’ ` ` e e Bu o o o o a e . . X ⊆ E(δ)i,j ) ⇒ (Y ⊆ E(δ)i,j ). ’ ` ´ ´ a + Nˆu c´ tˆ n tai X ⊆ E(δ)i,j v` Y e o o . a E(δ)i,j th` d`.ng viˆc kiˆ m tra v` kˆt luˆn r khˆng ı u e e a e o . . .c δ. ´ ’ thoa phu thuˆc h`m xˆ p xı loai hai m´ o a a ’ . u . . ´ ` ´ ’ a + Nˆu v´.i moi E(δ)i,j ∈ Erδ thoa m˜n diˆu kiˆn (X ⊆ E(δ)i,j ) ⇔ (Y ⊆ E(δ)i,j ) th` kˆt e o e e ı e . . .c δ. ´ ’ luˆn r thoa phu thuˆc h`m xˆ p xı loai hai m´ a o a a ’ . u . . . ´ ´ ’ . a e . o a a ’ . Thuˆt to´n 2. Xˆy du.ng cˆy quyˆt dinh su. dung phu thuˆc h`m xˆ p xı loai hai a a a . . . . . (Examples) v` x´c dinh c´c phu thuˆc h`m xˆ p xı loai hai du.o.c t´ ˜ ` ´ ’ . ’ a a . Dˆu v`o: Mˆu thu a a a a o a a . ınh . . . liˆu mˆu. ˜ trˆn tˆp d˜ e e a u . a . ` ´ e o a Dˆu ra: Cˆy quyˆt dinh du.a trˆn phu thuˆc h`m. a a e . . . . .´.c 1. X´c dinh nhiˆu cua mˆu thu. (M ajorityClass(Examples )). ˜ ˜ ’ ’ a . e a Bu o i .´.c 2. Chon c´c phu thuˆc h`m xˆ p xı c´ m´.c dˆ nhiˆu trong m´.c xˆ p xı δ, ˜ ´ ’ o u o ´ e u a ’ Bu o o a a . . a . . approx(X → Y ) δ. .´.c 3. Kiˆ m tra phu thuˆc h`m xˆ p xı loai hai cho tˆp phu thuˆc h`m xˆ p xı t` du.o.c o. ’ ´ ´ e o a a ’ . a o a a ’ ım Bu o . . . . . . ’ .´.c 2 (X ≈>δ Y ). Bu o ´ ´ ´ ’ a + Chon phu thuˆc h`m xˆ p xı loai hai c´ m´.c xˆ p xı nho nhˆ t (X ≈>min(δ) Y ) o a a ’ . o u a ’ . . . ´ ´ ´ o o a + Tao cˆy quyˆt dinh v´.i gˆc l` phu thuˆc h`m xˆ p xı v`.a chon a e . o a a ’ u . . . . DT = BuildDecisionT ree(Examplei, X ≈>min(δ) Y, M ajorityClass(examples)). ˜ ´ ’ a o a . o a a ’ ınh + V´.i mˆi gi´ tri vi cua tˆp phu thuˆc h`m xˆ p xı, t´ o . . . ˜ ’ • Mˆu thu. Examplei = {Ki ⊆ Example v´.i X ≈>minδ Y = vi } a o • Subtree = BuildDecisionT ree(Examplei, X ≈>minδ Y, M ajorityClass(examples)) a a • Thˆm mˆt nh´nh Subtree v`o cˆy v´.i nh˜n l` vi e o a a a o . ´ ’ ’ ’ o a a e V´ du 1. Gia su. ta c´ tˆp huˆ n luyˆn nhu. sau (Bang 1) ı . . . ’ xˆy du.ng c´c phu thuˆc h`m xı loai hai v´.i m´.c xˆ p xı δ = 0.05 nhu. ´ ’ . Ch´ng ta c´ thˆ a u o e u a ’ a o a o . . . sau. ˜ ´. ˆ ˆ VU DU C THI, TR` N QUANG DIEU A . 182 ’ ´ ´ Ta thˆ y gi˜.a thuˆc t´ Tuˆ i, Hˆ sˆ lu.o.ng c´ mˆi tu.o.ng quan v´.i ch´.c danh. V´.i a u o ınh o e o o o o u o . . ´ .i phu thuˆc h`m xˆ p xı: ’ ´ ` ´ o a a ’ e e o o δ = 0.05 ta kiˆ m tra diˆu kiˆn dˆi v´ e . . . ’ Bang 1 STT ’ Tuˆ i o HSL Ngach CC . e ınh Nghiˆn c´.u viˆn ch´ e u .u viˆn ch´ e ınh Nghiˆn c´ e u e Nghiˆn c´.u viˆn e u e Nghiˆn c´.u viˆn e u e ınh Nghiˆn c´.u viˆn ch´ e u .u viˆn e Nghiˆn c´ e u e Nghiˆn c´.u viˆn e u .u viˆn e Nghiˆn c´ e u e Nghiˆn c´.u viˆn e u HV Ho`n th`nh a a cˆng viˆc o e . C´ o C´ o C´ o Khˆng o C´ o Khˆng o C´ o Khˆng o Khˆng o ´ Tiˆn s˜ khoa hoc e ı . ´ Tiˆn s˜ e ı ´ Tiˆn s˜ e ı Thac s˜ . ı ´ Tiˆn s˜ e ı Thac s˜ . ı ´ Tiˆn s˜ e ı Thac s˜ . ı Thac s˜ . ı ’ ’ o o e o o e o V´.i c˘p h`ng 1, 2 ta c´ ρ(t1 (Tuˆ i, Hˆ sˆ lu.o.ng), t2 (Tuˆ i, Hˆ sˆ lu.o.ng)) = 0 < 0.05. o a a . . ´ . ´ .o.c ρ(t1 (C´ thˆ giao nhiˆm vu), t2 (C´ thˆ giao nhiˆm vu)) = 0 < 0.05. ’ ’ o e e o e e Ta c˜ng t´ du . u ınh . . . . .o.ng tu. ta c˜ng kiˆ m tra dˆ d`ng v´.i c´c cˆt c`n lai, vˆy ta c´ phu thuˆc h`m Tuˆ i, ’ ’ ˜ a Tu u e e o a o o . a o o a o . . . . . .o.ng ≈> ’ o e e hˆ sˆ lu e o 0.05 C´ thˆ giao nhiˆm vu. . . . ´ ´ ´ ´ o a ınh a a e Sau khi t` tˆ t ca c´c phu thuˆc h`m xˆ p xı ph` ho.p v´.i qu´ tr` xˆy du.ng cˆy quyˆt ım a ’ a o a a ’ u . . . . ’ xˆy du.ng du.o.c cˆy quyˆt dinh nhu. sau (H` 1). ´ . dinh, ta c´ thˆ a o e e ınh . . . a 1 2 3 4 5 6 7 8 9 >40 >40 >40 >40 30-40 30-40