決策樹（Decision Tree）是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評(píng)價(jià)項(xiàng)目風(fēng)險(xiǎn)，判斷其可行性的決策分析方法，是直觀運(yùn)用概率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。在機(jī)器學(xué)習(xí)中，決策樹是一個(gè)預(yù)測(cè)模型，他代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。Entropy ＝ 系統(tǒng)的凌亂程度，使用算法ID3， C4．5和C5．0生成樹算法使用熵。這一度量是基于信息學(xué)理論中熵的概念。

決策樹是一種樹形結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉節(jié)點(diǎn)代表一種類別。

分類樹（決策樹）是一種十分常用的分類方法。它是一種監(jiān)督學(xué)習(xí)，所謂監(jiān)督學(xué)習(xí)就是給定一堆樣本，每個(gè)樣本都有一組屬性和一個(gè)類別，這些類別是事先確定的，那么通過學(xué)習(xí)得到一個(gè)分類器，這個(gè)分類器能夠?qū)π鲁霈F(xiàn)的對(duì)象給出正確的分類。這樣的機(jī)器學(xué)習(xí)就被稱之為監(jiān)督學(xué)習(xí)。

機(jī)器學(xué)習(xí)中，決策樹是一個(gè)預(yù)測(cè)模型；他代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。樹中每個(gè)節(jié)點(diǎn)表示某個(gè)對(duì)象，而每個(gè)分叉路徑則代表的某個(gè)可能的屬性值，而每個(gè)葉結(jié)點(diǎn)則對(duì)應(yīng)從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)所經(jīng)歷的路徑所表示的對(duì)象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨(dú)立的決策樹以處理不同輸出。數(shù)據(jù)挖掘中決策樹是一種經(jīng)常要用到的技術(shù)，可以用于分析數(shù)據(jù)，同樣也可以用來作預(yù)測(cè)。

從數(shù)據(jù)產(chǎn)生決策樹的機(jī)器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí)， 通俗說就是決策樹。

一個(gè)決策樹包含三種類型的節(jié)點(diǎn)：

●決策節(jié)點(diǎn)：通常用矩形框來表示

●機(jī)會(huì)節(jié)點(diǎn)：通常用圓圈來表示

●終結(jié)點(diǎn)：通常用三角形來表示

決策樹學(xué)習(xí)也是資料探勘中一個(gè)普通的方法。在這里，每個(gè)決策樹都表述了一種樹型結(jié)構(gòu)，它由它的分支來對(duì)該類型的對(duì)象依靠屬性進(jìn)行分類。每個(gè)決策樹可以依靠對(duì)源數(shù)據(jù)庫的分割進(jìn)行數(shù)據(jù)測(cè)試。這個(gè)過程可以遞歸式的對(duì)樹進(jìn)行修剪。 當(dāng)不能再進(jìn)行分割或一個(gè)單獨(dú)的類可以被應(yīng)用于某一分支時(shí)，遞歸過程就完成了。另外，隨機(jī)森林分類器將許多決策樹結(jié)合起來以提升分類的正確率。

決策樹同時(shí)也可以依靠計(jì)算條件概率來構(gòu)造。

決策樹如果依靠數(shù)學(xué)的計(jì)算方法可以取得更加理想的效果。 數(shù)據(jù)庫已如下所示：

（x， y） ＝ （x1， x2， x3…， xk， y）

相關(guān)的變量 Y 表示我們嘗試去理解，分類或者更一般化的結(jié)果。 其他的變量x1， x2， x3 等則是幫助我們達(dá)到目的的變量。

優(yōu)點(diǎn)

決策樹易于理解和實(shí)現(xiàn)，人們?cè)谠趯W(xué)習(xí)過程中不需要使用者了解很多的背景知識(shí)，這同時(shí)是它的能夠直接體現(xiàn)數(shù)據(jù)的特點(diǎn)，只要通過解釋后都有能力去理解決策樹所表達(dá)的意義。

對(duì)于決策樹，數(shù)據(jù)的準(zhǔn)備往往是簡(jiǎn)單或者是不必要的，而且能夠同時(shí)處理數(shù)據(jù)型和常規(guī)型屬性，在相對(duì)短的時(shí)間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果。

易于通過靜態(tài)測(cè)試來對(duì)模型進(jìn)行評(píng)測(cè)，可以測(cè)定模型可信度；如果給定一個(gè)觀察的模型，那么根據(jù)所產(chǎn)生的決策樹很容易推出相應(yīng)的邏輯表達(dá)式。

缺點(diǎn)

1）對(duì)連續(xù)性的字段比較難預(yù)測(cè)。

2）對(duì)有時(shí)間順序的數(shù)據(jù)，需要很多預(yù)處理的工作。

3）當(dāng)類別太多時(shí)，錯(cuò)誤可能就會(huì)增加的比較快。

4）一般的算法分類的時(shí)候，只是根據(jù)一個(gè)字段來分類。

算法

1、C4．5

C4．5算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：

1） 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足；

2） 在樹構(gòu)造過程中進(jìn)行剪枝；

3） 能夠完成對(duì)連續(xù)屬性的離散化處理；

4） 能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。

C4．5算法有如下優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點(diǎn)是：在構(gòu)造樹的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4．5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)程序無法運(yùn)行。

具體算法步驟如下；

1創(chuàng)建節(jié)點(diǎn)N

2如果訓(xùn)練集為空，在返回節(jié)點(diǎn)N標(biāo)記為Failure

3如果訓(xùn)練集中的所有記錄都屬于同一個(gè)類別，則以該類別標(biāo)記節(jié)點(diǎn)N

4如果候選屬性為空，則返回N作為葉節(jié)點(diǎn)，標(biāo)記為訓(xùn)練集中最普通的類；

5for each 候選屬性 attribute＿list

6if 候選屬性是連續(xù)的then

7對(duì)該屬性進(jìn)行離散化

8選擇候選屬性attribute＿list中具有最高信息增益率的屬性D

9標(biāo)記節(jié)點(diǎn)N為屬性D

10for each 屬性D的一致值d

11由節(jié)點(diǎn)N長(zhǎng)出一個(gè)條件為D＝d的分支

12設(shè)s是訓(xùn)練集中D＝d的訓(xùn)練樣本的集合

13if s為空

14加上一個(gè)樹葉，標(biāo)記為訓(xùn)練集中最普通的類

15else加上一個(gè)有C4．5（R － ｛D｝，C，s）返回的點(diǎn)

2、CART

背景：

分類與回歸樹（CART——Classification And Regression Tree）） 是一種非常有趣并且十分有效的非參數(shù)分類和回歸方法。它通過構(gòu)建二叉樹達(dá)到預(yù)測(cè)目的。

分類與回歸樹CART 模型最早由Breiman 等人提出，已經(jīng)在統(tǒng)計(jì)領(lǐng)域和數(shù)據(jù)挖掘技術(shù)中普遍使用。它采用與傳統(tǒng)統(tǒng)計(jì)學(xué)完全不同的方式構(gòu)建預(yù)測(cè)準(zhǔn)則，它是以二叉樹的形式給出，易于理解、使用和解釋。由CART 模型構(gòu)建的預(yù)測(cè)樹在很多情況下比常用的統(tǒng)計(jì)方法構(gòu)建的代數(shù)學(xué)預(yù)測(cè)準(zhǔn)則更加準(zhǔn)確，且數(shù)據(jù)越復(fù)雜、變量越多，算法的優(yōu)越性就越顯著。模型的關(guān)鍵是預(yù)測(cè)準(zhǔn)則的構(gòu)建，準(zhǔn)確的。

定義：

分類和回歸首先利用已知的多變量數(shù)據(jù)構(gòu)建預(yù)測(cè)準(zhǔn)則， 進(jìn)而根據(jù)其它變量值對(duì)一個(gè)變量進(jìn)行預(yù)測(cè)。在分類中， 人們往往先對(duì)某一客體進(jìn)行各種測(cè)量， 然后利用一定的分類準(zhǔn)則確定該客體歸屬那一類。例如， 給定某一化石的鑒定特征， 預(yù)測(cè)該化石屬那一科、那一屬， 甚至那一種。另外一個(gè)例子是， 已知某一地區(qū)的地質(zhì)和物化探信息， 預(yù)測(cè)該區(qū)是否有礦�；貧w則與分類不同， 它被用來預(yù)測(cè)客體的某一數(shù)值， 而不是客體的歸類。例如， 給定某一地區(qū)的礦產(chǎn)資源特征， 預(yù)測(cè)該區(qū)的資源量。