Khai thác thông tin tình trạng ùn tắc giao thông từ dữ liệu GPS - Trường hợp thành phố Hồ Chí Minh

36 Journal of Transportation Science and Technology, Vol 20, Aug 2016 KHAI THÁC THÔNG TIN TÌNH TRẠNG ÙN TẮC GIAO THÔNG TỪ DỮ LIỆU GPS - TRƯỜNG HỢP THÀNH PHỐ HỒ CHÍ MINH MINING INFORMATION ABOUT TRAFFIC CONGESTIONS FROM GPS DATA – CASE STUDY OF HO CHI MINH CITY Lê Văn Quốc Anh Khoa CNTT, ĐH GTVT TP.HCM, anh@ut.edu.vn Tóm tắt: Bài báo này đề xuất giải pháp trích xuất thông tin hữu ích về tình trạng giao thông từ dữ liệu GPS thu thập được từ các thiết bị giám sát hành trình của phương tiện giao thông. Giải thuật gom cụm dựa trên mật độ được tích hợp vào trong quy trình khai thác dữ liệu để lọc ra các vị trí thường xuyên ùn tắc trong mạng lưới giao thông đô thị. Chúng tôi tiến hành thực nghiệm trên bộ dữ liệu thật phạm vi Thành phố Hồ Chí Minh và thu được kết quả khá hứa hẹn về mặt ứng dụng. Từ khóa: Dữ liệu hành trình GPS; khai thác dữ liệu; phát hiện ùn tắc. Abstract: This paper presents an approach to the discovery of useful information about traffic condition from GPS data obtained from vehicle tracking devices. A density - based clustering approach is intergrated into the data mining process to figure out the most likely areas of congestions in urban traffic networks. We performed experiments on real - life datasets of Ho Chi Minh City and obtained very promissing results for developing applications. Keywords: Gps trajectory data; data mining; congestion detection. 1. Giới thiệu Khai thác dữ liệu là quá trình tìm kiếm và rút trích những thông tin tiềm ẩn có giá trị, hữu ích từ một khối lượng dữ liệu khá lớn ban đầu. Những thông tin được rút trích được gọi là tri thức, là yếu tố quyết định giúp phát triển các ứng dụng thông minh. Trong lĩnh vực giao thông vận tải, việc sử dụng kết quả từ việc phân tích dữ liệu từ các thiết bị giám sát hành trình, dữ liệu xe con di dộng (FCD) và dữ liệu điện thoại trực tuyến (FPD) đã đem lại những hiệu quả rõ rệt trong vấn đề giám sát và quản lý giao thông [1]. Bài báo này đề cập đến bài toán phân tích hay khai thác dữ liệu hành trình thu thập được từ các thiết bị thu GPS, gọi tắt là dữ liệu GPS, để trích xuất những thông tin có giá trị và hữu ích về tình trạng ùn tắc giao thông của mạng lưới giao thông trong đô thị. Nguồn của dữ liệu GPS khá đa dạng và phổ biến, thông dụng nhất là từ các thiết bị thu GPS gắn trên các phương tiện giao thông hay thu thập qua phần mềm viết cho các điện thoại thông minh. Việc khai thác dữ liệu GPS mang lại khá nhiều ứng dụng hữu ích, như: dự báo tắc nghẽn giao thông [2], khai thác địa điểm quan trọng và lộ trình thông dụng từ dữ liệu GPS [3], quy hoạch sử dụng các lộ trình tối ưu [4]. Mặc dù tính ứng dụng của bài toán này là khá đa dạng nhưng việc xử lý trên dữ liệu GPS và rút trích được những thông tin có giá trị gặp nhiều thách thức. Thứ nhất, với sự ổn định và tính chính xác tương đối, bản thân dữ liệu dạng này xuất hiện khá nhiều điểm dữ liệu nhiễu và mất mát thông tin [5]. Thứ hai, dữ liệu thu thập theo thời gian nên khối lượng dữ liệu để phân tích là khá lớn, có thể xem như là một dạng “Big Data”. Điểm cuối cùng là vấn đề biểu diễn những tri thức khai thác được từ dữ liệu GPS. Rất khó để mô tả hay diễn dịch nếu không sử dụng các công cụ trực quan hoá [6]. Bài báo này trình bày giải pháp hiệu quả cho bài toán trích xuất thông tin về tình trạng ùn tắc giao thông từ dữ liệu GPS với các đóng góp sau:  Mô hình hoá điểm ùn tắc giao thông dựa trên khái niệm Cluster.  Giải quyết vấn đề nhiễu bằng cách tách điểm dữ liệu và gom cụm dựa trên mật độ.  Trực quan hoá các điểm ùn tắc trên bản đồ. 2. Các khái niệm và công trình liên quan 2.1. Mô hình hoá dữ liệu GPS TẠP CHÍ KHOA HỌC CÔNG NGHỆ GIAO THÔNG VẬN TẢI, SỐ 20 - 08/2016 37 Dữ liệu thô thu thập từ các thiết bị thu GPS gọi là GPS Log tồn tại dưới khá nhiều định dạng, trong đó thông dụng là ở định dạng file (CSV, GPX, KML,) hoặc dạng bảng trong một hệ quản trị cơ sở dữ liệu quan hệ (Oracle, MS SQL Server,), tham khảo hình 1. Hình 1. Minh hoạ GPS Log thu thập từ một thiết bị giám sát hành trình phương tiện giao thông. Để có sự chuẩn hoá dữ liệu đầu vào cho giải thuật khai thác dữ liệu sau này, chúng tôi mô hình hoá dữ liệu GPS qua các khái niệm sau đây:  Toạ độ GPS: Được biểu diễn bởi bộ bốn , trong đó: id là mã định danh của đối tượng chuyển động (phương tiện giao thông hoặc một điện thoại có hỗ trợ GPS); lat là vĩ độ, lon là kinh độ; và time là thời gian ghi nhận vị trí của đối tượng.  GPS Log: Là một tập hợp các toạ độ GPS, có dạng {p1, p2, pn}, với mỗi pi là một toạ độ GPS .  Quỹ đạo GPS: Là một chuỗi gồm các toạ độ GPS thu thập không ngắt quãng của cùng một đối tượng chuyển động, có dạng p1  p2   pn, trong đó: pi.id = pj.id , 1  i, j  n; và 0 < pi+1.time - pi.time < T,  0 < i < n, với T là ngưỡng thời gian ngắt quãng cho phép giữa hai lần thu thập toạ độ liên tiếp. Với các khái niệm mô tả như trên thì các điểm dữ liệu trong dữ liệu thô sẽ được biểu diễn bằng các điểm GPS và dữ liệu đầu vào cho các giải thuật khai thác dữ liệu sẽ là các quỹ đạo GPS được trích xuất từ GPS Log. Khái niệm quỹ đạo GPS có thể hình dung từ hình 2. Chi tiết của quá trình trích xuất sẽ được trình bày trong mục 4.1. Hình 2. Minh hoạ một quỹ đạo GPS trích xuất từ GPS Log, khu vực TP.HCM, xuất phát từ Quận 10, qua Quận 2, và dừng ở Quận 7. 2.2. Gom cụm dữ liệu dựa trên mật độ - Giải thuật DBSCAN Giải thuật DBSCAN [7] là giải thuật gom cụm dữ liệu dựa trên mật độ được đánh giá là khá hiệu quả trong việc gom cụm điểm dữ liệu có yếu tố nhiễu. Ngoài ra, những đặc tính khác của giải thuật này rất phù hợp để được lựa chọn trong bài toán phát hiện điểm ùn tắc giao thông, như: Không yêu cầu cung cấp trước số lượng cụm (trong trường hợp này là số điểm ùn tắc); phát hiện được điểm ùn tắc với dạng hình học bất kỳ và có thể kết hợp với các cấu trúc dữ liệu (như R* Tree [8]) để tăng tốc quá trình xử lý với dữ liệu lớn. Do giải thuật này khá thông dụng nên bài báo sẽ không trình bày chi tiết giải thuật này. Độc giả quan tâm có thể tham khảo ở [7]. Với những tính chất đã nêu ở trên, giải thuật gom cụm dựa trên mật độ DBSCAN được lựa chọn cho hướng tiếp cận được đề xuất trong bài báo này. 2.3. Tình hình nghiên cứu gần đây Một số công trình liên quan đến bài toán khai thác dữ liệu GPS được công bố gần đây, với các mục tiêu khác nhau: Ước lượng tốc độ di chuyển trung bình của dòng giao thông từ dữ liệu hành trình GPS [9], phát hiện các dạng tắc nghẽn từ dữ liệu xe con lưu động (FCD) [10] hay khám phá đường đi ít tốn thời gian nhất [11]. Các giải pháp này chủ yếu dựa trên thống kê để ước lượng vận tốc trung bình của dòng giao thông và nếu áp dụng trên dữ liệu 38 Journal of Transportation Science and Technology, Vol 20, Aug 2016 thực nghiệm giới thiệu phần sau thì kết quả không tốt. Ngoài kỹ thuật thống kê, bài báo này đề xuất sử dụng giải thuật gom cụm dựa trên mật độ để loại bỏ nhiễu và tăng chất lượng kết quả, như phần thực nghiệm sẽ trình bày. 3. Nguồn dữ liệu thực nghiệm Để thực hiện việc kiểm nghiệm quy trình khai thác thông tin vị trí ùn tắc đề xuất ở trên, chúng tôi sử dụng dữ liệu GPS Log thu thập từ các phương tiện vận tải cung cấp bởi công ty OTS cung cấp dịch vụ giám sát hành trình xe ô tô. Số lượng xe được giám sát hành trình trong nguồn dữ liệu này là 411, khu vực thành phố Hồ Chí Minh (TP.HCM). Thời gian thu thập dữ liệu trong vòng một tuần, từ 01/06/2015 đến 07/06/2015. Hình 3 minh hoạ dữ liệu GPS Log được hiển thị trên bản đồ nền của TP.HCM. Có khá nhiều điểm nhiễu trong dữ liệu cần làm sạch. Hình 3. Dữ liệu thô chưa qua tiền xử lý và làm sạch dữ liệu. Xuất hiện một số đoạn nối các điểm không đúng thực tế. Hình 4. Dữ liệu thực nghiệm sau khi tiền xử lý loại bỏ các điểm nhiễu và tách các đoạn quỹ đạo. 4. Khai thác thông tin địa điểm ùn tắc từ dữ liệu GPS 4.1. Tiền xử lý và làm sạch dữ liệu Dữ liệu thô ban đầu ở dạng GPS Log sẽ được tách thành các tập toạ độ GPS theo định danh của thiết bị. Các toạ độ GPS trong mỗi tập được sắp xếp theo thứ tự thời gian để tạo thành một chuỗi toạ độ GPS cho mỗi đối tượng chuyển động. Với một giá trị ngưỡng thời gian ngắt quãng T cho trước, chuỗi toạ độ được quét tuần tự để tìm các điểm cắt (điểm cắt là điểm có khoảng cách thời gian đến điểm kế tiếp vượt qua ngưỡng T). Các phân đoạn thu được giữa các điểm cắt chính là các quỹ đạo GPS. Trong trường hợp dữ liệu GPS Log thu thập từ các phương tiện giao thông thì ngưỡng thời gian T có thể chọn là từ 30 phút đến 1 giờ, đây là thời gian các xe vận tải dừng đỗ tại trạm, bến, bãi. Tuy nhiên, rõ ràng là giá trị của ngưỡng thời gian này được chọn tuỳ thuộc vào đặc thù của từng loại dữ liệu thu thập được. Các phân đoạn thu được từ bước xử lý nêu trên là các chuỗi toạ độ GPS đảm bảo tính liên tục về thời gian giữa hai điểm liên tiếp. Trong thực tế, một số trường hợp thiết bị thu GPS ghi nhận toạ độ GPS không chính xác, dẫn đến mất tính liên tục về không gian trong chuỗi toạ độ GPS. Hình 5 minh hoạ một toạ độ GPS nhiễu được ghi nhận. Hình 5. Minh hoạ một toạ độ GPS nhiễu nằm cách xa quỹ đạo di chuyển. Do khoảng cách thời gian giữa các lần thu thập toạ độ thường là khá bé (vài giây) nên việc loại bỏ các toạ độ nhiễu này không ảnh hưởng đến tính liên tục về thời gian trong chuỗi quỹ đạo. Để thuận lợi trong các bước xử lý sau, giai đoạn tiền xử lý dữ liệu sẽ loại bỏ các toạ độ GPS nhiễu bằng cách sử dụng một ngưỡng khoảng cách d. Tuỳ thuộc vào tốc độ tối đa của phương tiện và khoảng cách thời gian giữa hai lần thu thập toạ độ GPS liên tiếp mà chọn giá trị ngưỡng khoảng cách d phù hợp. Với khoảng cách thời gian là 10s thì d có thể chọn là 280m, giả định phương tiện chạy với tốc độ dưới 100km/h. Hình 4 trình bày dữ liệu thô sau bước phân đoạn và làm sạch. Bước tiền xử lý dữ liệu chuyển đổi dữ liệu thô GPS Log sang các quỹ đạo GPS với sự đảm bảo về tính liên tục thời gian và không gian. Đây chính là đầu vào cho quy trình trích TẠP CHÍ KHOA HỌC CÔNG NGHỆ GIAO THÔNG VẬN TẢI, SỐ 20 - 08/2016 39 xuất thông tin vận tốc tức thời và khai thác địa điểm ùn tắc sẽ được trình bày tiếp theo đây. 4.2. Trích xuất thông tin vận tốc tức thời từ quỹ đạo GPS Đa số trường hợp thiết bị giám sát hành trình cũng ghi nhận vận tốc tức thời của phương tiện tại thời điểm thu thập thông tin về vị trí và lưu trữ vào GPS Log. Tuy nhiên một số trường hợp dữ liệu GPS Log không có thông tin về vận tốc tức thời (phần lớn dữ liệu ở dạng các file GPX hay KML). Trong các trường hợp này, vận tốc tức thời có thể được tính thông qua khoảng cách thời gian và không gian giữa hai điểm liên tiếp trong quỹ đạo. Khoảng cách không gian giữa hai toạ độ GPS được tính bằng hàm sau (công thức Haversine): function getDistanceFromLatLon (p1, p2) { R = 6371; // Bán kính Trái đất (km) dLat = (p2.lat-p1.lat)* PI/180; dLon = (p2.lon-p1.lon)* PI/180; a = sin(dLat/2)^2 + cos(p1.lat*PI/180)*cos(p2.lat*PI/180)* sin(dLon/2)^2; c = 2 * arcsin(sqrt(a)); return R * c; } Các vị trí điểm có tốc độ thấp hơn một ngưỡng vận tốc cho trước (ví dụ 5km/h) sẽ được lọc ra để tìm các vị trí thường xuyên ùn tắc. Hình 6 minh hoạ các vị trí có tốc độ di chuyển của các phương tiện trong bộ dữ liệu nghiên cứu của khu vực nội thành Thành phố Hồ Chí Minh có vận tốc di chuyển bé hơn 5km/h. Nhận xét rằng mặc dù vẫn phát hiện một số địa điểm có khả năng ùn tắc cao như giữa các giao lộ, các trục đường chính, nhưng có khá nhiều địa điểm được đánh dấu khá rời rạc, không tập trung. Sử dụng ngưỡng vận tốc để xác định các vị trí trên mạng lưới giao thông mà phương tiện di chuyển chậm. Cần lưu ý rằng không phải vị trí nào phương tiện đi chậm cũng phải là vị trí ùn tắc. Có những vị trí mà phương tiện di chuyển chậm là bình thường, ví dụ xe đi vào bến, xe dừng đèn đỏ, hay xe đi vào các đường nội bộ của khu dân cư. Tuy nhiên, việc phát hiện các vị trí mà phương tiện đi chậm lại vẫn rất hữu ích trong bài toán phát hiện điểm ùn tắc. Rõ ràng là các vị trí này chính là những ứng cử viên cho việc nhận diện vị trí ùn tắc. Thách thức bây giờ là làm sao lọc ra được các điểm ùn tắc thực sự từ danh sách các ứng cử viên này. Hình 6. Các vị trí ghi nhận tốc độ tức thời của đối tượng chuyển động thấp hơn ngưỡng vận tốc 5km/h. 4.3. DBSCAN tìm khu vực ùn tắc Từ tập hợp các vị trí ghi nhận có phương tiện đi chậm, chúng tôi đề xuất sử dụng phương pháp gom cụm dữ liệu theo mật độ, với giải thuật DBSCAN để loại bỏ các điểm ngoại biên. Điểm ngoại biên ở đây được hiểu là các vị trí mà có hiện tượng phương tiện đi chậm là ngẫu nhiên (xe dừng hay đi chậm có chủ đích). Hình 7. Kết quả sau khi dùng DBSCAN loại bỏ các điểm ngoại biên. Hai tham số quan trọng trong giải thuật DBSCAN là khoảng cách Epsilon và số điểm nhỏ nhất để xác định một vùng có mật độ dày (MinPts). Các tham số này được chọn bằng phương pháp thử và sai; giá trị để kết quả gom cụm là tốt nhất cho bộ dữ liệu thí nghiệm là Epsilon = 0.01 và MinPts = 5. Hình 7 minh hoạ các vị trí ùn tắc được ghi nhận sau khi chạy giải thuật DBSCAN. Nhận 40 Journal of Transportation Science and Technology, Vol 20, Aug 2016 xét rằng các vị trí ùn tắc phát hiện được phần lớn là ở các vòng xoay, ngã giao của trục đường chính và đường nhánh. 5. Kết quả và đánh giá Kết quả chạy giải thuật DBSCAN trên bộ dữ liệu nghiên cứu trả về thông tin 412 cụm, đó chính là các vị trí thường xuyên ùn tắc được phát hiện. Để đánh giá tính hợp lý của kết quả, chúng tôi sử dụng phần mềm Quantum GIS ( để trực quan hoá từng điểm ùn tắc trên bản đồ nền để kiểm tra. Hình 7 cho thấy sự phân bố của các vị trí ùn tắc được phát hiện. Các vị trí ùn tắc được phóng lớn để kiểm tra. Ví dụ trong hình 8, các vị trí ùn tắc được phát hiện gần vòng xoay Lăng Cha Cả đều nằm trên các giao lộ và trên thực tế thường xuyên xảy ra ùn tắc. Hình 8. Các điểm thường xuyên ùn tắc được phát hiện tại khu vực vòng xoay Lăng Cha Cả. 6. Kết luận và hướng phát triển Bài báo này đề xuất quy trình khai thác dữ liệu GPS để trích xuất thông tin về tình trạng ùn tắc giao thông. Dữ liệu thực nghiệm được thu thập từ các xe thực tế chạy trên các tuyến đường của Thành phố Hồ Chí Minh. Kết quả đạt được là rất hứa hẹn và trở thành nền tảng cho các ứng dụng tìm đường thông minh có tính đến tình trạng giao thông sau này. Đây cũng là hướng phát triển trong tương lai của hướng tiếp cận vừa trình bày. Lời cảm ơn Nghiên cứu này được hỗ trợ từ nguồn kinh phí nghiên cứu khoa học của Trường Đại học Giao thông vận tải TP. HCM (MS KH1504)  Tài liệu tham khảo [1] M. R. Evans, D. Oliver, X. Zhou, and S. Shekhar, “Spatial Big Data: Volume, Velocity and Veracity,” Big Data Tech. Technol. Geoinformatics, pp. 149–176, 2010. [2] F. Maier, R. Braun, F. Busch, and P. Mathias, “Pattern-based short-term prediction of urban congestion propagation and automatic response,” Traffic Eng. Control, vol. 49, no. 6, pp. 227–232, 2008. [3] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma, “Mining interesting locations and travel sequences from GPS trajectories,” Proc. 18th Int. Conf. World wide web - WWW ’09, 2009. [4] F. Bastani, Y. Huang, X. Xie, and J. W. Powell, “A Greener Transportation Mode: Flexible Routes Discovery from GPS Trajectory Data,” Proc. 19th ACM SIGSPATIAL Int. Conf. Adv. Geogr. Inf. Syst., pp. 405–408, 2011. [5] H. Jeung, H. Lu, S. Sathe, and M. L. Yiu, “Managing evolving uncertainty in trajectory databases,” IEEE Trans. Knowl. Data Eng., vol. 26, no. 7, pp. 1692–1705, 2014. [6] D. Zhang, K. Lee, and I. Lee, “Periodic Pattern Mining for Spatio-Temporal Trajectories: A Survey,” 2015 10th Int. Conf. Intell. Syst. Knowl. Eng., pp. 306–313, 2015. [7] M. Ester, H. Kriegel, J. S, and X. Xu, “A density- based algorithm for discovering clusters in large spatial databases with noise,” in KDD-96, 1996, pp. 226–231. [8] M. Ester, H. Kriegel, J. Sander, M. Wimmer, and X. Xu, “Incremental Clustering for Mining in a Data Warehousing Environment,” in VLDB Conference, 1998, pp. 323–333. [9] I. Barbosa, M. A. Casanova, C. Renso, and J. A. F. de Macedo, “Average Speed Estimation For Road Networks Based On GPS Raw Trajectories,” Iceis 2013, p. 511, 2013. [10] L. Xu, Y. Yue, and Q. Li, “Identifying Urban Traffic Congestion Pattern from Historical Floating Car Data,” Procedia - Soc. Behav. Sci., vol. 96, no. Cictp, pp. 2084–2095, 2013. [11] E.H.C. Lu, W.C.Lee, and V.S.Tseng, “Mining fastest path from trajectories with multiple destinations in road networks,” Knowl. Inf. Syst., vol. 29, no. 1, pp. 25–53, 2011. Ngày nhận bài: 18/07/2016 Ngày chuyển phản biện: 22/07/2016 Ngày hoàn thành sửa bài: 08/08/2016 Ngày chấp nhận đăng: 16/08/2016