原文地址：https://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91

機(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ù)，同樣也可以用來(lái)作預(yù)測(cè)。

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

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

決策節(jié)點(diǎn)：通常用矩形框來(lái)表式

機(jī)會(huì)節(jié)點(diǎn)：通常用圓圈來(lái)表式

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

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

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

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

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

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

類型

決策樹有幾種產(chǎn)生方法：

• 分類樹分析是當(dāng)預(yù)計(jì)結(jié)果可能為離散類型（例如三個(gè)種類的花，輸贏等）使用的概念。
• 回歸樹分析是當(dāng)局域結(jié)果可能為實(shí)數(shù)（例如房?jī)r(jià)，患者住院時(shí)間等）使用的概念。
• CART分析是結(jié)合了上述二者的一個(gè)概念。CART是Classification And Regression Trees的縮寫.
• en:CHAID（Chi-Square Automatic Interaction Detector）

建立方法

以資料母群體為根節(jié)點(diǎn)。

作單因子變異數(shù)分析等，找出變異量最大的變項(xiàng)作為分割準(zhǔn)則。（決策樹每個(gè)葉節(jié)點(diǎn)即為一連串法則的分類結(jié)果。）

若判斷結(jié)果的正確率或涵蓋率未滿足條件，則再依最大變異量條件長(zhǎng)出分岔。

在教學(xué)中的使用

決策樹，影響性圖表，應(yīng)用函數(shù)以及其他的決策分析工具和方法主要的授課對(duì)象是學(xué)校里商業(yè)、健康經(jīng)濟(jì)學(xué)和公共衛(wèi)生專業(yè)的本科生，屬于運(yùn)籌學(xué)和管理科學(xué)的范疇。

舉例闡述

下面我們用例子來(lái)說(shuō)明：

小王是一家著名高爾夫俱樂部的經(jīng)理。但是他被雇員數(shù)量問(wèn)題搞得心情十分不好。某些天好像所有人都來(lái)玩高爾夫，以至于所有員工都忙的團(tuán)團(tuán)轉(zhuǎn)還是應(yīng)付不過(guò)來(lái)，而有些天不知道什么原因卻一個(gè)人也不來(lái)，俱樂部為雇員數(shù)量浪費(fèi)了不少資金。

小王的目的是通過(guò)下周天氣預(yù)報(bào)尋找什么時(shí)候人們會(huì)打高爾夫，以適時(shí)調(diào)整雇員數(shù)量。因此首先他必須了解人們決定是否打球的原因。

在2周時(shí)間內(nèi)我們得到以下記錄：

天氣狀況有晴，云和雨；氣溫用華氏溫度表示；相對(duì)濕度用百分比；還有有無(wú)風(fēng)。當(dāng)然還有顧客是不是在這些日子光顧俱樂部。最終他得到了14行5列的數(shù)據(jù)表格。

決策樹模型就被建起來(lái)用于解決問(wèn)題。

決策樹是一個(gè)有向無(wú)環(huán)圖。根結(jié)點(diǎn)代表所有數(shù)據(jù)。分類樹算法可以通過(guò)變量outlook，找出最好地解釋非獨(dú)立變量play（打高爾夫的人）的方法。變量outlook的范疇被劃分為以下三個(gè)組：

晴天，多云天和雨天。

我們得出第一個(gè)結(jié)論：如果天氣是多云，人們總是選擇玩高爾夫，而只有少數(shù)很著迷的甚至在雨天也會(huì)玩。

接下來(lái)我們把晴天組的分為兩部分，我們發(fā)現(xiàn)顧客不喜歡濕度高于70%的天氣。最終我們還發(fā)現(xiàn)，如果雨天還有風(fēng)的話，就不會(huì)有人打了。

這就通過(guò)分類樹給出了一個(gè)解決方案。小王（老板）在晴天，潮濕的天氣或者刮風(fēng)的雨天解雇了大部分員工，因?yàn)檫@種天氣不會(huì)有人打高爾夫。而其他的天氣會(huì)有很多人打高爾夫，因此可以雇用一些臨時(shí)員工來(lái)工作。

公式

熵（Entropy）

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

決策樹的優(yōu)點(diǎn)

相對(duì)于其他數(shù)據(jù)挖掘算法，決策樹在以下幾個(gè)方面擁有優(yōu)勢(shì)：

• 決策樹易于理解和實(shí)現(xiàn).人們?cè)谕ㄟ^(guò)解釋后都有能力去理解決策樹所表達(dá)的意義。
• 對(duì)于決策樹，數(shù)據(jù)的準(zhǔn)備往往是簡(jiǎn)單或者是不必要的.其他的技術(shù)往往要求先把數(shù)據(jù)一般化，比如去掉多余的或者空白的屬性。
• 能夠同時(shí)處理數(shù)據(jù)型和常規(guī)型屬性。其他的技術(shù)往往要求數(shù)據(jù)屬性的單一。
• 是一個(gè)白盒模型如果給定一個(gè)觀察的模型，那么根據(jù)所產(chǎn)生的決策樹很容易推出相應(yīng)的邏輯表達(dá)式。
• 易于通過(guò)靜態(tài)測(cè)試來(lái)對(duì)模型進(jìn)行評(píng)測(cè)。表示有可能測(cè)量該模型的可信度。
• 在相對(duì)短的時(shí)間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果。

決策樹的缺點(diǎn)

決策樹：

• 對(duì)于那些各類別樣本數(shù)量不一致的數(shù)據(jù)，在決策樹當(dāng)中信息增益的結(jié)果偏向于那些具有更多數(shù)值的特征。

決策樹的剪枝

剪枝是決策樹停止分支的方法之一，剪枝有分預(yù)先剪枝和后剪枝兩種。預(yù)先剪枝是在樹的生長(zhǎng)過(guò)程中設(shè)定一個(gè)指標(biāo)，當(dāng)達(dá)到該指標(biāo)時(shí)就停止生長(zhǎng)，這樣做容易產(chǎn)生“視界局限”，就是一旦停止分支，使得節(jié)點(diǎn)N成為葉節(jié)點(diǎn)，就斷絕了其后繼節(jié)點(diǎn)進(jìn)行“好”的分支操作的任何可能性。不嚴(yán)格的說(shuō)這會(huì)已停止的分支會(huì)誤導(dǎo)學(xué)習(xí)算法，導(dǎo)致產(chǎn)生的樹不純度降差最大的地方過(guò)分靠近根節(jié)點(diǎn)。后剪枝中樹首先要充分生長(zhǎng)，直到葉節(jié)點(diǎn)都有最小的不純度值為止，因而可以克服“視界局限”。然后對(duì)所有相鄰的成對(duì)葉節(jié)點(diǎn)考慮是否消去它們，如果消去能引起令人滿意的不純度增長(zhǎng)，那么執(zhí)行消去，并令它們的公共父節(jié)點(diǎn)成為新的葉節(jié)點(diǎn)。這種“合并”葉節(jié)點(diǎn)的做法和節(jié)點(diǎn)分支的過(guò)程恰好相反，經(jīng)過(guò)剪枝后葉節(jié)點(diǎn)常常會(huì)分布在很寬的層次上，樹也變得非平衡。后剪枝技術(shù)的優(yōu)點(diǎn)是克服了“視界局限”效應(yīng)，而且無(wú)需保留部分樣本用于交叉驗(yàn)證，所以可以充分利用全部訓(xùn)練集的信息。但后剪枝的計(jì)算量代價(jià)比預(yù)剪枝方法大得多，特別是在大樣本集中，不過(guò)對(duì)于小樣本的情況，后剪枝方法還是優(yōu)于預(yù)剪枝方法的。

由決策樹擴(kuò)展為決策圖

在決策樹中所有從根到葉節(jié)點(diǎn)的路徑都是通過(guò)“與”（AND）運(yùn)算連接。在決策圖中可以使用“或”來(lái)連接多于一個(gè)的路徑。

決策樹的實(shí)現(xiàn)[編輯]

Bash[編輯]

決策樹的代碼實(shí)現(xiàn)可參考：決策樹算法實(shí)現(xiàn)——Bash

參考文獻(xiàn)

• • [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. （本論文把決策樹作為貝葉斯網(wǎng)絡(luò)使用Minimum Message Length?(MML的內(nèi)部結(jié)點(diǎn)).早期版本：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.）
  • [5]?Eruditionhome數(shù)據(jù)挖掘資源大詞典
  • [6]決策樹基礎(chǔ)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,非常好的一本介紹決策樹的書，是一本可以從基礎(chǔ)學(xué)起的好書，另外介紹的weka決策樹軟件也不錯(cuò)。是JAVA編的。

轉(zhuǎn)載于:https://www.cnblogs.com/davidwang456/articles/5599546.html

總結(jié)

以上是生活随笔為你收集整理的决策树--转的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。