基于凝聚層次的駕駛行為聚類與異常檢測方法

惠 飛,彭 娜,景首才,周 琪,賈 碩

(長安大學 信息工程學院,西安 710064)

0 概述

異常駕駛行為通常指行車速度超過速度限制、駕駛員突然改變速度或不斷地改變車輛側向位置等非平穩(wěn)行為,此類行為是導致交通事故的重要誘因。因此,為交通管理部門提供可靠的異常駕駛檢測方法具有非常重要的實際意義。

目前異常駕駛行為檢測方法主要基于視頻數據和車輛GPS軌跡數據進行研究。文獻[1]利用視頻數據對車輛的軌跡和速度進行分析,在背景差分法的基礎上通過建立跟蹤車輛信息鏈實現對車輛跟蹤和異常行為檢測;文獻[2]利用背景差分法和均值漂移算法獲取車輛位置、速度、方向等判別參數,對3種判別參數的狀態(tài)函數加權融合檢測車輛異常行為;文獻[3]利用GPS提供的位置、時間、速度信息,以車輛正常行駛情況下的縱向和橫向加速度為閾值,檢測和識別駕駛員異常駕駛行為;文獻[4]以大量重特大交通事故數據為基礎,通過聚類分析從危險駕駛行為角度研究外部影響因素與駕駛行為的關系。筆者通過對文獻的分析發(fā)現,目前基于視頻的異常行為檢測,主要針對單車受限場景,難以對運輸全過程進行監(jiān)控[5]。而對GPS的軌跡分析,也以對單車進行先驗閾值判斷為主,大多是設定檢測閾值而觸發(fā)報警,缺乏數據深層次分析與信息挖掘步驟,不具有智能化辨識與特性分析功能。

為此,本文提出一種基于GPS數據的駕駛行為異常檢測方法。首先根據時間、速度、加速度、方向、轉角等全局與局部特征及其對應的13個統計量,構建車輛駕駛行為的特征屬性,然后利用基于結構相似度度量的凝聚層次聚類方法對駕駛行為進行聚類建模,進而實現異常行為檢測。本文方法將測試數據與訓練數據集獲得的模型庫進行對比檢測,無需使用經驗指標來設定各類異常的閾值,從而有效避免人為因素對檢測結果的影響。

1 駕駛行為聚類與異常檢測方法框架

本文對商用車司機異常駕駛行為進行檢測,主要檢測超速、急加速、急減速、違章變道等行為。首先基于文獻[6]提出的全局和局部運動特征分類方法,總結關于車輛運行GPS數據所體現的司機駕駛行為特征,從GPS數據中提取運動特征及其統計量,構建車輛多特征駕駛行為模型,提出基于多特征的駕駛行為聚類與異常檢測方法,方法框架如圖1所示。其中數據準備與預處理為大數據剔除無關噪聲數據基本環(huán)節(jié),本文不再贅述。

圖1 基于多特征駕駛行為聚類的異常檢測方法框架

1.1 駕駛行為多特征提取

1.1.1 全局特征提取

對于位置點數據全局特征的提取,首先根據軌跡數據點的時間信息,提取出數據點發(fā)生的17個全局時間特征,即:“月”(Month,如1月);“日”(Day,如2日);“星期”(Week,星期日到星期六分別為0～6);“周末/周內”(Workday,其屬性為0/1屬性,周內為1,周末為0);“節(jié)假日”(Holiday,其屬性為0/1屬性,法定節(jié)假日為1,法定工作日為0);“時段”(Time,本文將1 d 24 h等間隔劃分為12個one-hot[7-8]時段特征,值為0/1)。在提取全局時間特征后,根據數據點信息提取其他運動參數。

軌跡是一系列連續(xù)GPS點的集合,記T=。其中,每個位置點pi包含位置信息(xi,yi)及時間信息(ti),記pi=。根據GPS數據信息提取兩位置點間的距離di、時間間隔Δti、速度vi、加速度ai、方向directioni、轉角θi以及相關統計量(均值、中值、標準差等)。然后將針對車輛駕駛行為中典型的異常駕駛行為(超速、急加/減速、違章變道)分別進行特征提取。

1.1.2 超速駕駛行為特征提取

通過對兩數據點間的行駛距離、速度和時間間隔分析,能夠實現對超速行為的識別。統計相關超速信息,通過對超速持續(xù)時間以及超速行為之間的間隔距離來判斷是否為違章超速行為,而非如超車等正常超速行為[9]。為判斷超速行為是否為違章超速行為,引入違章超速行駛行為距離判斷閾值ɑ與界定時長δ,按照行業(yè)判定經驗取:

a≥500 m,δ≈30 s

(1)

根據超速行為行駛距離di引入“違章超速”特征值k,k=1表示違章超速,k=0表示未違章超速:

(2)

將市區(qū)內行車速度按其大小值分為4個等級:低速(v≤20 km/h),中速(20 km/h60 km/h),本文根據司機駕駛速度等級提取“低速”“中速”“高速” “超速”4個特征(皆為one-hot特征,即值為0/1,0為否,1為是)。

1.1.3 急加/減速駕駛行為特征提取

在交通運輸行業(yè)相關法規(guī)中,急加/減速行為并不屬于違法違規(guī)行為,但經常性的急加/減速行為對制動系統及系統部件都有損害,并且急加/減速行為發(fā)生次數也是判斷司機開車是否平穩(wěn)的標準之一,對駕駛安全也有一定程度的影響。因此,在全局運動特征提取的基礎上,根據點pi、pi+1間速度vi、vi+1和時間間隔Δti計算點pi+1的加速度值,Δti要求不大于2 s,如式(3)所示。若Δti過長,則無意義。

(3)

查閱司機駕駛行為“急加/減速”判定標準,將加速度按其大小值分為4個標準等級:一級標準(ai≥2.78 m/s2,持續(xù)時間≥2 s),二級標準(2.22 m/s2≤a<2.78 m/s2,持續(xù)時間≥2 s),三級標準(1.67 m/s2≤a<2.22 m/s2，持續(xù)時間≥2 s),四級標準(ai<1.67 m/s2,持續(xù)時間≥2 s)。因此,本文根據加速度等級增加4個one-hot特征。

根據2個數據點pi與pi+1速度差值的正負判斷位置點處于加速或是減速,提取“加速/減速”特征,并根據2個數據點pi與pi+1之間的時間間隔Δti,增加“加速度持續(xù)時間”特征。

1.1.4 變道駕駛行為特征提取

在變道過程中,高速行駛狀態(tài)下的車輛轉向角度是很小的。因此,在提取出數據點全局特征的基礎上,還需計算出2個數據點之間行駛路線的彎曲程度和轉角。其中曲率si為兩位置點pi與pi+1之間的移動距離與其直線距離之比,表示兩點之間路徑的彎曲度,如式(4)所示。

si=(dist(pi-1,pi)+dist(pi,pi+1))/dist(pi-1,pi+1)

(4)

位置點的方向由數據集提供,表示每個位置點在當前位置從正北方向順時針旋轉的角度Δθi。轉角Δθi指連續(xù)2個位置點間方向轉動角度,根據兩點各自的方向信息θi與θi+1進行差值計算所得,如式(5)所示。

Δθi=|θi+1-θi|

(5)

兩位置點的方向與轉角示例圖如圖2所示。

圖2 位置點P1與P2的方向與轉角示例

根據一條軌跡為t=中所含軌跡點數n,統計其在一條行駛軌跡中車輛變道次數m并增加“變道次數”特征。對于是否未違章變道行為,將根據車輛連續(xù)變道次數m引入“違章變道”特征。根據行業(yè)經驗,設定連續(xù)變道次數大于3次判定為違章變道。

1.1.5 各特征統計量計算

在已有的距離、速度、加速度、曲率、轉角5個全局運動特征的基礎上,分別計算其對應的13個數學統計量:均值,中值,標準差,變異系數,最大3個數,最小3個數,自相關系數,偏度系數和峰度系數。其中,用變異系數來衡量數據的離散程度。計算最大/最小的3個數[10]是為了考慮定位系統獲取的GPS數據存在定位精度和誤差的因素。偏度系數和峰度系數用來分別衡量統計分布的左右對稱性和形狀的陡峭程度[11]。自相關系數是用來度量2個位置點在時間上的相關程度[12]。一條軌跡的時間序列可表示為xt∈{x1,x2,…,xn},為計算其自相關系數,可先用式(6)計算自協方差系數{ck},其中,k為時滯長度,N為序列長度。再利用式(7)計算時滯為1時的自相關系數。

(6)

r1=c1/c0

(7)

偏度系數與峰度系數的計算可參考文獻[11]。最后,對5個全局運動特征分別計算其對應13個統計量。圖3顯示了部分運動特征及其統計量結果。

圖3 部分運動特征及其統計量

1.2 基于結構距離的相似度度量方式

當檢測目標為運動位置點表現出的駕駛行為的異常情況時,不能直接采用常用的軌跡之間的相似度度量方式[13-14]。本文借鑒圖像質量評價中的結構相似度(Structural Similarity,SSIM)[15]思想,采用SSIM方法來度量數據點駕駛行為特征之間的距離。

結構距離(Structure Distance,SDist)指對軌跡結構各個特征屬性分別采取不同的距離計算方式來計算,最后結合為一個距離計算標準。本文數據點包含6個全局特征,其軌跡結構為pi=,各異常行為特征中還包含一些one-hot特征。因此,數據點結構距離共包含7個部分:時間距離timeDist,位置距離locDist,速度距離speedDist,加速度距離accDist,曲率距離curDist,轉角距離angleDist以及one-hot特征距離Dist。

定義W={Wt,Wv,Wd,Wa,Ws,Wθ,Wo}為各部分特征權重向量,分別對應軌跡的特征向量。通過這7個部分的距離構成了軌跡相似度的計算,如式(8)所示。其中,時間距離采用余弦相似度度量方式計算。位置距離采用歐氏距離計算。速度和加速度均采取各統計量和的平均。曲率和轉角均采用差的絕對值衡量。

SDist(pi,pj)=Wa×timeDist+Wv×speedDist+

Wd×locDis+Wa×accDist+

Ws×curDist+Wθ×

angleDist+Wo×Dist

(8)

由于軌跡中每個特征的值域不同,需要對結構距離進行歸一化處理,如式(9)所示,其中Normalized()為距離的歸一化函數。因為兩點間的結構相似度是對稱的,所以SSIM(pi,pj)=SSIM(pj,pi)。

SSIM(pi,pj)=1-Normalized(SDist(pi,pj))

(9)

下文將針對超速、急加/減速、急剎車、違章變道等典型異常駕駛行為,在已有的全局和局部特征以及相似度度量方式的基礎上,分別進行凝聚層次聚類與異常檢測。

2 基于多特征的聚類與異常檢測

2.1 基于多特征的凝聚層次聚類算法

聚類是將抽象的數據集劃分成由相似數據構成的若干個對象集或者簇,使數據對象在同一簇中相似度越大,類間相似度越小,聚類效果就越好。聚類分析是異常行為檢測的基礎,在傳統的基于聚類的異常點檢測方法中,對象是否被檢測為離群點很大程度依賴于簇的個數[16]。聚類算法中有部分算法需設定初始聚類中心和聚類數目,不能自動確定簇的個數,聚類結果不穩(wěn)定。

凝聚層次聚類算法具有聚類準確率高、聚類結果穩(wěn)定的優(yōu)點,無需選取初始聚類中心和設定任何參數。但其計算復雜度大,為了降低復雜度,自動確定聚類數目,本文在層次聚類方法中引入拉普拉斯特征映射思想自動確定聚類簇數。

2.1.1 拉普拉斯特征映射

步驟1通過特征相似矩陣Sn×n構造拉普拉斯特征矩陣Ln×n=D-1/2Sn×nD-1/2,其中矩陣D為由矩陣S獲得的對角矩陣。

步驟2對Ln×n矩陣進行特征值分解并按降序排列λ1≥λ2≥…≥λn;計算相鄰特征值之差,若第i個特征值和第i+1個特征值之間差異最大,則確定聚類個數k=argmax|λi+1-λi|。

步驟3構造m×k矩陣Lm×k=[l1,l2,…,lk],其中l(wèi)k為矩陣Ln×n的前k個特征值對應的特征向量;然后對Lm×k矩陣進行歸一化處理,得到矩陣X=[x1,x2,…,xm]后再對低維數據xi進行后續(xù)聚類。

2.1.2 凝聚層次聚類

在對特征矩陣進行拉普拉斯變換后,根據降維后的特征矩陣及聚類數進行最后的層次聚類?；谀鄣膶哟尉垲愃惴ǖ膫未a如下:

算法CURE層次聚類

輸入數據集D={p1,p2,…,pn}

輸出k個聚類簇及質心

1.3.3 患兒治療依從性評價 由于哮喘患兒是特殊群體，其對于治療的依從性是針對于家屬，臨床藥師對實驗組患兒家屬在1年時間內，每個月評估其治療的依從性，以能夠穩(wěn)定持續(xù)用藥為較好，以分值5分表示；以雖未能持續(xù)穩(wěn)定進行藥物治療，但對于疾病控制仍存在相應的重視及治療為一般，以分值3-4分表示；對于用藥治療頻率較低，完全不能按照療程進行治療為較差，以分值1-2分表示。

1.對數據集建立點與點之間的距離矩陣Sn×n。

2.根據上述步驟1～步驟3,得到低維數據矩陣X及其聚類個數k。

3.loop

4.將每個對象歸為一類,得到n類,每類包含一個對象。

5.將距離矩陣Sn×n中的值升序排列,選取最小距離的2個類合并為一個類。

6.重新計算新類與舊類之間的距離。

7.重復前三步,直到最后合并成一個類或達到設定條件則退出循環(huán)。

8.輸出k個聚類簇及其質心。

2.2 基于類標記的異常檢測算法

正常駕駛行為有較高的重復性和相似性特點,而異常駕駛行為相較正常駕駛行為可能因不同場景和交通狀況而表現出不同,與正常模式匹配存在很大的差距。在聚類結果中,有些簇的規(guī)?？赡芎苄?在無法區(qū)分噪音和離群點下,本文將這些簇標記為異常。由上一節(jié)的聚類簇結果,在設定參數α的條件下,根據閾值標記簇為正?；虍惓４?再將待測點與簇進行對比檢測。

2.2.1 簇結果標記

文獻[18]定義了大小簇的概念,假設C={c1,c2,…,ck}為簇集,簇成員個數記為|ci|,將其按成員數目降序排序得到{|c1|>|c2|>…>|ck|};給定參數α,當|c1|+|c2|+…+|cb|≥αn(n為原始數據集數目)時,則定義b(1≤b≤k-1)為大簇LC與小簇SC的邊界。那么,可以將簇標記為大簇LC={ci|i≤b}與小簇SC={ci|i≥b},并將ci(i≤b)標記為正常簇,ci(i≥b)標記為異簇。計算大小簇邊界的算法偽代碼如下:

算法計算大小簇邊界

輸入聚類簇及簇內數據,參數α

輸出簇邊界b

1.計算各簇ci的成員個數|ci|(i=1,2,…,k),并對|ci|按降序排序,設置參數α

2.for(i=1;i≤k;i++)

5.記錄大小簇邊界b并跳出循環(huán)

6.end for

2.2.2 異常檢測算法

假設某車輛的一條軌跡數據為t={p1,p2,…,pm},m指該軌跡長度。計算每個點pi與所有簇之間的距離dist(pi,cj)并找到距離最小的dist(pi,cmin)。若dist(pi,cmin)大于簇半徑R,則將該位置點標記為未知屬性點,重新計算簇半徑,將R′記為新的簇半徑;否則找出簇cmin所屬簇的標記,若標記為正常則點pi為正常點;若標記為異常則點pi為異常點。

3 實驗與結果分析

3.1 實驗環(huán)境設置與數據準備

實驗環(huán)境:Windows10操作系統,Intel Xeon 2.50 GHz CPU,16.0 GB內存。開發(fā)環(huán)境:Microsoft Visual Studio 2008,Matlab12,Anaconda2.0。采用Matlab統計學工具箱計算方向和轉角的統計量,其他特征采用python計算,并采用python語言對數據點進行聚類分類及后續(xù)異常檢測。

實驗數據采用真實的西安市2016年的商用車運行GPS數據,包括時間、經度、緯度、速度、方向等信息。實驗選取經度在lon∈[108.7,109.2]、緯度在lat∈[34.1,34.5]范圍的西安市區(qū)內數據,共包含59 999個軌跡點即4 953條軌跡,實驗中將2/3的數據作為訓練數據集,其余數據為用以驗證與調 整聚類模型準確率及其他性能的驗證數據集。

3.2 結果分析

3.2.1 聚類結果

圖4所示為本文基于多特征凝聚層次聚類結果與文獻[19]中基于因子分析的駕駛行駛聚類結果對比。其中用黑色實線框標出兩處聚類細節(jié),可以看出圖4(a)中將一段道路上的GPS數據點聚類為同一類簇,而在圖4(b)中更細致地區(qū)分了軌跡點之間的差異。

圖4 文獻[19]方法與本文方法聚類結果對比

對于本文采用的聚類算法,針對超速駕駛行為從聚類準確率與算法執(zhí)行時間2個性能上,與文獻[19]中的基于多特征的兩層聚類算法進行比較,比較結果如圖5所示,其中聚類準確率采取將聚類結果與手動標記的245個數據點進行比較的方式計算。

聚類準確率評估結果如圖5(a)所示,從中可以看出,聚類準確率隨著軌跡數據規(guī)模的增大而增大。當軌跡數目達到800左右,軌跡點數為9 948時,2種方法的聚類準確率趨于穩(wěn)定,本文方法的聚類準確率在95%左右,文獻[19]的聚類準確率在88%左右。由實驗結果可知,本文的聚類算法與文獻[19]采用的方法比較在聚類準確率上有一定的提高。由于本文方法同時采用了數據點的時間全局特征、兩點間行駛距離、速度大小、速度行業(yè)設定等級、是否違章超速及其統計量等與速度相關的完備因素來衡量駕駛行為間的相似度,更好地提取數據點聚類的特征工程。

執(zhí)行效率評估結果如圖5(b)所示,從中可以看出,隨著軌跡數據量的增大,本文方法在聚類效率上的優(yōu)勢就越加明顯。當軌跡數目達到1 000條時,本文方法的聚類時間減少了24%左右。這是因為本文方法在數據點聚類前將數據劃分到多個網格區(qū)域,后期同步執(zhí)行聚類算法,且在計算數據點間的相似度時引入譜聚類中的拉普拉斯映射思想,降低聚類數據集的維數并能自動確定聚類數目。因此,本文方法相比文獻[19]方法在聚類準確率和效率上有一定程度的提高。

圖5 聚類算法性能對比

3.2.2 異常駕駛行為檢測結果

圖6所示為驗證數據集中針對超速駕駛行為異常檢測結果。其中,灰色點是表現為正常的數據點,“×”為檢測出的異常點。實驗數據采用訓練數據集與驗證數據集生成的聚類簇作為模型庫。對于測試數據集,由于不能采集到及時的商用車GPS數據,因此采取在測試車輛上安裝GPS定位器的方法采集人為的異常駕駛數據,包括超速、急加/減速、突然左/右變道等幾項駕駛異常行為。實驗中讓3位志愿者司機共做了20次超速駕駛、40次變速駕駛(包括加速/減速)、20次變道,其余100次為正常行駛實驗,共2 000個數據點。

圖6 驗證數據集檢測結果示例

將本文方法與文獻[20]基于各類異常指標的駕駛行為異常檢測方法進行對比,實驗結果如表1所示,其中,M1指檢測為異常駕行為的數目,M2為正確檢測為異常駕駛行為的數目。從中可以看出,本文方法的平均檢測準確率高于文獻[20]中提出的基于各類異常指標的異常檢測方法。因為文獻[20]采用的異常檢測方法是根據已有的一些經驗指標來設定各類異常的閾值,對數據的測試有很強的人為主觀因素。而本文方法的檢測結果是將待測數據集與基于訓練數據集和驗證數據集獲得的模型庫進行比較獲得,在對數據集進行訓練時是基于提取的各類全局與局部運動特征以及相關統計量等因素,將 “多且相似”的正常的駕駛行為都將歸為一個簇,而訓練中的異常數據也將歸為異常簇,因此,測試時不受人為客觀因素的影響,檢測準確率更高。

表1 檢測準確性對比

4 結束語

基于GPS數據挖掘,本文針對商用車司機5種典型的異常駕駛行為進行檢測。在最大化提取每個位置點駕駛行為特征的基礎上,采用基于聚類的異常檢測方法使準確率和效率得到提升,且異常檢測準確率相比傳統設定閾值的方法更高。但本文對算法的檢測性能分析是建立在實驗采集的異常數據集上,不包含商用車司機駕駛車輛時的一些實際信息,使檢測準確率受到影響,下一步將對此進行改進。