二元决策树是基于顺序决策过程的结构。从根开始，将评估某个特征，并选择其中一个进行分支。重复此过程，直到达到最终叶子，这通常代表您正在寻找的分类目标。

决策树典型的为Iterative Dichotomizer 3 （ID3），它需要分类特征。这种情况限制了它的使用并导致C4.5的发展，C4.5也可以管理连续（但是binned和离散）的值。此外，C4.5也是众所周知的，因为它能够将树转换为一系列条件表达式（if <condition> then <…> else <…>）。

考虑到其他算法，决策树的动态似乎更简单。但是，如果数据集在保持内部平衡的同时是可拆分的，则整个过程直观且预测速度相当快。此外，决策树可以有效地使用非归一化数据集，因为它们的内部结构不受每个特征假定的值的影响。

下图绘制了非标准化的二维数据集，以及使用逻辑回归和决策树获得的交叉验证分数：

上图：逻辑回归和决策树（右）具有不同方差（左）和交叉验证分数的数据集示例

决策树总是达到接近1.0的分数，而逻辑回归的平均值略高于0.6。但是，如果没有适当的限制，决策树可能会增长，直到每个节点中存在单个样本（或非常低的数量）。这种情况会导致模型过度拟合，树无法正确推广。

使用一致的测试集或交叉验证以及最大允许深度可以帮助避免此问题。另一个需要考虑的重要因素是类平衡。决策树对不平衡类敏感，并且当类占优势时可能会导致准确性较差。为了缓解这个问题，可以使用其中一个重采样方法或使用class_weight参数，该参数由scikit-learn实现提供。通过这种方式，一个主导类可以按比例受到惩罚，避免偏差。

二元决策

考虑输入数据集X：

每个向量都是由m个特征组成的，因此每个特征都是基于元组(特征，阈值)创建节点的候选对象:

单节点分裂

根据特征和阈值，树的结构将改变。直观地说，您应该选择最能分离数据的特征。换句话说，完美分离的特征将仅存在于节点中，并且两个后续分支将不再基于它。这些条件保证了树向最终叶片的收敛，最终叶片的不确定性最小化。然而，在实际问题中，这通常是不可能的，因此有必要找到最小化由此产生的决策步骤数量的特征。

例如，考虑一类学生，其中所有男学生都有黑发，所有女学生都有金发，而两个子集都有不同大小的样本。如果您的任务是确定类的组成，则可以从以下细分开始：

分裂节点(Length)和包含另一个分裂节点的分支(Dark color)

但是，Dark color？Block将包含男性和女性（这是您要分类的目标）。该概念使用术语纯度（或更常见的是其相反的概念，杂质）来表达。理想情况是基于杂质为空的节点，因此所有后续决策将仅针对其余特征进行。您只需从颜色块开始：

最佳分裂节点的示例 - 最小化子节点的杂质

根据颜色特征，这两个结果集现在是纯的，这就足够你的任务了。如果您需要进一步的细节，如头发长度，则必须添加其他节点；它们的杂质不会为空，因为您知道，例如，有长头发的男生和女生。

假设您将选择元组定义如下：

这里，第一个元素是您要用于在特定节点处分割数据集的特征的索引（它将仅在开始时是整个数据集;在每个步骤之后，样本数量减少），而第二个元素是确定左右分支的阈值。选择最佳阈值是一个基本要素，因为它决定了树的结构，从而决定了它的性能。目标是减少最少数量的分裂中的残留杂质，以在样本数据和分类结果之间具有非常短的决策路径。

您还可以通过考虑两个分支来定义总杂质测量：

这里，D是所选节点的整个数据集，Dleft和Dright是结果子集（通过应用选择元组），并且I代表杂质测量。

杂质措施

要定义最常用的杂质测量，您需要考虑目标类的总数：

在某个节点j中，您可以定义概率p（y = i | Node = j）， 其中i是与每个类关联的索引[0，P-1]。换句话说，根据频率论方法，该值是属于类i并分配给节点j的样本数与属于所选节点的样本总数之间的比率：

Gini杂质指数

Gini杂质指数定义如下：

这里，总和总是扩展到所有类。这是一个非常常见的度量，它被scikit-learn用作默认值。给定样本，如果使用分支的概率分布随机选择标签，则Gini杂质测量错误分类的概率。当节点的所有样本被分类为单个类别时，索引达到其最小值（0.0）。

交叉熵杂质指数

交叉熵测量定义如下：

该度量基于信息理论，并且当属于单个类的样本存在于分裂中时假设为空值，而当类之间存在均匀分布时它是最大值（这是决策树中最糟糕的情况之一，因为这意味着在最终分类之前仍有许多决策步骤）。该指数与Gini杂质非常相似，交叉熵允许您选择最小化分类不确定性的分割，而Gini杂质最小化错误分类的可能性。

互信息的概念定义为I（X; Y）= H（X） - H（X | Y），作为两个变量共享的信息量，或者您可以通过知识获得的关于X的信息量的ÿ。考虑数据生成过程p（x）和条件概率p（x | y）也很有帮助。对于条件变量y，很容易证明互信息是它们之间Kullback-Leibler分歧的期望值：

因此，这是当I（X; Y）→0，p（x）≈p（x | y）时，Y的knowledge不提供关于X的任何有用信息。相反，较高的I（X; Y）值意味着边际分布p（x）和条件p（x | y）之间的平均强散度。条件概率的定义可以提供更好的洞察力：

在这里，这两个变量在统计上不是独立的，关于Y的knowledge必须提供关于x的比例信息。您可以使用这个概念来定义split提供的信息增益(它在形式上相当于互信息):

在这种情况下，您感兴趣的是父节点和子节点的分布。因此，在growing 树时，首先选择提供最高信息增益的分割。这保证了后续节点的杂质的最小化，因为通常在开始时选择最相关的特征，并且保留下一个特征用于微调。树的增长继续进行，直到验证以下条件之一：

所有节点都是纯粹的信息增益为空已达到最大深度Misclassification杂质指数

Misclassification 杂质指数是最简单的指数，定义如下：

解释很简单但不幸的是，就质量表现而言，这个指数并不是最佳选择，因为它对不同的概率分布并不特别敏感。在所有这些情况下，基尼或交叉熵指数是最自然的选择。

Feature importance

在使用多维数据集生成决策树时，评估每个特征在预测输出值中的重要性会很有用。决策树根据每个特征确定的杂质减少提供不同的方法。特别是，考虑到特征x（i），其重要性可以确定如下：

总和扩展到使用x（i）的所有节点，并且Nk是到达节点的样本数k。因此，重要性是计算的所有杂质减少的加权和，仅考虑使用特征来分割它们的节点。如果采用Gini 杂质指数，该措施也称为Gini importance。