吳 瓊，李永飛，李銘洋

（華北科技學(xué)院計算機(jī)學(xué)院，三河 065200）

0 引言

異常數(shù)據(jù)通常也稱為離群值、噪聲等。Edgeworth把異常值定義為“顯然嚴(yán)重偏離樣本集合中其他觀測值的觀測值”。異常數(shù)據(jù)檢測是指從數(shù)據(jù)中找出明顯與其他數(shù)據(jù)不同的數(shù)據(jù)，最早采用基于統(tǒng)計學(xué)的方法，現(xiàn)在已成為數(shù)據(jù)挖掘的四大任務(wù)之一。異常數(shù)據(jù)所占比例較小但卻可能蘊(yùn)含豐富的內(nèi)容，因此異常數(shù)據(jù)檢測具有重要的研究意義和應(yīng)用價值，對保障數(shù)據(jù)可信性也有重要作用。

從Knox等提出“基于距離的異常數(shù)據(jù)”的概念以來，異常數(shù)據(jù)檢測已經(jīng)成為數(shù)據(jù)挖掘中的一個研究熱點(diǎn)。異常值可能來源于機(jī)械故障、儀器錯誤、人為錯誤等，其產(chǎn)生往往不可避免，而且會影響數(shù)據(jù)分析的結(jié)果，甚至可能造成嚴(yán)重后果。目前，異常數(shù)據(jù)檢測已經(jīng)廣泛應(yīng)用于諸多領(lǐng)域。在醫(yī)療衛(wèi)生行業(yè)，異常數(shù)據(jù)檢測可以及時發(fā)現(xiàn)病人的身體指標(biāo)異常，提早治療，避免病情惡化。在生態(tài)環(huán)境監(jiān)測領(lǐng)域，可以對各項(xiàng)監(jiān)測指標(biāo)的異常情況盡早采取應(yīng)對措施。在應(yīng)急管理的事前數(shù)據(jù)采集和處理階段，異常數(shù)據(jù)實(shí)時檢測可以對突發(fā)事件及時響應(yīng)，進(jìn)而及時調(diào)整應(yīng)對措施。

近年來，隨著大數(shù)據(jù)時代的到來，海量數(shù)據(jù)的產(chǎn)生對數(shù)據(jù)處理的方法提出了更多的挑戰(zhàn)。異常數(shù)據(jù)檢測的實(shí)時性和準(zhǔn)確性方面有了更高的要求。異常數(shù)據(jù)檢測的核心問題是異常檢測算法模型的構(gòu)建，它將直接影響異常檢測的檢測率。

本文主要介紹傳統(tǒng)異常數(shù)據(jù)檢測方法和異常數(shù)據(jù)實(shí)時檢測方法。首先介紹常用的異常檢測方法以及它們常用的檢測算法，主要分為基于統(tǒng)計學(xué)和基于機(jī)器學(xué)習(xí)兩大類；接著介紹異常數(shù)據(jù)實(shí)時檢測方法以及采用的算法；最后對異常數(shù)據(jù)實(shí)時檢測的發(fā)展趨勢進(jìn)行總結(jié)和展望。

1 異常檢測方法

1.1 基于統(tǒng)計學(xué)的方法

基于統(tǒng)計學(xué)的異常檢測方法，一般建立一個數(shù)據(jù)分布模型，然后計算對象符合該模型的概率，將低概率的對象視為異常。最簡單的方法有箱線圖、3σ準(zhǔn)則、Grubbs檢驗(yàn)等，這些方法都需要假設(shè)數(shù)據(jù)服從某種分布，然后利用數(shù)據(jù)去進(jìn)行參數(shù)估計。復(fù)雜一些的還有混合高斯建模、基于馬爾科夫模型和時間序列建模，等等?；诮y(tǒng)計學(xué)的方法優(yōu)點(diǎn)是魯棒性較好，適合低維度數(shù)據(jù)。但是處理高維數(shù)據(jù)受限制，而且受數(shù)據(jù)分布和模型參數(shù)的影響，因此限制了它的應(yīng)用范圍。

1.2 基于機(jī)器學(xué)習(xí)的方法

機(jī)器學(xué)習(xí)算法按照是否需要人工標(biāo)記可以分為無監(jiān)督、有監(jiān)督和半監(jiān)督模式。無監(jiān)督模式不需要任何標(biāo)簽，也不依賴完善的先驗(yàn)知識，因此在異常檢測領(lǐng)域應(yīng)用更加廣泛。

基于聚類的異常檢測方法將數(shù)據(jù)分為不同的簇，而異常數(shù)據(jù)是不屬于任何一個簇的。

聚類分析屬于無監(jiān)督模式，不依賴預(yù)先對數(shù)據(jù)的標(biāo)記和訓(xùn)練，可以根據(jù)數(shù)據(jù)的相似度把數(shù)據(jù)劃分為多個類或類簇。K-means算法邏輯簡單、計算復(fù)雜度低、聚類效果也不錯，是應(yīng)用最廣泛的聚類算法之一。由于異常數(shù)據(jù)檢測的結(jié)果依賴于聚類算法的分析結(jié)果，因此要求在使用K-means算法實(shí)現(xiàn)異常檢測時能夠解決聚類結(jié)果不穩(wěn)定的問題。文獻(xiàn)［9］提出基于近鄰傳播算法和最大最小距離算法結(jié)合使用的APMMD算法，利用近鄰傳播算法和最大最小距離思想計算初始聚類中心，并將獲得的初始聚類中心應(yīng)用于K-means聚類算法中，使迭代次數(shù)降低，其聚類結(jié)果保持穩(wěn)定且具有較高的異常檢測的準(zhǔn)確率。

基于近鄰度的方法包括基于距離和基于密度的方法。這種方法不需要假設(shè)數(shù)據(jù)的分布。

（1）基于距離的方法?；诰嚯x的方法通過計算數(shù)據(jù)與近鄰數(shù)據(jù)之間的距離來判斷出異常數(shù)據(jù)，一般采用歐式距離和曼哈頓距離，主要應(yīng)用于全局近鄰。常用的算法是K-最近鄰（K-nearest neighbor）算法，它是一種簡單易用、有監(jiān)督模式的機(jī)器學(xué)習(xí)算法。KNN算法首先找到k個最近的鄰居，然后根據(jù)k個最近的鄰居計算異常分?jǐn)?shù)。

（2）基于密度的方法?；诿芏鹊姆椒ㄅc基于近鄰度的異常點(diǎn)檢測密切相關(guān)，是在基于距離的基礎(chǔ)上，把數(shù)據(jù)之間的距離和周圍鄰近的數(shù)據(jù)個數(shù)相結(jié)合。它通過比較每個點(diǎn)和其鄰域點(diǎn)的密度，當(dāng)點(diǎn)與包圍其的鄰居的密度不同時，被認(rèn)定為異常點(diǎn)。經(jīng)典的方法是Breunig等提出的局部離群點(diǎn)方法LOF（the local outlier factor）。LOF中計算距離采用歐式距離，LOF為每個點(diǎn)分配一個局部離群因子（LOF），LOF的大小表示該點(diǎn)的局部密度與其最近鄰居的局部密度之比，LOF越高，則表明是異常點(diǎn)的可能性越大。基于連通性的異常檢測算法COF（connectivity-based outlier factor）的局部密度通過鏈?zhǔn)骄嚯x方式計算求出。LOF和COF算法都是借助數(shù)據(jù)的相對密度計算異常分值，得分越高越可能是異常數(shù)據(jù)。由于LOF數(shù)據(jù)量的增多該算法的時間復(fù)雜度較高，文獻(xiàn)［13］提出改進(jìn)的LOF算法即K-LOF算法。先利用計算效率高的K-means聚類算法對數(shù)據(jù)進(jìn)行檢測預(yù)處理獲得初選異常數(shù)據(jù)，然后用基于密度的LOF算法再挖掘出最終的異常數(shù)據(jù)。結(jié)果表明，相比LOF算法K-LOF不但提高了檢測的精確度，也降低了異常數(shù)據(jù)檢測的計算復(fù)雜度。

另外，還有一些專用的異常檢測方法，如One Class SVM和孤立森林（Isolation Forest）。這類算法的思路是不需要利用統(tǒng)計、距離和密度的量化指標(biāo)去表達(dá)異常數(shù)據(jù)的疏離程度，而是直接描述正常數(shù)據(jù)與異常數(shù)據(jù)的疏離程度。

（1）One Class SVM算法。One Class SVM屬于無監(jiān)督學(xué)習(xí)算法，不需要標(biāo)記訓(xùn)練集和輸出標(biāo)簽。該算法的思路比較簡單，首先找一個超平面將正常數(shù)據(jù)找出來，再通過正常數(shù)據(jù)的特征去學(xué)習(xí)一個決策邊界，然后通過這個邊界去判斷新來的數(shù)據(jù)是否與訓(xùn)練數(shù)據(jù)類似，超出邊界則為異常。由于該算法只有一個Class，比較適合解決極度不平衡的數(shù)據(jù)異常檢測。文獻(xiàn)［14］得出One Class SVM算法核函數(shù)計算時間比較長，因此不適合用于大量數(shù)據(jù)的處理。

（2）孤立森林算法。孤立森林算法是2008年由南京大學(xué)周志華教授團(tuán)隊(duì)首次提出，2012年又進(jìn)行了改進(jìn)。孤立森林算法屬于無監(jiān)督學(xué)習(xí)，它通過樣本的疏密程度去描述樣本之間的差異。異常點(diǎn)被定義為“容易被孤立的離群點(diǎn)”。它由多個iTree（孤立二叉樹）構(gòu)成，每個iTree的構(gòu)建是從數(shù)據(jù)特征集合中隨機(jī)選擇一個分割值，通過這個分割值對數(shù)據(jù)進(jìn)行劃分然后構(gòu)造左右子樹，直到所有數(shù)據(jù)被劃分或已經(jīng)達(dá)到樹的高度限制，其中只關(guān)心路徑較短的點(diǎn)，它們更可能是異常點(diǎn)。這種劃分情況下，異常數(shù)據(jù)點(diǎn)在iTree中更靠近根節(jié)點(diǎn)，同時低密度的點(diǎn)遠(yuǎn)離大多數(shù)樣本，將很早被孤立。孤立森林算法是線性時間復(fù)雜度，與K-means、LOF等算法相比較，它不需要計算有關(guān)的距離、密度的指標(biāo)，處理異常數(shù)據(jù)快速且高效。因此適合實(shí)時在線異常數(shù)據(jù)檢測。表1列出了常用異常檢測算法的優(yōu)缺點(diǎn)比較。

表1 異常檢測算法優(yōu)缺點(diǎn)比較

2 基于流處理框架的異常數(shù)據(jù)實(shí)時檢測

由于傳統(tǒng)方法不能滿足海量的動態(tài)化數(shù)據(jù)的實(shí)時異常檢測的需求。因此出現(xiàn)了基于流處理框架的新方法。動態(tài)化的數(shù)據(jù)，也稱為數(shù)據(jù)流，它具有動態(tài)產(chǎn)生且事先無法預(yù)知的特點(diǎn)。動態(tài)數(shù)據(jù)需要剛到達(dá)就及時處理，同時滿足數(shù)據(jù)實(shí)時性異常檢測要求，數(shù)據(jù)處理效率要求更高。目前異常數(shù)據(jù)實(shí)時檢測中主要采用基于Storm、Spark等實(shí)時流處理框架結(jié)合機(jī)器學(xué)習(xí)算法和基于滑動窗口的方法等。依靠流數(shù)據(jù)分析處理方法實(shí)現(xiàn)異常檢測，可以用在實(shí)時數(shù)據(jù)分析場景中?；诹魈幚砜蚣艿漠惓?shù)據(jù)實(shí)時檢測方法對比如表2所示。

表2 基于流處理框架的異常數(shù)據(jù)實(shí)時檢測方法對比

2.1 結(jié)合機(jī)器學(xué)習(xí)算法的方法

Hadoop核心是分布式文件系統(tǒng)HDFS和并行化計算模型MapReduce。隨著海量數(shù)據(jù)的產(chǎn)生，為了加快數(shù)據(jù)的處理速度則采用并行化計算。文獻(xiàn)［17］為了解決初始聚類中心敏感問題，利用最大最小距離的思想改進(jìn)了K-means聚類算法，同時采用MapReduce并行化實(shí)現(xiàn)該算法的分布式聚類。結(jié)果表明提高了算法的計算效率，并且降低了算法執(zhí)行過程的通信開銷。文獻(xiàn)［18］采用基于Hadoop平臺中的MapReduce并行計算框架，并使用基于密度的LOF算法的分布式財務(wù)異常數(shù)據(jù)分析模型。采用MapReduce并行化計算框架，算法在運(yùn)行時可以在多個計算節(jié)點(diǎn)運(yùn)行。將MapReduce框架和加入領(lǐng)域關(guān)系的LOF算法結(jié)合使用，可以并行計算，進(jìn)而提高了數(shù)據(jù)處理速度和算法的準(zhǔn)確率。

由于孤立森林算法的每棵樹隨機(jī)采樣獨(dú)立生成，具有很好的處理大數(shù)據(jù)的能力和速度，可以進(jìn)行并行化處理。同時還存在孤立二叉樹間異常能力的差異性，文獻(xiàn)［19］采用加權(quán)計算測試樣本在孤立森林算法中異常值，同時采用基于內(nèi)存的Spark框架不同于Hadoop框架中從HDFS中讀取數(shù)據(jù)，比較適合迭代次數(shù)多的算法。結(jié)果表明在大規(guī)模數(shù)據(jù)下可以加快檢測速度和提高檢測精度。文獻(xiàn)［20］提出基于HDFS框架的數(shù)據(jù)異常檢測方法，利用分布式HDFS框架可以快速準(zhǔn)確地存儲數(shù)據(jù)，采用基于支持向量數(shù)據(jù)描述并結(jié)合最小閉包球算法實(shí)現(xiàn)實(shí)時異常檢測。該方法降低了時間復(fù)雜度，提高了異常檢測率，并減少了運(yùn)行時間。

由于K-means聚類算法在處理大量數(shù)據(jù)時效率較低，文獻(xiàn)［21］提出了基于Apache Flink流計算框架結(jié)合流處理思想的SK-means（stream K-means）方法，提高了算法的執(zhí)行效率，聚類效果更好并且可以較快地進(jìn)行異常數(shù)據(jù)檢測。文獻(xiàn)［22］提出基于分布式流處理框架Spark Streaming，采用流回歸機(jī)器學(xué)習(xí)算法和正態(tài)統(tǒng)計技術(shù)相結(jié)合的方法進(jìn)行數(shù)據(jù)異常檢測。該方法可以實(shí)時且準(zhǔn)確分析瓦斯?jié)舛攘鲾?shù)據(jù)中的異常數(shù)據(jù)，解決了流數(shù)據(jù)中大數(shù)據(jù)機(jī)器學(xué)習(xí)處理和實(shí)時性問題。文獻(xiàn)［23］提出基于Storm實(shí)時處理平臺采用動態(tài)KNN的累積距離的異常檢測方法。該方法適用于實(shí)時處理框架，每一組時間序列只用動態(tài)地保存?zhèn)€時間點(diǎn)的數(shù)值，可以簡化操作和節(jié)省內(nèi)存。同時可以動態(tài)地觀察數(shù)據(jù)檢測結(jié)果。

2.2 基于結(jié)合滑動窗口的方法

滑動窗口機(jī)制可以處理最新到達(dá)的數(shù)據(jù)，文獻(xiàn)［24］提出基于Storm流數(shù)據(jù)框架的滑動窗口計算方法。采用Storm平臺上實(shí)現(xiàn)滑動窗口計算方法進(jìn)行實(shí)時分析，并通過增大滑動窗口的吞吐量，提高了數(shù)據(jù)異常檢測的實(shí)時處理效率。但是該方法只對數(shù)值型數(shù)據(jù)實(shí)現(xiàn)了實(shí)時處理，還需要進(jìn)一步研究。文獻(xiàn)［25］提出基于Storm流處理的數(shù)據(jù)實(shí)時處理方法，采用基于滑動時間窗口實(shí)現(xiàn)異常數(shù)據(jù)檢測?？梢詫?shí)現(xiàn)在Storm上實(shí)時監(jiān)測數(shù)據(jù)預(yù)處理、數(shù)據(jù)異常檢測。

為了從海量數(shù)據(jù)中實(shí)時且高效地檢測出異常值，文獻(xiàn)［26］提出了Flink的異常檢測方法，針對實(shí)時流數(shù)據(jù)，首先用Kafka對數(shù)據(jù)進(jìn)行實(shí)時預(yù)處理，然后在Flink平臺上利用ARIMA模型進(jìn)行預(yù)測。

3 基于新型算法的異常數(shù)據(jù)實(shí)時檢測

隨著機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域的發(fā)展，又出現(xiàn)了一些新穎且有效的異常數(shù)據(jù)實(shí)時檢測方法?；谛滦退惴ǖ漠惓?shù)據(jù)實(shí)時檢測方法如表3所示。

表3 基于新型算法的異常數(shù)據(jù)實(shí)時檢測方法比較

3.1 基于層級實(shí)時記憶的方法

文獻(xiàn)［27］提出基于層級實(shí)時記憶（hierarchical temporal memory,HTM）的時間序列異常檢測算法，HTM算法是一種仿生物結(jié)構(gòu)的機(jī)器學(xué)習(xí)算法，它不需要采用滑動窗口法批處理數(shù)據(jù)，就可以實(shí)現(xiàn)對數(shù)據(jù)的實(shí)時檢測。它是“記憶-預(yù)測”的運(yùn)行模式，將復(fù)雜的問題轉(zhuǎn)化為模式識別，可以提前預(yù)警數(shù)據(jù)異常。隨著云計算技術(shù)的發(fā)展，云資源的運(yùn)行會產(chǎn)生海量的時序數(shù)據(jù)。文獻(xiàn)［28］將基于分層時間記憶算法用在企業(yè)多云時序數(shù)據(jù)實(shí)時監(jiān)測中，可以實(shí)現(xiàn)實(shí)時異常檢測。由于云資源監(jiān)測要實(shí)現(xiàn)自動化實(shí)時異常檢測，而HTM算法存儲大量時序數(shù)據(jù)符合實(shí)時流式分析、無監(jiān)督以及動態(tài)數(shù)據(jù)在線學(xué)習(xí)的要求。因?yàn)樵撍惴ㄟ\(yùn)用到監(jiān)測系統(tǒng)中可以高效地檢測異常，并提高企業(yè)的運(yùn)維效率。HTM算法已經(jīng)應(yīng)用到許多數(shù)據(jù)智能處理領(lǐng)域如異常檢測、數(shù)據(jù)預(yù)測。針對數(shù)據(jù)量的不斷增長，快速處理的需要，以及無法并行化計算的問題，文獻(xiàn)［29］提出了面向多核的并發(fā)HTM空間池算法，將HTM空間池區(qū)域分區(qū)，各區(qū)獨(dú)立完成訓(xùn)練任務(wù)并且利用CPU中的計算核心，實(shí)現(xiàn)多個核心并行完成。使用基于多核心和共享內(nèi)存的大數(shù)據(jù)平臺Phoenix，避免帶來額外的通信開銷，并且提高了算法的執(zhí)行效率和預(yù)測準(zhǔn)確率。

3.2 基于長短期記憶神經(jīng)網(wǎng)絡(luò)的方法

對于時間序列數(shù)據(jù)，直接采用LSTM算法自適應(yīng)性不高，而且單一模型檢測結(jié)果準(zhǔn)確率不高。文獻(xiàn)［30］提出通過LSTM網(wǎng)絡(luò)和自動編碼器進(jìn)行不同組合預(yù)測模型，進(jìn)而影響檢測器的性能。由于流數(shù)據(jù)數(shù)量大、到達(dá)快速，單個平穩(wěn)模型可能無法滿足數(shù)據(jù)實(shí)時異常檢測的要求。文獻(xiàn)［31］提出了基于LSTMs-Autoencoder的流數(shù)據(jù)異常檢測算法。該算法采用多個LSTM單元，形成了一個深層遞歸的神經(jīng)網(wǎng)絡(luò)（LSTMs），然后將遞歸神經(jīng)網(wǎng)絡(luò)與自動編碼器相結(jié)合，實(shí)現(xiàn)了對流數(shù)據(jù)的實(shí)時檢測并保證檢測結(jié)果準(zhǔn)確，同時還能應(yīng)對考慮概念漂移現(xiàn)象。

4 總結(jié)和展望

基于統(tǒng)計的方法由于數(shù)據(jù)分布快速且高效，魯棒性較好適合低維數(shù)據(jù)，但對高維數(shù)據(jù)處理受限制?；跈C(jī)器學(xué)習(xí)的方法克服了傳統(tǒng)統(tǒng)計方法不能處理高維數(shù)據(jù)的問題。隨著數(shù)據(jù)量的增多、動態(tài)數(shù)據(jù)的產(chǎn)生，對處理數(shù)據(jù)的速度、實(shí)時性有了更高的要求。大數(shù)據(jù)中的批處理方式處理速度較慢，可以采用基于Storm、Spark、Flink等流式處理框架來實(shí)現(xiàn)實(shí)時計算和分析，并且高效準(zhǔn)確地檢測出異常值。隨著機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域的發(fā)展，又出現(xiàn)了基于層級實(shí)時記憶的異常檢測算法，它不需要采用滑動窗口法批處理數(shù)據(jù)，就可以實(shí)現(xiàn)對數(shù)據(jù)的實(shí)時檢測。

隨著海量數(shù)據(jù)以及動態(tài)數(shù)據(jù)的產(chǎn)生，除了采用流處理框的并行化和實(shí)時的計算方法，還需要繼續(xù)改進(jìn)算法的性能，進(jìn)而實(shí)時檢測更多的異常數(shù)據(jù)。比如，雖然HTM算法具有較強(qiáng)的自適應(yīng)性，可以實(shí)現(xiàn)異常數(shù)據(jù)實(shí)時檢測。但它也存在時間復(fù)雜度的問題，要使之應(yīng)用廣泛還需要進(jìn)一步研究改進(jìn)。與此同時，對于數(shù)據(jù)類型的增多和應(yīng)用領(lǐng)域的擴(kuò)大，可以研究通過豐富數(shù)據(jù)編碼的方式來實(shí)現(xiàn)不同類型的數(shù)據(jù)異常檢測，同時實(shí)時數(shù)據(jù)異常檢測效果更好。面對數(shù)據(jù)不平衡等問題，可以通過從大量數(shù)據(jù)中學(xué)習(xí)獲得準(zhǔn)確有效的特征，建立基于深度學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)模型，進(jìn)而提高異常檢測的效率。對于不平衡數(shù)據(jù)的處理也可以采用基于深度學(xué)習(xí)的異常檢測方法。在異常數(shù)據(jù)實(shí)時檢測的未來發(fā)展中，基于層級實(shí)時記憶的和神經(jīng)網(wǎng)絡(luò)模型的方法改進(jìn)，以及基于深度學(xué)習(xí)的方法是一種趨勢。

5 結(jié)語

（1）新型的異常數(shù)據(jù)實(shí)時檢測方法不僅加快了海量動態(tài)數(shù)據(jù)的處理速度，也可以進(jìn)行實(shí)時異常數(shù)據(jù)檢測并實(shí)時反饋檢測結(jié)果。與此同時，還提高了異常數(shù)據(jù)檢測的效率和準(zhǔn)確率。

（2）異常檢測方法都需要快速且實(shí)時地檢測出結(jié)果，這樣才能最大程度地挽回?fù)p失或避免發(fā)生更大的事故。異常數(shù)據(jù)實(shí)時檢測還要繼續(xù)進(jìn)一步研究，準(zhǔn)確、高效地應(yīng)用到工業(yè)生產(chǎn)、醫(yī)療技術(shù)、物聯(lián)網(wǎng)檢測、應(yīng)急管理等領(lǐng)域中才具有實(shí)際意義。因此，異常數(shù)據(jù)實(shí)時檢測方法具有廣闊的應(yīng)用前景。