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

Lê Thị Thanh Hải

VẤN ĐỀ VỀ LUẬT KẾT HỢP MỜ
VÀ CÁC TỐN TỬ CĨ NGƢỠNG
TRONG KHAI PHÁ DỮ LIỆU

Ngành: Cơng nghệ thơng tin
Mã ngành: 1.01.10

TĨM TẮT LUẬN VĂN THẠC SỸ

NGƯỜI HƯỚNG DẪN KHOA HỌC:

PGS.TSKH. Bùi Công Cƣờng

Hà Nội - 2007


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

MỤC LỤC
MỤC LỤC ................................................................................................................. 2
DANH MỤC BẢNG BIỂU, HÌNH VẼ, CƠNG THỨC & KÍ HIỆU VIẾT TẮT ........ 4
LỜI CẢM ƠN ........................................................................................................... 6
MỞ ĐẦU ................................................................................................................... 7
1.

CHƯƠNG 1 - LUẬT KẾT HỢP ....................................................................... 9

1.1. Ý NGHĨA THỰC TIỄN CỦA LUẬT KẾT HỢP ............................................ 9
1.2. MƠ HÌNH HÌNH THỨC CỦA VẤN ĐỀ PHÁT HIỆN LUẬT ....................... 9
1.2.1. Các định nghĩa ....................................................................................... 9
1.2.1.1.
Thuộc tính và CSDL ....................................................................... 9
1.2.1.2.
Độ hỗ trợ của một tập thuộc tính ................................................... 10
1.2.1.3.
Tập phổ biến (Frequent Itemset):................................................... 10
1.2.1.4.
Độ hỗ trợ của luật r = X  Y ........................................................ 10
1.2.1.5.
Độ tin cậy của luật: r = X  Y...................................................... 10
1.2.1.6.
Luật kết hợp mạnh: ....................................................................... 11
1.2.2. Bài toán luật kết hợp ............................................................................ 11
1.2.3. Một số tính chất của tập phổ biến và luật kết hợp ................................. 13
1.3. THUẬT TỐN TÌM LUẬT KẾT HỢP........................................................ 14
1.3.1. Thuật toán Apriori nhị phân ................................................................. 14
1.3.1.1.
Giới thiệu ...................................................................................... 14
1.3.1.2.
Các bước thực hiện ....................................................................... 15
1.3.1.3.
Giải thích: ..................................................................................... 15
1.3.2. Thuật toán AprioriTid .......................................................................... 17
1.3.2.1.

Giới thiệu thuật toán...................................................................... 17
1.3.2.2.
Các bước thực hiện ....................................................................... 17
1.3.2.3.
Giải thích ...................................................................................... 18
1.3.3. Sinh ra các luật kết hợp mạnh từ tập phổ biến ...................................... 20
1.3.3.1.
Thuật toán ..................................................................................... 20
1.3.3.2.
Thuật toán nhanh hơn:................................................................... 21
1.3.4. Thuật toán FP-Growth ......................................................................... 22
1.3.4.1.
Ví dụ 1.2: ...................................................................................... 23
1.3.4.2.
Thuật tốn: .................................................................................... 26
2. CHƯƠNG 2 - LUẬT KẾT HỢP MỜ ............................................................. 29
2.1. Ý NGHĨA VỀ LUẬT KẾT HỢP MỜ ........................................................... 29
2.2. TẬP MỜ (FUZZY SET) VÀ MỘT SỐ KHÁI NIỆM [1] .............................. 30
2.2.1. Tập mờ: ................................................................................................ 30
2.2.1.1.
Định nghĩa tập mờ:........................................................................ 31

2


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

2.2.1.2.

Các phép toán trên tập mờ: ............................................................ 31
2.2.2. Số mờ và một số dạng phổ biến ............................................................ 32
2.2.2.1.
Định nghĩa tập mức: ...................................................................... 32
2.2.2.2.
Định nghĩa số mờ: ......................................................................... 32
2.2.2.3.
Các dạng phổ biến của số mờ: ....................................................... 32
2.2.3. Các phép toán trong logic mờ (toán tử mờ) .......................................... 33
2.2.3.1.
Phép phủ định (negation) .............................................................. 33
2.2.3.2.
Phép hội (conjunction): ................................................................. 33
2.2.3.3.
Phép tuyển (disconjunction): ......................................................... 34
2.3. LUẬT KẾT HỢP MỜ .................................................................................. 34
2.3.1. Cơ sở dữ liệu và thuộc tính: ................................................................. 34
2.3.2. Độ đo của luật ...................................................................................... 35
2.3.2.1.
Độ ủng hộ của bản ghi cho mệnh đề .............................................. 35
2.3.2.2.
Độ hỗ trợ của mệnh đề .................................................................. 36
2.3.2.3.
Tập phổ biến ................................................................................. 36
2.3.2.4.
Độ hỗ trợ của một luật mờ:............................................................ 36
2.3.2.5.
Độ tin cậy của một luật mờ ........................................................... 36
2.3.3. Bài toán................................................................................................ 37
2.3.4. Ưu điểm của việc áp dụng tập mờ để rời rạc hoá dữ liệu...................... 37

2.4. LUẬT KẾT HỢP MỜ VỚI CÁC TỐN TỬ CĨ NGƯỠNG ........................ 38
2.4.1. Tốn tử có ngưỡng ............................................................................... 38
2.4.1.1.
Định nghĩa: t-chuẩn có ngưỡng ..................................................... 38
2.4.1.2.
Định nghĩa: t-đối chuẩn có ngưỡng ............................................... 38
2.4.2. Bài tốn................................................................................................ 39
2.4.3. Thuật toán [9] ...................................................................................... 39
2.4.3.1.
Các ký hiệu sử dụng trong thuật tốn: ........................................... 39
2.4.3.2.
Thuật tốn: .................................................................................... 40
2.4.3.3.
Các chương trình con sử dụng trong thuật tốn: ............................ 40
2.4.3.4.
Ví dụ minh họa thuật tốn (Ví dụ 2.2) : ......................................... 41
2.4.4. Chuyển luật kết hợp mờ về luật có thuộc tính số ................................... 45
2.4.5. Luật kết hợp mờ với thuộc tính được đánh trọng số .............................. 45
2.4.6. Luật thật sự có ích ................................................................................ 46
2.4.6.1.
Phương pháp loại bỏ luật thừa ....................................................... 46
2.4.6.2.
Phương pháp tìm luật đơn giản ...................................................... 46
3. CHƯƠNG 3 - CÀI ĐẶT THỬ NGHIỆM ....................................................... 47
KẾT LUẬN ............................................................................................................. 51
TÀI LIỆU THAM KHẢO ...................................................................................... 53
PHỤ LỤC ................................................................................................................ 55

3



Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

DANH MỤC
BẢNG BIỂU, HÌNH VẼ, CƠNG THỨC & KÍ HIỆU VIẾT TẮT
DANH MỤC BẢNG BIỂU
Bảng 1.1 CSDL giao dịch (Ví dụ 1.1) ....................................................................... 12
Bảng 1.2 Độ hỗ trợ của các thuộc tính (Ví dụ 1.1) .................................................... 12
Bảng 1.3 Danh sách các tập mục phổ biến (Ví dụ 1.1) .............................................. 12
Bảng 1.4 Độ tin cậy của các luật sinh từ tập phổ biến (Ví dụ 1.1) ............................. 12
Bảng 1.5 Thực hiện các bước thuật toán Apriori ....................................................... 19
Bảng 1.6 Cơ sở dữ liệu giao dịch (Ví dụ 1.2) ............................................................ 23
Bảng 1.7 Độ hỗ trợ của tất cả các thuộc tính (Ví dụ 1.2) ........................................... 24
Bảng 1.8 Các tập phổ biến có 1 thuộc tính (Ví dụ 1.2) .............................................. 24
Bảng 1.9 Cơ sở dữ liệu lần thứ 2 (Ví dụ 1.2) ............................................................. 25
Bảng 2.1 Cơ sở dữ liệu giao tác (Ví dụ 2.1) .............................................................. 29
Bảng 2.2 Cơ sở dữ liệu sau khi rời rạc hóa thuộc tính chỉ mục (Ví dụ 2.1) ............... 30
Bảng 2.3 Cơ sở dữ liệu giao tác (Ví dụ 2.2) .............................................................. 41
Bảng 2.4 Cơ sở dữ liệu mờ (Ví dụ 2.2) ..................................................................... 43
Bảng 2.5 Độ hỗ trợ của tập có 1 thuộc tính (Ví dụ 2.2) ............................................. 44
Bảng 2.6 Độ hỗ trợ của tập có 2 thuộc tính (Ví dụ 2.2) ............................................. 44
Bảng 2.7 Luật được sinh ra (Ví dụ 2.2) ..................................................................... 45
DANH MỤC HÌNH VẼ
Hình 1.1 Cây CSDL khi duyệt lại (Ví dụ 1.2) ........................................................... 25
Hình 1.2 Cây CSDL kết hợp với bảng thuộc tính (Ví dụ 1.2) ................................... 26
Hình 2.1 Tập mờ ....................................................................................................... 31
Hình 2.2 Số mờ ......................................................................................................... 32
Hình 2.3 Số mờ dạng tam giác .................................................................................. 32

Hình 2.4 Số mờ dạng hình thang ............................................................................... 32
Hình 2.5 Số mờ dạng úp chng ............................................................................... 32
Hình 2.6 Đồ thị hàm thuộc của các tập mờ của thuộc tính Tuổi ................................ 42
Hình 2.7 Đồ thị hàm thuộc của các tập mờ của thuộc tính TGDSD ........................... 42
Hình 2.8 Đồ thị hàm thuộc của các tập mờ của thuộc tính TGSDHN ........................ 42
Hình 3.2 Giao diện xây dựng các thuộc tính mờ từ thuộc tính gốc ban đầu ............... 49
4


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Hình 3.3 Giao diện Cơ sở dữ liệu mờ ........................................................................ 50
Hình 3.4 Giao diện kết quả sinh các luật tin cậy ........................................................ 50
DANH MỤC CÔNG THỨC
<1.1> Độ hỗ trợ của tập thuộc tính............................................................................ 10
<1.2> Độ hỗ trợ của luật ........................................................................................... 10
<1.3> Độ tin cậy của luật .......................................................................................... 11
<2.1> Số mờ dạng tam giác M(a,b,c) ........................................................................ 32
<2.2> Số mờ dạng hình thang M(a,b,c,d) .................................................................. 32
<2.3> Số mờ dạng úp chuông ................................................................................... 32
<2.4> Độ ủng hộ của bản ghi cho mệnh đề ............................................................... 35
<2.5> Độ hỗ trợ của mệnh đề .................................................................................... 36
<2.6> Độ hỗ trợ của luật mờ ..................................................................................... 36
<2.7> Độ tin cậy của luật mờ .................................................................................... 36
<2.8> Tốn tử t-chuẩn có ngưỡng ............................................................................ 38
<2.9> Tốn tử t-đối chuẩn có ngưỡng ....................................................................... 38
KÝ HIỆU VIẾT TẮT
-


CSDL - Database: cơ sở dữ liệu

-

fminconf - fuzzy minimum confidence: độ tin cậy tối thiểu mờ

-

fminsupp - fuzzy minimum support: độ hỗ trợ tối thiểu mờ

-

minconf - minimum confidence: độ tin cậy tối thiểu

-

minsupp - minimum support: độ hỗ trợ tối thiểu

-

t-conorm: t-đối chuẩn

-

TID - Transaction Identification : định danh thuộc tính

-

t-norm: t-chuẩn


5


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

MỞ ĐẦU
Ngày nay với sự bùng nổ của khoa học cơng nghệ, của kỹ thuật số đã cho phép
số hóa thơng tin một cách dễ dàng. Chính vì vậy, với lượng dữ liệu khổng lồ như công
văn giấy tờ, chứng từ, tài liệu, thông tin khách hàng, số liệu kinh doanh,…việc đưa ra
cơng cụ để phân tích và xử lý thông tin đã trở thành một vấn đề thiết yếu. Ví dụ đối
với ngành kinh doanh, các vấn đề về quảng cáo mặt hàng như thế nào? nên sắp đặt bố
trí, nhập hàng ra sao? thường xuyên được đặt ra. Và vì thế, khai phá dữ liệu đã trở
thành một 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 để nhằm thực hiện các yêu cầu đó của xã hội.
Để có thể chọn lọc được những thơng tin có ý nghĩa, nhiều bài tốn đã được
đưa ra và một trong số đó là Khai phá luật kết hợp. Khai phá luật kết hợp lần đầu tiên
được đưa ra vào năm 1993 do Rakesh Agrawal, Tomasz Imielinsky và Arun Swami
giới thiệu. Sau đó, năm 1996 được Rakesh Agrawal, Heikki Mannila, Ramakrishnan
Srikant, Hannu Toivonen và A. Inkeri Verkamo tiếp tục phát triển. Trong những năm
gần đây, người ta tập trung vào cải tiến, phát triển thuật tốn hiệu quả hơn từ các thuật
tốn đã có và xây dựng các thuật toán mới nhằm phát hiện các luật kết hợp có ý nghĩa.
Các thơng tin về dữ liệu trên thực tế không chỉ tồn tại ở dạng nhị phân (có hoặc
khơng) mà cịn định lượng. Chính vì vậy, các khái niệm của tập mờ đã được kết hợp
với khai phá luật kết hợp để trở thành một hướng nghiên cứu mới. Việc kết hợp các tập
mờ thông qua các toán tử (t-chuẩn, t-đối chuẩn) với ngưỡng là sự mở rộng hơn để giải
quyết bài toán khai phá luật kết hợp.
Do đây là một lĩnh vực nghiên cứu đang được quan tâm và có nhiều triển vọng

nên tơi đã chọn “Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá
dữ liệu” làm đề tài cho luận văn của mình. Luận văn được xây dựng trên nền của một
số nghiên cứu về lĩnh vực này trong những năm gần đây.
Luận văn được tổ chức thành 4 chương như sau:
Chương 1: Luật kết hợp. Trong chương này tơi đã trình bày những nét khái quát
nhất về khai phá dữ liệu bằng luật kết hợp thông qua việc đưa ra các khái niệm, định
nghĩa và bài tốn tìm luật kết hợp. Những thuật tốn điển hình của luật kết hợp như
thuật tốn Apriori và một vài thuật toán khác cũng được đề cập để giải quyết bài toán.
Chương 2: Luật kết hợp mờ với toán tử có ngưỡng. Ở phần đầu của chương tơi
trình bày các khái niệm liên quan đến tập mờ để từ đó làm cơ sở đưa vào bài tốn khai
phá luật kết hợp. Với các bài tốn có thuộc tính số và hạng mục thì việc rời rạc hóa dữ
7


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

liệu có thể xảy ra một vài nhược điểm như vấn đề “điểm biên gãy”. Vì thế luật kết hợp
mờ là một giải pháp rất hiệu quả. Phần cuối chương là các khái niệm về các tốn tử có
ngưỡng và đưa ra bài toán xây dựng luật kết hợp mờ với các tốn tử có ngưỡng.
Chương 3: Cài đặt thử nghiệm: Là phần cài đặt thử nghiệm chương trình dùng
dữ liệu về việc sử dụng internet.
Kết luận: Phần này nêu lại những việc đã thực hiện và kết quả đạt được của
luận văn, vấn đề còn chưa được giải quyết thấu đáo và một số hướng nghiên cứu trong
tương lai.

8



Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

1.

CHƢƠNG 1 - LUẬT KẾT HỢP

Luật kết hợp là một lĩnh vực quan trọng trong khai phá dữ liệu và vì thế kỹ
thuật khai phá luật kết hợp ngày càng được quan tâm và phát triển mạnh trong những
năm trở lại đây, trở thành một hướng nghiên cứu lớn.
Trong chương này, chúng ta cùng tìm hiểu các khái niệm cơ sở và các thuật toán kinh
điển của luật kết hợp.
Ý NGHĨA THỰC TIỄN CỦA LUẬT KẾT HỢP

1.1.

Luật kết hợp là những luật có dạng: X  Y
Trong lĩnh vực bán hàng ta có thể có luật: “40% khách hàng mua cafe thì mua thêm
bánh quy, 3% khách hàng mua cả cafe và bánh quy”
Ở ví dụ này diễn tả mối quan hệ giữa cafe và bánh quy hay ta có luật X  Y tương
đương với cafe  bánh quy. Cafe là tiền đề của luật và bánh quy là kết quả của luật.
Các hệ số 40% và 3% là các độ đo của luật
- 40% là độ tin cậy của luật: trong những khách hàng mua cafe có 40% mua thêm
bánh quy
- 3% là độ hỗ trợ của luật: trong tất cả khách hàng mua ở cửa hàng có 3% mua cả
2 mặt hàng là cafe và bánh quy.
Các số này ta sẽ định nghĩa cụ thể ở các phần dưới
MƠ HÌNH HÌNH THỨC CỦA VẤN ĐỀ PHÁT HIỆN LUẬT


1.2.

1.2.1. Các định nghĩa
1.2.1.1.

Thuộc tính và CSDL

- I = {I1, I2, …,In} là tập tất cả các mục (Item)
hay được gọi là tập tất cả các thuộc tính (attributes)
mỗi một thuộc tính Ii với i = 1, n được gọi là 1 mục dữ liệu
- X = {Ix1, Ix2,…,Ixp}  I là 1 tập thuộc tính (Itemset)
- D = (T1, T2, …, Tm) là cơ sở dữ liệu trên I, là tập tất cả các tác vụ (transaction) hay
được gọi là tập các bản ghi. Mỗi bản ghi Tk với k = 1, m đều có định danh (TIDTransaction Identification) và nó là một tập các thuộc tính Tk  I với
k = 1, m Ta có Tk(Iv) xác định giá trị của thuộc tính Iv.
Ví dụ: nếu xét thuộc tính phân, Tk(Iv) = 1 nghĩa là khách hàng Tk chọn mua mặt hàng
9


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Iv, Tk(Iv) = 0 nếu khách hàng Tk không chọn mua hàng Iv).
- Một luật kết hợp có dạng X  Y
Trong đó:
+ X  I là tiền đề của luật
+ Y  I là hệ quả của luật,
+XY=
biểu thị mối quan hệ giữa tập thuộc tính X và tập thuộc tính Y. Vì vậy có thể nói
luật kết hợp biểu thị mối quan hệ giữa các tập con của I

Độ hỗ trợ và độ tin cậy là 2 thước đo của 1 luật kết hợp
1.2.1.2.

Độ hỗ trợ của một tập thuộc tính

Cho một tập thuộc tính X  I, cơ sở dữ liệu D
Độ hỗ trợ (support) của tập thuộc tính X trong cơ sở dữ liệu D (Ký hiệu supp(X)) là tỷ
lệ % giữa số bản ghi trong cơ sở dữ liệu D chứa tập thuộc tính X với tổng số các bản
ghi trong cơ sở dữ liệu D.
Supp( X ) 

1.2.1.3.

| {Tk  D \ X  Tk |
|D|

<1.1>

Tập phổ biến (Frequent Itemset):

Cho một tập thuộc tính X  I trong cơ sở dữ liệu D và ngưỡng hỗ trợ tối thiểu
minsupp  (0,1] (minsupp - Minimum Support) được xác định bởi người sử dụng.
Một tập thuộc tính X được gọi là tập phổ biến theo ngưỡng minsupp khi và chỉ khi độ
hỗ trợ của nó lớn hơn hoặc bằng ngưỡng minsupp
X  I là tập phổ biến  supp(X)  minsupp
Ký hiệu: FX(D, minsupp) là tập hợp các tập phổ biến theo ngưỡng minsupp
FX( D, minsupp) = {X  I \supp(X)  minsupp}
1.2.1.4.

Độ hỗ trợ của luật r = X  Y


Độ hỗ trợ của luật được tính bằng cơng thức: Supp (r) = supp(XY)
1.2.1.5.

<1.2>

Độ tin cậy của luật: r = X  Y

Độ tin cậy của luật r trong cơ sở dữ liệu D (Ký hiệu là conf(r)) là tỷ lệ % giữa số bản
ghi trong D chứa tập thuộc tính X thì cũng chứa tập thuộc tính Y. Về mặt xác suất độ
tin cậy của luật r là xác suất có điều kiện xảy ra Y với điều kiện đã xảy ra X

10


Lê Thị Thanh Hải

conf (r ) 







1.2.1.6.

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Tk  D \ X  Tk , Y  Tk 

Tk  D \ X  Tk 

Tk  D \ X  Y  Tk 
Tk  D \ X  Tk 

Tk  D \ X  Y  Tk 
D

<1.3>
D

Tk  D \ X  Tk 

supp( X  Y )
supp( X )

Luật kết hợp mạnh:

Luật r = X  Y được gọi là luật kết hợp mạnh theo ngưỡng độ hỗ trợ tối thiểu
minsupp  (0,1] và độ tin cậy tối thiểu minconf  (0,1] (Minimum Confidence) khi và
chỉ khi độ hỗ trợ của luật lớn hơn hoặc bằng độ hỗ trợ tối thiểu và độ tin cậy của luật
lớn hơn hoặc bằng độ tin cậy tối thiểu.
r = X  Y là luật kết hợp mạnh 

Supp (r)  minsupp
Conf (r)  minconf

1.2.2. Bài toán luật kết hợp
Người ta chỉ quan tâm đến luật kết hợp mạnh theo ngưỡng minsupp và minconf cho
trước.

Chính vì vậy bài tốn khai phá luật kết hợp thường chia làm 2 pha:
1- Tìm tất cả các tập phổ biến (FX) trong cơ sở dữ liệu, nghĩa là tìm tất cả các tập
thuộc tính X sao cho supp(X)  minsupp
2- Sinh ra các luật kết hợp mạnh từ các tập phổ biến tìm thấy ở pha 1Ví dụ 1.1: Bài toán khai phá luật kết hợp
Thực hiện bài toán khai phá luật kết hợp ở trên đối với đầu vào:
Cho CSDL D = {T1, T2, T3, T4, T5, T6} trên I = {A, B, C, D, E, F}
Các thuộc tính

TID
T1

A, C, E, F

T2

B, C, E

T3

A, B, D, E

11


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

T4


A, B, C, E

T5

D, F

T6

A, C, D

Bảng 1.1 CSDL giao dịch (Ví dụ 1.1)
Ta lần lượt tìm độ hỗ trợ của các tập thuộc tính. Bắt đầu từ tập có 1 thuộc tính rồi đến
2,3…. thuộc tính. Độ hỗ trợ của tập có 1 thuộc tính được tính trong bảng sau theo cách
Thuộc tính A có mặt trong 4 bản ghi (T1, T3, T4, T6) của D nên supp (A) = 4/6 = 67,7%
Thuộc tính

Số bản ghi

Độ hỗ trợ supp(X)

A

4

67,7%

B

3


50,0%

C

4

67,7%

D

3

50%

E

4

67,7%

F

2

33,3%

Bảng 1.2 Độ hỗ trợ của các thuộc tính (Ví dụ 1.1)
Nếu ta chọn độ hỗ trợ tối thiểu minsupp = 50% thì với cách tính tương tự trong bảng 1
ta có danh sách các tập phổ biến
Số thuộc tính


Danh sách các tập phổ biến

1

{A}, {B}, {C}, {D}, {E}

2

{AC}, {AE}, {BE}, {CE}

Bảng 1.3 Danh sách các tập mục phổ biến (Ví dụ 1.1)
Từ danh sách tập phổ biến đó các luật kết hợp được đưa ra trong bảng sau:
Luật kết hợp

Độ tin cậy

A→C

75%

A→E

75%

B→E

100 %

C→E


75%

Bảng 1.4 Độ tin cậy của các luật sinh từ tập phổ biến (Ví dụ 1.1)
Nếu ta chọn độ tin cậy tối thiểu minconf = 80% thì chỉ có luật B → E là luật kết hợp

12


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

mạnh.
1.2.3. Một số tính chất của tập phổ biến và luật kết hợp
Với tập phổ biến ta có 3 tính chất sau:
Tính chất 1 (độ hỗ trợ của tập con):
Nếu A  B với A, B là các tập thuộc tính thì supp (A) ≥ supp (B)
Điều này là rõ ràng vì tất cả các bản ghi trong D chứa B thì cũng chứa A.
Tính chất 2: Một tập chứa một tập khơng phổ biến thì cũng là tập khơng phổ biến
Nếu tập A không đủ độ hỗ trợ cực tiểu tức là supp(A) < minsupp thì tập B 
A cũng khơng phổ biến vì supp (B) ≤ supp (A) < minsupp (áp dụng tính chất
1)
Tính chất 3: Các tập con của tập phổ biến cũng là tập phổ biến
Nếu tập B là tập phổ biến trong D, tức là supp (B) ≥ minsupp, mọi tập con A
của B cũng là phổ biến trong D, bởi vì supp (A) ≥ supp(B) ≥ minsupp theo
tính chất 1.
Với luật kết hợp ta có 4 tính chất sau:
Tính chất 4. Khơng hợp các luật kết hợp
Nếu có X  Z và Y  Z trong D thì khơng nhất thiết X  Y  Z là đúng.

Xét trường hợp X  Y =  và các tác vụ trong D hỗ trợ Z nếu và chỉ nếu
chúng hỗ trợ hoặc X hoặc Y, khi đó luật X  Y  Z có độ tin cậy 0%.
Tương tự: X  Y  X  Z thì khơng thể suy ra X  Y  Z
Tính chất 5: Khơng tách luật
Nếu X  Y  Z thì X  Z và Y  Z chưa chắc xảy ra
Tính chất 6: Các luật kết hợp khơng có tính bắc cầu
Nếu X  Y và Y  Z, khơng thể suy ra X  Z
Tính chất 7:
Nếu luật A  (L-A) không thỏa mãn độ tin cậy cực tiểu thì với các tập mục B
 A  L, luật B  (L-B) cũng khơng thỏa mãn,
Vì supp(B) ≥ supp(A) (theo tính chất 1) và định nghĩa độ tin cậy, chúng ta
nhận được

13


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

conf(B  (L  B)) 

supp(L) supp(L)

 minconf
supp(B) supp(A)

Tương tự
Nếu có luật ((L-C)  D) thì ta cũng có luật (L-D)  D với D  C và D  
1.3.


THUẬT TỐN TÌM LUẬT KẾT HỢP

Phần này sẽ trình bày một số thuật tốn kinh điển để tìm luật kết hợp như thuật toán
Apriori [4] áp dụng đối với cơ sở dữ liệu nhị phân và một số thuật toán cải tiến của
Apriori. Các thuật toán này đều thực hiện 2 pha của bài tốn luật kết hợp trình bày ở
mục 1.2.2
1.3.1. Thuật toán Apriori nhị phân
1.3.1.1.

Giới thiệu

Thuật toán Apriori là thuật toán nhằm phát hiện các tập phổ biến bằng nhiều lần duyệt
dữ liệu. Trong lần duyệt đầu tiên chúng ta tính độ hỗ trợ của các tập thuộc tính riêng lẻ
và xác định nó có là tập phổ biến hay không bằng cách so sánh độ hỗ trợ của nó với độ
hỗ trợ cực tiểu (minsupp). Ở những lần duyệt sau, chúng ta bắt đầu từ 1 tập phổ biến
hạt giống của các tập phổ biến đã tìm được ở lần duyệt trước. Sử dụng tập phổ biến
này để sinh ra các tập tiềm năng mới gọi là tập ứng cử và tính độ hỗ trợ của tập ứng cử
đó trong mỗi lần duyệt dữ liệu. Cuối mỗi lần duyệt chúng ta xác định được tập nào là
tập phổ biến để làm hạt giống cho lần duyệt tiếp theo. Q trình này được thực hiện
cho đến khi khơng tìm thấy tập phổ biến nào mới trong các tập ứng cử.
Thuật toán này sinh các tập ứng cử để tính trong mỗi lần duyệt bằng cách chỉ sử dụng
từ các tập phổ biến ở lần duyệt trước mà không quan tâm tới các bản ghi trong cơ sở
dữ liệu. Cở sở của vấn đề này là áp dụng Tính chất 3 ở trên “Các tập con của tập phổ
biến cũng là tập phổ biến”. Do đó, các tập ứng cử có k thuộc tính có thể được sinh ra
bằng cách kết hợp từ tập phổ biến có k-1 thuộc tính và xóa các tập ứng cử nếu nó có
chứa bất kỳ một tập con nào không phải là tập phổ biến. Cách này làm giảm đáng kể
các tập ứng cử
Ký hiệu: Giả sử các thuộc tính trong mỗi bản ghi được lưu theo trật tự alphabet. Gọi số
các thuộc tính trong một tập thuộc tính là kích thước của nó và tập có kích thước k là

tập có k thuộc tính. Các thuộc tính trong mỗi tập thuộc tính đó cũng được lưu theo trật
tự alphabet.
Cụ thể:
Lk: tập các tập phổ biến có kích thước k (với độ hỗ trợ cực tiểu minsupp nào đó). Mỗi
phần tử của tập này có 2 trường là tập thuộc tính và độ hỗ trợ
14


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Ck: Tập các tập ứng cử có kích thước k. Mỗi phần tử của tập này có 2 trường là thuộc
tính và độ hỗ trợ
C k : Tập các tập ứng cử có kích thước k là định danh của các bản ghi kết hợp với ứng

cử
1.3.1.2. Các bước thực hiện
B1: L1 = {các tập phổ biến có 1 thuộc tính};
B2: For (k = 2; Lk-1  ; k++) do begin
// ứng cử mới

B3:

Ck = apriori_gen(Lk-1);

B4:
B5:

For mỗi bản ghi t  D do begin

Ct = subset(Ck, t);
// Các ứng cử mà chứa t
For mỗi ứng cử c  Ct

B6:
B7:
B8:

// tăng cho ứng cử c 1 đơn vị

c.count++;
end

B9: Lk = {c  Ck\ c.count  minsupp}
B10: end
B11: Return L =

L

k

k

1.3.1.3.

Giải thích:

Trong thuật toán này bước đầu tiên là đếm số lần có mặt của từng thuộc tính
(tập có 1 thuộc tính) để tìm xem tập nào là tập phổ biến. Từ đó xác định được tập L1.
Tiếp theo ở bước 2 ta thực hiện vịng lặp để tính Lk từ Lk-1 bao gồm 2 giai đoạn. Giai

đoạn 1 thực hiện ở bước 3 tìm các ứng cử Ck từ các tập phổ biến k-1 thuộc tính (Lk-1) ở
vịng trước. Ở đây ta sử dụng hàm apriori_gen với đối số là Lk-1 (Tập tất cả các tập phổ
biến có kích thước k-1) và kết quả là tập k thuộc tính. Hàm này thực hiện như sau:
-

Kết nối: Lk-1 với Lk-1 (Nếu 2 tập thuộc tính thứ i và n trong Lk-1 mà có k-2 thuộc
tính đầu giống nhau thì kết nối 2 tập đó với nhau)
i
i
i
im
1 1
1
2 2
2
p p
p
Giả sử: Lk-1 = {L1 L2 ...Lk 1 , L1 L2 ...Lk 1 ,...., L1 L2 ...Lk 1} với L j  L j  n , L j  L j

Nếu Lij  Lnj với j  1, k  2 và Lik 1  Lnk 1 thì chèn L1i Li2 ....Lik 1 Lnk 1 vào Ck
-

Tỉa: Chúng ta sẽ xoá tất cả những tập thuộc tính cCk nếu các tập con có k-1
thuộc tính của c khơng thuộc Lk-1:
For tất cả tập thuộc tính c Ck
For tất cả các tập con s có k-1 thuộc tính của c
Nếu s Lk-1 then xóa c khỏi Ck
15



Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Vấn đề đặt ra ở đây là chúng ta phải chứng minh Ck  Lk. Rõ ràng mỗi tập con
của một tập phổ biến phải cũng thoả mãn độ hỗ trợ tối thiểu. Do đó, nếu chúng ta mở
rộng mỗi tập thuộc tính trong Lk-1 với tất cả các thuộc tính có thể rồi sau đó xố tất cả
những tập thuộc tính là tập con của nó có cỡ k-1 mà lại khơng nằm trong Lk-1 chúng ta
sẽ được cịn lại tập của các tập thuộc tính trong Lk.
Bước kết hợp là để mở rộng Lk-1 với mọi thuộc tính trong cơ sở dữ liệu và sau
đó xố các tập thuộc tính mà các tập thuộc tính kích thước k-1 này có được bằng cách
xố thuộc tính thứ k-1 là không nằm trong Lk-1. Điều kiện Lik 1  Lnk 1 trong bước kết
hợp đơn giản để đảm bảo rằng khơng có 2 tập thuộc tính sinh trùng. Do đó sau bước
kết hợp thì Ck  Lk. Ở bước tỉa chúng ta xoá từ Ck tất cả các tập thuộc tính có k-1 thuộc
tính mà khơng nằm trong Lk-1 các tập này cũng là các tập không nằm trong Lk.
Tập các ứng cử Ck được lưu trong một cây băm. Mỗi nút của cây băm hoặc
chứa danh sách các tập thuộc tính (nút lá) hoặc 1 bảng băm (nút trong). Trong 1 nút
trong mỗi bucket của bảng băm trỏ tới 1 nút khác. Gốc của cây băm được xem là ở độ
sâu 1. Một nút trong ở độ sâu d trỏ tới các nút có độ sâu d+1. Các tập thuộc tính được
lưu trong các lá. Khi chúng ta bổ sung thêm 1 tập thuộc tính c chúng ta bắt đầu từ gốc
và đi xuống cây cho đến khi chạm vào lá. Ở một nút trong có độ sâu d, chúng ta quyết
định đi theo nhánh nào dựa vào việc áp dụng hàm băm đối với thuộc tính thứ d của tập
thuộc tính. Tất cả các nút được khởi tạo ban đầu là các nút lá. Khi số của các tập thuộc
tính trong nút lá vượt quá 1 ngưỡng nào đó, nút lá được chuyển thành nút trong.
Bắt đầu từ gốc. Hàm Subset tìm tất cả các ứng cử chứa trong bản ghi t như sau:

- Nếu chúng ta ở lá, chúng ta tìm các tập thuộc tính mà lá được chứa trong bản
ghi t và đưa các tham chiếu của nó vào tập kết quả.

- Nếu chúng ta ở nút trong và đang nắm giữ nó bởi việc băm thuộc tính i, chúng

ta băm trên mỗi thuộc tính ở sau i trong bản ghi t và áp dụng đệ quy thủ tục này
cho nút trong bucket tương ứng.

- Đối với gốc chúng ta băm trên tất cả các thuộc tính trong t.
Để xem tại sao hàm subset trả về tập mong muốn, chúng ta xem cái gì xảy ra ở
nút gốc. Cho mỗi tập thuộc tính c chứa trong bản ghi t, chắc chắn thuộc tính đầu tiên
của c cũng chứa trong bản ghi t. Vì nút gốc được tạo bằng cách băm trên tất cả các
thuộc tính chúng ta đã chắc chắn rằng chúng ta chỉ bỏ qua các tập thuộc tính mà bắt
đầo với một thuộc tính không nằm trong t. Tương tự chúng ta áp dụng cho các mức
sâu hơn. Thêm vào đó vì các thuộc tính được sắp xếp theo trật tự từ điển nên nếu
chúng ta đến nút hiện thời bằng việc băm thuộc tính i thì chúng ta chỉ cần xem xét các

16


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

thuộc tính trong t xuất hiện sau i.
1.3.2. Thuật tốn AprioriTid
1.3.2.1.

Giới thiệu thuật toán

Thuật toán AprioriTid [4] cũng sử dụng hàm apriori_gen để xác định các tập
ứng cử khi bắt đầu duyệt. Sự khác biệt thú vị của thuật toán này là cơ sở dữ liệu D
không sử dụng cho việc tìm độ hỗ trợ ở lần duyệt đầu tiên. Tập C k được sử dụng cho
mục đích này. Mỗi thành viên của C k có dạng <TID, {Xk}> ở đây mỗi Xk là tập phổ
biến tiềm năng đưa vào bản ghi có định danh TID. Với k=1, C 1 tương đương với cơ sở

dữ liệu D. Mặc dù về khái niệm mỗi thuộc tính i được thay bằng tập {i}. Với k1
C k được sinh bởi thuật toán (bước 10). Phần tử của C k ứng với bản ghi t là
 Ck \ c chứa trong t}>. Nếu 1 bản ghi không chứa bất kỳ một tập ứng cử có kích
thước k nào thì C k sẽ khơng có 1 mục nhập nào cho bản ghi này. Do đó thành viên của
các mục vào trong C k có thể nhỏ hơn số bản ghi trong cơ sở dữ liệu, đặc biệt khi k
lớn. Thêm vào đó, với giá trị k lớn mỗi mục vào có thể nhỏ hơn bản ghi tương ứng bởi
vì rất ít ứng cử được chứa trong bản ghi. Tuy nhiên, với k nhỏ mỗi mục vào có thể lớn
hơn bản ghi tương ứng bởi vì 1 mục vào trong Ck bao gồm tất cả các tập ứng cử kích
thước k chứa trong bản ghi.
Cấu trúc dữ liệu cũng được cải tiến
1.3.2.2. Các bước thực hiện
B1: L1 = {các tập phổ biến có 1 thuộc tính};
B2:

C 1 = D;

B3: For (k = 2; Lk-1  ; k++) do begin
// ứng cử mới

B4:

Ck = apriori_gen(Lk-1);

B5:

C k = ;

B6:

For tất cả các mục vào t  C k 1 do begin

B7:

// xác định các tập ứng cử trong Ck chứa trong bản ghi
// với định danh t.TID
Ct = { c  Ck \ (c-c[k])  t.tập của các tập thuộc tính 
(c-c[k-1])  t.tập của các tập thuộc tính};

B8:
B9:
B10:
B11:

For tất cả các ứng cử c  Ct do
// tăng cho ứng cử c 1 đơn vị

c.count++;

nếu (Ct  ) thì C k += <t.TID, Ct>;
end
17


Lê Thị Thanh Hải

B12:

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Lk = {c  Ck\ c.count  minsupp}

B10: end
B11: Return L =
1.3.2.3.

L

k

k

Giải thích

Cấu trúc dữ liệu
Chúng ta gán cho mỗi tập ứng cử một số duy nhất gọi là định danh (ID). Mỗi tập của
tập ứng cử Ck được lưu trong môt mảng chỉ mục của các định danh của các tập thuộc
tính trong Ck. Một thành viên của C k có cấu trúc <TID, {ID}>(<định danh của bản
ghi, định danh của tập>). Mỗi C k được lưu trong một cấu trúc tuần tự.
Hàm apriori_gen sinh tập ứng cử kích thước k Ck bằng cách kết hợp 2 tập phổ
biến kích thước (k-1). Mỗi tập ứng cử của chúng, ta duy trì 2 trường mới là trường
sinh và trường mở rộng. Trường sinh của một tập ứng cử Ck lưu định danh của 2 tập
phổ biến kích thước (k-1) mà chúng kết hợp với nhau để sinh Ck. Trường mở rộng của
một tập Ck lưu định danh của tất cả (k+1) ứng cử mà là mở rộng của Ck.
Ở bước 7, trường t.tập của tập thuộc tính của một mục vào t trong C k 1 là định danh
của tất cả (k-1) ứng cử trong bản ghi t. Với mỗi ứng cử Ck-1, trường mở rộng của nó
đưa ra Tk là tập của các định danh cho tất cả các ứng cử có kích thước k mà là mở rộng
của Ck-1. Với mỗi ck trong Tk trường sinh đưa ra định danh của 2 tập thuộc tính mà
sinh Ck. Nếu các tập thuộc tính nào đó được có mặt trong mục vào của t.tập của các
tập thuộc tính, chúng ta có thể kết luận rằng c k có mặt trong bản ghi t và thêm Ck vào

Ct .
Ví dụ
Xét Cơ sở dữ liệu D với độ hỗ trợ cho trước minsupp = 0,4(2/5)

18


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Database D
TID

Thuộc tính

1

ACD

2

BCE

3

ABCE

4

BE

C1

củatính
các thuộc tính
TID Tập
Thuộc
{{A}, {C}, {D}}
1
{{B}, {C}, {E}}
2
{{A}, {B},{C},{E}}
3
{{B}, {E}}
4

L1
Thuộc
TậpTID
thuộc Độ
hỗ trợ
tính
{A}tính
2/5
{B}
3/5
{C}
3/5
{E}

3/5

C2
Tập thuộc Độ
Thuộc
hỗ trợ
tính
tính
{A B}
1/5
{A C}
2/5
{A E}
1/5
{B C}
2/5
{B E}
3/5
{C E}
2/5

C2

TID
1
2
3
4

L2

Tập thuộc tính Độ hỗ trợ
{A C}
2/5
{B C}
2/5
{B E}
3/5
{C E}
2/5

Tập của các thuộc tính
{{A C}}
{{B C}, {B E}, {C E}}
{{AB},{AC},{AE},{BC},{BE},{CE}}
{{BE}}

C3
Tập thuộc tính Độ
Thuộc
hỗ trợ
tính
{B C E}
2/5
L3
Thuộc
hỗ trợ
TậpTID
thuộc Độ
tính
{B Ctính

E}
2/5

C3

TID Tập
của
các thuộc tính
Thuộc
tính
2 {{B C E}}
3

{{B C E}}

Bảng 1.5 Thực hiện các bƣớc thuật tốn Apriori
Trong ví dụ trên, ở bước 4, C2 được tính bởi hàm apriori_gen với đối số là L1. Trong
các bước từ 6 đến 10 chúng ta tính độ hỗ trợ cho các ứng cử trong C2 để tìm tập L2
bằng cách lặp lại các mục vào trong C 1 và sinh tập C 2 . Mục vào đầu tiên trong C 1 là
tập {{A}, {C}, {D}} tương ứng với bản ghi thứ 1. C t ở bước 7 tương ứng với mục vào
t=1 này là tập {{A C}} bởi vì {A C} là thành viên của C2 và cả ({A C}-{A}) và ({A
C} - {C}) là các thành viên của tập các tập thuộc tính của t=1.
Tiếp theo ở lần duyệt với k=3, C3 được tính bởi hàm apriori_gen với đối số L2. Thực
19


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

hiện với C 2 và C3 sinh tập C 3 . Lưu ý rằng khơng có mục vào nào trong C 3 đối với bản
ghi 1 và 4 do chúng không chứa bất kỳ mục dữ liệu nào trong C 3. Tập ứng cử {B C E}
trong C3 trở thành tập phổ biến và là thành viên duy nhất của L3. Khi chúng ta tìm C4
từ L3 kết quả là tập rỗng và vòng lặp kết thúc.
1.3.3. Sinh ra các luật kết hợp mạnh từ tập phổ biến
Với mỗi tập phổ biến L sẽ sinh ra tất cả các luật có dạng a  (L-a). Ở đây a là tập con
khơng rỗng của L sao cho

supp(L)
 minconf
supp(a)
Hay ta có a  (L-a) là luật kết hợp mạnh
Chúng ta cần xem xét tất cả các tập con của L để tìm ra đầy đủ luật.
Với a*  a  áp dụng tính chất 7 ta có a*  (L-a*) cũng là luật kết hợp mạnh.
Vì vậy trước tiên ta bắt đầu từ các luật có a là tập có kích thước lớn hay tương ứng với
vế phải là tập có kích thước nhỏ nhất (kích thước 1). Từ tập này sử dụng hàm
apriori_gen để sinh ra tất cả các vế phải
1.3.3.1. Thuật toán
For tất cả các tập phổ biến Lk, k  2 do
Call genrules(Lk, Lk)
Procedure genrules (Lk: tập phổ biến kích thước k, am: tập phổ biến kích thước m)
A= {am-1: tập thuộc tính kích thước (m-1)\am-1  am}
For tất cả am-1  A do again
Conf = supp(Lk)/supp(am-1);
If(conf  minconf) then
Begin
Output là luật am-1 Lk – am-1
với độ tin cậy = conf và độ hỗ trợ bằng supp(Lk)
Nếu (m-1>1) then
Call genrules (Lk, am-1);

//để sinh ra các luật vớiphần tiền đề là tâp con của am-1
end
End

20


Lê Thị Thanh Hải

1.3.3.2.

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Thuật toán nhanh hơn:

Ở trên, ta đã chỉ ra rằng nếu một luật không thoả mãn với tập cha a thì cũng khơng
thoả mãn với tập con của nó. Ví dụ như trên đã xét: nếu luật ABC  D có độ tin cậy
nhỏ hơn độ tin cậy cực tiểu thì luật AB  CD cũng khơng đủ độ tin cậy. Điều đó có
thể áp dụng theo hướng ngược lại như sau: nếu xảy ra luật với tập con thì cũng xảy ra
luật với tập cha. Ví dụ nếu luật AB  CD có độ tin cậy lớn hơn hoặc bằng độ tin cậy
cực tiểu thì luật ABC  D cũng đủ độ tin cậy.
Thuật toán 2:
For tất cả tập phổ biến Lk, k  2 do begin
H1 = {các phần kết luận là tập có kích thước 1 nhận được từ Lk}
Call ap_genrules(Lk, H1)
End
Procedure ap_genrules (Lk: tập phổ biến kích thước k, Hm: tập ứng cử kích thước m)
Nếu (k > m+1) then begin
Hm+1 = apriori_gen (Hm);
For tất cả hm+1  Hm+1 do begin

Conf = supp(Lk)/supp(Lk-hm+1);
If(conf  minconf) then
Output là luật Lk – hm+1  hm+1
//với độ tin cậy = conf và độ hỗ trợ bằng supp(Lk)
else
delete hm+1 từ Hm+1
end
Call ap_genrules (Lk, Hm+1);
End
Thuật toán nhanh hơn này sử dụng thủ tục apriori_gen mơ tả ở phần thuật tốn apriori.
Vấn đề ở đây là cần chứng minh tại sao nói thuật tốn 2 này nhanh hơn thuật tốn 1.
Ví dụ ta xét tập thuộc tính ABCDE. Giả sử rằng ACDE B và ABCE  D là các luật
mà phần kết luận có kích thước cực tiểu (=1) và thỏa mãn độ tin cậy cực tiểu minconf.
Trong thuật toán 1 gọi đệ quy thủ tục genrules(ABCDE, ACDE) sẽ kiểm tra các luật có 2
thuộc tính ở phần kết luận là ACD  BE, ADE  BC, CDE  AB và ACE  BD.

- Luật ACD  BE khơng xảy ra vì

E  BE
ABCD  E không thỏa mãn độ tin cậy tối thiểu

- Luật ADE  BC, CDE  AB cũng không thỏa mãn với lý do tương tự
21


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Gọi thủ tục genrules (ABCDE, ABCE) thì sẽ kiểm tra các luật ABC  CE, ABE  CD,

BCE  AD và ACE  BD. Ở đây ta cũng thấy 3 luật đầu là khơng thỏa mãn. Chỉ có
luật ACE  BD
Khai phá tập mục phổ biến không sinh các ứng cử:
Thuật tốn kinh điển apriori tìm tập phổ biến như đã trình bày ở trên thực hiện tốt bởi
rút gọn kích thước các tập ứng cử nhờ kỹ thuật tỉa. Tuy nhiên, trường hợp mẫu nhiều,
mẫu dài hoặc độ hỗ trợ cực tiểu thấp, các thuật toán như Apriori gặp phải2 chi phí lớn:

- Chi phí cho số lượng khổng lồ các tập ứng cử. Ví dụ nếu có 10 4 tập thuộc tính
thì thuật tốn Apriori sẽ cần sinh ra hơn 107 các tập ứng cử có 2 thuộc tính và
thực hiện kiểm tra sự xuất hiện của chúng. Hơn nữa, để khám phá được một
mẫu phổ biến có kích thước l thuật tốn phải kiểm tra (2l – 2)các mẫu phổ
biến tiềm năng. Ví dụ nếu kích thước l = 10 thì phải sinh 2100  1030 các ứng
cử (đây chính là số tập con của tập có 100 phần tử)

- Đòi hỏi lặp lại nhiều lần duyệt CSDL để kiểm tra tập rất lớn các ứng cử. Số
lần duyệt CSDL của thuật toán Apriori bằng độ dài của mẫu phổ biến dài nhất
tìm được. Trong trường hợp mẫu phổ biến dài và CSDL lớn, có nhiều bản ghi
điều này là khơng thể thực hiện được. Thuật tốn Apriori chỉ thích hợp cho
các CSDL thưa, với các CSDL dày thì thuật tốn thực hiện kém hiệu quả hơn.
1.3.4. Thuật tốn FP-Growth
Phần này trình bày một thuật tốn mới nói tìm các tập mục phổ biến rất hiệu quả, sử
dụng một kỹ thuật khác và không cần sinh ra các ứng cử. Thuật toán FP-Growth [5]
được giới thiệu bởi Jiawei Han, Jian Pei và Yiwen Yin vào năm 2000. Thuật toán này
thực hiện hiệu quả hơn thuật toán Apriori. Sự hiệu quả được xem ở 3 kỹ thuật chính:
i)

Mở rộng cấu trúc của cây prefix, được gọi là cây mẫu phổ biến (Frequant
pattern tree hoặc gọi tắt là FP-tree) [6] dùng để nén dữ liệu thích hợp. Chỉ có
các mục có độ dài 1 (1 thuộc tính) ở trong cây và các nút của cây được sắp
đặt để các nút xuất hiện thường xuyên có thể dễ dàng chia sẻ với các nút ít

xuất hiện hơn. CSDL lớn được nén chặt tới cấu trúc dữ liệu nhỏ hơn này
tránh được chi phí lặp lại duyệt qua CSDL.

ii)

Phương pháp khai phá phát triển từng đoạn dựa trên FP-tree gọi là phương
pháp FP-growth đã được thực hiện. Bắt đầu từ mẫu phổ biến có độ dài 1,
FP-growth xem xét chỉ cở sở mẫu phụ thuộc của nó như là CSDL con (subdatabase) bao gồm tập các tập phổ biến cùng xuất hiện với mẫu hậu tố
(suffix pattern), xây dựng cây FP phụ thuộc (conditional FP-tree) tương ứng

22


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

của nó và thực hiện khai phá đệ quy trên cây này. Mẫu phát triển nhận được
qua việc nối mẫu hậu tố với một đoạn mới được sinh ra từ conditional FPtree. Khai phá dựa trên FP-tree thực hiện theo cách phát triển các đoạn mẫu
để tránh chi phí cho việc sinh ra số lớn các tập ứng cử.
iii)

Kỹ thuật tìm kiếm được dùng ở đây là dựa vào sự phân chia, chia và chế
ngự (divide - and - conquer method) để phân rã nhiệm vụ khai phá thành tập
các nhiệm vụ nhỏ hơn với giới hạn các mẫu trong các CSDL nhằm thu gọn
khơng gian tìm kiếm

Phương pháp FP-growth đã chứng tỏ được tính hiệu quả của nó và có thể thực hiện
khai phá cho cả các mẫu ngắn và dài nhanh hơn thuật toán Apriori mà chỉ cần duyệt
CSDL 2 lần

Thuật toán FP-growth thực hiện như sau:

-

Duyệt CSDL lần thứ nhất để tính độ hỗ trợ của từng thuộc tính (đếm số lần
xuất hiện của từng thuộc tính)

-

Loại bỏ những thuộc tính khơng đáp ứng được độ hỗ trợ tối thiểu. Các thuộc
tính cịn lại được sắp theo thứ tự giảm dần của độ hỗ trợ (cũng tức là sắp theo
thứ tự giảm dần số lần xuất hiện trong CSDL). Ta nhận được danh sách L các
thuộc tính đã được sắp.

-

Duyệt CSDL lần thứ hai, với mỗi bản ghi t, loại bỏ những thuộc tính khơng
thỏa mãn độ hỗ trợ tối thiểu, các thuộc tính cịn lại sắp theo thứ tự giảm dần
của độ hỗ trợ. Lưu các thuộc tính vào cây FP-tree.

1.3.4.1.

Khai phá các mẫu phổ biến trên cây FP-tree đã xây dựng mà không cần duyệt
lại CSDL nữa.
Ví dụ 1.2:

Xét CSDL D dưới đây với độ hỗ trợ cực tiểu minsupp = 0,6 (3/5 bản ghi)
I={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}
TID

Thuộc tính

T100

a,c, d, f, g, i, m, p

T200

a, b, c, f, l, m, o

T300

b, f, h, j, o

T400

b, c, k, p, s

T500

a, c, e, f, l, m, n, p

Bảng 1.6 Cơ sở dữ liệu giao dịch (Ví dụ 1.2)

23


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Ta thực hiện theo các bước như trên:
B1: Tìm độ hỗ trợ của tất cả các thuộc tính
TID

Số lần xuất hiện

Độ hỗ trợ

a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
s

3
3
4

1
1
4
1
1
1
1
1
2
3
1
2
3
1

0,6
0,6
0,8
0,2
0,2
0,8
0,2
0,2
0,2
0,2
0,2
0,4
0,6
0,2
0,4

0,6
0,2

Bảng 1.7 Độ hỗ trợ của tất cả các thuộc tính (Ví dụ 1.2)
Bước 2: Tìm danh sách L
Thuộc tính

Số lần xuất hiện

Độ hỗ trợ

c

4

0,8

f

4

0,8

a

3

0,6

b

3

0,6

m

3

0,6

p

3

0,6

Bảng 1.8 Các tập phổ biến có 1 thuộc tính (Ví dụ 1.2)
Nghĩa là ta có danh sách các thuộc tính phổ biến theo thứ tự:
L = {(c:4/5), (f:4/5),(a:3/5), (b:3/5), (m:3/5), (p:3/5)}
(Số đằng sau dấu “:” là số lần xuất hiện thuộc tính đó trong CSDL-độ hỗ trợ của bản ghi
trong CSDL)

Bước 3: Duyệt CSDL lần thứ 2 và xây dựng cây FP-tree

24


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Khi đó:

-

Xây dựng F: (loại bỏ bớt thuộc tính và sắp xếp theo độ giảm của độ hỗ trợ)
Thuộc tính

TID
T100

c, f, a, m, p

T200

c, f, a, b, m

T300

f, b

T400

c, b, p

T500

c, f, a, m, p

Bảng 1.9 Cơ sở dữ liệu lần thứ 2 (Ví dụ 1.2)
Khởi tạo gốc có nhãn NULL
ROOT
c:1

Bắt
đầu từ
bản ghi
T100

f:1

ROOT

Tiếp
theo
đến
Bản
ghi
T200

f:2

c:4
f:3

a:2

m:1

p:
1

Lần
lượt
cho
đến
bản ghi
T500

c:2

a:1

ROOT
f:1
b:1

b:1

a:3

m:1

b:1

m:2

m:1
p:

p:
1
2
Hình 1.1 Cây CSDL khi duyệt lại (Ví dụ 1.2)

p:1
b:1
m:1

Để duyệt cây dễ dàng bảng item-header được xây dựng bằng việc liên kết nút (nodelink) nếu chúng có cùng tên thuộc tính
Thuộc tính đầu của các
liên kết nút

ROOT

f:1

c:4

c
f
a
b
m
p

f:3

b:1

a:3
m:2
p:2

25

b:1
p:1

b:1

m:1


Lê Thị Thanh Hải

Vấn đề về luật kết hợp mờ và các tốn tử có ngưỡng trong khai phá dữ liệu

Hình 1.2 Cây CSDL kết hợp với bảng thuộc tính (Ví dụ 1.2)
Dựa vào ví dụ trên cây FP-tree được xác định như sau:
Định nghĩa Cây FP-tree (Frequent pattern tree)
Cây FP-tree là cây có cấu trúc:

- Gốc của cây có nhãn null, con của gốc là các đường đi trên cây có item-prefix
- Mỗi nút trên một đường đi item-prefix bao gồm:
o Tên thuộc tính (item-name):
o Số đếm (count): là số các bản ghi mà có đường trỏ tới nút
o Liên kết (Node-link): liên kết đến nút tiếp theo trong cây mà có cùng tên
thuộc tính hoặc là null nếu có chỉ có 1 (khơng trỏ tới đâu)

- Mỗi mục vào trong bảng các đầu mục phổ biến (frequent-item-header table)
bao gồm:
o Tên thuộc tính
o Đầu của các nút liên kết (một con trỏ trỏ đến nút đầu tiên trong FP-tree
mang tên thuộc tính)
Dựa vào định nghĩa này chúng ta có thuật toán xây dựng FP-tree
1.3.4.2.

Thuật toán:

Input: CSDL các bản ghi D và ngưỡng độ hỗ trợ tối thiểu 
Output: FP-tree của D
1. Duyệt CSDL. Xây dựng F là tập của các thuộc tính phổ biến và tính độ hỗ trợ
của mỗi thuộc tính phổ biến. Sắp xếp F theo thứ tự giảm dần của độ hỗ trợ để
được FList
2. Khởi tạo gốc của FP-tree là T và gán nhãn NULL. Cho mỗi bản ghi t trong
CSDL D

-

Chọn các thuộc tính phổ biến, sắp xếp theo thứ tự của Flist. Để thứ tự của
các thuộc tính phổ biến được sắp trong t là [p | P] với p là thành phần đầu
tiên và P là danh sách còn lại. Gọi thủ tục Insert_tree([p | P],T)

-

Hàm Insert_tree([p | P],T) được thực hiện như sau: Nếu T có 1 con là N mà
N.item-name = p.item-name thì tăng số đếm của N lên 1. Nếu không khởi
tạo 1 nút N mới với số đếm khởi tạo là 1. Liên kết cha của nó là liên kết tới
T và nút liên kết của nó được liên kết tới các nút có cùng item-name. Nếu P

26