找到 R 中字符串组之间的距离

Question

我有一个非常大的数据集，看起来像这样。

我有两种类型的数据框

我的参考data.frame

ref=c("cake","brownies")

和我的实验data.frame

expr=c("cak","cakee","cake", "rownies","browwnies")

我想匹配 ref 和 expr data.frames 和找到它们之间的 levenstein 距离。输出可能如下所示...

ref   expr      distance 
cake  cak         1
cake  cakee       1
cake  cake        0
cake  rownies    ...

在我测量了他们的 levenstein 距离后，我想将距离小于 3 的任何字符串聚类到一个聚类中，我的数据可能看起来像

ref        expr      distance  cluster
cake       cak         1         1
cake       cakee       1         1
cake       cake        0         1
brownies   rownies     1         2 
brownies   browwnies   1         2

任何关于如何继续前进的帮助或建议都非常感谢。目前我正在尝试很多 R 包中找到 data.frame 之间的距离，例如

library("DescTools")

但它们似乎效果不佳。

Answer 1

这里有 2 种方法，一种是严格监督和更多手动，另一种是采用较少监督的方式。包 stringdist 有一堆不同的距离度量，其中 "lv" 是 Levenshtein。我添加了一个额外的观察“poundcake”来测试一个离参考词太远的词。

选项 1

获取每个实验字符串与其中一个参考字符串之间的距离矩阵。如果您有 2 个相似的参考字符串，或者如果一个实验词同样接近 2 个参考字符串，这可能会出现问题，但它适用于这种简单的情况。然后将矩阵重塑为数据框，并沿参考词计数以获得簇数。过滤距离小于阈值的情况。

library(dplyr)
library(stringdist)

max_dist <- 3

ref <- c("cake", "brownies")
expr <- c("cak", "cakee", "cake", "poundcake", "rownies","browwnies")

mtx <- stringdistmatrix(ref, expr, method = "lv", useNames = "strings")

mtx
#>          cak cakee cake poundcake rownies browwnies
#> cake       1     1    0         5       6         8
#> brownies   8     7    7         8       1         1

df1 <- as.data.frame(mtx) %>%
  tibble::rownames_to_column("ref") %>%
  tidyr::pivot_longer(-ref, names_to = "expr", values_to = "dist") %>%
  mutate(clust = as.numeric(forcats::as_factor(ref))) # could also use data.table::rleid

df1 %>%
  filter(dist <= max_dist)
#> # A tibble: 5 × 4
#>   ref      expr       dist clust
#>   <chr>    <chr>     <dbl> <dbl>
#> 1 cake     cak           1     1
#> 2 cake     cakee         1     1
#> 3 cake     cake          0     1
#> 4 brownies rownies       1     2
#> 5 brownies browwnies     1     2

选项 2

这可能适用于更复杂的情况。我用它来纠正人名的拼写，我有一套不完整的正确标签可供使用。将所有词组合成 1 个向量，得到一个距离矩阵（这次它将是正方形），然后使用阈值作为切割树的高度从层次聚类中创建聚类。然后，您可以匹配每个词的参考以获得聚类的标签。

这里的缺点是，您有几行用于非实验性的参考词——请注意，例如，“brownies”在实验性字符串中从未拼写正确，但现在您可以观察到这一点。

all_words <- c(ref, expr)
hc <- hclust(stringdistmatrix(all_words, method = "lv", useNames = "strings"))

df2 <- data.frame(word = c(ref, expr), 
                  clust = cutree(hc, h = max_dist)) %>%
  mutate(r = ref[clust])

df2 %>%
  filter(!is.na(r))
#>        word clust        r
#> 1      cake     1     cake
#> 2  brownies     2 brownies
#> 3       cak     1     cake
#> 4     cakee     1     cake
#> 5      cake     1     cake
#> 6   rownies     2 brownies
#> 7 browwnies     2 brownies

找到 R 中字符串组之间的距离

Find the distance between groups of string in R

r

string

stringdist

选项 1

选项 2