V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
sunhk25
V2EX  ›  Python

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

  •  
  •   sunhk25 · 2019-03-29 10:18:07 +08:00 · 6101 次点击
    这是一个创建于 2066 天前的主题,其中的信息可能已经有所发展或是发生改变。
    
    现在想到的方法是如下
    --方法 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 相似度
    
    所以正确的方案应该用数学上的那些手段来实现呢?
    
    第 1 条附言  ·  2019-03-29 19:14:29 +08:00
    • 谢谢各位的意见,我想做的就是类似文章相似度。
    • 比较的对象一个是手写的规整的文本,另一个是口头说话的声音识别结果。
    • 顺序和结构不是特别重视,也就是求核心的意思(单词)相似度。
    • 正在尝试交集并集,调和平均,余弦距离
    13 条回复    2019-03-29 14:31:30 +08:00
    youngxhui
        1
    youngxhui  
       2019-03-29 10:22:40 +08:00 via Android   ❤️ 1
    使用余弦距离
    aijam
        2
    aijam  
       2019-03-29 10:26:51 +08:00   ❤️ 1
    比如 edit distance,TF/IDF
    SeaRecluse
        3
    SeaRecluse  
       2019-03-29 10:28:03 +08:00   ❤️ 1
    只比较两个交叉熵,多个用余弦距离
    largecat
        4
    largecat  
       2019-03-29 10:33:23 +08:00 via Android   ❤️ 1
    还有一个
    A,B 合起来总共不重复的 5 个元素,共有 2 个,所以 2/5=40 %

    BC 合计不重复 4 个,共有 1 个所以 1/4=25 %
    cdcfishzz
        5
    cdcfishzz  
       2019-03-29 10:57:52 +08:00 via Android   ❤️ 1
    方法 2 是不正确的。
    假设两个完全一样的列表,预期值为 1。
    (3/(3+3)+3/(3+3))/2 = 3/6≠1。
    adrianyoung
        6
    adrianyoung  
       2019-03-29 11:19:00 +08:00   ❤️ 1
    可以参考一下 BLEU 的惩罚因子
    能够解决你提到的方法一的问题
    wkc
        7
    wkc  
       2019-03-29 11:25:50 +08:00   ❤️ 1
    adrianyoung
        8
    adrianyoung  
       2019-03-29 11:27:58 +08:00   ❤️ 1
    或者两个列表直接构建一个向量空间,算余弦距离
    holajamc
        9
    holajamc  
       2019-03-29 11:38:15 +08:00   ❤️ 1
    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
        10
    mamahaha  
       2019-03-29 11:50:17 +08:00   ❤️ 1
    很简单,并集除以交集,数值越大越不相似
    binux
        11
    binux  
       2019-03-29 12:07:29 +08:00 via Android   ❤️ 2
    顺序有关=>编辑距离
    顺序无关=>交集并集
    最终还是取决于应用
    swordspoet
        12
    swordspoet  
       2019-03-29 12:58:06 +08:00   ❤️ 1
    你的问题跟协同过滤的第一步有些类似,即计算物品之间的相似度,你可以把 A 和 B 当做是一条一条的交易记录,然后得到一个共现矩阵,然后将共现矩阵归一化就能得到物品之间的余弦相似度。参考推荐系统实战,第 53 页贴出了计算相似度的代码,希望对你有帮助。
    no1xsyzy
        13
    no1xsyzy  
       2019-03-29 14:31:30 +08:00   ❤️ 1
    首先两个分母含义不同的比值肯定不是算数平均或者平方平均
    第二个其实就是调和平均的一半——不如直接使用调和平均
    顺便考虑一下几何平均
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   917 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 21:42 · PVG 05:42 · LAX 13:42 · JFK 16:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.