基于加權極限學習機的異常軌跡檢測算法

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

（1.河海大學物聯網工程學院，常州213022；2.江蘇省輸配電重點實驗室，常州213022）

基于加權極限學習機的異常軌跡檢測算法

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

（1.河海大學物聯網工程學院，常州213022；2.江蘇省輸配電重點實驗室，常州213022）

針對現有異常軌跡檢測中分類不平衡造成難以確定最優分類面的問題，提出一種基于加權極限學習機（ELM，Extreme Learning Machine）的異常軌跡檢測算法。該算法采用加權ELM克服軌跡數據不平衡造成的分類面偏移，通過對正、負兩類樣本合理分配權重，并構造最優分類面獲得較好的異常檢測效果。仿真實驗表明，加權ELM算法在訓練速度，準確率，整體性能等方面均優于傳統SVM和BP網絡分類方法。

異常檢測；跡軌分析；極限學習機

1 引 言

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

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

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

極限學習機（the extreme learning machine，ELM）是一種較新的機器學習方法，相比較傳統的分類器，如支持向量機（SVM），BP神經網絡等，具有更快的學習及更好的分類性能［7］。從軌跡（樣本）數據的不平衡性出發，提出了一種基于加權極限學習機的異常軌跡檢測算法，并能自適應分配權重。最后通過與其它方法的比較和分析，表明了該算法的準確性和優越性。

2 ELM算法原理

極限學習采用單隱層前饋神經網絡（SLFN）框架，給定N個訓練樣本（xi，ti），含有L個節點的標準SLFN模型可以表示為

式中G（x）為隱層節點的激活函數，βi為第i個節點與所連接輸出神經元的輸出權值，（ai，bi）為第i個輸入神經元的輸入權值和偏置，Oj為第j個輸出神經元的實際輸出值。

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

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

其中隱層輸出矩陣為

不同于BP神經網絡，在訓練過程中極限學習機的初始權值隨機設置不需要調整，只需解出輸出權值最小二乘范數解即可。而根據Bartlett的理論［8］，前饋神經網絡的輸出權值范數越小，網絡的泛化性越好。因此需要在最小化輸出權值和最小化誤差之間做出折中，則構造如下公式

類似最小二乘支持向量機，該最優化問題可用公式表示成

其中ζi＝［ζi，1，...，ζi，m］T是訓練樣本xi在第m個輸出節點的輸出值與真實值之間的誤差向量。而C為正則化參數，它是用來權衡經驗風險和結構風險的懲罰因子，可以通過設置來防止過擬合，達到更好的分類效果。

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

綜上可知，ELM算法的訓練步驟為：

Step1：隨機設置輸入權值和偏置（ai，bi）i＝1，...，N

Step2：計算隱層輸出矩陣H

3 加權ELM的異常檢測

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

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

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

其中αi為lagrange乘數，且都是非負數。相應的KKT優化限制條件為

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

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

T為總樣本個數，posx為正樣本個數，權值矩陣W計算的偽代碼如下

4 實驗與分析

4.1 數據集描述

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

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

4.2 仿真軌跡實驗

圖1顯示了在一次人工軌跡數據上的實驗結果。首先分別產生260個訓練樣本和260個測試樣本，訓練集和測試集包含250條正常軌跡和10條異常軌跡，正常軌跡分為5個類別。采用帶有權值的極限學習機，普通的無權極限學習機，SVDD算法和BP網絡算法分別進行識別，識別結果如圖1所示。

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

表1給出了該算法在不同軌跡數據集上的測試結果，并與其他算法的檢驗結果進行了對比。從表中可以看出，對于異常軌跡檢測這種不平衡數據的檢測識別，采用了加權算法的效果要明顯好于其他傳統分類算法。

表1 加權ELM和SVDD、BP網絡在幾種異常軌跡的檢測中準確率對比

4.3 真實視頻數據實驗

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

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

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

圖1 各種算法效果比較

圖2 軌跡數據

圖3 加權ELM與普通ELM的效果比較

5 結論

異常軌跡檢測對智能化事件分析具有重要的意義。該算法將加權極限學習機算法引入了軌跡分類中，通過對權值的合理分配，克服傳統分類器中構造分類面偏移的缺點。最后通過人工數據和真實數據的對比測試，驗證了該算法的有效性和優越性，具有一定的潛在應用價值。

［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，FAN 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