Graph-based Clustering For Multivariate Time Series Data Using Pairwise Constraint Propagation

Recently,multivariate time series(MTS)data widely appear in various fields,such as climate detection,medical diagnosis and human behavior recognition.Therefore,MTS data mining has attracted lots of attention.Clustering,as an important technology of data mining,has produced a large number of research results in the past ten years.In order to further improve the accuracy of clustering,by converting pairwise constraints provided by exports into prior information,semi-supervised clustering has become a popular way.However,due to the high dimensionality and structural complexity of MTS data,semi-supervised clustering methods still have several limitations.First,due to the high dimensionality and multiple variables of MTS samples,it is very time-consuming to calculate the distance between MTS samples in the clustering process.Second,the pairwise constraints provided by experts are limited.However,traditional semi-supervised clustering method does not make full use of the prior information of the limited pairwise constraints.How to make full use of the pairwise constraints is still an urgent research problem.Thirdly,due to the complex structure of MTS data,there is a lack of efficient solutions for semi-supervised clustering of MTS data.In order to solve the problems above,this paper proposes a semi-supervised clustering method for MTS data,which includes:(1)Firstly,in order to efficiently calculate the distance between MTS samples,two approximate distance measure methods(ADTW and HDTW)based on dynamic time warping(DTW)are designed from the perspectives of boundary and dimension reduction,which greatly improve the calculation efficiency while maintaining the accuracy of the results obtained by true DTW algorithm as much as possible.(2)Then,in order to make full use of pairwise constraint information,a graph-based clustering method with pairwise constraints propagation(GCPCP)is proposed.The MTS data is converted into a graph,and the pairwise constraints are propagated on the graph through graph regularization.Then,the propagated pairwise constraints adjust the graph in turn.They depend on each other and update alternatively to obtain final clustering results with high performance.In order to verify the effectiveness and efficiency of the proposed method,a large number of comparative experiments are carried out with the approximate distance measurement method and the graph-based clustering method with pairwise constraint propagation.The experimental results on twelve MTS datasets show that the proposed method is much better than those state-of-the-art semi-supervised clustering methods.