數據整合中異常檢測算法研究①

方 正, 高 岑, 田 月, 王 嵩

1(中國科學院大學, 北京 100049)

2(中國科學院 沈陽計算技術研究所, 沈陽 110168)

數據整合中異常檢測算法研究①

方 正1,2, 高 岑2, 田 月2, 王 嵩2

1(中國科學院大學, 北京 100049)

2(中國科學院 沈陽計算技術研究所, 沈陽 110168)

傳統的數據整合方案[1]中存在結構上的不嚴謹性, 在整合期間由于各種原因導致整合后的結果存在很多異常離群點, 而且并沒有有效的措施進行檢測和避免. 本文提出了基于角度的改進后的三階段離群點檢測算法, 通過對數據整合后的結果進行檢測, 有效地消除了存在的大量疑似離群點. 這種改進算法減小了傳統算法中對離群點誤判的可能性, 考慮到數據動態變化的因素, 二次驗證疑似離群點的異常情況的真實性. 本文以生產事故應急救援平臺系統項目為背景.

數據整合; 異常檢測; 離群點檢測; 基于角度; 生產事故

引言

作為數據挖掘的一項技術, 離群點檢測已經在眾多領域得到了廣泛的應用, 如計算機入侵檢測、災難異常檢測等, 其中, 常用的檢測方法主要有: 基于密度的離群點檢測[2,4], 基于聚類的離群點檢測以及基于鄰近性方法的檢測[5,6]. 本文研究案例背景是生產事故應急救援平臺系統[3], 在平臺構建時需要融合來自不同信息系統的數據, 其中遇到的核心問題就是融合后數據出現異常狀況. 為了降低數據融合后的異常狀況, 基于數據特征眾多且復雜, 引入了高維數據下的離群點檢測相關算法.

文獻[7]中提到了利用基于角度的方法進行高維數據集的離群點檢測, 這種方法的優點是避免了對高維數據的降維, 不會使高維數據退化, 適用于各種復雜的高維數據. 但其在計算離群點因子時并沒有考慮到數據動態變化的因素. 本文對傳統的基于角度的離群點檢測算法進行改進, 并引進時間序列推進數據演變的概念, 在已有數據基礎上增加數據維度, 提出一種基于角度的三階段離群點檢測算法(Angle-Based Three Stage Outliter Detection), 相比較于傳統的離群點算法,此時的離群點總數量下降了9%左右.

1 異常檢測算法提出

異常對象一般被稱為離群點, 異常檢測也稱偏差檢測和例外挖掘[8]. 常見的異常成因: 數據來源多樣、自然變異以及數據測量或收集誤差. 異常數據挖掘是一個非常有趣的研究課題, 在國內外受到了廣泛的研究, 并且研究成果豐富, 大致可分為三類[7-9]: (1)基于模型的技術, 首先建立一個數據模型, 異常是那些通用模型不能完美擬合的對象, 如果模型是簇的集合, 則異常就是不顯著屬于任何簇的對象, 如在使用回歸模型時,異常是相對于遠離預測值的對象; (2)基于鄰近度的技術, 通常可以在對象之間定義鄰近性度量, 異常對象是那些遠離其他對象的對象; (3)基于密度的技術, 僅當一個點的局部密度顯著低于它的大部分近鄰時才將其分類為離群點.

基于角度的離群點檢測[10,11], 適用于高維度數據模型, 通常避免鄰近性度量, 并且采用新的啟發式方法來檢測離群點, 避免了在多維數據采用降維手段所造成的數據退化影響. 由于影響生產事故因素復雜, 其表現出來的數據特征差異性較大, 所以不能盲目認為某個點就是離群點, 原有的基于角度的離群點檢測算法就顯得不太適用, 故本文采用分段模式對原算法進行改進, 第一階段是傳統的高維離群點檢測, 第二階段是推進第一階段的數據進行必要的演練, 得到在時間序列上相對于第一階段的未來趨勢. 第三階段主要是分析第二階段末的時候第一階段中的疑似離群點是否仍然在檢測中表現異常, 如果是則將其判定為離群點, 反之則判定為正常數據.

2 基于角度的三階段離群點檢測算法

2.1 傳統的基于角度的離群點檢測算法

算法描述[7]:

(1) 圖1中的點除了形成了兩個小型的簇, 還有疑似離群點O. 在簇1中選取兩個數據點, 分別命名為對象X、對象Y, 此處的對象代表具有多屬性的事物, 例如煤礦生產事故監控模塊中的瓦斯傳感器或負壓傳感器,對象X與對象Y的區別是對象所處時間段不同, 對應的屬性數據也表現不同. 連線OX、OY形成一個角度.

(2) 對于點簇中心的點, 構成的角度差別很大, 對于遠離簇中心的點, 角度的變化較小. 對于離群點O, 角度變化顯著地小. 這樣就可以使用點的角度來確定一個點是否是離群點.

圖1 基于角度的離群點

(3) 結合角度和距離來對離群點建模. 對于每個點對象, 使用距離加權的角度方差(distance-weighted angle variance)作為離群點得分. 即給定一個點集D, 對于每個點(屬于D)定義基于角度的離群點因子(Angle-Based Outlier Factor, ABOF)為:

2.2 基于角度的三階段離群點檢測算法

2.2.1 算法及算法說明

算法: 基于角度的三階段離群點檢測算法

說明: xi, yi為點簇中的任意點, O代表疑似離群點,n為點簇數目, m為疑似離群點數目

算法說明: 低維問題向高維問題展開是一個數據推演的過程, 當然隨之計算ABOF也有所變化, 如公式(2), 參數α代表升維后其他數據特征的權重.

本文案例數據來源于生產事故應急救援平臺, 考慮到影響事故破壞程度的因素眾多, 且隨時間推移, 先前相關性較小的特征數據的影響力可能也越來越大.比如, 生產車間有毒化學氣體泄漏, 后期伴隨著天氣變化, 在有風與無風條件下其擴散范圍與速度是有很大差別的. 所以, 在異常檢測過程中, 本文改進后的算法采取分段處理, 共分為三個階段:

(1) 第一階段: 即算法描述中第1到第6步, 根據傳統的基于角度的離群點檢測算法, 計算出點簇中每個點的離群點因子(ABOF), 并按遞增序排列輸出, 劃分出疑似離群點;

(2) 第二階段: 即算法描述中第8到14第步, 若離群點數量超過總數一定的比例, 則對原數據集D中的點簇進行升維, 并映射到高維空間, 也就是說擴大數據特征,得到新的點集D’;

(3) 第三階段, 即算法描述中第15步, 根據得到的新的點集D’計算每個點的離群點因子, 按遞增序輸出,并與從(2)中得到的離群點進行比較, 得到新的離群點;

(4) 算法步驟7給出了離群點總數量的閾值, 所以循環迭代執行算法步驟7到步驟16, 達到閾值后算法退出.

算法圖示: 在離群點異常檢測過程中, 主要有兩種可能性, 一是有很大不同, 特別是離群因子前后變化較大, 則說明疑似離群點有被誤認的可能性, 如圖2所示;二是前后序列變化并不大, 則說明疑似離群點異常的可能性很大, 就將其劃分為離群點, 如圖3所示.

3 實驗與驗證

為驗證本文提出的改進算法的有效性, 基于沈陽市應急救援管理平臺系統[3]所提供的數據, 設計實驗與常見異常檢測算法進行比較, 并將離群點占比作為衡量標準. 離群點占比等于離群點與總數據量的比. 離群點比例隨著實驗次數的增加, 逐漸處于平穩的趨勢, 此時離群點比例較低的則說明對應的異常檢測算法較好.

圖2 離群點融合到新的點集

圖3 離群點沒有融合到新的點集

3.1 實驗及數據對象

實驗數據來源為實驗室在做項目沈陽市應急救援管理平臺系統數據, 項目背景之一是在生產事故發生后進行實時評估事故破壞程度, 由此給上層決策系統帶來數據支撐. 在數據整合[1]過程中, 傷亡率以及事件嚴重程度數據整合出錯率較高, 故選擇數據系統有: 企業內部資源管理系統, 員工排班系統, 地域分布系統,如圖4. 為了使實驗結果達到平穩狀態, 選擇數據量達到10萬條以上. 數據點簇的構造中考慮到的數據特征有: 周圍地域, 引起爆炸物種類, 事件發生時間等.

圖4 采取的相關數據系統

3.2 不同異常檢測算法比較

由于異常檢測算法眾多, 為驗證不同算法對于異常數據檢測的準確率, 本文設計如下對比試驗. 分別選取基于距離的離群點檢測算法、基于角度的離群點檢測算法以及本文2.2節提出的改進后的三階段檢測算法.

由表1可知, T1算法下檢測出的疑似離群點較多,說明數據整合期間異常情況可能較多, 但經過T2算法下的數據推演, 二次進行異常檢測, 發現近似有30%到40%疑似離群點被判為無異常情況, 歸屬于正常范圍.

表1 數據整合中的疑似離群點被二次驗證后的情況

由圖5可知, 隨著數據量的不斷增大, 離群數量處于一個平穩增長趨勢, 改進后的基于角度的三階段離群點檢測算法相對于其他兩種算法來說, 上下波動較小, 誤判率降低, 說明效果較好. 由此得出一般性規律:

(1) 數據動態性變化對于異常情況的出現影響較大, 也就會導致某個對象偏離了正常的點集D, 這就會影響了ABOF計算的準確性;

(2) 在隨著時間推進去適當擴大數據后, 再次計算ABOF時發現, 原離群點的離群因子并不顯著變小, 那我們就認為發生融合了, 不再假設此離群點異常;

(3) 另外一種情況是在數據推進后, 計算出疑似離群點的離群因子還是顯著的小, 那就必然斷定疑似離群點異常.

3.3 應用意義

本文是基于沈陽市生產事故應急救援平臺系統實例. 在平臺系統架構上, 因為數據源的多樣性和復雜性特征, 導致數據源在平臺融合階段出現大量的不一致數據, 很多有效數據在融合后出現異常情況, 結合傳統的數據異常算法檢測后效果甚微, 離群點異常保持在30%左右. 在利用本文提出的基于角度的三階段異常檢測算法后, 數據異常離群點下降了9%左右, 實驗數據如圖5所示.

4 總結

通過運用基于角度的三階段離群點檢測算法, 對大量的整合后的數據進行離群點檢測, 然后對實驗中出現的很多疑似離群點進行避免并糾正, 經過二次計算檢測部分疑似離群點融合到原點集中, 符合預期的實驗假設與算法理論推測, 同時, 該算法也提高了離群點檢測準確性, 缺點是增加了異常檢測算法的時間復雜度, 需要進一步改進.

1李立博. 面向服務的多源異構數據整合平臺的設計. 計算機工程與設計, 2011, 32(1): 141–144, 308.

2韓超. 場景分類與道路場景異常識別算法研究[碩士學位論文]. 北京: 北京交通大學, 2016.

3董釗. 智慧工廠構建過程中的有效數據整合問題研究[碩士學位論文]. 天津: 天津財經大學, 2015.

4胡彩平, 秦小麟. 一種基于密度的局部離群點檢測算法DLOF. 計算機研究與發展, 2010, 47(12): 2110–2116.

5江峰, 杜軍威, 眭躍飛, 等. 基于邊界和距離的離群點檢測.電子學報, 2010, 38(3): 700–705.

6王敬華, 趙新想, 張國燕, 等. NLOF: 一種新的基于密度的局部離群點檢測算法. 計算機科學, 2013, 40(8): 181–185.

7胡婷婷. 數據挖掘中的離群點檢測算法研究[碩士學位論文]. 廈門: 廈門大學, 2014.

8吳騫, 吳紹春. 基于離群分析的水位異常識別研究. 硅谷,2010, (24): 45. [doi: 10.3969/j.issn.1671-7597.2010.24.037]

9Su XG, Tsai CL. Outlier detection. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2011,1(3): 261–268. [doi: 10.1002/widm.v1.3]

10Wang Y, Wang XC, Wang XL. A spectral clustering based outlier detection technique. Perner P. Machine Learning and Data Mining in Pattern Recognition. New York, NY, USA.2016. 15–27.

11Zheng ZG, Jeong HY, Huang T, et al. KDE based outlier detection on distributed data streams in multimedia network.Multimedia Tools and Applications, doi: 10.1007/s11042-016-3681-y.

Research on Anomaly Detection Algorithm in Data Integration

FANG Zheng1,2, GAO Cen2, TIAN Yue2, WANG Song21(University of Chinese Academy of Sciences, Beijing 100049, China)
2(Shenyang Institute of Computing Technology, Chinese Ac
ademy of Sciences, Shenyang 110168, China)

Traditional data integration solutions in the presence of the structure are not precise. During the integration period, the integrated result due to various reasons has many abnormal outliers, which cannot be detected and avoided with effective measures. This paper proposes an improved three stage outlier detection algorithm based on angle, which is mainly to detect the results after data integration, and effectively solve the problem of a large number of suspected outliers. This improved algorithm reduces the possibility of outliers in the traditional algorithm, taking into account the factors of dynamic changes in the data, verifying the abnormal real situation of suspected outliers for two times. This paper is backgrounded on the project of production accident emergency rescue system.

data integration; anomaly detection; outlier detection; based angle; production accident

方正,高岑,田月,王嵩.數據整合中異常檢測算法研究.計算機系統應用,2017,26(7):200–203. http://www.c-s-a.org.cn/1003-3254/5936.html

2016-08-19; 收到修改稿時間: 2017-01-23