基于自適應Voronoi檢測器的故障檢測算法

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

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

0　引　言

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

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

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

1　傳統實值否定選擇算法

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

算法1否定選擇算法

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

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

圖1　檢測器的成熟過程

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

圖2　數據檢測識別過程

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

2　自體空間確定

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

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

算法2OPTICS聚類算法

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

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

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

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

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

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

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

5) 算法結束。

3　馮洛諾伊檢測器

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

3.1　自適應馮洛諾伊檢測器

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

3.2　存儲結構定義

數據節點定義

typedef struct DataNode{

//位置信息

}

馮洛諾伊網格節點定義

typedef struct VorinoiPoint{

int position[MaxDimension];

//位置信息

struct VorinoiPoint * nextPoint[Max];

//鄰邊節點

}

檢測器結構定義

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

typedef struct Detector{

struct DataNode * core;

//檢測器核心點

struct VorinoiPoint * points[Max];

//檢測器邊緣端點

}

3.3　自適應馮洛諾伊檢測器生成算法

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

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

(2) 根據3σ準則篩選出內外邊界數據。

(3) 根據篩選出的數據生成馮洛諾伊網格圖。

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

圖3　自適應馮洛諾伊檢測器生成算法

3.4　自適應馮洛諾伊檢測器在線更新算法

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

算法3自適應馮洛諾伊檢測器在線更新算法

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

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

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

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

4　實驗分析

4.1　Iris數據仿真實驗

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

核函數公式：

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

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

RNSA算法、V-detector算法和Voronoi-RNSA算法生成的檢測器數量分別為67 718和15，檢測器生成時間分別為33.06、4.05和5.28 s，對非virginica數據的識別率分別為90%、91%和98%?？梢钥闯鯲oronoi-RNSA算法相對于傳統否定選擇算法訓練時間較短，識別率較高。三種算法生成圖像如圖4-圖6所示。

圖4　RNSA算法檢測器生成圖

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

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

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

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

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

4.2　中國華北某電廠振動類型數據實驗分析

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

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

圖7　RNSA算法檢測器生成圖

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

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

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

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

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

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

5　結　語

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

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

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

[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] 徐學邈, 王如根, 侯勝利. 基于反面選擇原理的智能融合故障檢測模型及其應用[J]. 系統工程與電子技術,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]. 中國科學:信息科學, 2013, 43(5):611-625.

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

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

[9] 黨秋月, 陸月明. 基于OPTICS可達圖的自動識別簇方法[J]. 計算機應用, 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] 蘆天亮,鄭康鋒,傅蓉蓉,等.基于陰性選擇算法的異常檢測系統黑洞覆蓋優化[J].通信學報,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] 劉穎慧.基于人工免疫系統的異常狀態檢測及故障診斷研究[D].上海：上海交通大學，2013.