java - 查找具有不同长度的特征向量的相似性度量

Question

在Java中，我们如何找到两个具有不同长度的 vector 之间的相似性度量。 考虑我们有

V1 = [1, 0, 0, 1, 1]
V1 = [1, 0, 1, 0, 1, 0, 1, 0]

我正在寻找 Jaccard 系数或 Sørensen–Dice 系数以外的相似性度量

Answer 1

正如有人已经评论过的那样，可能的替代方案是编辑距离，有时也称为编辑距离。

编辑距离是一个函数，它为每对字符串 A 和 B 分配一个自然数 n，它表示最小数的操作需要将 A 转换为 B。允许的操作是

1. 从A中删除一个符号，
2. 将符号插入A，
3. 替换A中的符号。

请注意，编辑距离是对称的(对于将 A 转换为 B 的任何操作序列)，可以构造一个“反转”操作序列，其中将 B 转换为 A。

维基百科关于 Levenshtein distance 的文章列出了一些有用的属性。

最后，作为示例，让我们转换两个 vector :

[10011]
// Insert 1 into position 2:
[101011]
// Insert 0 into position 5:
[1010101]
// Insert 0 into position 7:
[10101010]

我们发现了 3 个操作的序列。如果我们设法证明不存在更短的序列，那么我们可以得出结论，V1 和 V2 之间的距离为 3。好吧，考虑到 Levenshtein 距离始终为 < em>至少两个字符串之间的大小差异(想想为什么会这样)，然后我们就得到了结论:

levenshtein_distance(V1,V2) == 3 // returns true!

希望这有帮助!