Khai thác tập phổ biến và luật kết hợp
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (369.47 KB, 20 trang )
1
KHAI THÁC
DỮ LIỆU &
ỨNG DỤNG
(DATA MINING)
GV : NGUYỄN HOÀNG TÚ ANH
2
BÀI 3- PHẦN 1
KHAI THÁC
TẬP PHỔ BIẾN &
LUẬT KẾT HỢP
3
NỘI DUNG
1. Gii thiu
2. Các khái niệm cơ bản
3. Bài toán khai thác tập phổ biến
4
GIỚI THIỆU
Mẫu phổ biến : là mẫu (tập các hạng mục, chuỗi con, cấu
trúc con, đồ thị con, …) xuất hiện thường xuyên trong tập
DL
– Agrawal, Imielinski, Swami – 1993 – trong ngữ cảnh bài toán tập phổ
biến và luật kết hợp
Mục đích : Tìm các hiện tượng thường xuyên xảy ra
trong DL
– Những sản phẩm nào thường được mua chung ? Bia và tã lót
– Người ta thường mua gi tiếp theo sau khi mua máy PC ?
– Dạng DNA nào có phản ứng với công thức thuốc mới ?
– Làm thế nào đề phân loại tự động văn bản Web ?
Ứng dụng :
– Áp dụng trong phân tích CSDL bán hàng
– Mở rộng sang quảng cáo, thiết kế catalog, phân tích chiến
dịch bán hàng, Web log, chuỗi DNA, …
5
GIỚI THIỆU
Bài toán khai thác tập phổ biến là bài toán
rất quan trọng lĩnh vực KTDL : vạch ra tính
chất ẩn, quan trọng của tập DL
Là nền tảng cho nhiều nhiệm vụ KTDL khác :
– Phân tích luật kết hợp, mối tương quan
– Mẫu tuần tự, cấu trúc ( Vd : đồ thị con)
– Phân tích DL không gian, đa phương tiện, phụ
thuộc thời gian
– Phân loại : phân loại dựa trên luật kết hợp
– Phân tích nhóm: gom nhóm dựa trên mẫu phổ biến
– ….
6
NỘI DUNG
1. Giới thiệu
2. Các khái nim cơ bn
3. Bài toán khai thác tập phổ biến
7
KHÁI NIỆM CƠ BẢN
1. CSDL GIAO DỊCH
(Transaction DB)
VD giỏ mua hàng:
o Giỏ 1: {Bánh mì,
Trứng, Sữa}
o Giỏ 2: {Bánh mì,
Đường}
…
o Giỏ n: {Bánh qui, ngũ
cốc, sữa}
TID Produces
1 MILK, BREAD, EGGS
2 BREAD, SUGAR
3 BREAD, CEREAL
4 MILK, BREAD, SUGAR
5 MILK, CEREAL
6 BREAD, CEREAL
7 MILK, CEREAL
8
MILK, BREAD, CEREAL,
EGGS
9 MILK, BREAD, CEREAL
8
KHÁI NIỆM CƠ BẢN
TID A B C D E
1 1 1 0 0 1
2 0 1 0 1 0
3 0 1 1 0 0
4 1 1 0 1 0
5 1 0 1 0 0
6 0 1 1 0 0
7 1 0 1 0 0
8 1 1 1 0 1
9 1 1 1 0 0
TID Products
1 A, B, E
2 B, D
3 B, C
4 A, B, D
5 A, C
6 B, C
7 A, C
8 A, B, C, E
9 A, B, C
ITEMS:
A = milk
B= bread
C= cereal
D= sugar
E= eggs
Biến đổi CSDL về
dạng nhị phân
9
1. CSDL GIAO DỊCH (tt)
Định nghĩa :
o Hạng mục (Item) : mặt hàng trong giỏ hay một thuộc tính
o Tập các hạng mục (itemset) I = {i
1
, i
2
, …, i
m
} :
VD : I = {sữa, bánh mì, ngũ cốc, sữa chua}
Tập k hạng mục (k-itemset)
o Giao dịch (Transation) : tập các hạng mục được mua trong
một giỏ ( có TID – mã giao dịch) : (Tid, tập hạng mục)
o Giao dịch t : tập các hạng mục sao cho t
⊆
I
o VD : t = { bánh mì, sữa chua, ngũ cốc}
o CSDL giao dịch : tập các giao dịch
o CSDL D = {t
1
,t
2
, …, t
n
} , t
i
={i
i1
,i
i2
, …, i
ik
} với i
ij
∈ I : CSDL
giao dịch
KHÁI NIỆM CƠ BẢN
10
2. ĐỘ PHỔ BIẾN VÀ TẬP PHỔ BIẾN
Giao dịch t chứa X nếu X là tập các hạng mục
trong I và X ⊆ t
VD : X = { bánh mì, sữa chua}
Độ phổ biến (supp) của tập các hạng mục X
trong CSDL D là tỷ lệ giữa số các giao dịch
chứa X trên tổng số các giao dịch trong D
Supp(X) = count(X) / | D |
Tập các hạng mục phổ biến S hay tập phổ
biến (frequent itemsets) là tập các hạng mục
có độ phổ biến thỏa mãn độ phổ biến tối thiểu
minsupp (do người dùng xác định)
Nếu supp(S) ≥
≥≥
≥ minsupp thì S - tập phổ biến .
KHÁI NIỆM CƠ BẢN
11
3. TÍNH CHẤT TẬP PHỔ BIẾN
Tất cả các tập con của tập phổ
biến đều là tập phổ biến
Thảo luận :
Tại sao ?
Nu tp con không ph bin thì tp
bao nó (tp cha) có ph bin hay
không ?
KHÁI NIỆM CƠ BẢN
12
I = { Beer, Bread, Jelly, Milk, PeanutButter}
X= {Bread,PeanutButter} ; Count(X) = 3 và |D| = 5
→
→→
→ supp(X) = 60%→
→→
→ X- tập phổ biến
X
2
= {Bread} →
→→
→ supp(X
2
) = ?
X
3
= {PeanutButter} →
→→
→ supp(X
3
) = ?; X
2
và X
3
có phổ biến ?
X
4
= {Milk}, X
5
={Milk, Bread} →
→→
→ X
4
và X
5
có phổ biến ?
VÍ DỤ 1
Minsupp = 60%
13
minsupp=30%
TẬP PHỔ BIẾN của VD 1
14
KHÁI NIỆM CƠ BẢN
4. TẬP PHỔ BIẾN TỐI
ĐẠI (Max-Pattern)
Tp ph bin & không
tn ti tp nào bao nó
là ph bin (Bayardo –
SIGMOD’98)
{B, C, D, E}, {A, C, D}-
tập phổ biến tối đại
{B, C, D}- không phải tập
phổ biến tối đại
Tid Items
10 A,B,C,D,E
20 B,C,D,E,
30 A,C,D,F
Minsupp=2
15
KHÁI NIỆM CƠ BẢN
5. TẬP PHỔ BIẾN ĐÓNG
(Closed Pattern)
Tp ph bin & không tn ti
tp nào bao nó có cùng đ
ph bin nh nó. (Pasquier,
ICDT’99)
Tp ph bin ĐÓNG là trng hp
nén các tp ph bin (có mt
thông tin)
{A, B}, {A, B, D}, {A,B, C} - tập
phổ biến đóng.
{A, B} - không phải tập phổ
biến tối đại
Minsupp=2
TID Items
10 a, b, c
20 a, b, c
30 a, b, d
40 a, b, d,
50 c, e, f
16
6. LUẬT KẾT HỢP( Association rule)
LKH có dng :
X ⇒
⇒⇒
⇒ Y, với X, Y ⊂
⊂⊂
⊂ I, và X ∩
∩∩
∩Y ={}
Ý nghĩa : khi X có mặt thì Y cũng có mặt ( với xác
suất nào đó)
LKH thng được đánh giá dựa trên 2 độ đo:
Độ phổ biến (support) : supp (X ⇒
⇒⇒
⇒ Y ) =P (X ∪
∪∪
∪ Y)
supp (X ⇒
⇒⇒
⇒ Y ) = supp(X
∪
∪∪
∪
Y)
Độ tin cậy (confidence) : conf (X ⇒
⇒⇒
⇒ Y ) = P(Y | X)
conf (X ⇒
⇒⇒
⇒ Y ) = supp(X
∪
∪∪
∪
Y) / supp(X)
KHÁI NIỆM CƠ BẢN
