決策樹

維基百科,自由的百科全書
前往: 導覽搜尋

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

簡介[編輯]

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

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

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

  1. 決策節點:通常用矩形框來表式
  2. 機會節點:通常用圓圈來表式
  3. 終結點:通常用三角形來表示

Decision-Tree-Elements.png

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

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

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


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

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

類型[編輯]

決策樹有幾種產生方法:

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

建立方法[編輯]

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

決策樹法的決策程序如下:

(1)繪製樹狀圖,根據已知條件排列出各個方案和每一方案的各種自然狀態。

(2)將各狀態機率及損益值標於機率枝上。

(3)計算各個方案期望值並將其標於該方案對應的狀態結點上。

(4)進行剪枝,比較各個方案的期望值,並標於方案枝上,將期望值小的(即劣等方案剪掉)所剩的最後方案為最佳方案。


在教學中的使用[編輯]

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

舉例闡述[編輯]

下面我們用例子來說明:

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

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

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

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

Golf dataset.png

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

Decision tree model.png

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

晴天,多雲天和雨天。

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

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

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

案例利用決策樹評價生產方案 決策樹是確定生產能力方案的一條簡捷的途徑。決策樹不僅可以幫助人們理解問題,還可以幫助人們解決問題。決策樹是一種通過圖示羅列解題的有關步驟以及各步驟發生的條件與結果的一種方法。近年來出現的許多專門軟體包可以用來建立和分析決策樹,利用這些專門軟體包,解決問題就變得更為簡便了。

決策樹由決策結點、機會結點與結點間的分枝連線組成。通常,人們用方框表示決策結點,用圓圈表示機會結點,從決策結點引出的分枝連線表示決策者可作出的選擇,從機會結點引出的分枝連線表示機會結點所示事件發生的機率。

在利用決策樹解題時,應從決策樹末端起,從後向前,步步推進到決策樹的始端。在向前推進的過程中,應在每一階段計算事件發生的期望值。需特別注意:如果決策樹所處理問題的計劃期較長,計算時應考慮資金的時間價值。

計算完畢後,開始對決策樹進行剪枝,在每個決策結點刪去除了最高期望值以外的其他所有分枝,最後步步推進到第一個決策結點,這時就找到了問題的最佳方案。

下面以南方醫院供應公司為例,看一看如何利用決策樹作出合適的生產能力計劃。

南方醫院供應公司是一家製造醫護人員的工裝大褂的公司。該公司正在考慮擴大生產能力。它可以有以下幾個選擇:1、什麼也不做;2、建一個小廠;3、建一個中型廠;4、建一個大廠。新增加的設備將生產一種新型的大褂,目前該產品的潛力或市場還是未知數。如果建一個大廠且市場較好就可實現$100,000的利潤。如果市場不好則會導致$90,000的損失。但是,如果市場較好,建中型廠將會獲得$ 60,000,小型廠將會獲得$40,000,市場不好則建中型廠將會損失$10,000,小型廠將會損失$5,000。當然,還有一個選擇就是什麼也不幹。最近的市場研究表明市場好的機率是0.4,也就是說市場不好的機率是0.6。參下圖: File:Tree 45.gif

在這些數據的基礎上,能產生最大的預期貨幣價值(EMV)的選擇就可找到。

EMV(建大廠)=(0.4)*($100,000)+(0.6)*(-$90,000)=-$14,000 EMV(中型廠)=(0.4) *($ 60,000))+(0.6)* (-$10,000)=+$18,000 EMV(建小廠)=(0.4)* ($40,000)+(0.6)*(-$5,000)=+$13,000 EMV(不建廠)=$0 根據EMV標準,南方公司應該建一個中型廠。

公式[編輯]

熵(Entropy)[編輯]

Entropy = 系統的凌亂程度,使用演算法ID3, C4.5和C5.0生成樹演算法使用熵。這一度量是基於信息學理論中熵的概念。  I_{E}(i) = - \sum^{m}_{j=1}  f (i,j) \log^{}_2 f (i, j)

決策樹的優點[編輯]

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

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

決策樹很擅長處理非數值型數據,這與神經網路只能處理數值型數據比起來,就免去了很多數據預處理工作。甚至有些決策樹演算法專為處理非數值型數據而設計,因此當採用此種方法建立決策樹同時又要處理數值型數據時,反而要做把數值型數據映射到非數值型數據的預處理。

決策樹的缺點[編輯]

決策樹:

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

決策樹的這種明確性可能帶來誤導。比如,決策樹每個節點對應分割的定義都是非常明確毫不含糊的,但在實際生活中這種明確可能帶來麻煩(憑什麼說年收入¥40,001的人具有較小的信用風險而¥40,000的人就沒有)。    建立一顆決策樹可能只要對資料庫進行幾遍掃描之後就能完成,這也意味著需要的計算資源較少,而且可以很容易的處理包含很多預測變數的情況,因此決策樹模型可以建立得很快,並適合應用到大量的數據上。

對最終要拿給人看的決策樹來說,在建立過程中讓其生長的太「枝繁葉茂」是沒有必要的,這樣既降低了樹的可理解性和可用性,同時也使決策樹本身對歷史數據的依賴性增大,也就是說這是這棵決策樹對此歷史數據可能非常準確,一旦應用到新的數據時準確性卻急劇下降,我們稱這種情況為訓練過度。為了使得到的決策樹所蘊含的規則具有普遍意義,必須防止訓練過度,同時也減少了訓練的時間。因此我們需要有一種方法能讓我們在適當的時候停止樹的生長。常用的方法是設定決策樹的最大高度(層數)來限制樹的生長。還有一種方法是設定每個節點必須包含的最少記錄數,當節點中記錄的個數小於這個數值時就停止分割。

與設置停止增長條件相對應的是在樹建立好之後對其進行修剪。先允許樹盡量生長,然後再把樹修剪到較小的尺寸,當然在修剪的同時要求盡量保持決策樹的準確度盡量不要下降太多。

決策樹的剪枝[編輯]

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

由決策樹擴展為決策圖[編輯]

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

決策樹的實現[編輯]

Bash[編輯]

決策樹的代碼實現可參考:決策樹演算法實現——Bash

相關條目[編輯]

參考文獻[編輯]