[数据结构与算法]机器学习-决策树

决策树

1.什么是决策树？

决策树是一种常见的机器学习方法，其核心思想是相同（或相似）的输入产生相同（或相似）的输出，通过树状结构来进行决策，其目的是通过对样本不同属性的判断决策，将具有相同属性的样本划分到一个叶子节点下，从而实现分类或回归. 以下西瓜分类的决策树模型图。

在上述示例模型中，通过对西瓜一系列特征（色泽、根蒂、敲声等）的判断，最终我们得出结论：这是否为一个好瓜. 决策过程中提出的每个判定问题都是对某个属性的“测试”，例如“色泽=？”，“根蒂=？”. 每个测试的结果可能得到最终结论，也可能需要进行下一步判断，其考虑问题的范围是在上次决策结果限定范围之内. 例如若在“色泽=青绿”之后再判断“根蒂=？”.

2. 决策树的结构

一般来说，一棵决策树包含一个根节点、若干个内部节点和若干个叶子节点. 叶子节点对应最终的决策结果，其它每个节点则对应与一个属性的测试. 最终划分到同一个叶子节点上的样本，具有相同的决策属性，可以对这些样本的值求平均值来实现回归，对这些样本进行投票（选取样本数量最多的类别）实现分类.

3. 如何构建决策树？

3.1 构建决策树算法

决策树的构建，就是不断选取好的特征作为决策节点，构建一颗泛化能力较强的树结构，其基本算法如下所示：

显然，决策树的构建是一个递归的过程，核心是以下两个问题：

• 如何选取特征. 决策树构建的每一步，应该挑选最优的特征，进行决策对数据集划分效果最好；
• 决定何时停止分裂子节点.

3.2 如何选择特征?

① 信息熵

信息熵（information entropy）是度量样本集合纯度的常用指标，该值越大，表示该集合纯度越低（或越混乱），该值越小，表示该集合纯度越高（或越有序）. 信息熵定义如下：
$$H=?\sum _{i=1}^{n}P(x_i)lo{g}_{2}P(x_i)$$
其中，$P(x_i)$表示集合中第i类样本所占比例，当$P(x_i)$为1时（只有一个类别，比例为100%）, $lo{g}_{2}P(x_i)$的值为0，整个系统信息熵为0；当类别越多，则$P(x_i)$的值越接近于0，$lo{g}_{2}P(x_i)$趋近去负无穷大，整个系统信息熵就越大.以下代码，展示了类别数量从1…10的集合信息熵变化.

② 信息增益

决策树根据属性进行判断，将具有相同属性的样本划分到相同节点下，此时，样本比划分之前更加有序（混乱程度降低），信息熵的值有所提升。用划分前的信息熵减去划分后的信息熵，就是决策树获得的信息增益。可以用以下表达式表示：
$$Gain(D,a)=Ent(D)?\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$
其中，D表示样本集合，a表示属性，v表示属性可能的取值$v^1,v^2,...,v^n$, $\frac{|D^v|}{|D|}$表示权重，样本越多的分支对分类结果影响更大，赋予更高的权重, $Gain(D,a)$表示在样本集合D上使用属性a来划分子节点所获得的信息增益. 以下是一个关于信息增益计算的示例.

③ 增益率

增益率不直接采用信息增益，而采用信息增益与熵值的比率来作为衡量特征优劣的标准. C4.5算法就是使用增益率作为标准来划分属性. 增益率定义为：
$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$
其中
$$IV(a)=?\sum _{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}$$

④ 基尼系数

基尼系数定义为：
$$Gini(p)=\sum _{k=1}^k{p}_k(1?p_k)=1?\sum _{k=1}^k{p}_k^2$$
直观来说，基尼系数反映了从数据集D中随机抽取两个样本，类别标记不一致的概率. 因此，基尼系数越小，数据集的纯度越高. CART决策树（Classification And Regression Tree）使用基尼系数来选择划分属性，选择属性时，选择划分后基尼值最小的属性作为最优属性. 采用和上式相同的符号表示，数据集D下属性a的基尼系数定义为：
$$Gini\_index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$

3.3 如何停止分裂?

以下几种情况会停止决策树子节点的构建：

• 当前节点所有样本属于同一个类别，无需划分
• 当前属性集为空，或者所有样本取值相同，无法划分
• 当前节点包含的样本集合为空，不能划分
• 当前节点样本数量少于指定数量

4. 决策树的剪枝

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段. 在决策树学习中，为了尽可能正确分类训练样本，节点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学的“太好了”，以至于把训练集本身的一些特点当做数据所具有的一般性质而导致过拟合. 因此，可通过主动去掉一些分支来降低过拟合风险.

（1）预剪枝. 决策树生成过程中，对每个节点在划分前进行评估，若当前节点不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶子节点.

（2）后剪枝. 先训练为一颗完整的决策树，然后自低向上对非叶子节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化能力提升，则将该子树替换为叶节点.