空间位置的关联分析及其向量化表示方法①

张 舒,郭旦怀,周纯葆,李薰春,靳 薇

1(中国科学院 计算机网络信息中心,北京 100190)

2(中国科学院大学,北京 100049)

3(国家广播电视总局广播电视科学研究院,北京 100866)

4(北京市科学技术研究院,北京 100089)

5(北京市新技术应用研究所,北京 100094)

空间位置作为重要的空间特征,常用于目的地预测与推荐,城市功能规划,交通管控系统,交通流量预测、位置分类等应用.传统的空间位置表示方法与空间向量化表示方法,常将其经纬度坐标与兴趣点(Points Of Interest,POI)信息将空间位置映射为 ID 类型,其中经纬度用来精确地描述空间位置,兴趣点为空间位置增添了大量属性特征.但是,传统的空间位置表示方法只保留了自身经纬度与POI 的信息,缺少了空间位置间隐含的时空关联信息,难以理解空间位置和推断空间位置间的关联关系.

融合空间位置的时空关联信息与其周边POI 信息,将有助于提高空间向量的表达效果.居民出行轨迹数据能够为结合两种信息的空间分析提供可靠的数据支持.居民的出行轨迹可体现居民的出行模式与活动规律,同时也反映出空间位置之间的关联,是制定城市交通管理方案的关键.随着GPS 定位技术的快速发展,可收集到大规模轨迹数据,使得轨迹数据能够被用于更加细粒度地分析空间位置的时空关联关系.当今的大规模轨迹数据,包括机动车轨迹与非机动车轨迹,已能够支持机器学习、深度学习等对于数据量的需求,并且能够为空间位置及其关联关系的理解、表示与推理学习提供可能性.

另一方面,随着深度学习在自然语言处理、计算机视觉等领域的迅猛发展,研究者已在空间分析中引入了深度学习方法[1].近些年提出的空间上下文理解模型中,考虑空间位置与其临近位置之间的关系,结合自然语言处理中的词向量模型,使用神经网络将词生成固定长度的向量表示,该词向量表示能包含该词的语义与上下文信息,最终生成结合空间邻接关系的空间位置向量化表示[2,3].但这些方法仅关注了空间的静态特征,尚未考虑到居民在空间之间的轨迹移动,从而缺失了居民出行的时空模式关联信息.

在使用深度学习技术处理复杂的关联关系时,一个有效的模型是图神经网络[4].图神经网络因其能够处理图结构形式的数据引起广大关注[5].借助图神经网络算法能够为更加复杂的图结构中的节点生成低维向量表示,该向量表示既包含了节点的类别特征,又聚合了节点在复杂图网络中的邻域特征[6].交通网络以图结构形式存在,因此,交通网络常使用图神经网络解决流量预测问题[7,8]与出发地、目的地预测[9]等问题.围绕空间向量化表示任务,DeepMove 基于出租车轨迹数据,使用图神经网络中的随机游走方法与Word2Vec 方法,为交通网络中的POI 节点生成含有邻域关联信息的向量化表示[10].但是DeepMove 仅使用了简单的图神经网络,未使用节点自身特征,难以聚合邻域节点特征.另一方面,这些研究只基于单一的轨迹数据,而没有考虑不同出行方式之间的联系.例如,居民从住所前往公司,通常会产生从住处到地铁站的骑行轨迹、从地铁站到公司所在地的地铁轨迹、公交站点之间的公交轨迹,通过综合这些轨迹才能发现住处和公司所在地之间存在的轨迹关联,而对不同类型的轨迹分别处理则会遗漏大量信息.

本文提出基于图神经网络的空间位置向量化表示方法,综合公交线路轨迹、地铁线路轨迹与大规模共享单车轨迹数据构建多源交通网络.同时,针对不同源交通轨迹数据的集成,本文提出一种针对不同类型轨迹数据的集成方法:将长距离出行与短距离出行进行匹配连接,以更全面地覆盖不同位置之间的空间关联.使用本文方法生成的空间位置的向量化表示,能够综合空间特征、邻域特征与时空关联特征.相较于其他已有方法,本文提出的空间向量化表示方法能够学习到空间位置的关联关系.

本文首先围绕着不同类型轨迹数据的网络构建展开讨论;其次介绍融合POI 与轨迹信息的空间向量化表示方法;然后设计实验以验证本文提出的空间向量化表示方法的有效性;最后讨论针对空间位置向量化表示任务,有待探索的研究方向.

1 多源交通轨迹数据网络构建

1.1 多源交通轨迹数据

相较于公交车与地铁等交通方式,近年来共享单车的流行为人们的出行方法提供了新的选择.共享单车因其更加灵活与便捷的特点,使得共享单车轨迹数据相较于其它交通轨迹数据,具有覆盖范围更广,数据规模更大,采样密度更高,位置精度更高等特点.由于共享单车在城市交通中的占比逐步增大,能够从一定程度上更加细粒度地描述城市居民的短距离出行模式,因此本文采用公共交通路网数据(包括公交线路与地铁线路),与共享单车轨迹数据相结合的方式,共同构建大规模交通网络.融合了共享单车轨迹数据与公共交通线路的交通网络能够更完整地体现居民的出行模式.

为了解居民的短距离出行模式,本文统计了共享单车轨迹数据分布.居民在工作日与非工作日一天内不同时间段的出行分布图如图1所示,可发现在工作日期间的早晚上班高峰时刻,居民对于共享单车出行的需求非常大;周末的出行需求量较为平均.此外,在剔除了异常轨迹距离后,骑行轨迹距离分布图如图2所示.可发现,当出行距离小于2 公里时,居民更倾向选择共享单车出行.

图1 不同时段内共享单车出行量分布图

图2 骑行轨迹距离分布图

对共享单车轨迹数据进行分析后可发现,利用共享单车轨迹数据与公共交通路网数据相结合的方式构建大规模交通网络,融合多种交通方式的出行轨迹,能够覆盖居民针对不同出行需求与出行距离的交通轨迹.

目前通过互联网开源数据,可获取到大量免费的共享单车轨迹数据以供研究者使用.本文使用摩拜共享单车开源数据集,涵盖了北京市居民于 2017年5月14日至2017年5月21日的骑行轨迹,样本量共计3 214 096 条.为避免异常数据的影响,剔除了骑行距离大于5 公里的轨迹.此外,通过数据爬取技术,获取北京市公共交通路网数据,具体包括公交车线路数据与地铁线路数据

1.2 集成不同类型轨迹数据的网络建模

为综合不同类型的轨迹数据,识别居民完整的出行模式,本文将长、短距离出行轨迹进行匹配连接.对不同类型轨迹数据的匹配方法如下:

第1 步.使用GeoHash[11]技术将共享单车轨迹数据与公交交通路网数据中的地点经纬度向量成固定长度的字符串.该字符串由空间位置的经纬度向量得到,并且其长短可用于划分空间位置的大小.本文具体使用长度为7 位的GeoHash 字符串.

第2 步.使用共享单车轨迹中的出发地与目的地作为节点,轨迹作为边,标记边的类型为共享单车出行,居民在此出发地与目的地的出行次数作为边的权重,以构建大规模交通网络.

第3 步.针对公共交通路网数据,以公共交通站点作为节点,线路作为边,依据公共交通的类型作为边的类型,构建大规模交通网络.

第4 步.通过以上步骤,合计产生 10.5 万个节点.通过百度地图开放平台,获取交通网络中的每个节点的POI 信息,经过one-hot 处理后,作为节点的属性特征;获取每个节点的交通拥堵信息,经过离散化处理后,作为节点的拥堵特征.

图3为使用该方法对长、短距离出行轨迹进行匹配的一个示例,例如从图中A-B,B-C,C-D 分别为某居民从住处到公交站的骑行轨迹,公交运行轨迹,从公交站到公司的骑行轨迹,通过匹配以上3 段轨迹可识别出A 到D 点的实际关联.

图3 长、短距离出行轨迹匹配示例

2 融合POI 与轨迹信息的空间向量化方法

本章节首先给出交通网络的形式化定义;然后介绍本文提出的POI 与轨迹信息融合模型;最后说明基于该模型的空间向量化表示方法.

2.1 形式化定义

文中常见符号的定义如表1所示.使用G=(V,E)表示交通网络,n=|V|表示节点的个数.使用X∈Rn×D表示节点特征矩阵,xv表示节点v的特征,其中xv∈RD,∀v∈V,表示矩阵X的第v行第j列,即节点v的第j个 特征.G与X作为图神经网络模型的输入.

表1 符号定义

2.2 POI 与轨迹信息融合建模

为了在神经网络模型中结合空间位置节点的POI 信息与轨迹关联信息,本文基于GraphSAGE 模型[12]提出融合建模的方法.GraphSAGE 模型能够通过对目标节点的邻居进行随机采样得到子图,再对子图进行卷积,替代了直接对全图进行卷积的方式,大大降低了计算和内存的压力.此外,GraphSAGE 模型通过学习聚合函数(aggregator)的方式,把邻居节点的特征聚合到中心节点自身.当学习得到聚合函数后,聚合函数能够泛化到新的节点或者新的网络上,即使是在训练过程中出现未知的节点,模型也能推断出其向量化表示.这一做法替代了直接学习网络节点的向量化表示,泛化能力更强,是一种归纳式(inductive)学习算法.

基于GraphSAGE 的向量化表示学习方法在每次迭代中进行以下3 个步骤:

第1 步.对图中的每个节点采样固定数量的邻居节点作为该节点的邻居节点集合;

第2 步.通过模型学习的聚合函数(aggregator)对采样得到的邻居节点集合进行聚合,以把邻居集合节点的特征信息聚合到中心节点上,得到新的节点向量;

第3 步.通过聚合邻域特征得到的节点的向量向量化表示用于损失计算,更新权重矩阵W.

算法1 为具体的向量化学习方法.在算法1 中,K为图卷积的层数,表示每个节点聚合K阶邻居.在外层循环的第k次迭代中,对于每个节点v首先通过聚合函数Agg来对节点v的邻居节点的k-1 层embedding向量进行聚合,得到节点v第k层的邻居聚合embedding,再将节点v的k-1 层得到的向量拼接起来接入全连接网络层,最终得到节点v在第k层的向量化表示.

算法1.基于POI 与轨迹信息融合建模的空间向量化表示算法G=(V,E) Wk,∀k∈K输入:图 ;节点特征矩阵 X;图采样深度 K;权重矩阵 ;非线性激活函数f;聚合函数Agg;邻居节点采样函数S.φv,∀v∈V输出:节点的向量化表示步骤:h0v←xv_,∀v∈V for k=1···K do:for v∈V do:hk(S(v))←Agg(h(k-1)i,∀i∈S(v))okv=CONCAT(h(k-1)v,hkS(v))hkv←f(Wk·okv)end hkv ← hkv||hkv||2,∀v∈V end φv=hKv,∀v∈V

2.3 空间向量化表示学习方法

已有的Place2Vec 研究通常使用POI 的语义特征与空间特征以生成POI 的向量化表示.但具体的某个空间位置通常存在多个POI,例如在商场与餐厅,住宅区与超市大多会同时出现,难以使用单独的POI 来表示空间位置.本文提出的方法通过构建大规模多源数据交通网络与POI 与轨迹信息融合方法直接得到细粒度空间位置的向量化表示.基于章节1.2 中使用公共交通路网数据与共享单车轨迹数据构建的大规模交通网络中,边具有各自的类型与权重,各节点的邻居数分布不均匀.因此,针对空间位置向量化表示任务,须对图神经网络中的采样方法与聚合方法加以修改,以适应交通网络的特性.具体的,考虑到使用多源数据构建的交通网络的边都具有类别、权重等特征,并且根据图2中对共享单车轨迹数据的统计分析,可发现居民在短距离出行时更倾向于选择共享单车出行.因此本文提出一种基于出行距离长短的采样方法,示意图见图4(a).对目标节点v的第k层邻居采样过程中,当k=1 时,即一阶采样函数,优先采样边类型为共享单车轨迹的邻居节点,当k=2 时,即二阶采样函数,优先采样边类型为公共交通线路的邻居节点.

经过采样函数后,节点的邻居节点集合是无序的,因此聚合函数不仅需要有很强的表征学习能力,还具有对称性(symmetric)要求,即函数的输出与输入聚合函数的节点顺序无关.本文使用文献[12]中提出的GCN aggregator 作为聚合方法,将不同层级的邻域中的邻居节点的特征聚合起来,并且将聚合后的邻域节点特征与目标节点特征拼接结合后,传递到全连接网络中.其中节点的聚合过程如图4(b)所示.利用图神经网络的反向传播机制,最终得到节点的向量化表示.

图4 交通网络中采样与聚合操作示意图

为了在无监督学习过程中得到更有效的空间位置向量化表示,使用图神经网络中的无监督损失函数,该损失函数的优化目标是最大化正样本的概率,使得邻居节点的向量化表示更加相近;同时最小化负样本的概率,使得没有共同交点的节点的向量化表示相异:

式(1)中,zv(v∈V)为图神经网络的输出,即空间位置的向量化表示;i为与v共同出现在一组随机游走上的节点;in～pn(i)表示in服从对i的负样本采样分布;Q定义为负样本的个数.对此,使用随机梯度下降学习方法与Mikolov 等[13]提出的负采样学习优化算法,用于更新图神经网络的权重矩阵Wk(∀k∈K)与聚合函数中的参数.当k=2,使用GCN 聚合方法,网络中节点规模为104左右时,本文提出方法的整体参数规模为105左右.此外,由于空间位置包含多个POI,可通过空间位置的向量化表示经过加权聚合操作后得到POI 的向 量化表示.具体的,POI 的向量化表示pi可定义为:

wij为位置向量 φj在pi中的权重.当使用平均权重时,wij=1.其中,本文使用tf-idf 统计方法计算权重wij[14],用以度量位置与POI 的相关程度.

3 实验分析

为了验证本文提出的空间位置的向量化表示方法的有效性,我们分别对空间位置向量化表示、由空间位置向量化表示加权聚合得到的POI 向量化表示进行评估.为了直观地理解空间位置的向量化表示,部分向量聚类结果采用可视化方式展现.

3.1 评价指标

使用空间位置向量化表示间(vi,vj)的Cosine 距离[15]以定义空间位置的相似度Sspace:

空间位置向量化表示的距离dplace则为:

相似的,由空间位置向量化表示经过加权聚合操作得到的POI 向量化表示,其相似度Spoi定义为POI向量化表示的Cosine 距离.此外,使用轮廓系数评估向量化表示的聚类结果[16].轮廓系数s(i)为:

其中,a(i) 表示样本i到同簇其他样本的平均距离;b(i)则为样本i到其他簇的最小平均距离;s(i) 的值域在[-1,+1]之间.a(i) 度量类内距离,b(i) 度量类间距离.当a(i) ＜＜b(i) 时,即类内距离远小于类间距离,则s(i)接近于1,表明聚类效果愈好.反之,当a(i) ＞＞b(i)时,即类内距离远大于类间距离,则s(i) 接近于-1,表明聚类效果愈差,样本i更应该被分类到其他簇.本文使用平均轮廓系数以评估整体样本的聚类结果.

3.2 实验结果与分析

3.2.1 空间位置关联分析

基于使用本文提出的向量化表示方法所生成的128 维POI 向量化表示,计算POI 之间的相似度Spoi.POI-POI 相似度矩阵如表2所示.具体的,可发现写字楼与企业园区,科研机构与高等院校,住宅区与购物中心的关联度更高,其向量间的Cosine 距离也较小.此外,由于使用多源交通数据构建网络,也能使得向量含有居民行为模式特征,例如机场的POI 向量与写字楼、高等院校的POI 向量的距离较小,而与超市、公园的POI 向量的距离较大,表明其关联程度较低.POI 关联性结果可验证本文提出的向量生成方法符合POI 之间的关联程度愈高,其间的Cosine 距离愈小这一规律,表明使用本文方法能够得到有效且可信度高的向量化表示.

为对比验证本文提出的向量方法的有效性,将本文方法生成的POI 向量与其他的已有方法进行对比.对比方法分别包括DeepMove[10],Node2Vec[17],其POI 的相关性关联热力图如图5所示.对比发现,使用本文方法得到的向量能够关联POI 的空间位置特征与居民的行为模式特征;POI 向量间的相似度基本符合先验知识,并且区分度高,优于已有方法.

表2 POI-POI 相关性(Cosine 距离)矩阵

为验证本文提出的多源数据构建大规模交通网络方法与交通网络采样方法的有效性,设置多组对比实验分别对模型、交通网络数据源、采样方法加以评估.基于K-means 聚类方法对POI 向量进行聚类操作,其超参数K为聚类类目,可表征为POI 的类目.在已有基于兴趣点(POI)大数据的研究综述中表明沈阳市有21 个POI 类目[18],由于POI 类目受多种人为主观分类因素影响,因此可认为K值应在 5～20范围内浮动.为避免聚类类目K值选取不当对实验结果造成的干扰,本文将K分别设定为5、10、15、20 以评估不同POI 聚类类目下的聚类效果,其中K值越大,类别越细致.并且每个K值分别进行5 次实验取平均值.使用平均轮廓系数对POI 向量聚类效果进行评估.表3给出了使用多种对比模型的实验结果,其中涉及的对比方法均使用融合了长、短距离轨迹的交通网络.实验结果表明,当POI 聚类类目K=15、K=20 时,由于本文提出方法相较于对比方法,既能够聚合了邻居节点的信息,又能够利用空间位置自身的特征,改善DeepMove[10]与Node2Vec[17]方法仅使用网络中的节点序列特征这一问题,因此当POI 分类类目较细致时,使用本文提出方法生成的向量能够保留更加细粒度的特征,其聚类效果优于对比方法.表4对比了不同采样方法的实验结果,实验结果表明在多数K值下,使用本文提出的路网采样方式生成的向量,其聚类效果都优于使用图神经网络中随机采样方式.表5对比了不同数据源的实验结果,实验结果表明,当K值较小时,使用代表长距离出行的公共交通线路所构建的交通网络,生成的向量聚类效果更好,但当K值逐步增大时,使用长、短距离融合的交通网络所生成的向量,其聚类效果比较稳定,当K=10、K=15 时,优于仅使用长距离出行轨迹或短距离出行轨迹构建的交通网络.因此可推断得出,当POI 分类较为粗泛时,长距离轨迹能区分不同功能区域,因此长距离轨迹构建的网络效果较好,当POI 分类较为细致时,融合长、短距离的出行轨迹能够捕捉到更加细粒度并且相对完整的出行模式,因此构建的交通网络所涵盖的信息更加丰富,效果更优.

表3 不同向量化方法的实验结果对比(轮廓系数)

表4 不同采样方法的实验结果对比(轮廓系数)

表5 不同数据源的实验结果对比(轮廓系数)

3.2.2 空间位置聚类分析

首先,利用K-means (K=8)对空间位置向量进行聚类分析,其中每个类别的轮廓系数如图6(a)所示.为了更加直观的反映聚类结果,使用t-SNE[19]方法将空间位置向量从128 维空间降维至低维空间,降维后的空间向量化表示的聚类结果如图6(b)所示,不同的颜色表明不同的类.本文结合低维空间向量化表示的可视化映射图作为一种直观的评价方式.通过观察图6可发现,使用本文提出的空间向量化表示方法得到的空间位置向量,映射在低维空间后,有较为明显的类间边界,能够验证本文提出的空间向量化表示方法的有效性.

图6 聚类分析结果

4 结论与展望

本文提出了一种基于图神经网络的空间向量化表示方法.基于共享单车轨迹数据与公共交通线路数据,将长、短距离出行轨迹进行匹配连接,构建大规模交通网络,该交通网络能够覆盖多种出行模式.提出了融合POI 与轨迹信息的空间向量化表示方法,综合位置自身的空间特征与其邻域的特征,并优化节点采样方法,提高了空间向量化表示的表达能力.以北京市的共享单车轨迹数据与公共交通路网数据为实例,经验证本文提出的空间向量化表示方法能够综合空间特征、邻域特征与居民出行模式,该向量可作为空间特征用于交流流量预测,交通调度与管理,地理画像,位置推荐等实际应用中.

在未来的工作中,将进一步研究融合多源数据,例如出租车,网约车数据,以构建大规模的交通网络.以及当网络规模增大时,如何提升模型性能,使其能够处理更大规模的交通网络.