# 信息生产：决策树

Again and again, the impossible problem is solved when we see that the problem is only a tough decision waiting to be made.一次又一次，当问题只是在于等待做出一个艰难的决定时，这个不可能解决的问题就已经被解决了。 ——Robert H. Schuller

Again and again, the impossible problem is solved when we see that the problem is only a chain of gradually simplified decisions waiting to be made. 一次又一次，当将问题简化为一个一个的小问题去解决时，这个不可能解决的问题就已经被解决了。 ——Xudong Cao

 --趣木木（讨论）注：为利于审校和编辑后期工作的进行，遇到文本格式与页面格式显示差异较大的 会出现两次。含有参考文献的段落利于后期编辑，为第一个段落；不含格式的段落利于后期审校，为第二个段落。若段落不含参考文献 则仅以一段显示。下为实例：


A decision tree consists of three types of nodes:[1]

## 引言

A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm that only contains conditional control statements.

A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm that only contains conditional control statements. 它是只包含条件控制语句（if,else等）的一种算法。决策树利用类似于树的决策模型及其可能的结果（包括机会事件的结果、资源成本和效用）作为工具来支持决策。由于其决策分支画成图形很像一棵树的枝干，故称决策树。

Decision trees are commonly used in operations research, specifically in decision analysis, to help identify a strategy most likely to reach a goal, but are also a popular tool in machine learning. Decision trees are commonly used in operations research, specifically in decision analysis, to help identify a strategy most likely to reach a goal, but are also a popular tool in machine learning. 决策树通常用于运筹学研究，特别是在决策分析中，去帮助识别最有可能实现目标的策略，但同样也在机器学习中比较常用。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系，是监督学习中的一种。

 --趣木木（讨论）加以补充 "他代表的是对象属性与对象值之间的一种映射关系，是监督学习中的一种。"


## 概览

A decision tree is a flowchart-like structure in which each internal node represents a "test" on an attribute (e.g. whether a coin flip comes up heads or tails), each branch represents the outcome of the test, and each leaf node represents a class label (decision taken after computing all attributes). The paths from root to leaf represent classification rules. 决策树是一种流程图式结构,其中每个内部节点表示对于一个属性上的“测试”(例如一个抛硬币是否出现正面或反面),每个分支代表测试的结果,每个叶节点代表一种类别(在计算所有特征/属性后进行决策)。从根到叶的路径表示分类规则。

In decision analysis, a decision tree and the closely related influence diagram are used as a visual and analytical decision support tool, where the expected values (or expected utility) of competing alternatives are calculated. 在决策分析 Decision Analysis中，决策树与影响图紧密相关，它们是可视化且具有分析性的决策支持工具，可用来计算在竞争方案中的期望值 Expected Value期望效用 Expected Utility

Much of the information in a decision tree can be represented more compactly as an influence diagram, focusing attention on the issues and relationships between events. 决策树中的许多信息可以更简洁地表示为影响图，更加关注问题和事件之间的关系。

  --趣木木（讨论）加以补充了影响图的一些概念


A decision tree consists of three types of nodes:[2]

A decision tree consists of three types of nodes:[1]

1. Decision nodes – typically represented by squares
2. Chance nodes – typically represented by circles
3. End nodes – typically represented by triangles
• □—-决策点-用正方形来表示。是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案。
• ○——状态节点-用圆圈表示。代表备选方案的经济效果（期望值），通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。
• △——结果节点-用三角形表示。将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。
 --趣木木（讨论）分别对决策点 状态节点 结果节点进行了补充


Decision trees are commonly used in operations research and operations management. If, in practice, decisions have to be taken online with no recall under incomplete knowledge, a decision tree should be paralleled by a probability model as a best choice model or online selection model algorithm. Another use of decision trees is as a descriptive means for calculating conditional probabilities. Decision trees are commonly used in operations research and operations management. If, in practice, decisions have to be taken online with no recall under incomplete knowledge, a decision tree should be paralleled by a probability model as a best choice model or online selection model algorithm. Another use of decision trees is as a descriptive means for calculating conditional probabilities. 决策树常用于运筹学和运营管理领域。在实践中，如果决策是在信息有缺失且不需回忆的情况下进行时，那么决策树应该与概率模型一样，是最优选择模型/在线选择模型算法。决策树也是一种计算条件概率的描述性方法。

 --趣木木（讨论）online selection model algorithm 只查到有在线学习算法  会再查询一下


Decision trees, influence diagrams, utility functions, and other decision analysis tools and methods are taught to undergraduate students in schools of business, health economics, and public health, and are examples of operations research or management science methods. 决策树、影响图、效用函数以及其他决策分析工具和方法常作为商学院、卫生经济学和公共卫生学院的本科生教学内容。它们也是运筹学或管理科学方法的一些示例。

## 组成部分

Drawn from left to right, a decision tree has only burst nodes (splitting paths) but no sink nodes (converging paths). Therefore, used manually, they can grow very big and are then often hard to draw fully by hand. Traditionally, decision trees have been created manually – as the aside example shows – although increasingly, specialized software is employed. 从左到右绘制的决策树只有分支节点(具有分裂路径)，没有汇聚节点(具有聚合路径)。因此，如果利用手工绘制，它们会变得非常大，且通常很难完全完成。传统上，决策树是手工创建的。正如图3所示——尽管越来越多地使用专门的软件。

## 训练

### 决策规则

The decision tree can be linearized into decision rules,[3] where the outcome is the contents of the leaf node, and the conditions along the path form a conjunction in the if clause. In general, the rules have the form: The decision tree can be linearized into decision rules,[2] where the outcome is the contents of the leaf node, and the conditions along the path form a conjunction in the if clause. In general, the rules have the form: 决策树能够将决策规则线性化，其中叶节点的内容是结果，在if语句中的连接所产生的路径是条件。一般来说，规则的形式如下:

if condition1 and condition2 and condition3 then outcome.

Decision rules can be generated by constructing association rules with the target variable on the right. They can also denote temporal or causal relations.[4] Decision rules can be generated by constructing association rules with the target variable on the right. They can also denote temporal or causal relations.[3] 可以通过利用右侧的目标变量来构造关联、生成决策规则。它们也可以表示时间或因果关系。

### 使用流程图符号的决策树Decision tree using flowchart symbols

Commonly a decision tree is drawn using flowchart symbols as it is easier for many to read and understand. 通常，决策树是使用流程图符号来绘制的，因为这样更容易阅读和理解。

## 测试(预测)

1. 进入根节点, 分支函数 $\displaystyle{ f_1(x) = x_3 - 1 = 0 - 1 = -1 }$ 小于0， 进入左分支
2. 分支函数 $\displaystyle{ f_2(x) = x_1 - x_2 + 1 = 3 - 2 + 1 = 2 }$ 大于0, 进入右分支
3. 分支函数 $\displaystyle{ f_4(x) = x_2 + 1 = 2 + 1 = 3 }$ 大于0, 进入右分支, 已经到达叶节点
4. 假设是三分类问题, 该叶节点上所有类别的后验概率是 (0.1, 0.7, 0.2), 那么该决策树预测输入样本属于第二类.

# 分支节点(树的结构)

## 分支函数形式

• 一维线性函数: $\displaystyle{ f(x) = x_i + b }$
• 多维线性函数: $\displaystyle{ f(x) = \lt a,x\gt + b }$, 其中$\displaystyle{ \lt a,x\gt }$表示向量内积。

## 分支函数选择

### 建立用于分支函数选择的函数集合

• 设定决策树为$\displaystyle{ B }$叉树，预测变量$\displaystyle{ X }$（即分支函数的自变量）属于有$\displaystyle{ L }$个水平的序数型(Ordinal)变量，或者$\displaystyle{ X }$为被离散化成$\displaystyle{ L }$段的区间型(Interval)变量。

$\displaystyle{ f(x)=x-a \begin{cases} \lt =0 &\text{then go to the left branch}\\ \gt 0 &\text{then go to the right branch} \end{cases} }$

$\displaystyle{ f(X) }$为决定一个含X观测的样本进入左分支还是右分支的判断条件。此函数即为一个合理的备选分支函数。

$\displaystyle{ \sum_{b=2}^{B} C_{L-1}^{b-1} }$

• 设定决策树为$\displaystyle{ B }$叉树，预测变量$\displaystyle{ X }$属于有$\displaystyle{ L }$个水平的列名型(Nominal)变量，则水平之间是无序的。

X是列名型变量，取值为$\displaystyle{ \{1,2,...,9\} }$，水平之间不存在排序关系。若函数形式为

$\displaystyle{ f(x) = x%3 }$

 L\B 2 3 4 ... 总 2 1 ... 1 3 3 1 ... 4 4 7 6 1 ... 14 5 15 25 10 ... 51 6 31 90 65 ... 202 7 63 301 350 ... 876 8 127 966 1701 ... 4139

$\displaystyle{ B_L=\sum_{b=1}^L{S(L,b)} }$

• 用于搜索的变量在全树中只使用一次
• 节点内部采样，减少观测
• $\displaystyle{ L }$个水平进行层次聚类。CHAID使用了这种技术：

1. 处理序数型或区间型变量时，在层次聚类时只考虑相邻分支的聚类，选择条件是“两个分支在目标变量上的分布最接近”（卡方意义上）；

$\displaystyle{ L }$个水平作为从$\displaystyle{ L }$个不同分支开始，每次聚类减少一个分支；

1. 处理列名型变量时，在层次聚类时考虑任意两个分支的聚类；

$\displaystyle{ L }$个水平作为从$\displaystyle{ L }$个不同分支开始，每次聚类减少一个分支；

### 选择最优分支函数

• 假设当前分支节点所有样本为 $\displaystyle{ \{ x_1,x_2,...,x_n\} }$, 对应的类别标签为$\displaystyle{ \{ y_1,y_2,...,y_n\} }$
• 分支函数$\displaystyle{ f(x: X \rightarrow B) }$将样本划分到两个或多个子节点. 其中$\displaystyle{ \mathcal{X}_{b} = \{x_i | f(x_i)=b\} }$ 表示第$\displaystyle{ b }$个子节点样本的集合，$\displaystyle{ b \in \{1,2,...,B\} }$
• $\displaystyle{ \mathcal{Y}_{b}, b \in \{1,2,....,B\} }$ 为对应的标签集合.

$\displaystyle{ f^* = \underset{f}\text{argmin} ( \sum_{b=1}^{B} L(\mathcal{X}_{b}, \mathcal{Y}_{b}) ) }$

## 损失函数形式设定

### 分类树损失函数

#### 基尼不纯度 Gini impurity 准则

$\displaystyle{ l_{G}(p) \propto n \sum_{i=1}^{m} p_i (1-p_i) }$

$\displaystyle{ \Delta Gini = i(0)-(\frac{n_1}{n_0}i(1)+\frac{n_2}{n_0}i(2)+\frac{n_3}{n_0}i(3)+... ) }$$\displaystyle{ \{n_0,n_1,n_2,n_3,...\} }$分别为当前节点与其分支节点的观测数；

#### 信息熵(Information entropy)准则

$\displaystyle{ l_{E}(p) \propto - n \sum^{m}_{i=1} p_i \log^{}_2 p_i }$

$\displaystyle{ \Delta H = H(0)-(\frac{n_1}{n_0}H(1)+\frac{n_2}{n_0}H(2)+\frac{n_3}{n_0}H(3)+... ) }$

#### 对数价值 Logworth 准则

$\displaystyle{ -log_{10}(mP) = \mbox{Logworth} -log_{10}{m} }$

  ---趣木木（讨论）Logworth释义未查询到合适结果


$\displaystyle{ m=\left\{\begin{array}{ll} C_{L-1}^{B-1} \mbox{ , when X is Ordinal/Interval} & \\ S(L,B) \mbox{ , when X is Nominal} & \end{array}\right. }$

 Y\B X Total X<5 X>=5 E(X<5) E(X>=5) (O-E)^2/E (X<5) (O-E)^2/E (X>=5) 1 364 293 71 239 125 12 23 2 364 363 1 239 125 64 123 3 336 42 294 220 116 139 273

$\displaystyle{ \Delta Gini=0.197, \Delta H=0.504, \mbox{Logworth}=140, m=96, \mbox{Adjusted Logworth}=138 }$

### 回归树损失函数

#### 方差的最大似然估计 MLE of Variance 准则

$\displaystyle{ {Var}_b = \frac{1}{n_b}\sum_{j=1}^{n_b}(y_{jb}-\bar{y}_b)^2 }$

#### 绝对偏差 Least Absolute Deviation 准则

$\displaystyle{ {LAD}_b = \frac{1}{n_b}\sum_{j=1}^{n_b}|y_{jb}-\bar{y}_b| }$

#### 分支规则的F检验 Branching's F-Test 准则

F-统计量检验：

$\displaystyle{ F=(\frac{SS_{between}}{SS_{within}})(\frac{n-B}{B-1}) \sim F_{B-1,n-B} }$

## 分支时的缺失值处理

• 处理序数型/区间型变量：无缺失值情况下如果发生了$\displaystyle{ b }$个分支，只需要考虑缺失值作为独立分支或者附着于$\displaystyle{ b }$个分支中的某一个的一共$\displaystyle{ b+1 }$种情况；
• 处理列名型变量：简单地把缺失值作为独立水平进行搜索。

# 叶节点(树的输出)

• 对于分类树, 决策树的叶节点上的输出就是所有类别的后验概率 $\displaystyle{ P(c|x) }$. 可以用该叶节点各类别样本的频率来近似后验概率 $\displaystyle{ P(c|x) }$. 后验概率最大的类别就是决策树对于新进单个观测点的预测结果，也就是 $\displaystyle{ c^* = \underset{c}{\text{argmax}} P(c|x) }$
• 对于回归树，决策树的叶节点上的输出是叶子结点上观测点目标变量$\displaystyle{ Y }$的中位数。

# 决策树停止生长准则

## 前向截止条件

• 最大深度： 树的节点的深度指的是，从根节点出发到当前节点的路径长度。如果某个节点的深度已经达到预先设定的深度，那么就停止分支, 该节点被设定为叶节点。
• 最少样本数量：一般来说，叶节点的样本量越多，推广力越强。反之, 则容易过拟合。限制叶节点的最低样本量有助于提升决策树的推广能力。 如果当前节点样本量已经低于预先设定的阈值，那么停止分支。
• 纯度准则：分支过程若导致节点上不断地降低基尼不纯度/熵/节点内方差等，说明纯度一直在改进。达到特定的纯度即可停止分支。

## 后向剪枝条件

• 最小化误分类/最大化准确度（分类树）：

$\displaystyle{ \mbox{Accuracy}=\frac{n_{TP}+n_{TN}}{n} }$

• 最大化收益（分类树）：

• 纯度准则（分类树，回归树）：

• ASE 平均平方误差（分类树，回归树）：

$\displaystyle{ ASE = 1 - \sum_{i=1}^N p_{i-train}p_{i-valid} }$

• 稳健性模型选择

$\displaystyle{ R_{\alpha}(T)=R(T)+\alpha |T| }$

• 提升度方法（分类树）：

# 决策树与罗斯·昆兰

 --趣木木（讨论）补充   E. B.Hunt未找到释义


1986年机器学习 Machine Learning杂志创刊，昆兰应邀在创刊号上重新发表了ID3算法,掀起了决策树研究的热潮。短短几年间众多决策树算法问世, ID4、ID5等名字迅速被其他研究者提出的算法占用，昆兰只好将自己的ID3后继算法命名为C4.0,在此基础上进一步提出了著名的C4.5。有趣的是,昆兰自称C4.5仅是对C4.0做了些小改进，因此将它命名为“第4.5代分类器”，而将后续的商业化版本称为C5.0。

# 成熟的决策树算法

## ID3

1970年代，一个叫昆兰的人找到了用信息论中的熵来度量决策树的决策选择过程，方法一出，它的简洁和高效就引起了轰动，昆兰把这个算法叫做ID3。它基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍 历可能的决策空间。

H(X)度量了X的不确定性，条件熵H(X|Y)度量了我们在知道Y以后X剩下的不确定性，那么H(X)-H(X|Y)度量了X在知道Y以后不确定性减少程度，这个度量在信息论中称为互信息。在决策树ID3算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。

ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。

### 算法过程

• 初始化信息增益的阈值ϵ
• 判断样本是否为同一类输出Di，如果是则返回单节点树T。标记类别为Di
• 判断特征是否为空，如果是则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
• 计算A中的各个特征（一共n个）输出D的信息增益，选择信息增益最大的特征Ag
• 如果Ag的信息增益小于阈值ϵ，则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
• 否则，按特征Ag的不同取值Agi将对应的样本输出D分成不同的类别Di。每个类别产生一个子节点。对应特征值为Agi。返回增加了节点的数T。
• 对于所有的子节点，令D=Di,A=A−{Ag}递归调用，得到子树Ti并返回。

### 缺点

ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。

• ID3没有考虑连续特征
• ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？
• ID3算法对于缺失值的情况没有做考虑
• 没有考虑过拟合的问题

## C4.5

ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法。ID3算法有四个主要的不足，一是不能处理连续特征，第二个就是用信息增益作为标准容易偏向于取值较多的特征，最后两个是缺失值处理的问和过拟合问题。昆兰在C4.5算法中改进了上述四个问题。

## C5.0

• 分支准则：ID3使用熵减收益作为准则，从C4.5开始使用熵减值与分支导致的熵增的比例作为准则（单节点纯度为0，分为多节点即带来熵增）
• 分支数：2（ID3命名由此得来：Iterative Dichotomizer v3，决定了这是一个迭代二分支算法）
• 叶节点大小：75
• 分支最大深度：15
• C5.0嵌入了大规模学习常用的推进法

# CART(Classification and Regression Tree)基尼分类树算法

$\displaystyle{ Gini(p) = \sum\limits_{k=1}{K}p_k(1-p_k) = 1- \sum\limits_{k=1}{K}p_k^2 }$

### CART分类树算法

（1）对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。

（2）计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。

（3）计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数，对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和上篇的C4.5算法里描述的相同。

（4）在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2.

（5）对左右的子节点递归的调用1-4步，生成决策树。

### 缺点

（1）无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样绝息到的决策树更加准确。这个决策树叫做多变量决策树 multi-variate decision tree 。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，这里不多介绍。

（2）如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

### 一些参数

• 分支准则: Gini不纯度改进
• 分支数：2
• 叶节点大小：60个观测
• 分支最大深度：10层
• 缺失值推断：2次
• 后向剪枝：ASE

# CHAID （CHi-squared Automatic Interaction Detection)

• 分支准则：Pearson卡方检验，显著性 1e-5，使用Kass P调整
• 分支数：<=6
• 节点大小：150
• 模型选择：因为存在前剪枝，使用最大树

# 分析实例

Analysis can take into account the decision maker's (e.g., the company's) preference or utility function, for example: 决策分析可以考虑决策者(又譬如公司)的偏好效用函数，例如:

The basic interpretation in this situation is that the company prefers B's risk and payoffs under realistic risk preference coefficients (greater than \$400K—in that range of risk aversion, the company would need to model a third strategy, "Neither A nor B"). 对于图中的情况，基本的解释是：对于现实风险偏好系数和产品A/B进行分析，公司偏好产品B的风险和偿付。当超过400K这一风险规避范围内时，公司将需要模拟第三种战略，即“既非a也非B”。

Another example, commonly used in operations research courses, is the distribution of lifeguards on beaches (a.k.a. the "Life's a Beach" example).[5] The example describes two beaches with lifeguards to be distributed on each beach. There is maximum budget B that can be distributed among the two beaches (in total), and using a marginal returns table, analysts can decide how many lifeguards to allocate to each beach. Another example, commonly used in operations research courses, is the distribution of lifeguards on beaches (a.k.a. the "Life's a Beach" example).[4] The example describes two beaches with lifeguards to be distributed on each beach. There is maximum budget B that can be distributed among the two beaches (in total), and using a marginal returns table, analysts can decide how many lifeguards to allocate to each beach. 在运筹学课程中经常使用的另一个例子是海滩上的救生员分布(又称“生活是海滩”的例子)。这个例子描述了两个海滩，每个海滩上都有救生员。在这两个海滩上(总共)可以分配的最多的救生员是B个，利用边际收益表，分析师可以决定每个海滩分配多少个救生员。

Lifeguards on each beach Drownings prevented in total, beach #1 Drownings prevented in total, beach #2
1 1 3
2 4 0

In this example, a decision tree can be drawn to illustrate the principles of diminishing returns on beach #2. 在该例子下，可以绘制一个决策树来说明海滩#1、海滩#2的收益递减原则。

 --趣木木（讨论）该句有改动 觉得表达的意思是 绘制海滩一号、二号的收益表


Beach Decision Tree

The decision tree illustrates that when sequentially distributing lifeguards, placing a first lifeguard on beach #1 would be optimal if there is only the budget for 1 lifeguard. But if there is a budget for two guards, then placing both on beach #2 would prevent more overall drownings. 该决策树表明，当按顺序分配救生员时，如果只能配有一名救生员，那么在海滩#1上部署该名救生员将是最优选择。但是如果能配有两名救生员，那么将他们都部署在海滩#2可以防止更多的溺水事件。

# 关联规则归纳

Main article: Decision tree learning Decision trees can also be seen as generative models of induction rules from empirical data. An optimal decision tree is then defined as a tree that accounts for most of the data, while minimizing the number of levels (or "questions").[6] Several algorithms to generate such optimal trees have been devised, such as ID3/4/5,[7] CLS, ASSISTANT, and CART.

Main article: Decision tree learning Decision trees can also be seen as generative models of induction rules from empirical data. An optimal decision tree is then defined as a tree that accounts for most of the data, while minimizing the number of levels (or "questions").[5] Several algorithms to generate such optimal trees have been devised, such as ID3/4/5,[6] CLS, ASSISTANT, and CART. 主要文章:决策树学习 决策树也可以看作是经验数据归纳规则的生成模型。将最优决策树定义为一个树，它负责大部分数据，同时最小化“问题”的数量。已经有了几种生成该种最优树的算法，如ID3/4/5、[6]CLS、ASSISTANT和CART。

 --趣木木（讨论） while minimizing the number of levels (or "questions") 中的level想理解为决策树的层数  但是感觉比较赘余  故未翻译levels


# 优缺点

## 决策树的优点

Among decision support tools, decision trees (and influence diagrams) have several advantages. Decision trees: 在决策支持工具中，决策树(和影响图)有几个优点。 决策树:

• Are simple to understand and interpret. People are able to understand decision tree models after a brief explanation.
• Have value even with little hard data. Important insights can be generated based on experts describing a situation (its alternatives, probabilities, and costs) and their preferences for outcomes.
• Help determine worst, best and expected values for different scenarios.
• Use a white box model. If a given result is provided by a model.
• Can be combined with other decision techniques.
• 简单直观，易于理解和解释。仅通过简单的解释，人们就能够理解决策树模型。
• 即使很少的数据也有价值。对于数据的见解可以基于专家描述的情况(其选择、可能性和成本)和对结果的偏好。
• 帮助确定最坏的、最好的和不同场景下的期望值。
• 相比于神经网络之类的黑盒分类模型，如果一个给定的结果是由一个模型提供的,决策树使用白盒模型,其在逻辑上可以得到很好的解释。
• 可以与其他决策技术相结合进行决策分析。
 --趣木木（讨论）下补充一些优缺点，上面对白盒模型 相对的黑盒分类模型也进行了一些解释

• 基本不需要预处理，不需要提前归一化，处理缺失值。
• 既可以处理离散值也可以处理连续值。（很多算法只是专注于离散值或者连续值。）
• 可以处理多维度输出的分类问题。
• 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
• 对于异常点的容错能力好，健壮性高。

## 决策树的缺点

• They are unstable, meaning that a small change in the data can lead to a large change in the structure of the optimal decision tree.
• They are often relatively inaccurate. Many other predictors perform better with similar data. This can be remedied by replacing a single decision tree with a random forest of decision trees, but a random forest is not as easy to interpret as a single decision tree.
• For data including categorical variables with different number of levels, information gain in decision trees is biased in favor of those attributes with more levels.[8]
• Calculations can get very complex, particularly if many values are uncertain and/or if many outcomes are linked.
• They are unstable, meaning that a small change in the data can lead to a large change in the structure of the optimal decision tree.
• They are often relatively inaccurate. Many other predictors perform better with similar data. This can be remedied by replacing a single decision tree with a random forest of decision trees, but a random forest is not as easy to interpret as a single decision tree.
• For data including categorical variables with different number of levels, information gain in decision trees is biased in favor of those attributes with more levels.[7]
• Calculations can get very complex, particularly if many values are uncertain and/or if many outcomes are linked.
• 其不稳定，这意味着决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
• 其通常是相对不准确的。许多其他预测器在处理类似数据时表现得更好。这可以通过用决策树的随机森林替换单个决策树来补救，但是随机森林不像单个决策树那样容易解释。
• 对于包含不同层次数量的分类变量的数据，决策树中的信息增益更倾向于层次数量更多的属性[7]
• 计算会变得非常复杂。特别是在许多结果是相互关联的情况下，许多值是不确定的和/或关系的时候计算会十分复杂。可以换神经网络分类方法来解决。
 --趣木木（讨论）补充缺点

• 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
• 寻找最优的决策树是一个十分难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
• 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

# 决策树的大规模训练

Bagging的原理图为下图。

## 推进法(Boosting)

Boosting算法要求基学习器能对特定的数据分布进行学习，这可通过“重赋权法” re-weighting 实现,即在训练过程的每一轮中, 根据样本分布为每个训练样本重新赋予-一个权重。对无法接受带权样本的基学习算法，则可通过“重采样法” re-sampling 来处理,即在每一轮学习中,根据样本分布对训练集重新进行采样,再用重采样而得的样本集对基学习器进行训练。一般而言，这两种做法没有显著的优劣差别。需注意的是，Boosting 算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件，一旦条件不满足，则当前基学习器即被抛弃,且学习过程停止。在此种情形下，初始设置的学习轮数T也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。若采用“重采样法”，则可获得“重启动”机会以避免训练过程过早停止，即在抛弃不满足条件的当前基学习器之后,可根据当前分布重新对训练样本进行采样,再基于新的采样结果重新训练出基学习器,从而使得学习过程可以持续到预设的T轮完成。从偏差-方差分解的角度看，Boosting 主要关注降低偏差,因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，进而使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基本调整权重后的训练集来训练弱学习器2，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。

1）如何计算学习误差率e?

2) 如何得到弱学习器权重系数α?

3）如何更新样本权重D?

4) 使用何种结合策略？

$\displaystyle{ w_{k+1,i} }$的式子中看出，如果第i个样本分类错误，则$\displaystyle{ y_iG_k(x_i) \lt 0 }$,导致样本的权重在第k+1个弱分类器中增大，如果分类正确，则权重在第k+1个弱分类器中减少。

Adaboost分类采用的是加权平均法，最终的强分类器为$\displaystyle{ f(x) = sign(\sum\limits_{k=1}^{K}\alpha_kG_k(x)) }$

• 变量选择
• 变量离散化
• 离散化程度降低
• 交互作用检测
• 分层回归
• 回归缺失值补齐

# 决策树剪枝的部分介绍

## 编者推荐

### 文章推荐

1. Kamiński, B.; Jakubczyk, M.; Szufel, P. (2017). "A framework for sensitivity analysis of decision trees". Central European Journal of Operations Research. 26 (1): 135–159. doi:10.1007/s10100-017-0479-6. PMC 5767274. PMID 29375266.
2. Kamiński, B.; Jakubczyk, M.; Szufel, P. (2017). "A framework for sensitivity analysis of decision trees". Central European Journal of Operations Research. 26 (1): 135–159. doi:10.1007/s10100-017-0479-6. PMC 5767274. PMID 29375266.
3. Quinlan, J. R. (1987). "Simplifying decision trees". International Journal of Man-Machine Studies. 27 (3): 221–234. CiteSeerX 10.1.1.18.4267. doi:10.1016/S0020-7373(87)80053-6.
4. K. Karimi and H.J. Hamilton (2011), "Generation and Interpretation of Temporal Decision Rules", International Journal of Computer Information Systems and Industrial Management Applications, Volume 3
5. Wagner, Harvey M. (1975-09-01) (in English). Principles of Operations Research: With Applications to Managerial Decisions (2nd ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 9780137095926.
6. R. Quinlan, "Learning efficient classification procedures", Machine Learning: an artificial intelligence approach, Michalski, Carbonell & Mitchell (eds.), Morgan Kaufmann, 1983, p. 463–482. doi:10.1007/978-3-662-12405-5_15
7. Utgoff, P. E. (1989). Incremental induction of decision trees. Machine learning, 4(2), 161–186. doi:10.1023/A:1022699900025
8. Deng,H.; Runger, G.; Tuv, E. (2011). Bias of importance measures for multi-valued attributes and solutions. Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN).