Segmentation And Clustering Of Multivariate Time Series

Multivariate time series widely exist in social life and various industries.Multivariate time series is a set of ordered multidimensional data,which records the values of multiple variables related to production and practical application at different times.The task of time series analysis is to discover potential characteristics of the time series,extract the information contained in the data,and understand the laws of things hidden behind the data,so as to better guide or control people’s behavior or decisions.Multivariate time series records the information of multiple dimensions of the observation object,and there is a correlation between these dimensions,so multivariate time series analysis is an important and challenging problem.Time series segmentation and clustering are two basic problems in time series analysis.Time series segmentation is also called change points detection,its purpose is to detect abnormal or abrupt points in the time series,and use these points as breakpoints to divide the time series into several segments.Time series clustering aims to divide the subsequences of time series into different clusters,so that the subsequences in the same cluster are as similar as possible.In this paper,we mainly study multivariate time series segmentation and clustering problems.For multivariate time series that follow the Gaussian distribution,when the multivariate time series have the same mean and covariance matrix in the same segment,we propose a segmentation model and design an algorithm to solve the proposed model.Taking advantage of the sparsity of breakpoints,the L₀-norm prior of the derivative of the time series mean can be used as a regularization term.Based on the maximum likelihood and the L₀-norm regularization,we construct an L₀-norm regularized segmentation model for multivariate time series segmentation,and design an alternate iterative algorithm to solve the proposed model.In the alternate iterative algorithm,the mean is obtained by solving the L₀-norm regularized optimization problem with respect to the derivative of the mean.The possible breakpoints set is estimated by using the derivative of the mean,and the optimal breakpoints are determined by the dynamic programming algorithm.We use the proposed method to segment the synthetic time series and the real time series.Segmentation results show that the proposed time series segmentation method has higher computational efficiency and more accurate segmentation than the existing time series segmentation methods.For the segmentation problem of multivariate time series that follow Gaussian distribution,when time series within the same segment have the same covariance matrix but different means,we construct the segmentation model and design an algorithm to solve the proposed model.In practical applications,a time series usually can be modeled as a piecewise continuous function,it is reasonable to assume that the means of the time series in the same segment are different.In addition,because of the contamination caused by some inevitable noise during the data acquisition procedure,the time series is usually degraded.So,in multivariate time series segmentation,we need to remove the random noise in the data as well as detect the breakpoints.Total variation（TV）prior of the data can efficiently remove noise and preserve sharp changes in the data.Therefore,we introduce the TV norm of the mean as a regular term in the maximum likelihood segmentation model,and construct a total variation regularized multivariate time series segmentation model.An alternate iterative algorithm is designed to solve the segmentation model.In the alternate iterative algorithm,the mean is obtained by solving an optimization problem with TV regularization,which is solved by the primal-dual algorithm.The possible breakpoints set is obtained by using the second-order gradient of the mean signal,and the dynamic programming algorithm is used to determine the optimal breakpoints.The experimental results show that the proposed method is efficient for segmenting either synthetic or real multivariate time series.Based on clusterwise regression method and the vector autoregressive（VAR）model of time series,we construct a new clustering method for multivariate time series.Considering the multivariate time series that follows the VAR model,we assume that each cluster can be modeled as a p-lag vector autoregressive model.Introducing a weigh function to represent the possibility that each time series data falls into a cluster,we cluster the time series by minimizing the weighted sum of squares of the regression errors.Temporal proximity is important in time series clustering,which encourages grouping adjacent time points into the same cluster.In order to achieve temporal proximity,the total variation of the weight function is introduced in the minimization model,and a regularized clusterwise vector autoregressive model is constructed.An alternate iterative method is designed to alternately calculate the weight function and the parameters of the VAR models,and the VAR model provides some interpretable information for the clustering results.Experimental results show the efficiency of the proposed method for clustering both synthetic and real multivariate time series and the proposed method is competitive to the existing methods for multivariate time series clustering.