郭一陽(yáng)，于炯，2*，杜旭升，楊少智，曹銘

基于自編碼器與集成學(xué)習(xí)的離群點(diǎn)檢測(cè)算法

郭一陽(yáng)1，于炯1，2*，杜旭升1，楊少智1，曹銘3

（1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046； 2.新疆大學(xué) 軟件學(xué)院，烏魯木齊 830091； 3.中國(guó)海洋大學(xué) 信息科學(xué)與工程學(xué)院，山東 青島 266100）（ ? 通信作者電子郵箱yujiong@xju.edu.cn）

針對(duì)基于自編碼器的離群點(diǎn)檢測(cè)算法在中小規(guī)模數(shù)據(jù)集上易過(guò)擬合以及傳統(tǒng)的基于集成學(xué)習(xí)的離群點(diǎn)檢測(cè)算法未對(duì)基檢測(cè)器進(jìn)行優(yōu)化選擇而導(dǎo)致的檢測(cè)精度低的問(wèn)題，提出了一種基于自編碼器與集成學(xué)習(xí)的離群點(diǎn)檢測(cè)（EAOD）算法。首先，隨機(jī)改變自編碼器的連接結(jié)構(gòu)來(lái)生成不同的基檢測(cè)器，以獲取數(shù)據(jù)對(duì)象的離群值和標(biāo)簽離群值；然后，通過(guò)最近鄰算法計(jì)算數(shù)據(jù)對(duì)象之間的歐氏距離，并在對(duì)象周圍構(gòu)建局部區(qū)域；最后，根據(jù)離群值與標(biāo)簽離群值之間的相似度，選擇在該區(qū)域內(nèi)檢測(cè)能力強(qiáng)的基檢測(cè)器進(jìn)行組合，組合后的對(duì)象離群值作為EAOD算法最終判定的離群值。在實(shí)驗(yàn)中，所提算法與自編碼器（AE）算法相比，在Cardio數(shù)據(jù)集上，接受者操作特征曲線下方的面積（AUC）和平均精度（AP）分值分別提高了8.08個(gè)百分點(diǎn)和9.17個(gè)百分點(diǎn)；所提算法與特征裝袋（FB）集成學(xué)習(xí)算法相比，在Mnist數(shù)據(jù)集上，運(yùn)行時(shí)間成本降低了21.33%。實(shí)驗(yàn)結(jié)果表明，在無(wú)監(jiān)督學(xué)習(xí)下所提算法具有良好的檢測(cè)性能和檢測(cè)實(shí)時(shí)性。

離群點(diǎn)檢測(cè)；集成學(xué)習(xí)；自編碼器；基檢測(cè)器；無(wú)監(jiān)督學(xué)習(xí)

0 引言

離群點(diǎn)是指那些與數(shù)據(jù)集中絕大多數(shù)對(duì)象的產(chǎn)生機(jī)制不同的、偏離程度較大的數(shù)據(jù)對(duì)象［1］。離群點(diǎn)檢測(cè)算法通常用于解決金融欺詐檢測(cè)、網(wǎng)絡(luò)入侵檢測(cè)、醫(yī)療輔助診斷等問(wèn)題［2-4］。

由于現(xiàn)實(shí)環(huán)境中往往缺乏數(shù)據(jù)集對(duì)應(yīng)的標(biāo)簽，因此在離群點(diǎn)檢測(cè)算法中通常采用無(wú)監(jiān)督學(xué)習(xí)的方式［5］。近十年，深度學(xué)習(xí)在數(shù)據(jù)挖掘領(lǐng)域蓬勃發(fā)展［6］?；谧跃幋a器的離群點(diǎn)檢測(cè)算法利用神經(jīng)網(wǎng)絡(luò)的強(qiáng)大學(xué)習(xí)能力，學(xué)習(xí)輸入數(shù)據(jù)的模式，最后將那些在自編碼器的輸出層中難以重構(gòu)的對(duì)象判定為離群點(diǎn)。但該算法在中小規(guī)模數(shù)據(jù)集上容易產(chǎn)生過(guò)擬合問(wèn)題，導(dǎo)致算法的檢測(cè)精度低［7］。在集成學(xué)習(xí)中，不同的基檢測(cè)器各自產(chǎn)生獨(dú)立誤差，將多個(gè)基檢測(cè)器進(jìn)行組合，可以降低單一基檢測(cè)器的過(guò)擬合風(fēng)險(xiǎn)［8］。因此，將自編碼器與集成學(xué)習(xí)相結(jié)合可以有效地降低過(guò)擬合風(fēng)險(xiǎn)。實(shí)際上，設(shè)計(jì)產(chǎn)生獨(dú)立誤差的集成學(xué)習(xí)框架具有一定的挑戰(zhàn)性。動(dòng)態(tài)分類器選擇（Dynamic Classifier Selection， DCS）算法［9］有效地緩解了這個(gè)具有挑戰(zhàn)性的問(wèn)題，其基本思想是平衡集成學(xué)習(xí)中基檢測(cè)器的準(zhǔn)確性和多樣性兩者之間的關(guān)系。DCS算法生成多個(gè)且不同的基檢測(cè)器，同時(shí)盡可能地提高基檢測(cè)器的準(zhǔn)確性，達(dá)到準(zhǔn)確識(shí)別離群點(diǎn)的目的。DCS算法的檢測(cè)效果取決于對(duì)基檢測(cè)器局部區(qū)域檢測(cè)能力的正確評(píng)估，如果在該局部區(qū)域內(nèi)不能正確評(píng)估基檢測(cè)器的檢測(cè)能力，那么將導(dǎo)致檢測(cè)精度低的結(jié)果。動(dòng)態(tài)集成選擇（Dynamic Ensemble Selection， DES）算法［10］通過(guò)優(yōu)化選擇一組基檢測(cè)器的方式，并通過(guò)一些規(guī)則（如投票規(guī)則）將該組基檢測(cè)器進(jìn)行有效組合，解決了不能正確評(píng)估基檢測(cè)器檢測(cè)能力的問(wèn)題。

受DCS和DES兩種算法的啟發(fā)，本文提出了基于自編碼器與集成學(xué)習(xí)的離群點(diǎn)檢測(cè)（Ensemble learning and Autoencoder-based Outlier Detection， EAOD）算法。由于數(shù)據(jù)對(duì)象之間在數(shù)據(jù)集中分布彼此有關(guān)聯(lián)，EAOD算法假設(shè)一組基檢測(cè)器在數(shù)據(jù)的鄰近對(duì)象上檢測(cè)能力良好，那么該組基檢測(cè)器在該數(shù)據(jù)上的檢測(cè)能力也同樣良好。EAOD算法的主要流程為：首先使用隨機(jī)連接的自編碼器作為集成學(xué)習(xí)框架中的基檢測(cè)器，初始化訓(xùn)練集數(shù)據(jù)對(duì)象的離群值，生成離群值矩陣和標(biāo)簽離群值矩陣；其次根據(jù)各個(gè)數(shù)據(jù)對(duì)象之間的歐氏距離在測(cè)試集數(shù)據(jù)對(duì)象周圍生成一個(gè)局部區(qū)域；最后在該局部區(qū)域內(nèi)，根據(jù)離群值矩陣和標(biāo)簽離群值矩陣計(jì)算數(shù)據(jù)對(duì)象余弦相似度，通過(guò)對(duì)比余弦相似度，選擇檢測(cè)能力強(qiáng)的基檢測(cè)器進(jìn)行組合，組合后的對(duì)象離群值作為EAOD算法最終判定的離群值。

本文算法的主要貢獻(xiàn)如下：

1）提出了一種隨機(jī)改變自編碼器連接結(jié)構(gòu)的方式。在EAOD算法中，通過(guò)對(duì)相鄰隱藏層中的神經(jīng)元進(jìn)行有放回隨機(jī)采樣，使得神經(jīng)元之間的一部分連接臨時(shí)性地消失，達(dá)到隨機(jī)改變自編碼器連接結(jié)構(gòu)的目的。

2）提出了一種在無(wú)監(jiān)督學(xué)習(xí)下標(biāo)記數(shù)據(jù)離群程度的方式。EAOD算法假設(shè)在不存在數(shù)據(jù)真實(shí)標(biāo)簽的情況下進(jìn)行離群點(diǎn)檢測(cè)，取全部基檢測(cè)器對(duì)數(shù)據(jù)輸出值的最大值作為數(shù)據(jù)離群程度的標(biāo)簽。

3）提出了一種在構(gòu)建的數(shù)據(jù)對(duì)象局部區(qū)域內(nèi)選擇合適的基檢測(cè)器進(jìn)行組合的方式。EAOD算法以定義鄰域簇的方式構(gòu)建數(shù)據(jù)局部區(qū)域，在該局部區(qū)域內(nèi)計(jì)算基檢測(cè)器上數(shù)據(jù)對(duì)象的離群值與標(biāo)簽離群值之間的余弦相似度，根據(jù)該相似度大小選擇合適的基檢測(cè)器進(jìn)行組合。

1 相關(guān)研究

從分類的角度，可以將現(xiàn)階段的離群點(diǎn)檢測(cè)算法分類為：1）基于統(tǒng)計(jì)；2）基于相似度；3）基于分類；4）基于聚類；5）基于神經(jīng)網(wǎng)絡(luò)；6）基于集成學(xué)習(xí)。值得注意的是，某些算法可能被劃分到不止一類中。

1）基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)算法通過(guò)對(duì)數(shù)據(jù)集中數(shù)據(jù)的分布情況做出假設(shè)，假定數(shù)據(jù)有一個(gè)已知的基本分布或統(tǒng)計(jì)模型，離群點(diǎn)則屬于基本模型中概率較低的對(duì)象。例如：基于直方圖的離群分?jǐn)?shù)（Histogram-Based Outlier Score， HBOS）算法［11］假設(shè)數(shù)據(jù)在每個(gè)維度具有獨(dú)立性，對(duì)每個(gè)維度做出直方圖進(jìn)行密度估計(jì)。該類算法常用到假設(shè)檢驗(yàn)或極值分析，其主要缺點(diǎn)是假設(shè)性強(qiáng)，效果與真實(shí)情況的匹配程度低。

2）基于相似度的離群點(diǎn)檢測(cè)算法針對(duì)正常點(diǎn)和離群點(diǎn)在數(shù)據(jù)集中分布不同的特點(diǎn)，通過(guò)數(shù)據(jù)對(duì)象之間的相似度（如：距離、密度等）檢測(cè)離群點(diǎn)。例如：最近鄰（-Nearest Neighbors，-NN）算法［12］通過(guò)計(jì)算數(shù)據(jù)對(duì)象之間的距離，得到數(shù)據(jù)對(duì)象的離群值等于該對(duì)象到它的第個(gè)近鄰的距離；局部離群因子（Local Outlier Factor， LOF）算法［13］通過(guò)評(píng)估數(shù)據(jù)集中數(shù)據(jù)對(duì)象與其近鄰的局部密度偏差，偏差較大的數(shù)據(jù)對(duì)象被定義是離群點(diǎn)。該類算法對(duì)數(shù)據(jù)對(duì)象的維度較為敏感，當(dāng)對(duì)象維度較高時(shí)，該類算法檢測(cè)性能較差。

3）基于分類的離群點(diǎn)檢測(cè)算法通過(guò)在數(shù)據(jù)集中不斷學(xué)習(xí)，找出有規(guī)律的決策邊界或超平面，得到的決策邊界或超平面所包含的少數(shù)數(shù)據(jù)對(duì)象被定義是離群點(diǎn)。該類算法的主要缺點(diǎn)是耗費(fèi)時(shí)間長(zhǎng)，且在稀疏數(shù)據(jù)集上效果較差［14］。

4）基于聚類的離群點(diǎn)檢測(cè)算法首先計(jì)算數(shù)據(jù)對(duì)象到它在距離上最近的簇的質(zhì)心之間的距離，其次根據(jù)該距離對(duì)數(shù)據(jù)對(duì)象賦予離群值，最后離群值越高的數(shù)據(jù)對(duì)象是離群點(diǎn)的可能性越高。該類算法的主要缺點(diǎn)是其尋找的是數(shù)據(jù)對(duì)象周圍的簇，不是發(fā)現(xiàn)離群點(diǎn)，檢測(cè)精度低［15］。

5）基于神經(jīng)網(wǎng)絡(luò)的離群點(diǎn)檢測(cè)算法通過(guò)學(xué)習(xí)輸入數(shù)據(jù)的模式，在輸出層重構(gòu)數(shù)據(jù)，以產(chǎn)生的重構(gòu)誤差作為對(duì)象的離群值。該類算法的主要缺點(diǎn)是其在中小規(guī)模數(shù)據(jù)集上容易產(chǎn)生過(guò)擬合問(wèn)題，導(dǎo)致算法的檢測(cè)精度低［16］。

6）基于集成學(xué)習(xí)的離群點(diǎn)檢測(cè)算法通過(guò)組合多個(gè)不同的基檢測(cè)器的輸出，得到精確的結(jié)果。其基本思想是執(zhí)行多個(gè)不同的基檢測(cè)器，產(chǎn)生不同的輸出值，對(duì)該多個(gè)不同的輸出值進(jìn)行評(píng)估，權(quán)衡偏差和方差。例如：文獻(xiàn)［17］設(shè)計(jì)了多個(gè)不同的基檢測(cè)器，增加模型的多樣性，提升檢測(cè)效果。該類算法的主要缺點(diǎn)是對(duì)集成學(xué)習(xí)中基檢測(cè)器的多樣性要求較高，若基檢測(cè)器不滿足一定程度的多樣性，則該算法不能保證多個(gè)不同的基檢測(cè)器的組合輸出比單個(gè)檢測(cè)能力強(qiáng)的基檢測(cè)器輸出更精確［18-19］。

2 本文方法

本章首先給出EAOD算法整體框架與流程，然后介紹EAOD算法中基檢測(cè)器的體系結(jié)構(gòu)及配置，最后給出EAOD算法的詳細(xì)步驟和時(shí)間復(fù)雜度分析。表1詳細(xì)列出了本節(jié)后續(xù)內(nèi)容所使用的符號(hào)定義。

表1　符號(hào)說(shuō)明

2.1　算法整體框架與流程

基于自編碼器與集成學(xué)習(xí)的EAOD離群點(diǎn)檢測(cè)算法分為4個(gè)階段實(shí)現(xiàn)：1）訓(xùn)練基檢測(cè)器。將隨機(jī)連接自編碼器作為集成學(xué)習(xí)中的基檢測(cè)器，并使用訓(xùn)練集訓(xùn)練基檢測(cè)器。2）標(biāo)記離群程度。在訓(xùn)練集的數(shù)據(jù)對(duì)象上標(biāo)記標(biāo)簽作為對(duì)象的離群程度。3）構(gòu)建局部區(qū)域。在測(cè)試集數(shù)據(jù)周圍構(gòu)建局部區(qū)域。4）基檢測(cè)器選擇與組合。在該局部區(qū)域選擇合適的基檢測(cè)器進(jìn)行組合，組合后的對(duì)象離群值作為EAOD算法最終判定的離群值。EAOD算法整體的框架與流程如圖1所示。

圖1　EAOD算法框架與流程

2.2　基檢測(cè)器的體系結(jié)構(gòu)及配置

2.2.1隨機(jī)連接自編碼器

自編碼器是一種特殊類型的多層前饋神經(jīng)網(wǎng)絡(luò)，具備對(duì)數(shù)據(jù)進(jìn)行分層和非線性降維功能。如圖2所示，自編碼器的輸入層節(jié)點(diǎn)數(shù)等于輸出層節(jié)點(diǎn)數(shù)，隱藏層的節(jié)點(diǎn)數(shù)相對(duì)較少；在體系結(jié)構(gòu)上，自編碼器是分層且對(duì)稱的。自編碼器的目標(biāo)是通過(guò)訓(xùn)練神經(jīng)網(wǎng)絡(luò)，最小化輸出層誤差進(jìn)而重構(gòu)輸入層。

圖2　自編碼器模型

隨機(jī)連接自編碼器是一種隨機(jī)改變自編碼器的連接結(jié)構(gòu)而產(chǎn)生的多層前饋神經(jīng)網(wǎng)絡(luò)。如圖3所示，輸入層節(jié)點(diǎn)數(shù)等于，從輸入層到節(jié)點(diǎn)數(shù)最少的隱藏層，其中相鄰兩層之間的節(jié)點(diǎn)數(shù)比值為，從節(jié)點(diǎn)數(shù)最少的隱藏層到輸出層，采用與從輸入層到節(jié)點(diǎn)數(shù)最少的隱藏層相對(duì)應(yīng)的完全對(duì)稱結(jié)構(gòu)。

圖3　隨機(jī)連接自編碼器模型

2.2.2激活函數(shù)

自編碼器中的每一個(gè)節(jié)點(diǎn)都會(huì)對(duì)輸入使用一個(gè)線性函數(shù)計(jì)算，激活函數(shù)將一個(gè)非線性函數(shù)應(yīng)用在線性函數(shù)的輸出結(jié)果上。實(shí)際上，在神經(jīng)網(wǎng)絡(luò)中應(yīng)用兩種不同的激活函數(shù)比應(yīng)用一種固定的激活函數(shù)效果相對(duì)要好，由于在神經(jīng)網(wǎng)絡(luò)不同層之間使用兩種不同的激活函數(shù)可以平衡不同激活函數(shù)之間的利與弊。

在自編碼器中，在最接近輸入層的隱藏層中和輸出層中使用Sigmoid激活函數(shù)。Sigmoid激活函數(shù)計(jì)算公式如式（1）所示：

在其余隱藏層中，使用整流線性單位（Rectified Linear Unit， ReLU）激活函數(shù)。ReLU激活函數(shù)計(jì)算公式如式（2）所示：

Sigmoid激活函數(shù)會(huì)引起梯度消失問(wèn)題，且它的計(jì)算代價(jià)高于ReLU激活函數(shù)。ReLU激活函數(shù)計(jì)算公式相對(duì)簡(jiǎn)單且計(jì)算代價(jià)相對(duì)較小，不存在梯度消失問(wèn)題，但ReLU激活函數(shù)觸發(fā)的神經(jīng)網(wǎng)絡(luò)權(quán)值更新可能導(dǎo)致神經(jīng)元失活，使其他神經(jīng)元處于停工狀態(tài)，神經(jīng)網(wǎng)絡(luò)權(quán)值更新停滯。為了解決兩個(gè)激活函數(shù)導(dǎo)致的問(wèn)題，在自編碼器中最接近輸入層的隱藏層中和輸出層中使用Sigmoid激活函數(shù)，在其余隱藏層中使用ReLU激活函數(shù)。這樣做的目的是：其一，若自編碼器處于最壞的情況，即使用ReLU激活函數(shù)的神經(jīng)節(jié)點(diǎn)全部失活，至少可以保證自編碼器兩端的神經(jīng)節(jié)點(diǎn)正常工作；其二，ReLU激活函數(shù)引起的問(wèn)題往往發(fā)生在梯度非常大的情況下，Sigmoid激活函數(shù)引起的梯度消失問(wèn)題有助于抑制ReLU激活函數(shù)所帶來(lái)的負(fù)面作用。

2.2.3權(quán)值更新

在自編碼器上更新權(quán)值使用了一種自適應(yīng)學(xué)習(xí)方法——均方根傳播（Root Mean Square propagation， RMSprop）。RMSprop自適應(yīng)學(xué)習(xí)方法是利用最新的梯度大小來(lái)標(biāo)準(zhǔn)化梯度的一種優(yōu)化器。

權(quán)值更新計(jì)算公式如式（3）（4）所示：

其中：w是在時(shí)刻的移動(dòng)平均梯度；是調(diào)節(jié)自適應(yīng)學(xué)習(xí)水平的參數(shù)，設(shè)置為0.9；g是在時(shí)刻的梯度；W是在時(shí)刻的權(quán)值；是學(xué)習(xí)率，初始值設(shè)置為0.02；是非常小的數(shù)值，其作用是避免零除。

2.3　算法詳細(xì)步驟

2.3.1訓(xùn)練基檢測(cè)器

在集成學(xué)習(xí)中，只有基檢測(cè)器具有較高的個(gè)體質(zhì)量，同時(shí)具有互補(bǔ)性，集成學(xué)習(xí)才能正常工作。實(shí)際上，由于預(yù)知基檢測(cè)器的適用區(qū)域不易實(shí)現(xiàn)，因此，側(cè)重于生成多樣化的基檢測(cè)器成為普遍做法，以實(shí)現(xiàn)模型學(xué)習(xí)不同的數(shù)據(jù)特征。在此，本文使用自編碼器作為基檢測(cè)器，變換其網(wǎng)絡(luò)體系結(jié)構(gòu)以產(chǎn)生差異性，實(shí)現(xiàn)基檢測(cè)器多樣化的目標(biāo)。

在訓(xùn)練基檢測(cè)器后，由于不同的基檢測(cè)器具有不相同的量綱，故應(yīng)對(duì)基檢測(cè)器輸出進(jìn)行歸一化處理，以提高收斂速度。歸一化處理具體過(guò)程：數(shù)據(jù)減去其均值，并除以方差，使處理后的數(shù)據(jù)滿足標(biāo)準(zhǔn)正態(tài)分布。歸一化公式如式（5）所示：

首先，將數(shù)據(jù)集（m+n）×d隨機(jī)劃分成兩部分：60%訓(xùn)練集X×d和40%測(cè)試集Y×d；其次，使用隨機(jī)連接自編碼器作為基檢測(cè)器構(gòu)建具備多樣性的集成學(xué)習(xí)模型，把X×d放入該集成學(xué)習(xí)模型訓(xùn)練；最后對(duì)集成學(xué)習(xí)中每個(gè)基檢測(cè)器輸出結(jié)果做歸一化處理，生成離群值矩陣。離群值矩陣只針對(duì)X×d中的數(shù)據(jù)，離群值矩陣如表2所示。

表2離群值矩陣

Tab.2　Outlier value matrix

本階段涉及的局部變量及函數(shù)：表示1×num_detector中每個(gè)基檢測(cè)器的列位置，split（）表示對(duì)數(shù)據(jù)集（m+n）×d進(jìn)行隨機(jī)劃分，init（）表示初始化基檢測(cè)器，train（）表示由X×d訓(xùn)練基檢測(cè)器。具體算法如下：

算法1 base_detector_training（（m+n）×d，1×num_detector）

1）=1

2）X×d，Y×dsplit（（m+n）×d）

3） while≤do

4） init（1×num_detector）

5） train（X×d，1×num_detector）

6）×num_detector.append（train（X×d，1×num_detector）

7）++

8） end

9） output（×num_detector）

2.3.2標(biāo)記離群程度

在絕大多數(shù)的實(shí)際應(yīng)用場(chǎng)景下，進(jìn)行離群點(diǎn)檢測(cè)所遭遇的核心挑戰(zhàn)是數(shù)據(jù)標(biāo)簽的缺失。這引起了無(wú)法有效地衡量基檢測(cè)器的預(yù)測(cè)結(jié)果與缺乏標(biāo)簽的數(shù)據(jù)離群程度之間差異的問(wèn)題。其解決思路只能從缺乏標(biāo)簽的正常數(shù)據(jù)和離群數(shù)據(jù)組成的混合數(shù)據(jù)出發(fā)。通常情況下，模型學(xué)習(xí)數(shù)據(jù)特征后，對(duì)數(shù)據(jù)輸出的離群值越大，該數(shù)據(jù)是離群點(diǎn)的可能性越大。因此，本文提出了一種從原始訓(xùn)練數(shù)據(jù)中生成偽離群值的方法，即定義了標(biāo)簽離群值這一概念：對(duì)于X×d中的某個(gè)數(shù)據(jù)，可從算法1輸出的離群值矩陣中獲取個(gè)不同的基檢測(cè)器對(duì)其計(jì)算所得的個(gè)不同的離群值，從該個(gè)離群值中取最大值作為衡量該數(shù)據(jù)的離群程度。

由于模型學(xué)習(xí)數(shù)據(jù)特征后所得到的輸出值通常包含離群值，因此，本文所提標(biāo)記離群程度的方法符合工業(yè)實(shí)際場(chǎng)景。

定義1 標(biāo)簽離群值。X×d中數(shù)據(jù)的標(biāo)簽離群值等于個(gè)基檢測(cè)器對(duì)該數(shù)據(jù)進(jìn)行計(jì)算輸出的最大值。其計(jì)算公式如式（6）所示：

根據(jù)式（6）計(jì)算得到X×d中所有數(shù)據(jù)的標(biāo)簽離群值矩陣，如表3所示。

表3標(biāo)簽離群值矩陣

Tab.3　Outlier label value matrix

本階段涉及的局部變量及函數(shù)：表示X×d中每個(gè)數(shù)據(jù)的行位置，表示臨時(shí)存儲(chǔ)變量，getMax（）表示使用式（6）獲取在×num_detector中第行的最大值。具體算法如下：

算法2 label_computing（×num_detector，X×d）

1）=1

2）0

3） while≤do

4）=getMax（×num_detector，）

5）×1.append（）

6）++

7） end

8） output（×1）

2.3.3構(gòu)建局部區(qū)域

在測(cè)試階段，EAOD算法首先要構(gòu)建局部區(qū)域，這是因?yàn)椋河捎跀?shù)據(jù)對(duì)象之間在數(shù)據(jù)集中分布彼此有關(guān)聯(lián)，EAOD算法根據(jù)基檢測(cè)器在測(cè)試數(shù)據(jù)的鄰近對(duì)象上的檢測(cè)能力來(lái)估計(jì)該基檢測(cè)器在上的檢測(cè)能力，因此，EAOD算法需要在局部區(qū)域上計(jì)算基檢測(cè)器的檢測(cè)能力。將算法2輸出的標(biāo)簽離群值劃分為多個(gè)簇，找到測(cè)試數(shù)據(jù)所屬的簇構(gòu)建局部區(qū)域。

定義2 鄰域簇Ψ。計(jì)算與周圍鄰點(diǎn)之間的歐氏距離，根據(jù)歐氏距離長(zhǎng)短得到的個(gè)最近鄰，由個(gè)最近鄰構(gòu)成的鄰域簇Ψ。如式（7）所示：

其中表示在歐氏距離上最接近的第個(gè)數(shù)據(jù)。

定義3 局部區(qū)域Ω。從Ψ中檢索出屬于X×d中的數(shù)據(jù)，這些數(shù)據(jù)構(gòu)成的局部區(qū)域Ω。如式（8）所示：

其中表示Ω中第個(gè)數(shù)據(jù)。

如圖4所示，通過(guò)-NN算法找到鄰近的個(gè)數(shù)據(jù)，存入鄰域簇Ψ中，再?gòu)泥徲虼?i>Ψ選擇出屬于X×d的數(shù)據(jù)存入Ω，進(jìn)而構(gòu)建出的局部區(qū)域，即Ω是Ψ的子集。

其中：值的取值影響Y×d中某一個(gè)數(shù)據(jù)的局部區(qū)域的建立，較小的值導(dǎo)致EAOD算法過(guò)多關(guān)注數(shù)據(jù)的局部關(guān)系，較大的值導(dǎo)致EAOD算法過(guò)多關(guān)注數(shù)據(jù)的全局關(guān)系。為了解決這兩個(gè)問(wèn)題，在實(shí)驗(yàn)中，發(fā)現(xiàn)將值設(shè)置為0.05（是X×d包含的數(shù)據(jù)總個(gè)數(shù)）取得了良好的效果。

圖4　數(shù)據(jù)對(duì)象的局部區(qū)域

本階段涉及的局部變量及函數(shù)：表示Y×d中每個(gè)數(shù)據(jù)的行位置，Ψ表示鄰域簇，getKPoints（）表示使用式（7）獲取最接近的個(gè)數(shù)據(jù)點(diǎn)，Ω表示局部區(qū)域，表示Y×d中所有數(shù)據(jù)的局部區(qū)域集合selectSubset（）表示使用式（8）獲取Ψ中屬于X×d的數(shù)據(jù)。具體算法如下：

算法3 local_area_constructing（X×d，Y×d）

1）=1

2）Ψ=［］

3）Ω=［］

4）=［］

5） while≤do

6）Ψ.append（getKPoints（））

7）Ω.append（selectSubset（Ψ，X×d））

8）.append（Ω）

9） end

10）output（）

2.3.4基檢測(cè)器選擇與組合

由算法3確定了測(cè)試點(diǎn)的局部區(qū)域Ω之后，在此局部區(qū)域上計(jì)算所有基檢測(cè)器的檢測(cè)能力，目的是為了選擇對(duì)檢測(cè)能力強(qiáng)的基檢測(cè)器進(jìn)行組合。

在算法2輸出的離群值矩陣×num_detector中，可獲取局部區(qū)域Ω中每個(gè)數(shù)據(jù)所對(duì)應(yīng)的個(gè)離群值，將每個(gè)數(shù)據(jù)對(duì)應(yīng)的個(gè)離群值存入矩陣×num_detector如式（9）所示：

在算法3輸出的標(biāo)簽離群值矩陣×1中，可獲取局部區(qū)域Ω中每個(gè)數(shù)據(jù)所對(duì)應(yīng)的1個(gè)標(biāo)簽離群值，將每個(gè)數(shù)據(jù)對(duì)應(yīng)的1個(gè)標(biāo)簽離群值存入矩陣×1。如式（10）所示：

余弦相似度可確定每個(gè)特征之間是否密切相關(guān)，故EAOD算法使用余弦相似度衡量基檢測(cè)器輸出值與標(biāo)簽離群值之間的差異，進(jìn)而推斷出基檢測(cè)器的檢測(cè)能力。

對(duì)于來(lái)說(shuō)，基檢測(cè)器的檢測(cè)能力δ正相關(guān)于其在上的輸出值與的標(biāo)簽離群值之間的余弦相似度，即余弦相似度越高的基檢測(cè)器檢測(cè)能力越強(qiáng)。如式（11）所示：

對(duì)于Ω中第個(gè)數(shù)據(jù)，根據(jù)式（9）～（11），計(jì)算在×num_detector中個(gè)離群值與在×num_detector中1個(gè)標(biāo)簽離群值之間的余弦相似度，即得到個(gè)δ；然后，對(duì)該個(gè)δ進(jìn)行降序排列，通過(guò)Top-個(gè)δ獲取對(duì)檢測(cè)能力強(qiáng)的個(gè)基檢測(cè)器。

同理，對(duì)于Ω中所有數(shù)據(jù)，共選擇出在局部區(qū)域Ω上（×）個(gè)檢測(cè)能力強(qiáng)的基檢測(cè)器，使用（×）個(gè)檢測(cè)能力強(qiáng)的基檢測(cè)器檢測(cè)，輸出（×）個(gè)離群值；最后，計(jì)算（×）個(gè)離群值的均值作為的最終離群值。

其中：降序排列個(gè)δ之后，前10%的δ有較高的相似度分值，因此=［/10］。

本階段涉及的局部變量及函數(shù)：searchOD（）表示檢索得到在×num_detector中個(gè)離群值，searchLabel（）表示檢索得到在×num_detector中1個(gè)標(biāo)簽離群值，computingCosine（）表示計(jì)算在×num_detector中個(gè)離群值與在×num_detector中1個(gè)標(biāo)簽離群值之間的余弦相似度，selecetTop（）表示檢索得到Top-個(gè)余弦相似度對(duì)應(yīng)的基檢測(cè)器，base_detector_training（）表示使用算法1在檢測(cè)能力強(qiáng)的基檢測(cè)器上檢測(cè)，average（）表示計(jì)算檢測(cè)能力強(qiáng)的基檢測(cè)器對(duì)的檢測(cè)結(jié)果的均值，該均值是判定最終的離群值。具體算法如下：

算法4 outlier_ predicating（Y×d，Ω，×1

×num_detector）

1）［］

2）［］

3）［］

4）［］

5）［］

6）［］

7） while≤do

8） while≤do

9）searchOD（，×num_detector）

10）searchLabel（，Q×1）

11）computingCosine（）

12）selecetTop（）

13） end

14）= base_detector_training（，）

15）=average（）

16）end

17）output（）

2.4　算法時(shí)間復(fù)雜度分析

設(shè)數(shù)據(jù)的數(shù)量和維度分別為和。算法1中，步驟1）～2）劃分?jǐn)?shù)據(jù)集，時(shí)間復(fù)雜度為（），步驟3）～8）遍歷基檢測(cè)器，由訓(xùn)練集訓(xùn)練基檢測(cè)器，時(shí)間復(fù)雜度為（），步驟9）為輸出訓(xùn)練值，時(shí)間復(fù)雜度為（）；算法2中，步驟1）～7）檢索獲取每個(gè)數(shù)據(jù)在基檢測(cè)器上的最大值，時(shí)間復(fù)雜度為（），步驟8）輸出檢索結(jié)果，時(shí)間復(fù)雜度為（）；算法3中，步驟1）～9）使用k-d tree為每個(gè)測(cè)試點(diǎn)構(gòu)建局部區(qū)域，其中用于距離計(jì)算的時(shí)間復(fù)雜度為（），用于根據(jù)距離長(zhǎng)短進(jìn)行排序的時(shí)間復(fù)雜度為（log），步驟10）輸出局部區(qū)域中數(shù)據(jù)，時(shí)間復(fù)雜度為（）；算法4中，步驟1）～16），遍歷測(cè)試集和局部區(qū)域中數(shù)據(jù)，找到在局部區(qū)域上檢測(cè)能力強(qiáng)的基檢測(cè)器，并使用這些基檢測(cè)器對(duì)測(cè)試集中數(shù)據(jù)進(jìn)行檢測(cè)，時(shí)間復(fù)雜度為（2），步驟17）輸出數(shù)據(jù)最終判定的離群值，時(shí)間復(fù)雜度為（）。

綜上可得EAOD算法的時(shí)間復(fù)雜度規(guī)模為（2）。

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

3.1　實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)的硬件環(huán)境是：處理器為Intel Xeon Gold 5117 CPU@ 2.00 GHz（2處理器），顯卡為Nvidia Tesla V100-PCIE-16 GB（共3塊），內(nèi)存（RAM）為256 GB。

實(shí)驗(yàn)的軟件環(huán)境是：操作系統(tǒng)環(huán)境為Microsoft Windows Server 2016 Standard，算法的實(shí)現(xiàn)環(huán)境為pycharm professional、python-3.6.2、tensorflow_gpu-1.14。

3.2　數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

表4總結(jié)了在實(shí)驗(yàn)中使用到的5個(gè)數(shù)據(jù)集。數(shù)據(jù)集選自O(shè)DDS（Outlier Detection DataSets）公開(kāi)數(shù)據(jù)集，分別是Cardio、Ionosphere、Mnist、Pendigits、Satimage-2。其中，大多數(shù)的數(shù)據(jù)被標(biāo)記為正常點(diǎn)，小部分的數(shù)據(jù)被標(biāo)記為離群點(diǎn)。ODDS提供了離群點(diǎn)檢測(cè)的標(biāo)準(zhǔn)數(shù)據(jù)集（http：//odds.cs.sto-nybrook.edu/）。

表4　實(shí)驗(yàn)中使用的ODDS公開(kāi)數(shù)據(jù)集

Cardio數(shù)據(jù)集是由專業(yè)醫(yī)生處理成的心電圖上的胎兒心率測(cè)量值，它屬于分類數(shù)據(jù)集，其中類別被分為3類：正常類、病理類、可疑類。在離群點(diǎn)檢測(cè)中，正常類被標(biāo)記成正常值類，病理類被標(biāo)記成離群值類，疑似類被丟棄；Ionosphere數(shù)據(jù)集是一個(gè)二分類數(shù)據(jù)集，原本該數(shù)據(jù)集維度是34，但其中有一個(gè)特征全是0值的屬性被丟棄，故總維度是33。其中，“bad”類作為離群值類，“good”類作為正常值類；原Mnist數(shù)據(jù)集是手寫(xiě)數(shù)字?jǐn)?shù)據(jù)集，訓(xùn)練集和測(cè)試集分別包含60 000個(gè)數(shù)據(jù)對(duì)象和10 000個(gè)數(shù)據(jù)對(duì)象?，F(xiàn)將原Mnist數(shù)據(jù)集轉(zhuǎn)化為離群點(diǎn)檢測(cè)數(shù)據(jù)集后，共包含7 603個(gè)數(shù)據(jù)對(duì)象。其中，零位數(shù)字類作為正常值類，從六位數(shù)字類中抽樣700張圖像作為離群值類，且從總特征隨機(jī)抽取100個(gè)特征；基于原始筆數(shù)字的Pendigits數(shù)據(jù)集是一個(gè)包含10個(gè)類和16個(gè)整數(shù)屬性的分類數(shù)據(jù)集，在該數(shù)據(jù)集中，所有類的頻率均相等。Satimage-2數(shù)據(jù)集是一個(gè)多類分類數(shù)據(jù)集，合并了訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)，從類別2中抽樣71個(gè)離群值，其他類別合并成一個(gè)離群類。

實(shí)驗(yàn)中所使用的全部數(shù)據(jù)集具有類別不平衡的特性。由于準(zhǔn)確率一般適用在平衡的數(shù)據(jù)上，因此，在使用類別不平衡的數(shù)據(jù)集的情況下，不適合使用準(zhǔn)確率作為評(píng)估指標(biāo)。使用接受者操作特征曲線下方的面積（Area Under receiver operating characteristic Curve， AUC）和平均精度（Average Precision， AP）對(duì)數(shù)據(jù)偏斜的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)評(píng)估是當(dāng)下的普遍做法。

根據(jù)真實(shí)標(biāo)簽和檢測(cè)結(jié)果，把樣本劃分成真正例（True Positive，）、假正例（False Positive，）、真反例（True Negative，）、假反例（False Negative，）四種類型。分類結(jié)果的混淆矩陣如表5所示。

表5　分類結(jié)果的混淆矩陣

接受者操作特征（Receiver Operating Characteristic， ROC）是一條曲線，其橫坐標(biāo)和縱坐標(biāo)分別是假正例率（False Postive Rate，）和真正例率（True Positive Rate，），AUC是ROC曲線與橫軸之間的面積。通常情況下，AUC分值越接近于1，算法的檢測(cè)性能越好。AUC計(jì)算過(guò)程如式（12）～（16）所示：

查準(zhǔn)率-查全率（Precision-Recall curve， P-R）曲線的橫坐標(biāo)和縱坐標(biāo)分別是查全率（Recall）和查準(zhǔn)率（Precision）。AP是在P-R曲線中，在每個(gè)閾值下計(jì)算得到的查準(zhǔn)率的加權(quán)平均值。AP計(jì)算過(guò)程如式（17）～（19）所示：

其中P和R分別表示在第個(gè)閾值處的查準(zhǔn)率和查全率。

3.3　實(shí)驗(yàn)設(shè)計(jì)

在實(shí)驗(yàn)中，對(duì)于每個(gè)數(shù)據(jù)集，60%的數(shù)據(jù)作為訓(xùn)練集，剩余的40%作為測(cè)試集。

在實(shí)驗(yàn)中，為了解決基檢測(cè)器因隱藏層壓縮程度過(guò)高而導(dǎo)致的數(shù)據(jù)無(wú)法重構(gòu)的問(wèn)題，將自編碼器中隱藏層節(jié)點(diǎn)數(shù)最小值設(shè)置為3，若按計(jì)算，若隱藏層中某一層節(jié)點(diǎn)數(shù)小于3，則該層節(jié)點(diǎn)數(shù)設(shè)置為3。為了確保本實(shí)驗(yàn)的結(jié)果具有穩(wěn)定性，現(xiàn)對(duì)EAOD算法執(zhí)行10次，對(duì)10次產(chǎn)生的結(jié)果計(jì)算均值作為最終的結(jié)果。集成學(xué)習(xí)中基檢測(cè)器的個(gè)數(shù)設(shè)置為50、層數(shù)設(shè)置為9、迭代次數(shù)設(shè)置為300、某一層節(jié)點(diǎn)數(shù)與它上一層的節(jié)點(diǎn)數(shù)比值設(shè)為0.5。

在實(shí)驗(yàn)中，為了驗(yàn)證EAOD算法的有效性，將其與其他離群點(diǎn)檢測(cè)算法在各數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)。具體來(lái)說(shuō)，該實(shí)驗(yàn)使用了HBOS、主成分分析（Principal Component Analysis， PCA）［20］、LOF、孤立森林（Isolation Forest， IForest）［21］、自編碼器（AutoEncoder， AE）［22］、特征裝袋（Feature Bagging， FB）［23］離群點(diǎn)檢測(cè)算法進(jìn)行了比較。對(duì)于LOF算法，將其最近鄰個(gè)數(shù)從2～100選取20次，選取其最佳檢測(cè)結(jié)果；對(duì)于IForest算法，將采樣大小設(shè)置為256，將樹(shù)的數(shù)目設(shè)置為100；對(duì)于AE算法，其參數(shù)設(shè)置與EAOD算法中自編碼器參數(shù)設(shè)置保持一致；對(duì)于FB算法，其基檢測(cè)器設(shè)置與EAOD算法中基檢測(cè)器設(shè)置保持一致。

在實(shí)驗(yàn)中，為了探究EAOD算法對(duì)起決定性參數(shù)的敏感程度，對(duì)集成學(xué)習(xí)中基檢測(cè)器個(gè)數(shù)、層數(shù)、迭代次數(shù)這3個(gè)參數(shù)進(jìn)行了敏感性實(shí)驗(yàn)分析。

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

表6展示了各個(gè)算法在5個(gè)離群點(diǎn)檢測(cè)公開(kāi)數(shù)據(jù)集上的AUC和AP的對(duì)比分值。

表6　各算法AUC分值和AP分值對(duì)比

如表6的AUC分值所示，EAOD與HBOS、IForest、LOF、PCA、AE、FB在AUC分值上相比：對(duì)于Cardio數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了15.06個(gè)百分點(diǎn)、1.88個(gè)百分點(diǎn)、30.84個(gè)百分點(diǎn)、2.46個(gè)百分點(diǎn)、8.08個(gè)百分點(diǎn)、6.89個(gè)百分點(diǎn)；對(duì)于Ionosphere數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了30.44個(gè)百分點(diǎn)、6.39個(gè)百分點(diǎn)、2.89個(gè)百分點(diǎn)、13.84個(gè)百分點(diǎn)、10.27個(gè)百分點(diǎn)、10.21個(gè)百分點(diǎn)；對(duì)于Mnist數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了33.11個(gè)百分點(diǎn)、11.15個(gè)百分點(diǎn)、18.63個(gè)百分點(diǎn)、6.52個(gè)百分點(diǎn)、8.9個(gè)百分點(diǎn)、8.98個(gè)百分點(diǎn)；對(duì)于Pendigits數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了3.43個(gè)百分點(diǎn)、0.91個(gè)百分點(diǎn)、44.93個(gè)百分點(diǎn)、9.97個(gè)百分點(diǎn)、8.47個(gè)百分點(diǎn)、5.45個(gè)百分點(diǎn)；對(duì)于Satimage-2數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了4.19個(gè)百分點(diǎn)、0.55個(gè)百分點(diǎn)、52.43個(gè)百分點(diǎn)、3.23個(gè)百分點(diǎn)、10.35個(gè)百分點(diǎn)、8.83個(gè)百分點(diǎn)。

如表6的AP分值所示，EAOD與HBOS、IForest、LOF、PCA、AE、FB在AP分值上相比：對(duì)于Cardio數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了26.87個(gè)百分點(diǎn)、12.91個(gè)百分點(diǎn)、47.66個(gè)百分點(diǎn)、11.02個(gè)百分點(diǎn)、9.17個(gè)百分點(diǎn)、8.04個(gè)百分點(diǎn)；對(duì)于Ionosphere數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了41.49個(gè)百分點(diǎn)、3.72個(gè)百分點(diǎn)、0.18個(gè)百分點(diǎn)、11.48個(gè)百分點(diǎn)、8.15個(gè)百分點(diǎn)、12.41個(gè)百分點(diǎn)；對(duì)于Mnist數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了35.69個(gè)百分點(diǎn)、21.29個(gè)百分點(diǎn)、19.32個(gè)百分點(diǎn)、11.62個(gè)百分點(diǎn)、11.39個(gè)百分點(diǎn)、17.79個(gè)百分點(diǎn)；對(duì)于Pendigits數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了5.88個(gè)百分點(diǎn)、3.39個(gè)百分點(diǎn)、20.6個(gè)百分點(diǎn)、8.52個(gè)百分點(diǎn)、8.27個(gè)百分點(diǎn)、7.37個(gè)百分點(diǎn)；對(duì)于Satimage-2數(shù)據(jù)集，樣本檢測(cè)的精度分別提升了13個(gè)百分點(diǎn)、1.54個(gè)百分點(diǎn)、79.41個(gè)百分點(diǎn)、5.33個(gè)百分點(diǎn)、6.01個(gè)百分點(diǎn)、8.63個(gè)百分點(diǎn)。

表6表明，EAOD算法在5個(gè)數(shù)據(jù)集上的AUC分值和AP分值均高于HBOS、IForest、LOF、PCA、AE和FB算法。這是因?yàn)镋AOD算法具備權(quán)衡偏差和方差的功能：EAOD算法通過(guò)隨機(jī)連接自編碼器使基檢測(cè)器具備多樣性，在選取標(biāo)簽離群值階段間接權(quán)衡偏差和方差，對(duì)檢測(cè)能力強(qiáng)的多個(gè)不同的基檢測(cè)器的輸出結(jié)果計(jì)算均值，再一次權(quán)衡偏差和方差，進(jìn)而減小了泛化誤差，提高了檢測(cè)性能。

如圖5所示，HBOS、IForest、LOF、PCA和AE算法也具有較短的時(shí)間耗費(fèi)，但從AUC和AP指標(biāo)來(lái)看，它們沒(méi)有較好的檢測(cè)性能。FB算法檢測(cè)時(shí)間耗費(fèi)較長(zhǎng)，是因?yàn)槠鋵?duì)特征選取進(jìn)行了較為復(fù)雜的特征統(tǒng)計(jì)計(jì)算，且缺乏對(duì)基檢測(cè)器進(jìn)行選擇性統(tǒng)計(jì)組合。EAOD算法對(duì)5種數(shù)據(jù)集均具有較為合理的檢測(cè)時(shí)間耗費(fèi)，以檢測(cè)一般規(guī)模的數(shù)據(jù)集最短耗時(shí)6.8 s來(lái)看，已基本滿足實(shí)際使用時(shí)的一般情況。因此綜合來(lái)看，EAOD算法在具有穩(wěn)定較高的檢測(cè)性能的前提下，也具有較為合理的檢測(cè)時(shí)間成本。

圖5　各算法在5種數(shù)據(jù)集上的時(shí)間耗費(fèi)對(duì)比

實(shí)驗(yàn)結(jié)果表明，EAOD算法在無(wú)監(jiān)督學(xué)習(xí)下，對(duì)真實(shí)數(shù)據(jù)集具有較好的檢測(cè)性能，同時(shí)具有較為合理的檢測(cè)時(shí)間成本。因此，EAOD算法是有效可行的。

3.5　參數(shù)敏感性分析

以Cardio數(shù)據(jù)集為例，通過(guò)實(shí)驗(yàn)分析了EAOD算法中基檢測(cè)器個(gè)數(shù)、層數(shù)以及迭代次數(shù)等3個(gè)關(guān)鍵參數(shù)變動(dòng)對(duì)AUC和AP分值的影響。

基檢測(cè)器個(gè)數(shù)分別設(shè)置為25、50、75、100、125和150。實(shí)驗(yàn)結(jié)果由圖6可知，基檢測(cè)器個(gè)數(shù)的變動(dòng)對(duì)于AUC分值沒(méi)有明顯影響。對(duì)于AP分值，基檢測(cè)器個(gè)數(shù)由25增加到50，再?gòu)?0增加到100的過(guò)程中，AP分值先上升后下降；基檢測(cè)器個(gè)數(shù)由100增加到150過(guò)程中，AP分值無(wú)顯著變化；AP分值在基檢測(cè)器個(gè)數(shù)等于50時(shí)達(dá)到最大值。

圖6　基檢測(cè)器個(gè)數(shù)變動(dòng)分析

基檢測(cè)器層數(shù)分別設(shè)置為3、5、7和9。實(shí)驗(yàn)結(jié)果由圖7可知：基檢測(cè)器層數(shù)的變動(dòng)對(duì)于AUC分值沒(méi)有明顯影響。對(duì)于AP分值，基檢測(cè)器層數(shù)由3增加到5時(shí)，AP分值顯著下降；基檢測(cè)器層數(shù)由5增加到9的過(guò)程中，AP分值持續(xù)上升；在基檢測(cè)器層數(shù)等于9時(shí)，AP分值最大。

圖7　基檢測(cè)器層數(shù)變動(dòng)分析

基檢測(cè)器迭代次數(shù)分別設(shè)置為50、100、150、200、250和300。實(shí)驗(yàn)結(jié)果由圖8可知，基檢測(cè)器迭代次數(shù)的變動(dòng)對(duì)于AUC分值沒(méi)有明顯影響。對(duì)于AP分值來(lái)說(shuō)，基檢測(cè)器迭代次數(shù)由50增加到100時(shí)，AP分值下降；基檢測(cè)器迭代次數(shù)由100增加到300的過(guò)程中，AP分值持續(xù)上升；在基檢測(cè)器迭代次數(shù)等于300時(shí)，AP分值取得最大值。

圖8　基檢測(cè)器迭代次數(shù)變動(dòng)分析

由于AUC與AP兩種評(píng)估指標(biāo)之間在統(tǒng)計(jì)學(xué)中存在明顯差異［24］，所以EAOD算法的重要參數(shù)變動(dòng)在AUC分值和AP分值表現(xiàn)上存在顯著差異。

4 結(jié)語(yǔ)

基于自編碼器的離群點(diǎn)檢測(cè)算法在中小規(guī)模數(shù)據(jù)集上易發(fā)生過(guò)擬合現(xiàn)象和傳統(tǒng)的基于集成學(xué)習(xí)的離群點(diǎn)檢測(cè)算法未對(duì)基檢測(cè)器進(jìn)行優(yōu)化選擇均是導(dǎo)致檢測(cè)精度低的主要因素。本文提出一種基于自編碼器與集成學(xué)習(xí)的EAOD離群點(diǎn)檢測(cè)算法來(lái)解決檢測(cè)精度低的問(wèn)題。該算法使用隨機(jī)連接自編碼器作為基檢測(cè)器在數(shù)據(jù)對(duì)象的局部區(qū)域中選擇一組檢測(cè)能力強(qiáng)的基檢測(cè)器進(jìn)行組合，組合后的對(duì)象離群值作為算法最終的判定結(jié)果。通過(guò)對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)在無(wú)監(jiān)督學(xué)習(xí)下所提算法優(yōu)于傳統(tǒng)機(jī)器學(xué)習(xí)算法。

EAOD算法構(gòu)建局部區(qū)域依賴計(jì)算歐氏距離來(lái)尋找最近鄰，存在一定計(jì)算量，因此以后的研究應(yīng)注重在保證檢測(cè)精度的前提下嘗試聚類等其他方法構(gòu)建局部區(qū)域。另外，EAOD算法可以考慮異構(gòu)算法作為其基檢測(cè)器，以更加多樣性地實(shí)現(xiàn)集成學(xué)習(xí)。

[1] PANG G S， CAO L B， AGGARWAL C. Deep learning for anomaly detection： challenges， methods， and opportunities［C］// Proceedings of the 14th ACM International Conference on Web Search and Data Mining. New York： ACM， 2021： 1127-1130.

[2] PANG G S， LI J D， VAN DEN HENGEL A， et al. Anomaly and Novelty Detection， Explanation， and Accommodation （ANDEA）［C］// Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York： ACM， 2021： 4145-4146.

[3] THUDUMU S， BRANCH P， JIN J， et al. A comprehensive survey of anomaly detection techniques for high dimensional big data［J］. Journal of Big Data， 2020， 7： No.42.

[4] QIAN J， ZENG G F， CAI Z P， et al. A survey on anomaly detection techniques in large-scale KPI data［C］// Proceedings of the 9th International Conference on Computer Engineering and Networks， AISC 1143. Singapore： Springer， 2021： 767-776.

[5] BERGMANN P， BATZNER K， FAUSER M， et al. The MVTec anomaly detection dataset： a comprehensive real-world dataset for unsupervised anomaly detection［J］. International Journal of Computer Vision， 2021， 129（4）： 1038-1059.

[6] 梅林，張鳳荔，高強(qiáng). 離群點(diǎn)檢測(cè)技術(shù)綜述［J］. 計(jì)算機(jī)應(yīng)用研究， 2020， 37（12）： 3521-3527.（MEI L， ZHANG F L， GAO Q. Overview of outlier detection technology［J］. Application Research of Computers， 2020， 37（12）： 3521-3527.）

[7] PANG G S， SHEN C H， CAO L B， et al. Deep learning for anomaly detection： a review［J］. ACM Computing Surveys， 2022， 54（2）： No.38.

[8] CHEN W Q， WANG Z L， ZHONG Y， et al. ADSIM： network anomaly detection via similarity-aware heterogeneous ensemble learning［C］// Proceedings of the 2021 IFIP/IEEE International Symposium on Integrated Network Management. Piscataway： IEEE， 2021： 608-612.

[9] CRUZ R M O， SABOURIN R， CAVALCANTI G D C. Dynamic classifier selection： recent advances and perspectives［J］. Information Fusion， 2018， 41： 195-216.

[10] CRUZ R M O， SABOURIN R， CAVALCANTI G D C. META-DES.Oracle： meta-learning and feature selection for dynamic ensemble selection［J］. Information Fusion， 2017， 38： 84-103.

[11] GOLDSTEIN M， DENGEL A. Histogram-Based Outlier Score （HBOS）： a fast unsupervised anomaly detection algorithm［EB/OL］. ［2021-03-22］.https：//www.goldiges.de/publications/HBOS-KI-2012.pdf.

[12] WANG X C， JIANG H C， YANG B Q. A k-nearest neighbor medoid-based outlier detection algorithm［C］// Proceedings of the 2021 International Conference on Communications， Information System and Computer Engineering. Piscataway： IEEE， 2021： 601-605.

[13] 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. New York： ACM， 2000： 93-104.

[14] FONG S， LI T， HAN D， et al. Lightweight classifier-based outlier detection algorithms from multivariate data stream［M］// FONG S J， MILLHAM R C. Bio-inspired Algorithms for Data Streaming and Visualization， Big Data Management， and Fog Computing， STNIC. Singapore： Springer， 2021： 97-125.

[15] 杜旭升，于炯，葉樂(lè)樂(lè)，等. 基于圖上隨機(jī)游走的離群點(diǎn)檢測(cè)算法［J］. 計(jì)算機(jī)應(yīng)用， 2020， 40（5）： 1322-1328.（DU X S， YU J， YE L L， et al. Outlier detection algorithm based on the graph random walk［J］. Journal of Computer Applications， 2020， 40（5）： 1322-1328.）

[16] LüBBERING M， GEBAUER M， RAMAMURTHY R， et al. Supervised autoencoder variants for end to end anomaly detection［C］// Proceedings of the 2021 International Conference on Pattern Recognition， LNCS 12662. Cham： Springer， 2021： 566-581.

[17] SARVARI H， DOMENICONI C， PRENKAJ B， et al. Unsupervised boosting-based autoencoder ensembles for outlier detection［C］// Proceedings of the 2021 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 12712. Cham： Springer， 2021： 91-103.

[18] BHATIA R， SHARMA R， GULERIA A. Anomaly detection systems using IP flows： a review［M］// BAREDAR P V， TANGELLAPALLI S， SOLANKI C S. Advances in Clean Energy Technologies， SPE. Singapore： Springer， 2021： 1035-1049.

[19] AVCI B， BODUROGLU A. Contributions of ensemble perception to outlier representation precision［J］. Attention， Perception， & Psychophysics， 2021， 83（3）： 1141-1151.

[20] AHSAN M， MASHURI M， KUSWANTO H， et al. Outlier detection using PCA mix based2control chart for continuous and categorical data［J］. Communications in Statistics-Simulation and Computation， 2021， 50（5）： 1496-1523.

[21] LIU F T， TING K M， ZHOU Z H. Isolation forest［C］// Proceedings of the 8th IEEE International Conference on Data Mining. Piscataway： IEEE， 2008： 413-422.

[22] OOSTERMAN D T， LANGENKAMP W H， BERGEN E L. Customs risk assessment based on unsupervised anomaly detection using autoencoders［C］// Proceedings of the 2021 SAI Intelligent Systems Conference， LNNS 294. Cham： Springer， 2022： 668-681.

[23] LAZAREVIC A， KUMAR V. Feature bagging for outlier detection［C］// Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. New York： ACM， 2005： 157-166.

[24] BELHADI A， DJENOURI Y， LIN J C W， et al. Trajectory outlier detection： algorithms， taxonomies， evaluation， and open challenges［J］. ACM Transactions on Management Information Systems， 2020， 11（3）： No.16.

GUO Yiyang，born in 1996， M. S. candidate. His research interests include machine learning， data mining.

YU Jiong，born in 1964， Ph. D.， professor. His research interests include distributed computing， machine learning， data mining.

DU Xusheng， born in 1995， Ph. D. candidate. His research interests include machine learning， data mining.

YANG Shaozhi，born in 1995， M. S. candidate. His research interests include machine learning， data mining.

CAO Ming，born in 1996， M. S. candidate. Her research interests include machine learning， data mining.

Outlier detection algorithm based on autoencoder and ensemble learning

GUO Yiyang1， YU Jiong1，2*， DU Xusheng1， YANG Shaozhi1， CAO Ming3

（1，，830046，；2，，830091，；3，，266100，）

The outlier detection algorithm based on autoencoder is easy to over-fit on small- and medium-sized datasets， and the traditional outlier detection algorithm based on ensemble learning does not optimize and select the base detectors， resulting in low detection accuracy. Aiming at the above problems， an Ensemble learning and Autoencoder-based Outlier Detection （EAOD） algorithm was proposed. Firstly， the outlier values and outlier label values of the data objects were obtained by randomly changing the connection structure of the autoencoder generate different base detectors. Secondly， local region around the object was constructed according to the Euclidean distance between the data objects calculated by the nearest neighbor algorithm. Finally， based on the similarity between the outlier values and the outlier label values， the base detectors with strong detection ability in the region were selected and combined together， and the object outlier value after combination was used as the final outlier value judged by EAOD algorithm. In the experiments， compared with the AutoEncoder （AE） algorithm， the proposed algorithm has the Area Under receiver operating characteristic Curve （AUC） and Average Precision （AP） scores increased by 8.08 percentage points and 9.17 percentage points respectively on Cardio dataset； compared with the Feature Bagging （FB） ensemble learning algorithm， the proposed algorithm has the detection time cost reduced by 21.33% on Mnist dataset. Experimental results show that the proposed algorithm has good detection performance and real-time performance under unsupervised learning.

outlier detection; ensemble learning; AutoEncoder (AE); base detector; unsupervised learning

This work is partially supported by National Natural Science Foundation of China （61862060， 61462079， 61562086， 61562078）.

TP311.1

A

1001-9081（2022）07-2078-10

10.11772/j.issn.1001-9081.2021050743

2021?05?10；

2021?09?08；

2021?09?15。

國(guó)家自然科學(xué)基金資助項(xiàng)目（61862060， 61462079， 61562086， 61562078）。

郭一陽(yáng)（1996—），男，山東滕州人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘； 于炯（1964—），男，北京人，教授，博士生導(dǎo)師，博士，主要研究方向：分布式計(jì)算、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘； 杜旭升（1995—），男，甘肅慶陽(yáng)人，博士研究生，CCF會(huì)員，主要研究方向：機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘； 楊少智（1995—），男，安徽鳳陽(yáng)人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘； 曹銘（1996—），女，山東菏澤人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘。