..

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

LUẬN VĂN THẠC SĨ KHOA HỌC

PHÁT HIỆN CÁC LUẬT KẾT HỢP
TRONG CƠ SỞ DỮ LIỆU
NGÀNH: CÔNG NGHỆ THÔNG TIN
MÃ SỐ:

NGUYỄN HỒNG PHƯƠNG

Người hướng dẫn khoa học: TS. NGUYỄN KIM ANH

HÀ NỘI 2009


LỜI CAM ĐOAN
Tôi xin cam đoan luận văn “Phát hiện các luật kết hợp trong cơ sở dữ liệu” là
do tôi thực hiện dưới sự hướng dẫn của TS. Nguyễn Kim Anh – Viện Công Nghệ
Thông Tin và Truyền Thông, trường Đại học Bách Khoa Hà Nội. Mọi trích dẫn và
tài liệu tham khảo được sử dụng trong luận văn đều được tơi chỉ rõ nguồn gốc.
Tơi xin hồn tồn chịu trách nhiệm về lời cam đoan trên.

Hà Nội, ngày 22 tháng 10 năm 2009.
Tác giả luận văn

Nguyễn Hồng Phương

Phát hiện các luật kết hợp trong cơ sở dữ liệu

Mục lục
Mục lục------------------------------------------------------------------------------------------- 1
Danh mục hình vẽ, bảng biểu ----------------------------------------------------------------- 3
Danh mục các thuật ngữ, từ viết tắt ---------------------------------------------------------- 5
Lời nói đầu--------------------------------------------------------------------------------------- 6
Chương 1: Tổng quan -------------------------------------------------------------------------- 8
1.1. Khai phá dữ liệu ------------------------------------------------------------------------ 8
1.2. Luật kết hợp ----------------------------------------------------------------------------- 9
1.2.1. Định nghĩa chính thức ------------------------------------------------------------ 9
1.2.2. Định nghĩa thay thế -------------------------------------------------------------- 10
1.3. Các vấn đề về phát hiện luật kết hợp trong cơ sở dữ liệu ----------------------- 11
Chương 2: Luật kết hợp cơ bản ------------------------------------------------------------- 13
2.1. Hai tính chất --------------------------------------------------------------------------- 13
2.1.1. Tính chất 1 ------------------------------------------------------------------------ 13
2.1.2. Tính chất 2 ------------------------------------------------------------------------ 13
2.2. Phát hiện các tập mục thường xuyên ----------------------------------------------- 14
2.2.1. Giải thuật Apriori ---------------------------------------------------------------- 14
2.2.2. Giải thuật AprioriTid ------------------------------------------------------------ 15
2.3. Phát hiện các luật kết hợp ----------------------------------------------------------- 17
2.3.1. Giải thuật đơn giản -------------------------------------------------------------- 18
2.3.2. Một giải thuật nhanh hơn ------------------------------------------------------- 19
Chương 3: Sử dụng FP-tree phát hiện các tập mục thường xuyên --------------------- 21
3.1. Giới thiệu ------------------------------------------------------------------------------ 21
3.2. Thiết kế và xây dựng cây mẫu thường xuyên ------------------------------------- 22
3.2.1. Cây mẫu thường xun --------------------------------------------------------- 22
3.2.2. Tính đầy đủ và tính cơ đọng của cây FP-------------------------------------- 26

3.3. Khai phá mẫu thường xuyên sử dụng cây FP ------------------------------------- 27
3.4. Đánh giá thực nghiệm và nghiên cứu hiệu năng --------------------------------- 31
Chương 4: Luật kết hợp mở rộng ----------------------------------------------------------- 33
4.1. Khai phá luật kết hợp đa mức ------------------------------------------------------- 33
4.1.1. Phát biểu bài toán ---------------------------------------------------------------- 33
4.1.2. Thuật toán ------------------------------------------------------------------------ 37
4.2. Khai phá luật kết hợp định lượng--------------------------------------------------- 40
4.2.1. Xử lý thuộc tính định lượng ---------------------------------------------------- 41
Nguyễn Hồng Phương

1/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

4.2.2. Ánh xạ từ bài toán luật kết hợp định lượng về bài toán luật kết hợp
boolean ----------------------------------------------------------------------------------- 43
4.2.3. Phát biểu hình thức bài tốn phát hiện luật kết hợp định lượng ----------- 44
4.2.4. Cách tiếp cận khối dày đặc ----------------------------------------------------- 47
4.3. Khai phá luật kết hợp mờ ------------------------------------------------------------ 53
4.3.1. Tập rõ ----------------------------------------------------------------------------- 54
4.3.2. Tập mờ ---------------------------------------------------------------------------- 54
4.3.3. Các thao tác mờ ------------------------------------------------------------------ 55
4.3.4. Giao dịch mờ và luật kết hợp mờ ---------------------------------------------- 56
4.3.5. Phân vùng mờ miền thuộc tính định lượng ---------------------------------- 60
4.4. Khai phá luật kết hợp mờ có trọng số ---------------------------------------------- 62
4.4.1. Luật kết hợp mờ trọng số ------------------------------------------------------- 62
4.4.2. Luật kết hợp mờ trọng số chuẩn hóa ------------------------------------------ 63
Chương 5: Thử nghiệm ---------------------------------------------------------------------- 67
5.1. Phát hiện luật kết hợp với thuật toán Apriori ------------------------------------- 67

5.1.1. Các lớp của thuật toán ---------------------------------------------------------- 67
5.1.2. Kết quả chạy thử ----------------------------------------------------------------- 68
5.2. Phát hiện luật kết hợp nhờ xây dựng FP-tree ------------------------------------- 70
5.2.1. Dữ liệu đầu vào ------------------------------------------------------------------ 70
5.2.2. Kết quả chạy thử ----------------------------------------------------------------- 70
5.3. Phát hiện luật kết hợp định lượng nhờ phân vùng ------------------------------- 71
5.3.1. Các lớp của thuật toán ---------------------------------------------------------- 71
5.3.2. Kết quả chạy thử ----------------------------------------------------------------- 73
Chương 6: Kết luận và hướng phát triển -------------------------------------------------- 74
6.1. Kết luận chung ------------------------------------------------------------------------ 74
6.1.1. Những kết quả đạt được -------------------------------------------------------- 74
6.1.2. Tồn tại ----------------------------------------------------------------------------- 74
6.2. Hướng phát triển ---------------------------------------------------------------------- 75
Tài liệu tham khảo ---------------------------------------------------------------------------- 76

Nguyễn Hồng Phương

2/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Danh mục hình vẽ, bảng biểu
Hình 1.1: Quá trình phát hiện tri thức .......................................................................... 9
Bảng 1.2: Ví dụ cơ sở dữ liệu .................................................................................... 11
Hình 1.3: Các vấn đề trình bày trong báo cáo ............................................................ 12
Hình 2.1: A nhỏ thì superset(A) cũng nhỏ ................................................................. 13
Hình 2.2: B lớn thì subset(B) cũng lớn ...................................................................... 13
Hình 2.3: Giải thuật Apriori ....................................................................................... 14
Hình 2.4: Hàm AprioriGen sử dụng trong giải thuật Apriori .................................... 15

Hình 2.5: Giải thuật AprioriTid ................................................................................. 16
Hình 2.6: Ví dụ về AprioriTid ................................................................................... 17
Hình 2.7: Một giải thuật đơn giản sinh các luật ......................................................... 18
Hình 2.8: Thủ tục GenRules được sử dụng trong giải thuật trên ............................... 18
Hình 2.9: Một giải thuật nhanh hơn để sinh luật ....................................................... 19
Hình 2.10: Thủ tục GenRules được sử dụng trong giải thuật nhanh ......................... 19
Bảng 3.1: Một cơ sở dữ liệu giao dịch ....................................................................... 23
Hình 3.2: Cây FP kết quả ........................................................................................... 25
Bảng 3.3: Cơ sở mẫu và cây FP có điều kiện của các mục........................................ 29
Hình 3.4: Thời gian thực hiện và ngưỡng hỗ trợ ....................................................... 32
Hình 3.5: Thời gian thực hiện và số giao dịch ........................................................... 32
Hình 4.1: Phân cấp khái niệm đồ uống ...................................................................... 33
Hình 4.2: Hai phân cấp khái niệm.............................................................................. 34
Hình 4.3: Ví dụ ........................................................................................................... 35
Hình 4.4: Ví dụ về luật thú vị..................................................................................... 37
Hình 4.5:Thuật tốn cơ bản ........................................................................................ 38
Hình 4.6: Thuật toán Cumulate .................................................................................. 40
Bảng 4.7: Quan hệ People (Người) ............................................................................ 41
Bảng 4.8: Ví dụ về luật kết hợp định lượng có phạm trù........................................... 41
Bảng 4.9: Hai cách tiếp cận phân vùng thuộc tính..................................................... 43
Bảng 4.10: Bảng thu được sau khi ánh xạ ................................................................. 44
Hình 4.11: Các bước giải quyết bài tốn.................................................................... 47
Hình 4.12: Ví dụ về một số luật định lượng .............................................................. 48
Hình 4.13: Tập mờ ..................................................................................................... 55
Hình 4.14: Phần bù mờ .............................................................................................. 55
Bảng 4.15: Tập 6 giao dịch mờ .................................................................................. 56
Bảng 4.16: Tuổi và giờ sinh của 6 người ................................................................... 58
Hình 4.17:Một số nhãn ngơn ngữ của thuộc tính Age ............................................... 59
Nguyễn Hồng Phương


3/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Hình 4.18: Một số nhãn ngơn ngữ của thuộc tính Hour ............................................ 59
Bảng 4.19: Giao dịch mờ tương ứng của bảng 4.16 .................................................. 59
Hình 4.20: Ví dụ phân vùng tập mờ ........................................................................... 61
Bảng 4.21: Miền của tập mờ Age (p = 30%) ............................................................. 61
Bảng 4.22: Ví dụ thuộc tính và giá trị mờ.................................................................. 63
Bảng 4.23: Trọng số của các mục .............................................................................. 63
Hình 4.24: Thuật tốn khai phá luật kết hợp trọng số chuẩn hóa .............................. 65
Bảng 5.1: Tổng hợp số liệu kiểm thử Apriori ............................................................ 69
Bảng 5.2: Tổng hợp số liệu kiểm thử FP-tree ............................................................ 70
Bảng 5.3: Tổng hợp số liệu kiểm thử luật định lượng ............................................... 73

Nguyễn Hồng Phương

4/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Danh mục các thuật ngữ, từ viết tắt
Thuật ngữ, từ viết tắt
Data Mining
KDD - Knowledge Discovery in
Databases
Association Rule Discovery
Apriori

item
itemset
k-itemset
frequent itemset
large itemset
FP-tree
minsup, smin
minconf, cmin
crisp set
Fuzzy set
Fuzzy transaction
quantitative association rule
quantitative attribute
categorical attribute
WFS
NWFS

Nguyễn Hồng Phương

Ý nghĩa, giải thích
Khai phá dữ liệu
Phát hiện tri thức trong cơ sở dữ liệu
Phát hiện luật kết hợp
Tên một giải thuật nổi tiếng để phát hiện các tập
mục thường xuyên
Mục
Tập mục
Tập mục có k mục
Tập mục thường xuyên, phổ biến
Tập mục lớn

Cây mẫu thường xuyên
Độ hỗ trợ tối thiểu
Độ tin cậy tối thiểu
Tập rõ
Tập mờ
Giao dịch mờ
Luật kết hợp định lượng
Thuộc tính định lượng
Thuộc tính phạm trù
Độ hỗ trợ mờ trọng số
Độ hỗ trợ mờ trọng số chuẩn hóa

5/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Lời nói đầu
Sự tiến bộ của cơng nghệ cho phép chúng ta thu thập một lượng lớn dữ liệu và
lưu trữ chúng. Tuy nhiên, các tập dữ liệu này tự chúng không phản ánh được các quy
luật giữa các thuộc tính để từ đó có thể vận dụng vào thực tế. Khai phá dữ liệu được
xem như là một hướng nghiên cứu trong cơ sở dữ liệu. Từ một khối dữ liệu lớn, việc
khai phá các tri thức trên chúng phục vụ cho các hệ thống sử dụng trí tuệ nhân tạo
đang được các trung tâm, các trường đại học và một số công ty lớn quan tâm nghiên
cứu và đã có một số cơng trình được cơng bố.
Bài tốn khai phá luật kết hợp đã được giới thiệu từ năm 1993, trong đó người
ta mong muốn xác định được mối quan hệ giữa các thuộc tính trong một cấu trúc của
cơ sở dữ liệu quan hệ. Bài toán khai phá luật kết hợp đặt ra là tìm tất cả các luật kết
hợp thỏa mãn độ hỗ trợ tối thiểu và độ tin cậy tối thiểu.
Với mong muốn tìm hiểu về lĩnh vực này và đồng thời cũng cài đặt thử

nghiệm một số thuật tốn, em đã thực hiện cơng việc này trong quá trình làm luận
văn cao học. Bản báo cáo này trình bày lý thuyết từ cơ bản đến chuyên sâu, từ nền
tảng của bài toán phát hiện luật kết hợp trong cơ sở dữ liệu giao dịch và xa hơn nữa
là phát hiện các luật kết hợp mở rộng trong cơ sở dữ liệu như luật kết hợp định lượng,
luật kết hợp đa mức, luật kết hợp mờ.
Bố cục của luận văn gồm các chương sau:
Chương 1 - Tổng quan. Chương này trình bày khái niệm khai phá dữ liệu và luật kết
hợp.
Chương 2 - Luật kết hợp cơ bản. Nội dung chương này giới thiệu các tính chất và
hai giai đoạn để tìm ra luật kết hợp trong cơ sở dữ liệu giao dịch.
Chương 3 - Sử dụng FP-Tree để phát hiện các tập mục thường xuyên. Chương này
giới thiệu một cách tiếp cận khác để sinh ra các tập mục thường xuyên mà không
phải trải qua bước sản sinh các tập mục ứng cử viên như cách truyền thống.
Chương 4 - Luật kết hợp mở rộng. Chương này trình bày các phạm vi khác nhau của
bài toán phát hiện luật kết hợp: phát hiện luật kết hợp đa mức trong cơ sở dữ liệu
giao dịch, phát hiện luật kết hợp định lượng, phát hiện luật kết hợp mờ trong cơ sở
dữ liệu quan hệ.
Chương 5 - Thử nghiệm. Chương này giới thiệu các cài đặt thuật toán và cung cấp
một số kết quả kiểm thử.

Nguyễn Hồng Phương

6/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Chương 6 - Kết luận và hướng phát triển. Chương này tổng kết lại những việc đã
làm được và chưa làm được của luận văn, đồng thời cung cấp một số gợi ý cho các
công việc tiếp theo.

Em xin gửi lời cảm ơn tới TS. Nguyễn Kim Anh, người đã tận tình giúp đỡ em trong
quá trình làm luận văn.
Em mong nhận được ý kiến đóng góp của thầy cơ giáo và bạn bè.
Hà Nội, ngày 22 tháng 10 năm 2009
Học viên

Nguyễn Hồng Phương

Nguyễn Hồng Phương

7/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Chương 1: Tổng quan
Phần đầu của chương này sẽ giới thiệu tổng quan quy trình khai phá dữ liệu (data
mining) một cách ngắn gọn. Luật kết hợp trình bày trong phần tiếp theo được xem
như là một kỹ thuật khai phá dữ liệu.

1.1. Khai phá dữ liệu
Khả năng sản sinh và thu thập dữ liệu đã tăng lên rất nhanh trong thập niên gần
đây.Các tiến bộ trong thu thập dữ liệu khoa học và thương mại như thiết bị mã vạch,
bộ cảm biến, vệ tinh không gian,... đã làm dữ liệu trở nên “ngập lụt”. Bên cạnh đó,
cơng nghệ lưu trữ cũng có tiến bộ. Con người đã tạo ra những thiết bị lưu trữ nhanh,
rẻ, dung lượng lớn như đĩa từ, đĩa CD-ROM.
Chúng ta cần có cơng nghệ mới hay công cụ với khả năng thông minh để tự động
biến đổi dữ liệu đã được xử lý thành những thơng tin và tri thức có ích. Thuật ngữ
phát hiện tri thức trong cơ sở dữ liệu (knowledge discovery in databases - KDD) đã
trở nên phổ biến. Quá trình phát hiện tri thức phải trải qua một số bước tương tác và

lặp. Xen giữa các bước là việc ứng dụng các giải thuật để trích rút ra các mẫu dữ liệu,
gọi là khai phá dữ liệu (data mining).
Theo [1], các bước cơ bản của quá trình phát hiện tri thức gồm:
1. Sau khi phân tích mục đích của người sử dụng cuối và nhận về các tri thức cần
thiết, chúng ta chọn ra các tập dữ liệu đích. Điều này có nghĩa là tập trung vào một
tập con các biến hay dữ liệu mẫu.
2. Dữ liệu đích được tiền xử lý và làm sạch để loại bỏ những dữ liệu bẩn và ngoại lai.
3. Đưa ra những đặc trưng có ích biểu diễn dữ liệu.
4. Mục tiêu của quá trình phát hiện tri thức là dự đoán các giá trị tương lai của các
biến quan tâm hoặc tìm ra những mẫu dữ liệu mà con người có thể hiểu. Giải thuật
khai phá dữ liệu thích hợp được lựa chọn và áp dụng. Có một số thuật giải: kết hợp,
phân lớp, phân nhóm,...

Nguyễn Hồng Phương

8/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Chọn

Biến đổi

Tiền xử lý



Khai phá
dữ liệu


Thông dịch /
Đánh giá




Dữ liệu

Dữ liệu
mục tiêu

Dữ liệu tiền
xử lý

Dữ liệu biến
đổi

Mẫu

Tri thức

Hình 1.1: Quá trình phát hiện tri thức

1.2. Luật kết hợp
Bài tốn phát hiện luật kết hợp từ dữ liệu được đề xuất trong [8] và gọi là "bài toán
cái rỏ hàng". Bài toán cho một tập các mặt hàng và một tập lớn các giao dịch. Nhiệm
vụ là tìm ra mối quan hệ giữa các mặt hàng trong rỏ hàng. Ralf Rantzau [1] có trình
bày các định nghĩa liên quan đến luật kết hợp.
1.2.1. Định nghĩa chính thức

Cho I = {I 1 , I 2 ,..., I m } là một tập các thuộc tính gọi là các mục (items). Một tập con
X ⊆ I được gọi là một tập mục (itemset). Một k-tập mục (k-itemset) là một tập mục

chứa k mục. Cho cơ sở dữ liệu D = {T1 , T2 ,..., Tn } là một tập các giao dịch, trong đó

mỗi giao dịch Ti , i ∈ {1,..., n} là một tập mục. Một giao dịch T chứa một tập mục

X nếu X ⊆ T . Mỗi tập mục có một thông số thống kê gọi là độ hỗ trợ (support) hay

tần số (frequency). Độ hỗ trợ s của một tập mục X là tỉ lệ các giao dịch trong cơ sở
dữ liệu D chứa tập mục X , tức là:
s( X ) =

{T ∈ D X ⊆ T }
D

Một luật kết hợp là một luật có dạng X ⇒ Y , trong đó X ⊂ I , Y ⊂ I và X ∩ Y = ∅.
X được gọi là phần đầu của luật (antecedent) và Y được gọi là phần thân của luật

(consequent). Luật X ⇒ Y có độ hỗ trợ s trong tập giao dịch D nếu s% các giao dịch
trong D chứa X ∪ Y :
s=

Nguyễn Hồng Phương

X ∪Y
D

9/78



Phát hiện các luật kết hợp trong cơ sở dữ liệu

Luật X ⇒ Y có độ tin cậy c trong tập giao dịch D nếu c% các giao dịch trong
D chứa X thì cũng chứa Y :
c=

X ∪Y
X

hay c( X , Y ) =

s( X ∪ Y )
s( X )

Độ tin cậy biểu thị khả năng của một luật. Một ngưỡng c min của độ tin cậy (còn gọi là
độ tin cậy tối thiểu - minconf) được sử dụng để loại bỏ những luật không đủ mạnh.
Một ngưỡng s min của độ hỗ trợ (còn gọi là độ hỗ trợ tối thiểu - minsupp) loại bỏ các
luật mà số lượng các giao dịch chứa phần đầu và thân luật nhỏ hơn một lượng xác
định. Các tập mục với độ hỗ trợ tối thiểu được gọi là các tập mục thường xuyên
(frequent itemsets) hay các tập mục lớn (large itemsets).
Bài toán tìm kiếm các luật kết hợp được phát biểu như sau: Cho một tập mục I , một
cơ sở dữ liệu các tập mục D , một ngưỡng hỗ trợ s min và một ngưỡng tin cậy c min ,
chúng ta phải tìm ra các luật kết hợp X ⇒ Y trong D với độ hỗ trợ s ≥ s min và độ tin
cậy c ≥ c min
1.2.2. Định nghĩa thay thế
Cho D = {T1 , T2 ,..., Tn } là một quan hệ trên sơ đồ quan hệ I = {I 1 , I 2 ,..., I m } , trong đó

mỗi thuộc tính I i , i ∈ {1,..., m} nhận hai giá trị {true, false}. Nói theo cách khác, D là
một tập các vector nhị phân chiều dài m. Với mỗi hàng T của quan hệ D thỏa mãn

điều kiện ∀i ∈ {1,..., m} : T [i ] ↔ I i ∈ T . Độ hỗ trợ của một tập mục X ⊆ I là:
s( X ) =

{T ∈ D ∀I

i

}

∈ X :T [i ]

D

Hơn nữa, chúng ta có thể dùng cách tiếp cận xác suất để định nghĩa độ hỗ trợ và độ
tin cậy. X và Y là các tập mục, trong đó X ⊂ I , Y ⊂ I và X ∩ Y = ∅. P( X ) là xác suất
tất cả các mục trong X có trong một giao dịch. Độ hỗ trợ s của một luật X ⇒ Y được
định nghĩa là s = P( X ∪ Y ) và độ tin cậy c là xác suất có điều kiện của Y khi có X,
tức là c = P(Y X )
Ví dụ:

Bảng 1.2 là một ví dụ về cơ sở dữ liệu các giao dịch trong siêu thị. I là một tập các
mặt hàng bao gồm các mặt hàng A, B, C, D. Mỗi dòng của bảng chứa một định danh
giao dịch TID mô tả một giao dịch mua hàng của một khách hàng, hay nói khác đi
đó là một rỏ các mặt hàng khách hàng đã quyết định mua.
Độ hỗ trợ của tập mục {A, B} là 0.4. Độ hỗ trợ của tập {A, B, D} là 0.3. Do đó, độ
tin cậy của luật {A, B}⇒{D} là 0.75. Nếu độ hỗ trợ tối thiểu smin nhỏ hơn hoặc bằng
Nguyễn Hồng Phương

10/78



Phát hiện các luật kết hợp trong cơ sở dữ liệu

0.3 và độ tin cậy cmin nhỏ hơn hoặc bằng 0.75 thì luật này được coi là luật kết hợp.
Chúng ta có thể phát biểu "Nếu khách hàng mua mặt hàng A và B thì có cơ hội 75%
khách hàng cũng sẽ mua D".
TID
1
2
3
4
5
6
7
8
9
10

Rỏ hàng
{A, C}
{B}
{A, B, C, D }
{B, D}
{A, B, D}
{A, B}
{A, D}
{B, C, D}
{C, D}
{A, B, D}


Bảng 1.2: Ví dụ cơ sở dữ liệu

1.3. Các vấn đề về phát hiện luật kết hợp trong cơ sở dữ liệu
Các nghiên cứu đều tập trung vào phát hiện các luật kết hợp trong cơ sở dữ liệu giao
dịch và cơ sở dữ liệu quan hệ. Cơ sở dữ liệu giao dịch là cơ sở dữ liệu có chứa các
giao dịch mà mỗi giao dịch thể hiện trạng thái "có" hay "khơng" sự xuất hiện của các
thuộc tính. Chính vì thế, nó cịn được gọi là cơ sở dữ liệu nhị phân. Cơ sở dữ liệu
quan hệ, như đã biết, có rất nhiều thuộc tính như thuộc tính nhị phân, thuộc tính
phạm trù, thuộc tính định lượng (số),…
Đối với cơ sở dữ liệu giao dịch, để phát hiện các luật kết hợp trong đó, đã có rất
nhiều cơng trình được đăng trên các tạp chí, kỷ yếu hội thảo. Thuật tốn Apriori và
các cải tiến của nó [2][8] đã được đề xuất để thực hiện nhiệm vụ này. Một đặc điểm
của những thuật toán này là tốn khá nhiều chi phí cho việc sinh ra các tập mục ứng
cử. Để giải quyết vấn đề này, [15][16][32] đã đề xuất sử dụng cây mẫu thường xuyên
(FP-tree) để phát hiện các tập mục thường xuyên, tránh được việc phải sinh quá
nhiều tập mục ứng cử. Xoay quanh bài toán đối với cơ sở dữ liệu giao dịch, một số
bài báo cũng trình bày khía cạnh khác: luật kết hợp đa mức [19][22][23][24][25].
Đối với cơ sở dữ liệu quan hệ, vấn đề trở nên phức tạp hơn rất nhiều. Vì cơ sở dữ
liệu quan hệ chứa các thuộc tính định lượng, phạm trù,… nên nảy sinh cơng đoạn xử
lý các thuộc tính này trước khi sinh các tập mục thường xuyên. Các bài toán ở đây
gồm: phát hiện luật kết hợp định lượng và phạm trù [1], phát hiện luật kết hợp mờ và
luật kết hợp mờ có trọng số [5][6][13][14][28][29].
Nguyễn Hồng Phương

11/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Bản luận văn này trình bày các vấn đề trên theo cấu trúc sau:

Phát hiện các luật kết hợp trong cơ sở dữ liệu

Phát hiện các luật kết hợp
trong cơ sở dữ liệu giao dịch

Kiểu
Apriori

Sử dụng
FP-Tree

Luật đa
mức

Phát hiện các luật kết hợp
trong cơ sở dữ liệu quan hệ

Luật định
lượng

Luật mờ

Luật mờ
có trọng
số

Hình 1.3: Các vấn đề trình bày trong báo cáo

Sau đó là phần cài đặt thử nghiệm các thuật toán và kết luận.


Nguyễn Hồng Phương

12/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Chương 2: Luật kết hợp cơ bản
Chương này giới thiệu một số thuật giải phát hiện các luật kết hợp trong cơ sở dữ
liệu giao dịch. Cách làm ở đây chia ra thành hai nhiệm vụ nhỏ hơn:
- Tìm kiếm các tập mục với độ hỗ trợ lớn hơn hoặc bằng ngưỡng tối thiểu smin
- Xây dựng các luật kết hợp với độ tin cậy lớn hơn hoặc bằng ngưỡng tối thiểu cmin

2.1. Hai tính chất
2.1.1. Tính chất 1
Nếu một tập mục là nhỏ (khơng thường xun) thì tất cả các siêu tập (tập cha) của nó
cũng là nhỏ (khơng thường xun).
{1,2,3,4,5}
{1,2,3,5}
{1,2,5}

{1,2,4,5}

{1,3,5}
{1,5}

{1,3,4,5}

{1,4,5}
{2,5}


{2,3,5}

{2,3,4,5}
{2,4,5}

{3,5}
{5}

{3,4,5}

{4,5}
A

Hình 2.1: A nhỏ thì superset(A) cũng nhỏ

2.1.2. Tính chất 2
Nếu một tập mục là lớn (thường xuyên) thì các tập con của nó cũng lớn (thường
xun).
{1,2,3,4,5}
{1,2,3,5}
{1,2,5}

{1,2,4,5}

{1,3,5}
{1,5}

{1,3,4,5}


{1,4,5}
{2,5}

{2,3,5}
{3,5}

B
{2,3,4,5}
{2,4,5}

{3,4,5}

{4,5}

{5}
Hình 2.2: B lớn thì subset(B) cũng lớn

Nguyễn Hồng Phương

13/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

2.2. Phát hiện các tập mục thường xuyên
Có rất nhiều thuật giải đã được đề xuất để giải quyết bài toán này. Phần này sẽ giới
thiệu chi tiết một vài trong số các thuật giải.
2.2.1. Giải thuật Apriori
Giải thuật Apriori là giải thuật kinh điển để tìm các tập mục thường xuyên. Nội dung
giải thuật được thể hiện trong hình 2.3. Mặc dù có nhiều giải thuật cải tiến khác,

nhưng ở đây, tơi xin trình bày lại giải thuật này vì nó là nền tảng giúp chúng ta hiểu
hơn về công việc cần tiến hành.
Giả sử mỗi tập mục gồm có hai trường: một tập các mục và một bộ đếm cho biết số
lượng các giao dịch hỗ trợ tập mục. Trong bước duyệt đầu tiên của giải thuật, với
mỗi mục i của tập I , chúng ta đếm số giao dịch chứa nó. Nếu kết quả vượt smin thì
mỗi mục sẽ là một 1-tập mục thường xuyên. Tất cả các bước duyệt sau này đều bao
gồm 2 pha. Gọi bước duyệt hiện tại là k. Trong pha đầu tiên, chúng ta xây dựng một
tập Ck các k-tập mục ứng cử (candidate k-itemsets) từ tập Lk-1 của các (k-1)-tập mục
thường xuyên có được ở bước trước. Tập mục ứng cử được tính tốn nhờ hàm
AprioriGen được chỉ ra trong hình 2.4.
Trong pha thứ hai, chúng ta quét cơ sở dữ liệu D và kiểm tra mỗi giao dịch t xem có
chứa các tập mục ứng cử trong đó hay khơng. Nếu t có chứa tập mục ứng cử thì bộ
đếm của tập mục này sẽ được tăng thêm 1 đơn vị. Chúng ta có hàm Subset để thực
hiện điều này.
Đầu vào: Cơ sở dữ liệu các giao dịch D và smin
Đầu ra: Tập Answer chứa tất cả các tập mục thường xuyên của D
Giải thuật:
1) L1 = {large 1-itemsets};
2) for(k=2; Lk-1≠∅; k++) do begin
3)
Ck = AprioriGen(Lk-1); // New candidate
4)
forall transactions t∈D do begin
5)
Ct = Subset(Ck, t); // Candidates contained in t
6)
forall candidates c∈Ct do
7)
c.count++
8)

end
9)
Lk = {c∈Ck c.count ≥ smin}
10) end
11) Answer = ∪k Lk;
Hình 2.3: Giải thuật Apriori

Nguyễn Hồng Phương

14/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Hàm AprioriGen bao gồm 2 pha. Nó nhận đối số là tập các (k-1)-tập mục thường
xuyên Lk-1. Trong pha đầu tiên, gọi là pha kết nối, chúng ta kết nối Lk-1 với chính nó.
Chúng ta giả sử rằng các mục của một tập mục được sắp xếp theo thứ tự từ điển.
Đầu vào: Một tập Lk-1 chứa tất cả các (k-1)-tập mục thường xuyên
Đầu ra: Tập Ck ứng cử là một siêu tập chứa tất cả các k-tập mục thường xuyên
Giải thuật:
1) Function AprioriGen(Lk-1: tập (k-1)-tập mục thường xuyên):tập k-tập mục thường
xuyên
2)
// Pha kết nối
3)
insert into Ck
4)
select p.item1, p.item2,...,p.itemk-1, q.itemk-1
5)
from Lk-1 p, Lk-1 q

6)
where p.item1 = q.item1,..., p.itemk-2 = q.itemk-2, p.itemk-1 < q.itemk-1
7)
// Pha cắt tỉa
8)
forall itemsets c∈Ck do
9)
forall (k-1)-subsets s of c do
10)
if(s∉Lk-1) then delete c from Ck;
11) return Ck;
12) end;

Hình 2.4: Hàm AprioriGen sử dụng trong giải thuật Apriori

Trong pha cắt tỉa, chúng ta xóa tất cả các tập mục c∈Ck mà các (k-1)-tập con của c
khơng có mặt trong Lk-1.
2.2.2. Giải thuật AprioriTid
Giải thuật AprioriTid được chỉ ra trong hình 2.5 cũng sử dụng hàm AprioriGen (hình
2.4) để quyết định các tập mục ứng cử trước khi vòng lặp duyệt bắt đầu. Đặc điểm
thú vị của giải thuật này là cơ sở dữ liệu D không được sử dụng để tính tốn độ hỗ
trợ sau lần duyệt đầu tiên. Hơn nữa, tập C k được sử dụng cho mục đích này. Mỗi
phần tử của tập C k có dạng <TID, {Xk}>, trong đó Xk là k-tập mục lớn ứng cử hiện
diện trong giao dịch với định danh TID. Với k=1, C 1 tương ứng với cơ sở dữ liệu D,
mỗi mục i được thay thế bởi tập mục {i}. Với k>1, C k được sinh ra bởi thuật giải
(bước 10). Phần tử của C k tương ứng với giao dịch t là <t.TID, {c∈Ck | c có trong t}>.
Nếu một giao dịch không chứa bất kỳ k-tập mục ứng cử thì C k sẽ khơng có một phần
tử (dịng vào, entry) cho giao dịch này. Do đó, số phần tử trong C k có thể nhỏ hơn số
giao dịch trong cơ sở dữ liệu, đặc biệt với giá trị rất lớn của k. Hơn nữa, với giá trị k
Nguyễn Hồng Phương


15/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

lớn, mỗi phần tử có thể nhỏ hơn giao dịch tương ứng bởi vì bởi vì có rất ít ứng viên
tiềm năng có thể hiện diện trong giao dịch. Tuy nhiên, với giá trị k nhỏ, mỗi phần tử
có thể lớn hơn giao dịch tương ứng bởi vì một phần tử trong Ck bao gồm tất cả các ktập mục ứng cử hiện diện trong giao dịch.
Đầu vào: Cơ sở dữ liệu các giao dịch D và smin
Đầu ra: Tập Answer chứa tất cả các tập mục thường xuyên của D
Giải thuật:

1) L1 = {large 1-itemsets};
2) C 1 = database D
3) for(k=2; Lk-1≠∅; k++) do begin
4)
Ck = AprioriGen(Lk-1); // New candidate
5)
C k = ∅;
6)
forall entries t ∈ C k −1 do begin
7)
// determine candidate itemsets in Ck contained
// in the transaction with identifier t.TID
Ct = {c∈Ck | (c-c[k]) ∈t.set-of-itemsets ∧
(c-c[k-1]) ∈t.set-of-itemsets}
8)
forall candidates c ∈Ct do
9)

c.count++;
10)
if(Ct≠∅) then C k +=<t.TID, Ct>;
11) end
12) Lk = {c∈Ck c.count ≥ smin}
13) end
14) Answer = ∪k Lk;

Hình 2.5: Giải thuật AprioriTid
Ví dụ:

Quan sát cơ sở dữ liệu trên hình 2.6, giả thiết smin (minimum support, minsup) là 2
giao dịch. Gọi AprioriGen với đối số là L1 ở bước 4 sẽ sinh ra các tập mục ứng cử C2.
Từ bước 6 đến bước 10, chúng ta đếm độ hỗ trợ của các tập mục ứng cử trong C2
bằng cách lặp trên các phần tử trong C 1 và sinh ra C 2 . Hạng mục đầu tiên trong C 1 là
{{1},{3},{4}} tương ứng với giao dịch TID là 100. Tập Ct ở bước 7 tương ứng với
hạng mục t này là {{1 3}} bởi vì {1 3} là phần tử của C2 và cả ({1 3}-{1}) và ({1
3}-{3}) đều là phần tử của t.set-of-itemsets.
Gọi AprioriGen với đối số là L2 sẽ sinh ra C3. Duyệt qua dữ liệu C 2 và C3 sẽ có được
C 3 . Chú ý rằng khơng có hạng mục trong C 3 với TID là 100 và 400. Tập ứng cử {2 3
Nguyễn Hồng Phương

16/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

5} trong C3 trở thành lớn và là phần tử duy nhất của L3. Sử dụng L3 sinh ra C4 là một
tập rỗng, chúng ta kết thúc tại đây.
Cơ sở dữ liệu

TID Items
100 1 3 4
200 2 3 5
300 1 2 3 5
400 2 5

TID
100
200
300
400

L1
Itemset Support
{1}
2
{2}
3
{3}
3
{5}
3

TID
100
200
300
400

C1

Set-of-Itemsets
{{1}, {3}, {4}}
{{2}, {3}, {5}}
{{1}, {2}, {3}, {5}}
{{2}, {5}}

C2
Itemset Support
{1 2}
1
{1 3}
2
{1 5}
1
{2 3}
2
{2 5}
3
{3 5}
2

C2
Set-of-Itemsets
{{1 3}}
{{2 3}, {2 5}, {3 5}}
{{1 2}, {1 3}, {1 5}, {2 3},
{2 5}, {3 5}}
{{2 5}}

C3

Itemset Support
{2 3 5}
2

L2
Itemset Support
{1 3}
2
{2 3}
2
{2 5}
3
{3 5}
2

C3
TID Set-of-Itemsets
200 {{2 3 5}}
300 {{2 3 5}}

L3
Itemset Support
{2 3 5}
2
Hình 2.6: Ví dụ về AprioriTid

2.3. Phát hiện các luật kết hợp
Như đã trình bày ở đầu chương, để tìm kiếm các luật kết hợp, chúng ta phải trải qua
hai bước: tìm các tập mục thường xuyên và xây dựng luật kết hợp. Hiệu quả của bài


Nguyễn Hồng Phương

17/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

tốn phụ thuộc chủ yếu vào hiệu quả của cơng việc tìm kiếm các tập mục thường
xuyên.
Xét một k-tập mục thường xuyên và một độ tin cậy tối thiểu 0, tức là mọi luật đều
được chấp nhận là luật kết hợp. Tổng số luật là

∑

 k
  . Nếu có tập mục thường
i =1
 i
k −1

xuyên {A, B, C}, chúng ta có thể xây dựng được 6 luật {A}⇒{B, C}, {B}⇒{A, C},
{C}⇒{A, B}, {A, B}⇒{C}, {A, C }⇒{B}, {B, C}⇒{A}
2.3.1. Giải thuật đơn giản
Cho một k-tập mục thường xuyên f với k ≥ 2 và một tập con l, trong đó, ∅ ⊂ l ⊂ f,
một luật l⇒f\l là một luật kết hợp nếu s(f)/s(l) ≥ cmin . Nếu luật l⇒f\l khơng có độ tin
cậy tối thiểu thì luật l'⇒f\l' cũng khơng, trong đó ∅ ⊂ l' ⊂ l. Do đó, thay vì phải xét
tất cả các tập con của f để sinh ra các luật kết hợp, chúng ta có thể sử dụng phương
pháp đệ quy để sinh ra luật với một (k-1)-tập con l' của một k-tập mục l như là phần
đầu của luật khi và chỉ khi l⇒f\l có độ tin cậy tối thiểu. Thuật giải được chỉ ra trên
hình 2.7 và 2.8 dưới đây:

Đầu vào: Tập tất cả các tập mục thường xuyên có nhiều hơn một mục
F =  k ≥2 Fk = F \ F1
Đầu ra: Tất cả các luật kết hợp
Phương pháp:
1)
forall f k ∈ F do
2)
GenRules(fk, fk);
Hình 2.7: Một giải thuật đơn giản sinh các luật
Đầu vào: Hai tập mục thường xuyên fk và lm, và một ngưỡng độ tin cậy cmin
Đầu ra: Các luật kết hợp với nhiều nhất m-1 mục ở phần đầu luật (m>2)
Phương pháp:
1)
procedure GenRules(fk: k-tập mục thường xuyên, lm: m-tập mục thường xuyên)
2)
L ← {các (m-1)-tập mục lm-1|lm-1⊂ lm}
3)
forall lm-1∈L do begin
4)
c ← s(fk)/s(lm-1); // Độ chắc chắn của luật
5)
if c ≥ cmin then begin
6)
output luật lm-1⇒(fk\lm-1);
7)
if m-1 ≥ 1 then
8)
GenRules(fk, lm-1);
9)
end;

10)
end;
11)
end;
Hình 2.8: Thủ tục GenRules được sử dụng trong giải thuật trên

Nguyễn Hồng Phương

18/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

2.3.2. Một giải thuật nhanh hơn
Ý tưởng của phần trước có thể được viết lại như sau: Nếu luật l⇒f\l có độ tin cậy tối
thiểu, tất cả các luật l'⇒f\l', trong đó ∅ ⊂ l' ⊂ l cũng phải có độ tin cậy tối thiểu.
Thay vì sinh ra vế trái của luật theo kiểu từ trên xuống (top-down) từ các k-tập mục
xuống các 1-tập mục, chúng ta có thể sinh ra vế phải từ dưới lên (bottom up) bắt đầu
với các 1-tập mục và tiến tới các k-tập mục. Tương ứng với việc sinh ra các tập con
trong dòng 2 của hình 2.8, chúng ta có thể tạo các siêu tập sử dụng hàm AprioriGen
trong hình 2.4. Theo cách tiếp cận này, giải thuật được chỉ ra trong hình 2.9 và 2.10.
Đầu vào: Tập tất cả các tập mục thường xuyên có nhiều hơn một mục
F =  k ≥2 Fk = F \ F1
Đầu ra: Tất cả các luật kết hợp
Phương pháp:
1)
forall f k ∈ F do begin
2)
3)


R1 ← {phần vế phải của các luật bắt nguồn từ fk với một mục trong vế phải}
GenRules(fk, fk);
Hình 2.9: Một giải thuật nhanh hơn để sinh luật

Đầu vào: Một k-tập mục thường xuyên fk, một tập m-mục thân luật Rm, và một ngưỡng
độ tin cậy cmin
Đầu ra: Các luật kết hợp với ít nhất m+1 mục ở thân luật
Phương pháp:
1) procedure GenRules(fk: k-tập mục thường xuyên, Rm: tập các thân luật m mục)
2)
if k>m+1 then begin
3)
Rm+1 ← AprioriGen(Rm);
4)
forall rm+1 ∈Rm+1 do begin
5)
c ← s(fk)/s(fk/rm+1);
6)
if c ≥ cmin then
7)
output luật (fk\rm) ⇒ rm+1;
8)
else
9)
Rm+1 ← Rm+1 \ rm+1;
10)
end;
11)
GenRules(fk, Rm+1);
12)

end;
13)end;
Hình 2.10: Thủ tục GenRules được sử dụng trong giải thuật nhanh

Giải thuật này hiệu quả hơn giải thuật trên. Quan sát ví dụ: cho tập mục thường
xuyên {A, B, C, D, E}. Giả sử rằng các luật {A, C, D, E}⇒{B} và {A, B, C,

Nguyễn Hồng Phương

19/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

E}⇒{D} là các luật kết hợp duy nhất có một mục phía bên phải. Sử dụng giải thuật
đơn giản, gọi đệ quy thủ tục GenRules({A, B, C, D, E},{A, C, D, E}) sẽ sinh ra các
vế phải của luật {B, A},{B, C},{B, D} và {B, E}. Ví dụ, luật với vế phải {B, E}
khơng được giữ vì {E}⊂{B, E} và luật {A, B, C, D}⇒{E} khơng có độ tin cậy tối
thiểu. Tương tự với GenRules({A, B, C, D, E},{A, B, C, E}). Luật kết hợp duy nhất
với 2 mục ở vế phải là {A, C, E}⇒{B, D}, là luật duy nhất được kiểm tra bởi giải
thuật nhanh.
Cả hai giải thuật đều có mặt trái là chúng có thể sinh ra các luật kết hợp trùng nhau.
Ví dụ, gọi GenRules({A, B, C, D, E},{B}) và GenRules({A, B, C, D, E},{D}). Cả
hai đều sinh ra {B, D} như là vế phải 2 mục. Do đó, cả hai đều sinh ra cùng luật {A,
C, E}⇒{B, D}.
Để tránh hiện tượng này, các luật nên được chèn vào một tập hợp. Vì các phần tử của
tập hợp là duy nhất nên tập hợp có thể được sử dụng như là một nguồn dữ liệu cho
việc sản sinh các luật kết hợp.

Nguyễn Hồng Phương


20/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

Chương 3: Sử dụng FP-tree phát hiện các tập mục
thường xuyên
Chương này giới thiệu một cấu trúc dữ liệu được dùng để tìm ra các tập mục thường
xuyên một cách hiệu quả hơn so với thuật toán Apriori. Phần đầu của chương phân
tích về những hạn chế của giải thuật Apriori và các cải tiến của giải thuật này. Các
phần tiếp theo giới thiệu cây FP và cách xây dựng cũng như khai thác cây FP để đưa
ra các tập mục thường xuyên.

3.1. Giới thiệu
Như đã trình bày ở phần trước, việc phát hiện các tập mục thường xuyên đóng một
vai trò quan trọng trong phát hiện luật kết hợp. Phần lớn các kết quả nghiên cứu như
[2][8][9] đều chọn cách tiếp cận kiểu Apriori: nếu các tập mục chiều dài k mà khơng
phải là thường xun thì các siêu tập của nó với chiều dài (k+1) cũng khơng thường
xun. Bản chất là lặp đi lặp lại việc sinh ra các tập mục ứng cử chiều dài k từ các
tập mục thường xuyên chiều dài (k-1) với k > 1 và sau đó kiểm tra xem các tập mục
ứng cử có đủ tần suất xuất hiện trong cơ sở dữ liệu hay không. Một số cải tiến cũng
đã được đề xuất để làm giảm số tập mục ứng cử. Tuy nhiên, với một số lượng lớn
các giao dịch có nhiều thuộc tính, các thuật giải tựa Apriori gặp phải một số vấn đề
sau:
Chi phí cho việc kiểm sốt một số lượng lớn các tập ứng cử. Ví dụ, nếu có 104
1-tập mục thường xuyên, thuật giải Apriori sẽ sinh ra hơn 107 tập ứng cử kích thước
2, sau đó phải thực hiện tính cộng và kiểm tra tần suất xuất hiện của chúng. Hơn nữa,
để phát hiện tập mục kích thước 100 như là {I1, I2,…, I100}, nó phải sinh ra khoảng
2100 ≈ 1030 ứng cử viên. Như vậy, chi phí sẽ rất tốn kém cho dù các kỹ thuật cài đặt

có được cải tiến.
Phải lặp đi lặp lại việc duyệt cơ sở dữ liệu để kiểm tra một lượng lớn các tập
ứng cử bằng cách so khớp.
Vấn đề thắt cổ chai của thuật toán Apriori nằm ở chỗ sinh các tập ứng cử và
kiểm tra nó. Nếu chúng ta có thể tránh được việc sinh ra quá nhiều tập ứng cử thì
hiệu quả có thể được cải thiện đáng kể. Han, Pei và Yin, trong [15] đã đề xuất sử
dụng cấu trúc cây trên ba khía cạnh sau:
Thứ nhất, cấu trúc dữ liệu nén truyền thống được gọi là cây mẫu thường
xuyên (FP-tree, frequent pattern tree) được xây dựng. Nó là sự mở rộng của cây tiền
tố để lưu trữ các thông tin cốt yếu về các mẫu thường xuyên. Chỉ những mục thường

Nguyễn Hồng Phương

21/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu

xuyên chiều dài 1 mới có các nút trong cây, và nút của cây được sắp xếp theo ý
tưởng là các nút nào xuất hiện thường xuyên hơn sẽ có cơ hội hơn để chia sẻ nút đó.
Thứ hai, phương pháp khai phá tăng trưởng phân đoạn mẫu dựa trên FP-tree
được phát triển bắt đầu từ mẫu thường xuyên kích thước 1( như một mẫu hậu tố khởi
đầu), chỉ kiểm tra cơ sở mẫu điều kiện ( một cơ sở dữ liệu con chứa tập các mục
thường xuyên cùng xuất hiện với mẫu hậu tố), xây dựng FP-tree và thực hiện khai
phá đệ quy với cây. Tăng trưởng mẫu đạt được thông qua thao tác kết nối mẫu hậu tố
với mẫu hậu tố mới được sinh ra từ cây FP điều kiện. Thao tác chính ở đây là đếm bộ
tích lũy và điều chỉnh bộ đếm tiền tố, do đó sẽ ít tốn kém hơn so với việc sinh các
ứng cử viên và so khớp mẫu được thực hiện trong thuật tốn kiểu Apriori.
Thứ ba, kỹ thuật tìm kiếm thực hiện dựa trên phân đoạn, chia và trị chứ không
phải là kết hợp sinh các tập mục thường xuyên từ dưới lên theo kiểu Apriori. Do đó

làm giảm kích thước cơ sở mẫu điều kiện được sinh ra ở mức tiếp sau của việc tìm
kiếm.

3.2. Thiết kế và xây dựng cây mẫu thường xuyên
Cho I = {a1, a2, …, am} là một tập các mục, DB = <T1, T2, …, Tn> là một cơ sở dữ
liệu giao dịch, trong đó Ti (với i = 1, 2, …, n) là một giao dịch chứa tập các mục
trong I. Độ hỗ trợ hay tần suất xuất hiện của mẫu A (tập các mục) là số giao dịch
chứa A trong DB. Chú ý rằng, độ hỗ trợ ở đây là con số tuyệt đối chứ không phải tỉ
lệ tương đối trong cơ sở dữ liệu như các thuật toán truyền thống. A được gọi là mẫu
thường xuyên nếu độ hỗ trợ của nó không nhỏ hơn độ hỗ trợ tối thiểu.
Cho cơ sở dữ liệu giao dịch DB và độ hỗ trợ tối thiểu minsup, bài tốn đi tìm tập đầy
đủ các mẫu thường xuyên được gọi là bài toán khai phá mẫu thường xuyên.
3.2.1. Cây mẫu thường xuyên
Để thiết kế một cấu trúc dữ liệu nén cho bài toán khai phá mẫu thường xuyên, chúng
ta quan sát một ví dụ.
Ví dụ 1: DB là cơ sở dữ liệu giao dịch cho trong bảng 3.1 và minsup = 3.

Nguyễn Hồng Phương

22/78


Phát hiện các luật kết hợp trong cơ sở dữ liệu
TID
Items
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

Bảng 3.1: Một cơ sở dữ liệu giao dịch

Vì các mục thường xun đóng một vai trị quan trọng trong khai phá mẫu thường
xuyên nên cần phải duyệt DB một lần để nhận diện tập các mục thường xuyên.
Nếu chúng ta lưu trữ tập các mục thường xuyên của mỗi giao dịch trong cấu trúc nén
nào đó thì có thể tránh được phải quét nhiều lần DB.
Nếu có nhiều giao dịch chia sẻ một tập mục thường xuyên giống nhau thì chúng có
thể được hịa nhập lại làm một với số lần xuất hiện được lưu trong biến count. Dễ
dàng kiểm tra hai tập có giống nhau hay khơng nếu các mục thường xuyên trong tất
cả các giao dịch được sắp xếp thông qua một thứ tự định trước.
Nếu hai giao dịch cùng có chung phần tiền tố, thơng qua một thứ tự sắp xếp các mục
thường xuyên, các phần chia sẻ có thể được hịa nhập bằng cách sử dụng một cấu
trúc tiền tố miễn là biến count được đăng ký hoàn chỉnh. Nếu các mục thường xuyên
được sắp xếp theo thứ tự giảm dần của tần suất thì sẽ có nhiều hơn các chuỗi tiền tố
được chia sẻ.
Dựa trên những phân tích trên, chúng ta có thể xây dựng cây FP như sau:
Bước 1: Duyệt cơ sở dữ liệu lần đầu, tìm tất cả các mục thường xuyên (các mẫu chỉ
có 1 mục) và sắp xếp chúng vào một danh sách L theo thứ tự giảm dần của tần suất.
Ví dụ, với cơ sở dữ liệu trên, ta có danh sách L = {f:4, c:4, a:3, b:3, m:3, p:3}, số
đằng sau dấu hai chấm ":" là độ hỗ trợ của mục tương ứng.
Bước 2: Duyệt cơ sở dữ liệu lần thứ hai, với mỗi giao dịch, sắp xếp các mục thường

xuyên của nó theo thứ tự trong L và đưa nó vào cây FP.
Minh họa việc xây dựng cây FP đối với cơ sở dữ liệu trên:
Bước 1: Duyệt DB lần đầu để sinh ra danh sách L

Nguyễn Hồng Phương

23/78