# Does nearest neighbour make any sense with t-SNE?

Answers on here have stated that the dimensions in t-SNE are meaningless, and that the distances between points are not a measure of similarity.

However, can we say anything about a point based on it's nearest neighbours in t-SNE space? This answer to why points that are exactly the same are not clustered suggests the ratio of distances between points is similar between lower and higher dimensional representations.

For example, the image below shows t-SNE on one of my datasets (15 classes).

Can I say that cro 479 (top right) is an outlier? Is fra 1353 (bottom left) is more similar to cir 375 than the other images in the fra class, etc? Or could these just be artefacts, e.g. fra 1353 got stuck on the other side of a few clusters and couldn't force its way through to the other fra class?

No, it is not necessary that this is the case, however, this is, in a convoluted way, the goal of T-SNE.

Before getting into the meat of the answer, let's take a look at some basic definitions, both mathematically and intuitively.

Nearest Neighbors: Consider a metric space $\mathbb{R}^d$ and a set of vectors $X_1, ..., X_n \in \mathbb{R}^d$, given a new vector $x \in \mathbb{R}^d$, we want to find the points such that $|| X_1 - x || \le ... \le ||X_n - x ||$. Intuitively, it's just the minimum of the distances using a suitable definition of norm in $\mathbb{R}^d$.

Now coming to whether the nearest neighbors actually matter while applying dimensionality reduction. Usually in my answers, I intend to rationalize something with mathematics, code and intuition. Let us first consider the intuitive aspect of things. If you have a point that is a distance $d$ away from another point, from our understanding of the t-sne algorithm we know that this distance is preserved as we transition into higher dimensions. Let us further assume that a point $y$ is the nearest neighbor of $x$ in some dimension $d$. By definition, there is a relationship between the distance in $d$ and $d + k$. So, we have our intuition which is that the distance is maintained across different dimensions, or at least, that is what we aim for. Let's try to justify it with some mathematics.

In this answer I talk about the math involved in t-sne, albeit not in detail (t-SNE: Why equal data values are visually not close?). What the math here is, is basically maximizing the probability that two points remain close in a projected space as they are in the original space assuming that the distribution of the points is exponential. So, looking at this equation $p_{j | i} = \frac{exp(\frac{-||x_j - x_i||^2}{2\sigma^2})}{\sum_{k \neq i}{exp(\frac{-||x_j - x_i||^2}{2\sigma^2})}}$. Notice that the probability is dependent on the distance between the two points, so the further apart they are, the further apart they get as they get projected to lower dimensions. Notice that if they are far apart in $\mathbb{R}^k$, there is a good chance they will not be close in the projected dimension. So now, we have a mathematical justification as to why the points "should" remain close. But again, since this is an exponential distribution, if these points are significantly far apart, there is no guarantee that the Nearest Neighbors property is maintained, although, this is the aim.

Now finally a neat coding example which demonstrates this concept too.

from sklearn.manifold import TSNE
from sklearn.neighbors import KNeighborsClassifier
X = [[0],[1],[2],[3],[4],[5],[6],[7],[8],[9]]
y = [0,1,2,3,4,5,6,7,8,9]
neighs = KNeighborsClassifier(n_neighbors=3)
neighs.fit(X, y)
X_embedded = TSNE(n_components=1).fit_transform(X)
neighs_tsne = KNeighborsClassifier(n_neighbors=3)
neighs_tsne.fit(X_embedded, y)
print(neighs.predict([[1.1]]))
>>>[0]
print(neighs_tsne.predict([[1.1]]))
>>>[0]


Although this is a very naive example and doesn't reflect the complexity, it does work by experiment for some simple examples.

EDIT: Also, adding some points with respect to the question itself, so it is not necessary that this is the case, it might be, however, rationalizing it through mathematics would prove that you have no concrete outcome (no definitive yes or no).

I hope this cleared up some of your concerns with TSNE.

• Thanks for the good answer. To summarize: Points that have a high similarity have a high probability of staying close. I'm guessing that the perplexity parameter controls how many points are used for the probability calculation, so clusters can become disjoint if perplexity is low. Can you comment on early exaggeration? Also, I assume the probability of points being outliers or misclassified (having all their NN in another class) using the TSNE space, would be increased if they are consistent after multiple TSNE with random initialisation? – geometrikal Aug 28 '17 at 6:40
• Yes, perplexity is one of the major factors which affects how close points stay to each other. Early exaggeration, intuitively is how tight clusters in the original space and how much space there will be between them in the embedded space (so it's a mixture of both perplexity and early exaggeration which affects the distances between points. Regarding your last question, the answer is yes, this is because of the exponentiation of the norm, which could cause issues in the embedding space, so there is a chance of misclassification. – PSub Aug 29 '17 at 4:24
• Thank you for this answer and the code snippet PSub. I am wondering whether this can be edited to accommodate for unsupervised settings where we don't have any information about the ground truth, and we rely on the accurate embedding by SNE. If we fit TSNE for 2 components, could we then train kNN on (X_embedded[0], X_embedded[1]), and then when we have new unseen data, first call TSNE.transform to embed into trained embedding and then call predict() to get the position of the new data point wrt the original map? – nvergos Sep 18 at 17:12