Tài liệu Nội suy thời gian đến tại một trạm xe buýt trên bản đồ không gian thời gian

ỦY BAN NHÂN DÂN TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT ĐẶNG NHƯ PHÚ NỘI SUY THỜI GIAN ĐẾN TẠI MỘT TRẠM CỦA XE BUÝT TRÊN BẢN ĐỒ KHÔNG GIAN – THỜI GIAN CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 8480104 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. TRẦN VĨNH PHƯỚC BÌNH DƯƠNG - 2019 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi và được sự hướng dẫn khoa học của Thầy PGS. TS. Trần Vĩnh Phước. Các nội dung nghiên cứu, kết quả trong đề tài này là trung thực và chưa công bố bất kỳ dưới hình thức nào từ trước đến nay. Những số liệu phục vụ cho việc phân tích, nhận xét, đánh giá được chính tác giả thu thập trong quá trình thực nghiệm tại các trạm xe buýt ở thành phố Hồ Chí Minh. Ngoài ra, luận văn còn sử dụng các bài báo của các tác giả đã nghiên cứu trước đây để phục vụ cho việc nghiên cứu và ứng dụng nhằm xử lý các vấn đề được nêu ra trong luận văn. Các nội dung, nhận xét, đánh giá, hình ảnh và số liệu của các tác giả khác được nêu trong luận văn đều có trích dẫn và chú thích nguồn gốc. Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách nhiệm về nội dung luận văn của mình. Trường đại học Thủ Dầu Một và giáo viên hướng dẫn không liên quan đến những vi phạm tác quyền, bản quyền do tôi gây ra trong quá trình thực hiện (nếu có). Bình Dương, ngày 01 tháng 3 năm 2019 Tác giả Đặng Như Phú ii LỜI CẢM ƠN Để hoàn thành luận văn này, em xin chân thành gửi lời cảm ơn đến Trường đại học Thủ Dầu Một. Cảm ơn Ban Giám hiệu Nhà trường đã tạo điều kiện tốt nhất để em có thể thực hiện tốt luận văn. Cảm ơn Phòng Sau đại học đã giúp đỡ và hướng dẫn em cách trình bày luận văn đúng theo quy định và em cũng cảm ơn các quý Thầy Cô trong Khoa Kỹ thuật - công nghệ đã dạy cho em những kiến thức nền tảng, thực tế để em có thể tự tin làm tốt được luận văn. Cảm ơn các bạn trong lớp cao học CH16TH01 – Chuyên ngành Hệ thống thông tin đã động viên, chia sẻ kinh nghiệm cho em. Đặc biệt, em xin cảm ơn giảng viên hướng dẫn PGS. TS. Trần Vĩnh Phước đã tận tâm truyền đạt những kiến thức về lĩnh vực Trực quan hóa dữ liệu và những tài liệu bổ ích mà Thầy dày công nghiên cứu để em được khai sáng tri thức. Thầy cũng đã tận tình hướng dẫn, giúp đỡ em hết lòng từ khi bắt đầu thực hiện đề tài cho đến khi hoàn thành. Em xin ghi khắc công ơn này. Từ đáy lòng mình, em xin biết ơn vô hạn tới gia đình thân yêu, công sinh thành, nuôi dưỡng và sự động viên của bố mẹ đã cho em động lực để nghiên cứu và hoàn thiện luận văn. Cám ơn những người bạn thân thiết đã chăm sóc, khích lệ em trong quá trình nghiên cứu. Em xin kính chúc quý Thầy Cô và các bạn thật nhiều sức khỏe, niềm vui và luôn thành công trong công việc và cuộc sống. iii TÓM TẮT LUẬN VĂN Bản đồ không gian - thời gian là một hình khối không gian – thời gian, các hành trình của các xe buýt qua các trạm sẽ được trực quan hóa trên bản đồ này. Với mỗi tuyến, một hành trình của một xe buýt đi qua tất cả các trạm dừng được biểu diễn trên bản đồ không gian - thời gian là một đường cong liên tục nối các điểm không gian - thời gian. Trong thực tế, hầu hết các xe buýt đến trạm là không đúng theo thời gian quy định (sớm hoặc muộn). Do đó, để hỗ trợ hành khách đánh giá thời gian đến trạm của xe buýt và hỗ trợ các chuyên giá dựa vào đó để đánh giá tình hình giao thông tại thành phố, một lý thuyết tập mờ đã được đề xuất nhằm mờ hóa thời gian đến thực tế của xe buýt tại một trạm dừng thông qua một cặp (T i, mi) với i=[1,5], mi chính là xác xuất đến trạm thuộc khoảng thời gian Ti được thống kê trong khoảng thời gian 30 ngày trước đó. Phương pháp này chỉ cho phép người dùng xem xét tình hình đến trạm của xe buýt của các ngày trước đó để đưa ra nhận định thời gian đến trạm của xem buýt tại thời điểm hiện tại. Do đó, để hỗ trợ người dùng dự đoán thời gian đến trạm của xe buýt tại từng thời điểm quan sát, phương pháp nội suy sai phân tiến Newton (Newton’s forward difference interpolation) được sử dụng để nội suy thời gian đến trạm của xe buýt, sau đó sử dụng mạng LSTM Networks điều chỉnh độ sai lệch giữa thời gian thực tế và thời gian nội suy. Khi đó, thời gian đến dự kiến được biểu diễn trên bản đồ không gian thời gian là một bộ (t’, p), trong đó t’ là thời gian dự đoán xe buýt sẽ đến trạm, p độ chính xác (%). Việc biểu diễn thời gian đến trên bản đồ không gian-thời gian sẽ giúp cho hành khách đón xe buýt hiệu quả hơn và các nhà quản lý xe buýt có thể xem xét và đánh giá mức độ tắc đường trên mọi hành trình và khả năng lái xe của các tài xế. iv MỤC LỤC LỜI CAM ĐOAN ............................................................................................... II LỜI CẢM ƠN ................................................................................................... III TÓM TẮT LUẬN VĂN ................................................................................... IV MỤC LỤC ......................................................................................................... V DANH MỤC BẢNG BIỂU ............................................................................. VII DANH MỤC HÌNH, ĐỒ THỊ ........................................................................ VIII DANH MỤC CÁC TỪ VIẾT TẮT................................................................... IX CHƯƠNG 1: GIỚI THIỆU..................................................................................1 1.1. ĐẶT VẤN ĐỀ NGHIÊN CỨU .....................................................................1 1.2. PHÁT BIỂU VẤN ĐỀ NGHIÊN CỨU.........................................................2 1.3. MỤC TIÊU ...................................................................................................3 1.4. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU ...............................................3 1.4.1. Đối tượng nghiên cứu ............................................................................3 1.4.2. Phạm vi nghiên cứu ...............................................................................4 1.5. PHƯƠNG PHÁP NGHIÊN CỨU .................................................................4 1.6. CÂU HỎI NGHIÊN CỨU ĐẶT RA ĐỂ GIẢI QUYẾT BÀI TOÁN ............4 1.7. CẤU TRÚC LUẬN VĂN .............................................................................5 CHƯƠNG 2: TỔNG QUAN VỀ CÁC NGHIÊN CỨU ĐƯỢC LIÊN QUAN .....7 2.1. GIỚI THIỆU ................................................................................................7 2.2. CÁC KHÁI NIỆM ĐƯỢC LIÊN QUAN ......................................................7 2.3. TRỰC QUAN HÓA .....................................................................................8 2.3.1. Tổng quan .............................................................................................8 2.3.2. Trực quan hóa dữ liệu .......................................................................... 11 2.4. BẢN ĐỒ KHÔNG GIAN – THỜI GIAN ................................................... 11 2.5. NỘI SUY SAI PHÂN TIẾN NEWTƠN ..................................................... 13 2.6. MẠNG LSTM ............................................................................................ 14 2.6.1. Tổng quan ........................................................................................... 14 2.6.2. Mô hình mạng LSTM ..........................................................................15 2.6.3. Ý tưởng cơ bản của mạng LSTM .........................................................16 2.6.3.1. Trạng thái tế bào (Cell State) ........................................................ 16 2.6.3.2. Cấu trúc cổng (Gates) ................................................................... 17 2.6.4. Một số biến thể của mạng LSTM ......................................................... 19 CHƯƠNG 3: NỘI SUY THỜI GIAN ĐẾN TẠI MỘT TRẠM CỦA XE BUÝT .......................................................................................................................... 21 v 3.1. QUY TRÌNH TỔNG QUÁT....................................................................... 21 3.2. XÂY DỰNG HÀM NỘI SUY SAI PHÂN TIẾN NEWTƠN ...................... 23 3.2.1. Chuẩn hóa dữ liệu thời gian đã thu thập ............................................... 23 3.2.2. Lựa chọn bậc sai phân ......................................................................... 23 3.2.3. Tổng kết .............................................................................................. 26 3.3. SỬ DỤNG MẠNG LSTM ĐỂ DỰ ĐOÁN ĐỘ SAI LỆCH THỜI GIAN ...27 3.3.1. Xây dựng bộ dữ liệu huấn luyện và kiểm tra ........................................ 27 3.3.2. Mô hình mạng LSTM áp dụng để huấn luyện và dự đoán .................... 30 3.3.2. Đánh giá hiệu quả của việc huấn luyện trên mô hình mạng LSTM ......30 3.3.4. Các bước thực hiện .............................................................................. 31 3.4. BIỂU DIỄN GIÁ TRỊ NỘI SUY TRÊN BẢN ĐỒ KHÔNG GIAN – THỜI GIAN ................................................................................................................ 32 3.5. CÁC GIẢI THUẬT ÁP DỤNG .................................................................. 35 3.5.1. Giải thuật tổng quát ............................................................................. 35 3.5.2. Giải thuật chuẩn hóa dữ liệu ................................................................ 36 3.5.3. Giải thuật lựa chọn bậc sai phân .......................................................... 37 3.5.4. Giải thuật huấn luyện dữ liệu ............................................................... 38 3.6. KẾT LUẬN ................................................................................................ 39 CHƯƠNG 4: KẾT QUẢ NGHIÊN CỨU VÀ ĐÁNH GIÁ KẾT QUẢ .............. 41 4.1. DỮ LIỆU THU THẬP................................................................................ 41 4.2. CHUẨN HÓA DỮ LIỆU............................................................................43 4.3. LỰA CHỌN BẬC SAI PHÂN ................................................................... 44 4.4. ÁP DỤNG MÔ HÌNH LSTM ĐỂ HUẤN LUYỆN VÀ DỰ ĐOÁN KẾT QUẢ.................................................................................................................. 48 4.5. ĐÁNH GIÁ KẾT QUẢ .............................................................................. 50 4.5.1. Phương pháp nội suy sai phân tiến Newtơn ......................................... 50 4.5.1. Phương pháp mạng LSTM ................................................................... 51 4.6. MÔ PHỎNG TRÊN ĐIỆN THOẠI ............................................................ 52 4.7. KẾT LUẬN ................................................................................................ 54 CHƯƠNG 5: KẾT LUẬN .................................................................................55 5.1. KẾT QUẢ ĐẠT ĐƯỢC ............................................................................. 55 5.2. HƯỚNG NGHIÊN CỨU ............................................................................ 56 TÀI LIỆU THAM KHẢO ................................................................................. 57 vi DANH MỤC BẢNG BIỂU Bảng 2.1: Bảng tính sai phân tiến cấp n ............................................................. 14 Bảng 3.1: Bảng chuyển đổi thời gian có dạng hh:mm:ss sang dạng giây ............ 23 Bảng 3.2: Bảng giá trị t’i , Δk,i ứng với bậc sai phân k ....................................... 25 Bảng 3.3: Bảng tính độ sai lệch thời gian trung bình Δk,avg theo bậc sai phân k ..26 Bảng 3.4: Bảng sai phân bậc kselect với các mốc có giá trị t0, t1, t2,…, tkselect ... 28 Bảng 3.5: Bảng sai phân bậc kselect tổng quát...................................................... 29 Bảng 3.6: Thời gian nội suy và độ sai lệch tương ứng, với s=n-kselect ................. 29 Bảng 4.1: Số liệu thời gian xe buýt đến trạm dừng thực tế ................................. 42 Bảng 4.2: Số liệu thời gian đến trạm dừng của các xe buýt được chuẩn hóa ......44 Bảng 4.3: Giá trị nội suy tại trạm 1 theo bậc sai phân từ 2 đến 5 ........................46 Bảng 4.4: Độ sai lệch giữa thời gian nội suy với thời gian thực tế tại trạm 1 theo bậc sai phân k = 2,3,4,5 ............................................................................. 47 Bảng 4.5: Trung bình cộng độ sai lệch thời gian giữa thời gian nội suy với thời gian thực tế theo bậc sai phân từ 2 đến 5 tại 5 trạm dừng xe buýt ..............48 Bảng 4.6: Thời gian dự đoán đến trạm của xe buýt tại 5 trạm ............................ 49 Bảng 4.7: Thời gian dự kiến mà xe buýt sẽ đến tại 5 trạm.................................. 49 vii DANH MỤC HÌNH, ĐỒ THỊ Hình 2.1: Mô hình trực quan hóa thông tin biểu diễn dân số nước Mỹ năm1999 9 Hình 2.2: Mô hình trực quan hóa dữ liệu để biểu diễn sơ yếu lý lịch.................. 10 Hình 2.3: Bản đồ hành quân của Napoleon khi rút quân khỏi Mowcow (18121813) ......................................................................................................... 10 Hình 2.4: Biểu diễn sự di chuyển của xe buýt trên hình khối không gian-thời gian ........................................................................................................... 12 Hình 2.5: Mô hình biểu diễn môdun với một lớp tanh trong mạng RNN chuẩn.. 15 Hình 2.6: Mô hình biểu diễn mô-đun trong mạng LSTM với 4 tầng tương tác ... 15 Hình 2.7: Các ký hiệu trong mạng LSTM .......................................................... 16 Hình 2.8: Trạng thái tế bào (Cell State) ............................................................. 16 Hình 2.9: Cấu trúc cổng (Gates) ........................................................................ 17 Hình 2.10: Mô hình hoạt động cổng (Gates): Sigmoid ....................................... 17 Hình 2.11: Mô hình xác định thông tin cần đưa vào:.......................................... 18 Hình 2.12: Mô hình cập nhật trạng thái tế bào cũ vào trạng thái tế bào mới ....... 18 Hình 2.13: Mô hình quyết định của cổng về việc đưa thông tin đầu ra ............... 19 Hình 2.14: Mạng LSTM được thêm các đường kết nối “peephole connections” 20 Hình 2.15: Mô hình mạng LSTM với hai cổng loại trừ và đầu vào được nối với nhau .......................................................................................................... 20 Hình 2.16: Mô hình mạng LSTM được đề xuất bởi Cho và các cộng sự năm 2014 .......................................................................................................... 20 Hình 3.1: Quy trình thực hiện ............................................................................ 22 Hình 3.2: Quá trình nội suy thời gian đến trạm của xe buýt ............................... 24 Hình 3.3: Mô hình mạng LSTM áp dụng để dự đoán độ sai lệch thời gian ......... 30 Hình 3.4: Biểu diễn các hành trình trên bản đồ không gian-thời gian ................. 33 Hình 3.5: Biểu diễn điểm không gian-thời gian và giá trị thời gian trên bản đồ không gian-thời gian ................................................................................. 34 Hình 4.1: Mô hình hiển thị các tuyến xe buýt và các trạm dừng ......................... 53 Hình 4.2: Mô hình hiển thị thời gian dự kiến mà xe buýt sẽ đến tại một trạm dừng .......................................................................................................... 54 viii DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt LSTM LSTM Networks Mô tả Long short-term memory: Bộ nhớ dài-ngắn Mạng bộ nhớ dài-ngắn RNN Recurrent Neural Network: Mạng Nơron hồi quy MSE Mean Square Error: Sai số toàn phương trung bình RMSE Root Mean Square Error: Sai số toàn phương trung bình gốc ix Chương 1 GIỚI THIỆU 1.1. ĐẶT VẤN ĐỀ NGHIÊN CỨU Phương tiện công cộng là một trong những giải pháp hàng đầu được áp dụng tại các thành phố lớn ở Việt Nam để hạn chế tình trạng ùn tắc giao thông, ô nhiễm môi trường, tai nạn giao thông,… Qua khảo sát thực nghiệm tại thành phố Hồ Chí Minh, do lượng dân cư tập trung đúc nên có nhiều phương tiện di chuyển nên hiện tượng ùn tắc giao thông vẫn thường xuyên xảy ra. Đây cũng là lý do mà hầu hết các xe buýt thường đến trạm không đúng theo thời gian quy định bởi các vấn đề giao thông ở thành phố Hồ Chí Minh như: tình trạng kẹt xe, ách tắc giao thông,…. Để hỗ trợ hành khách xác định thời gian mà xe buýt sẽ đến trạm và giúp các chuyên gia đánh giá tình hình giao thông tại thành phố một lý thuyết tập mờ được đề xuất nhằm biểu diễn thời gian không chắc chắn trên hình khối không gian – thời gian. Tuy nhiên, do dữ liệu biểu diễn trên hình khối này được thống kê trong 30 ngày trước đó, vì vậy việc dự đoán thời gian xe buýt đến trạm là chưa chính xác. Vấn đề được đặt ra ở đây là xây dựng một mô hình nội suy nhằm dự đoán thời gian đến trạm của xe buýt để hỗ trợ các hành khách chủ động thời gian để đón xe buýt kịp giờ và không bị lãng phí thời gian chờ xe buýt. Nội suy là một trong những phương pháp ước tính giá trị của các điểm dữ liệu chưa biết trong phạm vi của một tập hữu hạn rời rạc các giá trị thông qua một hàm số. Từ bộ dữ liệu là thời gian thực tế mà các xe buýt đến trạm dừng, tiến hành áp dụng phương pháp nội suy để ước lượng thời gian mà xe buýt sẽ đến trạm. Bản đồ không gian – thời gian được đề xuất nhằm biểu diễn trực quan bản đồ xe buýt của thành phố là một trong những phương pháp giúp hành khách cũng như các nhà nghiên cứu có cái nhìn trực quan về tình hình xe buýt đến trạm trong ngày. Dự báo thời gian xe buýt sẽ đến trạm sẽ giúp cho các hành khách định lượng 1 được thời gian mà xe buýt sẽ đến trạm thông qua các giá trị ước lượng từ phương pháp nội suy. Đồng thời, cho phép các nhà nghiên cứu xem xét và đánh giá tình hình giao thông tại thành phố để đưa ra các chiến lược và xây dựng cơ sở hạ tầng giao thông bền vững nhằm hạn chế tình trạng ùn tắc giao thông. Tuy nhiên, vấn đề đặt ra ở đây là làm thế nào để ước lượng thời gian đến trạm của xe buýt và cách thức biểu diễn dữ liệu ước lượng này trên bản đồ không gian – thời gian. Đây cũng chính là lý do mà đề tài “Nội suy thời gian đến tại một trạm của xe buýt trên bản đồ không gian – thời gian” được nghiên cứu để giải quyết vấn đề trên. 1.2. PHÁT BIỂU VẤN ĐỀ NGHIÊN CỨU Bản đồ không gian–thời gian là hình khối không gian-thời gian [1], mô hình di chuyển của các xe buýt trên bản đồ chính là sự kết hợp giữa mặt phẳng (x,y) biểu diễn bản đồ của thành phố với trục thời gian biểu diễn thời gian đến trạm của mỗi xe buýt. Xe buýt, trạm dừng xe buýt chính là các đối tượng không gian; thời gian đến của các xe buýt tại trạm dừng TD được biểu diễn trên trục thời gian theo thứ tự, đây chính là điểm không gian-thời gian trên bản đồ không gian-thời gian. Khi đó, việc di chuyển một đối tượng xe buýt trên bản đồ không gian-thời gian được xem như là đường kết nối các điểm không gian-thời gian. Một tuyến xe buýt có thể thực hiện nhiều hành trình trong một ngày và các hành trình của các xe buýt được đánh số theo thứ tự thời gian xuất phát. Về lý thuyết, mỗi hành trình xe buýt sẽ đến trạm theo thời gian quy định là t, tuy nhiên trong thực tế các xe buýt này sẽ đến trạm không theo đúng thời gian quy định (có thể đến sớm hoặc muộn), gọi đây là thời gian thực tế t’. Để hỗ trợ người dùng xác định thời gian mà xe buýt sẽ đến trạm, lý thuyết tập mờ được đề xuất nhằm biểu diễn thời gian không chắc chắn [2] (thời gian thực tế) của xe buýt khi đếm trạm dừng, bài toán xem xét trên phương diện xe buýt đến trạm là muộn hơn so với thực tế nhưng không quá 20 phút, khoảng thời gian tối đa này được chia thành 5 mức trễ khác nhau ([0;2],(2;5],(5;9],(9;14] và (14;20]), thời gian không chắc chắn này được mờ hóa bởi một hàm liên thuộc m(t’), hàm liên 2 thuộc này được xây dựng dựa trên phương pháp tỷ lệ phần trăm theo 05 mức trễ từ số liệu thống kê của 30 ngày trước đó. Thông qua việc biểu diễn trên mô hình trực quan hóa dữ liệu, hành khách có thể ước lượng được khoảng thời gian xe buýt sẽ đến trạm ở thời điểm hiện tại và các nhà nghiên cứu, hoạch định có thể đánh giá tình trạng giao thông tại thành phố. Do dữ liệu chỉ lấy trong 30 ngày và hàm liên thuộc được xây dựng dựa trên phương pháp thống kê theo tỷ lệ phần trăm, nên việc hỗ trợ cho người dùng dự đoán và đánh giá thời gian xe đến trạm ngay thời điểm hiện tại là không tối ưu. Vì vậy trong khuôn khổ bài báo này, một hướng nghiên cứu mới được đề xuất nhằm hỗ trợ người dùng tốt hơn trong việc dự đoán thời gian đến trạm của xe buýt bằng cách sử dụng phương pháp nội suy sai phân tiến Newton (Newton’s forward difference interpolation), sau đó sử dụng mô hình mạng LSTM điều chỉnh độ sai lệch giữa thời gian thực tế với thời gian nội suy. Từ việc áp dụng phương pháp trên, sẽ thu được một bộ (t’, p), trong đó t’ là thời gian dự đoán xe buýt sẽ đến trạm, p độ chính xác (%). Sau đó, kết quả này sẽ được biểu diễn trên bản đồ không gian-thời gian. 1.3. MỤC TIÊU Mục tiêu đề tài “Nội suy thời gian đến tại một trạm của xe buýt trên bản đồ không gian – thời gian” nhằm xây dựng giải thuật nhằm ước lượng thời gian đến trạm của xe buýt thông qua phương pháp nội suy kết hợp với mạng LSTM, và đồng thời đưa ra phương pháp biểu diễn các tuyến, hành trình và thời gian đến trạm của xe buýt trên bản đồ không gian – thời gian. 1.4. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU 1.4.1. Đối tượng nghiên cứu Thời gian đến trạm dừng của các xe buýt tại thành phố Hồ Chí Minh. Các hành trình di chuyển của các xe buýt khi đi qua các trạm dừng trên bản đồ xe buýt tại thành phố Hồ Chí Minh. 3 1.4.2. Phạm vi nghiên cứu Mối quan hệ biện chứng giữa các biến không gian, thời gian trong lĩnh vực trực quan hóa dữ liệu với hệ thống bản đồ xe buýt tại thành phố Hồ Chí Minh để biểu diễn trên bản đồ không gian - thời gian. Các mô hình nội suy, máy học để ước lượng thời gian mà xe buýt sẽ đến trạm từ tập dữ liệu thời gian đã thu thập. Các mô hình, phương pháp trực quan hóa dữ liệu 1.5. PHƯƠNG PHÁP NGHIÊN CỨU Phương pháp quan sát: được áp dụng để thu thập dữ liệu và nghiên cứu các quy luật đi đến trạm dừng của các xe buýt để trực quan hóa lên bản đồ không gian – thời gian. Phương pháp toán: được áp dụng để ước lượng thời gian đến của xe buýt, tính toán độ sai lệch thời gian. Phương pháp phân tích: Trên cơ sở dữ liệu thu thập được qua quá trình thực nghiệm tại các trạm dừng xe buýt tại thành phố Hồ Chí Minh, kết hợp với các lý thuyết đã học, các bài báo khoa học và các nghiên cứu trước đây của các tác giả. Cùng với sự chỉ bảo, hướng dẫn của Thầy hướng dẫn, em đã tiến hành phân tích dữ liệu thu thập và đề xuất mô hình nội suy kết hợp với mô hình dự đoán của Deep Learning để dự đoán thời gian mà xe buýt sẽ đến trạm và đề xuất cách thức biểu diễn trên thông tin, dữ liệu trên bản đồ không gian – thời gian. 1.6. CÂU HỎI NGHIÊN CỨU ĐẶT RA ĐỂ GIẢI QUYẾT BÀI TOÁN Trong quá trình nghiên cứu và thực hiện đề tài luận văn, phương pháp tự đặt câu hỏi và tự tìm câu trả lời được sử dụng để giải quyết các yêu cầu và nội dung của luận văn, dưới dây là quá trình đặt câu hỏi để tìm câu trả lời cho việc giải quyết bài toán (theo từ trên xuống) như sau: - Phương pháp nào sẽ được áp dụng để dự đoán thời gian đến trạm của xe buýt: Xích Markov, Mô hình hàng chờ (Waiting Line Model), Nội suy, Ngoại suy…? Phương pháp nội suy nào phù hợp với dữ liệu thu thập được? Với phương 4 pháp nội suy sai phân tiến Newtơn, việc chọn bậc sai phân tiến như thế nào là tối ưu? Cách thức và tiêu chí xác định bậc sai phân tiến? - Mô hình nào sẽ được áp dụng để xác định độ chênh lệch giữa thời gian nội suy và thời gian thực tế: áp dụng lại phương pháp Nội suy sai phân tiến Newtơn, nội suy Lagrange, Hồi quy tuyến tính, mạng LSTM,…? Với việc áp dụng mạng LSTM, cách thức huấn luyện dữ liệu trên mô hình đó như thế nào là tối ưu và cách thức biểu diễn thông tin, dữ liệu trên bản đồ không gian - thời gian? 1.7. CẤU TRÚC LUẬN VĂN Luận văn được cấu trúc thành 5 chương, có nội dung như sau:  Chương 1 – Giới thiệu: Trình bày mục tiêu và động lực để nghiên cứu mô hình nội suy thời gian đến trạm của xe buýt trên bản đồ không gian – thời gian, cũng như đối tượng, phạm vi và phương pháp nghiên cứu và cách thức tiếp cận đề tài theo phương pháp phân tích từ trên xuống thông qua việc tự đặt câu hỏi và trả lời.  Chương 2 – Tổng quan về các nghiên cứu được liên quan: Giới thiệu tổng quan về các lý thuyết nghiên cứu được áp dụng trong luận văn: lý thuyết về trực quan hóa dữ liệu, lý thuyết nội suy, máy học và các bài báo tham chiếu.  Chương 3 – Nội suy thời gian đến tại một trạm của xe buýt: Trình bày các quy trình áp dụng để thực hiện việc nội suy thời gian đến trạm của xe buýt và cách thức trực quan hóa thông tin, dữ liệu trên bản đồ không gian – thời gian. Phương pháp xây dựng hàm nội suy sai phân tiến Newtơn cho bộ dữ liệu đã thu thập và ứng dụng phương pháp mạng LSTM để huấn luyện dữ liệu, đồng thời trình bày các giải thuật áp dụng.  Chương 4 – Kết quả nghiên cứu và đánh giá kết quả: Mô tả kết quả thực nghiệm bằng phương pháp nội suy và mô hình mạng LSTM để ước lượng thời gian mà xe buýt sẽ đến trạm dựa trên bộ dữ liệu 5 thu thập được và cách thức biểu diễn dữ liệu trên bản đồ không gian – thời gian.  Chương 5 – Kết luận và hướng phát triển: Trong chương này, luận văn đã tóm tắt các kết quả đạt được thông qua việc đề xuất phương pháp nội suy và mô hình mạng LSTM để ước lượng thời gian đến trạm của xe buýt và phương pháp trực quan hóa thông, dữ liệu trên bản đồ không gian – thời gian. Luận văn cũng đề xuất hướng nghiên cứu mới để ước lượng thời gian đến trạm của xe buýt thông qua việc xây dựng hàm Gauss. 6 Chương 2 TỔNG QUAN VỀ CÁC NGHIÊN CỨU ĐƯỢC LIÊN QUAN 2.1. GIỚI THIỆU Luận văn vận dụng lý thuyết nội suy để ước lượng thời gian đến trạm của xe buýt với các mốc nội suy là thời gian đến trạm thực tế của xe buýt đã được thu thập. Lý thuyết DeepLearning, Mạng Nơron được nghiên cứu để dự đoán độ sai lệch giữa thời gian nội suy với thời gian thực tế mà xe buýt sẽ đến trạm. Lý thuyết về trực quan hóa dữ liệu được ứng dụng để biểu diễn trực quan hóa bản đồ xe buýt và thời gian mà xe buýt sẽ đến trạm. Bên cạnh đó, luận văn cũng được phát triển và xây dựng dựa trên nền tảng nghiên cứu của Thầy PGS.TS Trần Vĩnh Phước và các cộng sự bao gồm: - Visualization of Spatio-temporal Data of Bus Trips - Representing Uncertain Time on Space-time - An Approach to Representing Movement Data - Visualization Cube for Tracking Moving Object 2.2. CÁC KHÁI NIỆM ĐƯỢC LIÊN QUAN Bản đồ không gian – thời gian là một hình khối không gian – thời gian trên hệ tọa độ Đề-các ba chiều nhằm biểu diễn các đối tượng không gian, các đối tượng không-gian thời gian và các đường cong không gian-thời gian có thứ tự nhằm kết nối các đối tượng không gian – thời gian lại với nhau, đây chính là đường biểu diễn sự dịch chuyển của các đối tượng không gian – thời gian. 7 Độ sai lệch thời gian Δt chính là sự sai lệch giữa thời gian t’ được ước lượng từ phương pháp nội suy sai phân tiến Newtơn với thời gian thực tế t mà xe buýt sẽ đến trạm, giá trị này được tính bằng: Δt = t’ – t. Thời gian đến là thời gian thực tế mà xe buýt đến trạm dừng xe buýt. Thời gian thực tế t là thời gian mà xe buýt đến trạm dừng theo thực tế. Thời gian nội suy t’ là thời gian ước lượng mà xe buýt đến trạm dừng thông qua phương pháp nội suy sai phân tiến Newtơn. Sai số toàn phương trung bình (MSE) là một phương pháp dùng để đánh giá các sai số trong các mô hình ước lượng. Sai số này được xác định bằng trung bình cộng của các bình phương sai số giữa giá trị ước lượng với giá trị đánh giá. Sai số toàn phương trung bình gốc (RMSE) được tính bằng căn bậc hai sai số MSE, RMSE được sử dụng để nghiên cứu về khuynh hướng sai số, biên độ sai số tuyệt đối và giá trị sai số thực. Bộ lọc Kalman là một tập hợp các phương trình toán học nhằm cung cấp một phương pháp tính toán đệ quy (recursively) hiệu quả để ước lượng trạng thái của một quá trình, theo cách tối thiểu hóa giá trị trung bình của bình phương lỗi (phương sai: mean squared error). Bộ lọc rất hiệu quả trên các khía cạnh sau: Nó cho phép ước lượng trạng thái quá khứ, hiện tại thậm chí cả tương lai, và bộ lọc có thể hoạt động ngay cả khi độ chính xác thực sự của mô hình hệ thống là chưa biết. 2.3. TRỰC QUAN HÓA 2.3.1. Tổng quan Theo Kaizen [3], trực quan hóa là một trong những kỹ thuật biến đổi thông tin thành những hình ảnh, biểu đồ hoặc hoạt động diễn hoạt để con người có thể quan sát bằng mắt ở bất kỳ thời điểm nào, từ đó thể đưa ra những nhận định, phán đoán tùy theo góc độ, kiến thức, sự hiểu biết… của người quan sát về thông tin đó. 8 Trực quan hóa được phân thành nhiều nhánh để nghiên cứu và phát triển như: + Trực quan hóa khoa học; + Trực quan hóa thông tin; + Trực quan hóa giáo dục; + Trực quan hóa tri thức; + Trực quan hóa dữ liệu; + Trực quan hóa sản phẩm; + Phân tích trực quan; + Truyền thông trực quan; Để phân tích tình hình dân số thế giới hay cụ thể ở một quốc gia nào đó, một số nhà nghiên cứu đã sử dụng phương pháp trực quan hóa thông tin để biểu diễn. Như hình 2.1, các nhà nghiên cứu đã mô tả dân số nước Mỹ năm 1999 thông qua bản đồ để phân tích và so sánh với tình hình dân số với các nước Canada và Áo [4]. Hình 2.1. Mô hình trực quan hóa thông tin biểu diễn dân số nước Mỹ năm 1999 Để trực quan hóa hồ sơ công việc hay sơ yếu lý lịch của nhân viên trong công ty, mô hình trực quan hóa dữ liệu được sử dụng để biểu diễn trực quan thông tin của nhân viên trong công ty như ở hình 2.2. 9 Hình 2.2: Mô hình trực quan hóa dữ liệu để biểu diễn sơ yếu lý lịch1 Tác giả Charles Joseph Minard đã sử dụng mô hình phân tích trực quan để biểu diễn cuộc hành quân của Napoleon năm 1812 – 1813 khi rút quân ra khỏi Mowcow, hình 2.3 biểu diễn biến động số lượng quân của khi rút khỏi Mowcow theo thời gian. Hình 2.3: Bản đồ hành quân của Napoleon khi rút quân khỏi Mowcow (18121813)2 1 2 Hình ảnh tham chiếu tại: https://venngage.com/blog/dos-donts-infographic-resumes/ Hình ảnh tham chiếu tại: https://www.masswerk.at/minard/ 10 2.3.2. Trực quan hóa dữ liệu Trực quan hóa dữ liệu là một nhánh thuộc trực quan hóa, là một thuật ngữ mô tả cho việc biểu diễn trực quan dữ liệu nhằm giúp mọi người dễ hiểu bộ dữ liệu đó thông qua phương pháp trực quan. Qua mô hình trực quan hóa, mỗi người xem sẽ cho một đánh giá khác nhau tùy thuộc vào trình độ, chuyên môn của người xem. Hiện nay, có nhiều công cụ hỗ trợ trực quan hóa bộ dữ liệu mà nó vượt xa các biểu đồ, bảng biểu thống kê thông thường như bộ công cụ văn phòng của Microsoft: Word, Excel, các công cụ này cho phép biểu diễn và tra cứu thông tin, dữ liệu nhiều mức và nhiều chiều. Dữ liệu được hiển thị một cách tinh vi sinh động trên infographics, bản đồ địa lý, biểu đồ thu nhỏ, bản đồ nhiệt và biểu đồ chi tiết, biểu đồ cột,…. Các hình ảnh, đối tượng được trực quan có khả năng tương tác với người dùng để thực hiện các thao tác truy vấn và phân tích. 2.4. BẢN ĐỒ KHÔNG GIAN – THỜI GIAN Bản đồ không gian – thời gian là một hình khối không gian trên hệ tọa độ Đề-các ba chiều nhằm biểu diễn các đối tượng không gian, các đối tượng không gian - thời gian và các đường cong không gian – thời gian có thứ tự nhằm kết nối các đối tượng không gian lại với nhau, đây chính là đường biểu diễn sự dịch chuyển của các đối tượng không gian-thời gian. Trong khuôn khổ luận văn này, bản đồ không gian – thời gian chính là sự kết giữa mặt phẳng bản đồ của thành phố với trục thời gian được biểu diễn vuông góc với mặt phẳng bản đồ. Các đối tượng không gian là các trạm dừng xe buýt và lộ trình mà các xe buýt đi qua các trạm được cố định trên mặt phẳng bản đồ; thời gian đến trạm của các xe buýt được biểu diễn trên trục thời gian. Điểm không gian – thời gian trên bản đồ không gian – thời gian là điểm được kết hợp giữa thời gian được tham chiếu từ trục thời gian t và vị trí khi chiếu vuông góc xuống mặt phẳng bản đồ chính là trạm dừng xe buýt. [5] [6] [7] [8] [9] [10] [11] Một tuyến xe buýt bắt đầu từ điểm xuất phát đến trạm cuối cùng phải đi qua các trạm dừng để đón và trả khách theo quy định. Một tuyến xe buýt được đặt tên bởi tên của điểm đầu và điểm cuối. Trong một ngày, có nhiều hành trình xe buýt 11