請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49698
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 黃奎隆(Kwei-Long Huang) | |
dc.contributor.author | Chia-Hsiu Fu | en |
dc.contributor.author | 傅嘉修 | zh_TW |
dc.date.accessioned | 2021-06-15T11:42:41Z | - |
dc.date.available | 2020-08-21 | |
dc.date.copyright | 2020-08-21 | |
dc.date.issued | 2020 | |
dc.date.submitted | 2020-08-13 | |
dc.identifier.citation | Huang, H. Gartner, G. (2014). Using trajectories for collaborative filtering-based POI recommendation, Int. J. Data Mining, Modelling and Management, Vol. 6, No. 4, pp.333–346. Cui, G., Luo, J., Wang, X. (2017). Personalized travel route recommendation using collaborative filtering based on GPS trajectories. International Journal of Digital Earth, 11(3), 284–307. Zheng, Y. (2015). Trajectory Data Mining: An Overview. ACM Transactions on Intelligent Systems and Technology. 6. 1-41. Yoon, H., Zheng, Y., Xie, X., Woo, W. (2010). Smart itinerary recommendation based on user-generated gps trajectories. In: Ubiquitous intelligence and computing. Springer, pp.19–34 Zhang, F., Yuan, N. J., Wilkie, D., Zheng, Y. Xing, X. (2015). Sensing the Pulse of Urban Refueling Behavior: A Perspective from Taxi Mobility. ACM Transactions on Intelligent Systems and Technology. 6. 1-23. Zheng, Y., Li, Q., Chen Y., Xing, X. Ma, W. (2008). Understanding mobility based on GPS data. UbiComp 2008 - Proceedings of the 10th International Conference on Ubiquitous Computing. 312-321. Huang, J., Wang, L., Tian, C., Zhang, F. Xu, C. (2014). Mining freight truck's trip patterns from GPS data. 2014 17th IEEE International Conference on Intelligent Transportation Systems, ITSC 2014. 1988-1994. Lee WC., Krumm J. (2011). Trajectory Preprocessing. In: Zheng Y., Zhou X. (eds) Computing with Spatial Trajectories. pp.3-33. New York, Springer Douglas, D., Peucker, T. (1973). Algorithms for the Reduction of the Number of Points Required to Represent a Line or its Caricature. The Canadian Cartographer 10(2), 112–122 Gudmundsson, J. Kreveld, M. (2006). Computing longest duration flocks in trajectory data. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems. 35-42. Zheng, K., Zheng, Y., Yuan, N. J., Shang, S. Zhou, X. (2014). Online Discovery of Gathering Patterns over Trajectories. IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 8, pp. 1974-1988 Endo Y., Toda H., Nishida K., Kawanobe A. (2016). Deep Feature Extraction from Trajectories for Transportation Mode Estimation. PAKDD 2016: Proceedings, Part II, of the 20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, Volume 9652. pp.54-66 Yao, D. Zhang, C., Zhu, Z., Hu, Q., Wang, Z., Huang, J. Bi, J. (2018). Learning deep representation for trajectory clustering. Expert Systems. 35. e12252. Fu, Z., Hu, W. Tan, T. (2005). Similarity based vehicle trajectory clustering and anomaly detection. IEEE International Conference on Image Processing 2005, Genova, pp.602-605 Sabarish, B. A., Ramesh K., Kumar T, G. (2019). String-Based Feature Representation for Trajectory Clustering. International Journal of Embedded and Real-Time Communication Systems, 10(2), 1–18. Wang, Y., Qin, K., Chen, Y., Zhao, P. (2018). Detecting Anomalous Trajectories and Behavior Patterns Using Hierarchical Clustering from Taxi GPS Data. ISPRS International Journal of Geo-Information, 7(1), 25. Hung, C.-C., Peng, W.-C., Lee, W.-C. (2011). Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. The VLDB Journal, 24(2), 169–192. Zhang, C., Han, J., Shou, L., Lu, J., La Porta, T. (2014). Splitter: Mining Fine-Grained Sequential Patterns in Semantic Trajectories. Proceedings of the VLDB Endowment, 7(9), 769–780. Magdy, N., Sakr, M. A., Mostafa, T. El-Bahnasy, K. (2015). Review on trajectory similarity measures, 2015 IEEE Seventh International Conference on Intelligent Computing and Information Systems (ICICIS), Cairo, pp. 613-619 Agrawal, R., Faloutsos, C., Swami, A. (1993). Efficient Similarity Search In Sequence Databases. Lecture Notes in Computer Science. 730. 69-84. Berndt, D. J., Clifford, J. (1994) Using dynamic time warping to find patterns in time series. AAAI-94 workshop on knowledge discovery in databases, pp.229–248 Dodge, S., Laube, P., Weibel, R. (2012). Movement similarity assessment using symbolic representation of trajectories. International Journal of Geographical Information Science, 26(9), 1563–1588. Chen, L., Ng, R. (2004). On The Marriage of Lp-norms and Edit Distance. Proceedings 2004 VLDB Conference, 792–803. Chen, L., Özsu, M. T., Oria, V. (2005). Robust and fast similarity search for moving object trajectories. In Proceedings of the 24th ACM SIGMOD International Conference on Management of Data. ACM, 491–502. Vlachos, M., Kollios, G., Gunopulos, D. (2002). Discovering similar multidimensional trajectories, Proceedings 18th International Conference on Data Engineering, San Jose, CA, USA, pp.673-684 Choong, M. Y., Angeline, L., Chin, R. K. Y., Beng Yeo, K., Teo, K. T. K. (2017). Modeling of vehicle trajectory clustering based on LCSS for traffic pattern extraction. 2017 IEEE 2nd International Conference on Automatic Control and Intelligent Systems (I2CACIS). Kota Kinabalu, pp.74-79 Wagner, R. A. Fischer, M. J. (1974). The String-to-String Correction Problem. Journal of the ACM, Vol. 21, No. 1, 168–173. Yim, O. Kylee, A. B. (2015). Hierarchical Cluster Analysis: Comparison of Three Linkage Measures and Application to Psychological Data. The Quantitative Methods for Psychology. 11. 8-21. Jarman, A. (2020). Hierarchical Cluster Analysis: Comparison of Single linkage,Complete linkage, Average linkage and Centroid Linkage Method. 10.13140/RG.2.2.11388.90240. Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20, 53–65. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49698 | - |
dc.description.abstract | 隨著網際網路的普及,人們的消費模式也正在逐漸改變,電子商務供應鏈的發展促使線上零售的管道取代部分的傳統實體零售店面,而宅配在此供應鏈中負責最後一哩運送,佔有不可或缺的地位。近年隨著電商的蓬勃發展,宅配的需求也隨之增長,並衍生出龐大的宅配物流商機。而宅配貨件的配送工作因為貨件量大、工時長、路線規劃所要考慮的因素複雜,造成宅配人員的工作壓力居高不下。若能從大量累積的軌跡資料中將無形的過往經驗轉化為可判讀的知識,針對配送區內的紀錄歸納出較為頻繁的運送模式做為參考,應能有效幫助配送人員縮短作業時間,也降低各項成本的耗損。 本研究針對都市區域內的貨運車輛軌跡進行觀察,將軌跡資料中的資料點轉換為網格化表示以及路段表示,同時使用加權編輯距離(Weighted Edit Distance)以及最長共同子序列(Longest Common Subsequence)兩種方式定義樣本相似度的計算方式,並針對編輯距離在軌跡序列長度不同時,編輯距離會隨著長度膨脹的問題做出了修正,並且利用元素之間的距離關係定義作為依據,提出新的編輯操作成本定義方式。從分群結果來看,該資料集雖然不存在明顯的群集,但其中仍然有部分樣本具有非常相似的特徵,表明在該觀察區域內,駕駛車輛的人員確實具有習慣的行為模式。 | zh_TW |
dc.description.abstract | Due to the popularity of the internet, people's consumption patterns are gradually changing. Online retail websites are gradually replacing traditional retail stores because of the rapid development of e-commerce. In supply chains of E-commerce, home delivery is responsible for the last mile delivery and takes an important role in the distribution of goods. In recent years, with the vigorous development of online shopping, the demand for commodity distribution has also increased and created a lot of business opportunities for home delivery. Due to the large quantity of goods, long working hours, and complex factors to be considered in route planning of delivery, the couriers are working under great stress. The purpose of this study is to provide couriers with some experience-based route planning advice through finding the frequent trajectory patterns from the GPS records of home delivery fright trucks in urban areas. In this study, we applied a framework of trajectory pattern mining to observe the GPS records of home delivery fright trucks in urban areas and proposed a new concept to define the operation costs of edit distance based on the geographical relations between elements, and we also normalized the pairwise distance using the length of trajectory sequences. The data we used is recorded by the in-vehicle GPS devices equipped on the freight trucks and presented as sequences of timestamped coordinates on a daily basis. The raw GPS trajectory data is transformed into grid-based representation and road segment representation, and the pairwise similarities are calculated using weighted edit distance and longest common subsequence method. A hierarchical method is applied for clustering and the result shows that some frequent patterns ae exists in the original data. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T11:42:41Z (GMT). No. of bitstreams: 1 U0001-1208202006082000.pdf: 5263552 bytes, checksum: a31aa5f613b57646c79993a39a48d351 (MD5) Previous issue date: 2020 | en |
dc.description.tableofcontents | 口試委員審定書 i 致謝 ii 摘要 iv ABSTRACT v 目錄 vi 圖目錄 viii 表目錄 x 第一章 緒論 1 1.1 宅配業現況 1 1.2 軌跡資料探勘(Trajectory Data Mining) 3 1.3 研究背景與動機 4 1.4 研究範圍與目的 5 1.5 研究方法與流程 5 第二章 文獻探討 7 2.1 軌跡資料處理(Trajectory Data Preprocessing) 7 2.1.1 停留點偵測(Stay Point Detection) 7 2.1.2 軌跡分割(Trajectory Segmentation) 9 2.1.3 軌跡壓縮(Trajectory Compression) 10 2.2 軌跡模式探勘(Trajectory Pattern Mining) 12 2.3 軌跡相似度(Trajectory Similarity) 14 2.4 小結 16 第三章 問題描述與研究方法 17 3.1 問題描述 17 3.2 資料處理 19 3.2.1 軌跡(Trajectory) 19 3.2.2 停留點偵測(Stay Point Detection) 20 3.2.3 軌跡分割(Trajectory Segmentation) 21 3.2.4 軌跡壓縮(Trajectory Compression) 21 3.3 軌跡表示法轉換 24 3.3.1 網格化表示(Grid-Based Representation) 25 3.3.2 路段表示(Road Segment Representation) 26 3.4 軌跡相似度 27 3.4.1 最長共同子序列(LCSS, Longest Common Subsequence) 28 3.4.2 編輯距離(Edit Distance) 31 3.5 分群方法 35 3.5.1 階層式分群 35 3.5.2 群集距離(Linkage) 36 3.5.3 輪廓係數法(Silhouette Coefficient Analysis) 36 第四章 實際案例分析 38 4.1 資料描述 38 4.1.1 數值分佈 39 4.1.2 配送區域 41 4.1.3 地理分佈 42 4.2 資料預處理 45 4.2.1 缺失值處理 45 4.2.2 變數處理 46 4.2.3 軌跡分割及壓縮 47 4.3 軌跡表示法轉換 48 4.3.1 網格化表示 48 4.3.2 路段表示 49 4.4 分群結果 50 4.4.1 輪廓係數 50 4.4.2 群集特徵 53 第五章 結論與未來研究展望 61 5.1 結論 61 5.2 未來研究展望 61 文獻參考 63 | |
dc.language.iso | zh-TW | |
dc.title | 以編輯距離相似度及分群方式進行軌跡模式探勘-以都市地區宅配車輛為例 | zh_TW |
dc.title | Trajectory Pattern Mining Using Edit Distance Similarity and Clustering-A Case Study of Urban Home Delivery Vehicle | en |
dc.type | Thesis | |
dc.date.schoolyear | 108-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 吳政翰(Cheng-Han Wu),范治民(Chih-min Fan) | |
dc.subject.keyword | GPS軌跡,軌跡模式探勘,軌跡分群,軌跡相似度,加權編輯距離,最長共同子序列,網格化表示,路段表示, | zh_TW |
dc.subject.keyword | GPS Trajectory,Trajectory Pattern Mining,Trajectory Clustering,Trajectory Similarity,Weighted Edit Distance,Longest Common Subsequence,LCSS,Grid-Based Representation,Road Segment Representation, | en |
dc.relation.page | 66 | |
dc.identifier.doi | 10.6342/NTU202003043 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2020-08-14 | |
dc.contributor.author-college | 工學院 | zh_TW |
dc.contributor.author-dept | 工業工程學研究所 | zh_TW |
顯示於系所單位: | 工業工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-1208202006082000.pdf 目前未授權公開取用 | 5.14 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。