基于地址和宗地所有权关联的个体家庭户分组方法咨询

业务判定规则 #

判定同一家庭户需要同时满足两个条件：

1. 所有个体居住在相同地址
2. 个体间至少存在一宗地的直接或间接所有权关联
   其中所有权关联分为两类：

• 直接关联：两人共同拥有同一宗地
• 间接关联：形成链式交叉关联，两人共有一宗地，其中一人又与另一人共有其他宗地，且所有人均居住在同一地址

规则示例 #

• 若个体（9）单独居住在地址（C），即便另有个体（6）也拥有宗地（s），他也单独为一个家庭户。
• 若个体（12和13）共同居住在地址（F）且共有宗地（w），则属于同一家庭户。若三人共同居住在地址（B），但仅个体（7和8）共有宗地（r），居住在同地址的第三人（6）仅拥有宗地（m），则仅共有宗地的两人属于同一家庭户。
• 若地址（A）共居住4人（1、2、3和4），其中1、2、3通过宗地（m、n和o）的所有权关联，则三人属于同一家庭户；同地址的个体（4）不持有上述三宗宗地，仅持有宗地（p），不属于该家庭户。

需求说明 #

现有三个字段：id_address（地址ID）、id_owner（个体所有者ID）、id_parcel（宗地ID），需要生成全局唯一的家庭户编号id_household，最终输出效果如下：

id_address id_owner id_parcel id_household
          A        1         m            1
          A        1         n            1
          A        2         n            1
          A        2         o            1
          A        3         o            1
          A        4         p            2
          A        5         q            3
          B        6         s            4
          B        7         r            5
          B        8         r            5
          C        9         s            6
          D       10         t            7
          E       11         u            8
          E       11         v            8
          F       12         w            9
          F       13         w            9

原始测试数据（R语言结构）：

structure(list(id_address = c("A", "A", "A", "A", "A", "A", "A", 
"B", "B", "B", "C", "D", "E", "E", "F", "F"), id_owner = c(1L, 
1L, 2L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 11L, 12L, 13L
), id_parcel = c("m", "n", "n", "o", "o", "p", "q", "s", "r", 
"r", "s", "t", "u", "v", "w", "w"), id_household = c(1L, 1L, 
1L, 1L, 1L, 2L, 3L, 4L, 5L, 5L, 6L, 7L, 8L, 8L, 9L, 9L)), class = "data.frame", row.names = c(NA, 
-16L))

总数据量为80万行，循环实现效率过低，需要高性能处理方案。

高性能实现方案（R语言） #

该问题本质是同地址下所有者与宗地构成的二分图连通分量识别，使用图算法可高效实现，80万行数据处理耗时可控制在秒级：

# 加载依赖包
library(igraph)
library(dplyr)

# 处理逻辑
df_result <- df %>%
  # 按地址分组，不同地址的家庭户完全独立
  group_by(id_address) %>%
  group_modify(~{
    # 构造二分图边：所有者-宗地关联
    edges <- .x %>% select(id_owner, id_parcel) %>% mutate_all(as.character)
    g <- graph_from_data_frame(edges, directed = FALSE)
    # 计算连通分量
    comp <- components(g)
    # 匹配所有者对应的连通分量编号
    .x$household_local <- comp$membership[as.character(.x$id_owner)]
    .x
  }) %>%
  ungroup() %>%
  # 生成全局唯一家庭户ID
  mutate(id_household = as.integer(factor(paste(id_address, household_local)))) %>%
  select(-household_local)

内容的提问来源于stack exchange，提问作者Hugo Périlleux Sanchez