移動軌跡挖掘算法設(shè)計與系統(tǒng)實現(xiàn)

高瑞+周彩蘭+朱榮

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

關(guān)鍵詞： 移動軌跡； 挖掘算法； 交通堵塞； 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定位技術(shù)、無線通信技術(shù)和電子技術(shù)的發(fā)展，使得人們可以對移動對象如乘坐不同交通方式、車輛等進行跟蹤定位，與移動對象管理密切相關(guān)的是移動對象的跟蹤、定位、記錄、查詢等，用戶移動模式的有效支持才能使這些功能有效的實現(xiàn)。挖掘用戶的移動模式可以為移動對象管理服務(wù)，還可以在交通管理、安全和旅游等基于位置的服務(wù)中具有非常廣泛的應(yīng)用前景。

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

1 相關(guān)定義

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

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

轉(zhuǎn)換點定義：轉(zhuǎn)換點是指子軌跡之間的某一特定范圍內(nèi)停留時間在速度保持較低狀態(tài)下超過某一閾值的數(shù)據(jù)點。

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

2 轉(zhuǎn)換點的軌跡

2.1 轉(zhuǎn)換點的描述

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

2.2 正常情況下的轉(zhuǎn)換點

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

2.3 低速點的出現(xiàn)

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

3 移動軌跡轉(zhuǎn)換算法

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

4 算法分析

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

5 實驗結(jié)果與分析

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

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

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

6 精確度比較

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

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

7 結(jié) 論

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

參考文獻

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

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

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

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

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

[6] 賀然，張鋼，劉春鳳，等.車載網(wǎng)絡(luò)中基于移動軌跡預(yù)測的快速鄰居發(fā)現(xiàn)算法[J].計算機應(yīng)用研究，2015，32（9）：2737?2742.

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