如何在MATLAB中实现谱核函数？

Question

频谱核函数通过计算两个字符串之间相同的n元组数量来操作字符串。例如，'tool'有三个2元组（'to'，'oo'和'ol'），而'tool'和'fool'之间的相似度为2（共有'oo'和'ol'）。

我该如何编写一个MATLAB函数来计算这个度量值？

- versioner

---

听起来你对于创建支持向量机分类器的内核函数感兴趣。然而，仅使用汉明距离无法充分利用可用信息。请参考这里的源链接：http://en.wikipedia.org/wiki/String_kernel 祝你好运！我也在尝试同样的事情。 - user882358

Answer 1

第一步是创建一个能够为给定字符串生成n-gram的函数。一种向量化的方法是利用一些巧妙的索引方式。

function [subStrings, counts] = n_gram(fullString, N)
  if (N == 1)
    [subStrings, ~, index] = unique(cellstr(fullString.'));  %.'# Simple case
  else
    nString = numel(fullString);
    index = hankel(1:(nString-N+1), (nString-N+1):nString);
    [subStrings, ~, index] = unique(cellstr(fullString(index)));
  end
  counts = accumarray(index, 1);
end

这里使用函数HANKEL，首先创建一个索引矩阵，选择给定字符串中每组唯一的N长度子串。用此索引矩阵对给定字符串进行索引将创建一个字符数组，每行有一个N长度的子串。然后，函数CELLSTR将字符数组的每一行放入单元格数组的一个单元格中。接下来，函数UNIQUE删除重复的子串，如果需要，函数ACCUMARRAY用于计算每个唯一子串的出现次数。

有了上面的函数，您可以使用INTERSECT函数轻松地计算两个字符串之间共享的n-gram数量:

subStrings1 = n_gram('tool',2);
subStrings2 = n_gram('fool',2);
sharedStrings = intersect(subStrings1,subStrings2);
nShared = numel(sharedStrings);

- gnovice

---

你应该在函数n_gram中添加subStrings = intersect(subStrings, subStrings)以避免重复。例如，n_gram('hubbub', 2)在原始公式中会有一个重复的'ub'成员。 - mtrw

@mtrw：说得好，但是使用UNIQUE函数会更好。我会相应地进行更新。 - gnovice

哎呀，是的，UNIQUE 更为适合。 - mtrw

Answer 2

你所需要的是汉明距离，如果你执行doc pdist，你可以得到更好的描述。

A=['Marcin'; 'Martin'; 'Marsha']  %data

squareform(pdist(A, 'hamming'))  returns

         0    0.1667    0.5000

    0.1667         0    0.5000

    0.5000    0.5000         0

这个表单展示了有多少个字母是不同的。'Marcin'和'Martin'之间的差异是6个字母中的1个，所以你得到1/6=0.1667。'Marcin'与'Marsha'相比有6个字母中的3个不同，因此为3/6=0.5。
如果您想要实际不同字母的数量，只需将整个矩阵乘以A的长度即可。

- Marcin

---

这似乎并不完全符合问题所描述的情况。 - gnovice