基于軌跡大數據離線挖掘與在線實時監測的出租車異常軌跡檢測算法

王偉 譚松榮

摘要：本文探討了異常軌跡檢測算法的理論概述，對此類檢測算法進行了研究，通過分析出租車異常軌跡的框架，在一定程度上驗證了檢測算法的有效性和高效性。

關鍵詞：軌跡大數據;離線挖掘;異常軌跡;檢測算法

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1007-9416（2018）12-0118-02

1 異常軌跡檢測算法的理論概述

所謂軌跡其實就是一種時空數據的類型，它是通過記錄移動對象的歷史位置所形成的，而異常軌跡就是指一些沒有按照預期的模式出現的表現形式，軌跡的異常檢測的方法主要有分類檢測法、歷史相似性檢測法、距離檢測法以及網格劃分檢測法四種。

（1）運用分類檢測法可以將其分成兩個階段進行檢測，根據收集到的大量的軌跡數據，在移動的路徑當中提取出與位置相關的motif等移動的特征，再對其軌跡進行檢測，構建出一個數據的分辨率的視圖，可以有效對不同維度和不同粒度的軌跡特征進行分析，最終達到檢測的目的。但是由于數據是一直在更新產生的，所以分類檢測法并不能對軌跡流進行在線的異常檢測。（2）歷史軌跡相似性的檢測法是通過對歷史的軌跡進行收集，建立一個全局的特征模型，然后利用全局特征模型中的數據對異常的軌跡進行檢測，如果不考慮軌跡數據的變化速度，基于歷史軌跡相似性的異常檢測方法往往能夠提供比較精確的檢測數據，所以這類檢測方法經常運用與航海和路網交通中。（3）距離檢測方法就是將軌跡的數據進行集中，其中與大多數的軌跡不同且距離比較遠的軌跡就是異常軌跡，它的目的主要在于及時發現在某一個時間段內的異常移動的對象，比較強調軌跡本身的異常行為。（4）網格劃分檢測方法是指在劃分的大小相同的網格的城市路網當中有效識別出異常的網格單元。網格劃分檢測方法中的iBat檢測算法能夠對出租車異常軌跡進行識別，可以及時對出租車司機進行繞路或者欺騙的行為進行揭示，但是目前此類檢測方法的檢索效率和方式還有待完善，才能充分發揮出網格劃分檢測方法的作用。

2 出租車異常軌跡的檢測框架

2.1 準備數據和預處理

（1）對數據進行準備。文本通過對西安市的歷史的出租車軌跡數據進行收集，將8867輛出租車的GPS的數據作為檢測的樣本，并對數據進行處理，對一些頻率間隔不穩定以及定位不再西安市本地的數據進行剔除，再將剩余的數據進行編號，保證數據的可靠性。（2）對數據進行預處理。軌跡數據往往會因為環境和儀器產生故障的因素，會出現缺失、重復GPS的記錄數據的現象，并且如果傳送的頻率發生的異常，其定位的范圍就會超出所要研究的城市，所以就會產生一些異常的數據，這些異常數據嚴重影響了運算的結果，因此要提前對數據進行預處理，有效去除有問題的數據。對數據進行預處理可以通過對異常的數據進行分析，過濾掉狀態為熄火和防劫、頻率過高或者過低、經緯度范圍不在西安市、缺少或者重復等的數據，并對一些數據進行識別，然后再用oracle作為數據庫，將text格式的數據導入建立的表空間內，然后再使用sql的語句對數據進行處理。

2.2 提取出有效的載客軌跡

通過提取出有效的載客軌跡可以提供出有效的軌跡數據，幫助異常檢測工作能夠順利進行，載客軌跡的提取是將預處理后的數據進行排序，將車牌號和時間作為排序的基礎，并把一輛車在一個時間段之內變化的狀況作為檢測的線索，然后生成一個有效的OD表，才能有效提取出載客的軌跡數據。

2.3 將軌跡數據與地圖相匹配

對出租車進行異常軌跡檢測時，可以先將出租車的軌跡數據繪制在相對應的電子數據上，如果一輛出租車沒有異常的軌跡運動，那么盡管它沒有完全在道路上，但是它的總體的行駛趨勢還是會跟道路相似。并且如果想要數據發揮出它的有效性，就要在進行異常軌跡的檢測之前對數據進行校正，讓軌跡數據能夠真正的與地圖相匹配。通過在車輛指揮中心接收到車輛在行駛過程中的GPS位置信息，設計科學、合理的模型和算法，有效將車輛目前正在行駛的位置與電子地圖上的位置相連接，最終讓車輛的具體位置出現在電子地圖的道路上，這就是地圖匹配，目前已經有很多種方法能夠實現車輛的GPS位置信息能有效與路網的信息相關聯起來，比如多權值的地圖匹配方法等。

3 基于軌跡大數據挖掘的出租車異常軌跡檢測

由于GPS數據具有隨機性、特殊性、數據大量等特點，所以現在還沒有很好能夠應用在實際生活中的異常軌跡的檢測，并且軌跡的不同的表達方式在很大程度上影響了軌跡異常檢測算法的準確率和效率，所以對軌跡的表達方式進行研究，表達唯一的路口序列形式，在一定程度上降低軌跡數據的復雜性，并能對異常軌跡進行有效的實時監測[1]。

3.1 收集西安市的相關數據

根據西安市的經緯度的范圍，對西安市的電子地圖的數據進行下載，其中主要的信息有路段的信息和路口的信息，然后在提取相關的路口序列，有效利用幾何相交的原理將提取的路段信息和路口信息進行處理，所以可以得到23064個路口的信息和31114的路段信息。

3.2 對異常軌跡檢測的簡單的算法

所謂簡單的算法其實就是指將一些即將檢測的軌跡上的每一個軌跡的點與歷史中的軌跡進行對應檢查，從中找出比較異常的軌跡點，然后再充分根據相關的數據確定軌跡發生異常的片段和程度，其主要的算法是：通過輸入相關的軌跡數據集Ts，待測的軌跡Ttest以及閾值δ，然后依照公式for i=1：n do，來計算出每一個軌跡點會發生的軌跡的概率P（i），再將P（i）與閾值相比較，輸出發生異常的軌跡點，再將發生異常的軌跡點連接，使其組成異常的軌跡片段，計算出其長度，最后再與閾值進行比較，就可以得出異常的軌跡數值。

簡單的異常軌跡檢測算法的復雜程度和軌跡的數目都成正比，并且每一條軌跡都必須要與全部的軌跡數據庫進行匹配，所以此類方法的算法空間和時間的復雜度都是比較高的。并且簡單的異常軌跡檢測算法是對部分的軌跡進行檢測，避免了對全局的軌跡空間進行檢測，所以在很大程度上提高了異常軌跡檢測方法的精度和速率。

4 結語

隨著科學技術的不斷發展，帶動了智能終端的發展，并且由于我國許多城市的出租車都出現了繞路的欺騙行為，所以檢測出租車異常軌跡的檢測方法的出現是必然的趨勢，此類檢測方法通過對歷史的出租車行駛的軌跡進行收集，并對其數據進行預處理，可以有效分析出出租車在行駛過程中出現的異常軌跡行為，并且能夠根據分析出的結果，有效對乘客進行反饋以及向有關的管理部門發送通知，規范出租車司機的行為，保證出租車行業能呈現良好發展的態勢。

參考文獻

[1]韓博洋，汪兆洋，金蓓弘.一種基于軌跡大數據離線挖掘與在線實時監測的出租車異常軌跡檢測算法[J].中國科學技術大學學報，2016，46（3）：247-252.

Taxi Abnormal Trajectory Detection Algorithm Based on Off-line Mining of Large Trajectory Data and On-line Real-time Monitoring

WANG Wei， TAN Song-rong

（Tianyi Ai Music Cultural Technology Co.， Ltd. ， Guangzhou Guangdong 510180）

Abstract：In this paper the theory of abnormal trajectory detection algorithm is discussed， and this kind of detection algorithm is studied， By analyzing the framework of abnormal taxi trajectory， the effectiveness and efficiency of the detection algorithm are verified to a certain extent.

Key words：large trajectory data; off-line mining; abnormal trajectory; detection algorithm