# Distance-based dimensionality reduction from 2D to 1D?

Problem:

Let $C = \{c_1, c_2, c_3, ..., c_n\}$ be a set of cities. And $G = \{(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)\}$ a set of their respective geographical coordinates.

What I want to do is finding a set $G' = \{a_1, a_2, ..., a_n\}$ (or a function $F$ such that $G' = \{a_i = F(x_i, y_i) | i = 1, 2, ..., n \}$) that (at least loosely) verifies the following property:

For a given city $c_i$: the $k$ nearest neighbors of $c_1$ considering $G$ are the same considering $G'$.

In others words, I want to find 1-dimensional values that reflect 2-dimensional distance.

What I did so far: I used the t-SNE dimensionality reduction tool from the Python library SKLearn. And the result wasn't satisfying. So I thought maybe for small data points (around 50 city) I'd better go for something more straight-forward

• You might also look at multi-dimensional scaling. – G5W Apr 14 '17 at 0:19
• I posted an MDS solution at gis.stackexchange.com/a/15567/664. – whuber Apr 14 '17 at 0:21
• MDS is an option, but MDS will pay most attention to preserving large distances (because it tries to preserve all the distances, and large distances contribute more to the loss function). If you want to reproduce only $k$ nearest neighbours, then you want to preserve local similarities, i.e. you care mostly about preserving small distances. This is something t-sne is supposed to do; it's hard to say why the result wasn't satisfying, but note that 1D is a very tight space. If your set of cities is rich, then what you want might be impossible. Perhaps post the map of your G. – amoeba Apr 14 '17 at 0:29