鐘雯靜 ，張偉勁 ，何雪梅 ，常睿春

（1.成都理工大學(xué) 數(shù)學(xué)地質(zhì)四川省重點(diǎn)實(shí)驗(yàn)室，四川 成都 610059；2.成都理工大學(xué) 成都理工大學(xué)數(shù)字胡煥庸線研究院，四川成都 610059；3.成都理工大學(xué) 信息科學(xué)與技術(shù)學(xué)院（網(wǎng)絡(luò)安全學(xué)院），四川 成都 610059）

隨機(jī)森林算法具有較好的分類性能，一直是廣大研究者們的熱門研究對象，被廣泛應(yīng)用于數(shù)據(jù)挖掘、數(shù)據(jù)分析領(lǐng)域。隨機(jī)森林的改進(jìn)主要體現(xiàn)在以下幾個方面：(1)數(shù)據(jù)的預(yù)處理；(2)對RF中生成的決策樹改進(jìn)；(3)對投票方式的改進(jìn)。但是由于數(shù)據(jù)集的復(fù)雜性，盡管隨機(jī)森林具備較好的性能，仍然容易陷入過擬合或局部最優(yōu)的情況?；诖耍疚奶岢隽艘环N耦合可能性C-means聚類的RF算法，先用AUC值對傳統(tǒng)RF的決策樹進(jìn)行評估，選出AUC值高的樹，再進(jìn)行可能性C-means(pCM)聚類，選取每一類中AUC值最大的決策樹組成新的子森林。這種改進(jìn)方法既能夠舍棄分類性能差的決策樹，又能改善相似性高的決策樹出現(xiàn)分類錯誤的情況，在分類精度和分類時間上皆優(yōu)于經(jīng)典SVM和傳統(tǒng)RF算法。

1. 算法改進(jìn)

1.1 可能性C-means聚類(PCM)

本文采用的聚類方法是pCM聚類算法，是基于模糊C-means聚類(FCM)的一個改進(jìn)。以下是有關(guān)pCM算法的介紹：

pCM目標(biāo)函數(shù)：

N為樣本個數(shù)，C為聚類中心個數(shù)(2≤C≤N)；m為加權(quán)指數(shù)且m∈[1,∞)，關(guān)于m的最佳取值目前還沒有充分的理論研究作為支撐，一般情況下取m=1.5；為每個聚類的中心，表示樣本到聚類中心的距離；η是由FCM算法得出U,C后直接計算作為定值，通常取K=1：表示各個樣本到每個聚類中心距離的加權(quán)平方和。越小表示聚類效果越好。

1.2 評估指標(biāo)

本文將AUC值作為隨機(jī)森林算法里單棵CART決策樹分類精度的評估指標(biāo)，AUC值越高，模型的分類性能越好。

AUC值的計算公式：

其中表示第條樣本的序號，M、N分別表示正、負(fù)樣本的個數(shù)，表示只加正樣本的序號。

1.3 PCM-RF模型

傳統(tǒng)的隨機(jī)森林算法具有泛化能力強(qiáng)、擬合效果好、對部分缺失值不敏感等優(yōu)點(diǎn)。為提升分類精度，可適量增加RF中的決策樹數(shù)量，但此種方法也有弊端：如分類時間會增加且易陷入過擬合。生成的決策樹分類性能也有優(yōu)劣之分，若某棵樹分類錯誤，則其他與之相似度高的樹也會獲得錯誤的分類?；诖?，本文提出了pCM-RF算法：計算傳統(tǒng)RF中每棵CART樹的AUC值及AUC值的中位數(shù)Me，篩選出q棵AUC值高的決策樹，對選出的樹進(jìn)行pCM聚類，從每一類中選取分類精度最高的樹構(gòu)建新的隨機(jī)森林。將中位數(shù)Me作為選取標(biāo)準(zhǔn)可使得子森林中樹的數(shù)量不會超過原始森林的1/2，達(dá)到簡化決策樹數(shù)量目的，pCM-RF算法不僅能獲得更高的分類精度且能節(jié)約分類時間。

2. 實(shí)驗(yàn)設(shè)計

2.1 數(shù)據(jù)集

UCI數(shù)據(jù)庫是由University of CaliforniaIrvine提出的標(biāo)準(zhǔn)數(shù)據(jù)庫，本文實(shí)驗(yàn)用到的數(shù)據(jù)集皆來自于此，它們分別是Winequality-red,Abalone,Haberman’s Survival.Winequality-red包含4898個樣本，12個特征，共11類；Abalone包含4177個樣本，8個特征，共29類；Haberman’s Survival包含306個樣本，2個特征，共3類。

2.2 實(shí)驗(yàn)過程

由于經(jīng)典SVM算法具有良好的學(xué)習(xí)能力且分類性能好，是機(jī)器學(xué)習(xí)里占據(jù)主導(dǎo)地位的算法之一，因此本文在把pCMRF算法與傳統(tǒng)RF算法分類性能作對比的同時，也與經(jīng)典SVM算法作了對比分析。本文實(shí)驗(yàn)以分類精度作為算法分類效果的評估指標(biāo)，采用10折交叉驗(yàn)證的辦法，將數(shù)據(jù)均分為10份，輪流將9份數(shù)據(jù)作訓(xùn)練集，1份數(shù)據(jù)作測試集，讓所有的數(shù)據(jù)都有同等的機(jī)會作為訓(xùn)練集和測試集，最后取10次實(shí)驗(yàn)之后的結(jié)果均值作為模型性能的評估。實(shí)驗(yàn)流程如下：

輸入樣本數(shù)Y，聚類中心數(shù)C，權(quán)重指數(shù)m，最大迭代次數(shù)Max_iter，迭代閾值ε；

求出：

通過對聚類中心C和隸屬度矩陣U的不斷更新，計算目標(biāo)函數(shù)J(U,C)當(dāng)兩次結(jié)果的變化量小于迭代閾值ε時，迭代停止，輸出隸屬度矩陣U和聚類中心數(shù)C。

(4)從每一類選出AUC值最高的樹構(gòu)成新的子森林，得到pCM-RF模型。

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

用pCM-RF算法對3.1中三個數(shù)據(jù)集進(jìn)行分類，得到各自的分類精度和分類時間，再用經(jīng)典SVM和傳統(tǒng)RF算法對數(shù)據(jù)分類的結(jié)果作為對比實(shí)驗(yàn)。具體的分類精度與分類時間見圖1和表1。

圖1 不同算法下的分類精度

表1 不同算法下的分類精度和分類時間

從實(shí)驗(yàn)結(jié)果可以看出，pCM-RF算法在分類精度和分類時間兩方面皆明顯優(yōu)于傳統(tǒng)RF和SVM算法。與經(jīng)典SVM算法相比，分類精度提升了8.6%～12.6%，分類時間減少了57.7%～66.7%；與傳統(tǒng)RF算法相比，分類精度提升了3.6%～5.6%，分類時間減少了32.7%～40%。

2.4 分類精度分析

隨機(jī)森林算法中某些參數(shù)會影響算法對數(shù)據(jù)分類的精度，上述實(shí)驗(yàn)僅對pCM-RF算法與經(jīng)典SVM和傳統(tǒng)RF算法作了一個橫向的分類精度比較，下面將調(diào)整pCM-RF中CART決策樹的深度作縱向分析，通過不斷調(diào)整樹的深度得到不同的分類精度，分析樹的深度對最終分類精度的影響。

圖2 不同深度下PCM-RF的分類精度變化

從圖2中可以看出，當(dāng)模型中CART決策樹的深度大概在30～60這個范圍內(nèi)時，模型的分類性能達(dá)到最優(yōu)。當(dāng)樹的深度為60時，在Abalone數(shù)據(jù)集上出現(xiàn)了一個波動，這是由于pCM-RF在進(jìn)行分類時，由于隨機(jī)性會出現(xiàn)比上一次分類效果更差的情況，但是這個波動非常微小，屬于正常范疇。

從圖3中可以看出隨著深度的增加，模型的擬合效果逐漸優(yōu)化，但是當(dāng)深度超過50之后，模型在訓(xùn)練集上的均方誤差逐漸減小，在測試集上的均方誤差逐漸增大。由此可推斷，當(dāng)樹的深度增加到一定的程度，模型會陷入過擬合的現(xiàn)象，所以對深度參數(shù)的設(shè)置應(yīng)控制在30～50這個范 圍內(nèi)。

圖3 不同深度下PCM-RF的擬合效果

3. 結(jié)語

本文以分類精度和分類時間作為模型評估指標(biāo)，通過選出高精度的子樹，對子樹進(jìn)行pCM聚類，最后選出精度高、相似度低的樹構(gòu)建新模型，即pCM-RF算法。通過對UCI數(shù)據(jù)庫中的3個數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，證明了經(jīng)過改進(jìn)后的隨機(jī)森林算法在分類精度和分類時間方面都要優(yōu)于傳統(tǒng)的隨機(jī)森林，說明作此改進(jìn)提升了隨機(jī)森林的分類性能，同時也節(jié)約了分類時間。最后通過調(diào)整pCM-RF模型中決策樹的深度，分析其對分類精度的影響，根據(jù)實(shí)驗(yàn)結(jié)果可知，當(dāng)樹的深度不斷增加，模型的分類效果會有所優(yōu)化，但是樹的深度不能過深，否則模型容易陷入過擬合。

由于聚類方式和模型性能評估指標(biāo)有許多，可選取別的聚類方式和評估指標(biāo)再次實(shí)驗(yàn)。因此接下來的研究工作應(yīng)從以上兩個方面入手，即尋找更優(yōu)的聚類方式和選用其他精度評估指標(biāo)進(jìn)行實(shí)驗(yàn)再做比較分析。