Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: K-nearest neighbhors on an equispaced multidimensional grid

  • To: mathgroup at smc.vnet.net
  • Subject: [mg72036] Re: K-nearest neighbhors on an equispaced multidimensional grid
  • From: "Ray Koopman" <koopman at sfu.ca>
  • Date: Sat, 9 Dec 2006 06:09:44 -0500 (EST)
  • References: <elbij5$k7o$1@smc.vnet.net>

erwann.rogard at gmail.com wrote:
> hi,
>
> i am looking for an algorithm/data structure to find the K-nearest
> neighbors on an equispaced multidimensional grid.
>
> x=(x_1,...,x_D) where x_d takes values in (...,-1,0,1,...)  for all
> d=1,...,D
>
> for example if D=2 and x=(0,0) the
>
> 1-NN is x itself
> 5-NN are x, (-1,0), (0,-1),(1,0),(0,1)
> 9-NN are x, (-1,0), (0,-1),(1,0),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)
>
> etc...
>
> thanks,
>
> e.

Let X be an m-dimensional equispaced grid on -k,...,k:

In[1]:= X = With[{k = 1, m = 2}, Tuples[Range[-k,k], m]]

Out[1]= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}}

Pick a random point x from X:

In[2]:= x = X[[Random[Integer,{1,Length@X}]]]

Out[2]= {0,-1}

Prepend each point's squared distance from x to its coordinates:

In[3]:= Prepend[#, (#-x).(#-x)]& /@ X

Out[3]= {{1,-1,-1},{2,-1,0},{5,-1,1},{0,0,-1},{1,0,0},{4,0,1},
         {1,1,-1},{2,1,0},{5,1,1}}

Sort the points in terms of their distances from x:

In[4]:= Sort[%]

Out[4]= {{0,0,-1},{1,-1,-1},{1,0,0},{1,1,-1},{2,-1,0},{2,1,0},
         {4,0,1},{5,-1,1},{5,1,1}}

Group the points in terms of their distances from x:

In[5]:= Split[%, #1[[1]] == #2[[1]] &]

Out[5]= {{{0,0,-1}},{{1,-1,-1},{1,0,0},{1,1,-1}},{{2,-1,0},{2,1,0}},
         {{4,0,1}},{{5,-1,1},{5,1,1}}}

Extract the squared distances and insert them as headers:

In[6]:= {#[[1,1]], Rest/@#}& /@ %

Out[6]= {{0,{{0,-1}}},
         {1,{{-1,-1},{0,0},{1,-1}}},
         {2,{{-1,0},{1,0}}},{4,{{0,1}}},
         {5,{{-1,1},{1,1}}}}

Here it is all together, given X and x:

In[7]:= {#[[1,1]], Rest/@#}& /@ Split[Sort[Prepend[#, (#-x).(#-x)]&
         /@ X], #1[[1]] == #2[[1]] &]

Out[7]= {{0,{{0,-1}}},
         {1,{{-1,-1},{0,0},{1,-1}}},
         {2,{{-1,0},{1,0}}},{4,{{0,1}}},
         {5,{{-1,1},{1,1}}}}


  • Prev by Date: Re: Re: Finding the periphery of a region
  • Next by Date: Re: Solve chokes on Piecewise input that Reduce handles quite well??
  • Previous by thread: K-nearest neighbhors on an equispaced multidimensional grid
  • Next by thread: Re: K-nearest neighbhors on an equispaced multidimensional grid