基于鄰域密度的異常檢測方法

趙華，秦克云

西南交通大學數(shù)學學院，成都 610031

基于鄰域密度的異常檢測方法

趙華，秦克云

西南交通大學數(shù)學學院，成都 610031

提出了一個基于鄰域密度的異常檢測方法，它能處理混合數(shù)據(jù)的異常值。在該方法中，樣本的異常指標被定義為該樣本的鄰域大小和該樣本的平均鄰域密度的加權(quán)和。為了驗證提出的方法，進行了一系列實驗。實驗結(jié)果表明新提出的方法適用于混合數(shù)據(jù)，并且比其他檢測方法更有效。

異常檢測；鄰域密度；混合數(shù)據(jù)

1 引言

異常檢測是數(shù)據(jù)挖掘領(lǐng)域的一個重要的研究熱點。異常檢測的主要目的是發(fā)現(xiàn)數(shù)據(jù)集中明顯區(qū)別于其他大部分數(shù)據(jù)的小部分異常數(shù)據(jù)（也稱為異常值）。異常檢測已經(jīng)成功地應(yīng)用于醫(yī)療告警[1]、環(huán)境監(jiān)測[2]、欺詐檢測[3]、入侵檢測[4]，也涉及到軟件評價[5]、地理[6]、交通[7]、金融[8]等領(lǐng)域。異常值有兩個主要特點，一是異常值的數(shù)量是很小的，二是異常值明顯區(qū)別于其他的數(shù)據(jù)。

隨著異常檢測技術(shù)的不斷發(fā)展，人們提出了大量的異常檢測方法。異常檢測方法通常分為四種：基于密度的方法[9-11]、基于距離的方法[12]、基于深度的方法和基于聚類[13-14]的方法。Yang[15]提出了一個基于核模糊c-means聚類的模糊SVM算法解決異常檢測問題。Chen[16]將鄰域粗糙集和異常檢測相結(jié)合，提出了一個基于距離的異常檢測方法。Guo[17]提出了一個基于支持向量域描述（SVDD）的后處理方法，這個方法可以有效地解決異常檢測問題。從局部分布的角度出發(fā)，Zhang[18]引入了局部密度、局部對稱度等概念并提出了兩個異常檢測算法LDBOD和LDBOD+。Cassisi[13]提出了基于密度的聚類算法去處理異常檢測。這個算法應(yīng)用空間分層的思想有效地確定數(shù)據(jù)集中不同密度的聚類簇，并且引入了相反最近鄰域的概念。該方法可以檢測不同密度數(shù)據(jù)集的異常值。

本文提出了一種基于鄰域密度的異常檢測方法（NDOIA）。在這個方法中，樣本的鄰域異常指標是該樣本的鄰域大小和該樣本的平均鄰域密度的加權(quán)和。樣本的鄰域大小是指某樣本的鄰域中包含的其他樣本的個數(shù)，而樣本的平均鄰域密度則反映了該樣本的鄰域中其他樣本的密度大小。一個樣本的基于鄰域密度的異常指標能更有效地度量這個樣本與其他樣本的相異程度。此外，通過引用鄰域的概念，新的算法能夠處理混合數(shù)據(jù)集。在這里，混合數(shù)據(jù)是指混合了數(shù)值型屬性和名詞型屬性的數(shù)據(jù)。為了驗證本文提出算法的有效性，進行了一系列的實驗，實驗結(jié)果表明NDOIA能有效地處理混合數(shù)據(jù)的異常檢測問題。

2 基于鄰域密度的異常檢測方法

通常情況下，一個數(shù)據(jù)集可以表示成一個信息系統(tǒng)IS=U，A，其中U為對象的非空有限集合，稱為論域，A是屬性集。對于任意x∈U，定義其鄰域為[19]：

其中Δ是距離函數(shù)，對于?x1，x2，x3∈U，Δ滿足下面的條件：

設(shè)B1?A，B2?A，其中B1是數(shù)值型屬性集，B2是名詞型屬性集，樣本x關(guān)于屬性集B1，B2和B1∪B2的鄰域分別定義為：

基于密度的異常檢測方法受到了學術(shù)界廣泛關(guān)注。經(jīng)典的方法是使用k-nearest-neighbor技術(shù)，求所有樣本與它們k-nearest-neighbor樣本的平均距離，那些平均距離大的樣本被認為在屬性空間中更偏離大部分樣本（或者說與大部分樣本有極大差異），因此被認為是異常值。本章提出一種基于鄰域密度的異常檢測方法。在該方法中，一個樣本的異常程度由兩個因素決定，一是這個樣本的鄰域大小，即鄰域中樣本的個數(shù)；二是這個樣本的平均鄰域密度。因為一個樣本的鄰域大小不足以說明這個樣本在整個屬性空間中與周圍樣本之間的差異，所以引入了下面的定義。

定義1給定一個信息系統(tǒng)IS=U，A，對于任意的xi∈U，x的鄰域距離定義為：

定義2給定一個信息系統(tǒng)IS=U，A，對于任意的xi∈U，x的平均鄰域密度定義為：

一個樣本的平均鄰域密度越大，在屬性空間中這個樣本越有可能位于分布密度大的區(qū)域，成為異常值的可能性越小。

定義3給定一個信息系統(tǒng)IS=U，A，對于任意x∈U，基于鄰域密度的x的異常度指標定義如下：

基于鄰域密度異常度指標，提出下面的算法。

算法1基于鄰域密度的異常檢測方法（NDOIA）

輸入數(shù)據(jù)集D

輸出異常值集合O

3 實驗

為了驗證NDOIA，進行下面的實驗。從UCI機器學習數(shù)據(jù)庫中選擇了9個數(shù)據(jù)集。這些數(shù)據(jù)集的具體信息如表1所示，其中有4個混合屬性的數(shù)據(jù)集，3個名詞型屬性的數(shù)據(jù)集和2個數(shù)值型屬性的數(shù)據(jù)集。接下來，設(shè)計兩個實驗，一個針對分布不均勻的數(shù)據(jù)集，一個針對分布均勻的數(shù)據(jù)集。在這兩個實驗中，對于NDOIA，所有數(shù)據(jù)集的數(shù)值屬性都歸一化到[0，1]之間，數(shù)值屬性的鄰域閾值被設(shè)定為0.2，名詞型屬性的鄰域閾值為0。此外，在NDOIA中，w1為0.4，w2為0.6。

3.1 實驗1

Aggarw al[20]提出了一種驗證異常檢測算法的方法。接下來，通過Aggarwal的驗證方法，將本文提出的算法與CBLOF算法[14]和SEQ算法[21]進行對比分析。Aggarwal驗證方法簡單描述如下：用一個異常檢測算法在一個給定的數(shù)據(jù)集上進行異常值檢測，然后計算檢測到的異常值屬于少數(shù)類數(shù)據(jù)的百分比。在這里，少數(shù)類數(shù)據(jù)是指在數(shù)據(jù)集中數(shù)量少于5%的數(shù)據(jù)類別，而屬于少數(shù)類的樣本被認為是異常值。例如，數(shù)據(jù)集Car1包括1 728個樣本，這些樣本被分為4類“unacc”（70.023%），“acc”（22.222%），“good”（3.993%），“v-good”（3.762%）。很明顯，第3類和第4類（“good”和“v-good”）被認為是少數(shù)類樣本。類似地，另外幾個數(shù)據(jù)集的類分布如表2所示，其中少數(shù)類樣本用粗體標注。

表3到表8是3種不同的異常檢測算法在6個數(shù)據(jù)集上的計算結(jié)果，其中CBLOF表示基于聚類的異常檢測算法，SEQ表示基于粗糙集的異常檢測算法。另外，“最高比率”表示那些異常度較高的數(shù)據(jù)個數(shù)與其他數(shù)據(jù)個數(shù)的比率；“包含在少數(shù)類中的異常值個數(shù)”是檢測到的異常值屬于少數(shù)類樣本的個數(shù)，“覆蓋率”是“包含在少數(shù)類中的異常值個數(shù)”與少數(shù)類總樣本數(shù)的百分比。

表1 UCI數(shù)據(jù)集

表2 6個數(shù)據(jù)集的數(shù)據(jù)分布

表3 3個算法在Abalone1上的對比結(jié)果

表4 3個算法在Abalone2上的對比結(jié)果

表5 3個算法在Yeast1上的對比結(jié)果

表6 3個算法在Yeast2上的對比結(jié)果

表7 3個算法在Car1上的對比結(jié)果

表8 3個算法在Car2上的對比結(jié)果

從表3到表8中，可以觀察到3個算法都有一個共同的特點，即“覆蓋率”的增加程度隨著“最高比率”的增加而減小。在表3中，很容易發(fā)現(xiàn)，NDOIA和CBLOF的“覆蓋率”明顯高于SEQ。在表4中，為了檢測到所有的32個異常值，NDOIA需要選擇43個樣本，CBLOF需要選擇72個樣本，而SEQ則需要選擇86個樣本。通過觀察很容易發(fā)現(xiàn)，在表3到表8中，NDOIA算法的比其他兩個算法更能有效地檢測出異常值。

3.2 實驗2

為了進一步驗證提出的算法，將NDOIA與其他3個能處理混合屬性數(shù)據(jù)的檢測算法進行比較。這3個算法分別是KNN檢測算法[22]、PODM算法[23]和NED算法[16]。這里用到的數(shù)據(jù)集是Heart，Method和Chess。這3個數(shù)據(jù)集的類分布分別為150∶120，629∶511∶333，和1 669∶1 527。容易發(fā)現(xiàn)這些都是分布比較均勻的數(shù)據(jù)集。因此，用一個類似于文獻[23]中提到的方法生成異常值。該方法的具體步驟為：對于一個數(shù)據(jù)集，隨機地從最小分布的那類數(shù)據(jù)中選擇一些樣本（小于總樣本量的5%）作為一個新的類別，而其他的數(shù)據(jù)成為一類。Heart，Method和Chess的新數(shù)據(jù)集分布見表9。Heart1和Heart2是對于Heart選擇了不同數(shù)量的樣本作為少數(shù)類，Method1和Method2，以及Chess1和Chess2有相似的表示。特別地，少數(shù)類分布由粗體標識。另外，這些數(shù)據(jù)集的數(shù)值型屬性值都被歸一化到[0，1]。名詞型屬性的閾值被設(shè)定為0，數(shù)值型屬性的閾值被設(shè)定為0.2。這里設(shè)定的鄰域的閾值同樣適用于NED算法。另外，對于KNN異常檢測算法，最鄰近的大小設(shè)定為5（即k=5）。

表9 6個數(shù)據(jù)集的類分布

圖1 Heart1的覆蓋率曲線

圖2 Heart2的覆蓋率曲線

圖3 Chess1的覆蓋率曲線

圖4 Chess2的覆蓋率曲線

圖5 Method1的覆蓋率曲線

圖6 Method2的覆蓋率曲線

為了更直觀地比較這4種算法，用上節(jié)中提到的Aggarwal方法中的“覆蓋率”和“樣本個數(shù)”的概念，畫出了6個數(shù)據(jù)集的“覆蓋率”隨著“樣本個數(shù)”的增加曲線圖，具體如圖1～6所示。在這里，把圖1～6中的曲線稱為覆蓋率曲線。一個算法的覆蓋率曲線下的面積越大，則表示這個算法的檢測精度越高。圖1和圖2是Heart1和Heart2的覆蓋率曲線圖。發(fā)現(xiàn)曲線隨著異常值的增加而增加。由表9，知道Heart1和Heart2的異常值分別為8和10個。從圖1和圖2看到當覆蓋率達到1的時候，NDOIA和NED所選擇的樣本個數(shù)分別為10和11，明顯低于KNN和PODM。在圖1～6中，NDOIA算法的覆蓋率曲線下的面積都大于其他算法?？偟膩碚f，NODIA適用于混合數(shù)據(jù)并能有效地檢測出異常值。

4 結(jié)束語

本文提出了一個基于鄰域密度的異常檢測方法。這個方法能處理混合屬性數(shù)據(jù)的異常值。在這個方法中，樣本的鄰域異常指標是該樣本的鄰域大小和該樣本的平均鄰域密度的加權(quán)和。樣本的鄰域大小是指某樣本的鄰域中包含的其他樣本的個數(shù)。樣本的平均鄰域密度反映了該樣本的鄰域中其他樣本的密度大小。為了驗證新提出算法有效性，把它和其他代表性的算法進行了比較。實驗結(jié)果表明，提出的方法適用于混合數(shù)據(jù)，并具有更高的效率。

[1]Hauskrecht M，Batal I，Valko M，et al.Outlier detection for patient monitoring and alerting[J].Journal of Biomedical Information，2013，46（1）：47-55.

[2]Garces H，Sbarbaro D.Outliers detection in environmental monitoring databases[J].Engineering Applications of Artificial Intelligence，2011，24（2）：341-349.

[3]Richard J B，David J H.Statistical fraud detection：a review（with discussion）[J].Statistical Science，2002，17（3）：235-255.

[4]Leckie T，Yasinsac A，Member S.Metadata for anomalybased security protocol attack deduction[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（9）：1157-1168.

[5]Alan O，Catal C.Thresholds based outlier detection approach for mining class outliers：an empirical case study on software measurement datasets[J].Expert Systems with Applications，2011，38（4）：3440-3445.

[6]Maervoet J，Vens C，Berghe G V，et al.Outlier detection in relational data：a case study in geographical information systems[J].Expert Systems with Applications，2012，39（5）：4718-4728.

[7]Chen S Y，Wang W，Zuylen H D.A comparison of outlier detection algorithms for ITS data[J].Expert Systems with Applications，2010，37（2）：1169-1178.

[8]Aurea G，Veiga H.Wavelet-based detection of outliers in financial time series[J].Computational Statistics and Data Analysis，2010，54（11）：2580-2593.

[9]Breunig M M，Kriegel H P，Raymond T N，et al.LOF：identifying density-based local outliers[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data，Dallas，USA，2000：93-104.

[10]Kim S，Cho N W，Kang B，et al.Fast outlier detection for very large log data[J].Expert Systems with Applications，2011，38（8）：9587-9596.

[11]Pokrajac D，Lazarevic A，Latecki L J.Incremental local outlier detection for data streams[C]//IEEE Symposium on Computational Intelligence and Data Mining（CIDM），Honolulu，Hawaii，2007：504-515.

[12]Knorr E M，Raymond T N，Tucakov V.Distance-based outliers：algorithms and applications[J].VLDB Journal：Very Large Databases，2000，8：237-253.

[13]Cassisi C，F(xiàn)erro A，Giugno R，et al.Enhancing densitybased clustering：parameter reduction and outlier detection[J].Information Systems，2013，38（3）：317-330.

[14]He Z Y，Xu X F，Deng S C.Discovering cluster-based local outliers[J].Pattern Recognition Letters，2003，24（9/10）：1641-1650.

[15]Yang X W，Zhang G Q，Lu J，et al.A kernel fuzzy c-means clustering-based fuzzy support vector machine algorithm for classification problems with outliers or noises[J].IEEE Transactions on Fuzzy Systems，2011，19（1）：105-115.

[16]Chen Y M，Miao D Q，Zhang H Y.Neighborhood outlier detection[J].Expert Systems with Applications，2010，37（12）：8745-8749.

[17]Guo S M，Chena L C，Tsaib J S H.A boundary method for outlier detection based on support vector domain description[J].Pattern Recognition，2009，42（1）：77-83.

[18]Zhang Y，Yang S，Wang Y Y.LDBOD：a novel local distribution based outlier detector[J].Pattern Recognition Letters，2008，29（7）：967-976.

[19]Hu Q H，Yu D R，Liu J F，et al.Neighborhood rough set based heterogeneous feature subset selection[J].Information Sciences，2008，178（18）：3577-3594.

[20]Aggarwal C C，Yu P S.Outlier detection for high dimensional data[C]//Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data，California， 2001：37-46.

[21]Jiang F，Sui Y F，Cao C G.Some issues about outlier detection in rough set theory[J].Expert Systems with Applications，2009，36（1）：4680-4687.

[22]Ramaswamy S，Rastogi R，Shim K.Efficient algorithms for mining outliers from large data sets[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data，Dollas，2000：427-438.

[23]Ye M，Li X，Orlowska M E.Projected outlier detection in high-dimensional mixed-attributes data set[J].Expert Systems with Applications，2009，36（3）：7104-7113.

ZHAO Hua,QIN Keyun

School of Mathematics,Southwest Jiaotong University,Chengdu 610031,China

This paper proposes a neighborhood density based outlier detection method, which is applicable to the data with mixed numerical and categorical features. In this method, the outlierness indicator of a sample is defined as the weighted sum of neighborhood cardinality and average neighborhood density of this sample. To validate the effectiveness of this algorithm, it performs a series of experiments. Experimental results show that the proposal is applicable and effective to mixed data.

outlier detection; neighborhood density; mixed data

ZHAO Hua, QIN Keyun. Outlier detection method based on neighborhood density. Computer Engineering and Applications, 2014, 50（17）：24-28.

A

TP393

10.3778/j.issn.1002-8331.1401-0320

國家自然科學基金（No.61175044，No.61175055）；中央高校基礎(chǔ)研究基金（No.SW JTU11ZT29）。

趙華（1980—），女，博士生，主要研究方向為智能信息處理、數(shù)據(jù)挖掘；秦克云（1962—），男，教授，主要研究方向為智能信息處理、模糊集、粗糙集。E-mail：zzh8008@gmail.com

2014-01-20

2014-03-07

1002-8331（2014）17-0024-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-03-19,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1401-0320.htm l