Khai phá dữ liệu - Chương 2 LUẬT KẾT HỢP

Ch

ng 2

ươ

Ậ

Ế Ợ

LU T K T H P (Association Rules)

1

ữ ữ

• Phân Phân tích vi c ệ tích vi c ệ c a ủ mua hàng c a ủ mua hàng khách hàng b ng ằ khách hàng b ng ằ cách tìm ra nh ng ữ cách tìm ra nh ng ữ “m i k t h p” gi a ố ế ợ “m i k t h p” gi a ố ế ợ nh ng m t hàng ặ ữ nh ng m t hàng ữ ặ mà khách đã mua. mà khách đã mua.

toán toán

• Bài c ượ đ Bài c ượ đ thu c ộ Agrawal thu c ộ Agrawal nhóm nghiên c u ứ nhóm nghiên c u ứ c a IBM đ a ra ư ủ c a IBM đ a ra ư ủ vào năm 1994. vào năm 1994.

Bài toán phân tích gi Bài toán phân tích gi hàng hàng ỏ ỏ

2

01/18/13

www.lhu.edu.vn

Lu t k t h p: C s Lu t k t h p: C s

ậ ế ợ ậ ế ợ

ơ ở ơ ở

ng quan, hay các c u

ầ

ố ẫ

ố ế ợ

ự ươ

ậ ơ ở ữ ệ

ữ

– Tìm t n s m u, m i k t h p, s t ấ ng trong các c s d trúc nhân qu gi a các t p đ i t ơ ở ữ ố ượ ả ữ li u giao tác, c s d li u quan h , và nh ng kho thông tin ệ ệ khác.

Khai phá lu t k t h p: Khai phá lu t k t h p: ậ ế ợ ậ ế ợ

ế t th c ự ễ ể c: c:

ữ ệ ượ d hi u c: Tính hi u đ ể c: Tính hi u đ ượ ể ượ Cung c p thông tin thi Tính s d ng đ ấ ử ụ Tính s d ng đ ượ ử ụ Tính hi u qu : ệ Tính hi u qu : ệ ả Đã có nh ng thu t toán khai thác hi u ậ ả

quả

ị

t k ế ế

– Phân tích bán hàng trong siêu th , cross-marketing, thi catalog, loss-leader analysis, gom c m, phân l p, ...

ụ

ớ

Các ng d ng: Các ng d ng: ứ ứ ụ ụ

3

Lu t k t h p: C s Lu t k t h p: C s

ậ ế ợ ậ ế ợ

ơ ở ơ ở

bia [0.5%, 60%]

– khăn (cid:222) – mua:khăn (cid:222)

mua:bia [0.5%, 60%]

ng h p. Khăn và

– “N uế mua khăn thì mua bia trong 60% tr

ợ

bia đ

c mua chung trong 0.5% dòng d li u."

ượ

ườ ữ ệ

Đ nh d ng th hi n đ c tr ng cho các lu t k t h p: ư Đ nh d ng th hi n đ c tr ng cho các lu t k t h p: ư ậ ế ợ ậ ế ợ ể ệ ể ệ ạ ạ ặ ặ ị ị

mua(x, “bia") [0.5%, 60%]

ể ể ễ ễ

đi mể (x, "A") [1%, 75%]

Các bi u di n khác: Các bi u di n khác: – mua(x, “khăn") (cid:222) – khoa(x, "CS") ^ học(x, "DB") (cid:222)

4

Lu t k t h p: C s Lu t k t h p: C s

ậ ế ợ ậ ế ợ

ơ ở ơ ở

khăn (cid:222) bia [0.5%, 60%]

1 2 3 4 ườ

“N UẾ mua khăn THÌ mua bia trong 60% tr trên 0.5% dòng d li u" ng h p ợ ữ ệ

ế ế ề ế ề ế

ề, v trái lu t Ti n đề ậ Ti n đề ề ả, v ph i lu t M nh đ k t qu ậ ệ M nh đ k t qu ả ệ Support, đ h tr / ng h (“trong bao nhiêu ph n trăm d ộ ỗ ợ ủ ữ Support li u thì nh ng đi u ữ ệ v trái và v ph i cùng x y ra") ả ầ ả ế

ế ả ả ộ ề ở ế ế

kh năng v ph i x y ra") Confidence, đ m nh (“n u v trái x y ra thì có bao nhiêu Confidence ả ộ ạ ế ả ả

5

2.1 C¸c kh¸I niÖm

Cho I = {I1 , I2 , . . . , Im } lµ tËp c¸c ®¬n vÞ dỮ liÖu. Cho D lµ tËp c¸c giao t¸c, mçi giao t¸c T lµ tËp c¸c ®¬n vÞ d dữ liÖu sao cho T ˝ I

ÑÞnh nghÜa 1: Ta gäi giao t¸c T chøa X, víi X lµ tËp c¸c

®¬n vÞ dữ liÖu cña I, nÕu X ˝ T

d¹ng X ﬁ ÑÞnh nghÜa 2: Mét luËt kÕt hîp lµ mét phÐp suy diÔn cã I, Y (cid:204) I vµ X˙ Y = ˘

Y, trong ®ã X (cid:204) ÑÞnh nghÜa 3: Ta gäi luËt X ﬁ

Y cã møc x¸c nhËn(support) lµ s trong tËp giao t¸c D, nÕu cã s% giao t¸c trong D chøa X¨ Y. Ký hiÖu: Supp(X ﬁ Y) = s

6 2.1 C¸c kh¸I niÖm (Tieáp)

ÑÞnh nghÜa 4:Ta gäi luËt X ﬁ

Y lµ cã ®é tin cËy c

(Confidence) trªn tËp giao t¸c D, Ký hiÖu: c= Conf(X ﬁ

Y) = Supp(X ﬁ Y)/Supp(X)

NhËn xÐt: C¸c x¸c nhËn vµ ®é tin cËy chÝnh lµ c¸c x¸c

suÊt sau:

Supp(X ﬁ

Y)= P(X¨ Y) : X¸c suÊt cña X¨ Y trong D

Conf(X ﬁ

Y) = P(Y/X): X¸c suÊt cã ®iÒu kiÖn

ÑÞnh nghÜa 5: Cho

vµ

tríc Min_Supp=s0

Y lµ xaû ra nÕu tháa:

7 Min_Conf=c0 Ta gäi luËt X ﬁ Supp(X ﬁ

Y) > s0 vµ Conf(X ﬁ

Y)>c0

Ví d 1: Xét CSDL sau

ụ

C¸c ®¬n vÞ d liÖu

D E

Ngµy D1

D E

E D

C D E

D E D

T_ID t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12

8 D )= 2/6=33.3%

F) = 2/7=28.5%

Ta cã: Supp(Aﬁ D)=5/12=41.66%, Conf(Aﬁ D)=5/7 D)=2/12=17%, Conf(B ﬁ Supp(B ﬁ F) = 2/12 vµ Conf(D ﬁ Supp(D ﬁ Supp(Fﬁ D)=2/12 vµ Conf(Fﬁ D)=2/5 Supp(ACﬁ E)=17% Conf(ACﬁ E)=100% Supp(Eﬁ AC)=17% Conf(Eﬁ AC)=2/7=28.5%

9

2.1 Thu t toán Apriori

ậ

Nh n xét 1: ậ * Hai b

c chính c a bài toán khai thác d li u d a

ướ

ữ ệ

ự

ủ

ng xuyên x y

ườ

ả

trên các lu t k t h p: ơ

ra (tho ng

1. T o ra t ạ ả

ậ ế ợ t c t p đ n v d li u th ị ữ ệ ấ ả ậ ng là Min_Sup). ưỡ 2. T t p các đ n v d li u th ị ữ ệ ơ

ừ ậ

ườ

ng xuyên x y ra Y = ả ậ ạ

ớ ị ữ ệ

ậ

ỡ

ơ ỗ ậ

ậ

ộ

{I1, I2, . . ., Ik } v i k >= 2, sinh ra các lu t t o ra t ừ các đ n v d li u này b ng cách t m các t p con ằ c a m i t p đ n v d li u và tính các đ tin c y ị ữ ệ ủ c a chúng nh trên. ủ

ơ ư

10

2.1 Thu t toán Apriori

ậ

ế

ủ

ự

ậ

ế

ậ

ế

ấ

ậ

ổ

ế

ổ

ậ

ấ

Cách ti p c n c a thu t toán Apriori d a trên ậ nh n xét sau: N u b t kỳ t p k-đvdl nào là ấ không ph bi n thì b t kỳ t p (k+1)-đvdl ch a chúng cũng s không ph bi n, và ứ ẽ i: N u b t kỳ t p k-đvdl nào là ph c l ng ổ ế ượ ạ bi n thì m i t p con c a nó là ph bi n. ọ ậ ế

ổ ế

ủ

11

2.1 Thu t toán Apriori

ậ

ộ ậ

ị ữ ệ

ọ ố ơ

c a chúng và t p có k ph n t

Ký hi u:ệ - Ta g i s đ n v d li u trong m t t p h p là s ố là k-

ậ

ợ ầ ử

ơ

ổ ế

k-đvdl. ng: i) các đ n v d li u và

ị ữ ệ

ồ ơ

ỗ

ng: i) các đ n v d li u và

ị ữ ệ ị ữ ệ

ơ ơ

ỗ

các ph n t ầ ử ủ đ n v d li u ị ữ ệ - G i ọ Lk: T p h p các t p ph bi n g m các ậ ợ ậ g m 2 tr M i ph n t ầ ử ồ ườ ii) đ m s l n xu t hi n. ệ ấ ố ầ ế - Ck : T p h p các t p ng viên k- đ n v d li u. ậ ứ ợ ậ M i ph n t ườ ầ ử ồ ii) đ m s l n xu t hi n. ệ ố ầ ế

g m 2 tr ấ

12

Thu t toán Apriori d a trên các th t c sau ự

ủ ụ

ậ

ạ

ậ

ổ ế

; k++ ) do

Procedure 1: T o ra các t p ph bi n Begin L1 = {t p ph bi n1-đvdl}; ậ for ( k = 2; Lk-1 „

begin

ạ

ừ k-1);

D do

Ck = T o ra t p ng viên t (L ậ ứ for m i giao tác t ỗ begin

ậ

ủ

Ct = T p con c a (C for m i c ỗ

k) ch a t ứ Ct do c.count++;

Min_Supp*|D|}

Ck | c.count ‡

end Lk = {c ˛

end Return (¨

k Lk);

13

end

Thu t toán Apriori d a trên các th t c sau ự

ủ ụ

ậ

t c các lu t k t h p ấ ả ậ ế ợ

Procedure 2: Tìm ra t begin

th ng xuyên X˛ L do ả ườ

Result = ˘ for m i t p x y ra ỗ ậ begin

(cid:204) ˘ X sao cho a „ do

ậ

for m i a ỗ if(M c xác nh n(X)/M c xác nh n(a)>=Min_Conf) ứ ứ {a ﬁ then Result = Result ¨ ậ (X-a)}

end return Ressult

end

14 Trong ví d 1, v i Min_Conf=c

ớ

0=70% và Min_Supp

ụ =s0=40%

ơ

ả

ậ

ị ữ ệ

- Ta có t p L g m các t p đ n v d li u x y ra ậ ồ ng xuyên nh sau:

ư

ườ

ư

Aﬁ D v i c=71.42% và s=41.66% Dﬁ A v i c=71.42% và s=41.66% Bﬁ E v i c=83.33% và s=41.66% Eﬁ B v i c=71.42% và s=41.66%

th L = {{A}, {B}, {C}, {D}, {E}, {F}, {AD}, {BE}, {CE}, {DE}} Có các lu t k t h p nh sau: ậ ế ợ ớ ớ ớ ớ

15

Lu t k t h p: C s Lu t k t h p: C s

ậ ế ợ ậ ế ợ

ơ ở ơ ở

s M c xác nh n t M c xác nh n t ứ ứ ể s i thi u i thi u ể

– Cao

ậ ố ậ ố (cid:222) (cid:222) (cid:222) : (minsupp) / S / S00 : (minsupp) ít t p ph n t ầ ử ậ ậ ợ ệ r t th ít lu t h p l ấ nhi uề lu t h p l (itemset) ph bi n ổ ế ệ ấ ậ ợ ệ hi mế xu t hi n ườ xu t hi n ấ ệ – Th pấ

g Đ tin c y t Đ tin c y t ậ ố ậ ố ộ ộ ể g i thi u i thi u ể

(cid:222)

(cid:222) – Cao – Th pấ / C / C00 :: (minconf) ít lu t ậ nh ng t ầ nhi uề lu t, ph n l n r t ư ậ " ấ ả g n nh đúng t c “ ư ắ " ầ ớ ấ “không ch c ch n ắ

s g = 2 -10 %, g = 70 - 90 % Giá tr tiêu bi u Giá tr tiêu bi u ể :: s ể ị ị

16

Lu t k t h p: C s Lu t k t h p: C s

ậ ế ợ ậ ế ợ

ơ ở ơ ở

Giao tácác:: Giao t ạ ệ ạ

D ng k t ế <1, {item1,item2}> <2, {item3}>

– D ng quan h <1, item1> <1, item2> <2, item3>

ph n t đ n l và t p ph n t ầ ử ơ ẻ ầ ử ậ

ng giao tác có ch a I ố ượ ứ

ủ ậ I: s l ng ưỡ

s ộ ủ ộ support) ‡ itemsets: Item vàà itemsets: Item v Support c a t p Support Min Support s : Min Support T p ph n t ầ ử T p ph n t ầ ử ậ ậ ng cho support ổ ế :: có đ ng h ( ph bi n ph bi n ổ ế

17

Lu t k t h p: C s Lu t k t h p: C s

ậ ế ợ ậ ế ợ

ơ ở ơ ở

ỗ

ổ ế

c mua (trong m t l ộ t mua Cho: (1) CSDL các giao tác, (2) m i giao tác là m t Cho: ượ ộ ượ ặ

support 3 or 75% 2 or 50% 1 or 25% 2 or 50% max 25%

T p ph bi n ậ {A} {B} và {C} {D}, {E} và {F} {A,C} Các c p khác ặ

danh sách m t hàng đ c a khách hàng)Frequent item sets ủ Hàng mua ID c a giao tác ủ A,B,C 100 A,C 200 A,D 400 B,E,F 500

ậ t cấ ả lu t có support >= minsupport t cấ ả

Tìm: t Tìm: t •

If min. support 50% and min. confidence 50%, then A A [50%, 100%] C C [50%, 66.6%], C C (cid:222)(cid:222) A A (cid:222)(cid:222)

18

T o ng viên Apriori T o ng viên Apriori

ạ ứ ạ ứ

Nguyên t c Apriori: ắ Nguyên t c Apriori: ắ

ậ ữ ổ ế ủ ậ ổ ế ả

abc

Nh ng t p con c a t p ph bi n cũng ph i ph bi n abc, abd, acd, ace, bcd}} LL33=={{abc, abd, acd, ace, bcd ự ế LL33*L*L33 T k t: T k t: ự ế – abcd t và abd ừ – acde t ừ acd và ace

Rút g n:ọ Rút g n:ọ

ị ạ – acde b lo i vì ade không có trong L3

CC44={={abcdabcd}}

19

Ví d v Apriori (1/6) Ví d v Apriori (1/6)

ụ ề ụ ề

Database D Database D LL11 CC11

Tập {1} {2} {3} {5}

Độ ủng hộ 2 3 3 3

ID giao tác Phần tử 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5

Tập Độ ủng hộ {1} {2} {3} {4} {5}

2 3 3 1 3

Duy t DệDuy t Dệ

20

Ví d v Apriori (2/6) Ví d v Apriori (2/6)

ụ ề ụ ề

CC22 CC22 LL22

Tập Độ ủng hộ {1 3} {2 3} {2 5} {3 5}

2 2 3 2

Tập Độ ủng hộ {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

1 2 1 2 3 2

Tập {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

Duy t ệDuy t ệ DD

21

Ví d v Apriori (3/6) Ví d v Apriori (3/6)

ụ ề ụ ề

Tập Độ ủng hộ

CC33 LL33

{2 3 5}

Tập {2 3 5}

Duy t DệDuy t Dệ

22

Ví d v Apriori (4/6) Ví d v Apriori (4/6)

ụ ề ụ ề

12345 12345 ế ế

Không gian tìm Không gian tìm ki m c a ủ ki m c a ủ CSDL D CSDL D

1234 1234 1235 1235 1245 1245 1345 2345 1345 2345

123 124 125 134 135 145 234 235 245 345 123 124 125 134 135 145 234 235 245 345

12 13 14 15 23 24 25 34 35 45 12 13 14 15 23 24 25 34 35 45

11 22 33 44 55

23

Ví d v Apriori (5/6) Ví d v Apriori (5/6)

ụ ề ụ ề

12345 12345

Áp d ng ụÁp d ng ụ Heuristic Apriori Heuristic Apriori trên C p 1ấ trên C p 1ấ

1234 1234 1235 1235 1245 1245 1345 1345 2345 2345

123 124124 125 123 125 134134 135 135 145145 234234 235 245 345 235 245 345

12 13 1414 15 23 12 13 15 23 2424 25 25 3434 35 35 4545

11 22 33 44 55

24

Ví d v Apriori (6/6) Ví d v Apriori (6/6)

ụ ề ụ ề

ụ

12345 12345

ụÁp d ng Heuristic Áp d ng Heuristic Apriori Apriori trên C p 2ấ trên C p 2ấ

1234 1234 1235 1235 1245 1245 1345 2345 1345 2345

123 124 125 134 135 145 234 235 123 124 125 134 135 145 234 245 345 235 245 345

1212 13 13 1414 1515 23 23 2424 25 25 34 34 35 35 4545

11 22 33 44 55

25

T p ph bi n t i đ i ( maximal frequent sets). ổ ế ố ạ ậ

i đ i ( maximal frequent

T p ph bi n T p ph bi n t

ổ ế ổ ế ố ạ

ậ

ổ ế ố ạ ế ồ ạ ậ

i đ i n u M i t p ph ổ

(cid:204)

ậ ậ sets). Đ nh nghĩa: M là t p ph bi n t ị là t p ph bi n và không t n t ổ ế bi n S khác M mà M

S

ế

26

Thu t toán Apriori đã đ nhanh? Thu t toán Apriori đã đ nhanh?

ủ ủ

ậ ậ

c (

Ph n c t lõi c a thu t toán Apriori: Ph n c t lõi c a thu t toán Apriori: ố ố

ậ

ế

ể ế

– Duy t CSDL và đ i sánh m u đ đ m s l n xu t hi n c a ẫ

ố ầ

ủ

ệ

ấ

FP tree FP tree ướ k – 1) đ t o các t p ph ổ ể ạ

ậ ủ ầ ậ ủ ầ – Dùng các t p ph bi n kích th ổ ế ậ ướ k ng viên bi n kích th ứ ệ ố các t p ng viên trong các giao tác ậ ứ

7 t p ng viên

c 1 s t o ra 10 ẽ ạ

ướ

ậ ứ

ướ

Apriori: : Apriori ạ ạ ậ ậ ẽ ẽ ủ ủ

• 104 t p ph bi n kích th ổ ế c 2 ệ

ướ

ộ

c 100, ví d ụ

ổ ế 100 »

1030 ng viên.

• Đ phát hi n m t m u ph bi n kích th ẫ ầ ạ

ứ

– Duy t CSDL nhi u l n:

{a1, a2, …, a100}, c n t o 2 ệ

ề ầ

• C n duy t (

ầ

ệ n +1 ) l n, ầ n là chi u dài c a m u dài nh t ấ ề

ủ

ẫ

Tình tr ng ngh n c chai c a thu t toán ổ Tình tr ng ngh n c chai c a thu t toán ổ vi c t o ng viên ệ ạ ứ vi c t o ng viên ệ ạ ứ – Các t p ng viên đ s : ậ ứ ồ ộ ậ kích th ể

27

Thu t toán Apriori đã đ nhanh? Thu t toán Apriori đã đ nhanh?

ủ ủ

ậ ậ

ậ

ả

ộ

Th c t Th c t

dòng th

ng thu c tính trên ng dòng giao tác.

ố ớ ế ườ

ố ượ ớ ố ượ

ề

– Ví d :ụ

• 50 thu c tính m i cái có 1-3 giá tr , 100.000 dòng (không quá

ộ

ỗ

ị

t )ệ

ị

ỗ

ộ

ỗ

ộ

ị

ộ

ộ ặ

ị ư

ộ ậ

ộ

ể ậ ế ợ ộ

ộ

ỗ

ị

: ự ế : ự ế – Đ i v i ti p c n Apriori căn b n thì s l ng khó h n nhi u so v i s l

• 50 thu c tính m i cái có 10-100 giá tr , 100.000 dòng (h i t ) ơ ệ • 10.000 thu c tính m i cái có 5-10 giá tr , 100 dòng (quá t ...) ệ – L u ý: ư • M t thu c tính có th có m t vài giá tr khác nhau ộ • Các thu t toán lu t k t h p có đ c tr ng là xem m t c p thu c ặ tính-giá tr là m t thu c tính (2 thu c tính m i cái có 5 giá tr => ộ "10 thu c tính") ộ Cách kh c ph c v n đ ? ụ ấ ắ Cách kh c ph c v n đ ? ụ ấ ắ

ề ề

28

C i thi n hi u qu c a TT Apriori C i thi n hi u qu c a TT Apriori

ả ủ ả ủ

ệ ệ

ả ả

: Đ m t p d a vào k thu t băm Đ m t p d a vào k thu t băm ậ ậ ế ế ự ự

ươ

ng ng ứ

i h n thì không th ph bi n.

ướ k có hashing bucket count t ể

ổ ế

– M t giao tác không ch a t p ph bi n kích th

ỹ ỹ c

ướ k nào thì

c ổ ế các l n duy t ti p ti p theo. ệ ế

ứ ậ ầ

ế

không c n xét đ n ầ

ế ở

ậ ậ – M t t p kích th ộ ậ nh h n gi ớ ạ ỏ ơ : Thu nh giao tác ỏ Thu nh giao tác ỏ ộ

ậ

ổ ế

ẽ

trong ít nh t m t ph n chia c a DB.

– T p nào có kh năng ph bi n trong DB thì s ph bi n ổ ế ủ

ả ộ

ầ

ấ

Chia nhỏ: Chia nhỏ

ưỡ

ượ

ủ

– Khai thác trên t p con c a d li u đ ậ ng h th p h n + m t ph ứ ơ

c cho, ng ữ ệ ng th c đ xác đ nh tính đ y ị ể

ng c a đ ộ ủ ầ

ộ ấ

ươ

ộ

ủ đủ

ẫ : L y m u L y m u ẫ ấ ấ

29

Thu t toán FP-Tree

ậ

Ý t

ng:

ộ

ệ

ế

ự

ủ ẫ

Dùng đ quy đ gia tăng đ dài c a ưở ể m u ph bi n d a trên cây FP và các m u ổ ẫ đ ượ Ph ươ – V i m i item ph bi n trong Header Table, xây

ổ ệ ệ

ủ ề ớ

ỗ ơ ở ề ề i ti n trình trên v i m i cây đi u ki n m i ớ ỗ ế c t o ra

c phân ho ch ạ ệ : ng pháp th c hi n ự ớ ế d ng c s đi u ki n và cây đi u ki n c a nó ự – L p l ặ ệ ạ đ ượ ạ – Cho t ớ

ề ỗ

ồ

c t o ra là cây r ng ượ ạ ng đi đ n thì ng ng. M i ừ ỗ ơ c t o ra ng đi đ n đ ượ ạ ườ ơ

i khi cây đi u ki n đ ệ ho c ch bao g m m t đ ặ ộ ườ ỉ h p con các item trên đ t ổ ợ s là m t t p ph bi n ẽ ổ ế ộ ậ

30

ậ Các b Các b

c xây d ng cây FP-Tree c xây d ng cây FP-Tree

Thu t toán FP-Tree ướ ướ

ự ự

ổ ế

ầ ử ị ạ

ầ ủ ế ổ ế ậ ượ ậ : Duy t CSDL, xác đ nh t p F các item ph bi n ậ , sau đó lo i b các Item không tho ả ỏ ng minsup. S p x p các item trong t p F theo th ứ c t p k t qu là ế ả

ẽ ạ ố

ố ệ ứ ỗ

ế

ắ

ọ

theo th t

ủ Ứ ệ

ứ ự ả

ậ

ộ

ự ổ ế ầ

ể ư

ọ

B c 1 ệ ướ m t ph n t ộ ng ắ ưỡ gi m d n c a đ ph bi n, ta đ t ộ ự ả L. : T o nút g c cho cây T, và tên c a nút g c s là B c 2 ướ Null. Sau đó duy t CSDL l n th hai. ng v i m i giao ầ ớ tác trong CSDL ta th c hi n 2 công vi c sau: ệ – Ch n các item ph bi n trong các giao tác và s p x p chúng gi m d n đ ph bi n trong t p L ổ ế – G i hàm Insert_tree([p|P],T) đ đ a các item vào trong cây T

31

Thu t toán FP-Tree

ậ

Xây d ng cây FP-Tree Xây d ng cây FP-Tree ự ự

32

Thu t toán FP-Tree

ậ

null

Thêm TID=1 vào cây:

B:1

A:1

Thêm TID=2 vào cây:

null

B:2

C:1

A:1

TID 1 2 3 4 5 6 7 8 9 10

Items {A,B} {B,C,D} {A,C,D,E} {A,D,E} {A,B,C} {A,B,C,D} {B,C} {A,B,C} {A,B,D} {B,C,E}

D:1

33

Thu t toán FP-Tree

ậ

null

Transaction Database

B:8

A:2

A:5

C:3

C:1

D:1

C:3

D:1

E:1

D:1

E:1

TID 1 2 3 4 5 6 7 8 9 10

Items {A,B} {B,C,D} {A,C,D,E} {A,D,E} {A,B,C} {A,B,C,D} {B,C} {A,B,C} {A,B,D} {B,C,E}

Header table

D:1

E:1

c cây nh ư

ượ

ể ạ

ế

ậ

ả

Sau khi thêm các giao tác vào, ta đ hình trên D a trên cây, ta l p b ng header đ t o liên k t gi a các node có cùng item

ự ữ

34

Thu t toán FP-Tree

ậ

null

B:8

A:2

A:5

C:3

C:1

D:1

C:3

D:1

E:1

D:1

E:1

null

D:1

E:1

B:1

A:2

C:1

D:1

E:1

D:1

E:1

Nh ng giao tác có bao g m item E

ữ

ồ

E:1

35

Thu t toán FP-Tree

ậ

(New) Header table

null

ệ

Cây đi u ki n ề cho item E

B:1

A:2

C:1

D:1

null

A:2

C:1

E:1

D:1

E:1

ỏ

C:1

D:1

E:1

Item B b lo i ị ạ b do support(B)=1 nh h n ỏ ơ minsup=2.

ồ

ớ

D:1

ệ

ự

ế ụ

i b ng Header cho cây

ạ ả

ự

V i m i nhánh cây bao g m E. ỗ • Lo i b E ạ ỏ • Thêm vào cây m iớ • Xây d ng l m iớ

ộ ườ

Ti p t c th c hi n đ quy các ệ thao tác cho đ n khi trên cây ch ỉ ế còn m t đ ng đi đ n Item ph bi n:

ổ ế E(3)

36

Thu t toán FP-Tree

ậ

(New) Header table

null

Cây đi u ki n cho ệ ề t p item DE ậ

A:2

null

C:1

D:1

A:2

D:1

ậ

ổ ế

ế

Các t p ph bi n sau khi k t thúc ti n trình đ quy do cây ch còn m t đ

ế ng đi ộ ườ

ệ

ỉ

ng đi b t đ u v i E và

ắ ầ

ớ

T p ph bi n:

ổ ế DE(2), ADE(2)

ậ

T p các đ k t thúc v i D.

ườ ớ

ậ ế

ừ

ng d n vào ẫ

L n l t thêm t ng đ cây m i sau khi đã lo i b D

ầ ượ ớ

ườ ạ ỏ

A 2

37

Thu t toán FP-Tree

ậ

(New) Header table

null

A:1

C:1

null

D:1

K t thúc quá trình đ quy do cây r ng.

ệ

ế

ỗ

T p ph bi n:

ổ ế CE(2)

ậ

ng d n b t đ u t

E và

ắ ầ ừ

ẫ

T p các đ k t thúc v i C.

ườ ớ

ậ ế

t t ng nhánh vào cây

ầ ượ ừ

Thêm l n l m i (sau khi đã lo i b C)

ạ ỏ

ớ

38

Thu t toán FP-Tree

ậ

(New) Header table

null

A:2

Quá trình đ quy k t thúc do cây r ng. ế

ệ

ỗ

T p ph bi n:

ổ ế AE(2)

ậ

ng đi b t đ u t

E và

ắ ầ ừ

T p các đ k t thúc v i A.

ườ ớ

ậ ế

ng đi vào cây

Thêm l n l ườ ầ ượ ừ m i (sau khi lo i b A).

t t ng đ ạ ỏ

ớ

39

Thu t toán FP-Tree

ậ

ứ

ng đi đ n P

ộ ế

ỗ

ớ

ủ

ườ

Procedure FFP-growth(Tree, α) { (1) (2)

ườ ợ g c a các nút trong đ

ậ

ẫ g Uα, support =

c a các nút trong

g );

N u ế Tree có ch a m t đ Thì v i m i cách k t h p ự ệ đi P th c hi n phát sinh t p m u ủ ớ

ỗ

ầ

(3) min(support (4)

c l i ng v i m i Ai trong thành ph n c a

ủ Tree

ượ ự

ạ ứ ệ

ng th c hi n {

ớ

ậ

ế

ộ

ổ

- phát sinh t p m u β=AiUα v i đ ph bi n

(5)

ệ

ề

(6)

ự

ệ

ề

Treeβ theo đi u ki n c a

ạ

ọ

ẫ support = Ai.support; ơ ở ự - xây d ng c s đi u ki n cho β và sau đó ủ β; xây d ng cây FP - N u ế Treeβ ≠ ˘ thì g i l i hàm FFP-growth(

Treeβ, β)

(7) (8)

}

40

T o lu t k t h p T o lu t k t h p

ậ ế ợ ậ ế ợ

ạ ạ

– T o các t p ph bi n thì

ổ ế

ậ

ch mậ (đ c bi

ặ

ệ

t là các t p kích ậ

c 2)

– T o các lu t k t h p t

các t p ph bi n thì

nhanh

ạ th ướ ạ

ậ ế ợ ừ

ổ ế

ậ

ổ ế ng

ậ

c s d ng ử ụ

Ghi nh 1:ớ Ghi nh 1:ớ

– Khi t o các t p ph bi n, – Khi t o lu t k t h p, ưỡ

ậ ế ợ ng

ng đ ng h ộ ủ ưỡ ng đ tin c y ượ ộ

ậ đ

ộ đ ượ c s d ng ử ụ

Ghi nh 2:ớ Ghi nh 2:ớ ạ ạ

Th c t Th c t , vi c t o các t p ph bi n và t o các lu t , vi c t o các t p ph bi n và t o các lu t ệ ạ ệ ạ ạ ạ ậ ậ

c th c hi n v i Citum 4/275 Alpha

ụ ệ

ượ

ự

ớ

ậ ử ậ ử ổ ế ổ ế ờ ờ

ộ

ự ế ệ server có b nh chính 512 MB & Red Hat Linux release 5.0 (kernel 2.0.30)

ậ ự ế ự ế ậ k t h p th t s chi m th i gian bao lâu? ế ế ợ k t h p th t s chi m th i gian bao lâu? ế ế ợ – Xét m t ví d nh trong th c t … ỏ ộ – Các th nghi m đ ử ớ

41

Ch n nh ng lu t t ữ Ch n nh ng lu t t ữ

ậ ố ậ ố

ọ ọ

t nh t? ấ t nh t? ấ

ng r t l n, c n ch n ra nh ng lu t ọ ng r t l n, c n ch n ra nh ng lu t ọ ấ ớ ấ ớ ữ ữ ậ ậ ầ ầ ả ườ ả ườ T p k t qu th ế T p k t qu th ế

t nh t d a trên: t nh t d a trên:

: ấ ự ấ ự ộ

ậ ậ t ố t ố – Các đ đo khách quan Hai các đo ph bi n: ổ ế

¶ support; và confidence

•

(Silberschatz & Tuzhilin, – Các đ đo ch quan ủ

t n u ố ế ạ

ể

•

ờ (gây ng c nhiên cho user); và/ho c ặ ạ ộ (user có th dùng nó đ làm gì đó) ể c dùng trong các quá c dùng trong các quá

có th ho t đ ng ả ế ả ế

ữ ữ trình khám phá tri th c (KDD) trình khám phá tri th c (KDD) ộ KDD95) M t lu t (m u) là t ẫ ậ ộ ¶ gây b t ngấ ể Nh ng k t qu này s đ ẽ ượ Nh ng k t qu này s đ ẽ ượ ứ ứ

42

Lu t Boolean và lu t đ nh l Lu t Boolean và lu t đ nh l

ng ng

ậ ị ậ ị

ậ ậ

ượ ượ

Lu t k t h p Boolean so v i đ nh l Lu t k t h p Boolean so v i đ nh l ng ng ớ ị ớ ị (tùy vào ượ (tùy vào ượ

c dùng) c dùng)

ữ

ự

ấ

ế ủ

ụ

ệ

ị ượ ị ượ ậ

ậ ế ợ ậ ế ợ lo i giá tr đ lo i giá tr đ – Boolean: ệ ặ

(cid:222)

mua=DBMiner mua=DBMiner

mua(x,

Lu t liên quan đ n m i k t h p gi a các ph n

ố ế ợ

ữ

ậ

ầ

ế

ạ ạ Boolean: Lu t liên quan đ n m i k t h p gi a s có xu t ố ế ợ hi n và không xu t hi n c a các ph n t (ví d “có mua A" ầ ử ho c “không có mua A") =SQLServer, mua=DMBook (cid:222) mua=SQLServer, mua=DMBook [2%,60%] [2%,60%] mua(x, "SQLServer") ^ mua(x, "DMBook") ﬁ "DBMiner") [0.2%, 60%]

ượ ượ

ng: ng: ộ

ượ

(cid:222) (cid:222)

mua=PC [1%, 75%] mua=PC [1%, 75%]

mua(x, "PC")

ậ

ổ

– Đ nh l Đ nh l ị ị hay thu c tính đ nh l t ử ị tu iổ =30..39, thu nh p=42..48K =30..39, thu nh p=42..48K ậ ậ ﬁ tu i(x, "30..39") ^ thu nh p(x, "42..48K") [1%, 75%]

43

Các lu t đ nh l Các lu t đ nh l

ng ng

ậ ị ậ ị

ượ ượ

ví d : tu i, thu nh p, chi u ổ ậ ề ụ ng: ng: ị ị ộ ộ ượ ượ

30,5 20,3 25,8 27,0

ắ Các thu c tính đ nh l Các thu c tính đ nh l cao, cân n ngặ ạ :: ví d :ụ màu s c c a xe ác thu c tính phân lo i CCác thu c tính phân lo i ạ

ộ ộ CID 1 2 3 4 ủ chieu cao can nang thu nhap 168 175 174 170 ề ộ ị ị

75,4 80,0 70,3 65,2 ấ ề có quá nhi u giá tr khác nhau cho các thu c tính đ nh V n đ : V n đ : ấ ề ngượ l

ng sang các thu c ể ộ ị ộ i pháp: i pháp:

ảGi ả Gi tính phân lo i (chuy n qua không gian r i r c) chuy n các thu c tính đ nh l ạ ượ ờ ạ ể

44

Các lu t m t chi u và nhi u chi u ề Các lu t m t chi u và nhi u chi u ề

ộ ộ

ề ề

ậ ậ

ề Các m i k t h p m t chi u và nhi u chi u Các m i k t h p m t chi u và nhi u chi u ề

ố ế ợ ố ế ợ

ộ ộ

ề ề

ặ ậ ộ ộ

ỉ ộ ề ộ ạ ượ ề Các thu c tính ho c t p thu c tính ề ậ ộ ng (ví d , quy v ề ụ

(cid:222) bánh mì [0.4%, 52%] bánh mì [0.4%, 52%]

– M t chi u: M t chi u: trong lu t ch quy v m t đ i l “mua") Bia, khoai tây chiên (cid:222) Bia, khoai tây chiên mua(x, “Bia") ^ mua(x, “Khoai tây chiên") ﬁ mua(x, “Bánh mì") [0.4%, 52%]

ặ ề ề

ộ ạ ượ ộ ề

ề ạ c ờ ụ ị

– Nhi u chi u: ề Các thu c tính ho c thu c tính Nhi u chi u: ề ậ ượ quy v hai hay nhi u đ i l trong lu t đ ng (ví d : “mua", “th i gian giao d ch", “lo i khách hàng") Trong ví d sau là: qu c gia, tu i, thu nh p ố ụ ậ ổ

45

Các lu t nhi u chi u Các lu t nhi u chi u

ề ề

ậ ậ

quoc gia Ý Pháp Pháp Ý Ý Pháp

tuoi 50 40 30 50 45 35

thu nhap thap cao cao trung bình cao cao

CID 1 2 3 4 5 6

(cid:222)

(cid:222) ÁC LU TẬ :: CCÁC LU TẬ = Pháp qu c gia ố thu nh pậ = cao tu iổ = 50 thu nh pậ = cao [50%, 100%] = Pháp [50%, 75%] qu c gia ố = Ý [33%, 100%] qu c gia ố

46

Các lu t m t c p và nhi u c p Các lu t m t c p và nhi u c p

ộ ấ ộ ấ

ề ề

ấ ấ

ậ ậ

ố ế ợ

ầ ử

ữ

ệ ố

ộ ấ

ủ

ệ

Các m i k t h p m t c p và nhi u c p Các m i k t h p m t c p và nhi u c p ố ế ợ ố ế ợ ộ ấ ộ ấ ề ề ấ ấ

(cid:222)

– M t c p: hay thu c tính c a ộ ấ M i k t h p gi a các ph n t M t c p: ủ ộ ộ ấ cùng m t c p khái ni m (ví d cùng m t c p c a h th ng ụ phân c p)ấ Bia, Khoai tây chiên (cid:222) Bia, Khoai tây chiên

Bánh mì [0.4%, 52%] Bánh mì [0.4%, 52%]

ữ

ố ế ợ ệ

hay thu c tính ộ ấ

ầ ử ụ

ủ

ề

ấ

(cid:222)

Bánh Bánh

– Nhi u c p: ấ M i k t h p gi a các ph n t Nhi u c p: ề ấ ề c a nhi u c p khái ni m khác nhau (ví d nhi u c p c a h ệ ấ ề ủ th ng phân c p) ố :Karjala, Khoai tây chiên:Estrella:Barbeque (cid:222) Bia:Karjala, Khoai tây chiên:Estrella:Barbeque mì [0.1%, 74%] mì [0.1%, 74%]

47

Các lu t k t h p nhi u c p Các lu t k t h p nhi u c p

ậ ế ợ ậ ế ợ

ề ề

ấ ấ

ầ ầ

ố ố

t ẫ ố ở ấ t ẫ ố ở ấ

ậ ố

c p khái ni m phù h p ệ c p khái ni m phù h p ệ ứ ề ứ ề

ổ ế ủ ổ ế ủ

t nh t ấ Ti p c n: suy lu n ợ Ti p c n: suy lu n ợ M t d ng ph bi n c a tri th c n n là m t ộ M t d ng ph bi n c a tri th c n n là m t ộ c t ng quát hóa hay ể ượ ổ c t ng quát hóa hay ể ượ ổ

Khó tìm nh ng m u t c p quá g n g c ữ Khó tìm nh ng m u t c p quá g n g c ữ – đ ng h cao = quá ít lu t ậ ộ ộ ủ – đ ng h th p = quá nhi u lu t, không t ề ộ ấ ộ ủ ậ ở ấ ậ ế ậ ở ấ ậ ế ộ ạ ộ ạ thu c tính có th đ ộ thu c tính có th đ ộ chi ti chi ti

cây khái ni mệ cây khái ni mệ

Các lu t k t h p nhi u c p: Các lu t k t h p nhi u c p:

ữ ữ

ậ ậ

t hóa d a vào ự ế t hóa d a vào ế ự ề ậ ế ợ ề ậ ế ợ ố ế ợ ố ế ợ

nh ng lu t ph i ố ấ nh ng lu t ph i ố ấ h p các m i k t h p v i cây các khái ni m ệ ớ h p các m i k t h p v i cây các khái ni m ệ ớ

ợ ợ

48

Các lu t k t h p nhi u c p Các lu t k t h p nhi u c p

ậ ế ợ ậ ế ợ

ề ề

ấ ấ

th th ng t o ng t o Các ph n t Các ph n t ầ ầ ườ ườ

Th c ph m ự ẩ

ạ ử ử ạ thành các cây phân c pấ thành các cây phân c pấ ấ ấ

c p th p ử ở ấ c p th p ử ở ấ c cho là có đ ộ c cho là có đ ộ bánh mì s aữ

ơ ơ

ậ ậ 2% tr ngắ lúa mì

Các ph n t ầ Các ph n t ầ h n đ ượ ơ h n đ ượ ơ ng h th p h n ộ ấ ủ ng h th p h n ộ ấ ủ Các lu t v các t p ậ ở ề Các lu t v các t p ậ ở ề ẽ ẽ

các các s a không béo ữ c p thích h p s khá ợ ấ c p thích h p s khá ợ ấ ữh u ích ữ h u ích Fraser Sunset

CSDL giao tác có th đ CSDL giao tác có th đ ể ượ ể ượ

c c mã hóa d a trên các ự mã hóa d a trên các ự chi u và các c p chi u và các c p ề ề ấ ấ

49

Các lu t k t h p nhi u c p Các lu t k t h p nhi u c p

ậ ế ợ ậ ế ợ

ề ề

ấ ấ

Th c ph m ự ẩ

1 2

ID giao tác Mat hang T1 T2 T3 T4 T5

bánh mì s aữ

{111, 121, 211, 221} {111, 211, 222, 323} {112, 122, 221, 411} {111, 121} {111, 122, 211, 221, 413}

2 2% 2 tr ngắ 1 lúa mì

s a không béo ữ 1 2

Fraser Sunset 121= s a - 2% - Fraser ữ

50

Các lu t k t h p nhi u c p Các lu t k t h p nhi u c p

ậ ế ợ ậ ế ợ

ề ề

ấ ấ

Ti p c n trên-xu ng, ti n theo chi u sâu: Ti p c n trên-xu ng, ti n theo chi u sâu: ố ố ế ế

c tiên tìm nh ng lu t m nh ữ

ạ

ở ấ

c p th p h n c a

s a ữ ﬁ bánh mì [20%, 60%] – Sau đó tìm nh ng lu t “y u h n” ơ ở ấ ữ

ế

ậ

ủ

ấ

chúng:

s a 2%

ﬁ bánh mì lúa mì [6%, 50%]

ữ

ề ề c p cao: ế ế ậ ậ ậ – Tr ướ

ề ề ấ ấ

ấ

ổ ổ ậ ế ợ Khai thác thay đ i trên các lu t k t h p nhi u c p: Khai thác thay đ i trên các lu t k t h p nhi u c p: ề

ậ ế ợ

ề

ệ

s a ữ ﬁ bánh mì Wonder

ậ ế ợ ậ ế ợ – Các lu t k t h p trên nhi u c p khác nhau: s aữ ﬁ bánh mì lúa mì – Các lu t k t h p v i nhi u cây khái ni m: ớ

51

Các lu t k t h p nhi u c p Các lu t k t h p nhi u c p

ậ ế ợ ậ ế ợ

ề ề

ấ ấ

ủ

ậ

T ng quát hóa/chuyên bi T ng quát hóa/chuyên bi t hóa giá tr c a các thu c ị ủ t hóa giá tr c a các thu c ị ủ ộ ộ ệ ệ

chuyên bi chuyên bi

support c a các lu t tăng support

ữ

support c a các lu t ủ

t: t:

ệ support ệ

, đ ng h c a

ữ

ợ ệ ộ ủ

ậ ộ ủ

ng qui đ nh)

ỏ ơ

ưỡ

ả

ổ ổ tính… tính… – ...t ...t t sang t ng quát: ệ ừ ổ t sang t ng quát: ệ ừ ổ (có thêm nh ng lu t m i h p l ) ớ ợ ệ ậ – ...t ...t t ng quát sang chuyên bi ừ ổ t ng quát sang chuyên bi ừ ổ gi m (có nh ng lu t tr thành không h p l ậ ở ả chúng gi m xu ng nh h n ng ị ố

B c quá th p => quá nhi u lu t và quá thô s B c quá th p => quá nhi u lu t và quá thô s ậ ậ ơ ơ ấ ấ

ề ề Taffel Barbeque Chips

ậ ậ Pepsi light 0.5l bottle (cid:222) 200gr

B c quá cao => các lu t không hay B c quá cao => các lu t không hay ậ ậ

ậ ậ Food (cid:222) Clothes

52

L c lu t th a ậ L c lu t th a ậ

ừ ừ

ọ ọ

ư ừ ư ừ ể ể

Có nh ng lu t có th là d th a do đã có các m i ố Có nh ng lu t có th là d th a do đã có các m i ố tiên” gi a các ph n t tiên” gi a các ph n t ậ ữ ậ ữ quan h “t ệ ổ quan h “t ệ ổ ầ ử ầ ử ữ ữ

ậ

ộ

Ví d (s a có 4 l p con): Ví d (s a có 4 l p con): ớ ớ

bánh mì lúa mì [đ ng h = 8%, đ tin c y = ộ ủ

ộ ủ

ậ

ộ

(cid:222) bánh mì lúa mì [đ ng h = 2%, đ tin c y =

ụ ữ ụ ữ – s a ữ (cid:222) 70%] – s a 2% ữ 72%]

Ta nói lu t th nh t là t Ta nói lu t th nh t là t tiên c a lu t th hai tiên c a lu t th hai ứ ứ ấ ấ ậ ậ ổ ổ ủ ủ ứ ứ ậ ậ

M t lu t là d th a n u đ ng h c a nó g n v i ớ M t lu t là d th a n u đ ng h c a nó g n v i ớ ộ ủ ộ ủ ế ế

ậ ậ ị ị ự ự ầ ộ ủ ầ ộ ủ tiên c a lu t ậ ủ tiên c a lu t ậ ủ ổ ổ

ư ừ ộ ư ừ ộ giá tr “mong đ i”, d a trên t ợ giá tr “mong đ i”, d a trên t ợ – Lu t th a hai ứ ậ ở trên có th là d th a ể ư ừ

53

Khai thác d a trên ràng bu c ộ Khai thác d a trên ràng bu c ộ

ự ự

t các ràng

Khai thác c giga-byte d li u theo cách thăm dò, có ữ ệ Khai thác c giga-byte d li u theo cách thăm dò, có ữ ệ ả ả

ằ

ả

ử ụ

ố

ươt ươ t – Đi u này có kh thi không? - B ng cách s d ng t

ớ

ế ợ ạ ấ

Các lo i ràng bu c nào có th dùng trong khai thác d ữ Các lo i ràng bu c nào có th dùng trong khai thác d ữ ộ ộ ể ể

c bán chung t

i VanCouver

ng tác? ng tác? ề bu c!ộ ạ ạ li u?ệli u?ệ – Ràng bu c d ng tri th c Ràng bu c d ng tri th c ứ : phân l p, k t h p, …. ộ ứ ộ – Ràng bu c d li u Ràng bu c d li u ữ ộ ộ

ạ ạ ữ ệ : nh ng câu truy v n d ng SQL ữ ệ • Tìm nh ng c p s n ph m đ ượ ặ

ữ

ả

ạ

ẩ

– Nh ng ràng bu c v kích th Nh ng ràng bu c v kích th

tháng 12/98 ữ ữ

ộ ộ

ề ề

ướ ướ

• Có liên quan v vùng, giá, nhãn hi u, lo i khách hàng

ậ : c/c p b c ấ c/c p b c ấ ậ ạ ệ

ề ự ấ ề ự ấ

ữ ữ

3%, min_confidence ‡

‡

ề – Nh ng ràng bu c v s h p d n ẫ : Nh ng ràng bu c v s h p d n ộ ẫ ộ • Nh ng lu t m nh (min_support ạ

ậ

54 ữ 60%) ữ ữ

– Nh ng ràng bu c lu t ậ (xem slide sau) Nh ng ràng bu c lu t ậ

ộ ộ

Ràng bu c lu t ậ Ràng bu c lu t ậ

ộ ộ

ậ Có hai lo i ràng bu c lu t: Có hai lo i ràng bu c lu t: ậ ộ ộ ạ ạ

ộ ộ ậ ậ ậ ậ ạ ạ

• Metarule: P(X, Y) ^ Q(X, W) ﬁ

l y(X, "database ấ

systems")

• Lu t đ i sánh: tu i(X, "30..39") ^ thu nh p(X, "41K..60K")

ậ

ổ

ﬁ

ậ ố l y(X, "database systems"). ấ

– Ràng bu c d ng lu t: khai thác theo siêu lu t Ràng bu c d ng lu t: khai thác theo siêu lu t (meta-rule) (meta-rule)

ộ ộ ậ ạ ậ ạ ấ ấ

– Ràng bu c trên n i dung lu t: t o câu truy v n Ràng bu c trên n i dung lu t: t o câu truy v n d a trên ràng bu c (Ng, et al., SIGMOD’98) d a trên ràng bu c (Ng, et al., SIGMOD’98) ộ ộ ộ ộ

> 1000

ự ự • sum(LHS) < 100 ^ min(LHS) > 20 ^ count(LHS) > 3 ^ sum(RHS)