K Nearest Neighbors

Program to find the k - nearest neighbors (kNN) within a set of points.

Description

Program to find the k - nearest neighbors (kNN) within a set of points.
Distance metric used: Euclidean distance

Usage:
[neighbors distances] = kNearestNeighbors(dataMatrix, queryMatrix, k);
dataMatrix (N x D) - N vectors with dimensionality D (within which we search for the nearest neighbors)
queryMatrix (M x D) - M query vectors with dimensionality D
k (1 x 1) - Number of nearest neighbors desired

Example:
a = [1 1; 2 2; 3 2; 4 4; 5 6];
b = [1 1; 2 1; 6 2];
[neighbors distances] = kNearestNeighbors(a,b,2);

Output:
neighbors =
     1 2
     1 2
     4 3

distances =
         0 1.4142
    1.0000 1.0000
    2.8284 3.0000

• MATLAB release: MATLAB 7.5 (R2007b)

[John D'Errico]

Why would this be placed in the linear algebra category?

[Yiji Lin]

Very helpful! Easy understanding!

[Brijesh Shah]

easy but effective.thankx

[Wenwei Huang]

Helpful. Thanks.

[yan ziye]

what is the sortpos() function in this m file

[andy chen]

can you tell me what is sortpos() and sortval()

[Li]

Is it fast for large dataset? Is it implemented using KD-tree?

[Sravanti]

really nice, simple and easy - but don't you need to take the square root for distances?

[Miguel Torres]

The square distance is calculated (without square root) . Take a look a this tutorial:

http://people.revoledu.com/kardi/tutorial/KNN/KNN_Numerical-example.html

[Ridha Samosir]

i need code for r-nearest neightbour using sliding window concept start form window 3x3 then shift until window size of image reached. All of point is grouped based on color similarity using euclidian distance. Parameter for this code is count of r-nearest neightbour ( 25 ) and minimum color distance ( 6 ). Minimum color distance is a treshold for check the similarity between the point. So all of data point which have similarity distance color < 6 is taken for make a group. Start from window 3x3, define inisialization point X then memorizaed all data point ( 25 ) which color distance < 6.

[Avi]

good efficient code , can be added group so return group selected by the indexes and make majority voting with distance weight

Ydec = ArgMax(group(i)/Dist(i))

[Pototo]

hello, I am imputing some square matrices, but this algorithm is not working. I though that as long as D is the same for both matrices, this would work. Does that mean that N cannot be equal to M at all???
thanks in advance!!!!!!!

[djanahana djanahana]

thank's a lot