R中的字符串核函数

Question

R中的字符串核函数

6

我一直在使用R语言中“Kernlab”包中提供的stringdot函数。以下是我的代码：

library(kernlab)
x <- c("1","2","3")
y <- c("3","2","1")
lst <- list(x, y)
sk <- stringdot(length = 2, lambda = 1.2, type = "exponential", normalized = TRUE)
q <- kernelMatrix(sk,lst)

据我所知，指数核将创建长度为2的子字符串。例如，在此处，第一个向量的字符串将是1-2,1-3,2-3，而第二个向量的字符串将是3-2,3-1,2-1。它将尝试通过创建给定长度的各种子字符串并根据给定的lambda值减少子字符串的权重来匹配输入。

按照我的预期，输出应该包含(x,x)和(y,y)的值为1，(x,y)的值为0，因为给定的输入之间没有共同的子字符串，但输出显示(x,y)对的值为0.4723。

我不明白为什么x和y之间的相似度是0.4723。

- does_it_matter

关于指数字符串核，我熟悉“H Lodhi”在“使用字符串核进行文本分类”中提出的指数字符串核的工作原理。我无法找到kernlab软件包中使用的核的参考文献，并且Lodhi和这个kernlab的结果不匹配。请说明这个核与Lodhi的字符串子序列核之间的主要区别。 - does_it_matter

字符串内核不应该比较所有可能的对，而是应该比较n-gram吗？ - Drey

@Drey 没错，我之前不知道n-gram这个术语。我认为我上面给出的长度为2的字符串就像是双字母组合，对吗？ - does_it_matter

几乎 - 它们将是1-2，2-3但对于x不是1-3。而且对于y是3-2，2-1。 - Drey

你的意思是子序列之间不允许有间隔，但是当我用其他核函数（例如在同一软件包中可用的频谱）替换指数函数时，由于不允许间隔，(x,y)之间的相似度应该为零。 - does_it_matter

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nick Kennedy · Accepted Answer

通过查看 kernelMatrix 和 stringdot 的源代码，可以了解您的输入正在发生什么。

当一个列表作为x传递给kernelMatrix时，它会执行以下操作：

if (is(x, "list")) 
  x <- sapply(x, paste, collapse = "")

在您的情况下，这意味着您的lst输入变为c("123", "321")。 kernelMatrix然后取这个向量，并生成具有以下模式的矩阵（其中sk是stringkernel函数）：

sk("123", "123")    sk("123", "321")
                    sk("321", "321")

下左角的单元格随后被填充为上右角，然后整个矩阵通过除以左上角单元格乘以右下角单元格的平方根来进行归一化。

您可以通过执行以下操作检查各个值是否匹配：

stringdot(type = "exponential", lambda = 1.2)(123, 321)
#[1] 0.4723893

值得注意的是，在type =“ exponential”下，length参数没有任何作用。每种类型的stringkernel只有零个或一个参数，对于exponential，它是给出衰减的lambda。子字符串权重随着匹配子字符串变短而衰减，而lambda是衰减因子。

如手册所述，stringdot（type =“ spectrum”）使用length，仅匹配长度至少为该长度的子序列。由于123和321之间没有匹配的子字符串> = 2个字符，因此比较结果为零。

还应注意，换行符（"\n"）附加到每个字符串，并且即使是单个字符匹配，使用type =“ exponential”也将产生> 0的结果，因此不可能获得零的结果。例如：

stringdot(type = "exponential", lambda = 1.2)("blowfish", "mage")
#[1] 0.05274495

最后，看起来@Rahul想要一个Lodhi's 2002 algorithm的R语言实现。 kernlab并没有实现这个算法，我也不知道是否有R包可以实现。似乎github上有一个Python实现，但我还没有检查代码是否能运行，更别说是否能得到所需的输出了。如果有人有兴趣，可以重新在R中实现Python代码，如果觉得有用/必要的话。

针对评论的补充编辑：

归一化字符串核函数的结果取决于每个字符串与其自身相似的程度。

sk_u <- stringdot(type = "exponential", lambda = 1.2, normalized = FALSE)
sk_n <- stringdot(type = "exponential", lambda = 1.2, normalized = TRUE)

lapply(list(unnormalised = sk_u, normalised = sk_n), function(f) {
  c(
    "ab,xyzabqr" = f("ab", "xyzabqr"),
    "ab,abpmnop" = f("ab", "abpmnop"),
    "ab,ab" = f("ab"),
    "xyzabqr,xyzabqr" = f("xyzabqr"),
    "abpmnop,abpmnop" = f("abpmnop")
  )
})

#$unnormalised
#     ab,xyzabqr      ab,abpmnop           ab,ab xyzabqr,xyzabqr abpmnop,abpmnop 
#       3.194444        3.194444        4.467593       20.814201       22.480868 

#$normalised
#     ab,xyzabqr      ab,abpmnop           ab,ab xyzabqr,xyzabqr abpmnop,abpmnop 
#      0.3312674       0.3187513       1.0000000       1.0000000       1.0000000

可以看出，未经归一化的情况下，两种比较的结果是相同的。然而，由于归一化的结果等于（例如）sk_u("ab", "xyzabqr") / sqrt(sk_u("ab") * sk_u("xyzabqr"))，因此sk_n("ab", "xyzabqr")得分更高的原因与"abpmnop"中有两个p有关。