MỤC LỤC
a. Thuật toán sinh luật đơn giản 22
b. Thuật toán sinh luật nhanh 23
1
BẢNG CÁC KÝ HIỆU
STT Ký hiệu Diễn giải
1 CSDL Cơ sở dữ liệu
2 WAR Weighted association rule (Luật kết hợp có trọng số)
3 FUFM Fast utility - frequent mining (khai phá tập utility phổ
biến nhanh)
4 KDD Knowledge Discovery in Databases (khám phá tri
thức)
5 2P-UF Two phases algorithm for utility- frequent mining
(giải thuật 2 pha để khai phá tập utility phổ biến)
6 uti utility
7 sup support (độ hỗ trợ)
8 conf confidence (độ tin cậy)
2
LỜI NÓI ĐẦU
Trong thời đại bùng nổ thông tin, đỏi hỏi phải có những phương pháp
nhanh, phù hợp, tự động, chính xác và có hiệu quả để lấy được thông tin có
giá trị. Khai phá dữ liệu là một kỹ thuật được áp dụng rất hiệu quả phục vụ
cho mục đích này; là một khâu trong quá trình khám phá tri thức, khai phá dữ
liệu làm nhiệm vụ trích xuất các thông tin có giá trị tiềm ẩn, có nhiều ý nghĩa
trong những kho dữ liệu. Hiện nay, kỹ thuật này đang được áp dụng một cách
rộng rãi trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như: y tế,
marketing, ngân hàng, viễn thông,…
Khai phá luật kết hợp là một phương thức đặc trưng đối với khai phá dữ
liệu. Ra đời từ năm 1993, rất nhiều giải thuật khai phá luật kết hợp đã được
đưa ra để giải quyết hiệu quả bài toán, nhiều chương trình ứng dụng thực tế đã
được áp dụng thành công. Tuy nhiên hầu hết các nghiên cứu tập trung vào

hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ
liệu). Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và
sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong kho dữ
liệu. Khai phá dữ liệu được coi là một bước trong quá trình khám phá tri thức
(Knowledge Discovery in Databases – KDD) và là giai đoạn quan trọng nhất
trong tiến trình khám phá tri thức từ cơ sở dữ liệu, các tri thức này có rất nhiều
ý nghĩa, là cơ sở hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh.
Các bước trong quá trình khám phá tri thức:
- Làm sạch dữ liệu (Data cleaning): loại bỏ dữ liệu nhiễu hoặc dữ liệu
không thích hợp.
- Tích hợp dữ liệu (Data Intergration): Tích hợp dữ liệu từ các nguồn
khác nhau như cơ sở dữ liệu (CSDL), kho dữ liệu, file text,
- Trích chọn dữ liệu (data selection): trích chọn những tập dữ liệu cần
được khai phá từ các tập dữ liệu lớn ban đầu (database, data warehouses,…)
theo một số tiêu chí nhất định.
- Biến đổi dữ liệu (data transformation): chuẩn hoá và làm mịn dữ liệu,
đưa dữ liệu về dạng thuận lợi nhất, phù hợp cho việc khai phá bằng cách thực
hiện các thao tác nhóm hoặc tập hợp.
- Khai phá dữ liệu (data mining): là giai đoạn thiết yếu, đây là bước
quan trọng và tốn nhiều thời gian nhất của toàn bộ quá trình khám phá tri thức,
5
là bước áp dụng những kỹ thuật khai phá để khai thác, trích xuất thông tin có
ích, những mẫu điển hình, những mối liên hệ đặc biệt có nhiều giá trị, mang
nhiều ý nghĩa từ dữ liệu.
- Đánh giá mẫu (Pattern Evaluation): đánh giá sự hữu ích của các mẫu
biểu diễn tri thức dựa vào một số phép đo.
- Trình diễn dữ liệu (knowledge presentation): sử dụng các kỹ thuật
trình diễn và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho
người sử dụng.
Hình 1.1: Các bước trong quá trình khám phá trí thức

cho phép doanh nghiệp ra những quyết định kịp thời được định hướng bởi tri
thức mà khai phá dữ liệu mang lại.
Những ứng dụng điển hình của khai phá dữ liệu:
 Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis and decision
support)
 Text mining & Webmining: phân lớp văn bản và các trang Web, tóm tắt
văn bản, tìm kiếm thông tin,…
 Tin - sinh: tìm kiếm, đối sánh các quan hệ gen và thông tin di truyền,
mối liên hệ giữa một số hệ gen và một số bệnh di truyền,…
 Điều trị y học (medical treatment): mối liên hệ giữa triệu chứng, chẩn
đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc men,…).
 Tài chính và thị trường chứng khoán (finance & stock market): phân
tích tình hình tài chính và dự báo giá của các loại cổ phiếu trong thị
trường chứng khoán,…
Những ứng dụng thực tế:
+ Ngành bảo hiểm y tế Australia đã dựa vào việc chẩn đoán bệnh trong
y tế dựa trên kết quả xét nghiệm và đã phát hiện ra nhiều trường hợp xét
nghiệm không hợp lý, tiết kiệm được 1 triệu USD/năm.
+ Trang Web mua bán qua mạng Amazon.com cũng tăng doanh thu nhờ
áp dụng khái phá dữ liệu trong việc phân tích sở thích mua bán của khách
hàng.
+ Bitish Telecom đã phát hiện ra những nhóm người thường xuyên gọi
cho nhau bằng mobile và thu lợi hàng triệu USD.
8
1.2 Luật kết hợp
Được Agrawal đưa ra vào năm 1993, khai phá dữ liệu bằng phương pháp
phát hiện các luật kết hợp là một trong các phương pháp khai thác đặc trưng
đối với khai phá dữ liệu với nhiệm vụ phân tích dữ liệu trong CSDL nhằm
phát hiện và đưa ra những mối liên hệ giữa các giá trị dữ liệu. Cụ thể là tìm
tần số mẫu, mối kết hợp, sự tương quan hay các cấu trúc nhân quả giữa các tập

n
: {biscuit, eggs, milk}
9
Một giao dịch T gọi là hỗ trợ tập X nếu nó chứa tất cả các hạng mục trong X,
nghĩa là X
⊆
T. Ký hiệu support(X) là tỷ lệ phần trăm của các giao dịch hỗ trợ
X trên tổng số các giao dịch trong D, nghĩa là:
Support(X)=
{ }
D
TXDT ⊆∈ |
Hỗ trợ tối thiểu (minsup: minimum support) là một giá trị cho trước bởi
người sử dụng. Nếu tập hạng mục X có support(X) ≥ minsup thì ta nói X là
một tập các khoản mục thường xuyên.
Một luật kết hợp là một quan hệ có dạng X ⇒ Y, trong đó X, Y ⊆ I là
các tập hạng mục (itemset) và X ∩ Y = ∅. Ở đây X (vế trái luật) được gọi là
tiền đề, Y (vế phải luật) là mệnh đề kết quả (hệ quả).
Hai thông số quan trọng của luật kết hợp là độ hỗ trợ (s) và độ tin cậy
(c).
Độ hỗ trợ (support) của luật kết hợp X ⇒ Y là tỷ lệ % số giao dịch có
chứa cả X, Y so với tổng số giao dịch có trong cơ sở dữ liệu. Độ hỗ trợ còn
được coi là độ phổ biến.
Sup(X⇒Y)= support(X
∪
Y)
Độ hỗ trợ tối thiểu (minsup):
- Cao: ít tập phần tử phổ biến
ít luật hợp lệ thường xuất hiện
- Thấp: nhiều luật hợp lệ hiếm xuất hiện

 Một itemset là một tập hợp các item
Ví dụ: X = {milk, bread, cereal} là một itemset
 Một k-itemset là tập có k items
 Tập item phổ biến (hay tập item lớn) là tập hợp các item có độ hỗ trợ
lớn hơn hay bằng minsup.
 Tập item dự kiến (hay tập ứng cử viên) là tập hợp các item cần được
xem xét có phải là tập item phổ biến không.
1.2.2 Giải thuật Apriori khai phá tập hạng mục phổ biến
Apriori là thuật toán khai phá luật kết hợp phổ biến nhất và là cơ sở để phát
triển các giải thuật khác.
11
a. Bản chất
- Dựa trên tính chất Apriori của tập phổ biến: mọi tập item phổ biến thì tất cả
các tập item con của nó đều là phổ biến
- Tìm tất cả các tập phổ biến 1-hạng mục. Sau đó là tất cả các tập phổ biến 2-
hạng mục, …
+ Trong mỗi vòng lặp k, chỉ quan tâm đến những tập có chứa một
số các tập phổ biến (k-1)- hạng mục
+ Tạo các tập ứng viên kích thước k-hạng mục (k - candidate itemset) từ
các tập phổ biến có kích thước (k-1)-hạng mục
+ Kiểm tra độ phổ biến của các ứng viên trên CSDL và loại các ứng
viên không phổ biến
b. Ví dụ:
12
c. Giả mã
Input : CSDL D, minsupp
Output : L : các tập phổ biến trong D
Kí hiệu:
C
k

c.count ++
}
L
k+1
= { c
∈
Ck+1 | c.count ≥ minsupp }
}
return L =
k
∪
L
k
;
• Hàm tạo tập ứng viên (k+1) hạng mục: apriori_gen
Input: L
k
,
Output: tập ứng viên kích thước k+1
Procedure apriori_gen (L
k
: Tập phổ biến kích thước k)
for mỗi itemset l
1

∈
L
k
for mỗi itemset l
2

{ c = l
1
∪
l
2
; // Bước kết L
k
với chính nó
if has_infrequent_subset (c, L
k
) then
Xóa c ; // Loại bỏ các ứng viên không có lợi
else Thêm c vào C
k+1
;
}
return C
k+1
;
• Sử dụng tri thức để giảm C
k+1
Procedure has_infrequent_subset (c: Tập ứng viên kích thước k+1, Lk :
Tập phổ biến kích thước k)
for mỗi k-subset s
∈
c
If s
∉
Lk then
return True ;

Tập ứng viên k-hạng mục tương ứng giỏ có độ hỗ trợ < minsupp
sẽ bị loại
 Giảm số lượng giao dịch :
Loại bỏ các giao dịch không chứa bất kỳ tập phổ biến nào
 Chia để trị :
Chia CSDL thành các phân hoạch D1, D2, …, Dp
Tìm tập phố biến cục bộ trong từng phân hoạch và tổ hợp
 Lấy mẫu :
CSDL lớn
Chọn mẫu từ CSDL và tìm tập phổ biến trên mẫu, kiểm tra bao
đóng của các hạng mục phổ biến
• Hashtree
Một hashtree lưu trữ tất cả các ứng cử viên k hạng mục.
15
Mục đích của Hash Tree: giảm số ứng cử viên cần được kiểm tra
Cấu trúc:
+ Leaf node (nút lá): có chứa một danh sách các tập item.
+ Interior node (nút trong): có chứa một bảng băm (hash table)
- Mỗi bucket trỏ tới nút khác
- Độ sâu của nút gốc =1
- Các bucket của một nút tại độ sâu d trỏ đến các nút tại độ sâu d+1
Xây dựng hash-tree cho C
k
:
- Thêm vào tập item C
 Bắt đầu từ nút gốc
 Đi xuống cho đến khi gặp nút lá
 Tại nút trong tại độ sâu d, chọn nhánh để đi bằng cách áp dụng
một hàm băm tới item thứ d của C
- Tất cả các node được khởi tạo ban đầu là node lá

Hình 1.5: Tạo cây sử dụng hash function (hash on 2, 5 or 8)
19
Hình 1.6: Tạo cây sử dụng hash function (hash on 3, 6 or 9)
Subset Operation (Phép toán tập con): Cho một giao dịch t, có thể có những
tập con nào có kích thước là 3?
Hình 1.7: Phép toán tập con
20
Phép toán tập con sử dụng Hash Tree.
Hình 1.8: Phép toán tập con sử dụng Hash Tree
Hình 1.9: Phép toán tập con sử dụng Hash Tree
21
Hình 1.10: Phép toán tập con sử dụng Hash Tree
1.2.3 Thuật toán sinh luật kết hợp
a. Thuật toán sinh luật đơn giản
 Tìm các tập con không rỗng h của tập item phổ biến f ∈ F
 Với mỗi tập con h tìm được, ta xuất ra dạng luật h ⇒ (f-h) nếu tỷ lệ
sup ( )
min
sup ( )
port f
cof
port h
≥
Input: Tập large itemset L
k
Output: Tập luật
For all large itemset l
k
,k
≥

For all a
m-1

∈
A do begin
conf =support (l
k
)/support (a
m-1
);
if (conf
≥
minconf) then begin
output the rule a
m-1

⇒
(l
k
–a
m-1
),
With confidence =conf and support=support (l
k
);
if (m-1> l) then
call genrules (l
k
, a
m-1

cũng thoả mãn. Ở đây a
*
là tập con khác rỗng của a.
Ví dụ: Với itemset ABCD, nếu luật AB ⇒ CD thoả thì luật ABC ⇒ D
và ABD ⇒ C cũng thoả.
23
Giả mã của giải thuật:
R:=
φ
;
Forall
j
k
j
Ff
2
=
∪∈
do begin
m:=1;
H
m
=
}{i
fi∈
∪
;
Repeat
Forall h
∈

m
=
φ
or m
≥
|f|;
End;
Return R;
1.2.4 Ứng dụng của luật kết hợp
Tri thức mà luật kết hợp đem lại có một sự khác biệt cơ bản so với
thông tin thu được từ các câu lệnh truy vấn thông thường. Đó thường là những
tri thức, những mối liên hệ chưa được biết trước và mang tính dự báo đang
tiềm ẩn trong dữ liệu. Nó đáng kể và hỗ trợ không nhỏ trong quá trình ra quyết
định. Tìm kiếm được những luật kết hợp “quý hiếm” và mang nhiều thông tin
từ CSDL tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực
khai phá dữ liệu.
24
Luật kết hợp được ứng dụng trong nhiều lĩnh vực: Phân tích bán hàng
trong siêu thị, cross-marketing, thiết kế catalog, loss-leader analysis, gom
cụm, phân lớp,…
25

Trích đoạn So sánh 2 giải thuật 2P-UF và FUFM Cài đặt thuật toán Thiết kế, xây dựng chương trình

---