7.2 决策树

决策树(Decision Tree)可用于分类和回归任务。决策树从根结点出发，在一定的判断标准下，决策树在每个内部结点上寻找合适的特征来划分样本，使得划分后的结点之间具有最大的区分度。对内部结点重复上述操作，便可得到多层结点，直至达到各个叶结点（终止结点）。

7.2.1 分类树

分类树考虑响应变量为分类变量的情形，以叶结点处数量最多的类别作为叶结点的类别标签。首先考虑决策树是如何“生长”的，也就是根据什么准则来分裂结点。我们总是希望分裂后的结点中的样本尽可能的属于同一类别，即该结点有着较高的“纯度”。一言以蔽之，划分的过程就是从混乱走向有序的过程。

  1. 信息增益

    考虑在结点\(D\)中的所有样本共属于\(M\)个类别，考虑信息熵\(Ent(D)\)

    \[ \textrm{Ent}(D)=-\sum_{m=1}^Mp_m \log_2p_m \tag{7.1} \]

    如何理解信息熵？可以这样简单理解：对于不确定的、离谱的事情，人们就会拿不准，从而产生疑惑，想要知道更多的信息，此时信息熵就大；而对于确定的、理所应当的事情，人们就会很有把握，不会多问，此时信息熵就小。举个例子，一枚正常硬币猜正反，无论猜正面朝上还是猜反面朝上，概率都是0.5，因此只能瞎猜，没有什么把握。但对于一枚有特殊倾向的硬币，即正面朝上概率为0.9，那么大家自然都会猜正面朝上，并且有很大的把握。因此，信息熵是对不确定性的度量，信息熵越大，越不确定。

    由此可得信息增益的定义：

    \[ \textrm{Gain}(D,x)=\textrm{Ent}(D)-\sum_{v=1}^V\frac{n_v}{n}\textrm{Ent}(D^v) \tag{7.2} \]

    其中\(x\)表示某个特征，\(V\)表示该特征有多少个取值，\(n\)和\(n_v\)分别表示原结点与各个分支结点的样本量。

    若\(x\)是连续变量，则可将其离散化，并且连续变量可以在后续划分中进一步细分，而离散变量只能使用一次。

    我们要寻求合适的特征使得划分后的子结点与原结点相比信息熵平均下降得最多。这就是信息增益的准则。

    代表算法：ID3决策树

  2. 增益率

    信息增益准则对取值数目较多的特征有所偏好。由此引入增益率，其定义为

    \[ \textrm{Gain_ratio}(D,x)=\frac{\textrm{Gain}(D,x)}{\textrm{IV(x)}} \tag{7.3} \]

    其中

    \[ \textrm{IV}(x)=-\sum_{v=1}^V\frac{n_v}{n}\textrm{log}_2\frac{n_v}{n} \tag{7.4} \]

    事实上，\(\textrm{IV}(x)\)就是信息熵的形式，可以视作某种对\(x\)取值数量的惩罚。

    代表算法：C4.5决策树（先选信息增益高的，再选增益率高的）

  3. 基尼系数

    定义基尼系数

    \[ \textrm{Gini}(D)=\sum_{m=1}^Mp_m(1-p_m)=1-\sum_{m=1}^Mp_m^2 \tag{7.5} \]

    直观来看，基尼系数衡量的就是从结点\(D\)中随机抽取两个样本，其类别不一致的概率。因此基尼系数越小，该结点纯度越高。

    代表算法：CART决策树

正如园艺里需要对植物进行修剪一样，决策树也能进行剪枝。决策树的剪枝策略分为预剪枝和后剪枝。

  • 预剪枝

    在决策树的生成过程中，对每个结点在分裂前进行估计，若对该结点划分不能提高泛化能力，则停止划分并将该结点设置为叶结点。

    预剪枝降低了过拟合的风险，但存在欠拟合的可能。

  • 后剪枝

    先完整地生成决策树，然后自下而上地对所有非叶结点进行考察。若将该非叶结点替换为叶结点后能够提升泛化性能，则进行替换。

    后剪枝消耗的时间比预剪枝长，但欠拟合的风险较小，其泛化性能往往优于预剪枝策略。

7.2.2 回归树

回归树考虑响应变量为连续变量的情形，以叶结点的响应变量平均值作为该叶结点的预测值。

回归树划分结点的准则多种多样，但都是类似的，如最小化平方误差MSE、最小化均方根误差RMSE、最小化平均绝对误差MAE等。

同样，回归树也能进行剪枝操作。

  • 预剪枝

    回归树的预剪枝策略可以设置一个样本量阈值，当结点分裂后的样本量小于该阈值，则不进行分裂。

  • 后剪枝

    后剪枝可以采取代价复杂性剪枝的策略，即先生成一棵完整的树，然后考虑如下的惩罚残差平方和函数

    \[ \textrm{SSE}+\lambda|T| \tag{7.6} \]

    其中\(|T|\)表示该棵决策树叶结点的数量。\(\lambda\)的值可通过交叉验证的方法进行确定。

7.2.3 实现

rpart包中的rpart()函数可以用来构建回归树和分类树。

树的形式为二叉树

  1. rpart()参数

    • formula

      模型公式，看看谁是响应变量谁是预测变量。

    • data

      数据框。

    • weights

      设置权重。

    • subset

      指示数据框中的哪些样本会被用于建模。

    • na.action

      如何对待缺失值。默认使用na.rpart()函数，即删除缺失响应变量的样本或者缺失所有预测变量的样本（缺失部分预测变量也会被保留）。

    • method

      可选值为anova、poisson、class、exp。其中anova对应构建回归树，class对应构建分类树。

    • model

      是否在结果中保存模型框架。

      感觉用不上

    • x

      是否在结果中保存预测变量，默认为FALSE。

    • y

      是否在结果中保存响应变量，默认为TRUE。

    • parms

      添加到分裂函数中的额外参数。对于回归树而言，不用额外添加。对于分类树，可传入一个列表，列表中分为三个元素：prior、loss、split，分别表示先验概率（正数，且总和需为1）、损失矩阵（规定了错分时的损失，要求对角线元素为0，非对角线元素为正）、划分标准（可选值为基尼系数gini、信息增益information）。

    • control

      为rpart.control()函数以列表形式传入的参数。

      详情建议问ai，懒癌犯了0.0

    • cost

      一个向量长度为预测变量数的非负向量，在拆分预测变量时用作缩放比例，默认为1。若该值越大，则对应预测变量的重要性程度越低。在量纲不一致的情形，该参数可用于减轻量纲带来的影响，因为算法会倾向于选择尺度较大的预测变量。

  2. 其余函数

    • rpart.control()

      可更为细致地控制决策树的生长逻辑，如设置结点的最小训练样本数。

    • prune()

      用于剪枝。

    • predict()

      用于预测。

    • rpart.plot包

      用于绘制决策树的结果，是对plot.rpart()函数的拓展。