賈瑛

摘要：異常軌跡檢測算法通常不能依靠軌跡內(nèi)外部屬性而有效地進(jìn)行檢測，具有較大的應(yīng)用局限性。針對(duì)此類問題，基于BP神經(jīng)網(wǎng)絡(luò)提出了一種改進(jìn)的異常軌跡檢測方法。首先對(duì)原始軌跡數(shù)據(jù)去噪，并上傳百度云LBS云端儲(chǔ)存;其次基于百度地圖軌跡數(shù)據(jù)可視網(wǎng)站進(jìn)行了數(shù)據(jù)歸一化處理，得到了軌跡的屬性值;最后以軌跡內(nèi)外特征屬性代表BP神經(jīng)網(wǎng)絡(luò)算法的輸入層，以軌跡相似度度量代表輸出層，對(duì)隱含層系數(shù)調(diào)整后獲得訓(xùn)練模型。研究針對(duì)Deolfe項(xiàng)目的兩個(gè)用戶軌跡數(shù)據(jù)做了仿真實(shí)驗(yàn)，用以檢測用戶異常軌跡數(shù)據(jù)。結(jié)果證明，在選取的最優(yōu)訓(xùn)練方案基礎(chǔ)上，兩組數(shù)據(jù)的異常軌跡檢測正確率各達(dá)92.3%及100%，所搭建模型能夠作為異常軌跡檢測的工具。

關(guān)鍵詞：軌跡數(shù)據(jù)集;BP神經(jīng)網(wǎng)絡(luò);百度LBS云服務(wù);軌跡屬性;異常軌跡監(jiān)測

中圖分類號(hào)：TP3111

文獻(xiàn)標(biāo)志碼：A

AbnormalTrajectoryDetectionMethodBasedonBPNeuralNetwork

JIAYing

（

CollegeofMechanicalandElectricalInformation，BaojiVocational&TechnicalCollege，Baoji721013，China

）

Abstract：Existingabnormaltrajectorydetectionalgorithmsusuallycannotrelyontheinternalandexternalattributesofthetrajectoryforeffectivedetection，whichleadstogreatapplicationlimitations.Tosolvetheseproblems，animprovedabnormaltrajectorydetectionmethodbasedonBPneuralnetworkisproposed.Firstly，theoriginaltrajectorydataaredenoisedanduploadedtoBaiduCloudLBSforstorage.Secondly，thedataarenormalizedbasedonBaiduMapTrajectoryDataVisualWebsite，andtheattributevaluesofthetrajectoryareobtained.Finally，theinputlayeroftheBPneuralnetworkalgorithmisrepresentedbythefeatureattributesinsideandoutsidethetrajectory，andtheoutputisrepresentedbythetrajectorysimilaritymeasure.Thetrainingmodelisobtainedbyadjustingthecoefficientsofhiddenlayers.Inthispaper，twosetsofusertrajectorydataofDeolfeprojectaresimulatedtodetectuserabnormaltrajectorydata.Theresultsshowthat，onthebasisoftheoptimaltrainingscheme，theaccuraciesofabnormaltrajectorydetectionofthetwosetsare92.3%and100%，respectively.Themodelcanbeusedasatoolforabnormaltrajectorydetection.

Keywords：trajectorydataset;BPneuralnetwork;BaiduLBSCloudService;trajectoryattributes;abnormaltrajectorymonitoring

0引言

隨著移動(dòng)通信和無線網(wǎng)絡(luò)技術(shù)、GPS、WiFi、藍(lán)牙室內(nèi)定位技術(shù)的快速發(fā)展，及智能設(shè)備的廣泛應(yīng)用，人們對(duì)移動(dòng)對(duì)象位置和軌跡數(shù)據(jù)獲取也非常方便[12]。同時(shí)，隨著軌跡數(shù)據(jù)儲(chǔ)存技術(shù)的飛速發(fā)展，能將大量移動(dòng)對(duì)象位置及軌跡信息儲(chǔ)存到時(shí)空數(shù)據(jù)庫[36]。就軌跡來說，它所指是帶時(shí)間標(biāo)簽的位置信息而構(gòu)成的有序位置序列，且時(shí)空信息很豐富，并對(duì)軌跡數(shù)據(jù)的分析及挖掘起著很重要作用[79]。而異常軌跡檢測屬于軌跡模式挖掘的主要研究課題，并普遍用于智能交通與用戶行為分析中。

1異常軌跡監(jiān)測問題描述

目前，對(duì)異常軌跡檢測的研究主要集中在軌跡空間特征上，極少將軌跡本身屬性作為研究基礎(chǔ)[1012]。對(duì)非線性軌跡屬性數(shù)據(jù)的分類，是檢測軌跡數(shù)據(jù)是否異常的一種可行軌跡分類方法。而BP神經(jīng)網(wǎng)絡(luò)具備對(duì)非線性數(shù)據(jù)分類功能，所以文章提出一種基于BP神經(jīng)網(wǎng)絡(luò)的異常軌跡檢測方法。

1.1傳遞函數(shù)設(shè)計(jì)

傳遞函數(shù)應(yīng)用的是非線性函數(shù)logsig（），而這一對(duì)數(shù)S形函數(shù)曲線，如圖1所示。

其中l(wèi)ogsig（x）=[SX（]11+e-x[SX）]，計(jì)算出0到1之間的輸出。將軌跡劃分成兩個(gè)類別，那么這個(gè)函數(shù)表示為傳遞函數(shù)0和1的輸出，其中0為異常軌跡，1為正產(chǎn)軌跡。

1.2網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)

本文將選用多輸入和多隱含的神經(jīng)元與單輸出的BP神經(jīng)網(wǎng)絡(luò)。單層BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖[1316]，如圖2所示。

其中，BP神經(jīng)網(wǎng)絡(luò)輸入節(jié)點(diǎn)由xi表示，而隱節(jié)點(diǎn)由yj表示，

輸出節(jié)點(diǎn)由Ol表示。wij為輸入節(jié)點(diǎn)和隱節(jié)點(diǎn)網(wǎng)絡(luò)權(quán)值，Tj為隱節(jié)點(diǎn)和輸出節(jié)點(diǎn)間網(wǎng)絡(luò)權(quán)值。

2基于BP神經(jīng)網(wǎng)絡(luò)的異常軌跡監(jiān)測

本文以BP神經(jīng)網(wǎng)絡(luò)作為工具訓(xùn)練，從中獲取了軌跡異常檢測模型，按照軌跡本身四個(gè)屬性，實(shí)現(xiàn)了用戶軌跡是否為異常的目標(biāo)檢測，如圖3所示。

2.1軌跡屬性值提取

2.2軌跡坐標(biāo)處理

由于軌跡是以經(jīng)緯度來表示，并且每5秒則會(huì)對(duì)坐標(biāo)點(diǎn)采樣，所以坐標(biāo)點(diǎn)間的經(jīng)緯度值相差極小。為了便于計(jì)算，并不丟失軌跡本身的特征，文章運(yùn)用了將軌跡坐標(biāo)點(diǎn)直接乘以適當(dāng)系數(shù)的方法，而實(shí)驗(yàn)表明這一方法是可行的。具體操作方法為：設(shè)置一條軌跡

T（其公式為T={（t1，x1，y1），（t2，x2，y2），…，（tn，xn，yn）}，其中時(shí)空三元組（ti，xi，yi）代表軌跡T中的第i個(gè)位置點(diǎn)，而ti則為這個(gè)位置點(diǎn)的采樣時(shí)刻，（xi，yi）為ti時(shí)刻的GPS坐標(biāo)（1≤i≤n）），將軌跡集中xi、yi分別乘以系數(shù)λ，而這一系數(shù)選取取決于實(shí)際情況，這樣便于計(jì)算為原則。在實(shí)驗(yàn)中λ=1000，經(jīng)過處理后的軌跡則為T′={（x′1，y′1），（x′2，y′2），…，（x′n，y′n）}。因此，對(duì)軌跡數(shù)據(jù)集TS處理后的數(shù)據(jù)集則為TS′。

2.3利用BP神經(jīng)網(wǎng)絡(luò)算法訓(xùn)練監(jiān)測模型

2.3.1基于BP神經(jīng)網(wǎng)絡(luò)的異常軌跡監(jiān)測算法流程

BP神經(jīng)網(wǎng)絡(luò)算法是一種基于梯度下降的學(xué)習(xí)算法?？梢詫W(xué)習(xí)過程劃分成兩個(gè)階段，即信息正向傳遞、誤差反向傳播[1719]，如圖4所示。

2.3.2基于BP神經(jīng)網(wǎng)絡(luò)的異常軌跡檢測算法描述

構(gòu)建一個(gè)三層BP神經(jīng)網(wǎng)絡(luò)，其指令為：

net=

newff（PR，[S1，S2，…，SN]，[TF1，TF2，…，TFN]，BTF，BLF，PF）

其中，PR為輸入向量取值范圍，

Si則為第i（i=1，2，…，N）層神經(jīng)元個(gè)數(shù)，共計(jì)N層;TFi為第i層傳遞函數(shù);BTF表示為BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練函數(shù)，BLF表示BP神經(jīng)網(wǎng)絡(luò)權(quán)值與閥值學(xué)習(xí)函數(shù);PF表示性能函數(shù)，而試驗(yàn)所用最小均方誤差（mse）為性能函數(shù)。

執(zhí)行結(jié)果為構(gòu)建一個(gè)N層BP神經(jīng)網(wǎng)絡(luò)模型。對(duì)帶分類標(biāo)簽的數(shù)據(jù)集，先對(duì)設(shè)計(jì)的模型進(jìn)行現(xiàn)有軌跡訓(xùn)練，得到穩(wěn)定模型，然后將未知的軌跡放入模型中檢測判斷是否為異常軌跡。

3實(shí)驗(yàn)

在文章中的所提出的算法都是在Matlab2016a環(huán)境下實(shí)現(xiàn)的，硬件和軟件環(huán)境為：Intel（R）Core（TM）2Duo3.3GHzCPU，內(nèi)存為4GB，操作系統(tǒng)為Windows10。

3.1數(shù)據(jù)集選取

本次實(shí)驗(yàn)數(shù)據(jù)主要源自于GeoLifeGPSTrajectories項(xiàng)目中的某兩個(gè)用戶的軌跡數(shù)據(jù)集。由于軌跡集所使用的是格林威治時(shí)間，所以從23：0000：59、9：0010：59等這一時(shí)段轉(zhuǎn)換為北京時(shí)間則為7：008：59、17：0018：59，而這一時(shí)段正屬于上下班高峰期。因此，本文所選用的軌跡數(shù)據(jù)集為某兩個(gè)用戶2018年9月23日12月23日期間每天這一時(shí)段的軌跡數(shù)據(jù)，共計(jì)180條。

3.2試驗(yàn)結(jié)果

3.2.1BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練及仿真結(jié)果

在本次實(shí)驗(yàn)中，對(duì)第一個(gè)用戶的90條軌跡屬性數(shù)據(jù)給予分組，根據(jù)分組結(jié)果不同，提出了五種訓(xùn)練方案。在方案1中，30條軌跡屬性數(shù)據(jù)用于訓(xùn)練，剩余數(shù)據(jù)用于仿真;在方案2中，40條軌跡屬性數(shù)據(jù)用于訓(xùn)練，剩余數(shù)據(jù)用于仿真;在方案3中，50條軌跡屬性數(shù)據(jù)用于訓(xùn)練，剩余數(shù)據(jù)用于仿真;在方案4中，60條軌跡數(shù)據(jù)屬性用于訓(xùn)練，剩余數(shù)據(jù)用于仿真;在方案5中，70條軌跡屬性數(shù)據(jù)用于訓(xùn)練，剩余數(shù)據(jù)用于仿真。此外，由這五種方案所生成的精度、召回率、F度量值柱狀圖，如圖5所示。

精度是對(duì)精準(zhǔn)性的度量，也就是標(biāo)記為正類的元組或異常軌跡元組的實(shí)際正類所占百分比，其表達(dá)公式為：

precision=

[SX（]TPTP+FP[SX）]

公式中的TP代表為正確分類的異常軌跡條數(shù)，而FP代表的是異常軌跡錯(cuò)誤標(biāo)記的條數(shù)。

所謂的召回率則是指對(duì)完全性度量，也就是將正元組或是異常軌跡元組標(biāo)記為正類的百分比，而其表達(dá)公式則為：

recall=

[SX（]TPTP+FN[SX）]

公式中的FN代表為將正常軌跡錯(cuò)誤標(biāo)記成異常軌跡的條數(shù)。

而F度量所指的是把精度與召回率組合一個(gè)度量中，那么其表達(dá)公式為：

F=

[SX（]2×precision×recallprecision+recall[SX）]

由圖5得知，在這五種方案中只有方案4的性能最好，它的F度量值達(dá)到92.3%，所以利用此方案對(duì)另一用戶的軌跡數(shù)據(jù)集實(shí)行仿真實(shí)驗(yàn)，也就是使用另一用戶的60條軌跡屬性數(shù)據(jù)用作訓(xùn)練，而剩余數(shù)據(jù)則用作仿真實(shí)驗(yàn)。最終獲得此次軌跡檢測模型的輸出類別與實(shí)際類別的對(duì)比結(jié)果。

3.2.2網(wǎng)絡(luò)性能分析

采用方案4對(duì)另一用戶的仿真訓(xùn)練的BP神經(jīng)網(wǎng)絡(luò)性能，如圖6所示。

通過圖6（a）BP神經(jīng)網(wǎng)絡(luò)綜合性能可以得知，此次實(shí)驗(yàn)選用的是三層神經(jīng)網(wǎng)絡(luò)，第一次為輸入層有4個(gè)輸入節(jié)點(diǎn)，第二次為隱含層有10個(gè)隱節(jié)點(diǎn)，第三次為輸出層有1個(gè)輸出節(jié)點(diǎn)。因此得知實(shí)驗(yàn)使用的BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練算法為trainoss，而使用的性能函數(shù)則為均方誤差函數(shù)mse，并且這個(gè)模型的均方誤差mse值為1.31e24，梯度為7.85e24，最大驗(yàn)證失敗0次。用時(shí)5分9秒共迭代1671次，說明這個(gè)

模型非常穩(wěn)定，而且已經(jīng)滿足精度要求，所以能夠作為用戶軌跡聚類與異常軌跡檢測的模型。由圖6（b）得知，最小均方差在10-11時(shí)緩慢下降，然而在訓(xùn)練次數(shù)達(dá)到最大時(shí)，將會(huì)突然降到10-24，這是因?yàn)閷?shí)驗(yàn)的訓(xùn)練方法為trainoss，它屬于快速訓(xùn)練方法，所以在網(wǎng)絡(luò)性能到達(dá)一定精度時(shí)將會(huì)快速收斂。由圖6（c）得知，這種算法將會(huì)始終保持平穩(wěn)梯度下降，且驗(yàn)證失敗始終為0次，且訓(xùn)練次數(shù)達(dá)到足夠大時(shí)，將會(huì)呈直線下降，究其原因則等同于mse突然下降原因。

4總結(jié)

文章提供的基于BP神經(jīng)網(wǎng)絡(luò)異常軌跡檢測方法具有兩個(gè)階段。其一，先對(duì)軌跡數(shù)據(jù)收集，然后去除數(shù)據(jù)噪音并上傳到百度云LBS.云端儲(chǔ)存，最后設(shè)計(jì)軌跡顯示系統(tǒng)，實(shí)現(xiàn)在百度地圖上顯示軌跡數(shù)據(jù)集。其二，利用軌跡屬性提取算法對(duì)軌跡集進(jìn)行預(yù)處理，從中獲取軌跡屬性向量，如軌跡長度屬性、軌跡角度屬性、軌跡時(shí)長屬性、軌跡平均速度等。其次以軌跡特征屬性看作BP神經(jīng)網(wǎng)絡(luò)算法輸入層，以軌跡相似度量作為輸出層，然后訓(xùn)練出穩(wěn)定的異常軌跡檢測模型。最后用異常軌跡檢測模型判斷用戶軌跡是否為異常，便于獲取異常軌跡數(shù)據(jù)。

參考文獻(xiàn)

[1]

ZhengY.TrajectoryDataMining：AnOverview[J].ACM，2015，6（3）：29.

[2]PrelipceanAC，GidofalviG，SusiloYO.Measuresoftransportmodesegmentationoftrajectories[J].InternationalJournalofGeographicalInformationScience，2016：122.

[3]LüM，ChenL，XuZ，etal.Thediscoveryofpersonallysemanticplacesbasedontrajectorydatamining[J].Neurocomputing，2016，173（3）：11421153.

[4]GiannottiF，NanniM，PedreschiD，etal.Unveilingthecomplexityofhumanmobilitybyqueryingandminingmassivetrajectorydata[J].TheVLDBJournal，2011，20（5）：695.

[5]GuptaM，GaoJ，AggarwalCC.Outlierdetectionfortemporaldata：Asurvey[J].IEEETransactionsonKnowledgeandDataEngineering，2014，25（1）：120.

[6]HuW，LiX，TianG，etal.AnincrementalDPMMbasedmethodfortrajectoryclustering，modeling，andretrieval[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，2013，35（5）：10511065.

[7]CaiY，WangH，ChenX，etal.Trajectorybasedanomalousbehaviourdetectionforintelligenttrafficsurveillance[J].IETIntelligentTransportSystems，2015，9（8）：810816.

[8]LaxhammarR，F(xiàn)alkmanG.Onlinelearningandsequentialanomalydetectionintrajectories[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，2014，36（6）：11581173.

[9]ShenM，LiuDR，ShannSH.Outlierdetectionfromvehicletrajectoriestodiscoverroamingevents[J].InformationSciences，2015，294（9）：242254.

[10]王嶸冰，徐紅艷，李波.BP神經(jīng)網(wǎng)絡(luò)隱含層節(jié)點(diǎn)數(shù)確定方法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2018（4）：16.

[11]朱燕，李宏偉，樊超.基于聚類的出租車異常軌跡檢測[J].計(jì)算機(jī)工程，2017，43（2）：1620.

[12]閆密巧，王占宏，王志宇.基于Redis的海量軌跡數(shù)據(jù)存儲(chǔ)模型研究[J].微型電腦應(yīng)用，2017，33（4）：911.

[13]毛嘉莉，金澈清，章志剛.軌跡大數(shù)據(jù)異常檢測：研究進(jìn)展及系統(tǒng)框架[J].軟件學(xué)報(bào)，2017，28（1）：1734.

[14]俞慶英，李倩，陳傳明，等.基于BP神經(jīng)網(wǎng)絡(luò)的異常軌跡檢測方法研究[J/OL].計(jì)算機(jī)工程.https：//doi.org/10.19678/j.issn.10003428.0051574

[15]時(shí)磊，魯華棟.基于高斯混合模型的移動(dòng)目標(biāo)跟蹤[J].微型電腦應(yīng)用，2017，33（12）：7577.

[16]崔寶才.基于GA改進(jìn)BP神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)異常檢測方法[J].現(xiàn)代電子技術(shù)，2016，39（3）：9093.

[17]韓旭.基于車輛軌跡多特征的聚類分析及異常檢測方法的研究[D].哈爾濱：哈爾濱工程大學(xué)，2014.

[18]鮑蘇寧，張磊，楊光.基于核主成分分析的異常軌跡檢測方法[J].計(jì)算機(jī)應(yīng)用，2014，34（7）：21072110.

[19]龔暢，王華君，李榮，等.利用兩階段遺傳算法的機(jī)械手最優(yōu)軌跡控制仿真[J].微型電腦應(yīng)用，2016，32（4）：1822.

（收稿日期：2019.06.26）