Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021
DOI: 10.15625/vap.2021.0068

KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ
Nguyễn Duy Hàm
Khoa Công nghệ thông tin - Trường Đại học Cơng nghệ TP. Hồ Chí Minh
Trường Cao đẳng An ninh mạng iSPACE
,
TĨM TẮT: Khai thác mẫu là bài tốn quan trọng, tiền đề cho khai thác luật kết hợp, nhằm tìm mối quan hệ hữu ích của các
mục trong dữ liệu. Khai thác mẫu cũng là bài toán quan trọng có nhiều ứng dụng trong các hệ thống thơng minh. Do đó, khai thác
mẫu là bài tốn được quan tâm nghiên cứu từ rất sớm, nhiều nghiên cứu đề xuất các thuật toán, phương pháp khai thác khá hiệu
quả, như đề xuất các cấu trúc Nlist, cấu trúc bit véctơ DBV, MBiS, IWS,… sử dụng để tăng tốc độ tính tốn trên các cơ sở dữ liệu
dày. So với các tiếp cận khác thì Bit véctơ khá hiệu quả, giảm bộ nhớ lưu trữ và tăng tốc độ tính toán do sử dụng các phép toán
bitwise. Trong bài báo này tác giả đề xuất một định lý để tính nhanh độ hỗ trợ trọng số trên cấu trúc MBiS giúp giảm thời gian tính
tốn trong q trình khai thác mẫu phổ biến trên cơ sở dữ liệu trọng số. Các kết qủa thực nghiệm đã cho thấy phương pháp đề xuất
hiệu quả hơn các phương pháp dựa trên MBiS, IWS, NFWI về thời gian thực thi.

Từ khoá: Mẫu phổ biến, cơ sở dữ liệu trọng số, bit véctơ, MBiS.
I. GIỚI THIỆU
Khai thác mẫu phổ biến là bài toán quan trọng có nhiều ứng dụng trong thực tế. Nhu cầu về tìm mối liên hệ giữa
các dữ liệu trong cơ sở dữ liệu (CSDL) là rất lớn và thực tế nên các nghiên cứu về mẫu phổ biến, luật kết hợp đã được
quan tâm từ rất sớm [1-2].
Trong khai thác mẫu phổ biến có ba hướng tiếp cận chính, đó là: Thuật toán Apriori [1], thuật toán này theo tư
tưởng vét cạn các khả năng sinh ra tập phổ biến bằng cách sinh tập phổ biến nhiều phần tử hơn từ tập phổ biến ít phần
tử đã tìm thấy trước đó. Do việc quét CSDL nhiều lần nên cách tiếp cận này rất tốn thời gian, sau đó giải pháp sử dụng
thuật toán FP-Growth dựa trên cây FP-Tree với hai lần quét CSDL, đây cũng là một giải pháp hiệu quả, theo hướng
nghiên cứu này các tác giả đã đề xuất các cải tiến khá hiệu quả cho bài toán khai thác mẫu như NodeList, Nlist [1012]… tuy nhiên cách tiếp cận này không hiệu quả khi xét trên các ngưỡng lớn để tìm một tập nhỏ các mẫu phổ biến
phục vụ cho một nhiệm vụ cụ thể nào đó; Tiếp theo là tiếp cận theo thuật toán Eclat dựa trên cây IT-tree với chỉ một
lần đọc dữ liệu [6-9][13]. Cách tiếp cận này khá hiệu quả do quá trình cắt tỉa nhanh các nhánh chắc chắn không sinh ra
mẫu phổ biến dựa trên ngưỡng đưa vào, song việc lưu trữ các tidset của tập mục lại tốn khá nhiều bộ nhớ. Theo hướng
tiếp cận này cũng đã có nhiều cải tiến như sử dụng diffset thay cho tidset, sử dụng bit véctơ để lưu trữ tidset/diffset của

các tập mục như DBV [6], MBiS [7], IWS [8], các cải tiến này đã cho thấy hiệu quả rõ rệt trong lưu trữ và tăng tốc độ
tính tốn.
Tiếp cận bit véctơ là một tiếp cận hiệu quả với phương pháp Eclat, do thao tác tính giao các tidset của các tập
mục chiếm phần lớn thời gian khai thác, mà tiếp cận này giúp cho việc tính nhanh do sử dụng các phép toán bitwise,
đồng thời tiếp cận này cũng làm giảm bộ nhớ lưu trữ tidset của các tập mục. Trong bài báo này tác giả áp dụng phương
pháp lưu tidset của các tập mục bằng cách lưu thành các đoạn giao dịch liên tiếp để giảm không gian lưu trữ tidset,
đồng thời đề xuất một định lý trọng số về việc tính gộp tổng các trọng số các đoạn giao dịch liên tiếp giúp tính nhanh
độ hộ trợ của các tập mục trong quá trình khai thác. Phương pháp này cải thiện đáng kể thời gian tính tốn trong q
trình khai thác mẫu phổ biến trên cơ sở dữ liệu có trọng số.
Ngoài phần mở đầu, bài báo được cấu trúc như sau: Phần II trình bày về các nghiên cứu liên quan của bài tốn;
phương pháp đề xuất được trình bày trong Phần III; Phần IV là kết quả thực nghiệm; kết luận và hướng nghiên cứu tiếp
theo được trình bày trong Phần V.
II. CÁC NGHIÊN CỨU LIÊN QUAN
A. Bài toán khai thác mẫu phổ biến trên CSDL trọng số
Bài toán khai thác mẫu phổ biến được phát biểu như sau: là một bộ gồm ba thành phần: <T, I, W >, trong đó:
T = {t1, t2, ..., tm} là tập gồm m giao dịch của CSDL.
I = {i1, i2,.., in} là tập gồm n mục trong CSDL
W = {w1, w2, …, wn} là tập gồm n trọng số của n mục tương ứng trong tập I
Ví dụ 1: Cho CSDL DB gồm 6 giao dịch như Bảng 1, có 5 mục {A, B, C, D, E} và trọng số tương ứng của các
mục như trong Bảng 2.


KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ

268

Giao dịch

t1
t2

t3
t4
t5
t6

Bảng 1. CSDL DB
Các mục trong giao dịch

Bảng 2. Trọng số các mục trong DB
Mục
Trọng số

A, B, D, E
B, C, E
A, B, D, E
A, B, C, E
A, B, C, D, E
B, C, D

A
B
C
D
E

0,6
0,1
0,3
0,9
0,2


Tidset của tập mục X là tập hợp các giao dịch chứa X. Như vậy:
tidset(X) ={t|t ∈ T}

Tao và các cộng sự [5] đã đề xuất cơng thức tính trọng số giao dịch tw và độ hỗ trợ trọng số ws của tập mục X
dùng trong khai thác mẫu phổ biến trên CSDL trọng số.
Công thức xác định trọng số của mỗi giao dịch tk:
tw(tk) =

∑𝑖

𝑗∈(𝑡𝑘)

𝑤𝑖𝑗

(1)

𝑠(𝑡𝑘 )

­ tw(𝑡𝑘 ) là trọng số của giao dịch 𝑡𝑘
­ 𝑤𝑖𝑗 là trọng số của mục 𝑖𝑗 trong 𝑡𝑘
­ 𝑠𝑠(𝑡𝑘 ) là số các mục có mặt trong giao dịch 𝑡𝑘
Giao dịch
t1
t2
t3
t4
t5
t6
Sum tw


Bảng 3. Giá trị tw của CSDL DB
tw

𝑡𝑤(𝑡1 ) =

𝑡𝑤(𝑡2 ) =
𝑡𝑤(𝑡3 ) =
𝑡𝑤(𝑡4 ) =
𝑡𝑤(𝑡5 ) =
𝑡𝑤(𝑡1 ) =

Giá trị
0,45

4
0,1+0,3+0,2

=
=

0,20

=

0,45

4
0,6+0,1+0,3+0,2


=

0,3

=

0,42

=

0,43

0,6+0,1+0,9+0,2
3
0,6+0,1+0,9+0,2

4
0,6 + 0,1 + 0,3 + 0,9 +0 ,2

5
0,1 + 0,3 + 0,9
4

0,45 + 0,20 + 0,45 + 0,3 + 0,42 + 0,43

2,25

Công thức xác định độ hỗ trợ trọng số của mỗi tập mục X:
ws(X) =


∑𝑡

𝑘∈𝑡(𝑋)

𝑡𝑤(𝑡𝑘 )

(2)

𝑆𝑢𝑚(𝑡𝑤)

Với, t(X) là tập các giao dịch chứa tập mục X và sum(tw)= ∑𝑚
𝑘=1 𝑡𝑤 (𝑡𝑘 )
Ví dụ, với tập mục BD ở ví dụ 1.4 được xác định như sau:
ws(BD) =

𝑡𝑤(𝑡1 )+𝑡𝑤(3)+𝑡𝑤(𝑡5 )+𝑡𝑤(𝑡6 )
𝑤(𝑡1 )+𝑡𝑤(2)+𝑡𝑤(3)+𝑡𝑤(4)+𝑡𝑤(𝑡5 )+𝑡𝑤(𝑡6 )

=

0,45+0,45+0,42+0,43
2,25

≈ 0,78

Tập mục X được gọi là phổ biến nếu và chỉ nếu ws(X) ≥ minws, với minws được xác định bởi người sử dụng.

Bài toán khai thác mẫu phổ biến trọng số - frequent weighted (FWI) là bài tốn tìm tất cả các tập mục X (X ⊆ I)
thỏa mãn ws(X) ≥ minws, với minws là đại lượng được cho trước.


B. Một số tiếp cận khai thác mẫu phổ biến

Bài toán khai thác FWI trên CSDL trọng số được đề xuất lần đầu tiên bởi Ramkumar và đồng sự [4], trong
nghiên cứu này, các tác giả đã đưa ra mơ hình mơ tả khái niệm về luật kết hợp có trọng số, trong đó đề xuất thuật tốn
WIS để khai thác FWI. Sau đó Tao và đồng sự [5] đề xuất độ đo trọng số giao dịch tw (transaction weight) theo công
thức 1 và giá trị ws (weighted support) theo công thức 2 để khai thác mẫu phổ biến trọng số. Theo cách tiếp cận này thì
giá trị ws của tập mục vừa phản ánh được mức độ xuất hiện của tập mục trong các giao dịch, vừa thể hiện được mức độ
quan trọng khác nhau của các giao dịch. Một ưu điểm nữa của cách tiếp cận này là thỏa mãn tính chất bao đóng giảm
một cách tự nhiên. Tuy nhiên, thuật toán do Tao và đồng sự đề xuất dựa vào việc sinh ứng viên theo phương pháp
Apriori nên cần đọc CSDL nhiều lần, dẫn đến tốn thời gian xử lý và cả bộ nhớ lưu trữ và hiện nay hướng tiếp cận này
không được tiếp tục phát triển. Tiếp theo, Han và các công sự đã đề xuất hướng tiếp cận mới dựa trên cây FP-tree với
thuật toán FP-Growth [2]. FP-Growth đọc CSDL lần thứ nhất để tạo cây FP-tree, lần thứ 2 để chiếu lên cây và duyệt
cây xác định các tập phổ biến. Sau đó Deng và các cộng sự [12] đề xuất cấu trúc N-list giúp khai thác nhanh trong quá
trình duyệt cây FP-tree cùng một số kĩ thuật cắt nhánh trong tạo cây FP-tree làm giảm thời gian khai thác. Dựa trên cấu


Nguyễn Duy Hàm

269

trúc N-list, sau đó Bui và các cơng sự [11] đề xuất cấu trúc WN-List hiệu quả hơn với việc sử dụng khái niệm subsume
để cắt nhánh nhanh và tăng tốc tính tốn trên cây WN-tree. Tuy nhiên, các tiếp cận theo hướng này tốn thời gian trong
xây dựng cây ban đầu, do đó với các trường hợp ngưỡng đủ lớn thì cách tiếp cận này chưa thật sự hiệu quả.
Một tiếp cận khác là theo phương pháp Eclat [3]. Dựa trên tiếp cận này Vo và các đồng sự [13] đề xuất cách
thức lưu trữ trọng số trên cây WIT-tree là một mở rộng của cây IT-tree. Do chỉ cần quét CSDL một lần, cùng với áp
dụng chiến lược diffset thay cho tidset nên đã giảm được không gian lưu trữ tập giao dịch của các tập mục, đồng thời
giúp giảm thời gian trong khai thác FWI trên cây WIT-tree, nên phương pháp này tỏ ra hiệu quả hơn phương pháp theo
hướng tiếp cận Apriori trước đó, tuy nhiên diffset chỉ có hiệu quả trên các CSDL dày và kém hiệu quả trên CSDL thưa.
Sau đó Nguyen và các cộng sự [8] đề xuất thuật toán hiệu quả hơn bằng việc cải tiến bit véctơ - cắt bỏ các đoạn bit 0
liên tiếp trong biểu diễn tidset của các tập mục để tối ưu tính tốn và bộ nhớ rút ngắn thời gian khai thác. Các cải tiến

sử dụng Bit Véctơ trong biểu diễn tidset chưa thật sự có hiệu quả trên CSDL dày do mật độ các mục xuất hiện trong
các giao dịch là lớn nên việc cắt bỏ các bit 0 trong biểu diễn tidset khơng có nhiều ý nghĩa, mặt khác trong các tính
tốn độ hỗ trợ định lượng (trọng số và số lượng) của các tập mục còn mất nhiều thời gian do phải duyệt tất cả các bit 1
trong bit véctơ.
III. THUẬT TOÁN ĐỀ XUẤT
A. Biểu diễn tidset của tập mục
Nguyen và các cộng sự [7] đã đề xuất cấu trúc MBiS để giảm không gian lưu trữ tidset trong khai thác mẫu phổ
biến trên CSDL số lượng. Thay vì lưu tồn bộ các ID giao dịch của tập mục, MBiS chỉ cần lưu đầu mút của các đoạn
liên tiếp. Ví dụ item A xuất hiện trọng các giao dịch 1, 3, 4, 5 thì MBiS(A)= {[1][3,5]} nghĩa là tidset(A) chỉ có 2 đoạn,
đoạn 1 là giao dịch 1, đoạn 2 là từ giao dịch 3 đến giao dịch 5. Cách biểu diễn này cũng làm cho việc tính giao các
MBiS của tập mục nhanh hơn do chỉ cần cập nhật lại đoạn đầu và cuối của các đoạn giao. Trong bài báo này tác giả sử
dụng cấu trúc MBiS để lưu tidset của các tập mục.
B. MBiS-Tree
MBiS - Tree của CSDL DB là cây có 1 nút cha, mỗi nút con gồm ba thành phần:
- X: là tập mục của;
- ws: là độ hộ trợ trọng số của X;
- MBiS(X).
Lớp node thứ nhất của MBiS-tree là các tập mục 1 phần tử có ws thoả minws. Các nút trên cùng một mức của
MBiS-tree được kết hợp với nhau để tạo ra nút ở mức kế tiếp nếu ws của tập mục nút tạo thành thoả minws. Khi nút X kết
hợp với nút Y trên cùng một mức của cây để tạo ra nút Z = X ∪ Y và nút Z chỉ được thêm vào cây nếu ws(Z) > minws
MBiS(Z) = MBiS(X) ∩ MBiS(Y)

Các nút của MBiS-tree sau khi xây dựng xong chính là các mẫu phổ biến thoả mãn minws.
C. Thuật toán xác định giao của hai MBiS
Thuật toán 1 duyệt theo chiều dài của hai MBiS và tính các đoạn giao của hai MBiS này để tạo ra MBiS với tập
mục mới kết hợp tạo thành

Hình 1. Thuật tốn xác định giao hai MBiS

Độ phức tạp thuật toán INTERSECTION_WS là O(n1+m1) với n1 và m1 là số đoạn của MBiS(X) và MBiS(Y).



KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ

270

D. Thuật tốn tính nhanh ws của tập mục
Việc tính ws của các tập mục dựa trên MBiS khá đơn giản là duyệt hết các đoạn trong MBiS sau đó tính tổng tw
của các giao dịch theo thuật tốn như trong Hình 2.

Hình 2. Thuật tốn tính ws dựa trên MBiS

Trong quá trình xây dựng cây MBiS để khai thác mẫu phổ biến thao tác tính ws của các tập mục tạo thành được
thực hiện rất nhiều lần, tập mục nào có ws > minws mới được thêm vào cây MBiS. Để tính ws theo thuật tốn 2, với
mỗi tập mục, ta phải xét hết tất cả các đoạn bit trong MBiS của tập mục đó (dịng 1 và 2).
Do cấu trúc của MBis là lưu hai đầu mút các đoạn bit 1 liên tiếp nhau, biễn diễn cho tập mục xuất hiện trong các
giao dịch liền nhau, ví dụ MBiS(A) ={[1, 1],[3, 5]}nghĩa là A xuất hiện trong giao dịch 1 và trong các giao dịch từ 3
đến giao dịch 5, do đó ws(A) = tw1+ tw3+ tw4+ tw5.
Định lý 1: Gọi PAi là tổng tw của các giao dịch từ giao dịch 1 đến giao dịch i ( ∀ i ∈ [1..m] với m là số lượng
giao dịch của CSDL) thì tổng tw từ giao dịch l đến giao dịch k (l ≤ k ≤ m) được xác định theo công thức sau:
ws(tl) + ws(tl+1) +..+ ws(tk-1) + ws(tk) = PAk -PAl-1.

(3)

Chứng minh:
Theo định lý ta có PAk = tw1 + tw2 +…+ twk, tương tự PAl-1 = tw1 + tw2 +…+twl-1
Do đó, với k ≥ l ta có: PAk -PAl-1 = (tw1 + tw2 +…+twk) - ( tw1 + tw2 +…+twl-1)

⟹ PAj -PAi-1 = ws(tl) + ws(tl+1) +..+ ws(tk-1) + ws(tk)
Định lý đã được chứng minh.


Ngoài ra, theo định nghĩa của PA trong Định lý 1 ta có thể xác định các PAi rất đơn giản theo công thức sau:
PAi = [ws(t1) + ws(t2) +..+ ws(ti-1) ]+ ws(ti) = PAi-1 + ws(ti)
Ví dụ, với CSDL DB ta tạo bảng PA của ws các giao dịch theo công thức 4 như sau:
Index 0
tw
0
PA
0

1
0,45
0,45

2
0,20
0,65

3
0,45
1,1

4
0,30
1,4

5
0,42
1,82


(4)

6
0,45
2,25

Vậy, theo công thức 3 của Định lý 1 ta có:
ws(A) = (PA1 - PA0) + (PA5 - PA2) = (0,45 - 0) + (1,82 - 0,65) =1,62
Tương tự ta có: ws(B) = PA6 - PA0 = 2,25 - 0 = 2,25.
Tính ws của các tập mục dựa trên Định lý 1 được thực hiện theo thuật tốn trong Hình 3.

Hình 3. Thuật tốn tính nhanh ws dựa trên MBiS

Độ phức tạp thuật tốn = O(k) với k là số đoạn của MBiS(X).
E. Thuật toán khai thác nhanh FWI
MBiS - Tree được tạo ra với thuật tốn FAST_MBiS-tree được trình bày trong Hình 4 với đầu vào là tập P chứa các

mục thoả mãn minws và minws


Nguyễn Duy Hàm

271

Hình 4. Thuật tốn xây dựng MBiS-tree khai thác nhanh FWI

Ví dụ minh hoạ với CSDL DB trong ví dụ 1 và minws = 0,5:
Bước 1: Tính MBiS ws của các tập mục một phần tử như Bảng 5 và mảng PA như Bảng 4.
Bảng 5. MBiS của các mục


Mục
A
B
C
D
E

Tidset
1, 3, 4, 5
1, 2, 3, 4, 5, 6
2, 4, 5, 6
1, 3, 5, 6
1, 2, 3, 4, 5

MBiS
[1][3,5]
[1,6]
[2][4,6]
[1][3][5][6]
[1,5]

ws
0,72
1,00
0,60
0,78
0,81

Bước 2: Xây dựng MBiS-tree theo thuật toán 4.
Tất cả các tập mục 1 phần tử {A, B, C, D, E} (tập P ban đầu ) đều thoả minws.


Hình 5. Cây MBiS-tree với CSDL DB và minws = 0,5

Với mục A ta có wsA = 0,72, MBiS(A) ={[1][3,5]} kết nối với B có wsB = 1,0, MBiS(B) = {[1,6]} tạo ra tập mục
AB có wsAB = 0,72 > minws và MBiS(AB) = MBiS(A) ∩ MBiS(B) ={[1][3,5]} ∪ {[1,6]} ={[1][3,5]} thêm node AB vào
MBiS-tree. Tương tự ta có các node AD, AE, … cuối cùng ta có MBiS-tree như Hình 5.

Bước 3: Xuất ra cây MBiS gồm các node là mẫu phổ biến khai thác được bao gồm: {A, B, C, D, E, AB, AD, AE,
BC, BD, BE, DE, ABD, ABE, ADE, BDE, ABDE}.
IV. KẾT QUẢ THỰC NGHIỆM
A. Môi trường thực nghiệm
Các thuật tốn được cài đặt trên máy tính với cấu hình Intel i7-3632QM, CPU 2.2-GHz và RAM 8 GB, hệ điều
hành Windows 10, sử dụng C# (phiên bản 2016).


KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ

272

Bốn CSDL thực nghiệm được lấy từ website với đặc điểm được mô tả ở Bảng 6. Để
đảm bảo tính khách quan của phương pháp đề xuất, tác giả chọn CSDL RETAIL và BMS-POS là các dữ liệu thưa, hai
CSDL còn lại CONNECT và ACCIDENTS là các CSDL dày. Các CSDL này đều được thêm bảng trọng số bằng cách
sinh ngẫu nhiên trong khoảng [0,1].
Bảng 6. Mô tả CSDL thực nghiệm
Số lượng mục
Số lượng giao dịch
16.470
88.162
1.657
515.597


Stt
1
2

CSDL
RETAIL
BMS-POS

Ghi chú
Thêm trọng số
Thêm trọng số

3

CONNECT

468

340.183

Thêm trọng số

4

ACCIDENTS

130

67.557


Thêm trọng số

Tác giả tiến hành so sánh thời gian chạy với các phương pháp DBV[6], IWS[8], MBiS (Chỉnh sửa từ
MBiS_FWUI) [7] và NFWI[12]. Với mỗi ngưỡng thực nghiệm tác giả chạy 10 lần sau đó lấy kết quả trung bình của 10
lần chạy. Tất cả các phương pháp đều chạy trên cùng một nền tảng để đảm bảo kết quả khách quan nhất có thể. Về bộ
nhớ FAST_MBiS khơng có thay đổi nào với phương pháp MBiS thơng thường, trong q trình so sánh tác giả không
nhận thấy khác biệt nhiều về bộ nhớ giữa các phương pháp. Do đó trong bài báo này tác giả chỉ trình bày phần thực
nghiệm với thời gian thực thi.
B. So sánh thời gian thực thi
120

DBV

100

FAST_MBiS

MBiS

NFWI

80
60
40
20
0
6

4


2

MINWS (%)

1

0,2

0,1

0,2

0,1

0,2

0,1

Hình 6. So sánh thời gian chạy trên CSDL retail
250

DBV

200

FAST_MBiS

NFWI


MBiS

150
100
50
0
6

4

2

MINWS (%)

1

Hình 7. So sánh thời gian chạy và trên CSDL BMS-POS
250

DBV

200

FAST_MBiS

NFWI

MBiS

150

100
50
0
6

4

2

MINWS (%)

1

Hình 8. So sánh thời gian chạy trên CSDL connect


Nguyễn Duy Hàm

273

200
150

DBV

FAST_MBiS

NFWI

MBiS


100
50
0

6

4

2

MINWS (%)

1

0,2

0,1

Hình 9. So sánh thời gian chạy trên CSDL accidents

Từ kết quả thực nghiệm từ Hình 6 đến Hình 9 trên chúng ta có thể thấy, FAST_MBiS hiệu quả hơn các phương
pháp MBiS, và DBV trong toàn bộ ngưỡng minws. Tuy nhiên, đối với phương pháp NFWI - là phương pháp sử dụng
cấu trúc NLIST với tiếp cận FP-Growth nên đọc CSDL hai lần do đó tốn thời gian đọc CSDL, nên với các ngưỡng
minws lớn NFWI chạy chậm hơn các phương pháp còn lại do cây được tạo thành của DBV, MBiS, FAST_MBiS rất
nhỏ khi ngưỡng lớn nên cắt nhánh rất nhanh, và với các ngưỡng minws lớn thì FAST_MBiS có hiệu quả hơn hẳn các
phương pháp còn lại.
V. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Bài báo đề một phương pháp khai thác mẫu phổ biến trọng số hiệu quả bằng cách áp dụng cấu trúc cây MBiS
trong khai thác mẫu phổ biến trên CSDL số lượng (định lượng) [7], đồng thời cải tiến thuật tốn tính độ hỗ trợ trọng số

ws dựa trên cấu trúc MBiS bằng cách áp dụng kĩ thuật prefix sum arrary. Các kết quả thực nghiệm cho thấy thuật toán
hiệu quả hơn các phương pháp tiếp cận theo hướng bit véctơ như DBV, IWS, và hiệu quả hơn NFWI với cấu trúc
NLIST theo tiếp cận FP-Growth ở các ngưỡng minws lớn.
Trong thời gian tới tác giả tiếp tục nghiên cứu áp dụng phương pháp này cho các bài toán khai thác mẫu trên cơ
sở dữ liệu phân cấp và các bài toán khai thác mẫu top rank k, top k.
TÀI LIỆU THAM KHẢO
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]

Agrawal, R., Srikant, R. Fast algorithms for mining association rules. VLDB’94, pp. 487-499, 1994.
Han, J., Pei, J., & Yin, Y. Mining frequent patterns without candidate generation. Proc. of Conf on ACM SIGMOD
management of data, pp. 112, 2000.
Zaki, M. J. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), pp.
372-390, 2000.
Ramkumar, G. D., Ranka, S., & Tsur, S. Weighted Association Rules: Model and Algorithm. Proc. of Conference on
Knowledge Discovery and Data Mining - KDD, pp. 1-13, 1998.
Tao, F., Murtagh, F., & Farid, M. Weighted Association Rules mining using weighted support and signifocance framework.
Proc. of Conference on ACM SIGKDD, pp. 661-666, 2003.
Vo, B., Hong, P. T., & Le, B. DBV-Miner: A Dynamic bit - Vectơr approach for fast mining frequent close itemsets. Expert

Systems with Applications, 39(8), pp. 7196-7206, 2012.
Nguyen, D. H., Vo, D. B., Nguyen, T. H. M., Hong, T. P. MBiS: an efficient method for mining frequent weighted utility
itemsets from QDB. Journal of Computer Science and Cybernetics, 31(1), pp.17-30, 2015.
Nguyen, D. H., Vo, B., Nguyen, T. H. M., Witold, P. An efficient algorithm for mining frequent weighted itemsets using
interval word segments, Applied Intelligence 45(4), pp.1008 -1020, 2016.
Huynh M. H., Nguyen T. T. L., Vo B. Nguyen A., Tseng V. S. Efficient methods for mining weighted clickstream patterns.
Expert Systems with Applications, 142, 112993, 2020.
Vo B., Bui H., Vo T., Le T. Mining top-rank-k frequent weighted itemsets using WN-list structures and an early pruning
strategy. Knowledge Based Systems, 201-202, 106064, 2020.
Bui H., Vo B., Nguyen H., Nguyen Hoang T. A., Hong T. P. A weighted N-list-based method for mining frequent weighted
itemsets. Expert Systems with Applications, 96, pp. 388-405, 2018.
Deng, Z., Wang, Z., & Jiang, J. A new algorithm for fast mining frequent item- sets using N-lists. Science China Information
Sciences, 55(9), pp. 2008-2030, 2012.
Vo, B., Coenen, F., & Le, B. A new method for mining frequent weighted itemsets base on WIT-trees. Expert systems with
applications, 40(4), pp. 1256-1264, 2013.


274

KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ

FAST MINING OF FREQUENT PATTERN ON THE WEIGHTED DATABASE
Nguyen Duy Ham
ABSTRACT: Frequent pattern mining is an important problem, the premise for association rule mining, to find useful
relationships of items in the data. Frequent pattern mining is also an important problem that has many applications in intelligent
systems. Therefore, pattern mining is a problem that has been studied very early, many studies have proposed quite effective mining
algorithms and methods, such as the proposed Nlist structures, Bit véctơr structures DBV, MBiS, IWS,… or used to speed up
computation on thick databases. Compared with other approaches, bit véctơrs are quite efficient, reducing storage memory and
increasing computational speed due to the use of bitwise operations. In this paper, we propose a theorem for calculating weighted
support on the segment of MBiS bit segment, used to quickly calculate the support of the generated item set to help reduce the

computation time of the common pattern mining problem on the weighted database. The experimental results have shown that the
proposed method is more efficient than the existing methods in terms of execution time.