Is the distance in Nearest Neighbors a good measure of similarity?

Question

Let's train a Nearest Neighbor model with just one sample in it:

In [48]: nn = NearestNeighbors().fit([[0, 1, 0, 0]])

So this one sample has just one significant feature. Querying the model with the same sample returns 0 distance in the first array as expected:

In [50]: nn.kneighbors([[0, 1, 0, 0]], 1)
Out[50]: (array([[0.]]), array([[0]]))

But queries with samples of [0,2,0,0] and [0,1,1,0] both return the same distance value of 1:

In [51]: nn.kneighbors([[0, 2, 0, 0]], 1)
Out[51]: (array([[1.]]), array([[0]]))

In [52]: nn.kneighbors([[0, 1, 1, 0]], 1)
Out[52]: (array([[1.]]), array([[0]]))

This is counter-intuitive, because one would expect [0,2,0,0] to be more similar to [0,1,0,0] than [0,1,1,0]. Using Jaccard metric slightly improves on this issue:

In [56]: nn = NearestNeighbors(metric=scipy.spatial.distance.jaccard).fit([[0, 1, 0, 0]])

In [57]: nn.kneighbors([[0, 1, 0, 0]], 1)
Out[57]: (array([[0.]]), array([[0]]))

In [58]: nn.kneighbors([[0, 2, 0, 0]], 1)
Out[58]: (array([[1.]]), array([[0]]))

In [59]: nn.kneighbors([[0, 1, 1, 0]], 1)
Out[59]: (array([[0.5]]), array([[0]]))

But for my dataset Jaccard metric makes the kNN queries taking very long time, perhaps it is more suited for binary features. I have a set of readings from 52 sensors per row, nicely normalized with zero mean. I stumbled upon this issue when I fitted this set into sklearn.neighbors.NearestNeighbors and queried giving the first row of the training set as a sample and K=2, so it returned 0th index at 0 distance as expected and some other index with 0.02 distance. When I checked that other one I could not see ANY similarities, in fact most of the features where very dissimilar by value and/or by sign. I could get the same distance with a made-up sample of the first row from the training set where any one feature was increased by 0.02.

I am wondering now how to overcome this problem and if there is an easy way (ie. by tweaking parameters of NearestNeighbors) or a hacky way (ie. custom metrics, feature weights etc.) or should I rather use a different model? KMeans for example can converge clusters from my dataset pretty fast, but it uses NN internally and I do not fully like it because of the randomness in the init.

Answer 1

This is counter-intuitive, because one would expect [0,2,0,0] to be more similar to [0,1,0,0] than [0,1,1,0].

No this is expected, since the two points are exactly at the same distance in the Euclidean space. To see it take a simplified 2D version of your points:

• A (1,0)
• B (2,0)
• C (1,1)

Both B and C are exactly at distance 1 from A.

But for my dataset Jaccard metric makes the kNN queries taking very long time, perhaps it is more suited for binary features.

Jaccard actually assumes binary features, it will consider all non-zero values the same way. Its result is based on how many non-zero dimensions the two points have in common. I'm assuming that the implementation follows the original definition, there might be variants. Normally it's a very simple measure which doesn't require any heavy computation so it's surprising that it takes a long time.

When I checked that other one I could not see ANY similarities, in fact most of the features where very dissimilar by value and/or by sign. A change of sign has no particular importance in the euclidean space, it's the distance which matters.

Well the only way to really check would be to calculate the euclidean distance, with 52 dimensions just looking at the values is not going to give a good indication.

I could get the same distance with a made-up sample of the first row from the training set where any one feature was increased by 0.02.

I'm not sure I understand this part but again this sounds perfectly correct: changing any feature by 0.02 will move the data point in the space by a distance of 0.02 so... it's going to be at distance of 0.02 from the original point.

I am wondering now how to overcome this problem and if there is an easy way (ie. by tweaking parameters of NearestNeighbors) or a hacky way (ie. custom metrics, feature weights etc.)

If there is any data-specific way to measure the distance between two points, you should definitely define a custom metric. It's not a hack, as you can see NN relies entirely on the metric. The default euclidean distance is a generic measure, it might not be fit for your purpose.