PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Evolutionary Clustering

Kevin S. Xu, Mark Kliger, Alfred O. Hero III

arXiv:1104.1990v3cs.LGstat.ML

TL;DR

Clustering evolving objects must balance long-term trends against short-term noise, while prior evolutionary methods leave the smoothing-weight choice open. AFFECT tracks time-varying proximities with an adaptively estimated forgetting factor before applying static clustering, and the reported experiments show it outperforming static and existing evolutionary methods.

  • Problem

    Static clustering can be unstable under noise, while choosing the temporal smoothness penalty in existing evolutionary methods remains an open practical problem.

    Source: §1 · p. 2

  • Method

    AFFECT uses shrinkage estimation to adaptively weight past proximities when tracking true proximities, then applies static clustering to the estimates.

    Source: §1 · p. 2, §3.1 · p. 11

  • Results

    AFFECT outperforms static clustering and existing evolutionary clustering algorithms in the reported synthetic and real data experiments.

    Source: §1 · p. 3, §6 · p. 36

  • Takeaways & Limitations

    The framework extends to static methods using pairwise similarities or dissimilarities and accommodates changing cluster counts and objects entering or leaving the data set.

    Source: §1 · p. 3

    Choosing the number of clusters at each time step is beyond scope, and extension beyond the proposed block model is left for future work.

    Source: §3.3 · p. 15, §4.4.2 · p. 19

Abstract

from arXiv · show

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 naive 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.

1 Introduction

AFFECT tracks changing proximities before static clustering, addressing noisy time-varying data and the unresolved choice of temporal smoothing weight. It adaptively estimates that weight and outperforms static and existing evolutionary clustering methods in the reported experiments.

1 Introduction

  • Static clustering at each time step is sensitive to noise and can produce unstable results inconsistent with adjacent time steps.Objects may experience both long-term drift and short-term noise.Source: §1 · p. 2
  • Prior evolutionary methods often add a temporal smoothness penalty, but choosing its weight optimally in practice remains an open problem.The penalty limits deviation from clustering results at neighboring time steps.Source: §1 · p. 2
  • AFFECT estimates time-varying true proximities from current and past observations using shrinkage, then applies static clustering to those estimates.Its adaptive forgetting factor weights past proximities to minimize mean squared error and can vary over time.Source: §1 · pp. 2–3
  • AFFECT can extend static clustering methods that use pairwise similarities or dissimilarities, including hierarchical, k-means, and spectral clustering.It can accommodate changes in cluster count and objects entering or leaving the data set.Source: §1 · p. 3
  • AFFECT outperforms static clustering and existing evolutionary clustering algorithms in experiments, with minimal added computation over static clustering when one iteration estimates the forgetting factor.The paper extends earlier work limited to evolutionary spectral clustering and reports additional experiments.Source: §1 · p. 3

2.1 Static clustering algorithms

The section reviews static clustering methods that operate on pairwise proximities, then describes agglomerative hierarchical clustering, k-means, and spectral clustering.

2.1 Static clustering algorithms

  • For data clustering, pairwise proximities can be formed from object feature vectors; for graph clustering, the proximity matrix represents weighted edges.The paper uses “clustering” for both data clustering and graph clustering.Source: §2.1 · pp. 3–4

2.1.1 Agglomerative hierarchical clustering

  • Agglomerative hierarchical clustering repeatedly merges clusters according to their dissimilarity, producing a hierarchy that can be cut into a flat clustering.Single, complete, and average linkage use minimum, maximum, or average pairwise dissimilarity, respectively.Source: §2.1.1 · p. 4, §2.1 · p. 4

2.1.2 k-means

  • K-means assigns objects to their closest centroids and minimizes the sum of squared distances to those centroids.Its cost can be computed using a similarity matrix of pairwise feature-vector dot products.Source: §2.1.2 · p. 5

2.1.3 Spectral clustering

  • Spectral clustering relaxes graph optimization problems and discretizes the resulting eigenvector solution to obtain clusters.The reviewed variants are average association, ratio cut, and normalized cut.Source: §2.1.3 · p. 6

2.2 Related work

Related work contrasts evolutionary clustering with incremental and constrained clustering, and surveys evolutionary methods built around temporal penalties, adaptive filters, or probabilistic models.

2.2.1 Incremental clustering

  • Incremental clustering prioritizes low computational cost, whereas evolutionary clustering combines multiple time steps to improve clustering quality and can outperform static clustering.Type 1 data-stream clustering observes each object only once and is less directly related to this setting.Source: §2.2.1 · p. 7

2.2.2 Constrained clustering

  • Soft constraints encode preferences from labels or prior information, while disparate clustering favors changing memberships—the opposite of evolutionary clustering’s preference for smooth evolution.Hossain et al. (2010) describe a framework unifying disparate and dependent clustering.Source: §2.2.2 · p. 8

2.2.3 Evolutionary clustering

  • A common evolutionary approach adds temporal smoothness penalties to static clustering; PCQ penalizes disagreement with past similarities, while PCM penalizes changes in cluster assignments (Chi et al., 2009).Earlier frameworks also extended agglomerative hierarchical clustering and k-means.Source: §2.2.3 · p. 8
  • Existing methods leave the historical-weight parameter α without an optimal selection rule, typically choosing it ad hoc according to users’ smoothness preferences.An adaptive test-statistic approach still depends on a global smoothness preference.Source: §2.2.3 · p. 9
  • RG filters feature vectors before static clustering and adapts filter coefficients, but it cannot handle changing cluster counts or objects entering and leaving.AFFECT is described as adapting more quickly to cluster changes and applying to a broader class of problems.Source: §2.2.3 · pp. 9–10
  • Model-based evolutionary methods use mixtures, semi-Markov models, Dirichlet process mixtures, hierarchical mixtures, or smooth plaid models, with temporal evolution controlled by hyperparameters.Some of these hyperparameters can be estimated.Source: §2.2.3 · p. 10

3 Proposed evolutionary framework

The framework tracks time-varying proximities, estimates a smoothed proximity matrix and adaptively selects its forgetting factor, then applies static clustering.

3 Proposed evolutionary framework

  • Under tracked object identities, the framework models each observed proximity matrix as a true proximity matrix plus zero-mean noise, then estimates the evolving states for static clustering.The noise matrices across time are assumed mutually independent.Source: §3 · p. 10

3.1 Smoothed proximity matrix

  • The online smoothed proximity estimate uses current and past observations, with a time-varying forgetting factor controlling how quickly past proximities are discounted.The estimate can incorporate proximities from all previous time steps.Source: §3.1 · p. 11

3.2 Shrinkage estimation of true proximity matrix

  • Shrinkage chooses the forgetting factor by minimizing squared-error risk, balancing noisy unbiased current proximities against lower-variance but potentially drift-biased historical estimates.The oracle optimum is not implementable because it requires the unknown true proximity matrix and noise variance.Source: §3.2 · pp. 11–13

3.3 Block model for true proximity matrix

  • The block model assumes true proximities and their variances have cluster-based block structure, with equal within-cluster values and different between-cluster values; it is a simplistic choice absent prior shape information.The model is permutation invariant with respect to clusters, and extending the framework to other models is left for future work.Source: §3.3 · pp. 14–15

3.4 Adaptive estimation of forgetting factor

  • The adaptive procedure estimates cluster memberships and the forgetting factor iteratively, using block-based proximity estimates to update the smoothed matrix and recluster.Empirically, the estimated factor rarely changes after three iterations, and even one iteration often provides a good estimate.Source: §3.4 · p. 15

4 Evolutionary algorithms

AFFECT applies smoothed proximity matrices before static clustering, with interpretations for hierarchical, k-means, and spectral methods. The framework also addresses changing object sets, cluster-count selection, and matching clusters across time.

4.1 Agglomerative hierarchical clustering

  • For hierarchical clustering, AFFECT merges the pair with the lowest modified cost, combining the current dissimilarity with weighted costs from earlier time steps.The current dissimilarity is the snapshot cost; earlier-time merge costs make up the temporal cost.Source: §4.1 · pp. 16–17

4.2 k-means

  • Evolutionary k-means initializes each time step with the previous clustering and optimizes a modified cost that measures fit to current and past data.The snapshot and temporal costs use the sum-of-squares cost on current and earlier data, respectively.Source: §4.2 · p. 17

4.3 Spectral clustering

  • Average-association spectral clustering uses eigenvectors of the smoothed proximity matrix and optimizes a modified cost combining current and historical terms.When α_t−1 = 0, the modified cost matches PCQ, which uses historical data from time t−1 only.Source: §4.3 · p. 17
  • AFFECT replaces PCQ’s constant exponentially weighted forgetting factor with an adaptive one, which should help when the data’s rate of change varies over time.The cited discussion describes this as a potential performance improvement, not a guaranteed result.Source: §4.3 · pp. 17–18
  • For spectral clustering, the framework also supports ratio cut and normalized cut by forming their graph Laplacians from the smoothed proximity matrix.Unlike average association, these variants lack an obvious interpretation as optimizing a modified cost function.Source: §4.3 · p. 18

4.4.1 Adding and removing objects over time

  • When objects enter or leave, remove departing objects before smoothing and append new objects’ rows and columns afterward, so new objects do not affect the forgetting-factor update.The new objects still contribute to the clustering result through the updated proximity matrix.Source: §4.4.1 · p. 18, Figure 6 · p. 18

4.4.2 Selecting the number of clusters

  • Choosing the optimal number of clusters is beyond the paper’s scope; static-clustering heuristics can be applied at each time step, allowing the count to change over time.Examples include average silhouette width, stopping rules, the eigengap heuristic, and modularity.Source: §4.4.2 · p. 19

4.4.3 Matching clusters between time steps

  • Matching clusters across time requires permuting the current result; one-to-one matching can use maximum-weight matching, while many-to-one and one-to-many matching are outside scope.The proposed one-to-one weights count common objects between clusters at adjacent time steps.Source: §4.4.3 · p. 19

5 Experiments

Across synthetic and real-data experiments, AFFECT is evaluated for tracking and clustering accuracy against static and evolutionary methods. Results cover hierarchical, k-means, and spectral clustering, including settings with changing cluster membership, cluster counts, and object populations.

5 Experiments

  • The experiments assess tracking by MSE and clustering agreement by Rand index across hierarchical, k-means, and spectral methods.They compare AFFECT with static clustering and evolutionary methods including RG, PCQ, and PCM.Source: §5 · pp. 19–20

5.1 Well-separated Gaussians

  • For well-separated Gaussians, the estimated forgetting factor outperformed constant factors and achieved MSE close to the oracle.With 200 rather than 40 samples, the gap between estimated and oracle steady-state forgetting factors was much smaller, and it decreased as sample size increased.Source: Figure 7 · p. 20, §5.1 · pp. 20–21, Figure 8 · p. 21

5.2 Two colliding Gaussians

  • In two colliding Gaussians, estimated αt gave the best MSE among implementable choices, while αt = 0.5 worked better during movement and αt = 0.75 after clusters became stationary.The oracle factor is not implementable in practice; the estimated factor's MSE was best excluding that oracle.Source: §5.2 · p. 22, Figure 10 · p. 23
  • In two colliding Gaussians, estimated αt achieved the best Rand index, approaching the oracle, while RG responded slowly to changed memberships.Static clustering performed poorly once the clusters began overlapping; one-iteration AFFECT and AFFECT with αt = 0.5 also outperformed RG.Source: §5.2 · pp. 22, 24, Figure 11 · p. 23

5.3.1 Fixed number of flocks

  • Across 100 boids runs using complete-linkage hierarchical clustering, AFFECT achieved the best Rand-index clustering performance against RG with both short and long memory, though the difference was smaller than before.Estimated αt stayed roughly constant around 0.6; αt = 0.5 also performed well because flocking motions, including cluster changes, were smooth.Source: §5.3.1 · p. 27

5.3.2 Variable number of flocks

  • In variable-flock boids, AFFECT outperformed static clustering, PCQ, and PCM on spectral Rand index and alone accurately estimated cluster counts after rearrangement.Its estimated αt dropped when flocks scattered, and one iteration achieved the same mean Rand index as three.Source: §5.3.2 · pp. 27, 30, Figure 15 · p. 28, Table 3 · p. 28

5.4 MIT Reality Mining

  • AFFECT achieved the best Rand indices on MIT Reality Mining data both over all 46 weeks and during the school year.The comparison uses two-cluster normalized-cut spectral clustering; AFFECT also performs well when participants enter and leave over time.Source: §5.4 · pp. 30, 32, Table 4 · p. 31

5.5 NASDAQ stock prices

  • AFFECT was the best performer on NASDAQ stock clustering, though its improvement over alternatives was smaller than in earlier experiments.With one iteration, its computation time was almost equivalent to static k-means; its estimated αt dropped around the late-September 2008 market crash.Source: §5.5 · pp. 33, 35, Table 6 · p. 34, Figure 20 · p. 34

6 Conclusion

The conclusion presents AFFECT as adaptive proximity tracking followed by static clustering, with an explicit method for choosing the forgetting factor. It reports better performance than static and existing evolutionary clustering algorithms, while identifying estimator and model choices for future study.

6 Conclusion

  • A recursive update with an adaptive forgetting factor tracks true proximities, and the framework aims to minimize mean squared tracking error.Its stated advantages are extending almost any static clustering algorithm and explicitly selecting the forgetting factor.Source: §6 · pp. 35–36
  • AFFECT outperformed static and existing evolutionary clustering algorithms on several synthetic and real data sets.The conclusion reports good performance in both tracking and clustering.Source: §6 · p. 36
  • The study optimized MSE with a block model; future work includes convergence, finite-sample behavior, other loss functions, and other models.The estimated forgetting factor appeared to converge after three iterations in the presented experiments; its convergence properties remain future work.Source: §6 · p. 36

Appendix A True similarity matrix for dynamic Gaussian mixture model

The appendix derives the true similarity matrix and similarity variances for the dynamic Gaussian mixture model, using dot-product similarity. These quantities are used to calculate the oracle forgetting factor and confirm the assumed block structure.

Appendix A True similarity matrix for dynamic Gaussian mixture model

  • For dot-product similarity in the dynamic Gaussian mixture model, the appendix derives the true similarity matrix and variance matrix needed to calculate the oracle forgetting factor.The derivation concerns data sampled from the model described in Section 3.3.Source: Appendix A · p. 36
  • For distinct Gaussian-sampled objects, the mean calculation uses independence and applies to both same-cluster and different-cluster pairs; diagonal entries are treated separately.The appendix considers objects with cluster-specific means and covariance matrices.Source: Appendix A · pp. 36–37
  • The variance derivation uses a Gaussian characteristic-function result, and the resulting means and variances are substituted into (13) to compute the oracle forgetting factor.Because these expressions depend on clusters rather than individual objects, the appendix confirms the assumed block structure of both matrices.Source: Appendix A · p. 37
Loading 1104.1990v3…