一種基于加權(quán)深度森林的離群數(shù)據(jù)挖掘算法

李瑞峰，楊海峰，蔡江輝，荀亞玲，周永祥

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

1 引 言

離群點(diǎn)是在同一數(shù)據(jù)集中，與其他數(shù)據(jù)有明顯差異、偏離大多數(shù)數(shù)據(jù)的異常點(diǎn).離群點(diǎn)檢測(cè)被廣泛應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)的非法訪(fǎng)問(wèn)、極端天氣的發(fā)現(xiàn)、手機(jī)網(wǎng)絡(luò)詐騙等領(lǐng)域[1].能夠在大數(shù)據(jù)中準(zhǔn)確高效地找到離群點(diǎn)，是機(jī)器學(xué)習(xí)的主要任務(wù)之一.

目前，機(jī)器學(xué)習(xí)中離群點(diǎn)的檢測(cè)方法主要包括基于距離、密度、統(tǒng)計(jì)以及聚類(lèi)等方法.基于距離的方法通過(guò)計(jì)算點(diǎn)之間的距離，將與鄰域內(nèi)其他點(diǎn)距離較遠(yuǎn)的點(diǎn)視為離群點(diǎn)[2]，Liu等[3]對(duì)不同類(lèi)型的對(duì)象進(jìn)行組合，通過(guò)計(jì)算對(duì)象間的相似度及其語(yǔ)義信息來(lái)識(shí)別離群點(diǎn).在基于聚類(lèi)的方法中，將不屬于任何一個(gè)簇的樣本點(diǎn)定義為離群點(diǎn)，Huang等[4]使用RA-clust算法和綜合假設(shè)檢驗(yàn)相結(jié)合的方法對(duì)離群點(diǎn)進(jìn)行高效檢測(cè).基于密度的方法使用離群因子表示數(shù)據(jù)的離群程度，離群因子數(shù)值越大，離群的程度越大[5].Su等[6]利用重新定義的局部偏差系數(shù)與多級(jí)查詢(xún)相結(jié)合的方法對(duì)局部離群點(diǎn)進(jìn)行檢測(cè).Shao等[7]使用共享的最近鄰居密度來(lái)識(shí)別離群點(diǎn).Hoang等[8]通過(guò)對(duì)LOF算法進(jìn)行改進(jìn)，對(duì)數(shù)據(jù)的近鄰和逆近鄰點(diǎn)計(jì)算離群因子，使其能夠解決由不同密度引起的邊緣誤判問(wèn)題，提高離群點(diǎn)檢測(cè)的準(zhǔn)確性.基于統(tǒng)計(jì)的方法先使用正常數(shù)據(jù)建立一個(gè)線(xiàn)性模型，將該模型低概率區(qū)域中的點(diǎn)視為離群點(diǎn).例如，PCA算法[9]，一類(lèi)支持向量機(jī)算法(OCSVM)[10].但這些算法大多都較難應(yīng)對(duì)復(fù)雜數(shù)據(jù)的′維數(shù)災(zāi)難′問(wèn)題，在高維屬性中存在較多的無(wú)關(guān)屬性時(shí)，在一定程度上異常點(diǎn)容易被無(wú)關(guān)屬性掩蓋，影響異常點(diǎn)的檢測(cè)效率.

深度森林是一種有效的機(jī)器學(xué)習(xí)方法，該算法不涉及大規(guī)模的距離計(jì)算，也不取決于其近鄰密度的大小，與傳統(tǒng)的離群點(diǎn)挖掘算法相比具有更適用于海量高維數(shù)據(jù)、較少的超參數(shù)優(yōu)化的特點(diǎn).與上述方法不同，深度森林算法主要是通過(guò)集成思想來(lái)對(duì)數(shù)據(jù)特征進(jìn)行劃分并計(jì)算其概率分布.但是森林級(jí)聯(lián)模塊中的深度森林算法的森林特征隨機(jī)選擇性大，可能會(huì)導(dǎo)致很多無(wú)關(guān)屬性被作為根節(jié)點(diǎn)，從而影響算法的性能與效率.針對(duì)上述缺點(diǎn)，本文對(duì)深度森林算法進(jìn)行了改進(jìn)，提出了一種基于加權(quán)深度森林的離群數(shù)據(jù)挖掘算法WDF(Weight Deep Forest).算法的主要思想為：首先使用滑動(dòng)窗口方法對(duì)數(shù)據(jù)進(jìn)行粒度掃描；然后，在級(jí)聯(lián)森林模塊構(gòu)建過(guò)程中，將粒度掃描模塊中得到的概率向量進(jìn)行層級(jí)訓(xùn)練，根據(jù)每個(gè)實(shí)例的概率分?jǐn)?shù)來(lái)計(jì)算森林的預(yù)測(cè)準(zhǔn)確率，并定義了權(quán)重因子μ，使用權(quán)重因子μ賦予每個(gè)森林相應(yīng)的權(quán)重，μ越高，對(duì)應(yīng)的權(quán)重值越大，有效地減少森林中特征隨機(jī)選擇對(duì)算法性能的影響；其次，由于樣本數(shù)據(jù)中離群數(shù)據(jù)分布的不同，重新定義了局部孤立因子α以及閾值函數(shù)F(r)，根據(jù)數(shù)據(jù)的類(lèi)密度對(duì)孤立因子α進(jìn)行計(jì)算，α值越大，數(shù)據(jù)離群的可能性也就越大，α大于閾值函數(shù)F(r)的數(shù)據(jù)為離群數(shù)據(jù)，從而提高離群點(diǎn)檢測(cè)的正確性；最后采用UCI數(shù)據(jù)集和恒星光譜數(shù)據(jù)驗(yàn)證了該算法的有效性.

2 理論基礎(chǔ)

在深度森林算法[11]中，主要包括兩部分，多粒度掃描模塊和級(jí)聯(lián)森林結(jié)構(gòu)模塊，其模型結(jié)構(gòu)如圖1和圖2所示.

圖1 多粒度掃描模塊框架Fig.1 Multi-granularity scanning module framework

圖2 級(jí)聯(lián)森林結(jié)構(gòu)模塊框架Fig.2 Cascading forest structure module framework

如圖1所示，在多粒度掃描模塊中，通過(guò)不同大小的窗口m1和m2將n維數(shù)據(jù)劃分為(n-m1+1)個(gè)m1維，(n-m2+1)個(gè)m2維的數(shù)據(jù)實(shí)例，通過(guò)對(duì)兩個(gè)森林進(jìn)行訓(xùn)練，生成k(k為數(shù)據(jù)類(lèi)別總數(shù))個(gè)類(lèi)概率向量并將其結(jié)果進(jìn)行合并，分別得到2(n-m1+1)維，2(n-m2+1)維的數(shù)據(jù)實(shí)例.

如圖2所示，在級(jí)聯(lián)森林模塊中，將粒度掃描模塊得到的g維概率向量作為輸入，在4個(gè)森林中對(duì)其進(jìn)行訓(xùn)練.隨機(jī)森林使用基尼指數(shù)G作為節(jié)點(diǎn)分裂指標(biāo)，其公式為：

(1)

(2)

其中Pt代表第t類(lèi)的概率，A為數(shù)據(jù)集D中的某一屬性，按照屬性A將數(shù)據(jù)集分為D1和D2.

每個(gè)森林生成一個(gè)k維的概率向量并與g維的原始概率向量合并作為下一級(jí)聯(lián)層的輸入，為了防止過(guò)擬合，采用k折交叉驗(yàn)證方法進(jìn)行訓(xùn)練，交叉驗(yàn)證值β的公式如下：

(3)

其中，n為數(shù)據(jù)集劃分的子集個(gè)數(shù)，Qi為第i次劃分的分類(lèi)結(jié)果.級(jí)聯(lián)層依次迭代，直至達(dá)到最大級(jí)聯(lián)層數(shù)，將森林中的概率向量的平均值取最大值并作為最終結(jié)果輸出.

3 基于加權(quán)深度森林的離群數(shù)據(jù)挖掘方法

3.1 基本思想

針對(duì)深度森林算法在構(gòu)建級(jí)聯(lián)森林模塊時(shí)特征選擇的隨機(jī)性大導(dǎo)致算法的級(jí)聯(lián)層數(shù)增加，系統(tǒng)開(kāi)銷(xiāo)大等問(wèn)題，加權(quán)深度森林(WDF)算法重新定義了級(jí)聯(lián)森林模塊.為了方便描述該算法，首先給出了如下定義.

定義1.設(shè)數(shù)據(jù)集D={L1，L2，…，Lm}，類(lèi)別為C={C1，C2，…，Cn}，森林的預(yù)測(cè)概率矩陣如下：

(4)

其中，Bij表示第i條數(shù)據(jù)被劃分為第j類(lèi)的概率，根據(jù)森林預(yù)測(cè)概率矩陣中每一行中最大值的列下標(biāo)作為該條數(shù)據(jù)的最終預(yù)測(cè)類(lèi)別，并將其在矩陣中標(biāo)記為1，其余為0，例如：

(5)

則在算法中森林的準(zhǔn)確率公式如下：

(6)

其中，m表示數(shù)據(jù)總數(shù)，n表示類(lèi)別數(shù)，A[i][j]表示數(shù)據(jù)樣本的實(shí)際類(lèi)別矩陣，B[i][j]表示預(yù)測(cè)概率矩陣，通過(guò)交運(yùn)算得到每個(gè)森林的預(yù)測(cè)準(zhǔn)確率.

定義 2.設(shè)森林R={1，2，…，r}，森林的權(quán)重因子μ定義如下：

(7)

Pi表示第i個(gè)森林的準(zhǔn)確率，則第i個(gè)森林的類(lèi)預(yù)測(cè)概率矩陣為：

B(i)=B×μ

(8)

定義 3.形式背景為二元組，D={Lt|t=1..n}是記錄集，C={Cj|j= 1..r}是類(lèi)集，滿(mǎn)足Ci∩Cj=?且 ?Lt∈D→(Lt∈Ci∧Lt?Cj)(若i≠j)，則孤立因子α可以用公式(9-11)定義：

M(Lt)=min{d(Lt，L1)，d(Lt，L2)，...，d(Lt，Ln)}
(L1，L2，…，Ln∈Ci，t≠n)

(9)

(10)

(11)

在式(9)中，d(Lt，L1)為第t個(gè)點(diǎn)與第一個(gè)數(shù)據(jù)點(diǎn)的距離，ρ(Ci)表示第i類(lèi)數(shù)據(jù)的類(lèi)密度[12]，孤立因子α的閾值函數(shù)F(r)定義如下：

(12)

其中，r為數(shù)據(jù)集中的類(lèi)別數(shù)r>0，閾值函數(shù)F(r)為單調(diào)遞減函數(shù)，隨著r增加，F(xiàn)(r)減小.

基于以上定義，在WDF算法中構(gòu)建級(jí)聯(lián)森林模塊時(shí)，首先對(duì)森林集成部分進(jìn)行分析，在算法中用到的隨機(jī)森林和完全隨機(jī)森林都是隨機(jī)選擇特征，通過(guò)定義1可以得到森林的預(yù)測(cè)概率矩陣，用公式(6)計(jì)算出森林的準(zhǔn)確率，并引入定義2中的權(quán)重因子μ，對(duì)森林的概率結(jié)果進(jìn)行加權(quán).準(zhǔn)確率越高，權(quán)重因子μ越高，森林權(quán)重越大，反之，權(quán)重則越小，這一步驟可以有效降低特征隨機(jī)選擇的根節(jié)點(diǎn)中無(wú)關(guān)屬性對(duì)算法性能的影響.將加權(quán)之后的概率向量作為輸入進(jìn)入下一個(gè)森林級(jí)聯(lián)層繼續(xù)訓(xùn)練，重復(fù)上述操作，直到達(dá)到最大級(jí)聯(lián)層數(shù).在級(jí)聯(lián)加權(quán)森林構(gòu)造完成后，由于樣本數(shù)據(jù)分布的不同，數(shù)據(jù)被劃分為密度不同的類(lèi)，通過(guò)定義3中可以得到每類(lèi)樣本數(shù)據(jù)的類(lèi)密度，數(shù)據(jù)越多的類(lèi)，其類(lèi)密度越小，并用公式(11)計(jì)算其局部孤立因子α，α越大，數(shù)據(jù)離群的概率越大.通過(guò)公式(12)可以得到在不同數(shù)據(jù)集中孤立因子函數(shù)閾值F(r)，α值大于F(r)的數(shù)據(jù)則為離群數(shù)據(jù).

3.2 WDF算法描述

WDF算法主要包括兩部分，第1部分為多粒度掃描部分，第2部分為級(jí)聯(lián)加權(quán)森林部分.在多粒度掃描部分中，通過(guò)滑動(dòng)窗口對(duì)數(shù)據(jù)進(jìn)行掃描，將數(shù)據(jù)劃分為多個(gè)不同的維度，并依次進(jìn)入隨機(jī)森林和完全隨機(jī)森林訓(xùn)練，將得到的類(lèi)概率向量進(jìn)行合并作為級(jí)聯(lián)加權(quán)森林模塊的輸入.在級(jí)聯(lián)加權(quán)森林部分，輸入數(shù)據(jù)進(jìn)入森林集成部分進(jìn)行訓(xùn)練，包括兩個(gè)隨機(jī)森林和兩個(gè)完全隨機(jī)森林.為了避免過(guò)擬合，采用公式(3)中的k折交叉驗(yàn)證法進(jìn)行訓(xùn)練，并采用定義1的方法獲得森林的預(yù)測(cè)概率矩陣，矩陣每一行的最大值所對(duì)應(yīng)的下標(biāo)作為其預(yù)測(cè)結(jié)果，用公式(6)對(duì)森林的準(zhǔn)確率進(jìn)行計(jì)算.引入定義2中的權(quán)重因子，對(duì)森林進(jìn)行加權(quán)，森林的權(quán)重因子μ越大，權(quán)重值越大.將加權(quán)之后的每個(gè)森林的概率向量與粒度掃描層的概率結(jié)果相結(jié)合作為下一層森林級(jí)聯(lián)層的輸入，并計(jì)算該層的錯(cuò)誤率，遞歸上述操作，直到達(dá)到最大級(jí)層數(shù)，或該層的錯(cuò)誤率增加，迭代停止.WDF算法的具體步驟如下.

算法：加權(quán)深度森林(WDF)算法

輸入：訓(xùn)練集D，樣本個(gè)數(shù)X，測(cè)試集W，屬性個(gè)數(shù)A，窗口大小scan_size，最大級(jí)聯(lián)層數(shù)T，森林個(gè)數(shù)4

輸出：離群點(diǎn)個(gè)數(shù)

1. for x=1 to X do

2. win_len = len(A)-scan_size + 1；

3. 讀取訓(xùn)練集train_data；測(cè)試集test_data；

4. 讀取訓(xùn)練集標(biāo)簽train_label；

5. for i=1 to win_len do

7. end for

8. end for

9. for j=1 to 4 do

10. val_prob=np.zeros(len(train_data)，

len(set(train_label))×4))

11. one_result= max(val_prob)

13. result=val_prob(test_data) × μ；

14. end for

15. concatenate(result)；

16. if t

17. t=t+1；

18. end if

級(jí)聯(lián)加權(quán)森林模塊構(gòu)造完成以后，通過(guò)公式(9)-公式(12)對(duì)數(shù)據(jù)集中的每類(lèi)樣本數(shù)據(jù)計(jì)算其孤立因子α以及該數(shù)據(jù)集的閾值函數(shù)F(r)，將α> F(r)的數(shù)據(jù)作為離群數(shù)據(jù).

3.3 算法復(fù)雜性分析

本文的算法內(nèi)容主要包括兩個(gè)部分，第1部分是數(shù)據(jù)粒度掃描，第2部分是級(jí)聯(lián)加權(quán)森林.對(duì)于有n條訓(xùn)練數(shù)據(jù)，粒度掃描模塊的時(shí)間復(fù)雜度為O(n3)，級(jí)聯(lián)加權(quán)森林的時(shí)間復(fù)雜度為O(n3)，算法的整體時(shí)間復(fù)雜度為O(n3).改進(jìn)算法與深度森林算法都不涉及距離的計(jì)算，且改進(jìn)算法減小了可能對(duì)離群點(diǎn)檢測(cè)產(chǎn)生錯(cuò)誤影響的森林的權(quán)重，有效地減少了系統(tǒng)開(kāi)銷(xiāo).

4 實(shí)驗(yàn)分析

本文利用UCI數(shù)據(jù)集和恒星光譜數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，對(duì)本文提出的加權(quán)深度森林的離群數(shù)據(jù)挖掘算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)配置為Intel core i5-4210H，64位操作系統(tǒng)PC機(jī)，編程環(huán)境python3.7.

4.1 UCI數(shù)據(jù)集

為了驗(yàn)證WDF算法的有效性，實(shí)驗(yàn)中采用了UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集的屬性信息如表1所示.Epileptic Seizure數(shù)據(jù)集是癲癇發(fā)作病例檢測(cè)數(shù)據(jù)，類(lèi)別2、3、4、5為非癲癇發(fā)作者，視為正常數(shù)據(jù)，類(lèi)別1為癲癇發(fā)作者，視為離群數(shù)據(jù).HTRU2[13]數(shù)據(jù)集是脈沖星候選樣本數(shù)據(jù)，由兩種類(lèi)別構(gòu)成，實(shí)驗(yàn)中將數(shù)量相對(duì)較少的第2類(lèi)數(shù)據(jù)視為離群數(shù)據(jù).Wilt[14]數(shù)據(jù)集是高分辨率遙感數(shù)據(jù)，數(shù)據(jù)集中第2類(lèi)數(shù)據(jù)有261個(gè)樣本約占5.3%，視為離群數(shù)據(jù).Avila[15]數(shù)據(jù)集是Avila Bile圖像數(shù)據(jù)，將數(shù)據(jù)量相對(duì)較少的W、C、B類(lèi)數(shù)據(jù)作為離群數(shù)據(jù).Urban land cover數(shù)據(jù)集是土地覆蓋數(shù)據(jù)，將數(shù)據(jù)量較少的土地覆蓋類(lèi)型soil、pool類(lèi)組合作為離群數(shù)據(jù)，約占9.33%.First-order數(shù)據(jù)集是包含51個(gè)維度的一階定理證明數(shù)據(jù)，本實(shí)驗(yàn)去除了5個(gè)分類(lèi)屬性，共46個(gè)屬性，將未能證明定理的第2類(lèi)數(shù)據(jù)作為離群數(shù)據(jù).MEU-Mobile KSD數(shù)據(jù)集是觸摸移動(dòng)設(shè)備的動(dòng)態(tài)數(shù)據(jù)，共有56個(gè)類(lèi)別，將54、55、56類(lèi)組合作為離群數(shù)據(jù).

4.2 LAMOST恒星光譜數(shù)據(jù)集

實(shí)驗(yàn)中使用的恒星光譜數(shù)據(jù)是由郭守敬望遠(yuǎn)鏡(LAMOST)巡天探測(cè)獲得，每條光譜數(shù)據(jù)都有其對(duì)應(yīng)的波長(zhǎng)與流量，波長(zhǎng)范圍約在3700-9000，根據(jù)其表面溫度及譜線(xiàn)的不同，恒星被分為O、B、A、F、G、K、M這7大類(lèi).

式中，Dx、Dy分別為泥沙擴(kuò)散系數(shù)沿x、y方向的取值；S為含沙量；s F 為底部沖刷函數(shù)，采用切應(yīng)力理論表達(dá)式如下：

光譜數(shù)據(jù)的維度很高，但并不是所有的屬性都是我們所需要的，使用基于相關(guān)子空間[16]的特征選擇方法可以有效地解決高維數(shù)據(jù)的處理問(wèn)題，相關(guān)子空間βij公式如下：

(13)

公式(13)所示，δij表示局部密度差異因子，α表示局部密度差異因子的閾值，當(dāng)局部密度差異因子小于閾值時(shí)，第j維特征加入相關(guān)子空間中.每條屬性的特征強(qiáng)度通過(guò)Lick系統(tǒng)中線(xiàn)指數(shù)[17]的等效寬度(EW)來(lái)獲得，公式如下：

(14)

λ1和λ2表示中心波段的起始波長(zhǎng)和終止波長(zhǎng)，F(xiàn)Iλ表示在中心波段單位波長(zhǎng)的流量，F(xiàn)Cλ表示中心波段連續(xù)譜的流量.通過(guò)數(shù)據(jù)預(yù)處理，高維的恒星光譜數(shù)據(jù)被處理為12維，數(shù)據(jù)類(lèi)型為連續(xù)型，恒星數(shù)據(jù)集的屬性信息如表1所示.

表1 選擇的數(shù)據(jù)集Table 1 Selected data sets

從LAMOST DR5中獲取了6個(gè)不同數(shù)量的恒星光譜數(shù)據(jù)集，數(shù)據(jù)的具體屬性如表1所示.STAR1、STAR2和STAR3數(shù)據(jù)集的訓(xùn)練數(shù)據(jù)樣本由F類(lèi)型的恒星光譜與異常類(lèi)型數(shù)據(jù)兩部分組成，將非F類(lèi)數(shù)據(jù)視為離群數(shù)據(jù).STAR4、STAR5和STAR6數(shù)據(jù)集的數(shù)據(jù)樣本由恒星光譜數(shù)據(jù)與異常數(shù)據(jù)兩類(lèi)數(shù)據(jù)組成.恒星光譜數(shù)據(jù)中包含A、F、G、K、M 5種不同類(lèi)型的光譜數(shù)據(jù)，其數(shù)據(jù)分布為平衡數(shù)據(jù)，非恒星光譜數(shù)據(jù)視為異常數(shù)據(jù).

4.3 參數(shù)分析

為了驗(yàn)證窗口大小、決策樹(shù)數(shù)量對(duì)本文算法性能的影響，從表1的數(shù)據(jù)集中選擇了4個(gè)數(shù)據(jù)集進(jìn)行測(cè)驗(yàn)，分別為STAR 4、STAR 5、HTRU2和Avila數(shù)據(jù)集.采用AUC作為評(píng)估標(biāo)準(zhǔn)，并畫(huà)出了ROC曲線(xiàn)，AUC計(jì)算公式如下：

(15)

(16)

其中P1表示正常樣本的預(yù)測(cè)概率，P0表示異常樣本的預(yù)測(cè)概率，M、N分別為正常、異常樣本的個(gè)數(shù).ROC曲線(xiàn)下方圍成的面積即為AUC，AUC的值越接近1，說(shuō)明算法的性能越高，檢測(cè)效果越好，反之，則越差.

4.3.1 窗口大小X對(duì)AUC的影響

本實(shí)驗(yàn)采用不同的數(shù)據(jù)集對(duì)滑動(dòng)窗口大小X進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖3所示.在不同的數(shù)據(jù)集中，當(dāng)滑動(dòng)窗口為(1，2，1)和(2，2，1)時(shí)，算法的性能相對(duì)較低，可能的原因是窗口數(shù)太小，無(wú)關(guān)屬性作為主要特征的概率增加，離群點(diǎn)檢測(cè)的錯(cuò)誤率增大.隨著滑動(dòng)窗口數(shù)的增加，當(dāng)窗口大小為(4，2，2)和(8，4，2)時(shí)，不同數(shù)據(jù)集的AUC值都隨之增加，并且從圖中可以看出，當(dāng)窗口大小為(3，4，6)和(10，3，5)時(shí)，在不同的數(shù)據(jù)集中，該算法AUC值最高且接近于1.由于本算法第1部分是滑動(dòng)窗口粒度掃描模塊，第2部分是級(jí)聯(lián)加權(quán)森林模塊，窗口大小X對(duì)算法中離群點(diǎn)特征判斷具有重要影響，并且在HTRU2數(shù)據(jù)集中數(shù)據(jù)維數(shù)為8，因此窗口大小X選作(3，4，6)，不僅可以避免因?qū)傩蕴卣鬏^少對(duì)離群點(diǎn)特征造成的錯(cuò)誤判斷，還能減少大數(shù)據(jù)量產(chǎn)生的系統(tǒng)開(kāi)銷(xiāo).因此，在后續(xù)實(shí)驗(yàn)中將窗口大小X的默認(rèn)值設(shè)定為(3，4，6).

圖3 窗口大小X對(duì)AUC的影響Fig.3 Influence of window size X on AUC

4.3.2 決策樹(shù)的數(shù)量T對(duì)AUC的影響

該實(shí)驗(yàn)采用與4.3.1節(jié)相同的方法，對(duì)不同的決策樹(shù)的數(shù)量T進(jìn)行實(shí)驗(yàn)，結(jié)果如圖4所示.隨著決策樹(shù)數(shù)量T的增加，該算法在不同的數(shù)據(jù)集中的AUC值也隨之增加，且在T為100時(shí)，算法的AUC值逐漸收斂且趨于穩(wěn)定，接近于1.當(dāng)決策樹(shù)的數(shù)量T小于50時(shí)，不同數(shù)據(jù)集的AUC值差距較大，可能的原因是決策樹(shù)數(shù)量較少，在森林特征隨機(jī)選擇過(guò)程中，主要特征被作為根節(jié)點(diǎn)的概率較低，導(dǎo)致算法的AUC相對(duì)較低.當(dāng)子樹(shù)數(shù)量T為50時(shí)，AUC值開(kāi)始趨于收斂，并且當(dāng)T為100時(shí)收斂達(dá)到最大值，隨著決策樹(shù)中數(shù)量T的增加，當(dāng)T數(shù)量為200、400、800時(shí)，在不同的數(shù)據(jù)集下，算法的AUC值都接近于1.由于森林中子樹(shù)的數(shù)量太多會(huì)增加算法在時(shí)間和空間上的消耗，增加系統(tǒng)開(kāi)銷(xiāo).并且從多次實(shí)驗(yàn)中可以看出，決策樹(shù)的數(shù)量T為100-400范圍時(shí)，在不同數(shù)據(jù)集中，算法的整體性能較為穩(wěn)定且精度較高，且算法開(kāi)銷(xiāo)也較低，在該實(shí)驗(yàn)中使用T=100作為后續(xù)實(shí)驗(yàn)的默認(rèn)值.

圖4 子樹(shù)的數(shù)量T對(duì)AUC的影響Fig.4 Influence of the number of subtrees T on AUC

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

本節(jié)主要內(nèi)容是通過(guò)與4種不同的離群點(diǎn)檢測(cè)算法進(jìn)行AUC值和ROC曲線(xiàn)對(duì)比，來(lái)驗(yàn)證該算法的性能.

4.4.1 各對(duì)比算法的AUC

本節(jié)采用光譜數(shù)據(jù)對(duì)5種離群點(diǎn)檢測(cè)算法進(jìn)行對(duì)比，WDF算法的參數(shù)設(shè)置如4.3小節(jié)所述.快速隔離森林算法(FIF)通過(guò)計(jì)算數(shù)據(jù)在每個(gè)隔離樹(shù)中的平均高度來(lái)判斷離群數(shù)據(jù)，MO_GAAL和SO_GAAL[18]算法采用對(duì)抗性學(xué)習(xí)模型來(lái)檢測(cè)異常點(diǎn)，XGBOD[19]算法是一種基于無(wú)監(jiān)督的異常點(diǎn)檢測(cè)方法.

表2表示了在不同的數(shù)據(jù)集中各對(duì)比算法的AUC，其中黑體部分為這些數(shù)據(jù)集中最高的AUC值.在本實(shí)驗(yàn)所采用的

圖5 各算法的ROC曲線(xiàn)Fig.5 ROC curve of each algorithm

數(shù)據(jù)集中，WDF算法和XGBOD算法的AUC值相比于FIF、MO_GAAL、SO_GAAL算法較高，并且由表2可知，WDF算法的性能更加穩(wěn)定，在光譜數(shù)據(jù)的離群點(diǎn)檢測(cè)中，WDF算法相比其它幾種離群點(diǎn)檢測(cè)方法具有更高的AUC值，原因是在級(jí)聯(lián)森林模塊中，采用加權(quán)森林的方法對(duì)數(shù)據(jù)特征進(jìn)行概率計(jì)算，與傳統(tǒng)方法相比減少了低準(zhǔn)確率森林對(duì)異常數(shù)據(jù)特征判斷的干擾，使得離群數(shù)據(jù)檢測(cè)具有更高的可信度.

表2 對(duì)比算法的AUCTable 2 AUC of the comparison algorithm

圖5表示了各算法在3個(gè)代表數(shù)據(jù)集中的ROC曲線(xiàn)，其中dash-dot線(xiàn)為本文的算法，從圖中可以看出，WDF算法在不同的數(shù)據(jù)集中ROC曲線(xiàn)下的面積均大于其余的對(duì)比算法，且算法性能較為穩(wěn)定.在Wilt和STAR5數(shù)據(jù)集中，WDF算法的ROC面積遠(yuǎn)遠(yuǎn)超過(guò)了其他算法的ROC面積，并且AUC值幾乎接近于1.在Avila數(shù)據(jù)集中，WDF算法的ROC值僅低于XGBOD算法，XGBOD算法對(duì)于維數(shù)較低的數(shù)據(jù)集效果更加明顯.SO_GAAL算法與MO_GAAL算法在整體性能上表現(xiàn)較差，可能的原因是在生成模型中，離群數(shù)據(jù)的特征較不明顯，與正常數(shù)據(jù)差距較小，導(dǎo)致算法性能較低.

4.4.2 不同數(shù)據(jù)維度對(duì)算法的影響分析

圖6展示了不同維度的恒星光譜數(shù)據(jù)集在加權(quán)深度森林算法中的結(jié)果，隨著數(shù)據(jù)維度的增加，算法的AUC值整體呈上升趨勢(shì)，直到維度數(shù)為5時(shí)增長(zhǎng)發(fā)生波動(dòng).當(dāng)數(shù)據(jù)維數(shù)為6-10之間時(shí)，算法的AUC值變化幅度較大，可能的原因是在這些維數(shù)中包含了無(wú)關(guān)屬性，從而導(dǎo)致在森林特征隨機(jī)選擇過(guò)程中，無(wú)關(guān)屬性被選擇的概率較大，AUC值較低.當(dāng)維數(shù)為10-12之間時(shí)，不同的恒星光譜數(shù)據(jù)集中算法的AUC值都在0.9以上，并且當(dāng)維數(shù)為12時(shí)，不同數(shù)據(jù)集的AUC值基本都收斂于最大值1.因此在光譜數(shù)據(jù)集中選擇維數(shù)為12，既能保證算法具有較高的效率，同時(shí)可以避免因維數(shù)較小，某些明顯特征點(diǎn)被忽略.

圖6 數(shù)據(jù)維度A對(duì)AUC的影響Fig.6 Impact of data dimension A on AUC

4.4.3 算法的運(yùn)行時(shí)間

圖7表示了WDF算法與4個(gè)對(duì)比算法在各個(gè)數(shù)據(jù)集中運(yùn)行時(shí)間的對(duì)比結(jié)果，在6個(gè)光譜數(shù)據(jù)集中，隨著數(shù)據(jù)量的增加，各個(gè)算法的運(yùn)行時(shí)間也依次增加.在WDF算法中，隨著數(shù)據(jù)量不斷增加，在多粒度掃描模塊中每個(gè)森林中子樹(shù)的個(gè)

圖7 算法的運(yùn)行時(shí)間(s)Fig.7 Run time of algorithm(s)

數(shù)較多，導(dǎo)致其在進(jìn)行特征轉(zhuǎn)換時(shí)所需要的時(shí)間也增加.在級(jí)聯(lián)森林模塊中通過(guò)引入權(quán)重因子減少了特征隨機(jī)選擇導(dǎo)致的算法誤差，與4個(gè)對(duì)比算法相比，WDF算法的運(yùn)行時(shí)間并不是最少，相比于FIF、MO_GAAL算法消耗時(shí)間較長(zhǎng)，但WDF算法在離群點(diǎn)檢測(cè)中的精確率更高，能夠更加準(zhǔn)確的對(duì)離群點(diǎn)進(jìn)行檢測(cè)，整體而言WDF算法在離群點(diǎn)檢測(cè)方面具有更高的挖掘質(zhì)量.

5 結(jié)束語(yǔ)

本文提出了一種基于加權(quán)深度森林的離群數(shù)據(jù)挖掘算法，該算法采用森林加權(quán)的方式，通過(guò)計(jì)算森林的準(zhǔn)確率引入加權(quán)因子μ，賦予森林不同的權(quán)重值，準(zhǔn)確率越高，μ越大，權(quán)重值也越大，降低了森林特征隨機(jī)選擇對(duì)算法性能的影響，有效地提升了算法的整體性能；通過(guò)類(lèi)密度引入了局部孤立因子α及其閾值函數(shù)F(r)，α值大于F(r)的數(shù)據(jù)視為離群數(shù)據(jù)，使算法在不降低效率的情況下提高了離群點(diǎn)挖掘的準(zhǔn)確性.采用UCI數(shù)據(jù)集和恒星光譜數(shù)據(jù)集驗(yàn)證了算法的有效性.本文下一步的研究方向?yàn)榭紤]如何能提高算法的運(yùn)行速度，以實(shí)現(xiàn)海量數(shù)據(jù)離群點(diǎn)的快速檢測(cè).