ĐẠ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 TOÁ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

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 toá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
Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

3
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

Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

4

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

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
Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

7

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 toá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 toán hiệu quả hơn từ các thuật


9
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.
1.1. Ý NGHĨA THỰC TIỄN CỦA LUẬT KẾT HỢP
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
1.2. MÔ HÌNH HÌNH THỨC CỦA VẤN ĐỀ PHÁT HIỆN LUẬT
1.2.1. Các định nghĩa
1.2.1.1. Thuộc tính và CSDL
- I = {I
1
, I
2
, …,I

Transaction Identification) và nó là một tập các thuộc tính T
k
 I với
k =
m,1
Ta có T
k
(I
v
) xác định giá trị của thuộc tính I
v
.
Ví dụ: nếu xét thuộc tính phân, T
k
(I
v
) = 1 nghĩa là khách hàng T
k
chọn

mua mặt hàng
Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

10
I
v
, T
k
(I
v

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.2.1.5. Độ 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
Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

11
 
 
kk
kkk
TXDT
TYTXDT
rconf




\)(supp
)(supp
X
YX 


1.2.1.6. 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 toá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 1-
Ví 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 = {T
1
, T
2

D, F
T
6
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 (T
1
, T
3
, T
4
, T
6
) 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

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
Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

13
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

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ể:
L
k
: 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ợ
Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

15
C
k
: 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ợ
k
C
: 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: L

L

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 L
1.

Tiếp theo ở bước 2 ta thực hiện vòng lặp để tính L
k
từ L
k-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ử C
k
từ các tập phổ biến k-1 thuộc tính (L
k-1
) ở
vòng trước. Ở đây ta sử dụng hàm apriori_gen với đối số là L
k-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: L
k-1
với L
k-1
(Nếu 2 tập thuộc tính thứ i và n trong L
k-1
mà có k-2 thuộc
tính đầu giống nhau thì kết nối 2 tập đó với nhau)

nj
i
j
LLLL


 ,

Nếu
n
j
i
j
LL 
với
2,1  kj
và
n
k
i
k
LL
11 

thì chèn
n
k
i
k
ii

k
. 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 L
k-1
với tất cả các thuộc tính có thể rồi sau đó xoá 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 L
k-1
chúng ta
sẽ được còn lại tập của các tập thuộc tính trong L
k
.
Bước kết hợp là để mở rộng L
k-1
với mọi thuộc tính trong cơ sở dữ liệu và sau
đó xoá 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
xoá thuộc tính thứ k-1 là không nằm trong L
k-1.
Điều kiện
n
k
i
k
LL
11 

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ì C
k

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
Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

17
thuộc tính trong t xuất hiện sau i.
1.3.2. Thuật toá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
k
C
được sử dụng cho
mục đích này. Mỗi thành viên của
k
C
có dạng <TID, {X
k
}> ở đây mỗi X
k
là tập phổ
biến tiềm năng đưa vào bản ghi có định danh TID. Với k=1,
1
C
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
= D;
B3: For (k = 2; L
k-1
 ; k++) do begin
B4: C
k
= apriori_gen(L
k-1
); // ứng cử mới
B5:
k
C
= ;
B6: For tất cả các mục vào t 
1k
C
do begin
B7: // xác định các tập ứng cử trong C
k
chứa trong bản ghi
// với định danh t.TID
C
t
= { c  C
k
\ (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: For tất cả các ứng cử c  C
t

k
đượ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 C
k
. Một thành viên của
k
C
có cấu trúc <TID, {ID}>(<định danh của bản
ghi, định danh của tập>). Mỗi
k
C
đượ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 C
k
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ử C
k
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 C
k
. Trường mở rộng của
một tập C
k
lưu định danh của tất cả (k+1) ứng cử mà là mở rộng của C
k.
Ở 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
1k
C
là định danh


Bảng 1.5 Thực hiện các bƣớc thuật toán Apriori
Trong ví dụ trên, ở bước 4, C
2
được tính bởi hàm apriori_gen với đối số là L
1
. Trong
các bước từ 6 đến 10 chúng ta tính độ hỗ trợ cho các ứng cử trong C
2

A B C E
B E
4
Thuộc tính
TID
1
C

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

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

1
{{A C}}
{{B C}, {B E}, {C E}}
2
3
{{AB},{AC},{AE},{BC},{BE},{CE}}
{{BE}}
4
Tập của các thuộc tính
TID
L
2
{A C}
2/5
2/5
{B C}
{B E}
3/5
2/5
{C E}
Độ hỗ trợ
Tập thuộc tính

3
C
đố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 C
3
trở thành tập phổ biến và là thành viên duy nhất của L
3
. Khi chúng ta tìm C
4
từ L
3
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
minconf
supp(a)
supp(L)


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

Output là luật a
m-1
 L
k
– a
m-1

với độ tin cậy = conf và độ hỗ trợ bằng supp(L
k
)
Nếu (m-1>1) then
Call genrules (L
k
, a
m-1
);
//để sinh ra các luật vớiphần tiền đề là tâp con của a
m-1

end
End
Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

21
1.3.3.2. 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

m+1
do begin
Conf = supp(L
k
)/supp(L
k
-h
m+1
);
If(conf  minconf) then
Output là luật L
k
– h
m+1
 h
m+1

//với độ tin cậy = conf và độ hỗ trợ bằng supp(L
k
)
else
delete h
m+1
từ H
m+1
end
Call ap_genrules (L
k
, H
m+1

mẫu phổ biến có kích thước l thuật toán phải kiểm tra (2
l
– 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 2
100
 10
30
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 toán Apriori chỉ thích hợp cho
các CSDL thưa, với các CSDL dày thì thuật toán thực hiện kém hiệu quả hơn.
1.3.4. Thuật toán FP-Growth
Phần này trình bày một thuật toá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 (sub-
database) 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

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)
Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

24
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
3
0,6
b
3
0,6
c
4
0,8
d

1
0,2
o
2
0,4
p
3
0,6
s
1
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


Hình 1.1 Cây CSDL khi duyệt lại (Ví dụ 1.2)
Để 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 (node-
link) 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
c

f

a

b

m

p
m:1
ROOT
c:4
f:3

a:3

m:2
p:
2
b:1
Lần
lượt
cho
đến
bản ghi
T500
m:1
f:1

b:1
b:1
p:1
ROOT
c:4
f:3
a:3
m:2
p:2
b:1

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