Sci论文 - 至繁归于至简,Sci论文网。 设为首页|加入收藏
当前位置:首页 > 计算机论文 > 正文

基于Katz自动编码器的城市路网链路预测模型(附论文PDF版下载)

发布时间:2018-08-11 16:11:37 文章来源:SCI论文网 我要评论














SCI论文(www.scipaper.net):

        特别说明:理工类、计算机类和医药类等论文在小编发布时可能会因为复杂的科学计算公式,导致文本格式出错,在阅读时较难读懂,阅读体验一般,建议大家可以直接在文章底部翻页到最后一页下载论文PDF版文档进行深度学习和阅读,感谢理解!

盛津芳,刘家广,王 斌
SHENG Jinfang, LIU Jiaguang, WANG Bin
中南大学 信息科学与工程学院,长沙 410083
School of Information Science and Engineering, Central South University, Changsha 410083, China

SHENG Jinfang, LIU Jiaguang, WANG Bin. Katz Auto Encoder for Urban Road Network Link Prediction Model. Computer Engineering and Applications

Abstract:Urban road network is a special complex network. The link prediction of road network has important application value in urban planning and urban structure evolution. As the road network is highly sparse and nonline- ar, this paper proposes a road network link prediction model based on the Katz Auto Encoder Network Embedding (hereafter as KAENE). This prediction model is a deep learning network embedding model based on the Auto En- coder with the following characteristics. First, it uses Katz similarity matrix to preserve the structural characteristics of the road network. Second, the multi-layer non-linearAutoEncoderis used to learn network characterization of the road network. Third, during the model training period, it uses LLEloss function to preserve the local characteristics of the road network. Forth, it also uses L2-norm topreventoverfitting.Finally, it combines with the directional char- acteristics of the road network to improve the link prediction accuracy of the road network. Through experiments, this paper compared the different performance between KAENE model and other link prediction models usingdif- ferent urban road network data, at the same time, it also identified the influence of different embedded dimensions on the prediction accuracy of KAENE model. At last, we know the network characterization learning process of this model through visualization. The experimental results show that KAENE achieves a good performance in the link prediction tasks of six representative road network datasets at home and aboard.

Key words: Complex Networks; Link Prediction; Network Embedding; Auto Encoder; Urban Road Network

摘 要:城市交通道路网络(以下简称“路网”)是一种特殊的复杂网络,对路网进行链路预测在城市规划与城市结构演化方面有着重要的应用价值。针对路网的高度稀疏性、高度非线性特点,提出了一种基于 Katz 相似度自动编码器(Katz Auto Encoder Network Embedding,KAENE)的路网链路预测模型,它是一种基于自动编码器的深度学习网络嵌入模型,使用 Katz 相似度矩阵保存路网的结构特征,利用多层非线性自动编码器对路网进行网络表征学习,在模型训练阶段通过局部线性嵌入损失函数保存路网的局部特征,在此基础上引入 L2 范数来提高模型的泛化能力,最后结合路网的方向性特征提高路网的链路预测精确度。通过实验对比了 KAENE 模型与其它链路预测模型在国内外的不同城市路网数据上的表现以及不同嵌入维度对KAENE 模型预测精度的影响,最后通过可视化了解了模型的网络表征学习过程。实验结果表明,KAENE 在国内外 6 个具有代表性的路网数据集的链路预测任务中取得了良好的表现。

关键词:复杂网络;链路预测;网络嵌入;自动编码器;城市路网

基金项目:国家科技重大专项课题资助(No.2017ZX06002005)。
作者简介:盛津芳(1971-),女,博士,副教授,主要研究领域为大数据、云计算、复杂网络,E-mail: jfsheng@csu.edu.cn; 刘家广(1992—),男,硕士研究生,主要研究领域为复杂网络、深度学习;王斌(1973—),男,博士,教授, 主要研究领域为软件工程、云计算、复杂网络。

1 引言

随着城市化的发展,城市交通路网结构因交通模式、自然条件、人口区域分布、演化阶段及发展水平的不同会产生明显差异,经济技术的发展时刻改变着路网结构[1],城市道路交通路网演化会变得越来越复杂。路网的复杂演化加大了城市道路规划的决策难度,如果道路规划不合理,就会导致路网资源无法合理分配,甚至有可能阻碍城市化发展。

20 世纪以来,随着“小世界网络”与“无标度网络”研究的兴起,复杂网络可以作为一种网络建 模工具,进而对路网进行建模,复杂网络的链路预 测则为研究路网的演化方向提供了可行的解决方案。目前,链路预测在朋友圈好友推荐以及探究蛋白质 相互作用实验领域取得了成功[2]。以路网为例,对未 知链路的预测或者对未来链路的预测本质上是对路 网的演化方向的预测,也是对路网拓扑结构的数据 挖掘过程。

应用复杂网络理论进行城市路网拓扑结构描述和路网网络演化行为理解已成为交通地理信息系统重点研究方向之一。宋等[3]利用复杂网络理论,构建了以连接度、介中心和接近度为度量指标定义道路重要度评价模型。赵等[4]利用复杂网络理论分析了路网的复杂特性及鲁棒性。越来越多的复杂网络模型被用来分析路网结构特征。但是,利用复杂网络链路预测加深对路网演化行为理解,目前处于空白研究领域。因此,利用复杂网络的链路预测理论对路网进行数据挖掘,进而揭示路网的演化本质具有非常重要的意义。

近年来,网络嵌入技术[5]成为研究者的热点方向, 网络嵌入技术是指将网络中的节点或者边投影到低 维向量空间中,再用于后续复杂网络的数据挖掘任 务。网络嵌入技术将网络中的节点或者边投影到低 维向量空间中,而不损失网络的结构特征,网络中 两个节点的相似度信息可以用低维空间中节点间的 向量空间距离表示。这种技术不但可以用于复杂网络的链路预测,还可以用于网络中节点分类聚类等任务,因此具有非常好的扩展性。目前,将网络嵌入技术用于路网的链路预测面临着三个主要困难:

(1)路网的高度非线性。路网节点之间的链接关系非常复杂,捕获路网的非线性特征非常困难。(2) 路网的局部性与全局性特征。模型在进行训练时学习到的局部特征与全局特征很难得到兼顾。(3)路网的高度稀疏性。相对于科学家论文合作网络、Facebook 朋友网络、互联网网络等网络来说,路网具有高度稀疏性。

目前,深度学习在语音识别、计算机视觉等多类应用中取得了突破性的进展,深度学习所学得的模型中,非线性操作的层级数更多。基于深度学习的链路预测,可以使模型学习到复杂网络中更深层次的网络拓扑特征,为路网的高度非线性难题提供了解决方案。

基于以上应用背景以及路网这类“特殊”的复 杂网络,本文提出了基于 KAENE 的城市路网链路预测模型,它是一种基于自动编码器的深度学习网络 嵌入模型,使用 Katz 相似度矩阵保存路网的结构特征,利用多层非线性自动编码器对路网进行网络表 征学习,通过局部线性嵌入损失函数保存路网的局 部特征,最后结合路网的方向性特征提高路网的链 路预测精确度。KAENE 将会对于城市路网复杂演化的科学管理与规划、提高路网的资源利用率以及增 强交通网络的平衡性和可靠性具有重要的现实意义。

2 相关工作

2.1 网络嵌入技术
复杂网络的链路预测受到来自不同领域科学家的广泛关注,各种模型不断不提出。吕等[6]在链路预测的研究综述中总结了基于相似性指标、机器学习以及概率模型的链路预测方法。近几年来,基于网络嵌入技术的链路预测开始受到研究者们的广泛关注。网络嵌入技术将图的节点或者边投影到低维向量空间中,实现节点的向量化的同时可以保持网络结构的不变性。如图 1 所示,图 1(a)为一个简单

的复杂网络图,图 1(b)经过 LAP[7]将图 1(a)表征映射到二维平面空间。从图 1(b)中可以看出,
LAP 将整个网络划分成了 3 个集合:U1=[0,1,5],U2 = [2,3,4], U3 = [6,7,8,9],从横坐标轴进行切割,将其划分为 2 个集合[U1, U2]与U3,与图 1(a)相比,可以认为其表征结果在拓扑结构上具有一定的结构相似性,但是仍有改进的空间。由于二维空间的表征能力有限,我们通常关注的是网络在高维空间的向量表示。
目前基于网络嵌入技术的链路预测相关研究成果主要有 LAP[7]、Node2vec[8]、SDNE[9]、GF[10]、
LLE[11]、NMF[12]、SVD[13]、HOPE[14]等。

(a)复杂网络图 (b)LAP 表征学习结果

“二阶近似”来保存网络的结构特征。然而,在路网的链路预测任务中,SDNE 模型的预测效果有待提高。本文提出了一种KAENE 链路预测模型,与SDNE 不同之处在于:(1)使用 Katz 相似度矩阵保存路网的全局特征(2)在模型训练阶段引入局部线性嵌入损失函数保存路网的局部特征,在此基础上引入 L2 范数来提高模型的泛化能力(3)结合路网的方向性特征提高路网的链路预测精确度。
模型的设计与实现
相关定义
定义图 G=(V,E)为一个无向连通图,V 为 G 中节点的集合,E 为边集合。定义 N= |V|,N 为图 G 的节点数,M=|E|为图 G 的边数,则该网络中一共有 N (N
– 1) /2 节点对。给定时间ð时图 G 中各节点对状态, 链路预测问题可以形式地描述为推断当前状态中或将在时间ð+t 中形成的缺失链接的子集。
定义 A 为图G 的邻接矩阵,A 满足以下条件,

图 1 网络嵌入技术表征模型

A= (aij)n×n ,aij =

(1)


2.2 深度学习
传统的机器学习通过手工来提取原始数据的特征,深度学习的出现,避免了这一繁琐的过程。在语音识别、计算机视觉等领域,深度学习模型已经

A 是一个对称矩阵,对角线元素均为 0,矩阵的各个行和(列和)是各个顶点的度。所有元素相加和为边数的二倍。
定义网络 G 的平均度 Avd,

变得越来越重要。在过去,训练两个以上隐藏层的

Avd=  |E|
|V|

(2)

神经网络非常困难,其主要难点在于高维参数空间和高非凸目标函数以及基于梯度下降的方法很容易陷入局部最小。随着计算能力的提升以及无监督和有监督的训练算法的进展[15,16,17],这些问题都得到了有效解决。
目前,无监督学习方法,如自动编码器[18] 与
RBMs[19]等,这类算法采用逐层初始化神经网络的方式,自动实现了对未标注数据的特征提取。在深度学习框架下,Chang 等[20]使用了多层卷积神经网络实现了对异构数据的网络表征学习。Wang 等[9]人提出 SDNE 模型,使用了自动编码器对复杂网络进行表征学习,通过在损失函数中引入“一阶近似”与

即边的数量与节点数量的比值,平均度表达了网络的密度。一般来说,平均度越小网络越稀疏。
定义An为邻接矩阵的 n 阶幂,
An = A^n (3)
An = k表示的是从节点 i 出发走到节点 j 走 n 步, 有 k 种路径可达。如果 k 的值为 0,表示节点 i 与节点 j 在 n 步内不可达。
3.2Katz 相似矩阵
Katz 相似度[21]由 KatzL 在 1953 年提出,它考虑了节点间的所有路径数,对于短路径之间的节点赋予了较大的权重值,对于长路径之间的节点对赋予

了较小的权重值。已知邻接矩阵 A,则 Katz 相似性矩阵的定义如下,
SKatz = αA + α2A2 + α3A3 ⋯ (4)
其中 α∈(0,1),α 是控制路径权重的调节参数,通过

为 k 维编码偏差向量。
为了得到训练误差,需要将Y(k)作为输入,通过
解码神经元解码后得到Z(n),解码过程如下,
Z(n) = o (W(d)Y(k) + b(n)) (8)

i i
它来调节远距离路径对相似度的影响,当网络节点

数量很大时,Katz 系数在有限时间内很难被计算出。但是当 α 小于邻接矩阵 A 最大特征值的倒数时,
SKatz可以进行收敛,SKatz收敛后的表达形式如下,
SKatz  = (I — αA)–1    –I (5)
–1

o为解码神经元激活函数 W(d)为解码权重矩阵 b(n)
为 n 维解码偏差向量。
评估训练模型的好坏主要由目标损失函数决定。目标损失函数经常用方差代价函数,
||X(n)–Z(n)||2

I 为单位矩阵 (I — αA)

表示(I-A)的逆矩阵。在对

LMSE =

       i i
2

(9)

路网进行网络训练时,α 表达了长距离路径对预测结
果的贡献度。

整个模型的训练过程中,应用梯度下降算法对权重矩阵与偏差进行调整,

为了将 Katz 相似度指标系数映射到[0,1]之间,

W(d) = W(d)

&LMSE

需要对数据进行标准化,常用的标准化方法有
Min-Max 标准化以及 Z-score 标准化,本文中使用了

— η (d)
= W(d) — 5Z(n)o, (W(d)Y(k) + b(n))(10)

Min-Max 标准化,其计算方式如下,
x∗ = x–min
mas–min


(6)

i i

b(n)  = b(n) &LMSE &b

其中 min 为SKatz中的最小值,max 为最大值。

= b(n)  — ηZ(n)o, (W(d)Y(k)  + b(n)) (11)

i i

3.3自动编码器与损失函数
自动编码器是一种无监督机器学习技术,利用神经网络来产生一个高维输入的低维表示,从而达到网络嵌入的目的。传统的维度下降依赖于线性方法,如 PCA[22],通过找出高维数据中最大的方差的方向进行降维。然而,PCA 方法的线性也是导致自身可以抽取出的特征维度类型上的很大限制。自动
编码器使用大量的非线性函数克服了这些限制,从

其中5 为学习速率,由于 Sigmoid  函数的性质,
o的导函数为o,(x),当 x 取Sigmoid 函数两端的值(很大或者很小的值)时,Sigmoid 函数的斜率很小,即
o,(x)的值会很小,因此导致W(d)与b(n) 的权值下降的很慢,针对这个问题,我们引入了交叉熵损失函数,函数定义如下,
lossentropy = — 1 ∑s [X(n)lgZ(n) + (I — X(n))lg(I —


n i i i

而可以体现数据的天然非线性。
单层自动编码器的基本原理如下,假设输入一个 n 维向量X(n),通过自动编码神经元映射到一个 k 维向量Y(k),其中k < n,有
Y(k) = o (W(e)X(n) + b(k)) (7)

Z(n))](12)
其中 I 为单位向量,lossentropy对权重W(d)与偏差
b(n)导数为
  6LH = 1 ∑s xi(o (W(d)Y(k) + b(n)) — X(n))(13)


i i 6W(d) n i i

Y(k)为X(n)在 k 维空间的向量表示,o为编码神经元

6LH 1
(d)(k)(n)(n)

i i 6b(n) = n ∑s(o (W

Yi + b

) — Xi

)(14)

激活函数,通常使用的是 Sigmoid 函数,本文所使用
的激活函数都为 Sigmoid  W(e)为编码权重矩阵  b(k)

可以看出公式中没有o的导函数o,(x),因此避免了损失函数更新过慢的问题。而权值更新取决于(Z(n) —

X(n))即误差,误差越大更新越快,误差越小更新越慢。为了使模型学习到局部特征,引入 LLE 中的局部线性嵌入损失函数,

合 C 表示横向道路节点,n=|C|为横向节点个数,集合 D 表示纵向道路节点,m=|D|为纵向节点个数, 定义图 G 邻接限制矩阵 L 有以下形式,

lossLLE = ∑ |Y(k) — ∑ A

Y(k)|

(15)

L=( n × n n × m

18)

i i j

ij j

m × n m × m) (

其中A 为邻接矩阵,通过加入局部线性嵌入的限制, 使得网络在进行表征学习后,节点间保持嵌入之前的邻接关系。为了防止模型的过拟合,常用的做法其中n × n与m × m矩阵部分为全零矩阵,n × m与m × n为全 1 矩阵,定义矩阵 S 中的元素值S(i,j)与L(i,j)的&计算,则其结果R(i,j),

是在损失函数中加入 L2 范数规则限制,

R(i,j)

= { 0, L(i,j) = 0
S(i,j), L(i,j) = 1

(19)

L2 = 1 ∑K (||W(e)||2 + ||W(d)||2 )(16)
2

最后得到的损失函数为
LK(X, Z) = lossentropy + þlossLLE + L2(17)
单层的自动编码器是利用单层非线性函数学习网络的结构特征,只含有一个隐藏层,是一种浅层的学习模型。浅层学习模型的局限性在于有限样本和计算单元情况下对复杂函数的表示能力有限,针对复杂问题其泛化能力受到一定制约。自动编码器可以使用一种堆叠技术,实现更深层次的网络学习。堆叠的自动编码器的训练过程如图 2 所示。X(n)作
为第一层编码输入后输出Y(n–1),再将输出的Y(n–1)

R=S&L 保存了路网的方向性特征对结果的影响,通
过添加 L 限制提高预测的准确度。
3.5KAENE 模型
整个模型的框架描述如下,首先,在进行网络表征学习之前需要计算路网的Katz 相似矩阵SKatz, 然后标准化后得到 X,利用自动编码器对 X 矩阵进行网络嵌入学习得到 k 维网络表征矩阵Y(k),利用
Y(k)表征矩阵重构邻接矩阵后得到 Z 表征重构邻接
矩阵,对 Z 矩阵添加 L 限制最后得到R预测结果矩阵。模型的预测过程如算法 1 所示。
算法 1KADNE 路网链路预测算法

i i

作为新的输入进入到第二层自动编码器,堆叠自动编码器由多个自动编码器通过这样的方式堆叠,逐层进行非监督预训练,最终保留Y(k)作为节点 i 的表征向量。


图 2 堆叠自动编码器无监督训练过程

3.4 路网的方向性特征
由于城市路网道路有方向性特征,横向道路往往会与纵向道路连接,为了引入这种特征,定义集

输入:路网 G=(V,E)、Katz 参数α、局部线性嵌入系数þ、表

征维度 k、迭代次数 n、学习速率5

输出:R 表征预测结果矩阵

○1 输入 G 根据式(1)得到邻接矩阵 A

○2 输入 A、α,根据式(5)计算SKatz

○3 对SKatz根据式 (6)进行标准化后得到 X

○4 for i←1 to n do:

○5 输入 X、k,根据式(7)计算Y = Y (k)

○6 根据式(8)计算Z = Z(n)

○7 根据式(17)计算 Loss = LK(X, Z)
○8  输入5、þ,利用用 Adma 梯度下降算法和反向传播算法最小化 Loss 为目标,以学习速率5更新模型权重以及偏差参数
○9 endfor
○10 得到网络表征向量Y = Y(k)

原始采集的路网数据具有边缘节点独立性(边缘节点度为 1)以及网络非联通性等问题,可采用节点删除和保留最大联通子图两个方法解决。
4.2 数据集
本文采集了国内外具有代表性的几个城市路网数据集,经过对偶拓扑建模以及数据处理后,形成的数据集信息如表 1 所示:
表 1  国内外具有代表性的城市路网数据集信息表


○11 根据式(8)重建邻接矩阵,得到表征重构矩阵 Z 城市名称 节点 边 平均度
HengYang.China 726 1430 1.97
○12 根据式(18)得到 L ChangSha.China 5018 10497 2.09
HangZhou.China 11299 23772 2.10
○13 根据式(19)计算预测邻接矩阵 R= Z&L Rockford.USA 4767 10559 2.22
Seattle.USA 8191 17732 2.16
SanFrancisco.USA 11669 24067 2.06

4数据准备与处理

4.1 路网建模与数据处理
OpenStreetMap[23] 是 由  ODbL  (Open Database
License) 授权的共享开放地图数据库, OSM  是
OpenStreetMap 定义的地图 XML 格式文件,其主要包含了三种数据基本单元即节点(nodes)、路(ways) 以及关系(relations),nodes 定义了地图中点的坐标,
ways 定义了路段,一条 way 由多个node 节点组成,
relations 则定义了基本单元之间的关系。
在路网建模方面,主要有两种拓扑建模方法, 分别为主方法与对偶拓扑网络方法[24]。主方法是直接将道路抽象为边、交叉口抽象为节点,而对偶拓扑方法则恰恰相反,它将道路按路名映射为节点、交叉口映射为边。如图 3 所示,可以看出采用对偶方法不但使用了更少的节点与边,而且在功能的表达上更能体现其结构特点。

(a)现实路网 (b)主方法 (c)对偶方法
图 3    路网拓扑模型

从表中数据我们可以看出路网的平均度均在
2.0  左右,相比于科学家论文合作网络( 平均度
21.10)、Facebook 朋友网络(平均度 25.64)、Internet拓扑网络(平均度 9.86)等[25]网络来说,路网则显得更稀疏,而网络的稀疏性也是复杂网络链路预测需要解决的一个难题。
4.3训练集与测试集划分
在进行链路预测之前,我们需要划分训练集与测试集,通过随机采样的方式去掉 20%的边,这些被去掉的边会成为实验的真实测试数据。如图 4 所示,实线与虚心共同构成了整个网络结构,虚线部分的边集合是通过随机采样选择的测试数据,实线部分的边集合是训练数据集,首先将训练数据放入模型中训练,然后将训练好的模型对测试集进行预测并计算 MAP 指标。

图 4 训练集与测试集的划分
4.4评价方法
评价复杂网络链路预测模型的常用方法是
MAP[5]。MAP 估计每个节点的预测精度值,并计算所有节点的平均预测精度,计算方法如下:

Pre@k(i) = |{j|i,j∈V,indes(j)Šk,Oi(j)=1}|(20)

表示经排序的第 j 个节点,Oi (j) = 1表示节点 i 与节点 j 存在一条边。定义节点 i 的预测精确度为

地展示出来。
5.2 时间耗费与预测精度对比
本文对比了 18  种链路预测算法,其中包括了
10 种相似度算法以及 8 种网络嵌入算法,10 种基于

AP(i) = ∑j Pre@j(i)∗Oi(j)
|{Oi(j)=1}|
则 MAP 的计算方式为
MAP = ∑i ÆP(i)
|V|
其中,V 是网络中的节点集合。

文章出自SCI论文网转载请注明出处:https://www.scipaper.net/jisuanjilunwen/440.html

相关内容

发表评论

Sci论文网 - Sci论文发表 - Sci论文修改润色 - Sci论文期刊 - Sci论文代发
Copyright © Sci论文网 版权所有 | SCI论文网手机版 | 豫ICP备2022008342号-1 | 网站地图xml | 百度地图xml