note5.md

1. 对于决策树来说，每个节点选择的特征可以重复吗？如果是CART呢？
2. 会不会出现一个叶子结点中，正负样本数目相等的情况？如果出现这种情况，要怎么决定类别呢？

第5章 决策树

两种理解

• if-then规则。可以将决策树看成一个if-then规则的集合，使用二叉决策树做预测的过程可以写成如下的算法：

当前位置 = 根结点
while 当前结点是内部结点:
    if 特征 <= 阈值, then:
        进入左子结点
    else:
        进入右子结点
以当前叶子结点上的标签作为预测结果

这种理解方式有助于我们理解决策树的一个重要性质：互斥且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条规则所覆盖。

• 条件概率分布。对于任意的输入$x\in \mathcal{X}$（特征空间），都对应了一个唯一的叶子结点，在这个叶子结点上定义了条件概率分布$P(Y|X=x)$，我们会取条件概率最大的y作为该结点的标签。（注意不要和Hierarchical Softmax弄混，对于Softmax来说，给定x，在从根结点到叶子结点的路径上，总是以p的概率走到左子结点，以1-p的概率走到右子结点，所以叶子结点的概率和为1。而决策树是互斥的，对于给定的x，它以1的概率走到一个叶子结点，不同的叶子结点对应不同的x下的条件概率，所以和不等于1）。

决策树的构建

主要包含以下两部分：

• 特征选择。决定每个内部结点分裂的条件。
• 剪枝。避免过拟合，保证模型的泛化性能。

特征选择

​ 基本思路是，使得结点分裂后的“不纯度”下降得尽可能多，也即不确定性减少得多。例如，分裂前结点包含10个样本点，正负样本点各为5个。我们希望分裂之后能够将正负样本点分开，即一个子结点全是正类，另一个全是负类。如果达不到这种理想的情况，起码子结点中正负样本的个数有较大的差距，比如1个正类4个负类，我们可以以较大把握将该结点归为负类。

​ 衡量这种“不纯度下降幅度”的方法主要有以下三种：

• 信息增益

$$ g(D,A)=H(D)-H(D|A) $$

缺点是没有考虑特征取值个数的影响，偏向于选择取值较多的特征

• 信息增益比

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

• Gini指数

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

剪枝

​ 通过极小化决策树整体的损失函数或代价函数来实现。 $$ \begin{align} C_\alpha(T)&=C(T)+\alpha|T|\ &=\sum_{t=1}^{|T|}{N_tH_t(T)+\alpha|T|} \end{align} $$ ​ 其中，C(T)表示模型对训练数据的拟合程度，|T|表示模型的复杂程度，参数$\alpha$控制两者之间的影响。经验熵为 $$ H_t(T)=-\sum_k{\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}} $$ ​ 从叶子结点开始向上剪枝，如果剪枝（回退到父结点）后的整体损失函数下降，则进行剪枝，直到不能继续为止。

CART(Classification and regression tree)

• 二叉树
• 特征选择遵循Gini指数最小化准则
• 可以做分类（以叶子结点中多数样本的类别作为该结点的类别）或回归（以叶子结点中所有样本的预测值的均值作为该结点的预测值）
• 用递归的方法对树进行剪枝（每个$\alpha​$的区间对应唯一的一棵子树，一系列区间对应一个子树序列），通过交叉验证从子树序列中选取最优子树