algorithm - 两个数据集或数组之间的相似性

Question

假设我有一个如下所示的数据集:

{A:1, B:3, C:6, D:6}

我还有一个其他集合的列表来比较我的特定集合:

{A:1, B:3, C:6, D:6},  
{A:2, B:3, C:6, D:6},  
{A:99, B:3, C:6, D:6},  
{A:5, B:1, C:6, D:9},  
{A:4, B:2, C:2, D:6}

我的条目可以可视化为一个表格(有四列，A、B、C、D 和 E)。

如何找到最相似的集合？对于此示例，第 1 行是完美匹配，第 2 行紧随其后，而第 3 行相距很远。

我正在考虑计算一个简单的增量，例如:Abs(a1 - a2) + Abs(b1 - b2) + etc 可能得到 correlation value对于具有最佳增量的条目。

这是一个有效的方法吗？这个问题的名称是什么？

Answer 1

“距离”或“相似度”可能指的是这类问题。

像您所做的那样，简单地计算绝对差的总和应该会很有效。这称为 Manhattan distance .用数学术语来说，就是:∑<sub>x ∈ (a,b,c,d)</sub> Abs(x<sub>1</sub> - x<sub>2</sub>) .

尽管最佳衡量标准实际上取决于您想要的行为。

比率可能是一个更好的主意。

考虑像 1000000, 5, 5, 5 这样的东西对比999995, 5, 5, 5和 1000000, 0, 5, 5 .

根据上面的公式，第一个与第二个和第三个具有相同的相似度。

如果不需要这样(因为 999995 可以被认为非常接近 1000000 ，而 0 可以被认为离 5 很远)，你应该除以两者的最大值计算每个距离。

∑<sub>x ∈ (a,b,c,d)</sub> [ Abs(x<sub>1</sub> - x<sub>2</sub>) / max(x<sub>1</sub>, x<sub>2</sub>) ]

这会将每个数字放在 0 和 1 之间，这是值之间的百分比差异。

这意味着，对于我们上面的例子，我们会考虑 1000000, 5, 5, 5和 999995, 5, 5, 5非常相似(因为上面的总和将是 |1000000-999995|/1000000 + 0 + 0 + 0 = 0.000005 )和 1000000, 5, 5, 5和 1000000, 0, 5, 5将被认为更加不同(因为总和将为 |0+5|/5 + 0 + 0 + 0 = 1 )。

如果可能出现负值，则需要适当更新公式。您需要根据要解决的问题来决定如何处理它。应该10 to 0或多或少不同于(或等同于)5 to -5 ？

元素是否可以在任何程度上互换？

考虑像 A=1, B=2, C=3, D=4 这样的东西和 A=4, B=1, C=2, D=3 .

虽然每个单独的元素都发生了变化，但集合仍然由 1, 2, 3, 4 组成并且每个元素只是简单地移动 1 个位置(除了 4 )。

对于某些问题，这根本无关紧要，上面的内容与从 A=1, B=11, C=21, D=31 没有什么不同至 A=2, B=12, C=22, D=32 .对于其他问题，它可能非常相关。

对于像字符串或数组这样的序列，插入、删除或移动元素的想法可能很有意义。如果是这样，你会想看看 edit distance ，其中一个常见的是 Levenshtein distance .您可能还想考虑修改它以考虑单个值相差多少(但这不是微不足道的)。

对于像集合这样的东西，元素是可以互换的，但元素上实际上没有严格的顺序( {1, 2, 3} 与 {3, 1, 2} 相同)。如果是这种情况，最简单的方法可能是对值进行排序并仅使用编辑距离。您还可以通过某种方式同时遍历两者，这样您就可以更轻松地考虑值之间的差异。