一種改進(jìn)聚類算法的時(shí)間序列異常檢測(cè)方法

錢 宇，蔡文鋌

（中國(guó)民用航空飛行學(xué)院飛行技術(shù)學(xué)院，廣漢 618307）

0 引言

伴隨著大數(shù)據(jù)時(shí)代的到來(lái)，航空領(lǐng)域產(chǎn)生了大量具有明顯時(shí)間順序性的數(shù)據(jù)。尤其是傳感器的普及和生產(chǎn)的信息化，使越來(lái)越多的數(shù)據(jù)被記錄下來(lái)形成時(shí)間序列數(shù)據(jù)，例如飛機(jī)、無(wú)人機(jī)飛行數(shù)據(jù)等。在時(shí)間序列數(shù)據(jù)中，異常數(shù)據(jù)往往攜帶著大量有用信息，比如通過(guò)檢測(cè)飛機(jī)快速存取記錄器收集的數(shù)據(jù)可以有效識(shí)別飛機(jī)飛行過(guò)程中的異常行為、設(shè)備故障以及其他潛在風(fēng)險(xiǎn)。

國(guó)內(nèi)外學(xué)者在時(shí)間序列異常檢測(cè)方面進(jìn)行了大量研究，文獻(xiàn)［1］提出了一種使用卷積半分自編碼器來(lái)提取多參數(shù)數(shù)據(jù)特征的方法，并結(jié)合長(zhǎng)短期記憶神經(jīng)網(wǎng)絡(luò)對(duì)這些學(xué)習(xí)到的特征進(jìn)行異常點(diǎn)預(yù)測(cè)，通過(guò)這種方法能夠識(shí)別出在數(shù)據(jù)中具有異常行為的點(diǎn)。文獻(xiàn)［2］采用神經(jīng)網(wǎng)絡(luò)來(lái)辨別參數(shù)之間的隱藏狀態(tài)，并通過(guò)交互學(xué)習(xí)捕捉時(shí)間序列數(shù)據(jù)之間的依賴關(guān)系?；谟?jì)算得出的異常分?jǐn)?shù)，能夠?qū)r(shí)間序列的變化趨勢(shì)進(jìn)行預(yù)測(cè)，并根據(jù)異常情況做出判斷。文獻(xiàn)［3］針對(duì)飛行過(guò)程中不同飛行階段和機(jī)動(dòng)動(dòng)作將其截取成多個(gè)數(shù)據(jù)向量，并利用高斯混合模型對(duì)樣本數(shù)據(jù)進(jìn)行聚類以找出可能存在異常情況的飛行階段。文獻(xiàn)［4］使用局部離群概率算法分析航空公司航班的歷史飛行數(shù)據(jù)，成功地檢測(cè)到以往未被識(shí)別的飛機(jī)運(yùn)行異?，F(xiàn)象。還可以訓(xùn)練時(shí)間序列預(yù)測(cè)模型，根據(jù)模型的預(yù)測(cè)值與真實(shí)值的殘差進(jìn)行異常判定，文獻(xiàn)［5-8］利用神經(jīng)網(wǎng)絡(luò)建立時(shí)間序列預(yù)測(cè)模型；文獻(xiàn)［9］使用改進(jìn)的ARIMA 模型預(yù)測(cè)時(shí)間序列值；文獻(xiàn)［10］使用GAN 模型擬合多元時(shí)序數(shù)據(jù)分布并重構(gòu)時(shí)序誤差，相比于使用樣本數(shù)據(jù)訓(xùn)練模型半監(jiān)督學(xué)習(xí)方法可以更好地利用無(wú)標(biāo)簽數(shù)據(jù)；文獻(xiàn)［11］使用平均距離改進(jìn)局部離群因子算法，實(shí)現(xiàn)電力市場(chǎng)的異常行為檢測(cè)；文獻(xiàn)［12］在VAE 編碼器和解碼器中引入LSTM 網(wǎng)絡(luò)學(xué)習(xí)時(shí)間序列的時(shí)空關(guān)系。多元時(shí)間序列間通常存在著時(shí)空關(guān)系，因此也可以根據(jù)多變量間的時(shí)空關(guān)系判斷序列異常。文獻(xiàn)［13］利用圖神經(jīng)網(wǎng)絡(luò)進(jìn)行多變量時(shí)間序列異常檢測(cè)。文獻(xiàn)［14］利用圖遍歷和馬爾可夫鏈進(jìn)行相似矩陣轉(zhuǎn)換來(lái)檢測(cè)多元時(shí)序數(shù)據(jù)的異常，但因其需要異常狀態(tài)的先驗(yàn)知識(shí)及各種狀態(tài)變化概率，長(zhǎng)期預(yù)測(cè)涉及對(duì)更遠(yuǎn)未來(lái)進(jìn)行推斷和估計(jì)。文獻(xiàn)［15］采用自編碼器進(jìn)行對(duì)抗訓(xùn)練來(lái)放大異常的重建誤差。

聚類算法作為機(jī)器學(xué)習(xí)算法的一個(gè)重要分支，不需要給數(shù)據(jù)打標(biāo)簽，不需要標(biāo)記實(shí)例，成為最適合處理時(shí)間序列數(shù)據(jù)的方法之一，針對(duì)時(shí)間序列異常檢測(cè)領(lǐng)域，研究人員廣泛探索和應(yīng)用各種算法。文獻(xiàn)［16］提出的方法中，采用了分段線性表示來(lái)對(duì)電力時(shí)間序列數(shù)據(jù)進(jìn)行降維處理。該方法首先根據(jù)預(yù)定規(guī)則將原始數(shù)據(jù)進(jìn)行分段，并利用線性模型對(duì)每個(gè)子段進(jìn)行表示。通過(guò)這種方式，可以顯著減少數(shù)據(jù)的維度。文獻(xiàn)［17］將QAR 數(shù)據(jù)轉(zhuǎn)化為高維向量，使用DBSCAN 聚類算法將高密度區(qū)域劃分為簇，不屬于簇的點(diǎn)判定為異常航班。在相關(guān)文獻(xiàn)中，有幾項(xiàng)研究采用了不同的聚類算法和特征提取技術(shù)，以分析和檢測(cè)異常情況。首先，文獻(xiàn)［18］運(yùn)用聚類算法來(lái)選擇與飛行風(fēng)險(xiǎn)高度密切相關(guān)的參數(shù)。使用聚類方法對(duì)數(shù)據(jù)進(jìn)行處理，從中篩選出與飛行安全性最相關(guān)的參數(shù)。其次，在文獻(xiàn)［19］中，作者針對(duì)排隊(duì)檢測(cè)數(shù)據(jù)進(jìn)行了特征提取，并使用K-shape 聚類方法對(duì)提取后的數(shù)據(jù)進(jìn)行聚類分析。通過(guò)這種方式，得到了時(shí)間序列集合的平均特征序列作為異常序列判斷依據(jù)。此外，文獻(xiàn)［20］利用歷史數(shù)據(jù)來(lái)預(yù)測(cè)當(dāng)前時(shí)刻的區(qū)域用電量。

現(xiàn)有的聚類算法中通常采用歐氏距離對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行劃分，缺少時(shí)間序列對(duì)齊的靈活性，無(wú)法對(duì)時(shí)間序列數(shù)據(jù)很好地聚類。基于以上問(wèn)題，研究將QAR 數(shù)據(jù)和參數(shù)監(jiān)控標(biāo)準(zhǔn)數(shù)據(jù)匹配，得到異常標(biāo)簽；使用時(shí)間動(dòng)態(tài)規(guī)整距離度量方法替換聚類算法的歐氏距離度量方法，對(duì)QAR 參數(shù)航段數(shù)據(jù)進(jìn)行聚類得到聚類結(jié)果，最后分析改進(jìn)聚類算法異常檢測(cè)的性能。

1 QAR數(shù)據(jù)與飛行品質(zhì)監(jiān)控

快速存取記錄器（quick access recorder，QAR），指在日常運(yùn)行過(guò)程中用于監(jiān)控、采集與飛行相關(guān)的參數(shù)以及數(shù)據(jù)的機(jī)載飛行數(shù)據(jù)存儲(chǔ)記錄設(shè)備。QAR 記錄了航空器的運(yùn)行數(shù)據(jù)，用于監(jiān)控航空器的一系列參數(shù)，其中包含航空器的姿態(tài)、高度、速度以及航空器駕駛員的操作動(dòng)作等。

飛行品質(zhì)監(jiān)控（flight operations quality assurance，F(xiàn)OQA）是國(guó)際上公認(rèn)的保證飛行安全的重要手段之一，已得到世界民航業(yè)的普遍認(rèn)可。目前，飛行品質(zhì)監(jiān)控主要是利用快速存儲(chǔ)記錄器采集的數(shù)據(jù)進(jìn)行安全監(jiān)控［21］。

由于傳感器記錄過(guò)程中可能存在飛機(jī)飛行環(huán)境變化、引入噪聲等因素導(dǎo)致數(shù)據(jù)存在異常［22-23］，給后續(xù)的數(shù)據(jù)挖掘、模型訓(xùn)練和分析帶來(lái)很大的困擾。通過(guò)分析QAR 數(shù)據(jù)可以對(duì)飛機(jī)的飛行安全進(jìn)行監(jiān)控，及時(shí)發(fā)現(xiàn)和解決潛在的故障和問(wèn)題，提前采取維修措施，確保飛機(jī)的安全性和可靠性。因此，對(duì)QAR 數(shù)據(jù)進(jìn)行異常檢測(cè)以及深入挖掘異常數(shù)據(jù)背后所隱藏的信息是非常重要的，這是實(shí)現(xiàn)飛機(jī)飛行品質(zhì)監(jiān)控和保證飛行安全的重要手段。

2 時(shí)間序列異常檢測(cè)方法及實(shí)現(xiàn)

2.1 K-Medoids聚類算法

K-Medoids 聚類算法是一種用于將數(shù)據(jù)集分成k個(gè)簇的算法，它能夠通過(guò)迭代簇中心點(diǎn)來(lái)優(yōu)化聚類效果，每個(gè)簇包含一個(gè)代表點(diǎn)和一組與該代表點(diǎn)最相似的數(shù)據(jù)點(diǎn)。在K-Medoids 算法中，通過(guò)使用歐幾里得距離作為聚類準(zhǔn)則函數(shù)來(lái)衡量聚類結(jié)果的質(zhì)量，使用式（1）進(jìn)行計(jì)算：

其中，p表示樣本集中的樣本點(diǎn)，oi代表簇Ci的中心點(diǎn)，E表示聚類準(zhǔn)則函數(shù)值。

K-Medoids算法基本步驟如下：

（1）初始化：從樣本集中隨機(jī)選擇k個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心。

（2）計(jì)算距離：對(duì)于每個(gè)數(shù)據(jù)對(duì)象，計(jì)算它與所選聚類中心之間的距離。常用的距離度量方法包括歐氏距離、曼哈頓距離等。

（3）對(duì)于每個(gè)聚類簇計(jì)算其所有數(shù)據(jù)點(diǎn)到其他點(diǎn)的距離之和，選擇其中距離之和最小的點(diǎn)作為新的聚類中心。

（4）重復(fù)執(zhí)行步驟（2）、（3）的過(guò)程，直到聚類中心不再發(fā)生改變或達(dá)到設(shè)定的最大迭代次數(shù)為止。

2.2 動(dòng)態(tài)時(shí)間規(guī)整算法

動(dòng)態(tài)時(shí)間規(guī)整算法（dynamic time warping，DTW）是一種用于測(cè)量?jī)蓚€(gè)時(shí)間序列之間相似度的算法，該算法通過(guò)對(duì)時(shí)間軸進(jìn)行彎曲、拉伸或收縮來(lái)計(jì)算兩個(gè)時(shí)間序列間相似性［24］。動(dòng)態(tài)時(shí)間規(guī)整算法創(chuàng)建一個(gè)二維矩陣來(lái)存儲(chǔ)兩個(gè)時(shí)間序列之間每個(gè)數(shù)據(jù)點(diǎn)之間的局部距離值，并根據(jù)一定規(guī)則進(jìn)行累積距離計(jì)算。然后，根據(jù)累積距離矩陣找到最優(yōu)路徑，該路徑代表了將一個(gè)時(shí)間序列映射到另一個(gè)時(shí)間序列的最佳匹配方式。在路徑查找過(guò)程中，可以使用不同的約束條件來(lái)控制時(shí)間軸彎曲、拉伸或壓縮的程度，從而靈活地調(diào)整對(duì)齊結(jié)果。最后，通過(guò)計(jì)算最優(yōu)路徑上各個(gè)點(diǎn)之間的累積距離值，得到兩個(gè)時(shí)間序列之間的DTW 距離。DTW 算法是一種強(qiáng)大的工具，在比較和分析時(shí)間序列數(shù)據(jù)時(shí)發(fā)揮著重要作用。它能夠克服長(zhǎng)度不等以及形態(tài)變化等問(wèn)題，并提供更準(zhǔn)確的相似性度量結(jié)果［25］。DTW距離的對(duì)齊方式相比于歐氏距離，可以更加準(zhǔn)確地匹配時(shí)間序列，更能體現(xiàn)時(shí)間序列對(duì)應(yīng)特征點(diǎn)間的關(guān)系以及序列間的相似性。

圖1 歐氏距離和DTW距離的對(duì)齊模式

動(dòng)態(tài)時(shí)間規(guī)整算法步驟如下：對(duì)于兩個(gè)長(zhǎng)度為m和n的時(shí)間序列。首先定義一個(gè)m×n的矩陣D，用于存儲(chǔ)DTW 距離的計(jì)算結(jié)果；在計(jì)算DTW 距離時(shí)，首先需要初始化矩陣D，其中D［0］［0］為0，D［i］［0］和D［0］［j］均設(shè)為正無(wú)窮大。這里的i取值范圍是從1到m，而j取值范圍是從1 到n。接下來(lái)使用動(dòng)態(tài)規(guī)劃的方法，逐個(gè)計(jì)算矩陣中的元素D［i］［j］。具體計(jì)算方式如下：對(duì)于每個(gè)位置（i,j），將其定義為時(shí)間序列X中第i個(gè)元素與時(shí)間序列Y中第j個(gè)元素之間的距離，加上其左邊、上邊和左上方三個(gè)元素中的最小值?？梢员硎緸槭剑?）：

其中，d(X[i]，Y[j] )表示X中第i個(gè)元素和Y中第j個(gè)元素的距離。

2.3 改進(jìn)聚類算法

本研究根據(jù)實(shí)際時(shí)間序列數(shù)據(jù)異常檢測(cè)情況將K-Medoids 算法進(jìn)行了改進(jìn)，由于異常數(shù)據(jù)在數(shù)據(jù)集里占比很小且數(shù)據(jù)集中只有正常與異常兩種時(shí)間序列類別，因此在算法中只存在一個(gè)聚類簇。在時(shí)間序列距離度量方面，如圖2所示，將歐氏距離度量方法替換為DTW 距離度量方法。航班在實(shí)際運(yùn)行中相同飛行階段飛機(jī)飛行狀態(tài)變化趨勢(shì)相似，對(duì)時(shí)間序列形態(tài)的相似性判斷非常重要。DTW 算法為聚類簇劃分提供樣本序列，與聚類簇的相似性更加貼合聚類中心［26］，因此在分析時(shí)間序列樣本差異度時(shí)采用DTW算法進(jìn)行計(jì)算。

圖2 改進(jìn)聚類算法流程

2.4 異常檢測(cè)方法

基于改進(jìn)聚類算法，構(gòu)建對(duì)QAR 參數(shù)數(shù)據(jù)的異常檢測(cè)方法，方法流程如圖3所示。首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，將QAR 數(shù)據(jù)和參數(shù)監(jiān)控標(biāo)準(zhǔn)數(shù)據(jù)匹配，得到異常標(biāo)簽；利用改進(jìn)聚類算法對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行聚類得到聚類結(jié)果，在進(jìn)行時(shí)間序列異常檢測(cè)時(shí)采用1%的異常檢出率，即算法輸出距離樣本集中心序列最遠(yuǎn)的百分之一的序列；最后結(jié)合算法輸出序列與序列異常標(biāo)簽分析改進(jìn)聚類算法異常檢測(cè)的性能。

圖3 時(shí)間序列異常檢測(cè)方法流程

3 實(shí)驗(yàn)過(guò)程與結(jié)果分析

3.1 實(shí)驗(yàn)過(guò)程

3.1.1 異常數(shù)據(jù)篩選

本研究選用無(wú)極端天氣狀況下在成都雙流機(jī)場(chǎng)降落的A320 機(jī)型QAR 數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，總共500 個(gè)航班。根據(jù)QAR 數(shù)據(jù)和超限事件參數(shù)標(biāo)準(zhǔn)判斷QAR 參數(shù)數(shù)據(jù)是否為異常數(shù)據(jù)并得到異常標(biāo)簽，超限事件參數(shù)標(biāo)準(zhǔn)是根據(jù)民航法規(guī)設(shè)定的參數(shù)閾值得到的航班超限異常，部分超限參數(shù)閾值見(jiàn)表1。

表1 部分參數(shù)閾值及觸發(fā)條件

3.1.2 航段選取

為了選取不同航班處于同一飛行階段的時(shí)間序列數(shù)據(jù)，對(duì)每個(gè)航班的數(shù)據(jù)樣本進(jìn)行重抽樣。對(duì)于每個(gè)航班f來(lái)說(shuō)，樣本數(shù)據(jù)可以表示為式（3）：

對(duì)每個(gè)航班按相同的規(guī)則進(jìn)行航段選取，飛機(jī)在主輪著地時(shí)飛機(jī)的空地開(kāi)關(guān)會(huì)由AIR 轉(zhuǎn)化為GROUND，將飛機(jī)空地開(kāi)關(guān)轉(zhuǎn)換的點(diǎn)設(shè)為著陸點(diǎn)，每個(gè)航班取著陸點(diǎn)前34 點(diǎn)，著陸后取5 點(diǎn)。每個(gè)航班總計(jì)40 個(gè)時(shí)間戳，取值的范圍涵蓋了飛機(jī)在500英尺至滑行跑道上的高度。

3.1.3 評(píng)估指標(biāo)

為了驗(yàn)證時(shí)間序列異常檢測(cè)方法的性能，研究采用準(zhǔn)確率（Accuracy，Acc）和F1分?jǐn)?shù)來(lái)評(píng)估模型的性能。

其中，TP表示真正例數(shù)，F(xiàn)P表示假正例數(shù)，TN表示真反例數(shù)，F(xiàn)N表示假反例數(shù)。

3.2 結(jié)果分析

為了評(píng)估改進(jìn)聚類算法異常檢測(cè)的性能，在選定實(shí)驗(yàn)數(shù)據(jù)集上，通過(guò)對(duì)飛行數(shù)據(jù)進(jìn)行異常檢測(cè)評(píng)估各聚類算法性能。

分別采用K-Means、K-Medoids 和改進(jìn)聚類異常檢測(cè)算法識(shí)別在落地前34 s 至落地后5 s 這一時(shí)間段內(nèi)各QAR參數(shù)中帶有異常標(biāo)簽的時(shí)間序列，各種算法的異常檢測(cè)性能指標(biāo)如圖4、圖5所示。

從準(zhǔn)確率指標(biāo)來(lái)看，改進(jìn)K-Medoids 的平均準(zhǔn)確率最高，約為99.86%，比K-Medoids 約高0.4%，比K-Means 約高0.67%。三種算法中改進(jìn)K-Medoids 的F1 分?jǐn)?shù)最高，比K-Medoids 約高0.21%，比K-Means約高0.74%。

三種算法在垂直載荷（VRTG）和俯仰角（PITCH）數(shù)據(jù)集上的異常檢測(cè)準(zhǔn)確率較高，在航向道偏差（GLIDE_DEVC）數(shù)據(jù)集上準(zhǔn)確率有所下降，其中K-Means 下降最多約為0.4%，改進(jìn)K-Medoids 下降最少約為0.14%。這是由于航向道數(shù)據(jù)集中的序列數(shù)據(jù)以0為基準(zhǔn)上下波動(dòng)且波動(dòng)較多，改進(jìn)K-Medoids 算法在計(jì)算序列數(shù)據(jù)差異時(shí)會(huì)匹配“波峰”“波谷”，實(shí)現(xiàn)“一對(duì)多”的數(shù)據(jù)對(duì)應(yīng)，而使用歐氏距離計(jì)算序列差異的K-Means 和K-Medoids 算法在數(shù)據(jù)匹配時(shí)為“一對(duì)一”匹配，因此使用歐氏距離計(jì)算的聚類算法在序列數(shù)據(jù)有較多波動(dòng)的數(shù)據(jù)集中表現(xiàn)較差。

圖4 準(zhǔn)確率對(duì)比圖

圖5 F1分?jǐn)?shù)對(duì)比圖

4 結(jié)語(yǔ)

通過(guò)對(duì)現(xiàn)有時(shí)序數(shù)據(jù)異常檢測(cè)方法的分析和研究，提出了一種改進(jìn)的聚類算法，為時(shí)間序列數(shù)據(jù)異常檢測(cè)提供了一種有效且可行的解決方法。以具有時(shí)間序列特性的飛機(jī)QAR 參數(shù)數(shù)據(jù)作為實(shí)驗(yàn)對(duì)象，通過(guò)對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行異常檢測(cè)，體現(xiàn)改進(jìn)聚類算法異常檢測(cè)的性能，并將K-Means 算法、傳統(tǒng)K-Medoids 算法作為參照進(jìn)行實(shí)驗(yàn)對(duì)比，得出以下結(jié)論：

（1）動(dòng)態(tài)時(shí)間規(guī)整度量時(shí)間序列間的距離相較于歐氏距離縮小了形狀相似的序列數(shù)據(jù)間的距離，聚類算法結(jié)合動(dòng)態(tài)時(shí)間規(guī)整可以對(duì)形態(tài)特點(diǎn)相似的時(shí)間序列更好地聚類。

（2）研究提出的改進(jìn)K-Medoids 聚類算法在時(shí)間序列異常檢測(cè)方面尤其是在處理具有相似形態(tài)特點(diǎn)的時(shí)間序列數(shù)據(jù)時(shí)更具優(yōu)勢(shì)，該算法可以有效識(shí)別存在異常波動(dòng)和異常值的時(shí)間序列。

（3）后續(xù)研究可將該方法應(yīng)用于飛機(jī)運(yùn)行的其他階段及參數(shù)，檢測(cè)與分析其中所包含的潛在異常。