趙華，秦克云

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

基于鄰域密度的異常檢測(cè)方法

趙華，秦克云

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

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

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

1 引言

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

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

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

2 基于鄰域密度的異常檢測(cè)方法

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

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

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

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

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

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

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

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

基于鄰域密度異常度指標(biāo)，提出下面的算法。

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

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

輸出異常值集合O

3 實(shí)驗(yàn)

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

3.1 實(shí)驗(yàn)1

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

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

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

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

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)2

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

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

圖1 Heart1的覆蓋率曲線

圖2 Heart2的覆蓋率曲線

圖3 Chess1的覆蓋率曲線

圖4 Chess2的覆蓋率曲線

圖5 Method1的覆蓋率曲線

圖6 Method2的覆蓋率曲線

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

4 結(jié)束語(yǔ)

本文提出了一個(gè)基于鄰域密度的異常檢測(cè)方法。這個(gè)方法能處理混合屬性數(shù)據(jù)的異常值。在這個(gè)方法中，樣本的鄰域異常指標(biāo)是該樣本的鄰域大小和該樣本的平均鄰域密度的加權(quán)和。樣本的鄰域大小是指某樣本的鄰域中包含的其他樣本的個(gè)數(shù)。樣本的平均鄰域密度反映了該樣本的鄰域中其他樣本的密度大小。為了驗(yàn)證新提出算法有效性，把它和其他代表性的算法進(jìn)行了比較。實(shí)驗(yàn)結(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

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

趙華（1980—），女，博士生，主要研究方向?yàn)橹悄苄畔⑻幚?、?shù)據(jù)挖掘；秦克云（1962—），男，教授，主要研究方向?yàn)橹悄苄畔⑻幚?、模糊集、粗糙集。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