王若雨,趙千川,楊 文,2

(1.清華大學(xué) 自動(dòng)化系智能與網(wǎng)絡(luò)化系統(tǒng)研究中心,北京 100084;2.航天發(fā)射場(chǎng)可靠性重點(diǎn)實(shí)驗(yàn)室,海口 570100)

異常檢測(cè)是數(shù)據(jù)挖掘領(lǐng)域一項(xiàng)非常重要的技術(shù),廣泛應(yīng)用于金融、網(wǎng)絡(luò)、保險(xiǎn)、股票等多個(gè)領(lǐng)域[1]?；谙鄬?duì)密度的局部異常因子(local outlier factor,LOF)[2]算法是目前應(yīng)用最廣泛且最有效的無參數(shù)異常檢測(cè)算法之一,尤其是對(duì)于呈偏態(tài)分布的數(shù)據(jù)集。有鑒于此,相關(guān)文獻(xiàn)[3-12]開展了大量基于LOF的研究,但對(duì)于LOF的局限性,人們依然沒有找到較好的改進(jìn)方法,這使得該算法無法拓展到數(shù)據(jù)規(guī)模更大以及檢測(cè)精度需求更高的應(yīng)用場(chǎng)景中。第一,其時(shí)間復(fù)雜度較高,由于LOF要分別對(duì)n個(gè)樣本點(diǎn)進(jìn)行k近鄰搜索,因此使用線性掃描方法的時(shí)間復(fù)雜度為O(n2)。第二,其空間復(fù)雜度較高,由于LOF算法需要存儲(chǔ)每對(duì)數(shù)據(jù)點(diǎn)的距離信息,因此其空間復(fù)雜度也為O(n2)。這使得該算法無法應(yīng)用于數(shù)據(jù)流處理中,因?yàn)殡S著數(shù)據(jù)源源不斷的到達(dá),LOF所需內(nèi)存將持續(xù)增大,直到無法處理[8]。第三,LOF對(duì)交叉異常以及低密度簇周圍異常點(diǎn)識(shí)別不敏感。在真實(shí)場(chǎng)景中,正異常點(diǎn)通常不是涇渭分明而是交錯(cuò)在一起的,LOF對(duì)這種緊鄰正常數(shù)據(jù)簇且與其存在一定交叉的異常點(diǎn)的識(shí)別不敏感,最差情況下LOF將退化為隨機(jī)檢測(cè)器。同時(shí)在真實(shí)數(shù)據(jù)集中,正常數(shù)據(jù)的分布不會(huì)只集中在一個(gè)區(qū)域,而是分布在多個(gè)密度不同的簇中,雖然與多數(shù)算法相比,LOF可以較為有效地檢測(cè)出這種存在于非均勻密度數(shù)據(jù)中的異常點(diǎn),但其仍存在局限性,即相比于高密度簇,低密度簇正常點(diǎn)周圍的異常點(diǎn)更容易被LOF算法忽略。

1 理論基礎(chǔ)

LOF算法通過計(jì)算局部離群因子來衡量每個(gè)數(shù)據(jù)點(diǎn)的異常程度,數(shù)據(jù)點(diǎn)a局部離群因子的計(jì)算以及分析需要以下定義以及定理,其中定理1的具體證明過程參見文獻(xiàn)[2]。

定義1點(diǎn)a與其第k鄰域點(diǎn)之間的歐氏距離為dk(a)。

定義2點(diǎn)o到點(diǎn)a的可達(dá)距離為

dreach,k(a,o)=max{dk(o),d(a,o)}

(1)

式中d(a,o)為點(diǎn)a和點(diǎn)o之間的歐氏距離。

定義3點(diǎn)a的局部可達(dá)密度為

(2)

式中Nk(a)為a點(diǎn)k近鄰數(shù)據(jù)點(diǎn)的集合。

定義4點(diǎn)a的局部離群因子為

(3)

定義5點(diǎn)a第k鄰域中一點(diǎn)到點(diǎn)a可達(dá)距離的最小值以及最大值為

Fmin(a)=min{dreach,k(a,b)|b∈Nk(a)}

(4)

Fmax(a)=max{dreach,k(a,b)|b∈Nk(a)}

(5)

定義6點(diǎn)a第k鄰域中一點(diǎn)b的第k鄰域中一點(diǎn)到點(diǎn)b可達(dá)距離的最小值以及最大值為

Smin(a)=min{dreach,k(b,o)|b∈Nk(a)且o∈Nk(b)}

(6)

Smax(a)=max{dreach,k(b,o)|b∈Nk(a)且o∈Nk(b)}

(7)

定理1假設(shè)a為數(shù)據(jù)集D中的一個(gè)樣本點(diǎn),并且1≤k≤|D|,則點(diǎn)a局部離群因子的范圍為

(8)

2 iDELOF算法

iDELOF異常檢測(cè)算法,將iKSSE前置于LOF算法,高效剪切掉大量無用及干擾數(shù)據(jù),獲得更加精準(zhǔn)的搜索空間,極大提升LOF異常檢測(cè)算法的效率及效果。算法分為近鄰搜索空間提取(iKSSE)、異常分?jǐn)?shù)計(jì)算(anomaly score calculation,ASC)兩個(gè)階段,每個(gè)階段又分為兩步。

2.1 第一階段iKSSE

iKSSE分為構(gòu)造數(shù)據(jù)提取森林、提取近鄰搜索空間兩步。

第一步,構(gòu)造數(shù)據(jù)提取森林。利用孤立森林[13]提出的隔離思想對(duì)數(shù)據(jù)隨機(jī)選擇屬性、隨機(jī)設(shè)定閾值分隔為左右葉子節(jié)點(diǎn),不斷迭代重復(fù),直到葉子節(jié)點(diǎn)中只有一個(gè)樣本點(diǎn)或所有樣本點(diǎn)取值相同,或者提取樹到達(dá)最大設(shè)定閾值l。與IF算法建立的隔離樹一樣,提取樹也為二叉樹,其中每個(gè)節(jié)點(diǎn)又分為擁有兩個(gè)葉子節(jié)點(diǎn)的內(nèi)部節(jié)點(diǎn)以及沒有葉子節(jié)點(diǎn)的外部節(jié)點(diǎn)兩種類型;與隔離樹的區(qū)別在于,提取樹中每個(gè)外部節(jié)點(diǎn)的存儲(chǔ)內(nèi)容不再是數(shù)據(jù)點(diǎn)的數(shù)量,而是所有被分割到此節(jié)點(diǎn)的數(shù)據(jù)點(diǎn)以及數(shù)據(jù)點(diǎn)在樹中對(duì)應(yīng)的深度,即數(shù)據(jù)點(diǎn)被分割的次數(shù)。按上述方法,在多個(gè)隨機(jī)抽取的樣本子集上建立t棵提取樹,組合成為數(shù)據(jù)提取森林。構(gòu)建數(shù)據(jù)提取森林的具體細(xì)節(jié)見算法1、2。

算法1iDETree(X,c,l)

Input:X-input data,c-current tree depth,l-depth limit

Output:aniDETree

1:ifc≥lor|X|≤1 then

2: returnexNode{data←X,depth←c}

3:else

4: letAbe a list of attributes inX

5: randomly choose an attributea∈A

6: randomly choose a divide pointbfromminandmaxvalue of attributeainX

7:Xl←filter(X,a≤b)

8:Xr←filter(X,a>b)

10:end if

算法2iDEForest(X,t,φ)

Input:X-input data,t-number of trees,φ-subsample size

Output:a group ofiDETrees

1:InitializeiDEForest

2:set depth limitl=ceiling(log2φ)

3:fori=1∶tdo

6:end for

7:returniDEForest

第二步,提取近鄰搜索空間。遍歷提取森林中的所有外部節(jié)點(diǎn),取出每棵樹中深度位于設(shè)定的深度閾值Ct以下的外部節(jié)點(diǎn)中的所有樣本,即位于數(shù)據(jù)集全局較中心的數(shù)據(jù),并且將在所有樹中提取到的數(shù)據(jù)合并得到候選數(shù)據(jù)。最后根據(jù)設(shè)定的次數(shù)閾值N,在候選數(shù)據(jù)中篩選出提取次數(shù)超過N的所有數(shù)據(jù),作為第二階段近鄰數(shù)據(jù)的搜索空間。從構(gòu)建好的森林中提取近鄰數(shù)據(jù)搜索空間的具體細(xì)節(jié)見算法3、4。

算法3DataExtraction(T,Ct)

Input:T-an iDETree,Ct-depth threshold

Output:candidate_datafrom an iDETree

1:ifTis an external node

2: ifT.depth>Ctthen

3: returnT.data

4: end if

5:else

6: returncombine(DataExtraction(T.left,Ct),DataExtraction(T.right,Ct))

7:end if

算法4DataFilter(F,Ct,N)

Input:F-an iDEForest,Ct-depth threshold,N-filter threshold

Output:KNNsearch_space

1:Initializecandidate_data,search_space

2:forTinFdo

3:candidate_data=candidate_data∪DataExtraction(T,Ct)

4:end for

5:(value,counts)←count(condidate_data)

6:ifcounts≥Nthen

置于公共空間中的雕塑藝術(shù)，一般是以公共藝術(shù)的形態(tài)存在的，這種方式由來已久。但把來自國(guó)內(nèi)外11個(gè)國(guó)家的雕塑，以一種公共藝術(shù)的方式介入到沙漠之中，并永久性安置于沙海之地，可以說，目前在世界范圍內(nèi)尚屬首例。

7:search_space=search_space∪value

8:end if

9:returnKNNsearch_space

2.2 第二階段ASC

根據(jù)LOF的思想,計(jì)算每個(gè)測(cè)試點(diǎn)的局部利群因子,其中k近鄰的搜索空間不再是全部數(shù)據(jù)集而是由iKSSE提取所得的子集。異常分?jǐn)?shù)計(jì)算分為兩步:

第一步,在iKSSE提取所得搜索空間中實(shí)例化每個(gè)樣本點(diǎn)的k近鄰數(shù)據(jù),以及他們到樣本點(diǎn)的距離,將所得結(jié)果保存在數(shù)據(jù)庫(kù)M中;

3 前置iKSSE的優(yōu)越性

相對(duì)于LOF算法,iDELOF算法前置iKSSE,借助隔離的思想快速提取位于簇中心的子集作為ASC近鄰數(shù)據(jù)搜索空間,具有以下優(yōu)越性。

3.1 拉大正異常點(diǎn)局部離群因子之間的差距

對(duì)位于簇周圍的異常點(diǎn)p,其Fmin(p)、Fmax(p)增大,而Smin(p)、Smax(p)不變,因此異常點(diǎn)的LOF值增大;而對(duì)位于簇深處的正常點(diǎn)o,即其所有k近鄰都在簇中,并且其k近鄰的所有k近鄰點(diǎn)也都在簇中的點(diǎn),其Fmin(o)、Fmax(o)和Smin(o)、Smax(o)均改變不大,因此正常點(diǎn)的LOF值也變化不大。因此iDELOF算法拉大了正異常點(diǎn)LOF值之間的差距,使異常檢測(cè)變得更容易。為進(jìn)一步說明,圖1和圖2列舉了一個(gè)簡(jiǎn)單的例子,其中k取2。

圖1 加入iKSSE前后p點(diǎn)LOF的取值范圍

圖2 加入iKSSE前后o點(diǎn)LOF的取值范圍

3.2 增強(qiáng)對(duì)交叉異常的識(shí)別能力

對(duì)于LOF算法,簇中心與邊緣樣本點(diǎn)的LOF值相差不大,因此該算法無法有效識(shí)別此類交叉異常,當(dāng)簇的密度變化不大時(shí),LOF將退化為隨機(jī)檢測(cè)器。對(duì)于iDELOF算法,只有位于簇深處樣本點(diǎn)o的LOF值是相同的,而簇內(nèi)其余點(diǎn)p的Smin(p)、Smax(p)雖然變化不大,但Fmin(p)、Fmax(p)隨著與中心距離由近至遠(yuǎn)逐漸增加,因此LOF值也隨之增加,呈階梯分布,這使得算法更有可能將位于數(shù)據(jù)集邊緣的樣本點(diǎn)識(shí)別為交叉異常,而不是盲目地從整個(gè)數(shù)據(jù)集中隨機(jī)識(shí)別。為進(jìn)一步說明,圖3和圖4列舉了一個(gè)簡(jiǎn)單的例子,其中k取2,紅色點(diǎn)為交叉異常點(diǎn),黑色點(diǎn)為正常點(diǎn)。

圖3 加入iKSSE前后p點(diǎn)LOF的取值范圍

圖4 加入iKSSE前后o點(diǎn)LOF的取值范圍

3.3 增強(qiáng)低密度簇周圍異常點(diǎn)的識(shí)別能力

對(duì)于 LOF算法,在Fmin(a)、Fmax(a)相同的前提下,顯然低密度簇周圍異常點(diǎn)比高密度簇周圍異常點(diǎn)的Smin(a)、Smax(a)更高,其LOF值相應(yīng)的更小,因此也更容易被LOF忽略。對(duì)于iDELOF算法,圖5為數(shù)據(jù)提取森林中深度的等高線圖,從圖中可以看出當(dāng)深度閾值Ct固定時(shí),加入iKSSE后,對(duì)于近鄰數(shù)據(jù)的搜索空間,其低密度簇半徑的縮減量大于高密度簇,也就是說在Smin(a)、Smax(a)不變的情況下,顯然低密度簇周圍異常點(diǎn)比高密度簇周圍的異常點(diǎn)的Fmin(a)、Fmax(a)增加的更多,因此兩者LOF值之間的差距減小,改善了LOF對(duì)存在于不同密度簇周圍異常點(diǎn)的識(shí)別偏差。

圖5 各數(shù)據(jù)點(diǎn)在數(shù)據(jù)提取森林中的深度等高線

3.4 降低時(shí)間和空間復(fù)雜度

3.4.1 時(shí)間復(fù)雜度

對(duì)于iKSSE階段:假設(shè)建立t棵樹,每棵樹的采樣大小為ψ,則時(shí)間復(fù)雜度為O(tψlogψ),獨(dú)立于樣本大小以及空間維度,只在模型訓(xùn)練時(shí)提取一次。

對(duì)于ASC階段:不同于LOF算法,iDELOF算法是在iKSSE提取到的子集上進(jìn)行k近鄰搜索,因此每個(gè)估計(jì)器的時(shí)間成本是O(n·m),并且iDELOF只有一個(gè)基估計(jì)器,因此算法的時(shí)間成本就是O(n·m),其中n為數(shù)據(jù)集大小,m為iKSSE提取到的子集的大小(0

綜上算法的整體時(shí)間復(fù)雜度為O(tψlogψ)+O(n·m),可以看出iDELOF有效地將LOF的時(shí)間復(fù)雜度降低到與樣本數(shù)量呈線性關(guān)系且該線性關(guān)系的斜率很小,并且樣本數(shù)量越大,iKSSE的時(shí)間耗費(fèi)相較于其他算法就變得越微不足道,整個(gè)算法在時(shí)間復(fù)雜度上的優(yōu)越性也就越明顯。因此本文算法更適合應(yīng)用于超大規(guī)模的數(shù)據(jù)中。

3.4.2 空間復(fù)雜度

對(duì)于iKSSE階段:假設(shè)建立t棵樹,每棵樹的采樣大小為ψ=2a,則每棵樹最大的節(jié)點(diǎn)數(shù)為Nnode=2a+2a-1+…+20,因此所需內(nèi)存為O(t·Nnode),獨(dú)立于樣本數(shù)量,對(duì)于計(jì)算機(jī)來說微不足道。對(duì)于ASC階段:iDELOF算法是在iKSSE提取到的樣本子集上進(jìn)行k近鄰搜索,因此可以有效地將所需內(nèi)存減小到O(m2)。

綜上,算法整體的空間復(fù)雜度為O(t·Nnode)+O(m2),遠(yuǎn)小于LOF,且不會(huì)隨著樣本數(shù)量的增加而持續(xù)上漲,因此算法可以很容易加入在線學(xué)習(xí)的模塊,應(yīng)用于數(shù)據(jù)流中。

4 實(shí)驗(yàn)驗(yàn)證

進(jìn)行了4組實(shí)驗(yàn),每組實(shí)驗(yàn)分別進(jìn)行iDELOF算法與LOF、IF、iNNE(isolatin using nearest neighbour ensemble)[14]3種典型算法的對(duì)比分析,以驗(yàn)證iDELOF算法的優(yōu)越性及其應(yīng)對(duì)真實(shí)數(shù)據(jù)集的能力。其中前2組實(shí)驗(yàn)采用合成數(shù)據(jù)集,驗(yàn)證iDELOF算法在識(shí)別交叉異常以及軸平行異常方面的優(yōu)越性;第3組實(shí)驗(yàn)采用Backblaze上公開的磁盤數(shù)據(jù)集,驗(yàn)證當(dāng)數(shù)據(jù)集規(guī)模不斷增大時(shí)iDELOF算法在時(shí)間復(fù)雜度上的優(yōu)越性;第4組實(shí)驗(yàn)采用Backblaze和UCI上多個(gè)公開數(shù)據(jù)集,測(cè)試iDELOF應(yīng)對(duì)不同維度、異常比例及數(shù)量級(jí)的真實(shí)數(shù)據(jù)集的能力。各種算法的超參數(shù)均根據(jù)數(shù)據(jù)集調(diào)整到最佳組合,其中iDELOF、IF以及iNNE為隨機(jī)算法,他們的AUC值(AAUC)均采用10次不同的隨機(jī)數(shù)種子計(jì)算所得平均值。

4.1 交叉異常的識(shí)別

主要測(cè)試各種算法對(duì)交叉異常的識(shí)別能力。采用合成數(shù)據(jù)集,包括2個(gè)密度不同的正常數(shù)據(jù)簇,異常數(shù)據(jù)分布在正常簇周圍并且存在一定交叉。其中低密度簇包含200個(gè)樣本點(diǎn),周圍存在20個(gè)異常點(diǎn);高密度簇包含500個(gè)樣本點(diǎn),周圍存在40個(gè)異常點(diǎn)。異常點(diǎn)在固定環(huán)寬的圓環(huán)中隨機(jī)生成,根據(jù)圓環(huán)邊界與正常數(shù)據(jù)邊界圓環(huán)交叉程度的不同,生成5組不同的數(shù)據(jù)集,分別表示不同的正異常數(shù)據(jù)交叉比例,見圖6。

圖6 不同交叉比例的測(cè)試數(shù)據(jù)集

圖7為4種算法的AAUC隨著交叉比例的變化趨勢(shì)。從圖中可以看出隨著交叉比例的增大,各個(gè)算法的識(shí)別能力都有所下降,其中iDELOF一直擁有著最高的AAUC,且隨著交叉比例越大,iDELOF與其他算法之間的差距也越大,識(shí)別優(yōu)越性越明顯。

圖7 各算法在不同交叉比例下的AAUC

4.2 軸平行異常的識(shí)別

主要測(cè)試各種算法對(duì)軸平行異常的識(shí)別能力。實(shí)驗(yàn)采用2組軸平行異常的數(shù)據(jù)集,數(shù)據(jù)集1見圖8(a),正常數(shù)據(jù)呈螺旋形分布,其中隱藏著6個(gè)異常點(diǎn),數(shù)據(jù)集2見圖3(b),圖中左下和右上角為2個(gè)呈高斯分布的密度不同的正常數(shù)據(jù)簇,左上和右下角為2個(gè)異常數(shù)據(jù)簇。

圖8 軸平行異常測(cè)試數(shù)據(jù)

圖9為各數(shù)據(jù)點(diǎn)在不同算法下所得LOF值的等高線圖。從圖中可以看出,RC(robust covariance)及IF算法的識(shí)別效果非常差,這是由于IF基于正常數(shù)據(jù)點(diǎn)的投影進(jìn)行分割,因此對(duì)此類隱藏在軸平行中的異常點(diǎn)無能為力,iNNE的識(shí)別效果也不理想。而對(duì)于iDELOF以及LOF算法,只要調(diào)整好近鄰數(shù)據(jù)k的大小便可以很好刻畫出正異常點(diǎn)的分界。因此雖然加入iKSSE,iDELOF本質(zhì)上依然為基于相對(duì)密度的算法,與LOF算法一樣在識(shí)別軸平行異常方面具有明顯優(yōu)越性。

4.3 時(shí)間復(fù)雜度測(cè)試

主要驗(yàn)證iDELOF算法在時(shí)間復(fù)雜度方面優(yōu)越性。采用的數(shù)據(jù)集為Backblaze 2015年ST4000DM000型號(hào)的磁盤數(shù)據(jù),數(shù)據(jù)集規(guī)模為1 000～250 000。采用的方法為對(duì)比各算法檢測(cè)磁盤異常所需運(yùn)行時(shí)間隨樣本數(shù)量的變化情況,其中LOF算法根據(jù)是否使用R_tree[15]分為L(zhǎng)OFIndexed以及LOF算法。

圖10記錄了各算法的運(yùn)行時(shí)間隨數(shù)據(jù)集規(guī)模的變化趨勢(shì),圖11記錄了iKSSE在不同規(guī)模磁盤數(shù)據(jù)集下提取到的子集的大小。從圖10可以看出IF、iNNE以及iDELOF算法的時(shí)間復(fù)雜度與數(shù)據(jù)集大小呈線性關(guān)系,LOF算法的時(shí)間復(fù)雜度則與數(shù)據(jù)集大小的二次方成正比,而LOFIndexed算法利用R_tree對(duì)k近鄰進(jìn)行快速檢索,時(shí)間復(fù)雜度相比線性掃描方法有所降低,但當(dāng)樣本數(shù)據(jù)量增大時(shí),運(yùn)行時(shí)間依然很大。從圖11可以看出隨著磁盤數(shù)據(jù)集規(guī)模的擴(kuò)大,iKSSE提取到的子集的大小m不會(huì)隨之增加,而是穩(wěn)定在100附近。因此雖然在數(shù)據(jù)量較小時(shí),iDELOF由于加入iKSSE步驟,運(yùn)行時(shí)間比其他幾個(gè)算法略長(zhǎng),但是當(dāng)樣本數(shù)量逐漸增多時(shí),算法在時(shí)間復(fù)雜度上的優(yōu)越性就體現(xiàn)出來了:iDELOF的運(yùn)行時(shí)間隨著樣本規(guī)模增大而增加緩慢,其時(shí)間曲線的斜率m比最有效率的IF算法都要小。當(dāng)樣本的數(shù)量達(dá)到25 000時(shí),iDELOF算法的運(yùn)行時(shí)間已經(jīng)遠(yuǎn)遠(yuǎn)小于LOF算法;當(dāng)樣本數(shù)量達(dá)到250 000時(shí),iDELOF算法的運(yùn)算速度已經(jīng)逼近IF算法,并且可以預(yù)測(cè)隨著樣本規(guī)模的進(jìn)一步擴(kuò)大,iDELOF算法在時(shí)間復(fù)雜度上的優(yōu)越性也會(huì)體現(xiàn)得越明顯,成為最有效率的算法。

圖10 各算法在不同規(guī)模數(shù)據(jù)集下的運(yùn)行時(shí)間

圖11 iKSSE在不同規(guī)模數(shù)據(jù)集下獲得子集的大小

4.4 真實(shí)數(shù)據(jù)集測(cè)試

主要驗(yàn)證iDELOF算法應(yīng)對(duì)真實(shí)數(shù)據(jù)集的能力。采用包括Backblaze和UCI上不同維度、異常比例及數(shù)量級(jí)共5個(gè)公開數(shù)據(jù)集。每個(gè)數(shù)據(jù)集的大小、緯度、處理方式以及異常比例見表1。各個(gè)算法的超參數(shù)采用網(wǎng)格搜索法得到最佳組合見表2。不同算法在不同數(shù)據(jù)集上的AAUC值以及對(duì)應(yīng)的運(yùn)行時(shí)間記錄見表3和表4。iKSSE在不同數(shù)據(jù)集上提取到的子集大小記錄見表4。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

表2 各算法在不同數(shù)據(jù)集上的最佳參數(shù)

表3 各算法在不同數(shù)據(jù)集上的AAUC

表4 各算法的運(yùn)行時(shí)間以及iKSSE提取到的子集大小

對(duì)于檢測(cè)精度,從表3中可以看出iDELOF在多個(gè)不同真實(shí)數(shù)據(jù)集上均被證實(shí)擁有最優(yōu)的AAUC,在離群點(diǎn)檢測(cè)精度方面優(yōu)越性明顯。對(duì)于運(yùn)行效率,從表2中可以看出LOF算法在多數(shù)大規(guī)模數(shù)據(jù)集上都需要很大k值才可以達(dá)到較好的檢測(cè)效果,因此該算法的時(shí)間復(fù)雜度是所有算法中最高的。iDELOF算法由于前置了iKSSE,從各個(gè)數(shù)據(jù)集中提取到的子集的大小只占整個(gè)數(shù)據(jù)集的1%左右(見表4),這使得算法僅需要個(gè)位數(shù)的k值(見表2)就可以達(dá)到很好的效果。因此iDELOF在多數(shù)數(shù)據(jù)集上都保持著較小的時(shí)間復(fù)雜度(見表4),只在最后3個(gè)數(shù)據(jù)集上運(yùn)行時(shí)間比IF算法稍慢,這主要是數(shù)據(jù)集規(guī)模較小,算法的優(yōu)越性沒有完全體現(xiàn)的原因。

5 結(jié) 論

iDELOF異常檢測(cè)算法將基于隔離思想的近鄰搜索空間提取前置于LOF算法,高效剪切掉大量無用及干擾數(shù)據(jù),獲得更加精準(zhǔn)的搜索空間。研究表明:

1)iDELOF異常檢測(cè)算法拉大了正異常點(diǎn)局部利群因子的差距,增強(qiáng)了對(duì)交叉異常及低密度簇周圍異常點(diǎn)的識(shí)別能力,提升了檢測(cè)效果。

2)iDELOF異常檢測(cè)算法在識(shí)別軸平行異常方面,與LOF一致,具有明顯的優(yōu)越性。

3)iDELOF異常檢測(cè)算法通過iKSSE獲得的子集顯著小于原數(shù)據(jù)集,且多數(shù)子集數(shù)據(jù)量小于原數(shù)據(jù)集的1%,因此iDELOF的時(shí)間空間復(fù)雜度顯著降低。

4)原數(shù)據(jù)集數(shù)據(jù)量越大,iDELOF異常檢測(cè)算法在時(shí)間復(fù)雜度上的優(yōu)越性越明顯;當(dāng)樣本數(shù)量達(dá)到一定數(shù)值時(shí),iDELOF算法的運(yùn)行時(shí)效將高于IF算法。

5)不同緯度、規(guī)模、異常比例真實(shí)數(shù)據(jù)集實(shí)驗(yàn)表明:iDELOF算法在異常點(diǎn)檢測(cè)精度及運(yùn)行效率方面顯著優(yōu)于其他先進(jìn)算法。