Research On Clustering-based Fast Shapelet Discovery Algorithm And Its Application

Time series classification is a classical problem in time series data mining,different from general classification,the attributes of time series are stored in chronological order,at the same time,time series often have high dimension and large scale.Therefore,the general classification algorithms are accompanied with high computational complexity in feature selection and the selected features cannot explain the classification results,which leads to high time complexity and weak interpretability in current time series classification algorithms.Shapelet is a subsequence of time series which can represent the category information in maximum and can explain the classification results intuitively.Shapelet based classification algorithms have the advantages of strong interpretability and high classification accuracy.However,shapelet discovery algorithm relies on decision tree classifier,the classification accuracy is not high.Shapelet transformation algorithm and shapelet learning algorithm are combined with different classifiers which improves the classification accuracy,but the training process consumes too much time.In this paper,shapelet based classification algorithm is deeply studied.The training time is further shortened by improving the mechanism of shapelet discovery algorithm.At the same time,the classification accuracy is improved by combining shapelet discovery algorithm with shapelet transformation algorithm.The main contents and contributions of this paper are as follows.(1)Because current shapelet based classification algorithms rely on single classifier and consuming a lot of time,an improved k-means-based fast shapelet discovery algorithm is proposed.This algorithm reduces the repeated evaluation of similar features in time series by a sampling strategy based on k-means clustering and Euclidean distance sorting,and then reducing the scale of shapelet candidates by defining important data points.The discovered shapelets are directly applied to the shapelet transformation algorithm.Experimental results show that the proposed algorithm has higher classification accuracy and faster running time.Meanwhile,the proposed algorithm is applied to automatic detection of EEG features.(2)Because current time series chain discovery algorithms are difficult to define initial feature and only have a single discovery direction,a bidirectional shapelet based time series chain discovery algorithm is proposed.This algorithm uses shapelet as the initial feature to guide the bidirectional discovery of time series chain,and it is applied to ECG time series chain discovery.Experimental results show that abnormal ECG time series chain is occasionally detected in different ECG signals,which has a good auxiliary effect on the diagnosis of cardiac arrhythmia.At the same time,this paper conducts a waveform prediction experiement based on the average trend of discovered ECG time series chain.