Khai phá cây con thường xuyên trên cơ sở dữ liệu

Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 
KHAI PHÁ CÂY CON THƯỜNG XUYÊN TRÊN CƠ SỞ DỮ LIỆU 
WEBLOGS 
Hoàng Minh Quang1, Vũ Đức Thi2, Kiều Thu Thủy3, Đào Văn Tuyết4, Phan Trung Kiên5 
1Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam. 
2Viện Công nghệ thông tin, Đại học Quốc gia Hà Nội. 
3Học viện Bưu chính Viễn thông 
4Viện Cơ học và Tin học ứng dụng 
5Trường Đại học Tây Bắc 
1hoangquang@ioit.ac.vn, 2vdthi@vnu.edu.vn, 4tuyetdv@gmail.com, 5kienptr@gmail.com 
TÓM TẮT - Hầu hết các công ty, tổ chức hiện nay đều mong muốn thu thập và trích xuất dữ liệu về mối quan 
tâm của người sử dụng. Dữ liệu có cấu trúc dạng weblogs có thể biểu diễn dưới dạng đồ thị và cây. Khai phá dữ liệu 
cây con thường xuyên trên cơ sở dữ liệu weblogs là tìm tất cả các cây con trong rừng cây weblogs mà có số lần xuất 
hiện lớn hơn một ngưỡng cho trước. Đây là một bài toán có độ phức tạp tính toán hàm mũ và có rất nhiều nhà khoa 
học nghiên cứu về vấn đề này. Trong bài báo này, chúng tôi đề xuất một phương pháp hiệu quả khai phá cây con 
thường xuyên trên cơ sở dữ liệu weblogs với việc tối ưu hóa vấn đề phát hiện các cây con đẳng cấu và thuật toán tìm 
kiếm theo chiều sâu để giảm thời gian và giảm không gian bộ nhớ trong quá trình tính toán. 
Từ khóa - khai phá dữ liệu, cây con thường xuyên, khai phá đồ thị, weblogs, dữ liệu có cấu trúc 
I. GIỚI THIỆU 
Mục tiêu của khai phá dữ liệu là trích xuất thông tin hữu ích từ dữ liệu [5, 10]. Dữ liệu có thể có nhiều dạng: 
véctơ, bảng, hình ảnh, văn bản,... và dữ liệu cũng được biểu diễn khác nhau. Dữ liệu có cấu trúc và dữ liệu bán cấu trúc 
phù hợp cho biểu diễn đồ thị chẳng hạn cấu trúc protein-protein biểu diễn dưới dạng đồ thị với đỉnh là các gens và các 
cạnh là mối quan hệ các gens. Khai phá dữ liệu có cấu trúc (tree, graph, và lattices) ngày càng trở nên quan trọng trong 
mô hình hóa các cấu trúc tinh vi phức tạp và sự tương tác của nó, với ứng dụng rộng rãi trong nhiều lĩnh vực của cuộc 
sống như tin hóa học, tin sinh học, tầm nhìn máy tính, chỉ mục video, phục hồi văn bản, và phân tích Web,v.v[10]. 
Đặc biệt, với xu hướng phát triển của dữ liệu lớn (Big Data), khai phá dữ liệu có cấu trúc càng trở thành một nhu cầu 
thiết yếu. Có thể dễ dàng biểu diễn dữ liệu có cấu trúc dưới dạng đồ thị đặc biệt hơn là cây. 
Bản chất của cấu trúc sử dụng web là một dạng dữ liệu có cấu trúc dạng đồ thị. Tuy nhiên, vấn đề khai phá đồ 
thị con thường xuyên gặp vấn đề về độ phức tạp thời gian tính toán trong việc phát hiện đẳng cấu. Chính vì vậy, khai 
phá dữ liệu cấu trúc sử dụng web được đưa về khai phá cây con thường xuyên nhằm làm giảm thời gian phát hiện các 
đồ thị con đẳng cấu. Một trong những thuật toán hiệu quả nhất về phát hiện đồ thị con đẳng cấu được R.Shamir và 
D.Tsur đề xuất năm 1999 [29]. Hiện nay đã có rất nhiều các phương pháp khai phá cây con thường xuyên tuy nhiên 
theo tác giả khảo sát thì vẫn chưa có thuật toán nào áp dụng phương pháp phát hiện đẳng cấu của R.Shamir và D.Tsur 
trong quá trình khai phá dữ liệu. Trong bài báo này, chúng tôi áp dụng phương pháp phát hiện cây con đẳng cấu sử 
dụng phương pháp của R.Shamir và D.Tsur với điều kiện ràng buộc trên cây có gắn nhãn nhằm mục tiêu làm giảm hơn 
nữa thời gian phát hiện đồ thị con đẳng cấu. 
Weblogs là một cấu trúc ghi lại các trang trong một phiên người dùng truy cập. Ứng với mỗi phiên truy cập, cấu 
trúc weblogs sẽ được lưu dưới dạng một cây có gốc là trang bắt đầu vào thăm của một website. Từ đó, mỗi nút của cây 
là một trang khác trong website mà người dùng đã xem trong một phiên sử dụng. Việc người dùng xem các trang tạo 
thành một đồ thị, tuy nhiên để giảm thời gian khai phá dữ liệu weblogs thì các log sẽ được lưu dưới dạng cây và biểu 
diễn bằng một mã chuỗi chỉ ra đường dẫn từ trang chủ đến các trang con mà người dùng vào xem. Ví dụ về mã chuỗi 
biểu diễn cho một cây trong cơ sở dữ liệu weblogs: (2 3 4 -1 1 -1 3 -1 -1) biểu diễn một cây gốc là đỉnh 2, ký hiệu -1 
thể hiện việc quay lại cha của đỉnh hiện tại theo phương pháp duyệt cây theo độ sâu preorder. Các cấu trúc weblogs 
khác nhau đều có thể quy về cách biểu diễn theo string như trên. 
Một số tác giả sử dụng cơ sở dữ liệu cây weblogs CS-LOG [25, 26, 28]. Các thuật toán của các nhóm tác giả 
này đều có những điểm mạnh và điểm yếu vì vậy việc so sánh hiệu suất thực hiện chỉ mang tính chất tương đối. Các 
thuật toán đưa ra các mẫu cây con thường xuyên cũng khác nhau do sử dụng các kiểu cấu trúc cây khác nhau mặc dù 
cùng dùng chung cơ sở dữ liệu rừng cây CS-LOG được biểu diễn dưới dạng mã chuỗi theo trật tự duyệt trước theo độ 
sâu. Trong bài báo này, chúng tôi lấy CS-LOG làm cơ sở dữ liệu thử nghiệm thuật toán, các cơ sở dữ liệu weblogs 
khác có thể sử dụng trong thuật toán với điều kiện đưa về dạng mã chuỗi theo trật tự duyệt trước theo độ sâu (preorder 
depth first search) giống với cơ sở dữ liệu weblogs CS-LOG được cung cấp, thuật toán tìm ra các cây con thường 
xuyên chính xác (induced subtree frequent mining). 
328 KHAI PHÁ CÂY CON THƯỜNG XUYÊN TRÊN CƠ SỞ DỮ LIỆU WEBLOGS 
II. MỘT SỐ ĐỊNH NGHĨA 
Chúng ta biểu diễn dữ liệu weblogs bằng một dạng cây gắn nhãn không có thứ tự. Dựa theo biểu diễn cây của 
T.Asai và cộng sự. Một số định nghĩa được phát biểu lại trong thuật toán của T.Asai [26]. 
Cây gắn nhãn không có thứ tự là một đồ thị không có chu trình T = (V, E, r, label) với một đỉnh riêng biệt r gọi 
là đỉnh gốc thỏa mãn các điều kiện: V là tập hợp các đỉnh, E ⊆ V x V là tập hợp các cạnh, label là một ánh xạ label: 
VÆL được gọi là hàm gắn nhãn. Với mọi đỉnh v ∈ V có duy nhất một đường UP(v) = (v0 = r, v1, , vd) (d ≥ 0) từ 
đỉnh gốc đến đỉnh v. Độ sâu của đỉnh v ký hiệu là deg(v) = d. 
Cho hai đỉnh u và v. Nếu (u, v) ∈ E ta nói rằng u là đỉnh cha của v, v là đỉnh con của u. Nếu có đường từ u 
đến v thì u được gọi là tiền bối của v, v gọi là hậu bối của u. Một lá là một đỉnh không có đỉnh con. Với mỗi đỉnh v 
ta gọi T(v) là một cây con của cây T có gốc là v. Kích thước của T là số đỉnh trong nó |T| = |V|. 
Ta sử dụng một cây gắn nhãn có thứ tự để biểu diễn một cây gắn nhãn không có thứ tự. Cây gắn nhãn có 
thứ tự là cây gắn nhãn không có thứ tự được với thứ tự từ trái qua phải theo con của mỗi đỉnh. Một cây gắn nhãn 
có thứ tự là một bộ 5 T = (V, E, r, label, B) với V, E, r, label là tập các đỉnh, tập cạnh, đỉnh gốc, hàm gắn nhãn của 
tập đỉnh V. Một quan hệ hai ngôi B⊆VxV là thứ tự từ trái qua phải của các con của một đỉnh. RMB(T) = (r0, , rc) 
(c ≥ 0) là đường từ đỉnh gốc r tới lá bên phải nhất của cây T. Đường RMB(T) gọi là nhánh phải nhất của cây T, 
rml(T) = k là lá bên trái nhất của cây T. 
Cho hai cây không có thứ tự T = (VT, ET, rT, labelT) và D = (VD, ED, rD, labelD). Ta gọi cây T là cây mẫu đầu 
vào, cây D là cây dữ liệu, mẫu T xảy ra trong D nếu có một ánh xạ ℐ: VTÆVDthỏa mãn 3 điều kiện với mọi đỉnh x, y 
∈ VT. 
(1) ℐ là ánh xạ một – một, với mọi x ≠ y thì ℐ(x) ≠ ℐ(y) 
(2) ℐ bảo toàn quan hệ đỉnh cha, (x, y)∈ ET nếu và chỉ nếu (ℐ(x),ℐ(y)) ∈ ED. 
(3) ℐ bảo toàn nhãn, labelT(x) = labelD(ℐ(x)). 
Ánh xạ ℐ gọi là phù hợp từ cây T vào cây D. 
Định nghĩa (2.1). Cho số nguyên dương k ≥ 1, cây T = (V, E, r, label) là một k-mẫu không có thứ tự. Giả sử 
ta có sự phù hợpℐ: VT ÆVD∈ MD(T) từ cây T vào D = {Di}. Có bốn kiểu xảy ra của T trong D: 
(1) Xảy ra toàn thể của T (total occurrence) là một k-bộ TOC(ℐ) = 〈ℐ(1), , ℐ(k)〉 ∈ (VD)k. 
(2) Xảy ra nhúng của T (embedding occurrence) là tập EOC(ℐ) = {ℐ(1), , ℐ(k)} ⊆ VD. 
(3) Xảy ra gốc của T (rooted occurrence) ROC(ℐ) = ℐ(1) ∈VD. 
(4) Xảy ra tài liệu của T (document occurrence) là một chỉ số DOC(ℐ) = i sao cho EOC(ℐ)⊆ࢂࡰ࢏ với 1 ≤ i ≤ |D|. 
Định lý (2.1). TOC ≥ EOC ≥ ROC ≥ DOC. 
Định lý (2.2). D là một cơ sở dữ liệu cây và T là một mẫu cây, หࢀࡻࡰ(ࢀ)หหࡱࡻࡰ(ࢀ)ห = ࢑ࡻ(࢑) và 
หࡱࡻࡰ(ࢀ)ห
หࡾࡻࡰ(ࢀ)ห = ࡻ൫࢔࢑൯ 
Khai phá cây con thường xuyên 
Cho một ngưỡng minfreq, một lớp C các cây, một quan hệ thứ tự các cây con P ≼ T giữa hai cây P, T ∈ C, cho 
một tập hữu hạn dữ liệu cây D ⊆ C, vấn đề khai phá cây thường xuyên là tìm tất cả các cây P ⊆ C mà không có hai 
cây bất kỳ nào trong P đẳng cấu với nhau và cho tất cả p ∈ P: freq(P,D) = ∑T∈Dd(P,T) ≥ minfreq với d là một hàm 
phản đơn điệu ∀T ∈ C: d(P’,T)≥d(P,T) nếu P’ ≼ P. 
Cho một cơ sở dữ liệu rừng cây D và T là một cây trong cơ sở dữ liệu rừng cây D. Một cây con P có quan hệ 
P ≼ T được gọi là P xảy ra trong T hay P là cây con đẳng cấu của T và hàm d được xác định: 
ࢊ(ࡼ, ࢀ) = ൜ ૚ ࢔ế࢛ ࡼ ≤ ࢀ૙ ࢉáࢉ ࢚࢘ườ࢔ࢍ ࢎợ࢖ ࢑ࢎáࢉ 
Mức độ thường xuyên của cây con P là số lần xuất hiện của cây con P trong cơ sở dữ liệu rừng cây D chứa 
các cây T. Chúng ta mượn thuật ngữ giao tác trong khai phá dữ liệu luật kết hợp gọi là thường xuyên dựa trên 
giao tác. Mỗi giao tác là một cây T, cơ sở dữ liệu giao tác là cơ sở dữ liệu rừng cây D. Gọi độ hỗ trợ của cây P trong 
D là: sup(P, D) = freq(P, D)/|D|. Do tính chất phức tạp của đồ thị và cây nên một cây con P có thể xuất hiện nhiều 
lần trong một cây T trong khi với khai phá dữ liệu tập mục thường xuyên thì một tập con k-tập mục chỉ xuất hiện 
một lần trong một giao tác. Do đó hàm freq(P, D) chỉ được tính khi P là cây con của cây T trong cơ sở dữ liệu 
rừng cây D. 
Hoàng Minh Quang, Vũ Đức Thi, Kiều Thu Thủy, Đào Văn Tuyết, Phan Trung Kiên 329 
III. KIỂM TRA ĐẲNG CẤU 
Sử dụng phương pháp phát hiện đẳng cấu trong [29] với thay đổi một chút về nhãn của đỉnh và định nghĩa một 
thứ tự cho tất cả các đỉnh. Từ đó làm tăng hiệu suất phát hiện đẳng cấu trong cây có gắn nhãn. Các thành phần sau 
được phát biểu lại công trình nghiên cứu của R.Shamir và D.Tsur 1999 [29]. 
Cây có gốc là một bộ ba G = (V, E, r). Định nghĩa Gvr là cây con có gốc cha là r và v là một con của r và chỉ 
xem xét cây có gốc v.Gr và Hs là đẳng cấu nếu có một đẳng cấu giữa G và H dưới ánh xạ từ r tới s.Hs là cây con đẳng 
cấu với Gr nếu có một cây con Jr của Gr mà đẳng cấu với Hs.Tập láng giềng mở là tập tất cả láng giềng của v ký hiệu 
N(v).Tập láng giềng đóng là tập tất cả láng giềng của v bao gồm cả đỉnh v ký hiệu N[v].Bậc của v trong đồ thị G được 
định nghĩa là dG(v). Thuật toán có độ phức tạp là O(k1.5n). 
Cho G = (V, E) và H = (VH, EH) với |VH| > 1. Chọn một đỉnh r là gốc của G. Cần tìm một cây con đẳng cấu Hwu 
của Gvr với u là đỉnh của H và v là đỉnh của G và w là láng giềng của u. 
Bổ đề (1) Cho mọi đỉnh v của Gr, đỉnh u trong H, và một đỉnh w thuộc tập láng giềng đóng của u, ta có Huw là 
cây con đẳng cấu của Gvr nếu và chỉ nếu mọi đỉnh con u’ của u trong Huw có một đỉnh con phân biệt v’ của v mà Hu’u là 
cây con đẳng cấu của Gv’r. 
Chúng ta lưu giữ thông tin này trong các tập S(v, u) = {đỉnh w thuộc láng giềng đóng của u sao cho: Huw là cây 
con đẳng cấu của Gvr} với mọi đỉnh v của G và cho mọi đỉnh u của H. 
Định lý (3.1). Thuật toán Subtree-Isomorphism giải quyết vấn đề cây con đẳng cấu trong thời gian O(k1.5n) và 
không gian O(kn). 
Cho B = (X, Y, E) là một đồ thị song phương với X = (x1, , xs), Y = (y1, , yt), s ≤ t + 1. Cho X0 = X và Xi = 
X – {xi} với 1 ≤ i ≤ s, mi là sự phù hợp tối đa giữa Xi và Y. M là sự phù hợp tối đa của B, xác định đồ thị có hướng BM 
= (X∪ Y, EM) với 
EM = {(x, y): xy ∈ E – M, x ∈ X, y ∈ Y} ∪ {(y, x): xy ∈ M,x ∈ X, y ∈ Y} 
Bổ đề (3.1). Với mọi sự phù hợp tối đa M của B và mọi đỉnh xi∈ X, xi là điểm quan trọng (mi = m0 – 1) nếu và 
chỉ nếu xi được phù hợp trong M, không có đường trực tiếp nào trong BM từ một đỉnh thuộc XM tới xi. 
Hệ quả (3.1). Cho một phù hợp tối đa M của B, ta có thể tính giá trị của mi với 0 ≤ i ≤ s với độ phức tạp 
thời gian O(st). 
Định lý (3.2). Vấn đề tìm một phù hợp tối đa trong B có thể giảm độ tính toán từ O(st) tới tìm một phù hợp 
tối đa trong đồ thị con của B với nhiều nhất s2 đỉnh và cạnh với bậc cao nhất là s. 
Định lý (3.3). Thuật toán Improved-Subtree-Isomorphism tìm một phù hợp tối đa trong B(v,u) với độ 
phức tạp thời gian O(st + ts0.5D(u)). 
Định lý (3.4). g(n) = 2⊝(n) 
Định lý (3.5). f(n) = ⊝(n/logn) 
Định lý (3.6). Với mọi đỉnh khó yj, d(yj) ≤ k∊ + lj và D(yj) ≤ k∊ + f(lj) 
Định lý (3.7). ∑j=1k d(yj)0.5D(yj) = O(k1.5/logk). 
Định lý (3.8). Thuật toán Improved-Subtree-Isomorphism giải quyết vấn đề cây con đẳng cấu với độ phức 
tạp thời gian O((k1.5/logk)n). 
Thuật toán phát hiện cây con đẳng cấu của R.Shamir và D.Tsur 1999 [29] xác định cây con đẳng cấu trên 
cây không gắn nhãn và không có thứ tự. Bài toán tìm cây con thường xuyên trên cơ sở dữ liệu weblogs có điểm 
khác biệt là các cây trong cơ sở dữ liệu weblogs đều có thể gắn nhãn và hơn nữa còn có thể biểu diễn dưới dạng 
cây gắn nhãn có thứ tự. Chính vì vậy khi áp dụng thuật toán Improved-Subtree-Isomorphism vào cây gắn nhãn 
có gốc có thứ tự sẽ làm giảm hơn nữa độ phức tạp tính toán tùy thuộc vàocách thức gắn nhãn trong cây. Nếu cây 
có các nhãn riêng biệt không trùng lặp thì việc đánh thứ tự chỉ việc gắn cho các nhãn, nếu cây có các nhãn mà có 
trùng lặp thì ngoài thứ tự các nhãn còn có thứ tự từ trái sang phải trong cây. 
IV. SINH TẬP ỨNG VIÊN 
Có hai bước quan trọng trong việc tìm tất cả các cây con thường xuyên trong cơ sở dữ liệu các cây D. Bước đầu 
tiên là sinh tập cây con ứng viên để kiểm tra mức độ thường xuyên. Tập ứng viên được sinh ra phải không dư thừa, 
nghĩa là mỗi cây con ứng viên chỉ được sinh ra nhiều nhất một lần. Cây được biểu diễn dưới dạng mã chuỗi ký tự, cây 
T được sinh ra theo cách: thêm một đỉnh được gắn nhãn vào cây T theo phương pháp duyệt trước cây theo độ sâu 
(preorder depth first search) và thêm một ký tự duy nhất -1 không thuộc vào tập nhãn của cây (hoặc # hoặc $, ) khi 
xảy ra một quay lui từ đỉnh con lên đỉnh cha trong cây T [26]. 
3
n
2
c
2
h
l
Đ
th
(
c
x
r
h
d
c
c
h
c
M
h
đ
30 
Định dạ
hánh của cây
m + 1 = 2n –
ây T theo phư
 -1 -1 2 -1 thì
Trong v
iệu suất sinh 
à tập con của 
ối với cây ta 
ường xuyên 
k+1) đỉnh từ c
ần sinh cây c
uyên trong cơ
Chi [49
ộng (breadth-
ợp (join) và m
iễn chuẩn the
ây có gốc khô
hiều rộng có 
ình 2 chia sẻ 
uối của P (ví 
Phương
ỗi cặp cây c
ợp thì sẽ đượ
ược cây con 
ng này có ưu
 phải được du
 1 với m là số
ơng pháp duy
 l(T) = 01312
ấn đề sinh tậ
tập ứng viên. 
tập thường xu
cũng có tính 
là cây không
ây con k đỉnh
on (k+1) đỉn
 sở dữ liệu câ
] đề xuất một
first traversal)
ở rộng (exten
o chiều rộng 
ng có thứ tự 
thể lấy bằng c
tiền tố chung
dụ t3 và t4 tro
 pháp sinh tậ
on sẽ được kế
c thực hiện m
mức (k+1) sẽ
Hình 
 điểm có thể
yệt theo cả ha
 lượng cạnh 
ệt trước theo
22). 
p ứng viên tr
Trong khai ph
yên là tập thư
chất tương tự 
 thường xuyê
 nếu cây con
h. Từ đó giảm
y D. 
Hình
 thuật toán đư
 và theo chiề
sion). Để đảm
(breadth-first
biểu diễn dạn
ách bỏ đi mộ
 bằng cách bỏ
ng hình 2) th
p cây con ứn
t hợp với nh
ở rộng. Khi 
 phải thêm và
KH
1. Biểu diễn mã
 biểu diễn cá
i hướng tiến l
và n là số lượ
 độ sâu nhưng
ong bài toán t
á tập mục thư
ờng xuyên, t
là cây con củ
n. Dựa vào tí
 k đỉnh là thư
 số lượng c
 2. Kết hợp ha
ợc gọi là Hyb
u sâu (depth-
 bảo mỗi ứn
 canonical fo
g chuẩn mức 
t trong hai đỉn
 đi đỉnh cuối
ì ta bỏ đi 2 đỉn
Hình
g viên từ hai
au để sinh các
kết hợp hai c
o một vấn đề
AI PHÁ CÂY C
 chuỗi của cây
c cây với tùy
ên và quay lu
ng đỉnh có tr
 không chứa 
ìm mẫu thườ
ờng xuyên củ
ập cha của tậ
a cây thường 
nh chất này ta
ờng xuyên, nế
ây con ứng v
i cây t1 và t2 đư
ridTreeMiner
first traversal)
g viên chỉ đư
rm) dựa trên v
(k+1). Nếu có
h lá và chia s
. Trong trườn
h cuối và chi
3. Cây con tự đ
cây con thườ
 cây con ứng
ây con thường
 về tự đẳng c
ON THƯỜNG X
 duyệt trước the
 ý số lượng đ
i. Bộ nhớ để l
ong cây T. K
ký tự biểu diễ
ng xuyên dựa
a khai phá lu
p không thườ
xuyên là cây t
 chỉ cần sinh
u cây con k đ
iên trong quá
ợc các cây t3, 
 sử dụng kết 
 để sinh tập ứ
ợc sinh ra mộ
iệc duyệt the
 hai đỉnh lá t
ẻ tiền tố chun
g hợp đỉnh cu
a sẻ tiền tố ch
ẳng cấu. 
ng xuyên mứ
 viên mức (k+
 xuyên mức 
ấu cây con (t
UYÊN TRÊN C
o độ sâu. 
ỉnh con của m
ưu trữ cây the
ý hiệu l(T) m
n quay lui (v
 vào tính chấ
ật kết hợp thì
ng xuyên là tậ
hường xuyên
 các cây con 
ỉnh là không 
 trình tìm tất
t4, t5 t6. 
hợp cả phươn
ng viên dùng
t lần, Chi [25
o mức và thứ
rong cùng mứ
g mức (k-1),
ối của cây co
ung. 
c k chia sẻ ti
1). Các cây 
k chia sẻ tiền
ree automorp
Ơ SỞ DỮ LIỆU
ỗi đỉnh. The
o biểu diễn m
ô tả chuỗi cá
ới cây 0 1 3 1
t phản đơn đi
 tính chất phả
p không thườ
, cây cha của 
ứng viên mứ
thường xuyên
 cả các cây c
g pháp duyệt 
 hai phương p
] sử dụng một
 tự trong cây
c của cây T t
 ví dụ cây t1 v
n P là con củ
ền tố chung 
không thể thự
 tố chung mứ
hism), nếu kh
WEBLOGS 
o đó, mỗi 
ã chuỗi là 
c nhãn của 
 -1 2 -1 -1 
ệu để tăng 
n đơn điệu 
ng xuyên. 
cây không 
c (k+1) có 
 thì không 
on thường 
theo chiều 
háp là kết 
 dạng biểu 
. Cho một 
hì mã theo 
à t2 trong 
a hai đỉnh 
mức (k-1). 
c hiện kết 
c (k-1) để 
ông có tự 
Hoàng Minh Quang, Vũ Đức Thi, Kiều Thu Thủy, Đào Văn Tuyết, Phan Trung Kiên 331 
đẳng cấu thì việc sinh ứng viên sẽ phức tạp hơn nhiều. Ví dụ hình 3 thể hiện khi kết hợp hai cây thường xuyên mức k 
chia sẻ tiền tố chung mức (k-1) mà không có tự đẳng cấu sẽ có nhiều cây con mức (k+1). 
V. THUẬT TOÁN 
Thuật toán khai phá cây con thường xuyên tương tự như thuật toán khai phá tập mục thường xuyên trong khai 
phá dữ liệu luật kết hợp. Thông thường có hai phương pháp tiếp cận: phương pháp tiếp cận dựa trên thuật toán Apriori 
do Argawal đề xuất 1994 [1], phương pháp tiếp cận dựa trên phát triển mẫu dùng FP-Growth do Han đề xuất [30]. 
Thuật toán tìm cây con thường xuyên theo phương pháp tiếp cận Apriori: 
Trong bài báo này, chúng tôi cải tiến thuật toán tìm cây con theo phương pháp tiếp cận Apriori sử dụng một 
danh sách các cây con thường xuyên cùng với sử dụng phương pháp phát hiện đẳng cấu của R.Shamir và Tsur 1999 
[29] đồng thời thêm vào điều kiện gắn nhãn cho đỉnh và đưa thứ tự các đỉnh vào trong cây để tăng hiệu suất tìm kiếm 
tất cả cây con thường xuyên. 
Thuật toán kiểm tra cây con đẳng cấu 
Thuật toán khai phá cây con thường xuyên theo cách tiếp cận Apriori. 
Input: Cơ sở dữ liệu cây trong rừng cây D, ngưỡng độ hỗ 
trợ tối thiểu σ 
Output: F1, , Fk là các tập cây con thường xuyên với đỉnh 
tương ứng từ 1 đến k. 
1. F1 phát hiện tất cả các cây con thường xuyên có 1 
đỉnh từ rừng cây D 
2. k  2 
3. while Fk-1 ≠ ϕ do 
4. Fk ϕ 
5. Ck candidate_gen(Fk-1) 
6. foreach t ∊ Ck do 
7. t.count  0 
8. foreach Di∊ D do 
9. if Subtree-Isomorphism(t, Di) then 
10. t.count  t.count + 1 
11. end 
12. end 
13. if ((t.count ≥ σ) and (t không thuộc Fk)) then 
14. Fk Fk ∪ t 
15. end 
16. end 
17. k  k + 1 
18.end 
Thuật toán kiểm tra cây con đẳng cấu 
Input: cây có gốc G với đỉnh gốc là r, cây có gốc H 
Output: H có phải là cây con đẳng cấu của G hay không? 
1. Chọn một đỉnh r của G làm gốc G. 
2. Với mọi u ∈ H,v ∈ G đặt S(v,u)← φ. 
3. For all đỉnh lá v của Gr do 
4. For all đỉnh lá u của H do S(v,u)← N(u). 
5. For all đỉnh trong v của Gr theo thứ tự postorder do 
6. Cho v1,...,vt là các con của đỉnh v. 
7. For all đỉnh u = u0 của H với bậc cao nhất t + 1 do 
8. Cho u1,...,us là các láng giềng của đỉnh u. 
9. Xây dựng đồ thị song phương B(v,u) = (X,Y,Evu), 
 với X ={u1,...,us}, Y = {v1,...,vt}, 
 và Evu ={uivj : u ∈ S(vj,ui)}. 
 Xác định X0 = X và Xi = X −{ui}. 
10. For all 0≤ i ≤ s do tính mi là phù hợp tối đa giữa 
 Xi và Y. 
11. S(v,u)←{ui : mi = |Xi|, 0≤ i ≤ s}. 
12. If u ∈ S(v,u) then trả lời YES và dừng. 
13. End for 
14.End for 
15.Trả lời NO. 
3
th
c
p
g
<
[
t
n
g
c
32 
Dữ liệu
uộc lớp NP-
hấp nhận mất
Từ cấu 
háp duyệt trư
iá trị thuộc và
 , rồi từ đó
29] là cây khô
hứ tự các nh
ày, chúng tô
án nhãn và th
Thuật t
on ứng viên t
 web logs đư
đầy đủ [8] nê
 một số thông
trúc dữ liệu 
ớc theo độ sâ
o miền ký hi
 áp dụng thuậ
ng có thứ tự 
ãn thì độ phứ
i vẫn chưa ch
ứ tự cho nh
oán WETreeM
heo cách tiếp
ợc biểu diễn 
n chúng ta bi
 tin có thể coi
web logs thực
u (preorder d
ệu thuộc từ đi
t toán phát hi
và không đượ
c tạp tính to
ứng minh đ
ãn, chúng tôi
iner được x
 cận của Chi
KH
Hình 4. H
dưới dạng đồ
ểu diễn web l
 là chấp nhận
Hình 5. Cấu t
 tế, ta chuẩn
epth first sea
ển. Với mỗi k
ện cây con đẳ
c gán nhãn c
án trong phá
ược độ phức
 vẫn tiếp tục 
ây dựng dựa 
 [25], cải tiến
AI PHÁ CÂY C
ình dạng cây c
 thị. Việc tìm
ogs dưới dạng
 được khi biểu
rúc dữ liệu cây 
hóa web log
rch) như biểu
ý hiệu trong t
ng cấu theo [
ó độ phức tạp
t hiện cây co
 tạp tính toá
nghiên cứu v
trên phương p
 phương phá
ON THƯỜNG X
on đẳng cấu. 
 đồ thị con đ
 cây để giảm
 diễn web log
web logs thực 
s thành dạng 
 diễn trong H
ừ điển ta gán 
29]. Phương p
 tính toán là O
n đẳng cấu đ
n phát hiện c
ấn đề này. 
háp tiếp cận
p phát hiện c
UYÊN TRÊN C
ẳng cấu là c
 bớt độ phức
s dưới dạng 
tế. 
cây mã chuỗi
ình 1. Với m
một thứ tự ch
háp phát hiện
((k1.5/logk)n
ược giảm đi 
ây con đẳng
 Apriori, phư
ây con đẳng c
Ơ SỞ DỮ LIỆU
ó độ phức tạp
 tạp tính toán
cây thay cho đ
 có thứ tự th
ỗi nút chúng 
ẳng hạn A < 
 cây con đẳn
) nên khi gá
đáng kể. Tron
 cấu dựa trê
ơng pháp xây
ấu của Sham
WEBLOGS 
 tính toán 
. Chúng ta 
ồ thị. 
eo phương 
ta gán một 
B < C < D 
g cấu theo 
n nhãn và 
g bài báo 
n [29] mà 
 dựng cây 
ir và Tsur 
H[
h
l
th
n
v
tr
x
t
n
đ
d
oàng Minh Quan
29]. Chương 
iện thuật toán
Kết quả
iệu CS-LOGS
Qua nh
uật toán kha
ghiên cứu, cả
à tính toán độ
ợ cây con đư
uyên trong m
ế, chẳng hạn 
gưỡng thấp d
ang nghiên cứ
ữ liệu. 
g, Vũ Đức Thi, K
trình được th
 và trích xuất
 thực hiện th
 cắt gọn còn 
ững khảo sát 
i phá cây con
i tiến để nâng
 hỗ trợ của c
ợc sinh ra phả
ột cơ sở dữ li
với cơ sở dữ 
o thời gian tín
u thêm một 
iều Thu Thủy, Đ
ực hiện trên m
 kết quả ra fil
ử nghiệm thu
1000 cây giao
và nghiên cứu
 thường xuy
 cao hiệu suấ
ác cây con để
i ≥ một ngưỡ
ệu rừng cây c
liệu weblogs
h toán quá lớ
số ràng buộc 
ào Văn Tuyết, P
áy tính Core
e hiển thị trên
Hình 6. Giao
ật toán WET
 tác. 
Hình 7. T
 xây dựng thu
ên hiện nay đ
t khai phá nh
 xác định mứ
ng độ hỗ trợ t
ho trước nhìn
 CS-LOG nh
n dẫn đến việ
có ý nghĩa tr
han Trung Kiên
 2 Duo E750
 nền Web. 
 diện thuật toán
reeMiner so v
hực nghiệm W
VI. KẾT LUẬ
ật toán khai p
ều gặp hai v
ất là với các b
c độ thường 
ối thiểu cho t
 chung là có 
ư trình bày tr
c khó triển kh
ong việc liệt k
0, 2GB RAM
 WETreeMine
ới thuật toán
ETreeMiner. 
N 
há cây con th
ấn đề lớn mà
ộ dữ liệu lớn
xuyên của cây
rước là σ. Thu
độ phức tạp h
ong bài báo g
ai vào thực t
ê tất cả các m
 sử dụng ng
r. 
 TreeMiner c
ường xuyên, 
 các nhà kho
. Hai vấn đề 
 con có thỏa
ật toán tìm tấ
àm mũ. Vì vậ
ặp nhiều khó
ế. Trên cơ sở
ẫu cây con t
ôn ngữ lập tr
ủa Zaki [27] 
chúng tôi nhậ
a học đều đa
đó là kiểm tr
 mãn tính chấ
t cả các cây c
y khi áp dụn
 khăn khi kh
 bài báo này, 
hường xuyên
333 
ình C thực 
với bộ dữ 
n thấy các 
ng nỗ lực 
a đẳng cấu 
t về độ hỗ 
on thường 
g vào thực 
ai phá với 
các tác giả 
 của cơ sở 
334 KHAI PHÁ CÂY CON THƯỜNG XUYÊN TRÊN CƠ SỞ DỮ LIỆU WEBLOGS 
LỜI CẢM ƠN 
Nhóm tác giả cảm ơn Phòng Khoa học dữ liệu và ứng dụng - Viện Công nghệ thông tin – Viện Hàn lâm Khoa 
học và công nghệ Việt Nam đã cung cấp một số tài liệu nghiên cứu, dữ liệu web logs và trang thiết bị phục vụ thực 
nghiệm cho bài báo này được hoàn thiện. 
TÀI LIỆU THAM KHẢO 
[1]. Agrawal, R. and Srikant, R. 1994. Fast Algorithm for Mining Association Rules, In Proceedings of the 20th 
International Conference on Theoretical Informatics, 598-612. 
[2]. Avis, D. and Fukuda, K. 1996. Reverse Search for enumeration, Discrete Applied Mathematics, Volume 65, 21-46 
[3]. Brin, S. and Page, L. 1998. The Anatomy of a Large-scale Hyper-textual Web Search Engine. In Proceedings of 
the 7th International World Wide Web Conference, 107-117. 
[4]. Chakrabarti, S., Dom, B., Gibson, D., Kleinberg, J., Kumar, R., Raghavan, P., Rajagopaln, S. and Tomkins, A. 
1999. Mining the Link Structure of the World Wide Web, IEEE Computer 32(8), 60-76. 
[5]. Chen, M.S., Han, J. and Yu, P.S. 1996. Data Mining: An Overview from Database Perspective, IEEE Transaction 
on Knowledge and Data Engineering 8, 866–883. 
[6]. Cook, D.J. and Holder, L.B. 2000. Graph-based Data Mining, IEEE Intelligent Systems 15(2), 32–41. 
[7]. Deshpande, M., Kuramochi, M., Wale, N., and Karypis, G. 2005. Frequent Sub-Structure-based Approach for 
Classifying Chemical Compounds, IEEE Transactions on Knowledge and Data Engineering 17(8), 1036-1050. 
[8]. Fortin, S. 1996. The Graph Isomorphism Problem, Technical Report, no. TR06-20, The University of Alberta. 
[9]. Han, J., Cheng, H., Xin, D. and Yan, X. 2007. Frequent Pattern Mining: Current Status and Future Directions, 
Journal of Data Mining and Knowledge Discovery 15(1), 55–86. 
[10]. Han, J. and Kamber, M. 2006. Data Mining Concepts and Techniques, 2nd Edition, San Francisco: Morgan 
Kaufmann. 
[11]. Huan, J., Wang, W., Prins, J. and Yang, J. 2004a. SPIN: Mining Maximal Frequent Subgraphs from Graph 
Databases, In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and 
Data Mining, 581–586. 
[12]. Inokuchi, A., Washio, T. and Motoda, H. 2000. An Apriori-based Algorithm for Mining Frequent Substructures 
from Graph Data, In Proceedings of the 4th European Conference on Principles and Practice of Knowledge 
Discovery in Databases, 13–23. 
[13]. Jiang, C., Coenen, F. and Zito, M. 2010. Frequent Sub-graph Mining on Edge Weighted Graphs, Data 
Warehousing and Knowledge Discovery, Lecture Notes in Computer Science Volume 6263, 77-88. 
[14]. Kashima, H., Tsuda, K. and Inokuchi, A. 2003. Marginalized Kernels Between labelled Graphs, In Proceedings of 
the 20th International Conference on Machine Learning (ICML’03), 321-328. 
[15]. Kleinberg, J.M. 1998. Authoritative Sources in a Hyper-linked Environment, In Proceedings of ACM-SIAM 
Symposium Discrete Algorithms, 668-677. 
[16]. Kosala, R. and Blockeel, H. 2000. Web Mining Reasearch: A Survey, ACM, SIGKDD Explorations Newsletter 
2(1), 1-15. 
[17]. Liu, B. 2008. Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Springer. 
[18]. Newman, M.E.J. 2004. Detecting Commuity Structure in Networks, The European Physical Journal B-Condensed 
Matter and Complex Systems 38(2), 321-330. 
[19]. Shasha, D., Wang, J.T.L. and Giugno, R. 2002. Algorithms and Applications of Tree and Graph Searching, In 
Proceedings of the Twenty-first ACM SIGMOD-SIGACT-SIGART Symposium on Principles on Database 
Systems, 39-52. 
[20]. Washo, T. and Motoda, H. 2003. State of the Art of Graph-based Data Mining, SIGKDD Explorations 5, 59-68. 
[21]. Yan, X. and Han, J.W. 2002. gSpan: Graph-based Substructure pattern mining, In Proceedings of International 
Conference on Data Mining, 721–724. 
[22]. Yan, X., Yu, P.S. and Han, J. 2005b. Sub-Structure Similarity Search in Graph Databases, In Proceedings of the 
2005 ACM SIGMOD International Conference on Management of Data, 766-777. 
[23]. Yan, X., Zhu, F., Han, J. and Yu, P.S. 2006. Searching Substructures with Superimposed Distance, In 
Proceedings of the 22nd International Conference on Data Engineering, 88-97. 
Hoàng Minh Quang, Vũ Đức Thi, Kiều Thu Thủy, Đào Văn Tuyết, Phan Trung Kiên 335 
[24]. Yan, X., Cheng, H., Han, J. and Yu, P.S. 2008. Mining Significant graph patterns by leap search, In Proceedings 
of the 2008 ACM SIGMOD International Conference on Management Data, Vancouver, Canada, 433-444. 
[25]. Chi, Y., Yang, Y., Muntz, R. R.: HybridTreeMiner: An Efficient Algorithm for Mining Frequent Rooted Trees 
and Free Trees Using Canonical Forms, The 16th International Conference on Scientific and Statistical Database 
Management (SSDBM’04), June 2004. 
[26]. Asai, T., Arimura, H., Uno, T., Nakano, S.: Discovering Frequent Substructures in Large Unordered Trees, The 
6th International Conference on Discovery Science, October 2003. 
[27]. Zaki, M. J.: Efficiently Mining Frequent Trees in a Forest, Proc. of the 2002 Int. Conf. Knowledge Discovery and 
Data Mining (SIGKDD’02), July 2002. 
[28]. Tan, H., Dillon, T.S., Hadzic, F., Chang, E. and Feng, L. 2006. IMB3-Miner: Mining Induced/Embedded subtrees 
by Constraining the Level of Embedding, In Proceedings of the 8th Pacific-Asia Conference on Knowledge 
Discovery and Data Mining, 450–461. 
[29].Shamir, R. and Tsur, D. 1999. Faster Subtree Isomorphism, Journal of Algorithms 33(2), 267–280. 
[30]. Han, J., Pei, J. and Yin, Y. 2000. Mining Frequent Patterns without Candidate Generation, In Proceedings of 
ACM SIGMOD International Conference on Management of Data, 1–12.