文本相识度算法(余弦相似性、简单共有词、编辑距离、SimHash、汉明距离、Jaccard相似性系数、欧几里得距离、曼哈顿距离 )

el/2024/7/17 22:19:23

文本相似度计算在信息检索、数据挖掘、机器翻译、文档复制检测等领域有着广泛的应用。

比如舆论控制,我们假设你开发了一个微博网站,并且已经把世界上骂人的句子都已经收录进了数据库,那么当一个用户发微博时会先跟骂人句子的数据库进行比较,如果符合里面的句子就不让用户发出。

通常情况下,很多工程师就会想到用like或者where的sql语法去查找。可是当情况更为复杂呢?

数据库存放了“你是个坏人”,用户要发“小明是个坏人”,这时应该怎么办呢?

最简单的办法就是通过判断文本的相似程度来决定用户发的内容是否是骂人的。

本章节就几种简单的判断文本相似性的算法来讲解,帮助大家更好的理解。

相关算法

1、余弦相似性

余弦(余弦函数),三角函数的一种。在Rt△ABC(直角三角形)中,∠C=90°,角A的余弦是它的邻边比三角形的斜边,即cosA=b/c,也可写为cosA=AC/AB。余弦函数:f(x)=cosx(x∈R)

这是一个非常常见的算法,相信大家都应该学过余弦定理了,简单来说这个算法就是通过计算两个向量的夹角余弦值来评估他们的相似度。

对于二维空间,根据向量点积公式,显然可以得知(ps,这个公式不是这个算法的重点,可以不用强记):

假设向量a、b的坐标分别为(x1,y1)、(x2,y2) 。则:

设向量 A = (A1,A2,...,An),B = (B1,B2,...,Bn) 。推广到多维,数学家已经帮我们证明了,所以你只要记住下面的公式:

简单来说可以写成下面的式子:

(式子中的x和y是指词频)

比如我们要判断两句话

A=你是个坏人 
B=小明是个坏人

① 先进行分词

A=你 / 是 / 个 / 坏人 
B=小明 / 是 / 个 / 坏人

② 列出所有的词

{ 你 小明 是 个 坏人 }

③计算词频(出现次数)

A={1 0 1 1} (每个数字对应上面的字) 
B={0 1 1 1}

然后把词频带入公式

最终=0.667。

余弦值越接近1,就表明夹角越接近0度,也就是两个向量越相似,这就叫"余弦相似性"。

简单来说上面计算出的值代表两个句子大概六成相似,越接近1就越相似。

--------------------------------------------------

2、简单共有词

通过计算两篇文档共有的词的总字符数除以最长文档字符数来评估他们的相似度。

假设有A、B两句话,先取出这两句话的共同都有的词的字数然后看哪句话更长就除以哪句话的字数。

同样是A、B两句话,共有词的字符长度为4,最长句子长度为6,那么4/6,≈0.667。

-------------------------------------------------

3、编辑距离

编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。由俄罗斯科学家Vladimir Levenshtein(找不到他照片233333)在1965年提出这个概念。

例如将“BABAY是个好人”转成“BABY是个帅哥”,编辑举例就是2(好人变帅哥只要2就好...): BABY是个帅人(好→帅) 
BABY是个帅哥(人→哥)

然后拿编辑距离去除以两者之间的最大长度,2/6≈0.333,意味着只要变动这么多就可以从A变成B,所以不用变动的字符便代表了相似度,1-0.333=0.667。

----------------------------------------------------------------

4、SimHash + 汉明距离

simhash是谷歌发明的算法,据说很nb,可以将一个文档转换成64位的字节,然后我们可以通过判断两个字节的汉明距离就知道是否相似了。

汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如:

1011101 与 1001001 之间的汉明距离是 2。

"toned" 与 "roses" 之间的汉明距离是 3。

首先我们来计算SimHash:

① 提取文档关键词得到[word,weight]这样一个数组。(举例 [美国,4])

② 用hash算法将word转为固定长度的二进制值的字符串[hash(word),weight]。(举例 [100101,4])

③ word的hash从左到右与权重相乘,如果为1则乘以1 ,如果是0则曾以-1。(举例4,-4,-4,4,-4,4)

④ 接着计算下个数,直到将所有分词得出的词计算完,然后将每个词第三步得出的数组中的每一个值相加。(举例美国和51区,[4,-4,-4,4,-4,4]和[5 -5 5 -5 5 5]得到[9 -9 1 -1 1 9])

⑤ 对第四步得到的数组中每一个值进行判断,如果>0记为1,如果<0记为0。(举例[101011])

第四步得出的就是这个文档的SimHash。

这样我们就能将两个不同长度的文档转换为同样长度的SimHash值,so,我们现在可以计算第一个文档的值和第二个文档的汉明距离(一般<3就是相似度高的)。

SimHash本质上是局部敏感性的hash(如果是两个相似的句子,那么只会有部分不同),和md5之类的不一样。 正因为它的局部敏感性,所以我们可以使用海明距离来衡量SimHash值的相似度。

如果想要小数形式的可以这么做:1 - 汉明距离 / 最长关键词数组长度。

---------------------------------------------------------

5、Jaccard相似性系数

Jaccard 系数,又叫Jaccard相似性系数,用来比较样本集中的相似性和分散性的一个概率。Jaccard系数等于样本集交集与样本集合集的比值,即J = |A∩B| ÷ |A∪B|。

说白了就是交集除以并集,两个文档的共同都有的词除以两个文档所有的词

---------------------------------------------

6、欧几里得距离

欧几里得距离是用得非常广的公式,设A(x1, y1),B(x2, y2)是平面上任意两点那么两点间的距离距离(A,B)=平方根((x1-x2...)^2+(y1-y2....)^2)

我们可以拿两个文档所有的词(不重复)在A文档的词频作为x,在B文档的作为y进行计算。

同样拿A=你是个坏人、B=小明是个坏人 这两句话作为例子,词频分别为A={1 0 1 1} 、B={0 1 1 1}。

那么距离为根号2,≈ 1.414(余3位)

然后可以通过1 ÷ (1 + 欧几里德距离)得到相似度。

---------------------------------------------------------------------

7、曼哈顿距离

曼哈顿距离(Manhattan Distance)是由十九世纪的赫尔曼·闵可夫斯基所创词汇,是种使用在几何度量空间的几何学用语,用以标明两个点上在标准坐标系上的绝对轴距总和。

跟欧几里德距离有点像,简单来说就是d(i,j)=|x1-x2...|+|y1-y2...|,同理xn和yn分别代表两个文档所有的词(不重复)在A和B的词频。

然后可以通过1 ÷ (1 + 曼哈顿距离)得到相似度。

距离转换相似度

score = 1 / (euclideanDistance+1)

文本相似度分值的取值范围为[0, 1],0表示完全不相似,说明比较的两个文本之间没有任何关系,1表示完全相似,说明比较的两个文本其实是同一个文本的两个副本。这个公式的目的是处理距离和文本相似度分值的关系,距离和文本相似度分值是反比的关系,距离越远越不相似,距离趋于无穷大的时候,文本相似度分值趋于0,距离趋于或等于0的时候,文本相似度分值趋于或等于1。当然,当我们计算文本和自身的相似度的时候,我们期望的结果是完全相似,也就是完全等同,所以,距离等于0的时候,文本相似度分值等于1。

根据上述公式,当距离变量euclideanDistance==0的时候,score = 1 / (0+1)=1,相似度分值为1,表示比较的两个文本其实是同一个文本,当距离变量euclideanDistance趋于无穷大的时候,score趋于0,表示两个文本的相似度非常小。最后要说明的是,根据这个公式我们无法计算出相似度分值0,也就是说能计算出来的文本相似度分值的取值范围为(0, 1],任何两个文本都存存或多或少的相似度。





http://www.ngui.cc/el/5557107.html

相关文章

余弦方法计算相似度算法--Python实现 Java实现

&#xff08;1&#xff09;余弦相似性 通过测量两个向量之间的角的余弦值来度量它们之间的相似性。0度角的余弦值是1&#xff0c;而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。所以&#xff0c;它…

Python与shell交互os.system、 os.popen、 subprocess

这篇文章主要介绍了Python与shell的3种交互方式介绍,本文讲解了 os.system、 os.popen、 subprocess 模块等3种方法,需要的朋友可以参考下。 问题概述 考虑这样一个问题&#xff0c;有hello.py脚本&#xff0c;输出”hello, world!”&#xff1b;有TestInput.py脚本&#…

浏览器页面的缓存设置(不缓存设置)

HTML的HTTP协议头信息中控制着页面在几个地方的缓存信息&#xff0c;包括浏览器端&#xff0c;中间缓存服务器端(如&#xff1a;squid等)&#xff0c;Web服务器端。本文讨论头信息 中带缓存控制信息的HTML页面(JSP/Servlet生成好出来的也是HTML页面)在中间缓存服务器中的缓存情…

信号、信号量、进程的状态的区别你知道吗?

信号量(Semaphore)&#xff0c;有时被称为信号灯&#xff0c;是在多环境下使用的一种设施&#xff0c;是可以用来保证两个或多个关键代码段不被并发调用。 在进入一个关键代码段之前&#xff0c;线程必须获取一个信号量&#xff1b;一旦该关键代码段完成了&#xff0c;那么该线…

网关的作用(两个内网主机通信原理)

网关是一种充当转换重任的计算机系统或设备。在使用不同的通信协议、数据格式或语言,甚至体系结构完全不同的两种系统之间&#xff0c;网关是一个翻译器。与网桥只是简单地传达信息不同&#xff0c;网关对收到的信息要重新打包&#xff0c;以适应目的系统的需求。同时&#xff…

python中 if __name__ == '__main__': 的解析

当你打开一个.py文件时,经常会在代码的最下面看到 if __name__ __main__: ,现在就来介绍一下它的作用. 模块是对象&#xff0c;并且所有的模块都有一个内置属性 __name__。一个模块的 __name__ 的值取决于您如何应用模块。&#xff08; 1 &#xff09;如果 import 一个模块&a…

正则表达式 学习手册三

javascript表达式举例: 举例&#xff1a;匹配IP地址 100.4.5.6 var reg /^ ( (?: (?: 25[0-5] | 2[0-4] \d | ( (1\d{2}) |([1-9]?\d)) ) \. ) {3} (?:25[0-5]|2[0-4] \d | ( (1\d{2}) | ([1-9]?\d) ) ) ) $/; if (!reg.test($(#master).val())) …

区块链技术介绍----分布式总帐

区块链(Blockchain)是比特币的底层技术&#xff0c;像一个数据库账本&#xff0c;记载所有的交易记录。这项技术也因其安全、便捷的特性逐渐得到了银行与金融业的关注。 ​区块链(Blockchain)是比特币的一个重要概念&#xff0c;区块链是一串使用密码学方法相关联产生的数据块&…

正则表达式 高级规则——四(贪婪与非贪婪)

匹配次数中的贪婪与非贪婪 在使用修饰匹配次数的特殊符号时&#xff0c;有几种表示方法可以使同一个表达式能够匹配不同的次数&#xff0c;比如&#xff1a;"{m,n}", "{m,}", "?", "*",""&#xff0c;具体匹配的次数随被匹…

正则表达式高级用法---五(反向引用 /1, /2...)

反向引用 /1, /2... 表达式在匹配时&#xff0c;表达式引擎会将小括号 "( )" 包含的表达式所匹配到的字符串记录下来。在获取匹配结果的时候&#xff0c;小括号包含的表达式所匹配到的字符串可以单独获取。这一点&#xff0c;在前面的举例中&#xff0c;已经多次展示…