沈琰輝，劉華文，徐曉丹，趙建民，陳中育

浙江師范大學(xué) 數(shù)理與信息工程學(xué)院，浙江 金華 321004

基于鄰域離散度的異常點(diǎn)檢測(cè)算法*

沈琰輝，劉華文+，徐曉丹，趙建民，陳中育

浙江師范大學(xué) 數(shù)理與信息工程學(xué)院，浙江 金華 321004

SHEN Yanhui,LIU Huawen,XU Xiaodan,et al.Outlier detection algorithm based on dispersion of neighbors.Journal of Frontiers of Computer Science and Technology,2016,10(12)：1763-1772.

異常點(diǎn)檢測(cè)在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域中有著十分重要的作用。當(dāng)前異常點(diǎn)檢測(cè)算法的一大缺陷是正常數(shù)據(jù)在邊緣處異常度較高，導(dǎo)致在某些情況下誤判異常點(diǎn)。為了解決該問(wèn)題，提出了一種新的基于鄰域離散度的異常點(diǎn)檢測(cè)算法。該算法將數(shù)據(jù)點(diǎn)所在鄰域的離散度作為該數(shù)據(jù)點(diǎn)的異常度，既能有效避免邊緣數(shù)據(jù)點(diǎn)的異常度過(guò)高，又能較好地區(qū)分正常點(diǎn)與異常點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該算法能夠有效地檢測(cè)數(shù)據(jù)中的異常點(diǎn)，并且算法對(duì)參數(shù)選擇不敏感，性能較為穩(wěn)定。

異常點(diǎn)檢測(cè)；機(jī)器學(xué)習(xí)；數(shù)據(jù)挖掘；主成分分析

1 引言

隨著數(shù)字化技術(shù)的發(fā)展，人們收集到的數(shù)據(jù)越來(lái)越多。然而由于儀器故障、信號(hào)干擾、反常行為等因素，數(shù)據(jù)中通常存在異常點(diǎn)。異常點(diǎn)和其余數(shù)據(jù)點(diǎn)之間存在顯著差異，一方面會(huì)干擾特征提取、模式識(shí)別等機(jī)器學(xué)習(xí)任務(wù)，另一方面又有助于發(fā)現(xiàn)信用卡欺詐、基因突變、網(wǎng)絡(luò)入侵等異?，F(xiàn)象[1-2]。因此，異常點(diǎn)檢測(cè)引起了研究學(xué)者的廣泛關(guān)注。

當(dāng)前，許多異常點(diǎn)檢測(cè)算法通過(guò)距離或密度來(lái)度量數(shù)據(jù)點(diǎn)之間的差異性，例如LOF（local outlier factor）算法[3]、LDOF（local distance-based outlier factor）算法[4]等。然而這些算法的主要問(wèn)題是邊緣數(shù)據(jù)點(diǎn)的異常度較高，由于某些情況下邊緣數(shù)據(jù)點(diǎn)并非異常點(diǎn)，這種效應(yīng)會(huì)影響異常點(diǎn)檢測(cè)效果。例如對(duì)于均勻分布的數(shù)據(jù)（如圖1），其中并沒(méi)有異常點(diǎn)，但是在上述幾個(gè)算法下，點(diǎn)A和B的異常度卻高于其他數(shù)據(jù)點(diǎn)。如果數(shù)據(jù)是高斯分布的，這種效應(yīng)還將進(jìn)一步放大。顯然這種效應(yīng)對(duì)異常點(diǎn)檢測(cè)是不利的，因?yàn)樗鼤?huì)模糊正常點(diǎn)和異常點(diǎn)之間的界限。并且在無(wú)監(jiān)督學(xué)習(xí)的場(chǎng)景下，由于異常點(diǎn)的個(gè)數(shù)未知，一個(gè)有效的異常點(diǎn)檢測(cè)算法不但要適用于含有異常點(diǎn)的數(shù)據(jù)集，對(duì)于不含有異常點(diǎn)的數(shù)據(jù)集也要給出合理的結(jié)果。

為了解決上述問(wèn)題，本文提出了基于鄰域離散度的異常點(diǎn)檢測(cè)算法。該算法將數(shù)據(jù)點(diǎn)所在鄰域的離散度作為其異常度，因此對(duì)于均勻分布的正常數(shù)據(jù)點(diǎn)，該算法給出的每個(gè)數(shù)據(jù)點(diǎn)的異常度都是相同的，不存在邊緣放大效應(yīng)。實(shí)驗(yàn)結(jié)果顯示，該算法能夠更有效地檢測(cè)數(shù)據(jù)集中的異常點(diǎn)。

本文組織結(jié)構(gòu)如下：第2章介紹了異常點(diǎn)檢測(cè)的相關(guān)工作；第3章介紹了主成分分析（principal component analysis，PCA）及其與奇異值分解（singular value decomposition，SVD）的關(guān)聯(lián)；第4章介紹了本文算法的具體原理、算法步驟、算法復(fù)雜度以及參數(shù)的選擇；第5章將本文算法和其他幾種算法做了對(duì)比實(shí)驗(yàn)，分析了算法效果；第6章對(duì)全文進(jìn)行了總結(jié)。

Fig.1 Uniformly distributeddata圖1 均勻分布的數(shù)據(jù)

2 相關(guān)工作

異常點(diǎn)檢測(cè)的主要目的是檢測(cè)數(shù)據(jù)集中的少數(shù)類(lèi)，目前已經(jīng)提出了許多異常點(diǎn)檢測(cè)算法。根據(jù)模型的不同，大致可以分為基于統(tǒng)計(jì)模型的異常點(diǎn)檢測(cè)、基于鄰近度的異常點(diǎn)檢測(cè)、基于子空間的異常點(diǎn)檢測(cè)和基于集成學(xué)習(xí)的異常點(diǎn)檢測(cè)。

基于統(tǒng)計(jì)模型的異常點(diǎn)檢測(cè)算法早在計(jì)算機(jī)發(fā)明以前就有不少統(tǒng)計(jì)學(xué)家進(jìn)行了研究。該模型假設(shè)數(shù)據(jù)在總體上服從某種分布，并將每個(gè)數(shù)據(jù)點(diǎn)與該分布的契合程度作為其異常度，因此這類(lèi)方法得出的通常是全局意義上的異常點(diǎn)。一種具有代表性的方法是基于深度的異常點(diǎn)檢測(cè)算法[5]，它假設(shè)數(shù)據(jù)在空間中是由內(nèi)到外一層一層包裹而成，通過(guò)計(jì)算出凸多邊形包圍盒，將數(shù)據(jù)層層剝離，越處在外層多邊形上的數(shù)據(jù)點(diǎn)異常度越高，但這種方法對(duì)超過(guò)三維的數(shù)據(jù)就不甚理想。近年來(lái)，Kriegel等人提出了ABOD（angle based outlier detection）算法[6]。該算法的基本設(shè)想是：若某個(gè)數(shù)據(jù)點(diǎn)位于數(shù)據(jù)分布越稀疏的區(qū)域，那么以該點(diǎn)為頂點(diǎn)，任取其余兩個(gè)點(diǎn)與該點(diǎn)分別作直線，所形成的個(gè)夾角的方差越小。該算法主要優(yōu)點(diǎn)是無(wú)需設(shè)置參數(shù)，受數(shù)據(jù)維數(shù)的影響較小，然而該算法的時(shí)間復(fù)雜度為O(dn3)，當(dāng)數(shù)據(jù)量很大時(shí)，計(jì)算開(kāi)銷(xiāo)難以接受。為此Pham等人提出了FastVOA（fast variance of angles）算法[7]。該算法通過(guò)隨機(jī)投影和AMS Sketch方法對(duì)ABOD算法作近似處理，在一定誤差內(nèi)，可以將時(shí)間復(fù)雜度降低到O(n lbn(d+lb2n))。

基于鄰近度的異常點(diǎn)檢測(cè)算法側(cè)重于尋找局部異常點(diǎn)。這類(lèi)方法的基本假設(shè)是，數(shù)據(jù)集中可能包含多個(gè)數(shù)據(jù)種類(lèi)，每類(lèi)數(shù)據(jù)的分布性質(zhì)不同，從全局角度尋找異常點(diǎn)不一定有效。因此這類(lèi)方法在計(jì)算數(shù)據(jù)點(diǎn)的異常度時(shí)，只選擇對(duì)應(yīng)的局部鄰域作為參照集，而不考慮數(shù)據(jù)的整體分布。這類(lèi)方法中最具代表性的是基于距離的異常點(diǎn)檢測(cè)算法和基于密度的異常點(diǎn)檢測(cè)算法?；诰嚯x的異常點(diǎn)檢測(cè)算法最早由Knorr等人提出[8-9]，該算法的基本設(shè)想是：若某個(gè)數(shù)據(jù)點(diǎn)在半徑為?的區(qū)域內(nèi)的近鄰占總數(shù)據(jù)點(diǎn)的比例不超過(guò)π，則該數(shù)據(jù)點(diǎn)為異常點(diǎn)。該算法的主要缺點(diǎn)是，實(shí)際應(yīng)用中很難估計(jì)參數(shù)?。Ramaswamy等人提出了基于k近鄰的算法[10]，該算法將數(shù)據(jù)點(diǎn)到第k個(gè)近鄰的距離作為該點(diǎn)的異常度?；诰嚯x的異常點(diǎn)檢測(cè)算法的主要缺陷是，如果數(shù)據(jù)集同時(shí)包含多個(gè)密度不同的簇，那么密度較小的簇所包含的數(shù)據(jù)點(diǎn)容易被誤判為異常點(diǎn)。為了克服此問(wèn)題，Breunig等人提出了LOF算法[3]。該算法的基本設(shè)想是：如果某數(shù)據(jù)點(diǎn)處的密度低于其鄰域內(nèi)其他數(shù)據(jù)點(diǎn)處的平均密度，則該點(diǎn)為異常點(diǎn)，反之則為正常點(diǎn)。該算法的主要問(wèn)題是對(duì)k的取值比較敏感。Kriegel等人提出了LoOP（local outlier probabilities）算法[11]，該算法將LOF算法的思想與概率論相結(jié)合，使得算法對(duì)帶噪聲的數(shù)據(jù)更健壯，并且該算法給出的異常度等價(jià)于某數(shù)據(jù)點(diǎn)為異常點(diǎn)的概率，更具有直觀意義。Zhang等人提出了LDOF算法[4]，該算法在某種程度上借鑒了LOF算法相對(duì)密度的思想，它把某個(gè)數(shù)據(jù)點(diǎn)到k個(gè)近鄰的距離的均值稱(chēng)作KNN distance，把k個(gè)近鄰彼此之間的距離的均值稱(chēng)作KNN inner distance，然后把這兩種距離的比值作為該數(shù)據(jù)點(diǎn)的異常度。

傳統(tǒng)的基于鄰近度的異常點(diǎn)檢測(cè)算法都會(huì)受到“維數(shù)災(zāi)”的影響[12]。為了克服此問(wèn)題，Agrawal對(duì)LOF算法進(jìn)行了改進(jìn)[13]，提出了基于局部子空間的異常點(diǎn)檢測(cè)算法。該算法的基本設(shè)想是：若數(shù)據(jù)點(diǎn)的近鄰在某個(gè)屬性上的方差越小，則在該屬性上越容易發(fā)現(xiàn)異常點(diǎn)，應(yīng)該提高該屬性的權(quán)重，因此該算法使用加權(quán)歐式距離代替LOF算法中的距離函數(shù)。Keller等人通過(guò)對(duì)數(shù)據(jù)集在不同子空間內(nèi)屬性的邊際分布進(jìn)行研究，發(fā)現(xiàn)異常點(diǎn)只有在某些高對(duì)比度子空間內(nèi)才較為顯著，因此提出了HiCS（high contrast subspaces）算法[14]。該算法分兩階段進(jìn)行：第一階段搜索高對(duì)比度子空間，本質(zhì)上是特征選擇的過(guò)程；第二階段在特定的子空間內(nèi)使用傳統(tǒng)方法進(jìn)行異常點(diǎn)檢測(cè)。實(shí)驗(yàn)結(jié)果顯示，基于這一改進(jìn)的LOF算法在高維數(shù)據(jù)上的效果有了一定改善。然而這種方法的缺點(diǎn)是搜索子空間較為耗時(shí)，并且由于各個(gè)數(shù)據(jù)點(diǎn)所適用的子空間不一定相同，若只用一個(gè)子空間會(huì)影響各數(shù)據(jù)點(diǎn)異常度的準(zhǔn)確性。Kriegel等人提出了SOD[15]subspace outlier degree）算法和COP[16]（correlation outlier probability）算法，這兩個(gè)算法能夠?qū)γ總€(gè)數(shù)據(jù)點(diǎn)選擇最佳的子空間進(jìn)行異常度計(jì)算，但是算法復(fù)雜度較高。

基于集成學(xué)習(xí)的異常點(diǎn)檢測(cè)是近年來(lái)出現(xiàn)的一個(gè)新的研究熱點(diǎn)。這類(lèi)方法通過(guò)構(gòu)造多個(gè)不同的異常點(diǎn)檢測(cè)器，然后合并所有檢測(cè)器的輸出，使得檢測(cè)效果比任一單個(gè)的檢測(cè)器更好[17-19]。這類(lèi)方法的有效性主要取決于3個(gè)因素：檢測(cè)器本身的準(zhǔn)確度，檢測(cè)器之間的差異性，如何集成各個(gè)檢測(cè)器的輸出[20]。

3 PCA

PCA是無(wú)監(jiān)督學(xué)習(xí)中常用的一種數(shù)據(jù)分析方法，其主要思想是：在降低數(shù)據(jù)維數(shù)的同時(shí)，保持?jǐn)?shù)據(jù)中對(duì)方差貢獻(xiàn)最大的特征；其基本方法是：通過(guò)正交線性變換，將原數(shù)據(jù)投影到一個(gè)新的坐標(biāo)系統(tǒng)中，使得新數(shù)據(jù)在各個(gè)主分量（principal component，PC）上投影的方差最大化。

更具體地說(shuō)，假設(shè)數(shù)據(jù)矩陣為X∈?n×d，且每列均值為0。PCA尋求一組標(biāo)準(zhǔn)正交基W=(w1,w2,…,wp)，其中wk∈?d，使得：

為了求解上式，先將其展開(kāi)為矩陣形式：

通過(guò)拉格朗日乘子法得到：

令L(X,W)關(guān)于W的偏導(dǎo)數(shù)為0，并計(jì)算化簡(jiǎn)得：

由于X的協(xié)方差矩陣Σ=X′X，于是有：

顯然上式是一個(gè)特征方程。由于協(xié)方差矩陣Σ是實(shí)對(duì)稱(chēng)矩陣，能夠?qū)ζ鋵?duì)進(jìn)行特征分解，所得的特征向量即為標(biāo)準(zhǔn)正交基，各個(gè)特征值即為方差。

然而在實(shí)際計(jì)算中，為了保證數(shù)值穩(wěn)定性，PCA通常借助奇異值分解來(lái)實(shí)現(xiàn)。奇異值分解指的是把矩陣X分解為如下形式：

其中，U為n×n階正交矩陣，每列稱(chēng)為左奇異值向量；V為d×d階正交矩陣，每列稱(chēng)為右奇異值向量；S為n×d階對(duì)角矩陣，對(duì)角線上的元素Sij稱(chēng)為奇異值。將協(xié)方差矩陣Σ按奇異值分解的方式展開(kāi)：

可見(jiàn)PCA所求的標(biāo)準(zhǔn)正交基W就是矩陣X的右奇異值向量V，對(duì)應(yīng)的方差就是矩陣X的各個(gè)奇異值的平方。因此直接對(duì)矩陣X進(jìn)行奇異值分解就能間接實(shí)現(xiàn)PCA，無(wú)需通過(guò)計(jì)算協(xié)方差矩陣然后對(duì)其特征分解來(lái)實(shí)現(xiàn)。

4 基于鄰域離散度的異常點(diǎn)檢測(cè)算法

4.1 離散度

一般而言，數(shù)據(jù)中的異常點(diǎn)分布較為稀疏，正常點(diǎn)較為密集，如圖2所示。為了便于討論數(shù)據(jù)點(diǎn)在局部空間內(nèi)的分布情況，本文先給出鄰域的定義。

Fig.2 Data contaminated with outliers圖2 含異常點(diǎn)的數(shù)據(jù)

定義1（鄰域）對(duì)于數(shù)據(jù)點(diǎn)xi∈?d，若其k階近鄰依次為，其中。則稱(chēng)點(diǎn)集為數(shù)據(jù)點(diǎn)xi的鄰域，點(diǎn)集為數(shù)據(jù)點(diǎn)xi的去心鄰域。

在一定的k取值下，正常點(diǎn)的鄰域主要包含其他正常點(diǎn)以及少量噪聲點(diǎn)，因此正常點(diǎn)的鄰域所占空間較小，鄰域較為緊致；而異常點(diǎn)的鄰域包含其他異常點(diǎn)甚至正常點(diǎn)，因此異常點(diǎn)的鄰域所占空間較大，數(shù)據(jù)點(diǎn)在該空間內(nèi)的離散度較高。如圖2所示，正常數(shù)據(jù)點(diǎn)A的去心鄰域都是正常點(diǎn)，異常數(shù)據(jù)點(diǎn)B的去心鄰域既包含正常點(diǎn)也包含其他異常點(diǎn)。利用這一特性，只要度量各個(gè)數(shù)據(jù)點(diǎn)所在鄰域的離散度，就能實(shí)現(xiàn)異常點(diǎn)檢測(cè)。

可見(jiàn)本文對(duì)離散度的定義本質(zhì)上等同于跡范數(shù)（trace norm），因而。根據(jù)文獻(xiàn)[21]的證明，矩陣的跡范數(shù)具有以下性質(zhì)：

該性質(zhì)表明，跡范數(shù)的上界是譜范數(shù)與秩的乘積。若跡范數(shù)越大，則譜范數(shù)或秩越大，說(shuō)明構(gòu)成鄰域的數(shù)據(jù)點(diǎn)較為離散；若跡范數(shù)越小，則譜范數(shù)和秩都較小，說(shuō)明鄰域在整體上較為緊致。因此定義2能夠有效地刻畫(huà)鄰域的離散度。

為了進(jìn)一步驗(yàn)證定義2對(duì)正常點(diǎn)和異常點(diǎn)的區(qū)分能力，本文對(duì)圖2所示的數(shù)據(jù)集做了初步的實(shí)驗(yàn)：取k=5，分別計(jì)算正常點(diǎn)和異常點(diǎn)的鄰域離散度，然后將離散度視為隨機(jī)變量，通過(guò)核密度估計(jì)分別繪制出相應(yīng)的概率密度函數(shù)。最終如圖3所示，其中藍(lán)色實(shí)線代表正常點(diǎn)的鄰域離散度概率密度函數(shù)，紅色虛線代表異常點(diǎn)的鄰域離散度概率密度函數(shù)，可見(jiàn)兩個(gè)分布的重疊部分較小，因此定義2能夠有效區(qū)分正常點(diǎn)和異常點(diǎn)。

Fig.3 Probability density function of dispersion圖3 離散度的概率密度函數(shù)

4.2 基于鄰域離散度的異常點(diǎn)檢測(cè)算法

由前文的討論可知，正常點(diǎn)的鄰域離散度較小，而異常點(diǎn)的鄰域離散度較大，通過(guò)計(jì)算數(shù)據(jù)點(diǎn)所在鄰域的離散度，就能得知該數(shù)據(jù)點(diǎn)的異常度。因此，本文對(duì)數(shù)據(jù)點(diǎn)的異常度定義如下。

定義3（異常度）數(shù)據(jù)點(diǎn)xi的異常度即為該點(diǎn)所在的k階鄰域的離散度。若某個(gè)數(shù)據(jù)點(diǎn)的異常度越高，則該數(shù)據(jù)點(diǎn)越有可能是異常點(diǎn)。

根據(jù)上述定義，通過(guò)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的異常度，按數(shù)值高低進(jìn)行排序，最后輸出異常度最高的t個(gè)數(shù)據(jù)點(diǎn)，就可以實(shí)現(xiàn)異常點(diǎn)檢測(cè)。具體算法如下：

算法1 DON算法

本算法通過(guò)一次循環(huán)就能完成。對(duì)每個(gè)數(shù)據(jù)點(diǎn)來(lái)說(shuō)，主要的計(jì)算量在于兩部分：第一部分是尋找數(shù)據(jù)點(diǎn)xi的k近鄰，通過(guò)使用k-d樹(shù)[22]作為數(shù)據(jù)結(jié)構(gòu)，查詢(xún)k近鄰的時(shí)間復(fù)雜度為O(dnlbn)。第二部分是對(duì)鄰域做主成分分析，由于主成分分析是基于奇異值分解實(shí)現(xiàn)的，時(shí)間復(fù)雜度為O(min(kd2,k2d))。因此當(dāng)k的取值不超過(guò)數(shù)據(jù)維數(shù)時(shí)，每個(gè)數(shù)據(jù)點(diǎn)的計(jì)算復(fù)雜度與維數(shù)的關(guān)系仍然是線性的。

參數(shù)k的選取對(duì)算法效果有著最直接的影響。由定義1可知，當(dāng)k=n時(shí)，任意數(shù)據(jù)點(diǎn)所在鄰域等同于整個(gè)數(shù)據(jù)集X，因此鄰域的離散度等同于整個(gè)數(shù)據(jù)集的離散度，算法將失去區(qū)分能力，從而k的選取并不是越大越好。事實(shí)上，如果整個(gè)數(shù)據(jù)集落在m維（m＜d）的低維流形上，那么任意局部鄰域的有效維數(shù)m′都不會(huì)超過(guò)m，這就意味著取k=m就足以刻畫(huà)大部分正常點(diǎn)所在鄰域的特性。而確定整個(gè)數(shù)據(jù)集的有效維數(shù)可以通過(guò)對(duì)整個(gè)數(shù)據(jù)集做主成分分析來(lái)確定，如果前m個(gè)主成分的可解釋變異量（explained variance）足夠高，就可以舍棄其余主成分，認(rèn)為數(shù)據(jù)集的有效維數(shù)是m。

參數(shù)t的選取也十分重要。在實(shí)際的應(yīng)用場(chǎng)景中，由于沒(méi)有Ground Truth，無(wú)法得知真實(shí)異常點(diǎn)的個(gè)數(shù)，但是可以通過(guò)統(tǒng)計(jì)的方法估計(jì)t的大小。設(shè)正常點(diǎn)的異常度為隨機(jī)變量Y1，異常點(diǎn)的異常度為隨機(jī)變量Y2，所有數(shù)據(jù)點(diǎn)的異常度為隨機(jī)變量Y。若Y1與Y2均服從高斯分布，那么Y就服從混合高斯分布：

其中Δ∈{0,1},Pr(Δ=1)=π。通過(guò)EM算法[23]，給定適當(dāng)?shù)某跏贾岛褪諗織l件，經(jīng)過(guò)數(shù)次迭代就能求出隱變量π，即為異常點(diǎn)的比例，因此可以取。

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

5.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用UCI數(shù)據(jù)集[24]，具體屬性如表1所示。其中Iris、Wine數(shù)據(jù)集由3種類(lèi)別的樣本構(gòu)成，因此將其中一類(lèi)數(shù)據(jù)進(jìn)行采樣，使其所占比例低于10%，并標(biāo)記為異常點(diǎn)。

Table 1 Properties of dataset表1 數(shù)據(jù)集屬性

為了驗(yàn)證本文算法的有效性，將DON算法與其他幾種流行的異常點(diǎn)檢測(cè)算法進(jìn)行對(duì)比，這些算法分別是LOF算法[3]、LDOF算法[4]、LoOP算法[11]、HiCS算法[14]、SOD算法[15]。其中LOF和LoOP是基于密度的異常點(diǎn)檢測(cè)算法，LDOF是基于距離的異常點(diǎn)檢測(cè)算法，HiCS和SOD是基于子空間的異常點(diǎn)檢測(cè)算法。這幾種算法的實(shí)現(xiàn)均來(lái)自于ELKI數(shù)據(jù)挖掘框架[25]。

由于所有對(duì)比算法本質(zhì)上都是依據(jù)數(shù)據(jù)點(diǎn)的局部鄰域來(lái)計(jì)算異常度，對(duì)算法效果影響最大參數(shù)是k。因此本實(shí)驗(yàn)對(duì)所有算法分別取k=5,6,…,100進(jìn)行測(cè)試。對(duì)于SOD算法，根據(jù)文獻(xiàn)中的建議[15]，實(shí)驗(yàn)將參數(shù)l設(shè)置為k，α設(shè)置為0.8。

5.2 評(píng)價(jià)標(biāo)準(zhǔn)

為了更好地對(duì)比各個(gè)算法在不同參數(shù)下的檢測(cè)效果，本文采用AUC（area under curve）作為評(píng)價(jià)標(biāo)準(zhǔn)。AUC指的是ROC（receiver operating characteristic）曲線下方的面積，而ROC曲線的參數(shù)式方程如下：

假設(shè)所有數(shù)據(jù)點(diǎn)為集合D，真實(shí)異常點(diǎn)為集合G，算法輸出的前t個(gè)異常度最高的數(shù)據(jù)點(diǎn)為集合S(t)，則TPR(t)和FPR(t)的計(jì)算公式如下：

5.3 實(shí)驗(yàn)結(jié)果與分析

各個(gè)算法在不同k值下的AUC如圖4所示。

Fig.4 AUC trends with differentksettings of DON,LDOF,LOF,LoOP,HiCS,SOD圖4 k取不同值時(shí)DON、LDOF、LOF、LoOP、HiCS、SOD算法的AUC變化

對(duì)于Ann-Thyroid、Banknote兩個(gè)數(shù)據(jù)集來(lái)說(shuō)（如圖4（a）、（b）），DON算法在k增大時(shí)，AUC呈現(xiàn)出一定的降低趨勢(shì)，但總體來(lái)說(shuō)AUC仍然維持在0.9以上，算法比較穩(wěn)定。SOD算法的AUC波動(dòng)也不大，但是在各種k取值下，算法有效性均不及DON算法。而其余的算法在k≥100之后，AUC才趨于穩(wěn)定。因?yàn)殡S著k值增大，算法運(yùn)行時(shí)間也越長(zhǎng)，而且對(duì)無(wú)監(jiān)督學(xué)習(xí)來(lái)說(shuō)，算法在實(shí)際應(yīng)用時(shí)沒(méi)有Ground Truth，難以調(diào)整算法參數(shù)，所以相比之下DON算法具有一定優(yōu)勢(shì)。

對(duì)于BCWD、Diabetes、Yeast數(shù)據(jù)集來(lái)說(shuō)（如圖4（c）、（d）、（h）），由于這3個(gè)數(shù)據(jù)集的異常點(diǎn)比例在30%以上，取較大的k值才能刻畫(huà)數(shù)據(jù)點(diǎn)的局部特性。因此大部分算法的AUC總體上隨著k的增大而增大，但是DON算法的AUC高于其他算法，并且曲線走勢(shì)較為穩(wěn)健。

對(duì)于Ionosphere數(shù)據(jù)集來(lái)說(shuō)（如圖4（e）），DON算法在k≤30時(shí)效果較好，之后呈現(xiàn)出下降趨勢(shì)。LOF和LDOF算法在k=5附近取得最好效果，之后也逐漸下降。而LoOP算法則在k≥85附近才取得最好效果。HiCS算法總體上效果不佳，而且波動(dòng)較大。

對(duì)于Iris數(shù)據(jù)集來(lái)說(shuō)（如圖4（f）），大部分算法在k＞50之后，AUC開(kāi)始顯著下降?？紤]到該數(shù)據(jù)集由兩種數(shù)量為50的正常點(diǎn)以及10個(gè)異常點(diǎn)構(gòu)成，當(dāng)k＞50時(shí)，正常點(diǎn)的鄰域必然包含異常點(diǎn)或是另一類(lèi)別的數(shù)據(jù)點(diǎn)，導(dǎo)致正常點(diǎn)的異常度增大，與真實(shí)異常點(diǎn)之間的區(qū)分度降低，因此AUC的下降是合理的。

對(duì)Wine數(shù)據(jù)集來(lái)說(shuō)（如圖4（g）），DON算法在取不同的k時(shí)AUC較高，且波動(dòng)較小。而LOF、LDOF、LoOP算法則在k≥25之后，AUC才逐漸趨于穩(wěn)定。相比之下，HiCS、SOD算法的表現(xiàn)不太理想，尤其是k≥25之后，AUC嚴(yán)重降低。

綜上分析，DON算法在7個(gè)數(shù)據(jù)集上都取得了較好的效果，在不同參數(shù)下表現(xiàn)也較為穩(wěn)定，AUC基本不會(huì)隨著k值的變化出現(xiàn)較大波動(dòng)。

6 總結(jié)與未來(lái)工作

本文提出了一種新的基于鄰域離散度的異常點(diǎn)檢測(cè)算法，該算法能夠有效克服正常數(shù)據(jù)在邊緣處異常度過(guò)高的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，本文算法能夠更有效地檢測(cè)數(shù)據(jù)集中的異常點(diǎn)，并且對(duì)參數(shù)選擇不敏感，性能較為穩(wěn)定。進(jìn)一步的工作包括分析本文的異常點(diǎn)定義與其他文獻(xiàn)中的異常點(diǎn)定義之間的內(nèi)在聯(lián)系，研究使用集成學(xué)習(xí)的方式進(jìn)一步提高異常點(diǎn)檢測(cè)的準(zhǔn)確率。

[1]Yang Chao,Chen Guoliang,Shen Yifei.Outlier analysis for gene expression data[J].Journal of Computer Science and Technology,2004,19(1):13-21.

[2]Prakobphol K,Zhan J.A novel outlier detection scheme for network intrusion detection systems[C]//Proceedings of the 2008 International Conference on Information Security and Assurance,Busan,Korea,Apr 24-26,2008.Piscataway,USA: IEEE,2008:555-560.

[3]Breunig M M,Kriegel H P,Ng R T,et al.LOF:identifying density-based local outliers[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data,Dallas,USA,May 15-18,2000.New York:ACM,2000: 93-104.

[4]Zhang Ke,Hutter M,Jin Huidong.A new local distancebased outlier detection approach for scattered real-world data [C]//LNCS 5476:Proceedings of the 13th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining,Bangkok,Thailand,Apr 27-30,2009.Berlin,Heidelberg:Springer,2009:813-822.

[5]Johnson T,Kwok I,Ng R T.Fast computation of 2-dimensional depth contours[C]//Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, New York,Aug 27-31,1998.Menlo Park,USA:AAAI,1998: 224-228.

[6]Kriegel H P,Shubert M,Zimek A.Angle-based outlier detection in high-dimensional data[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Las Vegas,USA,Aug 24-27,2008.New York:ACM,2008:444-452.

[7]Pham N,Pagh R.A near-linear time approximation algorithm for angle-based outlier detection in high-dimensional data[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing,Aug 12-16,2012.New York:ACM,2012:877-885. [8]Knorr E M,Ng R T.A unified approach for mining outliers [C]//Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining,Newport Beach, USA,Aug 14-17,1997.Menlo Park,USA:AAAI,1997: 219-222.

[9]Knorr E M,Ng R T.Algorithms for mining distance-based outliers in large datasets[C]//Proceedings of the 24rd Inter-national Conference on Very Large Data Bases,New York, Aug 24-27,1998.San Francisco,USA:Morgan Kaufmann Publishers Inc,1998:392-403.

[10]Ramaswamy S,Rastogi R,Shim K.Efficient algorithms for mining outliers from largedata sets[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data,Dallas,USA,May 15-18,2000.New York: ACM,2000:427-438.

[11]Kriegel H P,Kr?ger P,Schubert E,et al.LoOP:local outlier probabilities[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management,Hong Kong, China,Nov 2-6,2009.New York:ACM,2009:1649-1652.

[12]Beyer K,Goldstein J,Ramakrishnan R,et al.When is“nearest neighbor"meaningful?[C]//LNCS 1540:Proceedings of the 7th International Conference on Database Theory,Jerusalem,Israel,Jan 10-12,1999.Berlin,Heidelberg:Springer, 1999:217-235.

[13]Agrawal A.Local subspace based outlier detection[C]//Proceedings of the 2nd International Conference on Contemporary Computing,Noida,India,Aug 17-19,2009.Berlin,Heidelberg:Springer,2009:149-157.

[14]Keller F,Muller E,Bohm K.HiCS:high contrast subspaces for density-based outlierranking[C]//Proceedings of the 2012 IEEE 28th International Conference on Data Engineering, Arlington,USA,Apr 1-5,2012.Piscataway,USA:IEEE, 2012:1037-1048.

[15]Kriegel H P,Kr?ger P,Schubert E,et al.Outlier detection in axis-parallel subspacesof high dimensional data[C]//Proceedings of the 13th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining,Bangkok,Thailand,Apr 27-30,2009.Berlin,Heidelberg:Springer,2009: 831-838.

[16]Kriegel H P,Kr?ger P,Schubert E,et al.Outlier detection in arbitrarily oriented subspaces[C]//Proceedings of the 12th IEEE International Conference on Data Mining,Brussels, Belgium,Dec 10-13,2012.Piscataway,USA:IEEE,2012: 379-388.

[17]LazarevicA,Kumar V.Feature bagging for outlier detection [C]//Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago,USA,Aug 21-24,2005.New York:ACM,2005: 157-166.

[18]Liu F T,Ting K M,Zhou Zhihua.Isolation-based anomaly detection[J].ACM Transactions on Knowledge Discovery from Data,2012,6(1):3.

[19]Zimek A,Gaudet M,Campello R J,et al.Subsampling for efficient and effective unsupervised outlier detection ensembles[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago,USA,Aug 11-14,2013.New York:ACM,2013: 428-436.

[20]Zimek A,Campello R J,Sander J,Ensembles for unsupervised outlier detection:challenges and research questions a position paper[J].ACM SIGKDD Explorations Newsletter, 2013,15(1):11-22.

[21]Fazel M.Matrix rank minimization with applications[D]. Serra Mall,Stanford,USA:Stanford University,2002.

[22]Arya S,Mount D M,Netanyahu N S,et al.An optimal algorithm for approximate nearest neighbor searching fixed dimensions[J].Journal of theACM,1998,45(6):891-923.

[23]Hastie T,Tibshirani R,Friedman J.The elements of statistical learning[M].New York:Springer,2001:272-282.

[24]Lichman M.UCI machine learning repository[Z].2013.

[25]Achtert E,Kriegel H P,Zimek A.ELKI:a software system for evaluation of subspace clustering algorithms[C]//LNCS 5069:Proceedings of the 20th International Conference on Scientific and Statistical Database Management,Hong Kong, China,Jul 9-11,2008.Berlin,Heidelberg:Springer,2008: 580-585.

SHEN Yanhui was born in 1987.He is an M.S.candidate at Zhejiang Normal University.His research interests include machine learning and data mining,etc.

沈琰輝（1987—），男，江蘇宜興人，浙江師范大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。

LIU Huawen was born in 1977.He received the Ph.D.degree in computer science from Jilin University in 2010. Now he is an associate professor at Zhejiang Normal University.His research interests include data mining and machine learning,etc.

劉華文（1977—），男，江西樂(lè)安人，2010年于吉林大學(xué)獲得計(jì)算機(jī)博士學(xué)位，現(xiàn)為浙江師范大學(xué)副教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，機(jī)器學(xué)習(xí)等。發(fā)表學(xué)術(shù)論文20余篇，其中SCI檢索13篇，主持或承擔(dān)過(guò)多項(xiàng)國(guó)家自然科學(xué)基金、浙江省自然科學(xué)基金、中國(guó)博士后基金和國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放項(xiàng)目等。

XU Xiaodan was born in 1978.She is a lecturer at Zhejiang Normal University.Her research interests include machine learning and data mining,etc.

徐曉丹（1978—），女，浙江東陽(yáng)人，浙江師范大學(xué)講師，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。發(fā)表學(xué)術(shù)論文10余篇，主持或參與過(guò)多項(xiàng)浙江省自然科學(xué)基金、浙江省教育廳項(xiàng)目等。

ZHAO Jianmin was born in 1950.He received the M.S.degree in computer science from Zhejiang University in 2000.Now he is a professor and Ph.D.supervisor at Zhejiang Normal University.His research interests include machine learning,cloud computing and Internet of things,etc.

趙建民（1950—），男，上海人，2000年于浙江大學(xué)獲得碩士學(xué)位，現(xiàn)為浙江師范大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，云計(jì)算，物聯(lián)網(wǎng)等。發(fā)表學(xué)術(shù)論文50余篇，主持或承擔(dān)過(guò)多項(xiàng)國(guó)家自然科學(xué)基金、浙江省自然科學(xué)基金重大項(xiàng)目、國(guó)家公安部項(xiàng)目等。

CHEN Zhongyu was born in 1965.He received the Ph.D.degree in computer science from Shanghai University in 2010.Now he is a professor at Zhejiang Normal University.His research interests include machine learning and data mining,etc.

陳中育（1965—），男，浙江浦江人，2010年于上海大學(xué)獲得計(jì)算機(jī)博士學(xué)位，現(xiàn)為浙江師范大學(xué)教授，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。發(fā)表學(xué)術(shù)論文30余篇，主持或承擔(dān)過(guò)多項(xiàng)國(guó)家自然科學(xué)基金、浙江省自然科學(xué)基金、浙江省科技廳重點(diǎn)項(xiàng)目等。

Outlier DetectionAlgorithm Based on Dispersion of Neighbors*

SHEN Yanhui,LIU Huawen+,XU Xiaodan,ZHAO Jianmin,CHEN Zhongyu
College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua,Zhejiang 321004,China
+Corresponding author:E-mail:hwliu@zjnu.edu.cn

Outlier detection is an important task of machine learning and data mining.A major limitation of the existing outlier detection methods is that the outlierness of border points may be very high,leading to yield misleading results in some situations.To cope with this problem,this paper proposes a novel outlier detection algorithm based on the dispersion of neighbors.The proposed algorithm adopts the dispersion of a data point's neighbors as its outlier degree, thus the outlierness of border points will not be very high while the normal data and outliers can still be well distinguished.The experimental results show the proposed algorithm is more effective in detecting outliers,less sensitive to parameter settings and is stable in terms of performance.

outlier detection;machine learning;data mining;principal component analysis

10.3778/j.issn.1673-9418.1509075

A

TP181

*The National Natural Science Foundation of China under Grant Nos.61272007,61272468,61572443(國(guó)家自然科學(xué)基金);the Natural Science Foundation of Zhejiang Province under Grant No.LY14F020012(浙江省自然科學(xué)基金);the Foundation of Zhejiang Educational Committee under Grant No.Y201328291(浙江省教育廳項(xiàng)目).

Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-20,http://www.cnki.net/kcms/detail/11.5602.TP.20151020.1041.002.html