决策树

维基百科,自由的百科全书
跳转至: 导航搜索

决策论中 (如风险管理),决策树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

相关条目[编辑]

参考文献[编辑]