Adaptive evolutionary clustering

Abstract

In many practical applications of clustering, the objects to be clustered evolve over time, and a clustering result is desired at each time step. In such applications, evolutionary clustering typically outperforms traditional static clustering by producing clustering results that reflect long-term trends while being robust to short-term variations. Several evolutionary clustering algorithms have recently been proposed, often by adding a temporal smoothness penalty to the cost function of a static clustering method. In this paper, we introduce a different approach to evolutionary clustering by accurately tracking the time-varying proximities between objects followed by static clustering. We present an evolutionary clustering framework that adaptively estimates the optimal smoothing parameter using shrinkage estimation, a statistical approach that improves a naïve estimate using additional information. The proposed framework can be used to extend a variety of static clustering algorithms, including hierarchical, k-means, and spectral clustering, into evolutionary clustering algorithms. Experiments on synthetic and real data sets indicate that the proposed framework outperforms static clustering and existing evolutionary clustering algorithms in many scenarios.

Appendix

1.1 True similarity matrix for dynamic Gaussian mixture model

We derive the true similarity matrix $\varPsi$ and the matrix of variances of similarities ${\text{ var}}(W)$, where the similarity is taken to be the dot product, for data sampled from the dynamic Gaussian mixture model described in Sect. 3.3. These matrices are required in order to calculate the oracle forgetting factor for the experiments in Sects. 5.1 and 5.2. We drop the superscript $t$ to simplify the notation.

Consider two arbitrary objects $\mathbf{x}_i \sim N(\varvec{\mu }_c,\Sigma _c)$ and $\mathbf{x}_j \sim N(\varvec{\mu }_d, \Sigma _d)$ where the entries of $\varvec{\mu }_c$ and $\Sigma _c$ are denoted by $\mu _{ck}$ and $\sigma _{ckl}$, respectively. For any distinct $i,j$ the mean is

$$\begin{aligned} {\text{ E}}\left[\mathbf{x}_i \mathbf{x}_j^T\right] = \sum _{k=1}^p {\text{ E}}\left[x_{ik}x_{jk}\right] = \sum _{k=1}^p \mu _{ck} \mu _{dk}, \end{aligned}$$

and the variance is

$$\begin{aligned} {\text{ var}}\left(\mathbf{x}_i \mathbf{x}_j^T\right)&= {\text{ E}}\left[\left(\mathbf{x}_i \mathbf{x}_j^T\right)^2\right] - {\text{ E}}\left[\mathbf{x}_i \mathbf{x}_j^T\right]^2 \\&= \sum _{k=1}^p \sum _{l=1}^p \left\{ {\text{ E}}\left[x_{ik}x_{jk}x_{il}x_{jl} \right] - \mu _{ck}\mu _{dk}\mu _{cl}\mu _{dl}\right\} \\&= \sum _{k=1}^p \sum _{l=1}^p \left\{ \left(\sigma _{ckl} + \mu _{ck}\mu _{cl}\right) \left(\sigma _{dkl} + \mu _{dk}\mu _{dl}\right) - \mu _{ck}\mu _{dk}\mu _{cl}\mu _{dl}\right\} \\&= \sum _{k=1}^p \sum _{l=1}^p \left\{ \sigma _{ckl}\sigma _{dkl} + \sigma _{ckl}\mu _{dk}\mu _{dl} + \sigma _{dkl}\mu _{ck} \mu _{cl}\right\} \end{aligned}$$

by independence of $\mathbf{x}_i$ and $\mathbf{x}_j$. This holds both for $\mathbf{x}_i,\mathbf{x}_j$ in the same cluster, i.e. $c=d$, and for $\mathbf{x}_i, \mathbf{x}_j$ in different clusters, i.e. $c \ne d$. Along the diagonal,

$$\begin{aligned} {\text{ E}}\left[\mathbf{x}_i \mathbf{x}_i^T\right] = \sum _{k=1}^p {\text{ E}}\left[x_{ik}^2\right] = \sum _{k=1}^p \left(\sigma _{ckk} + \mu _{ck}^2\right). \end{aligned}$$

The calculation for the variance is more involved. We first note that

$$\begin{aligned} {\text{ E}}\left[x_{ik}^2 x_{il}^2\right] = \mu _{ck}^2\mu _{cl}^2 + \mu _{ck}^2\sigma _{cll} + 4\mu _{ck}\mu _{cl}\sigma _{ckl} + \mu _{cl}^2\sigma _{ckk} + 2\sigma _{ckl}^2 + \sigma _{ckk}\sigma _{cll}, \end{aligned}$$

which can be derived from the characteristic function of the multivariate Gaussian distribution (Anderson 2003). Thus

$$\begin{aligned} {\text{ var}}\left(\mathbf{x}_i \mathbf{x}_i^T\right)&= \sum _{k=1}^p \sum _{l=1}^p \left\{ {\text{ E}}\left[x_{ik}^2 x_{il}^2\right] - \left(\sigma _{ckk} + \mu _{ck}^2\right) \left(\sigma _{cll} + \mu _{cl}^2\right)\right\} \\&= \sum _{k=1}^p \sum _{l=1}^p \left\{ 4\mu _{ck}\mu _{cl}\sigma _{ckl} + 2\sigma _{ckl}^2\right\} . \end{aligned}$$

The calculated means and variances are then substituted into (13) to compute the oracle forgetting factor. Since the expressions for the means and variances depend only on the clusters and not any objects in particular, it is confirmed that both $\varPsi$ and ${\text{ var}}(W)$ do indeed possess the assumed block structure discussed in Sect. 3.3.