find k nearest neighbours for each element in a matrix

hii I have two matrices in A,B. My matlab code for finding k nearest neighbours of A wrt B is:

A=[1 2 1;3 4 1;5 6 1;];
B=[11 12 2;13 4 2;15 16 2;17 18 2;1 2 2;3 4 2;5 6 2;];
[row,col]=size(A);
[row1,col1]=size(B);
dist=zeros(row,row1);
nnarray = zeros(row,row1);
k=5;
nnarray1 = zeros(row,k);
for i=1:row
for j=1:row1
      dist(i,j)=sqrt(sum((A(i,:)-B(j,:)).^2));
end
[y,index]=sort(dist(i,:));
  nnarray(i,:)=index';
  end

The ouptut matrix for nnarray is:

//nearest neighbours for A matrix

5   6   7   2   1   3   4
6   5   7   2   1   3   4
7   6   5   2   1   3   4

Here the output i got only one NEAREST NEIGHBOUR for each element in A matix wrt B.

 But I want to find 5 nearest neighbours for each element in A matrix. 
Eg : I want to find 5 nearest neighbours for A(1,2).

How to do it.? and Where should i modify my code

[Azzi Abdelmalek]

This is not clear

[indian]

edited my question

[Azzi Abdelmalek]

In this case what are the 5 values for A{1,1}

[indian]

5 values for A{1,1} will be the 5 nearest neighbours of that element

[Azzi Abdelmalek]

Ok, post those 5 nearest neighbours

[Roger Stafford]

I think all of us are having the same problem understanding what you are asking. The code you exhibited considered the Euclidean distance between the rows of A and the rows of B where the distance is the square root of the sum of the squares of the differences of the elements of the three columns of A and B respectively. In other words the distance between A(2,:) and B(5,:) for example would be

 sqrt((A(2,1)-B(5,1)^2+(A(2,2)-B(5,2)^2+(A(2,3)-B(5,3)^2)

and in your result you correctly found the index 5 as pointing to the second closest row of B to the second row of A. With this meaning of distance and neighbor you have already obtained your answer, namely, the first five columns of the result you gave.

If the above is what you mean by "distance", then there is no sense asking about the nearest neighbors of a single element such as A(1,2). You have to decide what kind of objects you are finding the distance between in determining what you mean by "neighbors".

[indian]

Please understand my question and leave my code.My problem is I want to find k nearest neighbours of each element in a matrix based on other matrix B I want 5 nearest neighbours of A(1,1)... basing on whole matrix B

In my answer I am finding out between rows but I want for each element in a matrix

Answer 1

[Image Analyst]

Not hard at all if you're clever, and use conv2 and sort. Check out this code:

m = magic(10) % Sample data
% Get the absolute value of hte differences
% in each of the 8 neighbor directions.
nn1 = abs(conv2(m, [-1,0,0;0,1,0;0,0,0], 'valid'))
nn2 = abs(conv2(m, [0,-1,0;0,1,0;0,0,0], 'valid'))
nn3 = abs(conv2(m, [0,0,-1;0,1,0;0,0,0], 'valid'))
nn4 = abs(conv2(m, [0,0,0;-1,1,0;0,0,0], 'valid'))
nn5 = abs(conv2(m, [0,0,0;0,1,-1;0,0,0], 'valid'))
nn6 = abs(conv2(m, [0,0,0;0,1,0;-1,0,0], 'valid'))
nn7 = abs(conv2(m, [0,0,0;0,1,0;0,-1,0], 'valid'))
nn8 = abs(conv2(m, [0,0,0;0,1,0;0,0,-1], 'valid'))
% Stack these as planes (slices) in a 3D matrix.
array3D = cat(3, nn1, nn2, nn3, nn4, nn5, nn6, nn7, nn8);
% Now sort along the z direction.
sorted3D = sort(array3D, 3);
% Let's see them - print them out just for fun.
for z = 1 : 8
  array2D = sorted3D(:,:,z)
end
% Only the first 5 were wanted, so take those:
finalOoutput = sorted3D(:,:,1:5)
msgbox('Done with demo! Check the command window.');

[Image Analyst]

Nevermind - this code produces the 5 closest neighbors to an element in the same matrix, not between different matrices. Why do you want that anyway?

Answer 2

[Shashank Prasanna]

Eg : I want to find 5 nearest neighbours for A(1,2).

That does not make much sense. You are finding neighbors of A(i,:), i.e. you are finding neighbors for each row of A which is treated as a vector with each row of B(j,:).

A=[1 2 1;3 4 1;5 6 1;];
B=[11 12 2;13 4 2;15 16 2;17 18 2;1 2 2;3 4 2;5 6 2;];
for i = 1:length(A)
D = sum((repmat(A(i,:),length(B),1) - B).^2,2);
[sortD idxD] = sort(D);
fiveNND{i,:} = idxD(1:5)';
end

fiveNND variable has a cell array of the index in A for the 5 nearest neighbors in B. It looks similar to what you have:

fiveNND =

      [1x5 double]
      [1x5 double]
      [1x5 double]

Note these are indices of B and here is how you will use them:

>> B(fiveNND{1},:) % First 5 neighbors for A(1,:)
>> B(fiveNND{2},:) % First 5 neighbors for A(2,:)
>> B(fiveNND{3},:) % First 5 neighbors for A(3,:)

Hope that makes sense. In any case I would recommend the use of PDIST2 or KNNSEARCH

http://www.mathworks.com/help/stats/pdist2.html

http://www.mathworks.com/help/stats/knnsearch.html

[indian]

yes my answer and your answer is same. My probelm is I want to find 5 nearest neighbours for a point in whole set of points.But my answer and your answer is returning only 1 nearest neighbors but not set of nearest neighbors

[Shashank Prasanna]

You have to clarify your question. Apparently your definition of nearest neighbor is starkly different from the whole world's definition of nearest neighbor.

My answer does return the 5 nearest neighbors in B to each row of A, not each element. And this is found here: B(fiveNND{1},:) This is the accepted definition of nearest neighbor

Unless you clarify your question everyone here is going to be making assumptions about what you want and you will never get your answer.

If you want 5 nearest neighbor to each point in A to all points all B (what we now understand from your request, but again you need to clarify)

Then why not just find there difference as follows?

A=[1 2 1;3 4 1;5 6 1;];
B=[11 12 2;13 4 2;15 16 2;17 18 2;1 2 2;3 4 2;5 6 2;];
D = A(1,1) - B(:);
[sortD, idxD] = sort(D);
[I,J] = ind2sub(size(B),idxD(1:5));
disp([I,J])

If this does not help, please provide your application and reason for doing this.

[Image Analyst]

Yes, I'd like to hear the reason for this too. I've never heard of such a need before. Often people say they want to do "X" as a method to accomplish "Z", but if they'd just told us what "Z" is in the first place, we could have told them that "X" is the wrong way and they really should use approach "Y".

[indian]

I am working in imbalanced data mining in which i have two classes miniorty class and majority class.My work is i have to find nearest neighbours for each instance in the minority class to the whole training set. I am implementing in matlab in which i find k nearest neighbours for each row in minority class to the whole training set.But in some research papers they asked for nearest neighbours each instance to the whole training set.That is my doubt too and how to implement it ?

[Image Analyst]

So how do you get 2D matrices like 3 by 7, almost like an image? What does each row and each column represent? What does A represent, and what does B represent?

[indian]

here the A and B are the sample matrices.Actually in problem my A matrices represent the miniortiy class and B represents the training set. My rows represent the instances and my columns represent each features.

[Shashank Prasanna]

If what you say is correct - rows are instances and columns are features, then go back to my first post. Neighbors are calculated in the feature space which is all the columns for each instance:

A(i,:) to B(j,:)

If you saw something in a research paper that is different, then some references would be great.

Take a look at some examples in the doc for neighbor searches:

http://www.mathworks.com/help/stats/classification-using-nearest-neighbors.html#bsehylk

[indian]

Here are the reference http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.308.9315&rep=rep1&type=pdf please see the 882 page