請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9185
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 許永真(Jane Yung-jen Hsu) | |
dc.contributor.author | Han-Wen Chang | en |
dc.contributor.author | 張翰文 | zh_TW |
dc.date.accessioned | 2021-05-20T20:12:12Z | - |
dc.date.available | 2009-07-28 | |
dc.date.available | 2021-05-20T20:12:12Z | - |
dc.date.copyright | 2009-07-28 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-07-27 | |
dc.identifier.citation | [1] M. Ankerst, M. M. Breunig, H.-P. Kriegel, and J. Sander. OPTICS: Ordering points to identify the clustering structure. ACM SIGMOD Record, 28(2):49–60, June 1999.
[2] D. Ashbrook and T. Starner. Using GPS to learn significant locations and predict movement across multiple users. Personal Ubiquitous Computing, 7(5):275–286, October 2003. [3] N. Bicocchi, G. Castelli, M. Mamei, A. Rosi, and F. Zambonelli. Supporting locationaware services for mobile users with the whereabouts diary. In Proceedings of the 1st International Conference on MOBILe Wireless MiddleWARE, Operating Systems, and Applications (MOBILWARE 2008), pages 1–6. ICST, February 2008. [4] D. Brosset, C. Claramunt, and E. Saux. A location and action-based model for route descriptions. In Proceeding of the 2nd International Conference on GeoSpatial Semantics (GeoS 2007), pages 146–159. Springer-Verlag, November 2007. [5] C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/˜cjlin/libsvm. [6] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD 1996), pages 226–231. AAAI Press, August 1996. [7] T. A. S. Foundation. Commons-Math: The Apache Commons Mathematics Library, 2007. Software available at http://commons.apache.org/math/. [8] L. Fritsch. Profiling and Location-Based Services (LBS), chapter Profiling and Location-Based Services (LBS), pages 147–168. Springer Netherlands, May 2008. [9] J. Froehlich, M.Y. Chen, I. E. Smith, and F. Potter. Voting with your feet: An investigative study of the relationship between place visit behavior and preference. In Proceedings of the 8th International Conference on Ubiquitous Computing (UbiComp 2006), volume 4206 of Lecture Notes in Computer Science, pages 333–350. Springer, September 2006. [10] F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2007), pages 330–339. ACM Press, August 2007. [11] K. J‥arvelin and J. Kek‥al‥ainen. Cumulated gain-based evaluation of ir techniques. ACM Transactions on Information Systems (TOIS), 20(4):422–446, October 2002. [12] J. Krumm and E. Horvitz. Predestination: Where do you want to go today? IEEE Computer, 40(4):105–107, 2007. [13] T. Kudo. CRF++: Yet Another CRF toolkit, December 2007. Software available at http://crfpp.sourceforge.net/. [14] V. Kulyukin, J. Nicholson, D. Ross, J. Marston, and F. Gaunet. The blind leading the blind: Toward collaborative online route information management by individuals with visual impairments. In Proceedings of AAAI 2008 Spring Symposium Series on Social Information Processing. AAAI, March 2008. [15] J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning (ICML), June 2001. [16] Q. Li, Y. Zheng, X. Xie, Y. Chen, W. Liu, and W.-Y. Ma. Mining user similarity based on location history. In Proceedings of the 16th Annual ACM International Symposium on Advances in Geographic Information Systems (GIS 2008), pages 1–10. ACM, November 2008. [17] L. Liao, D. Fox, and H. Kautz. Extracting places and activities from gps traces using hierarchical conditional random fields. International Journal of Robotics Research, 26(1):119–134, January 2007. [18] N. Marmasse and C. Schmandt. A user-centered location model. Personal Ubiquitous Computing, 6(5-6):318–321, December 2002. [19] A. T. Palma, V. Bogorny, B. Kuijpers, and L. O. Alvares. A clustering-based approach for discovering interesting places in trajectories. In Proceedings of the 2008 ACM Symposium on Applied Computing (SAC 2008), pages 863–868. ACM, March 2008. [20] J. Rekimoto, T. Miyaki, and T. Ishizawa. Lifetag: Wifi-based continuous location logging for life pattern analysis. In Proceedings of the 3rd International Symposium on Locationand Context-Awareness (LoCA 2007), volume 4718 of Lecture Notes in Computer Science, pages 35–49, September 2007. [21] S. D. Sabbata, S. Mizzaro, and L. Vassena. Spacerank: Using pagerank to estimate location importance. In Proceedings of ECAI 2008 Workshop on Mining Social Data, July 2008. [22] Y. Takeuchi and M. Sugimoto. A user-adaptive city guide system with an unobtrusive navigation interface. Personal and Ubiquitous Computing, 13(2):119–132, February 2009. [23] T. Vincenty. Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations. Survey Review, 22(176):88–93, April 1975. [24] I. H. Witten and E. Frank. Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, San Francisco, 2 edition, June 2005. [25] X. Xiao, X. Xie, Q. Luo, and W.-Y. Ma. Density based co-location pattern discovery. In Proceedings of the 16th Annual ACM International Symposium on Advances in Geographic Information Systems (GIS 2008), pages 1–10, 2008. [26] J. Ye, L. Coyle, S. Dobson, and P. Nixon. A unified semantics space model. In Proceedings of the 3rd International Symposium on Location- and Context-Awareness (LoCA 2007), volume 4718 of Lecture Notes in Computer Science, pages 103–120, September 2007. [27] Y. Ye, Y. Zheng, Y. Chen, J. Feng, and X. Xie. Mining individual life pattern based on loacation history. In Proceedings of the 10th International Conference on Mobile Data Management: Systems, Services and Middleware (MDM 2009), May 2009. [28] K. Zhang, H. Li, K. Torkkola, and M. Gardner. Adaptive learning of semantic locations and routes. In Proceedings of the 1st International Conference on Autonomic Computing and Communication Systems (Autonomics 2007), pages 1–10. ICST, 2007. [29] Y. Zheng, Q. Li, Y. Chen, X. Xie, and W.-Y. Ma. Understanding mobility based on gps data. In Proceedings of the 10th International Conference on Ubiquitous Computing (UbiComp 2008), pages 312–321. ACM Press, September 2008. [30] Y. Zheng, L. Wang, R. Zhang, X. Xie, and W.-Y. Ma. GeoLife: Managing and understanding your past life over maps. In Proceedings of the 9th International Conference on Mobile Data Management (MDM 2008), pages 211–212, April 2008. [31] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations and travel sequences from GPS trajectories. In Proceedings of the 18th International Conference on World Wide Web (WWW 2009), pages 791–800, April 2009. [32] C. Zhou, N. Bhatnagar, S. Shekhar, and L. Terveen. Mining personally important places from gps tracks. In Proceedings of the 23rd IEEE International Conference on Data Engineering Workshop, pages 517–526, April 2007. [33] C. Zhou, D. Frankowski, P. Ludford, S. Shekhar, and L. Terveen. Discovering personal gazetteers: an interactive clustering approach. In Proceedings of the 12th Annual ACM InternationalWorkshop on Geographic Information Systems (GIS 2004), pages 266–273. ACM, November 2004. [34] B. Ziebart, A. L. Maas, A. K. Dey, and J. A. Bagnell. Navigate like a cabbie: probabilistic reasoning from observed context-aware behavior. In Proceedings of the 10th International Conference on Ubiquitous Computing (UbiComp 2008), pages 322–331. ACM, September 2008. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9185 | - |
dc.description.abstract | 個人行蹤除了受到行程安排的影響外,也顯示了一個人某個面向的生活型態,例如常用的交通模式與常去的地點可以顯示一個人的習慣與偏好。而有些地點在一個人的生活模式中扮演較重要的角色;藉由較重要的活動據點可以了解一個人的生活模式。受惠於近來附有全球定位系統功能手機的普及,個人行蹤軌跡的取得與紀錄更加容易。從軌跡紀錄中可以進一步分析其交通行為與停留地點,並找出重要的活動據點。
在本論文中,我們設計了一個軌跡管理服務網頁,提供使用者將紀錄下來的軌跡上傳,並於網頁上標記、管理、與檢視。將軌跡分段並擷取特徵值後,我們應用條件隨機場模型(Conditional Random Fields)於交通模式辨認,並與支援向量機模型(Support Vector Machine)比較其預測準確度。實驗結果顯示,條件隨機場模型因為考慮了時間關係,辨識準確度較支援向量機模型高。 此外,我們使用 OPTICS 群聚演算法將使用者曾停留的位置群聚為活動據點,並比較十種可作為預測據點重要程度的特徵值,如造訪次數、停留時間等。在十種特徵值中,以造訪次數多寡與停留時間長短之排序最能將使用者認知中相對重要的據點優先辨識出來。 | zh_TW |
dc.description.abstract | The whereabouts of a person not only indicates her schedule, but also reflects her lifestyle. The transportation taken and the places visited indicate the habit and preference of the user. With the growing popularity of commercial GPS loggers and GPS-enabled mobile phones, the positions of a person could be obtained and logged, and further analyzed to infer the transportation taken and places visited. Moreover, some places are more significant than others in one's daily life. These significant places shapes the life of the person.
In this thesis, we created a prototype of a trajectory management service to annotate and visualize the trajectories. We adopted machine learning techniques to segment the trajectories and extract their features, and used supervised learning approach to train probabilistic models. We modeled the transportation mode learning problem as a sequence labeling problem using linear-chain conditional random fields (CRF). We compared the CRF model with support vector machines (SVM), and our results show that CRF outperforms SVM, when temporal relationship is considered. In addition, we adopted OPTICS clustering to find the places visited by the user. Results show that, among ten measures we used, visit frequency and stay duration predict the most significant places more accurately. | en |
dc.description.provenance | Made available in DSpace on 2021-05-20T20:12:12Z (GMT). No. of bitstreams: 1 ntu-98-R96922005-1.pdf: 3004327 bytes, checksum: b68fb69805fd6908e429c7ffd4baa5f7 (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | Contents
Acknowledgments iii Abstract v List of Figures xii List of Tables xiii Chapter 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Chapter 2 Background 5 2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Location-Based Services . . . . . . . . . . . . . . . . . . . . 5 2.1.2 Transportation Mode Learning . . . . . . . . . . . . . . . . . 9 2.1.3 Significant Location Mining . . . . . . . . . . . . . . . . . . 9 2.2 Related Technology . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 Support Vector Machine . . . . . . . . . . . . . . . . . . . . 11 2.2.2 Linear Conditional Random Fields . . . . . . . . . . . . . . . 12 2.2.3 OPTICS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Chapter 3 GPS Trajectory Analysis 17 3.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1 Location-Transportation Sequence . . . . . . . . . . . . . . . 18 3.1.2 Significant Place Set . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Chapter 4 Location-transportation Sequence 25 4.1 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.1.1 Trajectory Segmentation . . . . . . . . . . . . . . . . . . . . 26 4.1.2 Feature Extraction . . . . . . . . . . . . . . . . . . . . . . . 29 4.2 Classification and Sequence Labeling . . . . . . . . . . . . . . . . . 32 4.2.1 SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2.2 LCRF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . 36 Chapter 5 Significant Place Set 39 5.1 Location Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.2 Significance Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2.1 Feature Selection . . . . . . . . . . . . . . . . . . . . . . . . 40 5.3 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.3.1 Precision and Recall . . . . . . . . . . . . . . . . . . . . . . 44 5.3.2 Significance Ordering . . . . . . . . . . . . . . . . . . . . . 44 5.3.3 NDCG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Chapter 6 Experiment and Evaluation 47 6.1 The Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.1.1 Data Collection . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.1.2 Data Annotation . . . . . . . . . . . . . . . . . . . . . . . . 48 6.2 Transportation Mode Learning . . . . . . . . . . . . . . . . . . . . . 51 6.2.1 Experiment Steps . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2.2 Example Result . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.3 Significant Location Mining . . . . . . . . . . . . . . . . . . . . . . 57 6.3.1 Experiment Steps . . . . . . . . . . . . . . . . . . . . . . . . 57 6.3.2 Example Result . . . . . . . . . . . . . . . . . . . . . . . . . 59 Chapter 7 Conclusion 63 Bibliography 65 | |
dc.language.iso | en | |
dc.title | 由個人移動軌跡紀錄分析交通模式與活動據點 | zh_TW |
dc.title | Mining Transportation Modes and Significant Places from Individual GPS Trajectories | en |
dc.type | Thesis | |
dc.date.schoolyear | 97-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 朱浩華(Hao-Hua Chu),王傑智(Chieh-Chih Wang),許鈞南(Chun-Nan Hsu),陳穎平(Ying-ping Chen) | |
dc.subject.keyword | 適地性服務,軌跡分析,空間資料探勘,條件隨機場,資料叢集, | zh_TW |
dc.subject.keyword | Location-based Service,Trajectory Analysis,Spatial Data Mining,Conditional Random Field,Clustering, | en |
dc.relation.page | 69 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2009-07-27 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf | 2.93 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。