，

(北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100191)

0 引言

隨著互聯(lián)網(wǎng)的爆炸式發(fā)展和云時(shí)代的來臨，人們利用網(wǎng)絡(luò)獲取收集信息的同時(shí)，數(shù)據(jù)量呈現(xiàn)出指數(shù)爆炸式的增長，大數(shù)據(jù)吸引了越來越多的關(guān)注。大數(shù)據(jù)的5 V特點(diǎn)：Volume(大量)、Velocity(高速)、Variety(多樣)、Value(低價(jià)值密度)、Veracity(真實(shí)性)，使得傳統(tǒng)常規(guī)的小規(guī)模數(shù)據(jù)處理方法變得不再適用，數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生[1]。

數(shù)據(jù)挖掘指的是通過特定算法發(fā)掘大量數(shù)據(jù)中的重要隱含信息的過程，其通常包含四種類型，分別是關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、類別的描述、類別的判斷和孤立點(diǎn)發(fā)現(xiàn)[2]。孤立點(diǎn)發(fā)現(xiàn)是數(shù)據(jù)挖掘中的一個(gè)重要的分支，已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)，并且在天氣預(yù)報(bào)、股市分析、市場調(diào)研、藥品研發(fā)[3]、醫(yī)療保險(xiǎn)[4]、網(wǎng)絡(luò)入侵檢測[5]、商業(yè)欺詐檢測[6]、飛參數(shù)據(jù)、無線傳感器網(wǎng)絡(luò)[7]等領(lǐng)域得到了廣泛的應(yīng)用。

孤立點(diǎn)通常是指數(shù)據(jù)集中不符合一般模型的異常對象。由于孤立點(diǎn)既有可能是噪聲也有可能隱藏著比一般數(shù)據(jù)更為重要的信息，隨意刪除孤立點(diǎn)數(shù)據(jù)可能導(dǎo)致這些有價(jià)值信息的丟失，所以通過孤立點(diǎn)檢測技術(shù)發(fā)現(xiàn)并利用在孤立點(diǎn)中的有用信息具有非常重要的意義[8]。孤立點(diǎn)檢測也稱孤立點(diǎn)挖掘，是從海量數(shù)據(jù)中找到異常行為，并發(fā)現(xiàn)異常行為中所蘊(yùn)含的信息

的過程，這無疑是一項(xiàng)極富挑戰(zhàn)性的工作。目前對異常值檢測技術(shù)的研究主要分為兩個(gè)方面：理論方法研究和軟件平臺(tái)搭建。本文對異常值檢測課題的研究也將從這兩個(gè)方面展開。

1 系統(tǒng)結(jié)構(gòu)及原理

本文搭建的異常值檢測平臺(tái)可以實(shí)現(xiàn)時(shí)間序列和空間序列的異常值檢測。當(dāng)輸入數(shù)據(jù)集為時(shí)間序列時(shí)，采用基于互相關(guān)分析的異常值檢測方法；當(dāng)輸入數(shù)據(jù)集為空間序列時(shí)，采用基于SOM神經(jīng)網(wǎng)絡(luò)聚類的異常值檢測方法。具體系統(tǒng)平臺(tái)結(jié)構(gòu)如圖1所示。

圖1 異常值檢測平臺(tái)結(jié)構(gòu)

2 異常值檢測算法

2.1 時(shí)間序列異常值檢測

時(shí)間序列是指將同一統(tǒng)計(jì)指標(biāo)的數(shù)值按其發(fā)生的時(shí)間先后順序排列而成的數(shù)列，通常時(shí)間序列的特點(diǎn)是具有一定的趨勢性和相關(guān)性，時(shí)間序列分析的主要目的是就是根據(jù)這兩個(gè)特點(diǎn)，利用已有的歷史數(shù)據(jù)對未來進(jìn)行預(yù)測[9]。如果時(shí)間序列中存在異常值，將會(huì)嚴(yán)重影響到數(shù)據(jù)的預(yù)測效果。因此，時(shí)間序列異常值的檢測很有意義。

對于混合型屬性數(shù)據(jù)集，我們先將其分為數(shù)值型屬性數(shù)據(jù)和非數(shù)值型屬性數(shù)據(jù)兩部分分別處理。對于非數(shù)值型屬性數(shù)據(jù)進(jìn)行出現(xiàn)頻率的統(tǒng)計(jì)；對于數(shù)值型屬性先進(jìn)行利用線性插值將成片孤立點(diǎn)轉(zhuǎn)換成單獨(dú)孤立點(diǎn)，再對相鄰采樣時(shí)刻序列求互相關(guān)函數(shù)，最后用多級(jí)最大類間方差算法自適應(yīng)地選取閾值，并將孤立點(diǎn)分級(jí)輸出。當(dāng)檢測出的孤立點(diǎn)數(shù)目達(dá)到預(yù)設(shè)的比例時(shí)，檢測算法停止并輸出檢測結(jié)果。具體的算法原理框圖見圖2。

圖2 基于互相關(guān)分析的異常值檢測算法原理框圖

實(shí)際系統(tǒng)中的異常值按其分布范圍可以分為兩類：一類是單獨(dú)出現(xiàn)的異常值點(diǎn)，另一類是小范圍內(nèi)成片出現(xiàn)的異常值群。對于成片出現(xiàn)的異常值群采用了線性插值的方法對數(shù)據(jù)做預(yù)處理。利用剪枝策略確定數(shù)值型屬性數(shù)據(jù)集中一定不是異常值的正常點(diǎn)，并利用這些正常點(diǎn)對原始數(shù)據(jù)進(jìn)行線性插值，使得小范圍聚集的異常值數(shù)據(jù)之間插入正常數(shù)據(jù)點(diǎn)，轉(zhuǎn)化為單獨(dú)孤立點(diǎn)的情況進(jìn)行檢測。

對于只含有單獨(dú)孤立點(diǎn)的時(shí)間序列數(shù)據(jù)集，采用互相關(guān)分析的方法進(jìn)行孤立點(diǎn)檢測。每個(gè)采樣時(shí)刻處的各個(gè)維度的數(shù)據(jù)值都可以組成一個(gè)采樣時(shí)刻序列。選取前兩個(gè)采樣時(shí)刻序列作為一個(gè)滑動(dòng)計(jì)算窗，計(jì)算這兩個(gè)采樣時(shí)刻序列的互相關(guān)系數(shù)，得到互相關(guān)函數(shù)的第一個(gè)點(diǎn)。將活動(dòng)窗口按照步長為1的間隔移動(dòng)，長度為L的多維數(shù)值型屬性序列就可以生成一個(gè)點(diǎn)數(shù)為L-1的互相關(guān)函數(shù)。由于互相關(guān)系數(shù)反映的是相鄰采樣時(shí)刻序列的相似程度，所以互相關(guān)函數(shù)的谷值處可能存在孤立點(diǎn)。

由于正常點(diǎn)集與異常點(diǎn)集之間可能存在重合的位置關(guān)系，異常點(diǎn)和正常點(diǎn)之間的分界可能是模糊的，所以有時(shí)把一個(gè)數(shù)據(jù)點(diǎn)絕對的定義為異常點(diǎn)或正常點(diǎn)是不科學(xué)的，這時(shí)用孤立點(diǎn)分級(jí)的概念就可以定義孤立點(diǎn)的孤立程度，避免一概而論。因此孤立點(diǎn)檢測系統(tǒng)閾值的自適應(yīng)選擇和孤立點(diǎn)的分級(jí)輸出是必須要解決的兩個(gè)問題。最大類間方差算法，簡稱OTSU算法，最先在數(shù)字圖像處理鄰域中用于劃分前景和背景。OTSU算法可以將樣本點(diǎn)以類間方差最大，類內(nèi)方差最小的原則分為兩類，并自適應(yīng)地給出分類閾值。因此，算法對互相關(guān)函數(shù)幅值采用多級(jí)最大類間方差算法分類，將第一次分類產(chǎn)生的孤立點(diǎn)記為1級(jí)孤立點(diǎn)，并將此次分類產(chǎn)生的正常點(diǎn)集進(jìn)行二次分類，如此重復(fù)下去，逐步篩選出各級(jí)孤立點(diǎn)分級(jí)輸出，直到產(chǎn)生的孤立點(diǎn)個(gè)數(shù)到達(dá)預(yù)先設(shè)定的比例，并將最后一次最大類間方差算法的閾值記為最終的互相關(guān)系數(shù)閾值。

在非數(shù)值型空間內(nèi)，異常點(diǎn)的非數(shù)值型屬性值相比正常點(diǎn)出現(xiàn)的更不頻繁。基于這種考慮，我們先找出數(shù)據(jù)集中有幾種非數(shù)值屬性值，再對各個(gè)非數(shù)值型屬性值出現(xiàn)的頻數(shù)做出統(tǒng)計(jì)，得到非數(shù)值型屬性頻數(shù)表。依次找出出現(xiàn)頻數(shù)最少的非數(shù)值型屬性數(shù)據(jù)，直到累計(jì)頻數(shù)超過預(yù)先設(shè)定的孤立點(diǎn)比例閾值，停止算法并輸出對應(yīng)的非數(shù)值型屬性異常值。

2.2 空間序列異常值檢測

典型SOM網(wǎng)共有兩層，輸入層模擬的是人眼的視網(wǎng)膜，用于接收外界數(shù)據(jù)，一般為單層神經(jīng)元排列；輸出層模擬的是人腦的大腦皮層，用于處理輸入層獲得的數(shù)據(jù)信息，輸出層的每個(gè)神經(jīng)元都與它周圍的其他神經(jīng)元相互連接，排列成二維的棋盤狀平面[10]。SOM神經(jīng)網(wǎng)絡(luò)可以將任何高維數(shù)據(jù)集映射到二維的輸出神經(jīng)元平面上，映射的獲勝神經(jīng)元相距越近則它們所對應(yīng)的原始數(shù)據(jù)對象就越相似。

基于SOM神經(jīng)網(wǎng)絡(luò)的異常值檢測方法如下：第一，對迭代次數(shù)、輸出結(jié)點(diǎn)權(quán)值向量、學(xué)習(xí)率和鄰域半徑進(jìn)行初始化。對輸入向量進(jìn)行歸一化。第二，對于每一個(gè)輸入向量，利用歐式距離相似性度量準(zhǔn)則尋找與其對應(yīng)的競爭獲勝神經(jīng)元。第三，利用梯度下降法，對獲勝節(jié)點(diǎn)和其鄰域范圍內(nèi)神經(jīng)元集合中的每一個(gè)節(jié)點(diǎn)都進(jìn)行權(quán)值更新。第四，在所有輸入向量均遍歷結(jié)束，并且所有獲勝神經(jīng)元權(quán)值更新之后，更新學(xué)習(xí)率和鄰域函數(shù)。第五，當(dāng)神經(jīng)網(wǎng)絡(luò)的訓(xùn)練次數(shù)達(dá)到預(yù)設(shè)的最大次數(shù)時(shí)，退出訓(xùn)練學(xué)習(xí)過程，即可得到訓(xùn)練好的SOM神經(jīng)網(wǎng)絡(luò)。否則轉(zhuǎn)入第二步。第六，將4-鄰域內(nèi)沒有其他獲勝神經(jīng)元，并且類規(guī)模很小的孤立聚類視為孤立點(diǎn)輸出。算法原理的整體框圖見圖3。

圖3 SOM神經(jīng)網(wǎng)絡(luò)聚類算法原理框圖

3 異常值檢測平臺(tái)

3.1 檢測平臺(tái)概述

本系統(tǒng)在MATLAB開發(fā)環(huán)境下，實(shí)現(xiàn)了基于互相關(guān)分析的時(shí)間序列孤立點(diǎn)檢測算法和基于SOM神經(jīng)網(wǎng)絡(luò)聚類的非時(shí)間序列孤立點(diǎn)檢測算法，提供了相應(yīng)的數(shù)據(jù)集輸入接口以及檢測結(jié)果輸出界面。

系統(tǒng)設(shè)計(jì)功能主要分為兩個(gè)方面：(1)時(shí)間序列異常值檢測；(2)非時(shí)間序列異常值檢測?？傮w框圖見圖4。

圖4 系統(tǒng)軟件功能框圖

軟件可以用互相關(guān)分析法檢測時(shí)間序列數(shù)據(jù)集中的異常值，也可以用SOM神經(jīng)網(wǎng)絡(luò)聚類法檢測非時(shí)間序列數(shù)據(jù)集中的異常值。針對檢測結(jié)果提供了算法評價(jià)功能，顯示出每次檢測得到的真實(shí)值個(gè)數(shù)、真正異常值個(gè)數(shù)、偽異常值個(gè)數(shù)以及誤判為正常值數(shù)據(jù)個(gè)數(shù)，并利用這四個(gè)數(shù)據(jù)計(jì)算出評價(jià)系數(shù)，反映孤立點(diǎn)檢測結(jié)果的優(yōu)劣。結(jié)果分析時(shí)，系統(tǒng)不僅可以用文字描述出異常值在數(shù)據(jù)集中的位置，而且提供圖形化顯示結(jié)果功能，并將異常值標(biāo)記出來。

為了增加系統(tǒng)軟件的可擴(kuò)展性和開放性，設(shè)計(jì)時(shí)所遵從的總體原則和思路如下：提供數(shù)據(jù)輸入接口，使用戶可以靈活選擇待檢測的數(shù)據(jù)集；將每個(gè)算法封裝成單獨(dú)的模塊和子界面，使用戶可以在系統(tǒng)軟件上增加新的模塊和算法，滿足程序設(shè)計(jì)的模塊化和層次化要求；檢測結(jié)果不僅有文字描述，還有圖形顯示功能，更加具體生動(dòng)，有說服力，便于用戶靈活分析檢測結(jié)果，采用正確的方法處理檢測到的異常值；系統(tǒng)軟件提供檢測結(jié)果評價(jià)和分析功能，幫助用戶合理的調(diào)整孤立點(diǎn)比例閾值，使檢測效果達(dá)到最佳；友好的人機(jī)交互界面設(shè)計(jì)，便于用戶操作。

3.2 人機(jī)交互界面

系統(tǒng)主界面將數(shù)據(jù)集分為時(shí)間序列和非時(shí)間序列兩大類供用戶選擇。當(dāng)用戶選擇時(shí)間序列并點(diǎn)擊開始按鍵時(shí)，會(huì)進(jìn)入互相關(guān)分析法子界面?；ハ嚓P(guān)分析法子界面見圖5。

圖5 互相關(guān)分析子界面

該界面由7個(gè)部分組成。輸入數(shù)據(jù)選擇區(qū)可以讓用戶在計(jì)算機(jī)上選擇一個(gè)Excel數(shù)據(jù)文件作為孤立點(diǎn)檢測的原始數(shù)據(jù)；原始數(shù)據(jù)表格區(qū)可以以表格的形式在界面上展示原始數(shù)據(jù)，方便用戶查看；用戶系統(tǒng)控制區(qū)可以讓用戶輸入判決閾值和預(yù)設(shè)孤立點(diǎn)個(gè)數(shù)，控制檢測系統(tǒng)的啟動(dòng)、停止和復(fù)位；檢測結(jié)果顯示區(qū)可以告訴用戶檢測出的孤立點(diǎn)的數(shù)據(jù)值和其在數(shù)據(jù)集中的具體位置；檢測算法評價(jià)區(qū)可以通過構(gòu)造混淆矩陣計(jì)算四類數(shù)據(jù)個(gè)數(shù)來評價(jià)孤立點(diǎn)檢測算法的檢測率和誤報(bào)率；互相關(guān)函數(shù)圖象區(qū)可以畫出數(shù)值型屬性數(shù)據(jù)相鄰采樣時(shí)刻的互相關(guān)函數(shù)圖像；孤立點(diǎn)數(shù)據(jù)圖像區(qū)可以畫出各個(gè)屬性上數(shù)據(jù)變化的折線圖，并在其上標(biāo)出孤立點(diǎn)的位置。

當(dāng)用戶選擇非時(shí)間序列并點(diǎn)擊開始按鍵時(shí)，會(huì)進(jìn)入SOM神經(jīng)網(wǎng)絡(luò)聚類子界面。SOM神經(jīng)網(wǎng)絡(luò)聚類子界面見圖6。

圖6 SOM神經(jīng)網(wǎng)絡(luò)子界面

該界面由5個(gè)部分組成。與互相關(guān)分析子界面類似，該界面同樣可以選擇輸入數(shù)據(jù)、展示原始數(shù)據(jù)、控制相關(guān)參數(shù)、顯示檢測結(jié)果，同時(shí)還可以畫出神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，標(biāo)出獲勝神經(jīng)元和孤立點(diǎn)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 時(shí)間序列異常值檢測實(shí)驗(yàn)

以10個(gè)國家(澳大利亞、巴西、加拿大、中國、埃及、法國、德國、日本、英國、美國)從1950年到2008年的人口變化數(shù)據(jù)為例驗(yàn)證基于互相關(guān)分析的時(shí)間序列異常值檢測方法。同時(shí)，在數(shù)據(jù)集后補(bǔ)充了2個(gè)非數(shù)值型屬性，每個(gè)非數(shù)值型屬性同樣也有59個(gè)數(shù)據(jù)對象。

為了驗(yàn)證基于互相關(guān)分析的算法，在各個(gè)屬性中人為偽造了8個(gè)異常值，利用基于互相關(guān)分析的算法檢測該數(shù)據(jù)集的異常值情況。8個(gè)異常數(shù)據(jù)點(diǎn)的位置分別為：第4個(gè)屬性的第9個(gè)對象、第7個(gè)屬性的第19個(gè)對象、第9個(gè)屬性的第37個(gè)對象、第10個(gè)屬性的第46～48個(gè)對象、第11個(gè)屬性的第8個(gè)對象和第12個(gè)屬性的第31個(gè)對象。其中第10個(gè)屬性的第46-48個(gè)對象為小范圍內(nèi)聚集的成片孤立點(diǎn)，第11個(gè)屬性的第8個(gè)對象和第12個(gè)屬性的第31個(gè)對象為非數(shù)值型屬性孤立點(diǎn)。檢測結(jié)果如圖7所示。

圖7 時(shí)間序列數(shù)據(jù)集異常值檢測結(jié)果

經(jīng)驗(yàn)證，算法可以檢測出所有的數(shù)值型屬性和非數(shù)值型屬性的異常值，沒有出現(xiàn)虛警漏警的現(xiàn)象，評價(jià)系數(shù)為1。

4.2 空間序列異常值檢測實(shí)驗(yàn)

以每30個(gè)數(shù)據(jù)為一類，共分5類的聚類分析數(shù)據(jù)為例驗(yàn)證基于SOM神經(jīng)網(wǎng)絡(luò)的非時(shí)間序列異常值檢測方法。聚類分析數(shù)據(jù)共有5個(gè)屬性，150個(gè)對象。為了便于驗(yàn)證孤立點(diǎn)檢測的效果，在數(shù)據(jù)集中人為加入4個(gè)孤立點(diǎn)，分別位于第49個(gè)數(shù)據(jù)對象、第50個(gè)數(shù)據(jù)對象、第120個(gè)數(shù)據(jù)對象和第140個(gè)數(shù)據(jù)對象處。其中第49個(gè)數(shù)據(jù)對象和第50個(gè)數(shù)據(jù)對象處的孤立點(diǎn)分布趨于一致，屬于小范圍內(nèi)聚集的成片孤立點(diǎn)，第120個(gè)和第140個(gè)數(shù)據(jù)對象處的孤立點(diǎn)為單獨(dú)出現(xiàn)的孤立點(diǎn)。得到的孤立點(diǎn)檢測結(jié)果如圖8。

圖8 空間序列數(shù)據(jù)集異常值檢測結(jié)果

其中，網(wǎng)線代表SOM神經(jīng)元之間的連接關(guān)系，網(wǎng)線的交點(diǎn)代表SOM神經(jīng)網(wǎng)絡(luò)輸出層的所有神經(jīng)元，數(shù)字標(biāo)記處的神經(jīng)元代表在訓(xùn)練過程中獲勝的神經(jīng)元(右上角的數(shù)字僅代表獲勝神經(jīng)元編號(hào)，只為標(biāo)記使用，無其他含義)。此拓?fù)浣Y(jié)構(gòu)圖的獲得過程詳見異常值檢測算法章節(jié)中的圖3。不難看出，獲勝神經(jīng)元按其分布位置可以自然地分為8類，2號(hào)、5號(hào)和60號(hào)神經(jīng)元各自被劃分為一類。這三個(gè)規(guī)模較小的孤立聚類即為算法檢測出的孤立點(diǎn)。其中第2號(hào)神經(jīng)元代表第120數(shù)據(jù)對象處的單獨(dú)孤立點(diǎn)，第5號(hào)神經(jīng)元代表第140數(shù)據(jù)對象處的單獨(dú)孤立點(diǎn)，第60號(hào)神經(jīng)元代表第49個(gè)數(shù)據(jù)對象和第50個(gè)數(shù)據(jù)對象處的小范圍聚集成片孤立點(diǎn)。檢測結(jié)果直觀，檢測效果良好。

5 結(jié)束語

本文針對異常值檢測這一熱點(diǎn)研究方向，結(jié)合現(xiàn)有方法的不足之處，設(shè)計(jì)了一種時(shí)域空域相結(jié)合的異常值檢測系統(tǒng)。異常值檢測系統(tǒng)是在模塊化、層次化的基礎(chǔ)上搭建了統(tǒng)一的孤立點(diǎn)檢測軟件平臺(tái)，具有一定得開放性和可擴(kuò)展性，可以對各類屬性進(jìn)行異常值分析和數(shù)據(jù)處理，也可以在軟件平臺(tái)上加入其他的孤立點(diǎn)檢測算法，還可以擴(kuò)展到其他領(lǐng)域的數(shù)據(jù)。該平臺(tái)對于時(shí)間序列數(shù)據(jù)集和空間序列數(shù)據(jù)集分別采用了基于互相關(guān)分析和SOM神經(jīng)網(wǎng)絡(luò)的方法來進(jìn)行異常值檢測。經(jīng)驗(yàn)證，異常值檢測系統(tǒng)能夠較好地完成時(shí)域和空域的異常值檢測任務(wù)，具有較高的檢測效率和可靠性。

參考文獻(xiàn)：

[1] 顧 榮.大數(shù)據(jù)處理技術(shù)與系統(tǒng)研究[D].南京：南京大學(xué),2016.

[2] 謝方方.基于距離的孤立點(diǎn)挖掘在計(jì)算機(jī)取證中的應(yīng)用研究[D].山東師范大學(xué),2014.

[3] Xie Z, Li X, Wu W, et al. An Improved Outlier Detection Algorithm to Medical Insurance[M]. Intelligent Data Engineering and Automated Learning-IDEAL 2016. Springer International Publishing, 2016.

[4] Christy A, Gandhi G M, Vaithyasubramanian S. Cluster Based Outlier Detection Algorithm for Healthcare Data[J]. Procedia Computer Science, 2015, 50:209-215.

[5] Tao Li. Novel heuristic dual-ant clustering algorithm for network intrusion outliers detection[J]. Optik-International Journal for Light and Electron Optics, 2015, 126(4):494-497.

[6] Carneiro N, Figueira G, Costa M. A data mining based system for credit-card fraud detection in e-tail[J]. Decision Support Systems, 2017, 95.

[7] Abid A, Masmoudi A, Kachouri A, et al. Outlier Detection in Wireless Sensor Networks Based on OPTICS Method for Events and Errors Identification[J]. Wireless Personal Communications, 2017(1):1-13.

[8] 鄢團(tuán)軍, 劉 勇. 孤立點(diǎn)檢測算法與應(yīng)用[J]. 三峽大學(xué)學(xué)報(bào)(自然科學(xué)版), 2009, 31(1):98-103.

[9] 楊 櫻. 基于強(qiáng)化學(xué)習(xí)的績優(yōu)股票預(yù)測系統(tǒng)研究[D]. 秦皇島：燕山大學(xué), 2006.

[10] Cao C, Zhang W, Wang Z, et al. The Diagnosis Method of Stator Winding Faults in PMSMs Based on SOM Neural Networks[J]. Energy Procedia, 2017, 105:2295-2301.