Co-clustering of Time-Dependent Data via the Shape Invariant Model

In the parametric, or model-based, co-clustering framework, the latent block model (LBM, Govaert and Nadif, 2013) is the most popular approach. Data are represented in a matrix form \(\mathcal {X}=\{ x_{ij} \}_{1\le i \le n, 1 \le j \le d}\), where by now we should intend x_ij as a generic random variable. To aid the definition of the model, and in accordance with the parametric approach to clustering (Fraley & Raftery, 2002; Bouveyron et al., 2019), two latent random vectors z = {z_i}_1≤i≤n, and w = {w_j}_1≤j≤d, with \(z_{i} = (z_{i1},\dots ,z_{iK})\), \(w_{j}=(w_{j1},\dots ,w_{jL})\), are introduced, indicating respectively the row and column memberships, with K and L the number of row and column clusters. A standard binary notation is used for the latent variables, i.e. z_ik = 1 if the i th observation belongs to the k th row cluster and 0 otherwise and, likewise, w_jl = 1 if the j th variable belongs to the l th column cluster and 0 otherwise. The model formulation relies on a local independence assumption, where the n × d random variables {x_ij}_{1≤i≤n,1≤j≤d}, are assumed to be independent conditionally on z and w, in turn supposed to be independent. The LBM can be thus written as where The LBM is particularly flexible in modelling different data types, as handled by a proper specification of the marginal density p(x_ij;𝜃_kl) for binary (Govaert & Nadif, 2003), count (Govaert & Nadif, 2010), continuous (Lomet, 2012), categorical (Keribin et al., 2015), ordinal (Jacques & Biernacki, 2018; Corneli et al., 2020) and even mixed-type data (Selosse et al., 2020).

Once the LBM structure has been properly defined, extending its rationale to handle time-dependent data in a co-clustering framework boils down to a suitable specification of p(x_ij;𝜃_kl). Note that this reveals one of the main advantages of such a highly-structured model, consisting in the chance to search for patterns in multivariate and complex data by specifying only the model for the variable x_ij. As introduced in Section 1, multidimensional time-dependent data may be represented according to a three-way structure where the third mode accounts for the time evolution. The observed data assume an array configuration \(\mathcal {X}= \{ x_{ij}(\mathbf {t}_{i}) \}_{1\le i \le n, 1\le j \le d}\) with \(\mathbf {t}_{i}=(t_{i,1},\dots ,T_{i,n_{i}})\) as outlined in Section 2; from a practical standpoint, subject dependent time instants, sparsely sampled curves and different observational lengths can be handled by a suitable use of missing entries. Consistently with Eq. 1, we consider as a generative model for the curve in the (i,j)th entry, belonging to the generic block (k,l), the following with t ∈t_i a generic time instant. A relevant difference with respect to the original SIM consists, coherently with the co-clustering setting, in the parameters being block-specific since the generative model is specified conditionally to the block membership of the cell. As a consequence: Note that here we embed the ideas borrowed from the curve registration framework in a clustering setting. Therefore, while curve alignment aims to synchronize the curves to estimate a common mean shape, in our setting the SIM works as a suitable tool to model the heterogeneity inside a block and to introduce a flexible notion of cluster. The rationale behind considering the SIM in a co-clustering framework consists in looking for blocks characterized by a different mean shape function m(⋅;β_kl). Curves within the same block arise as random shifts and scale transformations of m(⋅;β_kl), driven by the block-specifically distributed random effects. Let consider the small panels on the left side of Fig. 2, displaying a number of curves which arise as transformations induced by non-zero values of α_ij,1, α_ij,2, or α_ij,3. Beyond the sample variability, the curves differ for a (phase) random shift on the x −axes, an amplitude shift on the y-axes, and a scale factor. According to model Eq. 3, all those curves belong to the same cluster, since they share the same mean shape function (Fig. 2, right panel).

Further flexibility can be naturally introduced within the model by “switching off” one or more random effects depending on subject-matter considerations and on the user’s cluster definition. For example, if there are reasons to support that similar, yet shifted in time, evolutions are expressions of different clusters, it makes sense to switch off α_ij,3. As a consequence, the model specification in Eq. 3 would no longer include the corresponding random effect α_ij,3

In the following, we refer to this model as TTF, to highlight that the third random effect is switched off. In the example illustrated in Fig. 2 this situation ideally leads to a two-cluster structure (Fig. 3, right panels). Similarly, if comparable time evolution curves associated to different intensities are seen as expressions of distinct groups, the random intercept α_ij,1 can be switched off, and we refer to this class of models as FTT. Lastly, removing α_ij,2 results in TFT models which would determine different blocks varying for a scale factor (Fig. 3, middle panels). From a practical standpoint, switching off a random effect amounts to constrain it to follow a degenerate distribution centered at zero in the estimation scheme outlined in the next section.

To estimate the LBM several approaches have been proposed, as for example Bayesian estimation (Wyse & Friel, 2012), greedy search algorithms (Wyse et al., 2017) and likelihood-based procedures (Govaert & models, 2008). In this work we focus on the latter class of methods. In principle, the estimation strategy would aim to maximize the log-likelihood \(\ell ({\Theta }) = \log p(\mathcal {X}; {\Theta })\) with \(p(\mathcal {X}; \theta )\) defined as in Eq. 2; nonetheless, the missing structure of the data makes this maximization impractical. For this reason the complete-data log-likelihood is usually considered as the objective function to optimize, defined as where the first two terms account for the proportions of row and column clusters while the third one depends on the probability density function of each block.

As a general solution, to maximize Eq. 4 and obtain an estimate of \(\hat {\Theta }\) when dealing with situations where latent variables are involved, one would in principle resort to the expectation-maximization algorithm (EM, Dempster et al., 1977). The basic idea underlying the EM algorithm consists in finding a lower bound of the log-likelihood and optimizing it via an iterative scheme in order to create a converging series of \(\hat {\Theta }^{(h)}\). In the co-clustering framework, this lower bound can be easily exhibited by rewriting the log-likelihood as follows where \({\mathscr{L}}(q; {\Theta }) = {\sum }_{\mathbf {z},\mathbf {w}} q(\mathbf {z},\mathbf {w})\log (p(\mathcal {X},\mathbf {z},\mathbf {w}| \theta )/q(\mathbf {z},\mathbf {w})),\) q(z,w) is a generic probability mass function on the support of (z,w) while ζ is a positive constant not depending on Θ.

The E step of the algorithm maximizes the lower bound \({\mathscr{L}}\) over q for a given value of Θ. Straightforward calculations show that \({\mathscr{L}}\) is maximized for \(q^{*}(\mathbf {z},\mathbf {w})=p(\mathbf {z},\mathbf {w}|\mathcal {X},\theta )\). Unfortunately, in a co-clustering scenario, the joint posterior distribution \(p(\mathbf {z},\mathbf {w}|\mathcal {X},{\Theta })\) is not tractable, as it involves terms that cannot be factorized as it conversely happens in a standard mixture model framework. As a consequence, several modifications have been explored, searching for viable solutions when performing the E step (see Govaert & Nadif, 2013 for a more detailed tractation); examples are the classification EM (CEM) and the variational EM (VEM). Here we propose to make use of a Gibbs sampler within the E step to approximate the posterior distribution \(p(\mathbf {z},\mathbf {w}|\mathcal {X},{\Theta })\). This results in a stochastic version of the EM algorithm, which will be called SEM-Gibbs in the following. Given an initial column partition w⁽⁰⁾ and an initial value for the parameters Θ⁽⁰⁾, at the h th iteration the algorithm proceeds as follows: In the proposed framework, due to the presence of the random effects, some additional challenges have to be faced. In fact, the maximization of the conditional expectation of Eq. 4 associated to model in Eq. 3 requires a cumbersome multidimensional integration in order to compute the marginal density defined as Note that, with a slight abuse of notation, we suppress the dependency on the time t, i.e. x_ij will represent x_ij(t_i). In the SE step, on the other hand, the evaluation of Eq. 5 is needed for all the possible configurations of \(\{z_{i}\}_{i=1,\dots ,n}\) and \(\{w_{j}\}_{j=1,\dots ,d}\). These quantities are obtained when the SEM-Gibbs is used to estimate models without any random effect involved, while their computation is more troublesome in our scenario.

We propose a modification of the SEM-Gibbs algorithm, called marginalized SEM-Gibbs (M-SEM), where an additional marginalization step is introduced to account for the random effects. Given an initial value for the parameters Θ⁽⁰⁾ and an initial column partition w⁽⁰⁾, the h-th iteration of the M-SEM algorithm alternates the following steps: The M-SEM algorithm is run until a convergence criterion is met. The convergence for the proposed procedure is assessed by monitoring the evolution of the complete-data log-likelihood: more specifically the algorithm reaches convergence when the sum of the changes in ℓ_c(Θ,z,w) in the last three iterations are smaller than a given threshold δ > 0. Since a burn-in period is considered, the final estimate for Θ, denoted as \(\hat {\Theta }\), is given by the mean of the sample distribution. A sample of (z,w) is then generated according to the SE step as illustrated above with \({\Theta }=\hat {\Theta }\). The final block-partition \((\hat {\mathbf {z}},\hat {\mathbf {w}})\) is then obtained as the mode of their sample distribution.

The approach considered in this work represents an extension to the likelihood maximization strategies, usually adopted in the LBM framework. Note that other choices could be alternatively explored, such as fully Bayesian estimation schemes that would allow for statistical inference on the parameter estimates (van Dijk et al., 2009) and for the automatic selection of the number of blocks (Wyse & Friel, 2012).

The choice of the number of groups is considered here as a model selection problem. Operationally we estimate several models, corresponding to different combinations of K and L and, in our case, to different configurations of the random effects, and we select the best one according to an information criterion. Note that the model selection step is more troublesome in this setting with respect to a standard clustering one, since we need to select not only the number of row clusters K but also the number of column ones L. Standard choices, such as the AIC and the BIC, are not directly available in the co-clustering framework where, as noted by Keribin et al. (2015), the computation of the likelihood of the LBM is challenging, even when the parameters are properly estimated. A viable alternative is to consider an approximated version of the ICL (Biernacki et al., 2000) that, relying on the complete-data log-likelihood, does not suffer from the same issues: where ν denotes number of specific parameters for each block while \(\ell _{c}(\hat {\Theta }, \hat {\mathbf {z}}, \hat {\mathbf {w}})\) is defined as in Eq. 4 with Θ, z and w being replaced by their estimates. The model associated with the highest value of the ICL is then selected.

Even if the use of this criterion is a well-established practice in co-clustering applications, Keribin et al. (2015) noted that its consistency has not been proved yet to estimate the number of blocks of a LBM. Additionally, Nagin (2009) and Corneli and Erosheva (2020) point out a bias of the ICL towards overestimation of the number of clusters in the longitudinal context. The validity of the ICL could be additionally undermined by the presence of random effects. As noted by Delattre et al. (2014), standard information criteria have unclear definitions in a mixed effect model framework, since the definition of the actual sample size is not trivial. Given that, common asymptotic approximations are not valid anymore. Even if a proper exploration of the problem from a co-clustering perspective is still missing, we believe that the mentioned issues might also have an impact on the derivation of the criterion in Eq. 7. The development of valid model selection tools for LBM when random effects are involved is out of scope of this work, therefore, operationally, we consider the ICL. Nonetheless, the analyses in Section 4 have to be interpreted with full awareness of the limitations described above.

Additionally note that, to practically evaluate Eq. 7, the complete-data log-likelihood is required. As outlined in the previous section, marginalization procedures are needed to compute the marginal densities involved in Eq. 4. As a consequence, the first term Eq. 7 is approximated, thus possibly depending on the considered marginalization scheme. Nonetheless, different approximation strategies have been proposed and their accuracy have been thoroughly tested (see, e.g. Pinheiro and Bates, 1995), showing that the choice of a specific procedure is not strongly influential.

Lastly, since the ICL would serve to the selection of both the number of row and column clusters and the random effect configuration, note that the involved computational time might be rather demanding, also depending on the sample size, the data dimension and the number of observed time occasions. In such situations, resorting to some greedy search strategy, where not all models under evaluations have to be estimated, could be helpful. See, for instance, Keribin et al. (2017) and Corneli et al. (2020).

The model introduced so far inherits the advantages of both its building ingredients, namely the LBM and the SIM. The local independence assumption allows for multivariate data with high-dimensional complex data structures to be handled in a relatively parsimonious way. On the other hand, the characteristics of the model introduce some relevant advantages, in terms of interpretability of the time evolutions of the variables, even in low dimensional settings. The random effects capture differences among the subjects, while curve summaries can be expressed as a function of the mean shape curve. Additionally, resorting to a smoother when modelling the mean shape function, allows for a flexible handling of functional data whereas the presence of random effects make the model effective also in a longitudinal setting. In fact, the borrowing strength mechanism induced by the random effects can handle sparsely and irregularly sampled longitudinal data (James and Sugar, 2003). Finally, we pursue clustering directly on the observed curves, without resorting to intermediate transformation steps, as is done in Bouveyron et al. (2018) where clustering is performed on an intermediate space, spanned by the basis expansion coefficients used to transform the original data, thus possibly endangering the interpretation in terms of the evolution in time. The model, despite its attractive features, introduces some difficulties that require caution, as in the following discussed.

This section examines the main features of the proposed approach on some synthetic data. The aim of the simulation study is twofold. The first goal of the analyses consists in exploring the capability of the proposed method to properly partition the data into blocks, also in comparison with some competitors such as the one proposed by Bouveyron et al. (2018) (funLBM in the following) and a double k-means approach, where row and column partitions are obtained separately and subsequently merged to produce blocks. With this regard, we evaluate the results by means of the co-clustering adjusted Rand index (CARI, Robert et al., 2021). This criterion generalizes the adjusted Rand index (Hubert and Arabie, 1985) to the co-clustering framework, and takes the value 1 when the blocks partitions perfectly agree up to a permutation. In order to have a fair comparison with the double k-means approach, for which selecting the number of blocks is not straightforward, and to separate the uncertainty due to model selection from the one due to cluster detection, we compared models by considering the number of blocks as known and equal to (K_true,L_true). Consistently, we estimate our model only for the true random effects configuration, being the one considered to generate the data.

As for the second aim of the simulations, we evaluate the performances of the ICL in the developed framework to select both the number of blocks (K,L) and the random effects configuration.

All the analyses have been conducted in the R environment (R Core Team, 2019) with the aid of nlme package (Pinheiro et al., 2019) to estimate the parameters in the M step, and the splines package to handle the B-spline involved in the common shape function. The code implementing the proposed procedure is available upon request.

The main simulation setup is defined as follows. We generated B = 100 Monte Carlo samples of curves according to the general specification in Eq. 3, with block-specific mean shape function m_kl(⋅) and both the parameters involved in the error term and the ones describing the random effects distribution being constant across the blocks. In fact, in the light of the considerations made in Section 3.5, the random scale parameter is switched off in the data generative mechanism, i.e. α_ij,2 is constrained to be degenerate in zero. We fixed the number of row and column clusters to K_true = 4 and L_true = 3. The mean shape functions m_kl(⋅) are chosen among four different curves, namely m₁₁ = m₁₃ = m₃₃ = m₁, m₁₂ = m₃₂ = m₃₁ = m₄₁ = m₂, m₂₁ = m₃₂ = m₄₂ = m₃ and m₂₂ = m₄₃ = m₄, as illustrated in Fig. 4 with different color lines, and specified as follows:

We set the other involved parameters to σ_𝜖,kl = 0.3, \(\mu _{kl}^{\alpha } = (0,0,0)\) and \({\Sigma }_{kl}^{\alpha } = \text {diag}(1,0,0.1)\) \(\forall k=1,\dots ,K_{\text {true}}, l=1,\dots ,L_{\text {true}}\). Three different scenarios are considered with generated curves consisting of T = 15 equi-spaced observations ranging in [0,1]. As a first baseline scenario, we set the number of rows to n = 100 and the number of columns to d = 20. The other scenarios are considered in order to obtain insights and indications on the performances of the proposed method when dealing with larger matrices. Coherently in the second scenario, n = 500 and d = 20 while in the third one, n = 100 and d = 50 thus increasing respectively the number of samples and features.

Results are reported in Table 1. The proposed method claims excellent performances in all the considered settings, with results notably featured by a very limited variability and sensitivity to changes in n or d. No clear-cut indications arise from the comparison with funLBM in the baseline scenario, but the latter method shows a larger sensitivity to an increase of data size and dimension, where its performances get worse. The use of an approach which is not specifically conceived for co-clustering, like the the double k-means, leads to a stronger degradation of the quality of the partitions. However, not considering jointly the variables and the observations, k-means behaves better with increasing dimensions.

As for the performances of the ICL, Table 2 shows the fractions of samples where the criterion has led to the selection of each of the considered configurations of (K,L), with \(K,L = 2,\dots ,5\), for models estimated with the proposed method and with funLBM. In all the considered settings, the actual number of co-clusters is the most frequently selected by the ICL criterion, yet a non-negligible tendency to favor overparameterized models, especially for larger sample size, is witnessed, consistently with the comments in Corneli et al. (2020). Conversely, when considering funLBM, the ICL selects the pair (K_true,L_true) in the very large majority of the Monte Carlo simulations.

In addition, the simulations described above have been run on a slightly different setup, where While the column partition remains unchanged with respect to the previous setting, in the row partition curves in cluster 3 and 4 differ with respect to either a time shift or a vertical shift only, hence the configuration gets consistent with K_true = 3 and a TFT layout. The reduced heterogeneity among curves in the new setting simplify the co-cluster detection for both the models, so that results in terms of CARI (not reported for brevity) are almost perfect when they are forced to partition data in the actual number of blocks. However, when the ICL is used to select (K,L), the different notion of group targeted by funLBM and the proposed model is strongly influencing: on one hand, for our proposal, an overall good behaviour is confirmed when the ICL is used to detect the number of blocks; on the other hand, the same does not apply to funLBM, whose likelihood does not support the designed cluster notion, and the ICL systematically does not select the actual cluster configuration (Table 3).

With respect to the exploration of the performances of the ICL when used to select the random effect configuration (Table 4), we may draw similar considerations to the selection of the number of co-clusters. Here, the ICL selects the true configuration for the majority of the samples in two scenarios while, in the third one, the true model is selected approximately one out of two samples. Nonetheless, also in this case, a tendency to overestimation is visible, with the TTT configuration frequently selected in all the scenarios. In general, the penalization term in Eq. 7 seems to be too weak and overall not completely able to account for the presence of random effects. These results, along with the remarks at the end of Section 3.3, provide a suggestion about a possibly fruitful research direction to provide some suitable adjustments.

In fact, it is worth noting that when the selection of the number of clusters is the aim, the observed behavior is preferable with respect to underestimation since it does not undermine the homogeneity within a block; this has been confirmed by further analyses suggesting that the additional groups are usually small and arising because of the presence of outliers. As for the random effect configuration, we believe that since the choice impacts the notion of cluster one aims to identify, it should be driven by subject-matter knowledge rather than by automatic criteria. Additionally, the reported analyses are exploratory in nature, aiming to provide general insights on the characteristics of the proposed approach. To limit computational time required to run the large number of models involved in Tables 2, 3, 4, we did not use multiple initializations and we have pre-selected the number of knots for the block-specific mean functions. In practice, we recommend using multiple starting values and carrying out sensitivity analyses on the number of knots to ensure that the conclusions are not affected.