Thuật toán khai thác tập phổ biến từ cơ sở dữ liệu số lượng có sự phân cấp các mục

Cách tiếp cận này khá thực tế, bởi CSDL có sự phân cấp thì các mục cha ở mỗi mức có một giá trị ảnh hưởng 
khác nhau. 
Tseng và các đồng sự [7] đề xuất hướng tiếp cận sử dụng FP-tree với thuật toán FP-Growth trong khai thác tập 
phổ biến với nhiều ngưỡng hỗ trợ. Cách tiếp cận này khá tốt với chỉ hai lần đọc CSDL, tuy nhiên quá trình duyệt cây 
FP-tree lại tốn khá nhiều thời gian. 
Vo và các đồng sự [8] sử dụng hướng tiếp cận Eclat với việc đề xuất cấu trúc GIT-tree là một mở rộng của IT-
tree với chỉ một lần đọc CSDL. Bước đầu tiên thêm các mục cha vào CSDL, bước thứ hai, đọc CSDL để chuyển CSDL 
sang chiều dọc. Sau đó sử dụng cấu trúc GIT-tree để khai thác tập phổ biến. 
Một số nghiên cứu khác trong thời gian gần đây khai thác trên CSDL có sự phân cấp item theo thời gian [13], 
hay khai thác mẫu phổ biến phân cấp [14] từ đó sinh luật kết hợp phân cấp với một ngưỡng phổ biến theo hai tiếp cận 
Aprriori hay FP-Growth. Các nghiên cứu này là các trường hợp riêng của bài toán khai thác tập phổ biến trên CSDL 
nhị phân có sự phân cấp item. 
C. CSDL số lượng có sự phân cấp các mục 
CSDL số lượng có sự phân cấp các mục là một bộ DB = , trong đó: T = {t1, t2, , tm} là tập các 
giao dịch, I = {i1, i2, , in} là tập các mục, W = {w1, w2, , wn} là tập các trọng số (lợi ích) tương ứng của mỗi mục 
trong tập các mục I, và H là tập các cây phân cấp thể hiện mối quan hệ giữa các mục. Mỗi giao dịch tk có dạng tk = {xk1, 
xk2, , xkn}, trong đó xki là số nguyên chỉ số lượng mục thứ i trong giao dịch tk, k = 1.. m, . 
Ví dụ 1: cho CSDL số lượng DB = như sau: 
Tập các mục I = {A, B, C, D, E, F} 
Tập các trọng số W = {0.3, 0.2, 0.5, 0.6, 0.9, 0.1} như trong bảng 2 
Tập các giao dịch T được cho trong bảng 1 dưới đây: 
Bảng 1. Các giao dịch Bảng 2. Bảng trọng số 
Giao dịch A B C D E F Mục Trọng số 
t1 1 1 0 2 1 0 A 0.3 
t2 0 1 3 0 1 0 B 0.2 
t3 2 1 0 2 2 2 C 0.5 
t4 3 1 1 0 1 0 D 0.6 
t5 1 2 2 1 3 1 E 0.9 
t6 0 1 1 1 0 1 F 0.1 
Và tập các cây phân cấp Tr 
Trong đó các kí hiệu A, B, C, D, E, F là đại diện cho tập các mặt hàng theo bảng sau: 
Bảng 3. Tên mặt hàng của các mục
Mục Tên mặt hàng 
A Desktop 
B Ink-jet Printer 
C Laser Printer 
B 
E 
C 
 G F 
K 
A D 
H 
Hình 1. Tập các cây phân cấp Tr 
Nguyễn Duy Hàm, Võ Đình Bảy, Nguyễn Thị Hồng Minh 681 
D Notebook 
E Scanner 
F Dot-matrix Printer 
G Non-impact 
H PC 
K Printer 
Theo bảng 1, và bảng 2, CSDL DB có 6 giao dịch {t1, t2, t3, t4, t5, t6} và 6 mục {A, B, C, D, E, F}, trọng số của 
các mục tương ứng là {0.3, 0.2, 0.5, 0.6, 0.9, 0.1}. Giao dịch t1 = {1, 1, 0, 2, 1, 0} có nghĩa là trong giao dịch t1 có một 
mục A (Desktop), một mục B (Ink-jet Printer), hai mục D (Notebook), một mục E (Scanner), và không có mục C (Laser 
Printer) và mục F (Dot-matrix Printer) nào. 
Tập J = {G, K, H} là tập các mục nút cha của cây phân cấp, là các mục không xuất hiện trong các giao dịch của 
CSDL DB. Tuy nhiên chúng có vai trò nhất định, thể hiện mối quan hệ của các mục trong CSDL. Do đó, khi khai thác 
tập phổ biến trên CSDL phân cấp đòi hỏi phải khai thác cả tập các mục trên cây phân cấp bao gồm (I ∪ J). 
Liu và các đồng sự [11] đưa ra hai định nghĩa để khai thác tập phổ biến từ CSDL có sự phân cấp các mục như sau: 
Định nghĩa 1: Một giao dịch t = với X ∈ (I ∪ J), X = (Y ∪ Z) là tập các mục có trong giao dịch (Y) và 
các mục cha của Y trên cây phân cấp (Z). 
Định nghĩa 2: Tập X là tập phổ biến thì suport(X) > minsup, đồng thời trong X không tồn tại một cặp mục nào 
có quan hệ cha con, như vậy X là phổ biến khi: 
൜ ܵݑ݌݌݋ݎݐሺܺሻ 	൒ 	݉݅݊ݏݑ݌∀ ௜ܺ, 	 ௝ܺ 	 ∈ ܺ, ௜ܺ	 ് ܲܽݎ݁݊ݐሺ ௝ܺሻ	 
Khai thác FWUI trên CSDL số lượng có sự phân cấp có những đặc trưng riêng khác với trên CSDL nhị phân có 
sự phân cấp, bởi các mục trong CSDL có kèm theo số lượng và trọng số. Do đó, để khai thác tập phổ biến trên CSDL 
có sự phân cấp các mục bao gồm cả các mục nút cha, chúng tôi đề xuất các định nghĩa sau: 
Định nghĩa 3: Nút cha trên cây phân cấp thuộc các giao dịch chứa nút con của nó. 
Với mỗi mục nút cha X trên cây phân cấp và tk ∈ T: 
X	∈	tk nếu và chỉ nếu Y ∈	tk và Y là con ở nút lá của X trên cây phân cấp. 
Khai thác tập phổ biến trên CSDL sỗ lượng có sự phân cấp, cần xác định trọng số của các mục nút cha trên cây 
phân cấp, đồng thời phải xác định số lượng của các mục cha trong mỗi giao dịch mà nó có mặt. Do các mục cha này sẽ 
được thêm vào các giao dịch trước khi khai thác theo định nghĩa 3. 
Để đảm bảo các mục nút cha sau khi thêm vào các giao dịch trong CSDL không quá khác biệt với các mục con 
ở nút lá, đồng thời các mục nút cha vẫn thể hiện được vai trò của nó, trong bài báo này chúng tôi xác định trọng số mục 
nút cha và số lượng của chúng trong mỗi giao dịch theo định nghĩa 4 và 5. 
Định nghĩa 4: Trọng số của mục nút cha trên cây phân cấp bằng trọng số lớn nhất của trọng số các nút con của 
nó ở nút lá: 
weight(A)	= max(weight(A1), weight(A1), .. weight(Ak)) 
Trong đó A là mục nút cha trên cây phân cấp, A1, A2, .., Ak là các nút lá của A 
Ví dụ 2: weight(K) = max(weight(C), weight(B), weight(F)) = max(0.5, 0.2, 0.1) = 0.5 
Theo định nghĩa 4, các mục nút cha ở mức càng thấp thì trọng số càng cao, điều này phản ánh được độ “quan 
trọng” của các mục ở mức khái quát, nghĩa là các mục ở mức khái quát càng cao thì trọng số càng lớn. 
Định nghĩa 5: Số lượng của mục nút cha trên cây phân cấp ở trong giao dịch nào thì bằng số lượng lớn nhất của 
số lượng các nút con của nó ở trong giao dịch đó. 
quantitative(A) ∈ tk = max(quantitative(A1), quantitative(A1), .. quantitative(Ak)) 
Trong đó: A1, A2, .., Ak ∈	tk và A1, A2, .., Ak là con của A trên cây phân cấp. 
Ví dụ 3: quantitative(K)	∈ t5 = max(quantitative(B), quantitative(C), quantitative (F)) (B, C, F	∈ t5) = max(2, 2, 
1) = 2 
Việc xác định số lượng các mục nút cha khi thêm vào các giao dịch có chứa các nút con của nó theo định nghĩa 
5 đảm bảo được vai trò của nó khi thêm vào CSDL, đồng thời số lượng của mục nút cha cũng không quá chênh lệnh so 
với số lượng của các nút con của nó. 
Định nghĩa 6: Itemset X ∈	(I ∪ J) với I là tập mục trong CSDL ban đầu (tập nút lá trên cây phân cấp) và J là tập 
các mục nút cha trên cây phân cấp được gọi là phổ biến theo ngưỡng minwus nếu wus(X) ൒ minwus, với minwus do 
người dùng xác định trước. 
682 THUẬT TOÁN KHAI THÁC TẬP PHỔ BIẾN TỪ CƠ SỞ DỮ LIỆU SỐ LƯỢNG CÓ SỰ PHÂN CẤP CÁC MỤC 
III. THUẬT TOÁN KHAI THÁC TẬP PHỔ BIẾN TỪ CSDL SỐ LƯỢNG CÓ SỰ PHÂN CẤP CÁC MỤC 
A. Cấu trúc HIT-tree 
Chúng tôi đề xuất một cấu trúc dữ liệu có tên HIT-tree, đây là một mở rộng của IT-tree [2] dùng để khai thác 
tập phổ biến trên CSDL số lượng có sự phân cấp mục theo tiếp cận khai thác từ CSDL theo chiều dọc với một lần đọc 
CSDL. Mỗi nút trên HIT-Tree gồm 3 thành phần: 
- itemset X – tập các mục trong CSDL 
- tidset X – tập các giao dịch chứa X 
- wus(X) – độ hỗ trợ trọng số hữu ích của X 
HIT-tree gồm nhiều mức, mỗi mức gồm nhiều lớp tương đương, mỗi lớp tương đương gồm nhiều nút. Các cặp 
itemset trên hai nút trong cùng một lớp tương đương kết hợp với nhau để tạo ra nút mới ở mức tiếp theo. Do đó, các 
itemset trên các nút cùng một lớp tương đương có cùng số lượng mục và chỉ khác nhau phần tử cuối cùng. Itemset X 
được tạo ra từ hợp hai itemset của hai nút cùng một lớp tương đương phải thỏa mãn hai điều kiện để được thêm vào 
HIT-tree: 
- ∀x’ ∈ X ൓x”∈ X: parent(x’) = x” (Không có cặp mục nào có mối quan hệ cha con trong X) 
- wus(X) ൒ minwus 
Sau khi xây dựng xong, các itemset trên các nút của HIT-tree chính là tập FWUI cần tìm theo ngưỡng minwus. 
B. Thuật toán 
Thuật toán MINE_FWUI 
Input: CSDL số lượng có sự phân cấp các mục DB và ngưỡng minwus 
Output: HIT-tree chứa các tập phổ biến trọng số hữu ích. 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
MINE_FWUI() 
 ADD_PARENT();//thêm nút cha cùng số lượng vào các giao dịch, đồng thời tính trọng số cho nút cha 
 CALCULATE_ TWU();// tính twu của các giao dịch trong CSDL mới 
 F = { i ∈ (I ∪ J), wus(i)	൒ minwus}; //tập 1-itemset thỏa mãn ngưỡng phổ biến minwus 
 HIT-tree =	∅; 
 CREATE_HIT-tree(F) 
 P = ∅; 
 for all i ∈ F // xét từng phần tử trong F 
 for j ∈ F with j > i //j phía sau i 
 X = Fi ∪ Fj; // X là itemset mới tạo thành từ Fi và Fj 
 if ∀x’ ∈ X ൓x”∈ X: parent(x’) = x”// không tồn tại 1 cặp mục nào là cha con trong X 
 T = tidset(Fi) ∩ tidset(Fj) //T là tidset của X 
 if wus(X) ൒ minwus 
 P = P ∪ ൏X, T, wus(X)൐ // kết nạp nút mới vào lớp P 
 HIT-tree = HIT-tree ∪ ൏X, T, wus(X)൐ // kết nạp nút mới vào HIT-tree 
 CREATE_HIT-tree(P)// gọi đệ quy với lớp P 
Hình 2. Thuật toán khai thác FWUI từ CSDL trọng số có sự phân cấp các mục 
Ví dụ 4: Thuật toán MINE_FWUI trong hình 2 với CSDL DB trong ví dụ 1 và minwus = 0.6 như sau: 
Dòng 2, thủ tục ADD_PARENT() cho kết quả như bảng 4 và 5. Thêm các mục nút cha, số lượng mục nút cha 
vào CSDL được thực hiện theo định nghĩa 3 và 5, thêm trọng số các mục nút cha theo định nghĩa 4, ta có kết quả như 
sau: 
Bảng 4. Các giao dịch Bảng 5. Bảng trọng số 
Giao dịch A B C D E F G H K Mục Trọng số 
t1 1 1 0 2 1 0 1 2 1 A 0.3 
t2 0 1 3 0 1 0 3 0 3 B 0.2 
t3 2 1 0 2 2 2 1 2 2 C 0.5 
t4 3 1 1 0 1 0 1 3 1 D 0.6 
t5 1 2 2 1 3 1 2 1 2 E 0.9 
t6 0 1 1 1 0 1 1 1 1 F 0.1 
 G 0.5 
 H 0.6 
 K 0.5 
Dòng 3, thủ tục CALCULATE_TWU() cho kết quả như bảng 6: 
N 
0
m
C
H
lý
tr
guyễn Duy Hàm
G
Dòng 4, tập
Từ dòn
Xét nút 
A kết h
.68 > minwus
A kết h
inwus → khô
Tương 
A kết hợ
Tương 
. Một số kĩ t
Zaki và
àm và các đồ
. Trong bài b
ong khai thác
, Võ Đình Bảy, N
iao dịch 
t1 
t2 
t3 
t4 
t5 ሺ
t6 
sum 
 F (1-itemset
g 6 đến dòng 
A trên cây HI
ợp với B: tids
 → kết nạp AB
ợp với C: tid
ng kết nạp AC
tự kết nạp {AE
p với H, khô
tự với các nút
huật cải tiến 
 các đồng sự 
ng sự đề xuấ
áo này chúng
 itemset trên 
Mục 
A 
B 
C 
D 
E 
F 
G 
H 
K 
guyễn Thị Hồng
ሺ0.3 ൈ 2 ൅ 0.2
0.3 ൅ 0.2 ൈ 2 ൅
 phổ biến) gồ
16 thủ tục đệ 
T-tree: 
et(AB) = tids
 vào HIT-tre
set(A, C) = ti
 vào HIT-tre
, AG, AK} v
ng xét do H là
 B, C, D, E, G
tốc độ tính to
[11] đề xuất 
t cấu trúc MB
 tôi sử dụng 
CSDL số lượn
ሺ0.6
ሺ0.6
ሺ0.6
Hình 
 Minh 
Bảng 6. tw
ሺ0.3 ൅
൅ 0.6 ൈ 2 ൅ 0
ሺ0.3 ൈ
0.5 ൈ 2 ൅ 0.6
m {A, B, C, D
quy CREATE
et(A)	∩ tidset
e. 
dset(A)	∩ tids
e. 
ào HIT-tree.
 cha của A tr
, H, K ta có c
án 
kĩ thuật diffs
yS [9], MBiS
cả ba giải phá
g có sự phân
Bảng 7. T
ሺ0.6
8 ൅ 1.12 ൅ 0.8
ሺ1.1
( 0.6
ሺ0.68 ൅ 1.1
8 ൅ 1.12 ൅ 0.8
ሺ0.68 ൅ 0.8
8 ൅ 1.12 ൅ 0.8
3. Cây HIT-tree
u của các giao
twu
0.2 ൅ 2 ൈ 0.6
ሺ0.2 ൅ 0.5 ൈ
.9 ൈ 2 ൅ 0.1 ൈ
3 ൅ 0.2 ൅ 0.5
൅ 0.9 ൈ 3 ൅ 0
ሺ0.2 ൅ 0.5 ൅
, E, G, H, K}
_HIT-tree() x
(B) = {1, 3, 4
et(C) = {1, 3
ên cây phân c
ây HIT-tree n
et thay thế tid
 [10] với mụ
p này trong th
 cấp các mục.
ập 1-itemset ph
wus 
8 ൅ 0.84 ൅ 0.7
4 ൅ 0.76 ൅ 0.8
2 ൅ 0.76 ൅ 0.8
8 ൅ 0.84 ൅ 0.8
2 ൅ 0.84 ൅ 0.7
ሺ0.84 ൅ 0.8
4 ൅ 0.76 ൅ 0.8
4 ൅ 0.76 ൅ 0.8
4 ൅ 0.76 ൅ 0.8
 với CSDL DB
 dịch 
൅ 0.9 ൅ 0.5 ൅
3 ൅ 0.9 ൅ 0.5
2 ൅ 0.5 ൅ 0.6
൅ 0.9 ൅ 0.5 ൅
.1 ൅ 0.5 ൈ 2 ൅
0.6 ൅ 0.1 ൅ 0.
 như bảng 7:
ây dựng cây H
, 5} ∩ {1, 2, 
, 4, 5} ∩ {2, 
ấp. 
hư hình 3 có 
set nhằm rút 
c tiêu tối ưu b
uật toán MIN
ổ biến 
6 ൅ 0.84ሻ/4.76
4 ൅ 0.43ሻ/4.7
4 ൅ 0.43ሻ/4.7
4 ൅ 0.43ሻ/4.7
6 ൅ 0.84ሻ/4.7
4 ൅ 0.43ሻ/4.7
4 ൅ 0.43ሻ/4.7
4 ൅ 0.43ሻ/4.7
4 ൅ 0.43ሻ/4.7
và minwus = 0
2 ൈ 0.6 ൅ 0.5ሻ
ൈ 3 ൅ 0.5 ൈ 3ሻ
ൈ 2 ൅ 0.5 ൈ 2ሻ
0.6 ൈ 3 ൅ 0.5ሻ
0.6 ൈ 0.5 ൈ 2ሻ
5 ൅ 0.6 ൅ 0.5ሻ
IT-tree bao g
3, 4, 5, 6} = 
4, 5, 6} = {4
các nút là FW
gọn bộ nhớ v
ộ nhớ trên tid
E_FWUI và 
= 0.65 
6 = 1.0 
6 = 0.67 
6 = 0.6 
6 = 0.91 
6 = 0.45 
6 = 1.0 
6 = 0.76 
6 = 1.0 
.6
/7	= 0.68 
/5	= 1.12 
/8	= 0.84 
/5	= 0.76 
/9	= 0.84 
/7	= 0.43 
 4.67 
ồm các nút là
{1, 3, 4, 5}, 
, 5}, wus(AC
UI. 
à tăng tốc độ
set và tăng h
so sánh chún
F 
A 
B 
C 
D 
E 
G 
H 
K 
 683 
 FWUI. 
wus(AB) = 
) = 0.34 < 
 tính toán. 
iệu quả xử 
g với nhau 
684 THUẬT TOÁN KHAI THÁC TẬP PHỔ BIẾN TỪ CƠ SỞ DỮ LIỆU SỐ LƯỢNG CÓ SỰ PHÂN CẤP CÁC MỤC 
IV. KẾT QUẢ THỰC NGHIỆM 
A. Môi trường thực nghiệm 
Hệ thống thử nghiệm được cài đặt bằng C# 2014 trên nền Microsoft Windows 8 Pro 64 bit, .Net Framework 4.5, 
thực hiện trên CPU Intel® Haswell Core™ i5 - 1.4 GHz, Ram 4Gb. Hệ thống phần mềm được sử dụng: Visual Studio 
2013 Ultimate. 
B. CSDL thực nghiệm 
CSDL thực nghiệm gồm ba CSDL: SALE-FACT_1997, SALE-FACT-1997_1998, SALE-FACT_SYNC rút ra 
từ CSDL Mirosoft Foodmart2000 của Microsoft SQL2000 (trong đó, SALE-FACT-1997_1998 là bản kết hợp của 
SALE-FACT-1997 và SALE-FACT-1998; SALE-FACT-SYNC là bản kết hợp của SALE-FACT-1997, SALE-
FACT_1998 và SALE-FACT-dec_1998). Cụ thể các CSDL phân cấp mục được mô tả như trong bảng 8 và 9. 
Bảng 8. Mô tả CSDL thực nghiệm Bảng 9. Cấu trúc cây phân cấp 
Tên CSDL Số lượng giao dịch Mức Tên mức Số lượng nút 
SALE-FACT_1997 20.522 1 Product_family 3 
SALE-Fact_1997_1998 54.537 2 Product_department 24 
SALE-FACT_SYN 58.308 3 Product_category 48 
 4 Product_subcategory 56 
 5 Product_class 110 
 6 Product 1560 
Từ bảng 9 ta thấy, có ba cây phân cấp (số lượng nút ở mức 1 là 3), độ cao của các cây phân cấp là 6 (có 6 mức). 
C. Kết quả thử nghiệm 
Để kết quả so sánh có độ chính xác cao, với mỗi ngưỡng phổ biến minwus chúng tôi tiến hành chạy chương 
trình 5 lần với mỗi phương pháp, sau đó lấy trung bình cộng của 5 lần chạy. 
Kết quả thử nghiệm trên các CSDL cho trong bảng 8 lần lượt được thể hiện qua các biểu đồ sau: 
Hình 4. Kết quả so sánh về thời gian (hình bên trái) và bộ nhớ (hình bên phải) trên CSDL SALE_FACT-1997 
Hình 5. Kết quả so sánh về thời gian (hình bên trái) và bộ nhớ (hình bên phải) trên CSDL SALE_FACT-1997_1998 
0
200
400
600
800
1000
0.3 0.2 0.1 0.06 0.03 0.01
tim
e(
s)
minwus(%)
DIFFSET
MByS
MBiS
0
100
200
300
400
500
600
700
800
0.3 0.2 0.1 0.06 0.03 0.01
m
em
or
y(
m
b)
minwus(%)
MBis
MByS
DIFFSET
0
50
100
150
200
250
300
350
400
0.3 0.2 0.1 0.06 0.03 0.01
tim
e(
s)
minwus(%)
MBiS
MByS
DIFFSET
0
200
400
600
800
1000
1200
1400
1600
0.3 0.2 0.1 0.06 0.03 0.01
m
em
or
y(
m
b)
minwus(%)
MBis
MByS
DIFFSET
Nguyễn Duy Hàm, Võ Đình Bảy, Nguyễn Thị Hồng Minh 685 
Hình 6. Kết quả so sánh về thời gian (hình bên trái) và bộ nhớ (hình bên phải) trên CSDL SALE_FACT-SYNC 
Các kết quả thực nghiệm từ hình 4 đến 6 trên cho thấy về mặt thời gian thuật toán sử dụng cấu trúc MBiS đạt 
được hiệu quả cao nhất sau đó là MByS và cuối cùng là DIFFSET. Ví dụ, CSDL SALE-FACT_1997 với ngưỡng 
minwus = 0.01, MBiS có thời gian xử lý là 68,301s, trong khi MByS là 294,022s và DIFFSET là 449.854s. Quan sát 
các hình bên phải (so sánh bộ nhớ sử dụng), ta thấy sự chênh lệch về bộ nhớ giữa các phương pháp là không đáng kể. 
Quan sát các hình bên trái (so sánh thời gian chạy), ta thấy với CSDL càng lớn thì DIFFSET càng có hiệu quả hơn, 
tiệm cận dần với phương pháp sử dụng cấu trúc MByS. 
V. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 
Bài báo đề xuất bài toán khai thác tập phổ biến trên CSDL số lượng có sự phân cấp mục, và phương thức tính 
trọng số và số lượng cho các mục trên cây phân cấp khi thêm vào CSDL bằng các định nghĩa 4 và 5. Đồng thời đề xuất 
thuật toán MINE_FWUI cùng với cấu HIT-tree để giải quyết bài toán này với chỉ một lần đọc CSDL. 
Bài báo thực nghiệm thuật toán đề xuất với các cấu trúc hiện có đối với khai thác dữ liệu theo chiều dọc như Diffset, 
MByS, MBiS trong lưu trữ tidset và so sánh hiệu quả của chúng về mặt thời gian chạy và bộ nhớ sử dụng. Kết quả thực 
nghiệm cho thấy cấu trúc MBiS có kết quả tốt nhất về mặt thời gian, kế đến là MByS và cuối cùng là kĩ thuật Diffset. 
Tiếp tục phát triển các kết quả đã đạt được, thời gian tới nhóm sẽ tiếp tục nghiên cứu mở rộng các bài toán trên 
CSDL số lượng có sự phân cấp mục, như khai thác tập phổ biến với nhiều ngưỡng hỗ trợ, khai thác tập phổ biến đóng, 
v.v.. Đồng thời, nghiên cứu các thuật toán hiệu quả hơn để giải quyết bài toán này như loại bỏ quá trình thêm mục nút 
cha vào CSDL, cũng như đề xuất các cấu trúc hiệu quả hơn trong khai thác tập phổ biến trên CSDL loại này. 
VI. TÀI LIỆU THAM KHẢO 
[1] Agrawal, R., Srikant, R.: “Fast algorithms for mining association rules”. Proc. of the 20th VLDB Conf. Santiago, 
Chile, pp. 487–499, 1994. 
[2] Zaki, M. J.: “Scalable algorithms for association mining”. IEEE Transactions on Knowledge and Data 
Engineering, 12(3), pp. 372-390, 2000. 
[3] Vo, B., Hong, le., Le, B.: “DBV-Miner: A Dynamic Bit-Vector approach for fast mining frequent closed 
itemsets”. Expert Systems with Applications 39, pp. 7196–7206, 2012. 
[4] Khan, M. S., Muyeba, M., Coenen, F.: “A weighted utility framework for mining association rules”. Proc. of 
conf. IEEE European Modeling Symposium, pp. 87 – 92, 2008. 
[5] Han, J., Fu, Y.: ”Discovery of multiple-level association rules from large databases”. Proc. of Conf. on Very 
Large Data Bases, Zurich, Switzerland, pp.420–431, 1995. 
[6] Liu, B., Hsu, W., Ma, Y.: ”Mining association rules with multiple minimum supports”. Proc.1999 Int. Conf. on 
Knowledge Discovery and Data Mining, San Diego, CA, USA, pp.337–341, 1999. 
[7] Tseng, M, C., Lin, W, Y.: ”Efficient mining of generalized association rules with non-uniform minimum 
support”. Data & Knowledge Engineering 66(1), pp.41-64, 2007. 
[8] Vo, B., Le, B.: ”Fast Algorithm for Mining Generalized Association Rules”. International Journal of Database 
Theory and Application 2(3), pp.1-12, 2009. 
[9] Nguyễn Duy Hàm, Võ Đình Bảy, Minh, Nguyễn Thị Hồng Minh: “Một phương pháp khai thác nhanh FWUI trên 
CSDL số lượng”. Một số vấn đề chọn lọc về CNTT và TT lần thứ 17. pp.280-285, 2014. 
[10] Ham, N, D., Vo, B., Minh, N, T, H., Hong , T, P.: “MBiS: an efficient method for mining frequent weighted utility 
itemsets from quantitative databases”. Journal of Computer Science and Cybernetics, 31(1), pp.17-30, 2015. 
0
100
200
300
400
500
0.3 0.2 0.1 0.06 0.03 0.01
tim
e(
s)
minwus(%)
MBiS
MByS
DIFFSET
0
200
400
600
800
1000
1200
1400
1600
1800
0.3 0.2 0.1 0.06 0.03 0.01
m
em
or
y(
m
b)
minwus(%)
MBis
MByS
DIFFSET
686 THUẬT TOÁN KHAI THÁC TẬP PHỔ BIẾN TỪ CƠ SỞ DỮ LIỆU SỐ LƯỢNG CÓ SỰ PHÂN CẤP CÁC MỤC 
[11] Zaki, M. J., Gouda, K.: “Fast Vertical Mining Using Diffsets”. KDD '03 Proc. of the ninth ACM SIGKDD 
international conf. on Knowledge discovery and data mining, Washington, DC, USA, pp.326-335, 2003. 
[12] Vo, B., & Le, B., Jason J. Jung, “A Tree-based Approach for Mining Frequent Weighted Utility Itemsets”, 
Computational Collective Intelligence Technologies and Applications, Lecture Notes in Computer 
Science Volume 7653, pp. 114-123, 2012. 
[13] Lan, G, C., Hong, T,P., Wu, P, S., “Mining hierarchical temporal association rules in a publication database”, 
Proc of IEEE Cognitive Informatics & Cognitive Computing (ICCI*CC), pp.503 – 508, 2013. 
[14] Ali, S, Z., Rathore, Y., “A effective and efficient algorithm for cross level frequent pattern mining”, Conf on 
Advances in Engineering and Technology Research (ICAETR), pp.1-6, 2014. 
MINING FREQUENT WEIGHTED UTILITY ITEMSETS FROM 
QUANLITY DATABASE WITH HIERARCHY OF ITEMS 
Nguyen Duy Ham, Vo Dinh Bay, Nguyen Thi Hong Minh 
ABSTRACT - Mining frequent itemsets (FIs) to find relationships among items plays an important role in data mining. Besides, 
mining FIs from traditional databases, mining FIs from weighted transactions databases and quantitative databases has received a 
lot of attention in recent years. However, there research only mining from database which no relation between the items from 
database. This paper, we propose the problem for mining FIs from quantitative databases with hierachy of items and propose an 
algorithm for sloving this problem based on diffset strategy, and MByS, MBiS structure in storing the tidset of itemset. The 
experimental results show that the method used MBiS structure to give the best effectively on runtime.