臺灣博碩士論文加值系統

時間序列是日常生活中很常用的資料，例如股票指數、匯率、心電圖等等。給定一條時間序列，時間序列分類問題是在一堆已分類好的類別中指派一個類別給它，解決時間序列分類問題的核心是計算兩條時間序列的距離。計算距離最常使用的方法之一是動態時間校正 (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 . . . . . . . . . . . . . . . . . . . . . . i
THESIS AUTHORIZATION FORM . . . . . . . . . . . . . . . . . . . . iii
ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
CHINESE ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi
LIST OF SYMBOLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiv
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 The Time Series Classi cation Problem . . . . . . . . . . . . . . . . . 4
2.2 The Euclidean Distance . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Dynamic Time Warping . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Dynamic Time Warping with Band Constraints . . . . . . . . . . . . 7
2.4.1 The Sakoe-Chiba Band . . . . . . . . . . . . . . . . . . . . . . 7
2.4.2 The Itakura Parallelogram Band . . . . . . . . . . . . . . . . 7
2.5 AWarp: Warping Distance for Sparse Time Series . . . . . . . . . . . 9
2.6 The Minimum First Method for Dynamic Time Warping . . . . . . . 10
2.7 UCR Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Chapter 3. Our Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1 Analysis of the Minimum First Method . . . . . . . . . . . . . . . . . 14
3.1.1 Observations of Time Series . . . . . . . . . . . . . . . . . . . 15
3.1.2 The Standard Deviation of the Variation Sequence . . . . . . 19
3.1.3 The Oscillation Indicator . . . . . . . . . . . . . . . . . . . . . 19
3.1.4 Combined Indicators . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Applications of the Minimum First Method . . . . . . . . . . . . . . . 21
3.2.1 The Sakoe-Chiba Band with the Minimum First Method . . . 24
3.2.2 The Itakura Parallelogram Band with the Minimum First Method 27
3.2.3 AWarp with the Minimum First Method . . . . . . . . . . . . 28
Chapter 4. Experimental Results . . . . . . . . . . . . . . . . . . . . . . 34
4.1 Sparse Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 Experimental Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2.1 The Procedure of UCR Datasets . . . . . . . . . . . . . . . . . 35
4.2.2 The Procedure of Sparse Datasets . . . . . . . . . . . . . . . . 36
4.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3.1 Results of UCR Datasets . . . . . . . . . . . . . . . . . . . . . 37
4.3.2 Results of Sparse Datasets . . . . . . . . . . . . . . . . . . . . 48
Chapter 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Appendixes
A. UCR Datasets Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
A.1 Original UCR Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . 59
A.2 Var Std and Oscillations for Sampled UCR Datasets . . . . . . . . . . 62
A.3 Classi cation Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . 65
A.4 Time and Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
A.4.1 DTW & DTW-M . . . . . . . . . . . . . . . . . . . . . . . . . 68
A.4.2 DTW- & DTW-M . . . . . . . . . . . . . . . . . . . . . . . 73
A.4.3 SCBand & SCBand-M . . . . . . . . . . . . . . . . . . . . . . 78
A.4.4 SCBand- & SCBand-M . . . . . . . . . . . . . . . . . . . . 83
A.4.5 ITABand & ITABand-M . . . . . . . . . . . . . . . . . . . . . 88
A.4.6 ITABand- & ITABand-M . . . . . . . . . . . . . . . . . . . 93
A.5 Training Indicators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
A.6 Average and Standard Deviation of Ten Execution Times . . . . . . . 102
B. Sparse Datasets Results . . . . . . . . . . . . . . . . . . . . . . . . . . 129
B.1 Length 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
B.2 Length 200 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
B.3 Length 500 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
B.4 Length 1000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

[1] B. B. Ali, Y. Masmoudi, and S. Dhouib, "Accurate and fast dynamic time
warping 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 distance
transform algorithms," IEEE Transactions on Pattern Analysis and Machine
Intelligence, 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 for
dynamic time warping on time series," Proceedings of the 23rd International
Computer Symposium , Yunlin, Taiwan, Dec. 2018. Also in New Trends in
Computer Technologies and Applications, Communications in Computer and
Information 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, and
G. 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, "Querying
and mining of time series data: experimental comparison of representations
and 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 jumping
dynamic time warping," Proceedings of the 7th International Conference on
Fuzzy 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 and
averaging 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 of
time 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 time
warping 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," Proceedings
of 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 of
the 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 elastic
distance 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 of
time series in improving dynamic time warping," Proceedings of 2018 IEEE
International Conference on Big Data, Seattle, WA, USA, pp. 3756-3761, Dec.
2018.
[26] M. Morel, C. Achard, R. Kulpa, and S. Dubuisson, "Time-series averaging
using 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 16th
International 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," IEEE
Transactions on Systems, Man, and Cybernetics, Part C (Applications and
Reviews), Vol. 35, No. 3, pp. 335-343, Aug. 2005.
[32] C. A. Ratanamahatana and E. J. Keogh, "Making time-series classification
more 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 for
spoken word recognition," IEEE Transactions on Acoustics, Speech, and Signal
Processing, Vol. 26, No. 1, pp. 43-49, Feb. 1978.
[34] Y. Sakurai, M. Yoshikawa, and C. Faloutsos, "FTW: Fast similarity search
under 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 warping
in 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 3rd
IKDD 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 dynamic
time warping matrix calculation," Proceedings of the 2016 SIAM International
Conference 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 invariant
dynamic time warping," Proceedings of the 16th International Conference on
Data Mining, Barcelona, Spain, pp. 1209-1214, 2016.
[39] Y.Wan, X.-L. Chen, and Y. Shi, "Adaptive cost dynamic time warping distance
in time series analysis for classification," Journal of Computational and Applied
Mathematics, Vol. 319, pp. 514-520, Aug. 2017.
[40] H. Yin, S. Yang, S. Ma, F. Liu, and Z. Chen, "A novel parallel scheme for fast
similarity 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 series
data," 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.