推荐系统之知识图谱个性推荐算法

知识图谱于2012年5月17日由Google正式提出，其初衷是为了提高搜索引擎的能力，改善用户的搜索质量以及搜索体验。随着人工智能的技术发展和应用，知识图谱逐渐成为关键技术之一，现已被广泛应用于智能搜索、智能问答、个性化推荐、内容分发等领域。

定义

知识图谱的官方定义如下：知识图谱是Google用于增强其搜索引擎功能的知识库。本质上, 知识图谱旨在描述真实世界中存在的各种实体或概念及其关系,其构成一张巨大的语义网络图，节点表示实体或概念，边则由属性或关系构成。

节点类型

1、实体: 指的是具有可区别性且独立存在的某种事物。如某一个人、某一个城市、某一种植物等、某一种商品等等。世界万物由具体事物组成，此指实体。如图1的“中国”、“美国”、“日本”等。，实体是知识图谱中的最基本元素，不同的实体间存在不同的关系。
2、语义类（概念）：具有同种特性的实体构成的集合，如国家、民族、书籍、电脑等。概念主要指集合、类别、对象类型、事物的种类，例如人物、地理等。
内容: 通常作为实体和语义类的名字、描述、解释等，可以由文本、图像、音视频等来表达。
3、属性(值): 从一个实体指向它的属性值。不同的属性类型对应于不同类型属性的边。属性值主要指对象指定属性的值。如图1所示的“面积”、“人口”、“首都”是几种不同的属性。属性值主要指对象指定属性的值，例如960万平方公里等。
4、关系: 形式化为一个函数，它把 k k个点映射到一个布尔值。在知识图谱上，关系则是一个把k k个图节点(实体、语义类、属性值)映射到布尔值的函数。

三元组是知识图谱的一种通用表示方式，其基本形式主要包括**(实体1-关系-实体2)和(实体-属性-属性值)**等。如下面的例子，中国是一个实体，北京是一个实体，中国-首都-北京是一个（实体-关系-实体）的三元组样例。北京是一个实体，人口是一种属性2069.3万是属性值。北京-人口-2069.3万构成一个（实体-属性-属性值）的三元组样例。

知识表示

在知识表示学习中，最为经典的模型就是TransE模型，TransE模型的核心作用就是将知识图谱中的三元组翻译成embedding向量。

TransE算法：

思想：

为了后面便于表示，我们先设定一些符号

h 表示知识图谱中的头实体的向量。
t 表示知识图谱中的尾实体的向量。
r 表示知识图谱中的关系的向量。

在TransE模型中，有这样一个假设：

t*=h+*r

也就是说，正常情况下的尾实体向量=头实体向量+关系向量。用图的方式描述如下：

如果一个三元组不满足上述的的关系，我们就可以认为这是一个错误的三元组。

先来介绍两个数学概念：

L1范数

也称为曼哈顿距离，对于一个向量X而言，其L1范数的计算公式为：

其中，xi表示向量X的第i个属性值，这里我们取的是绝对值。并且，使用L1范数可以衡量两个向量之间的差异性，也就是两个向量的距离。

L2范数

也称为欧式距离，对于一个向量X而言，其L2范数的计算公式为：

同样，L2范数也可以用来衡量两个向量之间的差距:

根据我们上面介绍的Trans中的假设，我们可以知道，对于一个三元组而言，头实体向量和关系向量之和与尾实体向量越接近，那么说明该三元组越接近一个正确的三元组，差距越大，那么说明这个三元组越不正常。那么我们可以选择L1或者L2范数来衡量三个向量的差距。

为此给出目标函数为：

梯度求解：

实现如下：

from random import uniform, sample
from numpy import *
from copy import deepcopy

class TransE:
    def __init__(self, entityList, relationList, tripleList, margin = 1, learingRate = 0.00001, dim = 10, L1 = True):
        self.margin = margin
        self.learingRate = learingRate
        self.dim = dim#向量维度
        self.entityList = entityList#一开始，entityList是entity的list；初始化后，变为字典，key是entity，values是其向量（使用narray）。
        self.relationList = relationList#理由同上
        self.tripleList = tripleList#理由同上
        self.loss = 0
        self.L1 = L1
def initialize(self):
    '''
    初始化向量
    '''
    entityVectorList = {}
    relationVectorList = {}
    for entity in self.entityList:
        n = 0
        entityVector = []
        while n < self.dim:
            ram = init(self.dim)#初始化的范围
            entityVector.append(ram)
            n += 1
        entityVector = norm(entityVector)#归一化
        entityVectorList[entity] = entityVector
    print("entityVector初始化完成，数量是%d"%len(entityVectorList))
    for relation in self. relationList:
        n = 0
        relationVector = []
        while n < self.dim:
            ram = init(self.dim)#初始化的范围
            relationVector.append(ram)
            n += 1
        relationVector = norm(relationVector)#归一化
        relationVectorList[relation] = relationVector
    print("relationVectorList初始化完成，数量是%d"%len(relationVectorList))
    self.entityList = entityVectorList
    self.relationList = relationVectorList
def transE(self, cI = 20):
    print("训练开始")
    for cycleIndex in range(cI):
        Sbatch = self.getSample(3)
        Tbatch = []#元组对（原三元组，打碎的三元组）的列表 ：{((h,r,t),(h',r,t'))}
        for sbatch in Sbatch:
            tripletWithCorruptedTriplet = (sbatch, self.getCorruptedTriplet(sbatch))
            # print(tripletWithCorruptedTriplet)
            if(tripletWithCorruptedTriplet not in Tbatch):
                Tbatch.append(tripletWithCorruptedTriplet)
        self.update(Tbatch)
        if cycleIndex % 100 == 0:
            print("第%d次循环"%cycleIndex)
            print(self.loss)
            self.writeRelationVector("E:\pythoncode\knownlageGraph\\transE-master\\relationVector.txt")
            self.writeEntilyVector("E:\pythoncode\knownlageGraph\\transE-master\\entityVector.txt")
            self.loss = 0
def getSample(self, size):
    return sample(self.tripleList, size)

def getCorruptedTriplet(self, triplet):
    '''
    training triplets with either the head or tail replaced by a random entity (but not both at the same time)
    :param triplet:
    :return corruptedTriplet:
    '''
    i = uniform(-1, 1)
    if i < 0:  # 小于0，打坏三元组的第一项
        while True:
            entityTemp = sample(self.entityList.keys(), 1)[0]
            if entityTemp != triplet[0]:
                break
        corruptedTriplet = (entityTemp, triplet[1], triplet[2])
    else:  # 大于等于0，打坏三元组的第二项
        while True:
            entityTemp = sample(self.entityList.keys(), 1)[0]
            if entityTemp != triplet[1]:
                break
        corruptedTriplet = (triplet[0], entityTemp, triplet[2])
    return corruptedTriplet

def update(self, Tbatch):
    copyEntityList = deepcopy(self.entityList)
    copyRelationList = deepcopy(self.relationList)

    for tripletWithCorruptedTriplet in Tbatch:
        headEntityVector = copyEntityList[
            tripletWithCorruptedTriplet[0][0]]  # tripletWithCorruptedTriplet是原三元组和打碎的三元组的元组tuple
        tailEntityVector = copyEntityList[tripletWithCorruptedTriplet[0][1]]
        relationVector = copyRelationList[tripletWithCorruptedTriplet[0][2]]
        headEntityVectorWithCorruptedTriplet = copyEntityList[tripletWithCorruptedTriplet[1][0]]
        tailEntityVectorWithCorruptedTriplet = copyEntityList[tripletWithCorruptedTriplet[1][1]]

        headEntityVectorBeforeBatch = self.entityList[
            tripletWithCorruptedTriplet[0][0]]  # tripletWithCorruptedTriplet是原三元组和打碎的三元组的元组tuple
        tailEntityVectorBeforeBatch = self.entityList[tripletWithCorruptedTriplet[0][1]]
        relationVectorBeforeBatch = self.relationList[tripletWithCorruptedTriplet[0][2]]
        headEntityVectorWithCorruptedTripletBeforeBatch = self.entityList[tripletWithCorruptedTriplet[1][0]]
        tailEntityVectorWithCorruptedTripletBeforeBatch = self.entityList[tripletWithCorruptedTriplet[1][1]]

        if self.L1:
            distTriplet = distanceL1(headEntityVectorBeforeBatch, tailEntityVectorBeforeBatch,
                                     relationVectorBeforeBatch)
            distCorruptedTriplet = distanceL1(headEntityVectorWithCorruptedTripletBeforeBatch,
                                              tailEntityVectorWithCorruptedTripletBeforeBatch,
                                              relationVectorBeforeBatch)
        else:
            distTriplet = distanceL2(headEntityVectorBeforeBatch, tailEntityVectorBeforeBatch,
                                     relationVectorBeforeBatch)
            distCorruptedTriplet = distanceL2(headEntityVectorWithCorruptedTripletBeforeBatch,
                                              tailEntityVectorWithCorruptedTripletBeforeBatch,
                                              relationVectorBeforeBatch)
        eg = self.margin + distTriplet - distCorruptedTriplet
        if eg > 0:  # [function]+ 是一个取正值的函数
            self.loss += eg
            if self.L1:
                tempPositive = 2 * self.learingRate * (
                            tailEntityVectorBeforeBatch - headEntityVectorBeforeBatch - relationVectorBeforeBatch)
                tempNegtative = 2 * self.learingRate * (
                            tailEntityVectorWithCorruptedTripletBeforeBatch - headEntityVectorWithCorruptedTripletBeforeBatch - relationVectorBeforeBatch)
                tempPositiveL1 = []
                tempNegtativeL1 = []
                for i in range(self.dim):  # 不知道有没有pythonic的写法（比如列表推倒或者numpy的函数）？
                    if tempPositive[i] >= 0:
                        tempPositiveL1.append(1)
                    else:
                        tempPositiveL1.append(-1)
                    if tempNegtative[i] >= 0:
                        tempNegtativeL1.append(1)
                    else:
                        tempNegtativeL1.append(-1)
                tempPositive = array(tempPositiveL1)
                tempNegtative = array(tempNegtativeL1)

            else:
                #根据损失函数的求梯度
                tempPositive = 2 * self.learingRate * (
                            tailEntityVectorBeforeBatch - headEntityVectorBeforeBatch - relationVectorBeforeBatch)
                tempNegtative = 2 * self.learingRate * (
                            tailEntityVectorWithCorruptedTripletBeforeBatch - headEntityVectorWithCorruptedTripletBeforeBatch - relationVectorBeforeBatch)

            headEntityVector = headEntityVector + tempPositive#更新向量
            tailEntityVector = tailEntityVector - tempPositive
            relationVector = relationVector + tempPositive - tempNegtative
            headEntityVectorWithCorruptedTriplet = headEntityVectorWithCorruptedTriplet - tempNegtative
            tailEntityVectorWithCorruptedTriplet = tailEntityVectorWithCorruptedTriplet + tempNegtative

            # 只归一化这几个刚更新的向量，而不是按原论文那些一口气全更新了
            copyEntityList[tripletWithCorruptedTriplet[0][0]] = norm(headEntityVector)
            copyEntityList[tripletWithCorruptedTriplet[0][1]] = norm(tailEntityVector)
            copyRelationList[tripletWithCorruptedTriplet[0][2]] = norm(relationVector)
            copyEntityList[tripletWithCorruptedTriplet[1][0]] = norm(headEntityVectorWithCorruptedTriplet)
            copyEntityList[tripletWithCorruptedTriplet[1][1]] = norm(tailEntityVectorWithCorruptedTriplet)

    self.entityList = copyEntityList
    self.relationList = copyRelationList
def writeEntilyVector(self, dir):
    print("写入实体")
    entityVectorFile = open(dir, 'w', encoding="utf-8")
    for entity in self.entityList.keys():
        entityVectorFile.write(entity + "    ")
        entityVectorFile.write(str(self.entityList[entity].tolist()))
        entityVectorFile.write("\n")
    entityVectorFile.close()

def writeRelationVector(self, dir):
    print("写入关系")
    relationVectorFile = open(dir, 'w', encoding="utf-8")
    for relation in self.relationList.keys():
        relationVectorFile.write(relation + "    ")
        relationVectorFile.write(str(self.relationList[relation].tolist()))
        relationVectorFile.write("\n")
    relationVectorFile.close()
    def init(dim):
    return uniform(-6/(dim**0.5), 6/(dim**0.5))

def norm(list):
    '''
    归一化
    :param 向量
    :return: 向量的平方和的开方后的向量
    '''
    var = linalg.norm(list)
    i = 0
    while i < len(list):
        list[i] = list[i]/var
        i += 1
    return array(list)

def distanceL1(h, t ,r):
    s = h + r - t
    sum = fabs(s).sum()
    return sum

def distanceL2(h, t, r):
    s = h + r - t
    sum = (s*s).sum()
    return sum

def openDetailsAndId(dir,sp="    "):
    idNum = 0
    list = []
    with open(dir,"r", encoding="utf-8") as file:
        lines = file.readlines()
        for line in lines:
            DetailsAndId = line.strip().split(sp)
            list.append(DetailsAndId[0])
            idNum += 1
    return idNum, list

def openTrain(dir,sp="    "):
    num = 0
    list = []
    with open(dir, "r", encoding="utf-8") as file:
        lines = file.readlines()
        for line in lines:
            triple = line.strip().split(sp)
            if(len(triple)<3):
                continue
            list.append(tuple(triple))
            num += 1
    return num, list

if __name__ == '__main__':
    dirEntity = "E:\pythoncode\ZXknownlageGraph\TransEgetvector\entity2id.txt"
    entityIdNum, entityList = openDetailsAndId(dirEntity)
    dirRelation = "E:\pythoncode\ZXknownlageGraph\TransEgetvector\\relation2id.txt"
    relationIdNum, relationList = openDetailsAndId(dirRelation)
    dirTrain = "E:\pythoncode\ZXknownlageGraph\TransEgetvector\\train.txt"
    tripleNum, tripleList = openTrain(dirTrain)

    # print(tripleNum, tripleList)

print("打开TransE")
transE = TransE(entityList,relationList,tripleList, margin=1, dim = 128)
print("TranE初始化")
transE.initialize()
transE.transE(1500)
transE.writeRelationVector("E:\pythoncode\ZXknownlageGraph\TransEgetvector\\relationVector.txt")
transE.writeEntilyVector("E:\pythoncode\ZXknownlageGraph\TransEgetvector\\entityVector.txt")

数据

结果向量

对于一个知识图谱而言，其中保存的全部都是正样本是肯定的了，那么，我们应该如何获取负样本呢：

具体的可以通过随机替换头实体的方式来实现一个错误的三元组，或者采用随机替换一个错误的尾实体的方式来形成一个错误的三元组。为了避免，我们在替换形成的三元组也存在于知识图谱中，我们需要在替换之后进行过滤。

定义

节点类型

推荐系统优势

知识表示