FGenHUSM: Một thuật toán hiệu quả khai thác các chuỗi sinh phổ biến lợi ích cao

Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
FGenHUSM: Một thuật toán hiệu quả khai thác
các chuỗi sinh phổ biến lợi ích cao
Trương Chí Tín1, Trần Ngọc Anh1, Dương Văn Hải1,2, Lê Hoài Bắc2
1 Khoa Toán – Tin học, Trường Đại học Đà Lạt
2 Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh
Tác giả liên hệ: Trần Ngọc Anh, anhtn@dlu.edu.vn
Ngày nhận bài: 15/07/2019, ngày sửa chữa: 09/10/2019, ngày duyệt đăng: 28/10/2019
Định danh DOI: 10.32913/mic-ict-research-vn.v2019.n2.872
Biên tập lĩnh vực điều phối phản biện và quyết định nhận đăng: PGS.TS. Lê Hoàng Sơn
Tóm tắt: Khai thác các chuỗi phổ biến và các chuỗi lợi ích cao có mức độ quan trọng khác nhau trong các ứng dụng
thực tế. Gần đây, các nghiên cứu tập trung giải quyết bài toán tổng quát hơn, là khai thác tập FHUS chuỗi phổ biến lợi
ích cao. Tuy nhiên, thời gian và bộ nhớ dùng để khai thác FHUS vẫn còn quá lớn. Bài báo đề xuất khái niệm tập FGHUS
các chuỗi sinh phổ biến lợi ích cao, là một biểu diễn súc tích của FHUS, và một thuật toán mới hiệu quả để khai thác
nó. Dựa vào hai chặn trên của độ đo lợi ích, hai chiến lược tỉa theo chiều rộng và sâu được thiết kế để loại bỏ nhanh các
chuỗi ít phổ biến hoặc lợi ích thấp. Sử dụng một chặn dưới mới của lợi ích, một chiến lược tỉa địa phương mới được đề
xuất để loại bỏ sớm các chuỗi không là chuỗi sinh phổ biến lợi ích cao. Dựa vào các chiến lược này, một thuật toán mới
퐹 푒푛 푈푆 được thiết kế để khai thác FGHUS mà tính hiệu quả của nó được thể hiện qua các thử nghiệm trên các
cơ sở dữ liệu lớn.
Từ khóa: Chuỗi lợi ích cao, khai thác chuỗi sinh phổ biến lợi ích cao, chặn trên và chặn dưới của độ đo lợi ích.
Title: FGenHUSM: An Efficient Algorithm For Mining Frequent Generator High Utility Sequences
Abstract: Mining the set of all frequent high utility sequences (FHUS) in quantitative sequential databases (QSDBs) plays an
important role in many real-life applications. However, for huge QSDBs and low minimum support and utility thresholds,
algorithms for discovering FHUS often exhibit poor performance in terms of runtime and memory consumption due
to the enormous cardinality of the FHUS set. To address this issue, this paper introduces a novel set of all frequent
generator high utility sequences (FGHUS). This set is a concise representation of FHUS having a cardinality that is
often much less than that of FHUS. Thus, it is more convenient for users to analyze the information provided by the
FGHUS set. This paper proposes a novel algorithm named 퐹 푒푛 푈푆 to efficiently mine FGHUS. The algorithm
adopts the depth and width pruning strategies to quickly eliminate infrequent or low utility sequences. In addition, it
also uses a novel local pruning strategy to prune non-frequent generator high utility sequences early, which is based on
a new lower bound on the utility measure. Experimental results on large QSDBs show that the proposed algorithm is
efficient in terms of runtime for mining FGHUS, and that the pruning strategies can greatly reduce the search space.
Keywords: High utility sequence, frequent generator high utility sequence, upper and lower bounds on utility measure.
I. GIỚI THIỆU
Khi khai thác tập các chuỗi phổ biến (FSM: Frequent
Sequence Mining) trên các cơ sở dữ liệu chuỗi tuần tự
(SDB: Sequential Datadase), ta có thể đánh mất nhiều chuỗi
lợi ích cao (HU: High Utility) quan trọng trong nhiều ứng
dụng thực tế khi chúng ít phổ biến. Chẳng hạn, lợi ích của
các mặt hàng bán được là thông tin rất hữu ích khi ra các
quyết định trong kinh doanh. Vì vậy, bài toán khai thác các
chuỗi HU (HUSM: High Utility Sequence Mining) trên các
SDB lượng hóa (QSDB: Quantitative SDB) ra đời sau đó
như một nhu cầu bức thiết.
HUSM tổng quát hơn FSM và có nhiều ứng dụng như
phân tích hành vi duyệt web [1], dữ liệu thương mại di
động [2], hiệu chỉnh gen [3], v.v. Ta xét một ứng dụng điển
hình của HUSM là phân tích dữ liệu mua hàng. Xét cơ sở
dữ liệu chuỗi biểu diễn các đơn mua hàng của khách hàng
trong một cửa hàng bán lẻ. Khi đó một chuỗi chứa các mặt
hàng được mua bởi một khách hàng ở các thời điểm khác
nhau. Chi tiết hơn, nó là một danh sách có thứ tự của các
tập mặt hàng, mỗi tập mặt hàng chứa các mặt hàng được
mua cùng nhau. Lấy ví dụ, ta có chuỗi 〈{kem đánh răng,
bàn chải đánh răng}, {bánh Kinh đô, phô mai}, {nhang}〉.
Chuỗi mặt hàng có thể được mua bởi một phụ nữ. Người
57
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
này mua kem đánh răng và bàn chải đánh răng cùng nhau,
sau đó mua bánh Kinh đô với phô mai, cuối cùng mua
nhang. Mỗi mặt hàng có một giá bán ra. Khi đó, ta có thể
xác định được giá trị của một tập các mặt hàng được mua
cùng nhau cũng như giá trị của một danh sách con các tập
mặt hàng trong chuỗi mua hàng của một khách hàng nào
đó. Khi khai thác trên một tập rất lớn các đơn mua hàng,
ta có thể biết được các thông tin như: (i) các mặt hàng nào
thường được mua cùng nhau, (ii) lợi ích đem lại của một
chuỗi các tập mặt hàng nào đó, v.v. Các thông tin này rất
có ích cho việc ra các quyết định kinh doanh của cửa hàng.
Cho Ψ′ là một QSDB chứa các chuỗi đầu vào, trong mỗi
chuỗi có các sự kiện, trong mỗi sự kiện có các thuộc tính,
mỗi thuộc tính gắn với một số lượng và một giá trị lợi ích.
Do mỗi chuỗi 훼 có thể xuất hiện ở các vị trí khác nhau (với
các lợi ích khác nhau) trong Ψ′, nên lợi ích của 훼 trong
Ψ′ có thể được tính dưới dạng tổng [4], giá trị lớn nhất
 max (훼) [5, 6] hoặc giá trị nhỏ nhất min (훼) [7, 8] (theo
nghĩa an toàn và ít rủi ro cho việc phát triển các chiến lược
kinh doanh hay ra quyết định). Khi đó, lợi ích của 훼 là
tổng lợi ích trên tất cả các chuỗi Ψ′ chứa 훼. Nếu lợi ích
của 훼 lớn hơn hoặc bằng một ngưỡng lợi ích tối thiểu ,
nó được gọi là chuỗi HU, ngược lại 훼 được gọi là chuỗi lợi
ích thấp (LU: Low Utility). Mục đích của HUSM là khai
thác tập chuỗi lợi ích cao (HUS) chứa các chuỗi HU trên
một QSDB.
Thuận lợi chính khi giải FSM là tính ‘a priori’, còn gọi là
tính đơn điệu giảm (anti-monotonic) hay DCP (Downward-
Closure Property), của độ đo hỗ trợ: Mọi chuỗi cha của
một chuỗi ít phổ biến (LF: Low Frequent) cũng LF [5, 9].
Đặc tính này cho phép rút gọn đáng kể không gian tìm
kiếm khi tiến hành khai thác các chuỗi lớn dần trên cây
tiền tố. Đáng tiếc là trong HUSM, độ đo lợi ích không có
tính DCP. Để khắc phục, các chặn trên (UB: Upper Bound)
lợi ích được thiết kế để thu hẹp phạm vi tìm kiếm.
Chặn trên SWU [5] (thỏa DCP nhưng giá trị lớn) và các
chặn trên khác chặt hơn (có giá trị nhỏ và gần với lợi ích
hơn) lần lượt được thiết kế và sử dụng (mặc dù chỉ thỏa
mãn các tính chất tựa DCP). Với max (훼), có thể kể ra SPU
và SRU (2013), PEU và RSU (2016), gần đây là MEU [6]
và SEU [10]. Với min (훼), các tác giả trong [7] đã đề xuất
hai chặn trên, RBU và LRU, thiết kế hai chiến lược tỉa theo
chiều sâu (DPS: Depth Pruning Strategy) và rộng (WPS:
Width Pruning Strategy), và tích hợp chúng vào thuật toán
EHUSM để khai thác hiệu quả HUS. Mặc dù EHUSM có
thể khai thác nhanh HUS, lực lượng tập kết quả thường rất
lớn, việc quản lý và phân tích chúng gây khó khăn đối với
người sử dụng. Một tiếp cận thường được dùng trong FSM
là khai thác các biểu diễn súc tích của chúng, chẳng hạn
như các chuỗi tối đại, đóng và sinh [11, 12]. Chú ý rằng,
bằng việc tích hợp FSM và HUSM, ta xét bài toán tổng quát
hơn, là FHUSM: Khai thác tập FHUS các chuỗi phổ biến
lợi ích cao (FHU: Frequent High Utility), đối với độ đo lợi
ích min. Theo cách tiếp cận trên, nhóm tác giả trong [13]
đã đề xuất các thuật toán hiệu quả nhằm khai thác hai biểu
diễn súc tích của FHUS, bao gồm các chuỗi phổ biến tối
đại lợi ích cao (FMaxHU) và tập FCHUS các chuỗi phổ
biến đóng lợi ích cao (FCHU). Tuy nhiên, chiều dài các
chuỗi FMaxHU và FCHU thường khá lớn. Vì vậy, bài báo
đề xuất một biểu diễn súc tích khác FGHUS của FHUS.
Trước đây, đã xuất hiện nhiều công trình nhằm khai thác
các tập (tập thuộc tính) sinh phổ biến có/không có lợi ích
cao [14–16]. Các chuỗi (danh sách có thứ tự các tập thuộc
tính) đóng/tối đại/sinh phổ biến cũng đã là đối tượng của
nhiều nghiên cứu gần đây [12, 17, 18]. Tập chứa các chuỗi
sinh phổ biến lợi ích cao (FGHUS) là mở rộng tự nhiên của
chuỗi sinh phổ biến truyền thống. Một chuỗi FHU được gọi
là chuỗi sinh phổ biến lợi ích cao (FGHU) nếu không tồn
tại chuỗi con FHU nào có cùng độ hỗ trợ.
Vì các chuỗi FGHU có chiều dài thường bé hơn nhiều
so với các chuỗi FMaxHU và FCHU, nên chúng có các ưu
điểm sau. Thứ nhất, ta có thể xem nó như một biểu diễn
nén của FHUS. Điều này cũng rất phù hợp với nguyên
lý chiều dài mô tả bé nhất (MDL: Minimum Description
Length) [19]. Thứ hai, nó cho độ chính xác cao trong các
nhiệm vụ chọn mô hình (so với FHUS hay tập FCHUS).
Ngoài ra, khai thác các mẫu sinh (với chiều dài tối thiểu)
còn là một bước quan trọng trong việc tìm các luật tuần
tự quan trọng, chẳng hạn, các luật với ít giả thiết (vế trái)
nhưng dẫn ra nhiều kết luận (vế phải), hoặc các luật không
dư thừa [20]. Khi đó, các mẫu sinh chính là vế trái, vế
phải có thể là các mẫu đóng hoặc không. Do đó, các mẫu
sinh trong FGHUS thường được ưa thích hơn đối với người
dùng khi cần phân tích tập kết quả, vì số lượng và chiều dài
của chúng khá bé so với FHUS. Tập FHUS thường được
sử dụng khi lực lượng của chúng khá bé, chẳng hạn khi
ngưỡng hỗ trợ ( 푠) và ngưỡng lợi ích tối thiểu ( ) khá
cao. Ngược lại, khi các ngưỡng này khá thấp và đặc biệt
trên các tập dữ liệu lớn, để vượt qua khó khăn trong việc sử
dụng cũng như phân tích tập kết quả FHUS với kích thước
quá lớn, tập FGHUS sẽ là một lựa chọn phù hợp hơn với
người dùng.
Mục tiêu của bài báo này là khai thác tập FGHUS. Để
khai thác hiệu quả nó, do FGHUS ⊆ FHUS, nên một chuỗi
LU hoặc LF sẽ không là FGHU. Do đó, tính chất DCP của
độ hỗ trợ và hai chiến lược WPS và DPS dựa vào RBU và
LRU [7, 8] có thể được sử dụng để tỉa hiệu quả các chuỗi
LF hoặc LU không những từ FHUS mà cả FGHUS. Tuy
nhiên, vì FGHUS không là tập con của tập tất cả các chuỗi
sinh phổ biến (FGS), nên ta không thể áp dụng trực tiếp
các điều kiện tỉa 3E trong [12] để loại bỏ các chuỗi không
là chuỗi sinh lợi ích cao (GHU).
58
Tập 2019, Số 2, Tháng 12
Bài báo có một số đóng góp sau đây: (i) đề xuất chặn
dưới SF của min; (ii) dựa vào điều kiện tỉa sớm tổng quát
 푃 [13] và SF, chiến lược tỉa địa phương (LPG) được
thiết kế để loại bỏ sớm các ứng viên (và các mở rộng của
chúng) không là GHU; (iii) tích hợp ba chiến lược DPS,
WPS và LPG vào thuật toán 퐹 푒푛 푈푆 để khai thác
các chuỗi sinh phổ biến lợi ích cao (FGHU); (iv) các thử
nghiệm trên hai cơ sở dữ liệu lớn, thực tế và tổng hợp, đã
chỉ ra tính hiệu quả của 퐹 푒푛 푈푆 (so với thuật toán cơ
sở không áp dụng các chiến lược tỉa) về mặt thời gian chạy
và lực lượng của FGHUS thường rất bé so với FHUS. Đây
là thuật toán đầu tiên khai thác biểu diễn súc tích FGHUS
của FHUS với độ đo lợi ích min.
Phần còn lại của bài báo được tổ chức như sau. Phần II
trình bày các khái niệm và kết quả cơ bản. Phần xây dựng
chiến lược tỉa địa phương LPG. Phần IV đưa ra thuật toán
퐹 푒푛 푈푆 và các kết quả thử nghiệm. Phần V đưa ra
các kết luận của bài báo.
II. CÁC KHÁI NIỆM VÀ KẾT QUẢ CƠ BẢN
1. Định nghĩa bài toán
Mục này giới thiệu vài khái niệm cơ sở liên quan đến
bài toán HUSM với min trong [7].
Định nghĩa 1 ([7]): Gọi A def= { 1, 2, . . . , } là tập
các thuộc tính phân biệt. Mỗi thuộc tính gắn liền với một
số dương P( ) thể hiện giá trị lợi ích đơn vị của nó. Khi đó,
ta có véctơ P( ) def= 〈P( 1), P( 2), . . . , P( )〉. Một thuộc
tính số lượng/định lượng (푞-thuộc tính) là một cặp ( , 푞),
với ∈ A và 푞 ∈ 푅+ là một số lượng dương. Tập con 
của A, ⊆ A, được gọi là một sự kiện. 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 theo thứ tự từ điển ≺. Một sự kiện số lượng (푞-sự
kiện) ứng với được định nghĩa là
 ′ def= {( 푖 , 푞푖) | 푖 ∈ , 푞푖 ∈ 푅+}.
 được gọi là sự kiện chiếu của ′, ký hiệu là = proj( ′).
Danh sách các 푞-sự kiện
〈
 ′ , = 1, 2, . . . , 
〉
ký hiệu là
훼′ = ′1 → ′2 · · · → ′ , được gọi là một 푞-chuỗi. Chuỗi
chiếu 훼 của 푞-chuỗi 훼′ được định nghĩa là
훼 = proj(훼′) def= proj( ′1) → proj( ′2) → · · · → proj( ′ ).
Để thuận tiện, ta ký hiệu 훼′[ ] def= ′ và 훼[ ]
def
= proj( ′ ).
Một 푞-chuỗi là rỗng () nếu tất cả các sự kiện của nó là
rỗng. Một cơ sở dữ liệu chuỗi lượng hóa (QSDB) D ′ chứa
hữu hạn các 푞-chuỗi đầu vào, D ′ = {Ψ′푖 , 푖 = 1, 2, . . . , }
và 푃( ). Mỗi 푞-chuỗi Ψ′푖 gắn với một định danh (SID) 푖.
Cơ sở dữ liệu chuỗi (không lượng hóa SDB) D ứng với
D ′ được định nghĩa là
D = proj(D ′) def= {proj(Ψ′푖), 푖 = 1, 2, . . . , } .
Kích thước của 푞-chuỗi 훼′, ký hiệu là size (훼′), là số các
푞-sự kiện ( ) của nó.
Từ đây về sau, ta xét hai 푞-chuỗi bất kỳ 훼′ = ′1 →
 ′2 → · · · → ′ và 훽 = ′1 → ′2 → · · · → ′푞 cùng
hai chuỗi tương ứng 훼 = 1 → 2 → · · · → và
훽 = 1 → 2 → · · · → 푞 .
Định nghĩa 2 ([7]): Xét hai 푞-sự kiện ′ và ′ sau:
 ′ =
{
 푖1 , 푞푖1 ), ( 푖2 , 푞푖2 ), . . . , ( 푖 , 푞푖 )
}
,
 ′ =
{( 푗1 , 푞 푗1 ), ( 푗2 ), 푞 푗2 ), . . . , ( 푗푛 , 푞 푗푛 )} ,
với ≤ 푛. ′ được gọi là chứa trong ′, ký hiệu là ′ v ′,
nếu tồn tại các số tự nhiên 1 ≤ 1 < · · · < ≤ 푛 sao cho
 푖푙 = 푗 푙 và 푞푖푙 = 푞 푗 푙 , với mọi 푙 = 1, 2, . . . , .
Ngoài ra, ta nói 훼′ chứa trong 훽′, ký hiệu là 훼′ v 훽′, nếu
 ≤ 푞 và tồn tại số nguyên dương, 1 ≤ 푗1 < · · · < 푗 ≤ 푞
sao cho ′ v ′푗 , với mọi = 1, 2, . . . , . Đồng thời,
훼′ @ 훽′ tương đương với ((훼′ @ 훽′) ∧ (훼′ ≠ 훽′)).
Tương tự, ta cũng dùng ký hiệu v để định nghĩa quan
hệ chứa trong trên tập tất cả các chuỗi. Ta nói 훼 v 훽 hoặc
훽 w 훼 (훽 được gọi là chuỗi cha của 훼) nếu tồn tại số
nguyên dương, 1 ≤ 푗1 < · · · < 푗 ≤ 푞 sao cho ⊆ 푗 ,
với mọi = 1, 2, . . . , . Đồng thời, 훼 @ 훽 tương đương với
((훼 v 훽) ∧ (훼 ≠ 훽)).
Ta nói 훽′ chứa 훼, ký hiệu là 훼 v 훽′ (hay 훽′ w 훼, 훽′
được gọi là 푞-chuỗi cha của 훼) nếu proj(훽′) w 훼.
Gọi
휌(훼) def= {Ψ′ ∈ D ′ | Ψ′ w 훼}
là tập tất cả các 푞-chuỗi đầu vào chứa 훼. Độ hỗ trợ của 훼
được định nghĩa là số các 푞-chuỗi đầu vào chứa 훼,
supp(훼) def= |휌(훼) |.
Định nghĩa 3 ([7]): Các lợi ích của 푞-thuộc tính ( , 푞),
푞-sự kiện ′ = ( 푖1 , 푞푖1 ), ( 푖2 , 푞푖2 ), . . . , ( 푖 , 푞푖 ), 푞-chuỗi
훼′ và QSDB D ′ lần lượt được định nghĩa là
 (( , 푞)) def= 푃( ) ∗ 푞,
 ( ′) def=
 ∑
푗=1
 (( 푖 푗 , 푞푖 푗 )),
 (훼′) def=
 ∑
푖=1
 ( ′푖),
 (D ′) def=
∑
Ψ′∈D′
 (Ψ′).
Để tránh tính toán lặp lại lợi ích của mỗi 푞-thuộc tính
( , 푞) trong các 푞-chuỗi Ψ′ của D ′, ta tính chúng một lần
và thay 푞 bởi (( , 푞)) = P( ) ∗푞 trong cơ sở dữ liệu. Biểu
diễn tương đương này của QSDB D ′ được gọi là QSDB
tích hợp của D ′, cũng được ký hiệu vắn tắt là D ′. Từ đây
về sau ta chỉ xét các QSDB tích hợp.
59
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Bảng I
D ′ −MỘT QSDB MINH HỌA
SID Chuỗi
1 Ψ′1 = ( , 9) → ( , 2) (푒, 20) → ( , 1) ( , 50)
→ ( , 8) ( , 16) → ( , 8) ( , 16) (푒, 35) ( , 60)
→ ( , 3) ( , 5) (푒, 2)
2 Ψ′2 = ( , 9) ( , 28) → ( , 15) ( , 10)
→ ( , 16) ( , 40) ( , 15) (푒, 20) → ( , 6) ( , 24) (푒, 25)
3 Ψ′3 = ( , 20) → (푒, 40) ( , 12) → ( ... → , → và → . Với
 → , không có thay đổi nào trên FGHUS. Với → 
và → , ta đẩy → 2813 và → 2303 vào FGHUS.
Khi đó, ta có new ( → ) = { , 푒, } và 푆new ( → ) =
{ , , , }.
Không có thay đổi nào trên FGHUS khi xét → → 
và → → . Với → → , ta tìm thấy trong
FGHUS chuỗi con → 2303 có cùng độ hỗ trợ tại dòng 14
trong UpdateFGHUS. Tại dòng tiếp theo, ta thực hiện thủ
tục LocalPruningGHU với → → và → . Mặc
dù SE(D ′′ → → ) = SE(D ′′ → ) = 7, chiến lược tỉa LPG
không thể được áp dụng vì
SF( min ( → )) = 29 < .
Tiếp tục, ta có
 new ( → → ) = { , , },
푆new ( → → ) = { , }.
Với 푠-mở rộng → → → , ta có new ( → →
 → ) = { }. Vì RBU( → → → ) ≥ ,
tại dòng 13, ta gọi LocalPruningGHU (trường hợp (i)) với
푖new = → → → và → → → . Trong
thủ tục ta không áp dụng được LPG, vì
SF( min ( → → → )) = 148 < .
Tiếp tục các dòng 14–15, trường hợp (ii) được xét giữa 푖new
với 훽 = → → → . Vì
SE(D ′′ → → → ) = SLIP(D ′′ → → → )
= SE(D ′′ → → → ) = SLIP(D ′′ → → → ) = 1,
SF( min ( → → → )) = 211 ≥ ,
ta tỉa toàn bộ nhánh non-GHU branch( → → →
 ) bởi LPG, cụ thể là đặt giá trị false cho trường do-ext
của 푖new.
Sau đó, ta xét 푠-mở rộng → → → và chèn
nó vào FGHUS. Với các 푖-mở rộng → → cũng
như → → , không có thay đổi nào diễn ra
vì → → là chuỗi cha của chuỗi → → 
trong FGHUS với cùng độ hỗ trợ 2. Cuối cùng, với 푖-mở
rộng → → . Ta có, new ( → → ) = ∅
và 푆new ( → → ) = { , }. Ở các dòng 26–30
trong DfsFGHUS, trường hợp (b) xảy ra với lời gọi
LocalPruningGHU( → → → , → → → ).
Khi đó, ta tỉa toàn bộ nhánh → → → không
chứa chuỗi sinh phổ biến lợi ích cao.
Quay trở lại nút → và xét các 푖-mở rộng của
nó, ta không tìm thấy lời giải nào, đồng thời cũng không
có nhánh nào bị tỉa. Tuy nhiên, với → 푒, ta tỉa
được 7 nhánh không chứa chuỗi sinh và đưa thêm ứng
viên → 푒 → 2151 vào FGHUS.
Khi xét hai nhánh bắt đầu tại → 2673 và →
 2153 , ta chèn thêm chúng vào FGHUS đồng thời loại bỏ
 → 푒 → 2151 . Tìm kiếm trên → __ kết thúc và ta
tiếp tục trên → __. Trong quá trình này, ta phát hiện
ra 12 lần sử dụng chiến lược tỉa LPG, và 64 lần sử dụng
WPS và DPS. Năm ứng viên sau được thêm vào FGHUS:
 → 푒 → 2081 , → → → 2041 , → → 3282
và → → → 2041 . Các ứng viên → 2303 ,
 → 2313 , → → → 2111 và → 푒 → 2151
bị loại vì → 2153 , → 2673 , → → → 2041 và
 → 푒 → 2081 đã có trong FGHUS tương ứng.
Sau đó, quá trình tìm kiếm trên 푒, , và diễn ra. Đáng
tiếc là, ta không thu được gì. Cuối cùng, ta có
FGHUS = { → 2204 ; → → 2113 , 푒 → → 2183 ,
 → 2673 , → 2153 ; → → → 2002 ,
 → → 2022 , 푒 → → → 2022 ,
 → → → 2022 , → → 2032 ,
 푒 → → → 2002 , 푒 → → → 2002 ,
 푒 → → 2002 , → → 2452 ,
 → → 3282 ; → 푒 → 2081 ,
 → → → 2041 , → → → 2041 },
với 18 lời giải, chiếm tỉ lệ 22% so với 83 chuỗi phổ biến
lợi ích cao.
3. Thử nghiệm
Các thử nghiệm nhằm minh họa tính hiệu quả của
퐹 푒푛 푈푆 được tiến hành trên các cơ sở dữ liệu được
mô tả trong Bảng III. Kosarak và Snake là hai QSDB thực
tế, trong khi D4C7T5N5S6I4 và D0.5C10T15N2S6I4 là hai
QSDB tổng hợp, với các giá trị về số lượng và lợi ích đơn
vị của các thuộc tính trong các QSDB tương ứng được tạo
ngẫu nhiên bởi chương trình sinh dữ liệu của IBM (IBM
Quest data generator) từ thư viện SPMF [21].
66
Tập 2019, Số 2, Tháng 12
Bảng III
QSDB D ′′ MINH HỌA THUẬT TOÁN 퐹 푒푛 푈푆 
Tên Số
chuỗi
Số
thuộc
tính
Độ dài
trung
bình
Loại
dữ liệu
Kosarak 10000 10094 8,14 Duyệt web
D4C7T5N5S6I4 4000 5000 28,7 Tổng hợp
D0.5C10T15N2S6I4 500 2000 127,7 Tổng hợp
Snake 163 20 60,6 Chuỗi protein
Với mỗi QSDB 푄 cố định, chúng tôi xác định một
ngưỡng 푠 tương đối (tần suất tính theo % đã được dùng
phổ biến trong các thực nghiệm cho các thuật toán về lĩnh
vực này, 푠% def= 푠 ∗ 100/|푄 | (%), trong đó |푄 | là số các
푞-chuỗi đầu vào của 푄). Nếu không gây hiểu nhầm ta cũng
ký hiệu 푠 tương đối là 푠.
Chúng tôi đã tiến hành khai thác các chuỗi sinh phổ
biến lợi ích cao bằng 퐹 푒푛 푈푆 trong ba trường hợp:
(i) Non: không dùng chiến lược tỉa nào (tìm các chuỗi phổ
biến lợi ích cao trước và sau đó lọc ra các chuỗi sinh);
(ii) WDPS: sử dụng WPS và DPS; (iii) All: dùng cả ba
chiến lược WPS, DPS và LPG.
Trước hết, chúng tôi nhận thấy rằng hai tập kết quả của
퐹 푒푛 푈푆 luôn trùng nhau tương ứng với hai trường
hợp: khi dùng cả ba chiến lược tỉa (All) và khi không dùng
bất cứ chiến lược nào (Non) mà chỉ đơn thuần dùng định
nghĩa của chuỗi sinh lợi ích cao phổ biến (Định nghĩa 5).
Do đó, tính đúng của 퐹 푒푛 푈푆 đã được kiểm chứng
thêm thông qua thực nghiệm.
Thời gian chạy của 퐹 푒푛 푈푆 được cho trong hình 1.
Khi ngưỡng cao, các điều kiện tỉa LRU(훼) < và
RBU(훼) < (trong hai chiến lược WPS và DPS, hay
푊 푃푆) dễ có cơ hội xảy ra hơn, nên số ứng viên (sinh ra
và chưa bị tỉa) khi dùng WDPS là bé hơn đáng kể so với
Non (không dùng chiến lược nào). Khi giảm dần, tác
dụng của WDPS cũng giảm theo. Ngược lại, với các ngưỡng
 thấp, vì điều kiện SF(훼) ≥ (trong chiến lược LPG
khi dùng All) dễ xảy ra hơn, nên số ứng viên sinh ra khi
dùng All (áp dụng cả ba chiến lược tỉa nêu trên) là bé hơn
đáng kể so với chỉ dùng WDPS. Vì vậy, so với Non, việc
áp dụng đồng thời cả ba chiến lược tỉa sẽ tỉa nhiều hơn các
chuỗi ứng viên, do đó thời gian thi hành của thuật toán sẽ
nhanh hơn đáng kể.
Ghi nhận số lượng các ứng viên được sinh ra tương ứng
trong hình 2 của ba trường hợp lý giải thêm về sự khác
nhau về thời gian chạy của chúng.
Hình 3 chỉ ra số lượng các chuỗi FGHU khai thác được
bởi 퐹 푒푛 푈푆 (#fGenHU) và số lượng các chuỗi FHU
(#fHU). Có thể thấy rằng, #fGenHU bé hơn #fHU từ 5 đến
100 lần theo trung bình (đặc biệt khi bé). Vì vậy, theo
1E+0
1E+1
1E+2
1E+3
1E+4
0.6 0.3 0.24 0.15 0.03 0.018 0.005 0.002 0.001 0.0003
Th
ờ
i g
ia
n 
ch
ạy
 (g
iâ
y)
mu (%)
D4C7T5N5S6I4 (ms = 0.25%)
1E+0
1E+1
1E+2
1E+3
3 2 1 0.6 0.1 0.01 0.006 0.004 0.002 0.001
Th
ờ
i g
ia
n 
ch
ạy
 (g
iâ
y)
mu (%)
Kosarak (ms = 0.15%)
3E+1
3E+2
3E+3
2 1.2 0.75 0.3 0.05 0.005 0.001 0.0001
Th
ờ
i g
ia
n 
ch
ạy
 (g
iâ
y)
mu (%)
D0.5C10T15N2S6I4 (ms = 2.2%)
2E+2
2E+3
2E+4
15 14 12 7 5 3 2.7 2.4
Th
ờ
i g
ia
n 
ch
ạy
 (g
iâ
y)
mu (%)
Snake (ms = 60%)
Hình 1. Thời gian chạy của 퐹 푒푛 푈푆 . Ghi chú: All (màu đỏ,
hình tam giác), WDPS (màu xanh đậm, hình tròn), Non (màu xanh
lá cây, hình vuông).
lực lượng, có thể xem FGHUS là một biểu diễn súc tích
của FHUS.
V. KẾT LUẬN
Bài báo này đã đề xuất khái niệm tập FGHUS các
chuỗi sinh phổ biến lợi ích cao và thuật toán hiệu quả
퐹 푒푛 푈푆 khai thác chúng, thông qua các kỹ thuật tỉa
các nhánh ứng viên trên cây tìm kiếm tiền tố. Trước hết,
hai chiến lược tỉa theo chiều rộng WPS và chiều sâu DPS
(đã dùng trong các kết quả trước đây cho việc tỉa các chuỗi
lợi ích thấp) được điều chỉnh phù hợp để tỉa các chuỗi ít
67
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
1E+4
1E+5
1E+6
0.6 0.3 0.24 0.15 0.03 0.018 0.005 0.002 0.001 0.0003
Số
 ứ
ng
 v
iê
n
mu (%)
D4C7T5N5S6I4 (ms = 0.25%)
1E+3
1E+4
1E+5
1E+6
3 2 1 0.6 0.1 0.01 0.006 0.004 0.002 0.001
Số
 ứ
ng
 v
iê
n
mu (%)
Kosarak (ms = 0.15%)
1E+6
1E+7
2 1.2 0.75 0.3 0.05 0.005 0.001 0.0001
Số
 ứ
ng
 v
iê
n
mu (%)
D0.5C10T15N2S6I4 (ms = 2.2%)
13
15
17
19
21
23
25
27
29
15 14 12 7 5 3 2.7 2.4
Số
 ứ
ng
 v
iê
n
x
 1
0
0
0
0
0
mu (%)
Snake (ms = 60%)
Hình 2. Số ứng viên sinh bởi 퐹 푒푛 푈푆 . Ghi chú: All (màu
đỏ, hình tam giác), WDPS (màu xanh đậm, hình tròn), Non (màu
xanh lá cây, hình vuông).
phổ biến hoặc các chuỗi lợi ích thấp. Sau đó, chúng tôi
đã chỉ ra một chặn dưới SF của độ đo lợi ích tối thiểu
 min. Dựa vào SF và điều kiện tỉa sớm tổng quát [13],
chiến lược tỉa LPG được đề xuất và dùng để tỉa các ứng
viên không là chuỗi sinh phổ biến lợi ích cao. Để ý rằng,
WPS và DPS có tác dụng tỉa mạnh với các ngưỡng lợi ích
tối thiểu cao, trong khi LPG có hiệu quả cao với các
 thấp. Do đó, chúng tôi đã tích hợp tất cả chúng vào
thuật toán 퐹 푒푛 푈푆 . Thực nghiệm trên bốn cơ sở dữ
liệu lớn (thực tế lẫn tổng hợp) đã chỉ ra rằng 퐹 푒푛 푈푆 
khai thác nhanh FGHUS − một biểu diễn súc tích của tập
các chuỗi phổ biến lợi ích cao.
1E+0
1E+1
1E+2
1E+3
1E+4
1E+5
1E+6
0.6 0.3 0.24 0.15 0.03 0.018 0.005 0.002 0.001 0.0003
Số
 lờ
i g
iả
i v
à 
số
 c
hu
ỗi
 F
H
U
mu (%)
D4C7T5N5S6I4 (ms = 0.25%)
5E+0
5E+1
5E+2
5E+3
5E+4
3 2 1 0.6 0.1 0.01 0.006 0.004 0.002 0.001
Số
 lờ
i g
iả
i v
à 
số
 c
hu
ỗi
 F
H
U
mu (%)
Kosarak (ms = 0.15%)
1E+0
1E+1
1E+2
1E+3
1E+4
1E+5
1E+6
2 1.2 0.75 0.3 0.05 0.005 0.001 0.0001
Số
 lờ
i g
iả
i v
à 
số
 c
hu
ỗi
 F
H
U
mu (%)
D0.5C10T15N2S6I4 (ms = 2.2%)
5E+0
5E+1
5E+2
5E+3
5E+4
5E+5
15 14 12 7 5 3 2.7 2.4
Số
 lờ
i g
iả
i v
à 
số
 c
hu
ỗi
 F
H
U
mu (%)
Snake (ms = 60%)
Hình 3. Số lời giải và số chuỗi FHU. Ghi chú: #fGenHU (màu
xanh đậm, hình thoi), #fHU (màu đỏ, hình dấu nhân).
LỜI CẢM ƠN
Nghiên cứu này được tài trợ bởi Quỹ Phát triển Khoa
học và Công nghệ Quốc gia (NAFOSTED) trong đề tài mã
số 102.05-2017.300.
TÀI LIỆU THAM KHẢO
[1] C. F. Ahmed, S. K. Tanbeer, and B.-S. Jeong, “Mining
high utility web access sequences in dynamic web log
data,” in 11th ACIS International Conference on Software
Engineering, Artificial Intelligence, Networking and Paral-
lel/Distributed Computing, 2010, pp. 76–81.
[2] B.-E. Shie, H.-F. Hsiao, V. S. Tseng, and S. Y. Philip,
“Mining high utility mobile sequential patterns in mobile
68
Tập 2019, Số 2, Tháng 12
commerce environments,” in International Conf. Database
Systems for Advanced Applications, 2011, pp. 224–238.
[3] M. Zihayat, H. Davoudi, and A. An, “Top-k utility-based
gene regulation sequential pattern discovery,” in IEEE In-
ternational Conference on Bioinformatics and Biomedicine,
2016, pp. 266–273.
[4] C. F. Ahmed, S. K. Tanbeer, and B.-S. Jeong, “A novel ap-
proach for mining high-utility sequential patterns in sequence
databases,” ETRI Journal, vol. 32, no. 5, pp. 676–686, 2010.
[5] J. Yin, Z. Zheng, and L. Cao, “USpan: An efficient algorithm
for mining high utility sequential patterns,” in ACM/SIGKDD
Int’l Conf. Knowl. Disc. Data Mining, 2012, pp. 660–668.
[6] J. C.-W. Lin, J. Zhang, and P. Fournier-Viger, “High-utility
sequential pattern mining with multiple minimum utility
thresholds,” in Asia-Pacific Web and Web-Age Infor. Man-
agement Joint Conf. Web and Big Data, 2017, pp. 215–229.
[7] T. Truong, A. Tran, H. Duong, B. Le, and P. Fournier-Viger,
“EHUSM: Mining high utility sequences with a pessimistic
utility model,” 1st Int’l Work. Utility-Driven Mining, 2018.
[8] T. C. Tin, T. N. Anh, D. Van Hai, and L. H. Bac, “HUPSMT:
An efficient algorithm for mining high utility-probability
sequences in uncertain databases with multiple minimum
utility thresholds,” Journal of Computer Science and Cy-
bernetics, vol. 35, no. 1, pp. 1–20, 2019.
[9] T. Truong-Chi and P. Fournier-Viger, “A survey of high
utility sequential pattern mining,” in High-Utility Pattern
Mining, P. Fournier-Viger, J. Lin, R. Nkambou, B. Vo, and
V. Tseng, Eds. Springer, 2019, pp. 97–129.
[10] W. Gan, J. C.-W. Lin, J. Zhang, H.-C. Chao, H. Fujita, and
S. Y. Philip, “ProUM: Projection-based utility mining on
sequence data,” Info. Sciences, vol. 513, pp. 222–240, 2020.
[11] X. Yan, J. Han, and R. Afshar, “CloSpan: Mining closed
sequential patterns in large datasets,” in SIAM International
Conference on Data Mining, 2003, pp. 166–177.
[12] B. Le, H. Duong, T. Truong, and P. Fournier-Viger,
“FCloSM, FGenSM: Two efficient algorithms for min-
ing frequent closed and generator sequences using the lo-
cal pruning strategy,” Knowledge and Information Systems,
vol. 53, no. 1, pp. 71–107, 2017.
[13] T. Truong, H. Duong, B. Le, and P. Fournier-Viger, “FMax-
CloHUSM: An efficient algorithm for mining frequent
closed and maximal high utility sequences,” Eng. Applica-
tions of Artificial Intelligence, vol. 85, pp. 1–20, 2019.
[14] L. Szathmary, P. Valtchev, A. Napoli, and R. Godin, “Effi-
cient vertical mining of frequent closures and generators,”
in Int’l Symp. Intelligent Data Analysis, 2009, pp. 393–404.
[15] A. Tran, T. Truong, and B. Le, “Simultaneous mining of
frequent closed itemsets and their generators: Foundation
and algorithm,” Engineering Applications of Artificial In-
telligence, vol. 36, pp. 64–80, 2014.
[16] P. Fournier-Viger, C.-W. Wu, and V. S. Tseng, “Novel con-
cise representations of high utility itemsets using generator
patterns,” in International Conference on Advanced Data
Mining and Applications, 2014, pp. 30–43.
[17] P. Fournier-Viger, A. Gomariz, M. Sˇebek, and M. Hlosta,
“VGEN: Fast vertical mining of sequential generator pat-
terns,” in International Conference on Data Warehousing
and Knowledge Discovery, 2014, pp. 476–488.
[18] H. Duong, T. Truong, and B. Le, “Efficient algorithms for
simultaneously mining concise representations of sequential
patterns based on extended pruning conditions,” Eng. Appli-
cations of Artificial Intelligence, vol. 67, pp. 197–210, 2018.
[19] P. D. Gru¨nwald, I. J. Myung, and M. A. Pitt, Advances in
minimum description length: Theory and applications. MIT
press, 2005.
[20] M.-T. Tran, B. Le, B. Vo, and T.-P. Hong, “Mining non-
redundant sequential rules with dynamic bit vectors and
pruning techniques,” Applied Intelligence, vol. 45, no. 2, pp.
333–342, 2016.
[21] P. Fournier-Viger, A. Gomariz, T. Gueniche, A. Soltani, C.-
W. Wu, and V. S. Tseng, “SPMF: A Java open-source pattern
mining library,” The Journal of Machine Learning Research,
vol. 15, no. 1, pp. 3389–3393, 2014.
Trương Chí Tín là giảng viên tại Khoa
Toán – Tin học, Trường Đại học Đà Lạt.
Tác giả tốt nghiệp Cử nhân Toán tại Trường
Đại học Đà Lạt năm 1983 và nhận bằng
Tiến sĩ về Điều khiển tối ưu ngẫu nhiên
năm 1990 tại Đại học Quốc gia Hà Nội.
Hướng nghiên cứu hiện nay của tác giả là
trí tuệ nhân tạo và khai thác dữ liệu.
Trần Ngọc Anh đang giảng dạy và nghiên
cứu tại Khoa Toán – Tin học, Trường Đại
học Đà Lạt. Tác giả tốt nghiệp Đại học
ngành Toán – Tin học vào năm 1999 tại
Đại học Đà Lạt, nhận bằng Thạc sĩ và Tiến
sĩ về Khoa học máy tính vào các năm 2004
và 2016 tại Trường Đại học Khoa học Tự
nhiên, Đại học Quốc gia Tp. Hồ Chí Minh.
Tác giả đang nghiên cứu về khai thác dữ
liệu và trí tuệ nhân tạo.
Dương Văn Hải tốt nghiệp Trường Đại học
Đà Lạt ngành Tin học năm 2004. Tác giả
tốt nghiệp Cao học ngành Công nghệ thông
tin năm 2009 và đang là Nghiên cứu sinh
tại Trường Đại học Khoa học Tự nhiên,
Đại học Quốc gia Tp. Hồ Chí Minh. Tác
giả hiện đang giảng dạy và nghiên cứu về
khai thác dữ liệu tại Khoa Toán – Tin học,
Trường Đại học Đà Lạt.
Lê Hoài Bắc nhận bằng Cử nhân Toán
năm 1984, Cao học Khoa học máy tính
năm 1990 và hoàn thành Luận án Tiến sĩ về
Đảm bảo Toán học cho máy tính năm 2000
tại Trường Đại học Khoa học Tự nhiên,
Đại học Quốc gia Tp. Hồ Chí Minh. Tác
giả hiện là giảng viên tại Khoa Công nghệ
Thông tin, Trường Đại học Khoa học Tự
nhiên, Đại học Quốc gia Tp. Hồ Chí Minh và đang nghiên cứu
về trí tuệ nhân tạo, tính toán mềm, khai thác dữ liệu và khoa học
dữ liệu.
69