Khai Thác Đồ Thị Con Trên Đồ Thị Có Trọng Số - Luận Án Tiến Sĩ Khoa Học Máy Tính

• Tác giả: Lê Thị Ngọc Thảo
• Người hướng dẫn: Lê Hoài Bắc
• Trường học: Đại học Quốc gia Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Khai Thác Đồ Thị Con Trên Đồ Thị Có Trọng Số
• Loại tài liệu: Luận án tiến sĩ
• Năm xuất bản: 2023
• Địa điểm: TP. Hồ Chí Minh

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. PHẦN MỞ ĐẦU
• 1.1. Giới thiệu chung về khai thác dữ liệu đồ thị
• 1.2. Bài toán khai thác đồ thị con phổ biến
• 1.3. Các hướng tiếp cận khai thác đồ thị con phổ biến
• 1.4. Bố cục của luận án
• 2. CƠ SỞ LÝ THUYẾT VỀ KHAI THÁC ĐỒ THỊ CON TRÊN ĐỒ THỊ CÓ TRỌNG SỐ
• 2.1. Các định nghĩa cơ bản về lý thuyết đồ thị
• 2.2. Thuật toán WeGraMi
• 2.3. Cơ sở lý thuyết về độ đo MaxMin
• 2.4. Độ phức tạp của thuật toán WeGraMi
• 2.5. Cơ sở dữ liệu và môi trường thực nghiệm
• 2.6. Thuật toán OWGraMi
• 2.7. Tia danh sách cạnh phổ biến
• 2.8. Xác định trọng số các đồ thị con dựa trên trọng số của đồ thị cha
• 2.9. Độ phức tạp của thuật toán OWGraMi
• 2.10. Kết chương
• 3. PHƯƠNG PHÁP MỞ RỘNG KHAI THÁC ĐỒ THỊ CON TRÊN ĐỒ THỊ CÓ TRỌNG SỐ
• 3.1. Giới thiệu hướng tiếp cận theo chiến lược áp dụng độ đo trung bình để tính trọng số
• 3.2. Cơ sở lý thuyết về chiến lược AveMin trong thuật toán AWeGraMi
• 3.3. Thuật toán AWeGraMi
• 3.4. Độ phức tạp của thuật toán AWeGraMi
• 3.5. Cơ sở dữ liệu và môi trường thực nghiệm
• 3.6. Kết chương
• DANH MỤC CÁC KÝ HIỆU, THUẬT NGỮ, CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG BIỂU
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

I. Tổng Quan Khai Thác Đồ Thị Con Trên Đồ Thị Có Trọng Số

Trong bối cảnh dữ liệu lớn (Big Data) ngày càng phát triển, việc khai thác hiệu quả dữ liệu đồ thị trở nên vô cùng quan trọng. Cơ sở dữ liệu đồ thị là lựa chọn tối ưu để tổ chức và lưu trữ các tập dữ liệu phức tạp, đặc biệt là các dữ liệu có kết nối. Mô hình đồ thị có trọng số được sử dụng rộng rãi để mô phỏng các mối quan hệ phức tạp giữa các đối tượng với mức độ quan trọng khác nhau. Bài toán khai thác các đồ thị con có trọng số từ một đồ thị lớn trở thành bài toán quan trọng trong nhiều lĩnh vực khoa học. Chủ đề này thu hút nhiều nghiên cứu, đặc biệt khi chỉ có thể sử dụng đồ thị lớn có trọng số để biểu diễn sự khác biệt giữa các đối tượng.

1.1. Giới thiệu về Khai Thác Dữ Liệu Đồ Thị

Khai thác dữ liệu đồ thị trở thành tâm điểm trong khai thác dữ liệu lớn. Thay vì tập trung vào giá trị dữ liệu, khai thác dữ liệu đồ thị tập trung vào mối liên hệ giữa các điểm dữ liệu. Điều này đặc biệt quan trọng với dữ liệu lớn, đa dạng và có kết nối. Mô hình đồ thị lớn có trọng số mô phỏng các mối quan hệ phức tạp có mức độ quan trọng khác nhau, ví dụ như tầm quan trọng của một cá nhân trong mạng xã hội hoặc mức độ lưu thông trên bản đồ. Khai phá tri thức từ đồ thị giúp truy vấn những câu hỏi phức tạp, vượt ra ngoài kết nối dữ liệu ban đầu.

1.2. Bài Toán Khai Thác Đồ Thị Con Phổ Biến FSM

Bài toán tìm kiếm đồ thị con trên đồ thị có trọng số được đề xuất lần đầu bởi Cook và Holder. Khai thác đồ thị con phổ biến (FSM) là một bài toán tâm điểm trong lĩnh vực khai thác dữ liệu đồ thị. Đồ thị con là một đồ thị thu được từ đồ thị ban đầu bằng cách loại bỏ một số đỉnh và cạnh. Đồ thị con phổ biến có số lần xuất hiện trong một cơ sở dữ liệu đồ thị hoặc đồ thị lớn vượt ngưỡng cho trước. Giá trị ngưỡng này gọi là độ hỗ trợ tối thiểu (min-sup). Mục đích của FSM là khám phá tập dữ liệu đồ thị con xuất hiện thường xuyên.

II. Thách Thức Trong Khai Thác Đồ Thị Con Có Trọng Số Lớn

Các thuật toán tìm đồ thị con đẳng cấu phổ biến đối mặt với hai thách thức: (1) xác định một đồ thị con của một đồ thị xuất hiện trong các đồ thị khác; (2) liệt kê hiệu quả tất cả các đồ thị con phổ biến. Số lượng các đồ thị con tăng theo kích thước của nó và đồ thị. Do đó, cần các thuật toán hiệu quả để xử lý cơ sở dữ liệu đồ thị lớn, cấu trúc phức tạp. Hai chiến lược chính: phát sinh ứng viên và tăng trưởng mẫu. Mỗi chiến lược có ưu và nhược điểm riêng, đòi hỏi sự cân nhắc kỹ lưỡng trong việc lựa chọn thuật toán.

2.1. Đồ Thị Con Đẳng Cấu và Liệt Kê Hiệu Quả

Một trong những thách thức lớn nhất của khai thác đồ thị con gần đúng là xử lý đồ thị con đẳng cấu. Cần một phương pháp hiệu quả để xác định liệu một đồ thị con có tồn tại trong một đồ thị lớn hơn. Việc liệt kê tất cả các đồ thị con phổ biến cũng rất tốn kém về mặt tính toán. Các thuật toán cần phải được thiết kế để tránh liệt kê các đồ thị con dư thừa và tối ưu hóa quá trình tìm kiếm.

2.2. Chiến Lược Phát Sinh Ứng Viên và Tăng Trưởng Mẫu

Chiến lược phát sinh ứng viên kết hợp các đồ thị con có cùng kích thước để tạo thành một đồ thị con ứng viên lớn hơn. Chiến lược tăng trưởng mẫu mở rộng một đồ thị con phổ biến bằng cách thêm một cạnh phụ. Cả hai chiến lược đều có ưu và nhược điểm riêng. Phát sinh ứng viên có thể tốn kém về mặt tính toán, trong khi tăng trưởng mẫu có thể dẫn đến sự trùng lặp trong quá trình tạo ứng viên. Cần sự kết hợp của cả hai chiến lược để đạt được hiệu quả cao nhất.

2.3. Tính Chất Bao Đóng Giảm DCP và Bài Toán Khai Thác

Tính chất bao đóng giảm (DCP) không còn thỏa mãn trong bài toán khai thác đồ thị con phổ biến trên đồ thị có trọng số. Điều này làm cho các thuật toán sử dụng trong WARM và WSM ít được sử dụng trong khai thác đồ thị con phổ biến vì không thể kiểm soát quá trình phát sinh tập ứng viên. Tuy nhiên, ý tưởng của WARM vẫn được vận dụng vào thuật toán khai thác đồ thị con có trọng số trên cạnh.

III. Thuật Toán WeGraMi Khai Thác Đồ Thị Con Trọng Số Hiệu Quả

Luận án đề xuất phương pháp tiếp cận mới để khai thác đồ thị con trên đồ thị có trọng số. Phương pháp này sử dụng độ đo MaxMin để tính trọng số cho đồ thị con. Thuật toán khai thác đồ thị con có trọng số WeGraMi được thiết kế để cắt tỉa không gian tìm kiếm dựa vào trọng số của đồ thị con, giúp giảm đáng kể chi phí tính toán. WeGraMi cung cấp giải pháp hiệu quả để khai thác đồ thị con phổ biến trong các đồ thị có trọng số lớn, phức tạp. Các bước triển khai thuật toán WeGraMi bao gồm tính độ hỗ trợ đầy đủ của một đồ thị con và sử dụng chiến lược MaxMin.

3.1. Cơ Sở Lý Thuyết Về Độ Đo MaxMin

Độ đo MaxMin được sử dụng để tính trọng số cho đồ thị con. Việc sử dụng MaxMin giúp đảm bảo rằng trọng số của đồ thị con phản ánh chính xác mức độ quan trọng của nó trong đồ thị lớn. MaxMin tập trung vào giá trị nhỏ nhất, giá trị lớn nhất và trung bình của các cạnh và đỉnh. Thuật toán tính độ đo trung tâm trong đồ thị đảm bảo trọng số của đồ thị con không bị ảnh hưởng bởi các đỉnh hoặc cạnh có trọng số thấp.

3.2. Cắt Tỉa Không Gian Tìm Kiếm Bằng Trọng Số

WeGraMi cắt tia không gian tìm kiếm dựa vào trọng số của đồ thị con. Điều này giúp giảm đáng kể số lượng các đồ thị con cần được xem xét, từ đó giảm chi phí tính toán. WeGraMi sử dụng ngưỡng trọng số để loại bỏ các đồ thị con không phổ biến, làm cho quá trình khai thác hiệu quả hơn. Độ phức tạp của khai thác đồ thị con trên đồ thị có trọng số cũng được giảm tải nhờ cơ chế này.

3.3. Mô Tả Chi Tiết Thuật Toán WeGraMi

Thuật toán WeGraMi bao gồm các bước sau: (1) Tính độ hỗ trợ đầy đủ của một đồ thị con. (2) Sử dụng chiến lược MaxMin để tính trọng số cho đồ thị con. (3) Cắt tia không gian tìm kiếm dựa vào trọng số của đồ thị con. (4) Lặp lại các bước trên cho đến khi tất cả các đồ thị con phổ biến được tìm thấy. Chi tiết về code cũng như các biến thể của thuật toán được mô tả trong luận án.

IV. Tối Ưu Hóa Thuật Toán WeGraMi OWGraMi AWeGraMi

Luận án giới thiệu các thuật toán tối ưu hóa WeGraMi, bao gồm OWGraMi và AWeGraMi, để cải thiện hiệu suất khai thác. OWGraMi sử dụng tia danh sách cạnh phổ biến và xác định trọng số dựa trên đồ thị cha. AWeGraMi áp dụng độ đo trung bình (AveMin) để tính trọng số, kết hợp giới hạn chặn trên dựa trên chiến lược MaxMin. Các cải tiến này giúp tăng tốc độ khai thác và giảm yêu cầu bộ nhớ. Mô hình đồ thị có trọng số trở nên linh hoạt hơn khi sử dụng các thuật toán này.

4.1. Thuật Toán OWGraMi Sử Dụng Danh Sách Cạnh Phổ Biến

OWGraMi (Optimized WeGraMi) sử dụng tia danh sách cạnh phổ biến để giảm số lượng các đồ thị con cần được xem xét. OWGraMi xác định trọng số của các đồ thị con dựa trên trọng số của đồ thị cha, giúp giảm chi phí tính toán. OWGraMi đặc biệt hiệu quả khi khai thác các đồ thị lớn có nhiều cạnh phổ biến. Phân tích mạng xã hội bằng đồ thị có thể tận dụng OWGraMi để nhanh chóng tìm ra các cộng đồng quan trọng.

4.2. Thuật Toán AWeGraMi Chiến Lược Độ Đo Trung Bình AveMin

AWeGraMi (Averaged WeGraMi) sử dụng chiến lược AveMin để tính trọng số cho các đồ thị con phổ biến. AveMin tính trung bình trọng số của các cạnh và đỉnh, cung cấp một ước tính chính xác hơn về mức độ quan trọng của đồ thị con. AWeGraMi kết hợp giới hạn chặn trên dựa trên chiến lược MaxMin, giúp giảm không gian tìm kiếm và tăng tốc độ khai thác. Bioinformatics đồ thị có thể áp dụng AWeGraMi để phân tích các mạng lưới tương tác protein.

4.3. So sánh OWGraMi AWeGraMi và WeGraMi

Mỗi thuật toán đều có ưu điểm riêng. WeGraMi là thuật toán cơ bản, OWGraMi tối ưu hóa bằng danh sách cạnh phổ biến và AWeGraMi tối ưu hóa bằng độ đo trung bình. Việc lựa chọn thuật toán phụ thuộc vào đặc điểm của đồ thị đầu vào. Ví dụ, OWGraMi hiệu quả với đồ thị có nhiều cạnh phổ biến, trong khi AWeGraMi hiệu quả hơn với đồ thị có trọng số phân bố không đều.

V. Ứng Dụng Kết Quả Nghiên Cứu Khai Thác Đồ Thị Con Trọng Số

Các thuật toán khai thác đồ thị con trọng số, đặc biệt là WeGraMi, OWGraMi và AWeGraMi, có ứng dụng rộng rãi trong nhiều lĩnh vực. Phân tích mạng xã hội, hệ hỗ trợ ra quyết định, phân tích dữ liệu và phát sinh luật kết hợp là những lĩnh vực hưởng lợi từ nghiên cứu này. Kết quả thực nghiệm cho thấy các thuật toán đề xuất có hiệu suất cao hơn so với các phương pháp hiện có, đặc biệt là trên các tập dữ liệu lớn và phức tạp. Machine learning đồ thị cũng tận dụng các kết quả nghiên cứu này.

5.1. Ứng Dụng Trong Phân Tích Mạng Xã Hội

Trong phân tích mạng xã hội, các thuật toán khai thác đồ thị con trọng số có thể được sử dụng để xác định các cộng đồng, tìm kiếm các cá nhân có ảnh hưởng và phát hiện các xu hướng. Trọng số cạnh có thể biểu diễn mức độ tương tác giữa các cá nhân, trong khi trọng số đỉnh có thể biểu diễn mức độ quan trọng của một cá nhân trong mạng. Các thuật toán này giúp hiểu rõ hơn về cấu trúc và động lực của mạng xã hội.

5.2. Ứng Dụng Trong Hệ Hỗ Trợ Ra Quyết Định

Trong hệ hỗ trợ ra quyết định, các thuật toán khai thác đồ thị con trọng số có thể được sử dụng để tìm kiếm các mẫu và mối quan hệ quan trọng trong dữ liệu. Các mẫu này có thể giúp người ra quyết định hiểu rõ hơn về tình hình và đưa ra các quyết định tốt hơn. Ví dụ, trong lĩnh vực tài chính, các thuật toán này có thể được sử dụng để phát hiện các gian lận và đánh giá rủi ro.

5.3. Kết Quả Thực Nghiệm và Đánh Giá Hiệu Năng

Kết quả thực nghiệm cho thấy các thuật toán WeGraMi, OWGraMi và AWeGraMi có hiệu suất cao hơn so với các phương pháp hiện có. Các thuật toán này có thể xử lý các tập dữ liệu lớn và phức tạp trong thời gian ngắn. OWGraMi và AWeGraMi đặc biệt hiệu quả khi khai thác các đồ thị có nhiều cạnh phổ biến hoặc trọng số phân bố không đều. Data Mining đồ thị ngày càng hiệu quả hơn nhờ những nghiên cứu này.

VI. Kết Luận Hướng Phát Triển Khai Thác Đồ Thị Con

Luận án đã trình bày một phương pháp hiệu quả để khai thác đồ thị con thuộc tính trên đồ thị có trọng số. Các thuật toán WeGraMi, OWGraMi và AWeGraMi cung cấp các giải pháp mạnh mẽ để giải quyết bài toán quan trọng này. Hướng phát triển trong tương lai bao gồm khai thác trên đồ thị động, đồ thị lớn, đồ thị thưa và đồ thị dày. Nghiên cứu này mở ra nhiều cơ hội cho các ứng dụng thực tế và đóng góp vào sự phát triển của lĩnh vực khai thác dữ liệu đồ thị.

6.1. Tóm Tắt Các Đóng Góp Chính Của Luận Án

Luận án đóng góp vào lĩnh vực khai thác dữ liệu đồ thị bằng cách đề xuất một phương pháp hiệu quả để khai thác đồ thị con trọng số. Các thuật toán WeGraMi, OWGraMi và AWeGraMi cung cấp các giải pháp mạnh mẽ để giải quyết bài toán quan trọng này. Nghiên cứu này cũng cung cấp các kết quả thực nghiệm chứng minh hiệu suất của các thuật toán đề xuất.

6.2. Hướng Nghiên Cứu Tương Lai Đồ Thị Động và Đồ Thị Lớn

Hướng nghiên cứu trong tương lai bao gồm khai thác trên đồ thị động, đồ thị lớn, đồ thị thưa và đồ thị dày. Khai thác trên đồ thị động đòi hỏi các thuật toán có thể xử lý sự thay đổi theo thời gian. Khai thác trên đồ thị lớn đòi hỏi các thuật toán có thể mở rộng quy mô và xử lý các tập dữ liệu lớn. Khai thác trên đồ thị thưa và đồ thị dày đòi hỏi các thuật toán có thể tận dụng cấu trúc của đồ thị để cải thiện hiệu suất. Tìm kiếm mẫu đồ thị sẽ trở nên quan trọng hơn khi kích thước đồ thị tăng lên.

6.3. Ứng Dụng Tiềm Năng và Kết Hợp Với Machine Learning

Nghiên cứu này mở ra nhiều cơ hội cho các ứng dụng thực tế trong nhiều lĩnh vực, bao gồm phân tích mạng xã hội, hệ hỗ trợ ra quyết định và phân tích dữ liệu. Ngoài ra, có thể kết hợp các thuật toán khai thác đồ thị con trọng số với các kỹ thuật machine learning để tạo ra các hệ thống thông minh hơn. Cắt đồ thị và các kỹ thuật độ đo gắn kết trong đồ thị sẽ giúp tạo ra những ứng dụng hiệu quả hơn.