在知识图谱构建阶段的实体对齐和属性值决策、判断一篇文章是否是你喜欢的文章、比较两篇文章的相似性等实例中，都涉及到了向量空间模型（Vector Space Model，简称VSM）和余弦相似度计算相关知识。
        这篇文章主要是先叙述VSM和余弦相似度相关理论知识，然后引用阮一峰大神的例子进行解释，最后通过Python简单实现百度百科和互动百科Infobox的余弦相似度计算。


一. 基础知识
        第一部分参考我的文章: 基于VSM的命名实体识别、歧义消解和指代消解


        第一步，向量空间模型VSM
        向量空间模型（Vector Space Model，简称VSM）表示通过向量的方式来表征文本。一个文档（Document）被描述为一系列关键词（Term）的向量。
        简言之，判断一篇文章是否是你喜欢的文章，即将文章抽象成一个向量，该向量由n个词Term组成，每个词都有一个权重（Term Weight），不同的词根据自己在文档中的权重来影响文档相关性的重要程度。
        Document = { term1, term2, …… , termN }
        Document Vector = { weight1, weight2, …… , weightN }





        其中ti(i=1,2,...n)是一列相互之间不同的词，wi(d)是ti在d中对应的权值。

        选取特征词时，需要降维处理选出有代表性的特征词，包括人工选择或自动选择。


        第二步，TF-IDF
        特征抽取完后，因为每个词语对实体的贡献度不同，所以需要对这些词语赋予不同的权重。计算词项在向量中的权重方法——TF-IDF。

        它表示TF（词频）和IDF（倒文档频率）的乘积：





        词频（Term Frequency，简称TF）表示特征词出现的次数除以文章总词数：



        其中TF表示某个关键词出现的频率，IDF为所有文档的数目除以包含该词语的文档数目的对数值。


        |D|表示所有文档的数目，|w∈d|表示包含词语w的文档数目。

        由于“是”“的”“这”等词经常会出现，故需要IDF值来降低其权值。所谓降维，就是降低维度。具体到文档相似度计算，就是减少词语的数量。常见的可用于降维的词以功能词和停用词为主（如："的"，"这"等），事实上，采取降维的策略在很多情况下不仅可以提高效率，还可以提高精度。

        最后TF-IDF计算权重越大表示该词条对这个文本的重要性越大。

        第三步，余弦相似度计算
        这样，就需要一群你喜欢的文章，才可以计算IDF值。依次计算得到你喜欢的文章D=(w1, w2, ..., wn)共n个关键词的权重。当你给出一篇文章E时，采用相同的方法计算出E=(q1, q2, ..., qn)，然后计算D和E的相似度。

        计算两篇文章间的相似度就通过两个向量的余弦夹角cos来描述。文本D1和D2的相似性公式如下：


        其中分子表示两个向量的点乘积，分母表示两个向量的模的积。

        计算过后，就可以得到相似度了。我们也可以人工的选择两个相似度高的文档，计算其相似度，然后定义其阈值。同样，一篇文章和你喜欢的一类文章，可以取平均值或寻找一类文章向量的中心来计算。主要是将语言问题转换为数学问题进行解决。

        缺点：计算量太大、添加新文本需要重新训练词的权值、词之间的关联性没考虑等。其中余弦定理为什么能表示文章相似度间参考资料。


二. 实例解释
        第二部分主要参考阮一峰大神的个人博客，举例解释VSM实现余弦相似度计算，强烈推荐大家去阅读阮神的博客：TF-IDF与余弦相似性的应用
        此部分为转载，阮神举了一个简单的例子（后面第三部分是相对复杂的例子）：



　　句子A：我喜欢看电视，不喜欢看电影。

　　句子B：我不喜欢看电视，也不喜欢看电影。


    请问怎样才能计算上面两句话的相似程度？
    基本思路是：如果这两句话的用词越相似，它们的内容就应该越相似。因此，可以从词频入手，计算它们的相似程度。

   第一步，分词。


　　句子A：我/喜欢/看/电视，不/喜欢/看/电影。

　　句子B：我/不/喜欢/看/电视，也/不/喜欢/看/电影。


   第二步，列出所有的词。


　　我，喜欢，看，电视，电影，不，也。


   第三步，计算词频。


　　句子A：我 1，喜欢 2，看 2，电视 1，电影 1，不 1，也 0。

　　句子B：我 1，喜欢 2，看 2，电视 1，电影 1，不 2，也 1。


   第四步，写出词频向量。


　　句子A：[1, 2, 2, 1, 1, 1, 0]

　　句子B：[1, 2, 2, 1, 1, 2, 1]


   到这里，问题就变成了如何计算这两个向量的相似程度。


   使用余弦这个公式，我们就可以得到，句子A与句子B的夹角的余弦。



    余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，这就叫"余弦相似性"。所以，上面的句子A和句子B是很相似的，事实上它们的夹角大约为20.3度。
    由此，我们就得到了"找出相似文章"的一种算法：


（1）使用TF-IDF算法，找出两篇文章的关键词；
（2）每篇文章各取出若干个关键词（比如20个），合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）；
（3）生成两篇文章各自的词频向量；
（4）计算两个向量的余弦相似度，值越大就表示越相似。


    "余弦相似度"是一种非常有用的算法，只要是计算两个向量的相似程度，都可用它。
        PS：这部分内容完全照搬阮神的博客，因为真的讲得通俗易懂，我都有点爱不释手了。如果觉得版权不妥之处，我可以删除，同时推荐大家阅读他的更多文章。

        阮一峰个人博客链接：http://www.ruanyifeng.com/home.html



三. 代码实现
        最后就简单讲解我的Python实现百度百科和互动百科关于消息盒InfoBox的相似度计算。其中爬虫部分参考我的博客：

        [Python爬虫] Selenium获取百度百科旅游景点的InfoBox消息盒




        我已经通过Selenium爬取了所有“国家5A级景区”的InfoBox消息盒，并使用开源分词工具进行了分词处理，“故宫”数据如下所示：


        计算“百度百科-故宫”和“互动百科-故宫”的消息盒相似度代码如下。基本步骤：

        1.分别统计两个文档的关键词，读取txt文件，CountKey()函数统计

        2.两篇文章的关键词合并成一个集合MergeKey()函数，相同的合并，不同的添加

        3.计算每篇文章对于这个集合的词的词频 TF-IDF算法计算权重，此处仅词频

        4.生成两篇文章各自的词频向量

        5.计算两个向量的余弦相似度，值越大表示越相似 
# -*- coding: utf-8 -*-
import time          
import re          
import os
import string
import sys
import math


''' ------------------------------------------------------- '''
#统计关键词及个数
def CountKey(fileName, resultName):
    try:
        #计算文件行数
        lineNums = len(open(fileName,'rU').readlines())
        print u'文件行数: ' + str(lineNums)

        #统计格式 格式<Key:Value> <属性:出现个数>
        i = 0
        table = {}
        source = open(fileName,"r")
        result = open(resultName,"w")
        
        while i < lineNums:
            line = source.readline()
            line = line.rstrip('\n')
            print line
            
            words = line.split(" ")  #空格分隔
            print str(words).decode('string_escape') #list显示中文
            
            #字典插入与赋值
            for word in words:
                if word!="" and table.has_key(word):      #如果存在次数加1
                    num = table[word]
                    table[word] = num + 1
                elif word!="":                            #否则初值为1
                    table[word] = 1
            i = i + 1

        #键值从大到小排序 函数原型：sorted(dic,value,reverse)
        dic = sorted(table.iteritems(), key = lambda asd:asd[1], reverse = True)
        for i in range(len(dic)):
            #print 'key=%s, value=%s' % (dic[i][0],dic[i][1])
            result.write("<"+dic[i][0]+":"+str(dic[i][1])+">\n")
        return dic
        
    except Exception,e:    
        print 'Error:',e
    finally:
        source.close()
        result.close()
        print 'END\n\n'


''' ------------------------------------------------------- '''
#统计关键词及个数 并计算相似度
def MergeKeys(dic1,dic2):
    #合并关键词 采用三个数组实现
    arrayKey = []
    for i in range(len(dic1)):
        arrayKey.append(dic1[i][0])       #向数组中添加元素
    for i in range(len(dic2)):       
        if dic2[i][0] in arrayKey:
            print 'has_key',dic2[i][0]
        else:                             #合并
            arrayKey.append(dic2[i][0])
    else:
        print '\n\n'
    
    test = str(arrayKey).decode('string_escape')  #字符转换
    print test

    #计算词频 infobox可忽略TF-IDF
    arrayNum1 = [0]*len(arrayKey)
    arrayNum2 = [0]*len(arrayKey)
    
    #赋值arrayNum1
    for i in range(len(dic1)):     
        key = dic1[i][0]
        value = dic1[i][1]
        j = 0
        while j < len(arrayKey):
            if key == arrayKey[j]:
                arrayNum1[j] = value
                break
            else:
                j = j + 1

    #赋值arrayNum2
    for i in range(len(dic2)):     
        key = dic2[i][0]
        value = dic2[i][1]
        j = 0
        while j < len(arrayKey):
            if key == arrayKey[j]:
                arrayNum2[j] = value
                break
            else:
                j = j + 1
    
    print arrayNum1
    print arrayNum2
    print len(arrayNum1),len(arrayNum2),len(arrayKey)

    #计算两个向量的点积
    x = 0
    i = 0
    while i < len(arrayKey):
        x = x + arrayNum1[i] * arrayNum2[i]
        i = i + 1
    print x

    #计算两个向量的模
    i = 0
    sq1 = 0
    while i < len(arrayKey):
        sq1 = sq1 + arrayNum1[i] * arrayNum1[i]   #pow(a,2)
        i = i + 1
    print sq1
    
    i = 0
    sq2 = 0
    while i < len(arrayKey):
        sq2 = sq2 + arrayNum2[i] * arrayNum2[i]
        i = i + 1
    print sq2
    
    result = float(x) / ( math.sqrt(sq1) * math.sqrt(sq2) )
    return result
    

''' ------------------------------------------------------- 
    基本步骤：
        1.分别统计两个文档的关键词
        2.两篇文章的关键词合并成一个集合,相同的合并,不同的添加
        3.计算每篇文章对于这个集合的词的词频 TF-IDF算法计算权重
        4.生成两篇文章各自的词频向量
        5.计算两个向量的余弦相似度,值越大表示越相似                             
    ------------------------------------------------------- '''
#主函数
def main():
    #计算文档1-百度的关键词及个数
    fileName1 = "BaiduSpider.txt"
    resultName1 = "Result_Key_BD.txt"
    dic1 = CountKey(fileName1, resultName1)
    
    #计算文档2-互动的关键词及个数
    fileName2 = "HudongSpider\\001.txt"
    resultName2 = "HudongSpider\\Result_Key_001.txt"
    dic2 = CountKey(fileName2, resultName2)

    #合并两篇文章的关键词及相似度计算
    result = MergeKeys(dic1, dic2)
    print result


if __name__ == '__main__':
    main()
        其中由于只需要计算InfoBox消息盒的相似度，不会存在一些故不需要计算TF-IDF值，通过词频就可以表示权重，在代码中简单添加循环后，可以计算百度百科的“故宫”与互动百科不同实体的相似度，运行结果如下所示，可以发现“北京故宫”和“故宫”相似度最高。这也是简单的实体对齐。





        希望文章对你有所帮助，尤其是代码部分。如果文章中有错误或不足之处，还请海涵~毕竟作者自己也还在学习当中，如果有关于实体对齐和属性对齐的好方法和实现代码，也可以推荐给我，3Q。

        最后是参考和推荐一些相关的文章关于VSM和余弦相似度计算：

        TF-IDF与余弦相似性的应用（一）：自动提取关键词 - 阮一峰

        TF-IDF与余弦相似性的应用（二）：找出相似文章 - 阮一峰

        Lucene学习之计算相似度模型VSM(Vector Space Model)

        VSM向量空间模型对文本的分类以及简单实现 - java

        话说正确率、召回率和F值 - silence1214

        向量空间模型(VSM) - wyy_820211网易博客

        向量空间模型(VSM)的余弦定理公式(cos) - live41

        向量空间模型文档相似度计算实现（C#）- felomeng

        向量空间模型(VSM)在文档相似度计算上的简单介绍 - felomeng

        隐马尔科夫模型学习总结.pdf - a123456ei

        向量空间模型VSM - ljiabin
（By:Eastmount 2015-11-18 深夜5点   http://blog.csdn.net/eastmount/）  

	

下面这道题算是高中三角函数稍微复杂的计算，抓住通项进行化简。大胆地进行三角函数展开，多项式展开。化简过程用到一个积化和差公式，现在高中已经不讲积化和差公式了，大概就是觉得太麻烦。说真的积化和差公式我也觉得很麻烦，只会记得一组余弦的公式(总共4个)，但是其实很容易推导，要用马上就可以推导，所以记不住也无所谓，推导用不了几秒。
最后一步累加求和，完全利用三角函数单位圆上的对称性，向量和为零等。直接看图如下。
这题风格很像下面一讲中的那道复杂三角函数题：
黄老师讲数学(449)三角函数一些较难题目
顺便记录下面一些题目。
黄老师数学类文章：黄老师讲数学(451)利用向量证明柯西不等式并得到两个不等式结论用于解题黄老师讲数学(450)递推式的通项估值黄老师讲数学(449)三角函数一些较难题目黄老师讲数学(448)高一数学新教材黄老师讲数学(447)不等式与公切线黄老师讲数学(446)换元巧解2019浙江高考导数题的一步黄老师讲数学(445)用必要条件求解的2019浙江导数压轴题黄老师讲数学(444)同构法求导数大题参数取值范围黄老师讲数学(443)出现在八年级的费马点问题黄老师讲数学(442)挑战二次相遇问题变式-所有人都可以思考的小学奥数黄老师讲数学(441)奇(偶)函数中的参数值求解黄老师讲数学(440)高一函数性质两种题型黄老师讲数学(439)八年级题目用到胡不归模型黄老师讲数学(438)零点问题之唯一交点黄老师讲数学(437)一个零点个数题的两种解法黄老师讲数学(436)一道导数大题的零点问题黄老师讲数学(435)利用放缩技巧进行零点范围估计黄老师讲数学(434)导数大题中极值点与参数的转换黄老师讲数学(433)抽屉原理、质数、整除-一道较难的小学奥数数论题黄老师讲数学(432)数学使人严谨-对一道导数大题的讨论黄老师讲数学(431)莆田一中2020高二下期末数学考试小吴又考了第一名(含试卷和压轴导数解答)黄老师讲数学(430)莆田市中山中学八年级下数学期末质量监测试卷黄老师讲数学(429)又是一个关于比赛的概率题-类似2020高考数学理科卷I
黄老师讲数学(428) 2020全国卷2的三角函数导数压轴题
黄老师讲数学(427)2020年擢英中学八下数学期末考几道题讲评
黄老师讲数学(426)直线与网格点相交问题-东京大学入学1992年第5题
黄老师讲数学(425)含参抛物线通过的平面区域范围求解
黄老师讲数学(424)立体几何含多变量的体积范围求解
黄老师讲数学(423)三次方程及n次方程求根的一个技巧
黄老师讲数学(418)2020年高考数学答案详解(全国理科I卷)
黄老师讲数学(417)高考最后练习-包含函数构造新型拆项等代数问题
黄老师讲数学(416)2020高考最后练习-含一道较好概率大题
2019年10月-2019年12月数学文章合集2019年5月-2019年9月数学文章合集2019年1月-2019年4月数学文章合集2018年10月-2018年12月数学文章合集2018年1-9月 数学文章合集2016-2017年数学文章合集

向量空间余弦相似度(Cosine Similarity)

余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，这就叫"余弦相似性"。


向量空间余弦相似度理论就是基于上述来计算个体相似度的一种方法。下面做详细的推理过程分析。
如果向量a和b不是二维而是n维，上述余弦的计算法仍然正确。假定a和b是两个n维向量，a是 ，b是 ，则a与b的夹角 的余弦等于：
cosA=[(x1)*(x2)+(y1)*(y2)]/{根号下[(x1)^2+(y1)^2]*根号下[(x2)^2+(y2)^2]}


余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，夹角等于0，即两个向量相等，这就叫"余弦相似性"。
对于二值得只是其中向量每个分量的取值只能为0或者1和一般的情况计算过程一样。

一、前言
本文中根据甲方需求实现调用GPU加速计算两千万次的余弦相似度计算，根据需求分析，可以大致分为两个实现目标。

在10s内完成1：2000000次的余弦相似度计算。
在10s内同时完成topk的计算。

二、实现方法
因为在需求中需要完成GPU来加载数据和计算，因此使用普通的程序是无法完成调用GPU的任务，因此，在实现过程中决定采用卷积神经网络的思想来完成数据的加载和计算，同时也能根据需求，分别测试CPU和GPU两种设备下的速度。
初次之外，本文在实现过程中分别采用了两种方式来完成，分别如下：

采用调用torch网络中的torch.nn.function.cosine_similarity来计算余弦相似度
自行构造矩阵同时完成多纬度的计算。

经过测试，第一种方式中使用的for循环严重导致了时间的加长，第二种方式则能分别实现数据的加载和计算，因此，选择第二种方式更加合理。

2.1、方式一：For循环
主要实现分为两步：

构造网络结构，本文中的网络实际仅为余弦相似度的计算。class CosineSimilarity为网络结构。
生成随机特征，并加载到device设备中。
进行计算并循环第二部分。

代码如下：
import torch
import torch.nn.functional as F
import time


class CosineSimilarity(torch.nn.Module):

    def __init__(self, dim=1, eps=1e-8):
        super(CosineSimilarity, self).__init__()
        self.dim = dim
        self.eps = eps

    def forward(self, x1, x2):
        return F.cosine_similarity(x1, x2, self.dim, self.eps)


def test():
    device = torch.device("cuda:0" if torch.cuda.is_available() else "cpu")
    model = CosineSimilarity().to(device)
    model = torch.nn.DataParallel(model)

    start_time = time.time()
    for i in range(50000):
        x1 = torch.randn(1, 256).to(device)
        x2 = torch.randn(1, 256).to(device)

        distance = model(x1, x2)
        print("index:{}, similar:{}".format(i, distance))
    end_time = time.time()
    print("time is :{}".format(end_time-start_time))

if __name__ == "__main__":
    test()

2.2、方式二：自行构造矩阵
与方式一大致想通过，不同的是第一种方式中每次同时生成两个256纬的数据，加载到设备中之后再进行一次计算，第二种方式是直接全部加载数据到设备中再进行计算。基本过程与第一种方式类似。

构建网络模型，CosineSimilarityTest
加载数据到设备中CPU/GPU
加载模型到设备中model = CosineSimilarityTest().to(device)
进行计算

import torch
import torch.nn.functional as F
import time


class CosineSimilarityTest(torch.nn.Module):
    def __init__(self):
        super(CosineSimilarityTest, self).__init__()

    def forward(self, x1, x2):
        x2 = x2.t()
        x = x1.mm(x2)
    
        x1_frobenius = x1.norm(dim=1).unsqueeze(0).t()
        x2_frobenins = x2.norm(dim=0).unsqueeze(0)
        x_frobenins = x1_frobenius.mm(x2_frobenins)
    
        final = x.mul(1/x_frobenins)
        return final


def main():
    #  加载数据到设备中CP\GPU
    device = torch.device("cuda:0" if torch.cuda.is_available() else "cpu")
    x1 = torch.randn(5000000, 256).to(device)
    x2 = torch.randn(1, 256).to(device)

    start_time = time.time()
    model = CosineSimilarityTest().to(device)

    # 同时需要多卡计算时需要
    # model = torch.nn.DataParallel(model)

    final_value = model(x1, x2)
    print(final_value.size())

	# 输出排序并输出topk的输出
    value, indec = torch.topk(final_value, 3, dim=0, largest=True, sorted=True)
    print(value)

    end_time = time.time()
    print("消耗时间为：{}".format(end_time - start_time))


if __name__ == "__main__":
    main()

三、方法选择
通过上述两种方式的代码展现，可以直观的看出，第二种方式要更加的清晰。易于统计数据的加载和计算的消耗时间，而第一种方式明显更加混乱，加载数据与计算混合在一起。除此之外，还有如下两点原因。

使用for循环单次计算余弦相似度，明显循环调用了余弦相似度的计算公式，冗余严重。
第二种方式，采用矩阵的计算方式，更加符合GPU的架构设计。

四、测试结果
该测试结果方式2在服务器上CPU和GPU设备的测试结果，和上述的实际代码实际输出有偏差，但测试结果相同。
测试结果中指标分别为：
1、加载数据时间。

2、输出的结果纬度尺寸。

3、topk的值，该测试的k值为3.

4、计算消耗时间。
1、CPU设备测试结果。



2、GPU设备测试结果


五、结果分析
从上述的方法二的结论中可以看出两点不同的地方。

CPU加载数据的时间要明显比GPU时间更短，也更加优秀
GPU更加适合处理矩阵之间的计算，在浮点矩阵的计算上GPU比CPU更久优秀。