143
个编辑
更改
跳到导航
跳到搜索
创建页面，内容为“{{#seo: |keywords=决策树 |description=决策树 }} {{cquote|Again and again, the impossible problem is solved when we see that the problem is only '''a tough de…”
{{#seo:
|keywords=决策树
|description=决策树
}}
{{cquote|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}}
{{cquote|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}}
[[File:DecisionTree2.png|thumb]]
=引言=
如果突然问你"有一个陌生人叫X,Ta今天需要带伞吗?", 你一定会觉得这个问题就像告诉你"两千米外有一个超市,问超市里面有多少卷卫生纸"一样突兀. 可能几秒钟之后你会说"这要依情况而定, 如果今天烈日炎炎并且X是一个皮肤白皙的中国姑娘,或者外面下着大雨并且X是一个不得不去步行上班的屌丝码农, 那么Ta今天需要带伞, 否则不要."
当谈及这个看似无聊的问题的时候我们在谈什么？恩，在谈方法. 我们经常会遇到简单但又困难的抉择. 说简单,是因为候选方案简单而且清晰. 例如,要不要出国留学,要不要辞职创业,要不要投资黄金等等. 但是这些看似简单的选项背后却是困难的抉择. 面对这些困难的抉择, 一开始, 很可能不知所措. 值得庆幸的是, 很多时候, 这些看似不可能解决的问题, 最终可以被化解成一连串越来越简单的问题, 然后解决掉. 这个方法可以粗俗总结为: "如果这样这样这样, 那么选择A; 如果那样那样那样, 那么选择B", 当然这种方法有一个更加简洁形象的名字--决策树(Decision Tree), 也就是这篇文章的主题.
=定义=
决策树是一种分而治之(Divide and Conquer)的决策过程。一个困难的预测问题, 通过树的分支节点, 被划分成两个或多个较为简单的子集，从结构上划分为不同的子问题。将依规则分割数据集的过程不断递归下去(Recursive Partitioning)。随着树的深度不断增加，分支节点的子集越来越小，所需要提的问题数也逐渐简化。当分支节点的深度或者问题的简单程度满足一定的停止规则(Stopping Rule)时, 该分支节点会停止劈分，此为自上而下的停止阈值(Cutoff Threshold)法；有些决策树也使用自下而上的剪枝(Pruning)法。
==历史==
决策树含义直观,容易解释. 对于实际应用,决策树还有其他算法难以比肩的速度优势. 这使得决策树,一方面能够有效地进行大规模数据的处理和学习;另一方面在测试/预测阶段满足实时或者更高的速度要求. 历史上,因为预测结果方差大而且容易过拟合,决策树曾经一度被学术界冷落. 但是在近十年, 随着集成学习(Ensemble Learning)的发展和大数据时代的到来, 决策树的缺点被逐渐克服, 同时它的优点得到了更好的发挥. 在工业界, 决策树以及对应的集成学习算法(如Boosting,随机森林)已经成为解决实际问题的重要工具之一. 成功应用包括,人脸检测,人体动作识别(Body Tracking).
==组成部分==
===分支节点===
正如名称所指, 分支节点决定输入数据进入哪一个分支。每个分支节点对应一个分支函数(劈分函数)，将不同的预测变量的值域映射到有限，离散的分支上。
===根节点===
根节点是一个特殊的分支节点，它是决策树的起点。
对于决策树来说，所有节点的分类或者回归目标都要在根节点已经定义好了。如果决策树的目标变量是离散的（序数型或者是列名型变量），则称它为分类树（Classification Tree）；如果目标变量是连续的（区间型变量），则称它为回归树（Regression Tree）。
===叶节点===
叶节点存储了决策树的输出。对于分类问题，所有类别的后验概率都存储在叶节点，观测走过了全树从上到下的某一条路径（决策过程）之后会根据叶子节点给出一个“观测属于哪一类”的预报；对于回归问题，叶子结点上存储了训练集目标变量的中位数，不同观测走过决策路径后如果到达了相同的叶子结点，则对它们给出相同预报。
==训练==
一棵决策树由分支节点(树的结构)和叶节点(树的输出)组成. 决策树的训练的目标是通过最小化某种形式的损失函数或者经验风险, 来确定每个分支函数的参数,以及叶节点的输出.
决策树自上而下的循环分支学习（Recursive Regression）采用了贪心算法。每个分支节点只关心自己的目标函数。具体来说, 给定一个分支节点, 以及落在该节点上对应样本的观测（包含自变量与目标变量），选择某个（一次选择一个变量的方法很常见）或某些预测变量，也许会经过一步对变量的离散化（对于连续自变量<math>X</math>而言），经过搜索不同形式的分叉函数且得到一个最优解（最优的含义是特定准则下收益最高或损失最小）。这个分支过程, 从根节点开始, 递归进行, 不断产生新的分支, 直到满足结束准则时停止。整个过程和树的分支生长非常相似。
==测试(预测)==
下图提供了一个简单的例子说明决策树的测试过程. 测试样本为 <math> x = [3,2,0]; </math>
# 进入根节点, 分支函数 <math> f_1(x) = x_3 - 1 = 0 - 1 = -1 </math> 小于0， 进入左分支
# 分支函数 <math> f_2(x) = x_1 - x_2 + 1 = 3 - 2 + 1 = 2 </math> 大于0, 进入右分支
# 分支函数 <math> f_4(x) = x_2 + 1 = 2 + 1 = 3 </math> 大于0, 进入右分支, 已经到达叶节点
# 假设是三分类问题, 该叶节点上所有类别的后验概率是 (0.1, 0.7, 0.2), 那么该决策树预测输入样本属于第二类.
[[File:DecisionTree2.png]]
=分支节点(树的结构)=
如前文所述, 决策树训练的核心是学习分支节点上的分支函数。
==分支函数形式==
在具体的学习过程中， 需要明确定义分支函数的具体形式. 常用的函数的形式都非常的简单如:
*一维线性函数: <math>f(x) = x_i + b</math>
*多维线性函数: <math>f(x) = <a,x> + b </math>, 其中<math><a,x></math>表示向量内积。
一般地，在常见的工程应用中使用一维线性函数。计算允许的条件下使用2-3个变量的线性组合作为分支函数的可能形式。
==分支函数选择==
为寻找合适的决策变量<math>X</math>与分支函数<math>f(x:X\rightarrow B)</math>，首先要找到全部的把<math>X</math>变量的不同水平(Levels)集合<math>L</math>映射到预先设置好的节点分叉集(Branches)<math>B</math>上的解集，得到<math>\{g(L \rightarrow B)\}</math>。<math>X</math>到<math>L</math>上的映射<math>h(X \rightarrow L)</math>，对于离散型变量而言就是对自身的映射，而对于连续型变量而言是向所属离散化区段的映射。最后得到分支函数的备选集合<math>\{f(x:X \rightarrow B)\} = \{g(h(x))\}</math>。
[[File:decisiontree_robustsplitordinal.png]]
如上图，我们可以看到对于任意区间型或者序数型的变量X与任意单调映射f，使用X和f(X)作为预测函数的变量，决策树的结果没有改变。同理，单独变化极端值也不会对决策树结果进行影响。可以说这种分支函数的选择使得决策树建模具有稳健性。
===建立用于分支函数选择的函数集合===
*设定决策树为<math>B</math>叉树，预测变量<math>X</math>（即分支函数的自变量）属于有<math>L</math>个水平的序数型(Ordinal)变量，或者<math>X</math>为被离散化成<math>L</math>段的区间型(Interval)变量。
注：后一种情况不仅把问题等价于处理<math>L</math>个不同水平的序数型变量，而且有效避免了极端值的影响。
举例以说明：
<math>
f(x)=x-a
\begin{cases}
<=0 &\text{then go to the left branch}\\
>0 &\text{then go to the right branch}
\end{cases}
</math>
<math>f(X)</math>为决定一个含X观测的样本进入左分支还是右分支的判断条件。此函数即为一个合理的备选分支函数。
更一般地，选择函数<math>g(L\rightarrow B)</math>时，映射<math>\{1,2,3,4\} \rightarrow \{1,1,2,2\}</math>，<math>\{1,2,3,4\} \rightarrow \{1,1,1,2\}</math>是被允许的，而<math>\{1,2,3,4\} \rightarrow \{1,2,2,1\}</math>是不被允许的，因为各个分叉之间没有办法继续保持排序性了。
在处理<math>L</math>个水平的序数型变量时，可以得到<math>L-1</math>可选的截断点，从中挑选<math>B-1</math>个位置截断，以保持排序性。
因此，进行最多<math>B</math>分叉时，搜索可得到备选分支函数的总数为一组组合数的和：
<math>\sum_{b=2}^{B} C_{L-1}^{b-1}</math>
易得，在二叉树时，需要搜索的备择分支函数总数仅有<math>L-1</math>个。
*设定决策树为<math>B</math>叉树，预测变量<math>X</math>属于有<math>L</math>个水平的列名型(Nominal)变量，则水平之间是无序的。
举例以说明：
X是列名型变量，取值为<math>\{1,2,...,9\}</math>，水平之间不存在排序关系。若函数形式为
<math>f(x) = x%3 </math>
一个观测点依据变量X的取值除以3的余数来选择究竟要进入0，1，2分支中的哪一个。因为原变量是无序的，分支也自然无法定义有序，此函数为一个合理的分支函数。
在处理<math>L</math>个水平的序数型变量时，不考虑水平之间的顺序与分叉之间的顺序，将他们分进不同的<math>B</math>个分叉上，其总数为第二类斯特林数<math>S(L,B)</math>(Stirling Number of the second kind)。
求解第二类斯特林数的边界条件表达式/迭代式分别为：<math>S(L,1)=1; S(L,B)=B\cdot{S}(L-1,B)+S(L-1,B-1) </math>
第二类斯特林数表：
{| class="wikitable"
|-
| 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
|}
考虑所有<math>B</math>的可能（从2到<math>L</math>）并求和，称为贝尔数(Bell Number)：
<math>B_L=\sum_{b=1}^L{S(L,b)}</math>
在实际问题中，为避免备择函数总数增加过快，我们也会限制分叉数最大值<math>B_{max}</math>不超过5，常选择2或3；这样也避免了搜索贝尔数<math>\sum_{b=2}^L{S(L,b)}=B_L - 1</math> 这样多的备择分支函数，将搜索数缩小到了<math>\sum_{b=2}^{B_{max}}{S(L,b)}</math>。
其他有助于优化搜索的方法：
*用于搜索的变量在全树中只使用一次
*节点内部采样，减少观测
*对<math>L</math>个水平进行层次聚类。CHAID使用了这种技术：
[[File:decisiontree_chaid_clustering.png]]
a)处理序数型或区间型变量时，在层次聚类时只考虑相邻分支的聚类，选择条件是“两个分支在目标变量上的分布最接近”（卡方意义上）；
从<math>L</math>个水平作为从<math>L</math>个不同分支开始，每次聚类减少一个分支；
在已有<math>B'</math>个分支时，需要考虑的聚类选择一共有<math>(B'-1)/2</math>种；
于是，依次比较了<math>L-1</math>，<math>L-2</math>，...，<math>1</math>个，一共<math>L(L-1)/2</math>个备择模型，得到分支数分别为<math>L,L-1,....,1</math>的各1个模型（共<math>L</math>个）从中选取最优；
b)处理列名型变量时，在层次聚类时考虑任意两个分支的聚类；
从<math>L</math>个水平作为从<math>L</math>个不同分支开始，每次聚类减少一个分支；
在已有<math>B'</math>个分支时，需要考虑的聚类选择一共有<math>B'(B'-1)/2</math>种；
于是，依次比较了<math>L(L-1)/2</math>，<math>(L-1)(L-2)/2</math>，...，<math>1</math>个，一共<math>(L+1)L(L-1)/6</math>个备择模型，得到分支数分别为<math>L,L-1,....,1</math>的各1个模型（共<math>L</math>个）从中选取最优。
===选择最优分支函数===
得到备选集合后，我们选取的最优分支函数应该使得其全部子节点上的样本的加权损失函数和最小。
*假设当前分支节点所有样本为 <math>\{ x_1,x_2,...,x_n\}</math>, 对应的类别标签为<math>\{ y_1,y_2,...,y_n\}</math>
*分支函数<math> f(x: X \rightarrow B) </math>将样本划分到两个或多个子节点. 其中<math> \mathcal{X}_{b} = \{x_i | f(x_i)=b\} </math> 表示第<math>b</math>个子节点样本的集合，<math>b \in \{1,2,...,B\}</math>
*<math>\mathcal{Y}_{b}, b \in \{1,2,....,B\}</math> 为对应的标签集合.
使用以上定义的符号, 分支函数的学习准则可以描述成如下的优化问题:
<math> f^* = \underset{f}\text{argmin} ( \sum_{b=1}^{B} L(\mathcal{X}_{b}, \mathcal{Y}_{b}) ) </math>
其中损失函数<math> L(\mathcal{X}, \mathcal{Y}) </math> 描述了样本的不纯度带来的损失。对于一个子节点<math>b</math>，给定样本数，如果其中样本的标签都相同, 那么样本纯度很高, 对应的损失函数值低；如果样本标签随机分布, 那么样本纯度很低，对应的损失函数值高。给定<math> \mathcal{Y}</math>在分类集上的概率密度，如果标签都相同，那么不管样本数的多少，纯度都很高，损失为0；如果标签随机分布，纯度很低，那么样本总数越多，带来的损失就越大。
==损失函数形式设定==
在实际训练中, 需要根据不同的需求选择适当的损失函数是必须的，损失函数的形式即是我们选择最优分支函数的优化目标。
===分类树损失函数===
假设<math>p_i</math>表示第<math>i</math>样本数量占所有样本总量<math> n </math>的百分比。
不同准则下，使用损失函数可以得到每次分支带来损失下降的规律：
[[File:decisiontree_impurity.png]]
====基尼不纯度(Gini impurity)准则====
<math> l_{G}(p) \propto n \sum_{i=1}^{m} p_i (1-p_i) </math>
按其定义式所表达的，它的含义是“任意取两个观测其属于不同类的概率”。生态学中，与Simpson's Diversity Index具有相同定义。
[[File:decisiontree_gini_impurity.png]]
在分支时的基尼不纯度改进为：
<math>\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)+... )</math>，<math>\{n_0,n_1,n_2,n_3,...\}</math>分别为当前节点与其分支节点的观测数；
基尼不纯度改进越大，说明分支后各个子节点任取两个观测数与不同类的概率越低；
====信息熵(Information entropy)准则====
<math> l_{E}(p) \propto - n \sum^{m}_{i=1} p_i \log^{}_2 p_i</math>
按其定义式所表达的，它的含义是“在该节点内使用变长码字对类别进行编码，所能达到的最优平均码字长度”
[[File:decisiontree_entropy.png]]
在分支时的调减熵减为：
<math> \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)+... ) </math>
熵减越大，说明节点经过一步分支后，各节点都能以较短的变长码字进行编码；
====对数价值(Logworth)准则====
在分支时，分支规则与对目标规则关联性越强，皮尔逊卡方检验值（Pearson's Chi-Square Test）对应P值的负对数 <math>-log_{10}(P(\mathcal{X}_{\nu}^2>\sum_{i,j}\frac{(O_{ij}-E{ij})^2}{E_{ij}}))</math>就越大。
其中，皮尔逊卡方统计量为在0假设（分支对分类毫无改进）下所有加权误差平方之和<math>\sum_{i,j}\frac{(O_{ij}-E{ij})^2}{E_{ij}}</math>，其中自由度<math>\nu=(B-1)(card(Y)-1)</math>
====经过Kass调整（Bonferroni界调整）的对数价值(P-Adjusted Logworth)准则====
<math>-log_{10}(mP) = \mbox{Logworth} -log_{10}{m}</math>
直觉上我们对对数价值法进行反思考虑如下的问题：如果我们尝试足够多的分支大小与可能性，是否我们在滥用Logworth法？我们把备择分支方案数目增大100倍，自然会选到Logworth更大的分支函数，而一味的细分分支使用的变量<math>X</math>丝毫不能说明<math>X</math>的预测强度正在变强。
经过调整，我们将Logworth进行调整，减掉的部分为<math>-log_{10}(m)</math>，其中<math>m</math>即为前面推导的“<math>L</math>水平，<math>B</math>分支时，全部备择分支函数集合”的大小：
<math>
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.
</math>
{| class="wikitable"
|-
| 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
|}
本例中：
<math>\Delta Gini=0.197, \Delta H=0.504, \mbox{Logworth}=140, m=96, \mbox{Adjusted Logworth}=138</math>
===回归树损失函数===
====方差的最大似然估计（MLE of Variance）准则====
很自然的，对于回归树而言，某子节点<math>b</math>上的所谓“不纯度”可以用其因变量<math>Y</math>的方差来表示：
[[File:decisiontree_var_red.png]]
<math>{Var}_b = \frac{1}{n_b}\sum_{j=1}^{n_b}(y_{jb}-\bar{y}_b)^2</math>
====绝对偏差(Least Absolute Deviation)准则====
<math>{LAD}_b = \frac{1}{n_b}\sum_{j=1}^{n_b}|y_{jb}-\bar{y}_b|</math>
====分支规则的F检验(Branching's F-Test)准则====
根据传统的单路方差分析（One-Way Analysis of Variance），可以得到如下定义：
分支节点间方差：<math>SS_{between}=\sum_{b=1}^B n_b(\bar{y}_b-\bar{y})^2</math>
分支节点内方差：<math>SS_{within}=\sum_{b=1}^B\sum_{j=1}^{n_b} (\bar{y}_b-y_{jb})^2</math>
分支前总方差：<math>SS_{between}=\sum_{b=1}^B\sum_{j=1}^{n_b} (\bar{y}-y_{jb})^2</math>
F-统计量检验：
<math>F=(\frac{SS_{between}}{SS_{within}})(\frac{n-B}{B-1}) \sim F_{B-1,n-B}</math>
这些在强烈异方差性下表现并不稳定。建议先对因变量<math>Y</math>做合适的变换（如乘幂，取对数等）防止稳定性降低。
==分支时的缺失值处理==
在实际问题处理中，在合理的数据清洗后，如果发现分支变量<math>X</math>含有缺失值的观测点较多，可以把选择缺失值作为一个单独的水平来搜索最优分支函数；缺失值较少的情况下可以考虑先只考虑无缺失值的最优分支函数，再将缺失值并入最大的一个分支或者后验概率最接近的一个分支。
如果使用“缺失值用于分支搜索”的方案，缺失值的出现无法保证原有的序数型/区间型变量存在一个水平排序用于模型选择，所以：
*处理序数型/区间型变量：无缺失值情况下如果发生了<math>b</math>个分支，只需要考虑缺失值作为独立分支或者附着于<math>b</math>个分支中的某一个的一共<math>b+1</math>种情况；
*处理列名型变量：简单地把缺失值作为独立水平进行搜索。
如果使用“缺失值用于推断”的方案，首先使用变量重要性来描述变量并排序，然后根据观测在某些变量是否为缺失值判断是否能由观测点得到可靠的预报。
在实际使用中，如果变量间有较强的局部/全局共线性，使用这种方法是不当的。
=叶节点(树的输出)=
*对于分类树, 决策树的叶节点上的输出就是所有类别的后验概率 <math> P(c|x) </math>. 可以用该叶节点各类别样本的频率来近似后验概率 <math> P(c|x) </math>. 后验概率最大的类别就是决策树对于新进单个观测点的预测结果，也就是 <math> c^* = \underset{c}{\text{argmax}} P(c|x) </math>。
*对于回归树，决策树的叶节点上的输出是叶子结点上观测点目标变量<math>Y</math>的中位数
=决策树停止生长准则=
==前向截止条件==
*最大深度: 树的节点的深度指的是, 从根节点出发到当前节点的路径长度. 如果某个节点的深度已经达到预先设定的深度, 那么就停止分支, 该节点被设定为叶节点.
*最少样本数量: 一般来说, 叶节点的样本量越多, 推广力越强. 反之, 则容易[[过拟合]]. 限制叶节点的最低样本量有助于提升决策树的推广能力. 如果当前节点样本量已经低于预先设定的阈值, 那么停止分支.
*纯度准则：分支过程若导致节点上不断地降低Gini不纯度/熵/节点内方差等，说明纯度一直在改进。达到特定的纯度即可停止分支。
这样得到的模型称为最大树(Largest Tree)或者全树。
==后向剪枝条件==
[[File:decisiontree_postpruning.png]]
在训练集上正确率随着叶子节点的增加而增加，但模型在验证数据集上，叶子节点数超过某个阈值后泛化能力反而会减弱。有时我们要在正向分支过程上创造远多于我们所需要的节点（如使用层数停止准则），然后根据一定规则，使用验证数据集进行后向剪枝。
使用后向剪枝的根本原因是，分支准则的局部最优性很可能不会使某一层所有分支节点的提升都均匀，甚至差距很大。那些提升不够显著的节点要从前向截止得到的模型中删除，留下一个全树的子树作为最终模型。
有时为了优化泛化性能，我们不仅考虑子树，也考虑那些通过比某子树多一次分枝能得到的非子树，在验证集上比较效果。
*最小化误分类/最大化准确度（分类树）：
<math>\mbox{Accuracy}=\frac{n_{TP}+n_{TN}}{n}</math>
*最大化收益（分类树）：
我们可以做更宽泛的假设，对不同类的观测进行预测产生的误分类，导致的利润（损失）也是不一样的。
<math>\mbox{Profit}=\mbox{Profit}_{TP}\frac{n_{TP}}{n}+\mbox{Profit}_{TN}\frac{n_{TN}}{n}+\mbox{Profit}_{FP}\frac{n_{FP}}{n}+\mbox{Profit}_{FN}\frac{n_{FN}}{n}</math>
*纯度准则（分类树，回归树）：
在前向剪枝中，可能设定了一个较为宽的纯度标准以使得树得以充分发展，而后在后向剪枝中保留其包含N个结点的纯度提升最大的子树。
*ASE 平均平方误差（分类树，回归树）：
使用平均平方误差作为后向剪枝准则是使用纯度准则的一个特例。对于回归树这一点不难理解，对于分类树来说，这是在验证集上重新计算类似Gini不纯度的指标：
<math>ASE = 1 - \sum_{i=1}^N p_{i-train}p_{i-valid}</math>
*稳健性模型选择
根据前面定义的几种评价树的规则（损失或者收益函数），定义树模型的选择标准，最小化下式：
<math>R_{\alpha}(T)=R(T)+\alpha |T|</math>
其中T为树的总结点个数。这个定义有点像模型选择中的信息选择的定义（SBC, AIC等）：选择越多变量或者树的节点越多，解释性越强，训练集上的风险越小，但泛化性能也会变差。合理选择参数<math>\alpha</math>，使得损失与树的节点个数的某个线性叠加最小，这样模型会更稳健。
*提升度(Lift)方法（分类树）：
如果我们特定感兴趣某一类事件A，我们可以通过把A事件在每一个叶子结点中出现的比例从大到小排序。设其在整个观测中出现的比例为<math>P_A</math>
依次加入这些叶子结点，我们得到从0%到100%观测的序列，这中间预测正确的A事件的概率（预测性能）从一个很高的值<math>P^*_A</math>下降到<math>P_A</math>，这样考察前面尽量少的一部分比例的观测点可以提取出尽量多的A事件。这条轨道上的每一个值比上<math>P_A</math>得到了一条新的轨道，称为Lift曲线，在100%观测处轨道下降到1。一条值恒为1的水平线称为基准线（Baseline）。
=模型性能诊断=
决策树本身是一种非常不稳定，容易产生过拟合的模型。使用分类问题常用的性能诊断方法对模型在训练集与测试集上进行比较。
对于分类树，经常使用的方法有提升图（Lift Chart），收益图(Gains Chart)等。
=成熟的决策树算法=
在实践中，不同的分支函数与结束准则往往对于解决不同的问题有不同的效果，科学软件以及商业软件更倾向于将各种成熟的准则/参数配置/优化方案作为一个整体并命名为决策树方案。
==C5.0==
该算法从ID3,C4.5改进而来。
*分支准则：ID3使用熵减收益作为准则，从C4.5开始使用熵减值与分支导致的熵增的比例作为准则（单节点纯度为0，分为多节点即带来熵增）
*分支数：2（ID3命名由此得来：Iterative Dichotomizer v3，决定了这是一个迭代二分支算法）
*叶节点大小：75
*分支最大深度：15
*C5.0嵌入了大规模学习常用的推进法
==CART(Classification and Regression Tree)==
*分支准则: Gini不纯度改进
*分支数：2
*叶节点大小：60个观测
*分支最大深度：10层
*缺失值推断：2次
*后向剪枝：ASE
==CHAID(CHi-squared Automatic Interaction Detection)==
*分支准则：Pearson卡方检验，显著性 1e-5，使用Kass P调整
*分支数：<=6
*节点大小：150
*模型选择：因为存在前剪枝，使用最大树
=决策树的大规模训练=
==交叉验证(Cross Validation)==
==袋装法(Bagging)==
==推进法(Boosting)==
=辅助功能=
*变量选择
*变量离散化
*离散化程度降低
*交互作用检测
*分层回归
*回归缺失值补齐
[[Category:旧词条迁移]]
|keywords=决策树
|description=决策树
}}
{{cquote|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}}
{{cquote|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}}
[[File:DecisionTree2.png|thumb]]
=引言=
如果突然问你"有一个陌生人叫X,Ta今天需要带伞吗?", 你一定会觉得这个问题就像告诉你"两千米外有一个超市,问超市里面有多少卷卫生纸"一样突兀. 可能几秒钟之后你会说"这要依情况而定, 如果今天烈日炎炎并且X是一个皮肤白皙的中国姑娘,或者外面下着大雨并且X是一个不得不去步行上班的屌丝码农, 那么Ta今天需要带伞, 否则不要."
当谈及这个看似无聊的问题的时候我们在谈什么？恩，在谈方法. 我们经常会遇到简单但又困难的抉择. 说简单,是因为候选方案简单而且清晰. 例如,要不要出国留学,要不要辞职创业,要不要投资黄金等等. 但是这些看似简单的选项背后却是困难的抉择. 面对这些困难的抉择, 一开始, 很可能不知所措. 值得庆幸的是, 很多时候, 这些看似不可能解决的问题, 最终可以被化解成一连串越来越简单的问题, 然后解决掉. 这个方法可以粗俗总结为: "如果这样这样这样, 那么选择A; 如果那样那样那样, 那么选择B", 当然这种方法有一个更加简洁形象的名字--决策树(Decision Tree), 也就是这篇文章的主题.
=定义=
决策树是一种分而治之(Divide and Conquer)的决策过程。一个困难的预测问题, 通过树的分支节点, 被划分成两个或多个较为简单的子集，从结构上划分为不同的子问题。将依规则分割数据集的过程不断递归下去(Recursive Partitioning)。随着树的深度不断增加，分支节点的子集越来越小，所需要提的问题数也逐渐简化。当分支节点的深度或者问题的简单程度满足一定的停止规则(Stopping Rule)时, 该分支节点会停止劈分，此为自上而下的停止阈值(Cutoff Threshold)法；有些决策树也使用自下而上的剪枝(Pruning)法。
==历史==
决策树含义直观,容易解释. 对于实际应用,决策树还有其他算法难以比肩的速度优势. 这使得决策树,一方面能够有效地进行大规模数据的处理和学习;另一方面在测试/预测阶段满足实时或者更高的速度要求. 历史上,因为预测结果方差大而且容易过拟合,决策树曾经一度被学术界冷落. 但是在近十年, 随着集成学习(Ensemble Learning)的发展和大数据时代的到来, 决策树的缺点被逐渐克服, 同时它的优点得到了更好的发挥. 在工业界, 决策树以及对应的集成学习算法(如Boosting,随机森林)已经成为解决实际问题的重要工具之一. 成功应用包括,人脸检测,人体动作识别(Body Tracking).
==组成部分==
===分支节点===
正如名称所指, 分支节点决定输入数据进入哪一个分支。每个分支节点对应一个分支函数(劈分函数)，将不同的预测变量的值域映射到有限，离散的分支上。
===根节点===
根节点是一个特殊的分支节点，它是决策树的起点。
对于决策树来说，所有节点的分类或者回归目标都要在根节点已经定义好了。如果决策树的目标变量是离散的（序数型或者是列名型变量），则称它为分类树（Classification Tree）；如果目标变量是连续的（区间型变量），则称它为回归树（Regression Tree）。
===叶节点===
叶节点存储了决策树的输出。对于分类问题，所有类别的后验概率都存储在叶节点，观测走过了全树从上到下的某一条路径（决策过程）之后会根据叶子节点给出一个“观测属于哪一类”的预报；对于回归问题，叶子结点上存储了训练集目标变量的中位数，不同观测走过决策路径后如果到达了相同的叶子结点，则对它们给出相同预报。
==训练==
一棵决策树由分支节点(树的结构)和叶节点(树的输出)组成. 决策树的训练的目标是通过最小化某种形式的损失函数或者经验风险, 来确定每个分支函数的参数,以及叶节点的输出.
决策树自上而下的循环分支学习（Recursive Regression）采用了贪心算法。每个分支节点只关心自己的目标函数。具体来说, 给定一个分支节点, 以及落在该节点上对应样本的观测（包含自变量与目标变量），选择某个（一次选择一个变量的方法很常见）或某些预测变量，也许会经过一步对变量的离散化（对于连续自变量<math>X</math>而言），经过搜索不同形式的分叉函数且得到一个最优解（最优的含义是特定准则下收益最高或损失最小）。这个分支过程, 从根节点开始, 递归进行, 不断产生新的分支, 直到满足结束准则时停止。整个过程和树的分支生长非常相似。
==测试(预测)==
下图提供了一个简单的例子说明决策树的测试过程. 测试样本为 <math> x = [3,2,0]; </math>
# 进入根节点, 分支函数 <math> f_1(x) = x_3 - 1 = 0 - 1 = -1 </math> 小于0， 进入左分支
# 分支函数 <math> f_2(x) = x_1 - x_2 + 1 = 3 - 2 + 1 = 2 </math> 大于0, 进入右分支
# 分支函数 <math> f_4(x) = x_2 + 1 = 2 + 1 = 3 </math> 大于0, 进入右分支, 已经到达叶节点
# 假设是三分类问题, 该叶节点上所有类别的后验概率是 (0.1, 0.7, 0.2), 那么该决策树预测输入样本属于第二类.
[[File:DecisionTree2.png]]
=分支节点(树的结构)=
如前文所述, 决策树训练的核心是学习分支节点上的分支函数。
==分支函数形式==
在具体的学习过程中， 需要明确定义分支函数的具体形式. 常用的函数的形式都非常的简单如:
*一维线性函数: <math>f(x) = x_i + b</math>
*多维线性函数: <math>f(x) = <a,x> + b </math>, 其中<math><a,x></math>表示向量内积。
一般地，在常见的工程应用中使用一维线性函数。计算允许的条件下使用2-3个变量的线性组合作为分支函数的可能形式。
==分支函数选择==
为寻找合适的决策变量<math>X</math>与分支函数<math>f(x:X\rightarrow B)</math>，首先要找到全部的把<math>X</math>变量的不同水平(Levels)集合<math>L</math>映射到预先设置好的节点分叉集(Branches)<math>B</math>上的解集，得到<math>\{g(L \rightarrow B)\}</math>。<math>X</math>到<math>L</math>上的映射<math>h(X \rightarrow L)</math>，对于离散型变量而言就是对自身的映射，而对于连续型变量而言是向所属离散化区段的映射。最后得到分支函数的备选集合<math>\{f(x:X \rightarrow B)\} = \{g(h(x))\}</math>。
[[File:decisiontree_robustsplitordinal.png]]
如上图，我们可以看到对于任意区间型或者序数型的变量X与任意单调映射f，使用X和f(X)作为预测函数的变量，决策树的结果没有改变。同理，单独变化极端值也不会对决策树结果进行影响。可以说这种分支函数的选择使得决策树建模具有稳健性。
===建立用于分支函数选择的函数集合===
*设定决策树为<math>B</math>叉树，预测变量<math>X</math>（即分支函数的自变量）属于有<math>L</math>个水平的序数型(Ordinal)变量，或者<math>X</math>为被离散化成<math>L</math>段的区间型(Interval)变量。
注：后一种情况不仅把问题等价于处理<math>L</math>个不同水平的序数型变量，而且有效避免了极端值的影响。
举例以说明：
<math>
f(x)=x-a
\begin{cases}
<=0 &\text{then go to the left branch}\\
>0 &\text{then go to the right branch}
\end{cases}
</math>
<math>f(X)</math>为决定一个含X观测的样本进入左分支还是右分支的判断条件。此函数即为一个合理的备选分支函数。
更一般地，选择函数<math>g(L\rightarrow B)</math>时，映射<math>\{1,2,3,4\} \rightarrow \{1,1,2,2\}</math>，<math>\{1,2,3,4\} \rightarrow \{1,1,1,2\}</math>是被允许的，而<math>\{1,2,3,4\} \rightarrow \{1,2,2,1\}</math>是不被允许的，因为各个分叉之间没有办法继续保持排序性了。
在处理<math>L</math>个水平的序数型变量时，可以得到<math>L-1</math>可选的截断点，从中挑选<math>B-1</math>个位置截断，以保持排序性。
因此，进行最多<math>B</math>分叉时，搜索可得到备选分支函数的总数为一组组合数的和：
<math>\sum_{b=2}^{B} C_{L-1}^{b-1}</math>
易得，在二叉树时，需要搜索的备择分支函数总数仅有<math>L-1</math>个。
*设定决策树为<math>B</math>叉树，预测变量<math>X</math>属于有<math>L</math>个水平的列名型(Nominal)变量，则水平之间是无序的。
举例以说明：
X是列名型变量，取值为<math>\{1,2,...,9\}</math>，水平之间不存在排序关系。若函数形式为
<math>f(x) = x%3 </math>
一个观测点依据变量X的取值除以3的余数来选择究竟要进入0，1，2分支中的哪一个。因为原变量是无序的，分支也自然无法定义有序，此函数为一个合理的分支函数。
在处理<math>L</math>个水平的序数型变量时，不考虑水平之间的顺序与分叉之间的顺序，将他们分进不同的<math>B</math>个分叉上，其总数为第二类斯特林数<math>S(L,B)</math>(Stirling Number of the second kind)。
求解第二类斯特林数的边界条件表达式/迭代式分别为：<math>S(L,1)=1; S(L,B)=B\cdot{S}(L-1,B)+S(L-1,B-1) </math>
第二类斯特林数表：
{| class="wikitable"
|-
| 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
|}
考虑所有<math>B</math>的可能（从2到<math>L</math>）并求和，称为贝尔数(Bell Number)：
<math>B_L=\sum_{b=1}^L{S(L,b)}</math>
在实际问题中，为避免备择函数总数增加过快，我们也会限制分叉数最大值<math>B_{max}</math>不超过5，常选择2或3；这样也避免了搜索贝尔数<math>\sum_{b=2}^L{S(L,b)}=B_L - 1</math> 这样多的备择分支函数，将搜索数缩小到了<math>\sum_{b=2}^{B_{max}}{S(L,b)}</math>。
其他有助于优化搜索的方法：
*用于搜索的变量在全树中只使用一次
*节点内部采样，减少观测
*对<math>L</math>个水平进行层次聚类。CHAID使用了这种技术：
[[File:decisiontree_chaid_clustering.png]]
a)处理序数型或区间型变量时，在层次聚类时只考虑相邻分支的聚类，选择条件是“两个分支在目标变量上的分布最接近”（卡方意义上）；
从<math>L</math>个水平作为从<math>L</math>个不同分支开始，每次聚类减少一个分支；
在已有<math>B'</math>个分支时，需要考虑的聚类选择一共有<math>(B'-1)/2</math>种；
于是，依次比较了<math>L-1</math>，<math>L-2</math>，...，<math>1</math>个，一共<math>L(L-1)/2</math>个备择模型，得到分支数分别为<math>L,L-1,....,1</math>的各1个模型（共<math>L</math>个）从中选取最优；
b)处理列名型变量时，在层次聚类时考虑任意两个分支的聚类；
从<math>L</math>个水平作为从<math>L</math>个不同分支开始，每次聚类减少一个分支；
在已有<math>B'</math>个分支时，需要考虑的聚类选择一共有<math>B'(B'-1)/2</math>种；
于是，依次比较了<math>L(L-1)/2</math>，<math>(L-1)(L-2)/2</math>，...，<math>1</math>个，一共<math>(L+1)L(L-1)/6</math>个备择模型，得到分支数分别为<math>L,L-1,....,1</math>的各1个模型（共<math>L</math>个）从中选取最优。
===选择最优分支函数===
得到备选集合后，我们选取的最优分支函数应该使得其全部子节点上的样本的加权损失函数和最小。
*假设当前分支节点所有样本为 <math>\{ x_1,x_2,...,x_n\}</math>, 对应的类别标签为<math>\{ y_1,y_2,...,y_n\}</math>
*分支函数<math> f(x: X \rightarrow B) </math>将样本划分到两个或多个子节点. 其中<math> \mathcal{X}_{b} = \{x_i | f(x_i)=b\} </math> 表示第<math>b</math>个子节点样本的集合，<math>b \in \{1,2,...,B\}</math>
*<math>\mathcal{Y}_{b}, b \in \{1,2,....,B\}</math> 为对应的标签集合.
使用以上定义的符号, 分支函数的学习准则可以描述成如下的优化问题:
<math> f^* = \underset{f}\text{argmin} ( \sum_{b=1}^{B} L(\mathcal{X}_{b}, \mathcal{Y}_{b}) ) </math>
其中损失函数<math> L(\mathcal{X}, \mathcal{Y}) </math> 描述了样本的不纯度带来的损失。对于一个子节点<math>b</math>，给定样本数，如果其中样本的标签都相同, 那么样本纯度很高, 对应的损失函数值低；如果样本标签随机分布, 那么样本纯度很低，对应的损失函数值高。给定<math> \mathcal{Y}</math>在分类集上的概率密度，如果标签都相同，那么不管样本数的多少，纯度都很高，损失为0；如果标签随机分布，纯度很低，那么样本总数越多，带来的损失就越大。
==损失函数形式设定==
在实际训练中, 需要根据不同的需求选择适当的损失函数是必须的，损失函数的形式即是我们选择最优分支函数的优化目标。
===分类树损失函数===
假设<math>p_i</math>表示第<math>i</math>样本数量占所有样本总量<math> n </math>的百分比。
不同准则下，使用损失函数可以得到每次分支带来损失下降的规律：
[[File:decisiontree_impurity.png]]
====基尼不纯度(Gini impurity)准则====
<math> l_{G}(p) \propto n \sum_{i=1}^{m} p_i (1-p_i) </math>
按其定义式所表达的，它的含义是“任意取两个观测其属于不同类的概率”。生态学中，与Simpson's Diversity Index具有相同定义。
[[File:decisiontree_gini_impurity.png]]
在分支时的基尼不纯度改进为：
<math>\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)+... )</math>，<math>\{n_0,n_1,n_2,n_3,...\}</math>分别为当前节点与其分支节点的观测数；
基尼不纯度改进越大，说明分支后各个子节点任取两个观测数与不同类的概率越低；
====信息熵(Information entropy)准则====
<math> l_{E}(p) \propto - n \sum^{m}_{i=1} p_i \log^{}_2 p_i</math>
按其定义式所表达的，它的含义是“在该节点内使用变长码字对类别进行编码，所能达到的最优平均码字长度”
[[File:decisiontree_entropy.png]]
在分支时的调减熵减为：
<math> \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)+... ) </math>
熵减越大，说明节点经过一步分支后，各节点都能以较短的变长码字进行编码；
====对数价值(Logworth)准则====
在分支时，分支规则与对目标规则关联性越强，皮尔逊卡方检验值（Pearson's Chi-Square Test）对应P值的负对数 <math>-log_{10}(P(\mathcal{X}_{\nu}^2>\sum_{i,j}\frac{(O_{ij}-E{ij})^2}{E_{ij}}))</math>就越大。
其中，皮尔逊卡方统计量为在0假设（分支对分类毫无改进）下所有加权误差平方之和<math>\sum_{i,j}\frac{(O_{ij}-E{ij})^2}{E_{ij}}</math>，其中自由度<math>\nu=(B-1)(card(Y)-1)</math>
====经过Kass调整（Bonferroni界调整）的对数价值(P-Adjusted Logworth)准则====
<math>-log_{10}(mP) = \mbox{Logworth} -log_{10}{m}</math>
直觉上我们对对数价值法进行反思考虑如下的问题：如果我们尝试足够多的分支大小与可能性，是否我们在滥用Logworth法？我们把备择分支方案数目增大100倍，自然会选到Logworth更大的分支函数，而一味的细分分支使用的变量<math>X</math>丝毫不能说明<math>X</math>的预测强度正在变强。
经过调整，我们将Logworth进行调整，减掉的部分为<math>-log_{10}(m)</math>，其中<math>m</math>即为前面推导的“<math>L</math>水平，<math>B</math>分支时，全部备择分支函数集合”的大小：
<math>
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.
</math>
{| class="wikitable"
|-
| 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
|}
本例中：
<math>\Delta Gini=0.197, \Delta H=0.504, \mbox{Logworth}=140, m=96, \mbox{Adjusted Logworth}=138</math>
===回归树损失函数===
====方差的最大似然估计（MLE of Variance）准则====
很自然的，对于回归树而言，某子节点<math>b</math>上的所谓“不纯度”可以用其因变量<math>Y</math>的方差来表示：
[[File:decisiontree_var_red.png]]
<math>{Var}_b = \frac{1}{n_b}\sum_{j=1}^{n_b}(y_{jb}-\bar{y}_b)^2</math>
====绝对偏差(Least Absolute Deviation)准则====
<math>{LAD}_b = \frac{1}{n_b}\sum_{j=1}^{n_b}|y_{jb}-\bar{y}_b|</math>
====分支规则的F检验(Branching's F-Test)准则====
根据传统的单路方差分析（One-Way Analysis of Variance），可以得到如下定义：
分支节点间方差：<math>SS_{between}=\sum_{b=1}^B n_b(\bar{y}_b-\bar{y})^2</math>
分支节点内方差：<math>SS_{within}=\sum_{b=1}^B\sum_{j=1}^{n_b} (\bar{y}_b-y_{jb})^2</math>
分支前总方差：<math>SS_{between}=\sum_{b=1}^B\sum_{j=1}^{n_b} (\bar{y}-y_{jb})^2</math>
F-统计量检验：
<math>F=(\frac{SS_{between}}{SS_{within}})(\frac{n-B}{B-1}) \sim F_{B-1,n-B}</math>
这些在强烈异方差性下表现并不稳定。建议先对因变量<math>Y</math>做合适的变换（如乘幂，取对数等）防止稳定性降低。
==分支时的缺失值处理==
在实际问题处理中，在合理的数据清洗后，如果发现分支变量<math>X</math>含有缺失值的观测点较多，可以把选择缺失值作为一个单独的水平来搜索最优分支函数；缺失值较少的情况下可以考虑先只考虑无缺失值的最优分支函数，再将缺失值并入最大的一个分支或者后验概率最接近的一个分支。
如果使用“缺失值用于分支搜索”的方案，缺失值的出现无法保证原有的序数型/区间型变量存在一个水平排序用于模型选择，所以：
*处理序数型/区间型变量：无缺失值情况下如果发生了<math>b</math>个分支，只需要考虑缺失值作为独立分支或者附着于<math>b</math>个分支中的某一个的一共<math>b+1</math>种情况；
*处理列名型变量：简单地把缺失值作为独立水平进行搜索。
如果使用“缺失值用于推断”的方案，首先使用变量重要性来描述变量并排序，然后根据观测在某些变量是否为缺失值判断是否能由观测点得到可靠的预报。
在实际使用中，如果变量间有较强的局部/全局共线性，使用这种方法是不当的。
=叶节点(树的输出)=
*对于分类树, 决策树的叶节点上的输出就是所有类别的后验概率 <math> P(c|x) </math>. 可以用该叶节点各类别样本的频率来近似后验概率 <math> P(c|x) </math>. 后验概率最大的类别就是决策树对于新进单个观测点的预测结果，也就是 <math> c^* = \underset{c}{\text{argmax}} P(c|x) </math>。
*对于回归树，决策树的叶节点上的输出是叶子结点上观测点目标变量<math>Y</math>的中位数
=决策树停止生长准则=
==前向截止条件==
*最大深度: 树的节点的深度指的是, 从根节点出发到当前节点的路径长度. 如果某个节点的深度已经达到预先设定的深度, 那么就停止分支, 该节点被设定为叶节点.
*最少样本数量: 一般来说, 叶节点的样本量越多, 推广力越强. 反之, 则容易[[过拟合]]. 限制叶节点的最低样本量有助于提升决策树的推广能力. 如果当前节点样本量已经低于预先设定的阈值, 那么停止分支.
*纯度准则：分支过程若导致节点上不断地降低Gini不纯度/熵/节点内方差等，说明纯度一直在改进。达到特定的纯度即可停止分支。
这样得到的模型称为最大树(Largest Tree)或者全树。
==后向剪枝条件==
[[File:decisiontree_postpruning.png]]
在训练集上正确率随着叶子节点的增加而增加，但模型在验证数据集上，叶子节点数超过某个阈值后泛化能力反而会减弱。有时我们要在正向分支过程上创造远多于我们所需要的节点（如使用层数停止准则），然后根据一定规则，使用验证数据集进行后向剪枝。
使用后向剪枝的根本原因是，分支准则的局部最优性很可能不会使某一层所有分支节点的提升都均匀，甚至差距很大。那些提升不够显著的节点要从前向截止得到的模型中删除，留下一个全树的子树作为最终模型。
有时为了优化泛化性能，我们不仅考虑子树，也考虑那些通过比某子树多一次分枝能得到的非子树，在验证集上比较效果。
*最小化误分类/最大化准确度（分类树）：
<math>\mbox{Accuracy}=\frac{n_{TP}+n_{TN}}{n}</math>
*最大化收益（分类树）：
我们可以做更宽泛的假设，对不同类的观测进行预测产生的误分类，导致的利润（损失）也是不一样的。
<math>\mbox{Profit}=\mbox{Profit}_{TP}\frac{n_{TP}}{n}+\mbox{Profit}_{TN}\frac{n_{TN}}{n}+\mbox{Profit}_{FP}\frac{n_{FP}}{n}+\mbox{Profit}_{FN}\frac{n_{FN}}{n}</math>
*纯度准则（分类树，回归树）：
在前向剪枝中，可能设定了一个较为宽的纯度标准以使得树得以充分发展，而后在后向剪枝中保留其包含N个结点的纯度提升最大的子树。
*ASE 平均平方误差（分类树，回归树）：
使用平均平方误差作为后向剪枝准则是使用纯度准则的一个特例。对于回归树这一点不难理解，对于分类树来说，这是在验证集上重新计算类似Gini不纯度的指标：
<math>ASE = 1 - \sum_{i=1}^N p_{i-train}p_{i-valid}</math>
*稳健性模型选择
根据前面定义的几种评价树的规则（损失或者收益函数），定义树模型的选择标准，最小化下式：
<math>R_{\alpha}(T)=R(T)+\alpha |T|</math>
其中T为树的总结点个数。这个定义有点像模型选择中的信息选择的定义（SBC, AIC等）：选择越多变量或者树的节点越多，解释性越强，训练集上的风险越小，但泛化性能也会变差。合理选择参数<math>\alpha</math>，使得损失与树的节点个数的某个线性叠加最小，这样模型会更稳健。
*提升度(Lift)方法（分类树）：
如果我们特定感兴趣某一类事件A，我们可以通过把A事件在每一个叶子结点中出现的比例从大到小排序。设其在整个观测中出现的比例为<math>P_A</math>
依次加入这些叶子结点，我们得到从0%到100%观测的序列，这中间预测正确的A事件的概率（预测性能）从一个很高的值<math>P^*_A</math>下降到<math>P_A</math>，这样考察前面尽量少的一部分比例的观测点可以提取出尽量多的A事件。这条轨道上的每一个值比上<math>P_A</math>得到了一条新的轨道，称为Lift曲线，在100%观测处轨道下降到1。一条值恒为1的水平线称为基准线（Baseline）。
=模型性能诊断=
决策树本身是一种非常不稳定，容易产生过拟合的模型。使用分类问题常用的性能诊断方法对模型在训练集与测试集上进行比较。
对于分类树，经常使用的方法有提升图（Lift Chart），收益图(Gains Chart)等。
=成熟的决策树算法=
在实践中，不同的分支函数与结束准则往往对于解决不同的问题有不同的效果，科学软件以及商业软件更倾向于将各种成熟的准则/参数配置/优化方案作为一个整体并命名为决策树方案。
==C5.0==
该算法从ID3,C4.5改进而来。
*分支准则：ID3使用熵减收益作为准则，从C4.5开始使用熵减值与分支导致的熵增的比例作为准则（单节点纯度为0，分为多节点即带来熵增）
*分支数：2（ID3命名由此得来：Iterative Dichotomizer v3，决定了这是一个迭代二分支算法）
*叶节点大小：75
*分支最大深度：15
*C5.0嵌入了大规模学习常用的推进法
==CART(Classification and Regression Tree)==
*分支准则: Gini不纯度改进
*分支数：2
*叶节点大小：60个观测
*分支最大深度：10层
*缺失值推断：2次
*后向剪枝：ASE
==CHAID(CHi-squared Automatic Interaction Detection)==
*分支准则：Pearson卡方检验，显著性 1e-5，使用Kass P调整
*分支数：<=6
*节点大小：150
*模型选择：因为存在前剪枝，使用最大树
=决策树的大规模训练=
==交叉验证(Cross Validation)==
==袋装法(Bagging)==
==推进法(Boosting)==
=辅助功能=
*变量选择
*变量离散化
*离散化程度降低
*交互作用检测
*分层回归
*回归缺失值补齐
[[Category:旧词条迁移]]