LEEANDSEO
7of 19
between time series classification problems and traditional classification problems is that the attributes are arranged in order and input features may be correlated. The 1-NN is a popular classifier for the time series classification as its perfor- mance can compete with the most complex classifiers. 6 When a new observed time series instance comes out, the 1-NN classifier looks for the instance in the training dataset which has the shortest distance with the new instance and predicts the class of the new instance as the class label of the closest instance. A distance measure such as the Euclidean distance is used to compare two-time series instances. For a one-dimensional time series data, the Euclidean distance between two-time series instances w i and w k is measured by D ED ( w i , w k ) = √√ √ m ∑ t = 1 ( w it − w kt ) 2 , (6) where w i and w k are window instances with t = 1, … , m measurements to be compared each other. The other renowned distance measure for time series data is DTW, which is the method to find the optimal alignment between two time-dependent sequences. It has been widely used in the field of pattern recognition and broadly tested on the benchmark time series data. DTW is originally designed to compare different speech patterns for the purpose of automatic speech recognition to solve the problem of distortions in the time axis. 35 It makes a time series stretched and realigned to better match the other time series. 36 To find the DTW distance, the matrix M is built where the ( t , t ′ )th element of M is d ( w it , w kt ′ ) = ( w it − w kt ′ ) 2 . Then a warping path is defined as the monotonically increasing sequences of indices p = {(0,0), … , ( t , t ′ ), … , ( m , m )}. The DTW distance can be found by the warping path which has the minimum cumulative distance between two sequences.
√√ √
H ∑ h = 1
D DTW ( w i , w k ) = min p
M h ,
(7)
where H is the length of the warping path, M h is the matrix element corresponding to the h th element of a warping path p . 37 Figure 3 depicts how Euclidean matching and DTW matching compare similarities between two-time series instances. In brief, Euclidean distance measures the distance between the two waves regardless of the shapes, while the DTW measures the distance by taking into account the shapes of two sequences. However, due to its computational complexity of DTW, the distance measurement with the DTW may not be suitable to be applied for the real-time sensor streaming data in which it is required to find the nearest neighbor instance quickly.
FIGURE 3 1-NN comparison between Euclidean and DTW matching. 1-NN, 1-nearest neighbor; DTW, dynamic time warping
Made with FlippingBook - Online catalogs