通过名称的模糊匹配创建唯一ID（通过使用R的同意）

Question

使用R，我试图在一个按年和城市结构的数据集中匹配人们的名字。由于一些拼写错误，精确匹配是不可能的，所以我试图使用grep（）来模糊匹配名称。

数据集的样本块的结构如下所示：

df <- data.frame(matrix( c("1200013","1200013","1200013","1200013","1200013","1200013","1200013","1200013",                             "1996","1996","1996","1996","2000","2000","2004","2004","AGUSTINHO FORTUNATO FILHO","ANTONIO PEREIRA NETO","FERNANDO JOSE DA COSTA","PAULO CEZAR FERREIRA DE ARAUJO","PAULO CESAR FERREIRA DE ARAUJO","SEBASTIAO BOCALOM RODRIGUES","JOAO DE ALMEIDA","PAULO CESAR FERREIRA DE ARAUJO"), ncol=3,dimnames=list(seq(1:8),c("citycode","year","candidate")) ))

整洁的版本：

  citycode year                      candidate
1  1200013 1996      AGUSTINHO FORTUNATO FILHO
2  1200013 1996           ANTONIO PEREIRA NETO
3  1200013 1996         FERNANDO JOSE DA COSTA
4  1200013 1996 PAULO CEZAR FERREIRA DE ARAUJO
5  1200013 2000 PAULO CESAR FERREIRA DE ARAUJO
6  1200013 2000    SEBASTIAO BOCALOM RODRIGUES
7  1200013 2004                JOAO DE ALMEIDA
8  1200013 2004 PAULO CESAR FERREIRA DE ARAUJO

我想分别在每个城市登记，几年后是否有候选人出现。例如，在示例中，

PAULO CEZAR FERREIRA DE ARAUJO

保罗·塞萨尔·费雷拉·德阿劳乔

出现两次（拼写错误）。整个数据集中的每个候选者都应该被分配一个唯一的数字候选ID。数据集相当大（约5500个城市。100K条目），所以一个有点有效的编码将是有帮助的。关于如何实施这一点，有什么建议吗？

编辑：以下是我的尝试（在目前评论的帮助下），它在完成手头的任务方面非常缓慢（低效）。对此有何改进建议？

f <- function(x) {matches <- lapply(levels(x), agrep, x=levels(x),fixed=TRUE, value=FALSE)
                  levels(x) <- levels(x)[unlist(lapply(matches, function(x) x[1]))]
                  x
                }

temp <- tapply(df$candidate, df$citycode, f, simplify=TRUE)
df$candidatenew <- unlist(temp)
df$spellerror <- ifelse(as.character(df$candidate)==as.character(df$candidatenew), 0, 1)

编辑2：现在以良好的速度运行。问题是每一步都要与许多因素进行比较（谢谢你指出这一点，蓝先生）。将比较减少到一组（即一个城市）中的候选人，在5秒钟内运行80,000行命令——这是我可以忍受的速度。

df$candidate <- as.character(df$candidate)

f <- function(x) {x <- as.factor(x)
                  matches <- lapply(levels(x), agrep, x=levels(x),fixed=TRUE, value=FALSE)
                  levels(x) <- levels(x)[unlist(lapply(matches, function(x) x[1]))]
                  as.character(x)
                }

temp <- tapply(df$candidate, df$citycode, f, simplify=TRUE)
df$candidatenew <- unlist(temp)
df$spellerror <- ifelse(as.character(df$candidate)==as.character(df$candidatenew), 0, 1)

Answer 1

好的，鉴于重点是效率，我建议如下。

首先，请注意，根据第一原理的效率顺序，我们可以预测精确匹配将比grep快得多，grep将比模糊grep快得多。所以精确匹配，然后对剩余的观测值进行模糊grep。

第二，矢量化和避免循环。apply命令并不一定更快，因此如果可以，请坚持使用本机矢量化。所有的grep命令都是本机矢量化的，但是很难避免使用*ply或循环将每个元素与其他元素的矢量进行比较。

第三，利用外部信息缩小问题范围。只对每个城市或州的名字进行模糊匹配，这将大大减少必须进行的比较次数。

您可以结合第一和第三个原则：您甚至可以尝试对每个字符串的第一个字符进行精确匹配，然后在其中进行模糊匹配。

Answer 2

这是我的机会。这可能不是很有效，但我认为它会完成这项工作。我假设df$候选人是类因素。

#fuzzy matches candidate names to other candidate names
#compares each pair of names only once
##by looking at names that have a greater index
matches <- unlist(lapply(1:(length(levels(df[["candidate"]]))-1),
    function(x) {max(x,x + agrep(
        pattern=levels(df[["candidate"]])[x], 
        x=levels(df[["candidate"]])[-seq_len(x)]
    ))}
))
#assigns new levels (omits the last level because that doesn't change)
levels(df[["candidate"]])[-length(levels(df[["candidate"]]))] <- 
    levels(df[["candidate"]])[matches]