Discovery of Ill–Known Motifs in Time Series Data (Technologien für die intelligente Automation)

This book includes a novel motif discovery for time series, KITE ( ill-Known motIf discovery in Time sE ries data ), to identify ill-known motifs transformed by affine mappings such as translation, uniform scaling, reflection, stretch, and squeeze mappings. Additionally, such motifs may be covered with noise or have variable lengths. Besides KITE’s contribution to motif discovery, new avenues for the signal and image processing domains are explored and created. The core of KITE is an invariant representation method called Analytic Complex Quad Tree Wavelet Packet transform (ACQTWP). This wavelet transform applies to motif discovery as well as to several signal and image processing tasks. The efficiency of KITE is demonstrated with data sets from various domains and compared with state-of-the-art algorithms, where KITE yields the best outcomes. Abstract Kurzfassung Acknowledgement Contents Nomenclature 1 Introduction 1.1 Motivation 1.2 Goals of the Thesis 1.3 Scope of the Thesis 1.4 Thesis’ Outline 2 Preliminaries 2.1 Time Series Signals 2.2 Distance and Similarity Measure 2.3 Time Series Motif 2.4 Wavelet Transformations 2.4.1 Dual Tree Complex Wavelet Transform (DTCWT) 2.4.1.1 Limitations and Deficiencies 3 General Principles of Time Series Motif Discovery 3.1 Time Series Pre-Processing 3.2 Time Series Representation 3.2.1 Invariant Transformations 3.3 Time Series Distance and Similarity Measures 3.4 Summary 4 State of the Art in Time Series Motif Discovery 4.1 Motif Discovery Algorithms 4.1.1 Time Complexity 4.1.2 Detecting Ill-Known Motifs 4.2 Research Gaps 4.3 Summary 5 Distortion-Invariant Motif Discovery 5.1 KITE Architecture 5.2 Signal Pre-Processing for Motif Discovery 5.2.1 Motif Length Definition 5.3 Invariant Time Series Representation 5.3.1 Analytic Complex Quad Tree Wavelet Packet Transform (ACQTWP) 5.3.1.1 Inverse Analytic Complex Quad Tree Wavelet Packet Transform (IACQTWP) 5.3.1.2 Properties and Characteristics 5.3.1.3 Selection of the Best Basis 5.4 Feature Extraction from Variable Scales 5.5 Threshold Determination for Similarity Detection 5.6 Significant Motif Discovery 5.6.1 Excluding Misleading Motifs 5.6.2 Representative Motifs 5.7 Time Complexity Analysis 5.8 Summary 6 Evaluation 6.1 Validation Principles 6.1.1 Feature Selection 6.1.2 Quality Measures 6.2 Design of the Experiments 6.2.1 Test Cases 6.2.1.1 Synthetic Data 6.2.1.2 Real-World Data 6.3 Detection of Equal-Length Motifs 6.3.1 Equal-Length Motif Discovery on Synthesis Data 6.3.2 Equal-Length Motif Discovery on Real-World Data 6.3.3 Equal-Length Motif Discovery Summary 6.4 Detection of Variable-Length Motifs 6.4.1 Variable-Length Motif Discovery on Synthesis Data 6.4.2 Variable-Length Motif Discovery on Real-World Data 6.4.3 Variable-Length Motif Discovery Summary 6.5 KITE Robustness Toward Noise 6.6 Scalability Experiments 6.7 Case Studies 6.7.1 Anomaly Detection via Time Series Motif Discovery 6.8 Summary 7 Conclusion and Outlook 7.1 Conclusion and Contributions 7.2 Perspectives and Future Directions 8 Appendix A 8.1 Function and Signal Space 8.2 Transformations and Representation 8.3 Wavelet Transform 8.3.1 Scaling Function 8.3.2 Multiresolution Analysis 8.3.3 Discrete Wavelet Transform 8.3.4 Filter Bank Structure 8.3.5 Synthesis Filter Bank 9 Appendix B 9.1 Nobel Identities 9.2 Design of the q-shift Filters 9.3 Proof Lemma 1 9.4 Proof Lemma 2 10 Appendix C 10.1 Proof of Parseval’s Theorem 11 Appendix D 11.1 Equal-length Motif Discovery on Lightning Data Set 11.2 Variable-length Motif Discovery on Lightning Data Set 11.3 KITE’s Time Complexity and Distance Measures 11.4 KITE’s Performance Under Noise 11.5 Applications of KITE in Higher Dimension 11.5.1 Two Dimensional Analytic Complex Quad Tree Wavelet Packet 11.5.1.1 Motif Discovery on Image Data Set Bibliography List of Tables List of Figures