决策树学习

统计学，数据挖掘和机器学习中的决策树训练，使用决策树作为预测模型来预测样本的类标。这种决策树也称作分类树或回归树。在这些树的结构里， 叶子节点给出类标而内部节点代表某个属性。

在决策分析中，一棵决策树可以明确地表达决策的过程。在数据挖掘中，一棵决策树表达的是数据而不是决策。本页的决策树是数据挖掘中的决策树。

在数据挖掘中决策树训练是一个常用的方法。目标是创建一个模型来预测样本的目标值。例如右图。每个 内部节点 对应于一个输入属性，子节点代表父节点的属性的可能取值。每个叶子节点代表输入属性得到的可能输出值。

一棵树的训练过程为：根据一个指标，分裂训练集为几个子集。这个过程不断的在产生的子集里重复递归进行，即递归分割。当一个训练子集的类标都相同时 递归停止。这种 (TDITD) 是 贪心算法的一种, 也是目前为止最为常用的一种训练方法，但不是唯一的方法。

数据以如下方式表示:

其中Y是目标值，向量x由这些属性构成, x₁, x₂, x₃ 等等，用来得到目标值。

在数据挖掘中，决策树主要有两种类型:

术语分类和回归树 (CART) 包含了上述两种决策树, 最先由Breiman 等提出. 分类树和回归树有些共同点和不同点—例如处理在何处分裂的问题。

有些的方法产生多棵树：

还有其他很多决策树算法，常见的有:

构建决策树时通常采用自上而下的方法，在每一步选择一个最好的属性来分裂。 "最好" 的定义是使得子节点中的训练集尽量的纯。不同的算法使用不同的指标来定义"最好"。本部分介绍一些最常见的指标。

在CART算法中, 基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。基尼不纯度为这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本都是一个类时，基尼不纯度为零。

假设y的可能取值为${\displaystyle J}$ (sunny, overcast, rainy), (hot, mild, cool), (high, normal), and (true, false), 目标值（yes, no）, 总共14个数据点。为建造决策树，需要比较4棵决策树的信息增益，每棵决策树用一种属性做划分。信息增益最高的划分作为第一次划分，并在每个子节点继续此过程，直至其信息增益为0。

使用属性做划分时，产生2个子节点：值为真与为假。当前数据集，6个数据点的值为真，其中3个点的值为真，3个点的值为假；其余8个数据点的为假，其中6个点的值为真，2个点的值为假。 =true的子节点的信息熵计算为：

=false的子节点的信息熵计算为：

这个划分（使用属性）的信息熵是两个子节点信息熵的加权和：

为计算使用属性的信息增益，必须先计算出最初（未划分）的数据集的信息熵，数据集的有9个yes与5个no：

使用属性的信息增益是：

与其他的数据挖掘算法相比，决策树有许多优点:

在决策树中, 从根节点到叶节点的路径采用汇合或。而在决策图中, 可以采用 最小消息长度 (MML)来汇合两条或多条路径。

演化算法可以用来避免局部最优的问题