ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
——————–

BÙI BÁ ANH

XÂY DỰNG HỆ THỐNG KHUYẾN NGHỊ DỰA TRÊN
GRAPH NEURAL NETWORK

Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 8480101

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 7 năm 2023


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA – ĐHQG-HCM
Cán bộ hướng dẫn khoa học:
PGS.TS. Quản Thành Thơ

Cán bộ chấm nhận xét 1:
PGS.TS. Võ Thị Ngọc Châu
Cán bộ chấm nhận xét 2:
PGS.TS. Đỗ Văn Nhơn
Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp.
HCM ngày 11 tháng 07 năm 2023.
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: (Ghi rõ họ, tên, học
hàm, học vị của Hội đồng chấm bảo vệ luận văn thạc sĩ)
1. Chủ tịch: TS. Nguyễn Đức Dũng

2. Thư ký: TS. Trương Thị Thái Minh
3. Phản biện 1: PGS.TS. Võ Thị Ngọc Châu
4. Phản biện 2: PGS.TS. Đỗ Văn Nhơn
5. Ủy viên: TS. Bùi Thanh Hùng
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý
chuyên ngành sau khi luận văn đã được sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG

TS. Nguyễn Đức Dũng

TRƯỞNG KHOA KHOA HỌC VÀ
KỸ THUẬT MÁY TÍNH


ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: BÙI BÁ ANH

MSHV: 2171059

Ngày, tháng, năm sinh: 04/05/1999

Nơi sinh: Đắc Lắc

Chuyên ngành: Khoa học Máy tính


Mã số : 8480101

I. TÊN ĐỀ TÀI: XÂY DỰNG HỆ THỐNG KHUYẾN NGHỊ DỰA TRÊN GRAPH
NEURAL NETWORK
(BUILDING RECOMMENDATION SYSTEM BASED ON GRAPH NEURAL
NETWORK)
II. NHIỆM VỤ VÀ NỘI DUNG:
-

Xây dựng Hệ thống khuyến nghị dựa trên việc biểu diễn các phiên hoạt động dưới
dạng đồ thị và sử dụng cơ chế học sâu.
Nghiên cứu và đề xuất các phương pháp nhằm cải thiện độ chính xác của mơ hình.
Thực nghiệm và đánh giá kết quả của các phương pháp đề xuất.

III.

NGÀY GIAO NHIỆM VỤ : 06/02/2023

IV.

NGÀY HOÀN THÀNH NHIỆM VỤ: 09/06/2023

V. CÁN BỘ HƯỚNG DẪN: PGS.TS Quản Thành Thơ.

Tp. HCM, ngày 09 tháng 06 năm 2023
CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

HỘI ĐỒNG NGÀNH

(Họ tên và chữ ký)

PGS.TS Quản Thành Thơ
TRƯỞNG KHOA
KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
(Họ tên và chữ ký)

i


LỜI CẢM ƠN
Để hoàn thành luận văn tốt nghiệp này, học viên đã nhận được sự hỗ trợ
tích cực từ rất nhiều phía. Đầu tiên và quan trọng nhất, em xin gửi lời cảm
ơn chân thành đến giảng viên hướng dẫn trực tiếp của em, thầy PGS.TS.
Quản Thành Thơ. Thầy là người định hướng chính, cung cấp tài liệu cũng
như theo dõi quá trình thực hiện đề tài và hỗ trợ khi em gặp khó khăn. Hơn
hết thầy đã truyền cảm hứng cho em từ khi còn là sinh viên của Đại học
Bách Khoa về niềm đam mê với học máy, học sâu, xử lí ngơn ngữ tự nhiên
và nhiều vấn đề khác trong Lĩnh vực Khoa học Máy tính.
Em xin được gửi lời cảm ơn đến thầy TS. Nguyễn Tiến Thịnh, thầy đã
định hướng, hỗ trợ em từ giai đoạn Đề cương luận văn, cũng như đưa ra
những góp ý quý báu để em hoàn thiện hơn Luận văn tốt nghiệp này.
Em xin được tỏ lòng biết ơn sự tận tình dạy dỗ, giúp đỡ của q thầy cơ
trong khoa Khoa học và Kỹ thuật Máy tính nói riêng cũng như trường Đại
học Bách khoa TP. Hồ Chí Minh nói chung. Những kiến thức nhận được từ
q thầy cơ là vơ cũng q giá và bổ ích, hỗ trợ rất lớn cho em có thể hồn
thành luận văn tốt nghiệp này.
Em cũng xin được gửi lời cảm ơn đến Trung tâm ứng dụng Khoa học
Dữ liệu - Công ty cổ phần FPT đã tạo điều kiện cho em đào sâu nghiên cứu
nâng cao kiến thức chuyên môn cũng như hỗ trợ tài ngun để huấn luyện

mơ hình góp phần hoàn thiện luận văn.
Cuối cùng, em muốn gửi lời cảm ơn đến gia đình, người thân, bạn bè,
những người đã quan tâm, động viên, giúp đỡ cả về thể chất lẫn tinh thần để
em có đủ nghị lực, sức khỏe hồn thành tốt luận văn tốt nghiệp này.
Với lịng biết ơn chân thành, em xin gửi lời chúc sức khỏe cũng như
những lời chúc tốt đẹp nhất đến các quý thầy cơ trong Khoa Khoa học và Kỹ
thuật Máy tính - Trường Đại Học Bách Khoa Đại Học Quốc Gia Thành phố
Hồ Chí Minh.

ii


TĨM TẮT LUẬN VĂN
Bài tốn khuyến nghị theo phiên là một nhánh của Bài tốn khuyến nghị nói
chung, đã được nghiên cứu và ứng dụng trong thực tiễn từ nhiều năm trước.
Trong những năm trở lại đây, bài toán này đã được quan tâm và trở nên phổ
biến hơn do sự phát triển mạnh mẽ của các mơ hình học sâu có khả năng xử
lý tốt tính tuần tự đã đạt được những thành tựu to lớn trong nhiều tác vụ của
lĩnh vực Xử lý ngôn ngữ tự nhiên. Một trong những hướng tiếp cận tốt nhất
cho đến hiện tại là mơ hình Graph Neural Network, bằng việc biểu diễn
các phiên hoạt động dưới dạng đồ thị có hướng và áp dụng cơ chế học sâu,
đã mang lại những kết quả rất ấn tượng cho lớp bài toán này. Tuy nhiên, hầu
hết các nghiên cứu trước đó bỏ qua yếu tố thời gian theo dõi của người dùng
trên từng sản phẩm, trong khi đó lại là một dạng phản hồi gián tiếp mà hệ
thống có thể dùng để đánh giá mức độ u thích của người dùng trên chúng.
Do đó trong luận văn tốt nghiệp này, dựa trên cơ sở của mơ hình Graph
Neural Network, học viên tập trung khai thác yếu tố thời gian theo dõi của
người dùng và thời điểm tương tác như là một cách bổ sung thơng tin giúp
cải thiện chất lượng mơ hình khuyến nghị. Ngồi ra, cơ chế self-attention
cũng được đề xuất giúp mơ hình có thể khai phá tốt hơn mối quan hệ giữa

những sản phẩm trong một phiên hoạt động.

iii


ABSTRACT OF DISSERTATION
Session-based recommendation is a specific type of recommendation problem that has been widely studied and applied for a long time. With the rapid
advancement of deep learning models, which are capable of processing sequential data and achieving remarkable results in many natural language
processing tasks, this problem has attracted more attention and popularity
in recent research. One of the most effective approaches so far is the Graph
Neural Network model, which represents sessions as directed graphs and
applies deep learning to improve the quality of recommendations. However,
most of the previous studies overlook the user’s time spent on each product, which is a form of implicit feedback that can help the system measure
the user’s interest level. Therefore, in this thesis, the student builds on the
Graph Neural Network model and incorporates the user’s time spent factor
as a way to enhance the information for better recommendations. Moreover,
the self-attention mechanism is also proposed to help the model capture the
relationship between products in a session more effectively.

iv


LỜI CAM ĐOAN
Tôi xin cam đoan đề tài luận văn tốt nghiệp: “XÂY DỰNG HỆ THỐNG
KHUYẾN NGHỊ DỰA TRÊN GRAPH NEURAL NETWORK” là cơng
trình nghiên cứu của bản thân. Những phần tài liệu được sử dụng trong luận
văn đã được nêu rõ trong phần Tài liệu tham khảo. Các số liệu, kết quả trình
bày trong luận văn là hồn tồn trung thực, nếu có sai sót tơi xin chịu hồn
tồn trách nhiệm và chịu mọi kỷ luật của bộ môn và nhà trường đề ra.


Học viên

Bùi Bá Anh

v


Mục lục
Chương 1. GIỚI THIỆU ĐỀ TÀI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1. Giới thiệu chung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2. Mơ tả Bài tốn khuyến nghị theo phiên . . . . . . . . . . . . . . . . . . . .

3

1.3. Mục tiêu và nhiệm vụ của luận văn . . . . . . . . . . . . . . . . . . . . . . .

6

1.4. Giới hạn đề tài . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.5. Đóng góp của luận văn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


7

1.6. Tóm tắt nội dung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Chương 2. CƠ SỞ LÝ THUYẾT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.1. Tổng quan về Lý thuyết đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.1.1. Định nghĩa và ví dụ về đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.1.2. Các loại đồ thị đặc biệt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.1.3. Biểu diễn đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.2. Mơ hình Artificial Neural Network - ANN . . . . . . . . . . . . . . .

17


2.3. Mơ hình Graph Neural Network . . . . . . . . . . . . . . . . . . . . . . . .

20

2.3.1. Ví dụ mơ tả . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.3.2. Mơ hình Graph Neural Network . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.4. Cơ chế Self-Attention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

Chương 3. CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN . . . . . . .

28

3.1. Hướng tiếp cận cổ điển cho Bài toán khuyến nghị nói chung . . .
30
3.1.1. Khai phá luật kết hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

3.1.2. K-Nearest Neighbour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30


3.1.3. Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.2. Hướng tiếp cận bằng biểu diễn đặc trưng ẩn . . . . . . . . . . . . .

33

3.2.1. Phân tích ma trận thành nhân tử . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.2.2. Mơ hình Item2Vec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

vi i


3.3. Hướng tiếp cận bằng Học sâu . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

Chương 4. MƠ HÌNH ĐỀ XUẤT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.1. Mơ hình tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39


4.2. Phương pháp đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

4.3. Tập dữ liệu và phương pháp xử lý . . . . . . . . . . . . . . . . . . . . . . .

44

4.4. Đề xuất 1: Đánh giá lại mức độ quan tâm dựa trên thời gian
theo dõi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4.4.1. Động lực và ý tưởng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4.4.2. Mơ tả mơ hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

4.4.3. Tham số cấu hình của mơ hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

4.4.4. Kết quả thực nghiệm và thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . .

51


4.5. Đề xuất 2: Xây dựng đặc trưng phiên hoạt động bằng MultiHead Attention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
4.5.1. Động lực và ý tưởng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

4.5.2. Mơ tả mơ hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

4.5.3. Tham số cấu hình của mơ hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.5.4. Kết quả thực nghiệm và thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . .

57

Chương 5. KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

5.1. Kết quả đạt được . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

5.2. Hạn chế và vấn đề tồn đọng . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60


5.3. Hướng phát triển . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

vii
ii


Danh sách hình vẽ
1.1

Minh họa ứng dụng hệ thống khuyến nghị đề xuất sản phẩm
tương tự với một sản phẩm đã được lựa chọn trước trên nền
tảng Tiki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2

Minh họa tổng quát tương tác của người dùng trong một
phiên hoạt động. . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3

Ví dụ minh họa một người dùng thực hiện nhiều loại tương
tác trong một phiên hoạt động. . . . . . . . . . . . . . . . . . . 4

1.4


Ví dụ minh họa một người dùng thực hiện một loại tương
tác duy nhất trong một phiên hoạt động. . . . . . . . . . . . . . 5

1.5

Nhiệm vụ của Hệ thống khuyến nghị trong một phiên hoạt
động của người dùng. . . . . . . . . . . . . . . . . . . . . . . . 5

2.1

Bi toỏn 7 cõy cu Kăonigsberg biu din di dạng đồ thị . . . . 10

2.2

Đồ thị vô hướng và đồ thị có hướng . . . . . . . . . . . . . . . . 11

2.3

Đơn đồ thị và đa đồ thị . . . . . . . . . . . . . . . . . . . . . . 12

2.4

Biểu diễn ma trận kề cho đồ thị có hướng . . . . . . . . . . . . 16

2.5

Cấu trúc của một Perceptron . . . . . . . . . . . . . . . . . . . 18

2.6


Các hàm phi tuyến được sử dụng trong Perceptron . . . . . . . . 19

2.7

Hình ảnh về đồ thị và các giá trị khởi tạo trong ví dụ mơ tả . . . 20

2.8

Hình ảnh về đồ thị và các giá trị sau bước 1 trong ví dụ mơ tả . . 21

2.9

Hình ảnh về đồ thị và các giá trị sau bước 2 trong ví dụ mơ tả . . 22

2.10 Minh họa khối Scaled Dot-Product Attention . . . . . . . . . . 26
2.11 Minh họa các khối Multi-Head Self-Attention . . . . . . . . . . 27
3.1

Các mốc thời gian quan trọng của Bài toán khuyến nghị theo
phiên. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
viii
iii


3.2

Kiến trúc mơ hình Skip-gram và CBOW. . . . . . . . . . . . . . 35

3.3


Kiến trúc các mơ hình khuyến nghị tuần tự dựa trên học sâu. . . 36

4.1

Kiến trúc mơ hình SRGNN. . . . . . . . . . . . . . . . . . . . . 39

4.2

Biểu diễn các sản phẩm trong một phiên hoạt động dưới
dạng đa đồ thị có hướng và ma trận kề.

4.3

. . . . . . . . . . . . . 40

Các mốc thời gian được sử dụng để xác định trọng số cho
từng sản phẩm. . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.4

Các mốc thời gian được sử dụng để xác định trọng số cho
từng sản phẩm trong trường hợp sản phẩm được bấm chọn
nhiều lần. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.5

Kiến trúc của mô hình đề xuất 1 . . . . . . . . . . . . . . . . . 50

4.6


Minh họa hoạt động của self-attention để xác định đặc trưng
của chuỗi sản phẩm . . . . . . . . . . . . . . . . . . . . . . . . 54

4.7

Đề xuất sử dụng Multi-Head Attention để xác định đặc trưng
toàn cục của phiên hoạt động . . . . . . . . . . . . . . . . . . . 55

ix
iv


Danh sách bảng
4.1

Các thông số liên quan trên 3 tập dữ liệu Yoochose, Diginetica và Otto . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.2

Bảng giá trị các tham số cho mơ hình SRGNN kết hợp Đề
xuất 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3

Kết quả thực nghiệm mơ hình đề xuất 1 so với mơ hình gốc
(SRGNN) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.4


Bảng giá trị các tham số cho mơ hình SRGNN kết hợp Đề
xuất 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.5

Kết quả thực nghiệm mơ hình đề xuất 2 so với mơ hình gốc
(SRGNN) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

vx


Chương 1

GIỚI THIỆU ĐỀ TÀI
1.1.

Giới thiệu chung

Trong những năm gần đây, cùng với sự tiến bộ và phát triển nhanh chóng
của khoa học và cơng nghệ, đặc biệt là sự ra đời của Internet, con người tiếp
xúc nhiều và dần quen hơn với việc sử dụng các nền tảng trực tuyến trong
cuộc sống hàng ngày. Các kênh thương mại điện tử, trang mạng xã hội hay
các dịch vụ truyền hình, tin tức xuất hiện ngày càng nhiều và dần trở thành
một phần không thể thiếu trong cuộc sống của con người, giúp cho việc trao
đổi thông tin, mua bán và sử dụng dịch vụ trở nên nhanh chóng và hiệu quả
hơn. Dưới góc độ của nhà cung cấp dịch vụ, việc nắm bắt thị hiếu, thói quen
và sở thích của người dùng là vô cùng quan trọng, giúp họ biết được những
thứ mà người dùng đang thực sự cần để đề xuất, từ đó tối ưu hóa doanh thu,
lợi ích mang lại từ khách hàng cũng như là giúp duy trì sự tin tưởng và u
thích của họ đối với dịch vụ. Ngược lại, dưới góc độ của người dùng khi sử

dụng một nền tảng trực tuyến, sẽ có rất nhiều thơng tin được cung cấp và
có thể khiến họ trở nên khó khăn khi tìm kiếm những thơng tin thực sự cần
thiết, nếu chúng không được tổ chức và đề xuất một cách hợp lý. Hệ thống
khuyến nghị (Recommendation System - RS) [1] ra đời như là một cách để
nhà cung cấp dịch vụ nắm bắt và trích lọc ra thơng tin về sở thích, nhu cầu
cũng như mối quan tâm của người dùng để từ đó đưa ra chiến lược đề xuất
thông tin, sản phẩm một cách hiệu quả nhất. Một vài ví dụ phổ biến hiện
nay mà chúng ta thường bắt gặp, chẳng hạn như những video được đề xuất
khi sử dụng nền tảng Youtube, hay Gợi ý kết bạn khi sử dụng mạng xã hội
Facebook, ... thực chất đều là những dạng thể hiện của Hệ thống khuyến
1


nghị, khi mà chúng dựa trên những thông tin sử dụng của chính chúng ta đã
cung cấp để đưa ra gợi ý cho phù hợp.

Hình 1.1: Minh họa ứng dụng hệ thống khuyến nghị đề xuất sản phẩm
tương tự với một sản phẩm đã được lựa chọn trước trên nền tảng Tiki.vn
Tuy nhiên trong thực tế, hành vi tiêu dùng của con người lại phụ thuộc
rất nhiều vào những nhu cầu của họ trong một khoảng thời gian ngắn như
là việc mua hàng trên các trang thương mại điện tử, ăn uống, mua sắm, du
lịch, giải trí. Ví dụ minh hoạ như Hình 1.1, giả sử một người dùng đang có
nhu cầu mua một chiếc điện thoại mới, nhưng hệ thống lại đề xuất các sản
phẩm như máy giặt, điều hịa,... thì sẽ khơng phù hợp với nhu cầu thực sự
của họ tại thời điểm đó mà lúc này các sản phẩm được gợi ý phù hợp nên
là ốp lưng, cáp sạc, tai nghe. Vì vậy, bên cạnh việc thu thập dữ liệu hành
vi người dùng và tổ chức lưu trữ phù hợp thì việc nghiên cứu làm sao khai
thác hiệu quả những hành vi tương tác của người dùng với sản phẩm
trong ngắn hạn và đặc điểm tuần tự của chúng là rất quan trọng. Chủ
đề này còn được biết đến với tên gọi Bài toán Khuyến nghị theo phiên

(Session-based Recommender System - SBRS) [2, 3] là một nhánh của Bài
toán Khuyến nghị, đã ra đời từ rất lâu và nghiên cứu trong một thời gian
dài. Tuy nhiên gần đây, chủ đề này trở nên phổ biến và được quan tâm nhiều
hơn do sự ra đời của những kiến trúc mơ hình có khả năng giải quyết các dữ
liệu dạng chuỗi tuần tự như mơ hình RNN [4], cơ chế Self-Attention, kiến
trúc Transformer [5] đã đạt được những cột mốc đáng nhớ trong lĩnh vực Xử
2


lý ngôn ngữ tự nhiên (Natural Language Processing - NLP). Hay sự nổi lên
của Graph Neural Network (GNN) [6] hướng đến tổ chức dữ liệu dưới dạng
đồ thị và sử dụng cơ chế Học sâu (Deep Learning - DL) [7] mang lại những
kết quả rất vượt trội trên nhiều dạng bài toán và dạng dữ liệu (dù GNN đã
ra đời từ rất lâu). Đó là lý do tơi chọn thực hiện đề tài “Xây dựng hệ thống
khuyến nghị dựa trên Graph Neural Network”, mà cụ thể hơn là Bài toán
khuyến nghị theo phiên, bằng việc biểu diễn các sản phẩm trong một phiên
hoạt động dưới dạng đồ thị và áp dụng cơ chế học sâu, với mục tiêu khai
thác đặc tính tuần tự ngắn hạn trong việc đưa ra gợi ý sản phẩm tới người
dùng, từ đó giúp nâng cao chất lượng của kết quả gợi ý được đưa ra.

1.2.

Mô tả Bài tốn khuyến nghị theo phiên

Hình 1.2: Minh họa tổng quát tương tác của người dùng trong một phiên
hoạt động.
Trước tiên, khi nhắc tới một phiên hoạt động (session) của người dùng,
hai đặc điểm quan trọng nhất cần quan tâm là tính ngắn hạn và tính tuần
tự. Ví dụ, khi một người dùng truy cập vào một trang thương mại điện tử,
tương đương với một phiên hoạt động, tại thời điểm đó người này chỉ tìm

kiếm các mặt hàng điện thoại. Tuy nhiên sau đó vài ngày, người này lại tập
trung tìm kiếm mặt hàng quần áo, lúc này rõ ràng hệ thống không nên tiếp
tục đề xuất các mặt hàng điện thoại nữa. Tính ngắn hạn xuất phát từ nhu cầu
của người dùng tại một thời điểm cụ thể. Ngồi ra, các sản phẩm được tìm
3


kiếm trong một phiên hoạt động thường có các đặc điểm tương quan nào
đó, hoặc các sản phẩm được chọn sau có thể xuất phát từ việc quan sát các
sản phẩm trước đó và hành vi này có thể lặp lại ở nhiều người dùng. Đó là
biểu hiện của tính tuần tự. Các thành phần chính của một Hệ thống khuyến
nghị theo phiên bao gồm tập sản phẩm mà người dùng tương tác (items) và
hành vi tương tác của người dùng đối với sản phẩm (types). Hình 1.2 minh
họa một cách tổng quát hành vi của người dùng trong một phiên hoạt động.
Trong đó:
− t1 ,t2 , ..,tm là loại hành vi mà người dùng có thể tương tác với sản phẩm
(ví dụ như chọn (click), mua (buy), chia sẻ (share),...);
− i1 , i2 , .., in là tập hợp các sản phẩm đang có trong hệ thống;
Trong thực tế, khi tham gia vào một phiên hoạt động, người dùng thực
hiện rất nhiều tương tác lên các sản phẩm (ví dụ như Hình 1.3).

Hình 1.3: Ví dụ minh họa một người dùng thực hiện nhiều loại tương tác
trong một phiên hoạt động.
Tuy nhiên, trong phạm vi nghiên cứu và thực hiện luận văn tốt nghiệp
này, học viên sẽ tập trung vào một hành vi duy nhất của người dùng
trong xuyên suốt phiên hoạt động, cụ thể là tương tác chọn (click) (như
Hình 1.4). Giới hạn này giúp cho việc thiết lập dữ liệu huấn luyện đơn giản
hơn nhưng lại được ứng dụng trong thực tế hiệu quả (vì tất cả các tương tác
khác đều xuất phát từ hành vi này trước tiên). Ngoài ra, các tài liệu tham
4



khảo và cơng trình nghiên cứu được đào sâu cho đến hiện tại trên bài toán
khuyến nghị theo phiên cũng được giới hạn theo cách này.

Hình 1.4: Ví dụ minh họa một người dùng thực hiện một loại tương tác duy
nhất trong một phiên hoạt động.
Khi đó, nhiệm vụ của Hệ thống khuyến nghị là đưa ra đề xuất cho sản
phẩm tiếp theo người dùng có khả năng sẽ bấm vào dựa trên các sản phẩm
đã được lựa chọn trước đó trong cùng một phiên hoạt động (minh họa như
Hình 1.5).

Hình 1.5: Nhiệm vụ của Hệ thống khuyến nghị trong một phiên hoạt động
của người dùng.

5


1.3.

Mục tiêu và nhiệm vụ của luận văn

Mục tiêu của luận văn hướng đến việc nghiên cứu và xây dựng Hệ thống
khuyến nghị theo phiên sử dụng các phương pháp học sâu và mơ hình hóa
dữ liệu dưới dạng đồ thị. Cụ thể:
– Nắm được Lý thuyết đồ thị. Hiểu và sử dụng được các mơ hình học
sâu.
– Nắm được các phương pháp giải quyết cho Bài toán khuyến nghị, đặc
biệt là các phương pháp gần đây sử dụng các mơ hình học sâu và mơ
hình hóa dưới dạng đồ thị. Từ đó chỉ ra được các ưu nhược điểm của

từng phương pháp.
– Đưa ra được đề xuất có thể cải thiện hiệu suất của mơ hình dựa trên
thực nghiệm.
Từ những mục tiêu trên, học viên đề ra các nhiệm vụ cần thực hiện trong
q trình hồn thiện luận văn:
– Tìm hiểu về Hệ thống khuyến nghị, đặc biệt là nhóm Bài tốn khuyến
nghị theo phiên, các cơng trình liên quan, các phương pháp giải quyết
bài toán, ưu và nhược điểm của các phương pháp.
– Nghiên cứu và đề xuất các mơ hình giúp cải thiện độ chính xác cho
Bài tốn khuyến nghị theo phiên.
– Tìm kiếm các tập dữ liệu thực tế đã được công bố và thực hiện xử lý
dữ liệu. Tập trung vào các tập dữ liệu thường được sử dụng trong các
báo cáo khoa học để có được kết quả đánh giá khách quan. Bên cạnh
đó, tìm kiếm các tập dữ liệu mới để chứng minh tính tổng qt của
mơ hình đề xuất.
6


– Thực nghiệm, đánh giá kết quả của các mô hình đề xuất trên các tập
dữ liệu đã được xử lý trước đó.
– Chỉ ra những hạn chế và vấn đề tồn đọng, đề xuất các giải pháp cải
tiến và mở rộng của bài toán trong tương lai.

1.4.

Giới hạn đề tài

Xây dựng Hệ thống khuyến nghị là một bài toán rộng và có nhiều tác vụ
cũng như nhiều cách tiếp cận khác nhau, vì vậy nội dung của luận văn sẽ
được giới hạn như sau:

– Tập trung vào bài toán Xây dựng hệ thống khuyến nghị theo phiên, cụ
thể là dự đoán sản phẩm tiếp theo mà người dùng quan tâm. Tương
tác của người dùng trong phiên hoạt động dựa trên một hành vi duy
nhất là bấm chọn (click). Thông tin về người dùng hoạt động trong
phiên là ẩn danh (khơng xét đến các thuộc tính định danh và hành vi
ở các phiên hoạt động trong quá khứ).
– Khảo sát trên 3 Tập dữ liệu là Yoochoose, Diginetica và Otto.
– Các phương pháp tiếp cận cho bài toán bao gồm các mơ hình học sâu
như GRU, Graph Neural Network, cơ chế Attention. Mơ hình cơ sở
được sử dụng là SRGNN [8].
– Độ đo được sử dụng là Precision và Mean Reciprocal Rank.

1.5.

Đóng góp của luận văn

Trong luận văn, học viên đề xuất 2 phương án giúp cải thiện hiệu suất
của Hệ thống khuyến nghị theo phiên dựa trên cơ sở là mơ hình SRGNN sử
7


dụng cơ chế Graph Neural Network:
– Bổ sung thông tin về mức độ yêu thích của người dùng trên các sản
phẩm mà họ đã bấm chọn trong phiên hoạt động hiện tại, dựa trên thời
gian xem sản phẩm và thời điểm tương tác, giúp kết quả đề xuất trở
nên chính xác hơn.
– Thay thế cơ chế Attention trong mơ hình SRGNN bằng cơ chế SelfAttention (các khối Multi-Head Self-Attention trong kiến trúc Transformer) để tăng khả năng học của mô hình.

1.6.


Tóm tắt nội dung

Luận văn “Xây dựng hệ thống khuyến nghị dựa trên Graph Neural
Network” bao gồm Năm chương với các nội dung chính sau đây:
– Chương 1, GIỚI THIỆU ĐỀ TÀI: trình bày tổng quan về đề tài, lý
do thực hiện đề tài và ý nghĩa thực tiễn của bài toán, cũng như giới
hạn và phạm vi của đề tài. Cuối cùng là nhiệm vụ và cấu trúc của luận
văn.
– Chương 2, CƠ SỞ LÝ THUYẾT: tổng hợp những vấn đề học thuật
liên quan nhất sẽ áp dụng để giải quyết bài toán, tập trung chủ yếu
vào nội dung của học sâu, từ Mạng nơ ron nhân tạo (Artificial Neural
Network) tới Recurrent Neural Network, cơ chế attention và đặc biệt
là lý thuyết về Graph Neural Network.
– Chương 3, CÁC CƠNG TRÌNH NGHIÊN CỨU LIÊN QUAN:
trình bày một cách tổng quát về những nghiên cứu liên quan đã và
đang được thực hiện, cũng như xu hướng chung hiện nay trong việc

8


giải quyết bài toán. Phần này cũng đưa ra những bàn luận và đánh
giá cho các phương pháp kể trên vì đó là cơ sở quan trọng cho những
nghiên cứu của học viên trong quá trình thực hiện luận văn.
– Chương 4, MƠ HÌNH ĐỀ XUẤT: giới thiệu mơ hình cơ sở cho Bài
toán khuyến nghị theo phiên. Đồng thời đưa ra các cải tiến và động
lực cho các đề xuất đó. Cuối cùng, học viên trình bày các bước tiến
hành thí nghiệm trên những tập dữ liệu khác nhau và đánh giá kết quả
của những cải tiến so với mơ hình cơ sở.
– Chương 5, KẾT LUẬN: tổng hợp các kết quả đạt được trong quá
trình thực hiện luận văn từ bước nghiên cứu và xây dựng giả thuyết

đến triển khai thực nghiệm. Phần này cũng trình bày những hạn chế
và vấn đề tồn đọng, cuối cùng đề xuất các giải pháp cải tiến trong
tương lai.
Mục lục, Danh sách hình vẽ, Danh sách bảng được cung cấp ở đầu luận
văn. Tài liệu tham khảo sẽ được trình bày ở cuối luận văn.

9


Chương 2

CƠ SỞ LÝ THUYẾT
2.1.

Tổng quan về Lý thuyết đồ thị

2.1.1.

Định nghĩa và ví dụ về đồ thị

Lý thuyết đồ thị được xem như một lĩnh vực của toán học rời rạc, được
phát triển từ rất lâu và có nhiều ứng dụng trong khoa học cũng như thực tiễn,
đặc biệt là đối với các ngành toán học và khoa học máy tính. Hình 2.1 minh
họa Bài tốn 7 cây cầu 1 dưới dạng đồ thị.

Hình 2.1: Bài tốn 7 cây cu Kăonigsberg biu din di dng th
nh ngha: Mt đồ thị được biểu diễn dưới dạng G = (V, E), trong đó
V, E là hai tập hợp hữu hạn, với V là tập hợp các đỉnh (vertex) của đồ thị, E
là tập hợp các cạnh (edge). Một cạnh e của đồ thị được hình thành từ sự liên
kết hai đỉnh u, v thuộc đồ thị, thường được viết e = (u, v). Khi này ta nói, u, v

là hai mút của cạnh e và e là cạnh nối u với v.
Như vậy, nếu coi mỗi đỉnh của đồ thị biểu diễn một đối tượng, thì một cạnh
10


trong đồ thị biểu diễn một quan hệ hai ngôi giữa các đối tượng này. Nếu vai
trò của hai đầu mút u, v đối với cạnh e là như nhau, tức là không kể đến thứ
tự của chúng trong việc biểu diễn cạnh, ta gọi đó là cạnh vơ hướng. Ngược
lại, việc biểu diễn e cần kể đến thứ tự trước sau của u, v, khi này e là cạnh
có hướng, trong đó u (giả sử) là đỉnh đầu, v là đỉnh cuối của cạnh e. Trong
biểu diễn e = (u, v) đối với cạnh có hướng, ta nói e là cạnh nối từ u đến v.
Ngoài ra, trong định nghĩa cạnh, nếu một cạnh được nối bởi một đỉnh đến
chính nó, hay e = (u, u), e được gọi là khuyên.
Dưới đây là phân loại một số dạng đồ thị:
− Đồ thị vơ hướng và đồ thị có hướng: Một đồ thị mà tất cả các cạnh
của nó là vơ hướng được gọi là đồ thị vơ hướng (Hình 2.2a), ngược là
là đồ thị có hướng (Hình 2.2b). Nếu bỏ đi hướng trên tất cả các cạnh
có hướng, một đồ thị có hướng sẽ trở thành đồ thị vơ hướng.

Hình 2.2: Đồ thị vơ hướng và đồ thị có hướng
− Đơn đồ thị và đa đồ thị: Một đồ thị khơng có khun và giữa hai đỉnh
chỉ có nhiều nhất là một cạnh nối được gọi là một đơn đồ thị (Hình
2.3a). Các đồ thị có khun hay có nhiều hơn một cạnh nối giữa hai
đỉnh được gọi là các đa đồ thị (Hình 2.3b).
− Đồ thị có trọng số: Trong một đồ thị, nếu trên mỗi cạnh được gán
11


Hình 2.3: Đơn đồ thị và đa đồ thị
cho một số thực nào đó, ta gọi đó là đồ thị có trọng số. Nếu khơng nói

gì thêm, ta xem như đồ thị khơng có trọng số (trọng số trên tất cả các
cạnh là bằng nhau).
Một số khái niệm khác trong đồ thị:
− Kề: Đỉnh v được gọi là kề với u nếu có cạnh nối từ u đến v trên một
cạnh có hướng. Nếu đó là cạnh vơ hướng, ta nói u, v kề nhau.
− Liên thuộc: Nếu đỉnh u là một trong hai mút của cạnh e, khi này ta
nói đỉnh u liên thuộc cạnh e.
− Bậc của đỉnh: Trong đồ thị vô hướng, bậc của đỉnh u là tổng số cạnh
liên thuộc với nó, kí hiệu là deg(u). Trong đồ thị có hướng, người ta
quan tâm đến cả cạnh ra, vào tại một đỉnh, vì vậy khái niệm bậc được
thay thế bằng nửa bậc, bao gồm nửa bậc vào, kí hiệu deg− (u), là số
cạnh đi vào u, và nửa bậc ra, kí hiệu deg+ (u), là số cạnh đi ra từ u.
Nếu một đỉnh có bậc (hoặc nửa bậc vào, ra) bằng 0, ta gọi đó là đỉnh
treo. Từ những khái niệm về bậc nói trên, ta có Định lý bắt tay.
Định lý bắt tay: Trong đơn đồ thị vô hướng G = (V, E), tổng bậc của

12


tất cả các đỉnh trong đồ thị bằng 2 lần số cạnh:

∑ deg(u) = 2|E|

(2.1)

u∈V

Nếu đồ thị được cho là có hướng, tổng của nửa bậc vào và tổng của
nửa bậc ra bằng nhau và cùng bằng số cạnh trong đồ thị:


∑ deg+ (u) = ∑ deg− (u) = |E|

u∈V

(2.2)

u∈V

− Đường đi: là một dãy các cạnh kề nhau (cạnh sau kề cạnh trước), xuất
phát từ đỉnh s và kết thúc tại đỉnh t. Đường đi có thể là vơ hướng hoặc
có hướng. Số cạnh trên đường đi được gọi là độ dài của đường đi.
− Chu trình: là một đường đi khơng có cạnh lặp lại và đỉnh đầu trùng
với đỉnh cuối. Tương tự như đường đi, chu trình có thể có hướng hoặc
vơ hướng. Một chu trình khơng có đỉnh lặp (trừ đỉnh đầu, đỉnh cuối
trùng nhau) được gọi là một chu trình đơn.
− Đồ thị con: Đồ thị con của một đồ thị G là một đồ thị nhận được từ G
bằng cách bỏ đi một số cạnh và một số đỉnh (cùng với các cạnh liên
quan đến những đỉnh này). Khi đó, đồ thị con G′ = (V ′ , E ′ ), trong đó
V ′ ⊆ V và E ′ ⊆ E.
− Liên thông: Một đồ thị vô hướng được gọi là liên thông nếu giữa hai
đỉnh bất kỳ đều tồn tại một đường đi nào đó giữa hai đỉnh này là điểm
bắt đầu và kết thúc. Trong đồ thị có hướng, nếu ta khơng quan tâm
đến hướng của cạnh, và đồ thị vô hướng thu được là liên thơng, ta nói
đồ thị có hướng đó liên thơng yếu. Nếu điều kiện có hướng cũng được
thỏa mãn, đồ thị đó được gọi là liên thơng mạnh.
13