一種模型決策森林算法*

尹 儒，門昌騫，王文劍

1.山西大學 計算機與信息技術學院，太原030006

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

1 引言

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

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

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

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

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

2 模型決策森林

2.1 MDT 簡介

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

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

2.2 MDF 基本原理

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

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

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

（3）最后將得到的所有系數進行組合，得到矩陣Ri，如式（1）所示。

（4）將Ri根據F中的特征順序重新排序，得到最終的旋轉矩陣。

假設訓練數據有K個類，Ck指D中屬于第k類的樣本子集。則給定的訓練數據D對應的基尼指數為：

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

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

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

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

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

2.3 MDF 算法

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

算法1MDF 算法

初始化：訓練數據集D，測試數據集T，樹的棵數為L，特征集F，隨機分割份數S。

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

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

步驟3重復步驟1 和步驟2，直到模型決策樹的棵數達到L。

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

步驟5算法結束。

3 實驗結果分析

3.1 實驗環境及實驗數據

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

Table 1 Datasets used in experiments表1 實驗數據集

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

3.2 實驗結果與分析

（1）參數L對實驗結果的影響

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

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

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

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

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

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

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

（2）參數M對實驗結果的影響

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

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

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

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

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

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

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

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

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

Table 5 Algorithm list表5 算法一覽表

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

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

表6 給出了上述7 種方法分類性能優劣的排序結果。表6 中，每一行的值表示該列對應算法比其他列對應算法在該行對應數據集上錯誤率小的算法個數，這個值最大可為6，最小可為0。例如：第3 行第5列的數字4 表示在German 數據集上MDT_SVM(rbf)算法比其他4 種算法的錯誤率小。表6 中最后一行是每種算法在各個數據集上的錯誤率比其他算法小的個數總和。從表6 中可以看出，表現最好的是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 種方法排序結果

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

（4）與隨機森林算法的比較

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

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

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

4 結束語

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