吳遠(yuǎn)超，范 磊

（上海交通大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，上海 200240）

0 引 言

離群點(diǎn)檢測(cè)是數(shù)據(jù)挖掘的重要一部分，是指從大量事物中發(fā)現(xiàn)少量與多數(shù)事物具有明顯區(qū)別的異常個(gè)體的過程[1]。離群點(diǎn)理論應(yīng)用廣泛，如信用卡欺詐檢測(cè)、入侵檢測(cè)、故障檢測(cè)、災(zāi)害預(yù)測(cè)、公共衛(wèi)生中的異常疾病的爆發(fā)、恐怖活動(dòng)防范以及氣象預(yù)報(bào)等。

在高維度場(chǎng)景下，傳統(tǒng)的離群點(diǎn)檢測(cè)算法效果大多不甚理想。這是因?yàn)槠胀ǖ碾x群點(diǎn)檢測(cè)方法大多是基于數(shù)據(jù)之間的相似度和距離來挖掘離群點(diǎn)。而在高維空間數(shù)據(jù)變得稀疏，數(shù)據(jù)點(diǎn)之間的距離及密度不再具有直觀的意義，因此常規(guī)算法對(duì)高維離群點(diǎn)的檢測(cè)不再有效或效率較低[2]。

Pang等[3]提出了適合于高維空間的CINFO方法，通過將子空間搜索和離群點(diǎn)評(píng)分方法關(guān)聯(lián)起來，提高了檢測(cè)精度。本文對(duì)該方法進(jìn)行改進(jìn)，引入擴(kuò)展的孤立森林算法（Extended Isolation Forest，EIF）[4]，提出了EIF-CINFO方法，在保持原有檢測(cè)精度的情況下，提高了效率。

1 相關(guān)算法研究

高維數(shù)據(jù)常包含大量不相關(guān)的特征，這些噪聲特征可以將離群點(diǎn)偽裝成正常對(duì)象。因此，對(duì)高維數(shù)據(jù)而言，發(fā)現(xiàn)有意義的離群點(diǎn)變得十分復(fù)雜和不明顯。目前，已有一些針對(duì)特定場(chǎng)景下的離群點(diǎn)檢測(cè)方法，但在效率和精度上仍需改進(jìn)。

1.1 經(jīng)典高維度離群點(diǎn)檢測(cè)算法的不足

在現(xiàn)有的高維度離群點(diǎn)檢測(cè)算法中，基于子空間/特征選擇的方法[5-7]是主要的解決辦法。他們尋找相關(guān)的特征子集，在相關(guān)的特征子集上應(yīng)用離群點(diǎn)檢測(cè)方法，以緩解由不相關(guān)的特征造成的負(fù)面影響。然而，這些方法往往將子空間搜索和后續(xù)的離群點(diǎn)評(píng)分方法分離開來，因此會(huì)保留與得分無關(guān)的特征，降低了檢測(cè)性能。

1.2 CINFO方法中的孤立森林算法及其不足

CINFO方法針對(duì)經(jīng)典高維度離群點(diǎn)檢測(cè)算法的不足，通過將離群點(diǎn)評(píng)分和子空間搜索關(guān)聯(lián)起來相互優(yōu)化，提高了檢測(cè)效果。孤立森林（iForest）[8]是CINFO中的離群點(diǎn)評(píng)分算法，主要思想是對(duì)一個(gè)數(shù)據(jù)集構(gòu)成的屬性空間，隨機(jī)選定一個(gè)特征進(jìn)行空間分割得到兩個(gè)子空間。之后繼續(xù)在剩下的特征里隨機(jī)選定一個(gè)特征，對(duì)每個(gè)子空間切分，直至每個(gè)子空間只包含一種數(shù)據(jù)點(diǎn)或者樹的深度達(dá)到設(shè)定的最大值。

具體過程如下：對(duì)于大小為n、維度為m的數(shù)據(jù)集D，先通過隨機(jī)抽樣獲得一個(gè)數(shù)據(jù)子集Di={d1,d2,…,ds}；之后隨機(jī)選擇一個(gè)特征A，在其最小值和最大值的范圍內(nèi)隨機(jī)獲得一個(gè)切割值pa；根據(jù)pa對(duì)Di中的每個(gè)數(shù)據(jù)實(shí)例dj，按照其特征A的值di(A)進(jìn)行劃分，將Di中dj(A)＜pa的部分歸到結(jié)點(diǎn)的左邊，其余部分歸到節(jié)點(diǎn)的右邊，從而得到兩個(gè)子樹的數(shù)據(jù)集。按此方式分別在左右兩邊的數(shù)據(jù)集上重復(fù)構(gòu)造左右子樹，直到達(dá)到終止條件。終止條件如下：（1）訓(xùn)練數(shù)據(jù)中只包含一個(gè)樣本或只包含相同的樣本；（2）樹的高度達(dá)到限定高度。最后重復(fù)上述過程，構(gòu)造出t棵iTree得到iForest。

因?yàn)殡x群點(diǎn)一般距離正常點(diǎn)較遠(yuǎn)，所以能被更好地區(qū)分開。在樹上的體現(xiàn)是離群點(diǎn)距離iTree的根結(jié)點(diǎn)較近，因此可以通過統(tǒng)計(jì)不同iTree下數(shù)據(jù)點(diǎn)d的平均路徑長(zhǎng)度計(jì)算數(shù)據(jù)點(diǎn)的離群值。

iForest的缺點(diǎn)是不適用于特別高維的數(shù)據(jù)。由于每次切割數(shù)據(jù)空間都只使用了一個(gè)維度，建完樹后仍然有大量的維度信息沒有被利用，導(dǎo)致在高維空間下算法可靠性不高。另外，高維空間還可能存在大量噪音維度或不相關(guān)維度，影響分割的效果。本文針對(duì)iForest對(duì)CINFO方法進(jìn)行了改進(jìn)。

2 EIF-CINFO方案設(shè)計(jì)

在CINFO中，iForest只考慮了部分維度信息，因此對(duì)后續(xù)降維影響較大。而EIF-CINFO中的EIF采用隨機(jī)超平面的隔離機(jī)制，考慮了所有特征，有利于后續(xù)的特征降維。

EIF-CINFO方案過程如下：對(duì)原始數(shù)據(jù)集進(jìn)行離群點(diǎn)打分，之后設(shè)定一個(gè)閾值得到初步的離群點(diǎn)集合，再通過lasso回歸函數(shù)，剔除與離群點(diǎn)集合無關(guān)的特征；將得到剔除無關(guān)特征后的數(shù)據(jù)集再進(jìn)行離群點(diǎn)打分；一直重復(fù)上述步驟，直到lasso回歸的損失函數(shù)不再減小。具體流程如圖1所示。

圖1 方案流程

2.1 離群點(diǎn)打分

孤立森林不能很好地適應(yīng)高維度數(shù)據(jù)場(chǎng)景，會(huì)導(dǎo)致后續(xù)lasso回歸特征降維速度緩慢。為此，通過引入EIF來改正這一缺點(diǎn)。

孤立森林通過創(chuàng)建與某一軸平行的超平面來切割數(shù)據(jù)屬性空間。在高維度空間下，iForest切割數(shù)據(jù)空間使用的維度遠(yuǎn)小于總屬性維度，因此有很多維度信息并沒有被使用上。EIF通過允許在數(shù)據(jù)空間中隨機(jī)產(chǎn)生一個(gè)超平面，在切割平面的過程中兼顧到了所有維度信息。

EIF創(chuàng)建用來分割的超平面的方式由式（1）確定：

圖2 EIF單次分割

EIF的一個(gè)切割超平面在二叉樹上表現(xiàn)為一個(gè)節(jié)點(diǎn)建立左右子樹的功能。如果滿足上述不等式，則點(diǎn)x被傳遞到樹的左分支；否則，它將被傳至右分支。如圖2所示，分割中的x1被分到了左分支，x2被分到了右分支。

圖3是iForest中的一棵樹和EIF中一棵樹分割數(shù)據(jù)空間的對(duì)比圖[4]。

從圖3可以明顯看出，iForest中隔離超平面平行于坐標(biāo)軸，EIF中隔離超平面的方向是隨機(jī)的。

圖3 iForest和EIF中的一棵樹分割數(shù)據(jù)空間對(duì)比

2.2 設(shè)定閾值獲得離群點(diǎn)候選集

得到離群點(diǎn)評(píng)分后，設(shè)定閾值。超過閾值，則暫時(shí)認(rèn)定為離群點(diǎn)；反之，則暫時(shí)認(rèn)為是正常點(diǎn)。利用Cantelli不等式[9]設(shè)定的閾值，可以將誤報(bào)率控制在一定范圍內(nèi)，具體如下。

給出異常值向量y∈RN，y中大的數(shù)表示較高的離群度，μ和δ2是y的期望值和方差。那么，離群候選集R定義如下：

假設(shè)y具有期望值μ和方差δ2。令yi∈Y，離群閾值函數(shù)η(yi,a)=yi-μ-aδ，然后這個(gè)閾值設(shè)定導(dǎo)致的誤報(bào)率上限便為

證明過程如下：

式（3）為Cantelli不等式，因?yàn)榇蟮闹当硎倦x群值，這個(gè)不等式意味著當(dāng)將閾值定義為μ+aδ時(shí)，即令α=aδ，則yi大于等于μ+aδ的概率小于等于，那么可能錯(cuò)誤地將正常對(duì)象識(shí)別為離群值的概率最大為

Cantelli不等式是單邊的切比雪夫不等式。與切比雪夫不等式類似，它不對(duì)特定概率分布進(jìn)行假設(shè)，適用于具有統(tǒng)計(jì)平均值和方差的概率分布。

2.3 剔除無關(guān)特征

在得到初步離群點(diǎn)集合后，將初步離群點(diǎn)作為被預(yù)測(cè)變量，數(shù)據(jù)集中的特征作為預(yù)測(cè)變量，進(jìn)行l(wèi)asso回歸，以剔除與初步離群點(diǎn)集合無關(guān)的特征。R是離群閾值階段新創(chuàng)建的只包含初步離群點(diǎn)的數(shù)據(jù)集，L為被初步識(shí)別為離群點(diǎn)的數(shù)量，然后進(jìn)行如下的稀疏回歸學(xué)習(xí)：

其中ω是系數(shù)矢量，λ是正則化參數(shù)。式（4）獲得最小二乘模型的收縮解，得到與離群點(diǎn)集合R不相關(guān)的特征。然后，將之前數(shù)據(jù)集中的這些無關(guān)特征剔除，獲得新的數(shù)據(jù)集S：

2.4 算法描述

輸入：X為數(shù)據(jù)集，a為離群值閾值參數(shù)

輸出：M為對(duì)象異常值得分排序

y0←Φ(X)得到初始離群集合

mse0=1，t=0初始損失函數(shù)為1，t為迭代系數(shù)

repeat

t←t+1

Rt←η(yt-1,a)用閾值函數(shù)得到離群點(diǎn)候選集

ωt，mset←ψ(Rt,λt)進(jìn)行一次 lasso 降維

St←{x·i|ωit≠0,1≤i≤D|}剔除相關(guān)系數(shù)為0的特征，得到新集合

yt←φ(St)得到新的離群點(diǎn)打分

until mset＞mset-1直到損失函數(shù)不再下降

M←SortXw.r.t score對(duì)得分進(jìn)行排序

return M

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)標(biāo)準(zhǔn)

本節(jié)通過實(shí)驗(yàn)對(duì)CINFO和EIF-CINFO的有效性和性能進(jìn)行對(duì)比分析。實(shí)驗(yàn)分為兩部分，第一部分使用加州大學(xué)歐文分校機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Isolet和APS數(shù)據(jù)集，用于測(cè)試算法效果。第二部分為某公司實(shí)際采集的手機(jī)設(shè)備特征數(shù)據(jù)（Device），檢測(cè)算法在該數(shù)據(jù)集下的實(shí)際效果。

Isolet數(shù)據(jù)集為隔離字母語(yǔ)音識(shí)別，150名受試者兩次說出字母表中每個(gè)字母的名字，特征表里包含光譜系數(shù)、輪廓特征、聲吶特征、前音特征和后音特征等，數(shù)據(jù)集數(shù)據(jù)量為730個(gè)，特征維度為617。APS數(shù)據(jù)集為Scania卡車APS（空氣壓力系統(tǒng)）故障數(shù)據(jù)集。數(shù)據(jù)集的正類由APS系統(tǒng)特定組件的組件故障組成，負(fù)類由與APS無關(guān)的部件故障組成，由專家選擇組成。其中數(shù)據(jù)量為3 000個(gè)，特征維度為170。

在用Isolet和APS數(shù)據(jù)集進(jìn)行測(cè)試后，用實(shí)際的手機(jī)設(shè)備特征信息數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)集有兩類數(shù)據(jù)：描述設(shè)備固有屬性的靜態(tài)數(shù)據(jù)，如內(nèi)存大??；隨著時(shí)間變化的動(dòng)態(tài)數(shù)據(jù)，如地理位置信息。該數(shù)據(jù)集中將模擬器標(biāo)記為異常用戶，數(shù)據(jù)集數(shù)據(jù)量為3 200個(gè)，特征維度為245。

表1 數(shù)據(jù)集詳細(xì)情況

為了評(píng)估算法的性能，實(shí)驗(yàn)以ROC曲線和曲線下面積AUC為效果評(píng)價(jià)指標(biāo)，AUC范圍為[0，1]，它的值越接近1說明算法檢測(cè)效果越好[10]。

3.2 實(shí)驗(yàn)設(shè)置與結(jié)果

本節(jié)對(duì)兩種算法進(jìn)行精度和效率測(cè)試。考慮到EIF-CINFO主要是基于CINFO的改進(jìn)，在保持其檢測(cè)效果的同時(shí)，提高檢測(cè)效率。論文中指出，CINFO在他的競(jìng)爭(zhēng)者算法里有更好的表現(xiàn)，因此本實(shí)驗(yàn)考慮只將CINFO和EIF-CINFO進(jìn)行實(shí)驗(yàn)對(duì)比分析。

實(shí)驗(yàn)環(huán)境：CPU為2.40 GHz，內(nèi)存為8 GB；軟件環(huán)境：操作系統(tǒng)為Microsoft Windows 10，實(shí)驗(yàn)程序用Matlab編寫，開發(fā)環(huán)境為Matlab2017a。

算法參數(shù)設(shè)置：在所有的實(shí)驗(yàn)中，a設(shè)定為1.732（即誤報(bào)率上界為25%）；iForest和EIF的參數(shù)設(shè)定為iTree的數(shù)量T=50，子樣本數(shù)量ψ=256。

在相同的環(huán)境下，實(shí)現(xiàn)了CINFO和EIF-CINFO。

圖4和圖5分別給出了兩種算法在不同數(shù)據(jù)集上的ROC和AUC的表現(xiàn)。

圖4 CINFO在3個(gè)數(shù)據(jù)集下的ROC曲線

圖5 EIF-CINFO在3個(gè)數(shù)據(jù)集下的ROC曲線

表2為兩種方法在不同數(shù)據(jù)集上的AUC值。

表2 兩種方法的AUC值

表3給出了算法運(yùn)行時(shí)間和效率的提升效果。

表3 算法運(yùn)行時(shí)間

從實(shí)驗(yàn)可以看出，在準(zhǔn)確性方面，兩個(gè)算法差別不大，但在效率方面，EIF-CINFO有很大的提升。這是因?yàn)镃INFO中的孤立森林每棵樹只考慮到有限特征，導(dǎo)致在lasso回歸中速度較慢。而EIF是基于對(duì)每個(gè)特征的考慮，因而在lasso回歸篩選與離群點(diǎn)無關(guān)的特征時(shí)速度較快。表4為lasso降維時(shí)間的對(duì)比，可以看出EIF-CINFO中的lasso降維的時(shí)間要比CINFO的快很多，證明了之前的觀點(diǎn)。因?yàn)镋IF的隨機(jī)超平面的隔離機(jī)制考慮了所有特征，用EIF得到的預(yù)備離群點(diǎn)能夠更快地把與離群點(diǎn)無關(guān)的特征篩選出來。

表4 平均每次lasso降維時(shí)間

4 結(jié) 語(yǔ)

高維度離群點(diǎn)檢測(cè)是數(shù)據(jù)挖掘中的一個(gè)重要研究領(lǐng)域。本文對(duì)CINFO方法進(jìn)行改進(jìn)，用實(shí)際數(shù)據(jù)和公司生產(chǎn)數(shù)據(jù)的實(shí)驗(yàn)，證明了EIF-CINFO具有在高維度空間下良好識(shí)別離群點(diǎn)的能力，并且在計(jì)算時(shí)間上有較大改進(jìn)，同時(shí)具有較高的執(zhí)行效率。