，

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

0 引言

隨著互聯(lián)網(wǎng)的爆炸式發(fā)展和云時代的來臨，人們利用網(wǎng)絡(luò)獲取收集信息的同時，數(shù)據(jù)量呈現(xiàn)出指數(shù)爆炸式的增長，大數(shù)據(jù)吸引了越來越多的關(guān)注。大數(shù)據(jù)的5 V特點：Volume(大量)、Velocity(高速)、Variety(多樣)、Value(低價值密度)、Veracity(真實性)，使得傳統(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)、類別的描述、類別的判斷和孤立點發(fā)現(xiàn)[2]。孤立點發(fā)現(xiàn)是數(shù)據(jù)挖掘中的一個重要的分支，已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的研究熱點，并且在天氣預(yù)報、股市分析、市場調(diào)研、藥品研發(fā)[3]、醫(yī)療保險[4]、網(wǎng)絡(luò)入侵檢測[5]、商業(yè)欺詐檢測[6]、飛參數(shù)據(jù)、無線傳感器網(wǎng)絡(luò)[7]等領(lǐng)域得到了廣泛的應(yīng)用。

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

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

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

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

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

2 異常值檢測算法

2.1 時間序列異常值檢測

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

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

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

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

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

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

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

2.2 空間序列異常值檢測

典型SOM網(wǎng)共有兩層，輸入層模擬的是人眼的視網(wǎng)膜，用于接收外界數(shù)據(jù)，一般為單層神經(jīng)元排列；輸出層模擬的是人腦的大腦皮層，用于處理輸入層獲得的數(shù)據(jù)信息，輸出層的每個神經(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é)點權(quán)值向量、學(xué)習(xí)率和鄰域半徑進(jìn)行初始化。對輸入向量進(jìn)行歸一化。第二，對于每一個輸入向量，利用歐式距離相似性度量準(zhǔn)則尋找與其對應(yīng)的競爭獲勝神經(jīng)元。第三，利用梯度下降法，對獲勝節(jié)點和其鄰域范圍內(nèi)神經(jīng)元集合中的每一個節(jié)點都進(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ù)時，退出訓(xùn)練學(xué)習(xí)過程，即可得到訓(xùn)練好的SOM神經(jīng)網(wǎng)絡(luò)。否則轉(zhuǎn)入第二步。第六，將4-鄰域內(nèi)沒有其他獲勝神經(jīng)元，并且類規(guī)模很小的孤立聚類視為孤立點輸出。算法原理的整體框圖見圖3。

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

3 異常值檢測平臺

3.1 檢測平臺概述

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

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

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

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

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

3.2 人機(jī)交互界面

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

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

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

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

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

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

4 實驗結(jié)果與分析

4.1 時間序列異常值檢測實驗

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

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

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

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

4.2 空間序列異常值檢測實驗

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

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

[2] 謝方方.基于距離的孤立點挖掘在計算機(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)軍, 劉 勇. 孤立點檢測算法與應(yīng)用[J]. 三峽大學(xué)學(xué)報(自然科學(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.