Discovering u-shapelets with key points for time series clustering

Focusing on the problem that most existing time series clustering algorithms based on u-shapelets fail to simultaneously balance the efficiency and quality of u-shapelet extraction, this paper proposes a new time series clustering algorithm, keyUS, which identifies u-shapelets based on key points. First, a subset of time series is selected by random sampling from the time series dataset. Then, a two-step method is proposed to identify key points within the sampled time series. Secondly, these key points are utilized to extract subsequences to obtain the u-shapelet candidate set, effectively reducing the number of candidate subsequences while ensuring their high representativeness. Subsequently, the Davies-Bouldin (DB) index is introduced as a new quality evaluation method to ensure that the obtained u-shapelet set exhibits high quality. Finally, use k-Means to cluster the distance matrix constructed based on the u-shapelet set. We make experiments on various datasets and evaluate the performance of the keyUS with 12 baseline methods. The experimental results demonstrate that the keyUS algorithm has higher accuracy and better interpretability. The proposed method can effectively improve the clustering accuracy of time series while ensuring the efficiency of u-shapelet extraction.