冯慧芳，柏凤山，徐有基

(西北师范大学 数学与统计学院，兰州730070)

0 引言

随着网络通信技术、定位导航技术及卫星遥感技术的发展和广泛应用，获取海量时空数据变得越来越容易，这些时空大数据记录了移动对象(人、车、飞机、货物等)的时空变化.具有时空属性的大数据的产生为长时间、高精度、高效地跟踪研究个体时空移动特征提供了可能[1-2].通过数据挖掘技术分析这些时空大数据，研究个体时空移动特征，能够为城市规划与管理[3]、交通监控与预测[4]、旅游监测与分析[5]等众多领域的研究提供方法和决策指导.

基于车辆的轨迹时空数据挖掘研究是目前国内外城市大数据研究的热点之一.车辆轨迹数据的分析和建模不仅为了解人们的移动模式提供了新的角度，也为以数据为中心的智慧城市的构建、规划与管理提供支撑[6-7].文献[8]根据历史GPS数据建立了一种复杂度较低的交通流量预测模型，并用真实车辆GPS数据对预测模型进行了性能评价.文献[9]则是利用出租车轨迹数据创建一种新的轨迹路段出行时间模型，并采用纽约出租车数据验证了模型的有效性.文献[10]使用出租车GPS历史数据，通过对空车到达过程建模，预测单个乘客等候出租车需要时间.文献[11]用浮动车GPS数据分析了罗马南部EUR区交通流特征，并采用贝叶斯网络、神经网络和季节ARIMA(Seasonal AutoRegressive Moving Average)对短时车辆速度的预测能力做了比较研究.文献[12]根据GPS数据建立了能够刻画出行需求、速度和出行线路方向等特征的城市移动模型，应用该模型可预测城区道路交通能力.文献[13]以车辆轨迹数据为基础，提出了一种基于车辆轨迹大数据的道路网快速变化发现与更新方法，该方法相比常规方法能正确判断道路变化类型、区分真实变化与语义变化.

为了更好地理解城市交通状态，本文以典型河谷型城市兰州市为例，以出租车GPS轨迹数据为数据源，结合城市道路网络的拓扑结构特征和交通流特性，建立基于有向加权复杂网络的城市交通网络关键节点识别模型.

1 基于有向加权复杂网络的城市路网模型

1.1 有向加权城市路网模型的构建

复杂网络模型用G=(V,E)表示，其中，V={v1,v2,…,vN}为节点集合，E={e1,e2,…,ew}为边集合，网络节点数目为N=||V，边数为W=||E，网络邻接矩阵用A(G)=(aij)N×N表示.对有向有权网络，节点i到 j之间存在一条边，则aij=wij；否则，aij=0.一般情况下，wij≠wji，即有向加权网络的邻接矩阵一般不对称.

我们采用主方法构建路网拓扑[14]，即以现实道路网络的物理结构为基础，将道路的交叉口抽象为网络中的节点，交叉口之间的路段映射为节点间的连边，建立城市交通网络拓扑结构模型.由于道路分为单向和双向车道，因此根据车道类型构建有向复杂网络，方向代表车流方向，也表示了复杂网络中边的有向性.

1.2 网络边权的计算

在交通流理论中，交通流特性参数主要由流量、速度、密度这3个重要参数刻画，这3个参数是相互影响的，并已验证得出三者间的量化关系[15]：流量等于速度和密度的乘积.由此可知，如果通过相应的技术得到交通流速度，就可以根据相应的公式和一些与道路相关的固定参数计算出密度及流量信息.因此，本文将路段平均速度这一交通流基础参数作为构建的有向复杂网络的边的权重.

出租车GPS轨迹数据中包括车辆ID、经度、纬度、瞬时速度、记录时间、方向角及车辆状态信息.本文利用轨迹数据中所包含的速度信息进行计算，得到路段i的平均速度为

式中：mj表示第j辆出租车在i条路段上返回的轨迹数据的总次数；uijk表示第j辆出租车在i条路段上返回的第k个点的瞬时速度.

1.3 网络关键节点识别算法

DWNodeRank算法是文献[16]借鉴了著名的google排名算法PageRank算法提出的一种有向加权复杂网络的节点重要性排名算法.该算法既考虑了节点的局部连接属性，同时从整体上考虑了网络连接关系对节点重要性的影响.具体步骤如下.

Step 1根据构建的有向加权复杂网络写出其邻接矩阵A，A=(wij)n×n.

Step 2对邻接矩阵进行归一化处理，即将邻接矩阵A的每一行除以该行非零向量之和，得到归一化矩阵，该矩阵元素表示了一个节点到另一个节点的转移概率，定义为概率转移矩阵.如果网络中存在悬虚节点(网络中不存在指向其他节点边的节点称为悬虚节点)，则重新计算概率转移矩阵，其中η为布尔向量，如果该节点为悬虚节点，其值为1；否则，为0.

Step 3求概率转移矩阵的转置矩阵M=T.

Step 4计算DWNodeRank矩阵R，该矩阵，其中α为阻尼系数，α=0.85.该矩阵中值为1的特征值对应的特征向量是其平稳分布.

Step 5使用幂法迭代的思想求解DWNodeRank矩阵的平稳分布，然后将得到的结果排序后即为网络节点重要性的排序.

幂法迭代的具体实现步骤为：

(1)建立有向加权复杂网络邻接矩阵A，计算矩阵P,,M.

(2)根据DWNodeRank算法的Step4求出矩阵Rank.

(3)设Rank的初始迭代向量x=(x0,x1,…,xn)T，其中xi为节点vi的DWNodeRank初始值.

(4)迭代计算r=Rx.

(5)若‖‖x-r＜ε，迭代结束，返回r；否则，x=r，返回(4)，循环迭代.其中ε为迭代精度，一般设为10-8.

(6)迭代结束后得到的向量r就是DWNodeRank矩阵，将其结果按从大到小排序，即可得到网络节点重要性的排序，最终识别网络中的关键节点.

2 实验结果与分析

2.1 出租车GPS数据及其预处理

出租车GPS轨迹数据为兰州市2017年3月6～12日连续7天的3 000辆出租车数据，这7天当中5天是工作日，另外2天是休息日，正好可以反映工作日和休息日城市交通状况和居民出行特征，数据集具有一定代表性.原始数据是由出租车上的GPS装置定时向兰州市城市交通运输管理处的出租车调度监管信息中心发送数据，由中心系统数据处理后存入服务器的Oracle数据库中.GPS轨迹数据包括车辆ID、经度、纬度、瞬时速度、记录时间、车头朝向及车辆载客信息.轨迹点采样时间间隔为30 s，数据集大小约10.6 G.

在出租车GPS数据采集中不可避免的会产生偏差，比如终端设备故障、传输故障等，使得直接采集的GPS数据或多或少都是不完整的、不一致的，必须对原始GPS数据进行预处理.GPS数据预处理主要包括数据清理和路网拓扑匹配.数据清理就是通过处理GPS数据中的离群点、缺失值、冗余值等解决原始数据的不完整性和不一致性问题.由于GPS系统定位精度的问题，出租车GPS数据存在一定的误差，使得轨迹点往往并不完全在道路上，因此需要真实的城市路网地图数据对其进行匹配纠正.本文通过MNTG(Minnesota Traffic Generator)[17]获取兰州市城区路网拓扑信息，采用几何特性的方法[18]对租车轨迹数据进行路网拓扑匹配.具体流程如图1所示.图2为兰州市城区部分路网拓扑和1辆出租车部分GPS轨迹数据，其中黑色线表示路网，黑色点表示出租车轨迹点.

图1 GPS数据预处理流程Fig.1 GPS data processing flow chart

图2 部分路网拓扑和1辆出租车部分GPS轨迹数据Fig.2 Part of the road network topology and part of the GPS data for a taxi

2.2 城市交通状态分析

我国公安部于2002年公布了《城市交通管理评价指标体系》，以机动车行程平均速度为参数对城市道路交通拥堵进行量化定义[19]，具体级别如表1所示.

表1 我国城市道路交通拥堵评价标准当前工况Table 1 Evaluation criteria of urban road traffic congestion in China

由表1可知，平均速度小于20 km/h的路段为拥堵路段，定义全天24 h中速度小于20 km/h的路段占总路段的比例为拥堵路段比，用该参数衡量城市交通拥堵情况.图3为星期一和星期日全天24 h的拥堵路段比变化趋势.

图3 拥堵路段占比Fig.3 The proportion of congested roads

从图3中可看出星期一拥堵路段比的变化趋势：7:00-8:00和17:00-18:00为路段拥挤的高峰期；12:00下班时间和14:00上班时间有拥堵小高峰，但与7:00-8:00和17:00-18:00相比较，拥堵有所缓解，这主要是因为午休时间相对较短，部分离家远的人选择不回家；19:00以后，拥堵路段的占比逐渐下降.按理说在23:00-6:00这段时间应该很少有堵车路段，但是我们的统计结果显示拥堵路段比仍约12%，这是由于我们采用路段平均速度度量拥堵情况，而且在深夜和凌晨这个时间段内，由于路上光线不好，出租车司机驾驶非常小心，行驶速度相对较慢，故仍能统计到拥堵路段.

星期日与星期一拥堵路段比的变化趋势明显不同：星期一7:00的拥堵路段比为0.4，星期日仅为0.18，这说明在周末，一定比例的人还是选择早晨留在家里休息；星期日8:00-14:00拥堵路段比整体为上升趋势，这说明出门的人在不断增加，而且出门时间相对随意；19:00以后，拥堵路段逐渐下降.通过对工作日和休息日的GPS数据分析，我们发现图3路段拥堵的总体趋势与人们的日常生活规律基本一致.

路段平均速度反映了交通的拥堵状况，即平均速度越小，道路越拥堵.由于篇幅所限，我们只呈现了星期一7:00和23:00两个时间的可视化交通状态，如图4所示.两者对比发现，7:00拥堵路段明显较多，而且主要集中在西站什字、城关区.

2.3 城市路网关键节点识别

首先，以现实道路网络的物理结构为基础，建立路网络拓扑.然后，根据道路属性(单向或双向车道)构建有向网络，并以各个路段不同方向的车辆平均速度为有向网络的边的权重，最终将城市路网抽象为一个有向加权复杂网络.最后，根据DWNodeRank算法，对路网拓扑中的关键节点进行识别研究.

以小时为时间粒度，分析每个小时路网拓扑中的关键节点，研究结果表明随着时间的变化，交通状态和网络节点的排名都在变化，但网络节点排名变化较小，也就是说节点的重要性基本保持稳定状态.分析连续7天的数据也得出同样的结论.

我们提取每天每小时重要性排名前50的节点，共有50×24×7个节点，再按这些节点出现频数进行由高到低排序，最终得到排名前50的关键节点，如图5所示，其中西固区分布3个，安宁区分布8个，七里河区分布11个，其余28个全部分布在城关区.排名前10的关键节点对应的城区具体位置如表2所示，由此可见城关区交通流比较密集，而且容易拥堵.究其原因，一方面，城关区常住人口密度大；另一方面，城关区是行政区的中心地带，甘肃省和兰州市的政府职能部门、企业主管部门等均设立于此.

图4 可视化交通状态图(星期一)Fig.4 Visualize traffic status(Monday)

图5 排名前50的关键节点分布图Fig.5 Top 50 key nodes distribution

表2 排名前10关键节点对应的城区具体位置Table 2 Ranking the top 10 hub nodes corresponding to the city location

3 结 论

结合城市道路网络的拓扑结构特征和交通流特性，本文提出了基于有向加权复杂网络和DWNodeRank算法相结合的城市路网关键节点识别方法，并利用兰州市连续7天出租车GPS轨迹数据，以小时为时间粒度，对工作日和休息日中城市交通状态进行可视化时空分析.研究方法和结果将为交通管理部门规划、设计和管理提供科学的指导，对兰州市城市交通的持续健康发展具有重要意义.

本文利用连续7天的出租车GPS轨迹数据进行分析，该数据集并不能完全覆盖城市道路网络，且轨迹数据集种类比较单一，使得通过统计得到的路段平均速度存在一定误差.另外，虽然本文充分利用了出租车数据包含的速度信息，但只考虑了速度，因素较为单一.接下来我们将结合更多的机动车GPS数据，特别是城市公交车运营数据，挖掘GPS轨迹中的位置、状态和时间等信息，深入分析城市交通状态及其可视化呈现.

[1]高强,张凤荔,王瑞锦,等.轨迹大数据：数据处理关键技术研究综述[J].软件学报,2017,28(4)：959-993.[GAO Q,ZHANG F L,WANG R J,et al.Trajectory big data：A review of key technologies in data processing[J].Journal of Software,2017,28(4)：959-993.]

[2]赵竹珺,吉根林.时空轨迹分类研究进展[J].地球信息科学学报,2017,19(3)：289-297.[ZHAO Z J,JI G L.Research progress of spatial-temporal trajectory classification[J].Journal of Geo-information Science,2017,19(3)：289-297.]

[3]HAO J,ZHU J,ZHONG R.The rise of big data on urban studies and planning practices in China：Review and open research issues[J].Journal of Urban Management,2015(4)：92-124.

[4]ZHOU Z,DOU W,JIA G,et al.A method for real-time trajectory monitoring to improve taxi service using GPS big data[J].Information&Management,2016(53)：964-977.

[5]ZHENG W,HUANG X,LI Y.Understanding the tourist mobility using GPS：Where is the nextplace?[J].Tourism Management,2017(59)：267-280.

[6]郑宇.城市计算概述[J].武汉大学学报(信息科学版),2015,40(1)：1-13.[ZHENG Y.Overview of urban computing[J].Geomatics and Information Science of Wuhan University,2015,40(1)：1-13.]

[7]牟乃夏,张恒才,陈洁,等.轨迹数据挖掘城市应用研究综述[J].地球信息科学,2015,17(10)：1136-1142.[MOU N X,ZHANG H C,CHEN J,et al.A survey of urban application research on track data mining[J].JournalofGeo-information Science,2015,17(10)：1136-1142.]

[8]CASTRO P S,ZHANG D,LI S.Urban traffic modelling and prediction using large scale taxi GPS traces[M].Pervasive Computing,Springer Berlin Heidelberg,2012.

[9]ZHAN X,HASAN S,UKKUSUR S V,et al.Urban link travel time estimation using large-scale taxi data with partial information[J].Transportation Research Part C：Emerging Technologies,2013,33(2013)：37-49.

[10]齐观德,潘遥,李石坚,等.基于出租车轨迹数据挖掘的乘客候车时间预测[J],软件学报,Journal of Software,2013,24(Sup2)：14-23.[QI D G,PAN Y,LI S J,et al.Predicting passengers’waiting time by mining taxi traces[J].Journal of Software,2013,24(Sup2)：14-23.]

[11]FUSCO G,COLOMBARONI C,ISAENKO N.Shortterm speed predictions exploiting big data on large urban road networks[J].Transportation Research Part C,2016,2016(73)：183-201.

[12]CUI J,LIU F,HU J,et al.Identifying mismatch between urban travel demand and transport network services using GPS data：A case study in the fast growing Chinese city of Harbin[J].Neurocomputing,2016,2016(181)：4-18.

[13]杨伟,艾廷华.基于车辆轨迹大数据的道路网更新方法研究[J].计算机研究与发展，2016,53(12)：2681-2693.[YANG W,AI T H.A method for road network updating based on vehicle trajectory big data[J].Journal of Computer Research and Development,2016,53(12)：2681-2693.]

[14]胡一竑,吴勤旻,朱道立.城市道路网络的拓扑性质和脆弱性分析[J].复杂系统与复杂性科学,2009,6(3)：69-76.[HU Y H,WU Q M,ZHU D L.Topological properties and vulnerability analysis of spatial urban street networks[J].Journal of Computer Research and Development,2009,6(3)：69-76.]

[15]NIK HASHIM NIK MUSTAPHA,NIK NUR WAHIDAH NIK HASHIM.Outflow of traffic from the national capital Kuala Lumpur to the north,south and east coast highways using flow,speed and density relationships[J].Journal of Traffic and Transportation Engineering,2016,6(3)：540-548.

[16]张琨,李配配,朱保平,等.基于PageRank的有向加权复杂网络节点重要性评估方法[J].南京航空航天大学学 报,2013,45(3)：429-434.[ZHANG K,LI P P,ZHU B P,etal.Evaluation method fornode importancein directed-weighted complexnetworks based on pagerank[J].Journal of Nanjing University of Aeronautics&Astronautics,2013,45(3)：429-434.]

[17]MOKBEL M F,et al.MNTG：An extensible web-based traffic generator[M].In：Nascimento M A,et al.(eds),Advances in Spatial and Temporal Databases,SSTD 2013.Lecture Notes in Computer Science,vol 8098.Springer,Berlin,Heidelberg,2013.

[18]马云飞.基于出租车轨迹点的居民出行热点区域与时空特征研究：以昆山市为例[D].南京：南京师范大学，2014.[MA Y F.Research on residents behavior of attractive areas and spatial-temporal feature based on taxi trajectory data：A case of kunshan city[D].Nanjing Normal University,2014.]

[19]中华人民共和国公共安全行业标准.城市道路交通管理评价指标体系[S].中华人民共和国公共安全行业标准,2002.[People's Republic of China Public Safety Industry Standard.Evaluation index system of urban road traffic management[S].People's Republic of China Public Safety Industry Standard,2002.]