Cấu trúc của các chuỗi phổ biến dựa trên các chuỗi đóng và chuỗi sinh

KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 
15 
CẤU TRÚC CỦA CÁC CHUỖI PHỔ BIẾN 
DỰA TRÊN CÁC CHUỖI ĐÓNG VÀ CHUỖI SINH 
Tô Lan Nhia, Trần Ngọc Anha*, Dương Văn Hảia, Trương Chí Tína 
aKhoa Toán - Tin học, Trường Đại học Đà Lạt, Lâm Đồng, Việt Nam 
*Tác giả liên hệ: Email: anhtndalat@gmail.com 
Tóm tắt 
Bài toán khai thác các chuỗi phổ biến từ các cơ sở dữ liệu có nhiều ứng dụng trong thực tiễn 
như thương mại, truyền thông, kinh tế, v.v. Khó khăn lớn nhất của bài toán là không gian tìm 
kiếm và lực lượng của tập các chuỗi phổ biến thường rất lớn (đặc biệt trên các cơ sở dữ liệu 
lớn với các ngưỡng phổ biến tối thiểu bé). Các thuật toán khai thác chúng thường tiêu tốn 
quá nhiều thời gian và bộ nhớ. Ngoài ra, người sử dụng khó khăn trong việc hiểu và quản lý 
số lượng quá lớn tập này. Gần đây, một số tác giả đã đề xuất việc khai thác các chuỗi phổ 
biến đóng và các chuỗi sinh phổ biến với số lượng thường bé hơn hẳn so với số lượng các 
chuỗi phổ biến. Các tác giả đã chỉ ra rằng, từ chúng, ta có thể thu được tất cả các chuỗi phổ 
biến khác, tuy nhiên, chưa có một thuật toán tương ứng nào được đề xuất. Bài bào này chỉ 
ra cấu trúc của các chuỗi phổ biến dựa trên các chuỗi phổ biến đóng và các chuỗi sinh phổ 
biến. Dựa trên cấu trúc này, ta có thể phục hồi tất cả các chuỗi phổ biến từ các chuỗi phổ 
biến đóng và các chuỗi sinh phổ biến mà không cần quét lại cơ sở dữ liệu. Quá trình phục 
hồi này có thể tạo ra nhiều chuỗi trùng lặp, do đó, ta phải tốn bộ nhớ để lưu trữ và mất thời 
gian kiểm tra để loại bỏ chúng. Để khắc phục khó khăn này, báo cáo đề xuất hai điều kiện 
để tỉa sớm các chuỗi phổ biến trùng lặp trong quá trình phục hồi. 
Từ khóa: Khai thác chuỗi phổ biến; chuỗi phổ biến đóng; chuỗi sinh phổ biến. 
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 
16 
STRUCTURE OF FREQUENT SEQUENCES BASED ON 
FREQUENT CLOSED SEQUENCES AND FREQUENT 
GENERATORS 
Tô Lan Nhia, Tran Ngọc Anha*, Duong Van Haia, Truong Chi Tina 
aThe Faculty of Mathematics and Computer Science, Dalat University, Lamdong, Vietnam 
*Corresponding author: Email: anhtndalat@gmail.com 
Abstract 
Frequent sequence mining from database has many real applications such as 
communication, business, economic, etc. The main difficulty of the problem is that the search 
space and the cardinality of the set of frequent sequences are often enormous (especially on 
big databases with small minimum support thresholds). The proposed algorithms for mining 
them consume much memory and time. Furthermore, it is hard to the users for understanding 
and processing the result. Recently, some authors propose the mining of frequent closed 
sequences and generators of which the cardinalities are usually smaller than that of frequent 
sequences. They also show that, based on them, we can recover all remaining frequent 
sequences. However, there is no algorithm for doing that. The paper gives the structure of 
frequent sequences based on frequent closed sequences and frequent generators. Thanks to 
the structure, all frequent sequences can be recovered without accessing the database. Since 
the recovery can make many duplications, it needs to save and check to eliminate them. To 
overcome this drawback, the paper proposes two pruning conditions and uses them to early 
prune duplications in the progress of recovering frequent sequences. 
Keywords: Frequent sequence mining; frequent closed sequence; generator. 
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 
17 
1. GIỚI THIỆU 
Khai thác dữ liệu là tiến trình rút trích các thông tin hoặc mẫu hữu ích (tường 
minh, không tầm thường, chưa được biết trước đây) từ các nguồn dữ liệu lớn (như: các 
cơ sở dữ liệu, các kho dữ liệu) thu thập được từ các ngành khoa học, kinh doanh và kỹ 
thuật. Khai thác dữ liệu là một phần cơ bản trong quá trình khám phá tri thức từ dữ liệu. 
Quá trình này thường chứa ba bước (Han và Kamber, 2000). Ở bước đầu tiên, dữ liệu 
được xử lý thô qua các công đoạn sau: làm sạch dữ liệu, tích hợp dữ liệu, chọn các đặc 
trưng hữu ích, rút gọn số biến/số chiều dữ liệu, biến đổi/rời rạc hóa dữ liệu. Sau đó, các 
thuật toán khai thác dữ liệu được áp dụng để rút trích ra các thông tin, tri thức tiềm ẩn. 
Kết quả khai thác được đánh giá ở bước hậu xử lý dựa trên yêu cầu của người sử dụng 
hoặc tri thức biết trước. Nếu kết quả không phù hợp, ta cần lặp lại quá trình. 
Khai thác chuỗi phổ biến (Agrawal và Srikant, 1995) là một bài toán khó, đóng 
vai trò quan trọng trong khai thác dữ liệu và có nhiều ứng dụng rộng rãi trong truyền 
thông, thương mại, v.v. Đã có nhiều thuật toán được đề xuất để khai thác các chuỗi phổ 
biến từ các cơ sở dữ liệu. Thuật toán PrefixSpan (Pei và ctg, 2004) sử dụng định dạng dữ 
liệu theo chiều ngang, tiếp cận phát triển mẫu và các cơ sở dữ liệu chiếu. Các thuật toán 
SPADE (Zaki, 2001), SPAM (Ayres và ctg, 2002) sử dụng định dạng theo chiều dọc và 
cấu trúc bitmap. Những cải tiến của chúng như CM-SPADE, CM-SPAM (Philip và ctg, 
2014a) sử dụng thông tin đồng xuất hiện của các cặp thuộc tính phổ biến để tỉa sớm các 
chuỗi cha không phổ biến. Điểm chung của các thuật toán đã đề cập ở trên là khai thác 
các chuỗi phổ biến trực tiếp từ cơ sở dữ liệu. Tuy nhiên, trên các cơ sở dữ liệu lớn, đặc 
biệt với các ngưỡng hỗ trợ tối thiểu bé, không gian tìm kiếm và lực lượng của tập các 
chuỗi phổ biến (ký hiệu là ℱ𝑟𝑒𝒮) quá lớn. Do đó, các thuật toán tiêu tốn quá nhiều bộ 
nhớ và chạy rất lâu trước khi cho ra kết quả. 
Một tiếp cận gần đây hướng về việc tìm tập các chuỗi phổ biến tối đại (ký hiệu là 
ℱℳ𝑎𝑥𝒮) và sử dụng nó để tìm các chuỗi phổ biến. Chúng không chỉ cho phép rút gọn 
việc tính toán và lưu trữ mà còn giúp phân tích kết quả dễ dàng hơn. Các chuỗi phổ biến 
tối đại (mọi chuỗi cha thật sự của một chuỗi phổ biến tối đại đều không là chuỗi phổ biến) 
với số lượng bé hơn nhiều có thể xác định được lớp tất cả các chuỗi phổ biế ...  cần quét lại cơ sở dữ liệu. Để sinh ra các chuỗi phổ biến còn lại 
trong cùng lớp, ta chỉ cần bổ sung thêm các chuỗi con của chuỗi đóng vào các chuỗi sinh. 
Quá trình phục hồi theo cách này có thể tạo ra các chuỗi phổ biến trùng lặp (trong cùng 
lớp), do đó, ta phải tốn bộ nhớ để lưu trữ và mất thời gian kiểm tra để loại bỏ chúng. 
3. CẤU TRÚC CỦA LỚP TƯƠNG ĐƯƠNG CÁC CHUỖI PHỔ BIẾN 
Không mất tính tổng quát, trong phần này ta luôn xét lớp tương đương 𝓉𝓈, 𝓉𝓈 ∈
𝒯𝒮. Gọi Clo(𝓉𝓈) ≝ {σ ∈ ℱ𝒞𝑙𝑜𝒮 | ts(σ) = 𝓉𝓈} (5) 
4Ký hiệu Σ biểu thị phép hợp của các tập rời nhau. 
5Từ nay về sau ta luôn sử dụng giá trị này của 𝒯𝒮. 
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 
22 
là tập các chuỗi đóng trong ℱ𝒮(𝓉𝓈). 
Một nguyên nhân dẫn đến trùng lặp trong quá trình phục hồi các chuỗi phổ biến 
trong lớp tương đương 𝓉𝓈 là: nó có thể chứa nhiều chuỗi đóng (|Clo(𝓉𝓈)| ⩾ 1) và chứa 
các chuỗi là chuỗi sinh đồng thời của các chuỗi đóng đó (kiểu trùng lặp 2). Để loại bỏ 
trùng lặp kiểu này, ta chia nhỏ lớp tương đương các chuỗi phổ biến thành các lớp con 
(mức 1) dựa vào các chuỗi đóng trong lớp. Điều kiện tỉa CloPrun được đề xuất và áp 
dụng để khử bỏ sự trùng lặp giữa các lớp con. Khó khăn và cách giải quyết tương tự cũng 
được áp dụng để khử bỏ sự trùng lặp (kiểu 3) với GenPrun khi phục hồi các chuỗi trong 
mỗi lớp con mức 1. 
3.1. Phân hoạch lớp tương đương các chuỗi phổ biến thành các lớp con mức 1 
dựa vào các chuỗi đóng 
Vì |Clo(𝓉𝓈)| ⩾ 1, ta chia nhỏ lớp tương đương ℱ𝒮(𝓉𝓈) thành các lớp con mức 1. 
Mỗi lớp con là một tập tất cả các chuỗi phổ biến của ℱ𝒮(𝓉𝓈) chứa trong một chuỗi đóng 
cùng thuộc ℱ𝒮(𝓉𝓈), 
ℱ𝒮(𝓉𝓈) = ⋃ ℱ𝒮(σ୧)஢౟∊େ୪୭(𝓉𝓈) , (6) 
với, ℱ𝒮(σ୧) ≝ {α ∈ [σ୧] | α ⊑ σ୧} = {α ⊑ σ୧ | ts(α) = ts(σ୧) = 𝓉𝓈}, σ୧ ∈ Clo(𝓉𝓈) (7) 
Có thể thấy rằng {ℱ𝒮(σ୧), σ୧ ∊ Clo(𝓉𝓈)} không là một phân hoạch của ℱ𝒮(𝓉𝓈). 
Tức là có thể tồn tại một chuỗi phổ biến α của ℱ𝒮(𝓉𝓈) thuộc cả lớp con ℱ𝒮(σ୧) lẫn lớp 
con ℱ𝒮(σ୨) với 𝑖 ≠ 𝑗, σ୧, σ୨ ∊ Clo(𝓉𝓈). Như vậy, quá trình phục hồi các chuỗi phổ biến 
thuộc ℱ𝒮(𝓉𝓈) dựa vào (7) có thể sinh ra các chuỗi trùng lặp. Ví dụ 4 sẽ chỉ ra điều đó. 
Ví dụ 4. Xét lớp tương đương ứng với 𝓉𝓈ଶ = {tଵ, tଶ, tସ} . Ta có Clo(𝓉𝓈ଶ) =
{σଵ, σଶ, σଷ} , với σଵ = 〈𝐷(𝐴𝐶)A〉 , σଶ = 〈𝐷(𝐴𝐹)〉 , σଷ = 〈(𝐴𝐶𝐸)𝐴(AF)〉 , 𝐺𝑒𝑛(σଵ) =
𝐺𝑒𝑛(σଶ) = {γ = 〈D〉} , 𝐺𝑒𝑛(σଷ) = {γଵ = 〈AAA〉, γଶ = 〈AAF〉, γଷ = 〈EAA〉, γସ =
〈EAF〉}6. 
 Cấu trúc lớp tương đương ứng với 𝓉𝓈ଶ được chỉ ra trong Hình 2. Xét chuỗi 
sinh γ của σଵ và σଶ. 
 Trước hết, ta xét phép bổ sung các chuỗi con của σଵ vào γ. Khi đó, ta có 
ℱ𝒮(σଵ) = {α | γ ⊑ α ⊑
σଵ}{〈D〉, 〈DA〉, 〈DC〉, 〈D(AC)〉, 〈DAA〉, 〈DCA〉, 〈D(AC)A〉} . Bây giờ, xét tiếp 
phép bổ sung các chuỗi con của σଶ cũng vào γ, ta có ℱ𝒮(σଶ) =
{〈𝐷〉, 〈𝐷𝐴〉, 〈𝐷𝐹〉, 〈𝐷(𝐴𝐹)〉}. Nhận xét rằng 〈𝐷〉 và 〈𝐷𝐴〉 xuất hiện trong cả 
ℱ𝒮(σଶ)lẫn ℱ𝒮(σଵ). Khi đó ℱ𝒮(σଶ) ∩ ℱ𝒮(σଵ) = {〈𝐷〉, 〈𝐷𝐴〉} ≠ ∅, nghĩa là 
{ℱ𝒮(σଵ), ℱ𝒮(σଶ), ℱ𝒮(σଷ)} không là một phân hoạch của ℱ𝒮(𝓉𝓈ଶ). Sự trùng 
lặp này xuất hiện vì 〈𝐷〉 đồng thời là chuỗi sinh của σଵ và σଶ. Để loại bỏ 
trùng lặp kiểu 2 này, ta chỉ cần kiểm tra các chuỗi được tạo ra trong quá trình 
6Thông tin này được sử dụng trong các Ví dụ 5, 6. 
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 
23 
bổ sung các chuỗi con của σଶ vào γ có chứa trong σଵ hay không? Nếu có, 
chuỗi đó bị loại. 
Hình 2. Phân hoạch lớp tương đương 𝓕𝓢(𝓽𝓼𝟐). 
Để khử trùng lặp, ta sử dụng điều kiện tỉa CloPrun được định nghĩa như sau: 
∀σ୧ ∈ Clo(𝓉𝓈), ∀α ∈ ℱ𝑟𝑒𝒮: 
CloPrun(α, σ୧) ≝ (∃σ୩ ∈ Clo(𝓉𝓈ଶ) | k < i, α ⊑ σ୩). (8) 
Gọi ℱ𝒮∗(σ୧) ≝ ൛α ∈ ℱ𝒮(σ୧) ห not൫CloPrun(α, σ୧)൯ൟ. (9) 
Dễ thấy rằng, ℱ𝒮∗(σ୧) ⊆ ℱ𝒮(σ୧) , ℱ𝒮∗(σ୧) ∩ ℱ𝒮∗൫σ୨൯ = ∅ (với 𝑖 ≠ 𝑗 , σ୨ ∈
Clo(𝓉𝓈)) và {ℱ𝒮∗(σ୧), σ୧ ∈ Clo(𝓉𝓈)} tạo ra một phân hoạch của ℱ𝒮(𝓉𝓈): 
ℱ𝒮(𝓉𝓈) = ∑ ℱ𝒮∗(σ୧)஢౟∊େ୪୭(𝓉𝓈) . (10) 
Ví dụ 5. Dễ dàng ta có, ℱ𝒮∗(σଵ) = ℱ𝒮(σଵ) . Trong tập ℱ𝒮(σଶ) , hai chuỗi 
〈𝐷〉, 〈𝐷𝐴〉 không vượt qua được CloPrun tại σଵ nên bị loại. Do đó, ℱ𝒮∗(σଶ) =
{〈𝐷𝐹〉, 〈𝐷(𝐴𝐹)〉}. Với σଷ , vì γ୨ ⋢ σଵvà γ୨ ⋢ σଶ , ∀γ୨ ∈ Gen(σଷ) , do đó, không có sự 
trùng lặp giữa ℱ𝒮(σଷ) với ℱ𝒮(σଵ) và ℱ𝒮(σଶ). Khi đó, ℱ𝒮∗(𝜎ଷ) = ℱ𝒮(σଷ). Như vậy, 2 
sự trùng lặp (kiểu 2) giữa các lớp con mức 1 bị loại bỏ bởi điều kiện tỉa CloPrun (xem 
Hình 2)! 
3.2. Phân hoạch lớp con mức 1 thành các lớp con mức 2 dựa vào các chuỗi sinh 
Không mất tổng quát, bây giờ ta xét quá trình phục hồi lớp con mức 1 có đại diện 
là 𝓉𝓈 và chuỗi đóng σ୧ (σ୧ ∈ Clo(𝓉𝓈)), tức là ℱ𝒮∗(σ୧). Giả sử rằng chuỗi đóng σ୧ có 
nhiều hơn một chuỗi sinh (|Gen(σ୧)| > 1), gọi γ୨ và γ୩ là hai chuỗi sinh của nó (γ୨, γ୩ ∈
Gen(σ୧)). Việc bổ sung hai chuỗi con khác nhau của σ୧ vào γ୨ và γ୩ hoàn toàn có thể tạo 
ra cùng một chuỗi kết quả. Do đó, quá trình phục hồi lớp con mức 1, ℱ𝒮∗(σ୧), vẫn có thể 
sinh ra trùng lặp (kiểu trùng lặp 3)! Xem minh họa trong Hình 3. 
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 
24 
Hình 3. Phân hoạch mịn lớp tương đương 𝓕𝓢(𝓽𝓼𝟐) 
Hình thức hơn, nếu ký hiệu 
ℱ𝒮൫σ୧, γ୨൯ = ൛𝛼 ∊ ℱ𝒮∗(σ୧) | 𝛼 ⊒ 𝛾௝ൟ = ൛𝛼 | 𝛾௝ ⊑ 𝛼 ⊑ 𝜎௜ൟ (11) 
là lớp (con mức 2) chứa các chuỗi tạo ra từ phép bổ sung các chuỗi con của σ୧ vào chuỗi 
sinh γ୨ của nó. Khi đó, giữa ℱ𝒮൫σ୧, γ୨൯ và ℱ𝒮(σ୧, γ୫) vẫn có thể có phần giao chung 
trùng lặp (tức là, ℱ𝒮൫σ୧, γ୨൯ ∩ ℱ𝒮(σ୧, γ୫) ≠ ∅ ) với m ≠ j , γ୫ ∈ Gen(σ୧) . Với γ୨ ∈
Gen(σ୧), ∀𝛼 ∈ ℱ𝑟𝑒𝒮, định nghĩa điều kiện tỉa GenPrun như sau: 
GenPrun൫α, σ୧, γ୨൯ ≝ (∃γ୩ ∈ Gen(σ୧) | k < j, α ⊒ γ୩ ). (12) 
Gọi 
ℱ𝒮∗൫σ୧, γ୨൯ ≝ ቄ𝛼 ∈ ℱ𝒮∗(σ୧) ቚ α ⊒ γ୨ ∧ not ቀGenPrun൫α, σ୧, γ୨൯ቁቅ (13)
là tập các chuỗi tạo ra từ chuỗi sinh γ୨. Khi đó, ℱ𝒮∗൫σ୧, γ୨൯ ∩ ℱ𝒮∗(σ୧, γ୫) = ∅ 
(với m ≠ j, γ୫ ∈ Gen(σ୧)) và ൛ℱ𝒮∗൫σ୧, γ୨൯, γ௝ ∈ Gen(σ୧)ൟ tạo ra một phân hoạch của 
ℱ𝒮∗(σ୧): 
ℱ𝒮∗(σ୧) = ∑ ℱ𝒮∗൫σ୧, γ୨൯ஓౠ∈ୋୣ୬(஢౟) . (14) 
Ví dụ 6. Ta xét quá trình phục hồi từng lớp con ℱ𝒮∗(σ୧), i=1,2,3. Xem minh họa 
trong Hình 3. 
 Vì σଵ và σଶ chỉ có một chuỗi sinh nên quá trình phục hồi ℱ𝒮∗(σଵ) và 
ℱ𝒮∗(σଶ) không tạo ra trùng lặp (kiểu 3). 
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 
25 
 Xét quá trình phục hồi các chuỗi thuộc lớp con ℱ𝒮∗(σଷ). Vì |Gen(σଷ)| = 3, 
nên quá trình phục hồi sẽ tạo ra các trùng lặp. Để thuận tiện, đặt σ = σଷ =
〈(ACE)A(AF)〉. 
 Đầu tiên, ta có, ℱ𝒮(σ, γଵ = 〈AAA〉) = {〈AAA〉, α = 〈AA(AF)〉, 〈(AC)AA〉, 
〈(AC)A(AF)〉, 〈(AE)A(A)〉, 〈(AE)A(AF)〉, 〈(ACE)AA〉, 〈(ACE)A(AF〉} và 
ℱ𝒮∗(σ, γଵ) = ℱ𝒮(σ, γଵ). 
 Tiếp theo, FS൫σ,γ2=〈AAF〉൯={〈AAF〉, α=〈AA(AF)〉, 
〈(AC)AF〉,〈(AC)A(AF)〉, 
〈(AE)AF〉, 〈(AE)A(AF)〉, 〈(ACE)AF〉, 〈(ACE)A(AF)〉}. Dễ thấy rằng αtrong 
ℱ𝒮(σ, γଶ) đã xuất hiện trong ℱ𝒮(σ, γଵ) bởi vì bổ sung A vào đầu sự kiện cuối 
cùng của γଶ cũng chính là bổ sung F vào sau sự kiện cuối cùng của γଵ (tạo ra 
cùng α). Nếu sử dụng GenPrun trên γଵ khi thực hiện phép bổ sung vào γଶ, 
ta đã loại bỏ (sớm) được α vì α ⊒ γଵ. Tương tự ta cũng loại sớm được các 
chuỗi 〈(AC)A(AF)〉, 〈(EC)A(AF)〉và 〈(ACE)A(AF)〉. Khi đó, ℱ𝒮∗(σ, γଶ) =
{〈AAF〉, 〈(AC)AF〉, 〈(AE)A(AF)〉, 〈(ACE)AF〉} và ℱ𝒮∗(σ, γଵ) ∩
ℱ𝒮∗(σ, γଶ) = ∅. Như vậy, 4 sự trùng lặp (kiểu 3) giữa các lớp con mức 2 
cũng bị loại bỏ! 
 Sau đó, ℱ𝒮(σ, γଷ = 〈EAA〉) = 〈EAA〉, 〈EA(AF)〉, βଵ = 〈(EA)AA〉, βଶ = 
〈(EA)A(AF)〉, 〈(EC)AA〉, 〈(EC)A(AF)〉, βଷ = 〈(EAC)AA〉, βସ =
〈(EAC)A(AF)〉}. Bốn chuỗi β୩, k = 1,4തതതത không vượt qua GenPrun(α, σ, γଷ) 
vì β୩ ⊒ γଵ. Do đó, ℱ𝒮∗(σ, γଷ) {〈EAA〉, 〈EA(AF)〉, 〈(EC)AA〉, 〈(EC)A(AF)〉}. 
 Cuối cùng, ℱ𝒮(σ, γସ = 〈EAF〉) = {δଵ = 〈EAF〉, δଶ = 〈EA(AF)〉, δଷ =
〈(EA)AF〉, δସ = 〈(EA)A(AF)〉, δହ = 〈(EC)AF〉, δ଺ = 〈(EC)A(AF)〉, δ଻ =
〈(EAC)AF〉, δ଼ = 〈(EAC)A(AF)〉}. Sáu chuỗi δସ, δ଼ (chứa γଵ); δଷ, δ଻ (chứa 
γଶ); δଶ, δ଺ (chứa γଷ) không vượt qua GenPrun(α, σ, γସ) nên chúng bị loại. 
Cho nên, ℱ𝒮∗(σ, γଷ) = {δଵ, δହ}. 
3.3. Phân hoạch mịn tập các chuỗi phổ biến 
Sau khi loại bỏ được các trùng lặp (kiểu 2 và 3), ta có được một phân hoạch mịn 
(so với phân hoạch thô dựa trên (4)) tập ℱ𝑟𝑒𝒮 các chuỗi phổ biến. Thật vậy, từ (4), (10) 
và (14) ta có: 
ℱ𝑟𝑒𝒮 = ∑ ∑ ∑ ℱ𝒮∗൫σ௜ , γ௝൯ஓౠ∈ୋୣ୬(஢౟)ఙ೔∈େ୪୭(𝓉𝓈)𝓉𝓈∈𝒯𝒮 . (15) 
Điều đó có nghĩa là, ൛ℱ𝒮∗൫σ௜ , γ௝൯, 𝓉𝓈 ∈ 𝒯𝒮, 𝜎௜ ∈ Clo(𝓉𝓈), γ୨ ∈ Gen(σ୧)ൟ tạo ra 
một phân hoạch mịn của ℱ𝑟𝑒𝒮. Dựa vào nó, ta có thể phục hồi nhanh tất cả các chuỗi phổ 
biến chỉ dựa vào lớp ℱ𝒞𝑙𝑜𝒮 các chuỗi phổ biến đóng và lớp ℱ𝒢𝑒𝑛𝒮 các chuỗi sinh phổ 
biến mà không cần quét lại CSDL. 
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 
26 
Ví dụ 7. Như vậy là dựa vào tất cả 3 chuỗi phổ biến đóng σଵ , σଶ và σଷ (của 
Clo(𝓉𝓈ଶ)); tất cả 5 chuỗi sinh phổ biến γ, γଵ, γଶ, γଷ, γସ (của Gen(σ୧), i=1,2,3); và (15) ta 
đã phục hồi 27 chuỗi thuộc lớp tương đương ℱ𝒮(𝓉𝓈ଶ). Trong quá trình phục hồi ta đã tỉa 
sớm được 16 (=2+4+4+6, xem Ví dụ 5 và 6) chuỗi trùng lặp, đạt tỉ lệ 80% (16/(27-(3+4)))! 
Với cách làm tương tự, ta tiếp tục phục hồi 1049 chuỗi thuộc lớp tương đương ℱ𝒮(𝓉𝓈ଵ) 
và 48 chuỗi thuộc các lớp tương đương ℱ𝒮(𝓉𝓈௞), k = 3,6തതതത. Khi đó, ta thu được |ℱ𝑟𝑒𝒮| =
1124 từ |ℱ𝒞𝑙𝑜𝒮| = 16 chuỗi phổ biến đóng và |ℱ𝒢𝑒𝑛𝒮| = 20 chuỗi sinh phổ biến mà 
không cần quét lại CSDL! 
4. KẾT LUẬN 
Báo cáo này đề xuất một tiếp cận dựa trên phân hoạch để phục hồi tất các chuỗi 
phổ biến từ các chuỗi phổ biến đóng và các chuỗi sinh phổ biến. Trước hết, tập tất cả các 
chuỗi phổ biến được phân hoạch (thô) thành các lớp tương đương, mỗi lớp chứa các chuỗi 
cùng xuất hiện trong một tập chuỗi đầu vào, do đó, có cùng độ hỗ trợ. Quá trình phục hồi 
chuỗi dựa trên phân hoạch này có hai ưu điểm: (1) tiết kiệm được tính toán và lưu trữ 
trùng lặp độ hỗ trợ của các chuỗi, (2) loại bỏ được sự trùng lặp trong quá trình phục hồi 
các chuỗi từ các lớp tương đương khác nhau. Không mất tổng quát, ta chỉ cần xét việc 
phục hồi độc lập các chuỗi phổ biến trong mỗi lớp tương đương dựa vào thông tin cốt lõi 
là các chuỗi đóng và chuỗi sinh trong lớp. Để tạo ra một chuỗi phổ biến trong lớp ta chỉ 
cần bổ sung một cách phù hợp các chuỗi con của các chuỗi đóng thêm vào các chuỗi sinh. 
Đáng tiếc là, quá trình này vẫn tạo ra các chuỗi trùng lặp. Vì vậy, tiếp theo ta cần hiểu rõ 
cấu trúc bên trong của mỗi lớp. 
Mỗi lớp chuỗi phổ biến tương đương tiếp tục được phân hoạch thành các lớp con 
(mức 1) dựa vào các chuỗi đóng trong lớp và điều kiện tỉa CloPrun. Khi đó, quá trình 
phục hồi các chuỗi trong mỗi lớp con là độc lập (không trùng lặp với các lớp con khác). 
Tuy nhiên, tiến trình tạo ra các chuỗi trong một lớp con vẫn chứa trùng lặp. Nguyên nhân 
là chuỗi đóng đại diện cho lớp con có nhiều chuỗi sinh và việc bổ sung các chuỗi con 
khác nhau vào các chuỗi sinh khác nhau có thể tạo ra cùng chuỗi kết quả. Để loại bỏ sớm 
các trùng lặp kiểu này, mỗi lớp con mức 1 lại tiếp tục được phân hoạch thành các lớp con 
(mức 2) dựa vào các chuỗi sinh của lớp và điều kiện tỉa GenPrun. Cuối cùng, ta thu được 
một phân hoạch mịn hơn của tập tất cả các chuỗi phổ biến. Liệu rằng có còn xảy ra trùng 
lặp trong quá trình phục hồi mỗi lớp con mức 2 hay không? Nếu có thì cách khắc phục là 
gì? Trong các nghiên cứu tiếp theo, chúng tôi sẽ cố gắng tìm các câu trả lời cho chúng. 
LỜI CẢM ƠN 
Nhóm tác giả gửi lời cảm ơn đến Trường Đại học Đà lạt đã tài trợ kinh phí, tạo 
điều kiện cho nghiên cứu trong khuôn khổ đề tài nghiên cứu khoa học cấp trường năm 
2018. 
TÀI LIỆU THAM KHẢO 
Agrawal, R., Srikant, R. (1995). Mining sequential patterns. Proceedings of the eleventh 
international conference on data engineering, washington, dc, 3–14. 
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 
27 
Ayres, J., Flannick, J., Gehrke, J., Yiu, T. (2002). Sequential pattern mining using a 
bitmap representation. Proceedings of the eighth ACM SIGKDD international 
conference on knowledge discovery and data mining, KDD ’02, New York, NY, 
429–435. 
Birkhoff, G. (1967). Lattice theory, 3rd edition. American mathematical society, 
providence, ri. 
Dương, V.H., Trương, C.T., Lê, H.B. (2018). Efficient algorithms for simultaneously 
mining concise representations of sequential patterns based on extended pruning 
conditions. International journal engineering applications of artificial 
intelligence 67, 197-210. 
Gomariz, A., Campos, M., Marin, R., & Goethals, B. (2013). ClaSP: An Efficient 
Algorithm for Mining Frequent Closed Sequences. Proceedings of 17th Pacific-
Asia Conference, PAKDD '13, Gold Coast, Australia, pp.50–61. 
Han, J., & Kamber M. (2000). Data Mining Concepts and Techniques. Morgan 
Kanufmann. 
Lê, H.B., Dương, V.H., Trương, C.T., & Philip, F.V. (2017). FCloSM, FGenSM: Two 
Efficient Algorithms for Mining Frequent Closed and Generator Sequences using 
the Local Pruning Strategy. International Journal of Knowledge and Information 
Systems (KAIS) 53(1), 71-107. 
Pei, J., Han, J., Mortazavi-Asl, B., Wang, J., Pinto, H., Chen, Q., Dayal, U., & Hsu, M. 
(2004). Mining sequential patterns by pattern-growth: the PrefixSpan approach. 
Journal IEEE Transactions on Knowledge and Data Engineering 16(11), 1424–
1440. 
Philip, F.V., Gomariz, A., Campos, M., & Thomas, R. (2014a). Fast Vertical Mining of 
Sequential Patterns Using Co-occurrence Information. Proceedings of 18th 
Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 
'2014, 40–52. 
Philip, F.V., Gomariz, A., Šebek, M., & Hlosta, M. (2014b). VGEN: Fast Vertical Mining 
of Sequential Generator Patterns. Proceedings of 16th International Conference 
on Data Warehousing and Knowledge Discovery, DWKD'14, Munich, Germany, 
476-488. 
Wang, J., Han, J., Chun, L. (2007). Frequent closed sequence mining without candidate 
maintenance. IEEE Trans. Knowledge and Data Eng. 19(8), 1042-1056. 
Yan, X., Han, J., Afshar, R. (2003). CloSpan: Mining closed sequential patterns in large 
datasets. Proceedings of the 2003 SIAM International Conference on Data 
Mining, 166–177. 
Zaki, M.J. (2001). SPADE: An efficient algorithm for mining frequent sequences. 
Machine Learning 42(1), 31–60.