一种基于领域知识的链路预测方法

2020-11-12李奋华赵润林

计算机应用与软件 2020年11期

李奋华赵润林

(运城学院数学与信息技术学院山西运城 044000)

0 引言

个性化推荐技术已经在电子商务领域获得了较广泛的应用[1]。在推荐系统中，推荐算法是推荐系统的核心部分，协同过滤算法作为经典的推荐算法在推荐系统中获得了较成功的应用[2-3]。但是协同过滤算法自身存在一些问题，例如：在数据稀疏的情况下，其推荐效果较差，且在推荐过程中并没有考虑实体间的一些附加有用信息[2]。有些学者提出了基于链路预测的个性化推荐算法，这些算法主要是利用顾客商品二分网络中顾客与商品之间的关联信息来弥补数据稀疏的问题，通过使用二分网络的拓扑结构信息来改善算法的推荐质量。然而，这些算法在推荐过程中仅仅利用了二分网络的拓扑结构信息，并没有考虑商品的领域知识。文献[3]提出采用顾客商品二分网络中商品的领域信息进行推荐，能够进一步改善推荐的精度和效果。

本文结合顾客商品二分网络的拓扑结构和网络中节点的相关属性，提出一种基于领域知识的链路预测方法。在该方法中，推荐给顾客的不同商品有不同的权重，权重的大小由与该商品相关的领域知识来决定，权重越大的商品被认为是越符合顾客需求的，越值得推荐给顾客。

1 链路预测算法

1.1 典型的链路预测算法

链接预测(Link prediction)是指如何通过已知的边(即网络拓扑结构)或者节点的特征等信息来预测评估社会网络中节点之间未知链接(包括已存在而丢失的链接、未来的链接)存在的可能性[4-5]。几种典型的链路预测算法介绍如下：

1) 共同邻居方法(Common Neighbors，CN)：该方法是基于待预测节点对的共同邻居节点的数量来对社会网络进行链接预测[6-9]。在这里，假设Γ(x)代表节点x的共同邻居的集合[10-11]。一般来说，如果待预测节点对(x,y)具有的共同邻居数量越多，那么就认为节点x和节点y之间存在连边的可能性越大。因此，共同邻居方法的节点相似性度量指标定义如下：

(1)

2) Adamic Adar方法(简称AA)：该方法是基于待预测节点对的共同邻居集合来进行链接预测的。针对待预测节点对的每个共同邻居节点在链接预测中的作用不同，它赋予每个共同邻居一个权值，该权值是对应共同邻居节点度值对数的倒数[12-13]。如果一个节点的度值比其他节点小，那么该节点在链接预测中的作用比其他节点更重要[4-5，14-15]。该方法的节点相似性度量指标定义如下：

(2)

式中：Γ(x)、Γ(y)分别代表节点x、y的共同邻居的集合；Kz表示节点z的度。

3) Jaccard Index方法(简称JA)：该方法由Jaccard提出[10]，是信息检索领域被广泛应用的一种相似度度量方法[16-17]。它的主要思想是：给定一个节点对(x,y)，在节点x、y的邻居并集中，将随机选择一个邻居节点是该节点对共同邻居的概率作为节点相似度的度量指标。该方法定义如下：

(3)

一般来说，评估预测算法精确度的主要有两个指标：AUC和Precision。AUC是从整体上来考虑算法的预测精度；Precision是从局部层面来考虑算法的预测精度[18]。

1.2 顾客商品二分网络

复杂系统在现实生活中普遍存在，复杂网络是表示和研究复杂系统的有效方法之一。在复杂网络中，节点表示复杂系统中的个体，边表示个体之间存在的关系[5，16]。二分网络是复杂网络的一种特殊形式，在该网络中节点被分成不同的两类节点，同类节点之间不存在关系，只有在不同类节点之间才存在关系[19]。在电子商务领域，顾客购买商品构成的网络就是二分网络，假设P={p1,p2,…,pn}表示顾客商品网络中的商品集合，C={c1,c2,…,cm}表示顾客商品网络中的顾客集合，因此，能够获得一个隶属关系矩阵A=(aij)n×m，其中aij表示网络中节点i代表的特定对象(即商品i)与节点j代表的特定对象(即顾客j)的隶属(即购买)关系值，也就是说，在该矩阵中如果顾客ci购买了商品pj，那么aij赋值为1，否则aij赋值为0。在顾客商品二分网络中，如何选择顾客没有购买过的合适商品推荐给每个顾客是个性化推荐中很关键的问题，传统的协同过滤算法虽然有时能够取得较好的推荐效果，但是该算法仅仅考虑网络节点(顾客/商品)的直接邻居，具有一定的局限性[20]。图1为一个顾客商品二分网络，在该网络中平行四边形代表顾客，椭圆代表商品，实线表示顾客已购买商品，虚线表示将来顾客可能购买的商品(即个性化推荐)。

图1 顾客商品二分网络

2 方法设计与实现

2.1 基于领域知识的链路预测方法

链路预测实际上是根据网络的拓扑结构的特点来推断未来有可能出现的关系。在生物研究领域，研究者根据共有邻居的数量来计算蛋白质对之间的拓扑相似度，以此来进行预测和推荐。文献[3]利用二分网络的拓扑特点，在电子商务中的商品推荐方面做了一定的研究。在此启发下，根据顾客商品二分网络的拓扑特点，把链路预测和领域知识相融合，描述了一种顾客商品推荐方法。假设顾客商品二分网络G，通过相似度分值来计算未来顾客c购买商品P的连边的可能性大小，以此作为推荐的依据。对于节点x，Γ(x)代表节点x的共同邻居的集合，那么节点x的邻居的邻居集合定义如下：

Γ′(x)=Γc″∈Γ(x)(c″)

(4)

对式(1)作修改后，连边可能性的度量标准如下：

CP_CN(p,c)=|Γ(p)∩Γ′(c)|

(5)

同理，对式(3)作修改后，可获得连边可能性的度量标准如下：

(6)

在文献[3]的启发下，根据实际顾客商品网络中商品的分类，构建商品的分类层次结构树，在此分类结构树的基础上，构建商品之间的语义相似度的度量标准，如下：

(7)

式中:dis(pi)表示商品分类树中商品pi与根节点的路径长度；set(P)表示商品pi和商品pj共同的祖先节点的集合；n表示set(P)中祖先节点的个数。

把式(7)和式(5)、式(6)相融合就得到在顾客商品二分网络中基于链路预测和领域知识的推荐评估指标，如下：

(8)

(9)

式中：pi表示顾客c已经购买的商品；CHB(c)表示顾客c已经购买商品的集合；m表示顾客已经购买商品的数量(即CHB(c)集合的大小)。

2.2 实验分析

根据2.1节中描述的顾客商品推荐方法，在实际的超市购买数据集上进行实验，该数据集包含了近1年3 542名顾客的购买信息，其中涉及到的商品有487种，交易次数达到36 873次。在本实验中，用链路预测中的AUC作为推荐结果的度量标准，把该方法中的分值最高的前20种商品推荐给顾客，分别把数据集的70%、80%作为训练集，剩余的作为测试集，实验结果如表1和图2所示。