基于C4.5決策樹算法的全國積雪模型生成

陳 凱 ，曹曉光 ，楊冀紅 ，史良樹 ，戰(zhàn) 鷹

（1.北京航空航天大學圖像中心 北京 100191；2.中國土地勘測規(guī)劃研究院 北京 100035）

基于C4.5決策樹算法的全國積雪模型生成

陳 凱1，曹曉光1，楊冀紅2，史良樹2，戰(zhàn) 鷹2

（1.北京航空航天大學圖像中心 北京 100191；2.中國土地勘測規(guī)劃研究院 北京 100035）

C4.5算法是進行數(shù)據(jù)分類分析的經(jīng)典決策樹數(shù)據(jù)挖掘算法。本文介紹了決策樹及其常用算法，并根據(jù)1971-2000年全國氣象站點記錄的數(shù)據(jù)信息，采用C4.5決策樹算法建立全國積雪模型。通過積雪模型預測區(qū)域積雪分布情況的實驗表明正確率達到83.96%，可以用于輔助遙感圖像雪區(qū)檢測進行判斷決策。

C4.5；決策樹；數(shù)據(jù)挖掘；積雪模型

隨著現(xiàn)代氣象觀測技術的迅速發(fā)展和通信傳輸能力的不斷加強，各級氣象部門可獲得的氣象資料日益豐富，在海量的氣象數(shù)據(jù)中卻隱藏著很多重要的知識和信息。數(shù)據(jù)挖掘作為一門多學科的交叉性學科，主要研究從現(xiàn)存的大量的數(shù)據(jù)中通過加工處理，探尋出有用的、有潛在價值并且是可以被理解的信息或知識，從而為正確決策提供數(shù)據(jù)支持。決策樹是數(shù)據(jù)挖掘的重要分支，主要研究從一組毫無次序和規(guī)律的事例中推理出決策樹形式的分類規(guī)則，用于預測未知數(shù)據(jù)樣本的類別，由于其具有數(shù)據(jù)分析效率高、簡單直觀、容易理解等優(yōu)點，在越來越多的領域得到了廣泛應用，并取得了較好的效果[1]。

論文利用數(shù)據(jù)挖掘中的C4.5決策樹算法，對《中國國際交換站地面氣候標準值月值數(shù)據(jù)集（1971-2000年）》中的氣象數(shù)據(jù)進行分析，創(chuàng)建全國積雪模型，可用于預測具體區(qū)域特定月份的積雪情況，該模型可用于遙感圖像雪區(qū)判別中提供新思路或作為輔助驗證方法。

1 決策樹概述

決策樹起源于概念學習系統(tǒng)CLS(concept learning system)。CLS最早由Hun.t E.B等人于1966年提出,并首次用決策樹進行概念學習,后來的許多決策樹學習算法都可以看作是CLS算法的改進與更新。決策樹是一種樹結構，其內(nèi)部節(jié)點是決策節(jié)點，表示對數(shù)據(jù)實例在某個屬性上的測試；葉子節(jié)點代表類別，而每個分支則表示一個測試輸出。為了對測試樣本進行分類，在決策樹上從根節(jié)點開始，自上而下地對測試樣本的屬性值進行測試，直到測試樣本到達一個表示該樣本預測結果的葉子節(jié)點[2-3]。建立有效的決策樹，不僅需要考慮分類的正確性，而且需要考慮決策樹的復雜程度，即在保證具有一定的分類正確率條件下，越簡化越好[4]。

2 C4.5算法

決策樹學習算法是以一組樣本數(shù)據(jù)集為基礎的一種歸納學習算法，它著眼于從一組無次序、無規(guī)則的樣本數(shù)據(jù)中推理出決策樹表示形式的分類規(guī)則。1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎上，1993年Quinlan又提出了C4.5算法。由于C4.5算法是ID3算法的改進，所以在研究C4.5算法前，首先分析一下ID3算法的原理。

2.1 ID3算法

決策樹的生成過程也就是一個樹的節(jié)點的選擇過程，計算所有屬性的信息增益，選擇信息增益最大的屬性作為根節(jié)點。

1）計算給定的訓練數(shù)據(jù)集分類的信息期望I

設S是s個數(shù)據(jù)樣本的集合。假定類標號屬性具有m個不同類Ci(i=1，2，…，m)。設si是類 Ci中的樣本數(shù)。對一個給定的樣本分類所需的信息量由下式給出[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的樣本數(shù)。由屬性A劃分成子集的信息熵由下式給出：

對于給定的子集Sj，其信息量為：

3）計算屬性A的信息增益Gain(A)

信息增益Gain(A)越大，則屬性A對于分類提供的信息量越大，則選擇屬性A之后對于分類的不確定程度越小。因此將計算出的各個屬性的信息增益對比，選擇信息增益最大的屬性作為根節(jié)點。由根節(jié)點屬性的不同取值建立分支，采用遞歸的方法,對各分支的子集仍然選擇信息增益最大的屬性作為子節(jié)點，直到所有的子集包含同一類別的數(shù)據(jù)為止。由以上步驟就能構造一棵決策樹,可以用它來對新的樣本進行分類。

2.2 C4.5算法

C4.5算法是由Quinlan自己擴充ID3算法提出來的，它克服了ID3的不足，主要在以下幾個方面做出了改進[6]：1）用信息增益率代替信息增益來選擇屬性；2）在決策樹構造過程中或者構造完成之后，進行剪枝；3）能夠完成對連續(xù)屬性的離散化處理；4）能夠處理不完整數(shù)據(jù)，如未知的屬性值；5）可以根據(jù)決策樹轉化為產(chǎn)生式規(guī)則[7]。具體介紹如下。2.2.1 信息增益率

信息增益率是在信息增益基礎上發(fā)展起來的，設屬性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 連續(xù)屬性處理

C4.5算法對連續(xù)屬性值的一般處理過程是：1）對屬性值的數(shù)據(jù)集進行排序；2）根據(jù)不同的閾值動態(tài)地對數(shù)據(jù)集進行劃分；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決策樹的剪枝

剪枝即是刪除一些最不可靠的分枝，用多個類的葉節(jié)點代替，以加快分類的速度和提高決策樹正確分類新數(shù)據(jù)的能力。常用的剪枝方法有預剪枝和后剪枝：預剪枝就是提早結束決策樹的構造過程，通過選取一個閾值判斷樹的構造是否停止，因為適當?shù)拈撝岛茈y界定，所以預剪枝存在危險，不能保證樹的可靠性；后剪枝是在決策樹構造完畢后得到一棵完整的樹再進行剪枝，通常的思想是對每個樹節(jié)點進行錯誤估計，通過與其子樹的錯誤估計的比較，來判斷子樹的裁剪，如果子樹的錯誤估計較大，則被剪枝，最后用一個獨立的測試集去評估剪枝后的準確率，以此得到估計錯誤率最小的決策樹。C4.5的剪枝技術是基于悲觀錯誤的后剪枝方法，首先把構造的決策樹轉換成規(guī)則集合，然后通過刪去某些條件來使得規(guī)則變短或變少。

3 基于C4.5算法創(chuàng)建全國積雪模型

3.1 數(shù)據(jù)準備和預處理

本文由中國氣象科學數(shù)據(jù)共享服務網(wǎng)下載氣象數(shù)據(jù)《中國國際交換站地面氣候標準值月值數(shù)據(jù)集 （1971-2000年）》，該數(shù)據(jù)集為中國722個基本、基準地面氣象觀測站1971-2000年數(shù)據(jù)集，數(shù)據(jù)集內(nèi)容包括累年月氣溫、氣壓、降水、水汽壓、云、天氣現(xiàn)象、蒸發(fā)、積雪、風、地面溫度、凍土、日照等13個要素的數(shù)據(jù)，部分數(shù)據(jù)如表2所示。

表2中國國際交換站地面氣候標準值月值數(shù)據(jù)集（1971-2000年）Tab.2 Standard monthly data of surface climate of China international exchange station

考慮實際可提供的屬性信息有限，本次試驗生成積雪模型過程中選擇緯度、經(jīng)度、海拔、月份四個屬性數(shù)據(jù)。剔除無效數(shù)據(jù)樣本，并將數(shù)據(jù)集中各月積雪日作為類別屬性，用于表征特定區(qū)域每個月的積雪情況。按照實際需求，本文按照各月積雪天數(shù)分成以下六種積雪情況：[0,1)天為0類，[1,4)天為1類，[4,7)天為 2類，[7,11)天為3類，[11,21)天為 4類，[21,31]天為5類。

3.2 構造決策樹

為了使訓練數(shù)據(jù)集更具有說服力，選取各省90%站點的氣象數(shù)據(jù)作為訓練樣本，共7 680個訓練樣本，其余站點共804個數(shù)據(jù)記錄作為測試樣本。按照上節(jié)描述的C4.5算法，生成最終的決策樹，部分決策樹如圖1所示，即得到了全國的積雪分布模型。

圖1 全國積雪情況判別決策樹（部分）Fig.1 Dicision tree of national snow-cover distribution

經(jīng)過804個測試數(shù)據(jù)樣本驗證，采用C4.5決策樹算法建立的全國積雪分布模型的正確率達到83.96%，具體混淆矩陣如表3所示。由混淆矩陣可以看出，0類數(shù)據(jù)分類結果正確率最高，1類數(shù)據(jù)的正確率也較好，2類、3類、4類由于數(shù)據(jù)樣本少，導致分類錯誤較多，而5類由于與其他類別數(shù)據(jù)差別較大，所以雖然樣本少，但正確率也較高?？傮w來說，根據(jù)某一區(qū)域的經(jīng)緯度、月份、海拔高度信息，利用該積雪模型就能夠進行積雪情況的初步判斷，從而輔助后續(xù)遙感圖像雪區(qū)判別的決策與處理。

表3混淆矩陣Tab.3 Confusion matrix

4 結論

決策樹算法有廣泛的應用，C4.5算法在ID3算法基礎上進行了改進，是決策樹中經(jīng)典的算法。本文采用C4.5算法對氣象數(shù)據(jù)進行分類規(guī)則挖掘，創(chuàng)建全國積雪模型。實驗表明，采用該方法生成的模型能夠有效預測區(qū)域積雪情況，為遙感圖像雪區(qū)判別提供了新思路或作為輔助驗證方法。

[1]張波.數(shù)據(jù)挖掘在氣象中的應用研究與實現(xiàn)[D].成都:電子科技大學,2012.

[2]Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術[M].北京:機械工業(yè)出版社,2005.

[3]Bing Liu.Web數(shù)據(jù)挖掘[M].北京:清華大學出版社,2009.

[4]周琦.改進的C4.5決策樹算法研究及在高考成績預測分析中的應用[D].南寧:廣西大學,2012.

[5]鄒志文,朱金偉.數(shù)據(jù)挖掘算法研究與綜述[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]羅可.數(shù)據(jù)挖掘中分類算法綜述[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—），男，河北秦皇島人，碩士研究生。研究方向：圖像處理、模式識別、機器學習。