如何比较两个列表的相似度

[sunhk25]

现在想到的方法是如下
--方法 1--
A 列表：['aa', 'bb', 'cc']
B 列表：['bb', 'cc', 'ff', 'kk']
因为'bb'和'cc'相同所以有
A:2/3
B:2/4
所以 AB 相似度等于：(2/3 + 2/4) / 2 = 0.583
假如有 C 列表：['bb']
同样与 B 列表比较，同理 BC 相似度等于：(1/4+1/1) / 2 = 0.625
然而 AB 相似度<BC 相似度却不太理想

--方法 2--
另外一个方法就是分母用元素的合计数
AB 相似度等于：(2/(3+4) + 2/(3+4)) / 2 = 0.286
BC 相似度等于：(1/(4+1)+1/(4+1)) / 2 = 0.2
结果：AB 相似度>BC 相似度

所以正确的方案应该用数学上的那些手段来实现呢？

[youngxhui]

使用余弦距离

[aijam]

比如 edit distance，TF/IDF

[SeaRecluse]

只比较两个交叉熵，多个用余弦距离

[largecat]

还有一个
A,B 合起来总共不重复的 5 个元素，共有 2 个，所以 2/5=40 ％

BC 合计不重复 4 个，共有 1 个所以 1/4=25 ％

[cdcfishzz]

方法 2 是不正确的。
假设两个完全一样的列表，预期值为 1。
(3/(3+3)+3/(3+3))/2 ＝ 3/6≠1。

[adrianyoung]

可以参考一下 BLEU 的惩罚因子
能够解决你提到的方法一的问题

[wkc]

https://github.com/yanyiwu/simhash 文本相似度计算

[adrianyoung]

或者两个列表直接构建一个向量空间，算余弦距离

[holajamc]

In [1]: a = ['a', 'b', 'c']

In [2]: b = ['a', 'b', 'd']

In [3]: def jaccard_sim(a, b):
...: return len(set(a).union(set(b)))/len(set(a).intersection(set(b)))
...:

In [4]: jaccard_sim(a, b)
Out[4]: 2.0

杰卡德相似性

[mamahaha]

很简单，并集除以交集，数值越大越不相似

[binux]

顺序有关=>编辑距离
顺序无关=>交集并集
最终还是取决于应用

[swordspoet]

你的问题跟协同过滤的第一步有些类似，即计算物品之间的相似度，你可以把 A 和 B 当做是一条一条的交易记录，然后得到一个共现矩阵，然后将共现矩阵归一化就能得到物品之间的余弦相似度。参考推荐系统实战，第 53 页贴出了计算相似度的代码，希望对你有帮助。

[no1xsyzy]

首先两个分母含义不同的比值肯定不是算数平均或者平方平均
第二个其实就是调和平均的一半——不如直接使用调和平均
顺便考虑一下几何平均