任其亮,徐韜*,,劉媛,程龍春
(1.重慶交通大學(xué),重慶 400074;2.重慶設(shè)計集團有限公司,重慶 400050)
浮動車數(shù)據(jù)(Floating Car Data,FCD)因其覆蓋范圍廣、時效性高等特點,已成為城市交通大數(shù)據(jù)挖掘與分析的重要基礎(chǔ)數(shù)據(jù),并廣泛應(yīng)用于道路車速預(yù)測[1]、瓶頸識別[2]等智能交通應(yīng)用領(lǐng)域。FCD采集分析技術(shù)因多場景的應(yīng)用范圍使其擁有很強的挖掘和應(yīng)用價值,但是大量技術(shù)問題,例如,設(shè)備故障、信號遮蔽、傳輸失真或其他因素影響,會引發(fā)千萬數(shù)量級的FCD 出現(xiàn)無法避免的異?;蚴д鏀?shù)據(jù),為了確保動態(tài)交通數(shù)據(jù)信息的有效性和精準(zhǔn)性,準(zhǔn)確、實時的異常數(shù)據(jù)檢測和處理是不可或缺的。
現(xiàn)有異常檢測方法主要對由浮動車車速組成的一維時間序列進行直接處理,存在信息挖掘不足、檢測精度不高等問題。未能檢測出的異常數(shù)據(jù)會污染數(shù)據(jù)源,導(dǎo)致數(shù)據(jù)分析結(jié)果誤差較大或失真,從而降低FCD 數(shù)據(jù)挖掘和分析效果。根據(jù)異常數(shù)據(jù)樣本分布不同,異常數(shù)據(jù)可分為單點異常、上下文異常和群體異常這3類,F(xiàn)CD主要表現(xiàn)為單點異常和上下文異常。根據(jù)檢測方法模型特性的不同,現(xiàn)有異常數(shù)據(jù)檢測方法可分為基于數(shù)理統(tǒng)計方法、空間相似度方法(距離、密度)、集成學(xué)習(xí)、深度學(xué)習(xí)這4類。許倫輝等[3]根據(jù)前后速度差識別異常數(shù)據(jù)再利用動態(tài)時間規(guī)劃方法進行數(shù)據(jù)修復(fù),但對連續(xù)多個異常數(shù)據(jù)識別較弱;鄭啟晨[4]利用經(jīng)緯度閾值法和瞬時速度閾值法從空間軌跡視角對離群GPS(Global Positioning System)數(shù)據(jù)點進行識別,但無法識別出速度突變異常點;吳艷平等[5]根據(jù)浮動車運行軌跡從空間匹配出發(fā)對偏離樣本數(shù)據(jù)進行檢測并重構(gòu)軌跡序列,但僅適用于GPS坐標(biāo)異常類型的數(shù)據(jù)識別??梢姅?shù)理統(tǒng)計方法和空間相似度方法適用范圍有一定的局限性。
由于FCD 數(shù)據(jù)缺少樣本標(biāo)簽信息,更適應(yīng)于無監(jiān)督學(xué)習(xí)方法,因此,近年來大量學(xué)者利用集成學(xué)習(xí)、深度學(xué)習(xí)方法開展異常數(shù)據(jù)檢測。曹鵬等[6]利用K-means 聚類算法對浮動車停放和等待時的異常數(shù)據(jù)進行識別,Lam等[7]利用樸素貝葉斯和高斯混合模型對交叉口離群FCD 數(shù)據(jù)進行檢測,Li等[8]通過高斯過程回歸器識別出異常FCD 數(shù)據(jù)并估計路網(wǎng)交通量,Hu等[9]通過聚類算法對浮動車在交叉口轉(zhuǎn)彎時的異常數(shù)據(jù)進行檢測,檢測準(zhǔn)確率為85.0%。相關(guān)算法在其他領(lǐng)域異常數(shù)據(jù)檢測中得到了大量應(yīng)用,陳瀅生等[10]提出基于自編碼器的大數(shù)據(jù)集異常數(shù)據(jù)識別算法,并利用小波去噪進行預(yù)處理,但會損失部分價值信息;牛罡等[11]利用傳統(tǒng)IForest 對電力數(shù)據(jù)進行異常檢測,但收斂速度較慢;張萬旋等[12]提出IForest 動態(tài)更新策略,開展液體火箭發(fā)動機異常檢測,但無法避免更新樣本對模型參數(shù)污染問題;孫朝云等[13]提出基于D-S-LOF(Difference-Summation-Local Outlier Factor)的道路環(huán)境感知數(shù)據(jù)檢測方法,構(gòu)建由一階減法前向差分、相鄰兩項求和的二維特征向量,再利用局部異常因子(Local Outlier Factor,LOF)算法進行檢測,但容易陷入局部最優(yōu),不適用于具有全局特征的FCD數(shù)據(jù)檢測;唐立等[14]提出動態(tài)生長高度的改進IForest算法,但數(shù)據(jù)維度偏低,檢測準(zhǔn)確度有待提高。
綜上,目前流行的集成學(xué)習(xí)方法如IForest因具有高維數(shù)據(jù)全局性和魯棒性[15]特點,適合FCD開展異常數(shù)據(jù)檢測應(yīng)用,但當(dāng)前IForest算法在動態(tài)檢測中存在新樣本對模型污染和收斂性能不足等問題,且現(xiàn)有研究鮮有考慮載客和未載客不同運營條件下車輛駕駛行為差異對數(shù)據(jù)干擾的影響,需要提高數(shù)據(jù)維度充分挖掘數(shù)據(jù)信息,并分析不同載客狀態(tài)下模型適應(yīng)能力,提高異常數(shù)據(jù)檢測精度和處理能力?;诖耍疚耐ㄟ^差分等方式擴展原始數(shù)據(jù)維度,并在IForest基礎(chǔ)上提出差額累計更新和動態(tài)區(qū)分辨識的改進IIForest 算法,對FCD 異常數(shù)據(jù)進行檢測,同時對不同載客狀態(tài)異常數(shù)據(jù)分布特點進行對比分析,最后通過重慶市中心城區(qū)道路數(shù)據(jù)進行驗證,以證明該組合算法的有效性和適應(yīng)性。
每輛裝有GPS的浮動車(如出租車、公交車等)每10~15 s返回一條樣本數(shù)據(jù),樣本字段包括日期、時間片段、公司代碼、車牌ID、經(jīng)度、緯度、車速、方向角、載客狀態(tài)共9個字段。設(shè)城市道路網(wǎng)絡(luò)共含有n條路段,所需檢測路段為lj,j∈[1,n],將樣本數(shù)據(jù)中經(jīng)度、緯度信息匹配至城市GIS(Geographical Information System)路網(wǎng)中路段lj,統(tǒng)計出位于lj經(jīng)度、緯度坐標(biāo)內(nèi)的樣本數(shù)據(jù),按時間片段數(shù)值進行升序排列,排列后的車速字段數(shù)據(jù)匯總形成原始數(shù)據(jù)集合y,即
式中:i為樣本索引,i∈(1,m);m為樣本總條數(shù);yi為原始數(shù)據(jù)集合的異常數(shù)據(jù)值,yi∈y。
則本文定義的浮動車數(shù)據(jù)異常檢測算法任務(wù)為:在已知原始數(shù)據(jù)集合y的前提下,識別檢測出目標(biāo)路段lj中存在數(shù)據(jù)異常值yi,為后續(xù)異常數(shù)據(jù)修復(fù)和填補提供基礎(chǔ)。
根據(jù)交通流理論,無論是連續(xù)流還是間斷流,交通流參數(shù)在時間上存在一定的連續(xù)性,當(dāng)時間序列中某一時刻數(shù)據(jù)存在突變點或空值等異常值時,通過前后兩項的差分運算可快速識別出異常點;然而當(dāng)出現(xiàn)兩個及以上呈現(xiàn)遞增或遞減的連續(xù)異常值時,前后差分值則不會發(fā)生明顯變化,也就無法檢測數(shù)據(jù)的異常點。本文在借鑒前后差分的基礎(chǔ)上,構(gòu)建高維向量數(shù)據(jù)集,利用IForest 無監(jiān)督學(xué)習(xí)方式從高維向量數(shù)據(jù)集中進行采樣,訓(xùn)練出孤立樹并記錄路徑長度,計算出樣本測試集異常得分,進而檢測出數(shù)據(jù)異常點。
(1)建立S-DTA高維特征向量
孫朝云等[13]提出一種D-S 二維特征向量構(gòu)建方法,雖然增加了數(shù)據(jù)維度,但在處理多個連續(xù)異常值時不敏感。因此,借鑒D-S前后差分與求和思想,構(gòu)建由相鄰兩項求和(S)、三階求和平均差分(DTA)組成的二維度空間特征向量,設(shè)數(shù)據(jù)集y={y1,…,yi,…,ym}中yi為第i個樣本數(shù)值,若yi為異常點,則二維特征向量會出現(xiàn)一個離群點,即(Si,DDTA,i),Si為第i個樣本求和特征值,DDTA,i為第i個樣本三階求和平均差分特征值,各特征值表達(dá)形式為
(2)改進IIForest算法
IForest 基本思想是異常樣本更容易快速落入葉子結(jié)點,即異常樣本在決策樹上距離根節(jié)點更近。IForest算法不是篩選出正常樣本數(shù)據(jù),而是孤立出異常數(shù)據(jù),IForest算法通過遞歸地隨機分割數(shù)據(jù)集,直到所有的樣本點都是孤立的,在這種隨機分割的策略下,異常點通常具有較短的路徑,相較于LOF、K-means 等傳統(tǒng)算法,IForest 算法對高維數(shù)據(jù)有更好的魯棒性。IForest 算法需構(gòu)建孤立樹iTree,通過二叉搜索樹結(jié)構(gòu)來孤立樣本,流程如下。
Step 1 選擇樣本數(shù)據(jù)集中n個數(shù)據(jù)作為訓(xùn)練集,訓(xùn)練集最大值、最小值分別為Xmax、Xmin,并放入一個二叉樹BTree 中。
Step 2 選擇樣本數(shù)據(jù)集中任意維度ki和切割點Q(Q∈(Xmin,Xmax)),將ki維度下小于Q的樣本數(shù)據(jù)劃分到左節(jié)點,余下數(shù)據(jù)劃分到右節(jié)點。
Step 3 在下一子節(jié)點以遞歸方式重復(fù)Step 1和Step 2,直到每個節(jié)點只有一個樣本數(shù)據(jù)或達(dá)到設(shè)置的樹最大高度。
Step 4 選取下一個BTree,重復(fù)Step 1~Step 3,并訓(xùn)練完成所有BTree。
Step 5 計算每個iTree 平均路徑長度c(n),歸一化算式為
式中:H(n)為調(diào)和數(shù);n為用于生成單顆孤立樹的樣本點數(shù)量;ζ為歐拉常數(shù),ζ≈0.58。
Step 6 計算異常值分?jǐn)?shù)s(x,n),算式為
式中:hi(x)為樣本點x在孤立樹i中的深度值;t為孤立樹數(shù)量。
s(x,n)越接近1,表示該點為異常點的可能性越高;s(x,n)越接近0,表示該點為異常點的可能性越低;若s(x,n)接近于0.5,則該點可能為正常點或異常點。
傳統(tǒng)IForest算法主要存在兩個問題:一是在動態(tài)數(shù)據(jù)檢測下隨著樣本點P的不斷加入,由多個孤立樹組成的孤立森林會計算出樣本點異常值分?jǐn)?shù)并改變模型結(jié)構(gòu),導(dǎo)致模型被異常數(shù)據(jù)污染;二是每個孤立樹的異常數(shù)據(jù)檢測能力有差異,導(dǎo)致算法收斂速度存在差異。為解決上述問題,本文提出差額累計更新和動態(tài)區(qū)分辨識的改進IIForest(Improvement IForest,IIForest)算法,對于問題一,本文提出停止閾值σ,當(dāng)新樣本點異常值分?jǐn)?shù)s大于σ時,僅檢測新樣本,不更新孤立森林模型;對于問題二,則計算每個二叉樹BTree 的區(qū)分辨識度β,β處于設(shè)定停止區(qū)間時,則停止生長,以此提升算法收斂性能。關(guān)鍵改進步驟如下。
Step 1 根據(jù)所建立的孤立森林模型,計算新樣本點P的異常值分?jǐn)?shù)s。若s>σ,則只輸出s并進行判定;若s≤σ,則重新訓(xùn)練孤立樹iTree 并更新孤立森林模型。
Step 2 統(tǒng)計傳統(tǒng)IForest 算法Step 2 中,隨機ki維度下切分點Q左側(cè)集合的數(shù)據(jù)樣本數(shù)量NL和右側(cè)數(shù)據(jù)樣本數(shù)量NR。
Step 3 對該節(jié)點區(qū)分辨識能力進行判定。根據(jù)IForest算法原理,若該節(jié)點能有效區(qū)分正常點和異常點,則該節(jié)點為高辨識節(jié)點,可繼續(xù)生長;若該節(jié)點無法區(qū)分正常點和異常點,則該節(jié)點為低辨識節(jié)點,應(yīng)結(jié)束生長,并選擇下一個BTree 進行訓(xùn)練。區(qū)分辨識能力由區(qū)分辨識度β參數(shù)標(biāo)定,即
式中:β∈(a,δ)時,則認(rèn)為左右節(jié)點樣本數(shù)量差異較小,該節(jié)點為低辨識節(jié)點,停止生長,其中,α、δ為上下區(qū)間值;ε為偏離系數(shù),ε∈(0.5,1.5) 。本文ε=1,α、δ分別為0.8、1.25。
Step 4 重復(fù)Step 2~Step 3,并訓(xùn)練完成所有BTree,按照傳統(tǒng)IForest中Step 6計算異常值分?jǐn)?shù)。
Step 5 根據(jù)異常值分?jǐn)?shù),判斷該點是否為異常點。
本文IIForest算法能解決新加入異常點樣本對孤立森林模型的污染問題,同時識別出節(jié)點的辨識能力,有效減少非必要運算量,縮短算法運行時耗,提高模型收斂速度。
實驗環(huán)境為Intel(R)Core(TM)i7-10875H CPU 2.30 GHz,內(nèi)存32 G,Windows 10 專業(yè)版操作系統(tǒng),本文所涉及到的算法均使用Python 軟件中的Numpy、Pandas及Sklearn庫實現(xiàn)。
本文收集的數(shù)據(jù)集為重慶市中心城區(qū)2022 年7 月15 日12:00-12:15 浮動車(出租車)GPS 數(shù)據(jù),樣本總條數(shù)為299153條,其中經(jīng)緯或緯度為0的明顯錯誤數(shù)據(jù)6507 條,錯誤率為2.18%,因樣本數(shù)據(jù)集中在內(nèi)環(huán)快速路以內(nèi)區(qū)域,選取學(xué)府大道R1 作為測試路段,具體如圖1所示。
圖1 樣本數(shù)據(jù)分布示意圖Fig.1 Sample data distribution diagram
結(jié)合混淆矩陣定義,檢測結(jié)果可分為真陽性(True Positive,TP)、真陰性(True Negative,TN)、假陽性(False Positive,FP)、假陰性(False Negative,FN)這4 類。為評價不同模型異常數(shù)據(jù)檢測效果,選擇AUC、F1-score指標(biāo)進行評價。
(1)AUC
AUC是ROC(Receiver Operating Characteristic,ROC)曲線下的面積,ROC橫坐標(biāo)為假正率FPR,縱坐標(biāo)是真正率TPR,AUC ∈[0,1],AUC 越大,模型檢測準(zhǔn)確率越高。
(2)F1-score
F1-score 是精確率Precision (P) 和召回率Recall(R)的加權(quán)調(diào)和平均值,用以衡量模型檢測精度,F(xiàn)1-score越高,精度越理想。
式中:F1-scroe為F1-scroe的值;TP為預(yù)測正確答案的頻數(shù);FP為將其他類標(biāo)簽預(yù)測為本類標(biāo)簽的頻數(shù);FN為本類標(biāo)簽預(yù)測為其他類標(biāo)簽的頻數(shù)。
(1)建立二維特征向量
R1 有效樣本條數(shù)為1100 條,車速時間序列數(shù)據(jù)如圖2 所示,“車速”字段中最大值Max_speed 為74 km·h-1,最小值Min_speed 為0,與空值“null”相比,0 并不代表一定為異常值,即可能為等待信號燈、嚴(yán)重?fù)矶聲r靜止?fàn)顟B(tài)下的車速真實值,簡單刪除0樣本會導(dǎo)致分析結(jié)果失真,故需要通過智能學(xué)習(xí)算法識別出異常值。
圖2 R1車速分布時間序列圖Fig.2 Speed distribution time series diagram of R1
根據(jù)式(2)建立由S、DTA組成的特征向量數(shù)據(jù)集U,其中前900 個樣本數(shù)據(jù)為訓(xùn)練集Utrain,余下200樣本數(shù)據(jù)為測試集Utest。S-DTA特征向量圖如圖3(a)所示,可以看出,由于存在兩個及以上連續(xù)車速為0的值,圖中形成多個S為0的點,位于圖像邊緣側(cè)。孫朝云等[13]提出D-S二維特征向量,由于連續(xù)多個0值,邊緣形成“V”型圖像點,難以進行識別,如圖3(b)所示。
圖3 二維特性向量圖Fig.3 Two-dimensional characteristic vector map
(2)不同模型精度對比分析
設(shè)定本文IIForest 模型中各參數(shù)n_estimators為100,max_features 為2,contamination 為auto,max_samples 為256,bootstrap 為False,n_ jobs 為-1,random_state為1,將R1中Utrain作為訓(xùn)練集訓(xùn)練IIForest 模型,以測試集Utest用于測試模型精準(zhǔn)度。還需確定停止閾值σ,當(dāng)σ較大時,會導(dǎo)致部分被認(rèn)為是“正?!秉c進而被用于更新模型;當(dāng)σ較小時,會導(dǎo)致模型訓(xùn)練數(shù)據(jù)較少進而存在虛警風(fēng)險,經(jīng)過反復(fù)調(diào)試,當(dāng)σ=0.47 時AUC 最大,故本文取σ=0.47。通過測試后,特征向量數(shù)據(jù)集U中正常點和異常點分布如圖4所示??梢?,異常值分布在二維特征向量散點圖邊緣,同時有效識別出車速連續(xù)0值中的異常點和正常點。
圖4 S-DTA-IIForest異常檢測結(jié)果Fig.4 S-DTA-IIForest anomaly detection results
為量化分析模型的準(zhǔn)確性,在測試集Utest中新增人工標(biāo)定“Label”字段,分為正常值“Normal”和異常值“Outlier”兩種屬性,以AUC、F1-score 指標(biāo)對S-DTA-IIForest、S-DTA-Forest、T-Forest(傳統(tǒng)時間序列)、D-S-Forest、D-S-LOF等5種模型進行對比分析,各指標(biāo)如表1所示。
表1 模型檢測結(jié)果評價Table 1 Detection result evaluation
本文S-DTA-IIForest模型AUC最大,為86.63%;S-DTA-IForest 模型次之,為85.51%;T-IForest 模型AUC 最低,僅為65.42%。F1-score 指標(biāo)方面:S-DTA-IIForest模型最大,為0.89;S-DTA-IForest模型次之,為0.87;T-IForest 模型F1-score 得分最低,僅為0.70。表明經(jīng)過原始時間序列經(jīng)S-DTA 處理后,所構(gòu)建的二維特征向量能增加模型對異常數(shù)據(jù)的辨識能力。此外,S-DTA-IForest模型運行時間為0.1151 s,較S-DTA-IForest模型0.1166 s減少0.0015 s,運行效率提高1.29%,收斂速度明顯提升。
為分析S-DTA-IIForest 模型的參數(shù)適應(yīng)性能力,基于R1 同一數(shù)據(jù)集,對參數(shù)max_samples、n_estimators等不同數(shù)值進行測試。當(dāng)n_estimators為100 時,隨著構(gòu)建子樹的樣本數(shù)max_samples 增大,模型AUC 值出現(xiàn)波動,當(dāng)max_samples 為500時,模型AUC 值最大,運行時間穩(wěn)定在0.116 s 左右,max_samples 的增大并不會帶來運行時間的大幅增長,如圖5(a)所示;當(dāng)max_samples=256 時,隨著孤立樹數(shù)量n_estimators 的增大,初期模型AUC值總體呈增長態(tài)勢,n_estimators 大于100 后其AUC 值基本持平,但運行時間隨著n_estimators 的增大呈線性增長,當(dāng)樣本數(shù)量較大時,模型運行耗時也顯著增加,如圖5(b)所示。因此,建議模型參數(shù)max_samples為500,n_estimators為100。
圖5 模型不同參數(shù)適應(yīng)性分析Fig.5 Adaptability analysis of different parameters in model
(3)不同載客狀態(tài)下異常數(shù)據(jù)檢測分析
利用S-DTA-IIForest 模型篩選出異常值后,浮動車數(shù)據(jù)異常點可分為空值點、突增點、突減點這3類,如序號1083和1084為空值點,呈現(xiàn)單個或多個連續(xù)0 值,實際中多為“null”空值數(shù)據(jù);序號909 為突增點,表現(xiàn)為單個數(shù)據(jù)突然增加,隨后急劇下降;序號1099為突減點,表現(xiàn)為單個數(shù)據(jù)急速下降,隨后明顯增加,具體如圖6所示。
圖6 S-DTA-IIForest模型浮動車異常值識別情況Fig.6 Identification of abnormal values of floating cars in S-DTA-IIForest model
原始FCD 數(shù)據(jù)“載客狀態(tài)”為“0”表示未載客,“1”表示該車輛載客,Utest數(shù)據(jù)集中未載客樣本數(shù)量為56條,占總數(shù)28.0%,載客樣本條數(shù)144條,占72.0%。載客狀態(tài)下,S-DTA-IIForest 模型AUC 為88.72%,較未載客82.35 提高7.7%,F(xiàn)1-score 為0.92,較未載客0.83提高10.8%,可見載客狀態(tài)下模型精度更高,如表2所示。
表2 不同載客狀態(tài)檢測結(jié)果Table 2 Detection results of different passenger carrying states
從異常值分布看,Utest中異常點為10 個,異常率為5.0%,其中載客狀態(tài)異常點為6 個,占60.0%,未載客狀態(tài)異常點為4個,占40.0%,載客狀態(tài)數(shù)據(jù)異常率為4.2%,未載客狀態(tài)數(shù)據(jù)異常率為7.1%,未載客狀態(tài)數(shù)據(jù)異常率較載客狀態(tài)增大71.4%,即未載客狀態(tài)數(shù)據(jù)的異常率更高,如圖7所示。由于本文浮動車為出租車,在未載客時,駕駛員會頻繁接單或時刻觀察沿線是否有潛在顧客,車輛運行狀態(tài)更易受到干擾,數(shù)據(jù)會存在一定波動,因此數(shù)據(jù)異常概率更高。
圖7 不同載客狀態(tài)下異常率分布Fig.7 Anomaly rate distribution under different passenger carrying states
本文主要結(jié)論如下:
(1)構(gòu)建基于集成學(xué)習(xí)的S-DTA-IIForest 檢測模型,利用孤立森林模型全局檢測能力,實現(xiàn)對浮動車異常數(shù)據(jù)檢測,并基于重慶市學(xué)府大道實際案例進行驗證。結(jié)果表明,模型對浮動車異常數(shù)據(jù)精準(zhǔn)度AUC 為86.63%,F(xiàn)1-score 為0.89,整體預(yù)測精度較高,達(dá)到工程實際應(yīng)用水平。
(2)通過S-DTA方法將一維時間序列向二維特征向量轉(zhuǎn)換后,S-DTA-IIForest 模型AUC、F1-score較傳統(tǒng)T-Iforest 分別提高32.4%、26.5%,較D-SIIForest方法分別提高21.9%、17.9%,S-DTA方法更適用于浮動車數(shù)據(jù)集構(gòu)建處理。
(3) 模型參數(shù)方面,n_estimators 為100、max_samples 為500 時,模型接近最佳檢測性能。隨著n_estimators 的增加,模型AUC 值經(jīng)初期增長后趨于穩(wěn)定但運行時間呈線性增長;隨著max_samples的增大,模型AUC值出現(xiàn)波動但運行時間基本持平。
(4) 載客狀態(tài)下,模型AUC、F1-score 分別為88.72%、0.92,較未載客狀態(tài)分別提高7.7%、10.8%,載客狀態(tài)下模型檢測能力較未載客有一定提升,且未載客狀態(tài)數(shù)據(jù)異常率較載客狀態(tài)增大71.4%,未載客狀態(tài)下數(shù)據(jù)異常率更高。