Khai Phá Đồ Thị Con Đẳng Cấu Trong Khoa Học Dữ Liệu

Luận văn thạc sĩ toán học nghiên cứu bài toán đồ thị con đẳng cấu trong khai phá dữ liệu đồ thị và ứng dụng phát hiện đồ thị con phổ biến, khảo sát thực trạng, phân tích nguyên

• Tác giả: Phạm Thị Liên
• Người hướng dẫn: PGS. Đoàn Văn Ban
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Bài Toán Đồ Thị Con Đẳng Cấu Trong Khai Phá Dữ Liệu Đồ Thị Và Ứng Dụng Phát Hiện Đồ Thị Con Phổ Biến
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: KHAI PHÁ ĐỒ THỊ
• 1.1. Cấu trúc đồ thị
• 1.2. Các dạng biểu diễn cấu trúc dữ liệu đồ thị
• 1.3. Danh sách liên thuộc
• 1.4. Danh sách liền kề
• 1.5. Ma trận liên thuộc
• 1.6. Ma trận liền kề
• 1.7. Dạng chính tắc của đồ thị. Các kỹ thuật khai phá đồ thị
• 1.8. Phát hiện cấu trúc cộng đồng mạng xã hội
• 1.9. Khai phá đồ thị con thường xuyên đóng
• 1.10. Tổng kết chương 1
• 2. CHƯƠNG 2: BÀI TOÁN ĐỒ THỊ ĐẲNG CẤU VÀ KHAI PHÁ ĐỒ THỊ CON PHỔ BIẾN
• 2.1. Bài toán đồ thị đẳng cấu. Thuật toán kiểm tra đồ thị đẳng cấu
• 2.2. Thuật toán Dijsktra tìm đường đi ngắn nhất
• 2.3. Thuật toán tính khoảng cách d(u, v) trong các đồ thị phụ thêm và đồ thị kết đôi
• 2.4. Thuật toán xác ma trận dấu và dạng chính tắc của nó
• 2.5. Thuật toán sắp xếp các đỉnh của hai đồ thị để kiểm tra tính đẳng cấu của chúng dựa vào dạng chính tắc
• 2.6. Một số tính chất của đồ thị đẳng cấu
• 2.7. Bài toán đẳng cấu đồ thị con SGI
• 2.8. Một số khái niệm cơ sở và ký hiệu
• 2.9. Cây quyết định của đồ thị
• 2.10. Thuật toán xây dựng cây quyết định
• 2.11. Khai phá đồ thị con phổ biến
• 2.12. Cây các đồ thị con dạng chính tắc
• 2.13. Phép kết nối N-Join hai đồ thị
• 2.14. Thuật toán FFSM cho khai phá đồ thị con phổ biến trong CSDL đồ thị
• 2.15. Kết luận chương 2
• 3. CHƯƠNG 3: THỬ NGHIỆM VÀ ĐÁNH GIÁ
• 3.1. Dữ liệu và môi trường thử nghiệm
• 3.2. Bộ dữ liệu thử nghiệm
• 3.3. Môi trường thử nghiệm
• 3.4. Cài đặt và thử nghiệm thuật toán tìm kiếm tra đồ thị đẳng cấu
• 3.5. Mô tả yêu cầu bài toán kiếm tra đồ thị đẳng cấu
• 3.6. Kết quả thử nghiệm
• 3.7. Thử nghiệm thuật toán FFSM cho khai phá đồ thị con phổ biến
• 3.8. Mô tả yêu cầu bài toán khai phá đồ thị con phổ biến
• 3.9. Phân tích đánh giá kết quả
• 3.10. Kết luận chương 3
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Khai Phá Đồ Thị Con Đẳng Cấu Giới Thiệu

Khai phá đồ thị con là một lĩnh vực quan trọng trong khai thác dữ liệu đồ thị, tập trung vào việc tìm kiếm các mẫu hoặc cấu trúc con xuất hiện thường xuyên hoặc có ý nghĩa trong một hoặc nhiều đồ thị lớn. Bài toán đồ thị con đẳng cấu là một bài toán cơ bản trong lĩnh vực này, liên quan đến việc xác định xem một đồ thị nhỏ hơn (đồ thị con) có tồn tại trong một đồ thị lớn hơn hay không, sao cho cấu trúc liên kết của đồ thị con được bảo toàn. Ứng dụng của khai phá đồ thị con đẳng cấu rất đa dạng, từ tin sinh học (tìm kiếm các motif trong mạng lưới protein) đến phân tích mạng xã hội (phát hiện các cộng đồng nhỏ). Luận văn này sẽ đi sâu vào các thuật toán và ứng dụng của bài toán này. Theo [8], đồ thị là một biểu diễn hình ảnh của các đối tượng dữ liệu (đỉnh) và mối quan hệ giữa chúng (cạnh).

1.1. Định Nghĩa và Ý Nghĩa của Đồ Thị Con Đẳng Cấu

Bài toán đồ thị con đẳng cấu (Subgraph Isomorphism - SGI) là bài toán NP-đầy đủ, có nghĩa là việc tìm ra một thuật toán hiệu quả để giải quyết bài toán này là một thách thức lớn. Về cơ bản, bài toán này yêu cầu tìm một ánh xạ một-một từ các đỉnh của đồ thị con vào các đỉnh của đồ thị lớn hơn, sao cho các cạnh tương ứng cũng được bảo toàn. Việc giải quyết bài toán này có ý nghĩa quan trọng trong nhiều lĩnh vực, giúp chúng ta hiểu rõ hơn về cấu trúc và tính chất của dữ liệu đồ thị. Ví dụ, trong hóa tin học, việc tìm kiếm các mẫu đồ thị (substructure) trong các phân tử có thể giúp dự đoán tính chất hóa học của chúng.

1.2. Các Ứng Dụng Tiềm Năng Của Khai Phá Đồ Thị Con

Ứng dụng của khai phá đồ thị con rất rộng rãi. Trong tin sinh học, nó được sử dụng để phân tích mạng lưới tương tác protein, tìm kiếm các motif quan trọng trong điều hòa gen. Trong mạng xã hội, nó giúp phát hiện các cộng đồng nhỏ, phân tích hành vi người dùng và phát hiện gian lận. Trong an ninh mạng, nó có thể được sử dụng để phát hiện các cuộc tấn công mạng dựa trên phân tích mô hình đồ thị của lưu lượng mạng. Ngoài ra, khai phá đồ thị con còn được ứng dụng trong cơ sở dữ liệu đồ thị để truy vấn dữ liệu và tìm kiếm các mẫu phức tạp.

II. Thách Thức Trong Tìm Kiếm Đẳng Cấu Đồ Thị Con Vấn Đề

Bài toán tìm kiếm đẳng cấu đồ thị con đối mặt với nhiều thách thức lớn, chủ yếu do độ phức tạp tính toán của nó. Việc kiểm tra tất cả các khả năng ánh xạ giữa các đỉnh của đồ thị con và đồ thị lớn hơn là không khả thi đối với các đồ thị có kích thước lớn. Hơn nữa, sự tồn tại của các cấu trúc đồ thị phức tạp, như các chu trình và các thành phần liên thông mạnh, làm tăng thêm độ khó của bài toán. Các thuật toán hiện tại thường phải đối mặt với vấn đề độ phức tạp tính toán cao, đặc biệt khi kích thước của đồ thị tăng lên. Theo luận văn, độ phức tạp của bài toán tăng lên đáng kể khi đồ thị có số đỉnh lớn và mật độ cạnh dày.

2.1. Độ Phức Tạp Tính Toán Của Bài Toán Đẳng Cấu Đồ Thị Con

Bài toán đẳng cấu đồ thị con là một bài toán NP-đầy đủ, có nghĩa là không có thuật toán nào được biết đến có thể giải quyết bài toán này trong thời gian đa thức. Các thuật toán hiện tại thường có độ phức tạp theo cấp số mũ, khiến chúng trở nên không khả thi đối với các đồ thị lớn. Việc giảm độ phức tạp tính toán là một trong những mục tiêu chính của các nghiên cứu trong lĩnh vực này. Các kỹ thuật như tối ưu hóa đồ thị và sử dụng các heuristic có thể giúp cải thiện hiệu suất của các thuật toán.

2.2. Ảnh Hưởng Của Kích Thước và Mật Độ Đồ Thị Đến Hiệu Suất

Kích thước và mật độ của đồ thị có ảnh hưởng lớn đến hiệu suất của các thuật toán tìm kiếm đẳng cấu đồ thị con. Khi kích thước của đồ thị tăng lên, số lượng các khả năng ánh xạ giữa các đỉnh cũng tăng lên theo cấp số mũ, làm tăng thời gian tính toán. Tương tự, khi mật độ của đồ thị tăng lên, số lượng các cạnh cũng tăng lên, làm tăng độ phức tạp của việc kiểm tra tính đẳng cấu. Do đó, việc phát triển các thuật toán có thể xử lý hiệu quả các đồ thị lớn và dày đặc là một thách thức quan trọng.

III. Phương Pháp FFSM Khai Phá Đồ Thị Con Phổ Biến Hiệu Quả

Thuật toán FFSM (Fast Frequent Subgraph Mining) là một phương pháp hiệu quả để khai phá đồ thị con phổ biến trong cơ sở dữ liệu đồ thị. FFSM sử dụng một cách tiếp cận dựa trên việc mở rộng các đồ thị con, bắt đầu từ các cạnh đơn và dần dần thêm các đỉnh và cạnh mới để tạo ra các đồ thị con lớn hơn. Thuật toán này sử dụng các kỹ thuật tối ưu hóa đồ thị để giảm số lượng các đồ thị con cần kiểm tra, giúp cải thiện hiệu suất. Theo luận văn, FFSM có thể được sử dụng để liệt kê các đồ thị con phổ biến trên các bộ dữ liệu đồ thị.

3.1. Nguyên Lý Hoạt Động Của Thuật Toán FFSM

FFSM hoạt động bằng cách xây dựng một cây tìm kiếm, trong đó mỗi nút đại diện cho một đồ thị con. Thuật toán bắt đầu từ gốc của cây, đại diện cho một cạnh đơn, và dần dần mở rộng cây bằng cách thêm các đỉnh và cạnh mới. Tại mỗi bước, thuật toán kiểm tra xem đồ thị con hiện tại có phải là phổ biến hay không, dựa trên một ngưỡng hỗ trợ tối thiểu. Nếu đồ thị con là phổ biến, nó sẽ được thêm vào cây tìm kiếm và thuật toán tiếp tục mở rộng nó. Nếu không, nó sẽ bị loại bỏ. Thuật toán sử dụng các kỹ thuật tối ưu hóa đồ thị để giảm số lượng các đồ thị con cần kiểm tra.

3.2. Ưu Điểm và Hạn Chế Của FFSM Trong Khai Phá Đồ Thị

Ưu điểm chính của FFSM là hiệu suất cao, đặc biệt đối với các đồ thị có kích thước lớn và mật độ cao. Thuật toán này sử dụng các kỹ thuật tối ưu hóa đồ thị để giảm số lượng các đồ thị con cần kiểm tra, giúp cải thiện hiệu suất. Tuy nhiên, FFSM cũng có một số hạn chế. Ví dụ, nó có thể không hiệu quả đối với các đồ thị có cấu trúc rất phức tạp hoặc khi ngưỡng hỗ trợ tối thiểu quá thấp. Ngoài ra, FFSM có thể yêu cầu một lượng lớn bộ nhớ để lưu trữ cây tìm kiếm.

IV. Cây Quyết Định SGI Phương Pháp Kiểm Tra Đẳng Cấu Đồ Thị

Cây quyết định SGI (Subgraph Isomorphism Decision Tree) là một phương pháp tiếp cận dựa trên học máy trên đồ thị để kiểm tra tính đẳng cấu đồ thị con. Phương pháp này sử dụng một cây quyết định để phân loại các ma trận liền kề của đồ thị, giúp xác định xem một đồ thị con có tồn tại trong một đồ thị lớn hơn hay không. Cây quyết định được xây dựng dựa trên các đặc trưng của đồ thị, như bậc của các đỉnh và số lượng các cạnh. Theo luận văn, cây quyết định SGI có thể được sử dụng để phân loại các ma trận liền kề của đồ thị.

4.1. Xây Dựng Cây Quyết Định Để Kiểm Tra Đẳng Cấu

Việc xây dựng cây quyết định SGI bao gồm việc chọn các đặc trưng phù hợp của đồ thị và sử dụng chúng để phân loại các ma trận liền kề. Các đặc trưng có thể bao gồm bậc của các đỉnh, số lượng các cạnh, và các thuộc tính khác của đồ thị. Cây quyết định được xây dựng bằng cách sử dụng một thuật toán học máy, như ID3 hoặc C4.5. Sau khi cây quyết định được xây dựng, nó có thể được sử dụng để kiểm tra tính đẳng cấu đồ thị con bằng cách phân loại ma trận liền kề của đồ thị con và so sánh nó với các ma trận liền kề của đồ thị lớn hơn.

4.2. Ưu Điểm và Hạn Chế Của Cây Quyết Định SGI

Ưu điểm chính của cây quyết định SGI là khả năng xử lý các đồ thị có kích thước lớn và phức tạp. Phương pháp này sử dụng học máy trên đồ thị để tự động học các đặc trưng quan trọng của đồ thị, giúp cải thiện hiệu suất. Tuy nhiên, cây quyết định SGI cũng có một số hạn chế. Ví dụ, việc xây dựng cây quyết định có thể tốn thời gian, đặc biệt đối với các đồ thị rất lớn. Ngoài ra, hiệu suất của cây quyết định phụ thuộc vào chất lượng của các đặc trưng được chọn.

V. Ứng Dụng Thực Tế Phát Hiện Đồ Thị Con Phổ Biến Trong Tin Sinh

Khai phá đồ thị con phổ biến có nhiều ứng dụng thực tế, đặc biệt trong lĩnh vực tin sinh học. Trong tin sinh học, đồ thị được sử dụng để biểu diễn các mạng lưới tương tác protein, các con đường trao đổi chất, và các cấu trúc sinh học khác. Việc phát hiện các đồ thị con phổ biến trong các mạng lưới này có thể giúp các nhà khoa học hiểu rõ hơn về các quá trình sinh học và phát triển các phương pháp điều trị bệnh hiệu quả hơn. Ví dụ, việc tìm kiếm các motif trong mạng lưới tương tác protein có thể giúp xác định các protein quan trọng trong một con đường trao đổi chất.

5.1. Phân Tích Mạng Lưới Tương Tác Protein Bằng Khai Phá Đồ Thị

Các mạng lưới tương tác protein là các đồ thị trong đó các đỉnh đại diện cho các protein và các cạnh đại diện cho các tương tác giữa chúng. Việc phân tích các mạng lưới này bằng khai phá đồ thị có thể giúp xác định các protein quan trọng trong một quá trình sinh học cụ thể. Ví dụ, việc tìm kiếm các đồ thị con phổ biến trong các mạng lưới này có thể giúp xác định các protein có vai trò quan trọng trong điều hòa gen hoặc trong các con đường trao đổi chất.

5.2. Tìm Kiếm Motif Trong Các Con Đường Trao Đổi Chất

Các con đường trao đổi chất là các chuỗi các phản ứng hóa học xảy ra trong tế bào. Các con đường này có thể được biểu diễn dưới dạng đồ thị, trong đó các đỉnh đại diện cho các phân tử và các cạnh đại diện cho các phản ứng hóa học. Việc tìm kiếm các motif trong các con đường này có thể giúp xác định các phản ứng quan trọng và các enzyme có vai trò quan trọng trong quá trình trao đổi chất. Các motif này có thể được sử dụng để phát triển các phương pháp điều trị bệnh bằng cách nhắm mục tiêu vào các enzyme quan trọng.

VI. Kết Luận và Hướng Phát Triển Tương Lai Khai Phá Đồ Thị

Bài toán khai phá đồ thị con đẳng cấu và khai phá đồ thị con phổ biến là những lĩnh vực nghiên cứu quan trọng với nhiều ứng dụng thực tế. Mặc dù đã có nhiều tiến bộ trong lĩnh vực này, vẫn còn nhiều thách thức cần giải quyết, đặc biệt là vấn đề độ phức tạp tính toán. Các hướng nghiên cứu trong tương lai có thể tập trung vào việc phát triển các thuật toán hiệu quả hơn, sử dụng các kỹ thuật tối ưu hóa đồ thị và học máy trên đồ thị. Ngoài ra, việc khám phá các ứng dụng mới của khai phá đồ thị trong các lĩnh vực khác nhau cũng là một hướng đi đầy hứa hẹn.

6.1. Các Hướng Nghiên Cứu Tiềm Năng Trong Tương Lai

Các hướng nghiên cứu tiềm năng trong tương lai bao gồm việc phát triển các thuật toán khai phá đồ thị song song và phân tán, sử dụng các kỹ thuật học sâu trên đồ thị, và khám phá các ứng dụng mới của khai phá đồ thị trong các lĩnh vực như phân tích mạng xã hội, an ninh mạng, và trí tuệ nhân tạo. Ngoài ra, việc phát triển các công cụ và thư viện phần mềm dễ sử dụng để hỗ trợ khai phá đồ thị cũng là một hướng đi quan trọng.

6.2. Tầm Quan Trọng Của Khai Phá Đồ Thị Trong Kỷ Nguyên Dữ Liệu Lớn

Trong kỷ nguyên dữ liệu lớn, khai phá đồ thị đóng vai trò ngày càng quan trọng trong việc phân tích và khai thác thông tin từ các tập dữ liệu phức tạp. Các đồ thị có thể được sử dụng để biểu diễn nhiều loại dữ liệu khác nhau, từ mạng xã hội đến mạng lưới giao thông và mạng lưới sinh học. Việc phát triển các thuật toán và công cụ hiệu quả để khai phá đồ thị là rất quan trọng để tận dụng tối đa tiềm năng của dữ liệu lớn.

Nội dung chính

Tổng quan nghiên cứu

Khai phá dữ liệu đồ thị là lĩnh vực nghiên cứu quan trọng trong khoa học máy tính, với ứng dụng rộng rãi trong các ngành như tin sinh học, hóa học, mạng xã hội, và cơ sở dữ liệu. Theo ước tính, các tập dữ liệu đồ thị ngày càng phức tạp và có kích thước lớn, đòi hỏi các phương pháp khai phá hiệu quả để phát hiện các cấu trúc tiềm ẩn như đồ thị con phổ biến và các đồ thị con đẳng cấu. Bài toán đồ thị con đẳng cấu (Graph Isomorphism) và khai phá đồ thị con phổ biến là những thách thức lớn do độ phức tạp tính toán cao, đặc biệt khi số đỉnh và cạnh của đồ thị tăng lên. Mục tiêu nghiên cứu của luận văn là phát triển và đánh giá các thuật toán kiểm tra đẳng cấu đồ thị và khai phá đồ thị con phổ biến trong cơ sở dữ liệu đồ thị, nhằm nâng cao hiệu quả khai phá dữ liệu đồ thị trong thực tế. Phạm vi nghiên cứu tập trung vào các đồ thị vô hướng, không trọng số, với các thuật toán được thử nghiệm trên bộ dữ liệu đồ thị thực nghiệm tại Việt Nam trong giai đoạn 2018-2020. Ý nghĩa nghiên cứu thể hiện qua việc cung cấp các công cụ thuật toán có độ phức tạp đa thức, giúp giảm thiểu thời gian xử lý và tăng độ chính xác trong phát hiện các mẫu đồ thị con phổ biến, góp phần thúc đẩy ứng dụng khai phá dữ liệu đồ thị trong các lĩnh vực khoa học và công nghiệp.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình nghiên cứu sau:

• Lý thuyết đồ thị: Định nghĩa đồ thị vô hướng, đơn đồ thị, đồ thị con, ma trận liền kề, ma trận liên thuộc, và dạng chính tắc của đồ thị (Canonical Adjacency Matrix - CAM). Các khái niệm về đường đi ngắn nhất, bậc đỉnh, đồ thị liên thông được sử dụng để phân tích cấu trúc đồ thị.

• Bài toán đẳng cấu đồ thị (Graph Isomorphism - GI): Xác định sự tồn tại của ánh xạ song ánh giữa hai đồ thị sao cho bảo toàn cấu trúc cạnh và nhãn đỉnh. Thuật toán kiểm tra đẳng cấu dựa trên ma trận dấu (sign matrix) và dạng chính tắc của ma trận dấu, sử dụng vector tần suất dấu để phân loại đỉnh.

• Khai phá đồ thị con phổ biến (Frequent Subgraph Mining - FSM): Tìm kiếm các đồ thị con xuất hiện với tần suất tối thiểu trong cơ sở dữ liệu đồ thị. Thuật toán FFSM (Fast Frequent Subgraph Mining) và PSI-CFSM được áp dụng để khai phá các đồ thị con thường xuyên đóng, giúp giảm thiểu số lượng đồ thị con cần lưu trữ.

• Cây quyết định (Decision Tree): Mô hình cây dùng để phân lớp các ma trận liền kề của đồ thị, hỗ trợ việc kiểm tra đẳng cấu đồ thị con hiệu quả bằng cách tổ chức các hoán vị ma trận liền kề thành cấu trúc cây phân cấp.

Các khái niệm chính bao gồm: ma trận liền kề, ma trận dấu, vector tần suất dấu, đồ thị con thường xuyên đóng, cây quyết định, phép kết nối N-Join và phép mở rộng N-Extension.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Bộ dữ liệu thử nghiệm gồm khoảng 10.000 đồ thị vô hướng, không trọng số, được thu thập từ các ứng dụng thực tế và mô phỏng tại Viện Công nghệ Thông tin – Viện Hàn lâm Khoa học và Công nghệ Việt Nam.

• Phương pháp phân tích: Luận văn sử dụng phương pháp nghiên cứu lý thuyết kết hợp thực nghiệm. Thuật toán kiểm tra đẳng cấu đồ thị được cài đặt dựa trên ma trận dấu và dạng chính tắc, thuật toán FFSM được triển khai để khai phá đồ thị con phổ biến. Các thuật toán được đánh giá hiệu suất qua thời gian chạy và số lượng đồ thị con tìm được với các ngưỡng độ hỗ trợ tối thiểu khác nhau.

• Timeline nghiên cứu: Quá trình nghiên cứu kéo dài trong 2 năm (2018-2020), bao gồm giai đoạn thu thập tài liệu, phát triển thuật toán, cài đặt chương trình thử nghiệm, và phân tích kết quả trên bộ dữ liệu thực nghiệm.

• Cỡ mẫu và chọn mẫu: Cỡ mẫu gồm 10.000 đồ thị được chọn ngẫu nhiên từ các bộ dữ liệu lớn, đảm bảo tính đại diện cho các loại đồ thị phổ biến trong ứng dụng khai phá dữ liệu.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả thuật toán kiểm tra đẳng cấu đồ thị: Thuật toán graphIsomorphism dựa trên ma trận dấu và dạng chính tắc cho phép kiểm tra đẳng cấu hai đồ thị có số đỉnh lên đến 100 trong thời gian đa thức, với độ phức tạp tính toán tối đa khoảng $2n^5 + 14n^4 + 14n^3 + 4n^2$ bước thực hiện. Kết quả thử nghiệm trên bộ dữ liệu 10.000 đồ thị cho thấy thời gian trung bình kiểm tra một cặp đồ thị là dưới 5 giây.

2. Thuật toán FFSM khai phá đồ thị con phổ biến: Thuật toán FFSM thực hiện khai phá các đồ thị con phổ biến với ngưỡng độ hỗ trợ tối thiểu (minsup) từ 0.1 đến 0.5. Với minsup = 0.3, thuật toán tìm được khoảng 1.200 đồ thị con phổ biến trong bộ dữ liệu 10.000 đồ thị, giảm 40% so với việc khai phá toàn bộ đồ thị con thường xuyên.

3. Ứng dụng cây quyết định trong phân lớp ma trận liền kề: Việc tổ chức các hoán vị ma trận liền kề thành cây quyết định giúp giảm đáng kể số phép so sánh khi kiểm tra đẳng cấu đồ thị con. Cây quyết định compact giảm được khoảng 30% số nút so với cây quyết định thông thường, tăng tốc độ phân lớp và kiểm tra.

4. Phép kết nối N-Join và mở rộng N-Extension: Hai phép toán này giúp tối ưu hóa quá trình sinh đồ thị con ứng viên trong khai phá đồ thị con phổ biến, giảm thiểu số lượng đồ thị con trùng lặp và tăng hiệu quả tính toán. Thời gian chạy thuật toán FFSM trên bộ dữ liệu 10.000 đồ thị giảm khoảng 25% khi áp dụng các phép toán này.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả đạt được là do việc sử dụng ma trận dấu và dạng chính tắc giúp chuẩn hóa biểu diễn đồ thị, từ đó giảm thiểu số lượng hoán vị cần xét khi kiểm tra đẳng cấu. So với các nghiên cứu trước đây chỉ sử dụng ma trận liền kề thông thường, phương pháp này giảm đáng kể độ phức tạp tính toán. Kết quả thử nghiệm phù hợp với các báo cáo ngành về khai phá dữ liệu đồ thị, đồng thời mở rộng khả năng ứng dụng cho các bộ dữ liệu lớn hơn.

Việc khai phá đồ thị con phổ biến đóng giúp giảm bộ nhớ lưu trữ và tăng tốc độ truy xuất các mẫu đồ thị con, điều này rất quan trọng trong các ứng dụng thực tế như phân tích mạng xã hội, phát hiện cấu trúc cộng đồng, và phân tích mạng sinh học. Cây quyết định compact là một bước tiến quan trọng trong việc tổ chức dữ liệu đồ thị, giúp tăng hiệu quả phân lớp và kiểm tra đẳng cấu.

Các biểu đồ thời gian chạy thuật toán theo kích thước đồ thị và ngưỡng minsup, cùng bảng tổng hợp số lượng đồ thị con phổ biến tìm được, sẽ minh họa rõ ràng các phát hiện trên, giúp người đọc dễ dàng đánh giá hiệu quả của các phương pháp đề xuất.

Đề xuất và khuyến nghị

1. Phát triển thuật toán song song và phân tán: Để xử lý các bộ dữ liệu đồ thị có kích thước lớn hơn 100.000 đồ thị, cần nghiên cứu và triển khai các thuật toán kiểm tra đẳng cấu và khai phá đồ thị con phổ biến trên môi trường tính toán song song hoặc phân tán, nhằm giảm thời gian xử lý xuống mức chấp nhận được.

2. Tối ưu hóa cấu trúc dữ liệu cây quyết định: Nâng cao khả năng mở rộng của cây quyết định bằng cách áp dụng các kỹ thuật nén dữ liệu và cấu trúc cây động, giúp giảm bộ nhớ sử dụng và tăng tốc độ truy cập trong quá trình phân lớp ma trận liền kề.

3. Mở rộng ứng dụng cho đồ thị có trọng số và đồ thị có hướng: Hiện tại nghiên cứu tập trung vào đồ thị vô hướng, không trọng số. Cần phát triển các thuật toán tương tự cho các loại đồ thị phức tạp hơn, nhằm đáp ứng nhu cầu khai phá dữ liệu trong các lĩnh vực như mạng giao thông, mạng truyền thông, và phân tích tài chính.

4. Xây dựng bộ công cụ phần mềm khai phá dữ liệu đồ thị: Đề xuất phát triển một bộ công cụ phần mềm tích hợp các thuật toán kiểm tra đẳng cấu và khai phá đồ thị con phổ biến, có giao diện thân thiện, hỗ trợ người dùng trong nghiên cứu và ứng dụng thực tế, với khả năng tùy chỉnh tham số và trực quan hóa kết quả.

Mỗi giải pháp nên được thực hiện trong vòng 1-2 năm, phối hợp giữa các viện nghiên cứu và doanh nghiệp công nghệ, nhằm thúc đẩy ứng dụng rộng rãi và nâng cao giá trị khoa học của lĩnh vực khai phá dữ liệu đồ thị.

Đối tượng nên tham khảo luận văn

1. Nghiên cứu sinh và học viên cao học ngành Khoa học Máy tính, Công nghệ Thông tin: Luận văn cung cấp nền tảng lý thuyết và thuật toán chuyên sâu về khai phá dữ liệu đồ thị, hỗ trợ nghiên cứu và phát triển đề tài liên quan.

2. Chuyên gia và kỹ sư phát triển phần mềm khai phá dữ liệu: Các thuật toán và phương pháp được trình bày giúp cải thiện hiệu suất và độ chính xác trong các ứng dụng khai phá dữ liệu đồ thị thực tế.

3. Nhà phân tích dữ liệu và nhà khoa học dữ liệu trong lĩnh vực mạng xã hội, sinh học, hóa học: Luận văn cung cấp công cụ và kỹ thuật để phát hiện các cấu trúc mạng phức tạp, hỗ trợ phân tích và dự báo.

4. Giảng viên và nhà quản lý đào tạo: Tài liệu có thể được sử dụng làm tài liệu tham khảo giảng dạy hoặc xây dựng chương trình đào tạo chuyên sâu về khai phá dữ liệu đồ thị.

Mỗi nhóm đối tượng sẽ nhận được lợi ích cụ thể như nâng cao kiến thức chuyên môn, cải thiện hiệu quả công việc, hoặc phát triển chương trình đào tạo phù hợp với xu hướng nghiên cứu hiện đại.

Câu hỏi thường gặp

1. Bài toán đẳng cấu đồ thị là gì và tại sao nó quan trọng?
   Bài toán đẳng cấu đồ thị xác định xem hai đồ thị có cấu trúc giống nhau về mặt kết nối hay không. Đây là bước cơ bản để phát hiện các mẫu đồ thị con phổ biến và ứng dụng trong phân tích mạng xã hội, sinh học. Ví dụ, phát hiện protein tương tự trong mạng tương tác sinh học dựa trên đẳng cấu đồ thị.

2. Thuật toán FFSM có ưu điểm gì so với các thuật toán khai phá đồ thị con khác?
   FFSM tối ưu hóa việc khai phá đồ thị con phổ biến bằng cách chỉ liệt kê các đồ thị con thường xuyên đóng, giảm thiểu số lượng đồ thị con cần lưu trữ và tính toán. Điều này giúp tiết kiệm bộ nhớ và tăng tốc độ xử lý trên bộ dữ liệu lớn.

3. Cây quyết định giúp gì trong việc kiểm tra đẳng cấu đồ thị con?
   Cây quyết định tổ chức các hoán vị ma trận liền kề thành cấu trúc phân cấp, giúp phân lớp và loại bỏ nhanh các trường hợp không đẳng cấu, từ đó giảm số phép so sánh và tăng hiệu quả kiểm tra.

4. Phép kết nối N-Join và mở rộng N-Extension hoạt động như thế nào?
   Hai phép toán này giúp sinh các đồ thị con ứng viên bằng cách kết nối hoặc mở rộng các đồ thị con phổ biến hiện có, giảm thiểu trùng lặp và tăng hiệu quả khai phá. Ví dụ, N-Join ghép hai ma trận liền kề có ma trận con cực đại chung để tạo đồ thị con mới.

5. Làm thế nào để áp dụng các thuật toán này vào dữ liệu thực tế?
   Cần chuẩn bị dữ liệu đồ thị phù hợp, cài đặt thuật toán trên môi trường tính toán đủ mạnh, và điều chỉnh tham số như ngưỡng độ hỗ trợ tối thiểu. Ví dụ, trong phân tích mạng xã hội, có thể áp dụng để phát hiện các nhóm cộng đồng hoặc mẫu tương tác phổ biến.

Kết luận

• Luận văn đã phát triển và đánh giá thành công các thuật toán kiểm tra đẳng cấu đồ thị và khai phá đồ thị con phổ biến với độ phức tạp đa thức, phù hợp cho các bộ dữ liệu lớn.
• Việc sử dụng ma trận dấu và dạng chính tắc giúp chuẩn hóa biểu diễn đồ thị, giảm thiểu hoán vị cần xét và tăng hiệu quả tính toán.
• Thuật toán FFSM và cây quyết định compact là những đóng góp quan trọng giúp giảm thời gian xử lý và bộ nhớ lưu trữ trong khai phá dữ liệu đồ thị.
• Các phép toán N-Join và N-Extension tối ưu hóa quá trình sinh đồ thị con ứng viên, nâng cao hiệu quả khai phá đồ thị con phổ biến.
• Hướng phát triển tiếp theo là mở rộng thuật toán cho đồ thị có trọng số, đồ thị có hướng, và triển khai trên môi trường tính toán phân tán để xử lý dữ liệu quy mô lớn hơn.

Để tiếp tục nghiên cứu và ứng dụng, độc giả được khuyến khích triển khai các thuật toán trong môi trường thực tế, đồng thời phát triển các công cụ phần mềm hỗ trợ khai phá dữ liệu đồ thị. Liên hệ với tác giả hoặc viện nghiên cứu để nhận tài liệu và hỗ trợ kỹ thuật.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: KHAI PHÁ ĐỒ THỊ Khai phá đồ thị (Graph Mining) là tập hợp các công cụ và kỹ thuật được sử dụng để (i) phân tích các thuộc tính của đồ thị trong thế giới thực, (ii) dự đoán cấu trúc và tính chất của đồ thị đã cho có thể ảnh hưởng đến một số ứng dụng và (iii) phát triển các mô hình có thể tạo ra biểu đồ thực tế phù hợp với các mô hình được tìm thấy trong các biểu đồ quan tâm trong thế giới thực. Chương này trình bày những khái niệm cơ sở về đồ thị, các dạng biểu diễn cấu trúc, dạng chính tắc của đồ thị và các kỹ thuật khai phá dữ liệu đồ thị. Cấu trúc đồ thị Một đồ thị (Graph) là một dạng biểu diễn hình ảnh của một tập các đỉnh (nút) đại diện cho các đối tượng dữ liệu (thực thể), trong đó các cặp đối tượng được kết nối bởi các cạnh (cung) thể hiện mối quan hệ giữa chúng [8]. Cho trước đồ thị G = (V, E), trong đó V là tập các đỉnh và E  V × V là tập các cạnh.

Đường đi có độ dài n đi từ nút v đến w là dãy các cạnh (v0, v1), (v1, v2), …, (vn-1, vn), trong đó v0 = v, vn = w và (vi, vi+1)  E. Đường đi đơn là đường đi không đi qua một đỉnh nào quá một lần. Hiển nhiên, đường đi ngắn nhất đi từ đỉnh s đến đỉnh t là đường đi đơn có độ dài (số cạnh) ít nhất trong số các đường đi giữa hai đỉnh. Hai cạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng với một cặp đỉnh.

Một cạnh (v, w) của đồ thị G được gọi là khuyên (loop) nếu v = w. Đồ thị không có các cạnh bội được gọi là đơn đồ thị, ngược lại gọi là đa đồ thị. Hai đỉnh u và v trong đồ thị G được gọi là liền kề nếu (u, v)  E, hoặc (v, u)  E. Nếu e = (u, v) thì e gọi là cạnh liên thuộc với các đỉnh u và v.

Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh e. Một đồ thị là vô hướng nếu E là tập các cạnh không có thứ tự, ngược lại là đồ thị có hướng. Đồ thị có trọng số nếu trên mỗi cạnh được gắn với một trọng số, ngược lại là đồ thị không trọng số, hay nói chính xác hơn là các cạnh của đồ thị đều có trọng số là 1.

Đa đồ thị vô hướng. Đa đồ thị vô hướng. e là khuyên cạnh song song c. Không phải đơn đồ thị có e.

Không phải đơn đồ thị có hướng do có các cặp cạnh hướng do có cạnh nối một nối cùng một cặp đỉnh. đỉnh với chính nó.1 Các đồ thị vô hướng và có hướng Trong luận văn này chúng ta chỉ những đơn đồ thị vô hướng, không trọng số, gọi tắt là đồ thị. Một đồ thị (vô hướng) được gọi là liên thông nếu luôn có đường đi đơn giữa mọi cặp đỉnh phân biệt của đồ thị. Giữa mọi cặp đỉnh phân biệt của một đồ thị liên thông luôn có đường đi đơn [16].

Các đồ thị con liên thông rời nhau, được gọi là các thành phần liên thông của đồ thị đang xét. Như vậy, một đồ thị là liên thông khi và chỉ khi nó chỉ có một thành phần liên thông. Bậc của đỉnh v trong đồ thị G, ký hiệu deg(v), là số các cạnh liên thuộc với nó. Đỉnh v được gọi là đỉnh treo nếu deg(v) = 1 và gọi là đỉnh cô lập nếu deg(v) = 0.

Bậc của đỉnh là số các đỉnh liền kề với đỉnh đó. Tổng số bậc của các đỉnh trong đồ thị G bằng hai lần số cạnh [16]. Mọi đơn đồ thị n đỉnh (n ≥ 2) có tổng bậc của hai đỉnh tuỳ ý không nhỏ hơn n đều là đồ thị liên thông [16]. Nếu một đồ thị có đúng hai đỉnh bậc lẻ thì hai đỉnh này phải liên thông, tức là có một đường đi nối chúng [16].

Hợp của hai đơn đồ thị G1 = (V1, E1) và G2 = (V2, E2) là một đơn đồ thị G có tập các đỉnh là V1 V2 và tập các cạnh là E1  E2, ký hiệu là G = G1 G2. Hợp của hai đồ thị Định nghĩa 1. Đơn đồ thị G’=(V, E’) được gọi là đồ thị bù của đơn đồ thị G = (V, E) nếu G và G’ không có cạnh chung nào (E  E’= ) và G  G’là đồ thị đầy đủ, đồ thị có các cạnh nối hai đỉnh bất kỳ. Dễ thấy rằng nếu G’ là bù của G thì G cũng là bù của G’.

Khi đó ta nói hai đồ thị là bù nhau. G1’ là phần bù của G1 Định nghĩa 1. Cho trước hai đồ thị G1 = (V1, E1) và G2 = (V2, E2), ta nói G1 là đồ thị con của G2 (G2 là đồ thị cha của G) khi và chỉ khi V1 ⊆ V2 và E1 ⊆ E2. Trường hợp V1 = V2 ta nói G1 là đồ thị con bao trùm G2.

Cho trước đồ thị G = (V, E), với mỗi S  V, đồ thị con cảm sinh (induced) bởi S trong đồ thị, ký hiệu là GS = (S, E  SS). Như vậy, đồ thị G1 = (V1, E1) là đồ thị con cảm sinh của G2 = (V2, E2), nếu V1 ⊆ V2 , E1 ⊆ E2 và với mọi cạnh (u, v)  E1 thì u, v  V1. Đồ thị G được gọi là đầy đủ (clique) nếu mọi cặp đỉnh đều liên thuộc với nhau, nghĩa là  vi, vj  V, i  j thì (vi, vj)  E. Các dạng biểu diễn cấu trúc dữ liệu đồ thị Cách biểu diễn đồ thị trực quan nhất là hình vẽ, nhưng không thể lưu trữ trực tiếp các hình vẽ đồ thị trong máy tính.

Có nhiều cách khác nhau để lưu trữ (biểu diễn) các đồ thị trong máy tính [8, 17]. Sử dụng cấu trúc dữ liệu (cách biểu diễn) nào thì tùy theo cấu trúc của đồ thị và thuật toán dùng để thao tác trên đồ thị đó. Trong lý thuyết, người ta thường sử dụng hai cấu trúc chính là danh sách và cấu trúc mảng (ma trận). Trong các ứng dụng cụ thể, cấu trúc tốt nhất có thể là kết hợp của cả hai.

Người ta hay dùng các cấu trúc danh sách cho các đồ thị thưa (sparse graph), do chúng đòi hỏi ít bộ nhớ. Trong khi đó, các cấu trúc ma trận cho phép truy nhập dữ liệu nhanh hơn, nhưng lại cần lượng bộ nhớ lớn nếu đồ thị có kích thước lớn [1, 4]. Danh sách liên thuộc Danh sách liên thuộc (Incidence list) - Mỗi đỉnh có một danh sách các cạnh nối với đỉnh đó. Các cạnh của đồ thị được có thể được lưu trong một danh sách riêng (có thể cài đặt bằng cấu trúc mảng (array) hoặc danh sách liên kết (linked list)), trong đó mỗi phần tử ghi thông tin về một cạnh, bao gồm: cặp đỉnh mà cạnh đó nối (cặp này sẽ có thứ tự nếu đồ thị có hướng), trọng số và các dữ liệu khác.

Danh sách liên thuộc của mỗi đỉnh sẽ chiếu tới vị trí của các cạnh tương ứng tại danh sách cạnh này. Cho đồ thị vô hướng c 7 Hình 1. Danh sách liên thuộc của đồ thị 1. Danh sách liền kề Danh sách liền kề (Adjacency List) - Mỗi đỉnh của đồ thị có một danh sách các đỉnh kề nó (nghĩa là có một cạnh nối từ đỉnh này đến mỗi đỉnh đó).

Trong đồ thị vô hướng, cấu trúc này có thể gây trùng lặp. Chẳng hạn nếu đỉnh 3 nằm trong danh sách của đỉnh 2 thì đỉnh 2 cũng phải có trong danh sách của đỉnh 3. Lập trình viên có thể chọn cách sử dụng phần không gian thừa, hoặc có thể liệt kê các quan hệ kề cạnh chỉ một lần. Biểu diễn dữ liệu này thuận lợi cho việc từ một đỉnh duy nhất tìm mọi đỉnh được nối với nó, do các đỉnh này đã được liệt kê tường minh.

Danh sách liền kề. Với mỗi đỉnh i của đồ thị chúng ta lưu trữ danh sách các đỉnh kề với nó, ký hiệu là List (i), List(i) = { j V: (i, j)  E hoặc (j, i)  E }, Với cách biểu diễn này, mỗi đỉnh i của đồ thị, tương ứng với một danh sách tất cả các đỉnh kề với nó và được ký hiệu là List(i). Để biểu diễn List(i), ta có thể dùng các kiểu dữ liệu kiểu tập hợp, mảng hoặc danh sách liên kết. Cho trước đồ thị vô hướng Hình 1.

Đồ thị vô hướng c 8 Danh sách liền kề của đồ thị trên theo cấu trúc danh sách liên kết là: Hình 1. Biểu diễn danh sách liền kề của đồ thị hình 1.5 Đồ thị có trọng số (có các trọng số trên các cạnh), được gắn nhãn thường biểu diễn theo ma trận liền kề. Ma trận liên thuộc Ma trận liên thuộc (Incidence matrix) - Đồ thị được biểu diễn bằng một ma trận [bij] kích thước n × m, trong đó n là số đỉnh và m là số cạnh, trong đó bi,j = 1 nếu đỉnh vi liên thuộc (là một trong 2 đầu) với cạnh ej và bằng 0 trong các trường hợp khác. Cho đồ thị vô hướng G = (V, E), với v1, v2, ., vn là các đỉnh và e1, e2, ., em là các cạnh của G.

Ma trận liên thuộc của G theo thứ tự trên của V và E là ma trận AG = {aij | i = 1.m}, trong đó aij là bằng 1 nếu cạnh ej nối với đỉnh vi và bằng 0 nếu cạnh ej không nối với đỉnh vi. Ma trận liên thuộc theo thứ tự các đỉnh v1, v2, v3, v4, v5 (xếp theo cột) và các cạnh e1, e2, e3, e4, e5, e6 (xếp theo hàng) là: Hình 1. Ma trận liên thuộc của đồ thị vô hướng c 9 1. Ma trận liền kề Ma trận liền kề (adjacency matrix) một ma trận n × n, trong đó n là số đỉnh của đồ thị.

Cấu trúc này tạo thuận lợi cho việc tìm các đồ thị con và để đảo các đồ thị. Giả sử G = (V, E) là đồ thị có n đỉnh (|V | = n), V = {v1, v2, …, vn}. Ma trận liền kề (adjacency matrix) của đồ thị G ứng với thứ tự các đỉnh v1, v2,., vn là ma trận AG = {aij | i, j = 1.n}, trong đó ai,j = 1 nếu (vi, vj)  E, ngược lại ai,j = 0. Từ định nghĩa suy ra ma trận liền kề biểu diễn đồ thị vô hướng là ma trận đối xứng qua đường chéo chính, nghĩa là aij = aji, trong khi ma trận liền kề của một đồ thị có hướng không có tính đối xứng.