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

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

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

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

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

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

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

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

1 引 言

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

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

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

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

2 ELM算法原理

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

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

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

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

其中隱層輸出矩陣為

不同于BP神經(jīng)網(wǎng)絡(luò)，在訓(xùn)練過(guò)程中極限學(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)造如下公式

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

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

由隱層輸出矩陣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的異常檢測(cè)

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

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

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

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

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

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

T為總樣本個(gè)數(shù)，posx為正樣本個(gè)數(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］來(lái)創(chuàng)建仿真軌跡數(shù)據(jù)集。軌跡數(shù)據(jù)分為訓(xùn)練集和測(cè)試集，每個(gè)數(shù)據(jù)集包含正常軌跡和異常軌跡：如260條軌跡中，250條正常軌跡可分為5類(lèi)，另10條為異常軌跡。每條軌跡由空間特征點(diǎn)組成，坐標(biāo)作為特征向量值，以形式αi＝［x（1），...，x（trlen），y（1），...，y（trlen）］存儲(chǔ)，trlen表示軌跡長(zhǎng)度，這里選取16個(gè)采樣點(diǎn)。

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

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

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

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

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

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

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

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

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

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

圖1 各種算法效果比較

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

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

5 結(jié)論

異常軌跡檢測(cè)對(duì)智能化事件分析具有重要的意義。該算法將加權(quán)極限學(xué)習(xí)機(jī)算法引入了軌跡分類(lèi)中，通過(guò)對(duì)權(quán)值的合理分配，克服傳統(tǒng)分類(lèi)器中構(gòu)造分類(lèi)面偏移的缺點(diǎn)。最后通過(guò)人工數(shù)據(jù)和真實(shí)數(shù)據(jù)的對(duì)比測(cè)試，驗(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