点到不在同一组的点的最近邻距离

Question

在我的数据集中，我有一些点，其位置由 X 和 Y 给出，按 ID 分组。我想计算每个点到其他组中的点的最近邻 (NN) 距离。换句话说，如果一个点的ID是1，代码应该从满足ID != 1.

的点中搜索NND

伪 R 代码可能如下所示：

DT[DT, c("nn_dist", "nn_X", "nn_Y") := find_NNN(data.table(i.X, i.Y), .SD[ID != i.ID]), by = .EACHI]

为此，我尝试编写带有循环等命令式代码，但速度太慢。我尝试使用 FNN 库中的 get.knnx 函数，但后来我不知道如何获得 NN 距离和 NN 的位置。

如何在相对较大（~10,000 行）的数据集上进行此计算？

这是我正在使用的数据集的一小部分

structure(list(ID = c(1L, 1L, 2L, 2L), X = c(318L, 317L, 1273L, 
1272L), Y = c(1L, 2L, 1L, 2L), t = c(1, 1, 1, 1), uid = c(1L, 
2L, 1271L, 1272L)), row.names = c(NA, -4L), class = c("data.table", 
"data.frame"), .internal.selfref = <pointer: 0x7f89b481f0e0>)

t 数据集中所有点的列都相同
uid 是赋予每个点的唯一 ID，无论它们的位置或组如何，因此 max(uid) 等于数据集中的#rows

Answer 1

我曾经做过类似的工作。

spatstat库中的nncross函数可以完成这项工作。我不知道如何使用data.table，但下面的示例代码应该很容易理解。

library(spatstat)

# create an example dataframe of 100 points that belong to 10 classes
points <- data.frame(X=rnorm(100, mean = 0, sd = 1),
                     Y=rnorm(100, mean = 0, sd = 1),
                     class_id = sample(1:10, size = 100, replace = T))

# convert the dataframe of points to ppp object that can be used as input for nncross function
points.ppp <- as.ppp(points, 
                     W=owin( xrange = range(points$X),yrange = range(points$Y) )
                     )

# calculate for each points its NN point that belongs to another class. The "iX" and "iY" arguments are very important to tell the function to calculate only the cross-class distance, please see the help information of the nncross function for details.
NND_which <- nncross(points.ppp,
                 points.ppp,
                 iX = as.integer(points.ppp$marks), 
                 iY = as.integer(points.ppp$marks)
                 )

# put the NN pairs as well as the distance between them in a new dataframe
NND_pair <- data.frame(NND_source_id = 1:nrow(points),
                       NND_target_id = NND_which$which,
                       NND_dist = NND_which$dist)

这个函数应该比 R 中的循环快得多。但是如果你有非常多的点，比如数十亿个点，我建议在 Rcpp 的帮助下用 C++ 编写你自己的函数。

我不知道FNN库，可能其他知道如何使用它的人可以比较哪个函数更快。

Answer 2

您可以创建一个小的距离函数，传递 x、y 和所有候选点的数据框 d（即所有候选点的 x 和 y 值其他id组中的点，以及returns最近的inter-group点

的坐标和uid

dist <- function(x,y,d) d[order(d[,sqrt((X-x)^2 + (Y-y)^2)])][1]

然后将函数应用于框架

df[, c("nnX", "nnY", "nn"):=dist(X,Y, df[ID!=.BY$ID,.(X,Y,uid)]),by=.(ID,uid)]

输出：

   ID    X Y t  uid  nnX nnY   nn
1:  1  318 1 1    1 1272   2 1272
2:  1  317 2 1    2 1272   2 1272
3:  2 1273 1 1 1271  318   1    1
4:  2 1272 2 1 1272  318   1    1

如果您还需要到最近邻居的距离，您可以像这样更新函数和对函数的调用：

dist <- function(x,y,d) {
  d[, nn_dist:=sqrt((X-x)^2 + (Y-y)^2)][order(nn_dist)][1]
}
df[, c("nnX", "nnY", "nn", "nn_dist"):=dist(X,Y, df[ID!=.BY$ID,.(X,Y,uid)]),by=.(ID,uid)]

输出：

   ID    X Y t  uid  nnX nnY   nn  nn_dist
1:  1  318 1 1    1 1272   2 1272 954.0005
2:  1  317 2 1    2 1272   2 1272 955.0000
3:  2 1273 1 1 1271  318   1    1 955.0000
4:  2 1272 2 1 1272  318   1    1 954.0005

或者，您可以使用第一个函数并使用 df[, nn_dist := sqrt((X-nnX)^2 + (Y-nnY)^2)]

估计最后的距离

点到不在同一组的点的最近邻距离

Nearest neighbour distance of points to the point that are not in the same group

r

data.table

tidyverse