Bài giảng Khai phá dữ liệu - Chương 3: Khai phá luật kết hợp - Nguyễn Vương Thịnh

TR ƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM 
KHOA CÔNG NGHỆ THÔNG TIN 
BÀI G I ẢNG MÔN HỌC  KHAI PHÁ DỮ LIỆU 
Giảng viên : ThS. Nguyễn V ươ ng Thịnh 
Bộ môn : Hệ thống thông tin 
Hải Phòng, 2013 
CHƯƠNG 3: KHAI PHÁ LUẬT KẾT HỢP 
2 
Thông tin về giảng viê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 
Email 
thinhnv@vimaru.edu.vn 
Website cá nhân 
3 
Thông tin về học phầ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 
PHƯƠNG PHÁP HỌC TẬP, NGHIÊN CỨU 
Nghe giảng, t hảo luận, trao đổi với giảng viên trên lớp. 
Tự n ghiên cứu tài liệu và làm bài tập ở nhà. 
PHƯƠNG PHÁP ĐÁNH GIÁ 
SV phải t ham dự ít nhất 75% thời gian . 
Có 02 bài kiểm tra viết giữa học phần (X = X 2 = (L 1 + L 2 )/2). 
Thi kết thúc học phần bằng hình thức trắc nghiệm khách quan trên máy tính (Z = 0.5X + 0.5Y). 
4 
Tài liệu tham khảo 
Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques , Elsevier Inc, 2006. 
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ụ Weka ). 
Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4 th Edition) , Pearson Education Inc, 2004. 
Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Giáo trình Khai phá dữ liệu Web , NXB Giáo dục, 2009 
5 
6 
Công cụ phần mềm hỗ trợ 
Phần mềm Weka được phát triển bởi nhóm nghiên cứu của trường Đại học Waikato (New Zealand) từ năm 1999. Có thể download về tại địa chỉ:  
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 
8 
3 .1 . MỘT SỐ KHÁI NIỆM CƠ BẢN 
3 .1.1. Khái niệm mục (item) và tập mục (item set) 
Cho một tập gồm n đối tượng I = {I 1 , I 2 , I 3 ,, I n }, mỗi phần tử I i ∈ 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 = {T 1 , T 2 ,, T m }, mỗi phần tử T j ∈ D được gọi là một giao dịch (transaction) và là một tập con nào đó của I (T j ⊆ I). Người ta gọi D là cơ sở dữ liệu giao dịch (transaction database). Số giao dịch có trong D ký hiệu là |D|. 
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ữ liệu giao dịch D gồm các tập con T j khác nhau của I: 
T 1 
{A, B, C, D} 
T 2 
{A, C, E} 
T 3 
{A, E} 
T 4 
{A, E, F} 
T 5 
{A, B, C, E, F} 
9 
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 
10 
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 
“ Đỗ 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 ” 
Trong đó: C(X) là số lần xuất hiện của X hay số giao dịch có chứa X 
T 1 
{A, B, C, D} 
T 2 
{A, C, E} 
T 3 
{A, E} 
T 4 
{A, E, F} 
T 5 
{A, B, C, E, F} 
Ví dụ: X = {A, E} thì C(X) = 4 và sup(X) = 4/5 = 80% 
Các tập mục có độ hỗ trợ lớn hơn một giá trị ngưỡng minsup nào đó cho trước được gọi là các tập phổ biến (frequent item set). 
11 
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 xuất hiện trong cơ sở dữ liệu giao dịch thì sẽ kéo theo sự xuất hiện của Y với một một tỷ lệ nào đấy. 
Luật kết hợp được đặc trưng bởi: 
Độ hỗ trợ của luật : là tỷ lệ (hay xác suất) xuất hiện cả X và Y trong cùng một giao dịch. 
Độ tin cậy của luật : là tỷ lệ các giao dịch có chứa cả X và Y so với các giao dịch có chứa X. 
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. 
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ể: 
12 
Nếu đồng thời sup(X→Y) ≥ minsup và conf(X→Y) ≥ minconf thì X→Y được gọi là luật mạnh (strong association rule). 
13 
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. 
Output :	Tất cả các luật mạnh. 
Để 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à 2 k – 2, tức là từ K ta sẽ sinh được tối đa là 2 k - 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à: 
14 
3 .2. TÌM TẬP PHỔ BIẾN VỚI GIẢI THUẬT APRIORI 
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ỳ của nó cũng là tập phổ biến” 
Chứng minh : 
Xét X’ ⊆ X. Ký hiệu p là ngưỡng độ hỗ trợ minsup . M ột tập mục xuất hiện bao nhiêu lần thì các tập con chứa trong nó cũng xuất hiện ít nhất bấy nhiêu lần , nên ta có: 
	C(X’) ≥ C(X) (1). 
 X là tập phổ biến nên: 
Từ (1) và (2) suy ra: 
Tức là X’ cũng là tập phổ biến (đpcm). 
15 
3 .2.2. Giải thuật Apriori 
Mục đích: Tìm ra tất cả các tập phổ biến có thể có. 
Dựa trên nguyên lý Apriori. 
Hoạt động dựa trên Quy hoạch động: 
Từ các tập F i = { c i | c i là tập phổ biến, |c i | = i} gồm mọi tập mục phổ biến có độ dài i (1 ≤ i ≤ k), đi tìm tập F k+1 gồm mọi tập mục phổ biến có độ dài k+1. Các mục I 1 , I 2 ,, I n trong tập I được coi là sắp xếp theo một thứ tự cố định. 
16 
F 1 = { các tập phổ biến có độ dài 1}; 
for (k=1; F k != ⍉; k++) 
{ 
 	C k+1 = Apriori_gen (F k ); 
	 for each t ∈ D 
	{ 
	C t = { c | c ∈ C k+1 và c ⊆ t}; 
	 for each c ∈ C t 
	c.count++; 
	} 
	F k+1 = {c ∈ C k+1 | c.count ≥ mincount}; 
} 
return F = 
Input : 	- Cơ sở dữ liệu giao dịch D = {t 1 , t 2 ,, t m }. 
	- Ngưỡng độ hỗ trợ tối thiểu minsup. 
Output :	- Tập hợp tất cả các tập phổ biến. 
17 
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 F k . 
Đ ượ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ể : 
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 l i và l j ∈ F k có độ dài k và trùng nhau ở k-1 mục đầu tiên: c = l i + l j = {i 1 , i 2 ,, i k-1 , i k , i k’ }. 
	 Với l i = {i 1 , i 2 ,, i k-1 , i k }, l j = {i 1 , i 2 ,, i k-1 , i k’ }, và i 1 ≤ i 2 ≤≤ i k-1 ≤ i k ≤ i k’ . 
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 (∀s k ⊆ c và |s k | = k thì s k ∈ F k ). 
18 
function Apriori_gen (F k : tập các tập phổ biến độ dài k): Tập ứng viên có độ dài k+1 
{ 
	C k+1 = ⍉ ; 
	for each l i ∈ F k 
	for each l j ∈ F k 
	if (l i [1]=l j [1]) and (l i [2]=l j [2])  and (l i [k-1]=l j [k-1]) and (l i [k]<l j [k]) then 
	{ 
	c = {l i [1], l i [2], l i [3],, l i [k], l j [k]}; 
	if has_infrequent_subset (c, F k ) then 
	delete c; 
	else C k+1 = C k+1 ∪ {c}; 
	} 
	return C k+1 ; 
} 
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 . 
function has_infrequent_subset (c: Ứng viên có độ dài k+1, F k : Tập các tập phổ biến độ dài k): Boolean 
{ 
	for each s k ⊂ c 
	if s k ∉ F k then return True; 
	return False; 
} 
20 
3 .3. SINH LUẬT KẾT HỢP TỪ CÁC TẬP PHỔ BIẾN 
Để sinh các luật kết hợp: 
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. 
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 \ F 1 ; //Các tập phổ biến độ dài 1 không dùng để sinh luật 
	for each X ∈ F 
	for each S ⊂ X 
	if conf(S→(X\S)) ≥ minconf then 
	 	 R = R ∪ { S→(X\S)}; 
	return R; 
} 
21 
BÀI TẬP ÁP DỤNG 
Bài tập số 1 : Cho I = {A, B, C, D, E, F} và cơ sở dữ liệu giao dịch D: 
T1 
{A, B, C, F} 
T2 
{A, B, E, F} 
T3 
{A, C} 
T4 
{D, E} 
T5 
{B, F} 
Chọn ngưỡng minsup = 25% và minconf = 75%. Hãy xác định các luật kết hợp mạnh. 
22 
F 1 
Số lần xuất hiện 
{A} 
3 
{B} 
3 
{C} 
2 
{E} 
2 
{F} 
3 
Tập mục 
Số lần xuất hiện 
{A} 
3 
{B} 
3 
{C} 
2 
{D} 
1 
{E} 
2 
{F} 
3 
F 2 
Số lần xuất hiện 
{A, B} 
2 
{A, C} 
2 
{A, F} 
2 
{B, F} 
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} 
C 2 
Số lần xuất hiện 
{A, B} 
2 
{A, C} 
2 
{A, E} 
1 
{A, F} 
2 
{B, C} 
1 
{B, E} 
1 
{B, F} 
3 
{C, E} 
0 
{C, F} 
1 
{E, F} 
1 
Tập mục 
{A, B, C} 
{ A, B, F} 
{A, C, F} 
C 3 
Số lần xuất hiện 
{A, B, F} 
2 
F 3 
Số lần xuất hiện 
{A, B, F} 
2 
Sinh các tập mục có độ dài 3 từ tập phổ biến F 2 
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 
Loại các tập mục không thỏa mãn nguyên lý Apriori 
F 3 chỉ có một phần tử nên không thể tiếp tục kết nối để sinh F 4 . 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, F}} 
23 
{A, B} có thể sinh các luật: {A}→{B}, {B}→{A} 
{A, C} có thể sinh các luật: {A}→{C}, {C}→{A} 
{A, F} có thể sinh các luật: {A}→{F}, {F}→{A} 
24 
{B, F} có thể sinh các luật: {B}→{F}, {F}→{B} 
{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} 
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} 
26 
Bài tập số 2 : Cho I = {A, B, C, D, E, F} và cơ sở dữ liệu giao dịch D: 
T1 
{D, E} 
T2 
{A, B, D, E} 
T3 
{A, B, D} 
T4 
{C, D, E} 
T5 
{F} 
T6 
{B, C, D} 
Chọn ngưỡng minsup = 20% và minconf = 70%. Hãy xác định các luật kết hợp mạnh. 
27 
F 1 
Số lần xuất hiện 
{A} 
2 
{B} 
3 
{C} 
2 
{D} 
5 
{E} 
3 
Tập mục 
Số lần xuất hiện 
{A} 
2 
{B} 
3 
{C} 
2 
{D} 
5 
{E} 
3 
{F} 
1 
Tập mục 
{A, B} 
{A, C} 
{A, D} 
{A, E} 
{B, C} 
{B, D} 
{B, E} 
{C, D} 
{C, E} 
{D, E} 
C 2 
Số lần xuất hiện 
{A, B} 
2 
{A, C} 
0 
{A, D} 
2 
{A, E} 
1 
{B, C} 
1 
{B, D} 
3 
{B, E} 
1 
{C, D} 
2 
{C, E} 
1 
{D, E} 
3 
F 2 
Số lần xuất hiện 
{A, B} 
2 
{A, D} 
2 
{B, D} 
3 
{C, D} 
2 
{D, E} 
3 
Tập mục 
{A, B, D} 
C 3 
Số lần xuất hiện 
{A, B, D} 
2 
F 3 
Số lần xuất hiện 
{A, B, D} 
2 
Tập F 3 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 F 4 . 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}} 
28 
{A, B} sinh luật: {A}→{B}, {B}→{A} 
{A, D} sinh luật: {A}→{D}, {D}→{A} 
{ B, D} sinh luật: {B}→{D}, {D}→{B} 
29 
{C, D} sinh luật: {C}→{D}, {D}→{C} 
{D, E} sinh luật: {D}→{E}, {E}→{D} 
{A, B, D} sinh luật: {A}→{B, D}, {A, B}→{D}, {B}→{A, D}, {B, D}→{A}, {D}→{A, B}, {A, D}→B 
30 
Các luật kết hợp mạnh thu được gồm: 
{A}→{B} 
{A}→{D} 
{B}→{D} 
{C}→{D} 
{E}→{D} 
{A}→{B, D} 
{A,B}→{D} 
{A, D}→B 
31 
3 .4. TÌM TẬP PHỔ BIẾN VỚI GIẢI THUẬT 
FP-GROWTH 
Tư tưởng : Cho phép phát hiện ra các tập phổ biến mà không cần khởi tạo các ứng viên . 
BƯỚC 1 : Xây dựng một cấu trúc dữ liệu thu 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. 
BƯỚC 2 : Kết xuất các mục phổ biến dựa trên cây FP. Thao tác duyệt cây được thực hiện tại bước này. 
32 
BƯỚC 1: XÂY DỰNG CÂY FP 
(Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques) 
33 
Quét CSDL giao dịch và đếm số lần xuất hiện ứng với mỗi mục. 
Loại bỏ các mục không phổ biến. 
Sắp lại thứ tự các mục trong mỗi giao dịch theo thứ tự giảm dần của số lần xuất hiện. 
Mỗi nút của cây tương ứng với một mục và được gắn trọng số là số lần xuất hiện. 
Giải thuật FP-Growth đọc lần lượt từng giao dịch và ánh xạ tương ứng với mỗi đường đi (xuất phát từ nút gốc) trên cây FP. 
34 
Thứ tự sắp xếp của các mục được tuân thủ trong suốt quá trình xây dựng cây FP. 
Các đường đi có thể có thể có những đoạn trùng nhau do các giao dịch có các phần tử chung (chung tiền tố trong dãy). Mỗi lần có phần tử trùng thì trọng số của đỉnh ở vị trí trùng được tăng lên 1. 
Con trỏ được sử dụng để duy trì danh sách kết nối đơn giữa các nút đại diện cho cùng một mục. 
35 
BƯỚC 2: SINH TẬP PHỔ BIẾN 
(duyệt cây FP) 
(Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques) 
36 
Ứng với mỗi mục phổ biến I i : 
 Xây dựng tập các cơ sở mẫu có điều kiện (conditional pattern base). Mỗi mẫu có điều kiện là một đường đi nối từ đỉnh gốc tới đỉnh cha kề với đỉnh có chứa mục I i . Mỗi mẫu được gán trọng số bằng với trọng số của đỉnh có chứa mẫu I i ở cuối đường đi. 
Xây dựng cây FP có điều kiện (conditional FP-tree) dựa trên việc kết hợp các mẫu có chung tiền tố (nếu có). Khi đó t rọng số ứng với mỗi đỉnh là tổng các trọng số được ghép. 
Duyệt cây FP có điều kiện để sinh các tập phổ biến có hậu tố là I i . 
37 
TID	Items bought	 	 
100	{ f, a, c, d, g, i, m, p } 	 
200	{ a, b, c, f, l, m, o } 	 
300	 	 { b, f, h, j, o } 	 
400 	 	 { b, c, k, s, p } 	 
500 	 	 { a, f, c, e, l, p, m, n } 	 
Ví dụ 1 : Cho cơ sở dữ liệu giao dịch D gồm các giao dịch: 
Biết ngưỡng minsup = 60%. Hãy tìm các tập phổ biến. 
38 
Item frequency 
 f	4 
c	4 
a	3 
b	3 
m	3 
p	3 
TID	Items bought	 	 
100	{ f, a, c, d, g, i, m, p } 	 
200	{ a, b, c, f, l, m, o } 	 
300	 	 { b, f, h, j, o } 	 
400	 	 { b, c, k, s, p } 	 
500 	 	 { a, f, c, e, l, p, m, n } 
m incount = 3 	 
TID	Items bought	 (ordered) frequent items 
100	{ f, a, c, d, g, i, m, p } { f, c, a, m, p } 
200	{ a, b, c, f, l, m, o } 	 { f, c, a, b, m } 
300	 	 { b, f, h, j, o } 	 { f, b } 
400	 	 { b, c, k, s, p } 	 { c, b, p } 
500 	 	 { a, f, c, e, l, p, m, n } { f, c, a, m, p } 
Quét CSDL để tính số lần xuất hiện (support count) ứng với mỗi mục : 
Loại bỏ các mục không phải là phổ biến. 
Sắp các mục trong mỗi giao dịch theo thứ tự giảm của support count. 
39 
Đọc từng giao dịch và ánh xạ vào cây FP: 
{} 
f:1 
c:1 
a:1 
m:1 
p:1 
{ f, c, a, m, p } 
{} 
{} 
f:2 
c:2 
a:2 
b:1 
m:1 
p:1 
m:1 
{ f, c, a, b, m } 
TID	Items bought	 (ordered) frequent items 
100	{ f, a, c, d, g, i, m, p } { f, c, a, m, p } 
200	{ a, b, c, f, l, m, o } 	 { f, c, a, b, m } 
300	 	 { b, f, h, j, o } 	 { f, b } 
400	 	 { b, c, k, s, p } 	 { c, b, p } 
500 	 	 { a, f, c, e, l, p, m, n } { f, c, a, m, p } 
40 
{} 
f:4 
c:1 
b:1 
p:1 
b:1 
c:3 
a:3 
b:1 
m:2 
p:2 
m:1 
{} 
f:3 
c:2 
a:2 
b:1 
m:1 
p:1 
m:1 
{ f, b } 
b:1 
{ c, b, p } 
c:1 
b:1 
p:1 
{} 
f:3 
c:2 
a:2 
b:1 
m:1 
p:1 
m:1 
b:1 
{ f, c, a, m, p } 
 Node-Link 
Đọc từng giao dịch và ánh xạ vào cây FP (tiếp) 
41 
{} 
f:4 
c:1 
b:1 
p:1 
b:1 
c:3 
a:3 
b:1 
m:2 
p:2 
m:1 
Header Table 
Item head 
 f	 
c	 
a	 
b	 
m	 
p	 
Cây FP hoàn chỉnh: 
42 
{} 
f:4 
c:1 
b:1 
p:1 
b:1 
c:3 
a:3 
b:1 
m:2 
p:2 
m:1 
Header Table 
Item head 
 f	 
c	 
a	 
b	 
m	 
p	 
Xét mục p : 
Cơ sở mẫu có điều kiện gồm: f-c-a-m:2 và c-b:1 
f:2 
c:2 
a:2 
m:2 
c:1 
b:1 
{} 
{} 
c:3 
Tập phổ biến là: cp:3 
43 
{} 
f:4 
c:1 
b:1 
p:1 
b:1 
c:3 
a:3 
b:1 
m:2 
p:2 
m:1 
Header Table 
Item head 
 f	 
c	 
a	 
b	 
m	 
p	 
{} 
c:3 
a:3 
b:1 
f:3 
Xét mục m : 
Cơ sở mẫu có điều kiện gồm: f-c-a:2 và f-c-a-b:1 
{} 
c:3 
a:3 
f:3 
Tập phổ biến gồm: fm:3, fcm:3, fcam:3, fam:3, cm:3, cam:3, am:3 
44 
{} 
f:4 
c:1 
b:1 
p:1 
b:1 
c:3 
a:3 
b:1 
m:2 
p:2 
m:1 
Header Table 
Item head 
 f	 
c	 
a	 
b	 
m	 
p	 
{} 
c:1 
a:1 
c :1 
f:2 
Xét mục b : 
Cơ sở mẫu có điều kiện gồm: f-c-a:1, f:1 và c:1 
{} 
45 
{} 
f:4 
c:1 
b:1 
p:1 
b:1 
c:3 
a:3 
b:1 
m:2 
p:2 
m:1 
Header Table 
Item head 
 f	 
c	 
a	 
b	 
m	 
p	 
{} 
c:3 
f:3 
Xét mục a : 
Cơ sở mẫu có điều kiện gồm: f-c:3 
Tập phổ biến gồm: fa:3, fca:3, ca:3 
Xét mục c : 
Cơ sở mẫu có điều kiện gồm: f:3 
{} 
f:3 
Tập phổ biến gồm: fc:3 
46 
{} 
f:4 
c:1 
b:1 
p:1 
b:1 
c:3 
a:3 
b:1 
m:2 
p:2 
m:1 
Header Table 
Item head 
 f	 
c	 
a	 
b	 
m	 
p	 
Mục 
Cơ sở mẫu có điều kiện 
Cây FP có điều kiện 
Tập phổ biến 
p 
fcam:2, cb:1 
p:3, cp:3 
m 
fca:2, fcab:1 
m:3, fm:3, fcm:3, fcam:3, fam:3, cm:3, cam:3, am:3 
b 
fca:1, f:1, c:1 
Null 
b:3 
a 
fc:3 
a:3, fa:3, fca:3, ca:3 
c 
f:3 
c:4, fc:3 
f 
Null 
Null 
f:4 
47 
Ví dụ 2 : Cho cơ sở dữ liệu giao dịch D gồm các giao dịch: 
Biết ngưỡng minsup = 22%. Hãy tìm các tập phổ biến. 
48 
Tập mục 
Số lần xuất hiện 
I 2 
7 
I 1 
6 
I 3 
6 
I 4 
2 
I 5 
2 
Đếm số lần xuất hiện của các mục và sắp theo thứ tự giảm dần: 
49 
Giao dịch 
Danh sách mục 
T100 
I 2 , I 1 , I 5 
T200 
I 2, I 4 
T300 
I 2 , I 3 
T400 
I 2 , I 1 , I 4 
T500 
I 1 , I 3 
T600 
I 2 , I 3 
T700 
I 1 , I 3 
T800 
I 2 , I 1 , I 3 , I 5 
T900 
I 2 , I 1 , I 3 
50 
51 
52 
53 
I 2 :2 
NULL 
Xét mục I 5 : 
Cơ sở mẫu có điều kiện gồm: I 2 – I 1 :1 , I 2 – I 1 – I 3 :1 
I 1 :2 
I 3 :1 
I 2 :2 
NULL 
I 1 :2 
Tập phổ biến gồm: I 2 I 5 :2, I 2 I 1 I 5 :2, I 1 I 5 :2 
54 
I 2 :2 
NULL 
Xét mục I 4 : 
Cơ sở mẫu có điều kiện gồm: I 2 – I 1 :1 , I 2 :1 
I 1 :1 
I 2 :2 
NULL 
Tập phổ biến gồm: I 2 I 4 :2 
55 
I 2 :4 
NULL 
Xét mục I 3 : 
Cơ sở mẫu có điều kiện gồm: I 2 – I 1 :2, I 2 :2, I 1 :2 
I 1 :2 
I 1 :2 
Tập phổ biến gồm: I 2 I 3 :4, I 2 I 1 I 3 :2, I 1 I 3 :4 
56 
Xét mục I 1 : 
Cơ sở mẫu có điều kiện gồm: I 2 :4 
I 2 :4 
NULL 
Tập phổ biến gồm: I 2 I 1 :4 
57 
58 
3 .5. MỘT SỐ DẠNG THỨC CỦA CƠ SỞ DỮ LIỆU GIAO DỊCH 
3 .5.1. BIỂU DIỄN DƯỚI DẠNG MA TRẬN GIÁ TRỊ NHỊ PHÂN 
A 1 
A 2 
. . . 
A n 
T 1 
a 1,1 
a 1,2 
. . . 
a 1,n 
T 2 
a 2,1 
a 2,2 
. . . 
a 2,n 
T 3 
a 3,1 
a 3,2 
. . . 
a 3,n 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
T m-1 
a m-1,1 
a m-1,2 
. . . 
a m-1,n 
T m 
a m,1 
a m,2 
. . . 
a m,n 
Tập các mục I = {A 1 , A 2 ,..., A n } và CSDL giao dịch D = {T 1 , T 2 ,..., T m } 
Dòng thứ i tương ứng với giao dịch T i 
Cột thứ j tương ứng với mục A j 
Phần tử a i,j nhận giá trị 1 (TRUE) hoặc 0 (FALSE) tùy thuộc vào việc mục A j có xuất hiện trong giao dịch T i hay không? 
59 
A 
B 
C 
D 
E 
T 1 
0 
1 
1 
0 
1 
T 2 
1 
1 
1 
0 
0 
T 3 
0 
1 
0 
0 
1 
T 4 
0 
1 
1 
0 
1 
T 5 
1 
1 
1 
0 
1 
T 6 
0 
1 
1 
1 
0 
T 1 
{B , C, E} 
T 2 
{A, B, C } 
T 3 
{B, E} 
T 4 
{B, C , E } 
T 5 
{A, B, C, E} 
T 6 
{B, C, D} 
I = {A, B, C, D, E} 
D = {T 1 , T 2 , T 3 , T 4 , T 5 , T 6 } 
60 
3 .5.2. BIỂU DIỄN DƯỚI DẠNG MA TRẬN GIÁ TRỊ 
A 1 
A 2 
. . . 
A n 
T 1 
a 1,1 
a 1,2 
. . . 
a 1,n 
T 2 
a 2,1 
a 2,2 
. . . 
a 2,n 
T 3 
a 3,1 
a 3,2 
. . . 
a 3,n 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
T m-1 
a m-1,1 
a m-1,2 
. . . 
a m-1,n 
T m 
a m,1 
a m,2 
. . . 
a m,n 
Dòng thứ i tương ứng với giao dịch T i 
Cột thứ j tương ứng với thuộc tính A j 
Phần tử a i,j nhận giá trị d jk nào đó thuộc miền giá trị dom(A j ) của thuộc tính A j 
Cứ một cặp ghép (A j ,d jk ) (có thể được viết là A j = d jk với hàm ý “thuộc tính A j nhận giá trị d jk ”) mới được xem là một mục (Item). 
Tất cả các giao dịch đều có độ dài như nhau (chứa n mục). 
61 
Các luật kết hợp lúc này thường được biểu diễn dưới dạng: 
Cũng có thể phát biểu dưới dạng luật “ Nếu ... Thì ...” : 
Nếu: 
Thì: 
 )... 
 )... 
62 
A 
B 
C 
D 
E 
T 1 
1 
2 
1 
3 
2 
T 2 
1 
3 
2 
1 
2 
T 3 
1 
3 
2 
3 
1 
T 4 
2 
3 
2 
2 
2 
T 5 
3 
1 
1 
3 
1 
T 6 
2 
3 
2 
1 
2 
T 1 
{(A=1),(B=2),(C=1),(D=3),(E=2)} 
T 2 
{(A=1),(B=3),(C=2),(D=1),(E=2)} 
T 3 
{(A=1),(B=3),(C=2),(D=3),(E=1)} 
T 4 
{(A=2),(B=3),(C=2),(D=2),(E=2)} 
T 5 
{(A=3),(B=1),(C=1),(D=3),(E=1)} 
T 6 
{(A=2),(B=3),(C=2),(D=1),(E=2)} 
Luật {(A=1),(B=3)}→{(C=2)} có: 
s up = 2/6 = 33.3% 
c onf = 2/2 = 100% 
Luật này có thể biểu diễn dưới dạng: 
(A=1)^(B=3)→(C=2) 
Hoặc: 
Nếu A = 1 và B = 3 thì C = 2 với xác suất 100% 
Luật {(outlook=sunny),(temperature=hot)}→{(play=no)} có: 
s up = 2/14 = 14.3% 
c onf = 2/2 = 100% 
Luật này có thể biểu diễn dưới dạng: 
(outlook=sunny)^(temperature=hot)→(play=no) 
Nếu outlook = sunny và temparature = hot thì play = no với xác suất 100% 
64 
Khởi động phần mềm Weka, chọn Explorer: 
3 .6. KHAI PHÁ LUẬT KẾT HỢP VỚI 
PHẦN MỀM WEKA 
65 
Chọn tập tin dữ liệu sử dụng 
66 
Dữ liệu cần khai phá 
Lưu ý: Weka chỉ làm việc tốt với dữ liệu được biểu diễn ở dạng ma trận giá trị 
67 
Chọn khai phá luật kết hợp 
Chọn thuật toán khai phá 
(mặc định là Apriori) 
Click để thiết lập các thông số 
68 
Ngưỡng độ hỗ trợ tối thiểu (minsup) 
Ngưỡng độ hỗ trợ tối đa (maxsup) 
Chọn loại độ đo (mặc định là dùng độ tin cậy) 
Ngưỡng độ tin cậy tối thiểu (minconf) 
Số luật tối đa được hiển thị 
Có cho phép hiện kèm các tập phổ biển hay không 
Thiết lập các thông số: 
69 
Các luật thỏa mãn 
Kết quả khai phá: 
Q & A 
70