臺灣博碩士論文加值系統

隨著社群媒體的熱門興起（如Facebook, Flickr），使用者可以輕易地分享他們在旅行中的打卡資訊以及照片等等。從大量的打卡資料以及照片資訊的角度來看，我們希望能夠透過這些旅遊經驗來讓旅行規劃變得更容易。先前的研究探討了如何透過打卡資料來對既有的旅遊軌跡進行探勘以及排序。我們發現當使用者在進行旅行規劃時，使用者會使用一些與他們的旅行偏好相關的關鍵字，而且他們也會需要一個多元化的旅遊軌跡推薦結果。為了要提供一個多元的旅遊軌跡集合，我們認為需要從景點資料中萃取出更多的特徵資料。因此，在這篇論文中我們提出了一個關鍵字感知天際線旅遊規劃(KSTR)框架，可以從歷史紀錄的行動資料以及使用者的社交行為來進行有效的知識萃取。更進一步的說，我們從地理相關的mobility pattern、拜訪時間的影響以及社群的影響上取得特徵資訊，來解決Where、When、Who這三個議題。接著我們提出了一個關鍵字萃取模組，透過自動的將景點相關的關鍵字分類成不同的種類，來有效的與query輸入的關鍵字進行配對。接著我們設計了一個路徑重組的演算法來建立符合條件的旅遊路徑。為了要能提供一個多元化的結果，我們使用了天際線(Skyline)的概念來挑出最後的旅遊路徑。我們也使用了真實的地理相關的社群資料來進行實驗來驗證我們提出的演算法的效用以及效率，而實驗結果也顯現出KSTR良好的效能表現。

With the popularity of social media (e.g., Facebook and Flickr), users could easily share their check-in records and photos during their trips. In view of the huge amount of check- in data and photos in social media, we intend to discover travel experiences to facilitate trip planning. Prior works have been elaborated on mining and ranking existing travel routes from check-in data. We observe that when planning a trip, users may have some keywords about preference on his/her trips. Moreover, a diverse set of travel routes is needed. To provide a diverse set of travel routes, we claim that more features of Places of Interests (POIs) should be extracted. Therefore, in this paper, we propose a Keyword-aware Skyline Travel Route (KSTR) framework that use knowledge extraction from historical mobility records and the user’s social interactions. Explicitly, we model the “Where, When, Who” issues by featurizing the geographical mobility pattern, temporal influence and social influence. Then we propose a keyword extraction module to classify the POI-related tags automatically into different types, for effective matching with query keywords. We further design a route reconstruction algorithm to construct route candidates that fulfill the query inputs. To provide diverse query results, we explore Skyline concepts to rank routes. To evaluate the effectiveness and efficiency of the proposed algorithms, we have conducted extensive experiments on real location-based social network datasets, and the experimental results show that KSTR does indeed demonstrate good performance compared to state-of-the-art works.

摘要 ................... i
Abstract ................... ii
致謝 ................... iii
1 Introduction ...................1
2 Framework Overview ...................6
2.1 Keyword Extraction and PatternDiscovery ................... 8
2.1.1 Keyword Extraction ................... 8
2.1.2 Pattern Discovery Methods ............... 11
3 Travel route exploration ...................17
3.1 Query Keyword Matching .................... 17
3.2 Candidate Route Generation................... 19
3.3 Skyline Travel Routes Search .................. 21
3.4 Greedy Pruning.......................... 23
3.5 System Implementation...................... 24
4 Experiments................... 26
4.1 Keyword matching accuracy ................... 27
4.2 Efficiency ............................. 29
4.2.1 Tuning Approximate Parameters................... 30
4.2.2 Scalability......................... 31
4.3 Evaluation of route prediction accuracy ................... 33
4.3.1 Comparison of route prediction accuracy................... 34
4.4 ExamplesofRouteRecommendation................... 35
5 Conclusion ...................37
Bibliography...................38

[1] Z. Chen, H. T. Shen, X. Zhou, Y. Zheng, and X. Xie, “Searching trajec- tories by locations: an efficiency study,” in SIGMOD, 2010, pp. 255–266.
[2] H.-P. Hsieh and C.-T. Li, “Mining and planning time-aware routes from check-in data,” in CIKM, 2014, pp. 481–490.
[3] V. S. Tseng, E. H.-C. Lu, and C.-H. Huang, “Mining temporal mobile sequential patterns in location-based service environments,” in Proceed- ings of the 13th International Conference on Parallel and Distributed Systems (ICPADS), vol. 2, 2007, pp. 1–8.
[4] W. T. Hsu, Y. T. Wen, L. Y. Wei, and W. C. Peng, “Skyline travel routes: Exploring skyline for trip planning,” in MDM, vol. 2, 2014, pp. 31–36.
[5] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma, “Mining interesting loca- tions and travel sequences from gps trajectories for mobile users,” in WWW, 2009, pp. 791–800.
[6] Q. Yuan, G. Cong, and A. Sun, “Graph-based point-of-interest recom- mendation with geographical and temporal influences,” in CIKM, 2014, pp. 659–668.
[7] M. Ye, P. Yin, W.-C. Lee, and D.-L. Lee, “Exploiting geographical in- fluence for collaborative point-of-interest recommendation,” in SIGIR, 2011, pp. 325–334.
[8] Y.-T. Wen, P.-R. Lei, W.-C. Peng, and X.-F. Zhou, “Exploring social influence on location-based social networks,” in ICDM, 2014, pp. 1043– 1048.
[9] L.-Y. Wei, W.-C. Peng, B.-C. Chen, and T.-W. Lin, “Pats: A framework of pattern-aware trajectory search,” in MDM, 2010, pp. 372–377.
[10] H.-P. Hsieh, C.-T. Li, and S.-D. Lin, “Exploiting large-scale check-in data to recommend time-sensitive routes,” in UrbComp, 2012, pp. 55– 62.
[11] H. Gao, J. Tang, and H. Liu, “Exploring social-historical ties on location- based social networks.” in ICWSM, 2012.
[12] T. Lee, Z. Wang, H. Wang, and S.-w. Hwang, “Attribute extraction and scoring: A probabilistic approach,” in ICDE, 2013, pp. 194–205.
[13] T. Kurashima, T. Iwata, G. Irie, and K. Fujimura, “Travel route rec- ommendation using geotags in photo sharing sites,” in CIKM, 2010, pp. 579–588.