決策樹算法的研究綜述

摘要：數據挖掘中一項重要的方法是數據的分類，而決策樹是分類算法中一個主要的算法分支，決策樹算法是我們在數據挖掘中常常會用到的一種方法。本文重點介紹構造決策樹過程中應用最廣泛的ID3算法、C4.5算法和GART算法。

關鍵詞：數據挖掘；分類算法；決策樹；ID3、C4.5、GART算法

1.引言

隨著計算機技術的不斷進步，現(xiàn)在已經是互聯(lián)網時代，互聯(lián)網時代背景下是海量的數據，在大數據背景下，我們需要對數據進行更高層次的分析，發(fā)現(xiàn)數據之前存在的一切潛在的聯(lián)系及規(guī)則。而數據挖掘技術便是將這些看似毫無規(guī)則，毫無聯(lián)系的數據進行預測分析，提取其中有用的信息的過程。

數據挖掘技術中常用的一種分類方法便是決策樹。決策樹是一個樹結構，其每個非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放一個類別。運用決策樹進行決策的過程就是從根節(jié)點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結果。決策樹的應用十分廣泛，目前決策樹成功運用于醫(yī)學，制造產業(yè)、天文學、分支生物學以及商業(yè)等諸多領域。

2.決策樹的基本思想

首先，樹以代表訓練樣本的單個結點開始，選擇最具有分類能力的屬性作為決策樹的當前結點。其次根據當前決策結點屬性取值的不用，將訓練樣本數據集分為若干子集，每個取值形成一個分枝。針對上一步得到的一個子集，重復進行先前步驟，形成每個劃分樣本上的決策樹，一旦一個屬性出現(xiàn)在一個結點上，就不必在該結點的任何后代考慮它。

3.決策樹的構造

決策樹的構造主要有兩個步驟：分裂屬性的選擇和樹剪枝。

3.1分裂屬性的選擇

分裂屬性的選擇就是選擇哪個自變量作為樹杈，即在n個自變量中，優(yōu)先選擇哪個自變量進行分叉，而采用何種計算方式選擇樹杈決定了決策樹算法的類型，典型的分裂屬性的選擇的方法有ID3算法、C4.5算法、CART算法三種，三種決策樹算法選擇樹杈的方式是不一樣的。

3.1.1 ID3算法

ID3算法是目前決策樹算法中較有影響力的算法，它是1986年由Quinlan 提出的，該算法只是一個啟發(fā)式算法。ID3算法的核心是判斷測試哪個屬性為最佳的分類屬性。ID3算法選擇分裂后信息增益最大的屬性進行分裂，以信息增益度量屬性選擇。ID3算法中常用到的兩個概念是熵和信息增益。

熵，是刻畫任意樣本例集的純度，如果目標屬性具有m個不同的值，那么D相對于m這個狀態(tài)的分類的熵定義為：

[info（D）=-i=1mpilog2（Pi）]

其中Pi表示Pi是m類別的比例。

一個屬性的信息增益就是由于使用這個屬性分割樣例而導致的期望熵降低，更精確來講，一個屬性A相對樣本例集合S的信息增益Gain（S，A）被定義為：

gain（A）=info（D）-infoA（D）

A對D劃分的期望信息為；

[infoA（D）=j=1vDjDinfo（Dj）]

ID3算法不足之處是只能處理離散型數據，信息增益的選擇分裂屬性的方式會偏向選擇具有大量值得屬性.

3.1.2 C4.5算法

ID3算法在實際應用中存在一些問題，于是Quilan在保留ID3算法優(yōu)點基礎上提出了C4.5算法，C4.5算法只是ID3算法的改進算法。C4.5算法采用最大信息增益率的屬性被選為分裂屬性。C4.5算法中用到了“分裂信息”這一概念，該概念可以表示為：

[split_infoA（D）=-j=1vDjDlog2DjD]

信息增益率的定義是：

[gain_ratio（A）=gainAsplit_info（A）]

C4.5算法是對ID3算法的一種改進，改進后可以計算連續(xù)型屬性的值。對于連續(xù)型屬性的值，只需將連續(xù)型變量由小到大遞增排序，取相鄰連個值的中點作為分裂點，然后按照離散型變量計算信息增益的方法計算信息增益，取其中最大的信息增益作為最終的分裂點。

C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進行了改進：用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；在樹構造過程中進行剪枝；能夠完成對連續(xù)屬性的離散化處理；能夠對不完整的數據進行處理。

3.1.3 GART算法

GART算法選擇分裂屬性的方式首先要計算不純度，然后利用不純度計算Gini指標，然后計算有效子集的不純度和Gini指標，選擇最小的Gini指標作為分裂屬性。

不純度的計算方式為：

[Gimi（D）=1-i=1MP2i]

Pi表示按某個變量劃分中，目標變量不同類別的概率。某個自變量的Gini指標的計算方式如下：

[Gini（D）=1-i=1MP2i]

D1和D2分別為按變量的子集所劃分出的兩個不同元組。

3.2樹的剪枝

即在構建樹杈時，由于數據中的噪聲和離群點，許多分支反映的是訓練數據中的異常，而樹剪枝則是處理這種過分擬合的數據問題，常用的剪枝方法為先剪枝和后剪枝。

3.2.1先剪枝

通過提前停止樹的構造，如通過決定在給定的節(jié)點不再分裂或劃分訓練元組的子集，而對樹剪枝，一旦停止，該結點即為樹葉。

3.2.2后剪枝

它由完全生長的樹剪去子樹，通過刪除節(jié)點的分支，并用樹葉替換它而剪掉給定節(jié)點的子樹，樹葉用被替換的子樹種最頻繁的類標記。

其中C4.5使用悲觀剪枝方法，CART采用后剪枝。

總結

數據挖掘中比較熱門的就是分類算法的研究，而決策樹算法是分類算法中最重要的，在我們的生活中也有著廣泛的應用，本文介紹了從最基本的決策樹的含義開始定義，到決策樹的基本思想，最后介紹了決策樹中經典的ID3算法、C4.5算法和CART算法。

參考文獻：

[1]韓家煒.數據挖掘：概念與技術第二版[M].北京：機械工業(yè)出版社，2001.

[2]王艷兵，趙銳，姚青.基于可變精度的 ID3 改進算法[J].計算機工程與設計，2006，27（14）：2683-2685.

[3]韓松來，張輝，周華平.基于關聯(lián)度函數的決策樹分類算法[J]，計算機應用，2005，25（11）：2655-2657.

[4]Quinlan J R. Introduction of Decision Tree[J].Machine Learning， 1986.

[5]謝金梅，王艷妮.決策樹算法綜述[J].軟件導報，2008，7（11）： 83-85.

作者簡介：

田欣（1992.02- ），女，漢族，河北石家莊人，碩士研究生在讀，現(xiàn)就讀于河北大學管理學院，管理科學與工程專業(yè)。