基于改进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—），女，江苏苏州人，硕士研究生，研究方向为气象数据分析与处理。