TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG MÔN HỌC
KHAI PHÁ DỮ LIỆU
ƯƠ
Ậ Ế Ợ
CH
NG 3: KHAI PHÁ LU T K T H P
ươ ị
ả ộ ệ Gi ng viên B m ô n ễ : ThS. Nguy n V ng Th nh ố : H t h n g t h ô n g t in
ả
H i Phòng, 2013
ả
ề Th ô n g t in v g i n g v iê n
Họ và tên
Nguyễn Vương Thịnh
Đơn vị công tác
Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin
Học vị
Thạc sỹ
Chuyên ngành
Hệ thống thông tin
Cơ sở đào tạo
Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội
Năm tốt nghiệp
2012
Điện thoại
0983283791
thinhnv@vimaru.edu.vn
Website cá nhân http://scholar.vimaru.edu.vn/thinhnv
2
ề ọ
ầ
Th ô n g t in v h c p h n
Tên học phần
Khai phá dữ liệu
Tên tiếng Anh
Data Mining
Mã học phần
17409
Số tín chỉ
03 tín chỉ
Số tiết lý thuyết
39 tiết (13 tuần x 03 tiết/tuần)
Số tiết thực hành
10 tiết (05 tuần x 02 tiết/tuần)
Bộ môn phụ trách
Hệ thống thông tin
ƯƠ
Ọ
Ứ
P H
Ậ N G P HÁP H C T P, N GHIÊN C U
ổ ớ
ả
ả
ậ
ả
v N g h e g i n g , t h o lu n , t ra o đ i v i g i n g v iê n t rê n
ậ ở
ứ
n h à .
v T n g h iê n c u t à i li u v à là m b à i t p ƯƠ
P H
ờ
ự
ả
ữ
ầ
ể
ấ 7 5 % t h i g ia n . ọ ế t g i a h c p h n ( X = X2 = ( L1 +
l p .ớ ự ệ N G P HÁP Đ ÁN H GIÁ v S V p h i t h a m d ít n h t v Có 0 2 b à i k i m t ra v i
L2 ) /2 ) . ế
ệ
ắ
ọ
ầ
ằ
3
v Th i k t t h ú c h c p h n b n g h ìn h t h c
ứ t r c n g h i m
k h á c h q u a n t rê n m á y t ín h ( Z = 0 . 5 X + 0 . 5 Y) .
ệ
ả Tài li u tham kh o
1.
Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques,
Elsevier Inc, 2006.
2.
Ian H. Witten, Eibe Frank, Data Mining – Practical Machine Learning Tools and
ử ụ
ớ
ụ Techniques (the second edition), Elsevier Inc, 2005 (s d ng kèm v i công c
W e k a ).
3. Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems
(the 4th Edition), Pearson Education Inc, 2004.
4. Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn
ữ ệ
, NXB Giáo
Thu Trang, Nguyễn Cẩm Tú, Giáo trình Khai phá d li u Web
dục, 2009
4
5
ụ
ề
ở ể
ỗ ầ Cô n g c p h n m m h t rợ
c phát tri n b i nhóm nghiên c u c a tr ừ ầ ọ ườ ứ ủ n ă m 1 9 9 9 . Có ượ ( N e w Ze a la n d ) t
ỉ c h : ị đ a ề v i ạ ng Đ i ể t h
6
ề Ph n m m Weka đ h c Wa ik a t o ạ d o w n lo a d t h t t p ://w w w . c s . w a ik a t o . a c . n z /m l/w e k a /d o w n lo a d in g . h t m l
CHƯƠNG 3: KHAI PHÁ LUẬT KẾT HỢP
3.1. MỘT SỐ KHÁI NIỆM CƠ BẢN
3.2. TÌM TẬP PHỔ BIẾN VỚI GIẢI THUẬT APRIORI
3.3. SINH LUẬT KẾT HỢP TỪ CÁC TẬP PHỔ BIẾN
3.4. TÌM TẬP PHỔ BIẾN VỚI GIẢI THUẬT FP - GROWTH
3.5. MỘT SỐ DẠNG THỨC CỦA CSDL GIAO DỊCH
3.6. KHAI PHÁ LUẬT KẾT HỢP VỚI PHẦN MỀM WEKA
7
Ộ Ố
Ơ Ả
Ệ
3.1. M T S KHÁI NI M C B N
Cho một tập gồm n đối tượng I = {I1, I2, I3,…, In}, mỗi phần tử Ii
3.1.1. Khái niệm mục (item) và tập mục (item set)
∈
⊆ I được gọi là một mục (item). Một tập con bất kỳ X I được gọi là
một tập mục (item set).
Cho một tập D = {T1, T2,…, Tm}, mỗi phần tử Tj
∈ D được gọi là
I). ⊆
ộ ậ một giao dịch (transaction) và là một tập con nào đó của I (Tj ụ Người ta gọi D là cơ sở dữ liệu giao dịch (transaction database). ụ d li u g ia o
ơ ở ữ ệ ủ ồ ậ ị Ví d : I = { A, B, C, D , E, F} , ộ X = { A, D , E} là m t t p m c . M t c s d c h D g m c á c t p c o n Tj k h á c n h a u c a I: Số giao dịch có trong D ký hiệu là |D|.
T1
{A, B, C, D}
T2
{A, C, E}
T3
{A, E}
T4
{A, E, F}
T5
{A, B, C, E, F}
8
Milk, Bread, Coke 10:05
Beer, Bread 10:12
Beer, Milk, Diaper, Coke 10:15
Beer, Milk, Diaper, Bread 10:23
Milk, Diaper, Coke 10:30
9
3.1.2. Độ hỗ trợ (support) ứng với một tập mục
“Độ hỗ trợ ứng với tập mục X là xác suất xuất hiện của X trong
cơ sở dữ liệu giao dịch D”
)
Hoặc
X
sup(
“Đỗ hỗ trợ ứng với tập mục X là tỷ lệ các giao dịch có chứa X =
) trên tổng số các giao dịch có trong cơ sở dữ liệu giao dịch D”
C X ( D | |
{A, B, C, D}
T1
Ví d : X = {A, E} thì C(X) = 4 và sup(X) = 4/5 = 80%
Trong đó: C(X) là số lần xuất hiện của X hay số giao dịch có chứa X ụ
{A, C, E}
T2
{A, E}
T3
{A, E, F}
T4
T5
{A, B, C, E, F}
ị ưỡ ộ
10
ượ ọ ổ ậ ụ ướ c đ
ộ ỗ ợ ớ ơ ậ Các t p m c có đ h tr l n h n m t giá tr ng ng minsup nào đó ế c h o t r c g i là c á c t p p h b i n ( f re q u e n t it e m s e t ) .
3.1.3. Luật kết hợp (Association Rule)
Cho hai tập mục X, Y
⊆ I, X ∩ Y = ϕ. Luật kết hợp ký hiệu là X → Y
chỉ ra mối ràng buộc của tập mục Y theo tập mục X, nghĩa là khi X
ộ ỗ ợ ủ
ậ : là tỷ lệ (hay xác suất) xuất hiện cả X và Y
xuất hiện trong cơ sở dữ liệu giao dịch thì sẽ kéo theo sự xuất hiện
Luật kết hợp được đặc trưng bởi:
của Y với một một tỷ lệ nào đấy. Đ h tr c a lu t trong cùng một giao dịch.
)
(
=
=
�
X
Y
� X Y
sup(
)
sup(
)
C X Y D |
|
ộ
ủ
ậ : là tỷ lệ các giao dịch có chứa cả X và Y so
ậ Đ t in c y c a lu t với các giao dịch có chứa X.
)
sup(
)
=
=
(cid:0)
X
Y
conf (
)
X
Ȯ C X Y ( C X ) (
X sup(
Y )
Trong đó: C(X ∪ Y): Số giao dịch có chứa cả X và Y.
C(X): Số giao dịch có chứa X.
11
(cid:0)
Luật mạnh: Các luật có độ hỗ trợ lớn hơn một giá trị ngưỡng minsup và độ tin cậy lớn hơn một giá trị ngưỡng minconf cho trước được gọi là các luật “mạnh” hay “luật có giá trị” (strong association rules).
→ Cụ thể: ế ồ ờ
ạ ậ → ượ t h ì X Y đ là
12
N u đ n g t h i s u p ( X Y ) ≥ m in s u p v à c o n f ( X Y ) ≥ → ọ m in c o n f lu t m n h ( s t r o n g c g i a s s o c ia t io n ru le ) .
3.1.4. Bài toán khai phá luật kết hợp
Input:
Cơ sở dữ liệu giao dịch D. Các giá trị ngưỡng minsup, minconf. Tất cả các luật mạnh.
∪
|D
mincount = minsup * | � �
� �
13
Output: Để giải quyết bài toán khai phá luật kết hợp bao giờ cũng thường trải qua hai pha: Pha 1: Sinh tất cả các tập phổ biến có thể có. Ở pha này ta sử dụng các giải thuật tìm tập phổ biến như: Apriori, FP-Growth,... Pha 2: Ứng với mỗi tập phổ biến K tìm được ở pha 1, tách K thành hai tập X, Y không giao nhau (K = X Y và X ∩ Y = ϕ). Tính độ tin cậy của luật kết hợp X → Y, nếu độ tin cậy trên ngưỡng minconf thì nó là luật mạnh. Chú ý là nếu tập K có k phần tử thì số tập con thực sự của K sẽ là 2k – 2, tức là từ K ta sẽ sinh được tối đa là 2k - 2 luật. Lưu ý: Trong một số giải thuật, để xác định một tập là phổ biến người ta không sử dụng khái niệm độ hỗ trợ mà sử dụng khái niệm số lần xuất hiện (support count). Nếu số lần xuất hiện của tập mục trong cơ sở dữ liệu giao dịch lớn hơn một giá trị ngưỡng nào đấy thì nó là tập phổ biến. Giá trị ngưỡng này được xác định là:
Ậ
Ậ
Ả
Ổ Ế Ớ 3.2. TÌM T P PH BI N V I GI I THU T AP RIORI
3.2.1. Nguyên lý Apriori
:
ứ
ụ
ộ ậ ấ
ấ ấ
ứ
ệ
ậ
ầ
ệ ấ
“Nếu một tập mục là tập phổ biến thì mọi tập con khác rỗng bất kỳ
ầ , nên ta có: C(X’) ≥ C(X) (1).
X là tập phổ biến nên:
)
của nó cũng là tập phổ biến” Ch n g m in h Xét X’ ⊆ X. Ký hiệu p là ngưỡng độ hỗ trợ minsup. M t t p m c x u t h i n b a o n h iê u l n t h ì c á c t p co n ch a t ro n g n ó c ũ n g x u t h i n ít n h t b y n h iê u l n
X
p
sup(
)
C X (
)
p D |
| (2)
C X ( =� D | |
')
>
=
X
� p
C X (
')
p D |
� |
sup(
')
C X ( D |
|
Từ (1) và (2) suy ra:
Tức là X’ cũng là tập phổ biến (đpcm).
14
(cid:0)
3.2.2. Giải thuật Apriori
Dựa trên nguyên lý Apriori.
Hoạt động dựa trên Quy hoạch động:
Mục đích: Tìm ra tất cả các tập phổ biến có thể có.
Từ các tập Fi = { ci | ci là tập phổ biến, |ci| = i} gồm mọi tập mục phổ
biến có độ dài i (1 ≤ i ≤ k), đi tìm tập Fk+1 gồm mọi tập mục phổ biến
có độ dài k+1. Các mục I1, I2,…, In trong tập I được coi là sắp xếp theo
15
một thứ tự cố định.
Input:
ị C s d li u giao d ch D = {t1, t2,…, tm}. ể ưỡ
ộ ỗ ợ ố
Ng
ơ ở ữ ệ ng đ h tr t ậ ợ ấ ả
i thi u minsup. ổ ế
ậ
Output:
T p h p t
t c các t p ph bi n.
� �
| ;D � � ộ
mincount = minsup * | ậ ổ ế F1 = { các t p ph bi n có đ dài 1}; for(k=1; Fk != ?; k++) { Ck+1 = Apriori_gen(Fk);
D ∈
for each t {
⊆
Ck+1 và c
t};
∈ Ct ∈
Ct = { c | c for each c
c.count++;
∈
} Fk+1 = {c
Ck+1 | c.count ≥ mincount};
16
} return F =
FU k k
ủ ụ
Th t c con Apriori_gen • Thủ tục con Apriori_gen có nhiệm vụ sinh ra (generation) các tập mục có độ dài k+1 từ các tập mục có độ dài k trong tập Fk. • Được thi hành qua hai bước: nối (join) các tập mục có chung các tiền tố (prefix) và sau đó áp dụng nguyên lý Apriori để loại bỏ bớt những tập không thỏa mãn.
Cụ thể: v Bước nối: Sinh các tập mục c là ứng viên của tập phổ biến có độ dài k+1 bằng cách kết hợp hai tập phổ biến li và lj ∈ Fk có độ dài k và trùng nhau ở k-1 mục đầu tiên: c = li + lj = {i1, i2, …, ik-1, ik, ik’}. Với li = {i1, i2,…, ik-1, ik}, lj = {i1, i2,…, ik-1, ik’}, và i1 ≤ i2 ≤…≤ ik-1 ≤ ik ≤ ik’.
17
v Bước tỉa: Giữ lại tất cả các ứng viên c thỏa thỏa mãn nguyên lý Apriori tức là mọi tập con có độ dài k của nó đều là tập phổ biến (∀sk ⊆ c và |sk| = k thì sk ∈ Fk).
ổ ế
ậ ứ
ậ
ậ
ộ
ộ function Apriori_gen(Fk: t p các t p ph bi n đ dài k): T p ng viên có đ dài k+1 {
Fk∈
Ck+1 = ?; for each li
Fk∈
for each lj
if (li[1]=lj[1]) and (li[2]=lj[2]) … and (li[k1]=lj[k1]) and (li[k] ∪ {c}; c = {li[1], li[2], li[3],…, li[k], lj[k]};
if has_infrequent_subset(c, Fk) then
delete c;
else Ck+1 = Ck+1 } return Ck+1; } 18 Ứ ậ ộ ng viên có đ dài k+1, Fk: T p các ổ ế function has_infrequent_subset(c:
ộ
ậ
t p ph bi n đ dài k): Boolean
{ c ⊂
Fk then return True; for each sk
∉
if sk
return False; } 19 Hàm has_infrequent_subset làm nhiệm vụ kiểm tra xem một ứng
viên có độ dài k+1 có chứa tập không phổ biến hay không, nếu
có thì ứng viên lập tức bị loại. Đây là bước tỉa dựa trên nguyên lý
Apriori nhằm loại bỏ nhanh các ứng viên không thỏa mãn. v v = Để sinh các luật kết hợp: S minconf X S
\ )) ( (cid:0) (cid:0) Với mỗi tập phổ biến X ∈ F, ta xác định các tập mục không
rỗng là con của X.
Với mỗi tập mục con S không rỗng của X ta sẽ thu được một
luật kết hợp là S→(X\S). Nếu độ tin cậy của luật thỏa mãn
ngưỡng minconf thì luật đó là luật mạnh.
C X
)
(
conf (
C S
( )
ổ ế ậ ế ợ ậ ậ ậ function Rules_Generation(F: T p các t p ph bi n): T p các lu t k t h p
m nhạ
{ ổ ế ể ậ R = ?;
ậ
ộ
F=F \ F1; //Các t p ph bi n đ dài 1 không dùng đ sinh lu t
for each X F ∈
for each S if conf(S (X\S)) ≥ minconf then ∪ → X ⊂
→
R = R { S (X\S)}; 20 return R; } BÀI T P ÁP D NG ậ ố : Cho I = {A, B, C, D, E, F} và cơ sở dữ liệu giao dịch D: Bài t p s 1 T1 {A, B, C, F} T2 {A, B, E, F} T3 {A, C} T4 {D, E} T5 {B, F} 21 Chọn ngưỡng minsup = 25% và minconf = 75%. Hãy xác định các
luật kết hợp mạnh. = 25% *5 2 mincount = min sup * |D|
�
� =
� �
� � =
1.25
� � �
� � � C2 ậ ụ
T p m c F1 Sinh các t p ậ
ổ ế
ph bi n có
ộ
đ dài 1 Sinh các t p ậ
ộ
có đ dài 2
ằ
b ng cách
ậ
ố
n i các t p
ộ
có đ dài 1 {A}
{B}
{C}
{E}
{F} ố ầ
S l n
xu t ấ
hi nệ
3
3
2
2
3 {A}
{B}
{C}
{D}
{E}
{F} ố ầ
S l n
xu t ấ
hi nệ
3
3
2
1
2
3 T p ậ
m cụ
{A, B}
{A, C}
{A, E}
{A, F}
{B, C}
{B, E}
{B, F}
{C, E}
{C, F}
{E, F} {A, B}
{A, C}
{A, E}
{A, F}
{B, C}
{B, E}
{B, F}
{C, E}
{C, F}
{E, F} ố ầ
S l n
xu t ấ
hi nệ
2
2
1
2
1
1
3
0
1
1 ạ F2 Lo i các
ụ
ậ
t p m c
không
ỏ
th a mãn
nguyên lý
Apriori Sinh các t p ậ
ộ
ụ
m c có đ
ừ ậ
dài 3 t
t p
ổ ế
ph bi n F2 F3 C3 ậ
ụ
T p m c
{A, B, C}
{A, B, F}
{A, C, F} {A, B, F} ố ầ
S l n
xu t ấ
hi nệ
2 {A, B, F} ố ầ
S l n
xu t ấ
hi nệ
2 {A, B}
{A, C}
{A, F}
{B, F} ố ầ
S l n
xu t ấ
hi nệ
2
2
2
3 F3 chỉ có một phần tử nên không thể tiếp tục kết nối để sinh F4. Thuật
toán kết thúc. Ta có tập các tập phổ biến là: F ={{A}, {B}, {C}, {E}, {F}, {A, B}, {A, C}, {A, F}, {B, F}, {A, B, 22 F}} = = = A
conf ({ } 66.7% B
{ }) = = = (cid:0) B
conf ({ } 66.7% A
{ }) (cid:0) 2
3
2
3 {A, B} có thể sinh các luật: {A}→{B}, {B}→{A}
C A B
({ , })
C A
({ })
C A B
({ , })
C B
({ }) = = = {A, C} có thể sinh các luật: {A}→{C},
{C}→{A} A
conf ({ } C
{ }) 66.7% = = = (cid:0) C
conf ({ } A
{ }) 100% C A C
({ , })
C A
({ })
C A C
({ , })
C C
({ }) 2
3
2
2 (cid:0) = = = {A, F} có thể sinh các luật: {A}→{F}, {F}→{A} A
conf ({ } F
{ }) 66.7% = = = (cid:0) F conf ({ } A
{ }) 66.7% C A F
({ , })
C A
({ })
C A F
({ , })
C F
({ }) 2
3
2
3 23 (cid:0) = {B, F} có thể sinh các luật: {B}→{F}, {F}→{B} B
conf ({ } F
{ }) 100% C B F
({ , })
C B
({ }) 3
= =
3 = (cid:0) F conf ({ } B
{ }) 100% C B F
({ , })
C F
({ }) 3
= =
3 (cid:0) , }) = = = {A, B, F} có thể sinh các luật: {A}→{B, F}, {A, B}→{F},
{B}→{A, F}, {B, F}→{A}, {F}→{A, B}, {A, F}→{B} A
conf ({ } B F
{ , }) 66.7% C A B F
({ ,
C A
({ }) 2
3 , }) = = = (cid:0) A B
conf ({ , } F
{ }) 100% C A B F
({ ,
C A B
({ , }) 2
2 , }) = = = (cid:0) B
conf ({ } A F
{ , }) 66.7% C A B F
({ ,
C B
({ }) 2
3 = = = (cid:0) B F conf ({ , } A
{ }) 66.7% C A B F
, })
({ ,
C B F
({ , }) 2
3 24 (cid:0) , }) = = = F conf ({ } A B
{ , }) 66.7% C A B F
({ ,
C F
({ }) 2
3 = = = (cid:0) A F conf ({ , } B
{ }) 100% C A B F
, })
({ ,
C A F
({ , }) 2
2 (cid:0) 25 Như vậy các luật kết hợp mạnh thu được gồm:
{C}→{A}, {B}→{F}, {F}→{B}, {A, B}→{F}, {A, F}→{B} ậ ố : Cho I = {A, B, C, D, E, F} và cơ sở dữ liệu giao dịch D: Bài t p s 2 T1
T2
T3
T4
T5
T6 {D, E}
{A, B, D, E}
{A, B, D}
{C, D, E}
{F}
{B, C, D} 26 Chọn ngưỡng minsup = 20% và minconf = 70%. Hãy xác định
các luật kết hợp mạnh. = 20% *6 2 =
� �
� � =
1.2
� � �
� � � ậ ụ
T p m c C2 F1 {A}
{B}
{C}
{D}
{E} ố ầ
S l n
xu t ấ
hi nệ
2
3
2
5
3 mincount = min sup * |D|
�
�
ố ầ
S l n
xu t ấ
hi nệ
2
3
2
5
3
1 {A}
{B}
{C}
{D}
{E}
{F} T p ậ
m cụ
{A, B}
{A, C}
{A, D}
{A, E}
{B, C}
{B, D}
{B, E}
{C, D}
{C, E}
{D, E} {A, B}
{A, C}
{A, D}
{A, E}
{B, C}
{B, D}
{B, E}
{C, D}
{C, E}
{D, E} ố ầ
S l n
xu t ấ
hi nệ
2
0
2
1
1
3
1
2
1
3 ụ
ậ
T p m c
{A, B, D} F3 C3 F2 {A, B, D} ố ầ
S l n
xu t ấ
hi nệ
2 {A, B, D} ố ầ
S l n
xu t ấ
hi nệ
2 {A, B}
{A, D}
{B, D}
{C, D}
{D, E} ố ầ
S l n
xu t ấ
hi nệ
2
2
3
2
3 27 Tập F3 chỉ có một phần tử nên không thể tiếp tục kết nối để sinh
ứng viên cho tập F4. Thuật toán kết thúc. Tập các tập phổ biến
thu được:
F = {{A}, {B}, {C}, {D}, {E}, {A, B}, {A, D}, {B, D}, {C, D},
{D, E}, {A, B, D}} = = = {A, B} sinh luật: {A}→{B}, {B}→{A} A
conf ({ } B
{ }) 100% C A B
({ , })
C A
({ }) 2
2 (cid:0) = = = (cid:0) B conf ({ } A
{ }) 66.7% C A B
({ , })
C B
({ }) 2
3 = = = {A, D} sinh luật: {A}→{D},
{D}→{A} A
conf ({ } D
{ }) 100% C A D
({ , })
C A
({ }) 2
2 = = = (cid:0) D 40% conf ({ } A
{ }) C A B
({ , })
C D
({ }) 2
5 (cid:0) = {B, D} sinh luật: {B}→{D},
{D}→{B} B conf ({ } D
{ }) 100% C B D
({ , })
C B
({ }) 3
= =
3 = (cid:0) D
conf ({ } B
{ }) 60% 28 C B D
({ , })
C D
({ }) 3
= =
5 (cid:0) = = = {C, D} sinh luật: {C}→{D},
{D}→{C} D
conf ({ } C
{ }) 40% C C D
({ , })
C D
({ }) 2
5 = = = (cid:0) C D
{ }) conf ({ } 100% 2
2 C C D
({ , })
C C
({ })
{D, E} sinh luật: {D}→{E},
{E}→{D} (cid:0) = (cid:0) D
conf ({ } E
{ }) 60% = C D E
({ , })
C D
({ }) 3
= =
5 E D
{ }) conf ({ } 100% C D E
({ , })
C E
({ }) , }) = = = (cid:0) 3
= =
3
{A, B, D} sinh luật: {A}→{B, D}, {A, B}→{D}, {B}→{A, D}, {B,
D}→{A}, {D}→{A, B}, {A, D}→B
A B
conf ({ , } D
{ }) 100% C A B D
({ ,
C A B
({ , }) 2
2 , }) = = = (cid:0) A
conf ({ } B D
{ , }) 100% C A B D
({ ,
C A
({ }) 2
2 29 (cid:0) , }) = = = B
conf ({ } A D
{ , }) 66.7% C A B D
({ ,
C B
({ }) 2
3 , }) = = = (cid:0) B D
conf ({ , } A
{ }) 66.7% C A B D
({ ,
C B D
({ , }) 2
3 , }) = = = (cid:0) D
conf ({ } A B
{ , }) 40% C A B D
({ ,
C D
({ }) 2
5 , }) = = = (cid:0) A D
conf ({ , } B
{ }) 100% C A B D
({ ,
C A D
({ , }) 2
2 (cid:0) 30 Các luật kết hợp mạnh thu được gồm:
1. {A}→{B}
2. {A}→{D}
3. {B}→{D}
4. {C}→{D}
5. {E}→{D}
6. {A}→{B, D}
7. {A,B}→{D}
8. {A, D}→B C 1 C 2 : Kết xuất các mục phổ biến dựa trên
B
cây FP. Thao tác duyệt cây được thực hiện tại
bước này.
31 C 1 : XÂY D N G CÂY B
FP (Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques) 32 v Qu é t CS D L g ia o d c h v à đ m s l n x u t i t h t c á c m c t ro n g m i g ia o
l n c g n t r n g s là s v Gi i t h u t FP Gro w t h đ c l n l 33 v Th t c t u â n
t h t ro n g s u t q u á t rìn h x â y d n g c â y
FP.
v Cá c đ v t rí t rù n g đ c a đ n h c s v Co n t r đ 34 B (Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques) 35 ng v i m i m c ph bi n Ii:
v Xâ y d n g t p c á c c s n g đ i. đ v D u y t c â y FP c ó đ i u k i n đ s in h c á c t p
36
là Ii. p h b i n c ó h u t Ví d 1ụ : Ch o c s
g ia o d c h : TID
100
200
300
400
500 Items bought
{f, a, c, d, g, i, m, p}
{a, b, c, f, l, m, o}
{b, f, h, j, o}
{b, c, k, s, p}
{a, f, c, e, l, p, m, n} t n g 37 ớ ỗ ụ ố ầ ứ ể ấ ệ
q Quét CSDL đ tính s l n xu t hi n (support count) ng v i m i m c: TID
100
200
300
400
500 Items bought
{f, a, c, d, g, i, m, p}
{a, b, c, f, l, m, o}
{b, f, h, j, o}
{b, c, k, s, p}
{a, f, c, e, l, p, m, n} mincount = 3 Item frequency
4
f
4
c
3
a
b
3
m 3
3
p ạ ỏ ụ ổ ế ả q Lo i b c á c m c k h ô n g p h i là p h b i n .
q S p c á c m c t ro n g m i g ia o d c h t h e o t h t ụ ỗ ắ ị ứ ự ả ủ g i m c a s u p p o rt c o u n t . {f, c, a, b, m} 38 TID
100
200
300
400
500 Items bought (ordered) frequent items
{f, a, c, d, g, i, m, p} {f, c, a, m, p}
{a, b, c, f, l, m, o}
{b, f, h, j, o} {f, b}
{b, c, k, s, p} {c, b, p}
{a, f, c, e, l, p, m, n} {f, c, a, m, p} {f, c, a, b, m} TID
100
200
300
400
500 Items bought (ordered) frequent items
{f, a, c, d, g, i, m, p} {f, c, a, m, p}
{a, b, c, f, l, m, o}
{b, f, h, j, o} {f, b}
{b, c, k, s, p} {c, b, p}
{a, f, c, e, l, p, m, n} {f, c, a, m, p} Đọc từng giao dịch và ánh xạ vào cây FP: {} {} {f, c, a, b, m} {f, c, a, m, p} f:1 f:2 c:1 c:2 {} a:1 a:2 m:1 b:1 m:1 39 p:1 p:1 m:1 Đọc từng giao dịch và ánh xạ vào cây FP (tiếp) {} {} {} {f, b} {c, b, p} {f, c, a, m, p} f:3 c:1 f:3 f:4 c:1 c:2 b:1 b:1 c:2 c:3 b:1 b:1 b:1 a:2 p:1 a:2 a:3 p:1 m:1 b:1 m:1 b:1 m:2 b:1 Node-Link 40 p:1 m:1 p:1 m:1 p:2 m:1 Cây FP hoàn chỉnh: {} Header Table f:4 c:1 c:3 b:1 b:1 a:3 p:1 Item head
f
c
a
b
m
p m:2 b:1 41 p:2 m:1 v Xé t m c pụ {} : Header Table ơ ở ệ ề ẫ f:4 c:1 C s m u c ó đ i u k i n ồ g m : fc a m :2 v à c b :1 c:3 b:1 b:1 {} a:3 p:1 {} f:2 Item head
f
c
a
b
m
p m:2 b:1 c:1 c:2 c:3 p:2 m:1 b:1 a:2 m:2 42 ổ ậ ế
T p p h b i n là : c p :3 v Xé t m c mụ {} : Header Table ơ ở ệ ề ẫ C s m u c ó đ i u k i n f:4 c:1 ồ g m : fc a :2 v à fc a b :1 c:3 b:1 b:1 {} {} a:3 p:1 f:3 Item head
f
c
a
b
m
p m:2 b:1 f:3 p:2 m:1 c:3 c:3 a:3 a:3 b:1 ổ ế ồ ậ T p p h b i n g m : f m :3 , f c m :3 , f c a m :3 , f a m :3 , c m :3 , 43 c a m :3 , a m :3 v Xé t m c bụ {} : Header Table ơ ở ệ ề ẫ C s m u c ó đ i u k i n f:4 c:1 ồ g m : fc a :1 , f :1 v à c :1 c:3 b:1 b:1 {} a:3 p:1 f:2 Item head
f
c
a
b
m
p m:2 b:1 {} c:1 p:2 m:1 c:1 44 a:1 v Xé t m c aụ {} : Header Table ơ ở ệ ề ẫ C s m u c ó đ i u k i n f:4 c:1 ồ g m : fc :3 {} c:3 b:1 b:1 a:3 p:1 f:3 Item head
f
c
a
b
m
p m:2 b:1 c:3 p:2 m:1 v Xé t m c cụ ổ ồ ế ậ T p p h b i n g m : f a :3 , : f c a :3 , c a :3 ơ ở ệ ề ẫ C s m u c ó đ i u k i n ồ g m : f :3 {} 45 f:3 ồ ổ ậ ế
T p p h b i n g m : f c :3 {} Header Table f:4 c:1 c:3 b:1 b:1 a:3 p:1 Item head
f
c
a
b
m
p m:2 b:1 Mục Cơ sở mẫu có điều kiện Tập phổ biến Cây FP có điều
kiện p:2 m:1 46 Ví d 2ụ : Ch o c s
g ia o d c h : t n g 47 ấ ố ầ
ắ ủ
ệ
l n x u t h i n c a c á c
ả
ứ ự
g i m Số lần xuất hiện Tập mục ế
Đ m s
ụ
m c v à s p t h e o t h t
d n :ầ 48 49 50 51 52 v Xé t m c I5ụ : ơ ở ề ệ ẫ C s m u c ó đ i u k i n ồ g m : I2 – I1 :1 , I2 – I1 – I3 :1 ổ ồ ế ậ T p p h b i n g m : I2 I5 :2 , 53 I2 I1 I5 :2 , I1 I5 :2 v Xé t m c I4ụ : ơ ở ề ệ ẫ C s m u c ó đ i u k i n ồ g m : I2 – I1 :1 , I2 :1 ổ ồ ậ ế
T p p h b i n g m : I2 54 I4 :2 v Xé t m c I3ụ : ơ ở ề ệ ẫ C s m u c ó đ i u k i n ồ g m : I2 – I1 :2 , I2 :2 , I1 :2 ồ ổ ế ậ T p p h b i n g m : I2 I3 :4 , 55 I2 I1 I3 :2 , I1 I3 :4 v Xé t m c I1ụ : ơ ở ệ ề ẫ C s m u c ó đ i u k i n ồ g m : I2 :4 ồ ổ ậ ế
T p p h b i n g m : I2 56 I1 :4 57 ́ ́ ̣ ̣ ̣ ̣ ́ ̃ Ậ ̉ ̣ ̣ ̣ ́
I D AN G MA TR N GIA TRI N HI P HÂN 3 . 5 . 1 . BIÊU D IÊN D q T p c á c m c I = { A1 , A2 , . . . , An } v à CS D L g ia o d c h D = ụ ậ ị ̀ { T1 , T2 , . . . , Tm }
ứ ươ ớ ̣ n g n g v i g ia o d ic h Ti ứ
́ ́ ươ ư ̣ ̣ ơ
n g n g v i m u c Aj q D o n g t h i t
q Cô t t h j t
̀
q P h â n t ̀ ứ
ử ̣ ̣ ̣ ́ ̣ ̣ ̣ ̣ ̣ a i, j n h â n g iá t ri 1 ( TRUE) h o ă c 0 ( FALS E) t u y
̀
A1 ́
co xuâ t hiên
An t h u ô c v a o v iê c m u c Aj
. . . trong giao dich Ti hay không? 58 B C D E T1 {B, C, E} T1 0 1 1 0 1 T2 {A, B, C} T2 1 1 1 0 0 T3 {B, E} T3 0 1 0 0 1 T4 {B, C, E} T4 0 1 1 0 1 T5 {A, B, C, E} T5 1 1 1 0 1 T6 {B, C, D} 59 T6 0 1 1 1 0 ̃ ́ ƯƠ Ậ ̉ ̣ ̣ 3 . 5 . 2 . BIÊU D IÊN D ́
I D AN G MA TR N GIA TRI ̀ ứ ươ ớ ̣ ứ
́ ́ ươ ư ộ ơ ̣ n g n g v i g ia o d ic h Ti
n g n g v i t h u c t ín h Aj q D o n g t h i t
q Cô t t h j t
q P h â n t ứ
̀ ử ộ ề ̣ ̣ ị
a i, j n h â n g iá t ri d jk n à o đ ó t h u c m i n g iá t r ủ ộ d o m ( Aj) c a t h u c t ín h Aj ặ ộ ứ ế ớ c v i ể ượ
q C m t c p g h é p ( Aj, d jk ) ( c ó t h đ
ị ộ ậ ượ t là Aj = d jk v i
ớ
c x e m là h à m ý “ t h u c t ín h Aj n h n g iá t r d jk ” ) m i đ
m t ộ m cụ ( It e m ) . ứ ư ề ả ị ấ
m c ) .ụ 60 q Cá c lu t k t h p lú c n à y t h ợ ế ậ ườ ượ ễ ể ướ n g đ c b i u d i n d i ạ d n g : ể ướ ạ ậ ể
q Cũ n g c ó t h p h á t b i u d i d n g lu t “ N uế . . . Th ì. . . ” : N u :ế 61 Th ì: A B C D E T1 {(A=1),(B=2),(C=1),(D=3), (E=2)} 1 T1 2 1 3 2 T2 {(A=1),(B=3),(C=2),(D=1), 1 T2 3 2 1 2 (E=2)} 1 T3 3 2 3 1 T3 {(A=1),(B=3),(C=2),(D=3), (E=1)} 2 T4 3 2 2 2 T4 {(A=2),(B=3),(C=2),(D=2), 3 T5 1 1 3 1 (E=2)} 2 T6 3 2 1 2 T5 {(A=3),(B=1),(C=1),(D=3), (E=1)} T6 {(A=2),(B=3),(C=2),(D=1), ậ Lu t { ( A= 1 ) , (E=2)} → ( B= 3 ) } { ( C= 2 ) } c ó : s u p = 2 /6 = 3 3 . 3 % c o n f = 2 /2 = 1 0 0 %
ể ể ễ ậ ướ Lu t n à y c ó t h b i u d i n d ạ
i d n g : → ( A= 1 ) ^ ( B= 3 ) ( C= 2 ) Ho c :ặ 62 ớ ế N u A = 1 v à B = 3 t h ì C = 2 v i x á c ấ s u t 1 0 0 % → ậ Lu t { ( o u t lo o k = s u n n y ) , ( t e m p e ra t u re = h o t ) } { ( p la y = n o ) } c ó : s u p = 2 /1 4 = 1 4 . 3 % c o n f = 2 /2 = 1 0 0 % ể ễ ể ậ ướ Lu t n à y c ó t h b i u d i n d ạ
i d n g : → ( o u t lo o k = s u n n y ) ^ ( t e m p e ra t u re = h o t ) ( p la y = n o ) ớ ế N u o u t lo o k = s u n n y v à t e m p a ra t u re = h o t t h ì p la y = n o v i ấ
x á c s u t 1 0 0 % ở ộ ọ ề ầ 64 Kh i đ n g p h n m m We k a , c h n
Ex p lo re r: Ch n t p tin d li u s d ng 65 D li u c n k h a i
p h á L u ý: Weka ch làm vi c t c bi u di n 66 Clic k đ t h i t l p c á c 67 ế ậ t l p c á c t h ô n g Th i
:ố
s đ 68 ế ả K t q u k h a i p h á : 69 70Ậ
Ậ
Ổ
Ế Ợ Ừ
3.3. SINH LU T K T H P T CÁC T P PH
BI NẾ
Ụ
Ậ
Ậ
Ả
Ậ
Ổ Ế Ớ
3.4. TÌM T P PH BI N V I GI I THU T
FP GROWTH
ậ
ầ
n g
ế
ệ
ở ạ
ứ
ư ưở
: Ch o p h é p p h á t h i n ra c á c t p
T t
ổ
p h b i n m à k h ô n g c n k h i t o c á c n g
v iê n .
: Xây dựng một cấu trúc dữ liệu thu
ƯỚ
B
gọn gọi là cây FP. Bước này chỉ yêu cầu quét
CSDL giao dịch 02 lần.
ƯỚ
ƯỚ
Ự
ế
ị
ố ầ
ấ
ụ
ỗ
ớ
h i n n g v i m i m c .
ệ ứ
ạ
ổ
ế
ỏ
ạ
ụ
ứ ự
ụ
ỗ
v Lo i b c á c m c k h ô n g p h b i n .
ắ
v S p l
ị
ứ ự
ố ầ
ủ
ả
ầ
g i m d n c a s
d c h t h e o t h t
ệ
x u t h i n .
ươ
ứ
ủ
ộ
ấ
ỗ
v M i n ú t c a c â y t
ọ
ượ
ụ
ấ
ố
ắ
ớ
n g n g v i m t m c
ố ầ
l n x u t
ậ
ượ
v à đ
h i n .ệ
ả
ị
ỗ
ườ
ầ
ứ
ố
ấ
n g đ i ( x u t p h á t t
ừ
t t n g
ớ
n g n g v i m i
n ú t g c ) t rê n c â y
ọ
ạ ươ
g ia o d c h v à á n h x t
ừ
đ
FP.
ụ
ủ
s p x p c a c á c m c đ
ế
ố
ượ
ự
ứ ự ắ
ủ
ườ
ữ
ể
ể
ị
ố
ề
ử
ử
ỗ ầ
ỉ
ố ủ
ở ị
ượ
n g đ i c ó t h c ó t h c ó n h n g
ạ
đ o n t rù n g n h a u d o c á c g ia o d c h c ó c á c
ầ
p h n t
t ro n g
c h u n g ( c h u n g t i n t
ọ
ầ
t rù n g t h ì t r n g
d ã y ) . M i l n c ó p h n t
c t ă n g lê n
s
1 .
ể
ử ụ
ơ
ệ
ạ
ỏ ượ
ố
ế
ộ
ụ
d n g đ d u y t rì d a n h
ữ
s á c h k t n i đ n g i a c á c n ú t đ i d i n
c h o c ù n g m t m c .
ƯỚ
Ậ
Ổ
C 2 : S IN H T P P H
BI NẾ
ệ
( d u y t c â y FP )
Ứ
ổ ế
ớ ỗ ụ
ự
ậ
ơ ở
ẫ
ề
ệ
ẫ
ệ
ề
ộ
ỉ
ườ
ỉ
ỗ
ố ừ ỉ
ứ
ượ
n g đ i n i t
ề ớ đ n h c ó c h a m c Ii
ọ
ớ
ố ằ
b n g v i t r n g s
ở
ứ
ẫ
m u c ó đ i u k i n
( c o n d it io n a l p a t t e rn b a s e ) . M i m u c ó
ố
đ n h g c
đ i u k i n là m t đ
. M i ỗ
ụ
i ớ đ n h c h a
k v i
t
ẫ
ố
ọ
c g á n t r n g s
m u đ
ỉ
ủ
c ó c h a m u Ii
c a đ n h
ự
ề
ố ườ
c u i đ
ệ
ợ
ự
ế
ẫ
ố ứ
ố
ọ
ề
ế
( n u c ó ) . Kh i đ ó t r n g s
ố
ổ
ớ
ọ
v Xâ y d n g c â y FP c ó đ i u k i n ( c o n d it io n a l
ệ
FP t re e ) d a t rê n v i c k t h p c á c m u c ó
n g
c h u n g t i n t
ượ
ỉ
ỗ
c
v i m i đ n h là t n g c á c t r n g s
g h é p .
ệ
ề
ể
ệ
ậ
ố
ổ
ế
ậ
ơ ở ữ ệ
ồ
ị
d li u g ia o d c h D g m c á c
ị
ưỡ
ậ
ổ
n g m in s u p = 6 0 %. Hã y t ìm c á c t p p h
ế
Bi
b i n .ế
fcam:2, cb:1
p:3, cp:3
p
fca:2, fcab:1
m
m:3, fm:3, fcm:3, fcam:3,
fam:3, cm:3, cam:3, am:3
fca:1, f:1, c:1
Null
b:3
b
fc:3
a:3, fa:3, fca:3, ca:3
a
f:3
c:4, fc:3
c
Null
Null
f:4
f
ơ ở ữ ệ
ồ
ị
d li u g ia o d c h D g m c á c
ị
ưỡ
ậ
ổ
n g m in s u p = 2 2 %. Hã y t ìm c á c t p p h
ế
Bi
b i n .ế
I2
7
I1
6
I3
6
I4
2
I5
2
Giao dịch
Danh sách mục
T100
I2, I1, I5
T200
I2, I4
T300
I2, I3
T400
I2, I1, I4
T500
I1, I3
T600
I2, I3
T700
I1, I3
T800
I2, I1, I3, I5
T900
I2, I1, I3
NULL
NULL
I2:
2
I2:
2
I1:
2
I1:
2
I3:
1
NULL
NULL
I2:
2
I2:
2
I1:
1
NULL
I2:
4
I1:
2
I1:
2
NULL
I2:
4
̉ Ơ Ở Ư
Ư
̃
3.5. MÔT SÔ DANG TH C CUA C S D
LIÊU GIAO D ICH
ƯƠ
A2
T1
a1,1
a1,2
. . .
a1,n
T2
a2,1
a2,2
. . .
a2,n
T3
a3,1
a3,2
. . .
a3,n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . .
Tm-1
am-
1,n
am-
1,1
am-
1,2
Tm am,1
am,2
. . .
am,n
I = {A, B, C, D, E}
D = {T1, T2, T3, T4, T5,
T6}
A
An
A1
. . .
ộ
A2
q T t c c á c g ia o d c h đ u c ó đ d à i n h n h a u ( c h a n
T1
a1,1
a1,2
. . .
a1,n
T2
a2,1
a2,2
. . .
a2,n
T3
a3,1
a3,2
. . .
a3,n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Tm-1
. . .
am-
1,1
am-
1,2
am-
1,n
Tm am,1
am,2
. . .
am,n
Ế Ợ Ớ
Ầ
Ậ
3.6. KHAI PHÁ LU T K T H P V I
Ề
P H N M M W EKA
ữ ệ ử ụ
ọ ậ
ữ ệ
ầ
ư
ỉ
ễ ở ạ
ể
ậ
ệ ố ớ ữ ệ ượ
t v i d li u đ
ị
d ng ma tr n giá tr
ọ
ế
ậ
ọ
Ch n k h a i p h á lu t k t
h pợ
ặ
ị
ậ
Ch n t h u t t o á n k h a i
p h á
( m c đ n h là Ap rio ri)
ể
ế ậ
t h ô n g s ố
ố
ể
ộ
ưỡ
N g
n g đ
ậ
t in c y t
i
t h i u ể
( m in c o n f)
ưỡ
N g
n g
ộ ỗ ợ
đ h t r
ố
i t h i u
t
( m in s u p )
ọ
ị
ạ
Ch n lo i
ặ
ộ
đ đ o ( m c
đ n h là
ộ
d ù n g đ t in
c y )ậ
ộ
n g đ
i
ưỡ
N g
ỗ ợ ố
h t r t
đ a
( m a x s u p )
ố
ậ
S lu t
ố
i đ a
t
ể
ượ
c h i n
t h ị
Có c h o
p h é p
ệ
h i n kè m
c á c t p ậ
ể
ổ
p h b i n
h a y
k h ô n g
ỏ
ậ
Cá c lu t t h a
m ã n
Q & A
