Luận văn ThS: Khai thác mẫu phổ biến cực đại trong đồ thị đơn bằng phương pháp so sánh gần đúng

141 lượt xem
Share

Luận văn Khai thác mẫu phổ biến cực đại trong đồ thị đơn bằng phương pháp so sánh gần đúng giới thiệu tổng quan về mẫu phổ biến cực đại; khai thác mẫu phổ biến cực đại và thực nghiệm.

Mục lục nội dung

Luận văn ThS: Khai thác mẫu phổ biến cực đại trong đồ thị đơn bằng phương pháp so sánh gần đúng

1. Mở đầu

Khai thác dữ liệu đồ thị đang nhận được sự quan tâm rất lớn vào những năm gần đây bởi vì tính phổ biến của dữ liệu đồ thị đang phát triển rất mạnh và được sử dụng rộng rãi trong các nghành khoa học công nghệ. Bởi vì mẫu đồ thị phổ biến cực đại có ý nghĩa rất quan trọng trong các vấn đề nghiên cứu khoa học nên hiện nay có rất nhiều thuật toán khai thác mẫu phổ biến cực đại. Tuy nhiên kết hợp việc sử dụng phương pháp so sánh gần đúng trong khai thác mẫu phổ biến đang còn rất hạn chế. Luận Văn này sẽ đề xuất thuật toán ImaxAFG cải tiến để khai thác mẫu phổ biến cự đại trong đồ thị đơn sử dụng phương pháp so sánh gần đúng.

2. Nội dung

2.1 Tổng quan

Giới thiệu 

  • Giới thiệu khái quát về sự phát triển của khai thác dữ liệu đồ thị
  • Mục tiêu của đề tài
  • Nội dung nghiên cứu

Tổng quan về mẫu phổ biến cực đại

Khai thác đồ thị trong đồ thị đơn

Khai thác đồ thị sử dụng phương pháp so sánh gần đúng

Kiến trúc, hạ tầng của một hệ thống khai thác dữ liệu đồ thị

2.2 Khai thác mẫu phổ biến cực đại

Tổng quan 

Khái niệm cơ bản và các ký hiệu

Thuât toán ImaxAFG (cải tiến từ thuật toán MaxAFG)

  • Bài toán so sánh độ tương đồng
  • Phương pháp so sánh gần đúng
  • Thuật toán ImaxAFG
  • Độ phức tạp của thuật toán ImaxAFG

Bài toán tìm mẫu phổ biến cực đại trong đồ thị đơn sử dụng phương pháp so sánh gần đúng

2.3 Kết quả thực nghiệm

Giới thiệu 

Kết quả thực nghiệm thuật toán ImaxAFG dựa vào kỹ thuật kiểm tra ”k-fold cross validation” 

So sánh kết quả ImaxAFG và MaxAFG

3. Kết luận

Trong bài Luận Văn này trình bày thuật toán ImaxAFG, một thuật toán khai thác mẫu phổ biến cực đại trong dồ thị đơn sử dụng phương pháp so sánh gần đúng. Bằng việc thừa nhận sự khác nhau về cấu trúc như các đỉnh cũng như các cạnh của đồ thị, giữa mẫu đồ thị phổ biến và các sự biểu diễn của nó, có thể tìm ra được các mẫu phổ biến còn sót bởi các thuật toán không sử dụng phương pháp so sánh gần đúng. Trong một khía cạnh khác, tập trung vào việc khai thác mẫu đồ thị cực đại giúp giảm số lượng mẫu đáng kể, đó là một vấn đề rất quan trọng bởi vì việc sử dụng phương pháp so sánh gần đúng thì số lượng mẫu phổ biến tìm được có thể tăng lên gấp 100 lần so với thuật toán không sử dụng phương pháp so sánh gần đúng.

4. Tài liệu tham khảo

S. Ranu, A. Singh, Graphsig: a scalable approach to mining significant subgraphs in large graph databases, in: IEEE 25th International Conference on Data Engineering, 2009, pp. 844–855

S. Nijssen, J.N. Kok, A quickstart in frequent structure mining can make a difference, in: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’04, ACM, 2004, pp. 647–652

X. Yan, J. Han, gspan: graph-based substructure pattern mining, in: Proceedings of the 2002 IEEE International Conference on Data Mining, ICDM’02, 2002...

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận văn trên ---

141 lượt xem
Share
Ngày:04/09/2020 Chia sẻ bởi:
TẢI VỀ XEM ONLINE

CÓ THỂ BẠN QUAN TÂM