基于加權(quán)極限學(xué)習(xí)機(jī)的異常軌跡檢測算法

李威龍，范新南，2，李 敏，鄭併斌

（1.河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院，常州213022；2.江蘇省輸配電重點(diǎn)實(shí)驗(yàn)室，常州213022）

基于加權(quán)極限學(xué)習(xí)機(jī)的異常軌跡檢測算法

李威龍1，范新南1，2，李 敏1，鄭併斌1

（1.河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院，常州213022；2.江蘇省輸配電重點(diǎn)實(shí)驗(yàn)室，常州213022）

針對現(xiàn)有異常軌跡檢測中分類不平衡造成難以確定最優(yōu)分類面的問題，提出一種基于加權(quán)極限學(xué)習(xí)機(jī)（ELM，Extreme Learning Machine）的異常軌跡檢測算法。該算法采用加權(quán)ELM克服軌跡數(shù)據(jù)不平衡造成的分類面偏移，通過對正、負(fù)兩類樣本合理分配權(quán)重，并構(gòu)造最優(yōu)分類面獲得較好的異常檢測效果。仿真實(shí)驗(yàn)表明，加權(quán)ELM算法在訓(xùn)練速度，準(zhǔn)確率，整體性能等方面均優(yōu)于傳統(tǒng)SVM和BP網(wǎng)絡(luò)分類方法。

異常檢測；跡軌分析；極限學(xué)習(xí)機(jī)

1 引 言

目前，基于軌跡的異常事件分析已成為一個令人關(guān)注的研究課題，針對異常軌跡檢測，傳統(tǒng)分類器和相似性度量的方法被許多學(xué)者應(yīng)用。較早的有Johnson等［1］采用矢量量化（VQ）表示軌跡和多層神經(jīng)網(wǎng)絡(luò)識別分類的方法；Stauffer等［2］將量化后的軌跡矢量依據(jù)同現(xiàn)矩陣分析進(jìn)行分類。近年來，Lee等［3］提出TRAOD（TRAjectory Outlier Detection）算法，軌跡分段表示作為局部特征，并使用Hausdorff距離的不匹配性分離異常軌跡。Claudio Piciarelli等［4］提出采用（單）一類支持向量機(jī)的無監(jiān)督學(xué)習(xí)方法實(shí)現(xiàn)異常軌跡的檢測，獲得較好的檢驗(yàn)準(zhǔn)確度。還有Li等［5］使用分類器的思想，提出基于motifs模塊化的異常檢測算法，獲得了較好的泛化能力。

通常異常軌跡檢測研究中所需解決的基本問題是，如何在大量復(fù)雜軌跡數(shù)據(jù)中找出少量具有異常特征的軌跡。然而異常軌跡特征具有時空稀疏性以及復(fù)雜性（通常表現(xiàn)為高維特征）的特點(diǎn)，容易導(dǎo)致算法復(fù)雜度增加、檢測結(jié)果準(zhǔn)確性和魯棒性降低等問題［6］。

傳統(tǒng)分類器對所有樣本均賦予固定的正則化參數(shù)C，這表示對正負(fù)樣本的決策分配相同的權(quán)重。然而對于非平衡數(shù)據(jù)的處理，如包含極少異常的大量軌跡數(shù)據(jù)，則是一個典型的不平衡分類問題，極易導(dǎo)致分類曲面的偏移或者過擬合現(xiàn)象，因而無法取得較好的分類（識別）效果。

極限學(xué)習(xí)機(jī)（the extreme learning machine，ELM）是一種較新的機(jī)器學(xué)習(xí)方法，相比較傳統(tǒng)的分類器，如支持向量機(jī)（SVM），BP神經(jīng)網(wǎng)絡(luò)等，具有更快的學(xué)習(xí)及更好的分類性能［7］。從軌跡（樣本）數(shù)據(jù)的不平衡性出發(fā)，提出了一種基于加權(quán)極限學(xué)習(xí)機(jī)的異常軌跡檢測算法，并能自適應(yīng)分配權(quán)重。最后通過與其它方法的比較和分析，表明了該算法的準(zhǔn)確性和優(yōu)越性。

2 ELM算法原理

極限學(xué)習(xí)采用單隱層前饋神經(jīng)網(wǎng)絡(luò)（SLFN）框架，給定N個訓(xùn)練樣本（xi，ti），含有L個節(jié)點(diǎn)的標(biāo)準(zhǔn)SLFN模型可以表示為

式中G（x）為隱層節(jié)點(diǎn)的激活函數(shù)，βi為第i個節(jié)點(diǎn)與所連接輸出神經(jīng)元的輸出權(quán)值，（ai，bi）為第i個輸入神經(jīng)元的輸入權(quán)值和偏置，Oj為第j個輸出神經(jīng)元的實(shí)際輸出值。

存在一個（ai，bi）和βi，有，使得該SLFN模型可以零誤差逼近樣本集｛（xi，ti），i＝1，...，N｝，即

公式（2）可以合并成為下面矩陣式

其中隱層輸出矩陣為

不同于BP神經(jīng)網(wǎng)絡(luò)，在訓(xùn)練過程中極限學(xué)習(xí)機(jī)的初始權(quán)值隨機(jī)設(shè)置不需要調(diào)整，只需解出輸出權(quán)值最小二乘范數(shù)解即可。而根據(jù)Bartlett的理論［8］，前饋神經(jīng)網(wǎng)絡(luò)的輸出權(quán)值范數(shù)越小，網(wǎng)絡(luò)的泛化性越好。因此需要在最小化輸出權(quán)值和最小化誤差之間做出折中，則構(gòu)造如下公式

類似最小二乘支持向量機(jī)，該最優(yōu)化問題可用公式表示成

其中ζi＝［ζi，1，...，ζi，m］T是訓(xùn)練樣本xi在第m個輸出節(jié)點(diǎn)的輸出值與真實(shí)值之間的誤差向量。而C為正則化參數(shù)，它是用來權(quán)衡經(jīng)驗(yàn)風(fēng)險(xiǎn)和結(jié)構(gòu)風(fēng)險(xiǎn)的懲罰因子，可以通過設(shè)置來防止過擬合，達(dá)到更好的分類效果。

由隱層輸出矩陣H的Moore-Penrose廣義逆矩陣Hτ，可得解，其中T＝［ti，...，tN］。

綜上可知，ELM算法的訓(xùn)練步驟為：

Step1：隨機(jī)設(shè)置輸入權(quán)值和偏置（ai，bi）i＝1，...，N

Step2：計(jì)算隱層輸出矩陣H

3 加權(quán)ELM的異常檢測

這里提出一種基于加權(quán)（極限學(xué)習(xí)）的改進(jìn)方法，對于不平衡的兩類樣本給予不同的權(quán)值W，于是極限學(xué)習(xí)機(jī)算法的求解公式（6）就變成了如下形式

其中W是定義的一個N×N對角矩陣，每一個主對角元素wii都對應(yīng)著一個樣本xi，不同類別的樣本將會自動分配不同的權(quán)值。

根據(jù)KKT條件，可以定義lagrange函數(shù)求解該二次規(guī)劃問題，則等效為求解下面的公式：

其中αi為lagrange乘數(shù)，且都是非負(fù)數(shù)。相應(yīng)的KKT優(yōu)化限制條件為

對于異常檢測，屬于二分類問題，ELM只需要一個輸出節(jié)點(diǎn)，則決策函數(shù)為f（x）＝sign（h（x）β），即：

此外，權(quán)值矩陣W＝diag｛wii｝，i＝1，...，N的計(jì)算在該加權(quán)ELM中十分重要，它直接影響了最后的分類效果。這里在考慮計(jì)算復(fù)雜度和分類效果的同時，對軌跡異常檢測選擇了一種簡單有效的方法，就是根據(jù)兩類樣本的數(shù)量比來分配不同的權(quán)值。

T為總樣本個數(shù)，posx為正樣本個數(shù)，權(quán)值矩陣W計(jì)算的偽代碼如下

4 實(shí)驗(yàn)與分析

4.1 數(shù)據(jù)集描述

為了驗(yàn)證該算法的有效性，以仿真軌跡數(shù)據(jù)與真實(shí)視頻數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)。首先，選用AVIRES Lab的軌跡生成器［9］來創(chuàng)建仿真軌跡數(shù)據(jù)集。軌跡數(shù)據(jù)分為訓(xùn)練集和測試集，每個數(shù)據(jù)集包含正常軌跡和異常軌跡：如260條軌跡中，250條正常軌跡可分為5類，另10條為異常軌跡。每條軌跡由空間特征點(diǎn)組成，坐標(biāo)作為特征向量值，以形式αi＝［x（1），...，x（trlen），y（1），...，y（trlen）］存儲，trlen表示軌跡長度，這里選取16個采樣點(diǎn)。

真實(shí)視頻來自Central Florida大學(xué)的KNIGHT目標(biāo)跟蹤監(jiān)控系統(tǒng)［10］。訓(xùn)練集的數(shù)據(jù)從183mins的實(shí)時監(jiān)控視頻中獲取，共997條軌跡。測試集截取了其中15mins的視頻信息，共287條軌跡。視頻中記錄了所有移動目標(biāo)的軌跡，包含如行人橫穿馬路，踩踏草坪，測試人員曲線行走等異常軌跡信息。每條軌跡都是等時隙采樣，以空間坐標(biāo)向量的形式存儲。

4.2 仿真軌跡實(shí)驗(yàn)

圖1顯示了在一次人工軌跡數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果。首先分別產(chǎn)生260個訓(xùn)練樣本和260個測試樣本，訓(xùn)練集和測試集包含250條正常軌跡和10條異常軌跡，正常軌跡分為5個類別。采用帶有權(quán)值的極限學(xué)習(xí)機(jī)，普通的無權(quán)極限學(xué)習(xí)機(jī)，SVDD算法和BP網(wǎng)絡(luò)算法分別進(jìn)行識別，識別結(jié)果如圖1所示。

圖1中灰色表示正常軌跡，大致可看出分成5簇，代表5類正常軌跡集合，黑實(shí)線表示正確識別的異常軌跡，黑虛線表示被錯誤識別為正常的異常軌跡（漏檢軌跡）。從中可以看出，采用了加權(quán)極限學(xué)習(xí)機(jī)（ELM）算法進(jìn)行檢測，異常軌跡全部被正確的檢測出來，而采用其他算法進(jìn)行檢測分別都有誤判，與正常軌跡較為接近的異常軌跡被錯誤識別為正常軌跡，表明了分類面偏移造成不理想的結(jié)果。

表1給出了該算法在不同軌跡數(shù)據(jù)集上的測試結(jié)果，并與其他算法的檢驗(yàn)結(jié)果進(jìn)行了對比。從表中可以看出，對于異常軌跡檢測這種不平衡數(shù)據(jù)的檢測識別，采用了加權(quán)算法的效果要明顯好于其他傳統(tǒng)分類算法。

表1 加權(quán)ELM和SVDD、BP網(wǎng)絡(luò)在幾種異常軌跡的檢測中準(zhǔn)確率對比

4.3 真實(shí)視頻數(shù)據(jù)實(shí)驗(yàn)

以上仿真軌跡數(shù)據(jù)實(shí)驗(yàn)表明了此算法的優(yōu)越性，下面通過對真實(shí)視頻數(shù)據(jù)的檢測驗(yàn)證該算法的有效性。測試數(shù)據(jù)集如圖2所示，分為訓(xùn)練集和測試集，在固定監(jiān)控場景下，所有樣本軌跡用青色表示。

對于真實(shí)軌跡的實(shí)驗(yàn)，為了后續(xù)異常檢測的效果，一般需要對原始軌跡數(shù)據(jù)進(jìn)行預(yù)處理。首先采用等距映射（Isomap）算法提取軌跡中的有用信息，將軌跡的尺寸進(jìn)行規(guī)范化處理，給與分類器一個合適的輸入空間。然后將提煉后的數(shù)據(jù)集進(jìn)行訓(xùn)練，分別采用帶有權(quán)值的極限學(xué)習(xí)機(jī)和普通的無權(quán)極限學(xué)習(xí)機(jī)進(jìn)行識別比較。

如圖3所示，灰色表示正常軌跡，黑實(shí)線表示識別出的異常軌跡，黑虛線表示被誤判為異常的正常軌跡。結(jié)果表明該算法不僅可以識別出明顯偏離正常運(yùn)動規(guī)律的異常軌跡，而且還可以挖掘出具有一定隱蔽性、局部偏離正常的異常軌跡。因此，加權(quán)ELM對于異常檢測具有一定的現(xiàn)實(shí)意義。

圖1 各種算法效果比較

圖2 軌跡數(shù)據(jù)

圖3 加權(quán)ELM與普通ELM的效果比較

5 結(jié)論

異常軌跡檢測對智能化事件分析具有重要的意義。該算法將加權(quán)極限學(xué)習(xí)機(jī)算法引入了軌跡分類中，通過對權(quán)值的合理分配，克服傳統(tǒng)分類器中構(gòu)造分類面偏移的缺點(diǎn)。最后通過人工數(shù)據(jù)和真實(shí)數(shù)據(jù)的對比測試，驗(yàn)證了該算法的有效性和優(yōu)越性，具有一定的潛在應(yīng)用價(jià)值。

［1］N Johnson，D Hogg.Learning the distribution of object trajectories for event recognition［J］.Image Vis.Comput.，1996，14（8）：609-615.

［2］C Stauffer，W Grimson.Learning patterns of activity using realtime tracking［J］.IEEE Trans on Pattern Anal.Mach.Intell.，2000，22（8）：852-872.

［3］JG Lee，J Han，X Li.Trajectory Outlier Detection：A Partition-and-Detect Framework［C］.Proc.of the 2008 IEEE 24th Intl.Conf.on Data Engineering（ICDE），2008：140-149.

［4］C Piciarelli，Christian Micheloni，Gian Luca Foresti. Trajectory-Based Anomalous Event Detection［J］.IEEE Trans on Circuits And Systems For Video Technology，Novernber，2008，18（11）：1544-1554.

［5］X Li，JHan，S Kim.Motion-Alert：Automatic Anomaly Detection in Massive Moving Objects［C］.Proc.of the 4th IEEE Intl.Conf.on Intelligence and Security Informatics（ISI），2006：166-177.

［6］M Gupta，Jing Gao，Charu C.Aggarwal and Jiawei Han.Outlier Detection for Temporal Data：A Survey［J］.IEEE Trans on Knowledge And Data Engeering，January，2013，25（1）：1-20.

［7］Huang G B，Zhou H，Ding X，et al.Extreme learning machine for regression and multiclass classification［J］.Systems，Man and Cybernetics，Part B：Cybernetics，IEEE Transactions on，2012，42（2）：513-529.

［8］P L Bartlett.The Sample Complexity of Pattern Classification with Neural Networks：The Size of the Weights is More Important than the Size of the Network［J］.IEEE Trans on Information Theory，1998，42（2）：525-536.

［9］Claudio Piciarelli.Matlab Trajectory Generator［DB／OL］.Available：http：／／avires.dimi.uniud.it／papers／trclust.

［10］Arslan Basharat.Tracking Dataset［DB／OL］.Available：http：／／eecs.ucf.edu／～arslan／surveillance.

Trajectory Outliers Detection Algorithm Based on Weighted ELM

LIWei-long1，F(xiàn)AN Xin-nan1，2，LIMin1，ZHENG Bing-bin1
（1.College of Internet of Things Engineering，Hohai University，Changzhou 213022，China；2.Jiangsu Key Laboratory for Power Transmission and Distribution，Changzhou 213022，China）

It is difficult to find the optimal separating hyperplane caused by imbalance classification of the existing trajectory outlier detection algorithm，this paper proposes an algorithm to detect trajectory outliers bymeans ofweighted extreme learningmachine（ELM）.This algorithm adopts theweighted ELM to overcome the offset of separating hyperplane.Firstly，proper weight is set for positive and negative samples adaptively，and then the optimal separating hyperplane is constructed to get better effect for abnormal detection.The results of simulation experiments show that，in training speed，accuracy and overall performance，the weighted ELM algorithm is better than the traditional SVM and BP network classification method.

Outliers detection；Trajectory analysis；Extreme Learning Machine

10.3969／j.issn.1002-2279.2014.01.021

TP391

：A

：1002-2279（2014）01-0076-04

李威龍（1987-），男，江蘇高淳人，碩士研究生，主研方向：信息獲取與處理。

2013-11-05