Nghiên cứu các kỹ thuật khai phá mẫu dãy cho dữ liệu dãy

Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131
125 
NGHIÊN CỨU CÁC KỸ THUẬT KHAI PHÁ MẪU DÃY CHO DỮ LIỆU DÃY 
Quách Xuân Trưởng*, Nguyễn Văn Sự, Đinh Đức Hoàng 
Trường ĐH Công nghệ Thông tin và Truyền thông – ĐH Thái Nguyên 
TÓM TẮT 
Khai phá mẫu dãy là một nội dung quan trọng trong khai phá dữ liệu với nhiều ứng dụng rộng rãi 
như phân tích thị trường, phân tích mẫu truy cập web, phát hiện xâm nhập trong môi trường mạng, 
trong nghiên cứu DNA, dự đoán nhu cầu mua sắm của khách hàng, Khai phá mẫu dãy là việc 
phát hiện các dãy con phổ biến trong cơ sở dữ liệu dãy. Kể từ khi được đề xuất bởi Agrawal và 
Srikant đến nay bài toán này đã thu hút được nhiều nghiên cứu và có nhiều kỹ thuật được đề xuất. 
Đầu tiên là thuật toán dựa trên nguyên lý Apriori, sau đó là các thuật toán mở rộng được phát triển 
cho các ứng dụng phức tạp. Bài báo giới thiệu và phân tích các kỹ thuật bằng cách phân loại các 
kỹ thuật theo hai nhóm tiếp cận chính: phương pháp tiếp cận dựa trên Apriori và phương pháp tiến 
cận phát triển mẫu. Trong bài báo cũng phân tích mở rộng các kỹ thuật khác nhau dựa trên các đặc 
tính quan trọng và thảo luận một số tồn tại đang được tập trung nghiên cứu. 
Từ khóa: Cơ sở dữ liệu dãy, khai phá mẫu dãy, phát triển mẫu, apriori, phân tích mẫu. 
GIỚI THIỆU* 
Khai phá mẫu dãy là phương pháp tìm kiếm 
các mẫu dãy có ích từ trong cơ sở dữ liệu lớn, 
nó phát hiện ra các dãy con phổ biến từ cơ sở 
dữ liệu dãy. Đây là một chủ đề thiết thực và 
quan trọng trong khai phá dữ liệu với nhiều 
ứng dụng như phân tích giao dịch mua bán 
của khách hàng, phân tích web-log, khai thác 
các dãy DNA, các dự báo khí tượng thủy văn 
hay phân tích các dữ liệu y học [12][13][14]. 
Khai phá mẫu dãy là xác định những mẫu mà 
sự xuất hiện của chúng trong cơ sở dữ liệu 
thỏa mãn mức hỗ trợ tối thiểu nào đó do 
người dùng định nghĩa. Với số lượng các mẫu 
có thể là rất lớn và với các yêu cầu và lợi ích 
khác nhau, bằng cách sử dụng ngưỡng tối 
thiểu thì các mẫu không thỏa mãn ngưỡng tối 
thiểu được xem là không có ý nghĩa và không 
cần xem xét đến làm cho quá trình khai phá sẽ 
hiệu quả hơn. 
MỘT SỐ KHÁI NIỆM CƠ BẢN 
Cho một tập I={i1, i2, ., im} gồm m phần tử 
và gọi là các item. Mỗi phần tử được kết hợp 
với một tập thuộc tính như giá trị, giá cả, lợi 
nhuận, thời gian, giá trị trong thuộc tính A 
của phần tử i được kí hiệu bằng i.A. Một 
itemset là một tập con không rỗng các item và 
một itemset có lực lượng là k được gọi là k-
itemset. 
*
 Tel: 0989090832; Email: qxtruong@ictu.edu.vn 
Một dãy S= là một danh sách có 
thứ tự những itemset. Mỗi si (1≤i≤n) là một 
itemset, n là số lượng itemset. Kính thước của 
dãy bằng số lượng itemset có trong dãy. 
Chiều dài của dãy là tổng số item có trong 
dãy kí hiệu là 
1
n
j
j
l s
=
=∑ . Dãy có chiều dài k 
còn gọi là k-sequence, ví dụ: S= 
là một 3-sequence có kính thước là 2. 
Chuỗi β= được gọi là dãy con 
của dãy ∝= hay chuỗi ∝ là dãy 
cha của dãy β, kĩ hiệu là β⊆∝, nếu tồn tại 
những số nguyên 1≤j1<j2<<jn<m sao cho 
b1⊆aj1, b2⊆aj2, , bm⊆ajm. 
Một cơ sở dữ liệu dãy là một tập hợp các bộ 
dữ liệu có dạng (sid, s), trong đó sid là định 
danh của dãy và s là dãy các itemset. Cho một 
cơ sở dữ liệu dãy D, độ hỗ trợ tuyệt đối của 
một mẫu tuần tự f là tổng số dãy trong D có 
chứa f, kí hiệu là supD(f)=|{Si∈D|f⊆Si}|. Độ 
hỗ trợ tương đối của f là tỉ lệ phần trăm dãy 
trong D chứa f. Ở đâ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(f). Như vậy vấn đề 
khai phá mẫu dãy là đi tìm tập toàn bộ các 
mẫu đối với một cơ sở dữ liệu dãy với một độ 
hỗ trợ tối thiểu min_sup cho trước. Một mẫu f 
được coi là phổ biến nếu độ hỗ trợ của nó lớn 
hơn hoặc bằng min_sup: sup(f)≥min_sup, khi 
đó f được gọi là mẫu dãy [12]. 
Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131
126 
CÁC PHƯƠNG PHÁP KHAI PHÁ MẪU DÃY 
Phát hiện các mẫu dãy phổ biến có thể được 
xem như là việc phát hiện luật kết hợp trên cơ 
sở dữ liệu thời gian. Các thuật toán khai phá 
mẫu dãy kế thừa nhiều từ các thuật toán khai 
phá luật kết hợp, trong đó sự khác biệt chính 
là trong khai phá mẫu dãy tìm kiếm các mẫu 
dãy liên tục (trong nhiều giao dịch) mà ở đó 
thứ tự của các item và itemset là rất quan 
trọng, trong khi luật kết hợp chỉ tìm kiếm các 
mẫu nội bộ (trong một giao dịch). Theo các 
nghiên cứu, các thuật toán khai phá mẫu dãy 
chủ yếu tập trung vào hai nội dung sau: 
(1) Cách thức mà dãy ứng viên được sinh ra 
và lưu trữ. Các thuật toán có thể có các cách 
khác nhau với mục tiêu là giảm thiểu số 
lượng dãy ứng viên để giảm chi phí I/O. 
(2) Cách mà độ hỗ trợ được tính và tần xuất 
dãy ứng viên được kiểm tra. 
Dựa vào các tiêu chí trên, thuật toán khai phá 
mẫu dãy có thể được nhóm thành hai hướng 
tiếp cận chính: thuật toán dựa trên Apriorri, 
thuật toán phát triển mẫu. 
Phương pháp tiếp cận dựa trên Apriori 
Nguyên lý Apriori ứng dụng cho dãy là nếu 
một dãy S không phải là dãy phổ biến thì mọi 
dãy cha của S cũng không phải là dãy phổ 
biến. Các thuật toán này dựa vào nguyên lý 
apriori để sinh và kiểm tra các dãy ứng viên, 
trong đó nếu một dãy được kiểm tra không 
thỏa mãn ngưỡng tối thiểu thì các dãy chứa 
nó cũng sẽ bị loại. Có một số thuật toán theo 
phương pháp tiếp cận dựa trên Apriori như 
AprioriAll, GSP, SPADE, SPAM... và các 
biến thể của chúng. 
(1) Thuật toán GSP: Cấu trúc cơ bản của thuật 
toán GSP [14] là thuật toán duyệt dữ liệu 
nhiều lần, lần duyệt đầu tiên xác định độ hỗ 
trợ của từng item. Kết thúc lần duyệt đầu tiên, 
thuật toán đưa ra được tập các 1-sequence phổ 
biến gọi là tập khởi đầu. Tập khởi đầu được 
sử dụng để sinh ra các dãy ứng viên mới với 
mỗi dãy ứng viên có ít nhất một item thuộc 
dãy khởi đầu, vì thế tất cả các dãy ứng viên 
trong một lần duyệt sẽ có cùng số item. Độ hỗ 
trợ của các dãy ứng viên này được tìm thấy 
trong quá trình duyệt dữ liệu. Kết thúc lần 
duyệt, thuật toán xác định các dãy ứng viên 
phổ biến và những dãy ứng viên phổ biến này 
trở thành tập khởi đầu cho lần duyệt tiếp theo. 
Thuật toán kết thúc khi không tìm được dãy 
ứng viên nào cuối lần duyệt, hoặc khi không 
có dãy ứng viên nào được sinh ra. 
Hình 1. Sinh các ứng viên và mẫu dẫy trong GSP 
(2) Thuật toán SPADE: thuật toán SPADE 
[17] tổ chức dữ liệu theo chiều dọc, trong đó 
ứng với mỗi item sẽ lưu danh sách định danh 
của các dãy 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 nối đơn giản để sinh ra tập các 
ứng viên. Thuật toán này gom nhóm các mẫu 
dãy dựa theo tiền tố thành các lớp tương 
đương. Thuật toán chỉ duyệt cơ sở dữ liệu ba 
lần: lần nhứ nhất và thứ hai thực hiện tìm các 
mẫu dãy có độ dài 1 và 2. Ở lần duyệt thứ ba, 
thuật toán phát triển mẫu độ dài k từ hai mẫu 
độ dài (k-1) có (k-2) item đầu giống nhau, tiến 
hành duyệt trên từng lớp tương đương do đó 
thuật toán giảm được khá nhiều chi phí tính 
toán và sử dụng bộ nhớ hiệu quả hơn; tuy 
nhiên thuật toán cũng cần một lượng thời gian 
để chuyển đổi một cơ sở dữ liệu theo chiều 
ngang sang định dạng theo chiều dọc. 
Hình 2. Tổ chức dữ liệu và chia nhỏ không gian 
tìm kiếm trong SPADE 
Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131
127 
(3) Thuật toán SPAM: thuật toán SPAM [3] 
kết hợp các giải pháp của các thuật toán GSP, 
SPADE, FreeSpan. Tương tự như SPADE, 
thuật toán này cũng tổ chức dữ liệu theo chiều 
dọc, thông tin của 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 dãy trong cơ sở dữ liệu. 
Nếu item có mặt trong itemset j thì bit tương 
ứng đượ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. 
SPAM sử dụng phương pháp duyệt cây theo 
chiều sâu để sinh các ứng viên và nguyên tắc 
apriori để tỉa các ứng viên nhằm giảm không 
gian tìm kiếm. Thuật toán này hiệu quả đối với 
các cơ sở dữ liệu lớn vì tổ chức và lưu trữ dữ 
liệu dưới dạng bit nên thao tác sinh ứng viên 
và đếm độ hỗ trợ rất hiệu quả. 
Hình 3. Biến đổi dữ liệu sang dạng nhị phân 
dọc trong SPAM 
Các thuật toán theo phương pháp tiện cận dựa 
Apriori về cốt lõi dựa trên các đặc điểm chính 
sau [10]: 
- Tìm kiếm theo chiều rộng: Khi thuật toán 
xây dựng tập tất cả các dãy k-sequence trong 
mỗi lần lặp thứ k, thuật toán duyệt qua toàn 
bộ không gian tìm kiếm 
- Sinh và kiểm tra ứng viên: Thuật toán sử 
dụng phương pháp tạo và tỉa các ứng viên, tuy 
nhiên phương pháp tạo ứng viên sinh ra một 
lượng lớn các dãy ứng viên và việc kiểm tra 
từng ứng viên thoả mãn ngưỡng cho phép làm 
tiêu tốn nhiều bộ nhớ trong giai đoạn đầu của 
quá trình. 
- Duyệt cơ sở dữ liệu nhiều lần: Cơ sở dữ 
liệu gốc sẽ được duyệt lặp lại nhiều lần để 
kiểm tra các ứng viên được tạo ra có phổ biến 
hay không. Đây là điểm hạn chế của hầu hết 
các phương pháp dựa trên apriori vì nó đòi 
hỏi nhiều thời gian xử lý và chi phí I/O. 
Phương pháp tiếp cận phát triển mẫu 
Ý tưởng chính của phương pháp tiếp cận 
hướng phát triển mẫu là để tránh việc sinh 
toàn bộ các ứng viên và tập chung vào tìm 
kiếm trên một phần được hạn chế trên cơ sở 
dữ liệu ban đầu, việc phân vùng không gian 
tìm kiếm là nội dung quan trọng trong hướng 
tiếp cận này. Các thuật toán phát triển mẫu là 
các thuật toán duyệt theo chiều sâu, kỹ thuật 
này tạo ra cơ sở dữ liệu quy chiếu cho mỗi 
mẫu có chiều dài k và lặp lại quá trình để tìm 
kiếm mẫu có chiều dài k+1. Hướng tiếp cận 
này sử dụng kỹ thuật chia để trị, việc tạo cơ 
sở dữ liệu quy chiếu là một giải pháp nhằm 
làm giảm không gian tìm kiếm. Có một số 
thuật toán theo phương pháp tiếp cận như 
FreeSpan, PrefixSpan, Wap-mine, Prism... và 
các biến thể của chúng 
(1) Thuật toán FreeSpan, PrefixSpan: Tiếp 
cận theo hướng chia nhỏ dữ liệu, FreSpan[6] 
là thuật toán đầu tiên thực hiện phép chiếu 
trên cơ sở dữ liệu để giảm chi phí dữ liệu. Sau 
đó, thuật toán này được phát triển thành 
PrefixSpan [11]. Xuất phát từ tập mẫu dãy có 
độ dài 1, PrefixSpan tạo ra cơ sở dữ liệu được 
chiếu với mỗi mẫu đó. Trong cơ sở dữ liệu 
quy chiếu, mỗi dãy 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ởi những item phổ biến tìm được 
trong cơ sở dữ liệu được chiếu, quá trình này 
lặp đi lặp lại cho đến khi cơ sở dữ liệu chiếu 
không còn item phổ biến nào. Tuy nhiên khi 
phát triển mẫu cả FreeSpan, PrefixSpan đều 
phải thực hiện chiếu cơ sở dữ liệu và duyệt cơ 
sở dữ liệu quy chiếu để tìm item phổ biến. 
Hình 4. Xây dựng cơ sở dữ liệu quy chiếu 
trong PrefixSpan 
Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131
128 
(2) Thuật toán Wap-mine: Wap-mine [7] sử 
dụng kỹ thuật cấu trúc cây WAP-tree, trong 
kỹ thuật này cơ sở dữ liệu được duyệt hai lần 
để xây dựng cây WAP-tree từ các dãy phổ 
biến cùng với độ hỗ trợ của chúng. Một bảng 
được gọi là “header table” được sử dụng để 
chỉ sự xuất hiện lần đầu của item trong các 
tập phổ biến, nó được sử dụng để theo dõi các 
luồng trong khai phá cây. Wap-mine có hiệu 
quả trong việc hạn chế sinh các ứng viên, tuy 
nhiên lại phát sinh vấn đề tiêu thụ bộ nhớ do 
việc xây dựng lặp lại nhiều cây WAP-tree 
trung gian. 
Hình 5. Khai phá cây WAP – tree trong thuật 
toán WAP – Mine 
(3) Thuật toán Prism: Thuật toán Prism [2] 
sử dụng phương pháp mã hóa nguyên tố để 
biểu diễn thông tin của mẫu ứng viên và sử 
dụng cấu trúc dữ liệu cây từ điển để lưu trữ 
các mẫu dãy tuần tự. Thuật toán chỉ duyệt cơ 
sở dữ liệu đúng một lần để tìm tập mẫu dãy 
tuần tự có độ dài 1 cùng với khối mã hóa 
thông tin tương ứng cho các mẫu đó. Sau đó, 
phát triển mẫu bằng cách thêm vào mẫu một 
item phổ biến. Thông tin của mẫu mới được 
xác định dựa trên khối mã hóa của mẫu cũ và 
của item thêm vào, độ hỗ trợ của các ứng 
viên được xác định trực tiếp từ khối mã hóa 
nguyên tố. Như vậy, thuật toán Prism không 
phải duyệt cơ sở dữ liệu nhiều lần, đồng thời 
thuật toán làm giảm chi phí tính toán bằng 
cách sử dụng bảng tra cho khối mã hóa thông 
tin dựa trên lý thuyết mã hóa nguyên tố. 
Các thuật toán theo phương pháp tiện cận 
phát triển mẫu về cốt lõi dựa trên các đặc 
điểm chính sau [5]: 
- Phân vùng không gian tìm kiếm: Giải pháp 
cho phép phân vùng không gian tìm kiếm 
trong trường hợp số lượng lớn các dãy ứng 
viên được sinh ra giúp cho việc quản lý bộ 
nhớ hiệu quả hơn. Sau khi phân vùng không 
gian tìm kiếm, các phân vùng nhỏ có thể được 
khai phá song song. 
Hình 6. Không gian tìm kiếm mẫu dãy và mã hóa 
nguyên tố cho mẫu mở rộng trong Prism 
- Cây quy chiếu: Các thuật toán sử dụng cấu 
trúc dữ liệu cây để biểu diễn không gian tìm 
kiếm và sau đó sử dụng phương pháp duyệt 
theo chiều rộng hoặc duyệt theo chiều sâu để 
tìm kiếm các dãy phổ biến và tỉa các ứng viên 
dựa trên nguyên lý Apriori. 
- Duyệt theo theo chiều sâu: kỹ thuật duyệt 
cây theo chiều sâu được xem là một trong 
những tính chất quan trọng trong các thuật 
toán sử dựng mô hình cây. Theo một số 
nghiên cứu [2][15][1][4] nó được đánh giá 
cao và thực hiện rất hiệu quả vì sử dụng ít bộ 
nhớ hơn và định hướng không gian tìm kiếm 
do đó tạo ra số lượng ứng viên ít hơn kỹ thuật 
duyệt theo chiều rộng. 
- Tỉa các dãy ứng viên: Giải pháp tỉa trước 
các dãy ứng viên giúp việc biểu diễn không 
gian tìm kiếm nhỏ hơn và duy trì một thủ tục 
tìm kiếm có hướng và phạm vi hẹp hơn. Phần 
lớn các thuật toán này sử dụng kỹ thuật tìm 
kiếm theo chiều sâu và ứng dụng tính chất 
phản đơn điệu của nguyên lý Apriori. 
CÁC HẠN CHẾ VÀ MỘT SỐ VẤN ĐỀ 
MỞ RỘNG 
Thông qua một số vấn đề thảo luận ở trên, có 
rất nhiều các kỹ thuật hiệu quả và các biến thể 
của chúng được đề xuất, cung cấp cho chúng 
ta các giải pháp hiệu quả trong nhiều trường 
hợp. Tuy nhiên các kỹ thuật này vẫn còn một 
số hạn chế mà đến nay vẫn đang là những trở 
ngại và thách thức trong quá trình thực hiện 
khai phá mẫu dãy: 
Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131
129 
- Các thuật toán theo hướng tiếp cận dựa trên 
Apriori, với cơ sở dữ liệu dãy lớn nó sẽ tạo ra 
một lượng rất lớn các ứng viên. Mặt khác, 
trong quá trình khai phá kỹ thuật này đòi hỏi 
phải duyệt cơ sở dữ liệu gốc nhiều lần. 
- Trong hướng tiếp cận phát triển mẫu, chi 
phí chủ yếu của các kỹ thuật này là việc xây 
dựng cơ sở dữ liệu quy chiếu. Trong trường 
hợp xấu nhất, chúng ta phải xây dựng cơ sở 
dữ liệu quy chiếu cho mọi mẫu, với số lượng 
mẫu lớn thì chi phí này là không tầm thường. 
- Trong quá trình khai phá có thể tạo ra lượng 
lớn các mẫu dãy phổ biến, nhưng người sử 
dụng chỉ quan tâm một lượng nhỏ các mẫu có 
ích trong đó phù hợp với mục tiêu sử dụng, 
việc biểu diễn toàn bộ các mẫu gây khó khăn 
cho việc sử dụng. 
- Khó khăn trong quá trình khai phá các 
mẫu dãy dài bởi vì các mẫu này phải được 
phát triển từ một lượng lớn các mẫu ngắn, 
vì thế số lượng các ứng viên được sinh ra sẽ 
là cấp số nhân. 
Khai phá mẫu dãy đã được tập chung 
nghiên cứu mạnh mẽ trong những năm gần 
đây. Với các mục đích ứng dụng khác nhau 
tạo ra một lượng lớn sự đa dạng các thuật 
toán khai phá mẫu dãy, nhiều phần mở rộng 
của các định nghĩa ban đầu được đề xuất 
cho các mục đích đặc biệt như khai phá dãy 
mẫu với những rành buộc, mẫu dãy đóng, 
đa chiều, gia tăng 
Khai phá mẫu dãy đa chiều 
Mẫu dãy đơn chiều là chúng ta chỉ xem xét 
một thuộc tính cùng với các nhãn thời gian 
trong quá trình khai phá. Trong khi đó, với 
mẫu dãy đa chiều chúng ta có thể xem xét 
nhiều thuộc tính cùng một lúc. Khai phá mẫu 
dãy tuần tự đa chiều được giới thiệu bởi 
Helen Pinto và JiaweiHan [8] có thể cung cấp 
cho chúng ta các mẫu hữu ích và mang nhiều 
thông tin hơn. 
Khai phá mẫu dãy đóng 
Các thuật toán khai phá mẫu dãy được phát 
triển cho đến nay có hiệu suất tốt trong cơ sở 
dữ liệu có chứa các dãy phổ biến ngắn. Tuy 
nhiên, khi khai thác các dãy phổ biến dài, 
hoặc khi sử dụng ngưỡng hỗ trợ rất thấp, hiệu 
suất của các thuật toán trên thường giảm đáng 
kể. Ví dụ cơ sở dữ liệu chỉ chứa một dãy phổ 
biến , nó sẽ tạo ra 2100-1 
dãy phổ biến nếu ngưỡng tối thiểu là 1, mặc 
dù tất cả các dãy phổ biến này ngoại trừ dãy 
dài nhất là không cần thiết. Vì vậy, một giải 
pháp đề xuất thay vì khai thác tập toàn bộ các 
mẫu dãy phổ biến, chúng ta chỉ khai thác dãy 
phổ biến đóng, nghĩa là chỉ lấy tập các mẫu 
dãy phổ biến mà chúng không được chứa dãy 
phổ biến khác có cùng độ hỗ trợ [15][16]. Kỹ 
thuật này sẽ tạo ra một số lượng dãy ít hơn 
đáng kể so với dãy kỹ thuật truyền thống 
trong khi vẫn giữ được tính hiệu quả. 
Khai phá mẫu dãy dựa vào các ràng buộc 
Mặc dù hiệu quả của việc khai phá tập toàn 
bộ các mẫu dãy đã được cải thiện đáng kể dựa 
trên nhiều kỹ thuật được đề xuất. Tuy nhiên, 
trong nhiều trường hợp khai phá mẫu dãy vẫn 
phải đối mặt với các thách thức trong cả hai 
vấn đề hiệu suất và tính hiệu quả. Mặt khác, 
trong số lượng lớn các mẫu dãy, người sử 
dụng có thể chỉ quan tâm đến một nhóm nhỏ 
các mẫu trong đó. Nếu biểu diễn toàn bộ các 
mẫu có thể làm cho kết quả khó hiểu và khó 
sử dụng. Để khắc phục vấn đề này Jian Pei, 
JiaweiHan, Weiwang [5] đã giới thiệu hệ 
thống các ràng buộc được đưa vào phương 
pháp phát triển mẫu để khai phá mẫu dãy. 
Những ràng buộc này có thể được xem như 
những bộ lọc được áp dụng cho việc trích 
xuất các mẫu dãy. Khai phá mẫu dựa vào ràng 
buộc có thể vượt qua những khó khăn về hiệu 
suất và tính hiệu quả khi tập trung khai phá 
các mẫu dựa vào các ràng buộc phù hợp với 
lợi ích người sử dụng, hạn chế số lượng các 
mẫu tìm được trong một tập con đáp ứng các 
điều kiện mạnh. 
Khai phá mẫu dãy gia tăng 
Các thuật toán khai khá dữ liệu có độ phức 
tạp tính toán cao, do đó nếu sử dụng các giải 
pháp truyền thống thì khi thêm bản ghi dữ 
liệu mới phải khai phá lại từ đầu sẽ tiêu tốn 
một lượng thời gian lớn. Vì thế, có một 
hướng tiếp cận mới cho nội dung này gọi là 
khai phá mẫu dãy gia tăng. Ý tưởng chính của 
hướng tiếp cận này là khi thêm một lượng dữ 
liệu vào cơ sở dữ liệu thì phần dữ liệu gia 
tăng này được duyệt qua và kết hợp với các 
Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131
130 
mẫu dãy phổ biến đã được phát hiện trong lần 
khai phá trước nhằm xác định các thành phần 
của cơ sở dữ liệu ban đầu cần duyệt lại. Do 
vậy không cần phải duyệt lại toàn bộ cơ sở dữ 
liệu gốc. Một số thuật toán khai phá mẫu dãy 
gia tăng [5] được phát triển dựa trên các thuật 
toán GSP, SPADE và một số thuật toán mới 
được đề xuất như IUS, ISE, KISP. 
KẾT LUẬN 
Hiện nay, khai phá mẫu dãy có vai trò quan 
trọng. Nó hỗ trợ hiệu quả trong việc tìm kiếm 
các mối quan hệ giữa các dữ liệu. Trong nội 
dụng bài báo này, chúng tôi đã khảo sát và 
tông hợp các vấn đề cơ bản về khai thác mẫu 
dãy và các phương pháp cơ bản được sử dụng 
trong khai phá mẫu dãy. Trong thực tế, dữ 
liệu luôn được bổ sung và cập nhật liên tục 
trong cơ sở dữ liệu, việc khai phá mẫu dãy 
phổ biến luôn được quan tâm nghiên cứu. Các 
thuật toán khác nhau được phát triển để khai 
phá mẫu dãy trong dữ liệu, chúng đã chứng 
minh được tính hiệu quả cho các cơ sở dữ liệu 
nhỏ nhưng khi kích thước của cơ sở dữ liệu 
liên tục tăng lên, hiệu suất của các thuật toán 
này có thể giảm đáng kể. Do đó các phương 
pháp phải được cải thiện hoặc đề xuất mới để 
thực hiện quá trình khai phá một cách tốt hơn. 
TÀI LIỆU THAM KHẢO 
[1]. ANTUNES, C. AND OLIVEIRA, A. L. 2004. 
Sequential pattern mining algorithms: Trade-offs 
between speed and memory. In Proceedings of the 
Workshop on Mining Graphs, Trees and 
Sequences (MGTSECML/PKDD ’04). 
[2]. AYRES, J., FLANNICK, J.,GEHRKE, J., 
AND YIU, T. 2002. Sequential pattern mining 
using a bitmap representation. In Proceedings of 
the 8th ACM SIGKDD International Conference 
on Knowledge Discovery and Data Mining. 
429–435. 
[3]. Ayres, J., Gehrke, J.E., Yiu, T., Flannick, J. 
(2002), “Sequential Pattern Mining using a 
Bitmap Representaion”, in SIGKDD Conf., pp. 
1–7. 
[4]. EZEIFE, C. I. AND LU, Y. 2005. Mining web 
log sequential patterns with position coded pre-
order linked WAP-tree. Int. J. Data Mining 
Knowl. Discovery 10, 5–38. 
[5]. F. Masseglia, P. Poncelet, M. Teisseire 
(2000), "Incremental Mining of Sequential 
Patterns in Large Databases", BDA'OO, France 
[6]. Han, J., Pei, J., Mortazavi-Asl, B., Chen, 
Q., Dayal, U., and Hsu, M.C., (2000), 
“Freespan: Frequent pattern-projected 
sequential pattern mining”, in Proc. 2000 Int. 
Conf. Knowledge Discovery and Data Mining 
(KDD’00), pp. 355–359. 
[7]. Han, J., Pei, J., Mortazavi-Asl, B. and Zhu, 
H., “Mining access patterns efficiently from web 
logs”, In Proceedings of the Pacific- Asia 
Conference on Knowledge Discovery and Data 
Mining (PAKDD’00) Kyoto Japan, 2000. 
[8]. Helen Pinto Jiawei Han Jian Pei Ke Wang, 
“Multidimensional Sequential Pattern Mining”, In 
Proc. 2001 Int. Conf. Information and Knowledge 
Management (CIKM’01), Atlanta, GA, Nov. 2001 
pp. 81–88. 
[9]. Jian Pei, Jiawei Han, Wei Wang, “Constraint-
based sequential pattern mining: the pattern 
growth methods”, J Intell Inf Syst , Vol. 28, No.2, 
,2007, pp. 133 –160. 
[10]. NIZAR R. MABROUKEH and C. I. 
EZEIFE, “A Taxonomy of Sequential Pattern 
Mining Algorithms”, ACM Computing Surveys, 
Vol. 43, No. 1, Article 3, Publication date: 
November 2010. 
[11]. Pei, J., et al. (2004), “Mining Sequential 
Patterns by Pattern-Growth: The PrefixSpan 
Approach”, in: IEEE Trans. Knowledge and Data 
Engineering 16(10), pp. 1424–1440. 
[12]. Qiankun Zhao. Sourav S.Bhowmick, 
“Sequential Pattern Mining: A Survey”, Technical 
report, CAIS, Nanyang Technological University, 
Singgapore, No. 2003118, 2003. 
[13]. Rakesh Agrawal Ramakrishna Srikant, 
“Mining Sequential Patterns” , 11th Int. Conf. on 
Data Engineering, IEEE Computer Society Press, 
Taiwan, 1995 pp. 3-14 
[14]. Srikant R. and Agrawal R., “Mining 
sequential patterns: Generalizations and 
performance improvements”, Proceedings of the 
5th International Conference Extending Database 
Technology, 1996, 1057, 3-17. 
[15]. Wang, J. and Han, J. 2004. BIDE: Efficient 
mining of frequent closed sequences. In 
Proceedings of the 20th International Conference 
on Data Engineering. 79–90. 
[16]. Yan, X., Han, J., and Afshar, R. (2003), 
“CloSpan: Mining Closed Sequential Patterns in 
Large Databases”, in: Proceedings of SIAM 
International Conference on Data Mining 
[17]. Zaki, M.J. (2000), “SPADE: An Efficient 
Algorithm for Mining Frequent Sequences”, 
Machine Learning Journal 42(1/2), pp. 31–60. 
Quách Xuân Trường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131
131 
SUMMARY 
RESEARCHES OF SEQUENTIAL PATTERN MINING ALGORITHMS IN 
SEQUENTIAL DATA 
Quach Xuan Truong*, Nguyen Van Su, Dinh Duc Hoang 
College of Information Technology and Communications – TNU 
Sequential pattern mining is an important data mining problem with broad applications such as 
market analysis, web access, pattern analysis, intrusion detection in network environment, in DNA 
research, and predicting the shopping needs of customers. Sequential pattern mining discovers 
frequent subsequences as patterns in sequence database. Since introduced by Agrawaland Srikant, 
now, this problem has attracted a lot of researchers and there are many techniques proposed. The 
very first was Apriori-based algorithm, later more scalable algorithms for complex applications 
were developed. This paper presents and analyzes the techniques by clustering techniques in three 
main groups: apriori-based, pattern-growth, early-pruning. This paper also compares different 
techniques based on the important key features and discusses some challenges in which existing 
research is focused 
Key words: Sequential patterns, apriori based, pattern growth, Sequence database, pattern 
analysis. 
Ngày nhận bài: 13/3/2014; Ngày phản biện: 15/3/2014; Ngày duyệt đăng: 25/3/2014 
Phản biện khoa học: TS. Vũ Đức Thái – Trường ĐH CNTT&TT – ĐH Thái Nguyên 
*
 Tel: 0989090832; Email: qxtruong@ictu.edu.vn