r - 如何组合显示最常见字符的相似字符串

Question

在数据框中，我有一个字符串列表，这些字符串彼此相似但以 % 的差异分隔。我想将这些常见字符串组合成一个字符串，该字符串在每个位置都有最常见的字符。

数据框看起来像这样:

pattern  Freq     score rank
DT%E 37568 1138.4242    1
%TGE 37666 1018.0000    2
D%GE 37641 1017.3243    3
DTG% 37665  965.7692    4
%VGNE 34234  684.6800    5
SVGN% 34281  634.8333    6
SV%NE 34248  634.2222    7
SVG%E 34265  623.0000    8
%LGNE 41098  595.6232    9
SL%NE 41086  595.4493   10
SLGN% 41200  564.3836   11
SPT%AYNE 35082  539.7231   12
SP%AAYNE 35094  531.7273   13
SPTA%YNE 35061  531.2273   14
SPTAA%NE 35225  518.0147   15
SPTAAYN% 35144  516.8235   16
%PTAAYNE 35111  516.3382   17
S%TAAYNE 35100  516.1765   18
SPTAAY%E 35130  509.1304   19
SLG%E 41467  450.7283   20

我正在尝试使用模式列中最可能的字符串添加另一列

pattern  Freq     score rank  true_string
DT%E 37568 1138.4242    1  DTGE
%TGE 37666 1018.0000    2  DTGE
D%GE 37641 1017.3243    3  DTGE
DTG% 37665  965.7692    4  DTGE
%VGNE 34234  684.6800    5  SVGNE
SVGN% 34281  634.8333    6  SVGNE
SV%NE 34248  634.2222    7  SVGNE
SVG%E 34265  623.0000    8  SVGNE
%LGNE 41098  595.6232    9  SLGNE
SL%NE 41086  595.4493   10  SLGNE
SLGN% 41200  564.3836   11  SLGNE
SPT%AYNE 35082  539.7231   12  SPTAAYNE
SP%AAYNE 35094  531.7273   13  SPTAAYNE
SPTA%YNE 35061  531.2273   14  SPTAAYNE
SPTAA%NE 35225  518.0147   15  SPTAAYNE
SPTAAYN% 35144  516.8235   16  SPTAAYNE
%PTAAYNE 35111  516.3382   17  SPTAAYNE
S%TAAYNE 35100  516.1765   18  SPTAAYNE
SPTAAY%E 35130  509.1304   19  SPTAAYNE
SLG%E 41467  450.7283   20  SLGNE

Answer 1

这是一个棘手但有趣的问题。

这里有一些东西可以给你一些想法(并重现你的预期输出)；但是请注意，这在某种程度上是一种经验方法，它做出以下假设:

总有>=2属于相同的图案 true_string ;这是(分层)聚类方法工作所必需的(见下文)。如果您有 <2定义 true_string 的模式这行不通，这是有道理的，因为同一位置的两个字符出现的频率相同。

全部 pattern s 具有相同的长度 ;即我们只考虑单个字符替换而不考虑插入/删除。

方法

我们利用图书馆 stringdist计算字符串相似度。 stringdistmatrix提供各种距离度量(Levenshtein、Hamming 等，详情参见 ?stringdist::stringdistmatrix)。在这种情况下，我们使用 method = "qgram"因为它导致分组与您的预期输出一致(因此是较早的“经验”警告)。我不知道这对您的真实数据的概括效果如何，因此请务必记住，您可能必须使用不同的 method s 以找到“符合”您的期望的距离相似性度量。

在我们计算出字符串距离矩阵之后，我们使用层次聚类对字符串进行聚类；我们添加 grp基于垂直距离切割树的标签 v = 2 ，然后使用自定义 get_consensus_string根据 grp 推断共识字符串的函数;如开头所述，该函数假定一个 grp 内的所有字符串具有相同的长度，并为字符串中的每个位置选择出现频率最大的字符。

代码

先定制 get_consensus_string功能

library(tidyverse)
get_consensus_string <- function(x) {
    map_dfc(x, str_split, "") %>%
        rowid_to_column("pos") %>%
        gather(k, v, -pos) %>%
        group_by(pos, v) %>%
        add_count() %>%
        group_by(pos) %>%
        filter(n == max(n)) %>%
        arrange(pos, desc(v)) %>%
        dplyr::slice(1) %>%
        pull(v) %>%
        paste0(collapse = "")
}

我们现在可以添加 grp基于来自 stringdist::stringdistmatrix的字符串相似度距离矩阵的层次聚类结果的标签;我凭经验在 v = 2 的垂直距离处砍伐这里的树(这是一个可能需要调整的参数)；一旦我们有了 grp我们添加共识字符串的标签。

library(stringdist)
df %>%
    mutate(grp = cutree(hclust(stringdistmatrix(df$pattern, method = "qgram")), h = 2)) %>%
    group_by(grp) %>%
    mutate(true_string = get_consensus_string(pattern)) %>%
    ungroup()
## A tibble: 20 x 6
#   pattern   Freq score  rank   grp true_string
#   <fct>    <int> <dbl> <int> <int> <chr>
# 1 DT%E     37568 1138.     1     1 DTGE
# 2 %TGE     37666 1018      2     1 DTGE
# 3 D%GE     37641 1017.     3     1 DTGE
# 4 DTG%     37665  966.     4     1 DTGE
# 5 %VGNE    34234  685.     5     2 SVGNE
# 6 SVGN%    34281  635.     6     2 SVGNE
# 7 SV%NE    34248  634.     7     2 SVGNE
# 8 SVG%E    34265  623      8     2 SVGNE
# 9 %LGNE    41098  596.     9     3 SLGNE
#10 SL%NE    41086  595.    10     3 SLGNE
#11 SLGN%    41200  564.    11     3 SLGNE
#12 SPT%AYNE 35082  540.    12     4 SPTAAYNE
#13 SP%AAYNE 35094  532.    13     4 SPTAAYNE
#14 SPTA%YNE 35061  531.    14     4 SPTAAYNE
#15 SPTAA%NE 35225  518.    15     4 SPTAAYNE
#16 SPTAAYN% 35144  517.    16     4 SPTAAYNE
#17 %PTAAYNE 35111  516.    17     4 SPTAAYNE
#18 S%TAAYNE 35100  516.    18     4 SPTAAYNE
#19 SPTAAY%E 35130  509.    19     4 SPTAAYNE
#20 SLG%E    41467  451.    20     3 SLGNE

您可以看到最终代码非常干净，并重现了您的预期输出。

一些进一步的注释/评论

两个问题可能值得讨论:(1)如何选择合适的距离度量(2)在哪里砍树。

关于第一个问题，经验方法是尝试不同的度量并在 pattern 的层次聚类后可视化树状图。 s。

例如，对于 method = "qgram"你会做

mat <- as.matrix(stringdistmatrix(df$pattern, method = "qgram"))
rownames(mat) <- df$pattern
colnames(mat) <- df$pattern
plot(hclust(as.dist(mat)))

一旦您对聚类结果感到满意，我们就可以继续。

关于砍树，一种实用/实用的方法是检查树状图并找到我们砍树的合适高度(在我们的例子中， v = 2)；或者，如果您知道唯一的数量 true_string s 您可以在 cutree 中指定组数与 k .

在更专业的术语中，树状图的高度与使用完整链接的组之间的距离相关联(即基于最不同的对测量距离)。由于组之间的距离依次基于 pattern 之间的 q-gram-距离s 可以将高度与两个 pattern 之间的 q-gram-距离联系起来s，即两个 pattern 的 N-gram 向量之间的绝对差异s。