Bài giảng Khai phá dữ liệu (Data mining) - Chương 6: Luật kết hợp - Võ Thị Ngọc Châu

11
Chương 6: Luật kết hợp
Học kỳ 1 – 2011-2012
Khoa Khoa Học & Kỹ Thuật Máy Tính
Trường Đại Học Bách Khoa Tp. Hồ Chí Minh
Cao Học Ngành Khoa Học Máy Tính
Giáo trình điện tử
Biên soạn bởi: TS. Võ Thị Ngọc Châu
(chauvtn@cse.hcmut.edu.vn)
22
Tài liệu tham khảo
‡ [1] Jiawei Han, Micheline Kamber, “Data Mining: Concepts and 
Techniques”, Second Edition, Morgan Kaufmann Publishers, 2006.
‡ [2] David Hand, Heikki Mannila, Padhraic Smyth, “Principles of Data 
Mining”, MIT Press, 2001.
‡ [3] David L. Olson, Dursun Delen, “Advanced Data Mining 
Techniques”, Springer-Verlag, 2008.
‡ [4] Graham J. Williams, Simeon J. Simoff, “Data Mining: Theory, 
Methodology, Techniques, and Applications”, Springer-Verlag, 2006.
‡ [5] Hillol Kargupta, Jiawei Han, Philip S. Yu, Rajeev Motwani, and 
Vipin Kumar, “Next Generation of Data Mining”, Taylor & Francis 
Group, LLC, 2009.
‡ [6] Daniel T. Larose, “Data mining methods and models”, John Wiley 
& Sons, Inc, 2006.
‡ [7] Ian H.Witten, Eibe Frank, “Data mining : practical machine 
learning tools and techniques”, Second Edition, Elsevier Inc, 2005. 
‡ [8] Florent Messeglia, Pascal Poncelet & Maguelonne Teisseire, 
“Successes and new directions in data mining”, IGI Global, 2008.
‡ [9] Oded Maimon, Lior Rokach, “Data Mining and Knowledge 
Discovery Handbook”, Second Edition, Springer Science + Business
Media, LLC 2005, 2010.
33
Nội dung
‡ Chương 1: Tổng quan về khai phá dữ liệu
‡ Chương 2: Các vấn đề tiền xử lý dữ liệu
‡ Chương 3: Hồi qui dữ liệu
‡ Chương 4: Phân loại dữ liệu
‡ Chương 5: Gom cụm dữ liệu
‡ Chương 6: Luật kết hợp
‡ Chương 7: Khai phá dữ liệu và công nghệ cơ sở
dữ liệu
‡ Chương 8: Ứng dụng khai phá dữ liệu
‡ Chương 9: Các đề tài nghiên cứu trong khai phá
dữ liệu
‡ Chương 10: Ôn tập
44
Chương 6: Luật kết hợp
‡ 6.1. Tổng quan về khai phá luật kết hợp
‡ 6.2. Biểu diễn luật kết hợp
‡ 6.3. Khám phá các mẫu thường xuyên
‡ 6.4. Khám phá các luật kết hợp từ các mẫu 
thường xuyên
‡ 6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ 6.6. Phân tích tương quan
‡ 6.7. Tóm tắt
55
6.0. Tình huống 1 – Market basket analysis
66
6.0. Tình huống 2 - Tiếp thị chéo
77
6.0. Tình huống 2 - Tiếp thị chéo
88
6.0. Tình huống 
‡ Phân tích dữ liệu giỏ hàng (basket data 
analysis)
‡ Tiếp thị chéo (cross-marketing)
‡ Thiết kế catalog (catalog design)
‡ Phân loại dữ liệu (classification) và gom
cụm dữ liệu (clustering) với các mẫu phổ
biến
‡ 
99
6.1. Tổng quan về khai phá luật kết hợp
‡ Quá trình khai phá luật kết hợp
‡ Các khái niệm cơ bản
‡ Phân loại luật kết hợp
10
10
6.1. Tổng quan về khai phá luật kết hợp
‡ Quá trình khai phá luật kết hợp
Raw Data Items of Interest
Relationships 
among Items
(Rules)
User
Pre-
processing Mining
Post-
processing
11
11
6.1. Tổng quan về khai phá luật kết hợp
‡ Quá trình khai phá luật kết hợp
Association
RulesItems
Transactional/
Relational Data
Raw Data Items of Interest
Relationships 
among Items
(Rules)
User
Pre-
processing Mining
Post-
processing
Transaction Items_bought
---------------------------------
2000 A, B, C
1000 A, C
4000 A, D
5000 B, E, F
A, B, C, D, F, 
A → C (50%, 66.6%)
Bài toán phân tích giỏ thị trường
12
12
6.1. Tổng quan về khai phá luật kết hợp
‡ Dữ liệu mẫu của AllElectronics (sau quá
trình tiền xử lý)
13
13
6.1. Tổng quan về khai phá luật kết hợp
‡ Các khái niệm cơ bản
„ Item (phần tử)
„ Itemset (tập phần tử)
„ Transaction (giao dịch)
„ Association (sự kết hợp) và association rule (luật
kết hợp)
„ Support (độ hỗ trợ)
„ Confidence (độ tin cậy)
„ Frequent itemset (tập phần tử phổ biến/thường
xuyên)
„ Strong association rule (luật kết hợp mạnh)
14
14
6.1. Tổng quan về khai phá luật kết hợp
‡ Dữ liệu mẫu của AllElectronics (sau quá
trình tiền xử lý)
Item: I4
Itemsets:
{I1, I2, I5}, 
{I2}, 
Transaction: T800
15
15
6.1. Tổng quan về khai phá luật kết hợp
‡ Các khái niệm cơ bản
„ Item (phần tử)
‡ Các phần tử, mẫu, đối tượng đang được quan tâm.
‡ J = {I1, I2, , Im}: tập tất cả m phần tử có thể có
trong tập dữ liệu
„ Itemset (tập phần tử)
‡ Tập hợp các items
‡ Một itemset có k items gọi là k-itemset.
„ Transaction (giao dịch)
‡ Lần thực hiện tương tác với hệ thống (ví dụ: giao dịch
“khách hàng mua hàng”)
‡ Liên hệ với một tập T gồm các phần tử được giao dịch
16
16
6.1. Tổng quan về khai phá luật kết hợp
‡ Các khái niệm cơ bản
„ Association (sự kết hợp) và association rule 
(luật kết hợp)
‡ Sự kết hợp: các phần tử cùng xuất hiện với nhau trong
một hay nhiều giao dịch.
ƒ Thể hiện mối liên hệ giữa các phần tử/các tập phần tử
‡ Luật kết hợp: qui tắc kết hợp có điều kiện giữa các tập
phần tử.
ƒ Thể hiện mối liên hệ (có điều kiện) giữa các tập phần tử
ƒ Cho A và B là các tập phần tử, luật kết hợp giữa A và B là
A Æ B.
ƒ B xuất hiện trong điều kiện A xuất hiện.
17
17
6.1. Tổng quan về khai phá luật kết hợp
‡ Các khái niệm cơ bản
„ Support (độ hỗ trợ)
‡ Độ đo đo tần số xuất hiện của các phần tử/tập phần tử.
‡ Minimum support threshold (ngưỡng hỗ trợ tối thiểu)
ƒ Giá trị support nhỏ nhất được chỉ định bởi người dùng.
„ Confidence (độ tin cậy)
‡ Độ đo đo tần số xuất hiện của một tập phần tử trong
điều kiện xuất hiện của một tập phần tử khác.
‡ Minimum confidence threshold (ngưỡng tin cậy tối
thiểu)
ƒ Giá trị confidence nhỏ nhất được chỉ định bởi người dùng.
18
18
6.1. Tổng quan về khai phá luật kết hợp
‡ Các khái niệm cơ bản
„ Frequent itemset (tập phần tử phổ biến)
‡ Tập phần tử có support thỏa minimum support threshold.
‡ Cho A là một itemset
ƒ A là frequent itemset iff support(A) >= minimum support 
threshold.
„ Strong association rule (luật kết hợp mạnh)
‡ Luật kết hợp có support và confidence thỏa minimum 
support threshold và minimum confidence threshold.
‡ Cho luật kết hợp AÆB giữa A và B, A và B là itemsets
ƒ AÆB là strong association rule iff support(AÆB) >= 
minimum support threshold và confidence(AÆB) >= 
minimum confidence threshold.
19
19
6.1. Tổng quan về khai phá luật kết hợp
‡ Phân loại luật kết hợp
„ Boolean association rule (luật kết hợp luận
lý)/quantitative association rule (luật kết hợp lượng
số)
„ Single-dimensional association rule (luật kết hợp
đơn chiều)/multidimensional association rule (luật
kết hợp đa chiều)
„ Single-level association rule (luật kết hợp đơn
mức)/multilevel association rule (luật kết hợp đa
mức)
„ Association rule (luật kết hợp)/correlation rule (luật
tương quan thống kê)
20
20
6.1. Tổng quan về khai phá luật kết hợp
‡ Phân loại luật kết hợp
„ Boolean association rule (luật kết hợp luận
lý)/quantitative association rule (luật kết hợp
lượng số)
‡ Boolean association rule: luật mô tả sự kết hợp giữa sự
hiện diện/vắng mặt của các phần tử.
ƒ Computer Æ Financial_management_software
[support=2%, confidence=60%]
‡ Quantitative association rule: luật mô tả sự kết hợp
giữa các phần tử/thuộc tính định lượng.
ƒ Age(X, “30..39”) ∧ Income(X, “42K..48K”) Æ buys(X, 
high resolution TV)
21
21
6.1. Tổng quan về khai phá luật kết hợp
‡ Phân loại luật kết hợp
„ Single-dimensional association rule (luật kết hợp
đơn chiều)/multidimensional association rule (luật
kết hợp đa chiều)
‡ Single-dimensional association rule: luật chỉ liên quan
đến các phần tử/thuộc tính của một chiều dữ liệu.
ƒ Buys(X, “computer”) Æ Buys(X, 
“financial_management_software”)
‡ Multidimensional association rule: luật liên quan đến các
phần tử/thuộc tính của nhiều hơn một chiều.
ƒ Age(X, “30..39”) Æ Buys(X, “computer”)
22
22
6.1. Tổng quan về khai phá luật kết hợp
‡ Phân loại luật kết hợp
„ Single-level association rule (luật kết hợp đơn mức) 
/multilevel association rule (luật kết hợp đa mức)
‡ Single-level association rule: luật chỉ liên quan đến các
phần tử/thuộc tính ở một mức trừu tượng.
ƒ Age(X, “30..39”) Æ Buys(X, “computer”)
ƒ Age(X, “18..29”) Æ Buys(X, “camera”)
‡ Multilevel association rule: luật liên quan đến các phần
tử/thuộc tính ở các mức trừu tượng khác nhau.
ƒ Age(X, “30..39”) Æ Buys(X, “laptop computer”)
ƒ Age(X, “30..39”) Æ Buys(X, “computer”)
23
23
6.1. Tổng quan về khai phá luật kết hợp
‡ Phân loại luật kết hợp
„ Association rule (luật kết hợp)/correlation rule (luật
tương quan thống kê)
‡ Association rule: strong association rules AÆB (association 
rules đáp ứng yêu cầu minimum support threshold và
minimum confidence threshold).
‡ Correlation rule: strong association rules A Æ B đáp ứng
yêu cầu về sự tương quan thống kê giữa A và B.
24
24
6.2. Biểu diễn luật kết hợp
‡ Dạng luật: AÆB [support, confidence]
„ Cho trước minimum support threshold (min_sup), 
minimum confidence threshold (min_conf)
„ A và B là các itemsets
‡ Frequent itemsets/subsequences/substructures
‡ Closed frequent itemsets
‡ Maximal frequent itemsets
‡ Constrained frequent itemsets
‡ Approximate frequent itemsets
‡ Top-k frequent itemsets
25
25
6.2. Biểu diễn luật kết hợp
‡ Frequent 
itemsets/subsequences/substructures
„ Itemset/subsequence/substructure X là frequent 
nếu support(X) >= min_sup.
‡ Itemsets: tập các items
‡ Subsequences: chuỗi tuần tự các events/items
‡ Substructures: các tiểu cấu trúc (graph, lattice, tree, 
sequence, set, )
26
26
6.2. Biểu diễn luật kết hợp
‡ Closed frequent itemsets
„ Một itemset X closed trong J nếu không tồn tại tập
cha thực sự Y nào trong J có cùng support với X.
‡ X ⊆ J, X closed iff ∀ Y ⊆ J và X ⊂ Y: support(Y) 
support (X).
„ X là closed frequent itemset trong J nếu X là
frequent itemset và closed trong J.
‡ Maximal frequent itemsets
„ Một itemset X là maximal frequent itemset trong J
nếu không tồn tại tập cha thực sự Y nào trong J là
một frequent itemset.
‡ X ⊆ J, X là maximal frequent itemset iff ∀ Y ⊆ J và X ⊂ Y: 
Y không phải là một frequent itemset.
27
27
6.2. Biểu diễn luật kết hợp
‡ Constrained frequent itemsets
„ Frequent itemsets thỏa các ràng buộc do người
dùng định nghĩa.
‡ Approximate frequent itemsets
„ Frequent itemsets dẫn ra support (xấp xỉ) cho
các frequent itemsets sẽ được khai phá.
‡ Top-k frequent itemsets
„ Frequent itemsets có nhiều nhất k phần tử với k 
do người dùng chỉ định.
28
28
6.2. Biểu diễn luật kết hợp
‡ Luật kết hợp luận lý, đơn mức, đơn chiều giữa
các tập phần tử phổ biến: AÆB [support, 
confidence]
„ A và B là các frequent itemsets
‡ single-dimensional
‡ single-level
‡ Boolean
„ Support(AÆB) = Support(A U B) >= min_sup
„ Confidence(AÆB) = Support(A U B)/Support(A) = 
P(B|A) >= min_conf
29
29
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật Apriori: khám phá các mẫu thường
xuyên với tập dự tuyển
„ R. Agrawal, R. Srikant. Fast algorithms for mining 
association rules. In VLDB 1994, pp. 487-499.
‡ Giải thuật FP-Growth: khám phá các mẫu
thường xuyên với FP-tree 
„ J. Han, J. Pei, Y. Yin. Mining frequent patterns 
without candidate generation. In MOD 2000, pp. 
1-12.
30
30
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật Apriori
„ Dùng tri thức biết trước (prior knowledge) về đặc
điểm của các frequent itemsets
„ Tiếp cận lặp với quá trình tìm kiếm các frequent 
itemsets ở từng mức một (level-wise search)
‡ k+1-itemsets được tạo ra từ k-itemsets.
‡ Ở mỗi mức tìm kiếm, toàn bộ dữ liệu đều được kiểm tra.
„ Apriori property để giảm không gian tìm kiếm: All 
nonempty subsets of a frequent itemset must also 
be frequent.
‡ Chứng minh???
‡ Antimonotone: if a set cannot pass a test, all of its 
supersets will fail the same test as well.
31
31
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật Apriori
32
32
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật Apriori
33
33
6.3. Khám phá các mẫu thường xuyên
‡ Dữ liệu mẫu của AllElectronics (sau quá
trình tiền xử lý)
34
34
6.3. Khám phá các mẫu thường xuyên
min_sup = 2/9
minimum support count = 2
35
35
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật Apriori
„ Đặc điểm
‡ Tạo ra nhiều tập dự tuyển
ƒ 104 frequent 1-itemsets Æ nhiều hơn 107 (≈104(104-1)/2) 
2-itemsets dự tuyển
ƒ Một k-itemset cần ít nhất 2k -1 itemsets dự tuyển trước đó.
‡ Kiểm tra tập dữ liệu nhiều lần
ƒ Chi phí lớn khi kích thước các itemsets tăng lên dần.
ƒ Nếu k-itemsets được khám phá thì cần kiểm tra tập dữ liệu
k+1 lần.
36
36
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật Apriori
„ Các cải tiến của giải thuật Apriori
‡ Kỹ thuật dựa trên bảng băm (hash-based technique)
ƒ Một k-itemset ứng với hashing bucket count nhỏ hơn minimum 
support threshold không là một frequent itemset.
‡ Giảm giao dịch (transaction reduction)
ƒ Một giao dịch không chứa frequent k-itemset nào thì không cần
được kiểm tra ở các lần sau (cho k+1-itemset).
‡ Phân hoạch (partitioning)
ƒ Một itemset phải frequent trong ít nhất một phân hoạch thì mới có
thể frequent trong toàn bộ tập dữ liệu.
‡ Lấy mẫu (sampling)
ƒ Khai phá chỉ tập con dữ liệu cho trước với một trị support threshold 
nhỏ hơn và cần một phương pháp để xác định tính toàn diện
(completeness).
‡ Đếm itemset động (dynamic itemset counting)
ƒ Chỉ thêm các itemsets dự tuyển khi tất cả các tập con của chúng
được dự đoán là frequent.
37
37
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật FP-Growth
„ Nén tập dữ liệu vào cấu trúc cây (Frequent Pattern 
tree, FP-tree)
‡ Giảm chi phí cho toàn tập dữ liệu dùng trong quá trình
khai phá
ƒ Infrequent items bị loại bỏ sớm.
‡ Đảm bảo kết quả khai phá không bị ảnh hưởng
„ Phương pháp chia-để-trị (divide-and-conquer)
‡ Quá trình khai phá được chia thành các công tác nhỏ.
ƒ 1. Xây dựng FP-tree
ƒ 2. Khám phá frequent itemsets với FP-tree
„ Tránh tạo ra các tập dự tuyển
‡ Mỗi lần kiểm tra một phần tập dữ liệu
38
38
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật FP-Growth
„ 1. Xây dựng FP-tree
‡ 1.1. Kiểm tra tập dữ liệu, tìm frequent 1-itemsets
‡ 1.2. Sắp thứ tự frequent 1-itemsets theo sự giảm dần của
support count (frequency, tần số xuất hiện)
‡ 1.3. Kiểm tra tập dữ liệu, tạo FP-tree
ƒ Tạo root của FP-tree, được gán nhãn “null” {}
ƒ Mỗi giao dịch tương ứng một nhánh của FP-tree.
ƒ Mỗi node trên một nhánh tương ứng một item của giao dịch.
ƒ Các item của một giao dịch được sắp theo giảm dần.
ƒ Mỗi node kết hợp với support count của item tương ứng.
ƒ Các giao dịch có chung items tạo thành các nhánh có prefix 
chung.
39
39
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật FP-Growth
40
40
6.3. Khám phá các mẫu thường xuyên
41
41
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật FP-Growth
„ 2. Khám phá frequent itemsets với FP-tree
‡ 2.1. Tạo conditional pattern base cho mỗi node của FP-
tree
ƒ Tích luỹ các prefix paths with frequency của node đó
‡ 2.2. Tạo conditional FP-tree từ mỗi conditional pattern 
base
ƒ Tích lũy frequency cho mỗi item trong mỗi base
ƒ Xây dựng conditional FP-tree cho frequent items của base đó
‡ 2.3. Khám phá conditional FP-tree và phát triển frequent 
itemsets một cách đệ qui
ƒ Nếu conditional FP-tree có một path đơn thì liệt kê tất cả các
itemsets.
42
42
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật FP-Growth
43
43
6.3. Khám phá các mẫu thường xuyên
44
44
6.3. Khám phá các mẫu thường xuyên
‡ Giải thuật FP-Growth
„ Đặc điểm
‡ Không tạo tập itemsets dự tuyển
ƒ Không kiểm tra xem liệu itemsets dự tuyển có thực là
frequent itemsets
‡ Sử dụng cấu trúc dữ liệu nén dữ liệu từ tập dữ liệu
‡ Giảm chi phí kiểm tra tập dữ liệu
‡ Chi phí chủ yếu là đếm và xây dựng cây FP-tree lúc đầu
Æ Hiệu quả và co giãn tốt cho việc khám phá các frequent 
itemsets dài lẫn ngắn
45
45
6.3. Khám phá các mẫu thường xuyên
‡ So sánh giữa giải thuật Apriori và giải thuật FP-Growth
Co giãn với support threshold
46
46
6.3. Khám phá các mẫu thường xuyên
‡ So sánh giữa giải thuật Apriori và giải thuật FP-Growth
Co giãn tuyến tính với số giao dịch
47
47
6.4. Khám phá các luật kết hợp từ các 
mẫu thường xuyên
‡ Strong association rules AÆB
„ Support(AÆB) = Support(A U B) >= min_sup
„ Confidence(AÆB) = Support(A U B)/Support(A) 
= P(B|A) >= min_conf
Æ Support(AÆB) = Support_count(A U B) >= 
min_sup
ÆConfidence(AÆB) = P(B|A) = 
Support_count(AUB)/Support_count(A) >= 
min_conf
48
48
6.4. Khám phá các luật kết hợp từ các 
mẫu thường xuyên
‡ Quá trình tạo các strong association rules từ
tập các frequent itemsets
„ Cho mỗi frequent itemset l, tạo các tập con 
không rỗng của l.
‡ Support_count(l) >= min_sup
„ Cho mỗi tập con không rỗng s của l, tạo ra luật
“s Æ (l-s)” nếu
Support_count(l)/Support_count(s) >= min_conf
49
49
6.4. Khám phá các luật kết hợp từ các 
mẫu thường xuyên
Min_conf = 50%
I1 ∧ I2 ⇒ I5
I1 ∧ I5 ⇒ I2
I2 ∧ I5 ⇒ I1
I5 ⇒ I1 ∧ I2
50
50
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Ràng buộc (constraints)
„ Hướng dẫn quá trình khai phá mẫu (patterns) và
luật (rules)
„ Giới hạn không gian tìm kiếm dữ liệu trong quá
trình khai phá
„ Các dạng ràng buộc
‡ Ràng buộc kiểu tri thức (knowledge type constraints)
‡ Ràng buộc dữ liệu (data constraints)
‡ Ràng buộc mức/chiều (level/dimension constraints)
‡ Ràng buộc liên quan đến độ đo (interestingness 
constraints)
‡ Ràng buộc liên quan đến luật (rule constraints)
51
51
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Ràng buộc kiểu tri thức (knowledge type constraints)
„ Luật kết hợp/tương quan
‡ Ràng buộc dữ liệu (data constraints)
„ Task-relevant data (association rule mining)
‡ Ràng buộc mức/chiều (level/dimension constraints)
„ Chiều (thuộc tính) dữ liệu hay mức trừu tượng/ý niệm
‡ Ràng buộc liên quan đến độ đo (interestingness 
constraints)
„ Ngưỡng của các độ đo (thresholds)
‡ Ràng buộc liên quan đến luật (rule constraints)
„ Dạng luật sẽ được khám phá
52
52
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Khám phá luật dựa trên ràng buộc
„ Quá trình khai phá dữ liệu tốt hơn và hiệu quả
hơn (more effective and efficient).
‡ Luật được khám phá dựa trên các yêu cầu (ràng buộc) 
của người sử dụng.
ƒ More effective
‡ Bộ tối ưu hóa (optimizer) có thể được dùng để khai thác
các ràng buộc của người sử dụng.
ƒ More efficient
53
53
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Khám phá luật dựa trên ràng buộc liên
quan đến luật (rule constraints)
„ Dạng luật (meta-rule guided mining)
‡ Metarules: chỉ định dạng luật (về cú pháp – syntactic) 
mong muốn được khám phá
„ Nội dung luật (rule content)
‡ Ràng buộc giữa các biến trong A và/hoặc B trong luật
A Æ B
ƒ Quan hệ tập hợp cha/con
ƒ Miền trị
ƒ Các hàm kết hợp (aggregate functions)
54
54
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Metarules
„ Chỉ định dạng luật (về cú pháp – syntactic) 
mong muốn được khám phá
„ Dựa trên kinh nghiệm, mong đợi và trực giác của
nhà phân tích dữ liệu
„ Tạo nên giả thuyết (hypothesis) về các mối quan
hệ (relationships) trong các luật mà người dùng
quan tâm
Æ Quá trình khám phá luật kết hợp + quá trình
tìm kiếm luật trùng với metarules cho trước
55
55
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Metarules
„ Mẫu luật (rule template): P1 ∧ P2 ∧  ∧ Pl ⇒ Q1 ∧
Q2 ∧  ∧ Qr
‡ P1, P2, , Pl, Q1, Q2, , Qr: vị từ cụ thể (instantiated 
predicates) hay biến vị từ (predicate variables)
‡ Thường liên quan đến nhiều chiều/thuộc tính
„ Ví dụ của metarules
‡ Metarule
P1(X, Y) ∧ P2(X, W) ⇒ buys(X, “office software”)
‡ Luật thỏa metarule
age(X, “30..39”) ∧ income(X, “41k..60k”) ⇒ buys(X, 
“office software”)
56
56
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Ràng buộc giữa các biến S1, S2,  trong A 
và/hoặc B trong luật A Æ B
„ Quan hệ tập hợp cha/con: S1 ⊆/⊂ S2
„ Miền trị
‡ S1 θ value, θ ∈ {=, , , >=}
‡ value ∈/∉ S1
‡ ValueSet θ S1 hoặc S1 θ ValueSet, θ ∈ {=, , ⊆, ⊂, ⊄}
„ Các hàm kết hợp (aggregate functions)
‡ Agg(S1) θ value, Agg() ∈ {min, max, sum, count, avg}, 
θ ∈ {=, , , >=}
57
57
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Tính chất của các ràng buộc
„ Anti-monotone
„ Monotone
„ Succinctness
„ Convertible
58
58
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Tính chất của các ràng buộc
„ Anti-monotone
‡ “A constraint Ca is anti-monotone iff. for any pattern S 
not satisfying Ca, none of the super-patterns of S can 
satisfy Ca”.
‡ Ví dụ: sum(S.Price) <= value
„ Monotone
‡ “A constraint Cm is monotone iff. for any pattern S 
satisfying Cm, every super-pattern of S also satisfies it”.
‡ Ví dụ: sum(S.Price) >= value
59
59
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Tính chất của các ràng buộc
„ Succinctness
‡ “A subset of item Is is a succinct set, if it can be 
expressed as σp(I) for some selection predicate p, 
where σ is a selection operator”.
‡ “SP⊆2I is a succinct power set, if there is a fixed 
number of succinct set I1, , Ik ⊆I, s.t. SP can be 
expressed in terms of the strict power sets of I1, , Ik
using union and minus”.
‡ “A constraint Cs is succinct provided SATCs(I) is a 
succinct power set”.
Æ Có thể tạo tường minh và chính xác các tập thỏa
succinct constraints.
‡ Ví dụ: min(S.Price) <= value
60
60
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Tính chất của các ràng buộc
„ Convertible
‡ Các ràng buộc không có các tính chất anti-monotone, 
monotone, và succinctness
‡ Các ràng buộc hoặc là anti-monotone hoặc là monotone 
nếu các phần tử trong itemset đang kiểm tra có thứ tự.
‡ Ví dụ: 
ƒ Nếu các phần tử sắp theo thứ tự tăng dần thì avg(I.price) 
<= 100 là một convertible anti-monotone constraint.
ƒ Nếu các phần tử sắp theo thứ tự giảm dần thì avg(I.price) 
<= 100 là một convertible monotone constraint.
61
61
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
62
62
6.5. Khám phá các luật kết hợp dựa trên
ràng buộc
‡ Khám phá luật (rules)/tập phần tử phổ biến
(frequent itemsets) thỏa các ràng buộc
„ Cách tiếp cận trực tiếp
‡ Áp dụng các giải thuật truyền thống
‡ Kiểm tra các ràng buộc cho từng kết quả đạt được
ƒ Nếu thỏa ràng buộc thì trả về kết quả sau cùng.
„ Cách tiếp cận dựa trên tính chất của các ràng buộc
‡ Phân tích toàn diện các tính chất của các ràng buộc
‡ Kiểm tra các ràng buộc càng sớm càng tốt trong quá trình
khám phá rules/frequent itemsets
ƒ Không gian dữ liệu được thu hẹp càng sớm càng tốt.
63
63
6.6. Phân tích tương quan
‡ Strong association rules A ⇒ B
„ Dựa trên tần số xuất hiện của A và B (min_sup)
„ Dựa trên xác suất có điều kiện của B đối với A 
(min_conf)
ÆCác độ đo support và confidence dựa vào sự chủ
quan của người sử dụng
Æ Lượng rất lớn luật kết hợp có thể được trả về.
Æ Trong số 10,000 giao dịch, 6,000 giao dịch cho
computer games, 7,500 cho videos, và 4,000 cho
cả computer games và videos
Æ Buys(X, “computer games”) ⇒ Buys (X, “videos”) 
[support = 40%, confidence = 66%]
64
64
6.6. Phân tích tương quan
‡ Phân tích tương quan cho luật kết hợp A ⇒ B
„ Kiểm tra sự tương quan và phụ thuộc lẫn nhau
giữa A và B
„ Dựa vào thống kê về dữ liệu
„ Các độ đo khách quan, không phụ thuộc vào
người sử dụng
Æ Trong số 10,000 giao dịch, 6,000 giao dịch cho
computer games, 7,500 cho videos, và 4,000 cho
cả computer games và videos
Æ Buys(X, “computer games”) ⇒ Buys (X, “videos”) 
[support = 40%, confidence = 66%]
Æ P(“videos”) = 75% > 66%: “computer games” và
“videos” tương quan nghịch với nhau.
65
65
6.6. Phân tích tương quan
‡ Luật tương quan (correlation rules): A ⇒ B [support, 
confidence, correlation]
„ correlation: độ đo đo sự tương quan giữa A và B.
‡ Các độ đo correlation: lift, χ2 (Chi-square), all_confidence, cosine
ƒ lift: kiểm tra sự xuất hiện độc lập giữa A và B dựa trên xác suất (khả
năng)
ƒ χ2 (Chi-square): kiểm tra sự độc lập giữa A và B dựa trên giá trị mong
đợi và giá trị quan sát được
ƒ all_confidence: kiểm tra luật dựa trên trị support cực đại
ƒ cosine: giống lift tuy nhiên loại bỏ sự phụ thuộc vào tổng số giao dịch
hiện có
Æ all_confidence và cosine tốt cho tập dữ liệu lớn, không phụ thuộc
các giao dịch mà không chứa bất kì itemsets đang kiểm tra (null-
transactions).
Æ all_confidence và consine là các độ đo null-invariant.
66
66
6.6. Phân tích tương quan
‡ Độ đo tương quan lift
„ lift(A, B) < 1: A tương quan nghịch với B
„ lift(A, B) > 1: A tương quan thuận với B
„ lift(A, B) = 1: A và B độc lập nhau, không có tương quan
)(/)()(/)|(
)()(
)(),( BortsuppBAconfidenceBPABP
BPAP
BAPBAlift =>==∪=
lift({game}=>{video}) = 0.89 < 1 Æ {game} và {video} tương quan nghịch.
67
67
6.7. Tóm tắt
‡ Khai phá luật kết hợp
„ Được xem như là một trong những đóng góp quan trọng nhất từ cộng
đồng cơ sở dữ liệu trong việc khám phá tri thức
‡ Các dạng luật: luật kết hợp luận lý/luật kết hợp lượng số, luật kết
hợp đơn chiều/luật kết hợp đa chiều, luật kết hợp đơn mức/luật
kết hợp đa mức, luật kết hợp/luật tương quan thống kê
‡ Các dạng phần tử (item)/mẫu (pattern): Frequent 
itemsets/subsequences/substructures, Closed frequent itemsets, 
Maximal frequent itemsets, Constrained frequent itemsets, 
Approximate frequent itemsets, Top-k frequent itemsets
‡ Khám phá các frequent itemsets: giải thuật Apriori và giải thuật
FP-Growth dùng FP-tree
68
68
Hỏi & Đáp 
69
69
Đọc thêm
‡ R. Agrawal, R. Srikant. Fast algorithms for mining 
association rules. In VLDB 1994, pp. 487-499.
‡ J. Han, J. Pei, Y. Yin. Mining frequent patterns 
without candidate generation. In MOD 2000, pp. 
1-12. 
‡ J. Hipp, U. Guntzer, G. Nakhaeizadeh (2000). 
Algorithms for association rule mining – a general 
survey and comparison. SIGKDD Explorations 
2:1, pp. 58-64.
‡ W-J Lee, S-J Lee (2004). Discovery of fuzzy 
temporal association rules. IEEE transactions on 
Systems, Man, and Cybernetics – Part B 34:6, pp. 
2330-2342.
70
70
Chương 6: Luật kết hợp
Phần Phụ Lục
71
71
Nội dung Phụ lục
‡ Fuzzy association rules (Luật kết hợp mờ)
„ [3], chapter 5: Fuzzy Sets in Data Mining, pp. 79 - 86.
‡ Incremental association rule mining (Khai phá luật
kết hợp gia tăng)
„ Hong, T.P., Lin, C.W., Wu, Y.L. (2008), “Incrementally 
fast updated frequent pattern trees”, Expert Systems with 
Applications, 34(4), pp. 2424-2435.
„ Lin, C.W., Hong, T.P., Lu, W.H. (2009), “The Pre-FUFP 
algorithm for increment mining”, Expert Systems with 
Applications, 36(5), pp. 9498-9505.
Æ Tóm tắt phần phụ lục