一種模型決策森林算法*

尹 儒，門昌騫，王文劍

1.山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，太原030006

2.山西大學(xué) 計算智能與中文信息處理教育部重點實驗室，太原030006

1 引言

近年來，集成學(xué)習(xí)因其良好的泛化能力在很多現(xiàn)實領(lǐng)域得到了廣泛的應(yīng)用：智能交通中的行人與車輛檢測；視頻或者圖像中出現(xiàn)的物體識別、動作檢測；生物信息學(xué)研究中的癌癥預(yù)測、基因組功能預(yù)測；數(shù)據(jù)挖掘領(lǐng)域中的數(shù)據(jù)流挖掘等。隨機(jī)森林是集成學(xué)習(xí)的代表算法之一，它將多棵決策樹的結(jié)果進(jìn)行集成并以投票或者其他的方式將最后結(jié)果輸出，具有簡單高效等優(yōu)點。

在集成學(xué)習(xí)的研究中，國內(nèi)外學(xué)者先后提出了很多行之有效算法。這些算法主要有兩種思路：一種是基學(xué)習(xí)器之間存在互相依賴關(guān)系的Boosting 方法；另一種是基學(xué)習(xí)器相互獨立，沒有任何依賴關(guān)系的Bagging 方法。

1979 年Dasarathy 和Sheela 首次提 出了集成學(xué) 習(xí)的思想[1]，隨后有學(xué)者證明弱分類器集成后形成的分類器比其中任一基分類器的分類效果都好[2-3]。1997年，F(xiàn)reund 和Schapire 在Boosting 思想的基礎(chǔ)上提出了Adaboost（adaptive Boosting）算法[4]。該算法能夠有效提升學(xué)習(xí)器的精度，并且它將集成的思想擴(kuò)張到多分類問題和回歸問題中。但Adaboost 算法也存在一定缺陷，比如對噪聲比較敏感等[5-6]。2001 年，F(xiàn)riedman 提出基于殘差的GBDT（gradient Boosting decision tree）算法[7-8]。GBDT 算法具有預(yù)測精度高、適合低維數(shù)據(jù)等優(yōu)點，但當(dāng)數(shù)據(jù)維數(shù)高或者數(shù)據(jù)量大的時候，算法時間復(fù)雜度會不斷變高。針對GBDT 的缺點，Chen 等人于2016 年提出了XGBoost（extreme gradient Boosting）算法[9]。該算法高效實現(xiàn)了梯度提升，加快了模型訓(xùn)練速度，提高了算法的預(yù)測精度。之后，微軟在2017 年的NIPS（neural information processing systems）大會上提出了比XGBoost 更快的LightGBM[10]算法。

1996 年，Breiman 提出了Bagging（bootstrap aggregation）算法[11]。Bagging 算法能夠通過降低基學(xué)習(xí)器的方差來改善泛化誤差，在大規(guī)模數(shù)據(jù)集上的分類性能較好。這些優(yōu)點使得Bagging 算法在生物信息學(xué)[12]和遙感領(lǐng)域[13]得到了廣泛的應(yīng)用。2001 年，Breiman 提出了隨機(jī)森林（random forest，RF）算法[14]，它將Bagging 的理論與隨機(jī)子空間方法[15]相結(jié)合。隨機(jī)森林將決策樹作為基學(xué)習(xí)器，利用重采樣技術(shù)從訓(xùn)練集中生成不同的樣本子集，從而訓(xùn)練出不同的決策樹，最后使用投票策略進(jìn)行預(yù)測。2006 年，Rodriguez 等人提出了一種旋轉(zhuǎn)森林算法（rotation forests）[16]，該方法用PCA（principal component analysis）將樣本屬性進(jìn)行映射后生成隨機(jī)森林。2008 年，Liu等人提出了一種適用于連續(xù)數(shù)據(jù)異常檢測的iForest（isolation forest）[17]，這種方法具有較低的時間復(fù)雜度和較高的準(zhǔn)確度。2013 年，Ye 等人提出了一種層次隨機(jī)森林（stratified random forest）[18]，該方法利用Fisher 判別將樣本屬性分為兩部分來生成隨機(jī)森林。2016 年，Wang 等人提出了伯努利隨機(jī)森林（Bernoulli random forests）[19]，該方法是用兩個伯努利分布來選擇最優(yōu)特征與其對應(yīng)的最優(yōu)分裂值。2017年，Zhou等人提出了一種深度隨機(jī)森林（gcForest）[20]，這種方法采取了級聯(lián)森林和多粒度掃描策略來生成隨機(jī)森林。

模型決策樹（model decision tree，MDT）[21]是一種加速的決策樹算法。它并沒有像傳統(tǒng)決策樹一樣將遞歸程序執(zhí)行完，因此其訓(xùn)練速度會比傳統(tǒng)決策樹快，當(dāng)然分類錯誤率與傳統(tǒng)決策樹相比也不會太差，并且在有的數(shù)據(jù)集上誤差比傳統(tǒng)決策樹更小，但是隨著非純偽葉結(jié)點規(guī)模的增大，模型決策樹的精度也在下降。本文針對MDT 存在的缺點，利用隨機(jī)森林的優(yōu)點，提出了一種模型決策森林（model decision forest，MDF）算法。

2 模型決策森林

2.1 MDT 簡介

模型決策樹是一種加速的決策樹算法，它能夠在算法精度不損失或者損失很小的情況下，提高決策樹的訓(xùn)練效率，并且具備一定的抗過擬合能力。

MDT 的構(gòu)建過程為：首先根據(jù)當(dāng)前需要分裂的結(jié)點上訓(xùn)練數(shù)據(jù)的最優(yōu)特征來進(jìn)行劃分，然后在決策樹增長到一定程度時停止，此時得到的是一棵不完全決策樹，其最深層上的結(jié)點或者是葉結(jié)點，或者是非葉結(jié)點，但包含的樣本屬于同一類別（稱之為純偽葉結(jié)點），或者是非純偽葉結(jié)點。最后在不完全決策樹的非純偽葉結(jié)點上增加一個簡單分類模型，生成模型決策樹。

2.2 MDF 基本原理

模型決策森林將模型決策樹作為基分類器，因此MDF 算法的第一階段是生成多棵不同的模型決策樹（即構(gòu)建MDT）。在多棵樹的生成過程中，通過旋轉(zhuǎn)矩陣來產(chǎn)生不同的樣本子集進(jìn)而生成不同的模型決策樹。設(shè)給定的訓(xùn)練集為D={(x1,y1),(x2,y2),…,(xn,yn)}，其中，xi∈Xn×N,yi∈Yn×1，n為訓(xùn)練集的樣本個數(shù)，N為特征個數(shù)，特征集設(shè)為F，基分類器的個數(shù)為L。旋轉(zhuǎn)矩陣的計算方式如下：

（1）將特征集F隨機(jī)分割成S份，則每份包含的特征個數(shù)為M=N/S。

（2）令Fi,j表示訓(xùn)練第i個分類器所用到的第j個特征子集。從訓(xùn)練集Xi,j的所有樣本中隨機(jī)抽取一定比例的樣本生成，在Fi,j中的M個特征上運行PCA 算法，并把得到的主成分系數(shù)保存下來。這里只在上進(jìn)行PCA 轉(zhuǎn)換是為了盡量避免在不同的基分類器上可能選擇相似的特征子集而產(chǎn)生相似系數(shù)的情況。

（3）最后將得到的所有系數(shù)進(jìn)行組合，得到矩陣Ri，如式（1）所示。

（4）將Ri根據(jù)F中的特征順序重新排序，得到最終的旋轉(zhuǎn)矩陣。

假設(shè)訓(xùn)練數(shù)據(jù)有K個類，Ck指D中屬于第k類的樣本子集。則給定的訓(xùn)練數(shù)據(jù)D對應(yīng)的基尼指數(shù)為：

對于二分類問題(K=2)，訓(xùn)練數(shù)據(jù)集D根據(jù)某一特征A是否取某一可能值a被分割為D1和D2兩部分，即：

因此在特征A的條件下，集合D的基尼指數(shù)為：

Gini(D,A)表示經(jīng)A=a分割之后集合D的不確定性，值越小表示訓(xùn)練集的不確定性越小，相反越大則代表訓(xùn)練集的不確定性越大。

根據(jù)式（4）分別計算出每個特征的所有可能取值對訓(xùn)練集的基尼指數(shù)，然后對比它們的大小，選出其中最小值作為最優(yōu)特征和最優(yōu)切分點。

MDF 算法的第二階段是生成集成模型，本文采用簡單平均法將每棵模型決策樹的分類結(jié)果結(jié)合，具體公式如下：

2.3 MDF 算法

本文提出的模型決策森林算法是通過旋轉(zhuǎn)矩陣得到不同的樣本子集，從而訓(xùn)練出不同的模型決策樹，再將不同的模型決策樹集成得到最終的分類器。具體步驟如下：

算法1MDF 算法

初始化：訓(xùn)練數(shù)據(jù)集D，測試數(shù)據(jù)集T，樹的棵數(shù)為L，特征集F，隨機(jī)分割份數(shù)S。

步驟1將F分割為S份，則每份包含的特征個數(shù)為M=N/S。從訓(xùn)練集Xi,j的所有樣本中隨機(jī)抽取一定比例的樣本生成，在Fi,j中的M個特征上運行PCA 算法，并把得到的主成分系數(shù)保存下來。將得到的所有系數(shù)按照式（1）組合，并重新排序，得到旋轉(zhuǎn)矩陣。

步驟2計算，得到不同的訓(xùn)練樣本子集。在樣本子集上根據(jù)式（4）計算基尼指數(shù)，選擇最佳分裂點，直到非純偽葉結(jié)點的規(guī)模小于給點參數(shù)時停止建樹，然后在非純偽葉結(jié)點上用一個簡單分類模型構(gòu)建成模型決策樹。

步驟3重復(fù)步驟1 和步驟2，直到模型決策樹的棵數(shù)達(dá)到L。

步驟4將得到的L棵樹根據(jù)式（5）集成起來得到模型決策森林。

步驟5算法結(jié)束。

3 實驗結(jié)果分析

3.1 實驗環(huán)境及實驗數(shù)據(jù)

本實驗使用10 個典型的UCI 二分類數(shù)據(jù)集進(jìn)行測試，如表1 所示。實驗結(jié)果為每個數(shù)據(jù)集運行多次求出的均值，以盡量避免實驗結(jié)果的偶然性。實驗中采用的計算機(jī)硬件配置為：CPU Core i7-3 770，3.40 GHz，內(nèi)存8.0 GB。

Table 1 Datasets used in experiments表1 實驗數(shù)據(jù)集

實驗中基分類器模型決策樹的參數(shù)設(shè)置為高斯核，t設(shè)置為0.1。為了方便實驗，在模型決策森林的計算中沒有固定特征集F隨機(jī)分割的份數(shù)S，反而固定了每份包含的特征個數(shù)為M，根據(jù)公式S=N/M，即可求得S的大小。這兩者任意給出其中之一可求得另一值，且無論先給出哪一值對實驗結(jié)果都不影響，故本文為便于實驗先給出M。實驗中可能會遇到數(shù)據(jù)集的特征數(shù)無法被M整除的情況，本文選擇將整除M后的余數(shù)個特征作為最后一個特征子集。例如：訓(xùn)練集8 維，M=3，那么按照本文方法所有特征分為3 個特征子集，包括兩個含有3 個特征的子集和一個含有2 個特征的子集。

3.2 實驗結(jié)果與分析

（1）參數(shù)L對實驗結(jié)果的影響

在隨機(jī)森林中樹的數(shù)量的變化會影響隨機(jī)森林的精度。當(dāng)樹較少時，RF 的分類錯誤率比較高，算法性能比較差；當(dāng)樹較多時，RF 的分類精度會隨之提升，但是這也意味著RF 的復(fù)雜度變高，構(gòu)建時間變長，森林的可解釋性也慢慢減弱。因此為了了解樹的數(shù)量對MDF 的影響，本文考察L從小變大的情況下算法的分類錯誤率的變化，具體結(jié)果如表2 所示。

表2 中最后一列給出了10 個數(shù)據(jù)集在不同L下錯誤率的平均值。從表2 的實驗結(jié)果總體來看，在這10 個數(shù)據(jù)集上MDF 算法的分類錯誤率隨著L的增加變化幅度不大。在有些數(shù)據(jù)集上MDF 算法的分類錯誤率會隨著L的增加而先減小后增大，有些數(shù)據(jù)集上會先增大后減小，剩下的數(shù)據(jù)集則隨著L的增大變化不明顯。雖然表中的分類錯誤率隨著L的變化情況不一致，且錯誤率的最小值分布在不同的L下，但是錯誤率的最小值與表中其他錯誤率值的差距也較小。

Table 2 Effect of parameter L change on classification error rate表2 參數(shù)L 變化對算法分類錯誤率的影響 %

為了更好地說明不同L下的MDF 算法錯誤率的變化情況，選取了每行數(shù)據(jù)的3 個特征值來考察，具體如圖1 所示。

Fig.1 Error rate of MDF algorithm under 3 indices圖1 在3 種指標(biāo)下MDF 算法的錯誤率

圖1 中柱狀圖分別表示每個數(shù)據(jù)集在L從10 變化到150 時錯誤率的最小值、平均值和最大值。從圖中可以看出每個數(shù)據(jù)集的3 種柱的高低都比較接近，這也說明最小值與最大值、最小值與平均值以及最大值與平均值之間的差值較小。

綜上所述，MDF 的分類錯誤率隨L的變化幅度較小，可以得出模型決策森林的分類錯誤率對L的變化不敏感。因此本文后續(xù)實驗取L的值為10，這樣既可以獲得與較多樹時相近的分類錯誤率，也會避免因樹的數(shù)量增多而引起的MDF 復(fù)雜度變高，訓(xùn)練時間變長的問題。

（2）參數(shù)M對實驗結(jié)果的影響

實驗中M的大小不同會產(chǎn)生不同旋轉(zhuǎn)矩陣，即會產(chǎn)生不同的訓(xùn)練樣本子集，進(jìn)而影響模型決策森林的精度與訓(xùn)練時間。如果M太小可能選不到最佳分裂特征與其對應(yīng)的最佳分裂結(jié)點，從而影響MDF算法的分類精度；如果M太大可能會使MDF 算法的訓(xùn)練時間變長，從而影響算法的時間效率。因此合適的M對本文所提MDF算法至關(guān)重要，故本文考察了不同的M下算法分類精度的情況，實驗結(jié)果如表3所示。

表3 中分別列出了M取2～20 的情況下10 個數(shù)據(jù)集的分類錯誤率，表中橫線表示數(shù)據(jù)集的特征數(shù)沒有當(dāng)前M大的情況。比如：Breast_cancer 數(shù)據(jù)集9維，它的M最大可取到9，此時只有一個特征子集。因此在表中M取15 和20 的情況下，Breast_cancer 數(shù)據(jù)集在對應(yīng)位置標(biāo)為橫線。

根據(jù)表3 可以看出，當(dāng)M為2 時，大部分?jǐn)?shù)據(jù)集上的分類錯誤率都比M為3 時大；而當(dāng)M大于3 時，在有的數(shù)據(jù)集上，分類錯誤率在下降，有的數(shù)據(jù)集上分類錯誤率則有一些波動。很容易想到：隨著M的不斷增大，單棵樹在構(gòu)建過程中選擇分裂結(jié)點時可以有更多的特征加入到計算中，那么選中最優(yōu)分裂特征的概率也在不斷增大，因此M增大MDF 算法的分類錯誤率應(yīng)該逐漸下降。但是在有些數(shù)據(jù)集上隨著M的增大，分類錯誤率卻也在增大，猜想是因為隨著特征的增多，可能會在一定程度上造成一些過擬合的現(xiàn)象，尤其是對于特征數(shù)較少或者樣本數(shù)較少的數(shù)據(jù)集。對于特征比較多的數(shù)據(jù)集，即使M的取值較小，在構(gòu)建單棵樹的過程中可能會選不到較好的結(jié)點，但是本文的單樹是模型決策樹，在非純偽葉結(jié)點上還存在一個簡單分類器，因此最終的分類結(jié)果不會太差。

Table 3 Effect of parameter M change on classification error rate表3 參數(shù)M 變化對算法分類錯誤率的影響 %

綜上所述，在M=3 時算法的分類錯誤率具有一定的優(yōu)勢，并且M的值較小時有利于減少MDF 算法的訓(xùn)練時間，故本文在后續(xù)實驗中將M的值設(shè)定為3。

（3）與模型決策樹算法的比較

本文方法的基分類器是模型決策樹，故將MDF與MDT的分類錯誤率進(jìn)行了比較。其中MDF的M取值為3，L取值為10；MDT 中SVM 高斯核參數(shù)γ取值為0.5，線性核與高斯核的C都取1.0，LIBLINEAR模型參數(shù)s取2，模型葉結(jié)點參數(shù)t取0.1。實驗結(jié)果如表4，其中涉及到的模型決策樹算法具體含義如表5所示。

表4 中加粗?jǐn)?shù)字表示每行的最小值，最右邊一列best other 表示除了MDF 算法外的另外6 種方法在每個數(shù)據(jù)集上錯誤率的最小值。從表中可以看出，MDF算法在7 個數(shù)據(jù)集上分類錯誤率最小，MDTFS_LIB算法在兩個數(shù)據(jù)集上錯誤率最小，MDT_SVM(linear)算法在1 個數(shù)據(jù)集上錯誤率最小。根據(jù)表中best other 這一列可以看出，在幾個數(shù)據(jù)集上雖然本文提出的MDF 方法分類錯誤率不是最小，但是本文的錯誤率與其他方法的最小分類錯誤率相比也較接近，只有在Cod_rna 數(shù)據(jù)集上本文方法與其他方法最小值相差較多。為了更直觀地展現(xiàn)幾種方法的實驗結(jié)果，將表4 中的錯誤率轉(zhuǎn)化為正確率（100%-錯誤率）進(jìn)行比較，如圖2 所示。

Table 4 Classification error rate of 7 methods表4 7 種方法分類錯誤率 %

Table 5 Algorithm list表5 算法一覽表

圖2 的每個子圖中，縱坐標(biāo)都表示本文提出的MDF 算法的正確率，橫坐標(biāo)分別表示其他6 種方法的正確率，圖中對角虛線表示橫縱坐標(biāo)對應(yīng)的兩種方法正確率相等的情況。圖中一個黑點代表一個數(shù)據(jù)集，每幅子圖都有10 個黑點，代表10 個數(shù)據(jù)集。黑點在虛線的上方則表示在當(dāng)前這個數(shù)據(jù)集上MDF算法的正確率高于橫坐標(biāo)對應(yīng)的算法的正確率，同時黑點離虛線的垂直距離越大則表示MDF 算法正確率比橫坐標(biāo)對應(yīng)算法正確率高得越多；黑點在虛線的下方則表示在當(dāng)前這個數(shù)據(jù)集上橫坐標(biāo)對應(yīng)的算法的正確率高于MDF 算法的正確率，同時黑點離虛線的垂直距離越大則表示橫坐標(biāo)對應(yīng)的算法的正確率比MDF 算法正確率高得越多。

根據(jù)圖2 可以看出，在這6 幅子圖中虛線上方的黑點數(shù)量均多于虛線下方的黑點，這表示MDF 算法在多數(shù)數(shù)據(jù)集上的正確率高于其他6 種算法的正確率。在第一行前兩幅子圖中，MDF 算法的正確率分別在9 個數(shù)據(jù)集和8 個數(shù)據(jù)集上比MDT_LIB 算法和MDTFS_LIB 算法高，并且這些數(shù)據(jù)集中有6 個數(shù)據(jù)集上的正確率比這兩種算法正確率高得較多。在第一行第三幅圖和第二行第一幅圖上，MDF 算法的正確率各在8 個數(shù)據(jù)集上比MDT_SVM(linear)算法和MDTFS_SVM(linear)算法高，并且這幾個數(shù)據(jù)集中有3 個數(shù)據(jù)集離虛線的距離較近，這也表示它們的正確率比較接近。在第二行的最后兩幅子圖中，MDF 算法的正確率各在9 個數(shù)據(jù)集上比MDT_SVM(rbf)算法和MDTFS_SVM(rbf)算法高，并且倒數(shù)第二幅子圖上橫縱坐標(biāo)代表的算法的正確率更加接近，最后一幅子圖中MDF 算法的正確率比MDTFS_SVM(rbf)算法更高。

表6 給出了上述7 種方法分類性能優(yōu)劣的排序結(jié)果。表6 中，每一行的值表示該列對應(yīng)算法比其他列對應(yīng)算法在該行對應(yīng)數(shù)據(jù)集上錯誤率小的算法個數(shù)，這個值最大可為6，最小可為0。例如：第3 行第5列的數(shù)字4 表示在German 數(shù)據(jù)集上MDT_SVM(rbf)算法比其他4 種算法的錯誤率小。表6 中最后一行是每種算法在各個數(shù)據(jù)集上的錯誤率比其他算法小的個數(shù)總和。從表6 中可以看出，表現(xiàn)最好的是MDF算法，其次是MDT_SVM(rbf)算法，排在第三位的是MDTFS_SVM(linear)算法，排在最后一位的是MDT_LIB 算法。

Fig.2 Precision comparison of 7 methods圖2 7 種方法精度對比

Table 6 Sorting results of 7 methods表6 7 種方法排序結(jié)果

綜上，MDF 算法的分類性能有一定的優(yōu)勢，尤其是與MDT 算法相比。

（4）與隨機(jī)森林算法的比較

為了更好地說明本文提出的MDF 算法的性能，將之與隨機(jī)森林算法的分類錯誤率進(jìn)行了比較。實驗結(jié)果如表7 所示，其中參數(shù)L與MDF 相同，即L=10。

Table 7 Classification error rate of 2 methods表7 兩種方法分類錯誤率 %

根據(jù)表7 可以看出，在6 個數(shù)據(jù)集上MDF 算法的分類錯誤率比RF 小，在其他4 個數(shù)據(jù)集上RF 的錯誤率小于MDF。其中，在Banana 和Cod_rna 兩個數(shù)據(jù)集上RF 的錯誤率比MDF 小得較多，在image 數(shù)據(jù)集上MDF 比RF 的錯誤率小得較多。這說明本文提出的MDF 算法還有進(jìn)一步提升的空間。

4 結(jié)束語

本文提出了一種模型決策森林算法，它將模型決策樹作為基分類器，利用隨機(jī)森林的思想，生成多棵模型決策樹。與MDT 相比，MDF 對參數(shù)不敏感，因此可以設(shè)置較小的參數(shù)值從而減少訓(xùn)練時間，同時多棵樹集成以后的精度比MDT 高。另外，MDF 在樹的數(shù)量較少時也能取到不錯的精度，避免了因樹的數(shù)量增加時間復(fù)雜度增高的問題。在大數(shù)據(jù)環(huán)境下，如何構(gòu)建更魯棒的模型決策森林將是未來的研究重點。