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

PHẠM LINH SƠN

DỰ ĐỐN CHẤT LƯỢNG KHƠNG KHÍ DỰA TRÊN
GRAPH NEURAL NETWORK
Chun 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. Uỷ 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

PGS.TS. Phạm Trần Vũ


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

CỘNG HOA 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: PHẠM LINH SƠN

MSHV: 1970596

Ngày, tháng, năm sinh: 03/08/1991

Nơi sinh: Quảng Ngãi


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

Mã số: 8480101

I. TÊN ĐỀ TÀI: DỰ ĐỐN CHẤT LƯỢNG KHƠNG KHÍ DỰA TRÊN GRAPH
NEURAL NETWORK
(AIR QUALITY PREDICTION BASED ON GRAPH NEURAL NETWORK)
II. NHIỆM VỤ VÀ NỘI DUNG:
- Nghiên cứu, xây dựng hệ thống dự đốn chất lượng khơng khí dựa trên Graph Neural
Network.
- Nghiên cứu và đề xuất 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 phương pháp đề xuất.
III. NGÀY GIAO NHIỆM VỤ: 06/02/2022
IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 11/06/2023
V. CÁN BỘ HƯỚNG DẪN: PGS.TS Quản Thành Thơ.
Tp. HCM, ngày 12 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
Sau một quá trình thực hiện nghiên cứu, em cũng đã hoàn thành nội dung
luận văn. Luận văn được hồn thành khơng chỉ là kết quả cố gắng khơng
ngừng nghỉ của bản thân mà cịn có sự giúp đỡ, hỗ trợ tích cực của nhiều cá
nhân và tập thể.
Lời đầu tiên, em xin trân trọng tỏ lòng biết ơn chân thành và sâu sắc đến
PGS.TS Quản Thành Thơ, thầy là người hướng dẫn trực tiếp trong quá trình
thực hiện luận văn, nhờ những chia sẻ và đóng góp ý kiến của thầy giúp em
hoàn thiện những nội dung Luận văn. Hơn hết thầy còn là người truyền cảm
hứng cho em trong khoa học máy tính.
Em cũng xin chân thành cảm ơn đến toàn thể anh, chị, em đồng nghiệp
trong công ty Orient đã luôn tạo điều kiện cho em trong quá trình học và thực
hiện luận văn tốt nghiệp. Những lời động viên của toàn thể mọi người là niềm
động lực giúp em vượt quả khoảng thời gian khó khăn nhất trong q trình
thực hiện luận văn.
Cuối cùng, em xin gửi lời cảm ơn chân thành đến gia đình, bạn bè, các
anh, chị cùng lớp cao học đã ln động viên, quan tâm giúp đỡ em trong q
trình học tập và thực hiện luận văn.

ii


TĨM TẮT LUẬN VĂN
Dự đốn chất lượng khơng khí dựa trên Graph Neural Network là bài toán
tập trung vào các tác vụ quan trọng như trích xuất thơng tin những thơng số
trong khơng khí và trích xuất dựa trên mối liên kết không gian của dữ liệu, các
chỉ số trong khơng khí bao gồm 𝑃𝑀2.5, 𝑃𝑀10, 𝑁𝑂2, 𝐶𝑂, 𝑆𝑂2, 𝑂3, 𝐴𝑄𝐼.
Phân bố không gian giữa các cảm biến thể hiện mối liên quan và tính liên kết
của dữ liệu. Trước đây, các phương pháp truyền thống thường sử dụng mơ

hình ARIMA, CNN, LSTM để áp dụng vào bài toán dữ liệu chuỗi thời gian,
cách tiếp cận của các phương pháp này chủ yếu dựa vào các giá trị quan sát
được để đưa ra giá trị dự đoán. Tuy nhiên, những phương pháp truyền thống
vẫn chưa khai thác những khía cạnh tiềm năng khác của dữ liệu chuỗi thời
gian như tận dụng liên hệ, tính chất tương đồng của dữ liệu giữa các thiết bị
thu thập thông tin trong cùng một thời điểm. Đồng thời những phương pháp
trước đây cũng chưa thể hiện được rõ ràng sự đóng góp giữa các mối liên kết
khơng gian của cảm biến vào việc trích xuất đặc trưng. Do đó trong nội dung
của luận văn này, học viên tập trung khai thác bài toán dự đoán dữ liệu chuỗi
thời gian theo hướng sử dụng Graph Neural Network và đưa ra mơ hình đề
xuất, cải tiến so với mơ hình tham khảo.
Sử dụng thơng tin của chỉ số khơng khí kết hợp với thơng tin phân bố
không gian của các thiết bị cảm biến vào bài tốn dự đốn. Trong đó học viên
sử dụng lớp tích chập đồ thị (Graph Convolution Networks) để lọc ra lượng
thông tin trong mạng kết nối của thiết bị nhằm tận dụng nguồn dữ liệu tiềm
năng hiện có của hệ thống internet vạn vật, điều này cung cấp thêm thông tin
cho mơ hình, giúp cải thiện độ chính xác. Thư viện spektral được sử dụng để
mơ hình hóa dữ liệu đầu vào của mơ hình bằng cấu trúc dạng đồ thị.

iii


ABSTRACT OF DISSERTATION
The topic of predicting air quality using Graph Neural Networks focuses
on critical tasks including extracting data from sensors concerning parameters
in the air and extracting based on geographical interconnections of data,
indicators in the air, such as 𝑃𝑀2.5, 𝑃𝑀10, 𝑁𝑂2, 𝐶𝑂, 𝑆𝑂2, 𝑂3, 𝐴𝑄𝐼. When
dealing with time series data problems in the past, conventional approaches
frequently applied ARIMA, CNN, and LSTM models. predict worth.
Traditional approaches haven't yet fully utilized time series data' additional

potential benefits, such as utilizing the data similarity between concurrently
collecting equipment. The significance of the sensor's spatial links to feature
extraction, however, has not been made evident by earlier methods. As a
result, students in this thesis concentrate on employing Graph Neural
Networks to solve the problem of forecasting time series data and developing
a new and enhanced model above the reference model.
Utilizing the air index data along with the sensor's spatial distribution data
in the prediction problem. In order to take use of the current potential data
source of the internet of things system, students use the graph convolution
class to filter out the volume of data in the linked device's network. This gives
the model more information and increases accuracy. The input data of the
model is modeled using a graph structure using the spektral library.

iv


LỜI CAM ĐOAN
Tôi xin cam đoan luận văn tốt nghiệp: “DỰ ĐỐN CHẤT LƯỢNG
KHƠNG KHÍ 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 sử dụng tài liệu tham khảo 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 sai 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

Phạm Linh Sơn

v



Mục lục
Chương 1. GIỚI THIỆU ĐỀ TÀI ....................................................................1
1.1 Giới thiệu đề tài.........................................................................................1
1.2 Mơ tả bài tốn dự đốn chất lượng khơng khí dựa trên Graph
Neural Network ...............................................................................................2
1.3 Mục tiêu và nhiệm vụ của luận văn ........................................................3
1.4 Giới hạn đề tài ...........................................................................................4
1.5 Đóng góp của luận văn .............................................................................4
1.6 Tóm tắt nội dung.......................................................................................5
Chương 2. CƠ SỞ KIẾN THỨC ......................................................................7
2.1. Đồ thị .........................................................................................................7
2.2. Lý thuyết phổ đồ thị ................................................................................8
2.3. Graph Neural Network .........................................................................10
2.4. Mơ hình Artificial Neural Network .....................................................12
2.5. Mơ hình ghi nhớ dài-ngắn hạn .............................................................17
Chương 3. CƠNG TRÌNH NGHIÊN CỨU LIÊN QUAN ...........................20
3.1. Hồi quy dịch chuyển trung bình...........................................................21
3.2. Mạng ghi nhớ dài-ngắn hạn..................................................................21
3.3. Mạng nơ-ron tích chập ..........................................................................22
3.4. Học sâu trên đồ thị.................................................................................22
3.5. Mạng khuếch tán tích chập ..................................................................23
3.6. Mạng nơ-ron tích chập đồ thị khơng gian-thời gian ..........................23
3.7. Mạng quang phổ và mạng liên kết cục bộ ...........................................24
3.8. Mạng nơ-ron tích chập đồ thị với bộ lọc quang phổ nhanh-cục bộ..24
Chương 4. MƠ HÌNH ĐỀ XUẤT ...................................................................26
4.1. Mơ hình tham khảo ...............................................................................26
4.1.1. Mơ hình 1: GNN ................................................................................26
4.1.2. Mơ hình 2: CNN kết hợp LSTM .......................................................29
vi



4.1.3. Mơ hình 3: CNN ................................................................................29
4.1.4. Mơ hình 4: LSTM ..............................................................................31
4.2. Phương pháp đánh giá ..........................................................................31
4.2.1. Mean Absolute Error (MAE) ............................................................31
4.2.2. Mean Squared Error (MSE) ..............................................................32
4.2.3. Root Mean Squared Error (RMSE) ...................................................32
4.2.4. Mean Absolute Percentage Error (MAPE)........................................32
4.3. Mơ hình đề xuất .....................................................................................33
4.3.1. Động lực và ý tưởng ..........................................................................33
4.3.2. Mô tả mơ hình ...................................................................................35
4.3.3. Tham số cấu hình của mơ hình..........................................................37
4.3.4. Kết quả thực nghiệm và thảo luận .....................................................38
Chương 5. KẾT LUẬN ....................................................................................43
Tài liệu tham khảo ..........................................................................45

vii


Danh sách hình vẽ
2.1: Vector đặc trưng của mỗi đỉnh thuộc đồ thị .............................................. 8
2.2: Tính ma trận Laplacian từ ma trận bậc và ma trận kề ............................... 9
2.3: Đồ thị được áp dụng bộ lọc F vào mỗi đỉnh ............................................ 11
2.4: Phương thức lan truyền của mơ hình....................................................... 12
2.5: Các thành phần cơ bản của một nơ-ron sinh học .................................... 13
2.6: Cấu trúc của một perceptron ................................................................... 14
2.7: Một số hàm kích hoạt được sử dụng trong perceptron............................ 15
2.8: Cấu trúc mơ hình Artificial Neural Network .......................................... 16
2.9: Cơ chế hoạt động trong mơ hình Long Short-Term Memory ................. 18

3.1: Sơ đồ taxonomy của các cơng trình nghiên cứu liên quan...................... 20
4.1: Mơ hình tham khảo .................................................................................. 27
4.2: Mơ hình kết hợp CNN-LSTM ................................................................. 29
4.3: Mơ hình dự đốn dữ liệu chuỗi thời gian ................................................ 30
4.4: Mơ hình sử dụng LSTM .......................................................................... 31
4.5: Mơ hình đề xuất dựa trên mạng nơ-ron tích chập đồ thị ......................... 36
4.6: Phân bố của 2 hệ thống cảm biến trên không gian địa lý ........................ 39
4.7: Kết quả mơ hình đề xuất trên hệ thống cảm biến dày đặc ...................... 40
4.8: Kết quả mơ hình đề xuất trên hệ thống cảm biến thưa thớt .................... 40
4.9: Kết quả mơ hình GNN, GNN.base, CNN, LSTM, CNN-LSTM ............ 41

viii


Danh sách bảng
4.1: Các tham số trong mơ hình...................................................................... 38
4.2: Kết quả thực nghiệm của các mơ hình .................................................... 38

ix


Chương 1

GIỚI THIỆU ĐỀ TÀI
1.1 Giới thiệu đề tài
Ngày nay, sự phát triển của IoT (Internet of Things) trên thế giới mở ra định
hướng mới cho thu thập và phân tích dữ liệu từ hệ thống cảm biến. Các cảm
biến được triển khai rộng rãi ở nhiều nơi, sinh ra lượng dữ liệu lớn đã đưa ra
thách thức trong xử lý dữ liệu là làm thế nào để phân tích dữ liệu chuỗi thời
gian (Time Series). Mặc dù các cảm biến độc lập với nhau, nhưng có thể xây

dựng được một mạng đồ thị kết nối chặt chẽ giữa chúng. Từ đó, ta có thể khai
thác những đặc trưng của dữ liệu kết hợp với mối liên kết đến các chuỗi dữ liệu
lân cận, phân tích dữ liệu chuỗi thời gian nhằm mục đích dự đốn sớm được
những thơng tin trong dữ liệu theo chuỗi đa biến thời gian thực. Những lĩnh vực
mà ở đó dữ liệu chuỗi thời gian được sử dụng phân tích bao gồm: giao thơng,
thời tiết, địa chấn, dự báo và phân loại, một số kỹ thuật trước đây để giải quyết
những bài toán này như là: ARIMA (Rob & George, 2015), LSTM (Wensheng
Yang, Chengxin Ma & Yulong Shi, 2019). Dữ liệu chuỗi thời gian thường có
tính xu hướng, đây là tính chất thường thấy của dạng dữ liệu này. Tính xu hướng
ảnh hưởng khơng nhỏ đến phân tích và nhận định mối tương quan giữa các
chuỗi dữ liệu. Ngoài ra, dữ liệu chuỗi thời gian cịn có đặc tính chu kỳ, đây là
tính chất lặp đi lặp lại của dữ liệu, việc phát hiện ra chu kỳ của dữ liệu rất cần
thiết trong dự báo, cộng thêm khó khăn từ nhiễu do ảnh hưởng từ các yếu tố
mơi trường xung quanh. Do đó, những phương pháp dự đoán hiệu quả dành cho
loại dữ liệu chuỗi thời gian là rất cần thiết. Ngoài vấn đề về tính chất của dữ
liệu chuỗi thời gian, một thách thức khác của bài toán “Dự đoán chất lượng
1


khơng khí dựa trên Graph Neural Network” là làm sao xây dựng được mơ hình
tổng qt có khả năng thể hiện được sự phụ thuộc giữa các chuỗi dữ liệu khác
nhau, cũng như mối quan hệ tương đồng về dữ liệu. Mặc dù các cảm biến độc
lập với nhau, nhưng có thể xây dựng được một mạng đồ thị kết nối chặt chẽ
giữa chúng. Đây chính là mục tiêu quan trọng của bài toán dự đoán dữ liệu
chuỗi thời gian trong khoa học máy tính.

1.2 Mơ tả bài tốn dự đốn chất lượng khơng khí
dựa trên Graph Neural Network
Đầu vào của mơ hình là tập dữ liệu có cấu trúc đồ thị có dạng
[𝑏𝑎𝑡𝑐ℎ, 𝑛𝑜𝑑𝑒𝑠, 𝑛_𝑓𝑒𝑎𝑡], chứa 𝑏𝑎𝑡𝑐ℎ là kích thước của mỗi khối dữ liệu,

𝑛𝑜𝑑𝑒𝑠 là số đỉnh của đồ thị và 𝑛_𝑓𝑒𝑎𝑡 là các đặc trưng trên mỗi đỉnh. Dữ liệu
đầu vào được mơ hình hóa dựa trên ma trận Laplacian 𝐿 = 𝐷 − 𝐴. Laplacian
là ma trận biểu diễn mối liên hệ của đồ thị 𝐺 = (𝑉, 𝐸), với |𝑉| = 𝑛. Trong đó,
D là ma trận bậc (degree matrix) với 𝐷(𝑖, 𝑖) là bậc của đỉnh 𝑖𝑡ℎ, A là ma trận
kề với 𝐴(𝑖, 𝑗) = 1 nếu và chỉ nếu (𝑖, 𝑗) ∈ 𝐸.
Dự đoán dữ liệu chuỗi thời gian đa biến chủ yếu tập trung vào thông tin
thu được từ mạng lưới các cảm biến và yếu tố khơng gian, từ đó xây dựng
được cấu trúc dạng đồ thị. Trong đó, mỗi đỉnh của đồ thị đại diện cho mỗi
trạm thu dữ liệu, trọng số của đường nối giữa hai đỉnh là khoảng cách địa lý
trong thực tế.
Ví dụ với các chỉ số dữ liệu (𝑃𝑀2.5, 𝑃𝑀10, 𝑁𝑂2, 𝐶𝑂, 𝑆𝑂2, 𝑂3, 𝐴𝑄𝐼,
𝑙𝑎𝑡𝑖𝑡𝑢𝑑𝑒, 𝑙𝑜𝑛𝑔𝑖𝑡𝑢𝑑𝑒) tại mỗi đỉnh, trong đó latitude và longitude giúp xác

2


định vị trí đỉnh trong đồ thị, đầu ra của mơ hình sẽ là giá trị dự đốn chỉ số
chất lượng khơng khí AQI (Air Quality Indexing).

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 mơ hình
dự đốn dữ liệu chuỗi thời gian đa biến sử dụng các phương pháp học sâu và
lý thuyết phổ của đồ thị. Cụ thể:
- Hiểu và sử dụng được các mơ hình học sâu, các lý thuyết đồ thị và phổ
đồ thị cho biểu diễn dữ liệu.
- Xác định rõ công việc sẽ tập trung giải quyết trong bài toán dự đoán dữ
liệu chuỗi thời gian đa biến: đầu vào và đầu ra của mơ hình là gì? Mơ
hình sử dụng dataset có dữ liệu về cảm biến hay khơng? Đặc trưng của
dataset có những chỉ số khơng khí là gì?
- Nắm bắt những phương pháp gần đây để giải quyết bài tốn, đặc biệt là

những phương pháp sử dụng các mơ hình học sâu. Trên cơ sở đó có thể
chỉ ra được những ưu nhược điểm của từng phương pháp.
- Đưa ra đề 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.
- Cuối cùng, học viên sẽ hiểu rõ hơn những vấn đề, thách thức khi áp
dụng học sâu, học máy vào giải quyết một bài toán thực tế. Đánh giá
tính khả thi của các phương pháp trong thực tiễn, đồng thời sẽ có góc
nhìn chính xác hơn về học sâu, học máy nói chung.
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
quá trình làm luận văn:

3


- Tìm hiểu bài tốn dự đốn dữ liệu chuỗi thời gian, các cơng trình
nghiên cứu 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.
- Đề xuất các mơ hình giúp cải thiện độ chính xác cho bài tốn dự đốn
dữ liệu chuỗi thời gian.
- Thực nghiệm, đánh giá kết quả của mô hình đề xuất.
- Kết luận, nêu ra các vấn đề còn tồn đọng, đồng thời đưa ra các dự định
nghiên cứu tương lai.

1.4 Giới hạn đề tài
Dự đoán dữ liệu chuỗi thời gian là phương pháp nghiên cứu phổ biến và
có nhiều phương pháp khác nhau, vì vậy nội dung luận văn sẽ được giới hạn
như sau:
- Tập trung vào cơng việc trích xuất đặc trưng dữ liệu chuỗi thời gian đa
biến và mơ hình hóa dữ liệu dựa trên phổ đồ thị.
- Các mơ hình học sâu: CNN, LSTM, GNN.

- Mơ hình được đánh giá dựa trên độ đo MSE, RMSE, MAE, MAPE cho
tác vụ trích xuất đặc trưng của dữ liệu chuỗi thời gian.

1.5 Đóng góp của luận văn
Trong luận văn, học viên đề xuất phương pháp giúp cải thiện hiệu quả của
mơ hình dự đốn.
- Sử dụng mạng nơ-ron tích chập đồ thị vào trích xuất dữ liệu chuỗi thời
gian tần suất cao.

4


- Sử dụng phương pháp mơ hình hóa dữ liệu chuỗi thời gian dựa trên lý
thuyết phổ đồ thị.
- Kết hợp thông tin phân bố không gian trong mạng các cảm biến vào
đặc trưng dữ liệu chuỗi thời gian.

1.6 Tóm tắt nội dung
Nội dung của luận văn gồm 5 chương:
− Chương 1 GIỚI THIỆU ĐỀ TÀI: giới thiệu về nhu cầu dự đốn trong
dữ liệu chuỗi thời gian, mơ tả bài tốn dự đốn chất lượng khơng khí dựa trên
mạng nơ-ron tích chập đồ thị, tập dữ liệu dạng chuỗi thời gian được sử dụng
cũng như phương pháp đánh giá.
− Chương 2 CƠ SỞ KIẾN THỨC: bàn về cơ sở kiến thức cơ bản trong
học sâu, từ mạng nơ-ron tích chập tới mạng nơ-ron tích chập đồ thị, Hồi quy
dịch chuyển trung bình, Mạng ghi nhớ dài-ngắn hạn.
− Chương 3 CÁC CƠNG TRÌNH NGHIÊN CỨU LIÊN QUAN: nói
về các cơng trình nghiên cứu liên quan, bắt đầu từ cơng trình nghiên cứu
mạng học sâu trên đồ thị của Stefan Bloemheuvel, Jurgen van den Hoogen,
Dario Jozinovi´c, Alberto Michelini & Martin Atzmueller, 2022, mở ra hàng

loạt cơng trình tiếp theo cho hướng nghiên cứu cho bài toán dự đoán trong dữ
liệu chuỗi thời gian, và đó cũng là cơ sở quan trọng cho nghiên cứu của học
viên trong luận văn.
− Chương 4 CÁC MƠ HÌNH ĐỀ XUẤT: Chương 4 nói cụ thể về các
mơ hình đề xuất của học viên cho bài tồn dự đốn chất lượng khơng khí và
các kết quả thực nhiệm.

5


− Chương 5 KẾT LUẬN: Tổng kết các đóng góp của luận văn, các vấn
đề còn tồn tại của bài toán dự đoán dữ liệu chuỗi thời gian đồng thời nói về
nghiên cứu trong tương lai.

6


Chương 2

CƠ SỞ KIẾN THỨC
Trong luận văn, tác giả lựa chọn trình bày theo hướng sử dụng mơ hình
Graph Neural Networks cho bài tốn dự đốn chất lượng khơng khí. Trong
nhiều nghiên cứu trước đây chủ yếu sử dụng các cơng cụ tốn học hoặc sử dụng
học máy xoay quanh mơ hình mạng nơ-ron tích chập. Tuy nhiên, các mơ hình
đó vẫn tồn tại nhược điểm là chưa biểu diễn được mối liên kết tự nhiên giữa
tính khơng gian và thời gian của dữ liệu. Để giải quyết vấn đề đó, mơ hình mạng
nơ-ron tích chập đồ thị dựa trên lý thuyết phổ đồ thị được chọn là hướng nghiên
cứu chính của luận văn.

2.1. Đồ thị

Một phần của học sâu với đồ thị là tập trung vào cấu trúc dữ liệu dạng đồ
thị. Đồ thị thể hiện mối quan hệ giữa tập các đỉnh (vertices) được kết nối bởi
các cạnh (edges) với nhau.
Đồ thị được định nghĩa 𝐺 = (𝑉, 𝐸) trong đó V là tập đỉnh và E là tập cạnh.
Mỗi cạnh 𝑒𝑖𝑗 = (𝑥𝑖 , 𝑥𝑗 ) kết nối đỉnh 𝑥𝑖 và 𝑥𝑗 . Một cách phổ biến để biểu diễn
đồ thị là sử dụng ma trận kề (Adjacency matrix) 𝐴 ∈ ℝ𝑁×𝑁 với 𝑁 = |𝑉|, ma
trận kề là ma trận vng có giá trị của đường chéo chính bằng một 𝐴𝑖𝑗 = 1 nếu
tồn tại cạnh nối đỉnh 𝑥𝑖 đến 𝑥𝑗 , ngược lại 𝐴𝑖𝑗 = 0.
Số lượng đỉnh lân cận thuộc đỉnh 𝑥 được xác định bởi bậc của đỉnh 𝑥 và
biểu diễn như sau 𝐷𝑖𝑖 = ∑𝑗 𝐴𝑖𝑗 , trong đó D là ma trận bậc. Cạnh có thể có hướng

7


hoặc vơ hướng. Cạnh có hướng là cạnh chỉ hướng từ đỉnh nguồn đến đỉnh đích.
Cạnh vơ hướng là cạnh khơng có khái niệm liên quan đến đỉnh nguồn và đích.
Các đỉnh, cạnh và tồn bộ biểu đồ có thể có các các đặc trưng (features) của
dữ liệu, ví dụ: vector 𝑥 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) là một vector đặc trưng của đỉnh 𝑎.

𝑥1 𝑥2 … 𝑥𝑛

Hình 2.1: Vector đặc trưng của mỗi đỉnh thuộc đồ thị

2.2. Lý thuyết phổ đồ thị
Lý thuyết phổ đồ thị (Spectral Graph Theory) [5] là hướng nghiên cứu về
tính chất của đồ thị trong qua công cụ đại số với mối quan hệ của giá trị riêng
(eigenvalues) và vector riêng (eigenvectors), điển hình như ma trận kề, ma trận
Laplacian.
Ma trận Laplacian: Cho đồ thị 𝐺 = (𝑉, 𝐸), với |𝑉| = 𝑛, ma trận Laplacian
là ma trận thể hiện mối liên hệ của đồ thị G, có kích thước 𝑛 × 𝑛.

𝐿 =𝐷−𝐴

(2.1)

8


Trong đó, D là ma trận bậc (degree matrix) với 𝐷(𝑖, 𝑖) là bậc của đỉnh 𝑖𝑡ℎ,
A là ma trận kề với 𝐴(𝑖, 𝑗) = 1 nếu và chỉ nếu (𝑖, 𝑗) ∈ 𝐸. Vì vậy, ta có thể biểu
diễn ma trận Laplacian như sau:
deg(𝑖)
𝐿(𝑖, 𝑗) = {−1
0

𝑛ế𝑢 𝑖 = 𝑗
𝑛ế𝑢 (𝑖, 𝑗) ∈ 𝐸
𝑛𝑔ượ𝑐 𝑙ạ𝑖

1

(2.2)

4𝑥1 𝑥2 … 𝑥𝑛

2
5

3

3 -1 -1 -1 0


0

1

1

1

0

3 -1 -1 -1 0

-1 2 -1 0

1

0

1

0

0

-1 2 -1 0

1

1


0

0

1

0

=

-1 -1 3

0 -1

-1 0

2 -1

1

0

0

0

0 -1 -1 2

0


0

1

1

0

0

𝐷

𝐿

−

0

-1 -1 3

0 -1

1

-1 0

2 -1

0


0

0

0 -1 -1 2

𝐴

Hình 2.2: Tính ma trận Laplacian từ ma trận bậc và ma trận kề.

Trong đồ thị G, phép nhân một vector với ma trận Laplacian thể hiện sự sai
biệt của một đỉnh đối với các đỉnh lân cận.
𝐿𝑥 = 𝑤

(2.3)
9


Phần tử thứ 𝑖𝑡ℎ của phép nhân 𝐿𝑥 bằng tổng của các hiệu từ phần tử thứ 𝑖𝑡ℎ
đến các phần tử còn lại:

𝑤(𝑖) = deg(𝑖) 𝑥(𝑖) − ∑𝑗:(𝑖,𝑗)∈𝐸 𝑥𝑗 = ∑𝑗:(𝑖,𝑗)∈𝐸 (𝑥(𝑖) − 𝑥(𝑗))

(2.4)

Nếu một đỉnh của đồ thị G có vector đặc trưng là 𝑣 thì dạng tồn phương
(quadratic form) 𝑣 𝑡 𝐿𝑣 thể hiện chính xác mối liên hệ của đỉnh này đến các đỉnh
lân cận. 𝑣 𝑡 𝐿𝑣 được tính chính xác bằng tổng bình phương của các hiệu với
những giá trị của đỉnh lân cận.


𝑥 𝑡 𝐿𝑥 = ∑𝑖<𝑗:(𝑖,𝑗)∈𝐸 (𝑥(𝑖) − 𝑥(𝑗))2

(2.5)

2.3. Graph Neural Network
Graph Neural Network - GNNs là mơ hình học sâu dựa trên cơ sở của đồ
thị. Trước đây có 2 phương pháp sử dụng GNNs là: Phương pháp phổ (Spectral
method) và phương pháp không gian (Spatrial methods). Phương pháp phổ sử
dụng vector riêng (eigenvectors) và trị riêng (eigenvalues) của ma trận và thực
hiện tích chập với phép biến đổi Fourier đồ thị ( Graph Fourier Transformation)
và nghịch đảo biến đổi Fourier đồ thị (inverse Graph Fourier transform). Phép
biến đổi của đầu vào 𝑥 được định nghĩa là 𝐹(𝑥) = 𝑈 𝑇 𝑥 và 𝐹 −1 (𝑥) = 𝑈𝑥. Trong
đó, U đại diện cho ma trận vector riêng của ma trận chuẩn hóa Laplacian:

𝐿 = 𝐼 − 𝐷 −1/2 𝐴𝐷−1/2
10

(2.6)


Trong đó, D là ma trận bậc của ma trận kề A và I là ma trận đơn vị.
Phương pháp không gian sử dụng kỹ thuật message passing để xác định các
đỉnh lân cận và thực hiện tính tốn giới hạn đến lân cận thứ k. Mỗi đỉnh sẽ được
cập nhập giá trị mới bởi hàm 𝑓, một phép cập nhập được biểu diễn bởi hàm 𝑍 =
𝑓(𝐺)𝑋. Trong đó, 𝐺 là ma trận chuẩn hóa Laplacian và 𝑋 là đặc trưng của đỉnh
(node features). Tuy nhiên, vấn đề gặp phải với phương pháp khơng gian là định
nghĩa lớp tích chập kết hợp với k đỉnh lân cận.

𝐹 × 𝑥1 𝑥2 … 𝑥𝑛


𝐹 × 𝑥1 𝑥2 … 𝑥𝑛

1
4

𝐹 × 𝑥1 𝑥2 … 𝑥𝑛
2

𝐹 × 𝑥1 𝑥2 … 𝑥𝑛

5

3

𝐹 × 𝑥1 𝑥2 … 𝑥𝑛

Hình 2.3: Đồ thị được áp dụng bộ lọc F vào mỗi đỉnh.
𝐹 được xác định bởi một hàm số 𝑔𝜃 = 𝑑𝑖𝑎𝑔(𝜃) trong đó 𝜃 là bộ tham số
cần học.
Khi áp dụng hàm số 𝑔𝜃 tại mỗi đỉnh, đồng nghĩa thực hiện phép tốn 𝑔𝜃 ×
𝑥 = 𝑈𝑔𝜃 (Λ)𝑈 𝑇 , trong đó 𝑥 là vector đặc trưng, Λ là ma trận giá trị riêng, 𝑈 là
mà trận vector riêng của ma trận chuẩn hóa đồ thị Laplacian. Vì vậy, ta có thể
hiểu 𝑔𝜃 (Λ) là hàm số xác định ma trận giá trị riêng của L.

11


Tối ưu bằng cách áp dụng đa thức Chebyshev (Hammond, Vandergheynst
& Gribonval, 2011) và phương pháp chuẩn hóa, vì thế có thể tăng tốc độ học

và tránh hiện tượng khơng học được gì (vanishing gradients).
Phương pháp khơng gian tập trung vào sự kết nối của đồ thị trong khi
phương pháp phổ dựa vào giá trị riêng và vector riêng của đồ thị. Phương thức
lan truyền được biểu diễn như sau:

̃ −1/2 𝐴̃𝐷
̃ −1/2 𝐻(𝑙) 𝑊 (𝑙) )
𝐻(𝑙+1) = 𝜎(𝐷

𝐻1 = 𝜎(… )
H0

(2.7)

𝐻2 = 𝜎(… )
H2

H1

Hình 2.4: Phương thức lan truyền của mơ hình.

Trong đó, 𝐻 (𝑙) là ma trận của lớp kích hoạt thứ 𝑙𝑡ℎ, 𝜎 biểu thị hàm kích
̃ = ∑𝑗 𝐴̃𝑖𝑗 là ma trận bậc; 𝐴̃ = 𝐴 + 𝐼𝑁 là ma trận kề của đồ thị vô hướng
hoạt, 𝐷
G được kết hợp với ma trận đơn vị để thể hiện kết nối của một đỉnh với chính
nó, 𝑊 (𝑙) là ma trận trọng số huấn luyện.

2.4. Mô hình Artificial Neural Network
Mơ hình Mạng nơ-ron nhân tạo (Hopfield, 1988) là mơ hình tính tốn được
xây dựng dựa trên ý tưởng lấy từ cấu trúc và cách hoạt động của mạng nơ-ron


12


thần kinh trong não người nhằm thực hiện một tác vụ nào đó với tập dữ liệu đầu
vào.
Một mạng nơ-ron thần kinh được tạo nên từ nhiều nơ-ron sinh học kết nối
và hoạt động cùng nhau. Mỗi nơ-ron sinh học đó được cấu tạo bởi các thành
phần cơ bản được mơ tả trong Hình 3.1 bao gồm đi gai, thân nơ-ron và sợi
trục.
Các đi gai
(Dendrites)

Sợi trục
(Axon)

Thân nơ-ron
(Cell body)

Hình 2.5: Các thành phần cơ bản của một nơ-ron sinh học.

Nơ-ron thần kinh hoạt động bằng cách tiếp nhận các thông tin đưa vào từ
các đi gai (dendrites), tính tốn và tổng hợp tại thân nơ-ron (cell body), sau
đó lan truyền kết quả đến các nơ-ron khác thơng qua sợi trục (axon).
Có thể dễ dàng rút ra nhận xét rằng mạng nơ-ron thần kinh nhận nhiều thông
tin đầu vào nhưng chỉ đưa ra một kết quả duy nhất.
Tương tự như cách thức hoạt động của mạng nơ-ron thần kinh nêu trên,
ANN cũng được cấu thành từ nhiều nơ-ron được gọi là perceptron có cấu trúc
như Hình 3.2. Trong đó:


13


- 𝑥1 , 𝑥2 , 𝑥3 , … 𝑥𝑛 là các thông tin dữ liệu đầu vào.
- Phép cộng và hàm kích hoạt chính là các phép tính tốn và tổng hợp các
thông tin dữ liệu đầu vào.
- 𝑤0 , 𝑤1 , 𝑤2 , 𝑤3 , … 𝑤𝑛 là các trọng số cần phải học, đóng vai trị tham gia q
trình tính tốn và chuyển đổi các thơng tin đầu vào thành thông tin đầu ra.
- 𝑦 là dữ liệu đầu ra.

𝑤0

𝑥1

hàm kích hoạt
𝑤1

𝑥2

𝑤2
𝑥3

Σ

𝑤3

𝑦

……..


𝑤𝑛

𝑥𝑛
phép cộng

Hình 2.6: Cấu trúc của một perceptron.

Cụ thể hơn, phương thức tính tốn và tổng hợp dữ liệu của một perceptron
được mô tả theo từng bước sau:
1. Sau khi tiếp nhận tập các dữ liệu đầu vào {𝑥1 , 𝑥2 , … , 𝑥𝑛 }, perceptron thực
hiện phép cộng bằng cách tính tổng giá trị tất cả các tích số của từng cặp dữ
liệu đầu vào và giá trị trọng số tương ứng.
𝑎 = ∑𝑛𝑖=1 𝑤𝑖 𝑥𝑖 + 𝑤0
14

(2.8)