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