成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	林家慶 Lin, Chia-Ching
論文名稱：	在時間限制下有效率地探勘前K條最短路徑 Efficiently Mining Top-K Shortest Paths within a Travel Time Constraint in Road Networks
指導教授：	曾新穆 Tseng, Vincent S.
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2008
畢業學年度：	96
語文別：	中文
論文頁數：	63
中文關鍵詞：	路徑推薦、最短路徑、導覽路徑、全球定位系統、資料探勘
外文關鍵詞：	Global positioning system, Shortest path, Data mining., Navigation paths, Path recommendation
相關次數：	點閱：104 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

近年來，全球定位系統廣泛地被應用在生活中，進而衍生許多相關研究，而導覽路徑之規劃是其中一個重要的研究議題。本論文中，在使用者能接受旅程時間之路徑中，推薦前K條最短距離路徑，提出一個新的資料探勘演算法PATE〈Prediction-based Algorithm for Travel time Evaluation〉，準確地預測導覽路徑之旅程時間，並使用ENS-Tree〈Efficient Navigation path Search Tree〉結構，有效率地推薦導覽路徑給使用者，且減少記憶體儲存空間。在已知研究中，本論文為第一篇在規劃導覽路徑時加入時間限制之研究。最後，設計一套在道路網路下的資料產生器，模擬現實生活中之道路網路狀況，並做一系列實驗，證明本論文之方法在不同環境參數下有優異的效率與準確率。

In recent years, a number of studies have been done on GPS (Global Positioning System) due to the wide applications and one important issue is on the GPS navigation. In this paper, we propose a novel data mining algorithm named PATE (Prediction-based Algorithm for Travel time Evaluation) that can efficiently predict the travel time of a navigation path and precisely recommends the top-k navigation paths to the users under a user-specified travel time constraint in road network environments. To our best knowledge, this is the first work on discovering the shortest navigation path within a travel time constraint. Furthermore, we propose a novel search structure named ENS-Tree (Efficient Navigation Path Search Tree) for efficiently finding the shortest navigation path that meets the user-specified travel time constraint. Through a series of experiments, the proposed method was shown to have excellent performance under different system conditions.

英文摘要...............................................................................................................................i
中文摘要...............................................................................................................................ii
表目錄..................................................................................................................................v
圖目錄.................................................................................................................................vi
第一章 導論...............................................................................................................1
1 研究背景.......................................................................................................1
2 研究動機.......................................................................................................2
3 問題描述.......................................................................................................3
4 研究貢獻.......................................................................................................5
5 論文架構.......................................................................................................5
第二章 文獻討論.......................................................................................................6
1 全球定位系統〈Global Positioning System〉..........................................6
2 路徑規劃.......................................................................................................7
2.1 Dijkstra演算法.....................................................................................7
2.2 A*演算法..............................................................................................8
2.3 最快時間路徑.......................................................................................9
3 與時間切割相關研究.................................................................................11
4 資料探勘方法.............................................................................................13
4.1 關聯式規則探勘法〈Association Rule Mining〉...........................13
4.2 序列型樣探勘法〈Sequential Patterns Mining〉..........................15
4.3 瀏覽路徑探勘法〈Navigation Pattern Mining〉...........................19
第三章 研究方法.....................................................................................................22
1 方法架構.....................................................................................................22
2 資料前處理.................................................................................................23
3 PATE〈Prediction-based Algorithm for Travel time Evaluation〉.....25
3.1 決定斷點個數.....................................................................................25
3.2 決定斷點位置.....................................................................................26
3.3 時間切割方法.....................................................................................27
3.4 旅程時間評估表的計算.....................................................................29
4 ENS-Tree〈Efficient Navigation path Search Tree〉............................30
4.1 導覽路徑探勘.....................................................................................30
4.2 建構ENS-Tree....................................................................................33
4.3 使用ENS-Tree....................................................................................35
5 推薦系統.....................................................................................................36
第四章 實驗分析.....................................................................................................40
1 道路網路上導覽路徑之模擬.....................................................................40
2 實驗規劃.....................................................................................................43
iv
3 PATE效能實驗...........................................................................................45
3.1 時間區段個數之影響.........................................................................45
3.2 時間切割之優點.................................................................................46
3.3 各種方法之評估.................................................................................46
3.4 交通擁塞程度之影響.........................................................................47
3.5 道路網路規模之影響.........................................................................49
4 ENS-Tree效能實驗....................................................................................50
4.1 搜尋效率分析.....................................................................................50
4.2 記憶體分析.........................................................................................51
5 路徑推薦準確率實驗.................................................................................53
5.1 時間限制之影響.................................................................................53
5.2 交通擁塞程度之影響.........................................................................54
5.3 道路網路規模之影響.........................................................................55
5.4 路徑的推薦數之影響.........................................................................56
6 實驗總結.....................................................................................................57
第五章 結論.............................................................................................................58
1 研究結論.....................................................................................................58
2 未來發展.....................................................................................................59
參考文獻.............................................................................................................................60
                                    

[1].R. Agrawal, T. Imielinski, and A. Swami. Mining Association Rule between Sets of Items in Large Databases. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 207-216, Washington, D.C., May 1993.
[2].R. Agrawal and R.Srikant. Fast Algorithms for Mining Association Rules, In Proceeding of the 20th Very Large Data Bases, pages 487-499, Santiago, Chile, 1994.
[3].R. Agrawal and R. Srikant. Mining Sequential Patterns. In Proceedings of International Conference on Data Engineering, pages 3-14, Taipei, Taiwan , March 1995.
[4].A. Awasthi, Y. Lechevallier, M. Parent, and J. M. Proth. Rule based prediction of fastest paths on urban networks. In Proceedings of the 8th International IEEE Conference on Intelligent Transportation Systems, Vienna, Austria, September, 2005.
[5].S. K. Barai, DATA MINING APPLICATIONS IN TRANSPORATION ENGINEERING. Transport, 2003.
[6].J. Borges and M. Levene. Data Mining of User Navigation Patterns. In Proceedings of the WBBKDD'99 Workshop on Web Usage Analysis and User Profiling, San Diego, CA, USA, pages 31-36, 1999.
[7].M. S. Chen, J. Han, and P. Yu. Data Mining: An Overview from Database Perspective. IEEE Transactions on Knowledge and Data Engineering, Vol. 8, No. 6, pages 866-883, December 1996.
[8]. M. S. Chen, J. S. Park, and P. S. Yu. Data Mining for Path Traversal Patterns in a Web Environment. In Proceedings of the 16th International Conference on Distributed Computing Systems, Hong Kong, pages 385-392, May 27-30 1996.
[9]. M. S. Chen, J. S. Park, and P. S. Yu. Efficient Data Mining for Path Traversal Patterns. IEEE Transactions on Knowledge and Data Engineering, Vol. 10, No. 2, pages 209-221, March 1998.
[10].C. H. Cheong, and M. H. Wong. Mining Popular Paths in a Transportation Database System with Privacy Protection. In Proceedings of the 22nd International Conference on Data Engineering Workshops, 2006.
[11].H. D. Chon, D. Agrawal, and A. El. Abbadi, FATES: Finding A Time dEpendent Shortest path. In Proceedings of the 4th International Conference on Mobile Data Management, Melbourne, Australia. pages 165–180, 2003.
[12].E. W. Dijkstra. A Note on Two Problems in Connection with Graphs. Numerische Mathematik , Vol. 1, No. 1, pages 269-271, December 1959.
[13].A. El-Rabbany. (2006). Introduction to GPS :the Global Positioning System. 2nd ed, Boston, MA: Artech House.
[14].F. Engineer. Fast Shortest Path Algorithms for Large Road Networks. In Proceedings of the 36th Annual ORSNZ Conference, Wellington, New Zealand. 2001.
[15].H. Gonzalez, J. Han, X. Li, M. Myslinska, and J. P. Sondag. Adaptive Fastest Path Computation on a Road Network: A Traffic Mining Approach. In Proceeding of the 14th international conference on Very Large Data Bases, Vienna, Austria, September 2007.
[16].M. Halvey, T. Keane, and B. Smyth. Time-Based Segmentation of Log Data for User Navigation Prediction in Personalization. In Proceeding of the International Conference on Web Intelligence, pages 636-640, France, September 2005.
[17].M. Halvey, T. Keane, and B. Smyth. Predicting Navigation Patterns on the Mobile-Internet Using Time of the Week. In Proceeding of the 14th international conference on World Wide Web, pages 958-959, Chiba, Japan, May 2005.
[18].M. Halvey, T. Keane, and B. Smyth. Time Based Patterns in Mobile-Internet Surfing. In Proceedings of the SIGCHI conference on Human Factors in computing system, pages 31-34, Montréal, Québec, Canadaems, April 2006.
[19].P. E. Hart, N. J. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, Vol. SSC-4, No. 2, pages 100-107, 1968.
[20].J. Han, J. Pei, Y. Yin, and R. Mao. Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach. Data Mining and Knowledge Discovery, Vol. 8, No. 1, pages 53-87, 2004.
[21].E. Kanoulas, Y. Du, T. Xia, and D. Zhang. Finding Fastest Paths on A Road Network with Speed Patterns. In Proceeding of the 22nd International Conference on Data Engineering, 2006.
[22].N. Lassabe, A. Berro, and Y Duthen. Improvement of a Shortest Routes Algorithm. In Proceedings of the 10th International IEEE Conference on Intelligent Transportation Systems, Seattle, WA, USA, September 2007.
[23].J. Lin, E. Keogh, S. Lonardi, and B. Chiu. A Symbolic Representation of Time Series, with Implications for Streaming Algorithms. In Proceedings of the 8th ACM SIGMOD workshop on Research Issues in Data Mining and Knowledge Discovery, Diego, CA, June 2003.
[24].K. Nachtigall. Time depending shortest-path problems with applications to railway networks. European Journal of Operational Research, Vol. 83, pages 154-166, 1995.
[25].S. Pallottino and M. G. Scutella. Shortest Path Algorithms in Transportation models: classical and innovative aspects. Equilibrium and Advanced Transportation Modelling, pages 245-281. Kluwer Academic Publishers, 1998.
[26].J. S. Park, M. S. Chen, and P. S. Yu. An Effective Hash-Based Algorithm for Mining Association Rules, Proceeding. of the ACM SIGMOD Conference on Management of Data, pages 157-186, May 1995.
[27].M. Spiliopoulou, L. C. Faulstich, and K. Winkler. A Data Miner analyzing theNavigational Behaviour of Web Users. In Proceedings of the Workshop on Machine Learning in User Modelling of the ACA199, Greece, July 1999.
[28].K. Sung, M. G. H. Bell, M. Seong, S. Park. Shortest paths in a network with time-dependent flow speeds. European Journal of Operational Research, Vol. 121, No.1, pages 32–39, 2000.
[29]. Vincent. S. Tseng and K. W. Lin. Efficient Mining and Prediction of User Behavior Patterns in Mobile Web Systems. Information and Software Technology, Vol. 48, No. 6, pages 357-369, June 2006.
[30]. F. B. Zhan. Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures. Journal of Geographic Information and Decision Analysis, Vol. 1, No. 1, pages 69-82, 1997.

校內：2009-08-06公開
校外：2010-08-06公開

簡易檢索 / 詳目顯示

相關論文