65
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I would have thought that the trick is to describe the clusters based on the original variables, rather than the variables in the reduced space. $\endgroup$ – Tim Feb 23 '17 at 5:02
  • 1
    $\begingroup$ Right, but absent a concise, intuitive description of what objective the cluster assignment algorithm minimizes, I may be open to charges of choosing a clustering algorithm that facilitates getting the results that I want. $\endgroup$ – generic_user Feb 23 '17 at 15:28
  • 1
    $\begingroup$ For some caveats and nice visuals on t-SNE also have a look at distill.pub/2016/misread-tsne $\endgroup$ – Tom Wenseleers Mar 19 '18 at 15:33
82
$\begingroup$

The problem with t-SNE 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.

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).

Input data

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

EM clustering

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

t-SNE p=40

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:

t-SNE p=20

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.

t-SNE p=80

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:

Fish

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):

SNE fish

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:

t-SNE fish

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:

Fish, t-SNE, with original coordinates as initialization

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the answer. I can imagine neighborhood-based adaptive clustering methods, but are there any specific well-developed ones that you could recommend? $\endgroup$ – generic_user Mar 1 '17 at 0:01
  • 1
    $\begingroup$ CHAMAELEON is probably the most cited, but it seems there is only a binary available for the core step. The idea sounds nice, but you'll quickly experience the same effects that t-SNE makes visible. Such as the tendency to "flock" as seen with p=20, problems with hubs and anti-hubs, etc. $\endgroup$ – Erich Schubert Mar 1 '17 at 0:15
  • 2
    $\begingroup$ @AlexR: Perplexity is used to compute the similarities in the high-dimensional space that t-sne is then trying to match in 2D. Changing perplexity means changing similarities, so I don't see how comparing resulting KL divergences can be meaningful. $\endgroup$ – amoeba Jul 5 '17 at 11:50
  • 1
    $\begingroup$ @AlexR. "Only the conditional probability of the lower dimensional space depends on the perplexity" -- this statement is wrong. Perplexity is used to choose sigmas needed for eq (1), so it influences cond. probs. in the full space. $\endgroup$ – amoeba Jul 5 '17 at 18:35
  • 1
    $\begingroup$ For some caveats and nice visuals on t-SNE also have a look at distill.pub/2016/misread-tsne $\endgroup$ – Tom Wenseleers Mar 19 '18 at 15:33
29
$\begingroup$

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:

MNIST t-SNE

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):

MNIST t-SNE with late exaggeration

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:

enter image description here

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:

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ And for the last example, isn't that essentially what @ErichSchubert observed above: you can get visually "pleasing" results - that are obviously wrong? As with perplexity 20? That tSNE likes separating parts (as in the fish) that weren't separated? So do you know the clusters you see are indeed separate clusters? I don't like this "black box" in there. Yes, we tend to believe such plots more, but what if they are wrong? $\endgroup$ – Anony-Mousse Jun 19 '18 at 19:01
  • 1
    $\begingroup$ Well, tSNE is NN based. An agreement with this is to be expected. tSNE is a good choice to visualize NN. It doesn't preserve similarities well though, so it must be interpreted with care, as I understand. A gap in tSNE does not imply a large distance. $\endgroup$ – Anony-Mousse Jun 19 '18 at 22:35
  • 1
    $\begingroup$ +1 Curious how UMAP performs compared with t-SNE. $\endgroup$ – Paul Oct 16 '18 at 23:34
  • 1
    $\begingroup$ @Paul: the author claims the superiority of UMAP, in terms of computation time, it is. On MNIST dataset, I find UMAP generates better embedding than t-SNE, but not sure on other datasets. As far as I'm aware of, there is recently a CUDA version of t-SNE, which is much faster than the previous fastest t-SNE, but I couldn't install and test. $\endgroup$ – SiXUlm Apr 3 at 10:26
  • 1
    $\begingroup$ @SiXUlm Yes, but as you said, setting up CUDA stuff can be a pain, whereas FIt-SNE is super easy to start using. $\endgroup$ – amoeba Apr 3 at 13:30
6
$\begingroup$

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. Original image

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

$\endgroup$
  • 7
    $\begingroup$ If you choose such high perplexities, it's not really tSNE anymore. Every point is approximately everyday neighbor. It's no longer local. Yes, a 2d image can then be approximately reconstructed, because it's 2d. But not doing the entire thing at all is easier. $\endgroup$ – Anony-Mousse Jun 19 '18 at 18:52
  • 1
    $\begingroup$ My opinion is tSNE with large perplexity can reconstruct the global topology. 2d image is an example because its intrinsic dimensionality is 2. Real application of tSNE should select proper perplexity according to the purpose to capture the local or global characteristics. $\endgroup$ – renxwise Jun 20 '18 at 23:08
  • 1
    $\begingroup$ Perplexities this high mean you use an overly large "kernel", and effectively just use distances. It then likely degenerates to an approximate and very expensive MDS. Just use MDS then. SNE/tSNE really should be used with small perplexities, and local neighborhoods. $\endgroup$ – Erich Schubert Jun 21 '18 at 11:14
  • 2
    $\begingroup$ Exactly. When the perplexity is large enough, tSNE is indeed approximate to MDS, which illustrates that tSNE can also capture the global structure. Thus, statements that tSNE can only capture local structures are not correct. Different from MDS, tSNE can balance between local and global structures via the selection of perplexity. Obviously, selection of perplexity is dataset-dependent. $\endgroup$ – renxwise Jun 22 '18 at 11:44
  • $\begingroup$ Is there any rule of thumb for choosing plausible perplexity ? $\endgroup$ – Catbuilts Apr 1 at 3:45
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are there parameters that will influence t-SNE's likelihood of preserving distances? $\endgroup$ – Keith Hughitt Jan 19 at 1:00
  • $\begingroup$ Those are not consensus clustering algorithms. Consensus clustering is a type of ensembl learning that aggregates the results of repeating the clustering algorithm with some variation in parameters or input data, to obtain a final clustering result. You can use consensus clustering approaches with spectral clustering or GMM or indeed any clustering algorithm, but my point in your terminology is a little off, that's all :) $\endgroup$ – Christopher John Jan 24 at 11:17
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why do (did) you trust "the persistence diagram" more than UMAP? I don't think that looking at the persistence diagram can be described as "looking at the original data"... $\endgroup$ – amoeba Apr 3 at 8:49
  • $\begingroup$ You are correct. The persistence diagram only shows some characteristics of the original data, most often, connected components, 1-dimensional holes, and much more rare, 2 or more-dimensional holes due to expensive computation. So I should have said that I can only partially "look" at the original data by looking at the corresponding persistence diagram. But I can trust what I observe from this persistence diagram because it is directly built from the original data. $\endgroup$ – SiXUlm Apr 3 at 10:06
  • $\begingroup$ By contrast, by using UMAP or any other dimension reduction techniques, we only work with a projected/modified version of the original data. As the most voted answer pointed out, the clustering may be different for the different choices of parameters. $\endgroup$ – SiXUlm Apr 3 at 10:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.