7,129
个编辑
更改
跳到导航
跳到搜索
第3行：
第3行： − − − {{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}} − + + − =引言= − 如果突然问你"有一个陌生人叫X,Ta今天需要带伞吗?", 你一定会觉得这个问题就像告诉你"两千米外有一个超市,问超市里面有多少卷卫生纸"一样突兀. 可能几秒钟之后你会说"这要依情况而定, 如果今天烈日炎炎并且X是一个皮肤白皙的中国姑娘,或者外面下着大雨并且X是一个不得不去步行上班的屌丝码农, 那么Ta今天需要带伞, 否则不要."+ − 当谈及这个看似无聊的问题的时候我们在谈什么？恩，在谈方法. 我们经常会遇到简单但又困难的抉择. 说简单,是因为候选方案简单而且清晰. 例如,要不要出国留学,要不要辞职创业,要不要投资黄金等等. 但是这些看似简单的选项背后却是困难的抉择. 面对这些困难的抉择, 一开始, 很可能不知所措. 值得庆幸的是, 很多时候, 这些看似不可能解决的问题, 最终可以被化解成一连串越来越简单的问题, 然后解决掉. 这个方法可以粗俗总结为: "如果这样这样这样, 那么选择A; 如果那样那样那样, 那么选择B", 当然这种方法有一个更加简洁形象的名字--决策树(Decision Tree), 也就是这篇文章的主题. − + − + + + 第32行：
第28行： − 对于决策树来说，所有节点的分类或者回归目标都要在根节点已经定义好了。如果决策树的目标变量是离散的（序数型或者是列名型变量），则称它为分类树（Classification Tree）；如果目标变量是连续的（区间型变量），则称它为回归树（Regression Tree）。+ + + + 第41行：
第40行： − 决策树自上而下的循环分支学习（Recursive Regression）采用了贪心算法。每个分支节点只关心自己的目标函数。具体来说, 给定一个分支节点, 以及落在该节点上对应样本的观测（包含自变量与目标变量），选择某个（一次选择一个变量的方法很常见）或某些预测变量，也许会经过一步对变量的离散化（对于连续自变量<math>X</math>而言），经过搜索不同形式的分叉函数且得到一个最优解（最优的含义是特定准则下收益最高或损失最小）。这个分支过程, 从根节点开始, 递归进行, 不断产生新的分支, 直到满足结束准则时停止。整个过程和树的分支生长非常相似。+ + 第52行：
第52行： + 第58行：
第59行： + + + 第70行：
第74行： + 第89行：
第94行： + + + + + + + + + + + + + 第136行：
第154行： + + + 第149行：
第170行： + + + + + + + + + + + + + 第190行：
第224行： − + + + + + − + + + + + 第218行：
第260行： − + + 第224行：
第267行： − + + + + 第251行：
第297行： + − + − 第262行：
第308行： − + + − + + 第281行：
第329行： + + + 第295行：
第346行： + + 第306行：
第359行： + + − + − 在训练集上正确率随着叶子节点的增加而增加，但模型在验证数据集上，叶子节点数超过某个阈值后泛化能力反而会减弱。有时我们要在正向分支过程上创造远多于我们所需要的节点（如使用层数停止准则），然后根据一定规则，使用验证数据集进行后向剪枝。 + + + 第327行：
第384行： + + 第337行：
第396行： + 第345行：
第405行： + 第351行：
第412行： + 第356行：
第418行： − 对于分类树，经常使用的方法有提升图（Lift Chart），收益图(Gains Chart)等。+ + + + + 第369行：
第435行： + 第378行：
第445行： + 第385行：
第453行： − =决策树的大规模训练= − ==交叉验证(Cross Validation)== − ==袋装法(Bagging)== − ==推进法(Boosting)== − + − *变量选择+ − *变量离散化+ − *离散化程度降低+ − *交互作用检测+ − *分层回归+ − *回归缺失值补齐+ − + + + +
无编辑摘要
|description=决策树
|description=决策树
}}
}}
[[File:DecisionTree2.png|thumb]]
[[File:DecisionTree2.png|thumb]]
=引言=
如果突然问你"有一个陌生人叫X,Ta今天需要带伞吗?", 你一定会觉得这个问题就像告诉你"两千米外有一个超市,问超市里面有多少卷卫生纸"一样突兀. 可能几秒钟之后你会说"这要依情况而定, 如果今天烈日炎炎并且X是一个皮肤白皙的中国姑娘,或者外面下着大雨并且X是一个不得不去步行上班的屌丝码农, 那么Ta今天需要带伞, 否则不要."
当谈及这个看似无聊的问题的时候我们在谈什么？恩，在谈方法. 我们经常会遇到简单但又困难的抉择. 说简单,是因为候选方案简单而且清晰. 例如,要不要出国留学,要不要辞职创业,要不要投资黄金等等. 但是这些看似简单的选项背后却是困难的抉择. 面对这些困难的抉择, 一开始, 很可能不知所措. 值得庆幸的是, 很多时候, 这些看似不可能解决的问题, 最终可以被化解成一连串越来越简单的问题, 然后解决掉. 这个方法可以粗俗总结为: "如果这样这样这样, 那么选择A; 如果那样那样那样, 那么选择B", 当然这种方法有一个更加简洁形象的名字--'''决策树 Decision Tree''', 也就是这篇文章的主题.
=定义=
=定义=
决策树是一种分而治之(Divide and Conquer)的决策过程。一个困难的预测问题, 通过树的分支节点, 被划分成两个或多个较为简单的子集，从结构上划分为不同的子问题。将依规则分割数据集的过程不断递归下去(Recursive Partitioning)。随着树的深度不断增加，分支节点的子集越来越小，所需要提的问题数也逐渐简化。当分支节点的深度或者问题的简单程度满足一定的停止规则(Stopping Rule)时, 该分支节点会停止劈分，此为自上而下的停止阈值(Cutoff Threshold)法；有些决策树也使用自下而上的剪枝(Pruning)法。
决策树是一种分而治之 Divide and Conquer的决策过程。一个困难的预测问题, 通过树的分支节点, 被划分成两个或多个较为简单的子集，从结构上划分为不同的子问题。将依规则分割数据集的过程不断递归下去 Recursive Partitioning。随着树的深度不断增加，分支节点的子集越来越小，所需要提的问题数也逐渐简化。当分支节点的深度或者问题的简单程度满足一定的停止规则 Stopping Rule时, 该分支节点会停止劈分，此为自上而下的停止阈值 Cutoff Threshold法；有些决策树也使用自下而上的剪枝 Pruning法。
==历史==
==历史==
决策树含义直观,容易解释. 对于实际应用,决策树还有其他算法难以比肩的速度优势. 这使得决策树,一方面能够有效地进行大规模数据的处理和学习;另一方面在测试/预测阶段满足实时或者更高的速度要求. 历史上,因为预测结果方差大而且容易过拟合,决策树曾经一度被学术界冷落. 但是在近十年, 随着集成学习(Ensemble Learning)的发展和大数据时代的到来, 决策树的缺点被逐渐克服, 同时它的优点得到了更好的发挥. 在工业界, 决策树以及对应的集成学习算法(如Boosting,随机森林)已经成为解决实际问题的重要工具之一. 成功应用包括,人脸检测,人体动作识别(Body Tracking).
决策树含义直观,容易解释. 对于实际应用,决策树还有其他算法难以比肩的速度优势. 这使得决策树,一方面能够有效地进行大规模数据的处理和学习;另一方面在测试/预测阶段满足实时或者更高的速度要求. 历史上,因为预测结果方差大而且容易过拟合,决策树曾经一度被学术界冷落. 但是在近十年, 随着集成学习的发展和大数据时代的到来, 决策树的缺点被逐渐克服, 同时它的优点得到了更好的发挥. 在工业界, 决策树以及对应的集成学习算法(如[[随机森林]])已经成为解决实际问题的重要工具之一. 成功应用包括,人脸检测,人体动作识别。
==组成部分==
==组成部分==
===分支节点===
===分支节点===
正如名称所指, 分支节点决定输入数据进入哪一个分支。每个分支节点对应一个分支函数(劈分函数)，将不同的预测变量的值域映射到有限，离散的分支上。
正如名称所指, 分支节点决定输入数据进入哪一个分支。每个分支节点对应一个分支函数(劈分函数)，将不同的预测变量的值域映射到有限，离散的分支上。
===根节点===
===根节点===
根节点是一个特殊的分支节点，它是决策树的起点。
根节点是一个特殊的分支节点，它是决策树的起点。
对于决策树来说，所有节点的分类或者回归目标都要在根节点已经定义好了。如果决策树的目标变量是离散的（序数型或者是列名型变量），则称它为'''分类树 Classification Tree'''；如果目标变量是连续的（区间型变量），则称它为'''回归树 Regression Tree'''。
===叶节点===
===叶节点===
叶节点存储了决策树的输出。对于分类问题，所有类别的后验概率都存储在叶节点，观测走过了全树从上到下的某一条路径（决策过程）之后会根据叶子节点给出一个“观测属于哪一类”的预报；对于回归问题，叶子结点上存储了训练集目标变量的中位数，不同观测走过决策路径后如果到达了相同的叶子结点，则对它们给出相同预报。
叶节点存储了决策树的输出。对于分类问题，所有类别的后验概率都存储在叶节点，观测走过了全树从上到下的某一条路径（决策过程）之后会根据叶子节点给出一个“观测属于哪一类”的预报；对于回归问题，叶子结点上存储了训练集目标变量的中位数，不同观测走过决策路径后如果到达了相同的叶子结点，则对它们给出相同预报。
==训练==
==训练==
一棵决策树由分支节点(树的结构)和叶节点(树的输出)组成. 决策树的训练的目标是通过最小化某种形式的损失函数或者经验风险, 来确定每个分支函数的参数,以及叶节点的输出.
一棵决策树由分支节点(树的结构)和叶节点(树的输出)组成. 决策树的训练的目标是通过最小化某种形式的损失函数或者经验风险, 来确定每个分支函数的参数,以及叶节点的输出.
决策树自上而下的循环分支学习 Recursive Regression采用了贪心算法。每个分支节点只关心自己的目标函数。具体来说, 给定一个分支节点, 以及落在该节点上对应样本的观测（包含自变量与目标变量），选择某个（一次选择一个变量的方法很常见）或某些预测变量，也许会经过一步对变量的离散化（对于连续自变量<math>X</math>而言），经过搜索不同形式的分叉函数且得到一个最优解（最优的含义是特定准则下收益最高或损失最小）。这个分支过程, 从根节点开始, 递归进行, 不断产生新的分支, 直到满足结束准则时停止。整个过程和树的分支生长非常相似。
[[File:DecisionTree2.png]]
[[File:DecisionTree2.png]]
=分支节点(树的结构)=
=分支节点(树的结构)=
==分支函数形式==
==分支函数形式==
在具体的学习过程中， 需要明确定义分支函数的具体形式. 常用的函数的形式都非常的简单如:
在具体的学习过程中， 需要明确定义分支函数的具体形式. 常用的函数的形式都非常的简单如:
*一维线性函数: <math>f(x) = x_i + b</math>
*一维线性函数: <math>f(x) = x_i + b</math>
*多维线性函数: <math>f(x) = <a,x> + b </math>, 其中<math><a,x></math>表示向量内积。
*多维线性函数: <math>f(x) = <a,x> + b </math>, 其中<math><a,x></math>表示向量内积。
一般地，在常见的工程应用中使用一维线性函数。计算允许的条件下使用2-3个变量的线性组合作为分支函数的可能形式。
一般地，在常见的工程应用中使用一维线性函数。计算允许的条件下使用2-3个变量的线性组合作为分支函数的可能形式。
==分支函数选择==
==分支函数选择==
如上图，我们可以看到对于任意区间型或者序数型的变量X与任意单调映射f，使用X和f(X)作为预测函数的变量，决策树的结果没有改变。同理，单独变化极端值也不会对决策树结果进行影响。可以说这种分支函数的选择使得决策树建模具有稳健性。
如上图，我们可以看到对于任意区间型或者序数型的变量X与任意单调映射f，使用X和f(X)作为预测函数的变量，决策树的结果没有改变。同理，单独变化极端值也不会对决策树结果进行影响。可以说这种分支函数的选择使得决策树建模具有稳健性。
===建立用于分支函数选择的函数集合===
===建立用于分支函数选择的函数集合===
<math>f(X)</math>为决定一个含X观测的样本进入左分支还是右分支的判断条件。此函数即为一个合理的备选分支函数。
<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>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>L</math>个水平的序数型变量时，可以得到<math>L-1</math>可选的截断点，从中挑选<math>B-1</math>个位置截断，以保持排序性。
因此，进行最多<math>B</math>分叉时，搜索可得到备选分支函数的总数为一组组合数的和：
因此，进行最多<math>B</math>分叉时，搜索可得到备选分支函数的总数为一组组合数的和：
<math>\sum_{b=2}^{B} C_{L-1}^{b-1}</math>
<math>\sum_{b=2}^{B} C_{L-1}^{b-1}</math>
易得，在二叉树时，需要搜索的备择分支函数总数仅有<math>L-1</math>个。
易得，在二叉树时，需要搜索的备择分支函数总数仅有<math>L-1</math>个。
*设定决策树为<math>B</math>叉树，预测变量<math>X</math>属于有<math>L</math>个水平的列名型(Nominal)变量，则水平之间是无序的。
*设定决策树为<math>B</math>叉树，预测变量<math>X</math>属于有<math>L</math>个水平的列名型(Nominal)变量，则水平之间是无序的。
举例以说明：
举例以说明：
X是列名型变量，取值为<math>\{1,2,...,9\}</math>，水平之间不存在排序关系。若函数形式为
X是列名型变量，取值为<math>\{1,2,...,9\}</math>，水平之间不存在排序关系。若函数形式为
<math>f(x) = x%3 </math>
<math>f(x) = x%3 </math>
一个观测点依据变量X的取值除以3的余数来选择究竟要进入0，1，2分支中的哪一个。因为原变量是无序的，分支也自然无法定义有序，此函数为一个合理的分支函数。
一个观测点依据变量X的取值除以3的余数来选择究竟要进入0，1，2分支中的哪一个。因为原变量是无序的，分支也自然无法定义有序，此函数为一个合理的分支函数。
在处理<math>L</math>个水平的序数型变量时，不考虑水平之间的顺序与分叉之间的顺序，将他们分进不同的<math>B</math>个分叉上，其总数为第二类斯特林数<math>S(L,B)</math>(Stirling Number of the second kind)。
在处理<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>
求解第二类斯特林数的边界条件表达式/迭代式分别为：<math>S(L,1)=1; S(L,B)=B\cdot{S}(L-1,B)+S(L-1,B-1) </math>
第二类斯特林数表：
第二类斯特林数表：
{| class="wikitable"
{| class="wikitable"
考虑所有<math>B</math>的可能（从2到<math>L</math>）并求和，称为贝尔数(Bell Number)：
考虑所有<math>B</math>的可能（从2到<math>L</math>）并求和，称为贝尔数(Bell Number)：
<math>B_L=\sum_{b=1}^L{S(L,b)}</math>
<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>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>。
其他有助于优化搜索的方法：
其他有助于优化搜索的方法：
a)处理序数型或区间型变量时，在层次聚类时只考虑相邻分支的聚类，选择条件是“两个分支在目标变量上的分布最接近”（卡方意义上）；
a)处理序数型或区间型变量时，在层次聚类时只考虑相邻分支的聚类，选择条件是“两个分支在目标变量上的分布最接近”（卡方意义上）；
从<math>L</math>个水平作为从<math>L</math>个不同分支开始，每次聚类减少一个分支；
从<math>L</math>个水平作为从<math>L</math>个不同分支开始，每次聚类减少一个分支；
在已有<math>B'</math>个分支时，需要考虑的聚类选择一共有<math>(B'-1)/2</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>个）从中选取最优；
于是，依次比较了<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)处理列名型变量时，在层次聚类时考虑任意两个分支的聚类；
b)处理列名型变量时，在层次聚类时考虑任意两个分支的聚类；
从<math>L</math>个水平作为从<math>L</math>个不同分支开始，每次聚类减少一个分支；
从<math>L</math>个水平作为从<math>L</math>个不同分支开始，每次聚类减少一个分支；
在已有<math>B'</math>个分支时，需要考虑的聚类选择一共有<math>B'(B'-1)/2</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>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>\{ 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> 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>\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> 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> L(\mathcal{X}, \mathcal{Y}) </math> 描述了样本的不纯度带来的损失。对于一个子节点<math>b</math>，给定样本数，如果其中样本的标签都相同, 那么样本纯度很高, 对应的损失函数值低；如果样本标签随机分布, 那么样本纯度很低，对应的损失函数值高。给定<math> \mathcal{Y}</math>在分类集上的概率密度，如果标签都相同，那么不管样本数的多少，纯度都很高，损失为0；如果标签随机分布，纯度很低，那么样本总数越多，带来的损失就越大。
==损失函数形式设定==
==损失函数形式设定==
在实际训练中, 需要根据不同的需求选择适当的损失函数是必须的，损失函数的形式即是我们选择最优分支函数的优化目标。
在实际训练中, 需要根据不同的需求选择适当的损失函数是必须的，损失函数的形式即是我们选择最优分支函数的优化目标。
===分类树损失函数===
===分类树损失函数===
[[File:decisiontree_impurity.png]]
[[File:decisiontree_impurity.png]]
====基尼不纯度(Gini impurity)准则====
====基尼不纯度准则====
<math> l_{G}(p) \propto n \sum_{i=1}^{m} p_i (1-p_i) </math>
<math> l_{G}(p) \propto n \sum_{i=1}^{m} p_i (1-p_i) </math>
按其定义式所表达的，它的含义是“任意取两个观测其属于不同类的概率”。生态学中，与Simpson's Diversity Index具有相同定义。
按其定义式所表达的，它的含义是“任意取两个观测其属于不同类的概率”。生态学中，与Simpson's Diversity Index具有相同定义。
[[File:decisiontree_gini_impurity.png]]
[[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>分别为当前节点与其分支节点的观测数；
<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>
<math> l_{E}(p) \propto - n \sum^{m}_{i=1} p_i \log^{}_2 p_i</math>
按其定义式所表达的，它的含义是“在该节点内使用变长码字对类别进行编码，所能达到的最优平均码字长度”
按其定义式所表达的，它的含义是“在该节点内使用变长码字对类别进行编码，所能达到的最优平均码字长度”
[[File:decisiontree_entropy.png]]
[[File:decisiontree_entropy.png]]
在分支时的调减熵减为：
在分支时的调减熵减为：
熵减越大，说明节点经过一步分支后，各节点都能以较短的变长码字进行编码；
熵减越大，说明节点经过一步分支后，各节点都能以较短的变长码字进行编码；
====对数价值(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>就越大。
在分支时，分支规则与对目标规则关联性越强，皮尔逊卡方检验值（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>
其中，皮尔逊卡方统计量为在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)准则====
====经过Kass调整（Bonferroni界调整）的对数价值准则====
<math>-log_{10}(mP) = \mbox{Logworth} -log_{10}{m}</math>
<math>-log_{10}(mP) = \mbox{Logworth} -log_{10}{m}</math>
直觉上我们对对数价值法进行反思考虑如下的问题：如果我们尝试足够多的分支大小与可能性，是否我们在滥用Logworth法？我们把备择分支方案数目增大100倍，自然会选到Logworth更大的分支函数，而一味的细分分支使用的变量<math>X</math>丝毫不能说明<math>X</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>分支时，全部备择分支函数集合”的大小：
经过调整，我们将Logworth进行调整，减掉的部分为<math>-log_{10}(m)</math>，其中<math>m</math>即为前面推导的“<math>L</math>水平，<math>B</math>分支时，全部备择分支函数集合”的大小：
<math>
<math>
<math>\Delta Gini=0.197, \Delta H=0.504, \mbox{Logworth}=140, m=96, \mbox{Adjusted Logworth}=138</math>
<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>的方差来表示：
很自然的，对于回归树而言，某子节点<math>b</math>上的所谓“不纯度”可以用其因变量<math>Y</math>的方差来表示：
<math>{Var}_b = \frac{1}{n_b}\sum_{j=1}^{n_b}(y_{jb}-\bar{y}_b)^2</math>
<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>
<math>{LAD}_b = \frac{1}{n_b}\sum_{j=1}^{n_b}|y_{jb}-\bar{y}_b|</math>
====分支规则的F检验(Branching's F-Test)准则====
====分支规则的F检验准则====
根据传统的单路方差分析（One-Way Analysis of Variance），可以得到如下定义：
根据传统的单路方差分析（One-Way Analysis of Variance），可以得到如下定义：
这些在强烈异方差性下表现并不稳定。建议先对因变量<math>Y</math>做合适的变换（如乘幂，取对数等）防止稳定性降低。
这些在强烈异方差性下表现并不稳定。建议先对因变量<math>Y</math>做合适的变换（如乘幂，取对数等）防止稳定性降低。
==分支时的缺失值处理==
==分支时的缺失值处理==
在实际问题处理中，在合理的数据清洗后，如果发现分支变量<math>X</math>含有缺失值的观测点较多，可以把选择缺失值作为一个单独的水平来搜索最优分支函数；缺失值较少的情况下可以考虑先只考虑无缺失值的最优分支函数，再将缺失值并入最大的一个分支或者后验概率最接近的一个分支。
在实际问题处理中，在合理的数据清洗后，如果发现分支变量<math>X</math>含有缺失值的观测点较多，可以把选择缺失值作为一个单独的水平来搜索最优分支函数；缺失值较少的情况下可以考虑先只考虑无缺失值的最优分支函数，再将缺失值并入最大的一个分支或者后验概率最接近的一个分支。
如果使用“缺失值用于分支搜索”的方案，缺失值的出现无法保证原有的序数型/区间型变量存在一个水平排序用于模型选择，所以：
如果使用“缺失值用于分支搜索”的方案，缺失值的出现无法保证原有的序数型/区间型变量存在一个水平排序用于模型选择，所以：
*处理序数型/区间型变量：无缺失值情况下如果发生了<math>b</math>个分支，只需要考虑缺失值作为独立分支或者附着于<math>b</math>个分支中的某一个的一共<math>b+1</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> P(c|x) </math>. 可以用该叶节点各类别样本的频率来近似后验概率 <math> P(c|x) </math>. 后验概率最大的类别就是决策树对于新进单个观测点的预测结果，也就是 <math> c^* = \underset{c}{\text{argmax}} P(c|x) </math>。
*对于回归树，决策树的叶节点上的输出是叶子结点上观测点目标变量<math>Y</math>的中位数
*对于回归树，决策树的叶节点上的输出是叶子结点上观测点目标变量<math>Y</math>的中位数
=决策树停止生长准则=
=决策树停止生长准则=
*最少样本数量: 一般来说, 叶节点的样本量越多, 推广力越强. 反之, 则容易[[过拟合]]. 限制叶节点的最低样本量有助于提升决策树的推广能力. 如果当前节点样本量已经低于预先设定的阈值, 那么停止分支.
*最少样本数量: 一般来说, 叶节点的样本量越多, 推广力越强. 反之, 则容易[[过拟合]]. 限制叶节点的最低样本量有助于提升决策树的推广能力. 如果当前节点样本量已经低于预先设定的阈值, 那么停止分支.
*纯度准则：分支过程若导致节点上不断地降低Gini不纯度/熵/节点内方差等，说明纯度一直在改进。达到特定的纯度即可停止分支。
*纯度准则：分支过程若导致节点上不断地降低Gini不纯度/熵/节点内方差等，说明纯度一直在改进。达到特定的纯度即可停止分支。
这样得到的模型称为最大树(Largest Tree)或者全树。
这样得到的模型称为最大树(Largest Tree)或者全树。
==后向剪枝条件==
==后向剪枝条件==
[[File:decisiontree_postpruning.png]]
[[File:decisiontree_postpruning.png]]
在训练集上正确率随着叶子节点的增加而增加，但模型在验证数据集上，叶子节点数超过某个阈值后泛化能力反而会减弱。有时我们要在正向分支过程上创造远多于我们所需要的节点（如使用层数停止准则），然后根据一定规则，使用验证数据集进行后向剪枝。
使用后向剪枝的根本原因是，分支准则的局部最优性很可能不会使某一层所有分支节点的提升都均匀，甚至差距很大。那些提升不够显著的节点要从前向截止得到的模型中删除，留下一个全树的子树作为最终模型。
使用后向剪枝的根本原因是，分支准则的局部最优性很可能不会使某一层所有分支节点的提升都均匀，甚至差距很大。那些提升不够显著的节点要从前向截止得到的模型中删除，留下一个全树的子树作为最终模型。
有时为了优化泛化性能，我们不仅考虑子树，也考虑那些通过比某子树多一次分枝能得到的非子树，在验证集上比较效果。
有时为了优化泛化性能，我们不仅考虑子树，也考虑那些通过比某子树多一次分枝能得到的非子树，在验证集上比较效果。
*最小化误分类/最大化准确度（分类树）：
*最小化误分类/最大化准确度（分类树）：
<math>\mbox{Accuracy}=\frac{n_{TP}+n_{TN}}{n}</math>
<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>
<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个结点的纯度提升最大的子树。
在前向剪枝中，可能设定了一个较为宽的纯度标准以使得树得以充分发展，而后在后向剪枝中保留其包含N个结点的纯度提升最大的子树。
*ASE 平均平方误差（分类树，回归树）：
*ASE 平均平方误差（分类树，回归树）：
<math>ASE = 1 - \sum_{i=1}^N p_{i-train}p_{i-valid}</math>
<math>ASE = 1 - \sum_{i=1}^N p_{i-train}p_{i-valid}</math>
*稳健性模型选择
*稳健性模型选择
其中T为树的总结点个数。这个定义有点像模型选择中的信息选择的定义（SBC, AIC等）：选择越多变量或者树的节点越多，解释性越强，训练集上的风险越小，但泛化性能也会变差。合理选择参数<math>\alpha</math>，使得损失与树的节点个数的某个线性叠加最小，这样模型会更稳健。
其中T为树的总结点个数。这个定义有点像模型选择中的信息选择的定义（SBC, AIC等）：选择越多变量或者树的节点越多，解释性越强，训练集上的风险越小，但泛化性能也会变差。合理选择参数<math>\alpha</math>，使得损失与树的节点个数的某个线性叠加最小，这样模型会更稳健。
*提升度(Lift)方法（分类树）：
*提升度(Lift)方法（分类树）：
依次加入这些叶子结点，我们得到从0%到100%观测的序列，这中间预测正确的A事件的概率（预测性能）从一个很高的值<math>P^*_A</math>下降到<math>P_A</math>，这样考察前面尽量少的一部分比例的观测点可以提取出尽量多的A事件。这条轨道上的每一个值比上<math>P_A</math>得到了一条新的轨道，称为Lift曲线，在100%观测处轨道下降到1。一条值恒为1的水平线称为基准线（Baseline）。
依次加入这些叶子结点，我们得到从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==
==C5.0==
该算法从ID3,C4.5改进而来。
该算法从ID3,C4.5改进而来。
*分支准则：ID3使用熵减收益作为准则，从C4.5开始使用熵减值与分支导致的熵增的比例作为准则（单节点纯度为0，分为多节点即带来熵增）
*分支准则：ID3使用熵减收益作为准则，从C4.5开始使用熵减值与分支导致的熵增的比例作为准则（单节点纯度为0，分为多节点即带来熵增）
*分支数：2（ID3命名由此得来：Iterative Dichotomizer v3，决定了这是一个迭代二分支算法）
*分支数：2（ID3命名由此得来：Iterative Dichotomizer v3，决定了这是一个迭代二分支算法）
*分支最大深度：15
*分支最大深度：15
*C5.0嵌入了大规模学习常用的推进法
*C5.0嵌入了大规模学习常用的推进法
==CART(Classification and Regression Tree)==
==CART(Classification and Regression Tree)==
*缺失值推断：2次
*缺失值推断：2次
*后向剪枝：ASE
*后向剪枝：ASE
==CHAID(CHi-squared Automatic Interaction Detection)==
==CHAID(CHi-squared Automatic Interaction Detection)==
*模型选择：因为存在前剪枝，使用最大树
*模型选择：因为存在前剪枝，使用最大树
=辅助功能=
==编者推荐==
===集智课程===
====[]====
----
本中文词条由[[用户:薄荷|薄荷]]编辑，如有问题，欢迎在讨论页面留言。
[[Category:旧词条迁移]]
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''