李正方 杜景林 周蕓

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

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

中圖分類號： 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 ?引 ?言

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

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

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

1 ?相關算法分析

1.1 ?CART算法

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

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

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

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

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

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

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

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

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

CART算法中的分割度量函數(shù)被定義為基尼指數(shù)與加權基尼指數(shù)之間的差值。該分割度量函數(shù)被稱為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）]的值被稱為數(shù)據(jù)集[Sq]中屬性[ai]的Gini增益。能使得Gini增益取得最大值的屬性則作為劃分屬性，并將節(jié)點[L0]劃分為兩個子節(jié)點[Llast+1]和[Llast+2]，last代表最近一次在整個樹中創(chuàng)建的節(jié)點的索引值。假設屬性[ax]具有最大的Gini增益值，則讓子集[Slast+1=Lxq]和[Slast+2=Rxq]分別在節(jié)點[Llast+1]和[Llast+2]上執(zhí)行上述操作。當節(jié)點中的可用屬性只剩下一個或子集[Sq]中所有元素都來自同一類時停止劃分，并將該節(jié)點標記為葉子節(jié)點。此時，若將葉子節(jié)點處各自數(shù)據(jù)目標變量的均值或對目標變量擬合的線性方程作為預測結果返回，則可分別構建出回歸樹預測模型與模型樹預測模型。本文就該兩種方法對降雨量預測性能作出了對比研究。

1.2 ?dsCART算法

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

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

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

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

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

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

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

1.3 ?粒子群算法

粒子群算法（Particle ?Swarm ?Optimization，PSO）是一種常用的參數(shù)優(yōu)化工具，是由Eberhart 和 Kennedy受到鳥類搜索食物活動的啟發(fā)后建立的一個簡化模型，其中，鳥群被抽象為一個“粒子群”，通過PSO算法，這些粒子被賦予一個初始的隨機解，包括隨機位置和速度。然后通過迭代讓粒子更新自己的位置與速度，直到迭代結束后便獲取到全局最優(yōu)解。將該模型延伸到D維目標搜索空間，令粒子數(shù)為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內的隨機數(shù);w是PSO算法的慣性權重[13]。

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

1.4 ?本文算法

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

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

2 ?性能指標

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

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

[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代表樣本總數(shù);yi與pi（i=1，2，…，N）分別代表第i個樣本的實際值與預測值;[y]與[p]分別代表實際值與預測值的平均值。

3 ?實驗結果及分析

3.1 ?數(shù)據(jù)選取及處理

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

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

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

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

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

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

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

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

4 ?結 ?論

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

參考文獻

[1] 周飛燕，金林鵬，董軍.卷積神經(jīng)網(wǎng)絡研究綜述[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].現(xiàn)代電子技術，2018，41（23）：9?12.

[8] 苗煜飛，張霄宏.決策樹C4.5算法的優(yōu)化與應用[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—），男，四川巴中人，碩士研究生，研究方向為氣象數(shù)據(jù)分析與處理。

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

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