基于谱聚类：聚类完成后如何更新数据集且无需重新全量聚类？

Great question! Updating spectral clustering without re-running the entire pipeline is a common pain point—since spectral clustering relies on similarity matrices, Laplacian decomposition, and downstream clustering, we need targeted tweaks to each step instead of starting from scratch. Here are practical, actionable approaches:

1. Incrementally Update the Similarity & Laplacian Matrices #

The foundation of spectral clustering is the similarity matrix A and its corresponding Laplacian matrix L (either unnormalized L = D - A or normalized L = I - D^{-1/2}AD^{-1/2}, where D is the degree matrix). When adding new samples:

• Compute only new similarity entries: If you add m new samples, you don’t need to recompute the entire A matrix. Instead, build:

  A' = [[A,  B],
        [B^T, C]]
  

  Where B is an n×m matrix of similarity scores between existing n samples and new m samples, and C is an m×m matrix of similarities among the new samples. Use the same similarity metric (e.g., RBF kernel, k-nearest neighbors) you used for the original dataset.
• Update the degree matrix D incrementally: For existing samples, add the sum of their corresponding column in B to their degree values. For new samples, their degrees are the row sums of C.
• Derive the new Laplacian L': Using the updated A' and D', compute L' without reprocessing the original data.

2. Approximate Feature Vector Updates (Avoid Full Eigen-decomposition) #

The most computationally expensive step is decomposing the Laplacian to get the top k eigenvectors (used for downstream clustering). Instead of re-decomposing the full L', use these tricks:

• Power Iteration Warm-Start: Use the original top k eigenvectors as an initial guess for the new L'. Run a few iterations of power iteration to refine the eigenvectors—this is far faster than full decomposition, especially when m << n.
• Low-Rank Approximation: If L' is approximately low-rank (common in many real-world datasets), use techniques like the Sherman-Morrison formula to update the eigenvectors based on the incremental changes to L.

3. Assign New Samples to Existing Clusters (Semi-Supervised Approach) #

If you’re adding a small batch of samples and don’t expect the overall cluster structure to shift drastically, skip re-computing eigenvectors entirely:

• Compute the spectral embedding for new samples: For each new sample x, calculate its similarity vector s to all existing samples. For the normalized Laplacian, the embedding of x can be approximated as:

  u_x ≈ D^{-1/2} * s^T
  

  Where D is the original degree matrix (you can adjust it slightly if needed, but for small batches, this approximation holds).
• Assign to nearest cluster: Use the existing cluster centers (from the original K-means run on the top k eigenvectors) and assign u_x to the cluster with the smallest Euclidean or cosine distance.

4. Use Specialized Incremental Spectral Clustering Algorithms #

For large-scale or frequent updates, look into research-backed incremental methods:

• Nyström-Based Incremental Updates: The Nyström method approximates the full similarity matrix using a subset of samples. When adding new samples, you can either include them in the Nyström subset or update the approximation using the new similarity entries, then recompute the approximate eigenvectors.
• Kernel-Based Incremental Spectral Clustering: Some algorithms maintain an updated kernel matrix incrementally and use online eigen-decomposition techniques to track the top eigenvectors as new data arrives.

Key Caveats #

• If the new samples drastically change the data distribution (e.g., introducing entirely new clusters), incremental methods will fail—you’ll need to re-run full spectral clustering.
• Always validate the updated clusters using metrics like silhouette score or mutual information to ensure quality hasn’t degraded.

内容的提问来源于stack exchange，提问作者J.LIN