臺灣博碩士論文加值系統

隨著應用「全球衛星定位系統(Global Positioning System ; GPS)」於個人定位與導航之相關行動裝置產品日益普及，若對於各使用者每次使用於定位導航之資料加以蒐集儲存，可產生路徑資料庫。而將此資料加以分析，當可獲取許多有用的資訊與知識。目前應用 GPS 於導航的相關產品所做之最短路徑規劃，多為單純地找出起點至終點之最短路徑。然對於想要至當地旅遊的旅行者而言，此類最短路徑卻未必為其最佳路徑。因此類駕駛者往往至當地旅遊時無法判斷該去哪個景點，以及路線該如何規劃才會是該段旅程之最佳路徑。
本研究針對上述問題，提出以 GPS 資料探勘最適應路線給予當前使用者之演算法。因此類資料庫資料量通常十分龐大，本系統架構將對於使用者定出之起點與終點，建立適合旅遊之協同過濾推薦機制，通過此機制使用者得以在短時間內了解陌生的城市，並以較適合的路徑規劃旅程。

With the pervasiveness of the GPS-enabled devices, a huge amount of GPS traces has been accumulating unobtrusively and continuously in these Web communities. However, almost all of these applications still directly use raw GPS data, like coordinates and time stamps, without much understanding. Hence, so far, these communities cannot offer much support in giving people interesting information about geospatial locations. What’s more, facing such a large dataset in a community, it is impossible for a user to browse each GPS trajectory one by one. Therefore, the classifying of users' GPS logs is performed by mining each traces to determines the direction of it (positive or negative). When the number of the rating is greater than threshold this means that it is a similar place to the user. In contrast, if a lot of ratings are negative, so the rate of a place is not suit the person. When a user searches for the best place, recommender system will ask about user's location (latitude, longitude). Recommender system will send to user's mobile the best rated location as well as the nearest one from user's location. The mobile will show the location of recommended place on a map. Our study is based on GPS data mining that is our proposed before. It can use on numeric type of user’s attributes in the recommender system. In the experiment, we discussed the similar locations required to GPS data, user’s information data and the route which the user may be interested. Finally, we summarize the proposed the method and future research.

致謝 i
摘要 ii
Abstract iii
Table of Contents iv
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
1.1. Research Motivations 1
1.2. Research Goals 3
1.3. Thesis Organization 4
Chapter 2 Literature Review 5
2.1. Location Recommenders 5
2.2. Mining Location History 6
2.2.1. Traditional TFIDF 6
2.2.2. Edit Distance 7
2.2.3. Distances based on correlation coefficients 8
2.3. Recreational Itinerary Planning 9
Chapter 3 System Design 11
3.1. System Architecture 11
3.2. Data Collection (GPS Logs, Users Data, Locations Data) Module 12
3.3. Feature Preprocess 14
3.3.1. Users Feature 15
3.3.2. Locations Feature 17
3.4. Location Filtering 18
3.4.1. Locations-Content-aware Collaborative Filtering (LCCF) 18
3.4.2. Similar Location Module(Location-based) 21
3.5. Route Filtering 23
3.5.1. Collaborative-Filtering(CF) Based Route Recommendation 23
3.6. Recommender System 25
Chapter 4 Experimental Results 27
4.1. Datasets Description 27
4.1.1. GPS Datasets 27
4.1.2. Location Datasets 28
4.2.Locations-Content-aware Collaborative Filtering (LCCF) 29
4.3. Route Filtering 31
Chapter 5 Conclusions and Future Works 35
5.1. Conclusions 35
5.2. Future Works 36
References 37

[1]Shardanand, U., & Maes, P. (1995, May). Social information filtering: algorithms for automating “word of mouth”. In Proceedings of the SIGCHI conference on Human factors in computing systems (pp. 210-217). ACM Press/Addison-Wesley Publishing Co..
[2]Breese, J. S., Heckerman, D., & Kadie, C. (1998, July). Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence (pp. 43-52). Morgan Kaufmann Publishers Inc..
[3]Herlocker, J. L., Konstan, J. A., Terveen, L. G., & Riedl, J. T. (2004). Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems (TOIS), 22(1), 5-53.
[4]Gao, M., Liu, K., & Wu, Z. (2010). Personalisation in web computing and informatics: Theories, techniques, applications, and future research. Information Systems Frontiers, 12(5), 607-629.
[5]Adomavicius, G., & Tuzhilin, A. (2005). Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE transactions on knowledge and data engineering, 17(6), 734-749.
[6]Ricci, F. (2002). Travel recommender systems. IEEE Intelligent Systems, 17(6), 55-57.
[7]Gavalas, D., & Kenteris, M. (2011). A web-based pervasive recommendation system for mobile tourist guides. Personal and Ubiquitous Computing, 15(7), 759-770.
[8]Batet, M., Moreno, A., Sánchez, D., Isern, D., & Valls, A. (2012). Turist@: Agent-based personalised recommendation of tourist activities. Expert Systems with Applications, 39(8), 7319-7329.
[9]Martin, D., Alzua, A., & Lamsfus, C. (2011, January). A contextual geofencing mobile tourism service. In ENTER (pp. 191-202).
[10]Zheng, Y., & Zhou, X. (Eds.). (2011). Computing with spatial trajectories. Springer Science & Business Media.
[11]Borràs, J., de la Flor, J., Pérez, Y., Moreno, A., Valls, A., Isern, D., ... & Anton-Clavé, S. (2011). SigTur/E-Destination: a system for the management of complex tourist regions. In Information and Communication Technologies in Tourism 2011 (pp. 39-50). Springer, Vienna.
[12]Castillo, L., Armengol, E., Onaindía, E., Sebastiá, L., González-Boticario, J., Rodríguez, A., ... & Borrajo, D. (2008). SAMAP: An user-oriented adaptive system for planning tourist visits. Expert Systems with Applications, 34(2), 1318-1332.
[13]Tiwari, S., & Kaushik, S. (2013, March). Mining popular places in a geo-spatial region based on GPS data using semantic information. In International Workshop on Databases in Networked Information Systems (pp. 262-276). Springer Berlin Heidelberg.
[14]Ashbrook, D., & Starner, T. (2003). Using GPS to learn significant locations and predict movement across multiple users. Personal and Ubiquitous computing, 7(5), 275-286.
[15]Cheng, Z., Caverlee, J., Lee, K., & Sui, D. Z. (2011). Exploring millions of footprints in location sharing services. ICWSM, 2011, 81-88.
[16]Cho, E., Myers, S. A., & Leskovec, J. (2011, August). Friendship and mobility: user movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1082-1090). ACM.
[17]Noulas, A., Scellato, S., Mascolo, C., & Pontil, M. (2011). An Empirical Study of Geographic User Activity Patterns in Foursquare. ICwSM, 11, 70-573.
[18]Silva, T. H., de Melo, P. O., Almeida, J., Musolesi, M., & Loureiro, A. (2014). You are what you eat (and drink): Identifying cultural boundaries by analyzing food & drink habits in foursquare. arXiv preprint arXiv:1404.1009.
[19]Zheng, Y., Zhang, L., Xie, X., & Ma, W. Y. (2009, November). Mining correlation between locations using human location history. In Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems (pp. 472-475). ACM.
[20]Zheng, Y., Wang, L., Zhang, R., Xie, X., & Ma, W. Y. (2008, April). GeoLife: Managing and understanding your past life over maps. In Mobile Data Management, 2008. MDM'08. 9th International Conference on (pp. 211-212). IEEE.
[21]Zheng, Y., Li, Q., Chen, Y., Xie, X., & Ma, W. Y. (2008, September). Understanding mobility based on GPS data. In Proceedings of the 10th international conference on Ubiquitous computing (pp. 312-321). ACM.
[22]Zheng, Y., Zhang, L., Xie, X., & Ma, W. Y. (2009, April). Mining interesting locations and travel sequences from GPS trajectories. In Proceedings of the 18th international conference on World wide web (pp. 791-800). ACM.
[23]Khetarpaul, S., Chauhan, R., Gupta, S. K., Subramaniam, L. V., & Nambiar, U. (2011, March). Mining GPS data to determine interesting locations. In Proceedings of the 8th International Workshop on Information Integration on the Web: in conjunction with WWW 2011 (p. 8). ACM.
[24]Ashbrook, D., & Starner, T. (2003). Using GPS to learn significant locations and predict movement across multiple users. Personal and Ubiquitous computing, 7(5), 275-286.
[25]Bafna, P., Pramod, D., & Vaidya, A. (2016, March). Document clustering: TF-IDF approach. In Electrical, Electronics, and Optimization Techniques (ICEEOT), International Conference on (pp. 61-66). IEEE.
[26]Nassirtoussi, A. K., Aghabozorgi, S., Wah, T. Y., & Ngo, D. C. L. (2015). Text mining of news-headlines for FOREX market prediction: A Multi-layer Dimension Reduction Algorithm with semantics and sentiment. Expert Systems with Applications, 42(1), 306-324.
[27]Tajbakhsh, M. S., & Bagherzadeh, J. (2016, August). Microblogging Hash Tag Recommendation System Based on Semantic TF-IDF: Twitter Use Case. In Future Internet of Things and Cloud Workshops (FiCloudW), IEEE International Conference on (pp. 252-257). IEEE.
[28]Gusfield, D. (1997). Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge university press.
[29]Pevzner, P. (2000). Computational molecular biology: an algorithmic approach. MIT press.
[30]Moon, A., & Raju, T. (2013). A survey on document clustering with similarity measures. Int Journal of Advanced Research in Computer Science and Software Engg, 3(11), 559-601.
[31]Levenshtein, V. I. (1966, February). Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics doklady (Vol. 10, No. 8, pp. 707-710).
[32]Masek, W. J., & Paterson, M. S. (1980). A faster algorithm computing string edit distances. Journal of Computer and System sciences, 20(1), 18-31.
[33]Wagner, R. A., & Fischer, M. J. (1974). The string-to-string correction problem. Journal of the ACM (JACM), 21(1), 168-173.
[34]Hall, P. A., & Dowling, G. R. (1980). Approximate string matching. ACM computing surveys (CSUR), 12(4), 381-402.
[35]Kukich, K. (1992). Techniques for automatically correcting words in text. ACM Computing Surveys (CSUR), 24(4), 377-439.
[36]Peterson, J. L. (1980). Computer programs for detecting and correcting spelling errors. Communications of the ACM, 23(12), 676-687.
[37]Sankoff, D., & Kruskal, J. B. (1983). Time warps, string edits, and macromolecules: the theory and practice of sequence comparison. Reading: Addison-Wesley Publication, 1983, edited by Sankoff, David; Kruskal, Joseph B., 1.
[38]Oommen, B. J. (1986). Constrained string editing. Information Sciences, 40(3), 267-284.
[39]Marzal, A., & Vidal, E. (1993). Computation of normalized edit distance and applications. IEEE transactions on pattern analysis and machine intelligence, 15(9), 926-932.
[40]Székely, G. J., Rizzo, M. L., & Bakirov, N. K. (2007). Measuring and testing dependence by correlation of distances. The Annals of Statistics, 35(6), 2769-2794.
[41]Hu, J. G., Qi, H. N., Dong, F., & Wang, H. J. (2011). Improved ant colony algorithm for path planning of tourist scenic area. Jisuanji Yingyong Yanjiu, 28(5), 1647-1650.
[42]Wenbin, C., Qingbao, Z., & Jun, H. (2010, August). Path planning based on biphasic ant colony algorithm and fuzzy control in dynamic environment. In Intelligent Human-Machine Systems and Cybernetics (IHMSC), 2010 2nd International Conference on (Vol. 1, pp. 333-336). IEEE.
[43]Gavalas, D., Kenteris, M., Konstantopoulos, C., & Pantziou, G. (2012). Web application for recommending personalised mobile tourist routes. IET software, 6(4), 313-322.
[44]Peng, D., & Zhang, C. (2013, December). Research on Intelligent Route Programming for DIY Travel. In Computer Sciences and Applications (CSA), 2013 International Conference on (pp. 350-352). IEEE.
[45]Huang, C. J., & Lin, Y. H. (2006, August). The Approximate Shortest Distance Route Intelligent System For Traveling in Taiwan. In Innovative Computing, Information and Control, 2006. ICICIC'06. First International Conference on (Vol. 2, pp. 498-502). IEEE.
[46]GeoLife GPS Trajectories :
https://www.microsoft.com/en-us/download/details.aspx?id=52367
[47]Number of Facebook users by age in the U.S. as of February 2016: https://www.statista.com/statistics/398136/us-facebook-user-age-groups/
[48]Distribution of Facebook users in the United States as of January 2016, by gender: https://www.statista.com/statistics/266879/facebook-users-in-the-us-by-gender/
[49]China POI dataset:
http://www.poi86.com/
[50]ditujiupian’s Beijing POI dataset:
http://ditujiupian.com/
[51]Ouyang W, Yu CW, Yu KM, Safe path planning strategy for bike net. Wireless Pers Commun 2014; 78: 1995–2007.
[52]Mountain valuation:
http://wikipedia.qwika.com/de2en/Bergwertung.
[53]Tiwari, S., & Kaushik, S. (2013, March). Mining popular places in a geo-spatial region based on GPS data using semantic information. In International Workshop on Databases in Networked Information Systems (pp. 262-276). Springer Berlin Heidelberg.
[54]Bellman, R. (1962). Dynamic programming treatment of the travelling salesman problem. Journal of the ACM (JACM), 9(1), 61-63.
[55]Larranaga, P., Kuijpers, C. M., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 13(2), 129-170.
[56]Jones, J., & Adamatzky, A. (2014). Computation of the travelling salesman problem by a shrinking blob. Natural Computing, 13(1), 1-16.
[57]MacGregor, J. N., & Ormerod, T. (1996). Human performance on the traveling salesman problem. Attention, Perception, & Psychophysics, 58(4), 527-539.
[58]MacGregor, J. N., & Chu, Y. (2011). Human performance on the traveling salesman and related problems: A review. The Journal of Problem Solving, 3(2), 2.
[59]Resnick, P. (1994). An open architecture for collaborative filtering of netnews. In CSCW, 1994 (pp. 175-186). ACM Press.
[60]Takeuchi, Y., & Sugimoto, M. (2005, September). An outdoor recommendation system based on user location history. In Proceedings of the 1st International Workshop on Personalized Context Modeling and Management for UbiComp Applications (pp. 91-100).
[61]Zheng, Y., Liu, L., Wang, L., & Xie, X. (2008, April). Learning transportation mode from raw gps data for geographic applications on the web. In Proceedings of the 17th international conference on World Wide Web (pp. 247-256). ACM.