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
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: [email protected]
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
aThe Faculty of Mathematics and Computer Science, Dalat University, Lamdong, Vietnam
*Corresponding author: Email: [email protected]
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
1
|
|
chuỗi đầu vào chứa α được gọi là độ hỗ trợ của α, ký hiệu là: support(α) ≝ ts(α) .
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
<(ACE)(AB)(AD)(ABC)(ACDF)>
<B(ACE)(AD)(ACDF)(ABC)>
<C(ACE)(AF)>
t2
t3
T4
<D(ACE)(AH)(AF)>
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 α.
1Ký hiệu |X| dùng để chỉ lực số phần tử của tập hợp X.
2Từ 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)
(3)
(
)
{
| ( )
}
Khi đó, với mỗi 퓉퓈 ∈ 풯풮, gọi ℱ풮 퓉퓈 ≝ α ∈ ℱ푟푒풮 ts α = 퓉퓈 .
là lớp tương đương có đại diện là 퓉퓈 3. Vì ~ꢏꢐ là quan hệ tương đương, nên ta có:
3Ta 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.
5
|
|
Ví dụ 3. Ta có ℱ푟푒풮 = 1124 chuỗi phổ biến và 풯풮 = ꢔ퓉퓈ꢕ, 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)
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 풯풮.
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) , 퐺푒푛 σꢀ
( )
EAF .
{
〈 〉}
( )
{
〈
〉
〈
〉
〈
〉
퐺푒푛 σꢁ = γ = D
〈
,
퐺푒푛 σꢗ = γꢀ = AAA , γꢁ = AAF , γꢗ = EAA , γꢎ =
〉}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ó ℱ풮 σꢁ
=
{〈 〉 〈 〉 〈 〉 〈 〉} 〈 〉
ℱ풮 σꢁ lẫn ℱ풮 σꢀ . Khi đó ℱ풮 σꢁ ∩ ℱ풮 σꢀ = 퐷 , 퐷퐴 ≠ ∅, nghĩa là
〈
〉
퐷 , 퐷퐴 , 퐷퐹 , 퐷(퐴퐹) . Nhận xét rằng 퐷 và 퐷퐴 xuất hiện trong cả
( ) ( ) ( ) ( ) {〈 〉 〈 〉}
{
}
(
)
ℱ풮(σꢀ), ℱ풮(σꢁ), ℱ풮(σꢗ) 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.
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)
(9)
∗( )
( )
(
)
Gọi ℱ풮 σꢚ ≝ ꢔα ∈ ℱ풮 σꢚ ꢊ notꢠCloPrun α, σꢚ ꢡꢖ.
∗
∗( )
( )
∗( )
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
〈 〉 〈
퐷퐹 , 퐷(퐴퐹) . Với σꢗ, vì γꢌ ⋢ σꢀvà γꢌ ⋢ σꢁ , ∀γꢌ ∈ Gen σꢗ , do đó, không có sự
〉
∗( )
퐷 , 퐷퐴 không vượt qua được CloPrun tại σꢀ nên bị loại. Do đó, ℱ풮 σꢁ
=
{〈 〉 〈 〉} ( )
( )
( )
( )
∗( )
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)
(13)
Gọi
∗( )
∗
ℱ풮 ꢠσꢚ, γꢌꢡ ≝ ꢥ훼 ∈ ℱ풮 σꢚ ꢦ α ⊒ γꢌ ∧ not ꢧGenPrunꢠα, σꢚ, γꢌꢡꢨꢩ
∗
∗
(
)
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
13 trang
17580
Free
Bạn đang xem tài liệu "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ải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- cau_truc_cua_cac_chuoi_pho_bien_dua_tren_cac_chuoi_dong_va_c.pdf
