Evolutionary spectral clustering by incorporating temporal smoothness

Yun Chi, Xiaodan Song, Dengyong Zhou, Koji Hino, Belle L. TsengKDD 2007 · DOI

TL;DR

This paper introduces two novel frameworks for "evolutionary spectral clustering" that adapt to changing data over time by incorporating "temporal smoothness." By balancing current data relevance with historical consistency, these methods produce more robust and stable clustering results, particularly for dynamic data streams like web content or sensor data.

What Problem Does This Paper Address?

Many real-world applications involve data that changes over time, such as dynamic web content, evolving social networks, or sensor readings from moving objects. Traditional clustering algorithms often struggle with this "concept drift" and "short-term variations" (noise). Simply aggregating all historical data can lead to outdated clusters, while ignoring history makes the clustering overly sensitive to noise. The challenge is to develop clustering methods that can adapt to gradual changes (concept drift) while remaining stable and not drastically jumping between clusterings due to minor fluctuations. This paper tackles this by proposing methods that explicitly incorporate a measure of "temporal smoothness" into the clustering objective.

Methods

The core contribution is the development of two evolutionary spectral clustering frameworks: Preserving Cluster Quality (PCQ) and Preserving Cluster Membership (PCM). Both frameworks build upon spectral clustering, which leverages the eigenvectors of a similarity matrix to perform clustering.

  • Evolutionary Framework: The key innovation is defining a new cost function that combines a "snapshot cost" (how well the current clustering fits the current data) with a "temporal cost" (how consistent the current clustering is with past data or clusterings). This is achieved by introducing a parameter $\alpha$ to balance these two costs.
  • PCQ Framework: This framework measures temporal cost by evaluating how well the current clustering partition fits historical data. It essentially asks: "If I applied today's cluster assignments to yesterday's data, how good would that clustering be?" This is formulated by incorporating historical similarity matrices into the objective function.
  • PCM Framework: This framework measures temporal cost by directly comparing the current clustering partition with the historical clustering partition. It asks: "How much has my cluster assignment changed from last time?" This is achieved by measuring the distance between the eigenvector spaces of consecutive time steps.
  • Spectral Clustering Basis: Both frameworks leverage spectral clustering, which typically involves computing eigenvectors of a similarity matrix (often derived from data features or pairwise affinities). The paper proposes solutions to relaxed versions of their evolutionary spectral clustering problems by finding eigenvectors of modified similarity matrices.
  • Connection to K-Means: The authors demonstrate that their spectral clustering formulations are closely related to evolutionary k-means clustering, showing that their methods can provide solutions to the k-means problem under similar evolutionary constraints.

Datasets

  • Synthetic Data: The authors use synthetic datasets to demonstrate the properties of their algorithms. This includes:
  • A stationary case with Gaussian noise.
  • A non-stationary case with concept drift (rotation of data points).
  • A toy example with changing cluster numbers.
  • Real Blog Data: A dataset of blog interlinks collected over 63 weeks from NEC's in-house blog crawler. This dataset contains approximately 148,681 entry-to-entry links among 407 blogs, with known content-based groupings (technology vs. politics). This dataset is used to evaluate the algorithms in a realistic, evolving scenario.

Key Insights and Ideas

  • Balancing Act: The core idea of balancing current relevance (snapshot cost) with historical consistency (temporal cost) is crucial for handling evolving data. The parameter $\alpha$ provides a tunable knob to control this trade-off.
  • Temporal Smoothness is Key: Explicitly penalizing drastic changes in clustering between time steps leads to more stable and interpretable results, especially in the presence of noise or gradual drift.
  • Spectral Clustering's Adaptability: Spectral clustering, with its foundation in graph theory and eigenvector analysis, provides a flexible framework for incorporating these temporal smoothness constraints.
  • PCM vs. PCQ Nuances: While both frameworks aim for temporal smoothness, PCM (Preserving Cluster Membership) is shown to be more robust to noise and drastic changes in cluster assignments, as it directly penalizes changes in the eigenvector space, whereas PCQ relies on historical data fitting.
  • Generalization: The proposed frameworks can handle variations in the number of clusters and the insertion/removal of data points over time, making them applicable to more complex real-world scenarios.

Key Results

  • Improved Stability: Experiments on synthetic and real blog data show that the proposed evolutionary spectral clustering methods (both PCQ and PCM) produce significantly more stable and consistent clustering results compared to non-evolutionary baselines (like aggregating all data or clustering each time step independently).
  • Robustness to Noise: The evolutionary methods are less sensitive to short-term noise, leading to lower temporal costs and smoother cluster evolution.
  • Adaptability to Drift: The methods effectively adapt to long-term concept drifts, maintaining reasonable cluster quality even when data characteristics change.
  • Trade-off Control: The parameter $\alpha$ effectively controls the trade-off between snapshot cost and temporal cost, allowing users to prioritize current accuracy or historical consistency. For example, increasing $\alpha$ leads to better snapshot quality at the expense of temporal smoothness.
  • Blog Data Performance: On the NEC blog data, the evolutionary spectral clustering algorithms (specifically NC-based PCQ and PCM) significantly outperformed non-evolutionary baselines (ACC and IND) across various performance metrics, including snapshot cost, temporal cost, overall cost, and error compared to ground truth.

Limitations and Future Work

  • Computational Complexity: While the paper provides solutions to relaxed versions of the problems, spectral clustering itself can be computationally intensive, especially for very large datasets. The paper mentions that their solutions are practical ways of obtaining final clusters and upper bounds.
  • Parameter Tuning: The choice of $\alpha$ is crucial for balancing snapshot and temporal costs. While experiments show its effect, optimal selection might require domain knowledge or further automated methods.
  • Heuristic Solutions for Node Changes: The proposed methods for handling node insertion/removal are heuristic. Further research could explore more principled approaches.
  • Generalization to More Complex Temporal Dynamics: The current frameworks primarily focus on pairwise temporal smoothness (t vs. t-1). Extending this to capture more complex temporal dependencies or non-linear drifts could be a future direction.
  • Automated Cluster Number Selection: While the frameworks can handle varying cluster numbers, integrating robust automated methods for determining the optimal number of clusters at each time step would enhance their practical utility.

Summary updated

BibTeX
@inproceedings{chi2007evolutionary,
  author = {Yun Chi and Xiaodan Song and Dengyong Zhou and Koji Hino and Belle L. Tseng},
  title = {{Evolutionary spectral clustering by incorporating temporal smoothness}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2007},
  doi = {10.1145/1281192.1281212},
}
Figure