A New Simplex Sparse Learning Model to Measure Data Similarity for Clustering

Jin Huang, Feiping Nie, Heng Huang

Abstract

Similarity graph construction is a fundamental step in many machine learning algorithms, yet traditional methods like $k$-nearest neighbors and Gaussian kernels are highly sensitive to hyperparameter selection. This paper introduces Simplex Sparse Representation (SSR), a parameter-free model that represents each data point as a sparse linear combination of others under simplex constraints. By leveraging non-negativity and sum-to-one constraints, SSR automatically identifies optimal local neighborhoods, ensuring robustness to noise and scale variations. Experimental results across ten diverse datasets demonstrate that SSR consistently outperforms existing methods in clustering accuracy and graph quality.

Introduction

Many unsupervised and semi-supervised learning techniques, including spectral clustering and manifold learning, rely on an underlying similarity graph to capture the manifold structure of data. The performance of these methods is often bottlenecked by the quality of the graph construction. Traditional approaches require manual tuning of parameters such as the number of neighbors ($k$) or kernel width ($\sigma$), which is challenging in the presence of multi-scale data or outliers. We propose SSR to address these limitations by formulating similarity as a self-adjusting sparse reconstruction problem.

Methodology

The Simplex Sparse Representation (SSR) Model

The core of our approach is to represent each data point $x_i$ as a linear combination of the remaining points $X_{-i}$. Unlike standard sparse coding, we impose a simplex constraint on the reconstruction weights $\alpha_i$:

  1. Non-negativity: $\alpha_i \ge 0$
  2. Sum-to-one: $\mathbf{1}^T \alpha_i = 1$

These constraints offer several theoretical advantages. First, the geometry of the simplex naturally induces sparsity without requiring an explicit $\ell_1$ penalty parameter. Second, the sum-to-one constraint provides shift invariance, ensuring that the similarity measure is robust to global translations of the dataset.

Figure 1: Coefficient histogram comparing the sparsity of SSR and STSC. SSR exhibits a significantly higher frequency of zero coefficients, leading to a cleaner similarity graph.

Optimization via Accelerated Projected Gradient

To solve the SSR objective efficiently, we employ an Accelerated Projected Gradient (APG) algorithm. The projection onto the simplex is handled via a Lagrangian formulation and a Newton root-finding method, achieving quadratic convergence ($O(t^2)$). This allows the model to scale to high-dimensional data, typically converging in fewer than 30 iterations.

Experimental Evaluation

We evaluated SSR on a diverse set of benchmarks, including face recognition datasets (AR, AT&T, JAFFE, PIE, UMIST), handwritten digits (MNIST), and UCI datasets (Abalone, Ecoli, Scale). SSR was compared against $k$-means, Non-negative Matrix Factorization (NMF), Normalized Cut (NCut), and Self-Tuning Spectral Clustering (STSC).

Results and Discussion

SSR demonstrated superior performance across all metrics, including Accuracy, Normalized Mutual Information (NMI), and Purity. Notably, on the JAFFE face dataset, SSR achieved a clustering accuracy of 90.2%, a significant improvement over STSC's 81.3%.

Table 1: Clustering accuracy comparison across nine real-world datasets. SSR consistently achieves the highest accuracy (bolded) compared to baseline methods.

The visualization of similarity coefficients confirms that SSR produces "sharper" graphs than competing methods. By effectively ignoring outliers and focusing on the most representative neighbors, SSR provides a more reliable foundation for subsequent clustering steps.

Conclusion

Simplex Sparse Representation offers a robust, parameter-free alternative for similarity graph construction. By integrating sparsity and shift invariance directly into the optimization constraints, SSR eliminates the "guessing game" of hyperparameter tuning while delivering state-of-the-art clustering performance. Future work will explore the application of SSR to semi-supervised learning and the incorporation of group-level structural sparsity.

Summary updated

Abstract

The Laplacian matrix of a graph can be used in many areas of mathematical research and has a physical interpretation in various theories. However, there are a few open issues in the Laplacian graph construction: (i) Selecting the appropriate scale of analysis, (ii) Selecting the appropriate number of neighbors, (iii) Handling multiscale data, and, (iv) Dealing with noise and outliers. In this paper, we propose that the affinity between pairs of samples could be computed using sparse representation with proper constraints. This parameter free setting automatically produces the Laplacian graph, leads to significant reduction in computation cost and robustness to the outliers and noise. We further provide an efficient algorithm to solve the difficult optimization problem based on improvement of existing algorithms. To demonstrate our motivation, we conduct spectral clustering experiments with benchmark methods. Empirical experiments on 9 data sets demonstrate the effectiveness of our method.
BibTeX
@inproceedings{huang2015new,
  author = {Jin Huang and Feiping Nie and Heng Huang},
  title = {{A New Simplex Sparse Learning Model to Measure Data Similarity for Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure