决策树

1. 决策树是一种基本的分类与回归方法。这里主要讨论决策树用于分类。

2. 决策树模型是描述对样本进行分类的树形结构。树由结点和有向边组成：

   • 内部结点表示一个特征或者属性。
   • 叶子结点表示一个分类。
   • 有向边代表了一个划分规则。

3. 决策树从根结点到子结点的的有向边代表了一条路径。决策树的路径是互斥并且是完备的。

4. 用决策树分类时，对样本的某个特征进行测试，根据测试结果将样本分配到树的子结点上。此时每个子结点对应该特征的一个取值。

   递归地对样本测试，直到该样本被划分叶结点。最后将样本分配为叶结点所属的类。

5. 决策树的优点：可读性强，分类速度快。

6. 决策树学习通常包括3个步骤：

   • 特征选择。
   • 决策树生成。
   • 决策树剪枝。

一、 原理

1.1 基本概念

1. 决策树模型可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

2. 决策树将特征空间划分为互不相交的单元，在每个单元定义一个类的概率分布，这就构成了一个条件概率分布。

   • 决策树的每一条路径对应于划分中的一个基本单元。

   • 设某个单元 $\mathbb S$ 内部有 $N_S$ 个样本点，则它定义了一个条件概率分布 $p(y \mid \mathbf{\vec x}), \mathbf{\vec x} \in \mathbb S$ 。

     • 单元上的条件概率偏向哪个类，则该单元划归到该类的概率较大。即单元的类别为：

       $$\arg\max_y p(y \mid \mathbf{\vec x}), \mathbf{\vec x} \in \mathbb S$$

     • 决策树所代表的条件概率分布由各个单元给定条件下类的条件概率分布组成。

3. 决策树的学习目标是：根据给定的训练数据集构造一个决策树模型，使得它能够对样本进行正确的分类。

4. 决策树最优化的策略是：损失函数最小化。决策树的损失函数通常是正则化的极大似然函数。

5. 选择最优决策树的问题是个 NP 完全问题。一般采用启发式方法近似求解这个最优化问题，这时的解为次最优的。

6. 决策树学习的算法通常递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类。

   这一过程对应着特征空间的划分，也对应着决策树的构建。

1.2 生成

1. 决策树生成算法：

   • 构建根结点：将所有训练数据放在根结点。

   • 选择一个最优特征，根据这个特征将训练数据分割成子集，使得各个子集有一个在当前条件下最好的分类。

     • 若这些子集已能够被基本正确分类，则将该子集构成叶结点。
     • 若某个子集不能够被基本正确分类，则对该子集选择新的最优的特征，继续对该子集进行分割，构建相应的结点。

   • 如此递归下去，直至所有训练数据子集都被基本正确分类，或者没有合适的特征为止。

2. 上述生成的决策树可能对训练数据有很好的分类能力，但是对于未知的测试数据却未必有很好要的分类能力，即可能发生过拟合的现象。

   • 解决的方法是：对生成的决策树进行剪枝，从而使得决策树具有更好的泛化能力。
   • 剪枝是去掉过于细分的叶结点，使得该叶结点中的子集回退到父结点或更高层次的结点并让其成为叶结点。

3. 决策树的生成对应着模型的局部最优，决策树的剪枝则考虑全局最优。

4. 如果学习任意大小的决策树，则可以将决策树算法视作非参数算法。但是实践中经常有大小限制（如限制树的高度、限制树的叶结点数量），从而使得决策树成为有参数模型。

二、 特征选择

1. 特征选择的关键是：选取对训练数据有较强分类能力的特征。若一个特征的分类结果与随机分类的结果没有什么差别，则称这个特征是没有分类能力的。

2. 通常特征选择的指标是：信息增益或者信息增益比。这两个指标刻画了特征的分类能力。

3. 对于分布 $p(y)$，熵为 $H(y) = \sum_y -p(y)\log p(y)$ 。

   定义数据集 $\mathbb D$ 的经验熵为：$H(\mathbb D) = - \sum_{k=1}^K \frac {N_k}{N}\log \frac{N_k}{N}$ 。

   其中：

   • 样本的类别分别为 $c_1,c_2,\cdots,c_K$ 。

   • 类别 $c_k$ 的样本的数量为 $N_k$ ，所有样本的总数为 $N$ 。

     因此有： $\sum_{k=1}^K N_k = N$ 。

   • $\frac {N_k}{N}$ 是概率 $p(y=c_k)$ 的估计。

   • $H(\mathbb D)$ 就是熵 $H(y)$ 的估计。它刻画了数据集 $\mathbb D$ 中样本的类别分布情况。

4. 对于特征 $A$ ，定义数据集 $\mathbb D$ 在 $A$ 上的经验熵为：$H_A(\mathbb D) = - \sum_{i=1}^{n_A} \frac{N_{a_i}}{N}\log \frac{N_{a_i}}{N}$ 。

   其中：

   • 特征 $A$ 的取值范围为 $\{a_1,a_2,\cdots,a_{n_A} \}$ 。

   • 属性$A=a_i$ 的样本的数量为 $N_{a_i}$ 。

     因此有：$\sum_{i=1}^{n_A} N_{a_i,k} = N_k$

   • $\frac{N_{a_i}}{N}$ 是概率 $p(A=a_i)$ 的估计。

   • $H_A(\mathbb D)$ 刻画了数据集 $\mathbb D$ 中的样本在属性 $A$ 上的取值分布情况。

5. 对于特征 $A$ ，其条件熵为：$H(y\mid A) = \sum_A p(A) H(y\mid A)$ 。

   定义数据集 $\mathbb D$ 关于特征 $A$ 的经验条件熵为：

   $$H(\mathbb D\mid A) = \sum_{i=1}^{n_A}p(A=a_i) H(y\mid A=a_i) = \sum_{i=1}^{n_A} \frac{N_{a_i}}{N}\left[-\sum_{k=1}^K\frac{N_{a_i,k}}{N_{a_i}}\log\frac{N_{a_i,k}}{N_{a_i}}\right]$$

   其中：

   • 属性 $A=a_i$ 且类别为 $c_k$ 的样本的数量为 $N_{a_i,k}$，所有样本的总数为 $N$ 。

     因此有： $\sum_{k=1}^K N_{a_i,k} = N_{a_i} ,\; \sum_{i=1}^{n_A}N_{a_i}=\sum_{k=1}^KN_k = N$。

   • $-\sum_{k=1}^K\frac{N_{a_i,k}}{N_{a_i}}\log\frac{N_{a_i,k}}{N_{a_i}}$ 是条件熵 $H(y\mid A=a_i)$ 的估计。它刻画了数据集 $\mathbb D$ 中，属性 $A=a_i$ 中的那些样本中的类别的分布情况。

   • $H(\mathbb D\mid A)$ 是条件熵 $H(y\mid A)$ 的估计。

2.1 信息增益

1. 特征 $A$ 对训练数据集 $\mathbb D$ 的信息增益 $g(\mathbb D,A)$ 定义为：集合 $\mathbb D$ 的经验熵 $H(\mathbb D)$ 与关于特征 $A$ 经验条件熵 $H(\mathbb D\mid A)$ 之差。即： $g(\mathbb D,A)=H(\mathbb D)-H(\mathbb D\mid A)$ 。

   由于熵 $H(y)-H(y\mid A)$ 也称作互信息，因此信息增益也等于训练数据集中类与特征的互信息。

2. 决策树学习可以应用信息增益来选择特征。给定训练集 $\mathbb D$ 和特征 $A$ ：

   • 经验熵 $H(\mathbb D)$ 刻画了对数据集 $\mathbb D$ 进行分类的不确定性。
   • 经验条件熵 $H(\mathbb D\mid A)$ 刻画了在特征 $A$ 给定条件下，对数据集 $\mathbb D$ 分类的不确定性。
   • 信息增益 $H(\mathbb D)-H(\mathbb D\mid A)$ 刻画了由于特征 $A$ 的确定，从而使得对数据集 $\mathbb D$ 的分类的不确定性减少的程度。

3. 不同的特征往往具有不同的信息增益。

   • 信息增益大的特征具有更强的分类能力 。
   • 如果一个特征的信息增益为0，则表示该特征没有什么分类能力。

2.2 信息增益比

1. 以信息增益作为划分训练集的特征选取方案，存在偏向于选取值较多的特征的问题。

   公式 $H(\mathbb D\mid A) = \sum_{i=1}^{n_A} \frac{N_{a_i}}{N}\left[-\sum_{k=1}^K\frac{N_{a_i,k}}{N_{a_i}}\log\frac{N_{a_i,k}}{N_{a_i}}\right]$ 中：

   • 当极限情况下 ，特征 $A$ 在每个样本上的取值都不同，即 $n_A = N$ 。

     • 此时特征 $A$ 将每一个样本都划分到不同的子结点。即：$N_{a_i}=1,\quad i=1,\cdots,n_A$ 。

     • 由于 $\sum_{k=1}^K N_{a_i,k} = N_{a_i}=1$ ，因此有： $N_{a_i,k} \le 1,\quad i=1,\cdots,n_A;\quad k=1,\cdots,K$ 。

       即：$N_{a_i,k}$ 取值为 0 或者 1 。因此有：$\frac{N_{a_i,k}}{N_{a_i}}\log\frac{N_{a_i,k}}{N_{a_i}}=0$ 。

     • 最终使得$H(\mathbb D\mid A) = 0$ 。

   • 条件熵的最小值为 0，这意味着该情况下的信息增益达到了最大值。

     然而很显然这个特征 $A$ 显然不是最佳选择，因为它并不具有任何分类能力。

2. 可以通过定义信息增益比来解决该问题。

   特征 $A$ 对训练集 $\mathbb D$ 的信息增益比 $g_R(\mathbb D,A)$ 定义为：信息增益 $g(\mathbb D,A)$ 与关于特征 $A$ 的熵 $H_A(\mathbb D)$ 之比：

   $$g_R(\mathbb D,A)=\frac{g(\mathbb D,A)}{H_A(\mathbb D)}$$

   $H_A(\mathbb D)$ 表征了特征 $A$ 对训练集 $\mathbb D$ 的拆分能力。

   因为 $H_A(\mathbb D)$ 只考虑样本在特征 $A$ 上的取值，而不考虑样本的标记 $y$ ，所以这种拆分并不是对样本的分类。

3. 信息增益比本质上是对信息增益乘以一个加权系数：

   • 当特征 $A$ 的取值集合较大时，加权系数较小，表示抑制该特征。
   • 当特征 $A$ 的取值集合较小时，加权系数较大，表示鼓励该特征。

三、生成算法

1. 决策树有两种常用的生成算法：

   • ID3 生成算法。
   • C4.5 生成算法。

2. ID3 生成算法和 C4.5 生成算法只有树的生成算法，生成的树容易产生过拟合：对训练集拟合得很好，但是预测测试集效果较差。

3.1 ID3 生成算法

1. ID3 生成算法核心是在决策树的每个结点上应用信息增益准则选择特征，递归地构建决策树。

   • 从根结点开始，计算结点所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征划分出子结点。

   • 再对子结点递归地调用以上方法，构建决策树。

   • 直到所有特征的信息增益均很小或者没有特征可以选择为止，最后得到一个决策树 。

     如果不设置特征信息增益的下限，则可能会使得每个叶子都只有一个样本点，从而划分得太细。

2. ID3 生成算法：

   • 输入：

     • 训练数据集 $\mathbb D$
     • 特征集合 $\mathbb A =\{A_1,A_2,\cdots,A_n\}$
     • 特征信息增益阈值 $\varepsilon \gt 0$

   • 输出：决策树 $T$

   • 算法步骤：

     • 若 $\mathbb D$ 中所有样本均属于同一类 $c_k$，则 $T$ 为单结点树，并将 $c_k$ 作为该结点的类标记，算法终止。

     • 若 $\mathbb A=\phi$，则 $T$ 为单结点树，将 $\mathbb D$ 中样本数最大的类 $c_k$ 作为该结点的类标记，算法终止。

     • 否则计算 $g(\mathbb D,A_j),\; j=1,2,\cdots,n$，选择信息增益最大的特征 $A_g$ ：

       • 若 $g(\mathbb D,A_g) \lt \varepsilon$ ，则置 $T$ 为单结点树，将 $\mathbb D$ 中样本数最大的类 $c_k$ 作为该结点的类标记，算法终止 。

       • 若 $g(\mathbb D,A_g) \ge \varepsilon$ ，则对 $A_g$ 特征的每个可能取值 $a_i,i=1,2,\cdots,n_g$ ，根据 $A_g=a_i$ 将 $\mathbb D$ 划分为若干个非空子集 $\mathbb D_i$ 。

         将 $\mathbb D_i$ 中样本数最大的类作为该子集的标记，构建子结点。

     • 对第 $i$ 个子结点， 以 $\mathbb D_i$ 为训练集， 以 $\mathbb A-\{A_g\}$ 为特征集，递归地调用前面的步骤来构建子树。

3.2 C4.5 生成算法

1. C4.5 生成算法与 ID3 算法相似，但是 C4.5 算法在生成过程中用信息增益比来选择特征。

四、剪枝算法

1. 决策树生成算法生成的树往往对于训练数据拟合很准确，但是对于未知的测试数据分类却没有那么准确。即出现过拟合现象。

   过拟合产生得原因是决策树太复杂。解决的办法是：对决策树剪枝，即对生成的决策树进行简化。

2. 决策树的剪枝是从已生成的树上裁掉一些子树或者叶结点，并将根结点或者其父结点作为新的叶结点。

   剪枝的依据是：极小化决策树的整体损失函数或者代价函数。

3. 决策树生成算法是学习局部的模型，决策树剪枝是学习整体的模型。即：生成算法仅考虑局部最优，而剪枝算法考虑全局最优。

4.1 原理

1. 设树 $T$ 的叶结点个数为 $|T_f|$ 。设 $T_t,t=1,2,\cdots,|T_f|$ 为树的叶结点，该叶结点有 $N_t$ 个样本点，其中属于 $c_k$ 类的样本点有 $N_{t,k}$ 个， $k=1,2,\cdots,K$ 。

   这意味着： $\sum_{k=1}^{K}N_{t,k}=N_t$ 。

   令 $H(t)$ 为叶结点 $T_t$ 上的经验熵，令 $\alpha \ge 0$为参数，则决策树 $T$ 的损失函数定义为：

   $$C_\alpha(T)=\sum_{t=1}^{|T_{f}|}N_tH(t)+\alpha|T_{f}|$$

   其中：$H(t)=-\sum_{k=1}^{K}\frac{N_{t,k}}{N_t}\log\frac{N_{t,k}}{N_t}$ 。

   • 叶结点个数越多，表示决策树越复杂，则损失函数越大。
   • 叶结点经验熵越大，表示叶结点的样本类别分布很分散，则损失函数越大。
   • 叶结点经验熵还需要加权，权重为叶结点大小。即：越大的叶结点，其分类错误的影响越大。

2. 令 $C(T)=\sum_{t=1}^{|T_{f}|}N_tH(t)=-\sum_{t=1}^{|T_{f}|}\sum_{k=1}^{K}N_{t,k}\log\frac{N_{t,k}}{N_t}$ ，则： $C_\alpha(T)=C(T)+\alpha|T_{f}|$ 。

   其中 $\alpha|T_{f}|$ 为正则化项，$C(T)$ 表示预测误差。

3. $C(T)=0$ 意味着 $N_{t,k}=N_t$ ，即每个结点 $T_t$ 内的样本都是纯的，即单一的分类。

   决策树划分得越细致，则 $T$ 的叶子结点越多。当叶结点的数量等于样本集的数量时，树 $T$ 的每个叶子结点只有一个样本点。此时每个叶结点内的样本都是纯的，从而 $C(T)=0$ 。

   这样的决策树其实是没有什么实用价值的，所以必须使用正则化项来约束决策树的复杂程度。

4. 参数 $\alpha$ 控制预测误差与模型复杂度之间的关系。

   • 较大的 $\alpha$ 会选择较简单的模型 。
   • 较小的 $\alpha$ 会选择较复杂的模型。
   • $\alpha = 0$ 只考虑对训练集的拟合，不考虑模型复杂度。

5. 决策树剪枝的准则是：考虑当 $\alpha$ 确定时， $C_\alpha(T)$ 最小化。这等价于正则化的极大似然估计。

4.2 算法

1. 决策树的剪枝算法：

   • 输入：

     • 生成算法产生的决策树 $T$
     • 参数 $\alpha$

   • 输出： 修剪后的决策树 $T_\alpha$

   • 算法步骤：

     • 对树 $T$ 每个结点 $T_t,t=1,2,\cdots,|T_f|$ ，计算其经验熵 $H(t)$ 。

     • 递归地从树的叶结点向上回退：

       设一组叶结点回退到父结点之前与之后的整棵树分别为 $T$ 与 $T^{\prime}$，对应的损失函数值分别为 $C_\alpha(T)$ 与$C_\alpha(T^{\prime})$ 。若 $C_\alpha(T^{\prime}) \le C_\alpha(T)$， 则进行剪枝，将父结点变成新的叶结点。

     • 递归回退直到不能继续为止，得到损失函数最小的子树 $T_\alpha$ 。

五、CART 树

1. CART:classfification and regression tree ：学习在给定输入随机变量 $\mathbf{\vec x}$ 条件下，输出随机变量 $y$ 的条件概率分布的模型。

   • 它同样由特征选取、树的生成、剪枝组成。
   • 它既可用于分类，也可用于回归。

2. CART 假设决策树是二叉树：

   • 内部结点特征的取值为 是 与 否 。其中：左侧分支取 是，右侧分支取 否 。
   • 它递归地二分每个特征，将输入空间划分为有限个单元。

3. CART 树与ID3 决策树和 C4.5 决策树的重要区别：

   • CART 树是二叉树，而后两者是N 叉树。

     由于是二叉树，因此 CART 树的拆分不依赖于特征的取值数量。因此CART 树也就不像ID3 那样倾向于取值数量较多的特征。

   • CART 树的特征可以是离散的，也可以是连续的。

     而后两者的特征是离散的。如果是连续的特征，则需要执行分桶来进行离散化。

     CART 树处理连续特征时，也可以理解为二分桶的离散化。

4. CART算法分两步：

   • 决策树生成：用训练数据生成尽可能大的决策树。
   • 决策树剪枝：用验证数据基于损失函数最小化的标准对生成的决策树剪枝。

5.1 CART 生成算法

1. CART生成算法有两个生成准则：

   • CART 回归树：用平方误差最小化准则。
   • CART 分类树：用基尼指数最小化准则。

5.1.1 CART 回归树

5.1.1.1 划分单元和划分点

1. 一棵CART 回归树对应着输入空间的一个划分，以及在划分单元上的输出值。

   设输出 $y$ 为连续变量，训练数据集 $\mathbb D=\{(\mathbf {\vec x}_1,\tilde y_1),(\mathbf {\vec x}_2,\tilde y_2),\cdots,(\mathbf {\vec x}_N,\tilde y_N)\}$。

   设已经将输入空间划分为 $M$ 个单元 $R_1,R_2,\cdots,R_M$，且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$。则CART 回归树模型可以表示为：

   $$f(\mathbf{\vec x})=\sum_{m=1}^{M}c_m I(\mathbf {\vec x} \in R_m)$$

   其中 $I(\cdot)$ 为示性函数。

2. 如果已知输入空间的单元划分，基于平方误差最小的准则，则CART 回归树在训练数据集上的损失函数为：

   $$\sum_{m=1}^{M}\sum_{\mathbf {\vec x}_i \in R_m}(\tilde y_i-c_m)^{2}$$

   根据损失函数最小，则可以求解出每个单元上的最优输出值 $\hat c_m$ 为 ： $R_m$ 上所有输入样本 $\mathbf {\vec x}_i$ 对应的输出 $\tilde y_i$ 的平均值。

   即：$\hat c_m= \frac {1}{N_m} \sum_{\mathbf {\vec x}_i \in R_m}\tilde y_i$ ，其中 $N_m$ 表示单元 $R_m$ 中的样本数量。

3. 定义 $R_m$ 上样本的方差为 $\text{Var}_m$，则有：$\text{Var}_m=\frac{1}{N_m} \sum_{\mathbf {\vec x}_i \in R_m}(\tilde y_i-\hat c_m)^{2}$ 。则CART 回归树的训练集损失函数重写为：$N\times \sum_{m=1}^M \left(\frac{N_m}{N}\times \text{Var}_m\right)$ ，其中 $N$ 为训练样本总数。

   定义样本被划分到 $R_m$ 中的概率为 $P_m$，则 $P_m=\frac {N_m}{N}$ 。由于 $N$ 是个常数，因此损失函数重写为：

   $$\sum_{m=1}^M P_m\times \text{Var}_m$$

   其物理意义为：经过输入空间的单元划分之后，CART 回归树的方差，通过这个方差来刻画CART 回归树的纯度。

4. 问题是输入空间的单元划分是未知的。如何对输入空间进行划分？

   设输入为 $n$ 维： $\mathbf {\vec x} =(x_1,x_2,\cdots,x_n)^{T}$ 。

   • 选择第 $j$ 维 $x_j$ 和它的取值 $s$ 作为切分变量和切分点。定义两个区域：
   $$R_1(j,s)=\{\mathbf {\vec x} \mid x_j \le s\}\\ R_2(j,s)=\{\mathbf {\vec x}\mid x_j \gt s\}$$

   • 然后寻求最优切分变量 $j$ 和最优切分点 $s$ 。即求解：

     $$(j^*,s^*) = \min_{j,s}\left[ \min_{c_1} \sum_{\mathbf{\vec x_i} \in R_1(j,s)}(\tilde y_i-c_1)^{2} +\min_{c_2} \sum_{\mathbf{\vec x_i} \in R_2(j,s)}(\tilde y_i-c_2)^{2}\right]$$

     其意义为：

     • 首先假设已知切分变量 $j$ ，则遍历最优切分点 $s$，则到：

       $$\hat c_1= \frac {1}{N_1} \sum_{\mathbf {\vec x}_i \in R_1(j,s)}\tilde y_i ,\quad \hat c_2= \frac {1}{N_2} \sum_{\mathbf {\vec x}_i \in R_2(j,s)}\tilde y_i$$

       其中 $N_1$ 和 $N_2$ 分别代表区域 $R_1$ 和 $R_2$ 中的样本数量。

     • 然后遍历所有的特征维度，对每个维度找到最优切分点。从这些(切分维度,最优切分点) 中找到使得损失函数最小的那个。

5. 依次将输入空间划分为两个区域，然后重复对子区域划分，直到满足停止条件为止。这样的回归树称为最小二乘回归树。

5.1.1.2 生成算法

1. CART 回归树生成算法：

   • 输入：

     • 训练数据集 $\mathbb D$
     • 停止条件

   • 输出： CART回归树 $f(\mathbf{\vec x})$

   • 步骤：

     • 选择最优切分维度 $j$ 和切分点 $s$。

       即求解：

     $$(j^*,s^*) = \min_{j,s}\left[ \min_{c_1} \sum_{\mathbf {\vec x}_i \in R_1(j,s)}(\tilde y_i-c_1)^{2} +\min_{c_2} \sum_{\mathbf {\vec x}_i \in R_2(j,s)}(\tilde y_i-c_2)^{2}\right]$$

     • 用选定的 $(j,s)$ 划分区域并决定响应的输出值：

       $$R_1(j,s)=\{\mathbf {\vec x} \mid x_j \le s\},\quad R_2(j,s)=\{\mathbf {\vec x}\mid x_j \gt s\}\\ \hat c_1= \frac {1}{N_1} \sum_{\mathbf {\vec x}_i \in R_1(j,s)}\tilde y_i ,\quad \hat c_2= \frac {1}{N_2} \sum_{\mathbf {\vec x}_i \in R_2(j,s)}\tilde y_i$$

       其中 $N_1$ 和 $N_2$ 分别代表区域 $R_1$ 和 $R_2$ 中的样本数量。

     • 对子区域 $R_1,R_2$ 递归地切分，直到满足停止条件。

     • 最终将输入空间划分为 $M$ 个区域 $R_1,R_2,\cdots,R_M$，生成决策树：$f(\mathbf {\vec x})=\sum_{m=1}^{M}\hat c_m I(\mathbf {\vec x} \in R_m)$ 。

5.1.2 CART 分类树

5.1.2.1 基尼系数

1. CART 分类树采用基尼指数选择最优特征。

2. 假设有 $K$ 个分类，样本属于第 $k$ 类的概率为 $p_k=p(y=c_k)$ 。则概率分布的基尼指数为：

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

   基尼指数表示：样本集合中，随机选中一个样本，该样本被分错的概率。基尼指数越小，表示越不容易分错。

   样本被选错概率 = 样本被选中的概率 $p_k$ * 样本被分错的概率 $1-p_k$ 。

3. 对于给定的样本集合 $\mathbb D$，设属于类 $c_k$ 的样本子集为 $\mathbb D_k$，则样本集的基尼指数为：

   $$Gini(\mathbb D)=1-\sum_{k=1}^{K}(\frac{N_k}{N})^{2}$$

   其中 $N$ 为样本总数， $N_k$ 为子集 $\mathbb D_k$ 的样本数量。

4. 对于最简单的二项分布，设 $p(X=1)=p,P(X=0)=1-p$，则其基尼系数与熵的图形见下图。

   • 可以看到基尼系数与熵一样，也是度量不确定性的度量。

   • 对于样本集 $\mathbb D$， $Gini(\mathbb D)$ 越小，说明集合中的样本越纯净。

     

5. 若样本集 $\mathbb D$ 根据特征 $A$ 是否小于 $a$ 而被分为两个子集: $\mathbb D_1$ 和 $\mathbb D_2$，其中：

   $$\mathbb D_1=\{(\mathbf{\vec x},y) \in \mathbb D \mid x_A \le a\}\\ \mathbb D_2=\{(\mathbf {\vec x},y) \in \mathbb D \mid x_A \gt a\}=\mathbb D-\mathbb D_1$$

   则在特征 $A:a$ 的条件下，集合 $\mathbb D$ 的基尼指数为：

   $$Gini(\mathbb D,A:a)=\frac{N_1}{N}Gini(\mathbb D_1)+\frac{N_2}{N}Gini(\mathbb D_2)$$

   其中 $N$ 为样本总数， $N_1,N_2$ 分别子集 $\mathbb D_1,\mathbb D_2$ 的样本数量。它就是每个子集的基尼系数的加权和，权重是每个子集的大小（以子集占整体集合大小的百分比来表示）。

5.1.2.2 划分单元和划分点

1. 一棵CART 分类树对应着输入空间的一个划分，以及在划分单元上的输出值。

   设输出 $y$ 为分类的类别，是离散变量。训练数据集 $\mathbb D=\{(\mathbf {\vec x}_1,\tilde y_1),(\mathbf {\vec x}_2,\tilde y_2),\cdots,(\mathbf {\vec x}_N,\tilde y_N)\}$。

   设已经将输入空间划分为 $M$ 个单元 $R_1,R_2,\cdots,R_M$，且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$。则CART 分类树模型可以表示为：

   $$f(\mathbf{\vec x})=\sum_{m=1}^{M}c_m I(\mathbf {\vec x} \in R_m)$$

   其中 $I(\cdot)$ 为示性函数。

2. 如果已知输入空间的单元划分，基于分类误差最小的准则，则CART 分类树在训练数据集上的损失函数为：