移動軌跡挖掘算法設計與系統實現

高瑞+周彩蘭+朱榮

摘 要： 為了提高有效地識別不同交通方式的精確度，根據采取的交通方式GPS定位軌跡特征，構建一套適用于識別不同交通方式的精確度預測優化算法模型，研究內容包括軌跡轉換點分段、移動軌跡轉預測計算、結果精度分析三個部分。采用對交通堵塞及多種交通方式的情況提出轉換點分段方法的算法，挖掘用戶的移動行為，將GPS原始軌跡劃分成為交通方式單一的子軌跡段，有效地識別不同交通方式，達到的效果較為理想。實驗結果表明，統一時間的分段方法與轉換點的識別方法相比，統一時間分段方法的整體精確度要低于轉換點識別方法，高級特征的精確度均高于基本特征的精確度。

關鍵詞： 移動軌跡； 挖掘算法； 交通堵塞； GPS定位

中圖分類號： TN967.1?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2017）01?0134?03

Abstract： In order to improve the identification accuracy of different transportation modes， an accuracy forecasting optimization algorithm model suitable for the identification of different transportation modes was constructed according to the traffic mode to locate the GPS trace features. The segmentation of track transition point， moving track prediction and calculation， and result accuracy analysis are studied. The algorithm of using the transition point segmentation method to deal with the traffic jam and various transportation modes is adopted to mine the user movement behavior， and divide the GPS original trajectory into the sub?trajectory with single transportation mode， which can identify different transportation modes effectively， and achieve the satisfied effect. The experimental results show that the overall accuracy of the transition point identification method is higher than that of the unified time segmentation method， and the accuracy of the advanced feature is higher than that of the basic feature.

Keywords： mobile trajectory； mining algorithm； traffic jam； GPS location

0 引 言

隨著GPS定位技術、無線通信技術和電子技術的發展，使得人們可以對移動對象如乘坐不同交通方式、車輛等進行跟蹤定位，與移動對象管理密切相關的是移動對象的跟蹤、定位、記錄、查詢等，用戶移動模式的有效支持才能使這些功能有效的實現。挖掘用戶的移動模式可以為移動對象管理服務，還可以在交通管理、安全和旅游等基于位置的服務中具有非常廣泛的應用前景。

在定位技術中，GPS定位是精度最高的定位技術之一，目前GPS定位研究最多的是通過內置客戶端獲得用戶的連續軌跡。本文通過轉換點分段方法的算法，對交通堵塞及多種交通方式，將GPS原始軌跡劃分成為交通方式單一的子軌跡段，有效地識別不同交通方式，達到的效果較為理想。

1 相關定義

為了方便討論，首先引進如下符號說明，移動對象的移動產生一個連續的運動軌跡，該運動軌跡可以由位置、時間描述。表示軌跡，表示數據點，表示緯度，表示經度，表示時間。在軌跡的邊上標記一個連續的自然數列，移動對象的軌跡可描述為：

GPS軌跡定義：GPS軌跡是由一系列隨著時間變化，軌跡位置也在空間上發生變化的許多數據點形成的，采用經緯度的形式表示位置信息。由于對象的移動行為往往是一個周而復始的過程，所以上述軌跡是一個有向標記圖，每個連續的運動軌跡對應一個有向標記圖。

轉換點定義：轉換點是指子軌跡之間的某一特定范圍內停留時間在速度保持較低狀態下超過某一閾值的數據點。

子軌跡定義：子軌跡是指經過轉換點分段之后的一段軌跡，由許多數據點形成，并且這些數據點是連續的、相對的和緊密的，且每段子軌跡代表一種交通方式，不同的子軌跡中相鄰數據點間的間隔是不同的。如軌跡子軌跡其中

2 轉換點的軌跡

2.1 轉換點的描述

通常情況下，人們在轉換交通方式前一個時間段一般保持著較低速度在運動，利用轉換點將GPS的軌跡進行不同交通方式的分段，每一段交通方式稱為子軌跡，每一段子軌跡都只允許有一種交通工具。如圖1所示，用戶軌跡由12個數據點構成，點為轉換點，轉化點將軌跡分為三段子軌跡。

2.2 正常情況下的轉換點

由于交通堵塞或間斷性停車使得轉換點的識別出現兩種情況，即交通堵塞或交通正常。正常是指未發生交通堵塞情況，只有在換乘另一種交通工具時，人才發生停頓。速度小于某一閾值的點要通過GPS軌跡中每個數據點的速度才能計算出，如圖2所示。

2.3 低速點的出現

多個低速點會出現在交通堵塞導致不間斷的停頓的狀況中，這些低速點把交通方式相同的子軌跡段劃分為更小的子軌跡。人在坐公交車和步行的過程中，必然會出現多個低速度點，如點一種交通方式下的子軌跡被它們又分成了好幾段的子軌跡，如具體見圖3。

3 移動軌跡轉換算法

算法1描述了如何識別轉換點的具體步驟，其中分別表示子軌跡段的長度、時間和平均速度。

4 算法分析

本文從三個方面對算法進行分析，第一是對每段的子軌跡抽取與速度相關的基本特征，并抽取與速度無關的高級特征，然后進行訓練；第二是當處理一段GPS原始軌跡時，先計算軌跡中每一個點的速度，然后抽取對應的每一個子軌跡段上的基本特征，并抽取對應的每一個子軌跡段上的高級特征，推斷模型的輸入數據就是這些特征；第三是對每一個子軌跡段的交通方式進行識別，識別的根據由推斷模型的這些特征確定。

5 實驗結果與分析

為了驗證轉換點分段交通識別方法，記錄40個被測試人員在160天的上班路線，每個試驗者都攜帶一個帶有GPS功能的設備記錄自己的位置信息，以隨機抽樣的方法從每個試驗者的GPS軌跡中選擇一部分數據作為訓練集，其余作為測試集，對方法進行驗證。為了比較轉換點和統一時間兩種不同的分段方法，分別選擇相同的幾組數據集進行反復實驗。

圖4為三組不同數據點轉換點的分段方法曲線圖，從圖4可以看出，三組數據點在轉換點的分段方法曲線圖上的速度均為2.2 m/s時，分段精確度達到最高，三組數據點250，1 540，3 520對應的分段精確度分別為87%，86%，90%。

圖5為三組不同數據點統一時間的分段方法曲線圖，由圖5可以看出，統一時間的識別方法三組數據點均在時間為155 s時達到最高的分段精確度，三組數據點250，1 540，3 520對應的分段精確度分別為30%，38%，51%，三組數據點整體精確度較小，均低于60%，效果較差。與轉換點的識別方法相比，轉換點的識別方法的整體精確度要高于統一時間的分段方法。

6 精確度比較

本試驗分別隨機抽取了所有數據中的6組數據，為了確保試驗的準確性，對抽取的每組數據特征進行多次的反復實驗，比較不同特征在識別交通方式時精確度的差別。

基本特征與高級特征精確度比較如圖6所示，從圖6可以看出，6組數據高級特征精確度均高于基本特征的精確度，其中第一組數據與第六組數據基本特征與高級特征精確度差距較小；第二組數據與第五組數據基本特征與高級特征精確度差距較大，由于基本特征受速度影響，導致識別精確度不理想。在實際應用中，利用高級特征進行識別比利用基本特征識別精確度更高，更接近實際。

7 結 論

本文對交通堵塞及多種交通方式的情況提出轉換點分段方法的算法，將GPS原始軌跡劃分成為交通方式單一的子軌跡段，有效地識別不同交通方式，達到的效果較為理想。對比轉換點的識別方法與統一時間的分段方法，前者的整體精確度要高于后者，高級特征精確度均高于基本特征的精確度。

參考文獻

[1] 熊妍，羅澤，閻保平.GPS位置歷史挖掘和移動軌跡異常檢測系統的設計與實現[J].計算機應用研究，2013，30（9）：2704?2707.

[2] 彭茗菁，馬傳香，李偉亮.基于MAP/REDUCE的移動目標連續軌跡模式挖掘的研究[J].物聯網技術，2014，4（10）：59?61.

[3] 劉雨露，方剛.基于二進制的挖掘算法在移動計算中的應用[J].計算機工程與設計，2009，30（14）：3319?3322.

[4] 吳信才，劉少雄.基于鄰接關系的空間數據挖掘[J].計算機工程，2002，28（7）：89?91.

[5] 李國徽，程遠國.傳感器網絡中頻繁移動模式挖掘算法研究[J].小型微型計算機系統，2008，29（6）：1015?1020.

[6] 賀然，張鋼，劉春鳳，等.車載網絡中基于移動軌跡預測的快速鄰居發現算法[J].計算機應用研究，2015，32（9）：2737?2742.

[7] 趙德偉，高江錦，徐正巧.基于K?means算法的Web日志挖掘在移動學習中的實現[J].電腦編程技巧與維護，2012（16）：92?94.