改進(jìn)DCA算法用于工程時序數(shù)據(jù)異常檢測

徐 偉，孫向陽，邸澤雷坤

（上海大學(xué) 悉尼工商學(xué)院，上海 201899）

0 引言

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

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

1 DCA算法

1.1 DCA算法概述

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

圖1 DC細(xì)胞狀態(tài)的轉(zhuǎn)化工程

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

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

圖2 DCA算法中的數(shù)據(jù)結(jié)構(gòu)

圖2 描述了DCA算法的數(shù)據(jù)結(jié)構(gòu)，每個DC細(xì)胞將采取信號融合的機(jī)制通過對輸入信號進(jìn)行計算來獲取輸出信號。輸出信號計算公式如下：

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

表1 DCA權(quán)值矩陣表

1.3 DCA算法步驟

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

算法1 DCA算法

輸入：PAMP、DS、SS信號。

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

a)初始化DC種群，確保DC細(xì)胞為未成熟狀態(tài)

b)隨機(jī)選取DC對信號與抗原進(jìn)行采樣

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

d)如果Σcsm〉MT(遷移閾值)，相應(yīng)的DC發(fā)生狀態(tài)遷移，未成熟DC轉(zhuǎn)為成熟DC。

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

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

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

根據(jù)算法1的描述，編寫描述DC的狀態(tài)轉(zhuǎn)換和計算MCAV的偽代碼。

算法2 描述DC的狀態(tài)轉(zhuǎn)換

輸入：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算法

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

2.1 時間序列分割算法

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

圖3 時間序列免疫過程

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

圖4 EDCA算法流程圖

定義1：信息熵是指某一事件發(fā)生時包含的信息量的數(shù)學(xué)期望，是衡量一個隨機(jī)變量取值的不確定性程度。系統(tǒng)的隨機(jī)性越大，非?；靵y時信息熵一定很大，反之亦然。信息熵的公式定義如下：

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

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

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

輸入：時序數(shù)據(jù)。

輸出：分割窗口長度。

a)序列點差值符號化：為了計算時間序列的信息熵，需要對每一個序列點進(jìn)行符號化。在時間序列X=x(ti)中，設(shè)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)就轉(zhuǎn)換成由{0,1,2}組成的符號化序列S。

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

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

算法5 計算最優(yōu)窗口長度

輸入：時序數(shù)據(jù)。

輸出：分割窗口長度。

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算法中輸入信號的提取

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

算法6 計算PAMP和SS信號

輸入：時序數(shù)據(jù)極差。

輸出：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，分別代表方差，平均值，中位數(shù)，標(biāo)準(zhǔn)差四個統(tǒng)計屬性列，在公式(6)中，maxp，maxd，maxs表示 PAMP，DS，SS信號的最大值。wp,c，wp,c，ws,c表示 PAMP，DS，SS 映射到CSM的權(quán)重。最終MT在tmedian的±50%區(qū)間內(nèi)隨機(jī)取值。由于5個屬性列數(shù)值范圍并非處于同一個級別，因此在計算輸入信號之前，必須對其進(jìn)行歸一化，計算方法如公式(7)所示。

3 EDCA算法實驗

3.1 實驗數(shù)據(jù)

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

表2 盾構(gòu)密封艙土壓力值數(shù)據(jù)集

3.2 實驗環(huán)境

實驗采用的計算機(jī)環(huán)境為：Intel?Core?處理器，主頻為2.5GHZ，8GB內(nèi)存，1T硬盤。操作系統(tǒng)為64位Windows 10，所有算法均由MATLAB軟件實現(xiàn)。

3.3 算法實驗及結(jié)果分析

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

圖5 土壓力分布圖

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

圖6 熵極差與窗口長度的關(guān)系

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

圖7 實驗結(jié)果圖

4 結(jié)束語

本文對傳統(tǒng)DCA算法完成改進(jìn)工作，提出基于信息熵的EDCA算法，對時序數(shù)據(jù)進(jìn)行異常檢測，實現(xiàn)隧道工程風(fēng)險預(yù)警工作。實驗結(jié)果表明：基于危險理論和信息熵的 EDCA算法對工程時序數(shù)據(jù)異常檢測具有較高的準(zhǔn)確性和良好的魯棒性。