Một cách tiếp cận để xấp xỉ dữ liệu trong cơ sở dữ liệu mờ

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

Thêm vào BST

Báo xấu

40
lượt xem 4
download

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

In this paper, we introduced a method to approximate data on domain of fuzzy attributes in relation of fuzzy databases based hedge algebra. Because, domain of fuzzy attributes can except values are number, linguistic values, thus we have to effect and simply on method to approximate data.

Chủ đề:

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

Lưu

Nội dung Text: Một cách tiếp cận để xấp xỉ dữ liệu trong cơ sở dữ liệu mờ

’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.23, S.2 (2007), 110–121 ı e e . . a ` . ’ ´ ´ ’ ˜. ˆ ˆ ´ ˆ ˆ ˆ ˆ MOT CACH TIEP CAN DE XAP XI DU LIEU . . . . ’ . ˜. ˆ . ` TRONG CO SO DU LIEU MO . ˜ ` ˜ ˆ ´ ˆ ˆ ˆ ` NGUYEN CAT HO1 , NGUYEN CONG HAO2 1 Viˆn e . Cˆng nghˆ thˆng tin, Viˆn Khoa hoc v` Cˆng nghˆ Viˆt Nam o e o e e e . . . a o . . 2 .`.ng Dai hoc Khoa hoc Huˆ ´ Tru o e . . . Abstract. In this paper, we introduced a method to approximate data on domain of fuzzy attributes in relation of fuzzy databases based hedge algebra. Because, domain of fuzzy attributes can except values are number, linguistic values, thus we have to eﬀect and simply on method to approximate data. ´ ´ ` T´m t˘t. B`i b´o tr` b`y mˆt phu.o.ng ph´p xˆp xı d˜. liˆu trˆn miˆn tri thuˆc t´ m`. cua mˆt o a a a ınh a o a a ’ u e e e o ınh o ’ o . . . . . ’ ´ ’ u e ’ ’ ı ` ’ e o . e o ınh o o e a quan hˆ trong co. so. d˜. liˆu m`. du.a trˆn dai sˆ gia tu.. Bo.i v` miˆn tri cua thuˆc t´ m`. c´ thˆ l` e o . . . . . ` o o ´ ´ o u a gi´ tri sˆ , gi´ tri ngˆn ng˜., do d´ ch´ ng ta cˆn c´ mˆt phu.o.ng ph´p xˆp xı d˜. liˆu mˆt c´ch do.n a . o a . o u a a ’ u e o a . . . ’ ’ gian v` hiˆu qua. a e . ´ ˘ ˆ ˆ E 1. DAT VAN D` . ` a ’ ’ u e o a e a a o a e u a a Co. so. d˜. liˆu m`. d˜ du.o.c nhiˆu t´c gia trong v` ngo`i nu.´.c quan tˆm nghiˆn c´.u v` d˜ . . .ng kˆt qua d´ng kˆ ([1–5, 10, 12]). C´ nhiˆu c´ch tiˆp cˆn kh´c nhau nhu. c´ch tiˆp ´ ´ ` ´ . ’ a e a e c´ nh˜ o u e’ o e a e a a . ([1]), theo l´ thuyˆt kha n˘ng ([4]) Prade v` Testemale n˘m 1983, ´ ´ . ’ a y e a a cˆn theo l´ thuyˆt tˆp m` a y e a o . ` ´ ´ ´ ´ . quan hˆ tu.o.ng du.o.ng ([2, 3, 5])... Tˆ t ca c´c c´ch tiˆp cˆn trˆn nh˘ m muc d´ n˘m b˘t v` xu. e a ’ a a e a e a ıch a a a ’ . . ’ l´ mˆt c´ch thoa d´ng trˆn mˆt luˆn diˆ m n`o d´ c´c thˆng tin khˆng ch´ x´c (unexact), y o a a e o a e’ a o a o o ınh a . . . ´c ch˘n (uncertainty) hay nh˜.ng thˆng tin khˆng dˆy du (incomplete). Do su. da ´ ` ’ a o o khˆng ch˘ o a a u . ’ ´ ’ a nh˜.ng loai thˆng tin n`y nˆn ta g˘p rˆ t kh´ kh˘n trong biˆ u thi ng˜. ngh˜ v` thao o a e a a o a e ıa a dang cu u . . . u . t´c v´.i ch´ng. a o u ` a ´ ’ ’ e e u a a o Trong th`.i gian qua, dai sˆ gia tu. du.o.c nhiˆu t´c gia nghiˆn c´.u trong [6–8] v` d˜ c´ o . . o .ng u.ng dung d´ng kˆ , d˘c biˆt trong lˆp luˆn xˆ p xı v` trong mˆt sˆ b`i to´n diˆu khiˆ n. ’ a ´ nh˜ ´ u a e . e a a a ’ a o o a a ` e e’ . . . . . ´ .u vˆ co. so. d˜. liˆu m`. theo c´ch tiˆp cˆn dai sˆ gia tu. l` mˆt hu.´.ng ´ . ´ ’ u e ’ a o V` vˆy, viˆc nghiˆn c´ ` ı a e e u e o a e a o . . . . . o .i cˆn quan tˆm giai quyˆt. ´ ’ m´ ` o a a e ´ ’. ˆ 2. DAI SO GIA TU . ’ ´ ´ . ` ` o ’ Dˆ xˆy du.ng c´ch tiˆp cˆn dai sˆ gia tu., trong phˆn n`y s˜ tr` b`y tˆ ng quan vˆ mˆt e’ a a e a a a e ınh a o e . . o . . ban cua dai sˆ gia tu. v` kha n˘ng biˆ u thi ng˜. ngh˜ du.a v`o cˆ u tr´c cua dai sˆ ´ ´ ´ ´ ’ ’ a ’ a e’ ıa . a a u ’ sˆ n´t co ’ o e . u . o . o ´ ınh a ’ ´ ´ ’., h`m dinh lu.o.ng ng˜. ngh˜ v` mˆt sˆ t´ chˆ t cua dai sˆ gia tu.. ’ gia tu a u ıa a o o . . . . o ` ´ ` n ngˆn ng˜. cua biˆn chˆn l´ TRUTH gˆ m c´c t`. sau: ’ e a y o a u Ta x´t miˆ e e o u dom(TRUTH) = {true, false, very true, very false, more-or-less true, more-or-less false, ’ ´ ´ ’ ˜. ˆ ˆ ´ ˆ ˆ ˆ ˆ MOT CACH TIEP CAN DE XAP XI DU LIEU . . . 111 possibly true, possibly false, approximately true, approximately false, little true, little false,very ´ ’ a u o a a u possibly true,very possibly false...}, trong d´ true, false l` c´c t`. nguyˆn thuy, c´c t`. nhˆ n e a ’ (mordiﬁer hay intensiﬁer) very, more-or-less, possibly, approximately, little goi l` c´c gia tu. . a a ’ e’ ` n ngˆn ng˜. T = dom(TRUTH) c´ thˆ biˆ u thi nhu. mˆt dai sˆ AH = ´ (hedges). Khi d´ miˆ o e o . o o e o u . . ` ’ (X, G, H, ), trong d´ G l` tˆp c´c t`. nguyˆn thuy du.o.c xem l` c´c phˆn tu. sinh. H l` tˆp e a a a ’ a a o a a a u . . . . du.o.c xem nhu. l` c´c ph´p to´n mˆt ngˆi, quan hˆ (trˆn c´c t`. (c´c kh´i niˆm m`.) ’ a a e a o o e e a u a a e o c´c gia tu a . . . . ’ l` quan hˆ th´. tu. du.o.c “cam sinh” t`. ng˜. ngh˜ tu. nhiˆn. V´ du du.a trˆn ng˜. ngh˜ c´c a e u . u u ıa . e ı . . e u ıa, a . . quan hˆ th´. tu. sau l` d´ng: false true, more true very true nhu.ngvery false more false, e u . a u . ’ a possibly true true nhu.ng false possibly false... Tˆp X du.o.c sinh ra t`. G bo.i c´c ph´p a u e . . . vˆy mˆi phˆn tu. cua X s˜ c´ dang biˆ u diˆn x = h h ˜ ’ ˜ ` o a ’ ’ e o . e e t´ trong H . Nhu a ınh n n−1 ...h1x, x ∈ G. . ´ ` ` ´ Tˆp tˆ t ca c´c phˆn tu. du.o.c sinh ra t`. mˆt phˆn tu. x du.o.c k´ hiˆu l` H(x). Nˆu G c´ d´ng a a ’ a a ’ u o a ’ y e a e o u . . . . . . nguyˆn thuy m`., th` mˆt du.o.c goi l` phˆn tu. sinh du.o.ng k´ hiˆu l` c+ , mˆt goi l` ’ o e ı o a ’ y e a o . a hai t` u . . . a ` . . . sinh ˆm k´ hiˆu l` c− v` ta c´ c− < c+ . Trong v´ du trˆn true l` du.o.ng c`n false ` phˆn tu a ’ o a y e a a o ı . e a . ´ ’ o ´ o o a l` ˆm. Cho dai sˆ gia tu. X = (X, G, H, ), v´.i G = {c+ , c− }, trong d´ c+ v` c− tu.o.ng u.ng aa . . sinh du.o.ng v` ˆm, X l` tˆp nˆn. H = H + ∪ H − v´.i H − = {h , h , ..., h } v` l` phˆn tu a ` a ’ aa a a ` e o a 1 2 p . + = {h H a p+1 , ..., hp+q}, h1 > h2 > ... > hp v` hp+1 < ... < hp+q . ´ u ıa ’ e Dinh ngh˜ 2.1. ([9]) f : X → [0, 1] goi l` h`m dinh lu.o.ng ng˜. ngh˜ cua X nˆu ∀h, ∈ H + ıa . . a a . . ho˘c ∀h, k ∈ H − v` ∀x, y ∈ X, ta c´: a a o . f (hx) − f (x) f (hy) − f (y) = . f (kx) − f (x) f (ky) − f (y) ´ ’ a a V´.i dai sˆ gia tu. v` h`m dinh lu.o.ng ng˜. ngh˜ ta c´ thˆ dinh ngh˜ t´ m`. cua mˆt o . o u ıa o e’ . o ıa ınh o ’ . . . .. Cho tru.´.c h`m dinh lu.o.ng ng˜. ngh˜ f cua X . X´t bˆ t k` x ∈ X. T´ m`. ´ ’ kh´i niˆm m` a e o o a u ıa e a y ınh o . . . ` ’ o ınh ’ a o a cua x khi d´ du.o.c do b˘ ng du.`.ng k´ cua tˆp f (H(x)) ⊆ [0, 1]. . . a . H` 1. T´ m`. cua gi´ tri True ınh ınh o ’ ´ ’ a Dinh ngh˜ 2.2. [9] H`m f m : X → [0, 1] du.o.c goi l` dˆ do t´ m`. trˆn X nˆu thoa m˜n ıa a ınh o e e . . . a o . e e c´c diˆu kiˆn sau: a ` . (1) f m(c− ) = W > 0 v` f m(c+ ) = 1 − W > 0 a ı (2) V´.i c ∈ {c− , c+} th` o p+q f m(hi c) = f m(c) i=1 f m(hy) f m(hc) f m(hx) (3) V´.i moi x, y ∈ X, ∀h ∈ H, o = = , v´.i c ∈ {c− , c+ } o . f m(x) f m(y) f m(c) ˜ ` ˜ ˆ ´ ˆ ˆ ˆ ` NGUYEN CAT HO, NGUYEN CONG HAO 112 ´ ngh˜ l` tı sˆ n`y khˆng phu thuˆc v`o x v` y , du.o.c k´ hiˆu l` µ(h) goi l` dˆ do t´ m`. ıa a ’ o a o o a a ınh o . . . ı e a . . a o . ’ ’ (fuzziness measure) cua gia tu. h. ` e Mˆnh dˆ 2.1. [9] e . (1) f m(hx) = µ(h)f m(x), v´.i moi x ∈ X o . p+q (2) o f m(hi c) = f m(c), trong d´ c ∈ {c− , c+ } i=1 p+q f m(hi x) = f m(x), ∀x ∈ X (3) i=1 p p+q µ(hi ) = α v` a (4) µ(hi ) = β , v´.i α, β > 0 v` α + β = 1. o a i=p+1 i=1 Dinh ngh˜ 2.3. [9] H`m Sign : X → {−1, 0, 1} l` mˆt ´nh xa du.o.c dinh ngh˜ mˆt c´ch ıa a a o a ıa o a . . . . . . . sau, v´.i moi h, h ∈ H : o dˆ qui nhu e . . ´ (1) Sign(c−) = −1 v` Sign(hc−) = +Sign(c−) nˆu hc− < c− a e −) = −Sign(c−) nˆu hc− > c− ´ Sign(hc e + ´ Sign(c ) = +1 v` Sign(hc+) = +Sign(c+) nˆu hc+ > c+ a e ´ Sign(hc+) = −Sign(c+) nˆu hc+ < c+ e ´ ´ (2) Sign(h hx) = −Sign(hx) nˆu h l` negative dˆi v´.i h v` h hx = hx e a a o o .i h v` h hx = hx ´ ´ a o o (3) Sign(h hx) = +Sign(hx) nˆu h l` positive dˆi v´ e a ´ (4) Sign(h hx) = 0 nˆu h hx = hx. e ’ ’ ’ o o a a a . Dinh ngh˜ 2.4. [9] Gia su. cho tru.´.c dˆ do t´ m`. cua c´c gia tu. µ(h), v` c´c gi´ tri ıa ınh o ’ a . . . cua c´c phˆn tu. sinh f m(c− ), f m(c+) v` w l` phˆn tu. trung h`a. H`m dinh ` dˆ do t´ m` ’ a o ınh o a ’ a a ` a ’ o a . . .o.ng ng˜. ngh˜ (quantitatively semantic function) ν cua X du.o.c xˆy du.ng nhu. sau v´.i ’ u ıa a o lu . . . x = him ...hi2 hi1 c: (1) ν(c− ) = W − α.f m(c− ) v` ν(c+ ) = W + α.f m(c+) a (2) ν(hj x) = p 1 f m(hi x)− 1−Sign(hj x)Sign(h1hj x)(β −α) f m(hj x) ν(x)+Sign(hj x)× 2 i=j v´.i 1 o j p, v` a j ν(hj x) = ν(x)+Sign(hj x)× f m(hi x)− i=p+1 1 1−Sign(hj x)Sign(h1hj x)(β−α) f m(hj x) 2 v´.i j > p. o ’ ´ ´ ’ ˜. ˆ ˆ ´ ˆ ˆ `. ˆ ˆ 3. MOT CACH TIEP CAN DE XAP XI DU LIEU MO . . . ` ´ a o e’ a ’ u e e e Trong muc n`y, s˜ tr` b`y mˆt phu.o.ng ph´p m´.i dˆ xˆ p xı d˜. liˆu trˆn miˆn tri cua a e ınh a o . . ’ . . . trong quan hˆ cua co. so. d˜. liˆu m`.. Viˆc d´nh gi´ d˜. liˆu trˆn miˆn tri thuˆc ` ’ u e thuˆc t´ m` o ınh o e ’ o e a e e o a u e . . . . . . . . cua quan hˆ trong co. so. d˜. liˆu m`. theo c´ch tiˆp cˆn dai sˆ gia tu. du.o.c xˆy du.ng ´ ´ a ’ ’ u e ’ t´ m` ınh o e o a e . . o . . . a . ´ ’ e a ınh o ’ a a . a . o u a o du.a trˆn phˆn hoach t´ m`. cua c´c gi´ tri trong dai sˆ gia tu. (gi´ tri ngˆn ng˜.). Nhu. vˆy, . . . . .o.ng u.ng v´.i thuˆc t´ m`. Ai v` xem nhu. mˆt dai sˆ gia ´ . ´ nˆu goi Dom(Ai ) l` miˆn tri tu e a ` e ´ o o ınh o a o . o . . . ´ ’ ı a a a a . o ’ a tu. th` khi d´ Dom(Ai ) = Num(Ai) ∪ LV (Ai), v´.i Num(Ai ) l` tˆp c´c gi´ tri sˆ cua Ai v` o o . . cua A . Dˆ xˆ p xı d˜. liˆu, ta x´t hai tru.`.ng ho.p sau. ´ e’ a ’ u e LV (Ai ) l` tˆp c´c gi´ tri ngˆn ng˜ ’ a a a a . o u e o i . . . ’ ´ ´ ’ ˜. ˆ ˆ ´ ˆ ˆ ˆ ˆ MOT CACH TIEP CAN DE XAP XI DU LIEU . . . 113 ` 3.1. Miˆn tri cua thuˆc t´ trong quan hˆ l` gi´ tri ngˆn ng˜. e o ınh e a a . o u . ’ . . Trong tru.`.ng ho.p n`y, ch´ng ta di xˆy du.ng c´c phˆn hoach du.a v`o t´ m`. cua c´c o a u a a a ınh o ’ a a . . . . gi´ tri ngˆn ng˜.. a . o u ´ ’ ’ a o e V` t´ m`. cua c´c gi´ tri trong dai sˆ gia tu. l` mˆt doan con cua [0,1] cho nˆn ho c´c ı ınh o ’ a a . . o . . a . . vˆy cua c´c gi´ tri c´ c`ng dˆ d`i s˜ tao th`nh phˆn hoach cua [0,1]. Phˆn ’ a ’ a . o u doan con nhu a o a e . a a a . . . . .ng v´.i c´c gi´ tri c´ dˆ d`i t`. l´.n ho.n s˜ min ho.n v` khi dˆ d`i l´.n vˆ han th` dˆ hoach u o a a . o o a u o e . a o . ı o o a o . ´ . . . ` ` ’ d`i cua c´c doan trong phˆn hoach giam dˆn vˆ 0. a ’ a a a e . . ˜ o y e Dinh ngh˜ 3.1. Goi f m l` dˆ do t´ m`. trˆn DSGT X . V´.i mˆi x ∈ X, ta k´ hiˆu ıa a o ınh o e o . . . . I(x) ⊆ [0, 1] v` |I(x)| l` dˆ d`i cua I(x). a a o a ’ . ´ ´ ’ Mˆt ho c´c ξ = {I(x) : x ∈ X} du.o.c goi l` phˆn hoach cua [0,1] g˘n v´.i x nˆu: o . a a o e . . . a a . +), I(c−)} l` phˆn hoach cua [0,1] sao cho|I(c)| = f m(c), v´.i c ∈ {c+ , c−}. ’ (1) {I(c a a o . .o.c dinh ngh˜ v` |I(x)| = f m(x) th` {I(hix) : i = 1..p + q} du.o.c ´ (2) Nˆu doan I(x) d˜ du . . e a ıa a ı . . ’ a I(x) sao cho thoa m˜n diˆu kiˆn |I(hix)| = f m(hi x) v` |I(hix)| ’ a ` dinh ngh˜ l` phˆn hoach cu ıa a a e e a . . . ´ e ınh. l` tˆp s˘p th´. tu. tuyˆn t´ a a a u . . ´ ´ ` Tˆp {I(hix)} du.o.c goi l` phˆn hoach g˘n v´.i phˆn tu. x. Ta c´ a a o a ’ o . . . a a . p+q |I(hix)| = |I(x)| = i=1 f m(x). a o a Dinh ngh˜ 3.2. Cho P k = {I(x) : x ∈ X k } v´.i X k = {x ∈ X : |x| = k} l` mˆt phˆn hoach. ıa o . . . ´ Ta n´i r˘ ng u xˆ p xı ν theo m´.c k trong P k du.o.c k´ hiˆu u ≈k ν khi v` chı khi I(u) v` I(v) o ` a a ’ u y e a ’ a . . ’ c`ng thuˆc mˆt khoang trong P k . C´ ngh˜ l` ∀u, v ∈ X , u ≈k v ⇔ ∃∆k ∈ P k : I(u) ⊆ ∆k u o o o ıa a . . v` I(v) ⊆ ∆k . a ´ ’ X V´ du 3.1. Cho dai sˆ gia tu. X = (X , G, H, ), trong d´ H = H + ∪ H − , H + = {ho.n, ı . o . o ´t}, ho.n < rˆ t, H − = {´ kha n˘ng}, ´ > kha n˘ng, G = { tre , gi`} . Ta c´ P 1 = {I (tre), ´ ’ a ’ a ’ a ’ rˆ a a ıt, ıt o .o.ng tu., P 2 = {I (ho.n tre ), I (rˆ t tre ), I (´ tre ), I (kha ´ ’ ’ ’ I (gi`)} l` mˆt phˆn hoach cua [0, 1]. Tu a a o a a ’ ıt ’ . . . .n gi`), I (rˆ t gi`), I (´ gi`), I (kha n˘ng gi`)} l` phˆn hoach cua [0, 1]. ´ ’ a ’ ’ a a a ıt a a a a n˘ng tre ), I (ho a . ´ ’ ’ ’ V´ du 3.2. Theo V´ du 3.1, P 1 l` phˆn hoach cua [0, 1]. Ta c´ ho.n tre ≈1 rˆ t tre v` ı . ı . a a o a ı . 1 1 .n tre ) ⊆ ∆1 v` I (rˆ t tre ) ⊆ ∆1 .P 2 l` phˆn hoach cua [0, 1], ta ´ ’ ’ ’ ’ a a a a ∃∆ = I (tre ) ∈ P m` I (ho a . ´ ´ c´ ´ gi` ≈2 rˆ t ´ gi` v` ∃∆2 = I (´ gi` )∈ P 2 m` I (´ gi`) ⊆ ∆2 v` I (rˆ t ´ gi`) ⊆ ∆2. o ıt a a ıt a ı ıt a a ıt a a a ıt a a o a Dinh ngh˜ 3.3. X´t P k = {I(x) : x ∈ X k } v´.i X k = {x ∈ X : |x| = k} l` mˆt phˆn hoach. ıa e o . . . ´ Ta n´i r˘ ng u khˆng xˆ p xı v m´.c k trong P k du.o.c k´ hiˆu u =k v khi v` chı khi I(u) v` o ` a o a ’ u y e a ’ a . . k k k ’ I(v) khˆng c`ng thuˆc mˆt khoang trong P . C´ ngh˜ l` ∀u, v ∈ X , u =k v ⇔ ∀∆ ∈ P : o u o o o ıa a . . k ho˘c I(v) ⊂ ∆k . I(u) ⊂ ∆ a . ´ ’ ’ ’ a ’ V´ du 3.3. Theo V´ du 3.1, P 2 = {I (ho.n tre ), I (rˆ t tre ), I (´ tre ), I (kha n˘ng tre ), I (ho.n ı . ı . a ıt ’ ´ a ´ ’ a ’ gi`), I (rˆ t gi`), I (´ gi`), I (kha n˘ng gi`)} l` phˆn hoach cua [0, 1]. Chon ∆2 = I (rˆ t a a ıt a a a a a . . 2 , ta c´ I (´ tre ) ⊂ ∆2 v` I (rˆ t tre ) ⊆ ∆2 (1’). M˘c kh´c v´.i moi ∆2 = I (´ tre ) ´ ’ ’ ıt ’ tre )∈ P o ıt ’ a a a a o . . 2 2 2 . (1’) v` (2’) ta suy ra ´ tre = rˆ t tre . ´ ´ ∈ P ta c´ I (´ tre ) ⊂ ∆ v` I (rˆ t tre ) ⊂ ∆ (2’) . T` o ıt ’ a a ’ u a ıt ’ 2 a ’ a o a Dinh ngh˜ 3.4. X´t P k = {I(x) : x ∈ X k } v´.i X k = {x ∈ X : |x| = k} l` mˆt phˆn ıa e o . . .o.ng ng˜. ngh˜ trˆn X . Ta n´i r˘ ng u nho ho.n v m´.c k trong P k ` ’ hoach. Goi ν l` h`m dinh lu . a a u ıa e o a u . . . ’ du.o.c k´ hiˆu u