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

To appear in Data Mining and Knowledge Discovery, MATLAB toolbox available at http://tbayes.eecs.umich.edu/xukevin/affect

References in corpus (3)

• Modularity and community structure in networks
• Natural Scales in Geographical Patterns
• GED: the method for group evolution discovery in social networks

Cited by in corpus (19)

• Dynamic stochastic blockmodels for time-evolving social networks
• Consistent estimation of dynamic and multi-layer block models
• Operational Framework for Recent Advances in Backtracking Search Optimisation Algorithm: A Systematic Review and Performance Evaluation
• Multi-layer graph analysis for dynamic social networks
• Dynamic Clustering via Asymptotics of the Dependent Dirichlet Process Mixture
• A Regularized Graph Layout Framework for Dynamic Network Visualization
• Evolutionary Self-Expressive Models for Subspace Clustering
• Evolutionary Robust Clustering Over Time for Temporal Data
• An embedding-based distance for temporal graphs
• Variational Inference for Latent Space Models for Dynamic Networks
• Identification of Dynamic functional brain network states Through Tensor Decomposition
• Bayesian Overlapping Community Detection in Dynamic Networks
• Evolutionary Clustering of Streaming Trajectories
• Neural Ordinary Differential Equation Model for Evolutionary Subspace Clustering and Its Applications
• Clustering evolving data using kernel-based methods
• Clust-Splitter - an Efficient Nonsmooth Optimization-Based Algorithm for Clustering Large Datasets
• Evolutionary Clustering via Message Passing
• LSTM-Assisted Evolutionary Self-Expressive Subspace Clustering
• Adaptive Shrinkage Estimation for Streaming Graphs