ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

TRẦN VĨNH HOÀNG

MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU
SINH LUẬT KẾT HỢP
LUẬN VĂN THẠC SĨ


1.3.6. Giải thuật di truyền 12
1.4. Lựa chọn các kỹ thuật khai phá 13
1.5. Các dạng CSDL thường được sử dụng để KPDL 14
1.6. Một số ứng dụng của KPDL 14
2. Chương 2: Một số vấn đề cơ bản về Luật kết hợp 16
2.1. Định nghĩa luật kết hợp 16
2.1.1. Ví dụ về luật kết hợp 16
2.1.2. Các định nghĩa và tính chất 16
2.1.2.1. Các định nghĩa cơ bản 16
2.1.2.2. Một số tính chất của tập mục phổ biến 19
2.1.2.3. Một số tính chất của luật kết hợp 19
2.2. Các loại luật kết hợp và hướng tiếp cận 20
2.2.1. Luật kết hợp nhị phân 20
2.2.2. Luật kết hợp định lượng 20
2.2.2.1. Giới thiệu 20
2.2.2.2. Khai phá luật kết hợp định lượng 20
2.2.3. Luật kết hợp đơn chiều 22
2.2.4. Luật kết hợp đa chiều 22
2.2.5. Luật kết hợp đa mức 22
2.2.5.1. Giới thiệu 22
2.2.5.2. Khai phá luật kết hợp đa mức 24
2.2.6. Luật kết hợp với thuộc tính có trọng số 27
2.2.7. Luật kết hợp mờ 27
2.2.8. Luật kết hợp đóng 27 Một số phương pháp khai phá dữ liệu sinh luật kết hợp
2
3. Chương 3: Một số phương pháp KPDL sinh luật kết hợp 29
3.1. Thuật toán Apriori 29

KẾT LUẬN 80
Danh sách tài liệu tham khảo tiếng Việt 82
Danh sách tài liệu tham khảo tiếng Anh 82
Danh sách WebSites tham khảo 83
Phụ lục (Mã nguồn chương trình) 83 Một số phương pháp khai phá dữ liệu sinh luật kết hợp
5
Ký hiệu và Từ viết tắt
Stt
Ký hiệu viết tắt
Nghĩa tiếng Việt
Nghĩa tiếng Anh
1
CSDL
Cơ sở dữ liệu
Database
2
HQTCSDL
Hệ quản trị cơ sở dữ liệu
Database Management System
3
KPDL
Khai phá dữ liệu
Data Mining
4
KDD
Khai phá tri thức
Knowledge Discovery in Database

Bảng 3.4: Thủ tục Apriori_Gen. 34
Bảng 3.5: Thủ tục Has_Infrequent_Subset. 35
Bảng 3.6: Thủ tục tính tích luỹ độ hỗ trợ của các ứng cử là tập con của giao dịch t. 37
Bảng 3.7: Thuật toán đơn giản sinh luật kết hợp từ tập mục phổ biến. 40
Bảng 3.8: Thủ tục GenRules. 40
Bảng 3.9: Thuật toán nhanh hơn sinh luật kết hợp từ tập mục phổ biến. 40
Bảng 3.10: Thủ tục Ap_GenRules. 41
Bảng 3.11: Cơ sở dữ liệu minh hoạ thuật toán FP-Growth. 43
Bảng 3.12: Mô tả cây FP-tree. 43
Bảng 3.13: Kết quả khai phá dữ liệu bởi thuật toán FP-Growth. 46
Bảng 3.14: Thủ tục thêm 1 tập mục vào FP-tree. 47
Bảng 3.15: Thủ tục tạo cây FP-tree T từ CSDL D. 47
Bảng 3.16: Thủ tục tạo CSDL phụ thuộc mẫu từ cây T. 48
Bảng 3.17: Thủ tục FP_Growth. 48
Bảng 3.18: Cơ sở dữ liệu minh hoạ thuật toán Charm. 51
Bảng 3.19: Mô tả cây IT-tree. 54
Bảng 3.20: Thuật toán Charm. 56
Bảng 3.21: Thủ tục Charm_Extend. 57
Bảng 3.22: Thủ tục Charm_Property. 57
Bảng 3.23: Thủ tục Subsumption_Check. 58
Bảng 3.24: Thủ tục GenAllClosedRules. 60
Bảng 3.25: Cơ sở dữ liệu minh hoạ thuật toán Closet. 63
Bảng 3.26: Thủ tục ClosetMining. 67
Bảng 3.27: Thủ tục Closet. 67
Bảng 4.1: Cấu trúc file dữ liệu RawDataFile. 70
Bảng 4.2: Cấu trúc file dữ liệu StandardData. 72
Bảng 4.3: Cấu trúc file ItemMap. 73 Một số phương pháp khai phá dữ liệu sinh luật kết hợp

Hình 4.5: Màn hình nhập liệu dạng Grid (Visual). 76
Hình 4.6: Màn hình tiến trình thực hiện khai phá dữ liệu. 77
Hình 4.7: Màn hình tiến trình so sánh các giải thuật. 77
Hình 4.8: Màn hình kết quả khai phá dữ liệu dạng Text. 78
Hình 4.9: Màn hình kết quả khai phá dữ liệu dạng Grid (Visual). 78 Một số phương pháp khai phá dữ liệu sinh luật kết hợp
7
MỞ ĐẦU
Ngày nay với một Hệ quản trị cơ sở dữ liệu (HQTCSDL) mạnh, các doanh nghiệp có
thể dễ dàng tổ chức, lưu trữ hàng triệu hồ sơ khách hàng, hợp đồng, số liệu kinh doanh,
công văn, chứng từ, tài liệu, cũng như khai thác chúng một cách có hiệu quả. Có thể nói
rằng với ngôn ngữ truy vấn SQL, các HQTCSDL ngày nay có thể đáp ứng được khoảng
80% nhu cầu khai thác thông tin của con người. Tuy nhiên, chỉ có một chuyên viên phân
tích thị trường đầy kinh nghiệm mới có thể đưa ra được những kết luận đại loại như:
“Khách hàng ở độ tuổi 18-22 khi mua hoa và quà lưu niệm thường mua thêm thiệp” hay
“Khi giá dầu thô tăng đột biến thì chỉ số chứng khoán giảm”. Vấn đề đặt ra là liệu máy
tính có thể tự phát hiện ra được các kết luận như thế sau khi phân tích một khối lượng lớn
dữ liệu hay không?. Câu trả lời là hoàn toàn có thể.
Trong một vài thập niên gần đây, Khai phá dữ liệu (KPDL) đã trở thành một trong
những hướng nghiên cứu chính trong lĩnh vực khoa học máy tính và công nghệ tri thức.
Trong quá trình phát triển đó với hàng loạt nghiên cứu, đề xuất được thử nghiệm và ứng
dụng thành công vào đời sống, đã chứng tỏ rằng KPDL là một lĩnh vực nghiên cứu ổn
định, có nền tảng lý thuyết vững chắc. KPDL bao hàm rất nhiều hướng tiếp cận. Các kỹ
thuật chính được áp dụng trong lĩnh vực này phần lớn được thừa kế từ lĩnh vực cơ sở dữ
liệu (CSDL), máy học (Machine Learning), trí tuệ nhân tạo (AI – Artificial Intelligence),

Chương 4: Xây dựng ứng dụng minh hoạ
Triển khai các giải thuật khai phá luật kết hợp trình bày trong Chương 3 và áp dụng
vào CSDL đơn hàng thực tế và so sánh chúng với nhau. Một số phương pháp khai phá dữ liệu sinh luật kết hợp
9
1. Chương 1: Tổng quan về khai phá dữ liệu (KPDL)
1.1. Khái niệm
KPDL (Data Mining) là quá trình tìm kiếm, phát hiện các tri thức tiềm ẩn và hữu dụng
trong CDSL nhất định. Trong đó tri thức được ngầm hiểu là các thông tin mang tính chất
quy luật và hữu ích đối với người sử dụng.
KPDL là bước quan trọng nhất trong quá trình Khai phá tri thức (KDD – Knowledge
Discovery in Database) - gồm 5 bước như sau [006]:
+ Thu thập dữ liệu (Data colection): là bước thu thập, 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 (Databases, Data marts, Data warehouses, Data
repositories) ban đầu theo một số tiêu chí nhất định.
+ Tiền xử lý dữ liệu (Data preprocessing): là bước làm sạch dữ liệu (xử lý với dữ liệu
không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, …), rút gọn dữ liệu (sử dụng hàm
nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu, …), rời
rạc hoá dữ liệu (rời rạc hoá dựa vào histograms, entropy, phân khoảng, …). Sau bước này,
dữ liệu sẽ nhất quán, đầy đủ, được rút gọn, và được rời rạc hóa.
+ Biến đổi dữ liệu (Data Transformation): đây là bước chuẩn hoá và làm mịn dữ liệu
để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau.
+ KPDL (Data mining): đây là bước áp dụng những kỹ thuật phân tích (phần nhiều là
các kỹ thuật của máy học) nhằm để khai phá dữ liệu, trích chọn được những mẫu thông
tin, những mối liên hệ đặc biệt trong dữ liệu. Đây được xem là bước quan trọng nhất và

được gọi là học có giám sát (Supervised learning).
+ Khai phá luật kết hợp (Association rules mining): khai phá các tri thức dạng luật kết
hợp. Ví dụ: “60% nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua
thêm đậu phộng”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học,
tin-sinh, tài chính và thị trường chứng khoán, …
+ Phân tích chuỗi theo thời gian (Sequential/Temporal patterns): tương tự như khai
phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Phương pháp này được ứng
dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao.
+ Phân cụm (Clustering/Segmentation): xếp các đối tượng theo từng cụm dữ liệu tự
nhiên. Phân cụm còn được gọi là học không giám sát (Unsupervised learning).
+ Mô tả khái niệm (Concept description and summarization): thiên về mô tả, tổng hợp
và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản.
1.3. Một số phương pháp KPDL phổ biến
1.3.1. Phương pháp suy diễn và quy nạp
+ Phương pháp suy diễn: Rút ra thông tin là kết quả logic từ các thông tin nằm trong
CSDL dựa trên các quan hệ trong dữ liệu. Phương pháp suy diễn dựa trên các sự kiện
chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết suất được bằng cách sử
dụng phương pháp này thường là các luật suy diễn.
+ Phương pháp quy nạp: Các thông tin được suy ra từ CSDL bằng cách nó tự tìm
kiếm, tạo mẫu và sinh ra tri thức chứ không bắt đầu với các tri thức đã biết trước.
1.3.2. Cây quyết định và luật
+ Cây quyết định: Cây quyết định là một phương pháp mô tả tri thức dạng đơn giản
nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút trong của cây được
gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các
lá miêu tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây,
qua các cạnh tương ứng với giá trị của các thuộc tính của đối tượng tới lá. Một số phương pháp khai phá dữ liệu sinh luật kết hợp
11

R\X với độ hỗ trợ (tần số xuất hiện) và độ tin cậy:
- Độ hỗ trợ

= s(X

{B}, r).
- Độ tin cậy

= s(X

{B}, r) / s(X, r).
Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật X => B sao
cho tần số xuất hiện của luật không nhỏ hơn ngưỡng

min
cho trước và độ tin cậy của luật
không nhỏ hơn ngưỡng

min
cho trước. Những ngưỡng này thường do người dùng hoặc
các chuyên gia trong lĩnh vực xác định.
Giải thuật tìm các luật kết hợp được bắt đầu bằng việc tìm tất cả các tập mục thường
xuyên xuất hiện (FIS - Frequent ItemSet), đây là các tập mục mà tần số xuất hiện lớn hơn

min
. Sau đó các luật kết hợp sẽ được khai phá từ các tập mục phổ biến này dựa trên

min
.
Chúng ta sẽ đi sâu nghiên cứu về Luật kết hợp trong Chương 2 và Chương 3.

có thể sử dụng các hàm số bất kỳ chứ không chỉ đơn giản là sử dụng các hàm biểu tượng
để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó.
Đặc điểm của mạng neural là không cần gia công dữ liệu nhiều trước khi bắt đầu quá
trình học như các kỹ thuật khác. Tuy nhiên để có thể sử dụng mạng neural có hiệu quả cần
xác định các yếu tố khi thiết kế mạng như:
- Mô hình mạng (kiến trúc) là gì ?
- Mạng cần bao nhiêu tầng và bao nhiêu nút ?
- Khi nào thì việc học dừng ?
Mạng neural được đóng góp với những thông tin trợ giúp của các chuyên gia đáng tin
cậy và được họ đảm bảo các mô hình này làm việc tốt. Sau khi học, mạng có thể được coi
là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học.
1.3.6. Giải thuật di truyền
Đây là phương pháp không chỉ phục vụ phát hiện tri thức mà còn phục vụ rất nhiều bài
toán khác. Ví dụ bài toán tối ưu hoá hoặc lập lịch. Tư tưởng của thuật toán là áp dụng quy
luật của sự chọn lọc tự nhiên. Người ta mô phỏng tập hợp dữ liệu ban đầu bằng ký tự nhị
phân và gọi là những quần thể xuất phát. Bằng các thao tác lai ghép, đột biến chúng ta
biến đổi quần thể gene ban đầu và loại bỏ đi một số gene làm cho số lượng gene trong
quần thể là không thay đổi. Một hàm thích nghi được xây dựng để xác định mức độ thích Một số phương pháp khai phá dữ liệu sinh luật kết hợp
13
nghi của quần thể theo các giai đoạn. Quá trình tiến hoá làm cho các quần thể thích nghi
ngày càng cao. Về mặt lý thuyết giải thuật di truyền cho ta lời giải tối ưu toàn cục (Khác
với phương pháp mạng neural). Tuy nhiên, người ta cũng hạn chế lời giải với một mức độ
thích nghi nào đó để hạn chế số lượng các bước xây dựng quần thể.
Nói theo nghĩa rộng thì giải thuật di truyền mô phỏng lại hệ thống tiến hoá trong tự
nhiên, chính xác hơn là các giải thuật chỉ ra tập các cá thể được hình thành, được ước
lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể
tạo giống và lựa chọn các cá thể nào để loại bỏ.
Một số phương pháp khai phá dữ liệu sinh luật kết hợp
14
Đối với câu hỏi thứ 2: Có thể tạo ra được tất cả các mẫu đáng quan tâm không ? Vấn
đề này liên quan đến tính hoàn thiện của thuật toán khai phá. Nó thường không thực hiện
được và không có khả năng đối với cả hệ thống khai phá dữ liệu để sinh ra tất cả các mẫu
có thể có, có thể tồn tại. Thay cho điều đó người ta tập trung vào mục tiêu tìm kiếm. Khai
phá luật kết hợp là một ví dụ, ở đó người ta sử dụng các độ đo có thể đảm bảo khai phá
trọn vẹn, có nghĩa là với ngưỡng độ hỗ trợ và độ tin cậy nhỏ nhất xác định trước thì có thể
tìm được.
Đối với câu hỏi thứ 3: Hệ thống khai phá có thể chỉ sinh ra các mẫu cần quan tâm
không ? Đây chính là vấn đề tối ưu trong khai phá dữ liệu. Vấn đề này còn là thách thức
rất lớn đối với các nhà khoa học trong lĩnh vực khai phá dữ liệu.
1.5. Các dạng CSDL thường được sử dụng để KPDL
Do KPDL được ứng dụng rộng rãi nên có rất nhiều dạng dữ liệu khác nhau được chấp
nhận trong KPDL [105]. Sau đây là một số dữ liệu điển hình:
+ CSDL quan hệ (Relational databases): là CSDL tác nghiệp được tổ chức theo mô
hình quan hệ. Hầu hết các hệ quản trị CSDL hiện nay đều hỗ trợ dạng CSDL này như
SQL Server, Oracle, DB2, MySQL, MS Access, ….
+ CSDL giao dịch (Transaction databases): đây cũng là một dạng CSDL tác nghiệp,
nhưng các bản ghi thường là các giao dịch. Dạng dữ liệu này phổ biến trong lĩnh vực
thương mại và tài chính ngân hàng.
+ CSDL đa chiều (Multidimentional structures, Data warehouses, Data mart): là các
kho dữ liệu được tập hợp, chọn lọc từ nhiều nguồn khác nhau. Dạng dữ liệu này có mang
tính lịch sử (mang tính thời gian) và chủ yếu phục vụ cho quá trình phân tích cũng như
khai phá tri thức nhằm hỗ trợ quá trình ra quyết định.
+ CSDL hướng đối tượng (Object-oriented databases): dạng CSDL là tập các đối
tượng, các đối tượng này có quan hệ và có thể tương tác với nhau.
+ Dữ liệu không gian và thời gian (Spatial, Temporal, and Time-series data): là dạng

2. Chương 2: Một số vấn đề cơ bản về Luật kết hợp
Khai phá dữ liệu sinh luật kết hợp là một hướng tiếp cận quan trọng trong KPDL nói
chung (thậm chí có những chuyên gia đánh giá là hướng tiếp cận quan trọng nhất), nó
được ra đời và phát triển mạnh mẽ trong những năm gần đây. Lần đầu tiên nó được các
tác giả R. Agrawal, T. Imielinski và A. Swami đề xuất năm 1993, sau đó ngày càng được
nhóm tác giả và các nhà khoa học khác nghiên cứu phát triển và hoàn thiện.
2.1. Định nghĩa luật kết hợp
2.1.1. Ví dụ về luật kết hợp
Ví dụ 1: “Tại siêu thị 10% giao dịch là khách hàng mua bia và lạc. Cũng để ý thấy
nếu một người mua bia thì chắc đến 70% rằng người đó sẽ mua thêm lạc.”
Ví dụ 2: “Tại quầy lưu niệm 12% giao dịch là khách hàng nam giới mua quà lưu niệm
và hoa để tặng bạn gái anh ta. Người bán hàng chắc đến 90% rằng nếu khách hàng là
nam giới mua quà lưu niệm mua cả hoa thì người được tặng là bạn gái anh ta.”
Ở đây vế trái (tiền đề - antecedent) của luật là “mua bia”, “nam giới, mua quà lưu
niệm và hoa”, còn “mua lạc” và “tặng bạn gái” là vế phải (mệnh đề kết luận -
consequent) của luật.
Các số 10%, 12% được gọi là độ hỗ trợ của luật (Support – số phần trăm các giao dịch
chứa cả về phải và vế trái của luật).
Các số 70%, 90% được gọi là độ tin cậy của luật (Confidence – số phần trăm giao dịch
thoả mãn vế trái thì cũng thoả mãn vế phải).
Chúng ta thấy rằng tri thức đem lại bởi những luật kết hợp ở dạng trên có 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 dữ liệu 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. Những tri thức này không chỉ đơn giản là kết quả của các phép
nhóm, tính tổng hay sắp xếp mà là kết quả của quá trình tính toán phức tạp và tốn nhiều
thời gian.
Tuy luật kết hợp là dạng luật khá đơn giản nhưng lại mang rất nhiều ý nghĩa. Thông
tin mà dạng luật này đem lại rất đá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 KPDL và đây chính là động


2
I
(với 2
I
là tập các tập con của I).
Ví dụ: CSDL (dạng giao dịch) I = {A, B, C, D, T, W}, T = {1, 2, 3, 4, 5, 6} với thông
tin về giao dịch cho ở bảng sau:
TID
Danh sách các mục
1
A
C

T
W
2

C
D

W
3
A
C

T
W
4
A




Tuy nhiên khi xét trên 1 CSDL D cụ thể ta có thể bỏ qua |D| vì nó cố định và lúc này
có thể coi sup(X) = |{t

D: X

t}|.
+ Tập mục phổ biến (FIS: Frequent ItemSet): Tập mục X được gọi là tập mục phổ biến
với độ hỗ trợ minsup (minsup là giá trị cho trước được xác định bởi người sử dụng) nếu độ
hỗ trợ của nó lớn hơn hoặc bằng minsup: s(X)

minsup.
Bảng sau đây liệt kê các FIS trong CSDL cho ở trên với giá trị minsup = 50%

Các tập mục phổ biến
Tần suất
Độ hỗ trợ
C
6
100%
W, CW
5
83%
A, D, T, AC, AW, CD, CT, ACW
4
67%
AT, DW, TW, ACT, ATW, CDW, CTW, ACTW
3


minconf.

+ Bài toán khai phá dữ luật kết hợp (ở dạng đơn giải nhất): Cho một CSDL D, độ hỗ
trợ tối thiểu minsup, độ tin cậy tối thiểu minconf. Hãy tìm kiếm tất cả các luật kết hợp r
dạng X => Y (s, c) thoả mãn cả 2 điều kiện:
+ s(r) = s(X

Y)

minsup.
+ c(r) = s(X

Y) / s(X)

minconf.

Hầu hết các thuật toán được đề xuất để khai phá luật kết hợp thường chia bài toán
thành 2 pha:
+ Pha 1: Tìm tất cả các tập mục phổ biến từ CSDL tức là tìm tất cả các tập mục X thoả
mãn s(X)

minsup. Đây là pha tốn khá nhiều thời gian của CPU và thời gian vào ra ổ đĩa.
+ Pha 2: Sinh các luật tin cậy từ các tập phổ biến đã tìm thấy ở pha 1. Pha này tương
đối đơn giản và tốn ít thời gian hơn so với pha trên. Nếu X là một tập mục phổ biến thì
luật kết hợp được sinh từ X có dạng r: X\Y => Y, với Y

X, Y

Ø và c(r)

AW
 
%100
C
Có
Một số phương pháp khai phá dữ liệu sinh luật kết hợp
19
Bảng 2.3: Các luật kết hợp được sinh từ tập mục phổ biến ACW.

2.1.2.2. Một số tính chất của tập mục phổ biến
+ Tính chất 1: Độ hỗ trợ của tập con.
Cho X, Y là các tập mục và X

Y thì sup(X)

sup(Y).
+ Tính chất 2: Một tập chứa tập không phổ biến thì nó cũng không phổ biến.
Cụ thể: Nếu X

Y và sup(X) < minsup thì sup(Y) < minsup.
+ Tính chất 3: Mọi tập con của một tập phổ biến cũng là tập phổ biến.
Cụ thể: Nếu X

Y và sup(Y) > minsup thì sup(X) > minsup.

2.1.2.3. Một số tính chất của luật kết hợp
+ Tính chất 1: Không hợp các luật kết hợp.


minconf. (*)
Xuất phát từ giả thiết: X => Y

Z là luật kết hợp mạnh nên
sup(X

Y

Z)

minsup và sup(X

Y

Z) / sup(X)

minconf
mà hiển nhiên sup(X

Y)

sup(X

Y

Z) nên (*) đã được chứng minh.
Tương tự X => Z cũng là luật kết hợp mạnh.

+ Tính chất 3: Các luật kết hợp không có tính chất bắc cầu.


sup(L) / sup(L \ C)

minconf.
Và hiển nhiên theo giả thiết sup(L)

minsup nên (L \ D) => D là mạnh.
Các tính chất này của luật kết hợp sẽ được sử dụng trong các thuật toán về sau.

2.2. Các loại luật kết hợp và hướng tiếp cận
2.2.1. Luật kết hợp nhị phân
// Binary association rule or Boolean association rule.
Đối với các luật kết hợp này, các mục chỉ được quan tâm là có xuất hiện hay không
xuất hiện trong giao dịch chứ không quan tâm đến mức độ xuất hiện.
Ví dụ: “Mua bia => Mua lạc”, “Mua quà, Mua hoa => Tặng bạn gái”,
Đây là dạng luật kết hợp đơn giản nhất và điều đặc biệt là chúng ta có thể chuyển các
dạng luật khác về dạng luật này nhờ phương pháp rời rạc hoá. Các thuật toán tiêu biểu
thực hiện khai phá luật kết hợp nhị phân là Apriori và FP-Growth. Chúng ta sẽ đi sâu
nghiên cứu trong phần tiếp sau.
2.2.2. Luật kết hợp định lượng
// Quantitative assosiation rule.
2.2.2.1. Giới thiệu
Đối với loại này, ta không chỉ quan tâm tới sự có mặt hay không của các mục trong
giao dịch mà còn quan tâm tới định lượng của từng mục trong luật.
Ví dụ: “Mua bia 2-5 chai => Mua lạc 5-10 gói”,
“Tuổi 20-30, Mua quà $5-$10, Mua hoa $3-$8 => Tặng bạn gái thân”,
2.2.2.2. Khai phá luật kết hợp định lượng
Để phát hiện ra luật kết hợp định lượng ta phải thực hiện các bước sau:
+ Tiền xử lý: Thực hiện rời rạc hoá chuyển đổi các thuộc tính số và thuộc tính phân
loại thành các thuộc tính nhị phân để có thể sử dụng được các thuật toán khai phá luật kết

450
0003
40
Nam
Đúng
2
550
0004
20
Nữ
Sai
0
150

Bảng 2.4: Dữ liệu điều tra dân số.

Giải thích các thuộc tính:
TID: Định danh cho mỗi cuộc điều tra. Khi khai phá dữ liệu không cần quan tâm đến
thuộc tính này.
Tuổi: Thuộc tính này có kiểu số và nhận nhiều giá trị khác nhau. Để khai phá dữ liệu
dạng này ta ánh xạ thuộc tính nhận giá trị trong khoảng nào đó thành các thuộc tính nhị
phân. Ta có thể thực hiện ánh xạ như sau: Tuổi dưới 16 thành thuộc tính “rất trẻ”, từ 16
đến 30 thành thuộc tính “trẻ”, từ 31 đến 55 thành thuộc tính “trung niên”, lớn hơn 55
thành thuộc tính “già”.

Trung niên
8.
Chưa kết hôn
13.
Lương trung bình
4.
Già
9.
Không con
14.
Lương cao
5.
Nam
10.
Một con
Bảng 2.5: Danh sách thuộc tính sau khi rời rạc hoá.

Giả sử sau khi khai phá ta tìm được các luật sau:
2 ^ 6 => 13, 3 ^ 7 => 14,
Ta chuyển các luật này về dạng định lượng tương ứng:
“Trẻ” ^ “Nữ”=>“Lương trung bình”, “Trung niên” ^ “Đã kết hôn”=>“Lương cao”,
Hay “Tuổi 16-30” ^ “Giới tính nữ” => “Lương trên 200 và dưới 400”,
“Tuổi 31-55” ^ “Đã kết hôn” => “Lương trên 400”,
2.2.3. Luật kết hợp đơn chiều
// Single-dimention assiociation rule.
Đối với loại này, các luật chỉ tham chiếu đến 1 chiều của dữ liệu.
Ví dụ: “Mua bia => Mua lạc”, “Mua quà, Mua hoa => Mua thiếp”,

TID
Danh sách các mục bán
1
Máy tính để bàn IBM, Máy in HP màu.
2
Phần mềm bảng tính Excel, Hệ quản trị CSDL MySql.
3
Chuột Mitsumi, Bàn phím Mitsumi.
4
Máy tính để bàn HP, Hệ quản trị CSDL MySql.
5
Máy tính để bàn Fujitsu, Máy tính xách tay Toshiba.
Bảng 2.6: Ví dụ CSDL giao dịch bán hàng.

Bảng trên cho biết các giao dịch của một cửa hàng bán máy tính: định danh giao dịch
TID và các mục bán được tương ứng. Khái niệm phân cấp cho các mục chỉ ra trong hình
sau (Theo chiều mũi tên, khi độ sâu tăng mức trừu tượng giảm dần):

Hình 2.1: Sự phân cấp mức độ trừu tượng của dữ liệu.

Khái niệm phân cấp được xác định tuần tự từ mức thấp đến mức cao. Trong hình trên,
khái niệm phân cấp thành 5 mức: 0, 1, 2, 3 và 4. Ta qui ước các mức được đánh số từ trên
Mức 0
Mức 1
Mức 2
Mức 3
Mức 4

24
xuống, bắt đầu từ mức 0 ở nút gốc cho tất cả các nút (mức tổng quát nhất). Mức 1 bao
gồm “Phần cứng” và “Phần mềm”, , Mức 4 là mức cụ thể, riêng biệt nhất.
Các mục trong bảng dữ liệu cho ban đầu là mức cao nhất của khái niệm phân cấp trong
hình trên. Khó có thể tìm ra các mẫu mua đáng quan tâm trong mức nguyên thuỷ này.
Chẳng hạn: “Máy tính để bàn IBM” hoặc “Phần mềm Lotus”, chúng chỉ xuất hiện rất ít
trên tổng số các giao dịch, vì thế khó có thể tìm được các luật kết hợp có chứa chúng.
Các luật được sinh ra từ khai phá luật kết hợp đa mức với khái niệm phân cấp được gọi
là luật kết hợp đa mức (vì chúng đề cập đến hơn một mức khái niệm).

2.2.5.2. Khai phá luật kết hợp đa mức
Có một số hướng tiếp cận dựa trên khung làm việc độ hỗ trợ và độ tin cậy (support-
confidence framework). Nhìn chung các thuật toán đều sử dụng chiến lược chia để trị
Top-down, ở đó thực hiện tính tích luỹ cho các tập mục trong mỗi mức khái niệm, bắt đầu
từ mức khái niệm 1 và đi xuống mức cao hơn, mức khái niệm cụ thể hơn, cho đến khi
không còn tập mục phổ biến nào được tìm thấy. Điều đó có nghĩa là: lần đầu tiên ta tìm tất
cả các tập mục phổ biến ở mức khái niệm 1, sau đó tìm các tập mục phổ biến ở mức khái
niệm 2, và cứ tiếp tục như vậy… Với mỗi mức, có thể sử dụng bất kỳ thuật toán nào để
phát hiện tập mục phổ biến, chẳng hạn như Apriori, FP-Growth hoặc các biến thể của
chúng. Tuy nhiên khi áp dụng các thuật toán đó ta phải có một số cải tiến như sau:
+ Sử dụng ngưỡng độ hỗ trợ (minsup) giống nhau cho tất cả các mức trừu tượng.
Ví dụ: trong hình sau, sử dụng minsup = 10% cho cả hai mức trừu tượng (ví dụ từ mức
“Máy tính” xuống mức “Máy tính để bàn” và “Máy tính xách tay”). Khi đó cả “Máy
tính” và “Máy tính để bàn” được tìm thấy là phổ biến, trong khi đó “Máy tính xách tay”
thì không.

Hình 2.2: Khai phá luật kết hợp đa mức với minsup giống nhau tại các mức.

Khi sử dụng minsup giống nhau thì thủ tục tìm kiếm sẽ đơn giản hơn. Phương pháp
này thực sự đơn giản trong trường hợp người dùng yêu cầu chỉ một ngưỡng độ hỗ trợ cực

Hình 2.3: Khai phá luật kết hợp đa mức với minsup giảm dần.

Với các tiếp cận trên, ta có một số lựa chọn:
+ Từ mức này đến mức khác một cách độc lập (level-by-level independent): Đây là
cách tìm kiếm hoàn toàn theo chiều rộng, ở đó không có tri thức cơ sở của các tập mục
phổ biến được dùng để tỉa. Mỗi nút đều được xét mà không chú ý đến nút cha đã xét có là
phổ biến hay không.
+ Đi qua các mức có chọn lọc (level-cross filtering): Một mục ở mức thứ i được xét
khi và chỉ khi nút cha ở mức thứ (i-1) là phổ biến. Nói cách khác là, ta chỉ nghiên cứu luật
kết hợp cụ thể hơn từ luật trừu tượng (tổng quát) hơn. Nếu một nút là phổ biến thì các nút
con của nó sẽ được xét, nếu không các nút con của nó sẽ bị tỉa. Điều đó sẽ làm giảm
không gian tìm kiếm. Ví dụ: trong hình sau, các nút con của “Máy tính” sẽ không được
xét vì “Máy tính” không là phổ biến.

Hình 2.4: Khai phá luật kết hợp đa mức với minsup giảm dần kết hợp lọc.
Máy tính
sup = 16%
Máy để bàn
[không xét]

Máy xách tay
[không xét]

Mức 2
minsup = 20%

Mức 3
minsup = 8%

Máy tính