羅計(jì)根，熊玲珠，杜建強(qiáng)，聶 斌，熊旺平，李郅琴

1.江西中醫(yī)藥大學(xué) 計(jì)算機(jī)學(xué)院，南昌 330004

2.江西師范大學(xué) 信息化辦公室，南昌 330022

隨機(jī)森林（random forest，RF）[1]是集成分類模型，通過多棵決策樹共同投票使模型具有高穩(wěn)定性，同時(shí)也因其強(qiáng)大的分類能力使得它在各類數(shù)據(jù)挖掘比賽中脫穎而出，成為各家競(jìng)相追捧的算法之一。在惡意軟件檢測(cè)[2]、情境感知推薦[3]、疾病診斷[4]中有廣泛的應(yīng)用。

RF算法具有高準(zhǔn)確率、泛化性強(qiáng)等諸多優(yōu)勢(shì)，但也存在不足。在遇到高維數(shù)據(jù)的時(shí)候，因其特征隨機(jī)抽取機(jī)制，導(dǎo)致抽取的特征和類別變量相關(guān)性差，此外，隨機(jī)抽取的自變量可能存在高度冗余，直接影響隨機(jī)森林隨機(jī)特征子集的質(zhì)量，導(dǎo)致隨機(jī)森林的收斂性減弱，降低隨機(jī)森林模型的準(zhǔn)確度、泛化能力及性能。因此，隨機(jī)抽取的特征子集優(yōu)劣是保證RF高準(zhǔn)確率的前提。針對(duì)數(shù)據(jù)維度高，特征間高度冗余給隨機(jī)森林模型帶來的準(zhǔn)確率不高的問題，本文提出一種融合近似馬爾科夫毯的隨機(jī)森林優(yōu)化算法。

1 相關(guān)研究

針對(duì)隨機(jī)森林模型隨機(jī)抽取特征時(shí)所造成的自變量間存在相關(guān)性和冗余性等問題，Wu 等人[5]指出RF 算法，在特征子集選擇時(shí)，會(huì)有大量不相關(guān)的特征進(jìn)入特征子空間，從而影響分類器性能，提出一種分層采樣特征子集空間的RF改進(jìn)算法，分層采樣的RF方法可以獲得更高的分類正確率；姚登舉[6]針對(duì)臨床高維數(shù)據(jù)和特征間高度相關(guān)性等問題，提出在Filter 式特征選擇基礎(chǔ)上構(gòu)建RF，先用RF 算法變量重要性對(duì)特征排序，然后通過迭代實(shí)驗(yàn)確定特征選擇的閾值，選擇特征重要性較大的特征構(gòu)成RF的特征子集；針對(duì)高維特征冗余問題，姚登舉等人還提出一種基于RF和序列聯(lián)合搜索策略的Wrapper式特征選擇算法，該算法利用RF善于從具有小邊際效應(yīng)和復(fù)雜相互作用的特征中識(shí)別主要相關(guān)特征的能力，以RF變量重要性分?jǐn)?shù)作為特征重要性度量，采用序列后向和序列前向相結(jié)合的序列聯(lián)合特征搜索策略選擇特征子集，以特征子集上分類器的分類正確率評(píng)價(jià)特征子集的質(zhì)量，最后選擇分類正確率最高的特征子集作為最優(yōu)特征子集；馮盼峰等人[7]提出兩階段逐步變量選擇的隨機(jī)森林算法，第一階段提出變量重要性排序，目的是進(jìn)一步提高重要變量與無關(guān)或者冗余變量的區(qū)分度，第二階段完成隨機(jī)森林的構(gòu)建。

此外Amaratunga 等人[8]提出一種特殊RF 算法，該方法加權(quán)隨機(jī)采樣和特征排序方法提高RF 的分類性能，在10組真實(shí)的基因表達(dá)數(shù)據(jù)集上的實(shí)驗(yàn)表明，特殊RF 方法的分類性能優(yōu)于基本的RF 方法；Svetnik 等人[9]通過交叉驗(yàn)證的方法計(jì)算數(shù)據(jù)每個(gè)特征的重要性評(píng)分并排序，重復(fù)20 次選取前50%的特征建立RF 模型；Genuer 等人[10]提出“兩步法”構(gòu)建RF 模型，第一步對(duì)特征降序排列，初步剔除不重要特征，第二步選擇降序排列前K個(gè)變量，建立RF 算法，最終選擇袋外數(shù)據(jù)驗(yàn)證誤差最小的模型；同樣Díaz-Uriarte 等人[11]提出建立RF判別模型，該方法通過計(jì)算特征重要性評(píng)分，不斷剔除20%的變量，對(duì)剩余的特征建立RF判別模型，最后選擇所含變量相對(duì)最少，分類精度最高的RF 模型。通過以上研究看出，現(xiàn)階段對(duì)于高維樣本構(gòu)建RF 模型存在的特征相關(guān)性較差且存在冗余的問題，大部分研究集中剔除重要性偏低的屬性，但會(huì)造成構(gòu)建RF時(shí)，變量隨機(jī)抽樣存在多樣性不高的情況，導(dǎo)致RF 的泛化能力不強(qiáng)的問題。

基于上述問題，本文在建立RF 算法隨機(jī)抽取特征的多樣性的基礎(chǔ)上，消除特征相關(guān)和冗余特征的干擾，提出一種融合近似馬爾科夫毯的隨機(jī)森林優(yōu)化算法AMBRF（random forest model combining with approximate Markov blanket），利用近似馬爾科夫毯對(duì)原始特征構(gòu)建相似特征組，得到不同的特征組合，決策樹節(jié)點(diǎn)分裂前按照比例從每個(gè)相似特征組隨機(jī)抽取一定比例的特征，得到最佳特征子集，完成決策樹的構(gòu)建，重復(fù)上述過程多次，達(dá)到隨機(jī)森林規(guī)模，再根據(jù)改進(jìn)的OOB測(cè)試方法得到最終模型評(píng)價(jià)結(jié)果。

2 隨機(jī)森林

隨機(jī)森林（RF）是一種經(jīng)典的集成分類模算法，由多棵決策樹（decision tree，DT）構(gòu)成。RF對(duì)數(shù)據(jù)采取有放回隨機(jī)抽樣方法產(chǎn)生訓(xùn)練樣本，假設(shè)數(shù)據(jù)集D的樣本量為M，采用Bootstrap 有放回抽樣時(shí)，單個(gè)樣本被抽中的概率為1/M，通過抽取M次之后，單個(gè)樣本沒有被抽取到的概率為(1-1/M)M。只要樣本量M足夠大，數(shù)據(jù)集D會(huì)留下37%的樣本未被抽中，這部分稱為袋外數(shù)據(jù)（out of bag，OOB），用于模型評(píng)估。然后，訓(xùn)練樣本采用隨機(jī)抽樣的方法抽取特征子集，特征抽取個(gè)數(shù)一般為,n為數(shù)據(jù)集D的特征個(gè)數(shù)。構(gòu)建完多棵決策樹后形成隨機(jī)森林，通過對(duì)單個(gè)樣本結(jié)果投票的方式得到測(cè)試樣本的最終結(jié)果。隨機(jī)森林算法的偽代碼如下所示。

算法1隨機(jī)森林（RF）算法

3 近似馬爾科夫毯

針對(duì)RF 算法在高維數(shù)據(jù)集上表現(xiàn)出的不足，特征選擇是有效解決辦法之一。特征可以分為無關(guān)特征、弱相關(guān)且冗余、弱相關(guān)非冗余、強(qiáng)相關(guān)特四種[12]。好的特征選擇方法則需要去無關(guān)、弱相關(guān)且冗余，保留弱相關(guān)非冗余、強(qiáng)相關(guān)特征。就近似馬爾科夫毯[13（]approximate Markov blanket，AMB）方法給出如下定義：

設(shè)特征集合F、特征fi(fi∈F)、特征子集Mi?F(Mi≠fi)，分類的類別標(biāo)簽為C，概率為P。

定義1（強(qiáng)相關(guān)特征）特征fi是強(qiáng)相關(guān)特征時(shí)候，當(dāng)且僅當(dāng)[13]：

強(qiáng)相關(guān)特征是構(gòu)建隨機(jī)森林模型必不可少的，否則將影響數(shù)據(jù)分布。

定義2（弱相關(guān)特征）特征fi是弱相關(guān)特征時(shí)，當(dāng)且僅當(dāng)[14]：

定義3（無關(guān)特征）特征fi是無關(guān)特征當(dāng)且僅當(dāng)[14]：

最優(yōu)特征子集不能包含無關(guān)特征。

定義4（馬爾科夫毯）特征子集Mi是fi的馬爾科夫毯[15]當(dāng)且僅當(dāng)在給定Mi條件下面特征fi和FMi-{fi}獨(dú)立，即：

如果特征子集Mi是特征fi的馬爾科夫毯，則fi一個(gè)特征即可表達(dá)特征子集Mi的全部信息，也包括特征子集Mi對(duì)類別C的表達(dá)，即當(dāng)fi存在的時(shí)候，形成的Mi對(duì)分類沒有貢獻(xiàn)能力，可以選擇丟棄，視Mi為fi的冗余特征，強(qiáng)相關(guān)特征是不存在馬爾科夫毯。

定義5（近似馬爾科夫毯）特征fi是特征fj的近似馬爾科夫毯[16]的條件為：

其中，表達(dá)式J(fi,C)表示特征fi和類別C的相關(guān)性，J(fi,fj)表示fi和fj的相關(guān)性，本文中使用J(·)選擇最大信息系數(shù)[17（]maximal information coefficient，MIC）計(jì)算，如公式（1）所示：

其中，D={(f1i,f2i),i=1,2,…,n} 是有序?qū)?，X表示將f1的值域劃為X段，Y表示將f2的值域劃分為Y段，XY ＜B(n)表示網(wǎng)格數(shù)目不大于B(n)，分子I*(D,X,Y)表示不同X×Y網(wǎng)格劃分下的互信息最大值，分母ln(min(X,Y))表示將不同劃分下最大互信息歸一化的值。MIC(D)∈[0,1]，越接近1 表示兩者相關(guān)性越高，反之相關(guān)性越低。

定義6（相似特征）特征fj是fi特征的相似特征[18]的條件是：fi是fj的近似馬爾科夫毯。

fi和fj擁有相似的信息，都是對(duì)類別標(biāo)簽的同一部分信息進(jìn)行表達(dá)。

定義7（相似特征組）相似特征組是近似馬爾科夫毯fi和fj的所有相似特征的集合。

為了使得RF算法在隨機(jī)抽取到的特征與類別C具有相關(guān)性且滿足RF算法特征多樣性的要求，利用AMB構(gòu)造相似特征組。算法偽代碼如下所示。

算法2基于近似馬爾科夫毯的相似特征組聚類算法

4 融合近似馬爾科夫毯的隨機(jī)森林模型

RF 算法強(qiáng)大的分類能力離不開兩個(gè)隨機(jī)，隨機(jī)之一即為特征隨機(jī)抽取，RF在處理高維樣本時(shí)，極有可能抽到大部分特征都是無關(guān)特征或者弱相關(guān)冗余特征，將造成RF算法精度降低，泛化能力減小。AMB算法可有效地將相關(guān)特征聚類，形成相似特征組，即在相似特征組中，隨意抽取一定比例特征fi可代表該整組特征的全部信息，也可以包含對(duì)分類標(biāo)簽C的表達(dá)。融合近似馬爾科夫毯的隨機(jī)森林模型先利用AMB算法構(gòu)造相似特征組G={G1,G2,…,Gp}，再根據(jù)特征比例從每組特征Gi隨機(jī)抽取特征構(gòu)造RF算法單棵決策樹的劃分屬性。該模型構(gòu)造流程如圖1所示。

圖1融合近似馬爾科夫毯的隨機(jī)森林模型（AMBRF）流程圖，輸入樣本的特征維度是n，根據(jù)文獻(xiàn)[19]，單個(gè)決策樹分裂屬性個(gè)數(shù)定為，由AMB 算法得到p相似特征組，其中相似特征組Gi包含xi個(gè)特征，則按照比例應(yīng)從該相似特征組Gi中隨機(jī)抽取個(gè)屬性，按照同樣的思想從其他相似特征組中抽取部分屬性，構(gòu)建單棵決策樹。重復(fù)上述過程多次，直到滿足隨機(jī)森林規(guī)模后停止構(gòu)樹。融合近似馬爾科夫毯的隨機(jī)森林（AMBRF）算法偽代碼如下所示。

算法3融合近似馬爾科夫毯的隨機(jī)森林算法

當(dāng)樣本數(shù)量m足夠大的時(shí)候，理想情況下總會(huì)留下約37%的樣本抽不到而成為OOB 數(shù)據(jù)，但是現(xiàn)實(shí)中樣本有限，如果以O(shè)OB數(shù)據(jù)作為測(cè)試樣本，存在測(cè)試樣本不足的情況。因此對(duì)隨機(jī)森林的精確測(cè)試上，改變傳統(tǒng)OOB 測(cè)試的方法，提出樣本單棵決策樹輪空測(cè)試法進(jìn)行實(shí)驗(yàn)驗(yàn)證。具體思想為：遍歷所有樣本，取到樣本i之后，遍歷RF中所有決策樹，如果樣本i不作為第j棵決策樹的訓(xùn)練樣本，則進(jìn)行測(cè)試，得到該樣本的預(yù)測(cè)標(biāo)簽，直到所有決策樹預(yù)測(cè)完之后，投票表決樣本i的類別標(biāo)簽，直至所有樣本驗(yàn)證完成結(jié)束算法。

假設(shè)訓(xùn)練集樣本個(gè)數(shù)為m，構(gòu)建為k棵CART決策樹，特征數(shù)為n,原始隨機(jī)森林的時(shí)間復(fù)雜度為O(kmn(logm)2)[20]。本文提出的AMBRF算法共分成兩部分：構(gòu)建近似馬爾科夫毯相似特征組和建立隨機(jī)森林模型。對(duì)于第一部分，其時(shí)間主要花在計(jì)算兩個(gè)特征之間的相關(guān)性MIC值，時(shí)間復(fù)雜度為O(m2.4)[21]，因此本部分的時(shí)間復(fù)雜度為O(nm2.4)，第二部分為隨機(jī)森林構(gòu)建，設(shè)此階段需要從p個(gè)相似特征組中抽取部分特征，時(shí)間復(fù)雜度為O(kpmn(logm)2)，綜上可知，本文提出AMBRF算法的時(shí)間復(fù)雜度為兩部分之和，即O(nm2.4+kpmn(logm)2)。

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

5.1 實(shí)驗(yàn)數(shù)據(jù)

為了客觀且全面地驗(yàn)證本文提出的融合近似馬爾科夫毯的隨機(jī)森林模型（AMBRF）的優(yōu)勢(shì)，分析AMBRF在不同特征維度的數(shù)據(jù)集適應(yīng)性，選取UCI上12 組不同維度的數(shù)據(jù)集，表1為12組數(shù)據(jù)集的基本信息。

表1 UCI數(shù)據(jù)集Table 1 UCIdata set

5.2 評(píng)價(jià)指標(biāo)

本文提供的模型評(píng)價(jià)指標(biāo)有準(zhǔn)確率（Accuracy）、精確率（Precision）、召回率（Recall）、F 值，依據(jù)表2 所示的混淆矩陣，可以得到這些評(píng)價(jià)指標(biāo)的計(jì)算公式：

表2 混淆矩陣Table 2 Confusion matrix

為全面評(píng)價(jià)本文提出的AMBRF算法，從近似馬爾科夫毯構(gòu)建相似特征組時(shí)間、特征相關(guān)性的誤差平方和、AMBRF 和其他分類算法各類評(píng)價(jià)指標(biāo)等角度分析本文實(shí)驗(yàn)。

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

本實(shí)驗(yàn)設(shè)備采用Intel?CoreTMi7-10510U CPU @2.30 GHz，RAM 16.0 GB，64 位Windows10 操作系統(tǒng)，對(duì)以上12組實(shí)驗(yàn)數(shù)據(jù)，共設(shè)置3組對(duì)比實(shí)驗(yàn)，就以上4個(gè)評(píng)價(jià)指標(biāo)進(jìn)行對(duì)比分析。

實(shí)驗(yàn)一為構(gòu)建基于近似馬爾科夫毯的相似特征組所耗時(shí)間和均方根誤差RMSE分析，實(shí)驗(yàn)結(jié)果見表3所示。

表3 構(gòu)建基于AMB的相似特征組所耗時(shí)間和RMSE分析Table 3 Time and RMSE analysis of building AMB based feature similarity groups

由表3 的實(shí)驗(yàn)結(jié)果可知，RMSE 在各組數(shù)據(jù)上均保持在較低的水平，表明構(gòu)建基于AMB 的相似特征組和因變量的相關(guān)性較大，能很好地反映各個(gè)相似特征組對(duì)因變量的表達(dá)具有較高的全面性。

結(jié)合表1的數(shù)據(jù)信息內(nèi)容和表3的實(shí)驗(yàn)數(shù)據(jù)可以看出，構(gòu)建基于AMB 的相似特征組所耗時(shí)間跟樣本數(shù)量和特征數(shù)量存在明顯的關(guān)系，TT3600 數(shù)據(jù)集的樣本量達(dá)到3 600條，特征數(shù)量達(dá)4 813個(gè)，是12個(gè)數(shù)據(jù)集中規(guī)模最大，因此在構(gòu)建該數(shù)據(jù)集的相似特征組所耗時(shí)間為2 033.724 2 s。AFTS數(shù)據(jù)的樣本量雖然達(dá)到60 000條，但是因?yàn)槠涮卣鱾€(gè)數(shù)只有170個(gè)，因此所構(gòu)建的相似特征組就少，耗費(fèi)時(shí)間較少，只要42.437 7 s。

實(shí)驗(yàn)二為RF和AMBRF以及文獻(xiàn)[22]利用Fisher系數(shù)對(duì)特征排序，再按組隨機(jī)抽取特征的FisherRF三組算法的各種評(píng)價(jià)指標(biāo)對(duì)比實(shí)驗(yàn)，表4即對(duì)比實(shí)驗(yàn)的結(jié)果。

表4 RF和AMBRF算法的準(zhǔn)確性對(duì)比實(shí)驗(yàn)Table 4 Accuracy comparison test of RF and AMBRF algorithms

為了直觀地展示三個(gè)算法在12 組數(shù)據(jù)中的效果，繪制如圖2所示的柱狀圖。

圖2 各組數(shù)據(jù)集對(duì)比實(shí)驗(yàn)柱狀圖Fig.2 Comparison test histogram for each data set

根據(jù)表4和圖2所示，RF和FisherRF、AMBRF在各組數(shù)據(jù)上的對(duì)比實(shí)驗(yàn)結(jié)果可以看出，AMBRF 在高維數(shù)據(jù)中各項(xiàng)評(píng)價(jià)指標(biāo)上均有明顯的提升，具體分析如下：

（1）在German、breast_data、dermatology、HVWN 四組低維數(shù)據(jù)集上，AMBRF算法各項(xiàng)指標(biāo)均不如傳統(tǒng)RF和文獻(xiàn)方法FisherRF，但是三種算法在綜合指標(biāo)F 值上相差不大，甚至接近。因?yàn)樗慕M數(shù)據(jù)的維度相對(duì)較低，均在100 維以下，特征之間的冗余度不高，特征之間卻存在不相關(guān)性，所以FisherRF 更加適宜于這種情況，由實(shí)驗(yàn)結(jié)果也可反映出這種問題。而AMBRF 算法在構(gòu)建基于AMB 的相似特征組時(shí)，由于需要從每個(gè)特征組合中隨機(jī)抽取一定比例的特征個(gè)數(shù)，這將導(dǎo)致構(gòu)建每棵樹的特征多樣性減少，使得AMBRF算法的決策樹多樣性減弱，導(dǎo)致整個(gè)模型的效果偏低。

（2）對(duì)于Clean、AFTS、Arrhythmia、PSF 數(shù)據(jù)中，特征維度在100到1 000之間，這四組數(shù)據(jù)中，本文提出的AMBRF 和文獻(xiàn)FisherRF 各有所長(zhǎng)。在Clean、AFTS 這兩組數(shù)據(jù)中，AMBRF 的各項(xiàng)評(píng)價(jià)指標(biāo)高于FisherRF 算法；在Arrhythmia、PSF 這兩組數(shù)據(jù)中，F(xiàn)isherRF 的各項(xiàng)評(píng)價(jià)指標(biāo)高于AMBRF算法；為了驗(yàn)證在特征維度適中情況下，AMBRF 和FisherRF 算法的優(yōu)劣性，設(shè)置AMB構(gòu)建相似組對(duì)比實(shí)驗(yàn)，根據(jù)相似組個(gè)數(shù)、每個(gè)相似組的特征個(gè)數(shù)等角度解釋造成上述現(xiàn)象的原因。

如表5 所示，通過查看每個(gè)相似特征組的特征個(gè)數(shù)，以及每個(gè)數(shù)據(jù)集構(gòu)建的相似組個(gè)數(shù)可知，Clean數(shù)據(jù)集的每個(gè)相似組中均有多個(gè)屬性，特征間的冗余性較大，同理AFTS數(shù)據(jù)集的每個(gè)相似組也存在這種特征之間冗余性較大的情況。但在Arrhythmia、PSF 兩組數(shù)據(jù)上，構(gòu)建的相似組更多，存在多個(gè)相似組只有1 個(gè)特征的情況（Arrhythmia數(shù)據(jù)集構(gòu)建了18個(gè)特征組均只含有1個(gè)特征，PSF數(shù)據(jù)集構(gòu)建了6個(gè)特征組均只含有1個(gè)特征，而Clean和AFTS兩組數(shù)據(jù)集都只存在1個(gè)相似組含有1個(gè)特征，相似組內(nèi)特征越少冗余性越低），根據(jù)算法3可知，從這些相似特征組中抽取的特征子集較為單一，多樣性不高。相比于Clean和AFTS數(shù)據(jù)集，Arrhythmia、PSF 數(shù)據(jù)集特征維度較高，但是特征間的冗余性不大。綜上分析，AMBRF 更加適用于存在大量冗余特征的數(shù)據(jù)集，對(duì)特征存在高度冗余的數(shù)據(jù)集有更好的效果，也可反映出文獻(xiàn)算法FisherRF 可以解決特征無關(guān)特征對(duì)隨機(jī)森林構(gòu)建的干擾，對(duì)特征冗余性較高的數(shù)據(jù)集效果不明顯。

表5 AMB構(gòu)建相似組對(duì)比實(shí)驗(yàn)詳情Table 5 Details of comparative experiment of similar groups constructed by AMB

（3）在剩下的4 組數(shù)據(jù)中，ABD 數(shù)據(jù)的特征個(gè)數(shù)達(dá)到8 266 維，其余三組數(shù)據(jù)QAR、TT3600、DB 也都超過1 000維，此時(shí)改進(jìn)算法AMBRF的效果明顯優(yōu)于FisherRF和傳統(tǒng)RF。在數(shù)據(jù)集QAR 上，改進(jìn)算法AMBRF 的綜合評(píng)價(jià)指標(biāo)F 值為0.826 0，傳統(tǒng)RF 的F 值為0.665 2，F(xiàn)isherRF 的F 值0.815 3，均有所提升；在數(shù)據(jù)集TT3600上，AMBRF 的綜合評(píng)價(jià)指標(biāo)F 值為0.708 5，傳統(tǒng)RF 的F 值只有0.295 8，F(xiàn)isherRF 的F 值僅為0.390 2。在這組數(shù)據(jù)集上，AMBRF相較其他算法提升幅度達(dá)到31%；在數(shù)據(jù)集DB 上，改進(jìn)算法AMBRF 的綜合評(píng)價(jià)指標(biāo)F 值為0.938 5，傳統(tǒng)RF 的F 值為0.760 1，F(xiàn)isherRF 的F 值為0.845 6，AMBRF 相較其他算法提升幅度達(dá)到9%；數(shù)據(jù)集ABD 上，改進(jìn)算法AMBRF 的綜合評(píng)價(jià)指標(biāo)F 值為0.739 3，傳統(tǒng)RF 的F 值只有0.359 7，F(xiàn)isherRF 的F 值為0.550 8，AMBRF 相較其他算法提升幅度達(dá)到19%。通過上述分析知道，AMBRF 算法在TT3600、ABD 兩組數(shù)據(jù)集上表現(xiàn)異常突出，究其數(shù)據(jù)特點(diǎn)可知，這兩組數(shù)據(jù)均為文本分類任務(wù)構(gòu)建的詞袋模型，特征維度較高且稀疏，存在大量的冗余特征，因此通過隨機(jī)抽取相似特征組中特征可以有效避免傳統(tǒng)RF隨機(jī)抽取特征形成冗余特征子集。

綜上所述，本文提出的AMBRF算法相比于其他兩種算法具有更好的實(shí)驗(yàn)效果，尤其是對(duì)高維數(shù)據(jù)，或者是存在高度冗余特征的數(shù)據(jù)中具有明顯的優(yōu)勢(shì)。

實(shí)驗(yàn)三為RF、FisherRF和AMBRF三組算法隨機(jī)森林構(gòu)建時(shí)間對(duì)比實(shí)驗(yàn)（不包括相似特征組構(gòu)建時(shí)間），表6展示三個(gè)算法對(duì)比實(shí)驗(yàn)的結(jié)果。

表6 構(gòu)建隨機(jī)森林的時(shí)間對(duì)比實(shí)驗(yàn)Table 6 Time comparison test of constructing random forest 單位：s

由表6 可知，當(dāng)特征維度比較低時(shí)，RF、FisherRF、AMBRF 三種算法在構(gòu)建隨機(jī)森林消耗時(shí)間更加接近。特征維度較高時(shí)，RF 和FisherRF 在構(gòu)建森林時(shí)所耗時(shí)間整體上低于改進(jìn)算法AMBRF 構(gòu)建森林的時(shí)間。這是因?yàn)槭褂肁MBRF構(gòu)建隨機(jī)森林的時(shí)候，要求先構(gòu)建相似特征組，構(gòu)建單棵決策樹的時(shí)候需要遍歷所有的相似組特征，按比例從其中抽取部分特征，合成最優(yōu)特征子集，因此構(gòu)建100 棵樹時(shí)，需要重復(fù)上述循環(huán)100 次，導(dǎo)致改進(jìn)算法AMBRF 在建立隨機(jī)森林時(shí)耗費(fèi)的時(shí)間比其他兩種算法更長(zhǎng)。由AMBRF 的時(shí)間復(fù)雜度O(nm2.4+kpmn(logm)2)可知，耗時(shí)的長(zhǎng)短主要由樣本數(shù)量m決定，當(dāng)樣本量較大時(shí)，構(gòu)建隨機(jī)森林消耗時(shí)間更長(zhǎng)，由TT3600 數(shù)據(jù)集的時(shí)間對(duì)比實(shí)驗(yàn)可以明顯看出，AMBRF構(gòu)建隨機(jī)森林時(shí)間為4 374.47 s，是其他兩種算法的8 倍，從實(shí)驗(yàn)角度驗(yàn)證本文分析的AMBRF 算法時(shí)間復(fù)雜度的正確性。

6 總結(jié)

針對(duì)特征的相關(guān)和冗余，影響隨機(jī)森林（RF）隨機(jī)抽取特征的質(zhì)量等問題。本文提出一種融合近似馬爾科夫毯（AMB）的隨機(jī)森林算法（AMBRF），該算法先利用AMB 構(gòu)建多個(gè)相似特征組；再?gòu)拿總€(gè)相似組中按照比例抽取特征形成單棵決策樹的最佳特征子集，重復(fù)上述過程多次。該算法利用AMB消除特征間的相關(guān)性和冗余性，提高隨機(jī)抽取特征的質(zhì)量。通過大量驗(yàn)證性實(shí)驗(yàn)得出本文提出的改進(jìn)算法AMBRF優(yōu)于傳統(tǒng)RF算法及FisherRF算法，對(duì)高維樣本和具有冗余特征的樣本更加切實(shí)可行。但是，對(duì)于特征數(shù)較少的數(shù)據(jù)集會(huì)增加各決策樹之間的相關(guān)性，使決策樹不具備多樣性，效果不佳；AMBRF 構(gòu)建隨機(jī)森林的復(fù)雜度明顯高于其他兩種算法，使得運(yùn)行時(shí)間較大；在今后的工作中，將重點(diǎn)考慮這兩個(gè)問題。