Chương 1. Tổng quan về các phương pháp biểu diễn đồ thị và ứng dụng Chương này trình bày sơ lược về khái niệm đồ thị và tập trung tìm hiểu tổng quan về một số phương pháp biểu diễn đồ thị phổ biến, đồng thời nêu lên một số ứng dụng của việc biểu diễn đồ thị trong thực tế. Biểu diễn mạng đồ thị hai phía bằng phương pháp nhúng đỉnh. Trong chương này, đề tài khái quát bài toán biểu diễn mạng đồ thị hai phía và trọng tâm tìm hiểu cụ thể một phương pháp nhúng đỉnh mạng đồ thị hai phía với kỹ thuật bước đi ngẫu nhiên và tối ưu hóa đồng thời các thành phần nhằm bảo toàn được đặc trưng các quan hệ trực tiếp và quan hệ gián tiếp thông qua bắc cầu các đỉnh của mạng đồ thị hai phía.
Hệ thống khuyến nghị và các độ đo đánh giá hệ thống khuyến nghị. Chương này đề tài sẽ trình bày những vấn đề tổng quan về hệ thống khuyến nghị, phân tích các hướng tiếp cận phổ biến trong xây dựng hệ thống khuyến nghị cũng như tìm hiểu các phương pháp đánh giá hiệu quả của một hệ thống khuyến nghị. Từ đó lựa chọn mô hình và độ đo cho hệ thống khuyến nghị dự kiến xây dựng thực tế. Xây dựng hệ thống khuyến nghị bằng phương pháp nhúng đỉnh mạng đồ thị hai phía áp dụng vào thực tế.
4 Nội dung chương này là đóng góp chính của đề tài, trong đó tập trung trình bày về cách thức thu thập và xử lý dữ liệu thực tế để thiết lập một mạng đồ thị hai phía, từ đó ứng dụng phương pháp nhúng đỉnh mạng đồ thị hai phía từ thực tế để xây dựng một hệ thống khuyến nghị, áp dụng cho hoạt động sản xuất của một doanh nghiệp. Chương này cũng đánh giá hiệu quả của hệ thống khuyến nghị được xây dựng qua các độ đo và so sánh với các hệ thống khuyến nghị thông thường khác. Cuối cùng là phần kết luận tổng hợp các kết quả nghiên cứu đã đạt được, các đóng góp của đề tài, hướng mở rộng nghiên cứu và phát triển đề tài. TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP BIỂU DIỄN ĐỒ THỊ VÀ ỨNG DỤNG Học máy trong lĩnh vực đồ thị là một trong những công việc quan trọng nhưng phổ biến, với các ứng dụng trải rộng từ nghiên cứu phân tử, điều chế thuốc cho đến giới thiệu bạn bè trong mạng xã hội.
Thách thức chính đối với học máy về đồ thị là tìm một phương pháp để biểu diễn, hoặc mã hóa, cấu trúc đồ thị sao cho có thể dễ dàng được khai phá bởi các mô hình học máy. Phần này giới thiệu tổng quan về các phương pháp biểu diễn đồ thị và các ứng dụng của đồ thị đối với học máy. Tổng quan về đồ thị 1. Các khái niệm về đồ thị Đồ thị là một cấu trúc dữ liệu phổ biến, được sử dụng rất nhiều trong khoa học máy tính và các lĩnh vực liên quan.
Hệ thống giao thông, quy hoạch đô thị, cấu trúc phân tử, vật lý y sinh, mạng xã hội hay hệ thống khuyến nghị thương mại điện tử v.v… tất cả đều có thể sẵn sàng được mô hình hóa thành đồ thị và giữ nguyên các đặc tính tương tác giữa các phần tử độc lập trong hệ thống. Do tính phổ biến của mình, đồ thị là xương sống của vô số hệ thống trong thực tế, cho phép các thông tin về sự tương tác, quan hệ giữa các thực thế được lưu trữ và truy xuất một cách hiệu quả. Một đồ thị 𝒢 được đặc trưng bởi một tập hợp 𝑉 với N đỉnh và một tập hợp 𝐸 gồm các cạnh nối giữa các cặp đỉnh. Phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị.
Một số định nghĩa và ký hiệu về đồ thị như sau: - Đơn đồ thị vô hướng 𝒢 = (𝑉, 𝐸) bao gồm 𝑉 là tập các đỉnh khác rỗng, và 𝐸 là tập các cặp không có thứ tự gồm hai phần tử khác nhau của 𝑉 gọi là các cạnh. 6 - Đa đồ thị vô hướng 𝒢 = (𝑉, 𝐸) bao gồm 𝑉 là tập các đỉnh khác rỗng, và 𝐸 là tập các cặp không có thứ tự gồm hai phần tử khác nhau của 𝑉 gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp (bội hay song song) nếu chúng cùng tương ứng với một cặp đỉnh. Mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp đỉnh nào đó.
Đơn đồ thị vô hướng và đa đồ thị vô hướng. - Đồ thị có hướng 𝒢 = (𝑉, 𝐸) bao gồm 𝑉 là tập các đỉnh khác rỗng và 𝐸 là tập các cặp có thứ tự gồm hai phần tử khác nhau của 𝑉 gọi là các cung. Tương tự có đơn đồ thị có hướng và đa đồ thị có hướng. Đơn đồ thị có hướng - Hai đỉnh 𝑢 và 𝑣 trong đồ thị vô hướng 𝒢 = (𝑉, 𝐸) được gọi là liền kề nếu (𝑢, 𝑣) ∈ 𝐸.
Nếu 𝑒 = (𝑢, 𝑣) thì 𝑒 gọi là cạnh liên thuộc với các đỉnh 7 𝑢 và 𝑣. Cạnh 𝑒 cũng được gọi là cạnh nối các đỉnh 𝑢 và 𝑣. Các đỉnh 𝑢 và 𝑣 gọi là các điểm đầu mút của cạnh 𝑒. - Bậc của đỉnh 𝑣 trong đồ thị 𝒢 = (𝑉, 𝐸), ký hiệu deg(𝑣), là tổng số các cạnh liên thuộc với nó.
- Đường đi P độ dài n từ đỉnh 𝑢 đến đỉnh 𝑣, với n là số nguyên dương, trên đồ thị 𝒢 = (𝑉, 𝐸) là dãy P: 𝑥0 , 𝑥1 , … , 𝑥𝑛−1 , 𝑥𝑛 , trong đó 𝑢 = 𝑥0 , 𝑣 = 𝑥𝑛 , 𝑥𝑖 ∈ 𝑉, 𝑖 = 0, 1, 2, … , 𝑛 − 1, 𝑛. Đỉnh 𝑢 gọi là đỉnh đầu, đỉnh 𝑣 gọi là đỉnh cuối của đường đi. - Đường đi có đỉnh đầu trùng với đỉnh cuối được gọi là 1 chu trình. Một đồ thị thường được mô tả bởi một ma trận kề 𝐗 bậc N x N, với 𝐗 𝑖𝑗 là giá trị gắn liền với cạnh giữa cặp đỉnh (i, j).
Giá trị này bằng 0 nếu không có mối liên kết giữa các đỉnh. Với đồ thị của cây nhị phân, ma trận X là ma trận nhị phân và 𝐗 𝑖𝑗 = 1 thể hiện là hai đỉnh được liên kết với nhau. Đồ thị hai phía Đồ thị hai phía (bipartite graph) là một đồ thị có các đỉnh gồm hai tập độc lập 𝑈 và 𝑉 không giao nhau, sao cho mỗi cạnh liên kết một đỉnh thuộc 𝑈 với một đỉnh thuộc 𝑉. Đồ thị hai phía là một đồ thị không chứa chu trình có độ dài lẻ.
Đồ thị hai phía thường được viết dưới dạng 𝒢 = (𝑈, 𝑉, 𝐸) với với hai tập đỉnh 𝑈 và 𝑉, và 𝐸 là tập các cạnh của đồ thị. Đồ thị hai phía 8 1. Đồ thị đối với học máy Đồ thị không chỉ hữu dụng như là một kho chứa thông tin có cấu trúc, chúng còn đóng một vai trò quan trọng trong học máy hiện đại. Nhiều ứng dụng học máy tìm kiếm các phương pháp để có thể đưa ra dự đoán hoặc khám phá ra các hình mẫu mới bằng cách sử dụng dữ liệu cấu trúc đồ thị để trích xuất thông tin đặc trưng.
Ví dụ như để xác định vai trò của một protein trong đồ thị tương tác sinh học, tìm ra một hiệu quả trị liệu mới với các loại thuốc hiện hữu, đoán vai trò của một cá nhân trong một mạng cộng tác, giới thiệu những người bạn mới cho một người dùng trong một mạng xã hội, đây là các mạng lưới, hệ thống mà cấu trúc của nó có thể được biểu diễn dưới dạng đồ thị. Mạng cộng đồng với cấu trúc gồm ba nhóm riêng biệt. Các đỉnh lân cận trong cùng 1 nhóm sẽ có xu hướng liên kết chặt với nhau hơn so với các đỉnh thuộc nhóm khác. Vấn đề trọng tâm của học máy về đồ thị là tìm ra một cách thức để kết hợp thông tin về cấu trúc đồ thị vào trong một mô hình học máy.
Ví dụ trường hợp dự đoán liên kết trong một mạng xã hội, ta có thể muốn mã hóa các thuộc tính theo cặp giữa các nút đồ thị, như là độ bền chặt của mối quan hệ hoặc số lượng bạn chung giữa những người dùng. Hoặc đối với trường hợp phân loại nút, ta có thể 9 muốn tích hợp thông tin về vị trí toàn cục của nút hoặc cấu trúc của vùng lân cận của nút trong đồ thị (Hình 1. Xét từ khía cạnh học máy, thách thức ở đây chính là không có một cách đơn giản nào để mã hóa thông tin có số chiều lớn của cấu trúc đồ thị vào thành một vector đặc trưng. Để trích xuất thông tin cấu trúc từ các đồ thị, các hướng tiếp cận học máy truyền thống thường dựa trên thống kê tóm tắt (ví dụ bậc đồ thị hoặc hệ số phân cụm), các hàm lõi, hoặc các đặc trưng được tính toán cẩn thận để đo các cấu trúc lân cận cục bộ [1].
Tuy nhiên các phương pháp này bị giới hạn do các đặc trưng được tính toán thủ công này không linh hoạt, chúng không thích nghi trong quá trình học, và việc thiết kế các đặc trưng này là một quá trình rất mất thời gian và tốn kém. Gần đây đã có rất nhiều hướng tiếp cận để tìm ra cách biểu diễn học máy để mã hóa thông tin cấu trúc của đồ thị. Ý tưởng của hướng tiếp cận này là học một phép ánh xạ để nhúng các đỉnh, hoặc toàn bộ đồ thị, vào một không gian vector ℝ𝑑 có số chiều thấp. Mục tiêu là tối ưu hóa ánh xạ này để các quan hệ hình học trong không gian nhúng phản ánh được cấu trúc của đồ thị gốc.
Sau khi tối ưu hóa không gian nhúng, các dữ liệu nhúng đã được học có thể được sử dụng như là các đặc trưng đầu vào cho các tác vụ học máy sau đó. Sự khác biệt chính giữa hướng tiếp cận học biểu diễn với các phương pháp trước đó là ở cách xử lý vấn đề biểu diễn cấu trúc đồ thị. Các phương pháp truyền thống thực hiện các bước tiền xử lý, dùng các thống kê được tính toán thủ công để trích xuất thông tin cấu trúc. Ngược lại, hướng tiếp cận học biểu diễn xem vấn đề như là một tác vụ học máy, sử dụng cách tiếp cận theo hướng thiên về dữ liệu để học các phép nhúng có thể mã hóa cấu trúc đồ thị.