资讯专栏INFORMATION COLUMN

文本相似度 余弦值相似度算法 VS L氏编辑距离(动态规划)

fxp / 1856人阅读

摘要:本文对两种文本相似度算法进行比较。余弦值相似度算法最小编辑距离法氏编辑距离基于词条空间编辑距离,又称距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。但是同时也可以看出余弦相似度得到的结果相对比较高一些。

本文由作者祝娜授权网易云社区发布。

本文对两种文本相似度算法进行比较。余弦值相似度算法 VS 最小编辑距离法
1、L氏编辑距离(基于词条空间)
编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

算法实现步骤:

1 设置n为字符串s的长度。("我是个小仙女")
设置m为字符串t的长度。("我不是个小仙女")
如果n等于0,返回m并退出。
如果m等于0,返回n并退出。
构造两个向量v0[m+1] 和v1[m+1],串联0..m之间所有的元素。
2 初始化 v0 to 0..m。
3 检查 s (i from 1 to n) 中的每个字符。
4 检查 t (j from 1 to m) 中的每个字符
5 如果 s[i] 等于 t[j],则编辑代价cost为 0;
如果 s[i] 不等于 t[j],则编辑代价cost为1。
6 设置单元v1[j]为下面的最小值之一:
a、紧邻该单元上方+1:v1[j-1] + 1
b、紧邻该单元左侧+1:v0[j] + 1
c、该单元对角线上方和左侧+cost:v0[j-1] + cost
7 在完成迭代 (3, 4, 5, 6) 之后,v1[m]便是编辑距离的值。

我们得到最小编辑距离为1那么它们的相似度为 (1-ld/(double)Math.max(str1.length(), str2.length()));

1 - 1/8=7/8.

其算法实现(java):

public static float levenshtein(String str1,String str2) {  
    //计算两个字符串的长度。  
    int len1 = str1.length();  
    int len2 = str2.length();  
    //建立上面说的数组,比字符长度大一个空间  
    int[][] dif = new int[len1 + 1][len2 + 1];  
    //赋初值,步骤B。  
    for (int a = 0; a <= len1; a++) {  
        dif[a][0] = a;  
    }  
    for (int a = 0; a <= len2; a++) {  
        dif[0][a] = a;  
    }  
    //计算两个字符是否一样,计算左上的值  
    int temp;  
    for (int i = 1; i <= len1; i++) {  
        for (int j = 1; j <= len2; j++) {  
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {  
                temp = 0;  
            } else {  
                temp = 1;  
            }  
            //取三个值中最小的  
            dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,  
                    dif[i - 1][j] + 1);  
        }  
    }  

    float similarity =1 - (float) dif[len1][len2] / Math.max(str1.length(), str2.length());  
    return similarity;
}

2、余弦值(基于权值空间)

关于余弦相似度可以参照 百度词条 余弦相似度

通过测量两个向量之间的角的余弦值来度量它们之间的相似性。0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。所以,它通常用于文件比较。

算法步骤
预处理→文本特征项选择→加权→生成向量空间模型后计算余弦。

具体步骤见附件: 余弦相似度算法步骤解释.docx
其算法实现(java):

public static double getSimilarity(String doc1, String doc2) { if (doc1 != null && doc1.trim().length() > 0 && doc2 != null && doc2.trim().length() > 0) {

        MapAlgorithmMap = new HashMap();            // 将两个字符串中的中文字符以及出现的总数封装到,AlgorithmMap中
        for (int i = 0; i < doc1.length(); i++) {                char d1 = doc1.charAt(i);                if (isHanZi(d1)) {                    int charIndex = getGB2312Id(d1);                    if (charIndex != -1) {                        int[] fq = AlgorithmMap.get(charIndex);                        if (fq != null && fq.length == 2) {
                        fq[0]++;
                    } else {
                        fq = new int[2];
                        fq[0] = 1;
                        fq[1] = 0;
                        AlgorithmMap.put(charIndex, fq);
                    }
                }
            }
        }            for (int i = 0; i < doc2.length(); i++) {                char d2 = doc2.charAt(i);                if (isHanZi(d2)) {                    int charIndex = getGB2312Id(d2);                    if (charIndex != -1) {                        int[] fq = AlgorithmMap.get(charIndex);                        if (fq != null && fq.length == 2) {
                        fq[1]++;
                    } else {
                        fq = new int[2];
                        fq[0] = 0;
                        fq[1] = 1;
                        AlgorithmMap.put(charIndex, fq);
                    }
                }
            }
        }

        Iteratoriterator = AlgorithmMap.keySet().iterator();            double sqdoc1 = 0;            double sqdoc2 = 0;            double denominator = 0;            while (iterator.hasNext()) {                int[] c = AlgorithmMap.get(iterator.next());
            denominator += c[0] * c[1];
            sqdoc1 += c[0] * c[0];
            sqdoc2 += c[1] * c[1];
        }            double origin = denominator / Math.sqrt(sqdoc1 * sqdoc2);            if (String.valueOf(origin).equals("NaN")) {                return Double.valueOf("0");
        }
        BigDecimal bg = new BigDecimal(origin);            double f1 = bg.setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();            return f1;
    } else {            throw new NullPointerException(" the Document is null or have not cahrs!!");
    }
}    public static boolean isHanZi(char ch) {        // 判断是否汉字
    return (ch >= 0x4E00 && ch <= 0x9FA5);

}    /**
 * 根据输入的Unicode字符,获取它的GB2312编码或者ascii编码,
 *
 * @param ch
 *            输入的GB2312中文字符或者ASCII字符(128个)
 * @return ch在GB2312中的位置,-1表示该字符不认识
 */
public static short getGB2312Id(char ch) {        try {            byte[] buffer = Character.toString(ch).getBytes("GB2312");            if (buffer.length != 2) {                // 正常情况下buffer应该是两个字节,否则说明ch不属于GB2312编码,故返回"?",此时说明不认识该字符
            return -1;
        }            int b0 = (buffer[0] & 0x0FF) - 161; // 编码从A1开始,因此减去0xA1=161
        int b1 = (buffer[1] & 0x0FF) - 161; // 第一个字符和最后一个字符没有汉字,因此每个区只收16*6-2=94个汉字
        return (short) (b0 * 94 + b1);
    } catch (UnsupportedEncodingException e) {
        e.printStackTrace();
    }        return -1;
}

现在对两种计算相似度的算法进行比较:

编辑距离相似度运行结果:

"第六章 字符编码" 与 "第一章 设计模式" 的相似度为:0.07159507274627686

"第六章 字符编码" 与 "第二章 python学习" 的相似度为:0.06676656007766724

"第六章 字符编码" 与 "第三章 python简介" 的相似度为:0.08275055885314941

"第六章 字符编码" 与 "第四章 输入输出" 的相似度为:0.1878122091293335

"第六章 字符编码" 与 "第五章 数据类型和变量" 的相似度为:0.20358151197433472

"第六章 字符编码" 与 "第六章 字符编码" 的相似度为:1.0

"第六章 字符编码" 与 "第七章 list" 的相似度为:0.20995670557022095

runtime:989毫秒

L编辑距离的时间 算法采用矩阵的方式,计算两个字符串之间的变化步骤,会遍历两个文本中的每一个字符两两比较,可以推断出时间复杂度至少为 document1.length × document2.length

cos相似度运行结果:

"第六章 字符编码" 与 "第一章 设计模式" 的相似度为:0.5

"第六章 字符编码" 与 "第二章 python学习" 的相似度为:0.59

"第六章 字符编码" 与 "第三章 python简介" 的相似度为:0.68

"第六章 字符编码" 与 "第四章 输入输出" 的相似度为:0.62

"第六章 字符编码" 与 "第五章 数据类型和变量" 的相似度为:0.72

"第六章 字符编码" 与 "第六章 字符编码" 的相似度为:1.0

"第六章 字符编码" 与 "第七章 list" 的相似度为:0.59

runtime:400毫秒

使用余弦定理计算文本效率相对比较高:其算法复杂度大致为:document1.length + document2.length。

但是同时也可以看出 余弦相似度得到的结果相对比较高一些。使用分词或者过滤掉一些常用词会对结果的准确性更有利。

使用分词的方法在本文中没有展开。但是如果去掉文章里的“的、了、吧,呢、啊”等可以提高结果的准确率。当然同时也可以提高判断的阀值。

运行结果:

"第六章 字符编码" 与 "第一章 设计模式" 的相似度为:0.37

"第六章 字符编码" 与 "第二章 python学习" 的相似度为:0.48

"第六章 字符编码" 与 "第三章 python简介" 的相似度为:0.57

"第六章 字符编码" 与 "第四章 输入输出" 的相似度为:0.56

"第六章 字符编码" 与 "第五章 数据类型和变量" 的相似度为:0.67

"第六章 字符编码" 与 "第六章 字符编码" 的相似度为:1.0

"第六章 字符编码" 与 "第七章 list" 的相似度为:0.48

runtime:519毫秒

看以看出准确度有了一定的提高。

番外:

L编辑距离动态计算法,调用python脚本实现,脚本文件

author = "victor"

-- coding:utf-8 --

import sys

import Levenshtein

if name == "__main__":

if(len(sys.argv) < 3):

    print("Usage: python myratiodetect.py str1 str2")

    exit(-1)

str1 = sys.argv[1]

str2 = sys.argv[2]

r = Levenshtein.ratio(str1, str2)

print(r)

exit(0)

本地运行的前提为:已经适应pip安装了:python_Levenshtein,所以其对服务器的依赖比较大,如果工程环境迁移了的话,会比较受影响。

程序的运行结果:

"第六章 字符编码" 与 "第一章 设计模式" 的相似度为:0.157063851181

"第六章 字符编码" 与 "第二章 python学习" 的相似度为:0.165801038753

"第六章 字符编码" 与 "第三章 python简介" 的相似度为:0.194563908481

"第六章 字符编码" 与 "第四章 输入输出" 的相似度为:0.268671351528

"第六章 字符编码" 与 "第五章 数据类型和变量" 的相似度为:0.300997688969

"第六章 字符编码" 与 "第六章 字符编码" 的相似度为:1.0

"第六章 字符编码" 与 "第七章 list" 的相似度为:0.296406739228

runtime:2247毫秒

运行速度.....比较慢..2333

参考:

https://www.2cto.com/kf/20140...

http://wdhdmx.iteye.com/blog/...

http://blog.sina.com.cn/s/blo...

http://blog.sina.com.cn/s/blo...

更多网易技术、产品、运营经验分享请访问网易云社区。
文章来源: 网易云社区

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/25320.html

相关文章

  • 推荐系统01--余弦相似

    摘要:在近邻推荐中,最常用的相似度是余弦相似度。这就是由于余弦相似度被向量长度归一化后的结果。用余弦相似度计算出来,两个用户的相似度达到。余弦相似度适用于评分数据,杰卡德相似度适合用于隐式反馈数据。 今天,我们来聊聊协同过滤中的相似度计算方法有哪些。相似度的本质推荐系统中,推荐算法分为两个门派,一个是机器学习派,另一个就是相似度门派。机器学习派是后起之秀,而相似度派则是泰山北斗,以致撑起来推...

    cncoder 评论0 收藏0
  • Move Mirror:使用 TensorFlow.js 在浏览器中预测姿势之 AI 实验

    摘要:文和,创意实验室创意技术专家在机器学习和计算机视觉领域,姿势预测或根据图像数据探测人体及其姿势的能力,堪称最令人兴奋而又最棘手的一个话题。使用,用户可以直接在浏览器中运行机器学习模型,无需服务器。 文 /  Jane Friedhoff 和 Irene Alvarado,Google 创意实验室创意技术专家在机器学习和计算机视觉领域,姿势预测或根据图像数据探测人体及其姿势的能力,堪称最令人兴...

    MiracleWong 评论0 收藏0
  • 基于TensorFlow理解三大降维技术:PCA、t-SNE 和自编码器

    摘要:代码地址在这篇文章中,我将尽我所能揭秘三种降维技术和自编码器。动机当处理真实问题和真实数据时,我们往往遇到维度高达数百万的高维数据。尽管在其原来的高维结构中,数据能够得到较好的表达,但有时候我们可能需要给数据降维。 代码地址:https://github.com/eliorc/Medium/blob/master/PCA-tSNE-AE.ipynb在这篇文章中,我将尽我所能揭秘三种降维技术:...

    Wildcard 评论0 收藏0
  • 自然语言处理真实项目实战

    摘要:在自然语言处理中,一个很重要的技术手段就是将文档转换为一个矢量,这个过程一般是使用这个库进行处理的。自然语言处理中,一般来说,代表词。自然语言预处理中,一个很重要的步骤就是将你收集的句子进行分词,将一个句子分解成词的列表。 前言 本文根据实际项目撰写,由于项目保密要求,源代码将进行一定程度的删减。本文撰写的目的是进行公司培训,请勿以任何形式进行转载。由于是日语项目,用到的分词软件等,在...

    王岩威 评论0 收藏0
  • [论文简读] Web Content Extraction Using Clustering

    摘要:实验结果实验数据集数据集都是新闻类网页,从五个中文新闻网站中收集一百个页面这最多也就五类吧,而且也就五百个,好像有点少了吧结果与验证性能指标这这这比较文本长度就了那不是只要包含新闻正文不就好了。 《Web Content Extraction Using Clustering with Web Structure》引用 Huang X, Gao Y, Huang L, et al. ...

    levinit 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<