Jorbe's Blog

本文将分析用Cosin算法和欧拉距离来计算文本相似度时存在的问题，更一般的，将阐述用向量内积的方法来计算相似度存在的弊端，Cosin算法就是一种基于向量内积的算法。最后将给出一个全新的相似度计算算法，并通过一些简单例子比较这些相似度计算算法的性能。

在计算文本之间的相似度时，一般的做法是先把文档分词，去停用词，然后计算每个词的tf-idf值，再映射到向量空间，最后用Cosin算法计算两个文本的相似度大小。

首先，简要介绍下Cosin算法的原理。
Cosin算法先把两个文本映射到一个高维度的向量空间模型，然后再计算这两个向量之间的夹角余弦值大小，夹角余弦值越大则代表两个向量越相似。有，故有Cosin算法的公式，分子就是两个向量的内积。即Cosin算法计算的是两个向量之间的夹角的余弦值，向量之间的夹角越大，余弦值越小，最后计算出来的相似度也越小。

但向量之间夹角大小真的可以很完美地用来衡量它们之间的相似度大小吗？事实上还没有一种完美的算法可以“完美”地计算出两个文本之间的相似度大小，主要是因为衡量文本之间的相似度没有一个统一的标准，比如让不同的人去判断三个两两之间都比较相似的文本哪两个更相似，不同的人肯定会得出不同的答案，当然，这样说有点吹毛求疵，毕竟只要两个文本从某种程度上比较相似的话，那用相似度算法计算出来的相似度值肯定不会小。而本文的目的就是综合分析Cosin和欧拉距离相似度计算算法，给出它们在理论思想上的一些欠缺之处，然后给出一种可能相对比较“完美”的相似度计算算法(具体的测试结果将在七月份公布，目前只从主观理论角度进行简单分析)。

基于欧拉距离的相似度算法

两点之间的距离计算公式(欧拉距离公式)。欧拉距离也是一种衡量文本之间相似度大小的方法。它基于的想法是，把文本映射到向量空间之后，若它们之间的直线距离较短，则认为它们相似度较大。在很多情况下，这种思想确实可以作为一种相似度衡量方法，但仔细想想就会发现这种方法太粗糙了，后面我会用一张空间图来说明这种粗糙性。也正是这种粗糙性，造成了用KNN算法来分类时的准确率始终难以掌控。基于欧拉距离的相似度算法只关注向量空间中两个向量之差的长度值，并没有关注夹角的大小。注：一般来说两个向量之间的夹角越大，那这两个向量之差的长度值也越大，但这只有在两个向量长度相差不大时才会出现。

(上图所示是分别计算B,C,D向量和A向量的相似度大小关系，其中B,C向量和A向量之间的夹角大小一样)

基于向量夹角的相似度算法

基于夹角余弦的相似度算法则与基于欧拉距离的相似度算法完全相反，它只关注向量之间夹角的大小，而不关注向量之差的长度值大小。又回到前面提出来的问题：向量之间夹角大小真的可以完美地衡量它们之间的相似度大小吗？事实上，基于欧拉距离和基于向量夹角大小从某种角度上来说是一样的，因为向量空间模型中两个比较接近的点，一般来说它们之间的夹角也比较小，而两个向量之间的夹角比较小时，一般来说它们之间的欧拉距离也比较小。所以这两种算法其实师出一家，在大多数情况下确实可以很好地用来衡量相似度大小，但在有些情况下这两种算法就不太奏效了(见上图)。事实上根据上图，基于欧拉距离的相似度算法和基于向量夹角的相似度算法可以互相否定对方。

基于重合度的相似度算法

重合度算法其实就是先把两个向量表示成两个“长度”相等的一维坐标，即映射到一维空间，再进行重合度加权求和，它既不关注夹角的大小，也不关注向量之差的长度值。所以是一种与基于欧拉距离和基于向量夹角完全不同的相似度算法。

定义重合度：两个向量在某个维度上的值的接近程度。
基于重合度的相似度算法计算公式：      分母nO(0)是作为一个归一化因子。其中称为共同维度函数，(该函数的具体形式还有待验证)，为重合度函数，这里先不给出重合度函数的具体公式，先初步令，后面会结合具体实验来修正重合度函数。

直观解释：我们说当两个向量的在每个维度上的重合度加权和的值越大，并且共同维度数越多，则代表这两个向量越相似。很多时候我们认为两个向量相似或两个“东西”相似当且仅当这两个“东西”身上的共同性质越多(共同维度数越多)，并且在每个共同性质上的值越接近(重合度越高)，才可以说这两个“东西”越相似。

下面先通过几个简单的例子来比较基于重合度的相似度算法和基于向量夹角的相似度算法的差异性。

例：分别计算B,C,D,E向量与A向量的相似度大小关系
实验一：其中A=(1,2,1)    B=(0,1,5)    C=(1,1,1)    D=(0,2,1)    E=(5,2,1)
①基于重合度的相似度算法：
S(A,B) = t(1)+t(t)
S(A,C) = 2t(0)+t(1)
S(A,D) = 2t(0)
S(A,E) = 2t(0)+t(4)
得到最后结果为：C>E>D>B
注：上面的相似度计算省略了分母，因为分母是个常数，并不影响最后的计算结果，其中t函数的定义已在上面给出。
②基于向量夹角的相似度算法：
S(A,B) = 0.560
S(A,C) = 0.943
S(A,D) = 0.913
S(A,E) = 0.745
得到最后结果为：C>D>E>B
实验二：其中A,B,C,D向量和上面的一致，令E=(2,2,1)
①基于重合度的相似度算法：
S(A,B) = t(1)+t(t)
S(A,C) = 2t(0)+t(1)
S(A,D) = 2t(0)
S(A,E) = 2t(0)+t(1)
得到最后结果为：C=E>D>B
②基于向量夹角的相似度算法：
S(A,B) = 0.560
S(A,C) = 0.943
S(A,D) = 0.913
S(A,E) = 0.953
得到最后结果为：E>C>D>B

结论：

从实验一的结果可以看出，重合度法有着比向量夹角法更好的物理解释，在大多数情况下我们更愿意相信E与A比D与A更相似；从实验二的结果中可以看出，重合度法不会偏向于某一个维度，即实验二中的C和E其实应该和A有着相同的相似度大小，但向量夹角法则更偏向于E的相似度更大一点。所以综合来说，重合度法在大多数情况下比向量夹角法更适用，更准确。

再结合tf-idf来解释重合度法：

tf-idf值代表某个单词维度在文本中的重要度或称为倾向度，只有当两个文本在每个单词维度的倾向度越接近时，才能称这两个文本越相似，这也很好地解释了重合度法的优越性。事实上这也是重合度法的核心思想，而基于向量夹角的相似度算法只在内层用到了tf-idf(将文本映射到向量空间模型时)，在具体到计算相似度大小时却没有用到tf-idf思想。

综上，基于重合度的相似度算法比基于欧拉和基于向量夹角余弦的相似度算法更好。当然后面还必须在得到一些实验结果数据之后才能真正得出这个结论，事实胜于雄辩 : )。基于重合度的相似度算法是我独立设计出来的一个相似度计算算法，没有参考任何人的资料，所以不太清楚是否有人早已经提出了类似的算法，但从目前我搜索的结果来看还没看到类似的算法的提出。不过，由于本人的学识有限，这个算法本身可能还存在一些欠缺之处，欢迎大家拍砖

• ← 查找第k小数
• 生命中最宝贵的 →