決策樹

決策論中（如風險管理），決策樹（Decision tree）由一個決策圖和可能的結果（包括資源成本和風險）組成，用來創建到達目標的規劃。決策樹建立並用來輔助決策，是一種特殊的樹結構。決策樹是一個利用像樹一樣的圖形或決策模型的決策支持工具，包括隨機事件結果，資源代價和實用性。它是一個算法顯示的方法。決策樹經常在運籌學中使用，特別是在決策分析中，它幫助確定一個能最可能達到目標的策略。如果在實際中，決策不得不在沒有完備知識的情況下被在線採用，一個決策樹應該平行概率模型作為最佳的選擇模型或在線選擇模型算法。決策樹的另一個使用是作為計算條件概率的描述性手段。

簡介

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

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

一個決策樹包含三種類型的節點：

決策節點：通常用矩形框來表示
機會節點：通常用圓圈來表示
終結點：通常用三角形來表示

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

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

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

(x, y) = (x1, x2, x3…, xk, y)

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

類型

決策樹有幾種產生方法：

分類樹分析是當預計結果可能為離散類型（例如三個種類的花，輸贏等）使用的概念。
回歸樹分析是當局域結果可能為實數（例如房價，患者住院時間等）使用的概念。
CART分析是結合了上述二者的一個概念。CART是Classification And Regression Trees的縮寫.
CHAID（英語：CHAID）（Chi-Square Automatic Interaction Detector）

建立方法

以資料母群體為根節點。
作單因子變異數分析等，找出變異量最大的變項作為分割準則。（決策樹每個葉節點即為一連串法則的分類結果。）
若判斷結果的正確率或涵蓋率未滿足條件，則再依最大變異量條件長出分岔。

在教學中的使用

決策樹，影響性圖表，應用函數以及其他的決策分析工具和方法主要的授課對象是學校里商業、健康經濟學和公共衛生專業的本科生，屬於運籌學和管理科學的範疇。

舉例闡述

下面我們用例子來說明：

小王是一家著名高爾夫俱樂部的經理。但是他被雇員數量問題搞得心情十分不好。某些天好像所有人都來玩高爾夫，以至於所有員工都忙的團團轉還是應付不過來，而有些天不知道什麼原因卻一個人也不來，俱樂部為雇員數量浪費了不少資金。

小王的目的是通過下周天氣預報尋找什麼時候人們會打高爾夫，以適時調整雇員數量。因此首先他必須了解人們決定是否打球的原因。

在2周時間內我們得到以下記錄：

天氣狀況有晴，雲和雨；氣溫用華氏溫度表示；相對濕度用百分比；還有有無風。當然還有顧客是不是在這些日子光顧俱樂部。最終他得到了14行5列的數據表格。

Play golf dataset
Independent variables				Dep. var
Outlook	Temperature	Humidity	Windy	Play
sunny	85	85	FALSE	Don't play
sunny	80	90	TRUE	Don't play
overcast	83	78	FALSE	Play
rain	70	96	FALSE	Play
rain	68	80	FALSE	Play
rain	65	70	TRUE	Don't play
overcast	64	65	TRUE	Play
sunny	72	95	FALSE	Don't play
sunny	69	70	FALSE	Play
rain	75	80	FALSE	Play
sunny	75	70	TRUE	Play
overcast	72	90	TRUE	Play
overcast	81	75	FALSE	Play
rain	71	80	TRUE	Don't play

決策樹模型就被建起來用於解決問題。

決策樹是一個有向無環圖。根結點代表所有數據。分類樹算法可以通過變量outlook，找出最好地解釋非獨立變量play（打高爾夫的人）的方法。變量outlook的範疇被劃分為以下三個組：

晴天，多雲天和雨天。

我們得出第一個結論：如果天氣是多雲，人們總是選擇玩高爾夫，而只有少數很着迷的甚至在雨天也會玩。

接下來我們把晴天組的分為兩部分，我們發現顧客不喜歡濕度高於70%的天氣。最終我們還發現，如果雨天還有風的話，就不會有人打了。

這就通過分類樹給出了一個解決方案。小王（老闆）在晴天，潮濕的天氣或者颳風的雨天解僱了大部分員工，因為這種天氣不會有人打高爾夫。而其他的天氣會有很多人打高爾夫，因此可以雇用一些臨時員工來工作。

公式

C4.5和C5.0生成樹算法使用熵。這一度量是基於資訊科學理論中熵的概念。

$I_{E}(i)=-\sum _{j=1}^{m}f(i,j)\log _{2}^{}f(i,j)$

決策樹的優點

相對於其他數據挖掘算法，決策樹在以下幾個方面擁有優勢：

決策樹易於理解和實現.人們在通過解釋後都有能力去理解決策樹所表達的意義。
對於決策樹，數據的準備往往是簡單或者是不必要的.其他的技術往往要求先把數據一般化，比如去掉多餘的或者空白的屬性。
能夠同時處理數據型和常規型屬性。其他的技術往往要求數據屬性的單一。
是一個白盒模型如果給定一個觀察的模型，那麼根據所產生的決策樹很容易推出相應的邏輯表達式。
易於通過靜態測試來對模型進行評測。表示有可能測量該模型的可信度。
在相對短的時間內能夠對大型數據源做出可行且效果良好的結果。

決策樹的缺點

決策樹：

對於那些各類別樣本數量不一致的數據，在決策樹當中信息增益的結果偏向於那些具有更多數值的特徵。

決策樹的剪枝

剪枝是決策樹停止分支的方法之一，剪枝有分預先剪枝和後剪枝兩種。預先剪枝是在樹的生長過程中設定一個指標，當達到該指標時就停止生長，這樣做容易產生「視界局限」，就是一旦停止分支，使得節點N成為葉節點，就斷絕了其後繼節點進行「好」的分支操作的任何可能性。不嚴格的說這會已停止的分支會誤導學習算法，導致產生的樹不純度降差最大的地方過分靠近根節點。後剪枝中樹首先要充分生長，直到葉節點都有最小的不純度值為止，因而可以克服「視界局限」。然後對所有相鄰的成對葉節點考慮是否消去它們，如果消去能引起令人滿意的不純度增長，那麼執行消去，並令它們的公共父節點成為新的葉節點。這種「合併」葉節點的做法和節點分支的過程恰好相反，經過剪枝後葉節點常常會分布在很寬的層次上，樹也變得非平衡。後剪枝技術的優點是克服了「視界局限」效應，而且無需保留部分樣本用於交叉驗證，所以可以充分利用全部訓練集的信息。但後剪枝的計算量代價比預剪枝方法大得多，特別是在大樣本集中，不過對於小樣本的情況，後剪枝方法還是優於預剪枝方法的^{[來源請求]}。

由決策樹擴展為決策圖

在決策樹中所有從根到葉節點的路徑都是透過「與」（AND）運算連接。在決策圖中可以使用「或」來連接多於一個的路徑。

決策樹的實現

Bash

決策樹的代碼實現可參考：決策樹算法實現——Bash（頁面存檔備份，存於網際網路檔案館）

參考文獻

[1] T. Menzies, Y. Hu, Data Mining For Very Busy People. IEEE Computer, October 2003, pgs. 18-25.
[2]決策樹分析（頁面存檔備份，存於網際網路檔案館）mindtools.com
[3]J.W. Comley and D.L. Dowe（頁面存檔備份，存於網際網路檔案館）, "Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages", 第十一章 (pp265-294) in P. Grunwald, M.A. Pitt and I.J. Myung (eds)., Advances in Minimum Description Length: Theory and Applications, M.I.T. Press, April 2005, ISBN 0262072629. （本論文把決策樹作為貝葉斯網絡使用Minimum Message Length（頁面存檔備份，存於網際網路檔案館） (MML的內部結點).早期版本：Comley and Dowe (2003)（頁面存檔備份，存於網際網路檔案館）, .pdf（頁面存檔備份，存於網際網路檔案館）.）
[4]P.J. Tan and D.L. Dowe（頁面存檔備份，存於網際網路檔案館） (2004), MML Inference of Oblique Decision Trees（頁面存檔備份，存於網際網路檔案館）,人工智能講義3339, Springer-Verlag, pp1082-1088（頁面存檔備份，存於網際網路檔案館）.（此論文使用Minimum Message Length（英語：Minimum Message Length）.）
[5] Eruditionhome（頁面存檔備份，存於網際網路檔案館）數據挖掘資源大詞典
[6]決策樹基礎（頁面存檔備份，存於網際網路檔案館）vanguardsw.com
[7]General Morphological Analysis: A General Method for Non-Quantified Modelling （頁面存檔備份，存於網際網路檔案館） From the Swedish Morphological Society（頁面存檔備份，存於網際網路檔案館）
[8]decisiontrees.net Interactive Tutorial
[9][Morgan.Kaufmann.Data.Mining.Practical.Machine.Learning.Tools.and.Techniques.Second.Edition]Jun.2005,非常好的一本介紹決策樹的書，是一本可以從基礎學起的好書，另外介紹的weka決策樹軟件也不錯。是JAVA編的。

簡介

類型