Page 40 - 《软件学报》2020年第12期

3706 Journal of Software 软件学报 Vol.31, No.12, December 2020

点,, vv 和 v 分别是其对应顶点的嵌入向量.σ(x)是 Sigmoid 函数,K 是每次采样时选取负采样的边的数目.从文
i
j
n
献[27]中,我们可以得到一组参数设置:K 取 5,且 Pv ∝ d 3/ 4 ,d v 是顶点 v 的出度.在计算顶点的嵌入向量的梯度
()
v
n
时,我们采用文献[28]所提出的异步随机梯度的算法.具体做法为:如果边 e ij 被采样,假设此边的权重用 w ij 表示,

那么可以利用公式(3)来计算顶点 v i 的嵌入向量 v 的梯度:
i
∂ O ∂ log (pv | )v
= w ⋅ j i (3)
v ∂ ij v ∂
i i
在使用负采样方法进行嵌入向量的计算时,对于图中的每条边而言,一次计算的时间复杂度为 O(ϕ×(K+1)),
其中,ϕ表示每次采样所需要的时间,K 表示负采样的边的数目.假设一个图中含有 E 条边,此时的时间复杂度将
增加至 O(ϕ×K×E).由于 K 在计算时取值为较小的整数,因此计算过程中的时间复杂度取决于采样时间ϕ以及图
中所含边数 E.为了降低计算复杂度,我们使用了文献[29]中提出的别名表方法,该方法能根据边的权重调整每
条边被采样的概率,将每次采样的时间复杂度将至 O(1).最终,学习二部图中顶点的嵌入向量的时间复杂度为
O(K×E).
为了将 POI-POI 图、POI-地区图和 POI-时间段图嵌入到同一个低维潜空间中,我们使用文献[23]中提出的

联合嵌入学习方法,通过联合训练的方式得到 POI、地区和时间段在共享低维空间中的的表述向量: ,vr 和 t .
2.4 计算用户偏好

通过迭代学习参数,当图形中节点的结构稳定后,我们能够获得 POI、地区和时间段的表述向量.然而,嵌入
图模型不能直接学习用户的表述向量,需要利用合理的设计,将用户的偏好用 POI 来表述.其中,Yin 等人在文献
[23]中提出了一种基于时间延迟的动态用户偏好模型,其计算公式如下:
)
u = ∑ exp − (ττ− i v ⋅ i (4)
τ
(, , ) D ∩ u ( i τ ∈ < ) τ
i τ
uv
i

其中,D u 表示目标用户的签到记录集合,τ表示当前时间节点, v 表示 POI v i 的嵌入向量.由公式(4)可知:该方法将
i
用户偏好视作用户历史访问记录的加权累积,而每一次访问对用户偏好的权重随时间衰减,时间越早的签到,对
目前的用户偏好的影响越小.
按照公式(4)对用户偏好进行建模时,最近一次访问的 POI 对用户偏好的影响最大.通过对 Yelp 数据集中用
户最近一次访问记录的评分进行统计,其结果如图 5 所示,可以清晰地发现:在最后一次访问中,用户对项目的评
分较为均匀地分布在 1 分~5 分的间隔中,其中被评 1 分和 2 分的项目比例(18%)和(16%),而如果认为最近的行
为对用户偏好的影响最大,则计算出的用户偏好中会夹杂大量低评分的项目,明显不能真实反映用户的偏好.

Fig.5 Last score distribution
图 5 最近一次的评分分布
此外,在数据非常稀疏时,则获取的用户偏好会极端接近上一次的用户偏好.例如,假设用户访问集合
{(t 1 ,v 1 ),(t 2 ,v 2 ),(t 3 ,v 3 )},其中,t 1 和 t 2 距离当前时间较远,t 3 距离当前时间较近,则目前的用户偏好会和 t 3 时刻的偏好
非常相似.可见,这种方法虽然突出了用户偏好的时间衰减,但却忽略了用户偏好的周期性和连续性.而在日常