臺灣博碩士論文加值系統

近年來行動裝置日漸普及，人們廣泛應用其內建全球定位系統(GPS)，提供與空間位置相關之多樣化服務，包含以地理位置標籤紀錄使用者當下經緯度座標，或以軌跡方式呈現使用者移動過程，可反映出使用者對該位置的喜好，也間接透露個人興趣與其行為模式。若能透過協同過濾(CF)方法找出行為相似用戶，來輔助系統過濾興趣景點之資訊，給予使用者較符合需求之個性化推薦列表，便可避免使用者花費過多的時間搜索不感興趣之訊息。
本研究提出基於GPS軌跡相似之協同過濾位置推薦系統(CFLRS)，以其他使用者的歷史軌跡資訊協同過濾來預測該用戶未來較可能感興趣之景點。首先，將歷史軌跡之定位點透過速度限制和停留時間閥值，篩選出軌跡中所含之停留點，即可知使用者過去停留於哪些興趣景點；其次，將所歷經之停留點轉換為語意序列和其他用戶軌跡進行比對，以計算出使用者相似度，來預測其可能感興趣景點位置的語義類別；最後，利用使用者所查詢之當下位置與興趣景點作距離和評分正規化，並將推薦價值依降冪排序，使推薦項目更加貼切使用者的興趣與需求。
根據模擬實驗結果，本論文所提出CFLRS策略相較於策略STHUI、ISTBU及CLAR，於正規化折扣累計增益(nDCG)上有較佳表現。當速度限制閥值為3 km，停留時間閥值為30 min，查詢範圍1 km，使用系統人數為100人時，CFLRS之nDCG略高於其他策略平均約7.9%；在平均推薦時間上CFLRS略高於其他策略平均約4.7%；在推薦覆蓋度上CFLRS略低於其他策略平均約3.4%。因此，CFLRS可預測使用者下一個感興趣的位置類型，故可用於作個性化推薦。

The smart phones are gaining popularity in recent years. The Global Positioning System (GPS) on smart phones provides the services that can be associated broadly with spatial locations. These services include recording the current coordinates of user’s locations with geographical location labels, or presenting the movements of user in trajectories. These informations can reflect the users preference for visiting locations and their behavior patterns. The collaborative filtering (CF) technique can find the cluster of similar users and filter the interest information for users. A system with CF can give the user a personalized recommendation list to avoid searching those information that are not interested by user.
This study proposed a Collaborative Filtering Location Recommendation System Based on GPS Trajectory Similarity (CFLRS) methods. Our syetem used CF technique to predict the user interested location from others’ historical trajectory information. First, filter out the Stay Point (SP) ftom historical trajectory according to speed limit and stop time thresholds The SP then can be converted to semantic trajectories. We calculate the user similarity by semantic trajectories , and predict the semantic category which the user may be interested. Finally, the recommended value is calculated by the current position of user and interest of points. It may make the recommendation more suitable for the users interests and needs.
From to the simulation results, the proposed CFLRS strategy has better performance on the normalized discount cumulative gain (nDCG) than the strategies STHUI, ISTBU and CLAR. As the speed limit threshold is 3 kilometers per hour, the stop time threshold is 30 minutes, and the query range is 1 kilometer, for 100 people, the nDCG of CFLRS is better than other three strategies about 7.9%. On the average recommended time, CFLRS is higher than other three strategies only about 4.7%. On the recommended coverage, CFLRS is only 3.4% lower than other three strategies. Therefore, CFLRS could predict the users next category of location which they interested, so it could recommend the personalized recommendation results.

中文摘要 i
英文摘要 iii
誌謝 v
表目錄 viii
圖目錄 ix
第一章 緒論 1
1.1 研究動機 2
1.2 研究目的 3
1.3 論文架構 5
第二章 文獻探討 6
2.1位置相關查詢 6
2.2協同過濾推薦系統 7
2.2.1協同過濾推薦機制與限制 8
2.2.2使用者相似度 11
2.3推薦機制之分析與比較 13
2.3.1基於GPS歷史數據協同位置和活動推薦 13
2.3.2基於語意軌跡高效項目推薦系統 14
2.3.3藉由位置歷史資訊推斷用戶社交聯繫 15
2.3.4軌跡相關策略比較 16
第三章 基於GPS軌跡相似之協同過濾位置推薦系統 18
3.1 CFLRS推薦系統架構 18
3.2 CFLRS推薦系統之組成 19
3.2.1檢測軌跡停留點 19
3.2.2語意化軌跡 24
3.2.3計算使用者相似度 27
3.2.4 CFLRS推薦價值計算 31
3.3 CFLRS演算法 35
第四章 效能模擬與分析 38
4.1系統參數設定 38
4.1.1模擬實驗說明 38
4.1.2系統模擬環境設定 40
4.2 效能評估因子 45
4.2.1平均推薦時間 45
4.2.2推薦覆蓋率 45
4.2.3正規化折扣累積增益 46
4.3 模擬結果分析與比較 46
4.3.1停留點閥值分析 47
4.3.2使用者相似度之權重分析 49
4.3.3平均推薦時間分析 51
4.3.4推薦覆蓋率分析 56
4.3.5正規化折扣累積增益分析 60
第五章 結論與未來研究方向 63
5.1結論 63
5.2未來研究方向 64
參考文獻 65
附錄 72
A 中英專有名詞對照表 72
B 參數對照表 75
C 模擬系統介面簡介 77
D 作者簡歷 79

[1]eMarketer, “Most Smartphone Owners Use Location-Based Services,” http://www.emarketer.com/Article/Most-Smartphone-Owners-Use-Location-Based-Services/1013863, Apr. 2016.
[2]J. Oh and Z. J. Haas, “Personal Environment Service Based on the Integration of Mobile Communications and Wireless Personal Area Networks,” IEEE Communications Magazine, vol. 48, no. 6, pp. 66-72, Jun. 2010.
[3]W. Lv, F. Wang, Y. Zhang, and T. Zhu, “A Distributed Location Based Service Framework of Ubiquitous Computing,” in Proceedings of the First International Conference on Networking and Distributed Computing, Hangzhou, China, pp. 43-47, Oct. 2010.
[4]A. Desai, Z. Laliwala, and S. Chaudhary, “Context and Location Based Service Grouping and Group Notification,” in Proceedings of the Asia-Pacific Services Computing Conference, Singapore, pp. 227-232, Dec. 2009.
[5]Z. Yin, L. Cao, J. Han, J. Luo, and T. S Huang, “Diversified Trajectory Pattern Ranking in Geo-Tagged Social Media,’’ in Proceedings of the Society for Industrial and Applied Mathematics Conference, Arizona, USA, pp. 980-991, Apr. 2011.
[6]H. A. Karimi and P. Krishnamurthy, “Real-time Routing in Mobile Networks Using GPS and GIS Techniques,” in Proceedings of the 34th Annual Hawaii International Conference, Hawaii, USA, pp. 11-22, Jan. 2001.
[7]S. J. Vaughan-Nichols, “Will Mobile Computings Future Be Location, Location, Location?,” IEEE Computer Society, vol. 42, no. 2, pp. 14-17, Feb. 2009.
[8]B. Sadoun and O. Al-Bayari, “LBS and GIS Technology Combination and Applications,” in Proceeding of the International Conference on Computer Systems and Applications, Amman, Jordan, pp. 578-583, May 2007.
[9]“2015年來台旅客消費及動向調查”，中華民國交通部觀光局，http://admin.taiwan.net.tw/upload/statistic/20160817/1a5c49a5-d6c4-4b92-ba75-1052067550df.pdf, 2015。
[10]J. L. Herlocker, J. A. Konstan, L. G. Terveen, and J. T. Riedl, “Evaluating Collaborative Filtering Recommender Systems,’’ Journal of the ACM Transactions on Information Systems, vol. 22, no. 1, pp.5-53, 2004.
[11]Yoon H, Y. Zheng,X. Xie, and W. Woo, “Smart Itinerary Recommendation based on User-generated GPS Trajectories,’’ in Proceedings of the Ubiquitous intelligence and computing, New York, USA, pp. 19–34, 2010.
[12]X. Cao, G. Cong, C. S. Jensen, “Mining Significant Semantic Locations from GPS Data,’’ Journal of the VLDB Endowment, vol. 3, no. 1-2, pp. 1009–1020, 2010
[13]Q. Li, Y. Zheng, X. Xie, Y. Chen, and W. Liu, W.Y. Ma, “Mining User Similarity based on Location History,’’ in Proceedings of the 16th ACM SIGSPATIAL international conference on advances in geographic information systems, New York, USA, pp. 34, Nov. 2008.
[14]J. L. Duan, S. Prasad, and J. W. Huang, “Discovering Unknown but Interesting Items on Personal Social Network,’’ in Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 145-156, May 2012.
[15]J. B. Schafer, D. Frankowski, J. Herlocker, and S. Sen, “Collaborative Filtering Recommender Systems,” Springer Berlin Heidelberg, pp. 291-324, 2006.
[16]Y. Zheng, L. Zhang, X. Xie, and W. Y. Ma, “Mining Interesting Locations and Travel Sequences from GPS Trajectories,” in Proceedings of the 18th ACM International Conference on World Wide Web, pp. 791-800, 2009.
[17]Y. Zheng, and X. Xie, “Learning Travel Recommendations from User-generated GPS Traces,” Journal of the ACM Trans Intell Sys Technol , vol. 2, no. 2, pp. 2-29, 2011
[18]謝幸、鄭宇，”基於地理信息的用户行為理解’’， https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/E59FBAE4BA8EE59CB0E79086E4BFA1E681AFE79A84E794A8E688B7E8A18CE4B8BAE79086E8A7A3.pdf，2008。
[19]J. Bao, Y. Zheng, D. Wilkie, and M. Mokbel, “Recommendations in Location-based Social Networks a Survey,” in Proceedings of the Geoinformatica, vol. 19, no. 3, pp. 525-565, 2015.
[20]C. Duhigg, “The Power of Habit：Why We Do What We Do in Life and Business,” Random House Incorporated, Feb. 2012.
[21]L. Huang, Q. Li, and Y. Yue, “Activity Identification from GPS Trajectories using Spatial Temporal POIs’ attractiveness,” in Proceedings of the 2nd ACM SIGSPATIAL international workshop on location based social networks, New York, USA, pp. 27–30, 2010.
[22]P. Symeonidis, A. Papadimitriou, Y. Manolopoulos, P. Senkul, and I. Toroslu, “Geo-social Recommendations based on Incremental Tensor Reduction and Local Path Traversal,” in Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Location-Based Social Networks, Chicago, USA, pp. 89-96, Nov. 2011.
[23]W. S. Ku, and R. Zimmermann, “Location-based Spatial Queries with Data Sharing in Mobile Environments,” in Proceedings of the 22nd International Conference on Data Engineering Workshops, Atlanta, USA, pp. 140-144, Apr. 2006.
[24]項亮，“推薦系統實踐”，人民郵電出版社，第44~63頁，2012。
[25]陶曉，“利用用戶行為數據” https://www.zybuluo.com/xtccc/note/200320，2015。
[26]彭其捷，“[Data mining]協同過濾法(collaborative Filtering)及相關概念”，http://divakalife.blogspot.tw/2010/04/data-mining-collaborative-filtering.html，四月 2010.
[27]P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl , “GroupLens: An Open Architecture for Collaborative Filtering of Netnews,” in Proceedings of ACM Conference on Computer Supported Cooperative Work, pp.175-186, 1994.
[28]蔣凡，”推薦系統”，人民郵電出版社，第8~11頁，2013。
[29]李艷民、胡聰、吳賓等人，”推薦系統技術、評估及高效算法”，機械工業出版社，第387~390頁，2015。
[30]B. Sarwar, G. Karypis, J. Konstan, and J. Riedl, “Item-Based Collaborative Filtering Recommendation Algorithms,” in Proceedings of the 10th international conference on World Wide Web, 2001.
[31]J. L. Herlocker, and J. A. Konstan, “An Algorithmic Framewoek for Performing Collaborative Filtering,” in Proceedings of the 22nd Annual International ACM SIGIR Conference, pp. 230-237, Aug. 1999.
[32]L. T. Weng, Y. Xu, Y. Li, and R. Nayak, “Exploiting Item Taxonomy for Solving Cold-Start Problem in Recommendation Making,” in Proceedings of the 20th IEEE International Conference on Tools with Artificial Intelligence, Dayton, USA, pp. 113-120, 2008.
[33]O. Sean, A. Robin, D. Ted, and F. Ellen, “Mahout in Action,” Oreilly & Associates Incorporated, pp. 40-47, Oct. 2011.
[34]J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl, “An Algorithmic Framework for Performing Collaborative Filtering,” in Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, pp. 230-237, 1999.
[35]O. Sean, A. Robin, D. Ted, and F. Ellen, “Mahout in Action,” Oreilly & Associates Incorporated, pp. 42, Oct. 2011.
[36]V. W. Zheng, Y. Zheng, X. Xie, and Q. Yang, “Collaborative Location and Activity Recommendations with GPS History Data,” in Proceedings of the 19th international conference on World wide web, pp. 1029-1038, 2010.
[37]J. C. Yinga, H. S. Chena, and K. W. Linb, “Semantic Trajectory-based High Utility Item Recommendation System,” Journal of the Expert Systems with Applications, vol. 41, no. 10, pp. 4762-4776, 2014.
[38]X. Xiao, Y. Zheng, Q. Luo, and X. Xie, “Inferring Social Ties Between Users with Human Location History,” Journal of Ambient Intelligence and Humanized Computing, vol. 5, no. 1, pp. 3-19, 2014.
[39]TranSafety, “Study Compares Older and Younger Pedestrian Walking Speeds,” http://www.usroads.com/journals/p/rej/9710/re971001.htm, 1997.
[40]K. Aspelin, N. Carey, “Establishing Pedestrian Walking Speeds,” Portland State University, May 2005.
[41]賴筱桐，”〈台北都會〉忠孝橋引道拆除往北市恐多塞30分鐘” http://news.ltn.com.tw/news/local/paper/955823，2016。
[42]羅躍軍，”一種GPS設備無效漂移信號的過濾方法”，2011。
https://www.google.ch/patents/CN102183773A?cl=zh
[43]Running Biji，“影響GPS定位的環境殺手” http://tw.running.biji.co/index.php?q=news&act=info&id=865，2016。
[44]雷克斯，”關於衛星導航系統的兩三事” http://blog.nutsfactory.net/2014/02/17/about-gps-tracker，2014。
[45]鄭宇、謝幸，”基於用户軌跡挖掘的智能位置服務”，中國計算機學會通訊，2010。
[46]朱麟、柳凱道、孫盛智，”基於空間語意軌跡的GPS航跡行為特徵檢測研究”，計算機應用與軟件，2014。
[47]吳曄堅，”基於用戶協同過濾算法”，https://gold.xitu.io/post/578ef297a34131005b91cb31，2016。
[48]S. Opricovic, G. H. Tzeng, “Compromise Solution by MCDM Methods: a Comparative Analysis of VIKOR and TOPSIS,” European Journal of Operational Research, 2004.
[49]C. C. Tuan, C. F. Hung, and L. W. Yang, “Multi-Dimensional Preference Decision-making for Location Dependent Data Prefetching Query,” in Proceedings of the Knowledge Community Seminar on KC2011, Taipei, Taiwan, May 28, 2011.
[50]“103年度各月份人口數、戶數統計表”，臺北市政府民政局，http://ca.gov.taipei/public/Attachment/621911361859.htm，2014。
[51]WikiGPS, http://www.wikigps.com, 2014
[52]Mobile01, http://www.mobile01.com/topicdetail.php?f=228&t=1011422, 2009
[53]A. Gerald, “The Likert Scale Revisited,” Journal-Market research society, vol. 39, no. 2, pp. 313-348, Apr. 1997.
[54]J. Dearringer, “A Tale of Two Studies: Establishing Google & Bing Click-Through Rates”, https://moz.com/blog/a-tale-of-two-studies-google-vs-bing-clickthrough-rate, 2011
[55]C. D. Manning, P. Raghavan, H. Sch¨utze, “Introduction to information retrieval,” Cambridge University Press, vol. 1, pp. 422-446, 2008.