利用出租车轨迹数据挖掘城市居民出行特征

张 俊 涛，武 芳，张 浩

（1.信息工程大学，河南 郑州 450002；2.西安测绘信息技术总站，陕西 西安 710054）

0 引言

近年来，移动定位技术在车载移动终端、移动设备上得到广泛使用，使得大量群体轨迹数据的获取在技术上及经济上可行性越来越高，大量的轨迹数据在日常生活中日益积累并为不同类型的应用服务，通过对这些轨迹数据的挖掘、分析，将有益于城市规划、城市交通管理以及智能的基于位置的服务。

关于轨迹数据挖掘、分析的研究，从研究对象的数量特征看，分为个体行为特点［1－3］以及群体行为特点［4，5］的研究。由于出租车轨迹数据主要是通过不同出租车（车辆ID）对产生轨迹数据的个体进行区分，而对于实际上某段轨迹真实所属的个人则难以区分，故利用出租车轨迹数据挖掘、分析城市居民出行行为特点实质上是一种利用轨迹数据进行群体行为特点的研究。当前此类型研究主要通过定义一系列适用于不同应用场景的距离度量指标［6－9］，依赖于数据挖掘中聚类的方法及其衍生方法进行，其中典型的方法有：针对轨迹点直接进行基于密度聚类［10，11］；将轨迹点转换为化简的线段序列，通过对线段的聚类以发现热点路径［12，13］；将轨迹转换为某类型的格网序列，在格网上聚类以发现热点区域［14，15］。这些类型的方法存在一个问题，即未能考虑轨迹的方向和数量特征对结果可能产生的影响，因为轨迹在某种程度上代表的是具有数量特征的一种流向（人流、物流等）。

受电动力学中高斯定律的启发，本文将出租车轨迹的方向和数量特征考虑在内，提出一种基于高斯定律思想的出租车轨迹挖掘、分析方法，以南京出租车轨迹数据为基础，通过对不同时段数据的挖掘分析，得到城市不同区域、不同时段乘客（居民）净流入量情况的时空分布，发现城市居民的出行行为时空特征。

1 数据预处理

从现实世界直接采集的数据或多或少都是不完整的、不一致的，并不能直接用于数据分析、挖掘，出租车轨迹数据也不例外。基于研究需要，本文从数据清理、冗余数据化简以及地图匹配三方面对原始出租车轨迹数据进行预处理。

1.1 数据清理

数据清理过程通过处理数据中的缺失值、光滑噪声数据、识别和删除离群点来解决原始数据中存在的不完整性和不一致性问题。出租车轨迹数据存在的主要问题是轨迹点经纬度坐标越界以及轨迹点位置异常，需要对其进行处理。1）经纬度数据越界处理。本文以南京市辖区为研究对象，重点研究区域为南京绕城高速以内区域（主城区），放宽到整个南京市辖区范围，不在此地理坐标范围内的记录应予以去除。2）异常值过滤。直观的，出租车的行车速度应在一定的合理范围内［16］，此外，车载GPS设备由于测量误差会产生一些异常值，本文采用文献［16］的方法配合中位数滤波器进行异常值过滤［17］。

1.2 冗余数据化简

轨迹数据在采集过程中由于交通拥堵、车辆停靠以及缓慢移动的情况下定位系统会产生大量的定位冗余点，故需对其化简以便使用。轨迹数据的化简问题，实质上就是线的化简问题，此问题在计算机图形学以及制图学领域已有广泛而深入的研究，其中Douglas-Peucker（DP）算法［18］以其模型简单、计算快捷而被广泛应用，在曲线节点密度较高时，具有良好的去除冗余的结果，而轨迹数据正好满足这一点，本文采用其进行出租车轨迹数据的冗余数据化简。

1.3 地图匹配

由于GPS定位精度的问题，轨迹点存在一定的误差，使得轨迹点往往并不在道路上，因此需要使用已有的地图数据对其进行匹配纠正。简单便捷的匹配方法是将GPS轨迹点匹配到距离它最近的道路上［19，20］，这是一类利用几何特性的方法。文献［21］利用几何特性并考虑道路拓扑关系进行轨迹匹配，其模型简单，计算便捷，准确度高，本文用其进行出租车轨迹数据的地图匹配。

预处理前后的轨迹（线）数据如图1所示，预处理前的数据中由于存在大量不完整、不一致的脏数据，以至于几乎将正常的轨迹数据完全“淹没”，而经过预处理后的数据，清楚地“勾勒”出城市道路网。

2 基本原理与方法

利用出租车轨迹数据挖掘城市居民出行的时空特征时，将出租车轨迹的方向和载客的数量特征考虑在内，类比电动力学中高斯定律所描述的场景，本文提出一种基于高斯定律思想的出租车轨迹挖掘、分析方法。

2.1 高斯定律

在电动力学中，高斯定律（Gauss′law）表明在闭合曲面内的电荷之和与产生的电场在该闭合曲面上的电通量积分之间的关系［22］。式（1）［23］为高斯定律的数学表达式，公式中V为封闭曲面Ω围成的空间，ε0为介电常数，qi为V中包含的电荷，E为空间中电场分布的矢量函数。式（1）表明闭合曲面Ω中所包含的电荷之和与该曲面上的电通量的积分呈正比。电场线有起点和终点，只要闭合面内有净余的正（或负）电荷，穿过闭合面的电通量就不等于零，即

2.2 高斯定律与轨迹数据

直观地理解高斯定律，即式（1）中封闭曲面Ω内所包含的电荷之和与穿过该封闭曲面的电场线（有向，终点与起点分别在曲面Ω的两侧）呈正比。按电动力学中的知识，一条电场线起源于正电荷而终结于负电荷。类比出租车轨迹数据，一个载客段对应高斯定律中一条电场线，其中该载客段的起点对应于高斯定律中一个正电荷，而终点对应于高斯定律中的一个负电荷；高斯定律中穿过封闭曲面Ω的电场线与该封闭曲面包含的电荷之和呈正比，对应出租车轨迹数据，在假设所有出租车平均载客量大致稳定为1／λ0的条件下，穿过指定区域的轨迹（有向，终点与起点分别在该区域两侧）正比于该区域包含的起点与终点之和（为便于直观地比较，起点定义为－1，终点定义为＋1），只不过出租车轨迹对应的是一个二维场景；理论上在高斯定律中选择的封闭曲面Ω的空间尺度（以最大直径表示）d（Ω）→0＋时，表示了空间中电荷密度的分布，当选择不同空间尺度的封闭曲面Ω时，则代表当前尺度下电荷量在空间中的分布，对应于出租车轨迹数据，当选择不同尺度的区域时，起点与终点之和则代表了不同尺度下出租车载客的净流入量密度的空间分布，表达式如下：静电场是有源场。特别值得强调的是，式（1）中左端为第二类曲面积分，即还要考虑空间中电场的分布的矢量函数的方向特征。

式中：Ti表示起始于平面上封闭区域Ω外而终止于Ω内的载客段或起始于Ω内而终止于Ω外的载客段。若终止于封闭区域内，δ（Ti）的值为＋1，否则为－1。1／λ0为出租车平均载客量，并假定一定时段内其为相对稳定的常数。

2.3 基于高斯定律思想的轨迹挖掘

通过前述高斯定律中电场线与出租车轨迹数据以及正负电荷与出租车载客段的起始点和终点的类比，可以发现它们间具有高度的相似特征，高斯定律中通过在封闭曲面Ω上对电场进行第二类曲面积分得到该封闭曲面包含的电荷量，对于出租车轨迹数据，通过统计穿过平面上一定区域边线的出租载客段的轨迹，得到该区域一定时段出租车载客的净流入量，这个净流入量综合考虑了出租车轨迹数据的方向与数量特征，在一定程度上可以反映出城市内不同区域对居民出行的“吸引力”大小。

在统计穿过平面上一定区域边界的出租载客段的轨迹时，计算轨迹是否穿越区域边界较为复杂与耗时，而直接统计区域内的载客段起点与终点数较简单，鉴于此，本文的出租车轨迹挖掘算法设计如下：1）对获取的出租车轨迹数据进行预处理，然后依据出租车载客状态的切换（载客到空车、空车到载客），将轨迹数据按空车状态和载客状态进行分割，提取载客段的起点和终点，并添加类型为Int的discrimination属性字段，对于起点其值为－1，终点为＋ 1；2）对预处理后的有效出租车轨迹数据覆盖的区域进行分割，设定分割的尺寸a（本文以栅格进行分割）；3）对分割后平面上的各个分割单元，统计落入其中的载客段的起点与终点，该单元的统计值为count终点－count起点；4）根据各单元的统计值乘以出租车平均载客数量1／λ0即可得到某个时段的乘客净流入量（λ0可以通过调查统计的方式获得）。

需要说明的是，城市内不同区域对居民出行的“吸引力”大小数值在空间上的分布应该具有连续性，然而出租车轨迹数据的轨迹点通常都是沿城市道路分布，是离散的，因此再添加一个扩展搜索半径r，统计落入各个单元及其外扩r后的范围内的起点与终点数，从而使结果更加平滑和连续。

经过前面的计算，得到的是一幅出租车乘客净流入量在空间分布的栅格数据图，此时通过栅格数据可视化的方法，再叠加矢量地图或遥感影像图，可直观地发现出租车乘客净流入量情况在空间的分布情况。为了更加准确发掘某个时段城市居民搭乘出租车的出行情况，此时可以借助栅格数据空间分析的手段进行处理，再用可视化的方法予以可视化显示。具体借用三维地形分析中山顶点的提取方法，并予以适用性改造，其流程如图2所示。

以提取局部出租车乘客净流入量（正）峰值点为例，记栅格数据为［raster＿data］，处理栅格数据某个操作记为operation（），具体的计算过程为：1）邻域统计／栅格计算。通过r×r大小的窗口统计和栅格计算得到乘客净流入量的局部极大值栅格：［n＿max＿1］＝boolean（（neighbor＿maxr×r（［passagers＿income］）－［passagers＿income］）＝0）×［passagers＿income］。2）负值过滤。通过邻域统计得到乘客净流入量栅格［n＿max＿1］可能会包含负值（净流出）区域的极大值，这是提取局部出租车乘客净流入量（正）峰值点所不需要的，需对其进行过滤：［n＿max＿2］＝boolean（［n＿max＿1］＞0）×［passagers＿income］。3）栅格转矢量。将乘客净流入量局部极大值栅格［n＿max＿2］转为矢量点，具体先将其转为矢量面要素，再提取其中心点，点的属性值为净流入量局部极大值：center（raster2polygon（［n＿max＿2］））。

峰值点只代表了该点是出租车乘客净流入量局部的峰值所在位置，其属性值为该点的峰值，理论上并不能表示峰值点邻近区域的净流入量情况。但假设出租车乘客净流入量在空间上是平稳变化，不出现属性值急剧变化的区域，此时峰值点的属性值在一定程度上就能近似表示峰值点邻近区域的净流入量情况。以地形作为类比，在地形变化比较平稳的前提下（无断崖等），以同一个高程作为基准面，通常山顶高程越高的山体具有更大的体积，与此类似，在出租车乘客净流入量在空间上平稳变化的前提下，以同一个“高程”作为基准面（0），峰值点属性值越高的邻近区域的乘客净流入量越大。

3 实验与分析

以2010年9月1－2日南京市出租车轨迹数据为实验对象，首先对经过预处理的数据进行整体统计分析，然后应用本文基于高斯定律思想的出租车轨迹挖掘方法进行不同时段的轨迹数据挖掘。

3.1 数据总体分析

以10 min为间隔统计各时段出租车载客次数（图3），可以看出，从早上5：00时开始出租车载客次数迅速增加，直至稳定；中午12：00－14：00时出现了一个微小的低谷；到16：00－19：00时又出现了一个明显的低谷，这基本符合人们的正常出行行为特点。

图3 各时段载客次数统计Fig.3 The period passengers statistics

3.2 轨迹挖掘实验

对经过预处理后的2010年9月1－2日的轨迹数据，以100 m为栅格划分尺度，500 m为扩展搜索半径，分时段应用本文所述的方法，具体的时段划分为每天5：00－10：30和16：30－22：00两个时段，每个时段5 h 30 min，结果如图4a－4d所示。在9月2日输出结果的基础上，实验进一步借用地形分析中山顶点提取的方法对图中的乘客净流入量、净流出量峰值点进行提取（图4c、图4d），同时计算乘客净流出、净流入量在空间的分布情况（图4e、图4f）。

3.3 实验分析

城市热点区域（路段）是指城市中具有极强的商业、娱乐、就业岗位集聚效应和便利的基础设施的区域（路段）。通过观察两个5：00－10：30时段的实验结果，发现图中心均出现了一个明显的高值区域，表明这个区域在这一时段的人流净流量比较高，属于净流入区，这个区域正是南京的鼓楼－新街口－夫子庙一带及其邻近区域，该区域也正是南京的中央商务区（CBD）；紧接着外围出现了一圈明显的低值区域，表明这个区域的人流净流量比较低，属于净流出区，对比遥感影像及电子地图，可以发现这个区域的居民区分布较为密集，属于城市功能区划分中的居民区；再往外围，出现了两个比较明显的高值区域以及若干相对高值的区域，一个是南京火车站商圈及邻近区域，另一个是明故宫－钟山风景区一带区域。观察两个16：30－22：00时段的实验结果，发现其与两个5：00－10：30时段的实验结果中的高值与地址区域分布在空间位置上基本相反，这个结果基本符合人们早上（上午）外出工作，晚上（下午）回家休息的通勤特征。进一步分析发现，实验揭示的南京市居民的通勤时空特征也基本符合Alain对城市结构与通勤模式布局关系的剖析［24］：在典型的单中心通勤模式中，其中心具有极强的就业岗位集聚效应和便利的基础设施及商业设施，通勤流格局是沿放射线走廊由外围向中心聚集；在理想化多中心格局下，城市出现多个“自给自足”的外围中心，这些中心对周边具有均衡的吸引力就业与人口接近，但这种模式仅存在于城市规划者的设想中；还有一种多中心模式，不存在主次中心之分，就业岗位与基础设施均等分布，此时通勤流呈自由随机的格局；而现实的城市结构中，往往形成了单一中心－多个次中心的组合式空间结构，通勤流呈放射状与随机兼顾的格局。

4 结语

本文在出租车轨迹数据挖掘的过程中，特别考虑了出租车轨迹的有向性以及人流的净流量，提出了基于高斯定律思想的轨迹挖掘方法，相比单纯地通过空间聚类及单纯地通过出租车乘客下车空间位置的分析，该方法能较好地通过对出租车轨迹数据的分析，发现不同时段、不同尺度下出租车载客的净流入量密度的空间分布，从而进一步发现城市居民的热点区域及出行行为的时空特征。通过验证，此方法具有良好的效果。需要指出的是，受限于实验数据来源，本文实验仅使用出租车轨迹来分析城市热点区域与居民通勤的时空模式还具有一定的局限性，如果能综合使用各种导航定位终端产生的用户历史轨迹数据和出租车轨迹数据，尤其考虑到当前具备导航定位功能的智能手机普及率之高，应当会得出更精确和全面的结果，值得进一步研究。

［1］ HADJIELEFTHERIOU M，KOLLIOS G.Complex spatio-temporal pattern queries［A］.International Conference on Very Large Data Bases，2005.877－888.

［2］ ZHOU X，SHEN H T，LIU Q，et al.A hybrid prediction model for moving objects［A］.IEEE International Conference on Data Engineering［C］.2008.70－79.

［3］ SAKR M A，G TING R H.Spatiotemporal pattern queries［J］.Geoinformatica，2011，15（3）：497－540.

［4］ GUDMUNDSSON J，KREVELD M V，SPECKMANN B.Efficient detection of motion patterns in spatio-temporal data sets［A］.Proceedings of International Symposium of Acm Geographic Information Systems［C］.2004.250－257.

［5］ JEUNG H，SHEN H T，ZHOU X.Convoy queries in spatiotemporal databases［A］.IEEE 24th International Conference On Data Engineering［C］.2008.1457－1459.

［6］ CHEN L，TAMER ？ZSU M，ORIA V.Robust and fast simi

larity search for moving object trajectories［A］.Proc.acm Sig

mod Int.conf.on Management of Data［C］.2005.491－502.［7］ YI B，JAGADISH H V，FALOUTSOS C.Efficient retrieval of similar time sequences under time warping［A］.International Conference on Data Engineering［C］.IEEE Computer Society，1998.201.

［8］ VLACHOS M，KOLLIOS G，GUNOPULOS D.Discovering similar multidimensional trajectories［A］.Data Engineering，2002［C］.Proceedings 18th International Conference on IEEE，2002.673－684.

［9］ JEUNG H，YIU M L，ZHOU X，et al.Discovery of convoys in trajectory databases［J］.Proceedings of the Vldb Endowment，2008，1（1）：1068－1080.

［10］ YUE Y，ZHUANG Y，LI Q，et al.Mining time-dependent attractive areas and movement patterns from taxi trajectory data［A］.Geoinformatics，2009［C］.17th International Conference on IEEE，2009.1－6.

［11］ ESTER M，KRIEGEL H，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise［A］.Int Conference on Knowledge Discovery ＆Data Mining［C］.1996.226－231.

［12］ LI Z，DING B，HAN J，et al.Swarm：Mining relaxed temporal moving object clusters［J］.Submission，2010，3（12）：723－734.

［13］ LAWSON C T，RAVI S S，HWANG J H.Compression and Mining of GPS Trace Data：New Techniques and Applications［R］.Technical Report.Region II University Transportation Research Center，2011.

［14］ PANG L X，CHAWLA S，LIU W，et al.On mining anomalous patterns in road traffic streams［A］.Advanced Data Mining and Applications［M］.Springer Berlin Heidelberg，2011.237－251.

［15］ SAVAGE N S，NISHIMURA S，CHAVEZ N E，et al.Frequent trajectory mining on GPS data［A］.Proceedings of the 3rd International Workshop on Location and the Web［C］.ACM，2010.3.

［16］ 何雯，李德毅，安利峰，等.基于GPS轨迹的规律路径挖掘算法［J］.吉林大学学报（工学版），2014，44（6）：1764－1770.

［17］ LEE W C，KRUMM J.Trajectory preprocessing［A］.Computing with Spatial Trajectories［C］.Springer New York，2011.21－23.

［18］ DOUGLAS D H，PEUCKER T K.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature［J］.Cartographica：The International Journal for Geographic Information and Geovisualization，1973，10（2）：112－122.

［19］ KORNHAUSER A.An introduction to map matching for personal navigation assistants［J］.Geometric Distributions，1996.

［20］ QUDDUS M A，OCHIENG W Y，NOLAND R B.Current map-matching algorithms for transport applications：State-ofthe art and future research directions［J］.Transportation Research Part C：Emerging Technologies，2007，15（5）：312－328.

［21］ 马云飞.基于出租车轨迹点的居民出行热点区域与时空特征研究［D］.南京：南京师范大学，2014.

［22］ 郭硕鸿.电动力学（第三版）［M］.北京：高等教育出版社，2010.3－8.

［23］ Gauss′s law.http：／／en.wikipedia.org／wiki／Gauss%27s＿law，2015－01－31.

［24］ BERTAUD A.The Spatial Organization of Cities：Deliberate Outcome or Unforeseen Consequence［R］.University of California（UC），2004.