Innovative Approach for Enhancing Time-Series Classification Accuracy
Learn how a novel framework leverages learned constraints to improve the accuracy of Dynamic Time Warping (DTW) for time-series classification, leading to significant gains in efficiency and precision across diverse datasets. Explore the advancements made in DTW performance and the integration of constraints to optimize classification results.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Making Time-series Classification more accurate Using Learned Constraints Chotirat Ann Ratanamahatana Eamonn Keogh Society for Industry and Applied Mathematics(SIAM) International Conference On Data Mining, 2004 Presenter : Shu-Kai, Hung Date : 2016/10/5
Abstract It has long been known that Dynamic Time Warping (DTW) is superior to Euclidean distance for classification and clustering of time series. However, until lately, most research has utilized Euclidean distance because it is more efficiently calculated. A recently introduced technique that greatly mitigates DTWs demanding CPU time has sparked a flurry of research activity. However, the technique and its many extensions still only allow DTW to be applied to moderately large datasets. In addition, almost all of the research on DTW has focused exclusively on speeding up its calculation. there has been little work done on improving its accuracy. In this work, we target the accuracy aspect of DTW performance and introduce a new framework that learns arbitrary constraints on the warping path of the DTW calculation. Apart from improving the accuracy of classification, our technique as a side effect speeds up DTW by a wide margin as well. We show the utility of our approach on datasets from diverse domains and demonstrate significant gains in accuracy and efficiency.
Dynamic Time Warping Dynamic Time Warping Q =?1?2 ?? ?? ex : Q = 1 3 2 4 5 0 C = ?1?2 ?? ?? ex : C = 1 2 2 3 4 ? ??,?? = (?? ??)2 The ?? ?? ? is defined as ??= (?,?)? => 1 2 2 3 4 1 0 1 1 4 9 3 4 1 1 0 1 2 1 0 0 1 4 4 9 4 4 1 0 5 16 9 1 4 1 0 4 1 1 0 1
DTW condition Boundary conditions : The path must start in ?1= (1,1) and end in ??= (m,n) Continuity condition : both i and j indexes can only increase by 0 or 1 on each step along the path. Monotonic condition : both i and j indexes either stay the same or increase. Slope constraint condition :The path should not be too steep or too shallow. The condition is expressed as a ratio a/b, where b is the number of steps in the x direction and a is the number in the y direction. Adjustment Window condition : The distance that the path is allowed to wander is limited to a window (or band ) of size r, directly above and to the right of the diagonal.
General model of global constraints. General model of global constraints. global constraint as constraining the indices of the warping path ??= (?,?)?,such that j ?? i j+??, where ??is a term defining the allowed range of warping, for a given point in a sequence where ??is the height above the diagonal in the y direction, as well as the width to the right of the diagonal in the x direction.
Sakoe-Chiba Band Itakura Parallelogram
Ratanamahatana Ratanamahatana- -Keogh Band (R Keogh Band (R- -K Band). K Band). define any arbitrary global constraint with the vector R. Euclidean distance can be defined in terms of ??= 0; 1 i m Are we better off with wider band? (Sakoe-Chiba Band) Need to learn its wider(learn its function)
lower bounding distance measure lower bounding distance measure LB_Keogh(Under Sakoe-Chiba Band) LB_Keogh(Q,C) DTW(Q,C)
Learning multiple Learning multiple Ratanamahatana for classification for classification initial state Forward Search: ??= 0 Backward Search: ??= m heuristic function Accuracy metric Distance metric operators If improvement is made, continue working on the same piece of envelope Ratanamahatana- -Keogh bands Keogh bands If no improvement is made, first the modification to the envelope needs to be undone, then redo the modification on the left half (start:mid-1) and the right half (mid:end) individually.
Forward Search terminal test: Forward Search: The search is complete when one of the following is true: No improvement can be made. The envelope s width reaches m When a condition end- start+1 threshold is met for all the pieces of the envelope Left half modification Right half modification
Local maximum Local maximum Forward search with Accuracy metric. Forward search with Distance metric. Backward search with Accuracy metric. Backward search with Distance metric.
