使用data.table连接图形的组件

Question

我正在尝试根据它们是否一起处于事务中来标记地址实体ID号.

这个想法是,如果一个地址在与另一个地址的交易中,则假定该交易中的所有地址以及与这些地址的未来交易中的所有地址都归同一实体所有.

我目前在SQL中使用循环运行相当大的数据集(约150-180百万个),但我觉得R的data.table可以更快地解决这个问题并且语法更简单,我只是不确定如何做到这一点.任何帮助深表感谢!

这是一个例子:

DT <- data.table(Address=c('A','B','C','A','D','C','E'), Transaction=c(1,1,2,3,3,4,4))

Address  Transaction
      A            1
      B            1
      C            2
      A            3
      D            3
      C            4
      E            4

我正在寻找的结果如下:

Address  Transaction  Entity
      A            1       1
      B            1       1
      C            2       2
      A            3       1
      D            3       1
      C            4       2
      E            4       2

Answer 1

我会继续迭代地址.对于每个地址,找到它的伙伴/邻居并给它们都具有相同的实体ID.从地址到实体的映射可以存储在单独的表中,并在循环完成后映射到事务表.

setkey(DT,Address)
AE  <- DT[,.(Address=unique(Address),Entity=NA_integer_)]
eid <- 0L
for (a in AE$Address){

    ts      <- DT[.(a)]$Transaction
    fellows <- DT[Transaction %in% ts, unique(Address)]
    f_ent   <- AE[.(fellows)][!is.na(Entity), if (.N > 0) min(Entity) else 0L]

    a_ent <- if (f_ent == 0L){
        eid = eid + 1L
    } else {
        f_ent
    }

    AE[.(fellows),Entity:=a_ent]
}

DT[AE,Entity:=Entity][order(Transaction)]
#    Address Transaction Entity
# 1:       A           1      1
# 2:       B           1      1
# 3:       C           2      2
# 4:       A           3      1
# 5:       D           3      1
# 6:       C           4      2
# 7:       E           4      2

我很确定这是有效的,但更一般的示例数据会有所帮助.

当你面对数百万条记录时,你可能希望调整一下这个更快一点.最昂贵的一步是计算fellows.

你几乎都在标记图形的连通分量(见图论).将地址视为节点,将每个事务视为添加

• 新的地址和
• 地址之间的新链接.

R igraph包可能是有意义的; 更可能的是,它计算连通组件.(我不熟悉它.)

一般来说,如果你的数据集在增长,保持这个变量是最新的将是一个真正的头痛,我认为你应该看看你是否可以没有它.