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

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

分類樹（決策樹）是一種十分常用的分類方法。它是一種監(jiān)督學習，所謂監(jiān)督學習就是給定一堆樣本，每個樣本都有一組屬性和一個類別，這些類別是事先確定的，那么通過學習得到一個分類器，這個分類器能夠對新出現(xiàn)的對象給出正確的分類。這樣的機器學習就被稱之為監(jiān)督學習。

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

從數(shù)據(jù)產生決策樹的機器學習技術叫做決策樹學習， 通俗說就是決策樹。

一個決策樹包含三種類型的節(jié)點：

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

●機會節(jié)點：通常用圓圈來表示

●終結點：通常用三角形來表示

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

決策樹同時也可以依靠計算條件概率來構造。

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

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

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

優(yōu)點

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

對于決策樹，數(shù)據(jù)的準備往往是簡單或者是不必要的，而且能夠同時處理數(shù)據(jù)型和常規(guī)型屬性，在相對短的時間內能夠對大型數(shù)據(jù)源做出可行且效果良好的結果。

易于通過靜態(tài)測試來對模型進行評測，可以測定模型可信度；如果給定一個觀察的模型，那么根據(jù)所產生的決策樹很容易推出相應的邏輯表達式。

缺點

1）對連續(xù)性的字段比較難預測。

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

3）當類別太多時，錯誤可能就會增加的比較快。

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

算法

1、C4．5

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

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

2） 在樹構造過程中進行剪枝；

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

4） 能夠對不完整數(shù)據(jù)進行處理。

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

具體算法步驟如下；

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

2如果訓練集為空，在返回節(jié)點N標記為Failure

3如果訓練集中的所有記錄都屬于同一個類別，則以該類別標記節(jié)點N

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

5for each 候選屬性 attribute＿list

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

7對該屬性進行離散化

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

9標記節(jié)點N為屬性D

10for each 屬性D的一致值d

11由節(jié)點N長出一個條件為D＝d的分支

12設s是訓練集中D＝d的訓練樣本的集合

13if s為空

14加上一個樹葉，標記為訓練集中最普通的類

15else加上一個有C4．5（R － ｛D｝，C，s）返回的點

2、CART

背景：

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

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

定義：

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