摘要：數(shù)據(jù)挖掘中一項(xiàng)重要的方法是數(shù)據(jù)的分類，而決策樹是分類算法中一個(gè)主要的算法分支，決策樹算法是我們?cè)跀?shù)據(jù)挖掘中常常會(huì)用到的一種方法。本文重點(diǎn)介紹構(gòu)造決策樹過程中應(yīng)用最廣泛的ID3算法、C4.5算法和GART算法。

關(guān)鍵詞：數(shù)據(jù)挖掘；分類算法；決策樹；ID3、C4.5、GART算法

1.引言

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

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

2.決策樹的基本思想

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

3.決策樹的構(gòu)造

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

3.1分裂屬性的選擇

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

3.1.1 ID3算法

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

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

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

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

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

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

A對(duì)D劃分的期望信息為；

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

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

3.1.2 C4.5算法

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

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

信息增益率的定義是：

[gain_ratio（A）=gainAsplit_info（A）]

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

C4.5算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：用信息增益率來選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足；在樹構(gòu)造過程中進(jìn)行剪枝；能夠完成對(duì)連續(xù)屬性的離散化處理；能夠?qū)Σ煌暾臄?shù)據(jù)進(jìn)行處理。

3.1.3 GART算法

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

不純度的計(jì)算方式為：

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

Pi表示按某個(gè)變量劃分中，目標(biāo)變量不同類別的概率。某個(gè)自變量的Gini指標(biāo)的計(jì)算方式如下：

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

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

3.2樹的剪枝

即在構(gòu)建樹杈時(shí)，由于數(shù)據(jù)中的噪聲和離群點(diǎn)，許多分支反映的是訓(xùn)練數(shù)據(jù)中的異常，而樹剪枝則是處理這種過分?jǐn)M合的數(shù)據(jù)問題，常用的剪枝方法為先剪枝和后剪枝。

3.2.1先剪枝

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

3.2.2后剪枝

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

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

總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

作者簡(jiǎn)介：

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