ĐẠI HỌC KINH TẾ QUỐC DÂN
TRƯỜNG CÔNG NGHỆ
----------------
KHÓA LUẬN TỐT NGHIỆP
NGHIÊN CỨU VÀ PHÁT TRIỂN HỆ THỐNG PHÁT HIỆN
ĐƯỜNG ĐI TRÁNH ÙN TẮC SỬ DỤNG KỸ THUẬT PHÂN
CỤM DỰA TRÊN MẬT ĐỘ KẾT HỢP TÌM KIẾM TỐI ƯU
Tên sinh viên : Trần Quốc Tiến
Giảng viên hướng dẫn : TS. Lưu Minh Tuấn
Hà Nội, 5/2025
2025.2 CÔNG NGHÊ THÔNG TIN TRẦN QUỐC TIẾN 11215680
ĐẠI HỌC KINH TẾ QUỐC DÂN
TRƯỜNG CÔNG NGHỆ
----------------
KHÓA LUẬN TỐT NGHIỆP
NGHIÊN CỨU VÀ PHÁT TRIỂN HỆ THỐNG PHÁT HIỆN
ĐƯỜNG ĐI TRÁNH ÙN TẮC SỬ DỤNG KỸ THUẬT PHÂN
CỤM DỰA TRÊN MẬT ĐỘ KẾT HỢP TÌM KIẾM TỐI ƯU
Tên sinh viên : Trần Quốc Tiến
Mã sinh viên : 11215680
Lớp : Công nghệ thông tin 63A
Ngành : Công nghệ thông tin
Khoa : Công nghệ thông tin
Giảng viên hướng dẫn : TS. Lưu Minh Tuấn
(Chữ ký GVHD)
Hà Nội, 5/2025
i
MỤC LỤC
MỞ ĐẦU .............................................................................................................. 1
CHƯƠNG 1:TỔNG QUAN VỀ ĐỀ TÀI ........................................................... 2
1.1. Lý do chọn đề tài ........................................................................................... 2
1.1.1. Tình hình giao thông tại Việt Nam ............................................................. 2
1.1.2. Trí tuệ nhân tạo ........................................................................................... 4
1.2. Phát biểu đề tài .............................................................................................. 6
1.3. Đối tượng nghiên cứu .................................................................................... 7
1.4. Phạm vi nghiên cứu ....................................................................................... 7
1.5. Phương pháp nghiên cứu .............................................................................. 8
1.6. Ý nghĩa thực tiễn và ý nghĩa khoa học ........................................................ 8
CHƯƠNG 2:CƠ SỞ LÝ THUYẾT .................................................................. 10
2.1. Giới thiệu học máy ...................................................................................... 10
2.2. Giới thiệu phân cụm .................................................................................... 14
2.2.1. Thuật toán phân cụm dựa trên mật độ DBSCAN .................................... 15
2.2.1.1. Tham số chính .......................................................................................... 19
2.2.1.2. Đánh giá hiệu năng mô hình ................................................................... 20
2.2.1.3. Ưu điểm và nhược điểm của thuật toán DBSCAN .................................. 20
2.2.2. Giới thiệu thuật toán phân cụm dựa trên mật độ OPTICS ..................... 21
2.2.2.1. So sánh giữa thuật toán OPTICS và thuật toán DBSCAN ...................... 23
2.3. Thuật toán tìm kiếm tối ưu A* ................................................................... 24
CHƯƠNG 3: CÀI ĐẶT THỬ NGHIỆM ......................................................... 27
3.1. Mô hình đề xuất và đặc tả hệ thống........................................................... 27
3.1.1. Mô hình đề xuất ......................................................................................... 27
3.1.2. Đặc tả các thành phần .............................................................................. 28
3.2. Các công cụ và thư viện sử dụng ............................................................... 28
3.2.1. Ngôn ngữ lập trình Python ....................................................................... 28
ii
3.2.2. Thư viện phân tích dữ liệu Pandas .......................................................... 29
3.2.3. Thư viện học máy Scikit-learn .................................................................. 29
3.2.4. Thư viện vẽ biểu đồ Plotly ......................................................................... 30
3.2.5. Thư viện vẽ bản đồ Folium ....................................................................... 31
3.2.6. Thư viện thiết kế và phát triển ứng dụng Streamlit ................................. 32
3.3. Bộ dữ liệu thử nghiệm ................................................................................. 33
3.3.1. Thu thập và tiền xử lý bộ dữ liệu .............................................................. 33
3.3.2. Tiền xử lý bộ dữ liệu thử nghiệm ............................................................. 38
3.4. Cài đặt thử nghiệm ...................................................................................... 40
3.4.1. Thiết kế các tham số kiểm thử mô hình ................................................... 40
3.4.2. Xây dựng thuật toán A* ............................................................................ 44
3.5. Đánh giá kết quả thử nghiệm ..................................................................... 47
3.5.1. Đánh giá kết quả phân cụm ...................................................................... 47
3.5.2. Đánh giá kết quả tìm kiếm tối ưu ............................................................. 50
3.6. Phát triển ứng dụng dựa trên mô hình ..................................................... 53
CHƯƠNG 4: ĐÁNH GIÁ KẾT QUẢ .............................................................. 55
4.1. Kết quả đạt được ......................................................................................... 55
4.2. Những hạn chế ............................................................................................. 55
4.3. Hướng phát triển ......................................................................................... 56
KẾT LUẬN ......................................................................................................... 57
TÀI LIỆU THAM KHẢO ................................................................................. 58
iii
DANH MỤC CÁC TỪ VIẾT TẮT
Từ viết tắt
Ý nghĩa
DBSCAN
Density-Based Spatial Clustering of Applications
with Noise
OPTICS
Ordering Points To Identify the Clustering
Structure
Eps
Epsilon
MinPts
Minimun Points
CSV
Comma-Separated Values
