ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
LỜI CẢM ƠN
 ! 
"!#$%&'"!#!()*+,&'
- ./01)234567$.89.:
;'5'</.,(
"=#./,.%&#6<05%>?@5
A$BC3D<#.E&EF)(
!(&'"!#!G
)!3,(()*+,&'- ./(% 
.,9D&>HIJ(BK*'6$5LH 
,()*
'</.,(MNB)O()*+, 
M'- ./7$.8,!()*6$5LH 
6<09(P(6$
"KQ9R<S>.>'.5,T./7$.8. 
5L9(A%(BKP(6$5<.:K#$
U*'5&>H@,.:&!(&RD>B@A 
.?(A6.)0BV@$1W'!5,
X
- YZY[O\YY]
5L
Hồ Xuõn Hựng
MỤC LỤC
1
ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
LÝ THUYẾT TỔNG QUAN 10
1.1 SƠ LƯỢC VỀ KHAI PHÁ TRI THỨC 11
1.2 BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP 21
1.3 THUẬT TOÁN TèM LARGE ITEMSET - APRIORI 26
1.4 THUẬT TOÁN SINH LUẬT 31

Từ viết tắt Từ gốc
KDD Knowledge Discovery from Data
MIS Minimum Item Support
TID Transaction Identifier
DD Data Distribution
DMA Distritbuted Mining of Association Rules
DIC Dynamic Itemset Counting
CD Count Distribution
AIS
R. Agrawal – T. Imielinski – A. Swami
MFCS
Maximum Frequent Candidate Set
MFS
Maximum Frequent Set
SETM
Set-Oriented Mining for Association Rules.
DHP
Direct Hashing and Puning
FP-Tree
Frequent pattern tree
DIC
Dynamic Itemset Counting
DANH MỤC CÁC THUẬT NGỮ
5
ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
Tên tiếng Anh Tên Tiếng Việt Ý nghĩa
Item Khoản mục Một thuộc tính trong Cơ sở dữ liệu giao
dịch
Itemset Tập các khoản mục Tập hợp các khoản mục
Association Rule Luật kết hợp

Khai phá Tri thức là hoạt động tư duy của con người dựa trên sự tri giác kết
quả đạt được từ việc khai phá dữ liệu. Tri thức có được do khai phá dữ liệu có
thể phân thành 2 loại như sau:
a. Phân lớp (Classification) :Mục đích là tìm ra tập các khẳng định
(predicate) mô tả các lớp đối tượng dữ liệu và áp dụng để xác định một
đối tượng dữ liệu thuộc hay không thuộc các lớp trên.
b. Kết hợp (Association) :Tri thức cho biết quan hệ giữa các thuộc
tính của đối tượng dữ liệu dưới dạng luật, gọi là luật kết hợp. Cơ sở lý
thuyết cho lớp bài toán khai phá tri thức kết hợp là dựa trên việc thống kê
mức độ thường xuyên xảy ra đồng thời các thuộc tính đú trờn một cơ sở
dữ liệu.
“Nghiờn cứu các phương pháp khai phá luật kết hợp và áp dụng để khai phá
dữ liệu tác nghiệp” là nội dung, đồng thời cũng là tên của đề tài tốt nghiệp
này. Đề tài giới thiệu về bài toán khai phá luật kết hợp cùng với các phương
pháp, thuật toán kinh điển nhưng quan trọng và đặc biệt bám sát các phương
pháp mới kể từ sau năm 2000. Đề tài cũng đưa ra đánh giá về hiệu năng của
một số thuật toán dựa trên kết quả thử nghiệm cài đặt các thuật toán đó.
Lí do chọn đề tài
Đề tài này được lựa chọn bởi những lí do sau:
a. Đề tài nghiên cứu có khả năng ứng dụng cao, được áp dụng để khai phá
thông tin trong nhiều lĩnh vực của xã hội, như Y tế, Bảo hiểm, Chứng
khoán v.v
b. Đề tài nghiên cứu là vấn đề quan trọng trên thế giới nhưng còn rất mới
mẻ tại Việt Nam.
c. Đề tài nghiên cứu có sự thách thức nhất định về chuyên môn, đòi hỏi
người tham gia phải nắm vững được những vấn đề chuyên môn khác
như: cơ sở dữ liệu, tính toán song song, kĩ thuật lập trình v.v
Mục tiêu của đề tài
Trong khuôn khổ của một bài luận văn tốt nghiệp, mục tiêu của đề tài được
xác định gồm:

ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
PHẦN I
CƠ SỞ LÝ THUYẾT
aBb(5A.%<1><LP'.> 3LH 
W'<65O':D<J>IP'5%&'$3D<# 
9
ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
6&'$<6&>0$&.E5A.%c$$(V> 
&>&'$<65.c#6$(5DLH 
.5%&'$BC3D<#'O
 3d
e ")ef1>IP'
\ ")\g BK5A.%C( 
h ")hM'$BC3D<#'O
LÝ THUYẾT TỔNG QUAN
gi.JW')<2#D5A.%IP'5>>5% 
&'$3D<#")GBB5j(').EW'&'$<6 
&>0$B52&N6&D5A.%.)0.%6$:@d
• "O5%&'$(H5&'$3D<#"&N6&' 
$.E5BB
• "O5%&'$<6&>0$^&#JAP
(&'$`
10
ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
• 6&'$<6&>0$&.Ek$((
1.1 SƠ LƯỢC VỀ KHAI PHÁ TRI THỨC
1.1.1 Khái niệm & nguồn gốc
Phát hiện tri thức và Khai phá dữ liệu (KDD) đang là hướng nghiên cứu thu
hút nhiều sự quan tâm trong vòng hai thập kỉ trở lại.
Bắt nguồn từ việc các công ty kinh doanh hoặc các công ty nghiên cứu thị

• Phân tích mẫu (Pattern analysis) : Tỡm cỏc mẫu đặc biệt trong dữ liệu lớn
Loại dữ liệu dùng để khai phá
Khai phá tri thức thường được áp dụng trên những loại dữ liệu như: Quan hệ
(relational), Giao dịch (transactional), Đối tượng (object-oriented), Tiến hoá
(temporal), multi-media …
Các kĩ thuật khai phá tri thức
• Thống kê (statistics)
• Học biểu tượng (symbolic learning)
• Mạng Nơron (neural networks)
• Mô hình hoá (visualization)
1.1.2 Các bước khai phá tri thức
Quá trình khai phá tri thức bao gồm những bước dưới đây:
Phát hiện và hiểu vấn đề :Hiểu phạm vi, lĩnh vực của bài toán và phát biểu
lại bài toán dưới dạng mô hình toán học
Thu thập và tiền xử lí dữ liệu : Xứ lí dữ liệu bị mất (missing data), loại
bỏ nhiễu (noises), chuyển dạng dữ liệu (transformation) và rút gọn dữ liệu
(reduction)
12
NG DễNG Lí THUYT LUT KT HP KHAI PH D LIU TC NGHIP
Khai phỏ d liu : Trớch lc mu (patterns) v/hoc mụ hỡnh
(models). Quỏ trỡnh ny gi l quỏ trỡnh phỏt hin tri thc.
ỏnh giỏ kt qu : Duyt mu, mụ hỡnh tỡm c (Loi b cỏc mu,
mụ hỡnh khụng cú ớch)
ng dng kt qu : a kt qu vo thc t (tr thnh d liu cho
chng trnh khỏc hoc thụng bỏo trc tuyn)
Hỡnh 1-1 Cỏc bc khai phỏ tri thc
1.1.3 Cỏc phng phỏp khai phỏ d liu
Khai phỏ d liu l bc quan trng nht trong quỏ trỡnh khai phỏ tri thc.
Cụng on khai phỏ tri thc c thc hin sau cỏc quỏ trỡnh thu thp v tinh
lc d liu, cú ngha l ch tm cc mu (pattern) cú ý ngha trờn tp d liu

coi như hàm tuyến tính với income.
Hình 1-3 Minh họa hồi qui
14
Income
Debt Income
Debt
Regression Line
ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
Tạo nhóm (Clustering)
Tạo nhóm là một nhiệm vụ thường thấy, bằng cách tìm kiếm các tập xác định
phân theo loại nhằm mô tả dữ liệu. Các loại có thể phân biệt hoặc giao nhau.
VD: tạo cỏc nhúm khách hàng giống nhau theo một cách nào đó trong CSDL
marketing hay xác định cỏc nhúm dải phổ hồng ngoại từ các ảnh chụp trên bầu
trời.
Hình dưới biểu diễn một cách tạo nhóm cho tập dữ liệu vay thành 3 nhóm.
Chú ý rằng cỏc nhúm có thể giao nhau.
Hình 1-4 Tạo nhóm cho tập dữ liệu vay
Tổng hợp (Summerizations)
Tổng hợp bao gồm các phương pháp tìm kiếm một cách mô tả ngắn gọn súc
tích một tập con dữ liệu. Các kỹ thuật tổng hợp thường được áp dụng trong
việc phân tích các dữ liệu tương tác và sinh báo cáo tự động.
Bài toán này rất quan trọng trong TextMining. Trong CSDL hiện nay, đa phần
các trường lại có kiểu Text, nhiều khi là mô tả hiện tượng, yêu cầu giải quyết
vấn đề, thăm dò ý kiến khách hàng. Rõ ràng một công việc vô cùng cần thiết

lượng mô tả bao gồm: độ chính xác dự đoán (predictive accuracy), độ mới
(novelty), độ hữu dụng (utility), và mức độ hiểu được của mô hình. Các tiêu
chuẩn về thống kê cũng như logic đều được áp dụng trong quá trình này.
Các phương pháp tìm kiếm (Search Method)
Phương pháp tìm kiếm bao gồm 2 thành phần: Tìm kiếm tham số (Parameter
Search) và Tìm kiếm mô hình (Model Search). Đối với Tìm kiếm tham số,
thuật toán thực hiện tìm kiếm các tham số tối ưu húa cỏc tiêu chuẩn lượng giá
mô hình, các dữ liệu quan sát được và một cách biểu diễn mô hình. Tìm kiếm
mô hình là một phép lặp các phương pháp tìm kiếm tham số.
1.1.4 Các kĩ thuật khai phá dữ liệu kinh điển
Bài toán Phân loại - Cây quyết định
16
ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
Luật phân loại (Classification Rules) giỳp gỏn cỏc đối tượng mới vào một tập
hợp các lớp. Ví dụ, với một hồ sơ của một khách hàng đăng kí bảo hiểm, nên
phân loại anh ta vào nhúm cú rủi ro thấp, vừa hay cao? Có nhiều kĩ thuật trong
lớp bài toán tìm luật phân loại như Mạng Neural, Bayesian; nhưng kĩ thuật
kinh điển nhất là kĩ thuật Cây quyết định (Decision Tree).
Cây quyết định là một phương pháp nhằm xếp loại các dữ liệu theo một tiêu
chuẩn nào đó dựa vào mức độ khác nhau của các thuộc tính, sự xếp loại mức
độ khác nhau của các thuộc tính cho phép chúng ta tạo ra các tri thức dưới
dạng các luật diễn tả mối quan hệ giữa các thuộc tính của đối tượng, đó là
những tri thức rất có ích cho việc làm quyết định, đặc biệt trong khâu dự báo
để làm quyết định. Cây quyết định có thể dễ dàng chuyển đổi sang dạng luật
với cấu trúc l9
Kĩ thuật này được thực hiện thông qua việc xây dựng một cây với mỗi nhánh
là thông tin được phân lớp qua mỗi câu hỏi, cỏc lỏ của cây sẽ tạo thành một
phân hoạch của tập dữ liệu ta có.
Quỏ trình dựng cây gồm hai bước:
e UVd.,3D<#()2:P3V'(L  

> 30
≤ 40 ≥ 40
Nữ
Màu
Xanh
≠
Nữ
Nguồn gốc Nam
Nội Ngoại
Nam
- -
Kiểu
Viva
≠
Nữ
Nam - -
ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
Khác với luật phân loại, luật tạo nhóm là luật được rút ra từ những đối tượng
đã biết khẳng định sự tương đồng giữa các đối tượng trong cùng một nhóm.
K-means là kĩ thuật tạo nhóm thường được dùng nhất trong thực tế, được phát
minh đầu tiên bởi J.B.Mac Queen năm 1967. Để tiện cho việc minh họa chúng
ta chỉ minh họa tiến trình với biểu đồ 2 chiều nhưng phương pháp hoàn toàn
có thể thực hiện với không gian n chiều. Khi đó cách thức thực hiện vẫn
không thay đổi.
Các bước thực hiện
e "M<BKR7
\ "4LM.E<pR7
h R.E @
] J<,(n@
[ fc$<,)2hq[.>&Rp&!.I

• Độ phân tán (Distribution) của dữ liệu?
• Thuộc tính nào mô tả dữ liệu chính xác nhất?
• Dữ liệu có giá trị khuyết (missing value) không?
'$3iV&'5&><  
A$>.c('<<>.E('.)0P<6DJo 
BC3D<#&3')*<&E3D<#('B'M'$ 
f6&>0$./.)0<<*#P.@5(L>2 
./@(A%&>P*H5%<N5V,=#'.@7 
DP'.7H.><N5VLH(5O 
.S<,W'<#Bb6$((<2$&'$<6 
&>0$ 3(':@<)05%5A.%P'( 
(<N5V56$(B)2LH.(L> 
25%&'$BC3D<#'O
20
ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
1.2 BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP
1.2.1 Giới thiệu bài toán
Khái niệm khai phá luật liên kết ra đời năm 1993 bởi Rakesh Agrawal cùng
với bài toán phân tích giỏ hàng. Bài toán này có thể được phát biểu như sau :
“Cú bao nhiêu phần trăm khách hàng mua đồng thời bơ và sữa?”.
Ứng dụng của khai phá luật liên kết sẽ mang lại cho người quản lý siêu thị
những vấn đề mang tính xu hướng: Đặt hàng loại gì, số lượng bao nhiêu,
quảng cáo, bán hàng, … nhằm tăng doanh số bán hàng và giảm giá thành.
1.2.2 Các khái niệm
Trước khi phát biểu bài toán, ta làm quen với một số khái niệm được dùng
trong bài viết sau. Những khái niệm hay thuật ngữ chưa có khái niệm tương
ứng bằng tiếng Việt sẽ được giữ nguyên bằng tiếng Anh, để người đọc tiện
theo dõi khi tham khảo các tài liệu gốc.
a. Item
Item có thể coi là một thuộc tính nhị phân.

Độ tin cậy (Confidence) của luật là xác suất một Transaction hỗ trợ X cũng hỗ
trợ Y.
 = l399(“r⇒st) = (X|s)
Có thể lấy ví dụ minh hoạ cho các khái niệm nói trên như sau:
Cho cơ sở dữ liệu giao dịch D của một cửa hàng cú cỏc mặt hàng là A, B, C,
D, E, F. D có 4 giao dịch tương ứng như sau.
Min support 50%
Min confidence 50%
Khách hàng mua C
Khách mua cả A và C
Khách hàng mua A
22
ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
Hình 1-6 Minh họa Luật kết hợp
Cho trước độ hỗ trợ tối thiểu minsup = 50%, độ tin cậy tối thiểu minconf
= 50%. Xét Itemset {A, C} có thể suy ra 2 luật kết hợp với độ hỗ trợ và độ
tin cậy lần lượt là:
 k⇒"(s = 50%, c = 66.7%)
 "⇒ k(s = 50%, c = 100%)
1.2.3 Các tính chất liên quan đến luật kết hợp
Các tính chất của luật kết hợp được bàn dưới đây sẽ là cơ sở lập luận của các
thuật toán khai phá luật kết hợp.
Tính chất 1d>k<6$W'52k<9B9B$$(^k`u
B$$(^`
Thật vậy, vì tất cả các Transaction hỗ trợ B thì cũng sẽ hỗ trợ A.
Tính chất 2d>9B9k&!f'(99B9'W'kG&!
<2^>B$$(^k`vB$B$$(^`vB$52<9B9' 
W'k`
Tính chất 3d><f'(99B9kW'G<f'(9
^>B$$(^`uB$B$$(^k`uB$`

ỨNG DÔNG LÝ THUYẾT LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU TÁC NGHIỆP
1.2.4 Phát biểu bài toán
Gọi I={I
1
, I
2
, , I
m
} là tập các thuộc tính nhị phân.
D là tập các Transaction.
Minsup và MinConf lần lượt là độ hỗ trợ tối thiểu và độ tin cậy tối
thiểu.
Bài toán đặt ra là với các dữ kiện đầu vào cho trước trên, phải tìm được các
luật kết hợp thoả mãn đồng thời hai điều kiện :
Có độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu
Có độ tin cậy lớn hơn độ tin cậy tối thiểu
1.2.5 Lược đồ cơ bản của thuật toán khai phá luật kết hợp
Trong thực tế có nhiều thuật toán khai phá luật kết hợp. Mặc dù khác nhau về
phương pháp chi tiết, song chúng đều thực hiện theo lược đồ chung gồm 2 giai
đoạn:
Giai đoạn 1: Tỡm cỏc Large Itemset
Giai đoạn 2: Tỡm các luật kết hợp từ các Large Itemset tìm được
Mục đích của giai đoạn 1 xuất phát từ tư tưởng sau:
“BF.@7<6&>0$r
⇒
sR'/M.@. n(0W'0$rxs
Bb<2. n(0KE=B^rxs`yB^r
⇒
s`uB$U.@a9B9
rxs<f'(9a9B9”

{ coke, bread, hamburger }
{ coke, hamburger , juice}
{ milk, sandwich, juice }
{ sandwich, milk, juice, bread }
{ hamburger, juice, coke}
{ coke, bread, hamburger }
{ coke, hamburger , juice}
{ hamburger, juice }
{ milk, hamburger, sweater }
{ coke, milk, juice }
{ coke, juice }
{ coke, sweater 39$'
<'YzYZY{Y|
}}}}}}}}}}}}}
}}}}}}}}}}}}}
}}}}}}}}}}}}}
}}}}}}}}}}}}}
}}}}}}}}}}}}}
}}}}}}}}}}}}}
}}}}}}}}}}}}}
}}}
Giai đoạn 1 Tìm các Large Itemset (MinSupport
là 40 %)
Giai đoạn 2 Tìm các luật kết hợp MinConfidence = 70%

Trích đoạn THUẬT TOÁN SINH LUẬT THUẬT TOÁN UWEP

---