Clustering on the output of t-SNE

Question

I've got an application where it'd be handy to cluster a noisy dataset before looking for subgroup effects within the clusters. I first looked at PCA, but it takes ~30 components to get to 90% of the variability, so clustering on just a couple of PC's will throw away a lot of information.

I then tried t-SNE (for the first time), which gives me an odd shape in two dimensions that is very amenable to clustering via k-means. What's more, running a random forest on the data with the cluster assignment as the outcome shows that the clusters have a fairly sensible interpretation given the context of the problem, in terms of the variables that make up the raw data.

But if I'm going to report on these clusters, how do I describe them? K-means clusters on principal components reveal individuals who are nearby to one another in terms of the derived variables that comprise X% of the variance in the dataset. What equivalent statement can be made about t-SNE clusters?

Perhaps something to the effect of:

t-SNE reveals approximate contiguity in an underlying high-dimensional manifold, so clusters on the low-dimensional representation of the high-dimensional space maximize the "likelihood" that contiguous individuals will not be in the same cluster

Can anyone propose a better blurb than that?

Answer 1

The problem with t-SNE (and UMAP) is that it does not preserve distances nor density. It only to some extent preserves nearest-neighbors. The difference is subtle, but affects any density- or distance based algorithm.

While clustering after t-SNE will sometimes (often?) work, you will never know whether the "clusters" you find are real, or just artifacts of t-SNE. You will not be able to explain the clusters. You may just be seeing 'shapes in clouds'. The use of both t-SNE and UMAP is now frequently seen as problematic because of distortions leading to incorrect conclusions, e.g.,

The specious art of single-cell genomics, Tara Chari and Lior Pachter. PLOS Computational Biology. DOI:10.1371/journal.pcbi.1011288

To see this effect, simply generate a multivariate Gaussian distribution. If you visualize this, you will have a ball that is dense and gets much less dense outwards, with some outliers that can be really far away.

Now run t-SNE on this data. You will usually get a circle of rather uniform density. If you use a low perplexity, it may even have some odd patterns in there. But you cannot really tell apart outliers anymore.

Now lets make things more complicated. Let's use 250 points in a normal distribution at (-2,0), and 750 points in a normal distribution at (+2,0).

This is supposed to be an easy data set, for example with EM:

If we run t-SNE with default perplexity of 40, we get an oddly shaped pattern:

Not bad, but also not that easy to cluster, is it? You will have a hard time finding a clustering algorithm that works here exactly as desired. And even if you would ask humans to cluster this data, most likely they will find much more than 2 clusters here.

If we run t-SNE with a too small perplexity such as 20, we get more of these patterns that do not exist:

This will cluster e.g. with DBSCAN, but it will yield four clusters. So beware, t-SNE can produce "fake" patterns!

The optimum perplexity appears to be somewhere around 80 for this data set; but I don't think this parameter should work for every other data set.

Now this is visually pleasing, but not better for analysis. A human annotator could likely select a cut and get a decent result; k-means however will fail even in this very very easy scenario! You can already see that density information is lost, all data seems to live in area of almost the same density. If we would instead further increase the perplexity, the uniformity would increase, and the separation would reduce again.

In conclusions, use t-SNE for visualization (and try different parameters to get something visually pleasing!), but rather do not run clustering afterwards, in particular do not use distance- or density based algorithms, as this information was intentionally (!) lost. Neighborhood-graph based approaches may be fine, but then you don't need to first run t-SNE beforehand, just use the neighbors immediately (because t-SNE tries to keep this nn-graph largely intact).

More examples

These examples were prepared for the presentation of the paper (but cannot be found in the paper yet, as I did this experiment later)

Erich Schubert, and Michael Gertz.
Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection – A Remedy Against the Curse of Dimensionality?
In: Proceedings of the 10th International Conference on Similarity Search and Applications (SISAP), Munich, Germany. 2017

First, we have this input data:

As you may guess, this is derived from a "color me" image for kids.

If we run this through SNE (NOT t-SNE, but the predecessor):

Wow, our fish has become quite a sea monster! Because the kernel size is chosen locally, we lose much of the density information.

But you will be really surprised by the output of t-SNE:

I have actually tried two implementations (the ELKI, and the sklearn implementations), and both produced such a result. Some disconnected fragments, but that each look somewhat consistent with the original data.

Two important points to explain this:

1. SGD relies on an iterative refinement procedure, and may get stuck in local optima. In particular, this makes it hard for the algorithm to "flip" a part of the data that it has mirrored, as this would require moving points through others that are supposed to be separate. So if some parts of the fish are mirrored, and other parts are not mirrored, it may be unable to fix this.

2. t-SNE uses the t-distribution in the projected space. In contrast to the Gaussian distribution used by regular SNE, this means most points will repel each other, because they have 0 affinity in the input domain (Gaussian gets zero quickly), but >0 affinity in the output domain. Sometimes (as in MNIST) this makes nicer visualization. In particular, it can help "splitting" a data set a bit more than in the input domain. This additional repulsion also often causes points to more evenly use the area, which can also be desirable. But here in this example, the repelling effects actually cause fragments of the fish to separate.

We can help (on this toy data set) the first issue by using the original coordinates as initial placement, rather than random coordinates (as usually used with t-SNE). This time, the image is sklearn instead of ELKI, because the sklearn version already had a parameter to pass initial coordinates:

As you can see, even with "perfect" initial placement, t-SNE will "break" the fish in a number of places that were originally connected because the Student-t repulsion in the output domain is stronger than the Gaussian affinity in the input space.

As you can see, t-SNE (and SNE, too!) are interesting visualization techniques, but they need to be handled carefully. I would rather not apply k-means on the result! because the result will be heavily distorted, and neither distances nor density are preserved well. Instead, rather use it for visualization.

Answer 2

I would like to provide a somewhat dissenting opinion to the well argued (+1) and highly upvoted answer by @ErichSchubert. Erich does not recommend clustering on the t-SNE output, and shows some toy examples where it can be misleading. His suggestion is to apply clustering to the original data instead.

use t-SNE for visualization (and try different parameters to get something visually pleasing!), but rather do not run clustering afterwards, in particular do not use distance- or density based algorithms, as this information was intentionally (!) lost.

I am well aware of the ways in which t-SNE output may be misleading (see https://distill.pub/2016/misread-tsne/) and I agree that it can produce weird results in some situations.

But let us consider some real high-dimensional data.

Take MNIST data: 70000 single-digit images. We know that there are 10 classes in the data. These classes appear well-separated to a human observer. However, clustering MNIST data into 10 clusters is a very difficult problem. I am not aware of any clustering algorithm that would correctly cluster the data into 10 clusters; more importantly, I am not aware of any clustering heuristic that would indicate that there are 10 (not more and not less) clusters in the data. I am certain that most common approaches would not be able to indicate that.

But let's do t-SNE instead. (One can find many figures of t-SNE applied to MNIST online, but they are often suboptimal. In my experience, it's necessary to run early exaggeration for quite some time to get good results. Below I am using perplexity=50, max_iter=2000, early_exag_coeff=12, stop_lying_iter=1000). Here is what I get, on the left unlabeled, and on the right colored according to the ground truth:

I would argue that the unlabeled t-SNE representation does suggest 10 clusters. Applying a good density based clustering algorithm such as HDBSCAN with carefully selected parameters will allow to cluster these 2D data into 10 clusters.

In case somebody will doubt that the left plot above indeed suggests 10 clusters, here is what I get with the "late exaggeration" trick where I additionally run max_iter=200 iterations with exaggeration=4 (this trick is suggested in this great paper: https://arxiv.org/abs/1712.09005):

Now it should be very obvious that there are 10 clusters.

I encourage everybody who thinks clustering after t-SNE is a bad idea to show a clustering algorithm that would achieve comparably good result.

And now even more real data.

In the MNIST case we know the ground truth. Consider now some data with unknown ground truth. Clustering and t-SNE are routinely used to describe cell variability in single cell RNA-seq data. E.g. Shekhar et al. 2016 tried to identify clusters among 27000 retinal cells (there are around 20k genes in the mouse genome so dimensionality of the data is in principle about 20k; however one usually starts with reducing dimensionality with PCA down to 50 or so). They do t-SNE and they separately do clustering (a complicated clustering pipeline followed by some cluster merges etc.). The final result looks pleasing:

The reason it looks so pleasing is that t-SNE produces clearly distinct clusters and clustering algorithm yields exactly the same clusters. Nice.

However, if you look in the supplementaries you will see that the authors tried many different clustering approaches. Many of them look awful on the t-SNE plot because e.g. the big central cluster gets split into many sub-clusters:

So what do you believe: the output of your favourite clustering algorithm together with your favourite heuristic for identifying the number of clusters, or what you see on the t-SNE plot? To be honest, despite all the shortcomings of t-SNE, I tend to believe t-SNE more. Or in any case, I don't see why I should believe it less.

Answer 3

I think with large perplexity t-SNE can reconstruct the global topology, as indicated in https://distill.pub/2016/misread-tsne/.

From the fish image, I sampled 4000 points for t-SNE. With a large perplexity (2000), the fish image was virtually reconstructed.

Here is the original image.

Here is the image reconstructed by t-SNE with perplexity = 2000.

Answer 4

Based on the mathematical evidence which we have, this method could technically preserve distances! why do you all ignore this feature! t-SNE is converting the high-dimensional Euclidean distances between samples into conditional probabilities which represent similarities. I have tried t-SNE with more than 11,000 samples (in genomics context) in parallel with different consensus clustering algorithms including Spectral clustering, Affinity and importantly with GMM clustering (which is a density based clustering algorithm!). As a result, I found very a good concordant result between two approaches (t-SNE vs. consensus clustering algorithms). I believe integrating t-SNE with consensus clustering algorithms could provide the best evidence of existing local and global structures of data.

Answer 5

You could try the DBSCAN clustering algorithm. Also, the perplexty of tsne should be about the same size as the smallest expected cluster.

Answer 6

Personally, I have experienced this once, but not with t-SNE or PCA. My original data is in 15-dimensional space. Using UMAP to reduce it to 2D and 3D embeddings, I got 2 perfectly and visually seperable clusters on both 2D and 3D plots. Too good to be true. But when I "looked" at the orginal data from the persistence diagram, I realized that there are much more "significant" clusters, not just 2.

Clustering on the output of the dimension reduction technique must be done with a lot of caution, otherwise any interpretation can be very misleading or wrong because reducing dimension will surely result in feature loss (maybe noisy or true features, but a priori, we don't know which). In my opinion, you can trust/interpret the clusters, if:

• The clusters in the projected data correspond/confirm to some classification defined a priori (think of MNIST dataset, where the clusters of projected data match very nicely with the classification of digits), and/or,

• You can confirm the presence of these clusters in the original data using other methods, like persistence diagrams. Counting only the number of connected components can be done in a quite reasonable amount of time.

Answer 7

for anyone who is looking into similar questions, I have performed DBSCAN(metric using cosine similarity) on word embeddings of 50 dimensions as well as tsne 2d dimensions. For my corpus containing 1600 lines, I have exactly the same clustering groups (same number of cluster, same items in the groups, same number of noises).

Sometimes theoretically the problem becomes too complex and you just have to take the engineering approach.