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
Ứ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
Đồ 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ị vô hướng: Không phân biệt thứ tự các đỉnh
Đồ 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
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ị 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ị 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ị bù
Là đồ thị ‘adapt’ vào đồ thị đang có để trở thành 1 đồ thị đầy đủ.
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 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
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 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.
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ệ
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)
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 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?
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