基于C4.5决策树算法的全国积雪模型生成

陈 凯 ，曹晓光 ，杨冀红 ，史良树 ，战 鹰

（1.北京航空航天大学图像中心 北京 100191；2.中国土地勘测规划研究院 北京 100035）

基于C4.5决策树算法的全国积雪模型生成

陈 凯1，曹晓光1，杨冀红2，史良树2，战 鹰2

（1.北京航空航天大学图像中心 北京 100191；2.中国土地勘测规划研究院 北京 100035）

C4.5算法是进行数据分类分析的经典决策树数据挖掘算法。本文介绍了决策树及其常用算法，并根据1971-2000年全国气象站点记录的数据信息，采用C4.5决策树算法建立全国积雪模型。通过积雪模型预测区域积雪分布情况的实验表明正确率达到83.96%，可以用于辅助遥感图像雪区检测进行判断决策。

C4.5；决策树；数据挖掘；积雪模型

随着现代气象观测技术的迅速发展和通信传输能力的不断加强，各级气象部门可获得的气象资料日益丰富，在海量的气象数据中却隐藏着很多重要的知识和信息。数据挖掘作为一门多学科的交叉性学科，主要研究从现存的大量的数据中通过加工处理，探寻出有用的、有潜在价值并且是可以被理解的信息或知识，从而为正确决策提供数据支持。决策树是数据挖掘的重要分支，主要研究从一组毫无次序和规律的事例中推理出决策树形式的分类规则，用于预测未知数据样本的类别，由于其具有数据分析效率高、简单直观、容易理解等优点，在越来越多的领域得到了广泛应用，并取得了较好的效果[1]。

论文利用数据挖掘中的C4.5决策树算法，对《中国国际交换站地面气候标准值月值数据集（1971-2000年）》中的气象数据进行分析，创建全国积雪模型，可用于预测具体区域特定月份的积雪情况，该模型可用于遥感图像雪区判别中提供新思路或作为辅助验证方法。

1 决策树概述

决策树起源于概念学习系统CLS(concept learning system)。CLS最早由Hun.t E.B等人于1966年提出,并首次用决策树进行概念学习,后来的许多决策树学习算法都可以看作是CLS算法的改进与更新。决策树是一种树结构，其内部节点是决策节点，表示对数据实例在某个属性上的测试；叶子节点代表类别，而每个分支则表示一个测试输出。为了对测试样本进行分类，在决策树上从根节点开始，自上而下地对测试样本的属性值进行测试，直到测试样本到达一个表示该样本预测结果的叶子节点[2-3]。建立有效的决策树，不仅需要考虑分类的正确性，而且需要考虑决策树的复杂程度，即在保证具有一定的分类正确率条件下，越简化越好[4]。

2 C4.5算法

决策树学习算法是以一组样本数据集为基础的一种归纳学习算法，它着眼于从一组无次序、无规则的样本数据中推理出决策树表示形式的分类规则。1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上，1993年Quinlan又提出了C4.5算法。由于C4.5算法是ID3算法的改进，所以在研究C4.5算法前，首先分析一下ID3算法的原理。

2.1 ID3算法

决策树的生成过程也就是一个树的节点的选择过程，计算所有属性的信息增益，选择信息增益最大的属性作为根节点。

1）计算给定的训练数据集分类的信息期望I

设S是s个数据样本的集合。假定类标号属性具有m个不同类Ci(i=1，2，…，m)。设si是类 Ci中的样本数。对一个给定的样本分类所需的信息量由下式给出[5]：

2）计算属性A的信息熵

设属性 A具有 v个不同值 ｛a1， a2，…，av｝。 可以用属性A将S划分为v个子集 ｛S1， S2，…，Sv｝，其中 Sj包含 S中这样一些样本，它们在A上具有相同的值aj(j=1，2，…v)。设sij是子集Sj中属于类Cj的样本数。由属性A划分成子集的信息熵由下式给出：

对于给定的子集Sj，其信息量为：

3）计算属性A的信息增益Gain(A)

信息增益Gain(A)越大，则属性A对于分类提供的信息量越大，则选择属性A之后对于分类的不确定程度越小。因此将计算出的各个属性的信息增益对比，选择信息增益最大的属性作为根节点。由根节点属性的不同取值建立分支，采用递归的方法,对各分支的子集仍然选择信息增益最大的属性作为子节点，直到所有的子集包含同一类别的数据为止。由以上步骤就能构造一棵决策树,可以用它来对新的样本进行分类。

2.2 C4.5算法

C4.5算法是由Quinlan自己扩充ID3算法提出来的，它克服了ID3的不足，主要在以下几个方面做出了改进[6]：1）用信息增益率代替信息增益来选择属性；2）在决策树构造过程中或者构造完成之后，进行剪枝；3）能够完成对连续属性的离散化处理；4）能够处理不完整数据，如未知的属性值；5）可以根据决策树转化为产生式规则[7]。具体介绍如下。2.2.1 信息增益率

信息增益率是在信息增益基础上发展起来的，设属性A具有 v个不同值 ｛a1，a2，…，av｝。 可以用属性A将S划分为v个子集 ｛S1， S2，…Sv｝，其中Sj包含S中这样一些样本，它们在A上具有相同的值aj(j=1，2，…，v）。假如以属性A的值为基准，SplitI(A)对样本进行分割，就是熵的概念，属性A的信息增益率可用下式计算：

2.2.2 连续属性处理

C4.5算法对连续属性值的一般处理过程是：1）对属性值的数据集进行排序；2）根据不同的阈值动态地对数据集进行划分；3）输出改变时确定一个阈值；4）取两个实际值的中点作为一个阈值；5）取两个划分，所有样本都在所取的这两个划分中；6）得出所有可能的阈值、增益以及增益比；7）每一个属性会变成有两种取值，即小于阈值或大于等于阈值。

2.2.3 C4.5算法的描述

具体C4.5算法流程如表1所示。

表1 C4.5算法流程Tab.1 C4.5 algorithm process

2.2.4 C4.5决策树的剪枝

剪枝即是删除一些最不可靠的分枝，用多个类的叶节点代替，以加快分类的速度和提高决策树正确分类新数据的能力。常用的剪枝方法有预剪枝和后剪枝：预剪枝就是提早结束决策树的构造过程，通过选取一个阈值判断树的构造是否停止，因为适当的阈值很难界定，所以预剪枝存在危险，不能保证树的可靠性；后剪枝是在决策树构造完毕后得到一棵完整的树再进行剪枝，通常的思想是对每个树节点进行错误估计，通过与其子树的错误估计的比较，来判断子树的裁剪，如果子树的错误估计较大，则被剪枝，最后用一个独立的测试集去评估剪枝后的准确率，以此得到估计错误率最小的决策树。C4.5的剪枝技术是基于悲观错误的后剪枝方法，首先把构造的决策树转换成规则集合，然后通过删去某些条件来使得规则变短或变少。

3 基于C4.5算法创建全国积雪模型

3.1 数据准备和预处理

本文由中国气象科学数据共享服务网下载气象数据《中国国际交换站地面气候标准值月值数据集 （1971-2000年）》，该数据集为中国722个基本、基准地面气象观测站1971-2000年数据集，数据集内容包括累年月气温、气压、降水、水汽压、云、天气现象、蒸发、积雪、风、地面温度、冻土、日照等13个要素的数据，部分数据如表2所示。

表2中国国际交换站地面气候标准值月值数据集（1971-2000年）Tab.2 Standard monthly data of surface climate of China international exchange station

考虑实际可提供的属性信息有限，本次试验生成积雪模型过程中选择纬度、经度、海拔、月份四个属性数据。剔除无效数据样本，并将数据集中各月积雪日作为类别属性，用于表征特定区域每个月的积雪情况。按照实际需求，本文按照各月积雪天数分成以下六种积雪情况：[0,1)天为0类，[1,4)天为1类，[4,7)天为 2类，[7,11)天为3类，[11,21)天为 4类，[21,31]天为5类。

3.2 构造决策树

为了使训练数据集更具有说服力，选取各省90%站点的气象数据作为训练样本，共7 680个训练样本，其余站点共804个数据记录作为测试样本。按照上节描述的C4.5算法，生成最终的决策树，部分决策树如图1所示，即得到了全国的积雪分布模型。

图1 全国积雪情况判别决策树（部分）Fig.1 Dicision tree of national snow-cover distribution

经过804个测试数据样本验证，采用C4.5决策树算法建立的全国积雪分布模型的正确率达到83.96%，具体混淆矩阵如表3所示。由混淆矩阵可以看出，0类数据分类结果正确率最高，1类数据的正确率也较好，2类、3类、4类由于数据样本少，导致分类错误较多，而5类由于与其他类别数据差别较大，所以虽然样本少，但正确率也较高。总体来说，根据某一区域的经纬度、月份、海拔高度信息，利用该积雪模型就能够进行积雪情况的初步判断，从而辅助后续遥感图像雪区判别的决策与处理。

表3混淆矩阵Tab.3 Confusion matrix

4 结论

决策树算法有广泛的应用，C4.5算法在ID3算法基础上进行了改进，是决策树中经典的算法。本文采用C4.5算法对气象数据进行分类规则挖掘，创建全国积雪模型。实验表明，采用该方法生成的模型能够有效预测区域积雪情况，为遥感图像雪区判别提供了新思路或作为辅助验证方法。

[1]张波.数据挖掘在气象中的应用研究与实现[D].成都:电子科技大学,2012.

[2]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社,2005.

[3]Bing Liu.Web数据挖掘[M].北京:清华大学出版社,2009.

[4]周琦.改进的C4.5决策树算法研究及在高考成绩预测分析中的应用[D].南宁:广西大学,2012.

[5]邹志文,朱金伟.数据挖掘算法研究与综述[J].计算机工程与设计,2005,36(9):2304-2305.

ZOU Zhi-wen,ZHU Jin-wei.Research and summary of data mining algorithms[J].Computer Engineering and Design,2005,36(9):2304-2305.

[6]罗可.数据挖掘中分类算法综述[J].计算机工程,2005,31(2):31-33.

LUO Ke.Review of classification algorithms in data mining[J].Computer Engineering,2005,31(2):31-33.

[7]曲守宁,卢健.C4.5分类算法在硕士研究生智育测评中的应用[J].济南大学学报：自然科学版,2009,23(3):253-256.

QU Shou-ning,LU Jian.Application of C4.5 classification algorithm in the survey and evaluation of postgraduate intellectual education[J].Journal of University of Jinan：Science and Technology,2009,23(3):253-256.

A method of generating national snow-cover model based on C4.5 algorithm of decision tree

CHEN Kai1,CAO Xiao-guang1,YANG Ji-hong2,SHI Liang-shu2,ZHAN Ying2
（1.Image Processing Center of Beihang University,Beijing 100191,China;2.China Land Surveying and Planning Institute,Beijing 100035,China）

The C4.5 algorithm of decision tree is one of classic data mining algorithms to analysis data classification.After the introduction of commonly used decision tree algorithms,a method of generating national snow-cover model based on C4.5 algorithm with the national meteorological stations recorded data of 1971-2000 is proposed in this paper.Experiments show that the accuracy rate of prediction of snow-cover distribution achieves 83.96%,which means that the method can be used to assist system to make reasonable decision in the project like the detection of snow-cover in the remote sensing images.

C4.5;decision tree;data mining;snow-cover model

TN959.4

A

1674-6236（2014）17-044-04

2013-11-20 稿件编号：201311179

陈 凯（1987—），男，河北秦皇岛人，硕士研究生。研究方向：图像处理、模式识别、机器学习。