R › R help

Nearest Neighbors

Classic

List

Threaded

7 messages Options

olemissrebs1123

Nearest Neighbors

I was wondering if there is a way in R to find k nearest neighbors of various orders, say order 2, 3, or 4. In otherwords neighbors of neighbors of neighbors. You get the idea. I know that I can use knearneigh(matrix.data, k) but this only gives me the k nearest neighbors and not of a particular order.

Thanks in advance.

Jeff Newmiller

Re: Nearest Neighbors

Isn't the obvious solution to subtract the set for level n-1 from the set for level n?
---------------------------------------------------------------------------
Jeff Newmiller The ..... ..... Go Live...
DCN:<[hidden email]> Basics: ##.#. ##.#. Live Go...
Live: OO#.. Dead: OO#.. Playing
Research Engineer (Solar/Batteries O.O#. #.O#. with
/Software/Embedded Controllers) .OO#. .OO#. rocks...1k
---------------------------------------------------------------------------
Sent from my phone. Please excuse my brevity.

olemissrebs1123 <[hidden email]> wrote:

>I was wondering if there is a way in R to find k nearest neighbors of
>various
>orders, say order 2, 3, or 4. In otherwords neighbors of neighbors of
>neighbors. You get the idea. I know that I can use
>knearneigh(matrix.data,
>k) but this only gives me the k nearest neighbors and not of a
>particular
>order.
>
>
>Thanks in advance.
>
>
>
>--
>View this message in context:
>http://r.789695.n4.nabble.com/Nearest-Neighbors-tp4637618.html
>Sent from the R help mailing list archive at Nabble.com.
>
>______________________________________________
>[hidden email] mailing list
>https://stat.ethz.ch/mailman/listinfo/r-help
>PLEASE do read the posting guide
>http://www.R-project.org/posting-guide.html
>and provide commented, minimal, self-contained, reproducible code.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

olemissrebs1123

Re: Nearest Neighbors

I don't see the "obvious" portion. What I am looking for is an output that gives me an n*k matrix n (x,y) pairs k neighbors but using order say 4.

David Carlson

Re: Nearest Neighbors

Look at function get.knn in package FNN:

> library(FNN)
> set.seed(42)
> x <- rnorm(100, 50, 15)
> y <- rnorm(100, 50, 15)
> dat <- data.frame(x, y)
> knns <- get.knn(dat, k=4)
> str(knns)
> knns.ndx <- data.frame(knns[["nn.index"]])
> head(knns.ndx)

knns is a list with two components, a matrix of indices to the nearest
neighbors and a matrix of distances to the nearest neighbors.

----------------------------------------------
David L Carlson
Associate Professor of Anthropology
Texas A&M University
College Station, TX 77843-4352

> -----Original Message-----
> From: [hidden email] [mailto:r-help-bounces@r-
> project.org] On Behalf Of olemissrebs1123
> Sent: Tuesday, July 24, 2012 1:27 PM
> To: [hidden email]
> Subject: Re: [R] Nearest Neighbors
>
> I don't see the "obvious" portion. What I am looking for is an output
> that
> gives me an n*k matrix n (x,y) pairs k neighbors but using order say 4.
>
>
>
> --
> View this message in context: http://r.789695.n4.nabble.com/Nearest-
> Neighbors-tp4637618p4637648.html
> Sent from the R help mailing list archive at Nabble.com.
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-
> guide.html
> and provide commented, minimal, self-contained, reproducible code.

olemissrebs1123

Re: Nearest Neighbors

This post has NOT been accepted by the mailing list yet.

David,

Thanks. I tried this but I still don't get the same result that I would get using MATLAB's find_nn() algorithm. Wherein you input the xy data, the number of neighbors and the order (as in the delaunay order). To this end it would find the nearest k neighbors up to the default order I believe.

This is what I am looking to do:
"USAGE: nnindex = find_nn(xc,yc,m)
where:
xc = x-coordinate for each obs (nobs x 1)
yc = y-coordinate for each obs (nobs x 1)
m = # of nearest neighbors to be found
order = 1, 2, 3, or 4. (default = 2)
This limits the extent to search for neighbors to the sum of the delaunay orders
e.g., delorder=2 limits the search to the delaunay neighbors and the neighbors of neighbors
Lower values of delorder speed computation and reduce memory. "

I would then like to create a Spatial weight matrix.

Thanks again,

Adrian

Petr Savicky

Re: Nearest Neighbors

In reply to this post by olemissrebs1123

On Tue, Jul 24, 2012 at 09:26:49AM -0700, olemissrebs1123 wrote:
> I was wondering if there is a way in R to find k nearest neighbors of various
> orders, say order 2, 3, or 4. In otherwords neighbors of neighbors of
> neighbors. You get the idea. I know that I can use knearneigh(matrix.data,
> k) but this only gives me the k nearest neighbors and not of a particular
> order.

Hi.

If i understand correctly, then this may be achieved by several iterations.
In the first iteration, the nearest neighbours are found. The next iteration
starts from them a finds their nearest neighbours. These are neighbours of
order 2. A general iteration finds neighbours of order n by looking for neighbours
of the points found in the previous step, which are the neighours of order n-1.

Hope this helps.

Petr Savicky.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

David Carlson

Re: Nearest Neighbors

Actually if you are looking for neighbors of neighbors you only need the
nearest neighbor for each point. The problem is that the nearest neighbor of
the nearest neighbor of point 1 is often point 1. Did you want the nearest
neighbor not counting any point twice? Sounds more like a traveling salesman
problem or nearest link cluster analysis.

> set.seed(42)
> x <- rnorm(100, 50, 15)
> y <- rnorm(100, 50, 15)
> dat <- cbind(x, y)
> library(spdep)
> nn <- knearneigh(dat, 1)
> nn1 <- nn$nn # Nearest neighbors
> nn2 <- nn1[nn1] # Nearest neighbor of the nearest neighbor
> nn3 <- nn2[nn1] # Third order
> nn4 <- nn3[nn1] # Fourth order
> head(cbind(nn1, nn2, nn3, nn4), 10)

nn2 nn3 nn4
[1,] 53 1 53 1
[2,] 34 2 34 2
[3,] 67 3 67 3
[4,] 35 60 46 60
[5,] 82 5 82 5
[6,] 10 6 10 6
[7,] 48 7 48 7
[8,] 40 8 40 8
[9,] 25 9 25 9
[10,] 6 10 6 10

----------------------------------------------
David L Carlson
Associate Professor of Anthropology
Texas A&M University
College Station, TX 77843-4352

> -----Original Message-----
> From: [hidden email] [mailto:r-help-bounces@r-
> project.org] On Behalf Of Petr Savicky
> Sent: Sunday, July 29, 2012 1:44 PM
> To: [hidden email]
> Subject: Re: [R] Nearest Neighbors
>
> On Tue, Jul 24, 2012 at 09:26:49AM -0700, olemissrebs1123 wrote:
> > I was wondering if there is a way in R to find k nearest neighbors of
> various
> > orders, say order 2, 3, or 4. In otherwords neighbors of neighbors of
> > neighbors. You get the idea. I know that I can use
> knearneigh(matrix.data,
> > k) but this only gives me the k nearest neighbors and not of a
> particular
> > order.
>
> Hi.
>
> If i understand correctly, then this may be achieved by several
> iterations.
> In the first iteration, the nearest neighbours are found. The next
> iteration
> starts from them a finds their nearest neighbours. These are neighbours
> of
> order 2. A general iteration finds neighbours of order n by looking for
> neighbours
> of the points found in the previous step, which are the neighours of
> order n-1.
>
> Hope this helps.
>
> Petr Savicky.
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-
> guide.html
> and provide commented, minimal, self-contained, reproducible code.