离散相似度度量算法

Question

假设我有两个列表，每个列表都包含一个共同超集的不同子集，是否有算法可以给我提供相似度测量？

例如：

A = { John，Mary，Kate，Peter }，B = { Peter，James，Mary，Kate }

这两个列表有多相似？请注意，我不知道共同超集的所有元素。

更新： 我表述不清，并且可能以草率的方式使用了“set”一词。我很抱歉。 澄清：顺序很重要。 如果相同的元素占据列表中相同的位置，则该元素的相似性最高。 相同元素之间的距离越大，则相似性越低。 如果元素仅存在于其中一个列表中，则相似性甚至更低。

我甚至可以添加额外的维度，较低的索引具有更大的价值，因此a[1]==b[1]比a[9]==b[9]更有价值，但这主要是因为我很好奇。

- Cubed

---

一个好的相似度测量取决于数据和应用的约束条件。顺序重要吗？ - Holstebroe

谢谢，Holstebroe。需要澄清的是，顺序对相似性很重要。如果 A_1 和 B_1 都是约翰，那将会更加相似。 - Cubed

感谢所有的回答。我认为其中许多都是正确和有效的。不幸的是，我只能设置一个被接受的答案，这让我很烦恼，因为我想给你们所有人以荣誉。 - Cubed

Answer 1

Jaccard指数（又称Tanimoto系数），恰好用于OP问题中提到的用例。

Tanimoto系数tau等于Nc除以Na + Nb - Nc，或者

tau = Nc / (Na + Nb - Nc)

• Na：第一个集合中的项目数量

• Nb：第二个集合中的项目数量

• Nc：两个集合的交集，或者是a和b共有的独特项目数

以下是用Python编写的Tanimoto函数：

def tanimoto(x, y) :
  w = [ ns for ns in x if ns not in y ]
  return float(len(w) / (len(x) + len(y) - len(w)))

- doug

---

为什么要重新发明这个？好答案。 - Brian Stinar

在离散情况下（如此情况），这有时也被称为Jaccard度量（http://en.wikipedia.org/wiki/Jaccard_index）。 - mhum

Answer 2

我会探讨两种策略：

1. 将列表视为集合，并应用集合运算（交集、差集）
2. 将列表视为符号字符串，并应用Levenshtein算法

- Ekkehard.Horner

---

有趣。你会如何使用莱文斯坦算法处理仅存在于一个列表中的元素？这是我在解决问题时遇到的一个问题。我可以计算距离的“成本/惩罚”，但在一个列表中根本不存在的成本是多少呢？ - Cubed

假设您的问题可以进行“莱文斯坦距离”计算，那么在A中包含但不在B中的元素应该被视为插入。 - Ekkehard.Horner

Answer 3

如果您真正拥有集合（即，元素只是存在或不存在，没有附加计数），并且只有两个集合，那么将共享元素的数量相加并除以总元素数量可能是最好的选择。

如果您拥有（或可以获得）计数和/或超过两个集合，则可以使用类似于余弦相似度或TFIDF（词频*逆文档频率）的方法来做得更好。

后者试图给出在所有（或几乎所有）“文档”中出现的单词较低的权重-即，一组单词的集合。

- Jerry Coffin

Answer 4

你对“相似度测量”有什么定义？如果你只想知道两个集合中有多少项是共同的，你可以找到 A 和 B 的基数，将基数相加并从 A 和 B 的并集的基数中减去。

- gpcz

---

好的，我之前表述不清楚。我对这里的活跃度和答案质量感到非常惊讶，是积极的惊讶！在我的情况中，“相似性”包括顺序，因此两个相同元素之间的距离越大，它们就越不相似。同时，如果一个元素在其中一个列表中根本不存在，那么它的相似度必须比在两个列表中都存在但位置不同的情况下要低。 - Cubed

Answer 5

如果顺序很重要，您可以使用Levenshtein距离或其他类型的编辑距离。

- Peter Popov