Query: SSDTW: Shape segment dynamic time warping 

Candidate papers:

abstract: Abstract In order to increase the yield of a process, it is essential to establish a process control based on manufacturing data. Process management systems mainly consist of statistical process control (SPC) fault detection and classification (FDC) and advanced process control (APC) and are modeled using time series data. However, large amounts of time series data and various distributions are collected in the process; hence, preprocessing measures, such as length adjustment, are essential for modeling. Dynamic time warping (DTW) has been widely used as an algorithm that can measure the similarity between two different time series data and adjust their length. However, owing to the complex structure and time lag of processing time series data, there are limitations in applying the traditional DTW. Therefore, to solve this problem, we propose the shape segment dynamic time warping (SSDTW) algorithm that improves DTW in consideration of the structure information of time series data. By using the maximum overlap discrete wavelet transform (MODWT) the proposed method reflects the peripheral information of the time series data and divides the time series data interval to achieve a reasonable local alignment path. SSDTW attains more accurate alignment paths than DTW, derivative dynamic time warping (DDTW) and shapeDTW. Experiments conducted using semiconductor signal data and UCR time series data sets show that the proposed method is more effective than DTW, DDTW, and shapeDTW.
author_names: Jae Yeol Hong

Seung Hwan Park

Jun-Geol Baek
title: SSDTW: Shape segment dynamic time warping
venue: Expert Syst. Appl.
year: 2020

abstract: The semiconductor manufacturing process is divided into fabrication process and packaging process. Fabrication process is a core process for manufacturing semiconductors and consists of about 700 unit processes. This unit process accumulates vast amounts of data, and many manufacturing companies apply data based algorithms to manufacturing systems to improve process yield and quality. Data generated during the semiconductor manufacturing process from the process equipment is called fault detection and classification (FDC) trace data, and this data has time series characteristics of different patterns depending on the sensor type or the recipe. Therefore, it is necessary to develop a classification algorithm appropriate to the signal pattern for process monitoring. In this paper, we develop segmented dynamic time warping technique which is specialized for process signal classification. Generally, it is known that dynamic time warping (DTW) has superior classification performance for time series data. However, there is a limit to classification that reflects the characteristics of semiconductor process signals. Therefore, we developed a classification algorithm for process signal data through segmented DTW using maximum overlap discrete wavelet transform (MODWT) and random sample consensus (RANSAC) and validated it.
author_names: Jae Yeol Hong

Seung Hwan Park

Jun-Geol Baek
title: Segmented Dynamic Time Warping Based Signal Pattern Classification
venue: 2019 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC)
year: 2019

abstract: Different sets of research mainly focus on one variable time series now, while researches involving multivariate time series have been insufficient. In this paper, combined linear segments and fitting error for multivariate time series, we present a new method to reduce the time complexity of DTW distance metric algorithm. Based on the shape feature and the tilt angle, we propose a new approach for similarity matching of DTW multivariate time series. Experimental results demonstrate that this method is helpful for ensuring accuracy and for reducing the time complexity of similarity matching.
author_names: Danyang Cao

Jie Liu
title: Research on dynamic time warping multivariate time series similarity matching based on shape feature and inclination angle
venue: Journal of Cloud Computing
year: 2016

abstract: Different sets of research mainly focus on one variable time series now, while researches involving multivariate time series have been insufficient. In this paper, combined linear segments and fitt.
title: Research on dynamic time warping multivariate time series similarity matching based on shape feature and inclination angle
year: 2016

abstract: Abstract Clustering is a powerful vehicle to reveal and visualize structure of data. When dealing with time series, selecting a suitable measure to evaluate the similarities/dissimilarities within the data becomes necessary and subsequently it exhibits a significant impact on the results of clustering. This selection should be based upon the nature of time series and the application itself. When grouping time series based on their shape information is of interest (shape based clustering) using a Dynamic Time Warping (DTW) distance is a desirable choice. Using stretching or compressing segments of temporal data, DTW determines an optimal match between any two time series. In this way, time series exhibiting similar patterns occurring at different time periods, are considered as being similar. Although DTW is a suitable choice for comparing data with respect to their shape information, calculating the average of a collection of time series (which is required in clustering methods) based on this distance becomes a challenging problem. As the result, employing clustering techniques like K Means and Fuzzy C Means (where the cluster centers prototypes are calculated through averaging the data) along with the DTW distance is a challenging task and may produce unsatisfactory results. In this study, three alternatives for fuzzy clustering of time series using DTW distance are proposed. In the first method, a DTW based averaging technique proposed in the literature, has been applied to the Fuzzy C Means clustering. The second method considers a Fuzzy C Medoids clustering, while the third alternative comes as a hybrid technique, which exploits the advantages of both the Fuzzy C Means and Fuzzy C Medoids when clustering time series. Experimental studies are reported over a set of time series coming from the UCR time series database.
author_names: Hesam Izakian

Witold Pedrycz

Iqbal Jamal
title: Fuzzy clustering of time series data using dynamic time warping distance
venue: Eng. Appl. Artif. Intell.
year: 2015

abstract: Abstract. A two step vehicle recognition method from an aerial Lidar point cloud is proposed in this paper. First, the Lidar point cloud is segmented using the region growing algorithm with vehicle size limitation. Then the vehicle is recognized according to the profile shape based on dynamic time warping. The proposed method can detect vehicles parking under trees in an urban scene, and classifies the vehicles into different classes. The vehicle location, orientation, parking direction and size can also be determined. The experimental result based on a real urban Lidar point cloud shows that the proposed method can correctly recognize 95.1 of vehicles.
author_names: T Zhang

George Vosselman

Sander Oude Elberink
title: Vehicle Recognition In Aerial Lidar Point Cloud Based On Dynamic Time Warping
year: 2017

abstract: A growing attention has been paid to mining time series knowledge recently. Euclidean distance measure is used for comparing time series. However, it may be a brittle distance measure as less robustness. In this paper, a modification algorithm, which applied linguistic variable concept tree to describe the slope feather of time series, was presented named dynamic time warping. For reducing the computational time and local shape variance disturbing, the piecewise linear representation was used to process warping path. Moreover, the linguist concept tree was developed based on cloud models theory which integrities randomness and probability of uncertainty, so that made conversion between qualitative and quantitative knowledge. Experiments about cluster analysis on the basis of this algorithm, compared with Euclidean measure, were implemented on synthetic control chart time series. The results showed that this method, presented in this paper, have strong robustness to loss of feather data due to piecewise segment preprocessing. Moreover, after the construction of shape concept tree, we can discover knowledge of time series on different time granularity.
author_names: Yingjun Weng

Zhongying Zhu
title: Time series clustering based on shape dynamic time warping using cloud models
venue: Proceedings of the 2003 International Conference on Machine Learning and Cybernetics (IEEE Cat. No.03EX693)
year: 2003

abstract: BackgroundClassification methods of DNA most commonly use comparison of the differences in DNA symbolic records, which requires the global multiple sequence alignment. This solution is often inappropriate, causing a number of imprecisions and requires additional user intervention for exact alignment of the similar segments. The similar segments in DNA represented as a signal are characterized by a similar shape of the curve. The DNA alignment in genomic signals may adjust whole sections not only individual symbols. The dynamic time warping (DTW) is suitable for this purpose and can replace the multiple alignment of symbolic sequences in applications, such as phylogenetic analysis.MethodsThe proposed method is composed of three main parts. The first part represent conversion of symbolic representation of DNA sequences in the form of a string of A,C,G,T symbols to signal representation in the form of cumulated phase of complex components defined for each symbol. Next part represents signals size adjustment realized by standard signal preprocessing methods: median filtration, detrendization and resampling. The final part necessary for genomic signals comparison is position and length alignment of genomic signals by dynamic time warping (DTW).ResultsThe application of the DTW on set of genomic signals was evaluated in dendrogram construction using cluster analysis. The resulting tree was compared with a classical phylogenetic tree reconstructed using multiple alignment. The classification of genomic signals using the DTW is evolutionary closer to phylogeny of organisms. This method is more resistant to errors in the sequences and less dependent on the number of input sequences.ConclusionsClassification of genomic signals using dynamic time warping is an adequate variant to phylogenetic analysis using the symbolic DNA sequences alignment; in addition, it is robust, quick and more precise technique.
author_names: Helena Skutkova

Martin Vitek

Petr Babula

Rene Kizek

Ivo Provaznik
title: Classification of genomic signals using dynamic time warping
venue: BMC Bioinformatics
year: 2013

abstract: In this paper, we suggest a efficient handwritten character verification method in on line environments which automatically analyses two input character string and computes their similarity degrees. The proposed algorithm first applies the circular projection method to input handwritten strings and extracts their representative features including shape, directions, etc. It then calculates the similarity between two character strings by using an improved dynamic time warping (DTW) algorithm. We improved the conventional DTW algorithm efficiently through adopting the branch and bound policy to the existing DTW algorithm which is well known to produce good results in the various optimization problems. The experimental results to verify the performance of the proposed system show that the suggested handwritten character verification method operates more efficiently than the existing DTW and DDTW algorithms in terms of the speed.
author_names: Seok-Woo Jang

Young-Jae Park

Gye-Young Kim
title: Efficient Handwritten Character Verification Using an Improved Dynamic Time Warping Algorithm
year: 2010

abstract: Historical Chinese calligraphy is now being scanned by ongoing project of Universal Digital Library to enable universal access. 483 Calligraphic page images are segmented into 13,351 individual characters, followed by character feature extraction. When an image query submits, a short list of candidates from the database is selected according to simple features of stroke transect. Then the selected candidates are ranked by shape matching using two dimensional Dynamic Time Warping (DTW) After that, similar calligraphic characters are retrieved and ranked, then the query is recognized as the label of the most similar retrieved characters.
author_names: Xiafen Zhang

Yueting Zhuang
title: Dynamic Time Warping for Chinese calligraphic character matching and recognizing
venue: Pattern Recognit. Lett.
year: 2012