如何优化大规模数据框下的哈氏距离最近邻查询效率？

问题描述 #

现有两个R语言数据框df_1和df_2，需为df_1中的每个个体计算其与df_2所有个体的哈氏距离，筛选出距离最近的5个个体，并统计这些距离的最小值、最大值、均值、中位数及标准差。原始代码在小规模数据下可正常运行，但数据规模扩大时，因循环计算、全量矩阵存储等问题，效率会显著下降，需要适配大规模场景的优化方案。

原始方案的核心瓶颈 #

1. 双重循环计算距离：逐行逐列调用哈氏距离函数，R语言的循环效率极低，数据量增大后耗时呈指数增长
2. 全量距离矩阵存储：构建nrow(df_1)*nrow(df_2)规模的矩阵，当数据量达到万级以上时，会出现内存不足的问题
3. 低效的分组统计：使用base R的aggregate、tapply等函数，分组运算效率远低于专门的高效数据处理工具

优化方案 #

方案一：向量化计算 + data.table高效处理（适合中等规模数据） #

利用geosphere包的向量化特性直接计算全距离矩阵，结合data.table完成高效分组统计，避免循环和冗余内存占用。

set.seed(123)
library(geosphere)
library(data.table)

# 生成测试数据
df_1 <- data.frame(
  name_1 = c("john", "david", "alex", "kevin", "trevor", "xavier", "tom", "michael", "troy", "kelly", "chris", "henry", "taylor", "ryan", "peter"),
  lon = rnorm(15, mean = -74.0060, sd = 0.01),
  lat = rnorm(15, mean = 40.7128, sd = 0.01)
)

df_2 <- data.frame(
  name_2 = c("matthew", "tyler", "sebastian", "julie", "anna", "tim", "david", "nigel", "sarah", "steph", "sylvia", "boris", "theo", "malcolm"),
  lon = rnorm(14, mean = -74.0060, sd = 0.01),
  lat = rnorm(14, mean = 40.7128, sd = 0.01)
)

# 1. 向量化计算全距离矩阵（底层C实现，比R循环快100倍以上）
dist_matrix <- distHaversine(df_1[, c("lon", "lat")], df_2[, c("lon", "lat")])

# 2. 提取每个df_1个体的前5近邻索引和距离
top5_indices <- t(apply(dist_matrix, 1, function(x) order(x)[1:5]))
top5_distances <- t(apply(dist_matrix, 1, function(x) sort(x)[1:5]))

# 3. 构建近邻结果表
final <- data.table(
  name_1 = rep(df_1$name_1, each = 5),
  name_2 = df_2$name_2[as.vector(top5_indices)],
  distance = as.vector(top5_distances)
)

# 4. 高效分组统计并整理结果
final_summary <- final[, .(
  min_distance = min(distance),
  max_distance = max(distance),
  mean_distance = mean(distance),
  median_distance = median(distance),
  sd_distance = sd(distance),
  closest_people = paste(sort(name_2), collapse = ", "),
  closest_1 = sort(name_2)[1],
  closest_2 = sort(name_2)[2],
  closest_3 = sort(name_2)[3],
  closest_4 = sort(name_2)[4],
  closest_5 = sort(name_2)[5]
), by = name_1]

# 查看结果
print(final_summary)

方案二：空间近邻搜索（适合超大规模数据） #

当df_1和df_2规模达到十万级甚至百万级时，全距离矩阵会占用大量内存，此时可使用空间索引技术（如KD-tree）直接搜索近邻，无需计算全量距离。这里使用nngeo包的st_nn函数实现：

set.seed(123)
library(nngeo)
library(sf)
library(data.table)

# 生成测试数据
df_1 <- data.frame(
  name_1 = c("john", "david", "alex", "kevin", "trevor", "xavier", "tom", "michael", "troy", "kelly", "chris", "henry", "taylor", "ryan", "peter"),
  lon = rnorm(15, mean = -74.0060, sd = 0.01),
  lat = rnorm(15, mean = 40.7128, sd = 0.01)
)

df_2 <- data.frame(
  name_2 = c("matthew", "tyler", "sebastian", "julie", "anna", "tim", "david", "nigel", "sarah", "steph", "sylvia", "boris", "theo", "malcolm"),
  lon = rnorm(14, mean = -74.0060, sd = 0.01),
  lat = rnorm(14, mean = 40.7128, sd = 0.01)
)

# 转换为sf空间对象（WGS84坐标系）
sf_1 <- st_as_sf(df_1, coords = c("lon", "lat"), crs = 4326)
sf_2 <- st_as_sf(df_2, coords = c("lon", "lat"), crs = 4326)

# 基于空间索引搜索每个点的前5近邻，返回索引和距离
nn_result <- st_nn(sf_1, sf_2, k = 5, returnDist = TRUE)

# 整理结果数据
final <- data.table(
  name_1 = rep(df_1$name_1, each = 5),
  name_2 = unlist(lapply(nn_result$nn, function(idx) df_2$name_2[idx])),
  distance = unlist(nn_result$dist)
)

# 分组统计并拆分近邻
final_summary <- final[, .(
  min_distance = min(distance),
  max_distance = max(distance),
  mean_distance = mean(distance),
  median_distance = median(distance),
  sd_distance = sd(distance),
  closest_people = paste(sort(name_2), collapse = ", "),
  closest_1 = sort(name_2)[1],
  closest_2 = sort(name_2)[2],
  closest_3 = sort(name_2)[3],
  closest_4 = sort(name_2)[4],
  closest_5 = sort(name_2)[5]
), by = name_1]

# 查看结果
print(final_summary)

优化效果说明 #

• 向量化计算：替代R循环，利用底层C实现的距离函数，计算速度提升100~1000倍
• 内存优化：方案二无需存储全距离矩阵，内存占用从O(nm)降至O(nk)（k为近邻数，此处为5）
• 分组效率：data.table的分组运算比base R快5~50倍，尤其适合大规模分组场景

内容的提问来源于stack exchange，提问作者stats_noob