一種改進的高維度離群點檢測方法*

吳遠超，范 磊

（上海交通大學 網絡空間安全學院，上海 200240）

0 引 言

離群點檢測是數據挖掘的重要一部分，是指從大量事物中發現少量與多數事物具有明顯區別的異常個體的過程[1]。離群點理論應用廣泛，如信用卡欺詐檢測、入侵檢測、故障檢測、災害預測、公共衛生中的異常疾病的爆發、恐怖活動防范以及氣象預報等。

在高維度場景下，傳統的離群點檢測算法效果大多不甚理想。這是因為普通的離群點檢測方法大多是基于數據之間的相似度和距離來挖掘離群點。而在高維空間數據變得稀疏，數據點之間的距離及密度不再具有直觀的意義，因此常規算法對高維離群點的檢測不再有效或效率較低[2]。

Pang等[3]提出了適合于高維空間的CINFO方法，通過將子空間搜索和離群點評分方法關聯起來，提高了檢測精度。本文對該方法進行改進，引入擴展的孤立森林算法（Extended Isolation Forest，EIF）[4]，提出了EIF-CINFO方法，在保持原有檢測精度的情況下，提高了效率。

1 相關算法研究

高維數據常包含大量不相關的特征，這些噪聲特征可以將離群點偽裝成正常對象。因此，對高維數據而言，發現有意義的離群點變得十分復雜和不明顯。目前，已有一些針對特定場景下的離群點檢測方法，但在效率和精度上仍需改進。

1.1 經典高維度離群點檢測算法的不足

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

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

CINFO方法針對經典高維度離群點檢測算法的不足，通過將離群點評分和子空間搜索關聯起來相互優化，提高了檢測效果。孤立森林（iForest）[8]是CINFO中的離群點評分算法，主要思想是對一個數據集構成的屬性空間，隨機選定一個特征進行空間分割得到兩個子空間。之后繼續在剩下的特征里隨機選定一個特征，對每個子空間切分，直至每個子空間只包含一種數據點或者樹的深度達到設定的最大值。

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

因為離群點一般距離正常點較遠，所以能被更好地區分開。在樹上的體現是離群點距離iTree的根結點較近，因此可以通過統計不同iTree下數據點d的平均路徑長度計算數據點的離群值。

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

2 EIF-CINFO方案設計

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

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

圖1 方案流程

2.1 離群點打分

孤立森林不能很好地適應高維度數據場景，會導致后續lasso回歸特征降維速度緩慢。為此，通過引入EIF來改正這一缺點。

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

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

圖2 EIF單次分割

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

圖3是iForest中的一棵樹和EIF中一棵樹分割數據空間的對比圖[4]。

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

圖3 iForest和EIF中的一棵樹分割數據空間對比

2.2 設定閾值獲得離群點候選集

得到離群點評分后，設定閾值。超過閾值，則暫時認定為離群點；反之，則暫時認為是正常點。利用Cantelli不等式[9]設定的閾值，可以將誤報率控制在一定范圍內，具體如下。

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

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

證明過程如下：

式（3）為Cantelli不等式，因為大的值表示離群值，這個不等式意味著當將閾值定義為μ+aδ時，即令α=aδ，則yi大于等于μ+aδ的概率小于等于，那么可能錯誤地將正常對象識別為離群值的概率最大為

Cantelli不等式是單邊的切比雪夫不等式。與切比雪夫不等式類似，它不對特定概率分布進行假設，適用于具有統計平均值和方差的概率分布。

2.3 剔除無關特征

在得到初步離群點集合后，將初步離群點作為被預測變量，數據集中的特征作為預測變量，進行lasso回歸，以剔除與初步離群點集合無關的特征。R是離群閾值階段新創建的只包含初步離群點的數據集，L為被初步識別為離群點的數量，然后進行如下的稀疏回歸學習：

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

2.4 算法描述

輸入：X為數據集，a為離群值閾值參數

輸出：M為對象異常值得分排序

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

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

repeat

t←t+1

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

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

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

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

until mset＞mset-1直到損失函數不再下降

M←SortXw.r.t score對得分進行排序

return M

3 實驗及結果分析

3.1 實驗數據集及評價標準

本節通過實驗對CINFO和EIF-CINFO的有效性和性能進行對比分析。實驗分為兩部分，第一部分使用加州大學歐文分校機器學習數據庫中的Isolet和APS數據集，用于測試算法效果。第二部分為某公司實際采集的手機設備特征數據（Device），檢測算法在該數據集下的實際效果。

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

在用Isolet和APS數據集進行測試后，用實際的手機設備特征信息數據集進行實驗，該數據集有兩類數據：描述設備固有屬性的靜態數據，如內存大小；隨著時間變化的動態數據，如地理位置信息。該數據集中將模擬器標記為異常用戶，數據集數據量為3 200個，特征維度為245。

表1 數據集詳細情況

為了評估算法的性能，實驗以ROC曲線和曲線下面積AUC為效果評價指標，AUC范圍為[0，1]，它的值越接近1說明算法檢測效果越好[10]。

3.2 實驗設置與結果

本節對兩種算法進行精度和效率測試。考慮到EIF-CINFO主要是基于CINFO的改進，在保持其檢測效果的同時，提高檢測效率。論文中指出，CINFO在他的競爭者算法里有更好的表現，因此本實驗考慮只將CINFO和EIF-CINFO進行實驗對比分析。

實驗環境：CPU為2.40 GHz，內存為8 GB；軟件環境：操作系統為Microsoft Windows 10，實驗程序用Matlab編寫，開發環境為Matlab2017a。

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

在相同的環境下，實現了CINFO和EIF-CINFO。

圖4和圖5分別給出了兩種算法在不同數據集上的ROC和AUC的表現。

圖4 CINFO在3個數據集下的ROC曲線

圖5 EIF-CINFO在3個數據集下的ROC曲線

表2為兩種方法在不同數據集上的AUC值。

表2 兩種方法的AUC值

表3給出了算法運行時間和效率的提升效果。

表3 算法運行時間

從實驗可以看出，在準確性方面，兩個算法差別不大，但在效率方面，EIF-CINFO有很大的提升。這是因為CINFO中的孤立森林每棵樹只考慮到有限特征，導致在lasso回歸中速度較慢。而EIF是基于對每個特征的考慮，因而在lasso回歸篩選與離群點無關的特征時速度較快。表4為lasso降維時間的對比，可以看出EIF-CINFO中的lasso降維的時間要比CINFO的快很多，證明了之前的觀點。因為EIF的隨機超平面的隔離機制考慮了所有特征，用EIF得到的預備離群點能夠更快地把與離群點無關的特征篩選出來。

表4 平均每次lasso降維時間

4 結 語

高維度離群點檢測是數據挖掘中的一個重要研究領域。本文對CINFO方法進行改進，用實際數據和公司生產數據的實驗，證明了EIF-CINFO具有在高維度空間下良好識別離群點的能力，并且在計算時間上有較大改進，同時具有較高的執行效率。