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 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?

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

undefined undefined

1 Result do-thi-tri-thuc found