基于數據集成的隨機森林算法

謝 坤,容鈺添,胡奉平,陳 桓,姚小龍

(順豐科技有限公司 大數據與區塊鏈研發中心,廣東 深圳 518000)

0 概述

銷量預測是工業界中的重要研究問題,尤其在制造業、供應鏈等領域,它一般是預測未來一段時間內某產品的訂單需求量,其時間跨度可用天、周、月或者年為單位,且預測結果對決策有決定性影響。然而,銷量預測是一個非常困難的問題,在多數情況下,基于歷史數據很難建立一個高效且精準的模型,導致該現狀的主要原因有:缺乏歷史數據,雖然目前處于大數據時代,但在多數情況下,仍然沒有足夠的數據量來預測未來趨勢。歷史數據不穩定,例如同一個產品前后幾天的訂單需求量可能相差很大,這意味著數據有較強的隨機性,導致方差過大、不穩定。很多預測都偏向于長期預測,而長期預測本身比短期預測更加困難,例如,基于過去幾天的天氣狀況以及溫度數據,預測未來一個月后的天氣和溫度比預測一天后困難,因為第二天的天氣和溫度在某種程度上與剛過去幾天的數據有較強的關聯性。相反,預測周期越長,其準確率則難以保證。除了以上可能導致預測結果不準確的原因外,還有許多其他難以捕捉的因素也會對產品的未來銷量造成影響,比如相似產品的價格競爭等。

在缺乏預測數據的情況下,傳統機器學習與深度學習等算法預測效果較差,為此,本文提出一種基于數據集成的隨機森林(Random Forest,RF)算法。該算法通過對模型特征進行隨機重組,豐富訓練樣本的多樣性。

1 相關工作

目前,工業界中提升銷量預測準確率的方法主要在模型選擇、特征工程與集成學習等方面。早期的銷量預測主要以傳統的時間序列預測方法為主,其中,代表性方法為指數平滑模型、差分自回歸移動平均模型等,但它們都屬于線性預測模型,并不具備非線性建模能力。很多研究將上述方法應用到氣象[1]、經濟[2-3]與網絡流量[4]等領域進行分析預測,在實際生產環境中,實際值受到很多非線性關系的影響,因此預測效果較差。決策樹(Decision Tree)、支持向量機(Support Vector Machine,SVM)等具備良好的非線性建模能力,因此基于機器學習的預測方法日漸增多[5-6]。

隨著深度學習技術的快速發展,將深度學習相關技術應用到時間序列分析的研究越來越多。深度學習中的循環神經網絡(Recurrent Neural Network,RNN)結構適合序列輸入的特征,其中,以長短期記憶(Long Short Term Memory,LSTM)網絡最具代表性,它能夠避免原始RNN的梯度消失、爆炸以及遺忘長期記憶等問題[7],并廣泛應用于語音識別[8]、機器翻譯[9]和時間序列預測[10-11]等領域,且取得了顯著效果。特征工程涵蓋了特征提取、特征構造、特征編碼、特征縮放與特征降維[12]等方面,特征工程與具體的預測任務緊密相關,不同的任務涉及到不同的特征工程,好的特征工程可以挖掘出與業務比較相關的因素,有效提升模型效果。

近年來,隨著自動機器學習(Automatic Machine Learning,AML)的興起,特征工程逐漸向自動化方向發展,但一部分特征工程任務還未實現自動化[13]。集成學習的思想主要是組合多個不同模型來提升單個模型的性能,代表算法有隨機森林、梯度提升決策樹(Gradient Boosting Decision Tree,GBDT)等,這些算法可有效提高弱學習器的預測效果與泛化能力。差異性是集成學習能夠提高其性能的重要因素[14],因此研究人員在度量模型間多樣性和研究模型融合方法上做了大量工作[15-17]。不同于多數已有的研究工作,本文從數據角度出發,提出一種通用的數據集成方法,有效提升隨機森林和其他模型的預測準確率。

2 基于數據集成的高維預測算法

2.1 問題定義

2.2 特征提取

根據歷史數據序列{y(1),y(2),…,y(T)}預測y(T+D)的值,一般有2種方法:一是應用統計學中的時間序列預測模型(如ARIMA模型)直接預測下一個數值,但是對于長期預測問題,ARIMA模型的預測準確率不高;二是可以人為創建一個訓練數據集,使用機器學習的相關算法進行預測。具體地,對于每一個目標值y,需提取出其對應的特征向量x以創建訓練集{(x(t),y(t))},t=1,2,…,T。對于時間點t,本文將從2個維度對y(t)進行特征提取。一方面考慮歷史數據值,使用最近一周的觀測值作為目標y(t)的特征向量,即定義x(t)=(y(t-D-6),y(t-D-5),…,y(t-D)),其中,D+7≤t≤T(注意到本文的目標是預測時間段D后的Y值)。另一方面可以從時間信息的維度來增加特征,因為產品的訂單需求往往與時間相關。產品的訂單需求量可能取決于一周的第幾天,甚至與月份、年份或者節假日有關,也會呈現周期性波動。因此,基于以上討論,提取出表1中的信息并添加到特征向量中,對于非數值的分類特征,可以用One-Hot Encoding的方式進行編碼處理。

表1 基于歷史數據以及時間維度的特征信息Table 1 Feature information based on historical dataand time dimension

2.3 本文算法

隨機森林是用于分類或回歸任務的一種集成學習算法,由一組決策樹{h(x,Θk),k=1,2,…,K}組成,其中,x是輸入的特征向量,{Θk}是具有獨立同分布的隨機序列,h(x,Θk)是第k棵樹的預測結果。針對分類任務,隨機森林采用投票機制,它參考所有決策樹的分類結果,以得票最高的一類作為最終分類結果;針對回歸任務,隨機森林用所有決策樹返回的平均值作為最終預測結果。

(1)

算法1基于數據集成的隨機森林算法

步驟1將集合I={1,2,…,M}隨機分割成S個子集I1,I2,…,IS,S為1到M之間的隨機整數。

步驟5重復上述4個步驟N次。

步驟6返回N次結果的平均值作為最終預測值。

在討論本文算法的收斂性之前,有以下3個問題需要特別說明:

1)本文選擇隨機森林作為基礎模型進行研究,原因如下:文獻[18]首次提出并證明了隨機森林的收斂性定理,而本文算法是基于數據集成下的隨機森林,其數據特征得到了增強,且同樣繼承了隨機森林原本的收斂性質。由于隨機森林的收斂性質,可避免模型過擬合。同時,隨機森林的另一個重要特征是其并行性,因為每棵決策樹之間相互獨立,它們可以并行生成,能夠節省大量的訓練時間。因此,隨機森林本身擁有的優點在基于數據集成的隨機森林算法上都得到了良好繼承。

2)本文采用數據集成思想對目標變量Y進行隨機分割,該想法是受到了隨機森林結構的啟發,隨機森林本身是一種對決策樹的集成算法,多棵決策樹共同做決定,相比于單棵決策樹,模型最終的準確率、魯棒性都得到了明顯增強。本文將類似的集成想法應用到數據層面,模型的每輪擬合過程所用訓練集都是在原始數據集上通過隨機重組的方式而得到的新數據集,且數據重組的過程完全隨機化,與先前訓練集的生成過程相互獨立。本文算法的最終預測結果也是采用平均值進行估計的,這點與隨機森林相似。

3)本文算法沒有直接固定S=M,主要原因有2個:原因一是,如果固定S=M,該算法失去了算法1中數據集成的步驟1～步驟3,也沒有重復過程(算法1中的步驟5),此時模型退化為隨機森林,對準確率造成了影響;原因二是,如果固定S=M,則目標變量為M維向量(Y1,Y2,…,YM),該維度更高的M維向量比S(若S

根據文獻[18],隨著決策樹數目的逐漸增多,隨機森林的誤差將會逐步收斂,基于隨機森林的收斂性以及強大數定理,能夠證明本文算法也有類似的收斂性質。

(2)

其中:

(3)

(4)

證明結合文獻[18]中有關隨機森林的收斂性定理,僅需證明對任意的輸入向量x,以下收斂結果成立:

(5)

將式(3)代入式(5)的左邊部分,可得:

(6)

(7)

本文需要將M個指標隨機分組成Sn個非空子集,用S(M,Sn)來表示其可能的所有分組結果數目。利用遞歸方法來求解S(M,Sn),具體可用式(8)、式(9)表示:

S(M,Sn)=k·S(M-1,Sn)+S(M-1,Sn-1)

(8)

(9)

基于以上討論,重新表示式(6)時,首先考慮Sn的取值,以NS來代表Sn取值為S的總次數(在N輪訓練中),則有:

(10)

因此,式(6)可重新表示為:

(11)

根據式(11)可知,只需證明對任意的1≤S≤M,式(12)成立即可。

(12)

根據NS和Part(S)的定義可知,為了不失一般性,假設前NS個Sn的值均為S(如果不是則調整順序),即對任意的1≤n≤NS,均有Sn=S成立,且對任意的NS

(13)

式(13)最后一步的收斂是基于Sn在集合I={1,2,…,M}中的取值是完全隨機且等概率的。對于任意固定的Sn=S,只需要證明以下收斂結果成立即可。

(14)

|x,S,I1,I2,…,IS,Θ))=

|x,S,I1,I2,…,IS,Θ))

(15)

其中,式(15)的收斂性來自于文獻[18]中的定理2。

式(5)的右部分表達式為:

|x,S,I1,I2,…,IS,ΘK))=

(16)

其中,式(16)最后一步等式是因為所有決策樹的預測結果的期望相同(獨立同分布)。因此,當訓練的輪數N逐步增大時,則有:

LHS→RHS,N→∞

(17)

即式(5)成立,因此定理1成立。

2.4 本文算法的關鍵步驟與復雜度分析

2.4.1 本文算法的關鍵步驟

(18)

2.4.2 本文算法的復雜度分析

本文算法是一種集成方法,其基于隨機森林總共訓練N輪,且每輪訓練相對獨立,因此模型的訓練耗時約為每輪隨機森林耗時的總和。因為隨機森林中的決策樹通常是未經修剪的分類回歸樹,假設決策樹的棵數、訓練數據的樣本量以及特征向量的屬性個數分別為K、n和m,文獻[19]表明該隨機森林的算法復雜度為O(Knmlnn)。本文算法中每輪訓練是數據的隨機重組以及隨機森林的擬合過程,數據重組的耗時與隨機分割數S(S≤M)、訓練數據的樣本量n以及特征向量的屬性個數m成正比,因此該步驟耗時為O(Mnm)。基于以上討論,本文算法的復雜度為O(N(Knmlnn+Mnm))。此外,文獻[20]表明,如果隨機森林中決策樹的棵數K較大,隨機森林一般在達到該數目之前收斂。需特別說明的是,通常隨機森林中決策樹的棵數K以及樣本量個數n遠大于變量個數M,因此本文算法的復雜度可簡化為O(NKnmlnn),其相當于重復了N次的隨機森林。

3 實驗結果與分析

3.1 實驗環境

本文實驗的軟件與硬件環境參數設置如表2所示,其中,實驗選用Scikit-learn作為機器學習的主要框架。

表2 實驗軟件與硬件環境參數設置Table 2 Parameter setting of software and hardwareenvironment of experiment

3.2 實驗數據集

本文的實驗數據集來自順豐科技有限公司2019年上半年廣東省深圳市所有的快遞運單數據,約1億條運單,其中,每條運單均包含了托寄物品類的信息。由于同一類別的托寄物需要投入的人力、物力(紙箱、包裝袋等)相似,該實驗的目標是對于每一類托寄物,希望能提前預測出30天后的訂單量,以便提前準備好應對措施。例如,對于手機品類,假定共有D種不同的手機品牌,可以定義Y=Y1+Y2+…+YD為手機品類總訂單量,其中,Yd(1≤d≤D)為各手機品牌的訂單量。結合順豐科技有限公司所有的業務場景,實驗總共對40個品類的托寄物進行建模、訓練與預測。因為不同托寄物品類訂單量的數量級級別不同,所以本文統一對數據進行相應的歸一化處理,即用各品類托寄物的實際運單量除以2019年上半年該類別托寄物單天總單量的最大值。

3.3 各類預測模型的性能比較

利用順豐科技有限公司截止到2019年6月30日深圳市所有運單數據來預測30天后各托寄物品類的運單量,實驗選用的預測算法有ARIMA、RF、GBDT、LSTM與本文算法。其中,本文算法有2種不同的版本,一種是以Y=Y1+Y2+…+YD為目標變量,屬于單維度預測,另一種是以(Y1,Y2,…,YD)為目標變量,屬于高維度預測,并將預測出的高維向量求和作為最終預測結果。為了區分,本文稱第2種算法為高維基于數據集成的隨機森林(HDRF)算法,實際上HDRF算法是本文算法的一種特例。

除了時間序列算法ARIMA之外,RF算法、GBDT算法、LSTM算法、本文算法與HDRF算法在訓練過程中均采用了交叉驗證,其中,本文算法總共訓練了200輪(即N=200),且其基礎模型隨機森林中決策樹的數目為100、樹的深度為10。6種算法的預測結果對比如表3所示,由于涉及公司商業機密,托寄物品類的名稱以數字1～40替代。

表3 6種算法的預測結果對比Table 3 Comparison of prediction results of six algorithms

從表3可以看出,本文算法的預測結果與實際結果更為接近,這說明了相比于其他算法,本文算法的預測效果更好。為了更直觀地看出上述6種算法的預測效果,圖1對其在40種托寄物品類下運單量的預測值與實際值對比情況進行可視化,具體如圖1所示。其中,每個分圖對應一種預測算法。

圖1 6種算法的預測結果與實際結果對比折線圖Fig.1 Line chart of comparison between predicted results and actual results of six algorithms

從圖1可以看出,本文算法的預測效果最好,其次為HDRF算法,這2種算法的預測結果與實際結果非常接近,在HDRF算法的基礎上,結合數據集成方法后的本文算法表現更佳。本文從絕對誤差、相對誤差、均方差與時間耗費4個指標來對比所有算法的預測效果,結果如表4所示。

表4 6種算法的4種評價指標對比Table 4 Comparison of four evaluation indexes ofsix algorithms

從表4可以看出:相比于ARIMA算法、RF算法、GBDT算法和LSTM算法,本文算法的絕對誤差至少提升了86%,相比HDRF算法,本文算法的平均絕對誤差提升了26%;本文算法相比于其他算法,相對誤差以及均方差的提升效果與絕對誤差類似。絕對誤差、相對誤差、均方差是常用來評判模型效果的3個指標,這3個指標的對比結果說明了本文提出的數據集成思想的高效性。此外,表4反映的時間耗時與2.4節中對比分析RF算法、本文算法復雜度的理論結果一致。對于順豐有限公司的每種托寄物品類的數據,半年的數據量實質上是一個不到200個離散點的時間序列,因此除了本文算法外,其他算法的訓練時間都很短,本文算法的平均運行時間小于6 min,在時效犧牲不大的情況下,本文算法的預測準確率得到了大幅提升。

4 基于數據集成的預測算法

4.1 數據集成在其他算法上的應用

實驗基于順豐科技有限公司業務比較關注的托寄物類別中的手機類進行分析。為了驗證數據集成的有效性,實驗選取ARIMA算法為研究對象,分析數據集成下ARIMA算法的預測效果。手機類的運單數據較多且相對穩定,ARIMA算法自身的預測效果良好,相對準確率為74.66%,結合數據集成后,其相對準確率提高至77.74%,提升了3.08%。相比ARIMA算法,與數據集成相結合的ARIMA算法多出的時間耗費主要體現在其訓練輪數上,該時間耗費的對比情況與下文中關于算法2的復雜度分析結果一致,在犧牲173.9 s的運行時間情況下,使得算法的預測準確率提高了3.08%。

4.2 隨機切割數與訓練輪數對算法的影響

為了研究隨機分割數S對算法預測性能的影響,固定S值分別為2、3、4和5,用這些S值訓練與數據集成相結合的ARIMA算法的預測相對準確率和時間耗費,訓練輪數為200(N=200)輪,結果如表5所示。從表5可以看出,隨機分割數S的大小對算法的預測相對準確率影響不大,在運用隨機分割的思想(即S>1)下,與數據集成相結合的ARIMA算法的預測相對準確率提升了約3%。

表5 分割數S對算法相對準確率的影響Table 5 Influence of segmentation number Son relative accuracy of algorithm

同時,為了驗證訓練輪數N對算法預測效果的影響,實驗記錄了隨著訓練輪數的增加,ARIMA算法的預測相對準確率的變化過程,具體如圖2所示。從圖2可以看出,除了一些微小波動外,相對準確率隨著訓練輪數的增大呈現逐漸升高后趨于穩定的趨勢。

圖2 訓練輪數對ARIMA算法相對準確率的影響Fig.2 Influence of training round number on relativeaccuracy of ARIMA algorithm

4.3 基于數據集成的通用預測算法

基于以上幾組實驗可以看出,將數據集成結合到其他預測算法中時,能夠提升算法的預測效果,基于此,本文提出基于數據集成的通用預測算法,具體步驟如下:

算法2基于數據集成的通用預測算法

步驟1將集合I={1,2,…,M}隨機分割成S個子集I1,I2,…,IS,S為1到M之間的隨機整數。

步驟5重復以上4個步驟N次。

步驟6返回N次結果的平均值作為最終預測值。

算法2實質上是算法1的推廣,兩者的本質并無區別,它們的核心思想都在于預測目標變量以及訓練集拆分后的隨機重組過程(參照2.4節),不同之處在于后期基礎算法的選擇。算法1選擇以隨機森林作為基礎算法,而算法2在算法1的基礎上進行拓展,基礎算法的選擇自由度較寬泛,任意的預測算法都能適合。與算法1復雜度分析過程類似,算法2相當于是在數據隨機重組的基礎上將選擇的基礎算法重復訓練N次。假設基礎模型的參數為Θ,用函數O(f(n,m,Θ))表示其復雜度,則算法2的復雜度為O(N(f(n,m,Θ)+Mnm)。

5 結束語

將數據的隨機重組與現有隨機森林算法相結合,本文在數據層面上提出一種基于數據集成的隨機森林算法,該算法保留了隨機森林的收斂性質與優點。實驗結果表明,相比未使用數據集成的預測算法,本文算法在絕對誤差、相對誤差與均方差指標上均有大幅提升。同時,拓展實驗說明了數據集成還可以應用在ARIMA等其他算法上,且在不改變算法基本框架的條件下,僅對數據特征進行增強即可實現準確率約3%的提升。后續將利用大數定理、中心極限定理等理論知識對本文預測算法的收斂速度和準確率進行研究,并優化數據特征的隨機重組方式,使算法在理論與實踐中均取得較好的預測效果。