高瑞+周彩蘭+朱榮

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

關(guān)鍵詞： 移動(dòng)軌跡； 挖掘算法； 交通堵塞； GPS定位

中圖分類號(hào)： TN967.1?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ā)展，使得人們可以對(duì)移動(dòng)對(duì)象如乘坐不同交通方式、車輛等進(jìn)行跟蹤定位，與移動(dòng)對(duì)象管理密切相關(guān)的是移動(dòng)對(duì)象的跟蹤、定位、記錄、查詢等，用戶移動(dòng)模式的有效支持才能使這些功能有效的實(shí)現(xiàn)。挖掘用戶的移動(dòng)模式可以為移動(dòng)對(duì)象管理服務(wù)，還可以在交通管理、安全和旅游等基于位置的服務(wù)中具有非常廣泛的應(yīng)用前景。

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

1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算法分析

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

5 實(shí)驗(yàn)結(jié)果與分析

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

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

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

6 精確度比較

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

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

7 結(jié) 論

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

參考文獻(xiàn)

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

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

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

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

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

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

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