Clustering with t-SNE, Provably
Кластеризация с помощью t-SNE: строгое обоснование
2019-01-01
SCID: 54.1/m4qv2tbc
Discuss with AI
cluster recoveryearly exaggerationspectral clusteringswiss rollt-SNE
Figures from the paper
Abstract (AI)
t-distributed stochastic neighborhood embedding (t-SNE), a clustering and visualization method proposed by van der Maaten and Hinton in 2008, has rapidly become a standard tool in a number of natural sciences. Despite its overwhelming success, there is a distinct lack of mathematical foundations, and the inner workings of the algorithm are not well understood. The purpose of this paper is to prove that t-SNE is able to recover well-separated clusters; more precisely, we prove that t-SNE in the “early exaggeration” phase, an optimization technique proposed by van der Maaten and Hinton [ J. Mach. Learn. Res., 9 (2008), pp. 2579--2605] and van der Maaten [ J. Mach. Learn. Res., 15 (2014), pp. 3221--3245], can be rigorously analyzed. As a byproduct, the proof suggests novel ways for setting the exaggeration parameter $\alpha$ and step size $h$. Numerical examples illustrate the effectiveness of these rules: in particular, the quality of embedding of topological structures (e.g., the swiss roll) improves. We also discuss a connection to spectral clustering methods.
Key Findings
1
Numerical examples show that the proposed parameter-setting rules improve embeddings of topological structures such as the swiss roll.
2
The analysis establishes conditions under which early-exaggeration t-SNE can separate well-separated clusters.
3
The paper identifies a connection between early-exaggeration t-SNE and spectral clustering methods.
4
The paper provides a rigorous mathematical analysis of t-SNE’s early exaggeration phase for recovering well-separated clusters.
5
The proof suggests novel rules for selecting the exaggeration parameter α and optimization step size h.
Research Object
t-SNE in the early exaggeration phase applied to well-separated clusters and topological data structures
Research Subject
Theoretical cluster-recovery guarantees and embedding behavior of t-SNE, including the effects of the exaggeration parameter and step size
Publication Details
Publication Date
2019-01-01
Journal
Publisher
ISSN
Cited by
315
Open access PDF
Access Type
Author Information
Download PDF
Subscribe to digest
References available in scid.ai1
Cited by8
The art of using t-SNE for single-cell transcriptomics2019
Understanding How Dimension Reduction Tools Work: An Empirical Approach to Deciphering t-SNE, UMAP, TriMAP, and PaCMAP for Data Visualization2020
t-viSNE: Interactive Assessment and Interpretation of t-SNE Projections2020
Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data2021
Visualizing Time Series Data with Temporal Matching Based t-SNE2019
Dimensionality Reduction via Dynamical Systems: The Case of t-SNE2022
Federated t-SNE and UMAP for Distributed Data Visualization2025
Bridging urban theory and artificial intelligence: a multi-agent recommendation system for sustainable city development2026