按条件的字符串距离矩阵
String distance matrix by criteria
我写了一个脚本来做一些公司名称的模糊匹配。我正在将一些并非总是完全正确的公司名称（即可能存在小的拼写错误或缺少 "inc." 后缀）与 "correct" 公司名称和 ID 的语料库进行匹配。显然，重点是正确地将 ID 附加到并非总是正确的公司名称。
这是我正在匹配的数据集的一些非常简化的版本（我还没有使用 zip 部分，但稍后会回来）：
df <- data.frame(zip = c("4760","5445", "2200"), company = c("company x", "company y", "company z"))
corpus <- data.frame(zip = c("4760","5445", "2200", "2200", "2200"), company = c("company x inc.", "company y inc.", "company z inc.", "company a inc.", "company b inc."), id = c(12121212, 23232323, 34343434, 56565656, 67676767))
df
zip company
1 4760 company x
2 5445 company y
3 2200 company z
corpus
zip company id
1 4760 company x inc. 12121212
2 5445 company y inc. 23232323
3 2200 company z inc. 34343434
4 2200 company a inc. 56565656
5 2200 company b inc. 67676767
然后我使用下面的代码创建一个字符串距离矩阵
library(stringdist)
distance.method <- c("jw")
string.dist.matrix <- stringdistmatrix(tolower(corpus$company),
tolower(df$company),
method = distance.method,
nthread = getOption("sd_num_thread"))
string.dist.matrix
[,1] [,2] [,3]
[1,] 0.1190476 0.1798942 0.1798942
[2,] 0.1798942 0.1190476 0.1798942
[3,] 0.1798942 0.1798942 0.1190476
[4,] 0.1798942 0.1798942 0.1798942
[5,] 0.1798942 0.1798942 0.1798942
然后我继续匹配最小距离对。通常我想将 4000 家公司与 4,5 mio 的语料库相匹配。公司，这至少需要一些计算能力。我有一个想法，不是计算所有可能对之间的字符串距离，而是只为共享邮政编码的人计算它。正如我所看到的，与我在此处使用简化数据说明的情况相比，对于更复杂的情况，结果将是更小的计算量和更精确的模糊匹配。
简而言之，我想要的结果矩阵是这样的：
[,1] [,2] [,3]
[1,] 0.1190476 NA NA
[2,] NA 0.1190476 NA
[3,] NA NA 0.1190476
[4,] NA NA 0.1798942
[5,] NA NA 0.1798942
我只是想不出办法。有什么想法吗？
我有一些想法。如果你不需要你的距离矩阵，你可以这样解决。我使用 dplyr 是因为我更了解它。您可以将代码分成几部分而不是一个 dplyr 命令。或者使用 data.table。那甚至可能更快。
采取的步骤：
- 在 zip 上使用内部连接连接 df 和语料库。这将删除所有不需要的记录，并且您的公司名称彼此相邻。
- 计算公司名称之间的距离
- 按原公司分组
- 按最小距离过滤
这些步骤避免使用先创建矩阵然后寻找最小值或将其他值放入 NA。
library(stringdist)
library(dplyr)
df <- data.frame(zip = c("4760","5445", "2200"), company = c("company x", "company y", "company z"))
corpus <- data.frame(zip = c("4760","5445", "2200", "2200", "2200"), company = c("company x inc.", "company y inc.", "company z inc.", "company a inc.", "company b inc."), id = c(12121212, 23232323, 34343434, 56565656, 67676767))
distance.method <- c("jw")
combined_min_distance <- inner_join(df, corpus, by = "zip" ) %>%
mutate(distance = stringdist(tolower(combined$company.x),
tolower(combined$company.y),
method = distance.method,
nthread = getOption("sd_num_thread"))) %>%
group_by(company.x) %>%
filter(distance == min(distance))
combined_min_distance
zip company.x company.y id distance
(fctr) (fctr) (fctr) (dbl) (dbl)
1 2200 company z company z inc. 34343434 0.1190476
2 4760 company x company x inc. 12121212 0.1190476
3 5445 company y company y inc. 23232323 0.1190476
下面的方法使用 dplyr 并从 phiver 的 joining 两个数据帧的方法开始，然后继续生成类似于您的 string.dist.matrix 的数据帧或数据压缩 "key value" 形式的框架。我已将另一家公司添加到您的 df 数据框中，以包含具有相同 df zip 的多家公司的情况。
距离矩阵版本
是：
df <- data.frame(zip = c("4760","5445", "2200","2200"), company = c("company x", "company y", "company z","company a"))
corpus <- data.frame(zip = c("4760","5445", "2200", "2200", "2200"), company = c("company x inc.", "company y inc.", "company z inc.", "company a inc.", "company b inc."),
id = c(12121212, 23232323, 34343434, 56565656, 67676767))
# large matrix version
library(dplyr)
dist_mat <- inner_join(corpus, df, by = "zip") %>%
mutate(corpus_co=tolower(as.character(company.x)), df_co=tolower(as.character(company.y)), company.x=NULL, company.y=NULL) %>%
group_by(zip) %>%
do( { dist_df=data.frame(unique(.$corpus_co),
stringdistmatrix(unique(.$corpus_co), unique(.$df_co), method=distance.method), stringsAsFactors=FALSE);
colnames(dist_df) = c("corpus_co", unique(.$df_co));
dist_df})
结果
zip corpus_co company z company a company x company y
(fctr) (chr) (dbl) (dbl) (dbl) (dbl)
1 2200 company z inc. 0.1190476 0.1798942 NA NA
2 2200 company a inc. 0.1798942 0.1190476 NA NA
3 2200 company b inc. 0.1798942 0.1798942 NA NA
4 4760 company x inc. NA NA 0.1190476 NA
5 5445 company y inc. NA NA NA 0.1190476
但是，在您的 df 矩阵中有 4000 行，完整的字符串距离矩阵非常大并且有很多 NA。更高效的版本使用 tidyr 包中的 gather 函数来生成 key value 格式的结果。在这种方法中，一些变量形成唯一键，然后具有关联值。 tidyr 包的小插图更详细地解释了这一点。在您的例子中，corpus 公司名称和 df 公司名称形成 key，它们名称之间的字符串距离是 value。这是为每个邮政编码完成的，因此永远不会存储完整的字符串距离矩阵。您可能还会发现这更便于您进行后续分析。该代码仅在最后一行与以前的版本不同。
library(tidyr)
dist_keyval <- inner_join(corpus, df, by = "zip") %>%
mutate(corpus_co=tolower(as.character(company.x)), df_co=tolower(as.character(company.y)), company.x=NULL, company.y=NULL) %>%
group_by(zip) %>%
do( { dist_df=data.frame(unique(.$corpus_co),
stringdistmatrix(unique(.$corpus_co), unique(.$df_co), method=distance.method), stringsAsFactors=FALSE);
colnames(dist_df) = c("corpus_co", unique(.$df_co));
gather(dist_df, key=df_co, value=str_dist, -corpus_co)})
给出结果
zip corpus_co df_co str_dist
(fctr) (chr) (chr) (dbl)
1 2200 company z inc. company z 0.1190476
2 2200 company a inc. company z 0.1798942
3 2200 company b inc. company z 0.1798942
4 2200 company z inc. company a 0.1798942
5 2200 company a inc. company a 0.1190476
6 2200 company b inc. company a 0.1798942
7 4760 company x inc. company x 0.1190476
8 5445 company y inc. company y 0.1190476
已编辑
找到与每个 df_co 的最小距离的 corpus_co 的代码是：
dist_min <- dist_keyval %>% group_by(zip, df_co) %>%
slice(which.min(str_dist))
要将列添加到最终结果，您可以加入用于进行字符串距离计算的公司名称的形式（即小写名称），如下所示：
final_result <- corpus %>% mutate(lower_co = tolower(as.character(company))) %>%
right_join(dist_min, by = c("zip", "lower_co" = "corpus_co") ) %>%
select(c(df_co, company, id), everything(), -lower_co)
这给出了
df_co company id zip str_dist
1 company a company a inc. 56565656 2200 0.1190476
2 company z company z inc. 34343434 2200 0.1190476
3 company x company x inc. 12121212 4760 0.1190476
4 company y company y inc. 23232323 5445 0.1190476
最后一个 select 展示了如何将列重新排列成特定的顺序。
您可以使用 stringdist::amatch 并避免计算完整的 stringdist 矩阵。
df <- data.frame(zip = c("4760","5445", "2200"), company = c("company x", "company y", "company z"))
corpus <- data.frame(zip = c("4760","5445", "2200", "2200", "2200"), company = c("company x inc.", "company y inc.", "company z inc.", "company a inc.", "company b inc."), id = c(12121212, 23232323, 34343434, 56565656, 67676767))
i <- stringdist::amatch(df$company,corpus$company,maxDist=5)
merged <- data.frame(df$company,corpus$company[i])
merged
> merged
df.company corpus.company.i.
1 company x company x inc.
2 company y company y inc.
3 company z company z inc.
最好在之前做一些字符串清理，这样你就知道距离只是实际拼写错误造成的（注意下面的maxDist）。
lookup <- gsub(" inc.$","",corpus$company)
i2 <- stringdist::amatch(df$company,lookup,maxDist=2)
merged2 <- data.frame(df$company,corpus$company[i2])
我写了一个脚本来做一些公司名称的模糊匹配。我正在将一些并非总是完全正确的公司名称（即可能存在小的拼写错误或缺少 "inc." 后缀）与 "correct" 公司名称和 ID 的语料库进行匹配。显然，重点是正确地将 ID 附加到并非总是正确的公司名称。
这是我正在匹配的数据集的一些非常简化的版本（我还没有使用 zip 部分，但稍后会回来）：
df <- data.frame(zip = c("4760","5445", "2200"), company = c("company x", "company y", "company z"))
corpus <- data.frame(zip = c("4760","5445", "2200", "2200", "2200"), company = c("company x inc.", "company y inc.", "company z inc.", "company a inc.", "company b inc."), id = c(12121212, 23232323, 34343434, 56565656, 67676767))
df
zip company
1 4760 company x
2 5445 company y
3 2200 company z
corpus
zip company id
1 4760 company x inc. 12121212
2 5445 company y inc. 23232323
3 2200 company z inc. 34343434
4 2200 company a inc. 56565656
5 2200 company b inc. 67676767
然后我使用下面的代码创建一个字符串距离矩阵
library(stringdist)
distance.method <- c("jw")
string.dist.matrix <- stringdistmatrix(tolower(corpus$company),
tolower(df$company),
method = distance.method,
nthread = getOption("sd_num_thread"))
string.dist.matrix
[,1] [,2] [,3]
[1,] 0.1190476 0.1798942 0.1798942
[2,] 0.1798942 0.1190476 0.1798942
[3,] 0.1798942 0.1798942 0.1190476
[4,] 0.1798942 0.1798942 0.1798942
[5,] 0.1798942 0.1798942 0.1798942
然后我继续匹配最小距离对。通常我想将 4000 家公司与 4,5 mio 的语料库相匹配。公司，这至少需要一些计算能力。我有一个想法，不是计算所有可能对之间的字符串距离，而是只为共享邮政编码的人计算它。正如我所看到的，与我在此处使用简化数据说明的情况相比，对于更复杂的情况，结果将是更小的计算量和更精确的模糊匹配。
简而言之，我想要的结果矩阵是这样的：
[,1] [,2] [,3]
[1,] 0.1190476 NA NA
[2,] NA 0.1190476 NA
[3,] NA NA 0.1190476
[4,] NA NA 0.1798942
[5,] NA NA 0.1798942
我只是想不出办法。有什么想法吗？
我有一些想法。如果你不需要你的距离矩阵，你可以这样解决。我使用 dplyr 是因为我更了解它。您可以将代码分成几部分而不是一个 dplyr 命令。或者使用 data.table。那甚至可能更快。
采取的步骤：
- 在 zip 上使用内部连接连接 df 和语料库。这将删除所有不需要的记录，并且您的公司名称彼此相邻。
- 计算公司名称之间的距离
- 按原公司分组
- 按最小距离过滤
这些步骤避免使用先创建矩阵然后寻找最小值或将其他值放入 NA。
library(stringdist)
library(dplyr)
df <- data.frame(zip = c("4760","5445", "2200"), company = c("company x", "company y", "company z"))
corpus <- data.frame(zip = c("4760","5445", "2200", "2200", "2200"), company = c("company x inc.", "company y inc.", "company z inc.", "company a inc.", "company b inc."), id = c(12121212, 23232323, 34343434, 56565656, 67676767))
distance.method <- c("jw")
combined_min_distance <- inner_join(df, corpus, by = "zip" ) %>%
mutate(distance = stringdist(tolower(combined$company.x),
tolower(combined$company.y),
method = distance.method,
nthread = getOption("sd_num_thread"))) %>%
group_by(company.x) %>%
filter(distance == min(distance))
combined_min_distance
zip company.x company.y id distance
(fctr) (fctr) (fctr) (dbl) (dbl)
1 2200 company z company z inc. 34343434 0.1190476
2 4760 company x company x inc. 12121212 0.1190476
3 5445 company y company y inc. 23232323 0.1190476
下面的方法使用 dplyr 并从 phiver 的 joining 两个数据帧的方法开始，然后继续生成类似于您的 string.dist.matrix 的数据帧或数据压缩 "key value" 形式的框架。我已将另一家公司添加到您的 df 数据框中，以包含具有相同 df zip 的多家公司的情况。
距离矩阵版本 是：
df <- data.frame(zip = c("4760","5445", "2200","2200"), company = c("company x", "company y", "company z","company a"))
corpus <- data.frame(zip = c("4760","5445", "2200", "2200", "2200"), company = c("company x inc.", "company y inc.", "company z inc.", "company a inc.", "company b inc."),
id = c(12121212, 23232323, 34343434, 56565656, 67676767))
# large matrix version
library(dplyr)
dist_mat <- inner_join(corpus, df, by = "zip") %>%
mutate(corpus_co=tolower(as.character(company.x)), df_co=tolower(as.character(company.y)), company.x=NULL, company.y=NULL) %>%
group_by(zip) %>%
do( { dist_df=data.frame(unique(.$corpus_co),
stringdistmatrix(unique(.$corpus_co), unique(.$df_co), method=distance.method), stringsAsFactors=FALSE);
colnames(dist_df) = c("corpus_co", unique(.$df_co));
dist_df})
结果
zip corpus_co company z company a company x company y
(fctr) (chr) (dbl) (dbl) (dbl) (dbl)
1 2200 company z inc. 0.1190476 0.1798942 NA NA
2 2200 company a inc. 0.1798942 0.1190476 NA NA
3 2200 company b inc. 0.1798942 0.1798942 NA NA
4 4760 company x inc. NA NA 0.1190476 NA
5 5445 company y inc. NA NA NA 0.1190476
但是，在您的 df 矩阵中有 4000 行，完整的字符串距离矩阵非常大并且有很多 NA。更高效的版本使用 tidyr 包中的 gather 函数来生成 key value 格式的结果。在这种方法中，一些变量形成唯一键，然后具有关联值。 tidyr 包的小插图更详细地解释了这一点。在您的例子中，corpus 公司名称和 df 公司名称形成 key，它们名称之间的字符串距离是 value。这是为每个邮政编码完成的，因此永远不会存储完整的字符串距离矩阵。您可能还会发现这更便于您进行后续分析。该代码仅在最后一行与以前的版本不同。
library(tidyr)
dist_keyval <- inner_join(corpus, df, by = "zip") %>%
mutate(corpus_co=tolower(as.character(company.x)), df_co=tolower(as.character(company.y)), company.x=NULL, company.y=NULL) %>%
group_by(zip) %>%
do( { dist_df=data.frame(unique(.$corpus_co),
stringdistmatrix(unique(.$corpus_co), unique(.$df_co), method=distance.method), stringsAsFactors=FALSE);
colnames(dist_df) = c("corpus_co", unique(.$df_co));
gather(dist_df, key=df_co, value=str_dist, -corpus_co)})
给出结果
zip corpus_co df_co str_dist
(fctr) (chr) (chr) (dbl)
1 2200 company z inc. company z 0.1190476
2 2200 company a inc. company z 0.1798942
3 2200 company b inc. company z 0.1798942
4 2200 company z inc. company a 0.1798942
5 2200 company a inc. company a 0.1190476
6 2200 company b inc. company a 0.1798942
7 4760 company x inc. company x 0.1190476
8 5445 company y inc. company y 0.1190476
已编辑
找到与每个 df_co 的最小距离的 corpus_co 的代码是：
dist_min <- dist_keyval %>% group_by(zip, df_co) %>%
slice(which.min(str_dist))
要将列添加到最终结果，您可以加入用于进行字符串距离计算的公司名称的形式（即小写名称），如下所示：
final_result <- corpus %>% mutate(lower_co = tolower(as.character(company))) %>%
right_join(dist_min, by = c("zip", "lower_co" = "corpus_co") ) %>%
select(c(df_co, company, id), everything(), -lower_co)
这给出了
df_co company id zip str_dist
1 company a company a inc. 56565656 2200 0.1190476
2 company z company z inc. 34343434 2200 0.1190476
3 company x company x inc. 12121212 4760 0.1190476
4 company y company y inc. 23232323 5445 0.1190476
最后一个 select 展示了如何将列重新排列成特定的顺序。
您可以使用 stringdist::amatch 并避免计算完整的 stringdist 矩阵。
df <- data.frame(zip = c("4760","5445", "2200"), company = c("company x", "company y", "company z"))
corpus <- data.frame(zip = c("4760","5445", "2200", "2200", "2200"), company = c("company x inc.", "company y inc.", "company z inc.", "company a inc.", "company b inc."), id = c(12121212, 23232323, 34343434, 56565656, 67676767))
i <- stringdist::amatch(df$company,corpus$company,maxDist=5)
merged <- data.frame(df$company,corpus$company[i])
merged
> merged
df.company corpus.company.i.
1 company x company x inc.
2 company y company y inc.
3 company z company z inc.
最好在之前做一些字符串清理，这样你就知道距离只是实际拼写错误造成的（注意下面的maxDist）。
lookup <- gsub(" inc.$","",corpus$company)
i2 <- stringdist::amatch(df$company,lookup,maxDist=2)
merged2 <- data.frame(df$company,corpus$company[i2])