4.决策树

决策树

一、决策树概述

     训练阶段，根据训练数据构造决策树模型；在测试阶段，对数据进行分类。

     决策树重要的三个阶段：1.特征的选择 2.决策树的生成 3.决策树剪枝

     决策树内部节点表示特征或者属性，叶节点表示类别。

     特征的选择：根据信息增益（ID3）和信息增益比（C4.5）

二、基本的概念

     （1）经验熵的计算（由数据极大似然估计得到，所以在熵基础上称为经验熵）。熵值越大表示不确定性就越大。熵的公式：

     其中n表示类别数，Pi表示第i类别的数量与总数量的比。

     （2）经验条件熵：

     其中H(Y|X)为经验条件熵，表示在X条件下对数据集Y进行分类的不确定性

     （3）信息增益：表示不确定变化的程度

     其中H(D|A)为经验条件熵，表示在A条件下对数据集D进行分类的不确定性，H(D)表示D数据集原本的不确定性，因此g(D,A)表示数据集D不确定性减少的程度。
计算经验条件熵可如下：

     其中n表示根据特征A维度的类别数。

     （4）信息增益比：因为信息增益存在会偏向于取值较多的特征的问题，因此在C4.5中用到了信息增益比去选择特征。

三、决策树的生成

3.1 ID3

3.2 C4.5

四、决策树剪枝

4.1 原因

     （1）剪枝是为了防止过拟合，出现过于复杂的决策树，以至于对训练数据分类准确率很高，而对测试数据的泛化能力很差的情况。

     （2）简化分类模型。

4.2 具体的做法

     裁掉一些叶子结点。通过计算其损失函数来实现。

     损失函数（目标函数）：

     其中：

     其中C(T)为所有叶子节点的不确定性，|T|表示叶子结点的数量，α|T|起到了平衡决策树复杂度的作用。

     具体算法如下：

五、参考

     李航的《统计学习方法》