基于高維特征聚類優(yōu)化的隨機(jī)森林算法研究7

*王 博，莊暨軍，熊 軍，羅小臣

（1. 井岡山大學(xué)電子與信息工程學(xué)院，江西，吉安 343009；2. 井岡山大學(xué)學(xué)報(bào)編輯部，江西，吉安 343009；3. 井岡山大學(xué)計(jì)財(cái)處，江西，吉安 343009；4. 井岡山大學(xué)圖書館，江西，吉安 343009）

0 引言

隨機(jī)森林算法（RF）算法是集成學(xué)習(xí)（Ensemble Learning）算法中的典型代表之一。算法基于統(tǒng)計(jì)學(xué)習(xí)理論，采用自助重采樣技術(shù)（Bootstrap Sampling）

從訓(xùn)練樣本中抽取多個(gè)樣本集，利用抽取的樣本集分別構(gòu)建決策樹模型，然后將若干個(gè)決策樹聚集在一起，通過(guò)多數(shù)投票或取平均得到最終結(jié)果。決策樹算法與集成學(xué)習(xí)思想是構(gòu)建RF 算法的基石。

隨機(jī)森林算法具有能容忍高數(shù)據(jù)噪音，同時(shí)也具有高預(yù)測(cè)精度，而被眾多學(xué)者廣泛運(yùn)用到社會(huì)中各個(gè)領(lǐng)域。比如文獻(xiàn)[1]中，Chai.Z 將隨機(jī)森林算法運(yùn)用到工業(yè)故障分類，提高了故障檢測(cè)精度；文獻(xiàn)[2]中，Cheng.Li 在交通運(yùn)輸領(lǐng)域中運(yùn)用隨機(jī)森林算法，極大提升了運(yùn)輸效率和承載率；ZAFARI.A 在文獻(xiàn)[3]中的評(píng)估管理領(lǐng)域運(yùn)用隨機(jī)森林算法，得到了更加準(zhǔn)確的評(píng)估預(yù)測(cè)結(jié)果。但即便如此，隨機(jī)森林算法仍然存在自身的缺陷：在對(duì)高維度特征進(jìn)行篩選和選取的有效率比較低、對(duì)動(dòng)態(tài)數(shù)據(jù)聚類的泛化誤差估值較大。針對(duì)這些缺陷，國(guó)內(nèi)外學(xué)者對(duì)隨機(jī)森林算法做了許多改進(jìn)優(yōu)化的研究。在文獻(xiàn)[4]中，王德軍等將基于時(shí)間序列數(shù)據(jù)對(duì)隨機(jī)森林分類算法優(yōu)化，結(jié)果提高了10%的分類精度；文獻(xiàn)[5]中，劉曙光等提出的多時(shí)相遙感數(shù)據(jù)結(jié)合隨機(jī)森林特征變量?jī)?yōu)化方法，將總體分類精度提高了近9%；王磊等在文獻(xiàn)[6]中采用聚類欠采樣加權(quán)隨機(jī)森林算法，提高了預(yù)測(cè)精度。以上的算法優(yōu)化對(duì)提高隨機(jī)森林算法的預(yù)測(cè)精度和分類精度都取得了很大進(jìn)展，但是在對(duì)高維數(shù)據(jù)劃分特征度量時(shí)如何提高聚類性能，目前研究比較欠缺。

特征選擇是從原始特征集中抽取部分特征，使其能達(dá)到降低特征維度提高算法性能的效果。算法在構(gòu)建決策樹時(shí)，會(huì)隨機(jī)的抽取部分特征，利用特征評(píng)估方法選出其中分類效果最好，即最重要的特征作為分裂特征，這為隨機(jī)森林進(jìn)行特征選擇奠定了理論基礎(chǔ)。但由于隨機(jī)森林算法在構(gòu)建過(guò)程中引入了特征隨機(jī)選擇策略，所以單純的根據(jù)特征在決策樹節(jié)點(diǎn)被選為分裂特征的次數(shù)來(lái)判斷特征是否重要的方法是不可取的。Breiman 在對(duì)隨機(jī)森林進(jìn)行系統(tǒng)的分析后，提出使用袋外數(shù)據(jù)內(nèi)部估計(jì)方法監(jiān)測(cè)隨機(jī)森林的誤差，并將其作為隨機(jī)森林度量特征重要性的依據(jù)。

現(xiàn)嘗試用一種高維聚類優(yōu)化算法，針對(duì)高維特征數(shù)據(jù)集，采用K 均值聚類和模糊C 均值聚類相結(jié)合的方法，對(duì)數(shù)據(jù)集的高維特征聚類，傳統(tǒng)隨機(jī)森林算法進(jìn)行優(yōu)化，通過(guò)計(jì)算DBI、根據(jù)相關(guān)性閾值排序，篩選出高維特征簇群，以達(dá)到提高高維特征數(shù)據(jù)集聚類效果的目的。實(shí)驗(yàn)結(jié)果證明，該方法是切實(shí)有效的。

1 傳統(tǒng)隨機(jī)森林算法

傳統(tǒng)隨機(jī)森林算法中，對(duì)高維數(shù)據(jù)特征度量時(shí)運(yùn)用的方法主要是隨機(jī)置換法。即在首先對(duì)高維數(shù)據(jù)的所有相關(guān)特征進(jìn)行隨機(jī)置換，置換后再進(jìn)行迭代測(cè)試，根據(jù)測(cè)試結(jié)果的誤差變化越大，則代表該特征的相關(guān)程度越高。

從以上步驟可以看出，隨著訓(xùn)練數(shù)據(jù)集的不斷增加，高維數(shù)據(jù)特征需要的訓(xùn)練時(shí)間、空間性能呈指數(shù)級(jí)增加，最終將造成訓(xùn)練速度緩慢、訓(xùn)練效果降低的后果。本文將采取高維聚類的方法，對(duì)傳統(tǒng)算法加以優(yōu)化，以提高傳統(tǒng)隨機(jī)森林算法在高維數(shù)據(jù)訓(xùn)練方面的性能。

2 基于高維聚類優(yōu)化的隨機(jī)森林算法

2.1 聚類方法介紹

本文采用KM 聚類（K 均值聚類）、FCM 聚類（模糊C-均值）兩種聚類方法相結(jié)合，根據(jù)樣本相似度劃分族群，對(duì)高維數(shù)據(jù)集特征進(jìn)行聚類。根據(jù)這兩種聚類算法得到的DBI（聚類有效性）值，取DBI 最小值為最佳類數(shù)。

2.1.1 KM 聚類

根據(jù)文獻(xiàn)[9]的研究，當(dāng)DBI 的值與聚類效果成正比，所以，當(dāng)DBI 值最小時(shí)，表示此時(shí)的聚類類數(shù)為最佳值。

2.2 HDFC-RF 算法

2.2.1 HDFC-RF 特征評(píng)估算法

2.2.2 HDFC-RF 算法流程圖

根據(jù)上述的介紹，將HDFC-RF 算法流程歸納如下：

圖1 HDFC-RF 算法流程圖Fig.1 HDFC-RF algorithm flow chart

將文獻(xiàn)[10]和文獻(xiàn)[11]中的高維數(shù)據(jù)集Colon Tumor 作為輸入數(shù)據(jù)集。Colon Tumor 屬于生物數(shù)據(jù)集，在同等樣本規(guī)模下，具有更高維的數(shù)據(jù)特征，符合本文HDFC-RF 算法對(duì)高維數(shù)據(jù)特征聚類的訓(xùn)練數(shù)據(jù)集要求。

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental data set

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

3.1 實(shí)驗(yàn)準(zhǔn)備

3.2 實(shí)驗(yàn)結(jié)果

將本文的HDFC-RF 算法與傳統(tǒng)的RF 算法、文獻(xiàn)[6]中的FSRF 算法進(jìn)行比較，為了得到更穩(wěn)定的結(jié)果，將三種算法運(yùn)行30 次的均值作為最終結(jié)果。實(shí)驗(yàn)結(jié)果對(duì)比如圖2、圖3 所示：

圖2 HDFC-RF、FSRF、RF 聚類效果對(duì)比Fig.2 Training effect comparison of HDFC-RF&FSRF&RF

圖.3 HDFC-RF、FSRF、RF 訓(xùn)練時(shí)間對(duì)比Fig.3 Training Time comparison of HDFC-RF&FSRF&RF

根據(jù)以上兩圖可以得到如下結(jié)論：

1）圖2 表明，在數(shù)據(jù)集訓(xùn)練中，HDFC-RF 算法在重要特征集的前10 個(gè)特征就達(dá)到了最佳的分類效果，而傳統(tǒng)的RF 算法和FSRF 算法則分別需要近40 和60 個(gè)特征?？梢娡葮颖緮?shù)的情況下，HDFC-RF 能達(dá)到更好的聚類效果。

2）圖3 表明，在數(shù)據(jù)集訓(xùn)練的時(shí)間上，HDFC-RF 訓(xùn)練時(shí)間為8 s，而FSRF 和RF 算法分別為15 s 和40 s，顯然HDFC-RF 訓(xùn)練所需的時(shí)間比FSRF、RF 都要明顯縮短，速度得到了提高，說(shuō)明HDFC-RF 算法具有更加高效的訓(xùn)練效率。

4 結(jié)論

針對(duì)傳統(tǒng)的隨機(jī)森林算法在對(duì)高維特征數(shù)據(jù)集計(jì)算速度慢、聚類效果不佳的缺陷，提出了一種基于高維特征聚類的隨機(jī)森林算法（HDFC-RF），即在提取高維特征數(shù)據(jù)集聚類時(shí)，采用K 均值聚類和模糊C-均值結(jié)合的算法，通過(guò)計(jì)算DBI 指標(biāo)和對(duì)高維特征簇排序后，與相關(guān)性閾值δ比較，得到最終的高維特征序列。實(shí)驗(yàn)結(jié)果表明，經(jīng)過(guò)本文HDFC-RF 優(yōu)化后的隨機(jī)森林算法，具有更好的聚類效果、訓(xùn)練速度也更快，具備良好的可行性。