决策树

维基百科，自由的百科全书

跳转到： 导航, 搜索

决策论中 (如风险管理)，决策树由一个决策图和可能的结果(包括资源成本和风险)组成， 用来创建到达目标的规划。决策树建立并用来辅助决策，是一种特殊的树结构。

目录

[编辑] 簡介

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

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

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

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

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


(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. 若判斷結果的正確率或涵蓋率未滿足條件，則再依最大變異量條件長出分岔。

[编辑] 举例阐述

下面我们用例子来说明：

小王是一家著名高尔夫俱乐部的经理。但是他被雇员数量问题搞得心情十分不好。某些天好像所有人都打玩高尔夫，以至于所有员工都忙的团团转还是应付不过来，而有些天不知道什么原因却一个人也不来，俱乐部为雇员数量浪费了不少资金。

小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，以适时调整雇员数量。因此首先他必须了解人们决定是否打球的原因。

在2周时间内我们得到以下记录:

天气状况有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。当然还有顾客是不是在这些日子光顾俱乐部。最终他得到了14行5列的数据表格。

File:golf_dataset.png

决策树模型就被建起来用于解决问题。

File:Decision_tree_model.png

决策树是一个有向无环图。根结点代表所有数据。分类树算法可以通过变量outlook，找出最好地解释非独立变量play（打高尔夫的人）的方法。变量outlook的范畴被划分为以下三个组：

晴天，多云天和雨天。

我们得出第一个结论: 如果天气是多云，人们总是选择玩高尔夫，而只有少数很着迷的甚至在雨天也会玩。

接下来我们把晴天组的分为两部分，我们发现顾客不喜欢湿度高于70%的天气。最终我们还发现，如果雨天还有风的话，就不会有人打了。

这就通过分类树给出了一个解决方案。 David（老板）在晴天，潮湿的天气或者刮风的雨天解雇了大部分员工，因为这种天气不会有人打高尔夫。而其他的天气会有很多人打高尔夫，因此可以雇用一些临时员工来工作。


结论是决策树帮助我们把复杂的数据表示转换成相对简单的直观的结构。

[编辑] 公式

[编辑] 熵

算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是给予信息学理论中熵的概念。 I_{E}(i) = - \sum^{m}_{j=1} f (i,j) \log^{}_2 f (i, j)

[编辑] 决策树的优点

相对于其他数据挖掘算法，决策树在以下几个方面拥有优势：

  • 决策树易于理解和实现. 人们在通过解释后都有能力去理解决策树所表达的意义。
  • 对于决策树，数据的准备往往是简单或者是不必要的 . 其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。
  • 能够同时处理数据型和常规型属性。 其他的技术往往要求数据属性的单一。
  • 是一个白盒模型如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
  • 易于通过静态测试来对模型进行评测。 表示有可能测量该模型的可信度。
  • 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

[编辑] 由决策树扩展为决策图

在决策树中所有从根到叶节点的路径都是通过“与”（AND）运算连接。在决策图中可以使用“或”来连接多于一个的路径。


[编辑] 相关条目

[编辑] 参考文献

来自“http://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91”
个人工具