ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM ĐẶNG THÁI DUY NGHIÊN CỨU HỆ THỐNG KHỐI MÁY HỌC MLBLOCKS VÀ ỨNG DỤNG VÀO DỰ ĐỐN LỘ TRÌNH TỐI ƯU TRONG GIAO THÔNG LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN Đà Nẵng - Năm 2017 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM ĐẶNG THÁI DUY NGHIÊN CỨU HỆ THỐNG KHỐI MÁY HỌC MLBLOCKS VÀ ỨNG DỤNG VÀO DỰ ĐỐN LỘ TRÌNH TỐI ƯU TRONG GIAO THƠNG Chun ngành: Hệ thống thông tin Mã số: 60.48.01.04 LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN Người hướng dẫn khoa học: PGS.TSKH TRẦN QUỐC CHIẾN Đà Nẵng - Năm 2017 i LỜI CAM ĐOAN Tôi xin cam đoan luận văn cơng trình nghiên cứu riêng tơi, khơng chép cơng trình khoa học trước Các kết nêu luận văn có nguồn gốc rõ ràng trích dẫn đầy đủ Tơi xin chịu hồn tồn trách nhiệm luận văn Học viên Đặng Thái Duy ii MỤC LỤC DANH MỤC TỪ VIẾT TẮT v DANH MỤC CÁC BẢNG vi DANH MỤC CÁC HÌNH vii DANH MỤC CÁC BIỂU ĐỒ viii MỞ ĐẦU 1 Lý chọn đề tài Mục tiêu nhiệm vụ đề tài Đối tượng phạm vi nghiên cứu Giải pháp đề xuất Kết dự kiến Bố cục luận văn CHƯƠNG TỔNG QUAN 1.1 KHÁI NIỆM MÁY HỌC .5 1.2 CÁC ỨNG DỤNG MÁY HỌC 1.3 QUÁ TRÌNH MÁY HỌC 13 1.4 CÁC PHƯƠNG PHÁP MÁY HỌC 19 1.4.1 Phương pháp học không giám sát (Unsupervised Learning) 20 1.4.2 Phương pháp học bán giám sát (Semi-Supervised Learning) 20 1.4.3 Phương pháp học có giám sát (Supervised Learning) .24 1.4.4 Học tăng cường (reinforcement learning) .25 1.5 TIỂU KẾT CHƯƠNG 28 CHƯƠNG THIẾT KẾ VÀ THỰC THI KHỐI MÁY HỌC MLBLOCKS 29 2.1 TỔNG QUAN 29 2.2 KHÁI NIỆM MLBLOCK 30 2.3 CÁC ỨNG DỤNG MLBLOCK 31 2.3.1 Một số công cụ khai phá liệu 31 2.3.2 Ngơn ngữ lập trình thư viện cho ML 34 2.3.3 Công cụ hệ 2.0 36 iii 2.3.4 Mô hình chung cho tốn Machine Learning .39 2.3.5 Mơ hình khối máy học MLBlocks 42 2.4 THIẾT KẾ VÀ THỰC THI MLBLOCK CHO DỰ ĐỐN LỘ TRÌNH GIAO THÔNG .43 2.4.1 Mơ hình đề xuất 44 2.4.2 Sử dụng mơ hình .45 2.5 TIỂU KẾT CHƯƠNG 46 CHƯƠNG ỨNG DỤNG MLBLOCKS TRONG VIỆC DỰ ĐỐN LỘ TRÌNH TỐI ƯU TRONG GIAO THƠNG TẠI THÀNH PHỐ ĐÀ NẴNG 47 3.1 THỰC TRẠNG VÀ GIẢI PHÁP .47 3.1.1 Thực trạng giao thông thành phố Đà nẵng 47 3.1.2 Giải pháp 49 3.2 CÁC BƯỚC XÂY DỰNG MƠ HÌNH DỰ ĐỐN LỘ TRÌNH GIAO THƠNG 51 3.2.1 Bước 1: Dữ liệu thực nghiệm 51 3.2.2 Bước 2: Chia liệu training test .58 3.2.3 Bước 3: Huấn luyện 59 3.2.4 Bước 4: Thực phân lớp 61 3.2.5 Bước 5: Tìm đường ngắn .63 3.3 KẾT QUẢ THỰC NGHIỆM 69 3.3.1 Cài đặt môi trường thực nghiệm 69 3.3.2 Thực nghiệm test 70-30 70 3.3.3 Thực nghiệm Test Cross validation với liệu thông thường 72 3.3.4 Thực nghiệm Test Cross validation với liệu xét đến ngày nghỉ lễ .75 3.3.5 Biểu đồ so sánh kết thực nghiệm liệu bình thường liệu có xét đến ngày nghỉ lễ 78 3.3.6 Thực nghiệm với mức độ tắc đường khác 79 3.3.7 Biểu đồ so sánh kết thực nghiệm với mật độ giao thông khác 80 iv 3.3.8 Thực nghiệm tìm đường ngắn .81 3.4 TIỂU KẾT CHƯƠNG 81 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TƯƠNG LAI .82 TÀI LIỆU THAM KHẢO 83 QUYẾT ĐỊNH GIAO ĐỀ TÀI (Bản sao) v DANH MỤC TỪ VIẾT TẮT STT Nghĩa đầy đủ Từ viết tắt SVM Support Vector Machine WEKA Waikato Environment for Knowledge Analysis VSL Variable Speed Limit DT Decision Tree NB Navie Bayes NN Neural Network NLP Natural Language Processing vi DANH MỤC CÁC BẢNG Số hiệu bảng Tên bảng Trang 3.1 Cấu hình máy chủ thực nghiệm 69 3.2 Test 70-30 - Kết test mơ hình Decision Tree 70 3.3 Test 70-30 - Kết test mơ hình SVM 70 3.4 Test 70-30 - Kết test mơ hình Nạve Bayes 71 3.5 Test 70-30 - Kết test mơ hình Neural Network 71 3.6 Test 70-30 - So sánh kết phân lớp sử dụng SVM, Navies Bayes, J48 Neural Network với phân lớp 72 3.7 Test Cross Validation - Kết test mơ hình Decision Tree 73 3.8 Test Cross Validation - Kết test mơ hình SVM 74 3.9 Test Cross Validation - Kết test mô hình Nạve Bayes 74 3.10 Test Cross Validation - Kết test mơ hình Neural Network 75 3.11 Test Cross - So sánh kết phân lớp sử dụng SVM, Navies Bayes, J48 Neural Network 75 3.12 Test Cross Validation - Kết test mơ hình Decision Tree 76 3.13 Test Cross Validation - Kết test mơ hình SVM 76 3.14 Test Cross Validation - Kết test mơ hình Nạve Bayes 77 3.15 Test Cross Validation - Kết test mơ hình Neural Network 77 vii DANH MỤC CÁC HÌNH Số hiệu hình Tên hình Trang 2.1 Vai trò Azure quy trình Machine Learning 38 2.2 Mơ hình chung cho tốn Machine Learning 39 2.3 Mơ hình chung khối máy học 42 2.4 Ví dụ mơ hình khối máy học lấy ý tưởng từ điểm giao thông 43 2.5 Mô hình Dự đốn lộ trình Giao thơng 45 3.1 Tổng quan tình trạng giao thơng 48 3.2 Minh họa giải pháp tìm lộ trình giao thơng 51 3.3 Test 70-30 – Dữ liệu training 59 3.4 Test 70-30 – Dữ liệu Test 59 3.5 Lựa chọn liệu huấn luyện 60 3.6 Thông tin liệu huấn luyện 60 3.7 Thông tin tập Quan hệ 60 3.8 Thông tin Attributes 61 3.9 Thông tin chi tiết Attributes 61 3.10 Màn hình phân lớp liệu 62 3.11 Chức chọn phân lớp 62 3.12 Các phương thức test 63 3.13 Kết output phân lớp liệu 63 3.14 Test Cross Validation – Dữ liệu training 73 3.15 Thực nghiệm tìm đường ngắn 81 viii DANH MỤC CÁC BIỂU ĐỒ Số hiệu biểu đồ Tên biểu đồ Trang Biểu đồ 3.1 So sánh Dữ liệu thông thường Dữ liệu có ngày nghỉ lễ 78 Biểu đồ 3.2 Kết thực nghiệm với mật độ giao thông khác 80 73 Hình 3.14 Test Cross Validation – Dữ liệu training a Mơ hình Decision Tree Kết test: Bảng 3.7 Test Cross Validation - Kết test mơ hình Decision Tree Chi tiết độ xác phân lớp Avg Precision Recall F-Measure Class 81.0% 100.0% 89.5% S1 81.1% 97.9% 88.7% S2 81.3% 52.5% 63.8% S3 80.6% 89.6% 84.9% S4 66.1% 18.9% 29.4% S5 79.4% 100.0% 88.5% S6 78.6% 80.0% 79.3% 74 b Mơ hình Super Vector Machines (SVM) Kết test: Bảng 3.8 Test Cross Validation - Kết test mơ hình SVM Chi tiết độ xác phân lớp Avg Precision Recall F-Measure Class 52.3% 85.8% 65.0% S1 44.7% 82.5% 58.0% S2 34.9% 2.6% 4.8% S3 81.0% 11.3% 19.8% S4 22.6% 7.5% 11.3% S5 24.1% 29.5% 26.5% S6 40.1% 47.2% 43.4% c Mơ hình Naive Bayes Kết test: Bảng 3.9 Test Cross Validation - Kết test mơ hình Nạve Bayes Chi tiết độ xác phân lớp Avg Precision Recall F-Measure Class 75.1% 100.0% 85.8% S1 46.0% 79.2% 58.2% S2 44.9% 7.5% 12.9% S3 59.4% 70.0% 64.3% S4 2.6% 73.1% 5.0% S5 56.2% 56.1% 56.1% S6 58.8% 63.0% 60.8% 75 d Mơ hình Neural Network Kết test: Bảng 3.10 Test Cross Validation - Kết test mơ hình Neural Network Chi tiết độ xác phân lớp Avg Precision Recall F-Measure Class 81.0% 97.6% 88.5% S1 80.6% 91.7% 85.8% S2 67.8% 57.4% 62.2% S3 80.3% 88.0% 84.0% S4 81.4% 64.1% 71.7% S5 79.1% 85.7% 82.3% S6 76.4% 77.2% 76.8% e So sánh kết chạy SVM, Navies Bayes, J48 Neural Network với số phân lớp Bảng 3.11 Test Cross - So sánh kết phân lớp sử dụng SVM, Navies Bayes, J48 Neural Network Decision SVM Tree Navie Neural Bayes Network Precision 78.6% 40.1% 58.8% 76.4% Recall 80.0% 47.2% 63.0% 77.2% F-Measure 79.3% 43.4% 60.8% 76.8% 3.3.4 Thực nghiệm Test Cross validation với liệu xét đến ngày nghỉ lễ Để bám sát với thực tế hơn, thực nghiệm test với liệu thông thường, luận văn đề cập việc thực test với liệu có thông tin ngày nghỉ lễ xây dựng chương trước Phương thức test lựa chọn Test Cross validation với liệu có chứa thơng tin ngày nghỉ lễ: 76 a Mơ hình Decision Tree Kết test: Bảng 3.12 Test Cross Validation - Kết test mơ hình Decision Tree Chi tiết độ xác phân lớp Avg Precision Recall F-Measure Class 79.4% 100.0% 88.5% S1 79.4% 77.2% 78.3% S2 41.3% 52.5% 46.2% S3 4.1% 78.8% 7.8% S4 79.8% 79.8% 79.8% S5 79.4% 100.0% 88.5% S6 74.3% 79.4% 76.8% b Mơ hình Super Vector Machines (SVM) Kết test: Bảng 3.13 Test Cross Validation - Kết test mơ hình SVM Chi tiết độ xác phân lớp Avg Precision Recall F-Measure Class 51.2% 75.0% 60.9% S1 32.1% 76.5% 45.2% S2 32.1% 12.3% 17.8% S3 71.2% 0.3% 0.6% S4 22.6% 7.5% 11.3% S5 23.2% 29.5% 26.0% S6 39.9% 40.2% 40.0% 77 c Mơ hình Naive Bayes Kết test: Bảng 3.14 Test Cross Validation - Kết test mơ hình Nạve Bayes Chi tiết độ xác phân lớp Avg Precision Recall F-Measure Class 60.6% 54.0% 57.1% S1 40.8% 56.7% 47.5% S2 33.1% 29.4% 31.1% S3 65.5% 92.5% 76.7% S4 66.3% 54.2% 59.6% S5 70.4% 6.1% 11.2% S6 54.1% 51.3% 52.7% d Mơ hình Neural Network Kết test: Bảng 3.15 Test Cross Validation - Kết test mơ hình Neural Network Chi tiết độ xác phân lớp Avg Precision Recall F-Measure Class 80.5% 80.5% 80.5% S1 69.8% 69.8% 69.8% S2 17.7% 17.7% 17.7% S3 79.4% 87.2% 83.1% S4 75.5% 75.5% 75.5% S5 79.5% 79.5% 79.5% S6 79.5% 79.5% 79.5% 79 3.3.6 Thực nghiệm với mức độ tắc đường khác a Thực nghiệp với số lớp (mức độ tắc đường) Decision SVM Tree Navie Neural Bayes Network Precision 80.5% 58.9% 57.5% 75.0% Recall 80.5% 71.9% 69.7% 76.1% F-Measure 80.5% 64.8% 63.0% 75.5% Decision SVM Navie Neural Tree Bayes Network b Thực nghiệp với số lớp (mức độ tắc đường) Precision 80.1% 31.0% 48.7% 71.6% Recall 80.2% 51.4% 56.2% 71.6% F-Measure 80.1% 38.7% 52.2% 71.6% Decision SVM Navie Neural Tree Bayes Network c Thực nghiệp với số lớp (mức độ tắc đường) Precision 82.3% 38.9% 49.9% 76.5% Recall 81.7% 53.5% 58.6% 76.1% F-Measure 82.0% 45.0% 53.9% 76.3% Decision SVM Navie Neural Tree Bayes Network d Thực nghiệp với số lớp (mức độ tắc đường) Precision 78.6% 40.1% 54.8% 76.4% Recall 80.0% 47.2% 51,3% 77.2% F-Measure 79.3% 43.4% 53.0% 76.8% 80 3.3.7 Biểu đồ so sánh kết thực nghiệm với mật độ giao thông khác Kết thực nghiệm với mật độ giao thông khác 100 80 60 40 20 Class = Navie Bayes Class = Decision Tree Class = SVM Class = Neural NetWork Biểu đồ 3.2 Kết thực nghiệm với mật độ giao thông khác Dựa vào biểu đồ ta thấy - Với phân lớp Decision Tree J48, kết tương đối xác (giữ mức 80%) không bị phụ thuộc vào số lượng class - Với phân lớp Neural Network, độ xác thấp hơn, giữ ổn định 76% không bị ảnh hưởng nhiều vào số lượng class - Với phân lớp SVM Navie Bayes, độ xác thấp SVM thể rõ yếu chạy với số lượng class lớn Như vậy, phân lớp nên lựa chọn để sử dụng Dự đốn lộ trình Giao thơng Decision Tree J48 ... xây dựng mơ hình dự đốn áp dụng vào thực tế sống người Tìm hiểu số ứng dụng thực tế hệ thống khối máy học MLBlocks Ứng dụng hệ thông máy học MLBlocks vào việc dự đoán điểm đến toán giao thông. .. khối máy học áp dụng để giải tốn tối ưu giao thơng CHƯƠNG 3: ỨNG DỤNG MLBLOCKS TRONG VIỆC DỰ ĐỐN LỘ TRÌNH TỐI ƯU TRONG GIAO THÔNG TẠI THÀNH PHỐ ĐÀ NẴNG Trình bày q trình dự đốn lộ trình tối ưu giao. ..ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM ĐẶNG THÁI DUY NGHIÊN CỨU HỆ THỐNG KHỐI MÁY HỌC MLBLOCKS VÀ ỨNG DỤNG VÀO DỰ ĐỐN LỘ TRÌNH TỐI ƯU TRONG GIAO THƠNG Chun ngành: Hệ thống thơng tin