Re: K-nearest neighbhors on an equispaced multidimensional grid
- To: mathgroup at smc.vnet.net
- Subject: [mg72140] Re: K-nearest neighbhors on an equispaced multidimensional grid
- From: "Ray Koopman" <koopman at sfu.ca>
- Date: Wed, 13 Dec 2006 06:40:20 -0500 (EST)
- References: <elbij5$k7o$1@smc.vnet.net><ele6jq$rlj$1@smc.vnet.net>
Ray Koopman wrote:
> 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}}}}
Here's another way to get points grouped and ordered
in terms of their distances from x:
X = With[{k = 1, m = 2}, Tuples[Range[-k,k], m]];
x = X[[Random[Integer,{1,Length@X}]]]
{0,-1}
Sort[{(#[[1]]-x).(#[[1]]-x),#}& /@
Last@Reap[Scan[Sow[#,(#-x).(#-x)]&,X]]]
{{0,{{0,-1}}}
{1,{{-1,-1},{0,0},{1,-1}}}
{2,{{-1,0},{1,0}}}
{4,{{0,1}}}
{5,{{-1,1},{1,1}}}