• Home
  • All about Japan
  • Đồ thị tri thức (Knowledge graph) và các ứng dụng của đồ thị tri thức

Đồ thị tri thức (Knowledge graph) và các ứng dụng của đồ thị tri thức


Bài viết chủ đề Knowledge Graph (Đồ thị tri thức) dựa theo các chia sẻ của Tiến Sĩ Hiển Nguyễn tại chương trình Technical Event số thứ #04 do Gambaru tổ chức. Một số nội dung trong bài được rút gọn và không đề cập chi tiết như tại buổi chia sẻ, bạn có thể tham khảo thêm bằng việc xem video ở cuối bài viết.





Một số khái niệm trên đồ thị





Đồ thị là 1 bộ gồm 2 tập V và E. V là tập các đỉnh của đồ thị và E là tập các cạnh của đồ thị.





1 Đồ thị sẽ gồm tập đỉnh và tập cạnh.





Thông thường trong ứng dụng thực tế, các đồ thị sẽ tập trung vào các đồ thị hữu hạn (hữu hạn đỉnh)





Ví dụ 1 đồ thị cơ bản





Đồ thị cơ bản
Đồ thị cơ bản




Ứng dụng của đồ thị





Đồ thị có thể được dùng để:





  • Biểu diễn ngữ nghĩa của văn bản
  • Biểu diễn các biểu thức toán học
  • Biểu diễn thông tin Social network
  • Người dùng, các mối quan hệ của người dùng




Ứng dụng của đồ thị
Ứng dụng của đồ thị




Đồ thị có hướng và vô hướng





Đồ thị có hướng: Phân biệt thứ tự các đỉnh trong cạnh





Đồ thị có hướng
Đồ thị có hướng




Đồ thị vô hướng: Không phân biệt thứ tự các đỉnh





Đồ thị vô hướng
Đồ thị vô hướng




Đồ thị có trọng số: Trên đồ thị, ngoài tập đỉnh và tập cạnh thì bổ sung 1 ánh xạ đi từ tập cạnh đến mặt số thực và khi đó ánh xạ được gọi là trọng số của 1 cạnh.





Kề nhau





2 cạnh kề nhau nếu có chung 1 đỉnh





Kề nhau
Kề nhau




Bậc của đỉnh





Số cạnh được nối đến 1 đỉnh nào đó.





Với đồ thị có hướng thì có cạnh vào và cạnh ra





Các loại đồ thị





Đồ thị đơn





Đồ thị đơn là đồ thị mà 2 đỉnh bất kỳ được nối với nhau bởi không quá 1 cạnh và không có khuyên (đi 1 vòng lại chính nó)





Đa đồ thị là nếu có ít nhất 1 cặp đỉnh được nối với nhau bởi 2 cạnh trở lên và không có khuyên





Trong nghiên cứu, người ta thường hay quy về dạng đồ thị đơn để dễ nghiên cứu, biểu diễn





Đồ thị đủ





Là đồ thị có bậc n và giữa 2 đỉnh bất kỳ, đều có đỉnh





Đồ thị đủ
Đồ thị đủ




Đồ thị lưỡng phân





Là đồ thị có tập đỉnh thành V1, và V2. 2 tập này sẽ nối 1 đỉnh trong V1 với 1 đỉnh trong V2. Giữa các đỉnh trong 1 tập không nối với nhau.





Đồ thị lưỡng phân
Đồ thị lưỡng phân




Đồ thị lưỡng phân
Đồ thị lưỡng phân




Đồ thị con





Được xây dựng từ việc bỏ đi 1 số đỉnh trong đồ thị ban đầu và bỏ đi 1 số cạnh.





Đồ thị con
Đồ thị con




Đồ thị bù





Là đồ thị ‘adapt’ vào đồ thị đang có để trở thành 1 đồ thị đầy đủ.





Đồ thị bù
Đồ thị bù




Các phương pháp biểu diễn đồ thị





Biểu diễn hình học





Biểu diễn bằng hình vẽ, biểu diễn trên mặt phẳng





Biểu diễn hình học
Biểu diễn hình học




Biểu diễn bằng ma trận liên kết đỉnh cạnh





Biểu diễn bằng 1 ma trận với m dòng và n cột





Ma trận liên kết đỉnh cạnh
Ma trận liên kết đỉnh cạnh




Ma trận liên kết đỉnh cạnh
Ma trận liên kết đỉnh cạnh




Biểu diễn bằng ma trận kề





Biểu diễn bằng ma trận vuông





Biểu diễn bằng ma trận vuông
Biểu diễn bằng ma trận vuông




Biểu diễn bằng danh sách kề





Đẳng cấu đồ thị





2 đồ thị được gọi là đẳng cấu nếu có 1 phép tương ứng 1-1 giữa tập đỉnh và phép tương ứng 1-1 giữa tập cạnh. 





Đẳng cấu đồ thị
Đẳng cấu đồ thị




Một số bài toán trên đồ thị





Duyệt đồ thị





  • Duyệt đồ thị theo chiều sâu
  • Duyệt đồ thị theo chiều rộng




Tìm đường ngắn nhất





  • Thuật toán Dijkstra
  • Thuật toán Ford-Bellman
  • Thuật toán Floyd
  • Thuật giải sử dụng các heuristic




Hãy xem video dưới bài viết để nghe Thầy Hiển diễn giải chính xác các bài toán bên trên nhé.





Ứng dụng biểu diễn tri thức dạng quan hệ





Biểu diễn tri thức dạng quan hệ
Biểu diễn tri thức dạng quan hệ




Tri thức con người có rất nhiều dạng khác nhau. Vậy làm thế nào để đưa được tri thức con người lên trên máy tính để thực hiện các hoạt động suy luận, tìm kiếm.





Để làm việc đó, ta phải tích cấu trúc tri thức của con người có những thành phần nào. 





  • Khái niệm (tập C)
  • Mối quan hệ giữa các khái niệm (tập R)
  • Các luật suy diễn trong tri thức (Rules)




Cấu trúc mô hình tri thức quan hệ
Cấu trúc mô hình tri thức quan hệ




Rela model và đồ thị tri thức
Rela model và đồ thị tri thức




Biểu diễn các khái niệm, đối tượng trên mô hình thông qua các quan hệ đã được định nghĩa. Đồ thị bên trên còn thiếu trong việc biểu diễn quy tắc suy diễn (rules)





Ứng dụng hệ thống tra cứu kiến thức môn học
Ứng dụng hệ thống tra cứu kiến thức môn học




Ứng dụng biểu diễn thông tin trên mxh





Làm thế nào đánh giá sự ảnh hưởng của một người trên MXH để phục vụ cho các chiến dịch influencer marketing?





Mô hình người ảnh hưởng
Mô hình người ảnh hưởng




Mô hình biểu diễn thông tin MXH
Mô hình biểu diễn thông tin MXH




Biểu diễn quan hệ giữa người dùng
Biểu diễn quan hệ giữa người dùng




Hệ thống ADVO
Hệ thống ADVO




Bạn có thể xem chi tiết các kiến thức trong bài viết thông qua video từ buổi chia sẻ:











Nguồn: Gambaru.io