基于改進CART算法的降雨量預測模型

李正方 杜景林 周蕓

摘 ?要： 降雨量預測對于水資源的管理非常重要，可以幫助決策者提前做出應對舉措，降低災情發生時帶來的經濟損失和人員傷亡。同時，降雨量預測對人們的日常生活、出行等也有著非常重要參考意義。通過分類回歸樹算法構建兩個預測降雨量的模型，然后通過粒子群算法對模型中的參數進行優化。此外，為解決原算法不具備處理數據流問題的能力，根據dsCART算法的思想，對原算法生成決策樹的過程做出了調整，使其具有增量學習的能力，提高其在氣象信息系統中的實用性。最終通過實驗驗證了該改進方法的可行性、有效性。

關鍵詞： 降雨量預測; CART算法; 粒子群優化算法; 增量學習; 性能評價; 實驗驗證

中圖分類號： TN98?34 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）02?0133?05

Rainfall prediction model based on improved CART algorithm

LI Zhengfang， DU Jinglin， ZHOU Yun

Abstract： Rainfall forecasting is very important for water resources management， which can help decision makers to take measures in advance to reduce the economic losses and casualties caused by disasters. At the same time， rainfall forecasting is of great significance to people's daily life， travel and so on. In this paper， two models for predicting rainfall are constructed by means of the classified regression tree algorithm， and the parameters in the models are optimized by means of the particle swarm optimization （PSO）. In addition， the process of generating decision tree on the basis of original algorithm is adjusted according to the thought of the dsCART algorithm， which makes it have the ability of incremental learning and improve the practicability in the meteorological information system， so as to solve the problem that the original algorithm does not have the ability to deal with data flow. Finally， the feasibility and effectiveness of the improved method are verified with the experiments.

Keywords： rainfall forecast; CART algorithm; particle swarm optimization algorithm; incremental learning; performance evaluation; experimental verification

0 ?引 ?言

天氣預測對于應對極端氣候狀況及重大災情有著十分重要的作用。常見的用于預測天氣狀況的方法包括神經網絡[1] 、K?最近鄰[2]、決策樹[3]等方法。本文針對降雨問題提出了一種基于決策樹的降雨量預測模型。該模型基于公知的分類回歸樹（Classification And Regression Tree，CART）算法。 CART算法是由Breiman等人在1984年提出的，其目的是構造一個有效的算法讓其能從觀測的訓練樣本中給出分類器的分段常數估計或回歸函數估計。本文就這兩種估計方式構建了回歸樹模型和模型樹模型，并將這兩種模型用于預測降雨量時的性能做出了比較。

由于天氣預測時效性較強，氣象數據多以數據流的形式連續地輸入到系統當中，且受到氣候環境變化的影響，各氣象要素間的關系和相互作用可能隨時間發生一些漂移。解決這類問題的一個合適的工具是增量學習[4]。本文針對降雨量預測問題引用了Leszek Rutkowski 等人提出的dsCART[5]（Data Stream CART Algorithm）算法對原有算法構造生成決策樹的過程進行了調整與改進，使該算法具有了增量學習的能力。

利用CART算法對數據集進行劃分時，既要避免不必要的劃分增加時間開銷，同時也要防止過度劃分導致其生成的決策樹出現過擬合。為此，本文添加兩個參數作為約束條件。然而，在數據流的情況下，這些參數值的最優解也會隨著數據樣本的增加而變化。所以本文引用了粒子群算法[6]（Particle Swarm Optimization，PSO）對原算法進行了優化，使其能尋找出該參數在全局的最優解。實驗結果表明， 優化后的算法性能有了較大的提升。

1 ?相關算法分析

1.1 ?CART算法

現有的決策樹構造算法主要有：ID3算法[7]、C4.5算法[8]和CART算法[9]。其區別主要體現在樹的類型和純度度量標準不同。ID3算法產生的是一棵非二叉樹，用信息熵作為純度度量標準。通過分裂前后信息熵的變化計算信息增益，再根據信息增益的值決定是否進行該次分裂。C4.5算法同樣是用信息熵來衡量數據集的純度，但它增加了一個稱為分裂信息的附加函數，并通過計算信息增益與分裂信息的比值，即信息增益率[10]來決定是否進行該次劃分。而由CART算法構造的決策樹是一棵二叉樹，并采用基尼指數[11]（Gini index）作為衡量數據集純度的標準。其執行過程如下：在根節點[L0]處處理訓練數據集S的子集[Sq]，若[Sq]中的所有元素屬于同一類別，則該節點被標記為葉子節點并停止劃分。否則根據分割度量函數在該節點中選擇最佳劃分屬性繼續切分。對于每個可用劃分屬性[ai]，通過選擇劃分閾值將其取值集合[Ai]劃分為兩個不相交的互補子集X和Y。設劃分閾值為[AiL]，[Ai]的所有可能的劃分閾值為[Vi]，則集合X和Y將數據集[Sq]劃分成了兩個互不相交的子集[Lq（AiL）]和[Rq（AiL）]。

[Lq（AiL）={sj∈Sq|Vij∈X}] （1）

[Rq（AiL）={sj∈Sq|Vij∈Y}] （2）

集合[Lq（AiL）]，[Rq（AiL）]中元素取決于劃分的屬性[ai]和閾值[AiL]，令[pL，q（AiL）]，[pR，q（AiL）]分別表示數據集[Sq]中[Lq（AiL）]和[Rq（AiL）]所占的比例。[pL，q（AiL）]和[pR，q（AiL）]的關系表示如下：

[pR，q（AiL）=1-pL，q（AiL）] （3）

在這些參數中，只需考慮[pL，q（AiL）]，設數據集S被劃分為k個不同的類別，則集合[Lq（AiL）]和[Rq（AiL）]中元素來自類別k中的比例分別記為[pkL，q（AiL）]，[pkR，q（AiL）]。 數據集[Sq]中元素來自類別k的比例記為[pk，q]，k=1，2，…，k，并且該值不依賴于選擇的劃分屬性[ai]和劃分閾值[AiL]。由[pk，q]的值我們可以得出在節點[L0]處數據集[Sq]的基尼指數值：

[Gini（Sq）=1-k=1K（pk，q）2] ?（4）

當[Sq]中所有元素都屬于同一類別時，基尼指數值達到最小值0;當[Sq]中元素均勻分布在k個類別上時，基尼指數值最大，并且類別越多，基尼指數值也越大。此外，根據劃分閾值[AiL]得到的子集[Sq]的加權基尼指數定義為：

[wGini（Sq，AiL）=pL，q（AiL）Gini（Lq（AiL））+ ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1-pL，q（AiL））Gini（Rq（AiL））] （5）

其中，集合[Lq（AiL）]和[Rq（AiL）]的基尼指數由式（4）得：

[Gini（Lq（AiL））=1-k=1K（pkL，q（AiL））2] ?（6）

[Gini（Rq（AiL））=1-k=1K（pkR，q（AiL））2] （7）

CART算法中的分割度量函數被定義為基尼指數與加權基尼指數之間的差值。該分割度量函數被稱為Gini增益，其表達式如下：

[g（Sq，AiL）=Gini（Sq）-wGini（Sq，AiL）] （8）

在集合[Ai]中的所有可能的劃分閾值[AiL]中，選擇使得Gini增益取得最大值的那一個作為最終的劃分閾值。

[AiL，q=argmaxAiL∈Vi{g（Sq，AiL）}] ?（9）

該最佳劃分閾值[AiL，q]將集合[Ai]劃分出兩個子集[Liq=Liq（AiL，q）]和[Riq=Riq（AiL，q）]。[giq=g（Sq，AiL，q）]的值被稱為數據集[Sq]中屬性[ai]的Gini增益。能使得Gini增益取得最大值的屬性則作為劃分屬性，并將節點[L0]劃分為兩個子節點[Llast+1]和[Llast+2]，last代表最近一次在整個樹中創建的節點的索引值。假設屬性[ax]具有最大的Gini增益值，則讓子集[Slast+1=Lxq]和[Slast+2=Rxq]分別在節點[Llast+1]和[Llast+2]上執行上述操作。當節點中的可用屬性只剩下一個或子集[Sq]中所有元素都來自同一類時停止劃分，并將該節點標記為葉子節點。此時，若將葉子節點處各自數據目標變量的均值或對目標變量擬合的線性方程作為預測結果返回，則可分別構建出回歸樹預測模型與模型樹預測模型。本文就該兩種方法對降雨量預測性能作出了對比研究。

1.2 ?dsCART算法

在氣象信息系統中，往往需要利用最新收入的數據做天氣的實時預測。而傳統的預測天氣變化的算法一般只能對靜態數據進行處理。而增量學習具有在不訪問原有數據情況下，保留先前獲得的知識并學習新的信息的能力[12]。因此增量學習是處理這類問題的一個有效手段。Leszek Rutkowski等人提出了一種可用于處理數據流問題的dsCART算法，該算法具有增量學習能力。它需要解決的主要問題是確定每個節點中的最佳劃分屬性，因為在數據流情況下，數據集樣本被認為是無限大的，人們無法計算出無限數據集下的Gini增益值。因此，應該從當前節點的數據樣本中導出一個劃分屬性，該屬性需要滿足“它既是當前節點中的較優劃分屬性，同時也大概率會是整個數據流樣本中的較優劃分屬性”這一條件。為解決該問題，在dsCART算法中引入了一個約束參數θ，一個Gini增益約束函數[?G，K]。計算[Ai]每一個可能的劃分閾值[AiL]的Gini增益值[gq（AiL）]，由[gq（AiL）]導出節點[Lq]處屬性[ai]的Gini增益值[giq]，其中[giq=maxAiL∈Vi{gq（AiL）}]，通過[giq]得出兩個候選劃分屬性[ax]與[ay]：

[ax=argmaxai∈mq{giq}] ? （10）

[ay=argmaxai∈mq＼{ay}{giq}] ?（11）

式中，m是數據樣本中的屬性集合。確定候選劃分屬性后，分別計算Gini增益值[gxq]與[gyq]，并計算其差值與[?G，K]的關系，其中[?G，K]的表達式如下：

[?G，K=z（1-α）2Q（K）n] ?（12）

[Q（K）=5K2-8K+4] （13）

式中：α是一個固定的概率;[z（1-α）]是標準正態分布N（0，1）的第1-α個分位點;n是當前考慮節點中所有數據樣本的個數;K是類別數。如果[gxq-gyq>?G，K]或者[?G，K<θ]，則表明屬性[ax]比[ay]更適合作為劃分屬性，反之亦然，Leszek Rutkowski等人在本文中給出了該定理的證明。當確定好節點處的劃分屬性后，新的數據樣本加入到數據集中，原葉子節點中數據不再同屬一類時，根據上述過程再對節點進行劃分，并重新標記葉子節點。由此即可生成一棵可用于數據流的決策樹。

1.3 ?粒子群算法

粒子群算法（Particle ?Swarm ?Optimization，PSO）是一種常用的參數優化工具，是由Eberhart 和 Kennedy受到鳥類搜索食物活動的啟發后建立的一個簡化模型，其中，鳥群被抽象為一個“粒子群”，通過PSO算法，這些粒子被賦予一個初始的隨機解，包括隨機位置和速度。然后通過迭代讓粒子更新自己的位置與速度，直到迭代結束后便獲取到全局最優解。將該模型延伸到D維目標搜索空間，令粒子數為m，空間向量[Xi=（xi1，xi2，…，xiD）]，[Vi=（vi1，vi2，…，viD）]分別代表第i個粒子的位置與速度，其中i=1，2，…，m。對粒子的位置與速度進行迭代得到：

[vt+1id=w·vtid+c1·r1·（pid-xtid）+c2·r2·（pgd-xtid）] （14）

[xt+1id=xtid+vt+1id] （15）

式中：[pid=（pi1，pi2，…，piD）]是第i個粒子的最佳位置;[pgd=（pg1，pg2，…，pgD）]是群體的最佳位置;[xtid]與[vtid] 是在第t次迭代下第i個粒子的位置與速度;[c1]，[c2]，[r1]，[r2] 是0～1內的隨機數;w是PSO算法的慣性權重[13]。

粒子群算法能夠處理連續優化問題，搜索速度快并且結構簡單，易于實現，因此可以將該算法用于CART算法模型中以提高降雨量預測的準確性。

1.4 ?本文算法

文中，通過設定最小Gini增益值Gm讓算法判斷是否該進行此次劃分，并設定葉節點處的最少樣本數Cm讓算法在合適的時機停止劃分工作，防止“過擬合”現象的發生。然而在數據流的情況下，Gm與Cm的最優值也會隨著數據樣本的變化而改變，因此利用粒子群算法對原有的預測降雨算法進行了改進，設迭代次數為gen，種群規模為NP，最佳位置為Pbest，初始位置和速度分別為[x0i]，[v0i]。其優化算法執行流程如圖1所示。

同時，根據dsCART算法的思想，在選擇劃分屬性時通過計算當前節點[Lq]處的候選劃分屬性的Gini增益的差值大小來決定最終的劃分屬性，并對葉子節點的判定及標記添加了更新程序，其改進算法的具體執行過程在圖2中給出。其中，[giq]是葉節點[Lq]處屬性[ai]的Gini增益值，[nkq]是葉節點[Lq]中屬于第k類樣本數的個數，[nki，λ，q]是葉節點[Lq]處屬性[ai]值等于[aiλ]（[aiλ∈Ai]）的數據樣本中屬于第k類的樣本數的個數。

2 ?性能指標

文中使用一些性能指標來評價所構建模型的好壞，這些指標包括相關指數（R?Square）、均方根誤差（RMSE）和平均絕對誤差（MAE）。相關指數表征了預測值與實際值間擬合程度的高低;均方根誤差也被稱之為標準誤差，該值反映了預測值與實際值之間的偏差情況。

平均絕對誤差是將每個預測值與實際值的差值取絕對值再求和，再取均值后得到的，它避免了正負誤差相互抵消的問題。該三個指標的計算公式如下：

[R2=i=1N（yi-y）（pi-p）i=1N（yi-y）2·i=1N（pi-p）22] ?（16）

[RMSE=i=1N（yi-pi）2N] （17）

[MAE=1Ni=1Nyi-pi] ?（18）

式中：N代表樣本總數;yi與pi（i=1，2，…，N）分別代表第i個樣本的實際值與預測值;[y]與[p]分別代表實際值與預測值的平均值。

3 ?實驗結果及分析

3.1 ?數據選取及處理

為驗證所提出模型的有效性，本文選取了杭州蕭山氣象站在2008—2018年間的部分降雨數據。屬性類別包括日期、氣壓、溫度、露點、相對濕度、日降雨量。獲取到數據后需要對數據樣本中的缺失值進行填充，本文選擇用各氣象要素的中位數來代替要素中的缺失值。同時，將數據樣本中對預測結果沒有影響的項剔除掉，再對各有效氣象要素進行歸一化處理。最后，將氣壓、溫度、露點和相對濕度作為變量輸入到模型中，在葉節點處輸出降雨量的預測值。

3.2 ?回歸樹與模型樹預測結果對比

根據對葉節點處預測數值的分段常數估計和分段線性估計可分為回歸樹預測模型和模型樹預測模型。在本實驗中通過對比在不同訓練集數目兩種模型的相關指數、平均絕對誤差及均方根誤差的變化情況來選擇一個更適合預測降雨量的模型，并對該模型進行進一步的優化。該兩種模型的實驗結果如表1所示。當訓練集數目為1 800條時，兩個模型的預測結果圖時比如圖3所示。

由表1和圖3可以看出，隨著訓練集數目的增大，兩個模型的預測性能也在波動性的上升，整體來看，回歸樹的預測性能優于模型樹，但模型樹受訓練集數目變化的影響更小，其預測結果相對來說更加穩定。需要指出的是，此結果是在固定參數最小Gini增益值Gmin與葉節點最少樣本數Cmin的條件下得出的，可以看到，該參數值在數據樣本量為1 600和1 800時能取得較好的預測性能，而在小數據樣本量時，隨訓練集數目增加，模型的預測性能提升不大，這表明了該模型對參數Gmin與Cmin的值較為敏感。于是，本文利用粒子群算法對預測性能更好的回歸樹模型進行了進一步的優化。

3.3 ?PSO?CART模型預測結果分析

利用PSO算法將上述回歸樹預測模型按照圖1的流程進行優化后，得出了優化后預測模型的性能指標。圖4是在數據樣本量為1 800條時優化前后兩個模型的預測結果對比圖。圖5、圖6是隨著數據樣本量變化，模型優化前后的誤差變化情況。

由圖3、圖4可以看出，優化后的模型預測結果與實際值擬合程度更高，相關指數、均方根誤差、平均絕對誤差整體上也都優于優化前的模型，且隨著參數Gmin與Cmin的調整，該模型在全局的表現也更加穩定。由圖5可知，該模型的相關指數隨訓練數據集數值增加，整體呈上升趨勢，而誤差函數整體呈下降趨勢，當訓練集到達1 800條時，相關指數R?Square值到達0.65，平均絕對誤差下降為4.42，平均絕對誤差下降為7.02。實驗結果表明，該優化模型對實際值的擬合程度更高、誤差更小、更加穩定，證明了該優化方法的可行性。

同時，將訓練好的優化模型按照表1的步驟對CART算法的執行流程進行調整之后，該模型便具有了處理數據流問題的能力，整體而言，本文提出的優化及改進方法達到了預期效果。

4 ?結 ?論

本文首先就回歸樹與模型樹兩種模型對降雨量預測的性能做出了對比。實驗結果表明，模型樹的穩定性更好，其受訓練集樣本數量的影響較小，但整體的預測準確度要差于回歸樹;同時發現該算法對參數最小Gini增益值Gmin與最小葉節點樣本數Cmin的大小較為敏感，于是對性能表現相對更好的回歸樹模型進行了優化，通過PSO算法在二維目標空間搜索參數Gmin與Cmin的全局最優值。實驗結果證明，優化后的模型性能有了較為明顯的提升，且更加穩定。最后，將優化后的模型中CART算法選擇劃分屬性及生成、標記葉子節點的過程做了調整，使其具有了增量學習的能力，大大提高了該算法模型在氣象信息系統中的實用性。

參考文獻

[1] 周飛燕，金林鵬，董軍.卷積神經網絡研究綜述[J].計算機學報，2017，40（6）：1229?1251.

[2] GHIASSI M， FA′AL F， ABRISHAMCHI A. Large metropolitan water demand forcasting using DAN2， FTDNN， and KNN models： a case study of the city of Tehran， Iran [J]. Urban water journal， 2017， 14（6）： 655?659.

[3] YANG Yi， CHEN Wenguang. Taiga： performance optimization of the C4.5 decision tree construction algorithm [J]. Tsinghua science and technology， 2016， 21（4）： 415?425.

[4] STANGE R L， NETO J J. Applying adaptive technology in machine learning [J]. IEEE Latin America transactions， 2014， 12（7）： 1298?1306.

[5] RUTKOWSKI Leszek， JAWORSKI Maciej， PIETRUCZUK Lena， et al. The CART decision tree for mining data streams [J]. Information sciences， 2014（4）： 1?15.

[6] LIN C W， YANG L， FOURNIER?VIGER P， et al. A binary PSO approach to mine high?utility itemsets [J]. Soft computing， 2017， 21（17）： 5103?5121.

[7] 王子京，劉毓.決策樹ID3新屬性選擇方法[J].現代電子技術，2018，41（23）：9?12.

[8] 苗煜飛，張霄宏.決策樹C4.5算法的優化與應用[J].計算機工程與應用，2015，5（13）：255?258.

[9] 張亮，寧芊.CART決策樹的兩種改進及應用[J].計算機工程與設計，2015，36（5）：1209?1213.

[10] LAKKAKULA N P， NAIDU M M， REDDY K K. An entropy based elegant decision tree classifier to predict precipitation [C]// 2013 7th Asia Modelling Symposium. Hong Kong， China： IEEE， 2015： 11?19.

[11] PRASAD N， NAIDU M. Gain ratio as attribute selection measure in elegant decision tree to predict precipitation [C]// 2013 8th EUROSIM Congress on Modelling and Simulation. Cardiff： IEEE， 2013： 141?150.

[12] HACENE G B， GRIPON V， FARRUGIA N， et al. Transfer incremental learning using data augmentation [J]. Applied sciences?basel， 2018， 8（12）： 2512.

（上接第137頁）

[13] CHEN X， TIANFIELD H， MEI C L， et al. Biogeography?based learning particle swarm optimization [J]. Soft computing， 2017， 21（24）： 7519?7541.

[14] 羅麗娟，段隆振，段文影，等.C5.0算法的改進及應用[J].南昌大學學報（工科版），2017，39（1）：92?97.

作者簡介：李正方（1995—），男，四川巴中人，碩士研究生，研究方向為氣象數據分析與處理。

杜景林（1974—），男，河北承德人，博士，副教授，研究方向為計算機軟件和氣象傳感網技術。

周 ?蕓（1993—），女，江蘇蘇州人，碩士研究生，研究方向為氣象數據分析與處理。