改进大数据中距离集计算方法的方法？
Ways to improve method for calculating sets of distances in big data?
我 post 前阵子讨论过 calculate sets of distances using big data 的效率如何。那里的答案并没有完全回答我的问题，因为这个问题更具计算性（例如，如何在不进行大量合并的情况下找到 k 最近邻以计算每个点彼此之间的距离）而不是关于自己计算距离。
我们已经想出了一个在 data.table 中使用非 equi 连接的解决方案，但我非常感谢任何关于这是否是 go/ways 改进的正确方法的反馈速度等等。
问题概览
（有关更多详细信息，请参阅上面的链接 post。）我们有一个（实际上非常大）包含商店位置的数据集，例如：
library(tidyverse)
library(data.table)
ex <- data.table(x = c(5,6,7),
y = c(1,2,3))
我们想知道在每家商店的任意半径范围内还有多少家商店。这样做的简单但在计算上不可行的方法基本上是将数据集与其自身合并并计算每个商店组合的距离。显然，当您拥有数百万家商店时，这种方法会产生巨大的中间数据集，以及其他问题。
建议的解决方案
好的，现在开始我想要反馈的部分。本质上，基本思想是在每个商店周围画一个正方形，使用非相等连接查找商店“正方形”内的所有其他商店，然后计算距离并仅将商店保留在商店的正确半径内总店（即在初始正方形内画一个圆圈）。
为此，首先我们复制商店数据集并计算将保存正方形尺寸的变量：
# make copy of original dataframe with new names
ex.c <- rename(.data = ex, xc = x, yc = y)
# make bounding box for each point in original dataframe
ex$min.x <- ex$x - 2
ex$max.x <- ex$x + 2
ex$min.y <- ex$y - 2
ex$max.y <- ex$y + 2
然后我们将商店数据集与其本身合并，要求其他商店的坐标在主商店的任意数量内，这里是 2 个单位：
ex5 <- ex[ex.c,
.(x.x, x.min.x, x.max.x, x.min.y, x.min.y, i.xc, i.yc),
on = .(max.x >= xc, min.x <= xc,
max.y >= yc, min.y <= yc),
allow.cartesian = T]
ex5
x.x x.min.x x.max.x x.min.y x.max.y i.xc i.yc
1: 5 3 7 -1 3 5 1
2: 6 4 8 0 4 5 1
3: 7 5 9 1 5 5 1
4: 5 3 7 -1 3 6 2
5: 6 4 8 0 4 6 2
6: 7 5 9 1 5 6 2
7: 5 3 7 -1 3 7 3
8: 6 4 8 0 4 7 3
9: 7 5 9 1 5 7 3
然后我们计算距离，从那里我们可以保留所需半径内的商店：
## that does the square. now we need to cut to the circle
ex5[,
dist := sqrt((x.x - i.xc)^2 + (x.x - i.yc)^2)]
ex5
x.x x.min.x x.max.x x.min.y x.max.y i.xc i.yc dist
1: 5 3 7 -1 3 5 1 4.000000
2: 6 4 8 0 4 5 1 5.099020
3: 7 5 9 1 5 5 1 6.324555
4: 5 3 7 -1 3 6 2 3.162278
5: 6 4 8 0 4 6 2 4.000000
6: 7 5 9 1 5 6 2 5.099020
7: 5 3 7 -1 3 7 3 2.828427
8: 6 4 8 0 4 7 3 3.162278
9: 7 5 9 1 5 7 3 4.000000
如果有任何改进建议，我将不胜感激。真实数据量很大，特别欢迎大家提速。
如果我理解正确，OP 希望 知道每家商店的任意半径范围内有多少家其他商店。
下面的代码详细阐述了 OP 关于 non-equi self-join 的想法，但结合了 每个 i 的分组.它将一个新列附加到 ex，其中包含给定半径内请求的其他商店数量。
library(data.table)
# sample data with an additional data point to make the use case less uniform
ex <- data.table(x = c(5, 6, 7, 5.5),
y = c(1, 2, 3, 1.5))
ex
x y
1: 5.0 1.0
2: 6.0 2.0
3: 7.0 3.0
4: 5.5 1.5
radius <- 2 # parameter
bb_cols <- c("x.min", "x.max", "y.min", "y.max")
ex[, (bb_cols) := .(x - radius, x + radius, y - radius, y + radius)][
, count := .SD[.SD, on = .(x >= x.min, x <= x.max, y >= y.min, y <= y.max),
sum((x.x - i.x)^2 + (x.y - i.y)^2 <= radius^2) - 1L,
by = .EACHI]$V1][
, (bb_cols) := NULL]
ex
x y count
1: 5.0 1.0 2
2: 6.0 2.0 3
3: 7.0 3.0 1
4: 5.5 1.5 2
编辑：没有链接
响应 OP 的 ，可以在没有 chaining 的情况下编写代码：
ex[, (bb_cols) := .(x - radius, x + radius, y - radius, y + radius)]
ex[, count := .SD[.SD, on = .(x >= x.min, x <= x.max, y >= y.min, y <= y.max),
sum((x.x - i.x)^2 + (x.y - i.y)^2 <= radius^2) - 1L,
by = .EACHI]$V1]
ex[, (bb_cols) := NULL]
所有三个操作通过引用更新因此预计不会对性能产生影响。
验证
为了验证正确性，我们可以绘制位置和圆圈：
library(ggplot2)
library(ggforce)
ggplot(ex) +
geom_point(aes(x, y, colour = factor(seq_along(x)))) +
geom_circle(aes(x0 = x, y0 = y, r = radius, colour = factor(seq_along(x)))) +
coord_fixed() +
ggtitle(sprintf("Store locations and circles of radius %.1f", radius)) +
guides(colour = "none")
因此，位置 (6, 2) 的商店在 2 的半径（绿色圆圈）内还有 3 家其他商店。
当然，相邻店铺的数量取决于给定的radius。半径越小，代码找到的商店越少：
有
radius <- 1
我们得到
ex
x y count
1: 5.0 1.0 1
2: 6.0 2.0 1
3: 7.0 3.0 0
4: 5.5 1.5 2
相应地
因此，位置 (7, 3) 的商店在半径 1（蓝色圆圈）内没有其他商店。
说明
代码相当简洁，使用了data.table chaining.
bb_cols <- c("x.min", "x.max", "y.min", "y.max") 是辅助列的名称，它将保存 non-equi self-join 所需的边界框的坐标。 ex[, (bb_cols) := .(x - radius, x + radius, y - radius, y + radius)] 通过引用 创建辅助列 ，即不复制整个 data.table。请注意，不需要原始数据集的副本。.SD[.SD, on = .(x >= x.min, x <= x.max, y >= y.min, y <= y.max), sum((x.x - i.x)^2 + (x.y - i.y)^2 <= radius^2) - 1L, by = .EACHI]是关键部分。它在 non-equi self-join.
中实现 聚合
连接选取边界框内的所有位置。 by = .EACHI 聚合每个边界框的所有选取位置。
sum((x.x - i.x)^2 + (x.y - i.y)^2 <= radius^2) 计算边界框内有多少个位置位于圆内。请注意，比较不需要实际距离，因此我们可以避免计算量大的 sqrt().
边界框中心的商店包含在计数中。通过减去一个以仅计算圆圈内的 other 家商店来纠正这一点。- 默认情况下，包含计数的列已命名为
V1。它是从连接结果中选取的，并作为列 count 通过引用附加到 ex 。
- 最后，辅助列被移除参考。
我 post 前阵子讨论过 calculate sets of distances using big data 的效率如何。那里的答案并没有完全回答我的问题，因为这个问题更具计算性（例如，如何在不进行大量合并的情况下找到 k 最近邻以计算每个点彼此之间的距离）而不是关于自己计算距离。
我们已经想出了一个在 data.table 中使用非 equi 连接的解决方案，但我非常感谢任何关于这是否是 go/ways 改进的正确方法的反馈速度等等。
问题概览
（有关更多详细信息，请参阅上面的链接 post。）我们有一个（实际上非常大）包含商店位置的数据集，例如：
library(tidyverse)
library(data.table)
ex <- data.table(x = c(5,6,7),
y = c(1,2,3))
我们想知道在每家商店的任意半径范围内还有多少家商店。这样做的简单但在计算上不可行的方法基本上是将数据集与其自身合并并计算每个商店组合的距离。显然，当您拥有数百万家商店时，这种方法会产生巨大的中间数据集，以及其他问题。
建议的解决方案
好的，现在开始我想要反馈的部分。本质上，基本思想是在每个商店周围画一个正方形，使用非相等连接查找商店“正方形”内的所有其他商店，然后计算距离并仅将商店保留在商店的正确半径内总店（即在初始正方形内画一个圆圈）。
为此，首先我们复制商店数据集并计算将保存正方形尺寸的变量：
# make copy of original dataframe with new names
ex.c <- rename(.data = ex, xc = x, yc = y)
# make bounding box for each point in original dataframe
ex$min.x <- ex$x - 2
ex$max.x <- ex$x + 2
ex$min.y <- ex$y - 2
ex$max.y <- ex$y + 2
然后我们将商店数据集与其本身合并，要求其他商店的坐标在主商店的任意数量内，这里是 2 个单位：
ex5 <- ex[ex.c,
.(x.x, x.min.x, x.max.x, x.min.y, x.min.y, i.xc, i.yc),
on = .(max.x >= xc, min.x <= xc,
max.y >= yc, min.y <= yc),
allow.cartesian = T]
ex5
x.x x.min.x x.max.x x.min.y x.max.y i.xc i.yc
1: 5 3 7 -1 3 5 1
2: 6 4 8 0 4 5 1
3: 7 5 9 1 5 5 1
4: 5 3 7 -1 3 6 2
5: 6 4 8 0 4 6 2
6: 7 5 9 1 5 6 2
7: 5 3 7 -1 3 7 3
8: 6 4 8 0 4 7 3
9: 7 5 9 1 5 7 3
然后我们计算距离，从那里我们可以保留所需半径内的商店：
## that does the square. now we need to cut to the circle
ex5[,
dist := sqrt((x.x - i.xc)^2 + (x.x - i.yc)^2)]
ex5
x.x x.min.x x.max.x x.min.y x.max.y i.xc i.yc dist
1: 5 3 7 -1 3 5 1 4.000000
2: 6 4 8 0 4 5 1 5.099020
3: 7 5 9 1 5 5 1 6.324555
4: 5 3 7 -1 3 6 2 3.162278
5: 6 4 8 0 4 6 2 4.000000
6: 7 5 9 1 5 6 2 5.099020
7: 5 3 7 -1 3 7 3 2.828427
8: 6 4 8 0 4 7 3 3.162278
9: 7 5 9 1 5 7 3 4.000000
如果有任何改进建议，我将不胜感激。真实数据量很大，特别欢迎大家提速。
如果我理解正确，OP 希望 知道每家商店的任意半径范围内有多少家其他商店。
下面的代码详细阐述了 OP 关于 non-equi self-join 的想法，但结合了 每个 i 的分组.它将一个新列附加到 ex，其中包含给定半径内请求的其他商店数量。
library(data.table)
# sample data with an additional data point to make the use case less uniform
ex <- data.table(x = c(5, 6, 7, 5.5),
y = c(1, 2, 3, 1.5))
ex
x y 1: 5.0 1.0 2: 6.0 2.0 3: 7.0 3.0 4: 5.5 1.5
radius <- 2 # parameter
bb_cols <- c("x.min", "x.max", "y.min", "y.max")
ex[, (bb_cols) := .(x - radius, x + radius, y - radius, y + radius)][
, count := .SD[.SD, on = .(x >= x.min, x <= x.max, y >= y.min, y <= y.max),
sum((x.x - i.x)^2 + (x.y - i.y)^2 <= radius^2) - 1L,
by = .EACHI]$V1][
, (bb_cols) := NULL]
ex
x y count 1: 5.0 1.0 2 2: 6.0 2.0 3 3: 7.0 3.0 1 4: 5.5 1.5 2
编辑：没有链接
响应 OP 的
ex[, (bb_cols) := .(x - radius, x + radius, y - radius, y + radius)]
ex[, count := .SD[.SD, on = .(x >= x.min, x <= x.max, y >= y.min, y <= y.max),
sum((x.x - i.x)^2 + (x.y - i.y)^2 <= radius^2) - 1L,
by = .EACHI]$V1]
ex[, (bb_cols) := NULL]
所有三个操作通过引用更新因此预计不会对性能产生影响。
验证
为了验证正确性，我们可以绘制位置和圆圈：
library(ggplot2)
library(ggforce)
ggplot(ex) +
geom_point(aes(x, y, colour = factor(seq_along(x)))) +
geom_circle(aes(x0 = x, y0 = y, r = radius, colour = factor(seq_along(x)))) +
coord_fixed() +
ggtitle(sprintf("Store locations and circles of radius %.1f", radius)) +
guides(colour = "none")
因此，位置 (6, 2) 的商店在 2 的半径（绿色圆圈）内还有 3 家其他商店。
当然，相邻店铺的数量取决于给定的radius。半径越小，代码找到的商店越少：
有
radius <- 1
我们得到
ex
x y count 1: 5.0 1.0 1 2: 6.0 2.0 1 3: 7.0 3.0 0 4: 5.5 1.5 2
相应地
因此，位置 (7, 3) 的商店在半径 1（蓝色圆圈）内没有其他商店。
说明
代码相当简洁，使用了data.table chaining.
bb_cols <- c("x.min", "x.max", "y.min", "y.max")是辅助列的名称，它将保存 non-equi self-join 所需的边界框的坐标。ex[, (bb_cols) := .(x - radius, x + radius, y - radius, y + radius)]通过引用 创建辅助列 ，即不复制整个 data.table。请注意，不需要原始数据集的副本。.SD[.SD, on = .(x >= x.min, x <= x.max, y >= y.min, y <= y.max), sum((x.x - i.x)^2 + (x.y - i.y)^2 <= radius^2) - 1L, by = .EACHI]是关键部分。它在 non-equi self-join.
中实现 聚合 连接选取边界框内的所有位置。by = .EACHI聚合每个边界框的所有选取位置。
sum((x.x - i.x)^2 + (x.y - i.y)^2 <= radius^2)计算边界框内有多少个位置位于圆内。请注意，比较不需要实际距离，因此我们可以避免计算量大的sqrt().
边界框中心的商店包含在计数中。通过减去一个以仅计算圆圈内的 other 家商店来纠正这一点。- 默认情况下，包含计数的列已命名为
V1。它是从连接结果中选取的，并作为列count通过引用附加到ex。 - 最后，辅助列被移除参考。