進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-1708202017271200
論文名稱(中文) 建構及預測區域OD矩陣–以YouBike為例
論文名稱(英文) Constructing and predicting the regional origin-destination matrix from rental data - using the YouBike system in Taipei
校院名稱 成功大學
系所名稱(中) 資訊工程學系
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 108
學期 2
出版年 109
研究生(中文) 蕭詠麟
研究生(英文) Wing-Lun Siu
學號 P76075034
學位類別 碩士
語文別 英文
論文頁數 74頁
口試委員 指導教授-李強
口試委員-陳奕中
口試委員-黃淵科
召集委員-劉傳銘
口試委員-鍾毓驥
中文關鍵字 OD矩陣  空間資訊  空間資訊分群  人流預測 
英文關鍵字 origin-destination matrix  spatial information  spatial information clustering  people flow prediction 
學科別分類
中文摘要 Origin-Destination Matrix (OD矩陣)是空間資訊的專有名詞,其有效檢視道路的交通流量、城市的人流狀況、公共交通的需求程度等。OD矩陣亦被廣泛應用在交通、旅遊、商業、運輸等方面,因此深受學者及企業研究與應用。然而,OD矩陣的建構及預測是十分複雜與困難。首先在建構方面,OD矩陣建構過程中如果沒有適當定義起點與終點,容易造成資源的浪費,而且過往的方法定義起終點並沒有考慮資料的特性,容易把屬性不相似的資料歸類為同一個起終點,可能對後續預測的效果造成影響。在OD矩陣預測方面,空間因素的資訊無疑是預測的重要一環,但資料的空間特性往往難以表示,過往方法對於資料的空間屬性表示也過於簡單,未必能有效提升模型預測的效果。再者,外在因素間接影響模型預測的結果,例如雨天減少戶外地區的人流、週末提升觀光景點的交通量、上下班時段公共交通需求量增加等,因此在建構及預測OD矩陣時我們都必需考慮完整因素。鑑於以上建構及預測OD矩陣的問題,本論文開發了一套完整的OD矩陣建構及預測框架。在建構方面,我們基於DBSCAN開發HTS-DBSCAN演算法,該方法有效針對資料的距離與時間特性進行分群,同時改善傳統DBSCAN雜訊過多及資料無法切割的問題。在預測方面,我們提出了空間資料表示的方法,有效表示資料的距離與影響範圍。另外,也加入多種的外在因素進行預測,藉此提升模型預測的效果。在本論文最後,我們利用台灣台北市的YouBike借用量資料進行了一系列的實驗,並得到了不錯的成果。
英文摘要 Origin-destination (OD) matrices are widely used in transportation research to model the flow of people or vehicles within a given region. However, the construction of OD matrices is complicated by difficulties in defining appropriate start and end points, representing spatial features, and dealing with external factors, such as rain, periodic fluctuations in flow, and accidents. This paper presents a framework for the construction of OD matrices based on DBSCAN, in which data is grouped according to spatial and temporal characteristics. In formulating predictions, spatial data is represented in terms of distance and influence range. Mechanisms are also provided to deal with external factors. The efficacy of the proposed scheme was demonstrated in a series of experiments based on the YouBike rental data system in Taipei, Taiwan.
論文目次 摘要 I
Abstract II
Acknowledgements III
Table of Contents IV
List of Tables VI
List of Figures VII
I. Introduction 1
II. Related Work 11
2.1 DBSCAN Related Research 11
2.1.1 DBSCAN 11
2.1.2 ST-DBSCAN 11
2.1.3 HDBSCAN 11
2.2 Deep Learning 12
2.2.1 Artificial Neural Network 12
2.2.2 Deep Neural Network 12
2.2.3 Convolutional Neural Network 13
2.2.4 Long Short Term Memory 13
2.3 Research on People Flow and Destination Prediction 14
2.3.1 ST-RNN 14
2.3.2 Deep Spatio-temporal Residual Network 14
2.4 Research on OD matrix 15
2.4.1 Efficient OD Trip Matrix Prediction Based on Tensor Decomposition 15
2.4.2 Grid-Embedding based Multi-task Learning 15
2.4.3 MUlti-task Representation learning model for Arrival Time estimation 17
III. Datasets 18
3.1 Taipei City YouBike Data 18
3.2 Weather data of Taipei City in 2016 20
IV. Algorithm 21
4.1 Station Clustering 21
4.1.1 The introduction of DBSCAN 23
4.1.2 Time Series DBSCAN(TS-DBSCAN) 25
4.1.3 Hierarchical Time Series DBSCAN(HTS-DBSCAN) 29
4.1.4 Noise Handling of HTS-DBSCAN 32
4.2 Constructing OD Matrixes in Historical Areas 34
4.2.1 Definition of The Origin and Destination of The Area OD Matrix 34
4.2.2 Constructing Historical District OD Matrices 36
4.3 Prediction of Future OD Matrices 36
4.3.1 History Model 36
4.3.2 Spatial Model 37
4.3.3 External Model 42
4.3.4 Fusion Model 43
V. Experiment 45
5.1 Station Clustering 45
5.1.1 Comparison of DBSCAN, TS-DBSCAN and HTS-DBSCAN Results 45
5.1.2 Comparison of HTS-DBSCAN and K-means Analysis 47
5.2 Regional OD Matrix Prediction 51
5.2.1 Other Model Comparisons 53
5.2.2 Predictions for Different Time Units 54
5.2.3 Single Cluster and All Cluster Predictions 62
5.2.4 Model Factor Analysis 64
5.2.5 Inputting Historical Time Steps Analysis 68
VI. Conclusion 70
6.1 Advantages and Contributions 70
6.2 Conclusion 70
References 72
參考文獻 [1] Lingbo Liu, Zhilin Qiu, Guanbin Li, Qing Wang, Wanli Ouyang, Liang Lin, "Contextualized Spatial–Temporal Network for Taxi Origin-Destination Demand Prediction," IEEE Transactions on Intelligent Transportation Systems, pp. 3875-3887, 2019.
[2] Shudong Liu, Liaoyuan Zhang, Xu Chen, “Travel Destination Prediction Based on Origin-Destination Data,” Complex, Intelligent and Software Intensive Systems, pp. 315-325, 2020.
[3] Y. Englezou, Stelios Timotheou, Christos G. Panayiotou, “Bayesian estimation of the Origin-Destination matrix using traffic flow dynamics.,” International Conference on Intelligent Transportation Systems, pp. 2545-2550, 2019.
[4] Adrien Ickowicz, Ross Sparks:, “Estimation of an origin/destination matrix: application to a ferry transport data.,” Public Transport - Planning and Operations, pp. 235-258, 2015.
[5] Juha-Matti Kuusinen, Janne Sorsa, Marja-Liisa Siikonen, “The Elevator Trip Origin-Destination Matrix Estimation Problem.,” Transportation Science, pp. 559-576, 2015.
[6] Yuandong Wang, Hongzhi Yin, Hongxu Chen, Tianyu Wo, Jie Xu, Kai Zheng, “Origin-Destination Matrix Prediction via Graph Convolution: a New Perspective of Passenger Demand Modeling,” KDD, pp. 1227-1235, 2019.
[7] Huaxiu Yao, Fei Wu, Jintao Ke, Xianfeng Tang, Yitian Jia, Siyu Lu, Pinghua Gong, Jieping Ye, Zhenhui Li, “Deep Multi-View Spatial-Temporal Network for Taxi Demand Prediction,” AAAI, pp. 2588-2595, 2018.
[8] Anahid Nabavi Larijani, Ana-Maria Olteanu-Raimond, Julien Perret, Mathieu Brédif, Cezary Ziemlicki, “Investigating the mobile phone data to estimate the origin destination flow and analysis; case study: Paris region,” Transportation Research Procedia, pp. 64-78 , 2015.
[9] Junbo Zhang, Yu Zheng, Dekang Qi, “Deep Spatio-Temporal Residual Networks for Citywide Crowd Flows Prediction.,” AAAI, pp. 1655-1661, 2017.
[10] Martin Ester, Hans-Peter Kriegel, Jiirg Sander, Xiaowei Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” KDD, 1996.
[11] “ST-DBSCAN: An algorithm for clustering spatial–temporal data,” Data & Knowledge Engineering, pp. 208-221 , 2007.
[12] Leland McInnes, John Healy, and Steve Astels, “hdbscan: Hierarchical density based clustering,” The Journal of Open Source Software, 2017.
[13] Karen Simonyan, Andrew Zisserman, “Very Deep Convolutional Networks for Large-Scale Image Recognition,” ICLR, 2015.
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, Jian Sun, “Deep Residual Learning for Image Recognition,” CVPR, pp. 770-778 , 2016.
[15] Gao Huang, Zhuang Liu, Laurens van der Maaten, Kilian Q. Weinberger, “Densely Connected Convolutional Networks,” CVPR, 2016.
[16] Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, Jian Sun, “ShuffleNet: An Extremely Efficient Convolutional Neural Network for Mobile Devices,” CVPR, 2017.
[17] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, Yoshua Bengio, “Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling,” Neural and Evolutionary Computing, 2014.
[18] Xingjian Shi, Zhourong Chen, Hao Wang, Dit-Yan Yeung, Wai-kin Wong, Wang-chun Woo, “Convolutional LSTM Network: A Machine Learning Approach for Precipitation Nowcasting,” CVPR, 2015.
[19] Guokun Lai, Wei-Cheng Chang, Yiming Yang, Hanxiao Liu, “Modeling Long- and Short-Term Temporal Patterns with Deep Neural Networks,” SIGIR, 2018.
[20] Qiang Liu, Shu Wu, Liang Wang, Tieniu Tan, “Predicting the Next Location: A Recurrent Model with Spatial and Temporal Contexts,” AAAI, 2016.
[21] Shanshan Feng, Gao Cong, Bo An, Yeow Meng Chee, “POI2Vec: Geographical Latent Representation for Predicting Future Visitors.,” AAAI, 2017.
[22] Tomas Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, Jeffrey Dean, “Distributed Representations of Words and Phrases and their Compositionality,” NIPS, 2013.
[23] Jiangtao Ren, Qiwei Xie, “Efficient OD Trip Matrix Prediction Based on Tensor Decomposition.,” MDM, pp. 180-185, 2017.
[24] Yaguang Li, Kun Fu, Zheng Wang, Cyrus Shahabi, Jieping Ye, Yan Liu, “Multi-task Representation Learning for Travel Time Estimation.,” KDD, 2018.
[25] “台灣政府資料開放平台,” [線上]. Available: https://data.gov.tw.
[26] “https://taipei.youbike.com.tw/,” [線上]. Available: YouBike 公共自行車.
[27] “Weather Underground,” [線上]. Available: https://www.wunderground.com.
[28] Benjamin Moseley, Joshua R. Wang, “Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search,” NIPS, 2017.
[29] Y. Wu, S. Yang, and X. Yan, “Ontology-based subgraph querying.,” ICDE, p. 697–708, 2013.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2025-08-17起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2025-08-17起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw