Luận án tiến sĩ: Khai thác đồ thị con trên đồ thị có trọng số

ĐẠI HỌC QUỐC GIA THÀNH PHO HO CHI MINH TRUONG DAI HOC KHOA HOC TU NHIEN LE THI NGOC THAO KHAI THAC DO THI CON TREN DO THI CO TRONG SO LUAN AN TIEN SI KHOA HOC MAY TINH TP. Hồ Chí Minh - Năm 2023 ĐẠI HỌC QUOC GIA THÀNH PHO HO CHÍ MINH TRUONG ĐẠI HỌC KHOA HỌC TỰ NHIÊN LÊ THỊ NGỌC THẢO KHAI THÁC DO THỊ CON TREN DO THỊ CÓ TRỌNG SO Ngành: Khoa học máy tính Mã số ngành: 62480101 Phản biện 1: PGS. Huỳnh Trung Hiếu Phản biện 2: PGS. Nguyễn Tuấn Đăng Phản biện 3: PGS.

Trần Đăng Hưng Phản biện độc lập 1: PGS. Trần Đăng Hưng Phản biện độc lập 2: TS. Đặng Trường Sơn NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. Lê Hoài Bắc 2.

Võ Dinh Bay TP. Hồ Chí Minh - Năm 2023 LỜI CAM ĐOAN Tôi xin cam đoan nội dung luận án này là kết quả nghiên cứu của riêng tôi và các đồng tác giả trong các công trình được công bố liên quan đến luận án. Những kết quả nghiên cứu của chúng tôi được trình bày trong luận án và các bài báo khoa học đã công bố được nêu trong phần danh mục các công trình nghiên cứu và chưa được công bố trong bất kì công trình nào khác. Các kết quả nghiên cứu của nhiều tác giả được đưa vào trong nội dung của luận án đều nhận được sự đồng ý trước đó của các đồng tác giả.

Tất cả những tham khảo từ các nghiên cứu có liên quan đến nội dung của luận án đều được chỉ rõ nguồn gốc từ danh mục các tài liệu tham khảo trong luận án. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận án này đã được cảm ơn và các thông tin trích dẫn trong luận án đã được chỉ rõ nguồn gốc. Nghiên cứu sinh Lê Thị Ngọc Thảo LOI CẢM ON Đầu tiên, tôi xin chân thành và sâu sắc biết ơn sự tận tình dạy dỗ và sự giúp đỡ của tất cả quý thầy cô Khoa Công nghệ thông tin, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh. Đặc biệt, tôi xin gửi lời cám ơn chân thành nhất đến thầy Lê Hoài Bắc và thầy Võ Đình Bảy đã tận tình hướng dẫn và hết lòng giúp đỡ tôi trong thời gian làm luận án vừa qua.

Cuối cùng, tôi xin gửi lời cám ơn đến gia đình, bạn bè, đồng nghiệp, những người luôn bên cạnh động viên, và tạo mọi điều kiện tốt nhất dé tôi có thé học tập và hoàn tât được luận án này. 1 LO1 CAM O11 0Š Ö aa. 1 Danh mục các ký hiệu, thuật ngữ, các chữ VIẾT Ct eececccccscscscscsesesscscscsesesescseavaceveeees Vi Danh mục các bảng biGU .eeccescessessessesssessessessssssessessessusssessessesssssessesseesesssessesseeaees vil Danh mục các hình vẽ, đồ thị.- - ¿6 St SE E‡EE‡E+EEEEEESEEEEEESESEEEErkekererkrrererres Vili 0.Khai thác đồ thị con phổ biến w.Giới thiệu chung về khai thác dit liệu đồ thị.Bài toán khai thác đồ thị con phô biến.Các hướng tiếp cận khai thác đồ thị con phổ biến .Khai thác đồ thị con phô biến trên đồ thị có trọng SO vecccsssscsessssvseesssvsesessveecacaveeecers 5 2.Bài toán khai thác đồ thị con phổ biến trên đồ thị có trọng SO ceececssscstcssestceeseeeeee 5 2.Các hướng tiếp cận khai thác đồ thị con phổ biến trên đồ thị có trọng s6.Hạn chế của các phương pháp trước đây .Động cơ nghiÊn CỨU.-- t1 1 9 90H HH HH HH ch ghi nh 7 3.Phương pháp tiếp cận của luận án dé khai thác đồ thị con phổ biến trên đồ thị có {ONG 7 .Mục tiêu của luận áñ.Phương pháp tiếp cận của luận án.-- 2 2-2 ©+2E£+EE+EEtEE2EEEEEEEErrkrrrrrkrrkee 8 3.Nội dung và phạm vi nghiên cứu của luận án.Các đóng góp chính và bố cục của luận án.---¿- ¿2 ++x++z++zx++rx+zzxzzeez 9 4.Các đóng góp chính của luận am .BỐ cục của luận án. - - 5c St E3 SE EEE51EE111511111511111111111 1111.

Các định nghĩa cơ bản về lý thuyết đồ thị. Cơ sở lý thuyết về khai thác đồ thị con phổ biến. Phát biểu bài toán.---¿--552+E tt tt tre 15 1H 1. Các thuật toán khai thác đồ thị con phổ biến.

Cơ sở lý thuyết về khai thác đồ thị con trên đồ thị có trọng số. Các định nghĩa về đồ thị có trọng SỐ. Phát biểu Dai toán. Cơ sở lý thuyết và mô hình bài toán khai thác đồ thị có trọng số.

Kết chương. PHƯƠNG PHAP KHAI THÁC DO THỊ CON TREN ĐỎ THỊ CÓ TRONG SỐ. Thuật toán WeraÌMI. --- - --- c1 122311122311 ng vn vn ng ng ng 36 2.

Cơ sở lý thuyết về độ đo MaxMiin.-- ¿5c ©2SESE£EE‡E2EEEerkerkerxerkrree 36 2. Tính độ hỗ trợ đầy đủ của một đồ thị con. Sử dụng chiến lược MaxMin dé tính trọng số cho đồ thị con. Cắt tia không gian tìm kiếm dựa vào trọng số của đồ thị con.

Mô tả thuật toán WeGraMi. ---- - << 5+ 133222111199 21 11199 vn vn ngư42 2. Độ phức tap của thuật toán WeGralMI.- -- -c S cs St sisirrerrrirrrrrree 46 2. Cơ sở dt liệu và môi trường thực nghiỆm.

Kết quả thực nghiệm .-- ¿- -- cSESE+SE+EE2EE2EEEEEEEEEEEEEEEE1121121E11 11111. Thuật toán OWGraMII.- - - --G 1 111 2111101111100 111g 111g KH kg kết 56 2. Tia danh sách cạnh phổ biến .-- 2-2 2 2 E+EE+EE+2EE2EE£EEtEEZEEzEErrkrrrerer 56 2. Xác định trọng số các đồ thị con dua trên trọng số của đồ thị cha.

Mô tả thuật toán OWGraMi. Độ phức tạp của thuật toán OWGTralI. cv vn vn re 67 2. Co sở dt liệu và môi trường thực nghiéM.

Kết quả thực nghiệm .-- 2-22 5£ x2E++EE+2EE2EEE2EEE2EE221 221211221. Kết chương. PHƯƠNG PHÁP MỞ RỘNG KHAI THÁC ĐỎ THỊ CON TRÊN DO THỊ CÓ TRỌNG SỐ.--- 555cc nh Hee 74 3. Giới thiệu hướng tiếp cận theo chiến lược áp dụng độ đo trung bình dé tính trọng số AG thi COM.

Cơ sở lý thuyết về chiến lược AveMin trong thuật toán AWeGraMi. Thuật toán AWeralMII. Sử dụng chiến lược AveMin dé tinh trong số cho các dé thị con pho biến. Giới hạn chặn trên dựa vào Chiến lược MaxMin.

Mô tả thuật toán AWeGralMI. kS HT TH HH HH HH Hệ, 80 3. Độ phức tạp của thuật toán AWeraMI. Cơ so đữ liệu và môi trường thực nghiỆm.

Kết quả thực nghiệm.-- 2-2: 5£ £+SE+EE‡EESEEE2EEEE1711211211271712211 211 E1, 84 3. KẾt chương. 90 CÔNG TRINH CUA TÁC GIẢ. 92 Danh mục các ký hiệu, thuật ngữ, các chữ viết tắt Chữ viết tắt Tiếng Anh Nghĩa tiếng Việt FSM Frequent Subgraph Mining Khai thác đồ thi con phô biến DFS Depth-first search Tìm kiếm theo chiều sâu Weighted Association Rule | Khai thác luật kết hợp có trọng WARM , Mining SỐ Weighted Sequential Patterns ; ¬ , WSM ¬ Khai thác chuỗi có trọng sô Mining DCP Downward Closure Property Tính chất bao đóng giảm CSP Constraint Satisfaction Problem MNI Minimum Image Based Support O Big O Độ phức tap của thuật toán Độ hỗ trợ day đủ của đồ thi con Suo(S) , Nay.

có trọng sô S trong do thị G Min Phép toán tìm giá trị nhỏ nhật Max Phép toán tìm giá trị lớn nhất VI Danh mục các bảng biêu Bảng 1.Cac phép gan hợp lệ của các đỉnh trong đồ thị S. Đặc trưng của ba bộ dit lIỆu.- --- - 5 62+ S319 SH ng re49 Bang 2. Tỉ lệ phát sinh các trọng SỐ.-- 2-2 ©5¿52 E+EE+EE£2EE+EEtEEeEEErExsrkrrkerex 49 Bang 2. So sánh ba bước khai thác giữa thuật toán WeGraMI và OWGraMI.

Tỉ lệ phát sinh các trọng SỐ.----- ¿2-2 ©E+SE+EE+EE£EE2EZEEEerEerkerkrrkrree 68 Bảng 3. Tính trọng số đồ thị con phô biến S theo chiến lược MaxMin và AveMin vil Danh mục các hình vẽ, đồ thị Hình 1.Vi dụ về đồ thị G có trọng số và đồ thị con S. Miễn giá tri hợp lệ của các đỉnh trong S dựa trên phép gan hop lệ. Các phép gan hợp lệ và không hợp lệ của S trong G.

Trọng số của các đỉnh trong đồ thị con và trọng số của đồ thị con. Ví dụ cho chiến lược MinMin.--c:-+cc+csccterrrrkrrrrrrrrrrrkrrrre 4I Hình 2. Đồ thị G sau khi cắt tia đỉnh cạnh không phổ biến. Các đồ thị con được phát sinh từ cạnh DM-AÏ.

Số lượng đồ thị con ứng viên (a) và số lượng đồ thị con phổ biến thỏa ngưỡng trọng số (b) trên bộ dit liệu MiCo [CT I].-2- 2222 s+x+z£2z++zx+zxczsz 50 Hình 2. Số lượng đồ thị con ứng viên (a) và số lượng đồ thị con phổ biến thỏa ngưỡng trọng số (b) trên bộ dit liệu Facebook [CTI].--- 2 2z scszs+zs2 +2 51 Hình 2. Số lượng đồ thị con ứng viên (a) và số lượng đồ thị con phổ biến thoả ngưỡng trọng số (b) trên bộ dit liệu CiteSeer [CT I].----- 2 52sz+zs+cs+zxzsz 51 Hình 2. Thời gian thực thi trên bộ dữ liệu MiCo [CT1].

Thời gian thực thi trên bộ dữ liệu Facebook [CT1 ]. Thời gian thực thi trên bộ dữ liệu CiteSeer [CTI]. Yêu cầu bộ nhớ đối với bộ dit liệu MiCo [CTI]. Yêu cầu bộ nhớ đối với bộ dữ liệu Facebook [CT1].

Yêu cầu bộ nhớ đối với bộ dit liệu CiteSeer [CTI1]. Các đỉnh và cạnh phổ biến trong đồ thị lớn G. Các phép gan hợp lệ và không hợp lệ cho các cạnh phổ bién. Các đồ thị con thoả trong số kết hợp với một cạnh không thoả ngưỡng {ONG SỐ.

Phat sinh các đồ thị con không thỏa trong số từ một cạnh phô biến không thoa 5g ăắắ 5. Tính trọng số cho các đỒ thị ŒOH.-¿- 5s St ‡EEE+EeEEeEeExerrkerxrrrree 66 Hình 2. Số lượng đồ thi con ứng viên của bộ dữ liệu Facebook [CT2]. Số lượng đồ thi con ứng viên của bộ dữ liệu CiteSeer [CT2].

Thời gian thực hiện trên tập dữ liệu Facebook [CT2]. Thời gian thực hiện trên tap dữ liệu CiteSeer [CT2]. Lượng bộ nhớ tiêu thụ trên tập dữ liệu Facebook [CT2]. Lượng bộ nhớ tiêu thụ trên tập dữ liệu Citeseer [CT2].

Một ví dụ về chiến lược AveMin. Một ví dụ tính trọng số đồ thị con theo chiến lược MaxMin và AveMin. Một vi dụ về chiến lược MaxMin và AveMin. Tỷ lệ trọng số trong hai bộ dit liệu (Facebook và CiteSeer).

Số lượng đồ thị con ứng viên [CT3]. Thời gian chạy cho hai bộ dữ liệu [CT5 ].- -- -- 55+ 55s s<<<es+seecss 86 Hình 3. Yêu cầu về bộ nhớ cho hai bộ dit liệu [CT3].-----2- 2 s52 87 ix PHAN MO ĐẦU Phần mở đầu của luận án giới thiệu chung về lĩnh vực khai thác dé liệu đồ thị, trong đó dé cập đến bài toán khai thác đồ thị con phố biến và các phương pháp tiếp cận dé giải bài toán này. Tiếp theo đó, luận án tập trung vào giới thiệu bài toán của luận án: khai thác đồ thị con phô biến trên đồ thị có trọng số và đề xuất các hướng tiếp cận dé giải quyết bài toán này.

Phần mở dau cũng giới thiệu bố cục và các đóng góp chính của luận án. Khai thác đồ thị con phé biến 1.