Jaccard相似度和广义Jaccard相似度 – july_2的专栏 – 博客频道 – CSDN.NET

本文信息本文由方法SEO顾问发表于2016-06-14 04:15 星期二,共 1281字。转载请注明:Jaccard相似度和广义Jaccard相似度 – july_2的专栏 – 博客频道 – CSDN.NET_【方法SEO顾问】,如果我网站的文章对你有所帮助的话,来百度口碑给个好评呗!

1. 狭义Jaccard相似度,计算两个集合之间的相似程度,元素的“取值”为0或1

对集合A和B,Jaccard相似度计算如下:

Jaccard(A, B)= |A intersect B| / |A union B|

相似度数值在[0, 1]之间,当A==B的时候,为1. 优缺点,就是元素的取值只能是0或者1,无法利用更丰富的信息。

由相似度,可以转换成Jaccard距离:

Jaccard distance (A, B) = 1 - Jaccard(A, B)

2. 广义Jaccard相似度,元素的取值可以是实数。又称为Tanimoto系数,用EJ来表示,计算方式如下:

EJ(A,B)=(A*B)/(||A||^2+||B||^2-A*B)

其中A、B分别表示为两个向量,集合中每个元素表示为向量中的一个维度,在每个维度上,取值通常是[0, 1]之间的值,A*B表示向量乘积,||A||^2表示向量的模,即 ||A||^2 = sqrt (a1^2 + a2^2 + a3^2 + ......)。

广义Jaccard相似度计算公式中,如果把分母的A*B去掉,并将||A||^2+||B||^2替换为(||A||^2)*(||B||^2),就转成了余弦相似度(cosine similarity)。

EJ中每个分量的取值可以是实数,通常在[0, 1]之间。对于两篇文档,分词之后,形成两个“词语--词频向量”,词语可以做为EJ的维度,如何将词频转换为实数值。借鉴tf/idf的思路。对于每个词语,有两个频度:1.在当前文档中的频度;2. 在所有文档中的频度。其中1相当于tf,与权重正相关;2相当于df,与权重反相关。

对于2,计算权重为

idf (w) = log (TotalWC/C(w))

C(w)是词语w在所有文档中出现的次数,TotalWC是所有文档中所有词的总词频。

对于1,权重就可以取词频本身 tf(w) = D(w),D(w)表示在当前文档中w出现的次数。

具体计算的代码可以参考 “http://www.cnblogs.com/TtTiCk/archive/2007/08/04/842819.html”的Documents.cs中的“SimilitudeValueToDocumentUsingGeneralizedJaccardCoefficient”函数。

3. 其他扩展方法

文章“http://www.docin.com/p-461291267.html”给出了一种扩展方法,用最大最小值函数来代替乘积和模计算,如下:

EJ(A,B) = sum ( min(a1, b1) + min (a2, b2)... ) / sum ( max(a1, b1) + max (a2, b2).. )

即用向量中每个分量的的最小值和最大值来参与计算。

个人理解,这个可以做如下解释。当集合A中的元素a1出现C(a1)次的时候,我们可以认为集合中的元素是允许重复存在的,即集合A中有C(a1)个元素;集合B也是这样,有C(b1)个相同的元素,则A和B在这个元素上的交集就是min(a1, b1) ,并集就是max(a1, b1) ,这样上述公式就是利用狭义Jaccard相似度计算的结果。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: