[Stay Sharp]决策树基础

决策树概念

决策树是最常用的机器学习算法之一，它能被用来处理分类和回归问题。
它是一棵树，每个节点对应一个特征（属性），每一条边（分支）代表一个决策（规则），而每个叶子节点表示一个结果（类别或者连续的数值）

它经常模仿人类的处理问题的思路，所以比较容易解读它处理数据的流程。

以下是常见的银行贷款的流程，决策树就像这样，我们很容易看清楚它的处理流程。

image.png

常用方法

• ID3
• C4.5
• CART

ID3

ID3算法是Ross Quinlan提出的，它是C4.5算法的前辈，常常被用于机器学习和NLP领域中。
我们以经典的天气数据集（根据天气来判断要不要外出运动）为例。它有四个输入特征（outlook 天气 ,temp 温度,humidity 湿度 和 windy 风）输出为是否适合外出运动。

image.png

我们要构造一棵树，首先要构造一个root（根节点），我们知道树的每一个节点代表着一个特征，那么我们该如何选择这个特征呢？一旦我们找到了这个特征，我们就可以把这个特征作为根节点，然后使用同样的方法对每个分支进行处理，直到所有节点都不能再继续拆分（属于同一类别）。

如何找到最佳特征？

在ID3算法中，我们使用信息增益来找到最佳特征。
在引入信息增益前，我们要首先提出信息理论中的一个术语：entropy（熵），它用来表示一个数据集的纯度。它的公式是

数据集中共含有类样本，表示第类样本占所有样本的比例。对于二分类数据集而言，如果所有数据都属于同一类，那么数据集的熵最小，为0.而如果所有数据一半属于一类，另一半属于另一类，那么数据集的熵最大，为1.
所以熵越小，该类的数据越纯。据此，我们引入信息增益的概念，信息增益表示分类前和分类后的熵的差，所以如果信息增益越大，表明分类后的熵越小，分类的数据越纯，分类越准确。因此我们的ID3流程变成了：

1. 计算数据集的熵
2. 对于每一个特征：
     1. 计算按该特征分类后的每一类的熵
     2. 计算出按该特征分类后的各类的平均熵
     3. 计算当前特征的信息增益
3. 选取具有最大增益比的特征
4. 对每一个子类重复进行以上的步骤，直到生成最后的决策树。

以天气数据集举例，我们首先计算整个数据集的熵：
共计14个样本，其中5个输出为no，9个输出为yes，熵的计算公式为：

然后，我们分别计算按照每一个特征进行分类后的信息增益。
首先计算使用特征outlook分类后的信息增益，outlook有三条决策（sunny、overcast、rainy）：

每一条决策后的熵为：



按照outlook分类后平均的熵为：

信息增益为：

以此类推，我们求出使用每一个特征的信息增益（如下图），我们发现按照Outlook进行分类后的信息增益最大，于是我们选用Outlook作为我们的根节点。

image.png

再对Outlook分类后的数据进行以上操作，最终生成类决策树：

image.png

C4.5

C4.5是 Ross Quinlan在它的ID3基础扩展出来的算法，它使用的特征选择方法是增益率。信息增益方法对可取值数据较多的特征有所偏好，信息增益率对可取值数据较少的特征有所偏好。C4.5首先选出信息增益高于平均水平的特征，然后再从其中找出信息增益率最高的特征。

其中

CART

CART算法使用基尼指数进行特征划分。

其中

优点

• 白盒操作，易解读
• 不用特征归一化
• 能处理离线和连续数据（回归和分类）

不足

• 如果是连续数据，树会变得非常庞大，影响解读
• 容易过拟合数据，尤其是特征很多而样本很少的情况，可以通过剪枝等方法来改善它。
• 小的改动会生成完全不同的决策树。可以通过bagging, boosting和random forests来改善。

参考

李航《统计学习方法》

周志华《机器学习》

https://medium.com/deep-math-machine-learning-ai/chapter-4-decision-trees-algorithms-b93975f7a1f1