尹中川　徐遵義　韓紹超　王俊雪

(山東建筑大學(xué)計算機科學(xué)與技術(shù)學(xué)院　山東 濟南 250101)

0　引　言

現(xiàn)代工業(yè)隨著技術(shù)水平的不斷推進，工業(yè)生產(chǎn)現(xiàn)場人員不斷減少，生產(chǎn)規(guī)模不斷擴大，工業(yè)生產(chǎn)設(shè)備也隨之大型化、復(fù)雜化，在石化、冶金、電力等過程工業(yè)尤為顯著，設(shè)備故障停機會造成巨額損失。而在積累的歷史數(shù)據(jù)中又很難獲取足夠的故障樣本來訓(xùn)練診斷模型。如何在沒有或少量的故障樣本下，利用設(shè)備正常工作時的數(shù)據(jù)樣本來判別設(shè)備運行的情況，準(zhǔn)確預(yù)測故障，對保障設(shè)備安全運行，提高工業(yè)生產(chǎn)效益具有十分重要的意義。

生物免疫系統(tǒng)能夠在不需要先驗知識的條件下，通過自我學(xué)習(xí)，逐漸提高自身的免疫能力，達到有效防御外來物質(zhì)，保護本體的機制。根據(jù)生物免疫系統(tǒng)的這種機制，F(xiàn)orrest等[1]提出了用于異常檢測的二進制反面選擇算法。之后，Dasgupta[2]教授領(lǐng)導(dǎo)的課題組，又提出了等徑實值檢測器。文獻[3]在此基礎(chǔ)之上，提出了可變半徑實值檢測器。此后又有學(xué)者相繼提出了超球體檢測器、超矩形檢測器和超多類型檢測器等[2,8,10]。上述檢測器都在一定程度上減少了檢測器的數(shù)量，提高了對正常樣本的覆蓋率[3-5]。但并沒有完全覆蓋自體空間并消除檢測器之間的孔洞。

如何設(shè)計一種檢測器既能保證檢測器數(shù)量上的簡約，又能消除檢測器之間的孔洞并完全覆蓋正常樣本，對提高檢測精度和效率，具有重要意義。

1　傳統(tǒng)實值否定選擇算法

否定選擇算法借鑒生物免疫系統(tǒng)中胸腺T細(xì)胞生成時的否定選擇過程，模擬了免疫細(xì)胞的成熟過程，刪除通過系統(tǒng)對異常變化的成功檢測而使免疫系統(tǒng)發(fā)揮作用[3]。成功檢測異常的關(guān)鍵是系統(tǒng)能夠準(zhǔn)確區(qū)分自己和非己信號。算法通過隨機產(chǎn)生檢測器，并上出那些檢測到自體的檢測器。算法包括耐受和檢測兩個重要階段[5]，具體步驟見算法1。

算法1否定選擇算法

1) 隨機產(chǎn)生半徑相同的候選檢測器。

2) 對每一個候選檢測器計算與每一個自體元素間的親和度，如果檢測器識別出了任何一個自體元素，那么刪除該檢測器，否則認(rèn)為該檢測器已經(jīng)成熟，將其加入檢測器集合中；步驟1)和步驟2)如圖1所示。

圖1　檢測器的成熟過程

3) 將待測數(shù)據(jù)與成熟檢測器集合中元素逐個對比，如果出現(xiàn)匹配，則證明待檢測數(shù)據(jù)為非自體數(shù)據(jù)，即異常數(shù)據(jù)。步驟3)如圖2所示。

圖2　數(shù)據(jù)檢測識別過程

傳統(tǒng)實值檢測器的每個檢測器的半徑都是相同的，這導(dǎo)致了較高的重復(fù)覆蓋率，增加了檢測器的數(shù)量，以及不能很好地匹配一些形狀復(fù)雜的非自體空間?？勺儼霃降膶嵵捣穸ㄟx擇算法是在實值否定選擇算法的基礎(chǔ)上，產(chǎn)生半徑可變的檢測器，且當(dāng)兩個檢測器的重復(fù)覆蓋率超過臨界值時，會將較小的檢測器刪除。這樣既提高了檢測器的覆蓋率，也減少了檢測器的數(shù)量空洞，但增加了檢測器訓(xùn)練過程的時間。

2　自體空間確定

否定選擇算法的首要工作是確定自體空間，之后用來篩選成熟的檢測器。因此自體范圍的精確度直接影響到了檢測精度[8-9]。本文基于密度的聚類獲取位于自體空間邊界的低密度樣本，通過這些邊界樣本確定自體空間的邊界。下面介紹使用OPTICS聚類方式獲取自體空間的邊界樣本的過程。

OPTICS聚類是基于密度的聚類方式，其思想和DBSCAN非常類似，但是和DBSCAN不同的是，OPTICS算法可以獲得不同密度的聚類[7]。具體流程見算法2。

算法2OPTICS聚類算法

輸入：數(shù)據(jù)樣本D，初始化所有點的可達距離和核心距離為MAX，半徑ε，和最少點數(shù)MinPts。

1) 建立兩個隊列：有序隊列(核心點及該核心點的直接密度可達點)，結(jié)果隊列(存儲樣本輸出及處理次序)。

2) 如果D中數(shù)據(jù)全部處理完，則算法結(jié)束，否則從D中選擇一個未處理且未核心對象的點，將該核心點放入結(jié)果隊列，該核心點的直接密度可達點放入有序隊列，直接密度可達點并按可達距離升序排列。

3) 如果有序序列為空，則回到步驟2)，否則從有序隊列中取出第一個點。

(1) 如果該點不在結(jié)果隊列判斷該點是否為核心點，不是則回到步驟3)，是的話則將該點存入結(jié)果隊列。

(2) 該點是核心點的話，找到其所有直接密度可達點，并將這些點放入有序隊列，且將有序隊列中的點按照可達距離重新排序，如果該點已經(jīng)在有序隊列中且新的可達距離較小，則更新該點的可達距離。

4) 重復(fù)步驟3)，直至有序隊列空。

5) 算法結(jié)束。

3　馮洛諾伊檢測器

馮洛諾伊圖又叫泰森多邊形，是由一組連接兩相鄰點直線的垂直平分線組成的連續(xù)多邊形組成[6]。馮洛諾伊圖是對空間的一種剖分，其特點是多變形內(nèi)的任何位置離該多邊形的樣點的距離最近，離相鄰多邊形內(nèi)樣點的距離遠(yuǎn)，且每個多邊形內(nèi)含且僅包含一個樣點。

3.1　自適應(yīng)馮洛諾伊檢測器

本文針對實值否定選擇算法無法消除孔洞的缺陷，依據(jù)OPTICS[7]聚類，根據(jù)數(shù)據(jù)的密度來區(qū)分自體空間的邊界數(shù)據(jù)，依靠馮洛諾伊圖來劃分問題空間的區(qū)域。并借助馮洛諾伊圖只依靠周圍點來建立的原理，針對實時的檢測效果，對檢測器進行實時更新。

3.2　存儲結(jié)構(gòu)定義

數(shù)據(jù)節(jié)點定義

typedef struct DataNode{

//位置信息

}

馮洛諾伊網(wǎng)格節(jié)點定義

typedef struct VorinoiPoint{

int position[MaxDimension];

//位置信息

struct VorinoiPoint * nextPoint[Max];

//鄰邊節(jié)點

}

檢測器結(jié)構(gòu)定義

《花間集》皆唐末五代時人作，方斯時天下岌岌，生民救死不暇，士大夫乃流宕如此，可嘆也哉！或者亦出于無聊故耶？笠澤翁書。

typedef struct Detector{

struct DataNode * core;

//檢測器核心點

struct VorinoiPoint * points[Max];

//檢測器邊緣端點

}

3.3　自適應(yīng)馮洛諾伊檢測器生成算法

自適應(yīng)馮洛諾伊檢測器生成算法的基本步驟如下：

(1) 通過Optics聚類生成對應(yīng)的核心距離矩陣。

(2) 根據(jù)3σ準(zhǔn)則篩選出內(nèi)外邊界數(shù)據(jù)。

(3) 根據(jù)篩選出的數(shù)據(jù)生成馮洛諾伊網(wǎng)格圖。

(4) 外邊界數(shù)據(jù)所在網(wǎng)格即為馮洛諾伊檢測器。自適應(yīng)馮洛諾伊檢測器生成算法如圖3所示。

圖3　自適應(yīng)馮洛諾伊檢測器生成算法

3.4　自適應(yīng)馮洛諾伊檢測器在線更新算法

自適應(yīng)馮洛諾伊檢測器在線更新算法的基本思想:新的馮洛諾伊網(wǎng)格的生成只依賴對應(yīng)網(wǎng)格的相鄰網(wǎng)格，當(dāng)出現(xiàn)錯誤檢測時，將誤判點插入檢測器內(nèi)，與周圍最近的幾個檢測器一起重新生成一個新的檢測器，并更新周圍的檢測器。步驟見算法3。

算法3自適應(yīng)馮洛諾伊檢測器在線更新算法

1) 對所有檢測器到錯誤檢測數(shù)據(jù)按照距離進行排序，并生成隊列。

2) 訪問隊首檢測器，并出隊，以錯誤點到檢測器核心點的中位線生成馮洛諾伊邊界直線y=f(x)，且設(shè)置邊界的兩端點為空，添加到新的檢測器邊界中。

3) 訪問隊首并出隊，以錯誤點到該檢測器的核心點的中位線生成新的馮洛諾伊邊界直線，若新的馮洛諾伊邊界直線與存在的新檢測器邊界平行，且位于錯誤點的一側(cè)，則進行下一步；否則，將直線加入到新的檢測器邊界中，并更新邊界端點。

4) 若新的檢測器的邊界斷電是否所有都非空，則輸出新的檢測器，并根據(jù)周圍檢測器對應(yīng)的新檢測其邊界，更新生邊界；否則返回3)。

4　實驗分析

4.1　Iris數(shù)據(jù)仿真實驗

由于工業(yè)生產(chǎn)中的數(shù)據(jù)具有連續(xù)性，而正常數(shù)據(jù)與異常數(shù)據(jù)也具有線性可分的特性，考慮到Iris數(shù)據(jù)非線性可分樣本存在，在對Iris數(shù)據(jù)進行實驗之前需要使用多項式核函數(shù)對Iris數(shù)據(jù)進行空間變換[11]。

核函數(shù)公式：

K(Xi,Xj)=(Xi·Xj+1)2

為了方便實驗結(jié)果的觀察，Iris數(shù)據(jù)進行核函數(shù)變換后，再利用主元分析法(PCA)進行降維，將數(shù)據(jù)壓縮到二維，最后設(shè)定virginica數(shù)據(jù)中的30個為空間中的自體樣本。分別使用RNSA算法和V-detector算法與Voronoi-RNSA算法生成檢測器，比較它們在95%期望覆蓋率下的檢測器的生成時間和數(shù)量以及對非virginica數(shù)據(jù)的識別率。

RNSA算法、V-detector算法和Voronoi-RNSA算法生成的檢測器數(shù)量分別為67 718和15，檢測器生成時間分別為33.06、4.05和5.28 s，對非virginica數(shù)據(jù)的識別率分別為90%、91%和98%。可以看出Voronoi-RNSA算法相對于傳統(tǒng)否定選擇算法訓(xùn)練時間較短，識別率較高。三種算法生成圖像如圖4-圖6所示。

圖4　RNSA算法檢測器生成圖

圖5　V-detector算法檢測器生成圖

圖6　Voronoi-RNSA算法檢測器生成圖

從圖4中可知由于RNSA算法檢測器存在大量冗余，且由于半徑固定，自體空間的邊界匹配并不理想。

從圖5中可知V-detector算法相對RNSA算法，精簡了檢測器的數(shù)量，且在自體邊界附近可生成半徑較小的檢測器，邊界匹配度有一定程度提高。但由于檢測器是隨機生成的，需要大量的迭代計算才能對邊界的匹配度進一步提高。

從圖6中發(fā)現(xiàn)，Voronoi-RNSA算法邊界由自體空間的外邊界數(shù)據(jù)點確定不需要迭代計算且檢測器的數(shù)量依賴于邊界的復(fù)雜程度，且不存在孔洞。自體空間由外邊界和內(nèi)邊界數(shù)據(jù)確定，在自體樣本充足的情況下，可以精確描述自體邊界。

4.2　中國華北某電廠振動類型數(shù)據(jù)實驗分析

華北某電廠軸承振動歷史數(shù)據(jù)共29個測點，數(shù)據(jù)具有海量、無標(biāo)簽的特點，且故障樣本極少，無法人為指定自體樣本空間。

首先對數(shù)據(jù)進行主元分析，得到兩個主成分，其貢獻度超過98%。能夠表征絕大部分?jǐn)?shù)據(jù)信息。之后，分別使用RNSA算法和V-detector算法與Voronoi-RNSA算法生成檢測器，比較它們在90%期望覆蓋率下生成的檢測器對自體空間邊界的匹配情況。三種算法生成圖像如圖7-圖9所示。

圖7　RNSA算法檢測器生成圖

圖8　V-detector算法檢測器生成圖

圖9　Voronoi-RNSA算法檢測器生成圖

如圖7所示，RNSA算法在生成大量檢測器后，自體空間邊界附近仍然具有大量孔洞存在，真實的檢測精度難以保證。

如圖8所示，V-detector算法對自體空間邊界的匹配度有所提高，但仍然存在孔洞。算法收斂后，檢測器的隨機生成機制很難在孔洞處生成新的檢測器。

如圖9所示，Voronoi-RNSA算法使用內(nèi)外邊界數(shù)據(jù)生成自體空間與檢測器，檢測器可以很好地匹配自體空間邊界。此外，還可以添加有限的異常數(shù)據(jù)，對邊界檢測器進一步優(yōu)化。

以上實驗表明，傳統(tǒng)的否定選擇算法不可避免存在著孔洞，而這些孔洞更多存在于自體數(shù)據(jù)的邊界，然而真實數(shù)據(jù)往往具有連續(xù)性，故障數(shù)據(jù)很可能會存在于自體數(shù)據(jù)的邊界附近。因此真實的檢測精度要比檢測器的覆蓋率低很多。Voronoi-RNSA算法基于內(nèi)外邊界數(shù)據(jù)生成檢測器，能夠避免孔洞的產(chǎn)生，提高了檢測精度，極大地提高了否定選擇算法在實際故障檢測中的精度。此外，Voronoi檢測器能夠根據(jù)實際的誤判來實時修改自體邊界，從而檢測系統(tǒng)在一個較長時間運行訓(xùn)練后，能夠得到更高的檢測精度。

5　結(jié)　語

否定選擇算法是人工免疫系統(tǒng)中的重要環(huán)節(jié)，RNSA算法采用實值空間編碼抗原和抗體生成檢測器，V-detector算法采用了可變半徑的檢測器，也已經(jīng)取得了較好檢測效果。然而，使用傳統(tǒng)的檢測器定義方式會導(dǎo)致三個缺陷：(1) 無法避免非自體空間中孔洞的產(chǎn)生，從而在達到一定的覆蓋率后很難再提升，會有一定的誤報率；(2) 無法避免檢測器的重復(fù)覆蓋，檢測器的實際覆蓋效率并不高，導(dǎo)致檢測器的數(shù)量過多；(3) 檢測器的耐受訓(xùn)練過程占用大量時間，檢測器生成效率過低。

針對上述問題，針對機械設(shè)備的數(shù)據(jù)特點提出了一種基于自適應(yīng)馮洛諾伊檢測器的否定選擇算法(Voronoi-RNSA)。首先通過OPTICS聚類找到自體空間的外邊界和內(nèi)邊界數(shù)據(jù)，之后根據(jù)內(nèi)外邊界數(shù)據(jù)生成馮洛諾伊網(wǎng)格，外邊界所在的馮洛諾伊網(wǎng)格即是生成的檢測器。該檢測器生成方式極大地減少了檢測器耐受訓(xùn)練時間，并避免了重復(fù)覆蓋的問題，大大提高了檢測器實際覆蓋效率，減少了檢測器的數(shù)量，從理論上排除了孔洞的產(chǎn)生。實驗證明，Voronoi-RNSA算法比經(jīng)典的RNSA算法和V-Detector算法具有更高的檢測精度和更好的檢測器生成質(zhì)量。

由于馮洛諾伊網(wǎng)格圖在高維空間中生成過慢，使用Voronoi-RNSA算法對高維數(shù)據(jù)進行故障檢測，需要將高維數(shù)據(jù)壓縮到低維空間后在進行，從而影響了其在高維數(shù)據(jù)中的應(yīng)用推廣。而自體空間的描述精度直接影響到檢測器耐受過程，是影響檢測精度的重要因素。因此，可針對高維數(shù)據(jù)和自體空間的界定進行進一步的研究。

[1] Forrest S, Perelson A S, Allen L, et al. Self-Nonself Discrimination in a Computer[C]// Research in Security and Privacy, 1994. Proceedings. 1994 IEEE Computer Society Symposium on. IEEE, 1994:202-212.

[2] Dasgupta, Dipankar, Yu, Senhua, Nino, Fernando. Recent Advances in Artificial Immune Systems: Models and Applications[J]. Applied Soft Computing, 2011, 11(2):1574-1587.

[3] Chen L F. An improved negative selection approach for anomaly detection: with applications in medical diagnosis and quality inspection[J]. Neural Computing & Applications, 2013, 22(5):901-910.

[4] 徐學(xué)邈, 王如根, 侯勝利. 基于反面選擇原理的智能融合故障檢測模型及其應(yīng)用[J]. 系統(tǒng)工程與電子技術(shù),2009,31(8): 2030-2032.

[5] Tao Yuan, Hu Min, Yu Yanlin. A Novel Negative Selection Algorithm for Recognition Problems[J]. International Journal of Hybrid Information Technology,2015,8(11):101-112.

[6] 陳文, 李濤, 劉曉潔,等. 一種基于自體集層次聚類的否定選擇算法[J]. 中國科學(xué):信息科學(xué), 2013, 43(5):611-625.

[7] 張鳳斌, 王天博. 實值n維混沌映射否定選擇算法[J]. 計算機研究與發(fā)展, 2013, 50(7):1387-1398.

[8] 孫添, 何國良. 基于K-均值聚類和泰森多邊形的異常值檢測方法[J]. 重慶文理學(xué)院學(xué)報, 2016, 35(2):10-13.

[9] 黨秋月, 陸月明. 基于OPTICS可達圖的自動識別簇方法[J]. 計算機應(yīng)用, 2012, 32(A02):19-21.

[10] Aydin I, Karakose M, Akin E. Chaotic-based hybrid negative selection algorithm and its applications in fault and anomaly detection[J]. Expert Systems with Applications, 2010, 37(7):5285-5294.

[11] 蘆天亮,鄭康鋒,傅蓉蓉,等.基于陰性選擇算法的異常檢測系統(tǒng)黑洞覆蓋優(yōu)化[J].通信學(xué)報,2013(1):128-135.

[12] Li Dong, Liu Shulin, Zhang Hongli. A negative selection algorithm with online adaptive learning under small samples for anomaly detection[J]. Neurocomputing, 2015, 149(C):515-525.

[13] 劉穎慧.基于人工免疫系統(tǒng)的異常狀態(tài)檢測及故障診斷研究[D].上海：上海交通大學(xué)，2013.