离散相似性度量算法

Question

鉴于我有两个列表，每个列表都包含一个公共(public)超集的单独子集，是 有没有一种算法可以给我进行相似性测量？

例子:

A = {约翰、玛丽、凯特、彼得}和B = {彼得、詹姆斯、玛丽、凯特}

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

更新: 我不清楚，我可能草率地使用了“集合”这个词。我很抱歉。 澄清:顺序很重要。 如果相同的元素在列表中占据相同的位置，则我们对该元素的相似度最高。 相同元素相距越远，相似性越低。 如果元素仅存在于其中一个列表中，则相似度甚至更低。

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

Answer 1

Jaccard 指数(又名 Tanimoto 系数) 恰好用于 OP 问题中列举的用例。

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

tau = Nc / (Na + Nb - Nc)

• Na，第一组的项目数

• Nb，第二组的项目数

• Nc，两个集合的交集，或者唯一项的数量 a 和 b 通用

这里是 Tanimoto 编码为 Python 函数:

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)))