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.
Đồ 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ó thể được dù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.
2 cạnh kề nhau nếu có chung 1 đỉ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
Đồ 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
Là đồ thị có bậc n và giữa 2 đỉnh bất kỳ, đều có đỉnh
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.
Được xây dựng từ việc bỏ đi 1 số đỉnh trong đồ thị ban đầu và bỏ đi 1 số cạnh.
Là đồ thị ‘adapt’ vào đồ thị đang có để trở thành 1 đồ thị đầy đủ.
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.
Duyệt đồ thị
Tìm đường ngắn nhất
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é.
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.
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)
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