ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

VÕ ĐÌNH BẢY NÂNG CAO HIỆU QUẢ CỦA CÁC THUẬT TOÁN KHAI THÁC
LUẬT KẾT HỢP DỰA TRÊN DÀN
L

Tp. Hồ Chí Minh – 2011


Tôi xin cam an rng ni dung ca lun án này là kt qu nghiên cu ca chính bn
thân. Tt c nhg tham kho t các nghiên cu có liên quan 
. 
  nêu trong anh
 .


Tác gi lun án 
-ii-
Lời cảm ơn
Lời đầu tiên, em xin bày tỏ lòng biết ơn sâu sắc đến Thầy, PGS. TS. Lê Hoài Bắc bởi
nhờ sự động viên, chỉ bảo, hướng dẫn tận tình của Thầy, em mới có thể hoàn thành
luận án này.

Em cũng xin chân thành gửi lời cảm ơn đến các Thầy Cô trong khoa Công nghệ Thông
tin trường Đại học Khoa học Tự nhiên Tp. HCM đã tận tình dạy dỗ, chỉ bảo nhiều kiến
thức quí báu giúp em hoàn thành khóa học đúng tiến độ.

Xin cảm ơn Phòng Sau đại học về những hỗ trợ về mặt thủ tục, giấy tờ.

Xin cảm ơn các đồng nghiệp, bạn bè đã động viên tôi trong suốt thời gian thực hiện

 26
 28
 34
2.3. Dàn 37
 37
dàn -L) 39
 44
 44
 44
 51
 51

-iv-
 52
 52
 53
 54
 55
DÀN  58
3.1. Khdàn  58
dàn  58
 61
 66
 74
 76
 77
 80
 88
ây   90
 91

AR
Association Rule(s)

2
CHARM
Closed Association Rule
Mining


3
Cidset
Closed identifiers set

4
C
k

Cadidate k-itemsets
tem.
5
CSDL
Database(s)

6
Diffset
Difference set

7
Eclat
Equivalence class

Itemset-Tidset tree
Cây IT
15
L
k

Large k-itemsets

k item.
16
MFIL
Modification of Frequent
Itemset Lattice

17
minConf
Minimum confidence

18
mG
Minimal Generator


-vii-
19
minSup
Minimum support

20
minSupCount

27

Support

28


ng
29


 -viii-
Danh mục các bảng
 10
 13
 15
 16
  26
 32
 45
 49
 54
 64
 66
 67
 TW 74
 75

Hình 2.18  dàn -L 40
Hình 2.19   41
Hình 2.20  toán CHARM-L 43
Hình 2.21   con 45
Hình 2.22   48
Hình 2.23   52
Hình 2.24   53
Hình 2.25   55

-x-
Hình 2.26   57
Hình 3.1  D 59
Hình 3.2  LATTICE_FI D 
= 3 60
Hình 3.3  dàn  63
Hình 3.4   68
Hình 3.5   68
Hình 3.6 69
Hình 3.7 69
Hình 3.8 69
Hình 3.9 70
Hình 3.10   70
Hình 3.11   71
Hình 3.12 
Mushroom 71
Hình 3.13   72
Hình 3.14  72
Hình 3.15   72
Hình 3.16  73
Hình 3.17 73

Hình 4.3  dàn  109
Hình 4.4  dàn  110
-1-
Chƣơng 1. GIỚI THIỆU TỔNG QUAN Ch
sâu nghiên c
 trình
bày.
1.1. Khai thác dữ liệu


, 
 



3 bài toán chín
,  
  [B21],
hác  Web, v.v

CSDL) 
 
nhu 
[B22, B70], ILA [B79, B80], A12,

-3-
khai thác FI/FCI [B7, B13,
B15, B16, B17, B20, B26, B31, B36, B38, B57, B61, B62, B64, B65, B66, B73,
B82, B91, B96, B98, B103]chính 

 [B7]
c

-itemset-itemset 
-itemset



-itemset 
AprioriTid [B7]. 2) Eclat [B17,
B96, B98, B103]  và các
trong [B103
 xétTransactions
identifier set  
itemset
B98
 X 
Y X, Y Tid 
 
 [B98]. 3) FP-Growth [B16, B31, B38, B66, B91]
2000 [B38
FP và sau nó là không
 

-4-

sau
gian khai thác [B13, B31, B59, B61, B64, B65, B66, B72, B82,
B91, B96, B98 có 
là i) CHARM [B96], -tree; và ii) Closet [B66]
 FP-tree. Kf dCHARM [B96,
B98]   

trình bàyB91
Grahne và Zhu [B31] trình bày


B33, B49, B94].
 l
1
 . 
B3
 B4]

.
 các 
. B8] 
 
B63
 .

-6-
1.3. Giới thiệu về dàn
  
 
 

B8
khai thác dàB84].
1.4. Luật kết hợp
Bài toán khai thác  [B6, B7]  n
item I = {i
1
, i
2
i
n
D t  I 
  Transaction identifier 
XYX
pq
\
,

(X  Yq p 

 là sinh D 
  
Khai thác  [A2, B6, B7], khai
5, A8], 
   [A6, A7, B97, B101      A3,
A23, B13, B64, B65], A1, A10, B5, B93] và khai thác
A18]. 
tâm [B13, B25, B35, B64, B65, B97].        
11, B12, B27].
 sinh 
CSDL D  do 

1.5. Mục tiêu của luận án


-9-
- Khai thác các thông 
.
- Sinh các   .
1.6. Kết luận

     


h L

này. Ddàn vào
 lu
sinh 



     
          
 
  .

1: G
 
: T
   dàn 


C
1, 2, 3, 4, 5, 6
D
2, 4, 5, 6
T
1, 3, 5, 6
W
1, 2, 3, 4, 5
Mã giao



1
A, C, T, W
2
C, D, W
3
A, C, T, W
4
A, C, D, W
5
A, C, D, T, W
6
C, D, T -11-
Chƣơng 2. CƠ SỞ LÝ THUYẾT
i) .  X  Y(Y) 
minSupCount thì (X)  minSupCount.
ii) Y 
X(X) < minSupCount thì (Y) < minSupCount.

-12-
2.1.2 Các thuật toán khai thác tập phổ biến
Các thB7], Eclat
[B103] và FP-Growth [B38]. .
 
phph 
dàn 
2.1.2.1 Thuật toán Apriori
a) Ý tưởng của thuật toán
khai thác 
1-itemset 
 là 




òn 



-
-1)-


Apriori.