# 臺灣博碩士論文加值系統

(44.220.44.148) 您好！臺灣時間：2024/06/18 13:59

:::

### 詳目顯示

:

• 被引用:0
• 點閱:124
• 評分:
• 下載:13
• 書目收藏:0
 時間序列是日常生活中很常用的資料，例如股票指數、匯率、心電圖等等。給定一條時間序列，時間序列分類問題是在一堆已分類好的類別中指派一個類別給它，解決時間序列分類問題的核心是計算兩條時間序列的距離。計算距離最常使用的方法之一是動態時間校正 (DTW)，它的時間為O(n^2)，n代表給定的時間序列的長度，O(n^2)時間的執行效率不夠好，特別是對於長時間序列。為了減少DTW的執行時間，Chen等人在2018年提出了最小優先方法 (MFM) 來加快DTW的計算速度，並仍然維持它原來的準確度。雖然MFM在大多數的情況下都很有效率，但在某些資料集中，MFM比原始的DTW更差，換句話說，MFM適用於某些資料集，而原始的DTW方法適用於其他資料集。因此，在本論文中，我們訓練了兩個量化指標，包含變化量的標準差和波的振盪來自動判斷哪些資料集適合使用MFM，而這種適應性預測的準確度非常高。除此之外，我們還將MFM應用至其他DTW的相關方法，包含有限制範圍的DTW和用於稀疏時間序列的AWarp。
 The time series information is commonly used in daily life, such as stock indices, exchange rates, and electrocardiograms. Given a target time series, the time series classification (TSC) problem is to assign it a class in a set of classified classes. The essential step for solving the TSC problem is the distance calculation of two time series. One of the most common ways for calculating the distance is dynamic time warping (DTW), with O(n^2) time, where n denotes the length of the given time series. The execution efficiency of O(n^2) time is not good enough, especially for long time series. In order to practically reduce the execution time of DTW, Chen et al. proposed the minimum first method (MFM) in 2018 to speed up the calculation of DTW and to still maintain its original classification accuracy. MFM is effective in most cases, but MFM may be worse than the original DTW in some other datasets. In other words, MFM is suitable for some datasets and the original DTW method is suitable for other datasets. This thesis trains two quantitative indicators, including standard deviation of variations and wave oscillation, to automatically determine which datasets are suitable for using MFM. The accuracy of such suitability prediction is very high. Furthermore, we also apply MFM to other DTW related methods, including DTW with band constraints and AWarp: warping distance for sparse time series.
 THESIS VERIFICATION FORM . . . . . . . . . . . . . . . . . . . . . . iTHESIS AUTHORIZATION FORM . . . . . . . . . . . . . . . . . . . . iiiACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiCHINESE ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vLIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixLIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviLIST OF SYMBOLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxivChapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 The Time Series Classi cation Problem . . . . . . . . . . . . . . . . . 42.2 The Euclidean Distance . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 Dynamic Time Warping . . . . . . . . . . . . . . . . . . . . . . . . . 52.4 Dynamic Time Warping with Band Constraints . . . . . . . . . . . . 72.4.1 The Sakoe-Chiba Band . . . . . . . . . . . . . . . . . . . . . . 72.4.2 The Itakura Parallelogram Band . . . . . . . . . . . . . . . . 72.5 AWarp: Warping Distance for Sparse Time Series . . . . . . . . . . . 92.6 The Minimum First Method for Dynamic Time Warping . . . . . . . 102.7 UCR Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12Chapter 3. Our Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.1 Analysis of the Minimum First Method . . . . . . . . . . . . . . . . . 143.1.1 Observations of Time Series . . . . . . . . . . . . . . . . . . . 153.1.2 The Standard Deviation of the Variation Sequence . . . . . . 193.1.3 The Oscillation Indicator . . . . . . . . . . . . . . . . . . . . . 193.1.4 Combined Indicators . . . . . . . . . . . . . . . . . . . . . . . 203.2 Applications of the Minimum First Method . . . . . . . . . . . . . . . 213.2.1 The Sakoe-Chiba Band with the Minimum First Method . . . 243.2.2 The Itakura Parallelogram Band with the Minimum First Method 273.2.3 AWarp with the Minimum First Method . . . . . . . . . . . . 28Chapter 4. Experimental Results . . . . . . . . . . . . . . . . . . . . . . 344.1 Sparse Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.2 Experimental Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 354.2.1 The Procedure of UCR Datasets . . . . . . . . . . . . . . . . . 354.2.2 The Procedure of Sparse Datasets . . . . . . . . . . . . . . . . 364.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.3.1 Results of UCR Datasets . . . . . . . . . . . . . . . . . . . . . 374.3.2 Results of Sparse Datasets . . . . . . . . . . . . . . . . . . . . 48Chapter 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54AppendixesA. UCR Datasets Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 59A.1 Original UCR Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . 59A.2 Var Std and Oscillations for Sampled UCR Datasets . . . . . . . . . . 62A.3 Classi cation Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . 65A.4 Time and Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68A.4.1 DTW & DTW-M . . . . . . . . . . . . . . . . . . . . . . . . . 68A.4.2 DTW- & DTW-M . . . . . . . . . . . . . . . . . . . . . . . 73A.4.3 SCBand & SCBand-M . . . . . . . . . . . . . . . . . . . . . . 78A.4.4 SCBand- & SCBand-M . . . . . . . . . . . . . . . . . . . . 83A.4.5 ITABand & ITABand-M . . . . . . . . . . . . . . . . . . . . . 88A.4.6 ITABand- & ITABand-M . . . . . . . . . . . . . . . . . . . 93A.5 Training Indicators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98A.6 Average and Standard Deviation of Ten Execution Times . . . . . . . 102B. Sparse Datasets Results . . . . . . . . . . . . . . . . . . . . . . . . . . 129B.1 Length 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129B.2 Length 200 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130B.3 Length 500 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131B.4 Length 1000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
 [1] B. B. Ali, Y. Masmoudi, and S. Dhouib, "Accurate and fast dynamic timewarping approximation using upper bounds," Proceedings of the 38th Inter-national Conference on Telecommunications and Signal Processing, Prague,Czech, pp. 1-6, July 2015.[2] J. P. Bachmann and J.-C. Freytag, "Dynamic time warping and the (windowed)dog-keeper distance," Proceedings of the 10th International Conference on Sim-ilarity Search and Applications, Munich, Germany, pp. 127-140, Oct. 2017.[3] H. Breu, D. K. Joseph Gil, and M. Werman, "Linear time Euclidean distancetransform algorithms," IEEE Transactions on Pattern Analysis and MachineIntelligence, Vol. 17, No. 5, pp. 529-533, May 1995.[4] P. J. Brockwell and R. A. Davis, Introduction to Time Series and Forecasting.Heidelberg, Germany: Springer, 2016.[5] B.-X. Chen, K.-T. Tseng, and C.-B. Yang, "A minimum-first algorithm fordynamic time warping on time series," Proceedings of the 23rd InternationalComputer Symposium , Yunlin, Taiwan, Dec. 2018. Also in New Trends inComputer Technologies and Applications, Communications in Computer andInformation Science, Vol. 1013, pp. 449-456, Singapore: Springer.[6] Y. Chen, E. Keogh, B. Hu, N. Begum, A. Bagnall, A. Mueen, and G. Batista,The UCR time series classification archive." https://www.cs.ucr.edu/~eamonn/time_series_data/, 2015.[7] P.-E. Danielsson, "Euclidean distance mapping," Computer Graphics and Im-age Processing, Vol. 14, No. 3, pp. 227-248, Nov. 1980.[8] H. A. Dau, E. Keogh, K. Kamgar, C.-C. M. Yeh, Y. Zhu, S. Gharghabi, C. A.Ratanamahatana, Y. Chen, B. Hu, N. Begum, A. Bagnall, A. Mueen, andG. Batista, "The UCR time series classification archive." https://www.cs.ucr.edu/~eamonn/time_series_data_2018/, 2018.[9] R. Dechter and J. Pearl, "Generalized best-first search strategies and the opti-mality of A*," Journal of the ACM, Vol. 32, No. 3, pp. 505-536, July 1985.[10] H. Ding, G. Trajcevski, P. Scheuermann, X. Wang, and E. Keogh, "Queryingand mining of time series data: experimental comparison of representationsand distance measures," Proceedings of the Very Large Data Bases Endowment,Vol. 1, Auckland, New Zealand, pp. 1542-1552, 2008.[11] S. A. Dudani, "The distance-weighted k-nearest-neighbor rule," IEEE Trans-actions on Systems, Man, and Cybernetics, Vol. SMC-6, No. 4, pp. 325-327,Apr. 1976.[12] L. Feng, X. Zhao, Y. Liu, Y. Yao, and B. Jin, "A similarity measure of jumpingdynamic time warping," Proceedings of the 7th International Conference onFuzzy Systems and Knowledge Discovery, Yantai, China, pp. 1677-1681, 2010.[13] K. Fukunaga and P. Narendra, "A branch and bound algorithm for comput-ing k-nearest neighbors," IEEE Transactions on Computers, Vol. 24, No. 7,pp. 750-753, July 1975.[14] L. Gupta, D. L. Molfese, R. Tammana, and P. Simos, "Nonlinear alignment andaveraging for estimating the evoked potential," IEEE Transactions on Biomed-ical Engineering, Vol. 43, No. 4, pp. 348-356, Apr. 1996.[15] J. Hills, J. Lines, E. Baranauskas, J. Mapp, and A. Bagnall, "Classification oftime series by shapelet transformation," Data Mining and Knowledge Discovery,Vol. 28, No. 4, pp. 851-881, 2014.[16] C.-J. Hsu, K.-S. Huang, C.-B. Yang, and Y.-P. Guo, "Flexible dynamic timewarping for time series classification," Proceedings of the International Con-ference on Computational Science, Vol. 51, Reykjavk, Iceland, pp. 2838-2842,June 2015.[17] F. Itakura, "Minimum prediction residual principle applied to speech recogni-tion," IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. 23,No. 1, pp. 67-72, Feb. 1975.[18] Y.-S. Jeong, M. K. Jeong, and O. A. Omitaomu, "Weighted dynamic time warp-ing for time series classification," Pattern Recognition, Vol. 44, No. 9, pp. 2231-2240, 2011.[19] S. B. Junior, R. C. Guido, S.-H. Chen, L. S. Vieira, and F. L. Sanchez, "Im-proved dynamic time warping based on the discrete wavelet transform," Pro-ceedings of the 9th IEEE International Symposium on Multimedia Workshops,Beijing, China, pp. 256-263, Dec. 2007.[20] E. Keogh and C. A. Ratanamahatana, "Exact indexing of dynamic time warp-ing," Knowledge and Information Systems, Vol. 7, No. 3, pp. 358-386, Mar.2005.[21] E. J. Keogh and M. J. Pazzani, "Derivative dynamic time warping," Proceedingsof the 1st SIAM International Conference on Data Mining, Chicago, USA,pp. 1-11, Apr. 2001.[22] M. Lee, S. Lee, M.-J. Choi, Y.-S. Moon, and H.-S. Lim, "HybridFTW: Hy-brid computation of dynamic time warping distances," IEEE Access, Vol. 6,pp. 2085-2096, 2017.[23] H. Li and L. Yang, "Accurate and fast dynamic time warping," Proceedings ofthe 9th International Conference on Advanced Data Mining and Applications,Hangzhou, China, pp. 133-144, Dec. 2013.[24] J. Lines and A. Bagnall, "Time series classification with ensembles of elasticdistance measures," Data Mining and Knowledge Discovery, Vol. 29, No. 3,pp. 565-592, May 2015.[25] R. Ma, A. Ahmadzadeh, S. F. Boubrahimi, and R. Angryk, "Segmentation oftime series in improving dynamic time warping," Proceedings of 2018 IEEEInternational Conference on Big Data, Seattle, WA, USA, pp. 3756-3761, Dec.2018.[26] M. Morel, C. Achard, R. Kulpa, and S. Dubuisson, "Time-series averagingusing constrained dynamic time warping with tolerance," Pattern Recognition,Vol. 74, pp. 77-89, 2018.[27] A. Mueen, N. Chavoshi, N. Abu-El-Rub, H. Hamooni, and A. Minnich,AWarp: Fast warping distance for sparse time series," Proceedings of the 16thInternational Conference on Data Mining, Barcelona, Spain, pp. 350-359, Dec.2016.[28] A. Mueen, N. Chavoshi, N. Abu-El-Rub, H. Hamooni, and A. Minnich,AWarp: Fast warping distance for sparse time series." https://www.cs.unm.edu/~mueen/Projects/AWarp/, 2016.[29] M. Muller, "Dynamic time warping," Information Retrieval for Music and Mo-tion, pp. 69-84, 2007.[30] V. Niennattrakul and C. A. Ratanamahatana, "Learning DTW global con-straint for time series classification." arXiv:0903.0041, 2009.[31] S. T. Parthasaradhi, R. Derakhshani, L. A. Hornak, and S. Schuckers, "Time-series detection of perspiration as a liveness test in fingerprint devices," IEEETransactions on Systems, Man, and Cybernetics, Part C (Applications andReviews), Vol. 35, No. 3, pp. 335-343, Aug. 2005.[32] C. A. Ratanamahatana and E. J. Keogh, "Making time-series classificationmore accurate using learned constraints," Proceedings of the 4th SIAM Inter-national Conference on Data Mining, Orlando, Florida, USA, pp. 11-22, Apr.2004.[33] H. Sakoe and S. Chiba, "Dynamic programming algorithm optimization forspoken word recognition," IEEE Transactions on Acoustics, Speech, and SignalProcessing, Vol. 26, No. 1, pp. 43-49, Feb. 1978.[34] Y. Sakurai, M. Yoshikawa, and C. Faloutsos, "FTW: Fast similarity searchunder the time warping distance," Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Baltimore,Maryland, USA, pp. 326-337, 2005.[35] S. Salvador and P. Chan, "FastDTW: Toward accurate dynamic time warpingin linear time and space," Intelligent Data Analysis, Vol. 11, No. 5, pp. 561-580,Oct. 2007.[36] M. Shah, J. Grabocka, N. Schilling, M. Wistuba, and L. Schmidt-Thieme,Learning DTW-shapelets for time-series classification," Proceedings of the 3rdIKDD Conference on Data Science, Pune, India, pp. 3:1-3:8, Mar. 2016.[37] D. F. Silva and G. E. A. P. A. Batista, "Speeding up all-pairwise dynamictime warping matrix calculation," Proceedings of the 2016 SIAM InternationalConference on Data Mining, Miami, Florida, USA, pp. 837-845, 2016.[38] D. F. Silva, G. E. A. P. A. Batista, and E. Keogh, "Prefix and suffix invariantdynamic time warping," Proceedings of the 16th International Conference onData Mining, Barcelona, Spain, pp. 1209-1214, 2016.[39] Y.Wan, X.-L. Chen, and Y. Shi, "Adaptive cost dynamic time warping distancein time series analysis for classification," Journal of Computational and AppliedMathematics, Vol. 319, pp. 514-520, Aug. 2017.[40] H. Yin, S. Yang, S. Ma, F. Liu, and Z. Chen, "A novel parallel scheme for fastsimilarity search in large time series," China Communications, Vol. 12, No. 2,pp. 129-140, 2015.[41] X. Zhang, J. Liu, Y. Du, and T. Lv, "A novel clustering method on time seriesdata," Expert Systems with Applications, Vol. 38, No. 9, pp. 11891-11900, Sept.2011.[42] Z. Zhang, R. Tavenard, A. Bailly, X. Tang, P. Tang, and T. Corpetti, "Dy-namic time warping under limited warping path length," Information Sciences,Vol. 393, pp. 91-107, July 2017.[43] J. Zhao and L. Itti, "shapeDTW: shape dynamic time warping," Pattern Recog-nition, Vol. 74, pp. 171-184, 2018.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 應用感知特徵點法於財務時間序列的群集分析 2 動態時軸校正法應用於語音辨識之研究 3 基於距離之時間序列分析與模板匹配應用於人體下肢動作識別 4 藉由股價關聯圖探勘提升股票趨勢預測模型 5 使用差異空間之時間序列分類演算法 6 運用時序性資料分析於PM2.5 7 快速且精準之時間序列分群演算法-透過精準群心選擇 8 動態時軸校正法下限制的研究-以語音辨識為例 9 動態時軸校正法路徑限制的研究-以語音辨識為例

 無相關期刊

 1 最長波動子序列問題之演算法 2 基於卷積神經網路的台灣股市之投資組合交易 3 最長共同回文子序列問題之對角線演算法 4 移動環境中頻率指標調變之低複雜度接收機設計 5 銀行業之競爭程度與金融傳染效應:以臺灣國內銀行為例 6 併網與孤島調變控制之三階層T型逆變器 7 虛擬實境與遊戲機制對顧客體驗與滿意度的影響 -沉浸理論的觀點 8 在5G異構網路下考量流量及D2D轉傳之小細胞基地台睡眠策略 9 台灣東南部21.75°N斷面黑潮水、無機碳及營養鹽通量之時空變化 10 被迫成為「好士兵」一定不好嗎？探討員工每日強制性公民行為對後續自發性/強迫性公民行為的影響：自我耗竭與組織自尊的中介歷程、及外向性特質與情緒調節技能的干擾角色 11 情緒勞動如何影響服務績效？ 工作倦怠的中介效果與員工心理資本的調節效果 12 美學革命！競選廣告注入美學對選民之候選人態度與投票意願之影響 13 當高價產品遇上了可愛！以基模一致性理論探討反差萌行銷 14 美麗食物的雙面刃：食物美學對於療癒感與感知價格及購買意願之影響 15 潘朵拉的盒子: 罪惡訴求廣告對誘惑感知和消費者態度反應之影響

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室