隨著無線通訊技術的快速發展，適地性服務的廣泛應用與研究已經引起許多學者的關注，其中一個熱門的研究主題為旅遊推薦。近幾年雖然有一些研究專注於根據使用者位置進行景點推薦或是旅遊行程推薦，但是大多數研究沒有考慮到使用者的喜好或是旅遊時間限制。本研究提出一個新式的資料探勘架構以達到基於使用者位置之最佳化旅遊行程推薦，並且考慮到個人化因素以及使用者旅遊時間限制。在本架構中我們提出了個人化景點評分演算法及景點停留時間計算演算法來建立旅遊地圖網路。為了有效的從網路中找出最佳旅遊行程，我們提出了Trip-Mine演算法，為了提升這演算法執行時間以及記憶體效率我們亦提出了三個改良的策略。根據我們對文獻勘查的了解，本論文為第一篇同時考慮旅遊行程規劃以及使用者旅遊時間限制下如何有效率求解之研究。經由實驗結果顯示，我們所提出的方法在旅遊行程規劃效率上有優異的表現。

With the rapid development of wireless telecommunication technologies, a number of studies about Location-Based Services (LBSs) have been done due to wide applications. An active topic among these studies is travel recommendation. Most of the studies focused on recommending attractions or trips based on users’ locations. However, such recommendations may not satisfy users' preferences or their travel time constraints. In this thesis, we propose a novel data-mining-based framework to efficiently find the optimal trip which satisfies users’ travel time constraints based on users’ locations. In this framework, we construct a Trip-Map network by utilizing two algorithms for personalized attraction rating and attraction stay time calculating. To efficiently find optimal trip from the Trip-Map network, we propose a fast and memory-efficient algorithm, named Trip-Mine. Three effective strategies are also applied to further enhance the performance of Trip-Mine. To the best of our knowledge, this is the first work that takes trip planning and travel time constraints into account simultaneously. Finally, we perform extensive experiments and show that our proposed framework delivers excellent results.

[1] G. D. Abowd, C. G. Atkeson, J. Hong, S. Long, R. Kooper and M. Pinkerton, “Cyberguide: A Mobile Context‐Aware Tour Guide,” Wireless Networks, vol. 3, no. 5, pp. 421-433, Oct. 1997.
[2] D. L. Applegate, R. E. Bixby, V. Chvatal and W. J. Cook, “The Traveling Salesman Problem: A Computational Study,” Princeton University Press, 2006.
[3] Alta4, http://www.alta4.com/
[4] Bing Maps, http://www.bing.com/maps/
[5] M. D. Choudhury,M. Feldman,S. Amer-Yahia,N. Golbandi,R. Lempel and C. Yu, “Automatic Construction of Travel Itineraries using Social Breadcrumbs,” in Proceedings of the 21st ACM conference on Hypertext and hypermedia, pp.35-44 Jun. 2010
[6] D. Comaniciu and P. Meer, “Mean Shift: A Robust Approach toward Feature Space Analysis,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24 no. 5, 2002
[7] CitySights NY, http://www.citysightsny.com/
[8] M. Ester, H.-P. Kriegel, J. S and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in Proceedings of the 2th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 226-231 Aug. 1996.
[9] EveryTrail, http:// www.everytrail.com/
[10] Flickr, http://www.flickr.com/
[11] Y. Ge, H. Xiong, A. Tuzhilin, K. Xiao, M. Gruteser and M. J. Pazzani, “An Energy-Efficient Mobile Recommender System,” in Proceedings of the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 899-908, Jul. 2010.
[12] K. Gouda and M. J. Zaki, “GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets,” Data Mining and Knowledge Discovery, vol. 11, no. 3, pp. 223-242, Nov. 2005.
[13] GeoNames, http:// www.geonames.org/
[14] Google map, http:// maps.google.com.tw/
[15] Google city tours, http://citytours.googlelabs.com
[16] GPS-Photo Link, http://www.geospatialexperts.com/index.php
[17] Y. Huang and L. Bian, “A Bayesian Network and Analytic Hierarchy Process Based Personalized Recommendations for Tourist Attractions over the Internet,” Expert Systems with Applications, vol. 36, no. 1, pp. 933-943, Jan. 2009.
[18] T. Horozov, N. Narasimhan and V. Vasudevan, “Using Location for Personalized POI Recommendations in Mobile Environments,” in Proceedings of International Symposium on Applications on Internet, pp. 124-129, Jan. 2006.
[19] K. Jarvelin and J. Kekalainen, "Cumulated gain-based evaluation of IR techniques," ACM Transactions on Information Systems, vol.20, no.4, pp.422-446, October 2002.
[20] G. Jeh and J. Widom, “SimRank: a measure of structural-context similarity,” in Proceedings of the 8th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 538-543 Jul. 2002
[21] S. Kisilevich, D. Keim and L. Rokach, “A Novel Approach to Mining Travel Sequences Using Collections of Geotagged Photos,” in Proceedings of the 13th AGILE International Conference on Geographic Information Science, pp. 163-182, May 2010.
[22] J. Kim, H. Kim and J.-H. Ryu, “TripTip: A trip planning service with tag-based recommendation,” in Proceedings of the 27th international conference extended abstracts on Human factors in computing systems, pp. 3467-3472, Apr. 2009.
[23] S. Kisilevich, F. Mansmann and D. Keim, “P-DBSCAN: a density based clustering algorithm for exploration and analysis of attractive areas using collections of geo-tagged photos” in Proceedings of the 1st International Conference and Exhibition on Computing for Geospatial Research & Application, Jun. 2010
[24] C.-S. Lee, Y.-C. Chang and M.-H. Wang, “Ontological Recommendation Multi-Agent for Tainan City Travel,” Expert Systems with Applications, vol. 36, no. 3, pp. 6740-6753, Apr. 2009.
[25] Z. Li, B. Ding, J. Han and R. Kays, “Swarm: Mining Relaxed Temporal Moving Object Clusters,” in Proceedings of the VLDB Endowment, vol. 3, no. 1, pp. 723-734, 2010.
[26] E. H.-C. Lu, W.-C. Lee, and V. S. Tseng, “A Framework for Personal Mobile Commerce Pattern Mining and Prediction,” accepted and to appear in IEEE Transactions on Knowledge and Data Engineering.
[27] X. Lu, C. Wang, J.-M. Yang, Y. Pang and L. Zhang, “Photo2Trip: Generating Travel Routes from Geo-Tagged Photos for Trip Planning,” in Proceedings of the ACM International Conference on Multimedia, pp. 143-152, Oct. 2010.
[28] Lonely Planet, http://www.lonelyplanet.com/
[29] Panoramio, http:// www.panoramio.com/
[30] S. Schiaffino and A. Amandi, “Building an expert travel agent as a software agent,” Expert Systems with Applications, vol. 36, no. 2, pp. 1291-1299, March. 2009.
[31] V.-W. Soo and S.-H. Liang, “Recommending a Trip Plan by Negotiation with a Software Travel Agent,” Cooperative Information Agents V, vol. 2182, pp. 32-37, 2001.
[32] V. Tseng, C.-W. Wu, B.-E. Shie and P. Yu, “UP-Growth: An Efficient Algorithm for High Utility Itemsets Mining,” in Proceedings of the 16th ACM SIG KDD Conference on Knowledge Discovery and Data Mining, pp. 253-262, Jul. 2010.
[33] Trip Say, http:// www.tripsay.com/
[34] World Travel Guide, http:// www.worldtravelguide.net/
[35] C.-C. Yu and H.-P. Chang, “Personalized Location-Based Recommendation Services for Tour Planning in Mobile Tourism Applications,” E-Commerce and Web Technologies, vol. 5692, pp. 38-49, 2009.
[36] H. Yoon, Y. Zheng, X. Xie and W. Woo, “Smart Itinerary Recommendation Based on User-Generated GPS Trajectories,” in Proceedings of the International Conference on Ubiquitous Intelligence and Computing, pp. 19-34, Oct. 2010.
[37] Yahoo Travel, http:// travel.yahoo.com/
[38] Y. Zheng and X. Xie, “Learning Travel Recommendations from User-Generated GPS Traces,” ACM Transactions on Intelligent Systems and Technologies, vol. 2, no. 1, 2011.