Khai thác k mẫu tuần tự tối đại sử dụng cây dữ liệu chiếu tiền tố

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 76 - 
Abstract: This paper propose a method called 
TMSP to perform squential patten mining. Because 
maximal patterns compact representations of frequent 
patterns, so they are used for mining in TMSP. The 
main idea of TMSP is mining top-k frequent maximal 
equential patterns of length no less than the minimum 
length of each pattern (min_l) and no greater than the 
maximum length of each pattern (max_l) with k is the 
desired number of maximal sequential patterns to be 
mined. The proposed method helps user do not need 
turning specification of a minimum support threshold 
to perform the mining which is a disadvantage of 
previous studies. Experimental results on real datasets 
show that TMSP serves as an efficient solution for 
mining sequential patterns. The reults also 
demonstrate that TMSP is better than the maximal 
sequential pattern mining algorithm (MAXSP) in term 
memory efficient and easier for users to find the 
number of required patterns without adjusting minsup. 
Keywords: Sequential, Sequential pattern mining, 
maximal sequential patterns, Top-k maximal 
sequential patterns, prefix-projected databases. 
I. GIỚI THIỆU 
Khai thác mẫu tuần tự là một nhiệm vụ quan trọng 
của khai thác dữ liệu đã và đang được nghiên cứu rộng 
rãi [1-3]. Cho một tập các chuỗi, trong đó mỗi chuỗi 
bao gồm một danh sách các tập phổ biến và một 
ngưỡng hỗ trợ tối thiểu do người dùng chỉ định 
(minsup), khai thác mẫu tuần tự là tìm ra tất cả các 
mẫu phổ biến có độ hỗ trợ không thấp hơn minsup. 
Trong đó, thuật toán PrefixSpan [1] tổ chức dữ liệu 
theo chiều ngang và thực hiện phép chiếu trên CSDL 
để giảm chi phí lưu trữ dữ liệu, xuất phát từ tập mẫu 
tuần tự độ dài là 1, PrefixSpan tạo ra CSDL được 
chiếu với mỗi mẫu đó. Trong CSDL chiếu, mỗi chuỗi 
dữ liệu chỉ giữ lại phần hậu tố đối với tiền tố đã chiếu. 
Mẫu được phát triển bằng những item phổ biến tìm 
được trong CSDL được chiếu. Quá trình này được lặp 
lại cho đến khi CSDL chiếu không còn item phổ biến 
nào. Thuật toán SPADE [2] tổ chức dữ liệu theo chiều 
dọc, ứng với mỗi item sẽ lưu danh sách định danh của 
các chuỗi dữ liệu và định danh của các itemset có chứa 
item đó. Độ hỗ trợ của item được tính trực tiếp từ danh 
sách các định danh. Mặt khác, SPADE còn dựa trên lý 
thuyết dàn để chia nhỏ không gian tìm kiếm và thao 
tác kết đơn giản để tạo ra tập ứng viên. Thuật toán này 
gom nhóm các mẫu tuần tự dựa theo tiền tố thành các 
lớp tương đương. Thuật toán SPAM [3] cũng tổ chức 
dữ liệu theo chiều dọc như thuật toán SPADE, trong 
đó các mẫu ứng viên được biểu diễn dưới dạng bảng 
bit dọc, mỗi bit ứng với một itemset của một chuỗi 
trong CSDL. Nếu item có mặt trong itemset j thì bít 
tương ứng itemset j được đánh dấu là 1, ngược lại là 0. 
Độ hỗ trợ cũa mẫu được xác định dựa trên bảng bit. 
Các thuật toán trên tạo ra các mẫu phổ biến mà các 
mẫu đó có thể có cùng độ hỗ trợ hoặc là mẫu con của 
mẫu phổ biến khác và khi chọn minsup quá cao sẽ tạo 
ra ít các mẫu bỏ qua các thông tin có giá trị, còn ngược 
lại thì quá nhiều mẫu dẫn đến thuật toán thực thi chậm. 
Để chọn một giá trị minsup hợp lý đòi hỏi phải hiểu rõ 
về dữ liệu. Để khắc phục vấn đề này, P. Fournier-
Viger và cộng sự đã đề xuất thuật toán khai thác k mẫu 
tuần tự (TKS) [4], thuật toán TKS khai thác các mẫu 
tuần tự dựa vào thuật toán SPAM xuất phát từ giá trị 
minsup = 0 bước tiếp theo tìm các mẫu thỏa giá trị 
Khai thác k mẫu tuần tự tối đại sử dụng cây dữ 
liệu chiếu tiền tố 
Mining Top-k Maximal Sequential Patterns using Prefix-Projected 
Database Tree 
Lê Hoài Bắc, Nguyễn Thị Quyên 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 77 - 
minsup khi số lượng mẫu thu được lớn hơn k mẫu sẽ 
xóa các mẫu có độ hỗ trợ bằng minsup, xóa đến khi 
bằng k mẫu và tăng giá trị minsup bằng độ hỗ trợ thấp 
nhất trong tập k mẫu thu được, quá trình này được lặp 
lại cho đến khi CSDL chiếu không còn mẫu phổ biến 
nào. Thuật toán TKS khắc phục được vấn đề tinh 
chỉnh giá trị minsup nhưng trong số mẫu tuần tự thu 
được còn tồn tại các mẫu tuần tự có cùng độ hỗ trợ. 
Ngoài ra P. Tzvetkov và cộng sự cũng đã đề xuất thuật 
toán khai thác k mẫu tuần tự đóng TSP [5], sử dụng 
phương pháp chiếu dựa vào thuật toán PrefixSpan 
thực hiện tương tự như thuật toán TKS. Kết quả thuật 
toán TSP thu được không còn tồn tại các mẫu tuần tự 
có cùng độ hỗ trợ nhưng thuật toán TSP vẫn còn tồn 
tại các mẫu tuần tự con trong các mẫu tuần tự thu 
được. Do đó, Philippe và cộng sự đã đề xuất thuật toán 
khai thác các mẫu tuần tự tối đại (MaxSP) [7] khai 
thác các mẫu tuần tự dựa trên thuật toán PrefixSpan, 
kết quả nhận được không tồn tại mẫu tuần tự con 
nhưng rất khó cho người sử dụng phải điều chỉnh giá 
trị minsup hợp lý và dung lượng bộ nhớ sử dụng lớn. 
Chính vì vậy, trong bài báo này sẻ trình bày thuật toán 
khai thác k mẫu tuần tự tối đại (TMSP) để tối ưu hóa 
về bộ nhớ sử dụng và giúp người sử dụng dễ dàng tìm 
được số lượng mẫu tuần tự như mong muốn. 
II. MỘT SỐ ĐỊNH NGHĨA CƠ BẢN 
Chuỗi là một danh 
sách có thứ tự [7]. Cơ sở dữ liệu chuỗi D là một tập 
các chuỗi và tập các item 
 xảy ra trong chuỗi đó. Item là giá trị 
tượng trưng. Itemset là tập các item 
riêng biệt không có thứ tự. 
Ví dụ 1: Xét CSDL chuỗi như sau: 
Bảng 1. Cơ sở dữ liệu chuỗi 
SID Sequences 
1 
2 
3 
4 
Trong Bảng 1, Chuỗi có 5 itemset xảy ra theo 
thứ tự (a), (abc), (ac), (d) và sau cùng là (cf). 
Chiều dài của s, l(s) là tổng số các item trong s còn 
được gọi là l-sequence. 
Ví dụ 2: Chuỗi là một 3-sequence có kích 
thước là 2. 
Chuỗi là một chuỗi con của 
chuỗi khác kí hiệu là , 
nếu và chỉ nếu , sao cho 
 và . 
Người ta gọi là chuỗi cha của . 
Ví dụ 3: Chuỗi là chuỗi con của 
, nhưng không phải là chuỗi 
con của chuỗi và ngược lại. 
Định nghĩa 1. (Tiền tố - Prefix): Giả sử các items 
trong một itemset được sắp xếp theo thứ tự từ điển. 
Cho hai chuỗi 
 . Chuỗi là tiền tố của nếu và 
chỉ nếu [1]: 
a. 
 với mọi 
b. 
 . 
c. Các item trong 
 theo thứ tự là những 
item đứng sau 
 trong . 
Ví dụ 4: Xét CSDL như Bảng 1, Các tiền tố của 
chuỗi = là , <(a) 
(a)>, ,  nhưng các chuỗi 
, không phải là tiền tố của . 
Định nghĩa 2. (Hậu tố - Postfix): Cho chuỗi 
 có chuỗi 
 là tiền tố của . Chuỗi hậu tố của có dạng: 
 . Trong đó, 
 [1]. 
Nếu chuỗi thì = – = . 
Ví dụ 5: Xét CSDL như Bảng 1. Chuỗi = 
 có các tiền tố: 
 = Hậu tố = 
 = Hậu tố = 
 = Hậu tố = 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 78 - 
Định nghĩa 3. (Phép chiếu cơ sở dữ liệu theo tiền 
tố): 
Cho là mẫu trong cơ sở dữ liệu D. 
Cơ sở dữ liệu được chiếu theo , kí hiệu: , là 
tập hợp các hậu tố của các chuỗi dữ liệu trong D có 
liên quan đến tiền tố [1]. 
Ví dụ 6: Xét CSDL như Bảng 1, tiền tố = . 
Khi đó cơ sở dữ liệu được chiếu theo . = 
{, } 
Định nghĩa 4. (Độ hỗ trợ - Support): Xét CSDL 
chuỗi D, mỗi chuỗi có một chỉ số định danh duy nhất. 
Độ hỗ trợ tuyệt đối mẫu là tổng số chuỗi trong D có 
chứa p, ký hiệu . Độ 
hỗ trợ tương đối của p là tỉ lệ phần trăm chuỗi trong D 
chứa p. Ở đây, mức hỗ trợ tuyệt đối hoặc tương đối sẽ 
được sử dụng chuyển đổi qua lại, kí hiệu là sup(p). 
Ví dụ 7: Xét CSDL như Bảng 1, Mẫu p = 
xuất hiện trong chuỗi , , , . Vậy độ hỗ trợ của 
mẫu p là 4. 
Định nghĩa 5. (Mẫu tuần tự): Cho trước ngưỡng 
hỗ trợ tối thiểu (minsup) xác định bởi người dùng. Một 
mẫu được coi là phổ biến nếu độ hỗ trợ của nó lớn 
hơn hoặc bằng minsup: sup( ) ≥ minsup, khi đó 
được gọi là mẫu tuần tự [8]. 
Ví dụ 8: Xét CSDL như Bảng 1, có tập các item 
phân biệt là {a, b, c, d, e, f, g} và minsup = 2. Xét 
chuỗi = chuỗi có 5 itemset 
là: (a), (abc), (ac), (d), (cf) và có 9 lần xuất hiện của 
các item. 
Vậy có kích thước là 5 và có độ dài là 9. Trong 
chuỗi , item a xuất hiện ba lần nhưng nếu tính độ hỗ 
trợ thì độ hỗ trợ của item a chỉ được tính là 1 đối với 
chuỗi đó. Mẫu p = xuất hiện trong chuỗi , 
 , , . Vậy độ hỗ trợ của mẫu p là 4. Vì sup(p) > 
minsup nên p là mẫu tuần tự. 
Định nghĩa 6. (Mẫu tuần tự tối đại): Mẫu tuần tự 
 là mẫu tuần tự tối đại nếu nó không tồn mẫu tuần tự 
 sao cho mẫu là cha của mẫu , [8,9]. 
Ví dụ 9: Xét CSDL như Bảng 1, mẫu 
 có sup = 2 là mẫu tuần tự tối đại nhưng 
mẫu có sup = 3 không là mẫu tuần tự tối đại vì 
mẫu là con của mẫu . 
Định nghĩa 7. (Khai thác k mẫu tuần tự tối đại): 
Để tìm ra tập F gồm có k mẫu tuần tự tối đại mà mỗi 
mẫu tối đại 
và không tồn tại mẫu tuần tự tối đại 
 và 
 . 
Ví dụ 10: Xét CSDL như bảng 1, với k = 2, min_l 
= 1, max_l = 3. Thuật toán tìm được 2 mẫu như sau: 
: 3, : 3. Mặc dù thuật toán tìm 
được hơn 2 mẫu với độ hỗ trợ bằng 3: : 3, 
: 3, những mẫu này không nằm trong kết quả 
bởi vì chúng không là mẫu tuần tự tối đại và chúng là 
con của mẫu kết quả. 
Định nghĩa 8. Chuỗi s cho trước, tập chuỗi IDs của 
tất cả các chuỗi trong CSDL D chứa s gọi là danh sách 
chuỗi ID, ký hiệu: SIDList(s). Tổng của SIDList(s) gọi 
là tổng chuỗi ID, ký hiệu là SIDSum(s) [5]. 
Ví dụ 11: Xét CSDL như bảng 1 thì danh sách 
chuỗi ID của là [1, 2, 3, 4] và tổng chuỗi ID 
của là 10. 
III. PHƢƠNG PHÁP PHÁT TRIỂN 
III.1. Cấu trúc cây tiền tố 
Cây tiền tố là một cây có thứ tự, trong đó quan hệ 
giữa nút cha với nút con tương ứng là quan hệ giữa 
chuỗi con và chuỗi cha. Cây tiền tố được xây dựng 
như sau: Bắt đầu từ nút gốc của cây tại mức 0, nút gốc 
được gán nhãn là một chuỗi rỗng 〈〉. Tại mức min_l 
bất kỳ, mỗi nút được gán nhãn là một mẫu tuần tự độ 
dài min_l. Các nút ở mức (min_l + 1) kế tiếp được xây 
dựng đệ quy bằng cách mở rộng mẫu độ dài min_l ở 
mức trước đó. Mẫu mở rộng bằng cách thêm vào một 
item phổ biến đó là mở rộng theo chuỗi và mở rộng 
theo itemset. Quá trình mở rộng theo một thứ tự cho 
đến khi không còn item phổ biến. 
Ví dụ 12: xét mẫu p = , nếu thêm một item b 
vào mẫu p thì là mở rộng theo chuỗi và 
 là mở rộng theo itemset. (Hình 1) 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 79 - 
Hinh 1. Cây tiền tố 
III.2. Cấu trúc cây PDB 
Cấu trúc cây PDB là một bộ nhớ mô tả cây tìm 
kiếm tiền tố và lưu trữ thông tin về CSDL chiếu đã 
được khai thác một phần trong suốt quá trình khai thác 
đa duyệt. 
Khai thác các mẫu tuần tự dựa trên cây PDB như 
khai thác cây tìm kiếm tiền tố nhưng khai thác trên cây 
PDB làm giảm rất nhiều số lần duyệt trên CSDL chiếu 
bằng cách thực hiện chiếu các tiền tố theo thứ tự giảm 
dần theo độ hỗ trợ thay vì thực hiện tìm kiếm như cây 
tiền tố. Do đó, Cây PDB tại mỗi điểm của tiền tố có 
cùng độ dài sẽ được sắp xếp giảm dần theo độ hỗ trợ, 
khi giá trị minsup tăng những tiền tố có độ hỗ trợ thấp 
sẽ dẫn đến không phổ biến nên bộ nhớ sử dụng ít. 
Cây PDB có kích thước nhỏ hơn nhiều so với cây 
tìm kiếm tiền tố trong suốt quá trình khai thác dữ 
liệu. Độ sâu lớn nhất của cây PDB luôn luôn nhỏ 
hơn min_l. Mặt khác, giảm bộ nhớ để lưu trữ cây 
PDB, chúng ta sử dụng CSDL chiếu giả tại tất các nút 
cây PDB. Chúng ta chỉ lưu trữ danh sách các điểm của 
chuỗi hiện tại trong CSDL chuỗi ban đầu. 
Ví dụ 13: Xét CSDL như Bảng 1. Từ hình 2 ta thấy 
cây PDB chỉ lưu trữ danh sách các điểm của chuỗi, 
Khi chiếu theo tiền tố as có độ hỗ trợ là 4 thì ta tìm 
được các item as, bs, bi, cs, ci, ds, di, es, ei, fs, fi nhưng 
tại mỗi điểm sau khi được sắp xếp và lưu trữ giảm dần 
theo độ hỗ trợ như sau: bs: 4, cs: 4, as: 2, ds: 2, fs: 2, bi: 2, 
es: 1, fi: 1, di: 1, ci: 1, ei: 1. Chính vì vậy, các item có độ 
hỗ lớn sẽ thực hiện phép chiếu trước và giá trị minsup 
tăng nhanh dẫn đến các item có độ hỗ trợ thấp không 
phổ biến. Trong đó s mỡ rộng theo chuỗi, i mỡ rộng 
theo itemset. Quá trình lặp lại cho đến khi không còn 
item phổ biến. 
IV. THUẬT TOÁN TMSP 
IV.1. Thuật toán 
Thuật toán khai thác các mẫu tuần tự tối đại 
(MaxSP) sử dụng thuật toán PrefixSpan dựa trên cây 
tiền tố để khai thác các mẫu tuần tự. Đối với thuật toán 
khai thác k mẫu tuần tự tối đại (TMSP) với số mẫu 
tuần tự k biết trước cũng sử dụng thuật toán 
PrefixSpan để khai thác các mẫu tuần tự nhưng dựa 
trên cấu trúc cây PDB được mô tả chi tiết như Hình 3. 
Mô tả thuật toán TMSP thực hiện các bƣớc nhƣ 
sau: 
- Bước 1: Tính hằng số được tính theo công thức 
 (dòng 1). 
- Bước 2: Tìm tập tất cả các item phổ biến chèn vào 
histogram có độ dài là 1 (dòng 2). 
- Bước 3: Sắp xếp giảm dần các item có độ dài 
bằng 1 trong histogram (dòng 3). 
- Bước 4: Ứng với mỗi phổ biến gọi thủ tục 
TopSequencesTraversal (dòng 4). 
bs 
as 
cs 
ci 
ds 
fs 
as 
bs 
bi 
as 
cs ds es 
fs 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 80 - 
Hinh 2. Cây PDB 
Đầu vào: CSDL D, k, min_l, max_l; 
Đầu ra: Tập F gồm có k mẫu tuần tự tối đại 
Phƣơng pháp thực hiện: 
1. 
2. Duyệt CSDL D một lần, tìm mỗi item phổ biến 
 sao cho: 
 s có thể mở rộng đến s ; 
 Chèn vào histogram H[1]; 
3. Sắp xếp giảm dần các item trong H[1] dựa trên 
độ hộ trợ của chúng; 
4. Với mỗi , support( minsup 
 Gọi TopsequencesTraversal(s , 
 , min_l); 
TopsequencesTraversal(s , , min_l) 
5. Nếu support(s) < minsup thì kết thúc; 
6. Nếu thì 
7. Savepattern( ); 
8. Gọi PrefixSpanWSR(s, minsup, Ds, F); 
9. Kết thúc; 
10. Nếu l(s) > max_l thì kết thúc; 
11. Duyệt CSDL Ds một lần, tìm mỗi item phổ biến 
 sao cho: 
 s có thể mở rộng đến s ; 
 Nếu l( max_l thì ngưng mở rộng; 
 Chèn vào histogram H[l(s) + 1]; 
12. Sắp xếp giảm dần các item trong H[l(s) + 1] 
dựa trên độ hộ trợ của chúng; 
13. Next_level_top_support 
 GetLevelTopSupportFromHistogam( H[l(s) + 
1]) 
14. Với mỗi , support( 
 next_level_top_support 
15. Gọi TopSequencesTraversal(s , 
 , min_l); 
16. Kết thúc; 
PrefixSpanWSR(s, minsup, Ds, F) 
17. Nếu l(s) = max_l thì kết thúc; 
18. Sắp xếp giảm dần các item trong H[l(s) + 1] dựa 
trên độ hộ trợ của chúng; 
19. Duyệt CSDL Ds một lần, tìm mỗi item phổ biến 
. . . 
bs: 4 
cs: 4 
as: 2 
ds: 2 
fs: 2 
bi: 2 
es: 1 
fi: 1 
di: 1 
ci: 1 
ei: 1 
CSDL 
chiếu giả 
cs: 3 
as: 2 
ds: 2 
fs: 2 
ci: 2 
bs: 1 
es: 1 
CSDL 
chiếu 
giả 
bs: 3 
cs: 3 
as: 2 
ds: 1 
es: 1 
fs: 1 
ai: 1 
bi: 1 
CSDL 
chiếu 
giả 
as: 4 
bs: 4 
cs: 4 
ds: 3 
es: 3 
fs: 3 
gs: 1 
CSDL D 
bs: 4 cs: 4 
Cấp min_l 
as: 4 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 81 - 
 sao cho: 
20. s có thể mở rộng đến s ; 
21. Chèn vào histogram H[l(s) + 1]; 
22. Savepattern( ); 
23. Nếu l( ) < max_l thì 
24. PrefixSpanWSR(s , minsup, Ds, F); 
GetLevelTopSupportFromHistogam( H[l(s) + 
1]) 
25. ; 
26. Nếu thì 
 ; 
27. Kết quả trả về là độ hỗ trợ tại vị trí ; 
SavePattern(s) 
28. Nếu l(s) < min_l hoặc support(s) < minsup thì 
kết thúc; 
29. Nếu MaximalPatternVerification(s) = 
add_and_raise thì 
30. Nếu k thì 
31. Nếu support(s) > minsup hoặc l(s) > 
l_min(r) F thì 
32. Trong khi k và r F | l(r) 
< l(s) 
33. Xóa các mẫu có độ dài ngắn 
nhất từ F; 
34. Trong khi k và r F | 
35. Xóa các mẫu có độ hỗ trợ 
bằng minsup từ F; 
36. F:= F {s}; 
37. Cập nhật lại minsup bằng độ hỗ trợ nhỏ 
nhất trong tập F; 
38. Ngược lại F:= F {s}; 
39. Ngược lại nếu MaximalPatternVerification(s) 
= add_but_no_raise thì 
40. Nếu |F| = 0 hoặc l(s) l_min(r) thì 
41. F:= F {s}; 
MaximalPatternVerification( ) 
42. Nếu tồn tại item u, sao cho support(s i u) = 
support(s) hoặc support(s s u) = support(s) 
thì trả về no_add; 
43. Nếu SIDSum(s) không nằm trong SIDSum_Hash 
thì trả về add_and_raise; 
44. Với mọi 
45. Nếu s thì trả về no_add; 
46. Nếu s thì 
47. Thay thế với s; 
48. Trả về no_add; 
49. Trả về add_and_raise; 
Hinh 3. Mô tả thuật toán TMSP 
Mô tả chi tiết các thủ tục thực hiện trong thuật 
toán TMSP nhƣ sau: 
Thủ tục TopsequencesTraversal được miêu tả như 
sau: 
 Nếu độ hỗ trợ của s nhỏ hơn minsup thì kết thúc 
(dòng 5). 
 Nếu chiều dài của s bằng min_l thì lưu s vào tập F 
và gọi thủ tục PrefixSpanWSR (dòng 6 - 9). 
 Nếu chiều dài của s không bằng min_l mà lớn hơn 
max_l thì kết thúc ngược lại thì duyệt CSDL Ds và tìm 
mỗi item phổ biến sao cho s có thể mở rộng s và 
chỉ mỡ rộng khi chiều dài mẫu nhỏ hơn max_l và chèn 
 vào histogram có độ dài bằng l+1, sau đó sắp xếp 
các item trong histogram giảm dần theo độ hỗ trợ để 
tìm support dựa vào thủ tục 
GetLevelTopSupportFromHistogam. Cuối cùng nếu 
độ hỗ trợ của lớn hơn hoặc bằng support thì gọi đệ 
qui TopSequencesTraversal đến khi nào bằng min_l 
(dòng 10 - 16). 
Thủ tục SavePattern trả về một trong ba kết quả 
sau: 
+ add_but_no_raise: Thêm vào tập F nhưng không 
tăng giá trị minsup. 
+ add_and_raise: Thêm vào tập F và tăng giá trị 
minsup. 
+ no_add: Không thêm vào tập F. 
Thủ tục SavePattern được mô tả cụ thể như sau: 
Nếu chiều dài mẫu tuần tự s nhỏ hơn min_l hoặc độ hỗ 
trợ mẫu s nhỏ hơn minsup thì kết thúc (dòng 28). Nếu 
thủ tục ClosePatternVerification(s) cho kết quả 
add_and_raise thì kiểm tra nếu số lượng mẫu trong tập 
F lớn hơn hoặc bằng k và độ hỗ trợ mẫu s lớn hơn 
minsup hoặc độ dài mẫu s lớn hơn mẫu có độ dài thấp 
nhất trong tập F thì sẽ xóa các mẫu trong tập F có độ 
dài thấp hơn mẫu s cho đến khi số lượng mẫu trong 
tập F bằng k (dòng 29-33), trong trường hợp tất cả các 
mẫu trong tập F đều bằng nhau thì xóa các mẫu trong 
tập F có độ hỗ trợ bằng minsup cho đến khi số lượng 
mẫu trong tập F bằng k (dòng 34 - 35), sau đó thêm s 
vào và cập nhật lại minsup bằng độ hỗ trợ thấp nhất 
trong tập F (dòng 36 - 37). Nếu số lượng tập F nhỏ 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 82 - 
hơn k thì thêm s vào (dòng 38). Trong trường hợp thủ 
tục ClosePatternVerification(s) cho kết quả 
add_but_no_raise thì kiểm tra nếu chưa có mẫu hoặc 
độ dài mẫu s lớn hơn hoặc bằng độ dài mẫu thấp nhất 
trong tập F thì thêm mẫu s vào tập F (dòng 39 - 41). 
Thủ tục MaximalPatternVerification được mô tả 
các bước như sau: 
 Nếu tồn tại một item mở rộng u có cùng độ hỗ trợ 
với s thì không thêm s vào tập F (dòng 42). 
 Nếu SIDSum(s) (tổng chuổi ID) không nằm trong 
bảng Hash thì thêm s vào tập F và tăng độ hỗ trợ 
(dòng 43). 
 Với mỗi thì thủ tục sẽ thực hiện 1 trong 2 điều 
kiện như sau (dòng 44): 
- Nếu s là cha của thì không thêm vào tập F 
(dòng 45). 
- Nếu là cha của s thì thay thế với s nhưng 
không thêm vào tập F (dòng 46 - 48). 
 Trường hợp còn lại thêm vào tập F và tăng độ hỗ 
trợ (dòng 49). 
IV.2. Ví dụ minh họa 
Ví dụ 14: Cơ sở dữ liệu như Bảng 1, minh họa thuật 
toán TMSP với k = 2, min_l = 1 và max_l = 3 như sau: 
Minsup = 1; = 0.4; 
Duyệt CSDL D tìm được các item phổ biến, mỗi 
item phổ biến tạo nên một chuỗi có độ dài là 1. Vậy có 
7 mẫu phổ biến chèn vào histogram có độ dài là 1 đã 
được sắp xếp giảm dần theo độ hỗ trợ như sau: : 
4, : 4, : 4, : 3, : 3, : 3, 
: 1. 
Ứng với mỗi mẫu phổ biến thực hiện gọi 
TopSequencesTraversal để tìm 2 mẫu tuần tự tối đại: 
Lần lượt thực hiện TopSequencesTraversal(, 
D|, 1 ), TopSequencesTraversal(, D|, 1 
), . 
 TopSequencesTraversal(, D|, 1 ) 
Chiều dài mẫu = min_l = 1 nên: 
 SavePattern() nhưng mẫu này không lưu vào 
tập F vì mẫu tồn tại item b có thể mở rộng và 
cùng độ hỗ trợ . 
 Gọi PrefixSpanWSR(, 1, D|, F), tìm được 
các mẫu phổ biến có độ dài là 2 đã được sắp xếp giảm 
dần theo độ hỗ trợ như sau: : 4, : 4, 
: 2, : 2, : 2, : 2, 
: 1, : 1, : 1, : 1, : 1. 
Thực hiện đệ qui : 4, ta tìm các mẫu phổ biến 
tối đại có độ dài là 2: 
 SavePattern() lưu vào tập F vì 
SIDSum() = 10 chưa có trong bảng Hash. 
 Tập F: : 4, SIDSum = 10 
 Chiều dài mẫu < 3, đệ qui 
PrefixSpanWSR(, 1, D|, F), tìm được các 
mẫu phổ biến có độ dài là 3 đã được sắp xếp giảm dần 
theo độ hỗ trợ như sau: : 2, : 2, 
: 2, : 1, : 1, 
: 1. 
Thực hiện đệ qui : 2, tìm các mẫu phổ biến 
tối đại có độ dài là 3: 
 SavePattern() nhưng mẫu này không lưu 
vào tập F vì mẫu tồn tại item a có thể mở 
rộng và cùng độ hỗ trợ . 
 Chiều dài mẫu = 3, dừng đệ qui 
PrefixSpanWSR(, 1, D|, F). 
Thực hiện đệ qui : 2, tìm các mẫu phổ biến 
tối đại có độ dài là 3: 
 SavePattern() lưu vào tập F vì 
SIDSum() = 10 chưa có trong bảng Hash. 
 Tập F: : 4, SIDSum = 10 
 : 2, SIDSum = 3 
 Chiều dài mẫu = 3, dừng đệ qui 
PrefixSpanWSR(, 1, D|, F). 
Thực hiện đệ qui mẫu : 2, tìm các mẫu phổ 
biến tối đại có độ dài là 3: 
 SavePattern() lưu vào tập F vì 
SIDSum() = 5 chưa có trong bảng Hash. 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 83 - 
Số lượng mẫu trong tập F ≥ 2 và độ hỗ trợ mẫu 
 lớn hơn 1, do đó xóa mẫu : 
4 có độ dài mẫu ngắn nhất. 
Cập nhật lại minsup = 2. 
 Tập F: : 2, SIDSum = 3 
 : 2, SIDSum = 5 
 Chiều dài mẫu = 3, dừng đệ qui 
PrefixSpanWSR(, 2, D|, F). 
Thực hiện đệ qui : 4, tìm các mẫu phổ biến tối 
đại có độ dài là 2: 
 SavePattern(), không lưu vào tập F vì tồn 
tại chuỗi cha <(a)(b)(c). 
 Chiều dài mẫu < 3, đệ qui 
PrefixSpanWSR(, 2, D|, F), tìm được các 
mẫu phổ biến có độ dài là 3 đã được sắp xếp giảm dần 
theo độ hỗ trợ như sau: : 3, : 3, 
: 2,. 
Thực hiện đệ qui : 3, tìm các mẫu phổ biến 
tối đại có độ dài là 3: 
 SavePattern() lưu vào tập F vì 
SIDSum() = 9 chưa có trong bảng Hash. 
Số lượng mẫu trong tập F và độ hỗ trợ mẫu 
 lớn hơn 2, do đó xóa mẫu : 2. 
Cập nhật lại minsup = 2. 
 Tập F: : 2, SIDSum = 5 
 : 3, SIDSum = 9 
 Chiều dài mẫu = 3, dừng đệ qui 
PrefixSpanWSR(, 2, D|, F). 
Thực hiện đệ qui : 3, tìm các mẫu phổ biến 
tối đại có độ dài là 3. 
 SavePattern() lưu vào tập F vì 
SIDSum() = 7 chưa có trong bảng Hash. 
Số lượng mẫu trong tập F và độ hỗ trợ mẫu 
 lớn hơn 2, do đó xóa mẫu : 2 
có độ hỗ trợ thấp nhất. 
Cập nhật lại minsup = 3. 
 Tập F: : 3, SIDSum = 9 
 : 3, SIDSum = 7 
 Chiều dài mẫu = 3, dừng đệ qui 
PrefixSpanWSR(, 3, D|, F). 
 Tiếp tục thực hiện TopSequencesTraversal(, 
D|, 1 ), TopSequencesTraversal(, D|, 1 ), 
 thực hiện tương tự như tiền tố a. 
Vậy với k = 2, min_l = 1, max_l = 3. Ta có tập F 
gồm 2 mẫu tuần tự tối đại như sau: 
Bảng 2. Kết quả thuật toán TMSP với k =2, min_l =1, 
max_l =3 
Mẫu tuần tự tối đại SIDSum 
: 3 9 
: 3 7 
V. KẾT QUẢ THỰC NGHIỆM 
Đặc điểm CSDL được mô tả như Bảng 3. CSDL 
thực - Leviathan được lấy từ kho dữ liệu máy học 
UCI, CSDL này mỗi itemset chỉ có một item. CSDL 
tổng hợp - C6T5S4I4N1kD1k và N1KD10K_a1 phát 
sinh bởi bộ phát sinh dữ liệu IBM, CSDL này mỗi 
itemset là một tập các item. Việc thực nghiệm được 
tiến hành trên máy tính DELL có cấu hình CPU Intel 
core i5-2410M, 6G RAM và sử dụng hệ điều hành 
Microsoft Windows 10, cài đặt trên ngôn ngữ lập trình 
Java. 
Hình 4, Hình 5 và Hình 6 cho thấy bộ nhớ sử dụng 
của thuật toán TMSP vượt trội hơn thuật toán MaxSP 
trên các tập dữ liệu thực nghiệm. Ví dụ 15: Xét cơ sở 
dữ liệu Leviathan (có số lượng item phân biệt lớn) với 
 , bộ nhớ sử dụng MaxSP là 393 (mb) trong 
khi bộ nhớ sử dụng TMSP chỉ tốn 138 (mb). 
Bảng 3. Đặc điểm của CSDL 
CSDL Số chuỗi 
Số lƣợng item 
phân biệt 
Leviathan 5834 9025 
C6T5S4I4N1kD1k 1000 1000 
N1kD10k_a1 10000 1000 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 84 - 
Hinh 4. So sánh bộ nhớ sử dụng của hai thuật toán 
trên CSDL – Leviathan với min_l = 1, mal_l = 5 
Hinh 5. So sánh bộ nhớ sử dụng của hai thuật toán 
trên CSDL–C6T5S4I4N1kD1k với min_l =1, mal_l =3 
Hinh 6. So sánh bộ nhớ sử dụng của hai thuật toán 
trên CSDL – N1KD10K_a1 với min_l = 1, mal_l = 4 
VI. KẾT LUẬN 
Bài báo này trình bày thuật toán khai thác k mẫu 
tuần tự tối đại dựa trên cây PDB. Thuật toán TMSP sử 
dụng phương pháp chiếu tìm các mẫu tuần tự phổ biến 
để loại bỏ các mẫu con trong các mẫu thu được. Kết 
quả thực nghiệm cho thấy thuật toán TMSP đạt hiệu 
quả cao hơn MaxSP về bộ nhớ sử dụng và giúp người 
sử dụng dễ dàng tìm được số lượng mẫu cần khai thác 
mà không phải tinh chỉnh giá trị minsup. 
Hướng phát triển: thuật toán khai thác k mẫu tuần 
tự tối đại dựa trên phương pháp chiếu để tìm các mẫu 
tuần tự phổ biến dễ dàng tìm được k mẫu tuần tự tối 
đại nhưng mất nhiều thời gian thực hiện. Vì vậy, 
hướng phát triển tiếp theo là sử dụng phương pháp 
vector bit động [10] để tối ưu hóa về thời gian thực 
hiện và bộ nhớ sử dụng. 
LỜI CÁM ƠN 
Nghiên cứu này được tài trợ bởi Quỹ phát triển 
Khoa học và Công nghệ Quốc gia (NAFOSTED) 
trong đề tài mã số 102.05-2015.07. 
TÀI LIỆU THAM KHẢO 
[1] J. P. J. PEI, J. H. J. HAN, B. MORTAZAVI-ASL, 
H. PINTO, Q. C. Q. CHEN, U. DAYAL, AND M.-
C. H. M.-C. HSU, “PrefixSpan,: mining sequential 
patterns efficiently by prefix-projected pattern 
growth,” Proc. 17th Int. Conf. Data Eng., 2001. 
[2] M. J. ZAKI, “SPADE: An efficient algorithm for 
mining frequent sequences,” Mach. Learn., vol. 42, 
no. 1–2, pp. 31–60, 2001. 
[3] J. AYRES, J. GEHRKE, T. YIU, AND J. 
FLANNICK, “Sequential pattern mining using a 
bitmap representation,” Proc. eighth ACM 
SIGKDD Int. Conf. Knowl. Discov. data Min., pp. 
429–435, 2002. 
[4] P. FOURNIER-VIGER, A. GOMARIZ, T. 
GUENICHE, E. MWAMIKAZI, AND R. 
THOMAS, “TKS: Efficient mining of top-k 
sequential patterns,” Lect. Notes Comput. Sci. 
(including Subser. Lect. Notes Artif. Intell. Lect. 
Notes Bioinformatics), vol. 8346 LNAI, no. PART 
100
150
200
250
300
350
400
450
2 0 0 3 0 0 4 0 0 5 0 0 
M
em
o
ry
 u
sa
g
e 
(m
b
) 
k 
MaxSP TMSP
50
60
70
80
90
100
110
4 0 0 5 0 0 6 0 0 7 0 0 
M
em
o
ry
 u
sa
g
e 
(m
b
) 
k 
MaxSP TMSP
200
250
300
350
400
450
500
400 500 600 700 
M
em
o
ry
 u
sa
ge
 (
m
b
) 
k 
MaxSP TMSP
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 15 (35), tháng 6/2016 
- 85 - 
1, pp. 109–120, 2013. 
[5] P. TZVETKOV, X. YAN, AND J. HAN, “TSP: 
Mining top-k closed sequential patterns,” Knowl. 
Inf. Syst., vol. 7, no. 4, pp. 438–457, 2005. 
[6] K.SOHINI AND MR.V.PURUSHOTHAMA 
RAJU, “Mining Top-k Closed Sequential Patterns 
in Sequential Databases,” IOSR J. Comput. Eng. , 
vol. 15, no. 4, pp. 20–23, 2013. 
[7] P. FOURNIER-VIGER, C. W. WU, AND V. S. 
TSENG, “Mining maximal sequential patterns 
without candidate maintenance,” Lect. Notes 
Comput. Sci. (including Subser. Lect. Notes Artif. 
Intell. Lect. Notes Bioinformatics), vol. 8346 
LNAI, no. PART 1, pp. 169–180, 2013. 
[8] P. FOURNIER-VIGER, C. W. WU, A. 
GOMARIZ, AND V. S. TSENG, “VMSP: 
Efficient vertical mining of maximal sequential 
patterns,” Lect. Notes Comput. Sci. (including 
Subser. Lect. Notes Artif. Intell. Lect. Notes 
Bioinformatics), vol. 8436 LNAI, pp. 83–94, 2014. 
[9] M. J. ZAKI AND W. MEIRA JR., Data mining 
and analysis: fundamental concepts and 
algorithms. Cambridge University Press, New 
York, 2014. 
[10] M.-T. TRAN, B. LE, AND B. VO, 
“Combination of dynamic bit vectors and 
transaction information for mining frequent closed 
sequences efficiently,” Eng. Appl. Artif. Intell., vol. 
38, pp. 183–189, 2015. 
Nhận bài ngày: 09/03/2016 
SƠ LƢỢC VỀ TÁC GIẢ 
LÊ HOÀI BẮC 
Hiện là Phó Trưởng khoa, 
Trưởng Bộ môn Khoa học Máy 
tính, Khoa CNTT, Trường ĐH 
Khoa học Tự nhiên TP HCM. 
Hướng nghiên cứu: trí tuệ Nhân 
tạo, tính toán mềm và data 
mining. 
Email: lhbac@fit.hcmuns.edu.vn 
NGUYỄN THỊ QUYÊN 
Tốt nghiệp ĐH ngành CNTT 
năm 2008 tại Trường ĐH Sư 
phạm kỹ thuật TP HCM và Cao 
học ngành CNTT năm 2015 tại 
Trường ĐH Công nghệ TP 
HCM. 
Hiện công tác tại Khoa CNTT, 
Trường Cao đẳng nghề Công 
nghệ cao Đồng An. 
Hướng nghiên cứu: khai thác dữ 
liệu. 
Email: nguyenquyen@dongan.edu.vn