方 正, 高 岑, 田 月, 王 嵩

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

2(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所, 沈陽 110168)

數(shù)據(jù)整合中異常檢測算法研究①

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

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

2(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所, 沈陽 110168)

傳統(tǒng)的數(shù)據(jù)整合方案[1]中存在結(jié)構(gòu)上的不嚴(yán)謹(jǐn)性, 在整合期間由于各種原因?qū)е抡虾蟮慕Y(jié)果存在很多異常離群點(diǎn), 而且并沒有有效的措施進(jìn)行檢測和避免. 本文提出了基于角度的改進(jìn)后的三階段離群點(diǎn)檢測算法, 通過對數(shù)據(jù)整合后的結(jié)果進(jìn)行檢測, 有效地消除了存在的大量疑似離群點(diǎn). 這種改進(jìn)算法減小了傳統(tǒng)算法中對離群點(diǎn)誤判的可能性, 考慮到數(shù)據(jù)動(dòng)態(tài)變化的因素, 二次驗(yàn)證疑似離群點(diǎn)的異常情況的真實(shí)性. 本文以生產(chǎn)事故應(yīng)急救援平臺(tái)系統(tǒng)項(xiàng)目為背景.

數(shù)據(jù)整合; 異常檢測; 離群點(diǎn)檢測; 基于角度; 生產(chǎn)事故

引言

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

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

1 異常檢測算法提出

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

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

2 基于角度的三階段離群點(diǎn)檢測算法

2.1 傳統(tǒng)的基于角度的離群點(diǎn)檢測算法

算法描述[7]:

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

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

圖1 基于角度的離群點(diǎn)

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

2.2 基于角度的三階段離群點(diǎn)檢測算法

2.2.1 算法及算法說明

算法: 基于角度的三階段離群點(diǎn)檢測算法

說明: xi, yi為點(diǎn)簇中的任意點(diǎn), O代表疑似離群點(diǎn),n為點(diǎn)簇?cái)?shù)目, m為疑似離群點(diǎn)數(shù)目

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

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

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

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

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

(4) 算法步驟7給出了離群點(diǎn)總數(shù)量的閾值, 所以循環(huán)迭代執(zhí)行算法步驟7到步驟16, 達(dá)到閾值后算法退出.

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

3 實(shí)驗(yàn)與驗(yàn)證

為驗(yàn)證本文提出的改進(jìn)算法的有效性, 基于沈陽市應(yīng)急救援管理平臺(tái)系統(tǒng)[3]所提供的數(shù)據(jù), 設(shè)計(jì)實(shí)驗(yàn)與常見異常檢測算法進(jìn)行比較, 并將離群點(diǎn)占比作為衡量標(biāo)準(zhǔn). 離群點(diǎn)占比等于離群點(diǎn)與總數(shù)據(jù)量的比. 離群點(diǎn)比例隨著實(shí)驗(yàn)次數(shù)的增加, 逐漸處于平穩(wěn)的趨勢, 此時(shí)離群點(diǎn)比例較低的則說明對應(yīng)的異常檢測算法較好.

圖2 離群點(diǎn)融合到新的點(diǎn)集

圖3 離群點(diǎn)沒有融合到新的點(diǎn)集

3.1 實(shí)驗(yàn)及數(shù)據(jù)對象

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

圖4 采取的相關(guān)數(shù)據(jù)系統(tǒng)

3.2 不同異常檢測算法比較

由于異常檢測算法眾多, 為驗(yàn)證不同算法對于異常數(shù)據(jù)檢測的準(zhǔn)確率, 本文設(shè)計(jì)如下對比試驗(yàn). 分別選取基于距離的離群點(diǎn)檢測算法、基于角度的離群點(diǎn)檢測算法以及本文2.2節(jié)提出的改進(jìn)后的三階段檢測算法.

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

表1 數(shù)據(jù)整合中的疑似離群點(diǎn)被二次驗(yàn)證后的情況

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

(1) 數(shù)據(jù)動(dòng)態(tài)性變化對于異常情況的出現(xiàn)影響較大, 也就會(huì)導(dǎo)致某個(gè)對象偏離了正常的點(diǎn)集D, 這就會(huì)影響了ABOF計(jì)算的準(zhǔn)確性;

(2) 在隨著時(shí)間推進(jìn)去適當(dāng)擴(kuò)大數(shù)據(jù)后, 再次計(jì)算ABOF時(shí)發(fā)現(xiàn), 原離群點(diǎn)的離群因子并不顯著變小, 那我們就認(rèn)為發(fā)生融合了, 不再假設(shè)此離群點(diǎn)異常;

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

3.3 應(yīng)用意義

本文是基于沈陽市生產(chǎn)事故應(yīng)急救援平臺(tái)系統(tǒng)實(shí)例. 在平臺(tái)系統(tǒng)架構(gòu)上, 因?yàn)閿?shù)據(jù)源的多樣性和復(fù)雜性特征, 導(dǎo)致數(shù)據(jù)源在平臺(tái)融合階段出現(xiàn)大量的不一致數(shù)據(jù), 很多有效數(shù)據(jù)在融合后出現(xiàn)異常情況, 結(jié)合傳統(tǒng)的數(shù)據(jù)異常算法檢測后效果甚微, 離群點(diǎn)異常保持在30%左右. 在利用本文提出的基于角度的三階段異常檢測算法后, 數(shù)據(jù)異常離群點(diǎn)下降了9%左右, 實(shí)驗(yàn)數(shù)據(jù)如圖5所示.

4 總結(jié)

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

1李立博. 面向服務(wù)的多源異構(gòu)數(shù)據(jù)整合平臺(tái)的設(shè)計(jì). 計(jì)算機(jī)工程與設(shè)計(jì), 2011, 32(1): 141–144, 308.

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

3董釗. 智慧工廠構(gòu)建過程中的有效數(shù)據(jù)整合問題研究[碩士學(xué)位論文]. 天津: 天津財(cái)經(jīng)大學(xué), 2015.

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

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

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

7胡婷婷. 數(shù)據(jù)挖掘中的離群點(diǎn)檢測算法研究[碩士學(xué)位論文]. 廈門: 廈門大學(xué), 2014.

8吳騫, 吳紹春. 基于離群分析的水位異常識(shí)別研究. 硅谷,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

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

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