Khai phá cây con thường xuyên trên cơ sở dữ liệu
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óm tắt nội dung tài liệu: Khai phá cây con thường xuyên trên cơ sở dữ liệu
![Khai phá cây con thường xuyên trên cơ sở dữ liệu Khai phá cây con thường xuyên trên cơ sở dữ liệu](https://s1.tailieuvn.net/xb70nb5jd4llaq8g/thumb/2022/01/01/khai-pha-cay-con-thuong-xuyen-tren-co-so-du-lieu_eIfnEG2Avz.jpg)
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.
File đính kèm:
khai_pha_cay_con_thuong_xuyen_tren_co_so_du_lieu.pdf