Research And Application On Sequence Similarity Measure Method Based On LDTW Distance

The similarity measure is an important research of machine learning,and it is widely used in natural language processing,computer vision,and so on.As an important similarity measure method,Dynamic Time Warping(DTW)distance can solve the problem caused by the situation when the sequence is distorted and cannot be matched.However,there is a one-to-many problem(pathological alignment)between data points,resulting in low accuracy.A novel variant of DTW called Dynamic Time Warping under limited warping path length(LDTW)was proposed,which limits the total number of links during the optimization process of DTW,and improves the accuracy of the algorithm.Starting from the promotion and practice of LDTW,this thesis expanded its application field for different data scenarios.At the same time,aiming at the high time complexity of LDTW,the ant colony optimisation(ACO)algorithm based on heuristic search mechanism was used to optimize the algorithm,which reduced the calculation time and ensuring the accuracy at the same time.The main research work of this thesis is as follows:1.The application of LDTW in small data and poverty information system.Compared with big data analysis,small data pay more attention to accuracy.This thesis started with the important tool of small data research(the grey incidence analysis model)and developed the application and practice of LDTW.At present,traditional grey incidence degree(GID)methods usually align unequal sequences by data removal,mean statistic or prediction and so on.These manual interventions have a great impact on the performance of these methods.Aiming at reducing the impact of manual interventions,a novel GID based on dynamic time warping under limited warping path length(GID-LDTW)was proposed.The cases of the equal-length sequence and the unequal-length sequence were analyzed,and grey incidence clustering was further carried out.This method showed better performance and robustness,and it achieved the application of LDTW in small data uncertainty system.2.Research on LDTW optimization algorithm for large sample data.As the reduction of time cost is the core,an optimized dynamic time warping distance method based on ant colony optimisation algorithm(ACO_LDTW)was proposed under the premise of ensuring the accuracy.LDTW is based on DTW and the length of the best warping is the limited path by searching steps,so that the algorithm calculation time is too long,and it is not suitable for the case where the sample data amount is large.Therefore,a heuristic search mechanism with parallel computing ability was adopted,the ant colony algorithm based on the grid map was introduced to replace the recursive linear computation of LDTW.This algorithm searched the optimal path on the restricted distance matrix by simulating the behaviour of ant colony parallel foraging.The state transition probability function,pheromone initialization and update mechanism of ant colony algorithm were modified to achieve similarity measurement under the warping path constraints.Case analysis and classification experiments showed that the method can keep high accuracy while reducing time overhead.Further application of mechanical fault diagnosis showed that ACO_LDTW has good performance in the practical engineering field.