臺灣博碩士論文加值系統

分類問題在資料處理的應用上是一個相當重要的議題，特別是 TSC 問題。
在TSC 問題中，計算兩個時間序列之間的距離是一個核心的議題。其中一種知
名的計算距離的方法就是 DTW ，它建立在動態規劃的基礎上。然而，DTW 的
時間複雜度是 O(n2)。但是當資料長度越大時，它就必須花更多時間來計算。為
了要克服過度花費時間的問題，DDTW 將DTW 結合了扭曲視窗。這一個方法透
過限制可能的答案進而減少了計算時間，因此DTWW的答案可能不會是最佳解。
在這篇論文中，我們提出了一種方法，透過由小到大的順序來展開可能的答案。
我們的方法不僅可以減少所需的計算時間，還可以得到最佳解。

The classification problem is a critical issue in data processing field, especially emph{time series classification} (TSC) problem. In the TSC problem, the calculation of the distance of two time series is the kernel issue.

One of the famous methods for the distance calculation is the emph{dynamic time warping} (DTW), based on the dynamic programming. However, the time complexity of DTW is $O(n^2)$. When the data size is large, it takes too much time to calculate. In order to overcome time consuming problem, emph{dynamic time warping with window} (DTWW) combines the warping window into DTW calculation. This method reduces the computation time by restricting the number of possible solutions, so the answer of DTWW may not be the optimal solution. In this thesis, we present a method that expands the possible solutions in the minimum first order. Our method not only reduces the required computation time, but also gets the optimal answer.

THESIS VERIFICATION FORM . . . . . . . . . . . . . . . . . . . . . . i
THESIS AUTHORIZATION FORM . . . . . . . . . . . . . . . . . . . . iii
ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
CHINESE ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
LIST OF SYMBOLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2. Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 The Time Series Classi cation Problem . . . . . . . . . . . . . . . . . 4
2.2 The Distance Measurements . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.1 Euclidean Distance . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 Dynamic Time Warping Distance . . . . . . . . . . . . . . . . 5
2.2.3 Dynamic Time Warping with Window . . . . . . . . . . . . . 7
2.2.4 Derivative Dynamic Time Warping . . . . . . . . . . . . . . . 8
2.3 Similarity with the Longest Common Subsequence . . . . . . . . . . 9
Chapter 3. Our Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 An Example for Illustrating Our Method . . . . . . . . . . . . . . . . 11
3.2 The Irreplaceable Property . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 The Minimum First Order . . . . . . . . . . . . . . . . . . . . . . . . 18
Chapter 4. Experimental Results . . . . . . . . . . . . . . . . . . . . . . 20
4.1 The Experimental Datasets . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 The Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3 Analysis of Experimental Results . . . . . . . . . . . . . . . . . . . . 38
Chapter 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

[1] A. Bagnall, J. Lines, A. Bostrom, J. Large, and E. Keogh, “The great time
series classification bake off: a review and experimental evaluation of recent
algorithmic advances,” Data Mining and Knowledge Discovery, Vol. 31, No. 3,
pp. 606–660, May 2016.
[2] A. Bailly, S. Malinowski, R. Tavenard, L. Chapel, and T. Guyet, “Dense bag-of-
temporal-sift-words for time series classification,” Proceedings of International
Workshop on Advanced Analysis and Learning on Temporal Data (AALTD),
Porto, Portugal, pp. 17–30, Springer, 2015.
[3] M. G. Baydogan, G. Runger, and E. Tuv, “A bag-of-features framework to
classify time series,” IEEE Transactions on Pattern Analysis and Machine In-
telligence, Vol. 35, No. 11, pp. 2796–2802, Nov. 2013.
[4] L. Bergroth, H. Hakonen, and T. Raita, “A survey of longest common subse-
quence algorithms,” Proceedings of the 7th International Symposium on String
Processing and Information Retrieval (SPIRE), Curuna, Spain, pp. 39–48,
IEEE, 2000.
[5] Q. Chen, G. Hu, F. Gu, and P. Xiang, “Learning optimal warping window size
of DTW for time series classification,” Proceedings of the 11th International
Conference on Information Science, Signal Processing and their Applications
(ISSPA), Montreal, Canada, pp. 1272–1277, IEEE, June 2012.
[6] R. Collobert and J. Weston, “A unified architecture for natural language pro-
cessing: Deep neural networks with multitask learning,” Proceedings of the
25th International Conference on Machine learning (ICML), Helsinki, Finland,
pp. 160–167, ACM, June 2008.
[7] P.-E. Danielsson, “Euclidean distance mapping,” Computer Graphics and Im-
age Processing, Vol. 14, No. 3, pp. 227–248, Nov. 1980.
[8] J. Dean and S. Ghemawat, “Mapreduce: simplified data processing on large
clusters,” Communications of the ACM, Vol. 51, No. 1, pp. 107–113, Jan. 2008.
[9] 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, No. 2, pp. 1542–1552, Aug. 2008.
[10] L. Feng, X. Zhao, Y. Liu, Y. Yao, and B. Jin, “A similarity measure of jump-
ing dynamic time warping,” Proceedings of the 7th International Conference
on Fuzzy Systems and Knowledge Discovery (FSKD), Vol. 4, Yantai, China,
pp. 1677–1681, IEEE, Sept. 2010.
[11] W.-C. Fu, E. Keogh, Y. Lau, C. A. Ratanamahatana, and C.-W. Wong, “Scal-
ing and time warping in time series querying,” The International Journal on
Very Large Data Bases (VLDB), Vol. 17, No. 4, pp. 899–921, July 2008.
[12] 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, July 2014.
[13] D. S. Hirschberg, “Algorithms for the longest common subsequence problem,”
Journal of the ACM (JACM), Vol. 24, No. 4, pp. 664–675, 1977.
[14] 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.
[15] 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, Sept. 2011.
[16] 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
(ISMW), Beijing, China, pp. 256–263, IEEE, Mar. 2007.
[17] H. Kaya and Ş. Gündüz-Öğüdücü, “A distance based time series classification
framework,” Information Systems, Vol. 51, pp. 27–42, July 2015.
[18] E. Keogh and M. Pazzani, “Derivative dynamic time warping,” Proceedings of
the 1st SIAM International Conference on Data Mining (SDM), Chicago, USA,
pp. 1–11, SIAM, 2001.
[19] 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.
[20] 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, 2018.
[21] 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.
[22] M. Luczak, “Univariate and multivariate time series classification with paramet-
ric integral dynamic time warping,” Journal of Intelligent and Fuzzy Systems,
Vol. 33, No. 4, pp. 2403–2413, Sept. 2017.
[23] 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, Feb. 2018.
[24] M. M. Najafabadi, F. Villanustre, T. M. Khoshgoftaar, N. Seliya, R. Wald,
and E. Muharemagic, “Deep learning applications and challenges in big data
analytics,” Journal of Big Data, Vol. 2, No. 1, p. 1, Feb. 2015.
[25] V. Niennattrakul and C. A. Ratanamahatana, “Learning DTW global con-
straint for time series classification,” Computing Research Repository (CoRR),
Vol. abs/0903.0041, 2009.
[26] S. T. Parthasaradhi, R. Derakhshani, L. A. Hornak, and S. A. 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, July 2005.
[27] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel,
M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al., “Scikit-learn: Ma-
chine learning in python,” Journal of Machine Learning Research, Vol. 12,
No. 10, pp. 2825–2830, 2011.
[28] F. Petitjean, A. Ketterlin, and P. Gançarski, “A global averaging method for
dynamic time warping, with applications to clustering,” Pattern Recognition,
Vol. 44, No. 3, pp. 678–693, Mar. 2011.
[29] C. E. Rasmussen, “Gaussian processes in machine learning,” Advanced Lectures
on Machine Learning, pp. 63–71, Berlin, Heidelberg: Springer, Feb. 2004.
[30] C. A. Ratanamahatana and E. Keogh, “Making time-series classification more
accurate using learned constraints,” Proceedings of the 4th SIAM International
Conference on Data Mining, Florida, USA, pp. 11–22, SIAM, 2004.
[31] 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.
[32] S. Salvador and P. Chan, “Toward accurate dynamic time warping in linear
time and space,” Intelligent Data Analysis, Vol. 11, No. 5, pp. 561–580, Oct.
2007.
[33] P. Schäfer, “Scalable time series classification,” Data Mining and Knowledge
Discovery, Vol. 30, No. 5, pp. 1273–1298, Sept. 2016.
[34] 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 (CODS), New york, USA, p. 3, ACM, Mar.
2016.
[35] A. Sharabiani, H. Darabi, A. Rezaei, S. Harford, H. Johnson, and F. Karim,
“Efficient classification of long time series by 3-d dynamic time warping,” IEEE
Transactions on Systems, Man, and Cybernetics: Systems, Vol. 47, No. 10,
pp. 2688–2703, Oct. 2017.
[36] S. J. Shyu and C.-Y. Tsai, “Finding the longest common subsequence for multi-
ple biological sequences by ant colony optimization,” Computers & Operations
Research, Vol. 36, No. 1, pp. 73–91, Jan. 2009.
[37] A. Stefan, V. Athitsos, and G. Das, “The move-split-merge metric for time
series,” IEEE transactions on Knowledge and Data Engineering, Vol. 25, No. 6,
pp. 1425–1438, June 2013.
[38] 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.
[39] X. Xi, E. Keogh, C. Shelton, L. Wei, and C. A. Ratanamahatana, “Fast time se-
ries classification using numerosity reduction,” Proceedings of the 23rd Interna-
tional Conference on Machine Learning (IMCL), Pennsylvania, USA, pp. 1033–
1040, ACM, June 2006.
[40] 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.
[41] J. Zhao and L. Itti, “shapeDTW: shape dynamic time warping,” Pattern Recog-
nition, Vol. 74, pp. 171–184, Feb. 2018.