改進DCA算法用于工程時序數據異常檢測

徐 偉，孫向陽，邸澤雷坤

（上海大學 悉尼工商學院，上海 201899）

0 引言

隨著我國經濟建設的飛速發展，隧道工程建設取得了巨大的成果，然而隧道工程施工具有隱蔽性、復雜性和不確定性等特點，大型隧道工程建設期間都會存在大量的風險，造成隧道施工安全事故頻繁發生。隨著隧道監測技術的發展，最有效的降低隧道風險的措施就是對隧道施工過程進行實時安全監測，從大量的監測數據中及時、準確地發現異常序列，分析災害演化規律、建立災變預警模型。

近年來，很多學者提出了時序數據異常檢測技術。Knorr和Ng指出數據集中至少有K個對象與O點的距離大于σ，點O即為異常點。孟凡榮等人提出任意分布的連續時間序列Top-K異常檢測方法，在含噪聲時序數據對異常結果進行排序,克服噪聲對序列異常檢測準確性的影響。基于距離的異常檢測算法存在較高的計算復雜度，難以確定距離參數等困難。隨著人工智能的迅速發展，學者運用新的智能算法解決實際問題，例如K最近鄰算法[1]、神經網絡[2]、支持向量機[3]。傅嬈等[4]利用支持向量機對入侵特征進行分類,將線性不可分問題轉化為線性優化問題,尋找最優分類面并進行判斷,實現入侵檢測的功能。絕大數機器學習算法要求對原始數據進行分析，需要承擔巨大的時間成本。本文提出基于信息熵的改進DCA算法，并運用該算法實現對時序數據的異常檢測，提高良好的檢測效果。

1 DCA算法

1.1 DCA算法概述

樹突狀細胞進行抗原收集,對抗原數據進行分析處理,最終提呈給樹突狀細胞(DC),并根據抗原環境值來刺激或抑制T細胞對抗原進行免疫響應。在免疫過程中，細胞存在三種狀態：未成熟狀態,半成熟狀態,成熟狀態。未成熟DC能夠收集抗原碎片，并感知從組織發出的多種信號,信號包括病原相關分子模式(PAMP),危險信號 (DS),安全信號(SS),發炎信號(IC)。只有PAMP,DS,SS三種信號共同參與下，IC充當信號放大的角色。DC除了收集PAMP,DS,SS信號，自身也會輸出三種信號：協同刺激分子(CSM)、半成熟細胞分泌的分子 (semi mature)、成熟細胞分泌的分子(mature)。一旦CSM達到一定濃度，DC根據 semi mature和mature的相對濃度進行分化，未成熟DC轉換成半成熟DC或成熟DC，從組織遷移到淋巴結，將抗原提呈給T細胞，促進和抑制免疫反應。成熟DC產生激活因子，刺激T細胞進行免疫應答。半成熟DC產生耐受因子，促使T細胞進行免疫耐受，如圖1所示。

圖1 DC細胞狀態的轉化工程

1.2 DCA算法對輸入信號的處理

DCA算法的核心就是DC細胞從抗原中提取輸入信號，經過權值計算得出輸出信號，利用輸出信號得到成熟環境抗原值(MCAV),最終對抗原進行評價。

圖2 DCA算法中的數據結構

圖2 描述了DCA算法的數據結構，每個DC細胞將采取信號融合的機制通過對輸入信號進行計算來獲取輸出信號。輸出信號計算公式如下：

在公式(1)中,Oj(j=0,1,2)表示輸出信號,O0～O2依次表示 csm、semi mature、mature。Si表示輸入信號，S0～S2依次代表 PAMP，DS，SS,Wij表示從Si到Oj的權重值。權值是免疫學者在長期實驗過程中總結的經驗值,權值正負代表了信號的作用效果，權值的大小代表了輸入信號對輸出信號的影響程度。常用的權值矩陣如表1所示。

表1 DCA權值矩陣表

1.3 DCA算法步驟

DCA算法對抗原與信號的數據流進行一定的處理,最終輸出成熟抗原上下文值。算法經歷三個階段：DC細胞和抗原池初始化階段、輸出信號更新階段、抗原綜合評價階段。

算法1 DCA算法

輸入：PAMP、DS、SS信號。

輸出：csm、semi、mat信號、MCAV值。

a)初始化DC種群，確保DC細胞為未成熟狀態

b)隨機選取DC對信號與抗原進行采樣

c)計算輸出信號csm,semi,mature并累加求得Σcsm,Σsemi,Σmature。

d)如果Σcsm〉MT(遷移閾值)，相應的DC發生狀態遷移，未成熟DC轉為成熟DC。

e)判斷是否存在待測的信號與抗原。如果仍存在待處理數據，則轉到步驟b)。否則轉到步驟f)。

f)分別統計每個抗原被成熟DC標記為異常的次數O1以及被未成熟DC標記為正常的次數O2。計算該抗原的MCAV，計算MCAV的公式如下：

從公式(2)可以看出，MCAV的值介于0~1之間，其值用來度量抗原異常的可能性。MCAV越接近于1，則說明該抗原為異常數據的可能性越大；MCAV越接近于0，則說明該抗原為正常數據的可能性越大。

根據算法1的描述，編寫描述DC的狀態轉換和計算MCAV的偽代碼。

算法2 描述DC的狀態轉換

輸入：PAMP、DS、SS信號。

輸出：csm、semi、mat信號、cell context。

1.initialize DC

2.while Σcsm〈Migration Threshold do

3.get antigen；

4.store antigen；

5.get signals；

6.calculate interim output signals；

7.update cumulative output signals；

8.end

9.if Σsemi〉Σmat then

10.cell context is assigned as 0；

11.else

12.cell context is assigned as 1；

13.end

14.kill cell；

15.replace cell in population；

算法3 計算MCAV值。

輸入：抗原上下文值(antigen context)

輸出：MCAV。

1.for all antigen in total list do

2.increment antigen count for this antigen type；

3.if antigen context equals 1 then

4.increment antigen type mature count；

5.end

6.end

7.for all antigen types do

8.MCAV of antigen type=mature count/antigen count；

9.end

2 EDCA算法

針對時序數據的異常檢測，本文提出了一種基于信息熵理論的改進DCA算法(EDCA)，EDCA算法能夠有效地發現時序數據中的異常值。

2.1 時間序列分割算法

本文將時序數據分割成若干個相對短但不重疊的子序列。一般來講，正常子序列所表現的特征信息別于異常子序列，同時異常子序列帶來的局部波動可能會影響前后正常子序列。因此可以將每個子序列看成一個個獨立的抗原。DCA是基于DC群體的算法，每個DCA對一個個獨立的抗原進行采樣(如圖3所示)。

圖3 時間序列免疫過程

本文提出基于信息熵的時間序列分割算法(SABE)。通過應用SABE算法對時序數據進行分割，將分割后的子序列模擬成若干個獨立的抗原，DC細胞從抗原信號提取PAMP，DS，SS信號，應用EDCA算法對時序數據進行異常檢測，EDCA算法流程圖如圖4所示。

圖4 EDCA算法流程圖

定義1：信息熵是指某一事件發生時包含的信息量的數學期望，是衡量一個隨機變量取值的不確定性程度。系統的隨機性越大，非常混亂時信息熵一定很大，反之亦然。信息熵的公式定義如下：

在公式(3)中，P(xi)為序列中第i個序列點的值與所有序列值得總和之比，H(X)為整個序列點的信息熵。

基于信息熵的時間序列分割算法步驟如下：

算法4基于信息熵的時間序列分割

輸入：時序數據。

輸出：分割窗口長度。

a)序列點差值符號化：為了計算時間序列的信息熵，需要對每一個序列點進行符號化。在時間序列X=x(ti)中，設P=x(ti+1)-x(ti),Q=x(ti)-x(ti-1)。

如果 P×Q〈0,該點置為 0；如果 P×Q〉0,該點置為1；如果P×Q=0，該點位置2.則時間原序列X=x(ti)就轉換成由{0,1,2}組成的符號化序列S。

b)求各個子序列的信息熵：設符號化時間序列S的長度為L，分成k段等寬度的時間序列窗口，則子序列的長度均為L/k。設第i個子序列中“0”的數量和為 Cio、“1”的數量和為 Ci1、“2”的數量和為Ci2,第i個子序列的熵H(Xi)。計算H(Xi)如公式(4)所示。

c)確定時間序列分割窗口長度：當子序列的熵極差越大時，選取分割時間序列的窗口長度合適。偏大或偏小的窗口長度均不合適。

算法5 計算最優窗口長度

輸入：時序數據。

輸出：分割窗口長度。

1.Set the window size as k

2.Take symbolic time series S as input data

3.For k=0.8%×length(S)：3%×length(S)

4.Calculate entropy of every subse-quence with k

5.Set dictionary[k]=range(entropy)

6.End for

7.Get k by sorting dictionary；

8.end

2.2 EDCA算法中輸入信號的提取

本文采用方差，平均值，中位數，標準差，極差對每個抗原對應的子序列進行特征提取。根據先驗知識，選取極差屬性列來計算PAMP和SS信號，其計算過程見算法6。其余四個屬性列(方差、平均值、中位數、標準差)用來計算DS信號，其計算過程見公式(5)。除此之外未成熟DC發生遷移變成半成熟DC或成熟DC的遷移閾值的計算見公式(6).

算法6 計算PAMP和SS信號

輸入：時序數據極差。

輸出：PAMP和SS信號。

1.if |value-median|〈 std then

2.value is a safe signal；

3.SS=|median-value|；

4.PAMP=0；

5.else PAMP=|median-value|；.

6.SS=0；

7.END；

在公式(5)中,j的取值為1,2,3,4，分別代表方差，平均值，中位數，標準差四個統計屬性列，在公式(6)中，maxp，maxd，maxs表示 PAMP，DS，SS信號的最大值。wp,c，wp,c，ws,c表示 PAMP，DS，SS 映射到CSM的權重。最終MT在tmedian的±50%區間內隨機取值。由于5個屬性列數值范圍并非處于同一個級別，因此在計算輸入信號之前，必須對其進行歸一化，計算方法如公式(7)所示。

3 EDCA算法實驗

3.1 實驗數據

實驗數據集來源于上海市某隧道工程項目，該數據集收集了施工過程中盾構密封艙土壓力值。土壓力值是重點的監測對象。對土壓力值進行異常分析可以改進工程風險管理。表2為本實驗的基本信息，本實驗選取了該工程中2008年5月1日至2008年5月25日共11721條土壓力數據作為數據樣本。

表2 盾構密封艙土壓力值數據集

3.2 實驗環境

實驗采用的計算機環境為：Intel?Core?處理器，主頻為2.5GHZ，8GB內存，1T硬盤。操作系統為64位Windows 10，所有算法均由MATLAB軟件實現。

3.3 算法實驗及結果分析

本文對實驗數據進行預處理，將同一天的數據平均分成24塊，求出每塊數據的最大土壓力值，作為整點時刻的土壓力值。例如：2008-5-1的數據平均分成24塊，第一塊的最大土壓力值就是2008-5-1 0：00的土壓力值，第二塊的最大土壓力值就是2008-5-1 1：00的土壓力值，以此類推。預處理后的隧道工程土壓力數據如圖5所示。

圖5 土壓力分布圖

為了從土壓力數據源提取輸入信號，應用SABE算法對工程時序數據進行分割，分別不同窗口長度下的熵極差，并繪制熵極差和對應窗口長度的關系，如圖6所示。

圖6 熵極差與窗口長度的關系

從圖6可以看出最大熵極差出現在窗口長度L=14，最大熵極差為1.5774，此時該工程時間序列集分割成42個抗原。本實驗選擇表1的權值矩陣，設定異常閾值a =0.657，應用EDCA算法計算當前42個抗原的成熟環境抗原值MCAV，將MCAV大于異常閾值的抗原對應的時間子序列標記為異常，結果顯示第29,30,32個抗原處于異常狀態，實驗結果如圖7所示。通過對比查看原始數據，第29,30,32個抗原對應的數據發生的時間段為 2008-5-17 7：00～2008-5-18 10：00和 2008-5-19 1：00～2008-5-19 14：00。第一個時間段比災害發生時間提前了1～2天，第二個時間段比災害發生時間提前了幾個小時，表明EDCA算法能夠有效地捕捉異常。

圖7 實驗結果圖

4 結束語

本文對傳統DCA算法完成改進工作，提出基于信息熵的EDCA算法，對時序數據進行異常檢測，實現隧道工程風險預警工作。實驗結果表明：基于危險理論和信息熵的 EDCA算法對工程時序數據異常檢測具有較高的準確性和良好的魯棒性。