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

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

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

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

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

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 PCA

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

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

為了求解上式，先將其展開為矩陣形式：

通過拉格朗日乘子法得到：

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

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

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

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

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

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

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

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（鄰域）對于數(shù)據(jù)點(diǎn)xi∈?d，若其k階近鄰依次為，其中。則稱點(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)。利用這一特性，只要度量各個數(shù)據(jù)點(diǎn)所在鄰域的離散度，就能實(shí)現(xiàn)異常點(diǎn)檢測。

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

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

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

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

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

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

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

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

算法1 DON算法

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

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

參數(shù)t的選取也十分重要。在實(shí)際的應(yīng)用場景中，由于沒有Ground Truth，無法得知真實(shí)異常點(diǎn)的個數(shù)，但是可以通過統(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)=π。通過EM算法[23]，給定適當(dāng)?shù)某跏贾岛褪諗織l件，經(jīng)過數(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種類別的樣本構(gòu)成，因此將其中一類數(shù)據(jù)進(jìn)行采樣，使其所占比例低于10%，并標(biāo)記為異常點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文提出了一種新的基于鄰域離散度的異常點(diǎn)檢測算法，該算法能夠有效克服正常數(shù)據(jù)在邊緣處異常度過高的問題。實(shí)驗(yàn)結(jié)果表明，本文算法能夠更有效地檢測數(shù)據(jù)集中的異常點(diǎn)，并且對參數(shù)選擇不敏感，性能較為穩(wěn)定。進(jìn)一步的工作包括分析本文的異常點(diǎn)定義與其他文獻(xiàn)中的異常點(diǎn)定義之間的內(nèi)在聯(lián)系，研究使用集成學(xué)習(xí)的方式進(jìn)一步提高異常點(diǎn)檢測的準(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—），男，江西樂安人，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)過多項(xiàng)國家自然科學(xué)基金、浙江省自然科學(xué)基金、中國博士后基金和國家重點(diǎn)實(shí)驗(yàn)室開放項(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—），女，浙江東陽人，浙江師范大學(xué)講師，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。發(fā)表學(xué)術(shù)論文10余篇，主持或參與過多項(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)過多項(xiàng)國家自然科學(xué)基金、浙江省自然科學(xué)基金重大項(xiàng)目、國家公安部項(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)過多項(xiàng)國家自然科學(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(國家自然科學(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