Results of knnsearch do not make sense (to me)

Hello,

I am using [IDX,D] = knnsearch(y,y,'K',2,'NSMethod','exhaustive') to find the nearest neighbor to each point of y in y (excluding obviously the same point, hence the 2 in 'K').

The algorithm returns that point 34 is the nearest neighbor of point 72, but when one goes to point 72, its nearest neighbor is point 124 (I guess it should be point 34). Any clue why this happens?

[NaN1988]

Apologies for not being more clear. y is a matrix of variable dimension. When I mentioned point 34, 72, or 124 I was referring to the indexes. For example.

point 3 = [-1,3907 0,6324 0,76023]

point 4 = [-1,4093 0,6363 0,73788]

point 5 = [-1,4140 0,6371 0,71772]

According to knnsearch, the nearest neighbor of point 3 is point 4. The nearest neighbor of point 4 is point 5.

[John D'Errico]

But without attaching the data, how can we know what happened? In fact, a quick test of knnsearch shows that it worked perfectly for me on some random data (10000 points generated.)

[NaN1988]

I am attaching y in this message

[Jan]

@John: I dare to claim to know what happened, because I trust knnsearch to reply correct values.

[NaN1988]

Sorry for wasting your time, I had a wrong interpretation of the problem. Thank you for your help

[Jan]

@NaN1988: No, this is not a waste of time. It is the nature of problems, that they are trivial, after they are solved. Questions about Matlab are welcome in the forum!

Answer 1

[Jan]

 point 34 is the nearest neighbor of point 72, but when one goes to point
 72, its nearest neighbor is point 124 (I guess it should be point 34).

There is no problem.

p3 = [-1.3907, 0.6324, 0.76023]
p4 = [-1.4093, 0.6363, 0.73788]
p5 = [-1.4140, 0.6371, 0.71772]

If p4 is the nearest point to p3, it can be valid that p5 is the nearest to p4. There is no logical problem. Try this with numbers:

[1, 3, 4]

Now 3 is the nearest point to 1, but the nearest point of 3 is not 1 but 4. So only your expectation was wrong.

By the way, you can expect, that such a well tested function of the Matlab toolbox like knnsearch does not reply rubbish. If the output "does not make sense", then this is a problem of the process of "making sense", not of the output. ;-)

[NaN1988]

If p4 is the closest point to p3, isn't p3 the closest point to p4? Yes, I know what you mean, but I have a couple of comments. My data corresponds to the signal of a dynamical system, the probability that the distance between p3 and p4 is the same (within Matlab accuracy) as between p4 and p5 is really tiny. If this is the case, I believe Matlab should return a warning indicating that there are two nearest neighbors at identical distance.

[John D'Errico]

NO!!!!!!! That need not be at all true! Consider a 1-d case.

X = [-10 2 5 6];

So, clearly, the closest point to 2 (point 2) is 5, thus point 3. Since2 is closer to 5 than it is to -10.

But is it true that the closest point to point #3 is point #2? Of course not! 5 is closest to 6, not to 2.

Closest point is not a commutative operator. By making the assumption that it is, you have made a mistake.

[NaN1988]

Ok, now I understand...actually it is pretty silly, sometimes I get stuck in the most trivial things

Answer 2

[Image Analyst]

To run the code:

s = load('y.mat')
y = s.y;
plot3(y(:, 1), y(:, 2), y(:, 3), 'b.', 'MarkerSize', 16);
grid on;
[IDX,D] = knnsearch(y,y,'K', 2,'NSMethod','exhaustive')
% Show points 34 and 74 in command window
IDX(34,:)
IDX(72,:)
D(34,:)
D(72,:)

You see

ans =
    34    35
ans =
    72    73
ans =
            0     0.050199
ans =
            0     0.033753

So 35 is closest to 34, and 73 is closest to 72. So I'm not observing what you are.

As an alternative, why don't you just use pdist2() (in the Statistics and Machine Learning Toolbox), which is a more direct (and possibly faster) way of measuring distance of every point to every other point.