基于聚類和核密度估計假設(shè)檢驗的異常值檢測方法

周春蕾 田品卓 楊晨琛 王 皓

(1.南京大學(xué)計算機(jī)軟件新技術(shù)國家重點實驗室，南京，210023; 2.江蘇方天電力技術(shù)有限公司，南京，211102)

基于聚類和核密度估計假設(shè)檢驗的異常值檢測方法

周春蕾1,2田品卓1楊晨琛1,2王 皓1

(1.南京大學(xué)計算機(jī)軟件新技術(shù)國家重點實驗室，南京，210023; 2.江蘇方天電力技術(shù)有限公司，南京，211102)

異常值檢測是數(shù)據(jù)挖掘領(lǐng)域中的核心問題，在工業(yè)生產(chǎn)中也有著廣泛的應(yīng)用。準(zhǔn)確高效的異常值檢測方法能夠及時反映出工業(yè)系統(tǒng)運(yùn)行狀態(tài)，為相關(guān)人員提供參考，而傳統(tǒng)的異常值檢測方法無法很好地檢測出變化模式復(fù)雜、變化范圍小、具有流數(shù)據(jù)特性的數(shù)據(jù)中的異常值。因此，本文提出了一種新的針對該類型數(shù)據(jù)的異常值檢測方法：首先通過對數(shù)據(jù)進(jìn)行聚類劃分，將相似的數(shù)據(jù)進(jìn)行歸類，從而將原本復(fù)雜的數(shù)據(jù)分布拆解成為每個聚類下簡單數(shù)據(jù)分布的疊加；然后使用核密度估計假設(shè)檢驗的方法對待檢測數(shù)據(jù)進(jìn)行異常值檢測。在標(biāo)準(zhǔn)數(shù)據(jù)集和真實數(shù)據(jù)上的實驗結(jié)果表明，該方法相比于傳統(tǒng)的異常值檢測方法在檢測精度上有一定的提升。

異常值檢測；聚類；假設(shè)檢驗；核密度估計

引 言

異常值檢測是數(shù)據(jù)挖掘領(lǐng)域中的核心問題，近十幾年得到了廣泛的關(guān)注[1-3]。與此同時，異常值檢測在金融詐騙檢測[4]、抗網(wǎng)絡(luò)入侵[5]和疾病診斷[6]等領(lǐng)域也有著非常廣泛的應(yīng)用。異常值檢測主要關(guān)注如何甄別出數(shù)據(jù)集中不符合預(yù)期或不符合正常變化模式的異常數(shù)據(jù)點[7]。在檢測完成后，可以通過數(shù)據(jù)預(yù)處理對異常值進(jìn)行標(biāo)注或剔除，獲得不含噪聲的數(shù)據(jù)，從而提升機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法的準(zhǔn)確率。此外，檢測到并輸出的異常值也可為相關(guān)人員提供參考。

關(guān)于異常值的定義，Hawkins首先提出如果數(shù)據(jù)集中某個觀察值與其他值有較大的偏差，則兩者來源于不同的產(chǎn)生機(jī)制，該觀察值為一個異常[8]；Johnson等則認(rèn)為異常值為數(shù)據(jù)集中一些表現(xiàn)模式和其他點不一致的數(shù)據(jù)點[9]。迄今為止，國內(nèi)外學(xué)者提出了包括基于概率密度的異常值檢測方法、基于距離的異常值檢測方法、基于時間序列特性的異常值檢測方法以及基于流數(shù)據(jù)的異常值檢測方法等來對數(shù)據(jù)中可能存在的異常進(jìn)行檢測，如Barnett等[10]利用異常值往往出現(xiàn)概率很低的假設(shè)，使用多維高斯分布等方法來得到數(shù)據(jù)的概率密度函數(shù)，然后計算出數(shù)據(jù)出現(xiàn)的概率，將出現(xiàn)概率低的點標(biāo)記為異常點。該方法的效果取決于能否精確地得到數(shù)據(jù)的概率密度函數(shù)，當(dāng)數(shù)據(jù)分布很復(fù)雜，通過多維高斯分布擬合得到的概率密度函數(shù)和真實的概率密度函數(shù)存在很大差距時，該方法無法準(zhǔn)確地得到異常值。Knorr等[11]利用異常值在數(shù)據(jù)空間中往往是一些孤立點，它們與正常點存在較遠(yuǎn)的距離，所在區(qū)域內(nèi)數(shù)據(jù)密度很低的特性，使用k近鄰算法來尋找小于一定距離的最近鄰數(shù)量，如果近鄰數(shù)量小于一定的閾值δ，就認(rèn)為其為異常點。k近鄰算法的時間復(fù)雜度為O(D*N)，其中D為數(shù)據(jù)的維度，N為數(shù)據(jù)的樣本數(shù)量。盡管該方法在尋找近鄰點時可以采用Bentley提出的KD-Tree(K-dimensional tree)[12]樹形數(shù)據(jù)結(jié)構(gòu)將算法的時間復(fù)雜度減少到O(D*logN)，但仍然無法有效地處理維度較高、數(shù)據(jù)量較大的數(shù)據(jù)。Breunig等[13]利用聚類算法將數(shù)據(jù)進(jìn)行聚類，認(rèn)為數(shù)量較小的類是異常類，然后衡量數(shù)據(jù)點的局部異常值因子(Local outlier factor, LOF)來判斷其是否為異常點。LOF值實際反映的是樣本點所在區(qū)域的樣本密度與該點近鄰所在區(qū)域的樣本密度之間的關(guān)系，而在數(shù)量大、數(shù)據(jù)變化范圍小及每個點所在區(qū)域的數(shù)據(jù)密度都比較大的情況下，各個點的LOF值將非常接近，因此無法精確得到異常點。蘇衛(wèi)星等[14]利用時間序列的變化在時間上具有延續(xù)性，所以異常值往往是一些劇烈變化、不符合之前時間序列變化特性的數(shù)據(jù)點的假設(shè)，使用自回歸模型(Auto regressive,AR)來對數(shù)據(jù)進(jìn)行預(yù)測，通過分析預(yù)測的殘差結(jié)果是否有非常劇烈的變化來進(jìn)行異常值的判斷。賀力克等[15]通過對時間序列進(jìn)行窗口劃分，根據(jù)前后窗口內(nèi)時間序列的各種統(tǒng)計量特征來判斷時間序列是否發(fā)生突變或者跳變，從而確定是否存在異常值。由于基于時間序列的異常值檢測方法已存在前提假設(shè)，這類方法對于數(shù)據(jù)中存在的跳變異常點能夠進(jìn)行很好的識別，但是卻無法準(zhǔn)確地識別出漸變的異常點。Moradi等[16]使用滑動窗口的方法對窗口內(nèi)的數(shù)據(jù)進(jìn)行異常值檢測，對每個待檢測窗口中的數(shù)據(jù)，使用K-Means++方法進(jìn)行聚類，聚類后數(shù)據(jù)量較少的類中的點即被認(rèn)為是異常點。該方法只利用了當(dāng)前窗口內(nèi)的數(shù)據(jù)信息，能夠檢測出不符合當(dāng)前窗口中的數(shù)據(jù)變化規(guī)律的異常值，但是無法檢測出全局的異常值。

此外，當(dāng)存在異常值標(biāo)注時，可以利用一些監(jiān)督方法對異常值進(jìn)行檢測，例如Ngan等[17]利用正常數(shù)據(jù)訓(xùn)練一個單類支持向量機(jī)來對數(shù)據(jù)點進(jìn)行分類；Pawlowski等[18]利用貝葉斯網(wǎng)絡(luò)進(jìn)行異常值判斷。而對具有特定結(jié)構(gòu)信息的數(shù)據(jù)，也存在針對圖結(jié)構(gòu)的[19]和針對高維數(shù)據(jù)的異常值檢測方法[20]等，由于篇幅所限，在此不做具體討論。

針對變化模式復(fù)雜、變化范圍很小、有時間序列特性的流數(shù)據(jù)異常值檢測，本文提出了一種基于聚類和核密度估計(Kernel density estimation，KDE)[21]假設(shè)檢驗的異常值檢測方法。該方法利用正常數(shù)據(jù)是由多個簡單概率函數(shù)疊加而成的假設(shè)。首先采用基于層次方法的平衡迭代規(guī)約和聚類(Balanced iterative reducing and clustering using hierarchies,BIRCH)[22]算法對數(shù)據(jù)進(jìn)行劃分，將正常數(shù)據(jù)中相似的、具有相同變化規(guī)律的數(shù)據(jù)劃分到同一類中，從而將原始復(fù)雜的數(shù)據(jù)分布簡化為多個簡單數(shù)據(jù)分布的疊加；然后在每個類中使用核密度估計假設(shè)檢驗的方法，對待檢測樣本進(jìn)行異常值檢測。實驗結(jié)果表明，該方法相比基于高斯分布、基于時間序列和基于流數(shù)據(jù)的異常值檢測方法，具有更高的精度，能夠更好地檢測出該類型數(shù)據(jù)中的異常點和工業(yè)生產(chǎn)中傳感器產(chǎn)生的變化模式復(fù)雜的流數(shù)據(jù)中的異常值。

1 無監(jiān)督流數(shù)據(jù)異常值檢測

針對具有變化模式復(fù)雜、變化范圍很小、有時間序列特性的流數(shù)據(jù)異常值檢測問題，需要在無監(jiān)督的情況下，從大量的歷史數(shù)據(jù)中找出與正常的數(shù)據(jù)變化模式或者數(shù)據(jù)分布不同的數(shù)據(jù)點。該問題可以形式化表述為：給定一串具有時間序列特性的數(shù)據(jù)D={x1,x2,…,xn},xi∈D為一個d維數(shù)據(jù)，異常值檢測就是從中找出不符合數(shù)據(jù)變化規(guī)律和變化模式的異常點Do={o1,o2,…,ok}，其中k?n,Do?D。

判斷一個點是否為異常點，一種常用的方法是將其轉(zhuǎn)化為判斷該點出現(xiàn)的概率是否足夠大。如果出現(xiàn)概率大于一個閾值，那么該點可以認(rèn)為是正常點，否則為異常點。如果該點出現(xiàn)的概率很難得到，可以通過判斷它和正常數(shù)據(jù)是否服從同一分布來進(jìn)行判斷，如果該點和正常點來自同一分布就可以認(rèn)為該點為正常點，否則為異常點。

定義1如果數(shù)據(jù)點xt出現(xiàn)的概率P(xt|x1,x2,…,xt-1)<δ，那么xt為異常點，否則為正常點。

定義2設(shè)fi(·)為{x1,x2,…,xt-1}服從的概率密度函數(shù)，如果數(shù)據(jù)點xt滿足P(xt|fi(·))<δ，那么xt為異常點，否則即為正常點。

2 基于聚類和核密度估計假設(shè)檢驗的異常值檢測方法

2.1 基于BIRCH的聚類劃分方法

對變化模式復(fù)雜、變化范圍很小、有時間序列特性的流數(shù)據(jù)進(jìn)行聚類劃分，可以根據(jù)相關(guān)參數(shù)將其相似的數(shù)據(jù)歸為一類。根據(jù)數(shù)據(jù)特性，本文采用BIRCH算法和層次聚類算法實現(xiàn)數(shù)據(jù)劃分。

BIRCH算法主要通過聚類特征(Clustering feature，CF)和聚類特征樹(CF tree)來實現(xiàn)算法。CF代表一個聚類，每個CF向量都是一個三元組。對于一個記錄數(shù)為N的d維聚類樣本集X={X1,X2,…，XN}，CF表示為CF=(N,LS,SS)，其中LS為該聚類中所有樣本的線性和，反映了聚類的質(zhì)心；SS為該聚類中所有樣本的平方和，反映了聚類的直徑大小。聚類特征樹由若干個CF向量構(gòu)成，其結(jié)構(gòu)類似于B-樹?；贐IRCH的聚類劃分算法如下，其中對于劃分?jǐn)?shù)量K，在具體應(yīng)用中可通過設(shè)置不同值對數(shù)據(jù)進(jìn)行測試，選擇使算法性能最佳的值。

算法1基于BIRCH的聚類劃分算法

輸入：歷史數(shù)據(jù)D，劃分?jǐn)?shù)量K

輸出：{Di|0

(1)根據(jù)輸入樣本構(gòu)建BIRCH算法中的CF tree；

(2)對所有CF tree的葉子節(jié)點使用層次聚類算法進(jìn)行全局聚類；

(3)輸出全局聚類結(jié)果作為劃分結(jié)果。

2.2 核密度估計假設(shè)檢驗的異常值檢測方法

在聚類劃分完成后，使用核密度估計假設(shè)檢驗檢測異常值，其主要思想是：對于每個子聚類中的數(shù)據(jù)使用核密度估計方法來得到數(shù)據(jù)的概率密度函數(shù)fj，其算法如下。但在數(shù)據(jù)量少的時候核密度估計方法無法很準(zhǔn)確地反映出真實的數(shù)據(jù)分布，因此采用假設(shè)檢驗的方法來進(jìn)行判斷以得到更好的結(jié)果。

算法2核密度估計假設(shè)檢驗異常值檢測算法

輸入：待判斷樣本x,劃分結(jié)果{Di|0

輸出：0為正常點，1為異常點

(1)得到x所屬劃分Dj

(2)if|Dj|>200:使用KDE核密度估計方法得到Dj的概率密度函數(shù)fj以及Fj，從而計算出x出現(xiàn)的概率P(x)，如果P(x)<δ

return (1);

(3)else ifDj滿足Shapiro-Wilk檢驗：

根據(jù)Dj內(nèi)數(shù)據(jù)，計算得到μj和σj

else return (1);

(4)else

ifx通過Mann-Whitney檢驗 return 0;

else return (1)。

2.2.1 概率密度估計

KDE[21]是一種非參數(shù)估計方法，被用于估計未知密度函數(shù)。與參數(shù)估計方法不同的是，它無需假設(shè)數(shù)據(jù)服從某種分布，即可以在不利用任何先驗條件的情況下，根據(jù)數(shù)據(jù)樣本對未知密度函數(shù)進(jìn)行估計，達(dá)到所估結(jié)果與真實結(jié)果間具有最小均方積分誤差的目標(biāo)。

假設(shè)x1,x2,…，xn為獨立同分布F的n個樣本點，設(shè)其概率密度為f，則其核密度函數(shù)估計為

(1)

式中h(h>0)為一平滑參數(shù)，可由Silverman拇指法則得到

(2)

(3)

2.2.2 正態(tài)性檢驗-Shapiro-Wilk檢驗

雖然無參數(shù)的概率密度函數(shù)估計方法能夠在對數(shù)據(jù)無任何先驗知識的情況下得到較好的估計結(jié)果，但是這種方法是建立在大樣本性質(zhì)的前提上的。如果樣本數(shù)量較少，得到的概率密度函數(shù)估計誤差就會變大，因此它不適用于小樣本即樣本數(shù)小于200的情況。為了處理這種小樣本情況，本方法采用Shapiro-Wilk檢驗[23]來確定樣本是否服從正態(tài)分布。在滿足正態(tài)性(通過W檢驗)的前提下，可以非常簡單地得到數(shù)據(jù)出現(xiàn)的概率，從而判斷其是否為異常值。

Shapiro-Wilk(夏皮洛-威爾克)檢驗也被稱為W檢驗，建立在次序統(tǒng)計的基礎(chǔ)上，其原假設(shè)H0為：總體服從正態(tài)分布。檢驗步驟為：

(1) 將N個獨立觀察值按從小到大的次序排列，記為：x1,x2,…，xn。

(2) 依次將x1,x2,…，xn的值代入式(4)計算W檢驗統(tǒng)計量

(4)

(3) 根據(jù)預(yù)先設(shè)定的顯著水平α和樣本容量N，查W檢驗統(tǒng)計量的P分位數(shù)ZP表從而得到統(tǒng)計量W的α分位數(shù)Wα。

(4) 作出判斷：如果W

2.2.3 同分布檢驗-Mann-Whitney檢驗

對于不服從正態(tài)分布的樣本，可以采用Mann-Whitney檢驗(U檢驗)[24]來判斷兩組樣本數(shù)據(jù)是否來自于同一分布。

Mann-Whitney檢驗又稱秩和檢驗，是一種用于比較兩獨立樣本差異性的非參數(shù)檢驗方法。在檢驗時，首先將兩組樣本中的所有數(shù)據(jù)(假定兩個樣本總共有N個值)按從小到大的次序排列；再根據(jù)數(shù)值大小賦予每個值相應(yīng)的的秩，其中最小值的秩為1，最大值的秩為N，而相同值的秩為各秩的平均值。若兩樣本之間的秩和差距較大，則計算U檢驗統(tǒng)計量后將拒絕原假設(shè)，認(rèn)為二者之間存在明顯差異，不可能來自于同一分布。其檢驗步驟為：

(1) 混合兩樣本中的所有數(shù)據(jù)，根據(jù)數(shù)據(jù)次序賦予每個值相應(yīng)的秩，其中最小值的秩為1，最大值的秩為混合后數(shù)據(jù)總數(shù)。若存在多個值相等的數(shù)據(jù)，則取各值秩的平均值作為該值的秩。

(2) 由(1)分別計算兩樣本所有數(shù)據(jù)的秩和W1和W2。

(3) 由(2)分別計算兩樣本所有數(shù)據(jù)的U檢驗統(tǒng)計量U1和U2，其中n1為樣本1的數(shù)據(jù)總數(shù)，n2為樣本2的數(shù)據(jù)總數(shù)

(4) 取U=min(U1,U2)作為最終統(tǒng)計量。

(5) 根據(jù)兩樣本數(shù)據(jù)總數(shù)n1,n2和置信水平α，查U檢驗表，獲得U的臨界值Uα。

(6) 對U和Uα的大小進(jìn)行比較：若U

3 實驗結(jié)果

實驗使用了UCI中的Activity recognition from a single chest-mounted accelerometer(ARFSCMA)數(shù)據(jù)集和一臺燃煤機(jī)組超低排放數(shù)據(jù)兩種數(shù)據(jù)。這兩種數(shù)據(jù)集均具有時間序列特性，而且在某一段時間內(nèi)數(shù)據(jù)變化范圍不大，燃煤機(jī)組的超低排放數(shù)據(jù)相比于ARFSCMA數(shù)據(jù)的變化模式更為復(fù)雜。分別采用基于聚類核密度估計假設(shè)檢驗的方法、基于高斯擬合的方法[10]、基于AR時間序列的異常值檢測方法[14]和基于流數(shù)據(jù)聚類的異常值檢測方法[16]對測試數(shù)據(jù)進(jìn)行異常值檢測。

3.1 UCI數(shù)據(jù)集結(jié)果

ARFSCMA數(shù)據(jù)集使用Single chest-mounted accelerometer記錄了15位實驗者在不同時間段內(nèi)做7種不同動作時的值。分別選取其中的第1位和第2位實驗者做第1個動作時的數(shù)據(jù)進(jìn)行實驗，因此該數(shù)據(jù)變化模式相對單一。使用4萬條數(shù)據(jù)作為訓(xùn)練集，對300條數(shù)據(jù)進(jìn)行異常值檢測。在每一位實驗者待檢測的300條數(shù)據(jù)中，有200個異常值，其中包含漸變異常點和不同跳變程度的跳變異常點。把第1位實驗者的待檢測數(shù)據(jù)稱為測試集1，第2位實驗者的待檢測數(shù)據(jù)稱為數(shù)據(jù)集2。表1給出了4種不同的異常值檢測方法在測試集1和測試集2上的測試結(jié)果。

表1 4種異常值檢測方法在ARFSCMA數(shù)據(jù)集上的檢測結(jié)果

Tab.1 Detection results on ARFSCMA data set by using four outlier detection methods

數(shù)據(jù)集聚類核密度估計假設(shè)檢驗高斯分布擬合流數(shù)據(jù)聚類AR時間序列預(yù)測測試集1191178154121測試集213487117133

3.2 真實工業(yè)數(shù)據(jù)

使用一臺裝機(jī)容量為300MW的燃煤機(jī)組(以下稱為測試機(jī)組)2016年5月除測試集之外的脫硫超低排放設(shè)施運(yùn)行數(shù)據(jù)(1 min/條)為樣本建立模型，其變化模式相對ARFSCMA數(shù)據(jù)更加復(fù)雜。以2016/5/31 15:40-2016/5/31 23:59共500條數(shù)據(jù)為測試樣本，使用二氧化硫排放濃度為目標(biāo)測點，檢測二氧化硫時序數(shù)據(jù)中的異常值。測試樣本中一共有250個異常值，其中包括漸變異常點和不同跳變程度的跳變異常點。

在檢測過程中，對于BIRCH算法中劃分?jǐn)?shù)量這一參數(shù)，通過對樣本數(shù)據(jù)測試不同值發(fā)現(xiàn)，當(dāng)其為10時算法的性能最好，因此將劃分?jǐn)?shù)量設(shè)為10。在使用基于核密度假設(shè)檢驗的異值檢測算法時δ=0.05，通過Shaprio-Wilk和Mann-Whitney檢驗的置信度為95%。把真實工業(yè)數(shù)據(jù)的測試樣本稱為測試集3，表2給出了4種異常值檢測方法在真實工業(yè)數(shù)據(jù)上的檢測結(jié)果。

表2 4種異常值檢測方法在真實工業(yè)數(shù)據(jù)上的檢測結(jié)果

Tab.2 Detection results on real industrial data by using four outlier detection methods

數(shù)據(jù)集聚類核密度估計假設(shè)檢驗高斯分布擬合流數(shù)據(jù)聚類AR時間序列預(yù)測測試集3226154142126

3.3 實驗結(jié)果分析

圖1為4種異常值檢測方法在3種不同數(shù)據(jù)集上的檢測性能比較結(jié)果，其中testdata_one到testdata_three分別代表測試集1到3。Clustering & testing代表本文的方法，Gaussian fitting為高斯分布擬合方法，Online clustering為流數(shù)據(jù)聚類方法，AR predict為基于AR預(yù)測的時間序列異常值檢測方法。從圖1可以看出，相比于其他3種方法，基于聚類和核密度估計假設(shè)檢驗的方法在標(biāo)準(zhǔn)數(shù)據(jù)集和真實的工業(yè)數(shù)據(jù)集上都取得了比較好的效果，而且都能夠檢測出大部分的異常點。特別是在甄別機(jī)組超低排放數(shù)據(jù)這種變化模式比較復(fù)雜的實際應(yīng)用環(huán)境中，本文提出的方法相比于其他3種方法，優(yōu)勢更加明顯，能夠檢測出90%的異常。

圖1 4種異常值檢測方法在3種不同數(shù)據(jù)上的性能比較Fig. 1 Performance comparison of four outlier detection methods on three datasets

4 結(jié)束語

異常值檢測在工業(yè)生產(chǎn)中有著廣泛的應(yīng)用，但異常值檢測算法往往需要針對不同的數(shù)據(jù)特點和應(yīng)用場景進(jìn)行設(shè)計。本文針對變化模式復(fù)雜、變化范圍很小和有時間序列特性的流數(shù)據(jù)，提出了一種基于聚類和KDE假設(shè)檢驗異常值檢測方法。該方法充分利用大量的數(shù)據(jù)信息，合理選取聚類參數(shù)對數(shù)據(jù)進(jìn)行聚類，從而對原始復(fù)雜的數(shù)據(jù)分布進(jìn)行簡化，能夠更好地擬合得到數(shù)據(jù)的概率密度函數(shù)。同時，針對KDE算法在樣本數(shù)量較少時會出現(xiàn)精度不高的情況，設(shè)計了一種基于假設(shè)檢驗的算法來進(jìn)行處理，相比較單純使用KDE，算法適用性得到了提升。該算法為變化模式復(fù)雜的燃煤機(jī)組超低排放數(shù)據(jù)異常值檢測提供了一個普適的處理框架，相比于傳統(tǒng)異常值檢測算法，其準(zhǔn)確率更高。下一步希望能夠在分布式環(huán)境下處理該問題，使得算法性能和處理效率能夠得到進(jìn)一步的提升。

[1] Aggarwal C C. Outlier analysis[C]∥Data Mining. Switzerland: Springer International Publishing, 2015: 237-263.

[2] Chandola V, Banerjee A, Kumar V. Anomaly detection: A survey[J]. ACM Computing Surveys (CSUR), 2009, 41(3): 15.

[3] Hodge V, Austin J. A survey of outlier detection methodologies[J]. Artificial Intelligence Review, 2004, 22(2): 85-126.

[4] Phua C, Lee V, Smith K, et al. A comprehensive survey of data mining-based fraud detection research[C]∥Artificial Intelligence Review. [S.l.]: Springer, 2005.

[5] Kim G, Lee S, Kim S. A novel hybrid intrusion detection method integrating anomaly detection with misuse detection[J]. Expert Systems with Applications, 2014, 41(4): 1690-1700.

[6] Schiff G D, Volk L A, Volodarskaya M, et al. Screening for medication errors using an outlier detection system[J]. Journal of the American Medical Informatics Association, 2017, 24(2):1-7.

[7] Gupta M, Gao J, Aggarwal C C, et al. Outlier detection for temporal data: A survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(9): 2250-2267.

[8] Hawkins D M. Identification of outliers[M]. London: Chapman and Hall, 1980.

[9] Johnson R A, Wichern D W. Applied multivariate statistical analysis[M]. Upper Saddle River, NJ: Prentice Hall, 2002.

[10] Barnett V, Lewis T. Outliers in statistical data[M]. Chichester, UK: John Wiley & Sons, 1994.

[11] Knorr E M, Ng R T. A unified approach for mining outliers[C]∥Proceedings of the 1997 Conference of the Centre for Advanced Studies on Collaborative Research. Toronto, Ontario, Canada: IBM Press, 1997: 11.

[12] Bentley J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM, 1975, 18(9): 509-517.

[13] Breunig M M, Kriegel H P, Ng R T, et al. LOF: Identifying density-based local outliers[C]∥ACM Sigmod Record. New York, NY, USA: ACM, 2000, 29(2): 93-104.

[14] 蘇衛(wèi)星, 朱云龍, 胡琨元, 等. 基于模型的過程工業(yè)時間序列異常值檢測方法[J]. 儀器儀表學(xué)報, 2012,33(9): 2080-2087.

Su Weixing, Zhu Yunlong, Hu Kunyuan, et al.Model-based outlier detection method for time series of process industry[J]. Chinese Journal of Scientific Instrument,2012,33(9):2080-2087.

[15] 賀力克, 聶平由. 時序數(shù)據(jù)故障點檢測方法分析比較及應(yīng)用[J]. 湖南師范大學(xué)自然科學(xué)學(xué)報, 2012, 35(2): 35-40.

He Like, Nie Pingyou. Comparison and application of fault point detection method used in time series data analysis[J]. Journal of Natural Science of Hunan Normal University, 2012, 35(2): 35-40.

[16] Moradi K H, Ibrahim S, Hosseinkhani J. Outlier detection in stream data by clustering method[J]. Social Science Electronic Publishing, 2014,2:25-34.

[17] Ngan H Y T, Yung N H C, Yeh A G O. A comparative study of outlier detection for large-scale traffic data by one-class SVM and kernel density estimation[C]∥SPIE/IS & T Electronic Imaging. San Francisco, California, USA: International Society for Optics and Photonics, 2015: 94050I-1-94050I-10.

[18] Pawlowski N, Jaques M, Glocker B. Efficient variational Bayesian neural network ensembles for outlier detection[C]∥The 5th International Conference on Learning Representations. Toulon, France: [s.n.], 2017.

[19] Pincombe B. Anomaly detection in time series of graphs using ARMA processes[J]. Asor Bulletin, 2005, 24(4): 2.

[20] Paulheim H. Identifying wrong links between datasets by multi-dimensional outlier detection[C]∥Proceedings of the Third International Workshop on Debugging Ontologies and Ontology Mappings. Greece: [s.n.]，2014: 27-38.

[21] Silverman B W. Density estimation for statistics and data analysis[M]. [S.l.]: CRC Rress, 1986.

[22] Zhang T, Ramakrishnan R, Livny M. BIRCH: An efficient data clustering method for very large databases[C]∥ACM Sigmod Record. New York, NY, USA: ACM, 1996, 25(2): 103-114.

[23] Shapiro S S, Wilk M B. An analysis of variance test for normality (complete samples)[J]. Biometrika, 1965, 52(3/4): 591-611.

[24] Mann H B, Whitney D R. On a test of whether one of two random variables is stochastically larger than the other[J]. The Annals of Mathematical Statistics, 1947,18(1): 50-60.

OutlierDetectionBasedonClusteringandKDEHypothesisTesting

Zhou Chunlei1,2, Tian Pinzhuo1, Yang Chenchen1,2, Wang Hao1

(1.State Key Laboratory for Novel Software Technology, Nanjing University,Nanjing, 210023, China; 2.Jiangsu Frontier Electric Technology CO.LTD, Nanjing, 211102, China)

Outlier detection is the core problem in data mining and is widely used in industrial production. Accurate and efficient outlier detection method can reflect the condition of industrial system in time, which provides reference for the relevant personnel. Traditional outlier detection algorithms can′t efficiently detect outliers in those data with complicated change modes, small change range and the characteristics of streaming data. In this paper a new method for detecting outliers is proposed. Firstly, the data are clustered into several categories by clustering. The data in the same categories share the common characteristics. In this way, we believe that the data in the same categories are under the same distribution which are simpler to fit than the whole data. So the original complex data distribution can be factored into several simple distributions. Secondly, kernel density estimation (KDE) hypothesis testing is used for abnormal value detection. Experiments in the UCI dataset and real industrial data show that the proposed method is more efficient than traditional methods.

outlier detection; clustering; hypothesis testing; kernel density estimation

國家自然科學(xué)基金(61503178)資助項目；江蘇省自然科學(xué)基金(BK20150587)資助項目。

2017-05-18；

2017-07-09

TP391

A

周春蕾(1973-)，女，工程師，研究方向：電力行業(yè)節(jié)能減排信息化，E-mail:13851845492@163.com。

王皓(1983-)，通信作者，男，博士，研究方向：數(shù)據(jù)管理、機(jī)器學(xué)習(xí)，E-mail: wanghao@nju.edu.cn。

田品卓(1991-)，男，碩士，研究方向：機(jī)器學(xué)習(xí)，E-mail:tianpinzhuo@qq.com。

楊晨琛(1990-)，女，助理工程師，研究方向：電力行業(yè)節(jié)能減排技術(shù)，E-mail:15951854315@163.com。