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}}}}