利用出租車軌跡數據挖掘城市居民出行特征

張 俊 濤，武 芳，張 浩

（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 冗余數據化簡

軌跡數據在采集過程中由于交通擁堵、車輛?？恳约熬徛苿拥那闆r下定位系統會產生大量的定位冗余點，故需對其化簡以便使用。軌跡數據的化簡問題，實質上就是線的化簡問題，此問題在計算機圖形學以及制圖學領域已有廣泛而深入的研究，其中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.