隨著資訊工程技術的發展，越來越多基於GPS(Global Positioning System)的服務也將出現。在城市交通中，一定量的車載GPS資訊即可以提供無窮無盡的有用資料，從地圖服務到路線導航，當下流行的LBS(Location-based Service)應用皆出於此。
本文關注的是以車載GPS資訊來自動挖掘未知城市地圖資料，實驗設計為利用北京市計程車車載GPS資訊自動挖掘北京市內交通路口之所在位置。具體做法是先經過文件預處理剔除雜訊及無效資料，保證所使用資訊的有效性；再於GPS資訊中，逐次對每一輛計程車車載GPS資訊所提供的時間及經緯度，利用滑動窗口方法搜尋路口處的轉彎曲線後，再對轉彎曲線進行結合了動態密度方法的Mean-Shift運算。對每一個大的聚類，經歷準確的聚類劃分、聚類合併、捨去多餘點之過程，迭代多次之後得出交通路口所在位置。

With the development of information engineering and technology, more and more GPS-based services appear. In urban computing field, a certain amount of car GPS data can provide very useful information. From map service to navigation system, popular LBS applications are booming.
This thesis focuses on automatically mine the urban traffic intersections of any unknown city from car GPS data. The experiment is designed to take advantage of Peking Taxi GPS data in order to mine traffic intersections of the Peking City. The specific approach is at first data-preprocessing; secondly extract the curves in GPS information by sliding windows; thirdly, by dividing and merging clusters while deleting the remaining points again and again, to apply a combination of dynamic density clustering algorithm and Mean-Shift method to get the right location of the traffic intersection.

[1] Yu Zheng, Licia Capra, Ouri Wolfson, and Hai Yang “Urban Computing: Concepts, Methodologies, and Applications”, ACM Transaction on Intelligent Systems and Technology, Vol.6, No.2, pp. 1-47(2014).
[2] Yu Zheng, Yanchi Liu, Jing Yuan, Xing Xie, “Urban Computing with Taxicabs”, ACM International Joint Conference on Pervasive and Ubiquitous Computing, pp. 89-98 (2011).
[3] Alireza Fathi, John Krumm, “Detecting Road Intersections from GPS Traces”, Lecture Notes in Computer Science, Volume 6292, pp. 56-69 (2010).
[4] Jing Yuan, Yu Zheng, Xing Xie, Guangzhong Sun. “T-Drive: Enhancing Driving Directions with Taxi Drivers' Intelligence”, IEEE Transactions on Knowledge and Data Engineering, Vol. 25, No. 1, pp.220-232 (2013).
[5] Jing Yuan, Yu Zheng, Liuhang Zhang, Xing Xie, Guangzhong Sun. “Where to Find My Next Passenger”, ACM International Joint Conference on Pervasive and Ubiquitous Computing, pp. 109-118 (2011).
[6] Jing Yuan, Yu Zheng, Liuhang Zhang, Xing Xie. “T-Finder: A Recommender System for Finding Passengers and Vacant Taxis”, IEEE Transactions on Knowledge and Data Engineering, Vol.25, Issue 10, pp.2390-2403 (2013).
[7] Shuo Ma, Yu Zheng, Ouri Wolfson. “T-Share: A Large-Scale Dynamic Taxi Ridesharing Service”, IEEE 29th International Conference on Data Engineering, pp. 410-421 (2013).
[8] N. Lathia and L. Capra. “Mining Mobility Data to Minimise Travellers’ Spending on Public Transport”, ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.1181-1189 (2011).
[9] I. Ceapa, C. Smith,L. Capra. “Avoiding the Crowds: Understanding Tube Station Congestion Patterns from Trip Data”, ACM SIGKDD International Workshop on Urban Computing, pp.134-141 (2012).
[10] Favyen Bastani, Yan Huang, Xing Xie, Jason Powell. “A Greener Transportation Mode: Flexible Routes Discovery from GPS Trajectory Data”, ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp.405-408 (2011).
[11] Yu Zheng, Furui Liu, Hsun-Ping Hsie. “U-Air: When Urban Air Quality Inference Meets Big Data”, ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.1436-1444 (2013).
[12] O'Sullivan, Arthur. Urban Economics. Irwin McGraw-Hill, MA (2003).
[13] D. Karamshuk, A. Noulas, S. Scellato, V. Nicosia, C. Mascolo. “Geo-Spotting: Mining Online Location-based Services for Optimal Retail Store Placement”, ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.793-801 (2013).
[14] Wei Liu, Yu Zheng, Sanjay Chawla, Jing Yuan and Xing Xie. “Discovering Spatio-Temporal Causal Interactions in Traffic Data Streams”, ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.1010-1018 (2011).
[15] Linsey Xiaolin Pang, Sanjay Chawla, Wei Liu, Yu Zheng. “On Mining Anomalous Patterns in Road Traffic Streams”, International Conference on Advanced Data Mining and Applications, pp.273-251 (2011).
[16] Linsey Xiaolin Pang, Sanjay Chawla, Wei Liu, Yu Zheng. “On Detection of Emerging Anomalous Traffic Patterns Using GPS Data”, Data & Knowledge Engineering, Vol.87, pp.357-373 (2013).
[17] Keinosuke Fukunaga, Larry D. Hostetler. “The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition”, IEEE Transactions on Information Theory, Vol. IT-21, No.1, pp.32-40 (1975).
[18] Yizong Cheng. “Mean shift, mode seeking, and clustering”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, Issue.8, pp.790-799(1995).
[19] Dorin Comaniciu. “Mean Shift: a robust approach toward feature space analysis”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.24, No.5, pp.603-619 (2002).
[10] Dorin Comaniciu. “Real-time tracking of non-rigid objects using mean shift”, IEEE Conference on Computer Vision and Pattern Recognition, Vol. 2, pp.751-767 (2000).
[21] Robert T. Collins. “Mean-shift Blob Tracking through Scale Space”, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp.234-240 (2003).
[22] Wang J, Xia LN, Jing JW. “Maximum density clustering algorithm”, Journal of the Graduate School of the Chinese Academy of Sciences, Vol.26, No.4, pp.539-548 (2009).