Tài liệu Ứng dụng phương pháp nhúng đỉnh vào đồ thị hai phía để xây dựng hệ thống khuyến nghị

ỦY BAN NHÂN DÂN TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT NGUYỄN XUÂN BÌNH ỨNG DỤNG PHƯƠNG PHÁP NHÚNG ĐỈNH VÀO ĐỒ THỊ HAI PHÍA ĐỂ XÂY DỰNG HỆ THỐNG KHUYẾN NGHỊ LUẬN VĂN THẠC SĨ CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 8 48 01 04 BÌNH DƯƠNG – 2021 ỦY BAN NHÂN DÂN TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT NGUYỄN XUÂN BÌNH ỨNG DỤNG PHƯƠNG PHÁP NHÚNG ĐỈNH VÀO ĐỒ THỊ HAI PHÍA ĐỂ XÂY DỰNG HỆ THỐNG KHUYẾN NGHỊ LUẬN VĂN THẠC SĨ CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 8 48 01 04 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. TRẦN QUANG NGUYÊN BÌNH DƯƠNG – 2021 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi và được sự hướng dẫn khoa học của TS. Trần Quang Nguyên. Các nội dung nghiên cứu, kết quả trong đề tài này là trung thực và chưa công bố dưới bất kỳ hình thức nào trước đây. Những số liệu trong các bảng biểu phục vụ cho việc phân tích, nhận xét, đánh giá được chính tác giả thu thập từ các nguồn khác nhau có ghi rõ trong phần tài liệu tham khảo. Ngoài ra, trong báo cáo còn sử dụng một số nhận xét, đánh giá cũng như số liệu của các tác giả khác, cơ quan tổ chức khác đều có trích dẫn và chú thích nguồn gốc. Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách nhiệm về nội dung báo cáo của mình. Trường Đại học Thủ Dầu Một không liên quan đến những vi phạm tác quyền, bản quyền do tôi gây ra trong quá trình thực hiện (nếu có). Bình Dương, ngày 27 tháng 9 năm 2021 Người thực hiện i LỜI CẢM ƠN Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành nhất đến thầy Trần Quang Nguyên, thầy đã dành nhiều thời gian quí báu hướng dẫn tôi một cách tận tình và khoa học, tạo điều kiện tốt nhất để tôi hoàn thành Luận văn này. Tôi cũng xin trân trọng cảm ơn quý thầy cô Trường Đại học Thủ Dầu Một, đặc biệt là các thầy cô chuyên ngành Hệ thống Thông tin! Các thầy cô đã tận tình hướng dẫn và luôn tạo điều kiện thuận lợi giúp đỡ tôi trong suốt khóa học tại trường. Tôi cũng rất cảm ơn sự giúp đỡ nhiệt tình của bạn bè cùng khóa đã hỗ trợ tôi các kỹ năng thiết thực để hoàn thiện Luận văn hơn. Ngoài ra, với những tư liệu hữu ích để thực hiện luận văn, tôi xin cảm ơn lãnh đạo và đồng nghiệp tại Công ty Truyền tải điện 4 đã ủng hộ và tạo điều kiện giúp tôi thu thập cơ sở dữ liệu để hoàn thành mục tiêu của đề tài. Cuối cùng, tôi muốn gửi lòng biết ơn vô hạn đến gia đình tôi, tất cả mọi người đã luôn động viên, khuyến khích giúp tôi vượt qua những thời điểm khó khăn để tôi có thể hoàn thành tốt chương trình cao học tại trường Đại học Thủ Dầu Một. Tôi xin chúc quý thầy cô, gia đình và bạn bè luôn mạnh khỏe và đạt được nhiều thành công trong cuộc sống! Bình Dương, ngày 27 tháng 9 năm 2021 Người thực hiện ii MỤC LỤC LỜI CAM ĐOAN ................................................................................................... i LỜI CẢM ƠN ........................................................................................................ ii MỤC LỤC ............................................................................................................. iii DANH MỤC CÁC HÌNH ẢNH ........................................................................... vi DANH MỤC CÁC BẢNG BIỂU ........................................................................ vii MỞ ĐẦU ................................................................................................................ 1 1. Lý do chọn đề tài ...................................................................................... 1 2. Mục tiêu nghiên cứu ................................................................................. 2 3. Đối tượng, phạm vi nghiên cứu ................................................................ 2 4. Phương pháp nghiên cứu .......................................................................... 3 5. Đóng góp của đề tài .................................................................................. 3 6. Cấu trúc của đề tài .................................................................................... 4 CHƯƠNG 1. TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP BIỂU DIỄN ĐỒ THỊ VÀ ỨNG DỤNG.................................................................................................... 6 1.1. Tổng quan về đồ thị .................................................................................. 6 1.1.1. Các khái niệm về đồ thị .................................................................. 6 1.1.2. Đồ thị đối với học máy ................................................................... 9 1.2. Biểu diễn đồ thị bằng phép nhúng đỉnh .................................................. 11 1.2.1. Tổng quan về phép nhúng đỉnh đồ thị .......................................... 11 1.2.2. Phương pháp phân tích nhân tử .................................................... 13 1.2.3. Phương pháp bước đi ngẫu nhiên (Random walk) ....................... 15 1.2.4. Các kiến trúc nhúng sâu tổng quát ............................................... 18 iii 1.3. Ứng dụng của việc biểu diễn đồ thị bằng phương pháp nhúng đỉnh ...... 20 1.4. Kết luận................................................................................................... 22 CHƯƠNG 2. BIỂU DIỄN MẠNG ĐỒ THỊ HAI PHÍA BẰNG PHƯƠNG PHÁP NHÚNG ĐỈNH ......................................................................................... 23 2.1. Bài toán biểu diễn mạng đồ thị hai phía ................................................. 23 2.2. Phương pháp nhúng đỉnh đồ thị hai phía đề xuất ................................... 26 2.2.1. Mô hình hóa các quan hệ trực tiếp ............................................... 26 2.2.2. Mô hình hóa các quan hệ gián tiếp bằng bước đi nhẫu nhiên ...... 27 2.2.3. Tối ưu hóa mô hình chung ........................................................... 31 2.3. Kết luận................................................................................................... 32 CHƯƠNG 3. HỆ THỐNG KHUYẾN NGHỊ VÀ CÁC ĐỘ ĐO ĐÁNH GIÁ HỆ THỐNG KHUYẾN NGHỊ ................................................................................... 33 3.1. Tổng quan về bài toán khuyến nghị ....................................................... 33 3.1.1. Khái niệm hệ thống khuyến nghị ................................................. 33 3.1.2. Phát biểu bài toán hệ thống khuyến nghị ..................................... 34 3.1.3. Các hướng tiếp cận xây dựng hệ thống khuyến nghị ................... 36 3.2. Các phương pháp và độ đo đánh giá hệ thống khuyến nghị .................. 41 3.2.1. Phương pháp đánh giá hệ thống khuyến nghị .............................. 41 3.2.2. Đánh giá độ chính xác của dự đoán ............................................. 42 3.2.3. Đánh giá danh sách đề xuất .......................................................... 43 3.3. Kết luận................................................................................................... 47 CHƯƠNG 4. 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Ế ................................................................................................... 48 iv 4.1. Giới thiệu nguồn dữ liệu và sự cần thiết xây dựng hệ thống khuyến nghị thực tế tại doanh nghiệp ................................................................................... 48 4.2. Thu thập và xây dựng cơ sở dữ liệu ....................................................... 50 4.3. Thực nghiệm và kết quả ......................................................................... 55 4.3.1. Phương pháp thực nghiệm ............................................................ 55 4.3.2. Kết quả và đánh giá ...................................................................... 56 4.4. Kết luận................................................................................................... 62 KẾT LUẬN .......................................................................................................... 64 1. Kết quả đạt được của đề tài .................................................................... 64 2. Các mặt hạn chế và hướng phát triển của đề tài ..................................... 64 DANH MỤC TÀI LIỆU THAM KHẢO ............................................................. 66 PHỤ LỤC ............................................................................................................. 70 v DANH MỤC CÁC HÌNH ẢNH Hình 1.1. Đơn đồ thị vô hướng và đa đồ thị vô hướng. ......................................... 7 Hình 1.2. Đơn đồ thị có hướng .............................................................................. 7 Hình 1.3. Đồ thị hai phía ........................................................................................ 8 Hình 1.4. 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. ............................................................................................................. 9 Hình 1.5. Cách thức mã hóa - giải mã của phép nhúng đỉnh ............................... 11 Hình 1.6. Thực hiện các bước đi ngẫu nhiên để thống kê việc đồng xuất hiện giữa các cặp đỉnh .......................................................................................................... 15 Hình 1.7. Cách thức hoạt động của các tham số p và q trong bước đi ngẫu nhiên của phương pháp node2vec .................................................................................. 17 Hình 1.8. Tổng quan về tự động mã hóa sâu ....................................................... 18 Hình 1.9. Tổng quan về mã hóa tổng hợp vùng lân cận ...................................... 19 Hình 3.1. Giao diện hệ khuyến nghị sản phẩm của Tiki.vn ................................. 34 Hình 3.2. Ví dụ một ma trận đánh giá tổng quát .................................................. 35 Hình 3.3. Các hướng tiếp cận hệ thống khuyến nghị ........................................... 36 Hình 3.4. Phương pháp dựa trên người dùng và dựa trên đối tượng ................... 38 Hình 4.1. Ví dụ bảng liệt kê phiếu xuất kho ........................................................ 51 Hình 4.2. Dữ liệu thu được sau khi trích xuất các thông tin cần thiết ................. 52 Hình 4.3. Thống kê tần suất xuất hiện của đơn vị nhận ....................................... 54 vi DANH MỤC CÁC BẢNG BIỂU Bảng 4.1. Bảng dữ liệu sau khi xử lý thô ............................................................. 53 Bảng 4.2. Thống kê dữ liệu các đồ thị ................................................................. 57 Bảng 4.3. Kết quả thực nghiệm khi áp dụng nhúng đỉnh mạng đồ thị hai phía lên hai bộ dữ liệu Kho_PTC4 và DBLP .................................................................... 57 Bảng 4.4. Kết quả thực nghiệm các phương án số lượng bộ ký tự ...................... 58 Bảng 4.5. Tần suất các giá trị trọng số user-item trong các bộ dữ liệu ................ 60 Bảng 4.6. Kết quả thực nghiệm khi áp dụng nhúng đỉnh mạng đồ thị hai phía và khi áp dụng lọc cộng tác dựa trên người dùng và đối tượng................................ 60 Bảng 4.7. Kết quả thực nghiệm khi áp dụng nhúng đỉnh mạng đồ thị hai phía và khi áp dụng lọc cộng tác dựa trên người dùng và đối tượng................................ 62 vii MỞ ĐẦU 1. Lý do chọn đề tài Mạng đồ thị là một trong những cấu trúc mạnh mẽ nhất để mô hình hóa các vấn đề trong thế giới thực. Với sự gia tăng của các mạng xã hội quy mô lớn, biểu diễn mạng để đưa vào các mô hình học máy đã trở thành một lĩnh vực quan trọng của khai phá dữ liệu. Xây dựng một biểu diễn mạng hiệu quả là một thách thức quan trọng trong việc áp dụng học máy đối với dữ liệu mạng đồ thị. Các tác vụ học máy dựa trên mạng đồ thị có khả năng giải quyết đa dạng nhiều vấn đề khác nhau. Nhiều nghiên cứu đã được thực hiện trong các năm qua để tạo ra các biểu diễn đỉnh từ dữ liệu có cấu trúc mạng đồ thị bằng cách sử dụng các phương pháp học biểu diễn mạng. Mạng đồ thị hai phía là mô hình phù hợp nhất để biểu thị mối quan hệ giữa người sử dụng và vật phẩm (bộ phim, quyển sách, mặt hàng v.v…) trong thực tế. Nhiều phương pháp học biểu diễn mạng đã được phát triển, tuy nhiên số lượng nghiên cứu đối với mạng đồ thị hai phía là không nhiều, đặc biệt là việc biểu diễn các mối quan hệ không trực tiếp mà có tính chất bắc cầu là một trong những đặc trưng quan trọng của mạng đồ thị hai phía. Việc biểu diễn mạng đồ thị hai phía tốt sẽ là cơ sở để xây dựng một hệ thống khuyến nghị đáp ứng được các yêu cầu đặt ra như tốc độ đáp ứng, độ chính xác của kết quả khuyến nghị. Các hệ thống khuyến nghị đã được quan tâm nghiên cứu và phát triển nhanh chóng trong thời gian gần đây, đặc biệt các hệ khuyến nghị trong thương mại điện tử đem lại nhiều lợi nhuận cho các nhà bán sản phẩm. Từ thực tế đó có thể thấy nếu như các lĩnh vực quản trị nội bộ, hoạt động sản xuất kinh doanh của các doanh nghiệp được cũng được xây dựng một hệ thống khuyến nghị thì sẽ góp phần nâng cao hiệu quả, năng suất lao động của đơn vị. Do đó, đề tài lựa chọn việc nghiên cứu phương pháp nhúng đỉnh vào mạng đồ thị hai phía để xây dựng một hệ thống khuyến nghị, ứng dụng vào công tác quản lý kho và cấp phát vật tư thiết bị tại Công ty Truyền tải điện 4. 1 2. Mục tiêu nghiên cứu Mục tiêu của đề tài là nghiên cứu một phương pháp nhúng đỉnh mạng đồ thị hai phía, sau đó áp dụng các phương pháp học máy để xây dựng hệ thống khuyến nghị đối với mạng đồ thị hai phía, cuối cùng là áp dụng vào thực tế vào hoạt động sản xuất kinh doanh của một doanh nghiệp. Mục tiêu cụ thể gồm: - Tìm hiểu tổng quan các phương pháp biểu diễn mạng đồ thị. - Nghiên cứu phương pháp nhúng đỉnh mạng đồ thị hai phía. o Tìm hiểu và thiết lập một bộ bước đi ngẫu nhiên trên hai tập đỉnh khác loại của mạng đồ thị hai phía để tìm kiếm và bảo toàn các mối quan hệ gián tiếp giữa các đỉnh cùng phía. o Tìm hiểu và thiết lập một bộ tối ưu hóa chung đồng thời cho cả các quan hệ trực tiếp và quan hệ gián tiếp của các đỉnh của mạng đồ thị hai phía. - Tìm hiểu tổng quan về bài toán khuyến nghị, các hướng tiếp cận cũng như các phương pháp đánh giá hiệu quả của một hệ thống khuyến nghị. - Xây dựng hệ thống khuyến nghị với đầu vào là các vector nhúng đỉnh đã được học của mạng đồ thị hai phía. Áp dụng hệ thống khuyến nghị lên hoạt động thực tế là công tác quản lý kho và cấp phát vật tư thiết bị tại Công ty Truyền tải điện 4. 3. Đối tượng, phạm vi nghiên cứu Trọng tâm nghiên cứu của đề tài là xây dựng một hệ thống khuyến nghị ứng dụng trên thực tế sản xuất kinh doanh tại một doanh nghiệp, với nguồn dữ liệu của đơn vị để thiết lập nên một mạng đồ thị hai phía và áp dụng các phương pháp nhúng đỉnh để biểu diễn mạng đồ thị hai phía thực tế. Cơ sở dữ liệu được thu thập là hoạt động quản lý và cấp phát vật tư thiết bị cho các đơn vị trực thuộc của Công ty Truyền tải điện 4. Phạm vi nghiên cứu của đề tài là tìm hiểu một phương pháp cụ thể thực hiện nhúng đỉnh mạng đồ thị hai phía để đưa vào tác vụ học máy xây dựng hệ thống 2 khuyến nghị và ứng dụng thực tế. Kết quả của phương pháp được đánh giá và so sánh với hệ thống khuyến nghị cơ bản không áp dụng nhúng đỉnh đồ thị. 4. Phương pháp nghiên cứu Phương pháp nghiên cứu của luận văn là kết hợp nghiên cứu lý thuyết và áp dụng thực nghiệm Về lý thuyết, trước tiên đề tài nghiên cứu tổng quan về đồ thị, các phương pháp nhúng đỉnh đồ thị cũng như ứng dụng của nó. Đề tài tìm hiểu chi tiết về phương pháp nhúng đỉnh mạng đồ thị hai phía với các đặc điểm là sử dụng phương pháp bước đi ngẫu nhiên đề tìm kiếm và phát hiện các mối quan hệ bậc cao giữa các đỉnh cùng loại, và tối ưu hóa đồng thời các thành phần quan hệ trực tiếp và gián tiếp giữa các đỉnh, giúp bảo toàn tốt nhất đặc trưng của các quan hệ trong mạng đồ thi hai phía sau khi nhúng đỉnh. Kết quả nhúng đỉnh đồ thị hai phía này được sử dụng là đầu vào xây dựng hệ thống khuyến nghị. Về thực nghiệm, đề tài thu thập cơ sở dữ liệu thực tế là công tác quản lý và cấp phát vật tư thiết bị tại kho vật tư Công ty Truyền tải điện 4 trong khoảng thời gian từ năm 2017 đến tháng 6 năm 2021. Các dữ liệu này được thu thập và xây dựng thành một mạng đồ thị hai phía với hai loại đỉnh là user: các đơn vị sử dụng và item: các vật tư thiết bị. Dữ liệu được gán mã, xử lý thô và tinh chỉnh, lọc các nội dung thừa, các yếu tố gây nhiễu, các yếu tố không phải là trọng tâm công tác của yêu cầu công việc trong thực tế. Sau đó ứng dụng nhúng đỉnh vào mạng đồ thị hai phía này để xây dựng được hệ thống khuyến nghị trong hoạt động sản xuất kinh doanh thực tiễn của doanh nghiệp. 5. Đóng góp của đề tài Đề tài đã nghiên cứu tổng quan về các phương pháp nhúng đỉnh đồ thị, đặc biệt là đồ thị hai phía, tìm hiểu các mô hình hệ thống khuyến nghị, từ đó xây dựng có hiệu quả một hệ thống khuyến nghị trên cơ sở nhúng đỉnh mạng đồ thị hai phía áp dụng vào dữ liệu thực tế trong hoạt động của một doanh nghiệp. Đây sẽ là tiền đề để có thể tiếp tục phát triển hệ thống khuyến nghị này triển khai trên các cơ sở sản xuất kinh doanh khác hoặc các lĩnh vực khác của cuộc sống. 3 Ngoài ra, bộ cơ sở dữ liệu thực tế thu thập được cũng như cách thức xử lý dữ liệu và xây dựng thành mạng đồ thị hai phía sẽ giúp cho doanh nghiệp tiếp tục cập nhật, bổ sung cho cơ sở dữ liệu hiện có và cải thiện độ chính xác của hệ thống khuyến nghị, góp phần câng cao hiệu quả hoạt động của doanh nghiệp. 6. Cấu trúc của đề tài Cấu trúc của đề tài được trình bày trong 4 chương như sau: 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ế. Chương 2. 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. Chương 3. 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ế. Chương 4. 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. 5 CHƯƠNG 1. 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. 1.1. Tổng quan về đồ thị 1.1.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 đó. Hình 1.1. Đơ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. Hình 1.2. Đơ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ị. Hình 1.3. Đồ thị hai phía 8 1.1.2. Đồ 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ị. Hình 1.4. 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.4). 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ị. Các phần sau sẽ tìm hiểu các phương pháp biểu diễn đồ thị bằng nhúng đỉnh trong lĩnh vực học máy và khai phá dữ liệu, đặc biệt là các phương pháp có thể mở rộng cho các đồ thị rất lớn cỡ hàng triệu đỉnh và được thúc đẩy mạnh bởi các tiến bộ về học sâu. 10 1.2. Biểu diễn đồ thị bằng phép nhúng đỉnh 1.2.1. Tổng quan về phép nhúng đỉnh đồ thị Mục tiêu của nhúng đỉnh đồ thị là là mã hóa các đỉnh thành các vector có số chiều thấp nhưng có thể tóm tắt được vị trí của các đỉnh trong đồ thị và cấu trúc của phần đồ thị lân cận. Các phép nhúng số chiều thấp này có thể được quan sát bằng cách mã hóa hoặc chiếu các đỉnh lên một không gian đặc trưng với các quan hệ hình học trong không gian này tương ứng với sự tương tác giữa các đỉnh trong đồ thị ban đầu. Hình 1.5. Cách thức mã hóa - giải mã của phép nhúng đỉnh Các phép nhúng đỉnh đồ thị bao gồm phần chính là bộ mã hóa (encoder) và bộ giải mã (decoder). Bộ mã hóa là một hàm ánh xạ mỗi đỉnh thành một vector có số chiều thấp, gọi là vector nhúng, và bộ giải mã sẽ trả về thông tin cấu trúc của đồ thị từ các vector nhúng đã học (Hình 1.5). Ý tưởng của hướng tiếp cận mã hóa – giải mã này là: nếu ta có thể học cách giải mã thông tin đồ thị có số chiều lớn, ví dụ như các vị trí toàn cục của các đỉnh trong đồ thị hoặc cấu trúc của vùng đồ thị lân cận, từ các phép nhúng số chiều thấp đã được mã hóa trước đó, thì về tổng thể, các phép nhúng này cần phải chứa toàn bộ các thông tin cần thiết cho các tác vụ học máy phía sau. Bộ mã hóa là một hàm có dạng: ENC ∶ 𝒱 → ℝ𝑑 , 11 (1.1)