Achieving stable subspace clustering by post-processing generic clustering results

Duc-Son Pham, Ognjen Arandjelovic, Svetha Venkatesh

Introduction

Subspace clustering is a critical unsupervised learning task based on the premise that high-dimensional data, such as video frames or facial images, resides within a union of low-dimensional subspaces. Sparse Subspace Clustering (SSC) has emerged as a state-of-the-art method for this task. However, SSC suffers from significant sensitivity to parameter tuning; suboptimal initial settings can lead to skewed subspace models and a subsequent cycle of misclassification. This paper proposes a robust post-processing framework designed to refine "good enough" clustering results into highly accurate ones by identifying and correcting misclassified data points.

Methodology: Two-Step Refinement

The proposed method introduces a two-stage refinement process to enhance clustering stability and accuracy.

1. Stable Subspace Estimation

Standard Principal Component Analysis (PCA) can be heavily influenced by outliers within a cluster. To mitigate this, the authors employ a technique inspired by "stability selection." Instead of computing a subspace from the entire cluster, the algorithm repeatedly draws random subsets of the data. By averaging the projection matrices derived from these subsets, the influence of misclassified "outlier" points is filtered out, resulting in a more accurate representation of the true underlying subspace.

2. Dominant Nearest Subspace Clustering

With stable subspace models established, the algorithm re-evaluates the assignment of each data point. To ensure the refinement is conservative and does not disrupt correctly clustered points, a "dominance" rule is applied. A point is only reassigned to a different cluster if it fits the new subspace significantly better than its current one, governed by a sensitivity parameter $\eta$. This approach prioritizes stability, preventing a "cascade" of erroneous reassignments.

Key Results and Analysis

Convergence and Error Reduction

A primary advantage of the random sampling scheme is its ability to achieve lower projection errors compared to direct PCA. As shown in the experimental results, the random sampling approach converges quickly—typically within 40 to 60 iterations—and consistently reaches a lower error floor than standard methods.

Figure 1: Projection Norm Error vs. Iterations, comparing Random Sampling to Direct PCA. The random sampling approach achieves a lower error floor.

Performance on Motion Segmentation

The method was evaluated on the Hopkins 155 motion segmentation dataset. The refinement process proved highly effective at correcting initial errors. Notably, the algorithm successfully identified and reassigned numerous misclassified points while introducing virtually no new errors, significantly improving the overall clustering quality.

Figure 2: Correct vs. False Re-assignments across motion data instances. The high number of correct reassignments compared to negligible false ones highlights the algorithm's precision.

Face Clustering Benchmarks

Tests on the Extended Yale B and CMU PIE datasets further validated the "Stable Subspace" (SSS) approach. In multi-class scenarios (e.g., 8-class Yale B), SSS consistently outperformed standard PCA-based refinement, reducing error rates and improving Normalized Mutual Information (NMI) scores. The results closely approached those of an "Oracle" model, which represents the theoretical limit of subspace estimation using ground-truth labels.

Discussion and Limitations

While the SSS method provides a powerful tool for post-processing, its success depends on the quality of the initial clustering. The authors note that the initial cluster purity should ideally be between 50% and 80% for a stable subspace to emerge. If the initial pass is fundamentally flawed, post-processing cannot recover the true structure. Future research may focus on making parameters like the sampling fraction ($\rho$) and dominance threshold ($\eta$) adaptive to further improve robustness across diverse datasets.

Conclusion

By leveraging the power of random sampling and conservative reassignment rules, this post-processing technique effectively "cleans up" the noise inherent in standard subspace clustering algorithms. It offers a computationally feasible way to boost the performance of SSC, bringing it closer to theoretical performance limits in real-world computer vision applications.

Summary updated

Abstract

We propose an effective subspace selection scheme as a post-processing step to improve results obtained by sparse subspace clustering (SSC). Our method starts by the computation of stable subspaces using a novel random sampling scheme. Thus constructed preliminary subspaces are used to identify the initially incorrectly clustered data points and then to reassign them to more suitable clusters based on their goodness-of-fit to the preliminary model. To improve the robustness of the algorithm, we use a dominant nearest subspace classification scheme that controls the level of sensitivity against reassignment. We demonstrate that our algorithm is convergent and superior to the direct application of a generic alternative such as principal component analysis. On several popular datasets for motion segmentation and face clustering pervasively used in the sparse subspace clustering literature the proposed method is shown to reduce greatly the incidence of clustering errors while introducing negligible disturbance to the data points already correctly clustered.
BibTeX
@inproceedings{pham2016achieving,
  author = {Duc-Son Pham and Ognjen Arandjelovic and Svetha Venkatesh},
  title = {{Achieving stable subspace clustering by post-processing generic clustering results}},
  booktitle = {IJCNN},
  year = {2016},
  doi = {10.1109/ijcnn.2016.7727496},
}
Figure