Xem mẫu
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
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
a
Khoa 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.
15
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
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
a
The 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.
16
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
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ến (nhờ tính
chất Apriori: mọi tập con của một chuỗi phổ biến cũng là một chuỗi phổ biến với độ hỗ
trợ lớn hơn hoặc bằng nó). Tuy nhiên, vì có nhiều chuỗi phổ biến có thể được khai thác
trùng lặp (từ các chuỗi phổ biến tối đại khác nhau) và đánh mất thông tin về độ hỗ trợ nên
ℱℳ𝑎𝑥𝒮 không phù hợp cho việc tìm ℱ𝑟𝑒𝒮.
Xuất phát từ lý thuyết dàn (Birkhoff, 1967), các nghiên cứu gần đây tập trung vào
nghiên cứu các chuỗi phổ biến đóng. Một chuỗi là phổ biến đóng nếu không có chuỗi phổ
biến cha nào có cùng độ hỗ trợ. Nhờ đặc tính này, với một số lượng vừa phải, không quá
nhỏ như số các chuỗi phổ biến tối đại (thiếu thông tin cốt yếu về độ hỗ trợ), cũng không
quá lớn như số các chuỗi phổ biến (thông tin về độ hỗ trợ bị lưu trữ trùng lặp), tập các
chuỗi phổ biến đóng (ký hiệu là ℱ𝒞𝑙𝑜𝒮) rất phù hợp với việc khai thác chuỗi phổ biến.
Từ một chuỗi phổ biến đóng, ta có thể dẫn ra một nhóm các chuỗi phổ biến con khác có
cùng độ hỗ trợ, nói cách khác từ ℱ𝒞𝑙𝑜𝒮 ta có thể dẫn ra ℱ𝑟𝑒𝒮. Các thuật toán tiêu biểu
tìm ℱ𝒞𝑙𝑜𝒮 là Clospan (Yan, Han & Afshar, 2003), BIDE (Wang, Han & Chun, 2007),
17
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
ClaSP (Gomariz và ctg, 2013), CM-ClaSP (Philip và ctg, 2014) và FCloSM (Lê và ctg,
2017).
Có thể xem tập các chuỗi phổ biến đóng là một biểu diễn đặc thích hợp (đã so
sánh với ℱℳ𝑎𝑥𝒮) cho tập các chuỗi phổ biến. Trong nhiều nghiên cứu gần đây, các tác
giả rất quan tâm đến tập ℱ𝒢𝑒𝑛𝒮 các chuỗi phổ biến mà mỗi trong chúng không có chuỗi
phổ biến con nào có cùng độ hỗ trợ. Một chuỗi phổ biến như thế được gọi là một chuỗi
sinh phổ biến. Hai thuật toán tiêu biểu tìm ℱ𝒢𝑒𝑛𝒮 là VGEN (Philip và ctg, 2014b) và
FGenSM (Lê và ctg, 2017). Với lực lượng thường rất nhỏ so với lực lượng của ℱ𝑟𝑒𝒮,
việc khai thác ℱ𝒢𝑒𝑛𝒮 và ℱ𝒞𝑙𝑜𝒮 thường diễn ra nhanh chóng và ít tốn bộ nhớ. Một thuật
toán hiệu quả tìm đồng thời cả hai tập này được đề xuất gần đây là FGenCloSM (Dương,
Trương và Lê, 2018). Một khi đã tìm được chúng, ta có thể biết được ℱ𝑟𝑒𝒮. Câu hỏi đặt
ra là, làm thế nào xác định (phục hồi) tất cả các chuỗi phổ biến thuộc ℱ𝑟𝑒𝒮 từ ℱ𝒢𝑒𝑛𝒮 và
ℱ𝒞𝑙𝑜𝒮 mà không phải quét lại các cơ sở dữ liệu? Để trả lời câu hỏi này, chúng ta cần biết
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. Đây cũng chính là mục tiêu của báo cáo này. Trong quá trình phục hồi, ta có thể
sinh trùng lặp các chuỗi phổ biến, 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. Để vượt qua, báo cáo đề xuất hai điều kiện để tỉa sớm các trùng
lặp trong quá trình phục hồi.
Phần còn lại của báo cáo gồm ba mục. Ở mục 2, sau khi nhắc lại vài khái niệm cơ
sở, báo cáo đưa ra một quan hệ tương đương trên các chuỗi phổ biến và sử dụng nó để
phân hoạch tập tất cả các chuỗi phổ biến ℱ𝑟𝑒𝒮 thành các lớp tương đương. Mục 3 đưa ra
cấu trúc mỗi lớp tương đương các chuỗi phổ biến dựa vào các chuỗi đóng và các chuỗi
sinh trong lớp. Nhờ cấu trúc này, ta hạn chế được đáng kể các trùng lặp xảy ra trong quá
trình phục hồi 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ục cuối cùng là kết luận.
2. PHÂN HOẠCH TẬP CÁC CHUỖI PHỔ BIẾN THÀNH CÁC LỚP TƯƠNG
ĐƯƠNG
2.1. Một số khái niệm và ký hiệu
Gọi ℐ = {i , i , … , i } là tập m các thuộc tính phân biệt. Một tập con của ℐ được
gọi là một sự kiện. Sự kiện có nhiều hơn một thuộc tính được viết trong cặp dấu ( ) và
không có phân cách giữa các thuộc tính. Với sự kiện chỉ có một thuộc tính, đơn giản ta
chỉ viết thuộc tính đó. Không mất tổng quát, giả sử rằng các thuộc tính trong một sự kiện
được sắp tăng dần theo thứ tự từ điển. Một danh sách có thứ tự p sự kiện (p là một số
nguyên dương) được viết liền nhau trong cặp dấu 〈 〉 gọi là một chuỗi. Dữ liệu đầu vào
là một cơ sở dữ liệu 𝒟 = {t , t , … , t } chứa n giao dịch, mỗi giao dịch mô tả một chuỗi
(gọi là chuỗi đầu vào).
Ta sử dụng ký hiệu ⊑ để định nghĩa quan hệ thứ tự chứa trong trên tập tất cả các
chuỗi như sau:
18
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
α⊑β ∃p ∈ 𝒩 ∗ , 1 ⩽ j < j < ⋯ < j ⩽ q e ⊆ e , ∀k = 1, … , p.
Khi đó, ta gọi β là chuỗi cha của α và ký hiệu: α ⊏ β (α ⊑ β ∧ α β).
Gọi ts(α) ≝ {𝑡 ∊ 𝒟 | 𝑡 ⊒ α} là tập tất cả các chuỗi đầu vào chứa α. Số lượng các
chuỗi đầu vào chứa α được gọi là độ hỗ trợ của α, ký hiệu là: support(α) ≝ |ts(α)|1.
Nếu độ hỗ trợ của α lớn hơn hoặc bằng một ngưỡng hỗ trợ tối thiểu msup cho
trước, thì α được gọi là chuỗi phổ biến. Tập tất cả các chuỗi phổ biến được định nghĩa và
ký hiệu: ℱ𝑟𝑒𝒮 ≝ {α | support(α) ≥ msup}.
Ví dụ 1. Cho CSDL 𝒟 trong Bảng 1, với ℐ = {A, B, C, D, E, F, G, H} và msup là
2
2 . Chuỗi β = 〈D(AC)A〉 là chuỗi phổ biến vì ts(β) = {t , t , t } và support(β) =
|ts(β)| = 3 ≥ msup.
Bảng 1. CSDL 𝓓𝟏
Định danh Chuỗi đầu vào
t1
t2
t3
T4
Chuỗi σ được gọi là chuỗi đóng nếu không tồn tại chuỗi cha có cùng độ hỗ trợ với
nó: ∄β ⊐ σ | suppport(σ) = support(β).
Tập các chuỗi đóng được ký hiệu là 𝒞𝑙𝑜𝒮. Cho trước chuỗi α, ta gọi
Clo(α) ≝ {σ ∈ 𝒞𝒮 | (σ ⊒ α ∧ support(σ) = support(α))}
là tập các chuỗi phổ biến đóng chứa (hay của) α và có cùng độ hỗ trợ với α. Với chuỗi α
bất kỳ, có thể có nhiều chuỗi đóng tối tiểu (theo quan hệ thứ tự ⊑) cùng chứa α, tức
là |Clo(α)| ⩾ 1. Hơn nữa, Clo(σ) = {σ} ⇔ σ ∈ 𝒞𝑙𝑜𝒮.
Chuỗi γ được gọi là chuỗi sinh nếu không tồn tại chuỗi con có cùng độ hỗ trợ,
∄α ⊏ γ | support(γ) = support(α).
Cho trước chuỗi α, ta gọi en(α) ≝ {γ ⊑ α | support(γ) = support(α)} là tập
các chuỗi sinh chứa trong (hay của) α và có cùng độ hỗ trợ với α.
1
Ký hiệu |X| dùng để chỉ lực số phần tử của tập hợp X.
2
Từ nay về sau ta luôn xét CSDL 𝒟 với msup là 2.
19
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
Ví dụ 2. Chuỗi phổ biến β cho trong Ví dụ 1 là chuỗi đóng của α = 〈DA〉 vì
∄γ | (γ ⊐ β ∧ support(γ) = 3) và chuỗi δ = 〈𝐷〉 là một chuỗi sinh của α vì ∄δ′ | (δ′ ⊏
δ ∧ support(δ′) = support(δ)) . Do msup = 2 , support(δ) = support(α) =
support(β) = 3, nên δ là chuỗi sinh phổ biến. Khi đó, Clo(β) = Gen(δ) = 1. Ngoài ra,
ta cũng có Clo(δ) = {β, 〈D(AF)〉} và Gen(〈D(AC)(AF)〉) = {〈DAF〉, 〈DCF〉}.
Gọi ℱ𝒞𝑙𝑜𝒮 và ℱ𝒢𝑒𝑛𝒮 lần lượt là tập tất cả các chuỗi phổ biến đóng và tập tất cả
các chuỗi sinh phổ biến. Trong nhiều CSDL, tỉ lệ của tổng |ℱ𝒞𝑙𝑜𝒮| và |ℱ𝒢𝑒𝑛𝒮| so với
|ℱ𝑟𝑒𝒮| thường rất nhỏ, chẳng hạn trên 𝒟 với |ℱ𝒞𝑙𝑜𝒮| = 16 , |ℱ𝒢𝑒𝑛𝒮| = 20 và
|ℱ𝑟𝑒𝒮| = 1124, tỉ lệ này khoảng 3.2%. Tuy nhiên, từ chúng, ta có thể thu được tất cả các
chuỗi phổ biến khác mà không cần quét lại cơ sở dữ liệu. Trước hết, ta xét một quan hệ
tương đương trên tập các chuỗi, sau đó sử dụng nó để phân hoạch tập ℱ𝑟𝑒𝒮 thành các lớp
tương đương.
2.2. Quan hệ tương đương trên tập các chuỗi
Quan hệ hai ngôi ~ trên tập các chuỗi, được định nghĩa như sau: Với hai chuỗi
α, β ta có: α ~ β ts(α) = ts(β). Dễ thấy rằng ~ là một quan hệ tương đương. Khi
đó, nó phân hoạch một tập các chuỗi thành các lớp tương đương. Lớp tương đương chứa
𝛼 được ký hiệu là [𝛼],
[𝛼] ≝ {𝛽 | ts(β) = ts(α)}. (1)
Trong mỗi lớp tương đương, độ hỗ trợ được bảo toàn, tức là:
α ~ β ⟹ support(α) = support(β), ∀β ∈ [𝛼].
2.3. Phân hoạch tập các chuỗi phổ biến thành các lớp tương đương
Từ quan hệ tương đương ~ , ta phân hoạch tập tất cả các chuỗi phổ biến ℱ𝑟𝑒𝒮
thành các lớp tương đương. Không mất tổng quát, ta chỉ cần xét mỗi lớp tương đương
một cách độc lập. Vì chúng rời nhau, nên quá trình xác định các chuỗi phổ biến thuộc
ℱ𝑟𝑒𝒮 sẽ không bị trùng lặp từ lớp này sang lớp kia (kiểu trùng lặp 1). Hơn nữa, ta còn
giảm được đáng kể việc tính toán và lưu trữ trùng lặp các độ hỗ trợ trong cùng lớp. Đây
cũng chính là cơ sở cho các thuật toán song song hiệu quả khai thác tập các chuỗi phổ
biến trong môi trường song song và phân tán.
Trước hết, gọi 𝒯𝒮 ≝ {ts(σ) | σ ∈ ℱ𝒞𝑙𝑜𝒮}. (2)
Khi đó, với mỗi 𝓉𝓈 ∈ 𝒯𝒮, gọi ℱ𝒮(𝓉𝓈) ≝ {α ∈ ℱ𝑟𝑒𝒮 | ts(α) = 𝓉𝓈}. (3)
là lớp tương đương có đại diện là 𝓉𝓈 3. Vì ~ là quan hệ tương đương, nên ta có:
3
Ta gọi tắt “lớp tương đương có đại diện là 𝓉𝓈” là “lớp tương đương 𝓉𝓈”.
20
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
ℱ𝑟𝑒𝒮 = 4 ∑𝓉𝓈∈𝒯𝒮 ℱ𝒮(𝓉𝓈). (4)
Nghĩa là, {ℱ𝒮(𝓉𝓈), 𝓉𝓈 ∈ 𝒯𝒮} tạo ra một phân hoạch (thô) của ℱ𝑟𝑒𝒮. Một phân
hoạch mịn hơn của ℱ𝑟𝑒𝒮 sẽ được chỉ ra trong Mục 3.3.
Ví dụ 3. Ta có |ℱ𝑟𝑒𝒮| = 1124 chuỗi phổ biến và 𝒯𝒮 5= 𝓉𝓈 , k = 1,6 , trong đó:
𝓉𝓈 = {t , t }, 𝓉𝓈 = {t , t , t }, 𝓉𝓈 = {t , t }, 𝓉𝓈 = {t , t , t , t }, 𝓉𝓈 = {t , t } và
𝓉𝓈 = {t , t , t }. Khi đó, ℱ𝑟𝑒𝒮 được phân hoạch thành 6 lớp tương đương như trong
Hình 1.
Hình 1. Phân hoạch thô tập 𝓕𝒓𝒆𝓢 ứng với 𝓓𝟏 khi 𝐦𝐬𝐮𝐩 là 2
Lớp tương đương [α] đại diện bởi ts(α) chứa các chuỗi tối đại thuộc Clo(α) và
các chuỗi tối tiểu thuộc Gen(α) (theo quan hệ thứ tự ⊑) là các chuỗi đã biết thuộc ℱ𝒞𝑙𝑜𝒮
và ℱ𝒢𝑒𝑛𝒮 tương ứng. Các chuỗi còn lại (thuộc ℱ𝑟𝑒𝒮) trong mỗi lớp chính là các chuỗi
đứng sau các chuỗi sinh và đứng trước các chuỗi đóng (theo ⊑). Vì vậy, nếu biết các
chuỗi đóng và chuỗi sinh của một lớp, ta hoàn toàn có thể xác định tất cả các chuỗi còn
lại của nó. Nói cách khác, ta có thể phục hồi lớp ℱ𝑟𝑒𝒮 tất cả các chuỗi phổ biến từ ℱ𝒞𝑙𝑜𝒮
và ℱ𝒢𝑒𝑛𝒮 mà không 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)
4
Ký hiệu Σ biểu thị phép hợp của các tập rời nhau.
5
Từ nay về sau ta luôn sử dụng giá trị này của 𝒯𝒮.
21
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
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〉, γ =
6
〈EAF〉} .
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
6
Thông tin này được sử dụng trong các Ví dụ 5, 6.
22
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
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.
23
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
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).
24
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
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.
25
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
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.
26
- KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018
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.
27
nguon tai.lieu . vn
