一種改進聚類算法的時間序列異常檢測方法

錢 宇，蔡文鋌

（中國民用航空飛行學院飛行技術學院，廣漢 618307）

0 引言

伴隨著大數據時代的到來，航空領域產生了大量具有明顯時間順序性的數據。尤其是傳感器的普及和生產的信息化，使越來越多的數據被記錄下來形成時間序列數據，例如飛機、無人機飛行數據等。在時間序列數據中，異常數據往往攜帶著大量有用信息，比如通過檢測飛機快速存取記錄器收集的數據可以有效識別飛機飛行過程中的異常行為、設備故障以及其他潛在風險。

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

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

現有的聚類算法中通常采用歐氏距離對時間序列數據進行劃分，缺少時間序列對齊的靈活性，無法對時間序列數據很好地聚類。基于以上問題，研究將QAR 數據和參數監控標準數據匹配，得到異常標簽；使用時間動態規整距離度量方法替換聚類算法的歐氏距離度量方法，對QAR 參數航段數據進行聚類得到聚類結果，最后分析改進聚類算法異常檢測的性能。

1 QAR數據與飛行品質監控

快速存取記錄器（quick access recorder，QAR），指在日常運行過程中用于監控、采集與飛行相關的參數以及數據的機載飛行數據存儲記錄設備。QAR 記錄了航空器的運行數據，用于監控航空器的一系列參數，其中包含航空器的姿態、高度、速度以及航空器駕駛員的操作動作等。

飛行品質監控（flight operations quality assurance，FOQA）是國際上公認的保證飛行安全的重要手段之一，已得到世界民航業的普遍認可。目前，飛行品質監控主要是利用快速存儲記錄器采集的數據進行安全監控［21］。

由于傳感器記錄過程中可能存在飛機飛行環境變化、引入噪聲等因素導致數據存在異常［22-23］，給后續的數據挖掘、模型訓練和分析帶來很大的困擾。通過分析QAR 數據可以對飛機的飛行安全進行監控，及時發現和解決潛在的故障和問題，提前采取維修措施，確保飛機的安全性和可靠性。因此，對QAR 數據進行異常檢測以及深入挖掘異常數據背后所隱藏的信息是非常重要的，這是實現飛機飛行品質監控和保證飛行安全的重要手段。

2 時間序列異常檢測方法及實現

2.1 K-Medoids聚類算法

K-Medoids 聚類算法是一種用于將數據集分成k個簇的算法，它能夠通過迭代簇中心點來優化聚類效果，每個簇包含一個代表點和一組與該代表點最相似的數據點。在K-Medoids 算法中，通過使用歐幾里得距離作為聚類準則函數來衡量聚類結果的質量，使用式（1）進行計算：

其中，p表示樣本集中的樣本點，oi代表簇Ci的中心點，E表示聚類準則函數值。

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

（1）初始化：從樣本集中隨機選擇k個數據對象作為初始聚類中心。

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

（3）對于每個聚類簇計算其所有數據點到其他點的距離之和，選擇其中距離之和最小的點作為新的聚類中心。

（4）重復執行步驟（2）、（3）的過程，直到聚類中心不再發生改變或達到設定的最大迭代次數為止。

2.2 動態時間規整算法

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

圖1 歐氏距離和DTW距離的對齊模式

動態時間規整算法步驟如下：對于兩個長度為m和n的時間序列。首先定義一個m×n的矩陣D，用于存儲DTW 距離的計算結果；在計算DTW 距離時，首先需要初始化矩陣D，其中D［0］［0］為0，D［i］［0］和D［0］［j］均設為正無窮大。這里的i取值范圍是從1到m，而j取值范圍是從1 到n。接下來使用動態規劃的方法，逐個計算矩陣中的元素D［i］［j］。具體計算方式如下：對于每個位置（i,j），將其定義為時間序列X中第i個元素與時間序列Y中第j個元素之間的距離，加上其左邊、上邊和左上方三個元素中的最小值。可以表示為式（2）：

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

2.3 改進聚類算法

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

圖2 改進聚類算法流程

2.4 異常檢測方法

基于改進聚類算法，構建對QAR 參數數據的異常檢測方法，方法流程如圖3所示。首先對數據進行預處理，將QAR 數據和參數監控標準數據匹配，得到異常標簽；利用改進聚類算法對時間序列數據進行聚類得到聚類結果，在進行時間序列異常檢測時采用1%的異常檢出率，即算法輸出距離樣本集中心序列最遠的百分之一的序列；最后結合算法輸出序列與序列異常標簽分析改進聚類算法異常檢測的性能。

圖3 時間序列異常檢測方法流程

3 實驗過程與結果分析

3.1 實驗過程

3.1.1 異常數據篩選

本研究選用無極端天氣狀況下在成都雙流機場降落的A320 機型QAR 數據作為實驗數據，總共500 個航班。根據QAR 數據和超限事件參數標準判斷QAR 參數數據是否為異常數據并得到異常標簽，超限事件參數標準是根據民航法規設定的參數閾值得到的航班超限異常，部分超限參數閾值見表1。

表1 部分參數閾值及觸發條件

3.1.2 航段選取

為了選取不同航班處于同一飛行階段的時間序列數據，對每個航班的數據樣本進行重抽樣。對于每個航班f來說，樣本數據可以表示為式（3）：

對每個航班按相同的規則進行航段選取，飛機在主輪著地時飛機的空地開關會由AIR 轉化為GROUND，將飛機空地開關轉換的點設為著陸點，每個航班取著陸點前34 點，著陸后取5 點。每個航班總計40 個時間戳，取值的范圍涵蓋了飛機在500英尺至滑行跑道上的高度。

3.1.3 評估指標

為了驗證時間序列異常檢測方法的性能，研究采用準確率（Accuracy，Acc）和F1分數來評估模型的性能。

其中，TP表示真正例數，FP表示假正例數，TN表示真反例數，FN表示假反例數。

3.2 結果分析

為了評估改進聚類算法異常檢測的性能，在選定實驗數據集上，通過對飛行數據進行異常檢測評估各聚類算法性能。

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

從準確率指標來看，改進K-Medoids 的平均準確率最高，約為99.86%，比K-Medoids 約高0.4%，比K-Means 約高0.67%。三種算法中改進K-Medoids 的F1 分數最高，比K-Medoids 約高0.21%，比K-Means約高0.74%。

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

圖4 準確率對比圖

圖5 F1分數對比圖

4 結語

通過對現有時序數據異常檢測方法的分析和研究，提出了一種改進的聚類算法，為時間序列數據異常檢測提供了一種有效且可行的解決方法。以具有時間序列特性的飛機QAR 參數數據作為實驗對象，通過對時間序列數據進行異常檢測，體現改進聚類算法異常檢測的性能，并將K-Means 算法、傳統K-Medoids 算法作為參照進行實驗對比，得出以下結論：

（1）動態時間規整度量時間序列間的距離相較于歐氏距離縮小了形狀相似的序列數據間的距離，聚類算法結合動態時間規整可以對形態特點相似的時間序列更好地聚類。

（2）研究提出的改進K-Medoids 聚類算法在時間序列異常檢測方面尤其是在處理具有相似形態特點的時間序列數據時更具優勢，該算法可以有效識別存在異常波動和異常值的時間序列。

（3）后續研究可將該方法應用于飛機運行的其他階段及參數，檢測與分析其中所包含的潛在異常。