HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIỄN THƠNG
KHOA VIỄN THƠNG I

ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
Đề tài: “Ứng dụng AI trong quản lý tài ngun
và búp sóng vơ tuyến cho mạng 5G”
Giảng viên hướng dẫn

Ths. Lê Tùng Hoa

Sinh viên
Lớp
Khóa
Mã Sinh Viên
Hệ

Đỗ Minh Tồn
D17CQVT07-B
D17 (2017-2022)
B17DCVT359
Đại học chính quy

Hà Nội, tháng 11/2021




Hệ thống hỗ trợ nâng cao chất lượng tài liệu

KẾT QUẢ KIỂM TRA TRÙNG LẶP TÀI LIỆU

THÔNG TIN TÀI LIỆU

Tác giả

Đỗ Minh Toàn

Tên tài liệu

Đồ án - Đỗ Minh Toàn - B17DCVT359

Thời gian kiểm tra

20-12-2021, 15:00:50

Thời gian tạo báo cáo

20-12-2021, 15:02:26

KẾT QUẢ KIỂM TRA TRÙNG LẶP

Điểm

15

Nguồn trùng lặp tiêu biểu [text.123doc.org, dominhhai.github.io, nguyenvanhieu.vn]
(*) Kết quả trùng lặp phụ thuộc vào dữ liệu hệ thống tại thời điểm kiểm tra.


NHẬN XÉT

(Của giáo viên hướng dẫn)
Đồ án tốt nghiệp “Ứng dụng AI trong quản lý tài nguyên và búp sóng vơ tuyến cho
mạng 5G” của sinh viên Đỗ Minh Tồn nhằm đưa ra cái nhìn về việc áp dụng một số
thuật toán AI cụ thể là K-mean, DBSCAN dùng cho các trường hợp phân cụm, quản lý
búp sóng và thuật toán Q-learning và mạng LSTM sử dụng cho phân bổ tài ngun vơ
tuyến.
Thời gian làm đồ án cịn ngắn nhưng sinh viên đã thể hiện được sự chủ động tìm tịi
tài liệu và thực hiện q trình nghiên cứu chỉn chu. Kết quả mô phỏng tuy chỉ dừng lại
tại việc phân tích kết quả có sẵn nhưng cũng phần nào thể hiện sự nỗ lực tìm và hiểu sâu
hơn về mảng AI của sinh viên.
Đề nghị hội đồng chấm đồ án và giáo viên phản biện cho sinh viên được báo cáo và
hồn thành đồ án của mình tốt nhất có thể.

Điểm: …… (Bằng chữ: ……………….)
Ngày ….. tháng ….. năm 2021


NHẬN XÉT
(Của Giảng viên phản biện)
....................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................

...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
....................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................

Điểm: …… (Bằng chữ: ……………….)
Ngày ….. tháng ….. năm 2021


Đồ án tốt nghiệp Đại học

LỜI CẢM ƠN
Trong thời gian làm đồ án tốt nghiệp, em đã nhận được nhiều sự giúp đỡ, đóng góp
ý kiến và chỉ bảo nhiệt tình của thầy cơ, gia đình và bạn bè.
Em xin gửi lời cảm ơn chân thành đến cô Lê Tùng Hoa giảng viên Bộ môn Vô
Tuyến - Học viện Công nghệ Bưu chính Viễn Thơng, người đã tận tình hướng dẫn, chỉ
bảo em trong suốt quá trình làm đồ án.
Em cũng xin chân thành cảm ơn các thầy cô giáo trong Học viện nói chung, các
thầy cơ trong Bộ mơn Vơ Tuyến nói riêng đã dạy dỗ cho em kiến thức về các môn đại
cương cũng như các môn chuyên ngành, giúp em có được cơ sở lý thuyết vững vàng và

tạo điều kiện giúp đỡ em trong suốt quá trình học tập.
Cuối cùng, em xin chân thành cảm ơn gia đình và bạn bè, đã ln tạo điều kiện,
quan tâm, giúp đỡ, động viên em trong suốt quá trình học tập và hoàn thành đồ án tốt
nghiệp.
Với điều kiện thời gian cũng như kinh nghiệm còn hạn chế của một học viên, đồ án
này không thể tránh được những thiếu sót. Em rất mong nhận được sự chỉ bảo, đóng góp
ý kiến của các thầy cơ để em có điều kiện bổ sung, nâng cao ý thức của mình, phục vụ
tốt hơn công tác thực tế sau này.
Hà Nội, ngày 8 tháng 11 năm 2021
Sinh viên thực hiện
Đỗ Minh Toàn

Đỗ Minh Toàn - D17CQVT07-B

i


Đồ án tốt nghiệp Đại học

MỤC LỤC
LỜI CẢM ƠN ................................................................................................................ i
MỤC LỤC ..................................................................................................................... ii
DANH MỤC HÌNH ..................................................................................................... iv
DANH MỤC BẢNG BIỂU ...........................................................................................v
DANH MỤC VIẾT TẮT ............................................................................................. vi
PHẦN MỞ ĐẦU ........................................................................................................ viii
CHƯƠNG 1: TỔNG QUAN VỀ MACHINE LEARNING VÀ REINFORCEMENT
LEARNING ....................................................................................................................1
1. Machine learning ............................................................................................1
1.1. Lịch sử ra đời và phát triển ........................................................................1

1.2. Các phương pháp phổ biến nhất ................................................................3
1.3. Thuật toán K-mean ....................................................................................4
1.3.1. Thuật tốn k-means là gì?...................................................................4
1.3.2. Ý tưởng của thuật toán k-means .........................................................5
1.4. Thuật toán DBSCAN .................................................................................6
1.4.1. Thuật toán DBSCAN là gì? ................................................................6
1.4.2. Các định nghĩa trong DBSCAN .........................................................6
1.4.3. Phân loại dạng điểm trong DBSCAN.................................................7
1.4.4. Các bước trong thuật tốn DBSCAN .................................................9
2. Reinforcement Learning ..............................................................................10
2.1. Reinforcement Learning là gì? ................................................................10
2.2. Thuật toán Q – learning ...........................................................................12
2.3. Mạng hồi quy LSTM ...............................................................................14
2.3.1. Mạng RNNs ......................................................................................14
2.3.2. Mạng LSTM .....................................................................................15
2.3.3. Ý tưởng cốt lõi của LSTM ...............................................................17
2.3.4. Bên trong LSTM...............................................................................18
3. Kết luận chương 1.........................................................................................20
CHƯƠNG 2: TỔNG QUAN VỀ MẠNG 5G.............................................................21
1. Thực trạng triển khai mạng 5G trên thế giới và tại Việt Nam ................21
Đỗ Minh Toàn - D17CQVT07-B

ii


Đồ án tốt nghiệp Đại học
1.1. Thực trạng triển khai mạng 5G trên thế giới ...........................................21
1.2. Thực trạng triển khai mạng 5G tại Việt Nam ..........................................22
2. Các yêu cầu kỹ thuật và các trường hợp sử dụng mạng 5G ....................23
2.1. Các yêu cầu kỹ thuật của mạng 5G .........................................................23

2.2. Các trường hợp sử dụng mạng 5G ..........................................................25
2.2.1. Các trường hợp sử dụng của Internet di động ..................................25
2.2.2. Các trường hợp sử dụng của Internet of Things ...............................26
3. Kết luận chương 2.........................................................................................31
CHƯƠNG 3: ỨNG DỤNG AI TRONG QUẢN LÝ TÀI NGUYÊN VÀ BÚP SĨNG
VƠ TUYẾN CHO MẠNG 5G ....................................................................................32
1. Giới thiệu bài tốn ........................................................................................32
2. Mơ hình hệ thống ..........................................................................................33
2.1. Mơ hình mạng..........................................................................................33
2.2. Yêu cầu QoS ............................................................................................34
3. Deep Q learning với DBSCAN (DQLD) .....................................................35
4. Mô phỏng và đánh giá ..................................................................................38
4.1. Thiết lập mơ phỏng ..................................................................................38
4.2. Thuật tốn đường cơ sở ...........................................................................39
4.3. Kết quả hoạt động ....................................................................................40
5. Kết luận chương 3.........................................................................................43
KẾT LUẬN VÀ KIẾN NGHỊ ..............................................................................44
DANH MỤC TÀI LIỆU THAM KHẢO ............................................................45

Đỗ Minh Toàn - D17CQVT07-B

iii


Đồ án tốt nghiệp Đại học

DANH MỤC HÌNH
Hình 1. 1: lịch sử phát triển của machine learning ................................................................1
Hình 1. 2: Các phương pháp phổ biến của machine learning ..............................................3
Hình 1. 3: Kết quả phân cụm của thuật tốn kmeans [2]......................................................5

Hình 1. 4: Hình minh hoạ cách xác định ba loại điểm [3]....................................................8
Hình 1. 5 Quá trình lan truyền để xác định các cụm của thuật tốn DBSCAN [3] ...........9
Hình 1. 6: Quy trình bài tốn Reinforcement learning .......................................................10
Hình 1. 7: Trị chơi minh họa cách tìm đường cơ bản của RL [4].....................................11
Hình 1. 8: Trị chơi khi được áp dụng thuật tốn Bellman Equation.................................12
Hình 1. 9: Minh họa thuật tốn q-learning ...........................................................................13
Hình 1. 10: Recurrent Neural Network có các vịng lặp [5]...............................................15
Hình 1. 11: Recurrent Neural Network chưa được lặp [5] .................................................15
Hình 1. 12: Mơ-đun lặp lại trong RNN tiêu chuẩn chứa một lớp duy nhất ......................16
Hình 1. 13: Mơ-đun lặp lại trong một LSTM chứa bốn lớp tương tác .............................16
Hình 1. 14: Các ký hiệu của mạng RNN .............................................................................16
Hình 1. 15: Băng truyền của trạng thái tế bào .....................................................................17
Hình 1. 16: Các cổng sàng lọc thơng tin ..............................................................................17
Hình 1. 17: LSTM Lọc thơng tin cần loại bỏ ......................................................................18
Hình 1. 18: LSTM Quyết định thơng tin mới được lưu .....................................................19
Hình 1. 19: LSTM cập nhật trạng thái..................................................................................19
Hình 1. 20: LSTM quyết định đầu ra ...................................................................................19
Hình 2. 1: So sánh tốc độ mạng 4G và 5G tại các quốc gia và vùng lãnh thổ trên thế giới
[6] .............................................................................................................................................21
Hình 2. 2: Thái Lan có tỷ lệ chênh lệch tốc độ mạng 5G và 4G cao nhất thế giới [4] ...22
Hình 2. 3: Các nhóm ứng dụng 5G (theo ITU) [7] .............................................................23
Hình 2. 4: Tăng trưởng của kết nối IoT trên thế giới 2010-2030 [7].................................28
Hình 2. 5: Các họ trường hợp sử dụng 5G và các ví dụ về trường hợp liên quan ...........29
Hình 2. 6: Các kịch bản kỹ thuật cho mạng 5G...................................................................30
Hình 2. 7: Ánh xạ tám họ ca sử dụng thành ba kịch bản sử dụng .....................................31
Hình 3. 1: Mơ hình hệ thống của mạng mmWave [10]......................................................33
Đỗ Minh Tồn - D17CQVT07-B

iv



Đồ án tốt nghiệp Đại học

Hình 3. 2: Sơ đồ khái niệm về Deep Q-learning dựa trên LSTM [10] .............................38
Hình 3. 3: Độ trễ của người dùng URLLC so với tổng tải URLLC cung cấp ([0,5, 1]
Mbps) [10]...............................................................................................................................40
Hình 3. 4: Độ trễ của người dùng URLLC so với tổng tải URLLC cung cấp ([1,5, 2]
Mbps) [10]...............................................................................................................................41
Hình 3. 5: Tỷ lệ mất gói của người dùng URLLC so với tổng tải do URLLC cung cấp
[10] ...........................................................................................................................................42
Hình 3. 6: Tổng tỷ lệ người dùng URLLC so với tổng tải URLLC cung cấp [10] .........42
Hình 3. 7: Tổng tỷ lệ người dùng eMBB so với tổng tải eMBB được cung cấp [10].....43

DANH MỤC BẢNG BIỂU
Bảng 3. 1: Cài đặt cấu hình [10]............................................................................................39

Đỗ Minh Toàn - D17CQVT07-B

v


Đồ án tốt nghiệp Đại học

DANH MỤC VIẾT TẮT
Thuật ngữ viết tắt

Tiếng Anh

Tiếng Việt


AI

Artificial Intelligence

Trí tuệ nhân tạo

DBSCAN

Density-Based Spatial
Clustering of Applications
with Noise

Phân cụm dựa trên mật độ
không gian với các dạng
dữ liệu có nhiễu

DQLD

Deep Q-learning with
DBSCAN

Deep Q-learning với
DBSCAN

eMBB

Enhanced Mobile
Broadband

Băng rộng di động nâng

cao

gNBs

5G-NodeBs

5G-NodeBs

GRB

Group Resource Block

Nhóm khối tài nguyên

IoT

Internet of Things

Internet vạn vật

ITU

International
Liên minh Viễn thông
Telecommunication Union quốc tế

KPPF

Priority-based
Proportional Fairness


LoS

Line-of-Sight

LSTM

Long Short Term Memory Mạng bộ nhớ dài-ngắn
networks
hạn

mMTC

Massive Machine Type
Communications

Truyền thông máy số
lượng lớn

OFDMA

Orthogonal frequencydivision multiple access

Phân chia tần số trực giao
Đa truy cập

PCP

Poisson Cluster Process


Quy trình Cụm Poisson

Quality Class Indicator

Chỉ số phân loại chất
lượng

QoS

Quality of Service

Chất lượng dịch vụ

RB

Resource Block

Khối tài nguyên

RL

Reinforcement Learning

Học Củng cố

RNN

Recurrent Neural Network Mạng Nơ-ron Hồi quy

SINR


Signal-to-interferenceplus-noise ratio

QCI

Đỗ Minh Tồn - D17CQVT07-B

Cơng bằng tỷ lệ dựa trên
mức độ ưu tiên

Tỷ lệ tín hiệu trên nhiễucộng-nhiễu
vi


Đồ án tốt nghiệp Đại học
SYNC

Synchronization

Đồng bộ hóa

TTI

Transmission Time
Interval

Khoảng thời gian truyền

URLLC


Ultra-Reliable and LowLatency Communications

Truyền thông thời gian trễ
thấp và tin cậy cực cao

Đỗ Minh Toàn - D17CQVT07-B

vii


Đồ án tốt nghiệp Đại học

PHẦN MỞ ĐẦU
1. Tính cấp thiếu của đồ án
Sự ra đời của hệ thống truyền thông không dây thúc đẩy sự phát triển của các công
nghệ tiên tiến mới, bao gồm phương tiện tự lái, hệ thống máy bay không người lái, rô
bốt tự hành, Internet-of-Things và thực tế ảo. Những công nghệ này yêu cầu tốc độ dữ
liệu cao, độ trễ cực thấp và độ tin cậy cao, tất cả đều được hứa hẹn bởi thế hệ thứ năm
của hệ thống truyền thông không dây (5G). Nhiều nhóm nghiên cứu tun bố rằng 5G
khơng thể đáp ứng nhu cầu của nó nếu khơng tích hợp trí tuệ nhân tạo (AI) vì mạng
khơng dây 5G được kỳ vọng sẽ tạo ra lưu lượng truy cập chưa từng có cho phép các nhà
thiết kế nghiên cứu khơng dây truy cập vào dữ liệu lớn có thể giúp dự đoán nhu cầu và
điều chỉnh thiết kế mạng để đáp ứng người dùng các yêu cầu. Ứng dụng AI trong nhiều
khía cạnh của thiết kế truyền thơng khơng dây 5G bao gồm phân bổ tài nguyên vô tuyến,
quản lý mạng và an ninh mạng. Vì thế, em chọn đề tài “Ứng dụng AI trong quản lý tài
nguyên và búp sóng vơ tuyến cho mạng 5G” để tìm hiểu cách mà AI được áp dụng trong
mạng 5G nói chung và cụ thể trong quá trình quản lý tài nguyên và búp sóng như thế
nào.
2. Mục tiêu, đối tượng và phạm vi nghiên cứu
Mục tiêu nghiên cứu: Các thuật toán AI, thực trạng, các yêu cầu và trường hợp sử

dụng của mạng di động 5G, xây dựng giải pháp quản lý thông minh và tự động cho tài
nguyên và búp sóng vơ tuyến cho mạng 5G, cụ thể là giải quyết tính năng động phát
sinh từ tính di động của người dùng và lưu lượng truy cập của họ.
Đối tượng nghiên cứu: Các giải pháp AI, mạng di động 5G, xem xét sự cùng tồn tại
của Giao tiếp độ trễ thấp siêu đáng tin cậy (URLLC) và người dùng Mobile BroadBand
nâng cao (eMBB) trong mạng 5G mmWave và đề xuất kế hoạch phân nhóm búp sóng
và phân bổ tài nguyên vơ tuyến có nhận biết Chất lượng dịch vụ (QoS)
Phạm vi nghiên cứu:
• Các thuật tốn AI: Các thuật tốn K-mean, DBSCAN dùng cho các trường
hợp phân cụm, quản lý búp sóng. Thuật tốn Q-learning và mạng LSTM sử
dụng cho phân bổ tài ngun vơ tuyến.
• Mạng di động 5G: Thực trạng, các yêu cầu kỹ thuật và trường hợp sử dụng
trong mạng 5G.
3. Phương pháp nghiên cứu
Trên cơ sở các nhiệm vụ nghiên cứu vừa nêu, đồ án sử dụng phương pháp nghiên
cứu lý thuyết dựa trên việc phân tích các thuật tốn AI, kết hợp với mơ phỏng số liệu và
so sánh với các phương pháp trước đây trong việc quản lý búp sóng và tài ngun vơ
tuyến trong mạng 5G.
4. Bố cục đồ án
Đỗ Minh Toàn - D17CQVT07-B

viii


Đồ án tốt nghiệp Đại học
Chương 1: Tổng quan về Machine Learning và Reinforcement Learning. Phần này
sẽ giới thiệu khái quát về lịch sử ra đời, khái niệm của Machine learning và
Reinforcement Learning, các thuật toán K-mean, DBSCAN, Q-learning và mạng
LSTM.
Chương 2: Tổng quan về mạng thông tin di động 5G. Phần này sẽ nêu thực trạng

mạng 5G tại Việt Nam và trên thế giới, sau đó là các yêu cầu kỹ thuật của mạng 5G và
các trường hợp sử dụng.
Chương 3: Ứng dụng AI quản lý tài nguyên và búp sóng vơ tuyến cho mạng 5G.
Phần này trình bày mơ hình hệ thống 5G NodeB và áp dụng thuật tốn Deep Q-learning
với DBSCAN để quản lý, mơ phỏng và đánh giá mơ hình.
Kết luận và kiến nghị: Tổng kết các kiến thức cốt lõi và hướng phát triển tiếp theo
của đồ án.

Đỗ Minh Toàn - D17CQVT07-B

ix


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL

CHƯƠNG 1: TỔNG QUAN VỀ MACHINE LEARNING VÀ
REINFORCEMENT LEARNING
1. Machine learning
Những năm gần đây, AI - Artificial Intelligence (Trí Tuệ Nhân Tạo), và cụ thể hơn
là Machine Learning (Học Máy hoặc Máy Học) nổi lên như một bằng chứng của cuộc
cách mạng công nghiệp lần thứ tư (1 - động cơ hơi nước, 2 - năng lượng điện, 3 - cơng
nghệ thơng tin). Trí Tuệ Nhân Tạo đang len lỏi vào mọi lĩnh vực trong đời sống mà có
thể chúng ta khơng nhận ra. Xe tự hành của Google và Tesla, hệ thống tự tag khuôn mặt
trong ảnh của Facebook, trợ lý ảo Siri của Apple, hệ thống gợi ý sản phẩm của Amazon,
hệ thống gợi ý phim của Netflix, máy chơi cờ vây AlphaGo của Google DeepMind, …,
chỉ là một vài trong vô vàn những ứng dụng của AI/Machine Learning.

1.1. Lịch sử ra đời và phát triển


Hình 1. 1: lịch sử phát triển của machine learning
1950 - đây là năm Alan Turing, một trong những nhà toán học và khoa học máy
tính xuất sắc và có ảnh hưởng nhất của Anh, đã tạo ra phép thử Turing. Bài kiểm tra
được thiết kế để xác định xem một máy tính có trí thơng minh giống con người hay
khơng. Để vượt qua bài kiểm tra, máy tính cần có khả năng thuyết phục con người tin
rằng đó là một con người khác. Ngồi một chương trình máy tính mơ phỏng một cậu bé
13 tuổi người Ukraine được cho là đã vượt qua bài kiểm tra Turing, khơng có nỗ lực
thành cơng nào khác cho đến nay [1].
Đỗ Minh Tồn - D17CQVT07-B

1


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL

1952 - Arthur Samuels, nhà tiên phong người Mỹ trong lĩnh vực trí tuệ nhân tạo và
trị chơi máy tính, đã viết chương trình học máy tính đầu tiên. Chương trình đó thực sự
là trị chơi cờ caro. Máy tính IBM đầu tiên sẽ nghiên cứu những động thái nào dẫn đến
chiến thắng và sau đó đưa chúng vào chương trình của nó.
1957 - năm nay chứng kiến việc thiết kế mạng nơ-ron đầu tiên cho máy tính được
gọi là perceptron của Frank Rosenblatt. Nó đã kích thích thành cơng q trình suy nghĩ
của não người. Đây là nơi bắt nguồn các mạng nơ-ron ngày nay.
1967 - Thuật toán láng giềng gần nhất được viết lần đầu tiên trong năm nay. Nó cho
phép máy tính bắt đầu sử dụng nhận dạng mẫu cơ bản. Thuật tốn này có thể được sử
dụng để lập bản đồ lộ trình cho nhân viên bán hàng đi du lịch bắt đầu từ một thành phố
ngẫu nhiên và đảm bảo rằng nhân viên bán hàng đi qua tất cả các thành phố cần thiết
trong thời gian ngắn nhất. Ngày nay, thuật toán láng giềng gần nhất được gọi là KNN

chủ yếu được sử dụng để phân loại một điểm dữ liệu trên cơ sở cách phân loại láng giềng
của chúng. KNN được sử dụng trong các ứng dụng bán lẻ nhận dạng các kiểu sử dụng
thẻ tín dụng hoặc để ngăn chặn hành vi trộm cắp khi được thực hiện trong nhận dạng
hình ảnh CCTV trong các cửa hàng bán lẻ.
1981 - Gerald Dejong đưa ra khái niệm học tập dựa trên giải thích (EBL). Trong
loại hình học tập này, máy tính phân tích dữ liệu đào tạo và tạo ra một quy tắc chung mà
nó có thể tuân theo bằng cách loại bỏ dữ liệu có vẻ khơng quan trọng.
1985 - Terry Sejnowski đã phát minh ra chương trình NetTalk có thể học cách phát
âm các từ giống như một đứa trẻ trong q trình tiếp thu ngơn ngữ. Mạng nơ-ron nhân
tạo nhằm mục đích tái tạo lại một mơ hình đơn giản hóa sẽ cho thấy sự phức tạp của
việc học các nhiệm vụ nhận thức ở cấp độ con người.
Những năm 1990 - trong những năm 1990, công việc trong lĩnh vực học máy chuyển
từ phương pháp tiếp cận theo hướng tri thức sang phương pháp tiếp cận theo hướng dữ
liệu. Các nhà khoa học và nhà nghiên cứu đã tạo ra các chương trình cho máy tính có
thể phân tích một lượng lớn dữ liệu và đưa ra kết luận từ kết quả. Điều này dẫn đến sự
phát triển của máy tính IBM Deep Blue, máy tính đã giành chiến thắng trước nhà vô
địch cờ vua thế giới Garry Kasparov vào năm 1997.
2006 - đây là năm mà thuật ngữ “học sâu” được đặt ra bởi Geoffrey Hinton. Ông đã
sử dụng thuật ngữ này để giải thích một loại thuật tốn hồn tồn mới cho phép máy
tính nhìn và phân biệt các đối tượng hoặc văn bản trong hình ảnh hoặc video.
Năm 2010 - năm nay chứng kiến sự ra đời của Microsoft Kinect có thể theo dõi
thậm chí 20 đặc điểm của con người với tốc độ 30 lần mỗi giây. Microsoft Kinect cho
phép người dùng tương tác với máy thông qua cử chỉ và chuyển động.
2011 - đây là một năm thú vị đối với học máy. Để bắt đầu, IBM’s Watson đã quản
lý để đánh bại các đối thủ cạnh tranh là con người tại Jeopardy. Hơn nữa, Google đã
Đỗ Minh Toàn - D17CQVT07-B

2



Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL

phát triển Google Brain được trang bị một mạng nơ-ron sâu có thể học cách khám phá
và phân loại các đối tượng (đặc biệt là mèo).
2012 - Phòng thí nghiệm Google X đã phát triển một thuật tốn máy học có thể tự
động duyệt các video trên YouTube và xác định những video có mèo.
2014 - Facebook giới thiệu DeepFace, một thuật tốn phần mềm đặc biệt có thể
nhận dạng và xác minh các cá nhân trên ảnh ở cấp độ giống như con người.
Năm 2015 - đây là năm Amazon ra mắt nền tảng máy học của riêng mình, giúp máy
học dễ tiếp cận hơn và đưa nó lên vị trí hàng đầu trong phát triển phần mềm. Hơn nữa,
Microsoft đã tạo ra Bộ công cụ học máy phân tán, cho phép các nhà phát triển phân phối
hiệu quả các vấn đề về học máy trên nhiều máy. Tuy nhiên, trong cùng năm đó, hơn
3.000 nhà nghiên cứu AI và robot được các nhân vật như Elon Musk, Stephen Hawking
và Steve Wozniak xác nhận đã ký một bức thư ngỏ cảnh báo về sự nguy hiểm của vũ
khí tự động có thể chọn mục tiêu mà khơng cần bất kỳ sự can thiệp nào của con người.
Năm 2016 - đây là năm mà các thuật tốn trí tuệ nhân tạo của Google đã đánh bại
một kỳ thủ chuyên nghiệp tại trò chơi cờ vây của Trung Quốc. Cờ vây được coi là trò
chơi trên bàn cờ phức tạp nhất thế giới. Thuật toán AlphaGo do Google phát triển đã
thắng 5 trong 5 ván trong cuộc thi, đưa AI lên trang nhất.
2020 - Open AI đã công bố thuật tốn xử lý ngơn ngữ tự nhiên đột phá GPT-3 với
khả năng tạo văn bản giống người đáng chú ý khi được nhắc. Ngày nay, GPT-3 được
coi là mô hình ngơn ngữ tiên tiến và lớn nhất trên thế giới, sử dụng 175 tỷ tham số và
siêu máy tính Microsoft Azure’s AI để đào tạo.

1.2. Các phương pháp phổ biến nhất

Hình 1. 2: Các phương pháp phổ biến của machine learning
•


Các thuật tốn Supervised Learning có thể áp dụng những gì nó đã học trong
q khứ vào dữ liệu mới với sự trợ giúp của các ví dụ được gắn nhãn. Nó làm
điều đó để dự đốn các sự kiện trong tương lai. Các thuật toán như vậy bắt đầu

Đỗ Minh Toàn - D17CQVT07-B

3


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL

với việc phân tích tập dữ liệu đào tạo đã biết và sau đó đưa ra thơng tin chi tiết
để đưa ra dự đoán về các giá trị đầu ra. Hệ thống có thể cung cấp các mục tiêu
cho bất kỳ đầu vào mới nào sau khi được đào tạo đầy đủ. Thuật tốn cũng có
thể so sánh kết quả của nó với đầu ra chính xác và dự định để tìm lỗi và sửa đổi
mơ hình cho phù hợp.
• Các thuật tốn Unsupervised Learning được sử dụng khi dữ liệu được cung cấp
cho thuật tốn khơng được gắn nhãn hoặc phân loại theo bất kỳ cách nào. Học
khơng giám sát dựa trên các hệ thống phân tích các mẫu trong dữ liệu không
được gắn nhãn. Hệ thống khơng đi đến đầu ra có thể đúng hay sai, mà là hệ
thống khám phá dữ liệu và rút ra các suy luận từ các tập dữ liệu.
• Các thuật toán Semi-supervised learning nằm ở giữa hai thuật toán này. Nó sử
dụng cả dữ liệu được gắn nhãn và khơng được gắn nhãn để đào tạo. Thơng
thường, đó là một số lượng nhỏ dữ liệu được gắn nhãn và một lượng rất lớn dữ
liệu không được gắn nhãn. Các hệ thống sử dụng phương pháp này có thể cải
thiện đáng kể độ chính xác trong học tập của chúng. Hầu hết thời gian, hệ thống
học tập bán giám sát được chọn khi dữ liệu được gắn nhãn thu được yêu cầu

các tài nguyên có kỹ năng và phù hợp để học hỏi từ đó.
• Các thuật tốn Reinforcement learning đại diện cho một loại phương pháp học
tập khác. Loại thuật tốn này tương tác với mơi trường bằng cách tạo ra các
hành động và sau đó phát hiện ra lỗi hoặc phần thưởng. Phần thưởng bị trì hỗn
hoặc tìm kiếm thử và sai là những đặc điểm chính của việc học củng cố. Phương
pháp này cho phép máy móc tự động xác định hành vi tốt nhất trong bối cảnh
cụ thể để tối đa hóa hiệu suất của chúng và nhận được phần thưởng tốt nhất.
Nó u cầu tìm hiểu hành động nào hoạt động tốt nhất - cái gọi là tín hiệu củng
cố.

1.3. Thuật tốn K-mean
1.3.1. Thuật tốn k-means là gì?
K-means là một thuật tốn phân cụm đơn giản thuộc loại học không giám sát (tức
là dữ liệu không có nhãn) và được sử dụng để giải quyết bài toán phân cụm. Ý tưởng
của thuật toán phân cụm k-means là phân chia 1 bộ dữ liệu thành các cụm khác nhau.
Trong đó số lượng cụm được cho trước là k. Công việc phân cụm được xác lập dựa trên
nguyên lý: Các điểm dữ liệu trong cùng 1 cụm thì phải có cùng 1 số tính chất nhất định.
Tức là giữa các điểm trong cùng 1 cụm phải có sự liên quan lẫn nhau. Đối với máy tính
thì các điểm trong 1 cụm đó sẽ là các điểm dữ liệu gần nhau [2].
Thuật toán phân cụm k-means thường được sử dụng trong các ứng dụng cỗ máy tìm
kiếm, phân đoạn khách hàng, thống kê dữ liệu,…
Đỗ Minh Toàn - D17CQVT07-B

4


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL


Hình 1. 3: Kết quả phân cụm của thuật toán kmeans [2]
Thuật toán phân cụm k-means là một phương pháp được sử dụng trong phân tích
tính chất cụm của dữ liệu. Nó đặc biệt được sử dụng nhiều trong khai phá dữ liệu và
thống kê. Nó phân vùng dữ liệu thành k cụm khác nhau. Giải thuật này giúp chúng ta
xác định được dữ liệu của chúng ta nó thực sự thuộc về nhóm nào.

1.3.2. Ý tưởng của thuật toán k-means
1. Khởi tạo K điểm dữ liệu trong bộ dữ liệu và tạm thời coi nó là tâm của
các cụm dữ liệu của chúng ta.
2. Với mỗi điểm dữ liệu trong bộ dữ liệu, tâm cụm của nó sẽ được xác định
là 1 trong K tâm cụm gần nó nhất.
3. Sau khi tất cả các điểm dữ liệu đã có tâm, tính tốn lại vị trí của tâm cụm
để đảm bảo tâm của cụm nằm ở chính giữa cụm.
4. Bước 2 và bước 3 sẽ được lặp đi lặp lại cho tới khi vị trí của tâm cụm
khơng thay đổi hoặc tâm của tất cả các điểm dữ liệu không thay đổi.
Lựa chọn số lượng cụm
Chỉ việc lựa chọn số cụm k đã có thể tách thành 1 bài tốn riêng. Khơng có 1 con
số k nào là hợp lý cho tất cả các bài toán. Chúng ta có thể đọc hiểu tập dữ liệu của mình
để xác định xem trong đó có thể có bao nhiêu cụm? Nhưng khơng phải lúc nào chúng ta
cũng có thể làm thế. Cách làm duy nhất là chúng ta hãy thử với từng giá trị k=1,2,3,4,5,
… để xem kết quả phân cụm thay đổi như thế nào. Một số nghiên cứu cho thấy việc thay
đổi k sẽ có hiệu quả nhưng sẽ dừng lại ở 1 con số nào đó. Như vậy chúng ta hoàn toàn
Đỗ Minh Toàn - D17CQVT07-B

5


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL


có thể thử xem dữ liệu của mình tốt với giá trị k nào đó.
Khởi tạo k vị trí ban đầu
Bằng cách nào đó, hãy cố gắng khởi tạo k tâm cụm này phân bố đồng đều trên
không gian của bộ dữ liệu. Điều đó có thể làm khi chúng ta có thể xác định được khơng
gian và tính chất của dữ liệu. Nhưng ít nhất, các tâm cụm mà chúng ta khởi tạo cũng
đừng quá gần nhau, cũng đừng trùng nhau.
Còn 1 cách cuối cùng là chúng ta sẽ chạy thuật toán nhiều lần để lấy kết quả tốt nhất
trong các lần chạy đó. Với điều kiện là chúng ta khởi tạo tâm của k cụm ngẫu nhiên.
Về vấn đề tính dừng (hội tụ)
Đối với những trường hợp dữ liệu phức tạp, thuật toán k-means sẽ rất lâu hoặc
không bao giờ hội tụ. Tức là sẽ không bao giờ xác định được tâm cụm cố định để kết
thúc bài toán. Hoặc là phải chạy qua rất nhiều bước lặp. Trong những trường hợp như
vậy, thay vì phải tìm được k tâm cụm cố định thì ta sẽ dừng bài toán khi sự thay đổi ở
một con số chấp nhận được. Tức là giữa hai lần cập nhật tâm cụm thì chênh lệch vị trí
giữa tâm cũ và mới nhỏ hơn một số delta cho phép nào đó.

1.4. Thuật tốn DBSCAN
1.4.1. Thuật tốn DBSCAN là gì?
Thuật tốn DBSCAN là viết tắt của cụm từ Density-Based Spatial Clustering of
Applications with Noise, tên này có ý nghĩa là thuật tốn phân cụm dựa trên mật độ
không gian với các dạng dữ liệu có nhiễu. Trên thực tế DBSCAN có khả năng loại bỏ
các điểm dữ liệu nhiễu [3].
Trong thuật toán DBSCAN cũng không cần khai báo trước số lượng cụm cần phân
chia. Đây là một ưu điểm lớn của DBSCAN so với k-Means bởi vì đơi khi chúng ta sẽ
khơng thể biết trước số lượng cụm cần phân chia bao nhiêu là hợp lý, đặc biệt là trên
những bộ dữ liệu hồn tồn mới mà chúng ta chưa từng có kinh nghiệm về chúng.
Trong DBSCAN chúng ta chỉ cần xác định hàm tính tốn khoảng cách và bán kính
khoảng cách bao nhiêu được coi là gần nhau để thuật toán tự động thực hiện quá trình
phân cụm.

Bên cạnh ưu điểm khơng cần xác định số lượng cụm thì DBSCAN là thuật tốn có
tốc độ tính tốn rất nhanh.

1.4.2. Các định nghĩa trong DBSCAN
Định nghĩa 1: Vùng lân cận epsilon (Eps-neighborhood) của một điểm dữ liệu 𝑃
được định nghĩa là tợp hợp tất cả các điểm dữ liệu nằm trong phạm vi bán
kính epsilon (kí hiệu ϵ) xung quanh điểm 𝑃 . Kí hiệu tập hợp những điểm này là:
𝑁𝑒𝑝𝑠 (𝑃) = {𝑄 𝐷: ⅆ(𝑃, 𝑄) ≤ 𝜖}
Trong đó 𝐷 là tập hợp tất cả các điểm dữ liệu của tập huấn luyện.
Đỗ Minh Toàn - D17CQVT07-B

6


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL

Định nghĩa 2: Khả năng tiếp cận trực tiếp mật độ (directly density-reachable) đề
cập tới việc một điểm có thể tiếp cận trực tiếp tới một điểm dữ liệu khác. Cụ thể là một
điểm 𝑄 được coi là có thể tiếp cận trực tiếp bởi điểm 𝑃 tương ứng với tham
số 𝑒𝑝𝑠𝑖𝑙𝑜𝑛 và 𝑚𝑖𝑛𝑃𝑡𝑠 nếu như nó thoả mãn hai điều kiện:
1.

𝑄 nằm trong vùng lân cận epsilon của 𝑃 : 𝑄 ∈ 𝑁𝑒𝑝𝑠 (𝑃)

2. Số lượng các điểm dữ liệu nằm trong vùng lân cận epsilon tối thiểu
là 𝑚𝑖𝑛𝑃𝑡𝑠:

|𝑁𝑒𝑝𝑠 | > 1 min 𝑃𝑡𝑠


Như vậy một điểm dữ liệu có thể tiếp cận được trực tiếp tới một điểm khác không
chỉ dựa vào khoảng cách giữa chúng mà còn phụ thuộc vào mật độ các điểm dữ liệu
trong vùng lân cận epsilon phải tối thiểu bằng 𝑚𝑖𝑛𝑃𝑡𝑠. Khi đó vùng lân cận được coi là
có mật độ cao và sẽ được phân vào các cụm. Trái lại thì vùng lân cận sẽ có mật độ thấp.
Trong trường hợp mật độ thấp thì điểm dữ liệu ở trung tâm được coi là không kết nối
trực tiếp tới những điểm khác trong vùng lân cận và những điểm này có thể rơi vào biên
của cụm hoặc là một điểm dữ liệu nhiễu không thuộc về cụm nào.
Định nghĩa 3: Khả năng tiếp cận mật độ (density-reachable) liên quan đến cách
hình thành một chuỗi liên kết điểm trong cụm. Cụ thể là trong một tập hợp chuỗi
điểm {𝑃𝑖 }𝑛
𝑖=1

 𝐷 mà nếu như bất kì một điểm 𝑃𝑖

nào cũng đều có thể tiếp cận trực

tiếp mật độ (định nghĩa 2) bởi 𝑃𝑖−1 theo tham số 𝑒𝑝𝑠𝑖𝑙𝑜𝑛 và 𝑚𝑖𝑛𝑃𝑡𝑠 thì khi đó ta nói
điểm 𝑃

= 𝑃𝑛 có khả năng kết nối mật độ tới điểm 𝑄 = 𝑃1 .

Từ định nghĩa 3 ta suy ra hai điểm 𝑃𝑖 và 𝑃𝑗 bất kì thuộc chuỗi {𝑃𝑖 }𝑛
𝑖=1 thoả
mãn inối mật độ với nhau thì sẽ thuộc cùng một cụm. Từ đó suy ra các điểm trong
chuỗi {𝑃𝑖 }𝑛
𝑖=1 đều được phân về cùng cụm. Khả năng tiếp cận mật độ thể hiện sự mở
rộng phạm vi của một cụm dữ liệu dựa trên liên kết theo chuỗi. Xuất phát từ một điểm
dữ liệu ta có thể tìm được các điểm có khả năng kết nối mật độ tới nó theo lan truyền

chuỗi để xác định cụm.

1.4.3. Phân loại dạng điểm trong DBSCAN
Căn cứ vào vị trí của các điểm dữ liệu so với cụm chúng ta có thể chia chúng thành
ba loại: Đối với các điểm nằm sâu bên trong cụm chúng ta xem chúng là điểm lõi.
Các điểm biên nằm ở phần ngồi cùng của cụm và điểm nhiễu khơng thuộc bất kì một
cụm nào. Bên dưới là hình vẽ mô phỏng thể hiện ba loại điểm tương ứng nêu trên.

Đỗ Minh Toàn - D17CQVT07-B

7


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL

Core point
Border point
Noise point

𝜺
MinPts = 3

Hình 1. 4: Hình minh hoạ cách xác định ba loại điểm [3]
Hình 1.2 minh hoạ cách xác định ba loại điểm bao gồm: điểm lõi (core) chấm vuông
màu xanh, điểm biên (border), chấm tròn màu đen và điểm nhiễu (noise) chấm tròn màu
trắng trong thuật tốn DBSCAN. Các hình trịn đường viền nét đứt bán kính ϵ thể
hiện vùng lân cận epsilon tương ứng với các điểm lõi nhằm xác định nhãn cho từng
điểm. minPts=3 là số lượng tối thiểu để một điểm lõi rơi vào vùng có mật độ cao nếu

xung quanh chúng có số lượng điểm tối thiểu là 3.
Trong thuật tốn DBSCAN sử dụng hai tham số chính đó là:
minPts: Là một ngưỡng số điểm dữ liệu tối thiểu được nhóm lại với nhau nhằm xác
định một vùng lân cận epsilon có mật độ cao. Số lượng minPts khơng bao gồm điểm ở
tâm.
epsilon (kí hiệu ϵ): Một giá trị khoảng cách được sử dụng để xác định vùng lân cận
epsilon của bất kỳ điểm dữ liệu nào.
Hai tham số trên sẽ được sử dụng để xác định vùng lân cận epsilon và khả năng tiếp
cận giữa các điểm dữ liệu lẫn nhau. Từ đó giúp kết nối chuỗi dữ liệu vào chung một
cụm.
Hai tham số trên giúp xác định ba loại điểm:
điểm lõi (core): Đây là một điểm có ít nhất minPts điểm trong vùng lân cận
epsilon của chính nó.
điểm biên (border): Đây là một điểm có ít nhất một điểm lõi nằm ở vùng lân cận
epsilon nhưng mật độ khơng đủ minPts điểm.
Đỗ Minh Tồn - D17CQVT07-B

8


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL

điểm nhiễu (noise): Đây là điểm không phải là điểm lõi hay điểm biên.
Đối với một cặp điểm (𝑃, 𝑄) bất kì sẽ có ba khả năng:
Cả 𝑃 và 𝑄 đều có khả năng kết nối mật độ được với nhau. Khi đó 𝑃, 𝑄 đều thuộc
về chung một cụm.
𝑃 có khả năng kết nối mật độ được với 𝑄 nhưng 𝑄 không kết nối mật độ được
với 𝑃. Khi đó 𝑃 sẽ là điểm lõi của cụm cịn 𝑄 là một điểm biên.

𝑃 và 𝑄 đều khơng kết nối mật độ được với nhau. Trường hợp này 𝑃 và 𝑄 sẽ rơi vào
những cụm khác nhau hoặc một trong hai điểm là điểm nhiễu.

1.4.4. Các bước trong thuật toán DBSCAN
Các bước của thuật toán DBSCAN khá đơn giản. Thuật toán sẽ thực hiện lan truyền
để mở rộng dần phạm vi của cụm cho tới khi chạm tới những điểm biên thì thuật tốn
sẽ chuyển sang một cụm mới và lặp lại tiếp quá trình trên. Cụ thể chúng ta sẽ thấy được
q trình lan truyền này thơng qua hình 1.3 minh hoạ bên dưới.

Hình 1. 5 Quá trình lan truyền để xác định các cụm của thuật tốn DBSCAN [3]
Qui trình của thuật tốn:
Bước 1: Thuật tốn lựa chọn một điểm dữ liệu bất kì. Sau đó tiến hành xác định
các điểm lõi và điểm biên thông qua vùng lân cận epsilon bằng cách lan truyền theo liên
kết chuỗi các điểm thuộc cùng một cụm.
Bước 2: Cụm hồn tồn được xác định khi khơng thể mở rộng được thêm. Khi đó
lặp lại đệ qui tồn bộ q trình với điểm khởi tạo trong số các điểm dữ liệu cịn lại để
xác định một cụm mới.

Đỗ Minh Tồn - D17CQVT07-B

9


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan về ML và RL

2. Reinforcement Learning
2.1. Reinforcement Learning là gì?
Reinforcement Learning là việc đào tạo các mơ hình Machine Learning để đưa ra

một chuỗi các quyết định. Trong Reinforcement Learning, trí tuệ nhân tạo (AI) đối mặt
với một tình huống giống như trị chơi. Máy tính sử dụng thử và sai (trial and error) để
đưa ra giải pháp cho vấn đề. Để khiến máy làm những gì lập trình viên muốn, các máy
(agent) sẽ nhận được phần thưởng (reward) hoặc hình phạt (penalty) cho những hành
động(action) mà nó thực hiện. Mục tiêu của nó là tối đa hóa tổng phần thưởng.

Agent

State

Reward

action

𝑠𝑡

𝑅𝑡

𝐴𝑡

𝑅𝑡+1
Environment

𝑆𝑡+1
Hình 1. 6: Quy trình bài tốn Reinforcement learning
• Environment (Mơi trường): là khơng gian mà máy tương tác.
• Agent (Máy): là chủ thể tương tác với môi trường qua hành động.
• Policy (Chiến thuật): là chiến thuật mà máy sử dụng để đưa ra hành động.
• State (Trạng thái): mơ tả trạng thái hiện tại của máy.
• Reward (Phần thưởng): phần thưởng từ môi trường tương ứng với hành động

được thực hiện.
• Action (Hành động): là những gì máy có thể thực hiện.
Chúng ta sẽ bắt đầu từ state S(t), tại trạng thái này, agent sẽ dựa trên policy đã được
thiết kế sẵn để đưa ra một action A(t) trong environment. Environment sau khi quan sát
hành động sẽ chuyển đổi sang trạng thái tiếp theo S(t+1) đối với agent và đồng thời dựa
theo hành động mà agent đã thực hiện, environment sẽ đưa ra phần thưởng R(t) tương
ứng. Agent sẽ lặp đi lặp lại qui trình này cho đến khi tìm được chuỗi những hành động
tối đa hóa phần thưởng được nhận [4].
Đỗ Minh Toàn - D17CQVT07-B

10