Given a collection of multidimensional time-series that contains an unknown type and number of network structures between variables, how eficiently can we find typical patterns and their points of variation? How can we interpret important relationships with obtained patterns? In this paper, we propose a new method of model-based clustering, which we call network clustering via graphical lasso (NGL). Our method has the following properties: (a) Interpretable: it provides interpretable network structures and cluster assignments for the data; (b) Automatic: it determines the optimal cut points and the number of clusters automatically; (c) Accurate: it provides reliable clustering performance thanks to the automated algorithm. We evaluate our NGL algorithm on both real and synthetic datasets, obtaining interpretable network structure results and outperforming state-of-the-art baselines in terms of accuracy.
in most cases, we do not know the optimal number of clusters in advance.
Many applications generate time-series data including In this paper, we propose an automatic algorithm,
those used in automobiles [
In this paper, we focus on finding a network structure Contrast with Competitors. We will compare NGL
automatically from multidimensional time-series data. with existing methods from the viewpoint of network
Understanding the structure of these networks is useful inference. Network estimation with time-series
informabecause it allows us to devise models of sensor interac- tion has been studied as a method for analyzing
ecotion, which can be used to analyze such behaviours as nomic data and biological signal data because of the
fossil-eficient driving. However, there are many network high interpretability of its graphical model [
where is the empirical covariance (1/||) ∑︀|| , are the diferent samples,
=1 + + is the space of the positive definite matrices, determines the sparsity level of the network, and ‖ · ‖ ,1 is the of-diagonal ℓ1-norm. This is a convex optimization problem, which imposes the ℓ1-norm restriction.
To infer a time-varying sequence of networks, TVGL [
Assuming that neighboring segments tend to belong to
2. CutPointSearch: We modify the generic bottom- the same cluster, we update cut points through
Mergeup algorithm [
and Θ = { ,1 , 1,3 , ...}. , , , , and , are the data, model, and inverse covariance matrix from cut points to . Our goal is to determine if a segment should be merged with its neighboring segment. As 3.1. Model description cost shown in Figure 1, we have three candidates as updated cut points: (a) Solo has three segments all separated, (b) The MDL explains the model in a parsimonious way that Left and (c) Right have two segments in which one side calculates the required number of bits. Thus, it follows is merged. We compare the MDL costs using Equation the assumption that the more we can compress the data, (1), in these three cases, (a) vs. (b) vs. (c), and select the the more we can generalize its underlying structures. best cut points so that they minimize the local MDL cost. In a nutshell, we want to find the minimum number of For example, if (b) has the lowest cost, +2 is added to graphical lasso models needed to express the data. The the updated cut points. If (a) has the lowest cost, there is goodness of the model can be described as follows: no change from the previous cut points. We iterate this process throughout the whole sequence. < ; > = < > + < | >,
(1) where < > shows the cost of describing the model , and < | > represents the cost of describing the data given the model .
Model Coding Cost. The description complexity of model is the sum of the following elements: The number of clusters requires log* (). 1 The total number of observations of each cluster requires ∑︀
=1 log* (|ℱ|).
The mean value of each cluster which has a size × 1, requires ∑︀=1( × ). The inverse covariance matrix of each cluster which has a size × , requires ∑︀
=1 | |̸=0(2 log()+ )+log* (| |̸=0), where |·| ̸=0
describes the number of non-zero elements in a matrix
and is the floating point cost. 2
Data Coding Cost. Given a model , encoding cost of
the data using Hufman coding [
3.2.2. CutPointSearch (outer loop) This algorithm finds the optimal cut points. We are now given bundle and initial cut points . The user decides the interval of initial cut points. Since TVGL forces a time-varying similarity with neighboring network, we calculate Θ , Θ , and Θ using the TVGL graphical lasso optimization method. After obtaining each Θ , we run the MergeSegment algorithm to update the cut points. We iterate this process until the cut points are stable.
Now we have optimal cut points, which means that there are a limited number of segments that have enough samples with which to estimate the network structure. Next, we assign segments to a cluster and find the optimal number of clusters. As Algorithm 1 shows, we use the EM algorithm to classify each segment. For each iteration we vary = 1, 2, 3, ..., and minimize the function below:
2We used 4 × 8 bits in our setting So far, we have described how we calculate the MDL cost for our model. The next question is how to find arg min ∑︁ − (, ) + || ||,1, (2) optimal cut points that minimize MDL cost eficiently; =1 we still have numerous candidates with which to merge to summarize similar subsequences into a compact model, In the E-step, we assign each segment to the optimal and thus we modify the bottom-up algorithm to prevent a cluster, so that the log likelihood is maximized. In the pattern explosion. We answer this question in two steps, M-step, we calculate the value of each cluster using a MergeSegment and CutPointSearch. normal graphical lasso optimization algorithm. Until the cost function increases, we vary so as to minimize the cost function.
synthetic data. We do so because there are clear ground
truth networks with which to test the accuracy.
Experimental Setup. We randomly generate synthetic
multidimensional data in R5, which follows a
multivariate normal distribution ∼ (0, − 1). Each of the
clusters has a mean of ⃗0, so that the clustering
result is based entirely on the structure of the data. For
each cluster, we generate a random ground truth inverse
covariance as follows [
three state-of-the-art methods and one ablation method.
TICC [
Clustering Accuracy. We set each segment in each of the examples to have 100 observations in R5 (for example, "1,2,1" has a total of 300 observations). Table 1 shows the clustering accuracy for the macro-F1 scores for each dataset. As shown, NGL significantly outperforms the baselines. Our method consistently achieves the highest accuracy and lowest standard deviation. AutoPlait does not consider network structure, so it does not find any clusters. Although we gave the true number of clusters to TICC and TAGM, the average accuracy of our method is more than 10% higher. NGL no-cps shows that finding a large segment by CutPointSearch has meaning of grouping adjacent observations into the same cluster. Efect of Total Number of Samples. We next focus on the number of samples required for each method to accurately find clusters. We take the "1,2,3,4,1,2,3,4" example and vary the number of samples. As shown in Figure 2, our method outperforms the baselines for almost all segment lengths. Our method has a constantly high average, even for relatively small segment lengths. This is because our CutPointSearch algorithm correctly find cut points even if the sample size is small.
Here, we show that our NGL provides an interpretable result with real-world financial data. In general, stocks, bonds, and currency prices are correlated. By examining historical financial data, we can infer a financial network 1. Set ∈ R5× 5 equal to the adjacency matrix of structure to reveal the relationships between them. We an Erdős-Rényi directed random graph, where use hourly currency exchange rate data 3 of AUD/USD, every edge has a 20% chance of being selected. EUR/USD, GBP/USD, and USD/CAD from 2005 to 2018. 2. For every selected edge in set ∼ Assuming that the underlying network structure is conUniform([− 0.6, − 0.3] ∪ [0.3, 0.6]). We enforce a sistent for a week, we normalized the data for each week. symmetry constraint whereby every = . We also set the initial cut points at a week to capture the weekly correlation trend. The top of Figure 3 shows the 3. Let = min() be the smallest eigenvalue of clustering result obtained with NGL. During the global , and set = + (0.1 + ||), where is an financial crisis (from mid- 2007 to early 2009), we found identity matrix. that the network structure changed. There are abrupt changes on 2016/5/16 ∼ 2016/6/5, the bottom of FigWe run our experiments on four diferent temporal se- ure 3 shows how the correlation changed during this quences: "1,2,1","1,2,3,2,1","1,2,3,4,1,2,3,4","1,2,2,1,3,3,3,1". period. As we can see, a correlation related to the United We generate each dataset 10 times and report the mean and standard deviation of the macro-F1 score.
Model 1,2,1 1,2,3,2,1 1,2,3,4,1,2,3,4 1,2,2,1,3,3,3,1 Macro-F1 score of clustering accuracy for four diferent temporal sequences, comparing
NGL with state-of-the-art methods
TAGM (KDD’21)
TICC (KDD’18)
AutoPlait (SIGMOD’14)
NGL no-cps ber of samples for NGL and two other state-of-the-art methods.
clustering algorithm. We focused on the problem of the interpretable clustering of multidimensional time-series data with underlying network structures. Our proposed
Interpretable and Automatic and Accurate.
In future work, we will focus on the following direction: Online learning. In several situations, network inference needs to operate in an online fashion. And to the best of our knowledge, no study has dealt with online clustering based on network structure. In this context, we will develop an extension of our methods by utilizing the novel sliding window and bottom-up (SWAB) algorithm