决策树介绍

• 概念

决策树是一种有监督的机器学习算法，该方法可以用于解决分类和回归问题。

决策树可以简单地理解为达到某一特定结果的一系列决策。思考逻辑上，就像一连串的if-else，如果满足xx特征，则归为xx类别，否则则归为yy类别。（可以参考周志华老师《机器学习》里挑西瓜的案例）

这其中的关键，就是如何选取特征。一棵树能选取的特征往往有限，限制了模型的性能。因此就有了随机森林。

• 特征选择

特征选择决定了使用哪些特征来做判断。在训练数据集中，每个样本的属性可能有很多个，不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征，也就是分类能力较强的特征。

在特征选择中通常使用的准则是：熵

其中 c_k表示集合D中属于第k类样本的样本子集。

ID3算法

ID3是最早提出的决策树算法，他就是利用信息增益来选择特征的，它表示得知特征A的信息而使得样本集合不确定性减少的程度。

条件熵

信息增益=信息熵-条件熵

C4.5算法

是ID3的改进版，不是直接使用信息增益，而是引入“信息增益比”指标作为特征的选择依据。

ART（Classification and Regression Tree）

这种算法即可以用于分类，也可以用于回归问题。CART算法使用了基尼系数取代了信息熵模型。

!](https://img-blog.csdnimg.cn/97caf597334647beb453f2575c90fcf0.png)

• 优缺点

优点

决策树易于理解和解释，可以可视化分析，容易提取出规则；

可以同时处理标称型和数值型数据；

比较适合处理有缺失属性的样本；

能够处理不相关的特征；

测试数据集时，运行速度比较快；

在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

缺点

容易发生过拟合（随机森林可以很大程度上减少过拟合）；

容易忽略数据集中属性的相互关联；

对于那些各类别样本数量不一致的数据，在决策树中，进行属性划分时，不同的判定准则会带来不同的属性选择倾向

决策树实现逻辑

决策树是最简单的机器学习算法，它易于实现，可解释性强，完全符合人类的直观思维，有着广泛的应用。

决策树算法采用树形结构，使用层层推理来实现最终的分类。决策树由下面几种元素构成：

根节点：包含样本的全集

内部节点：对应特征属性测试

叶节点：代表决策的结果

预测时，在树的内部节点处用某一属性值进行判断，根据判断结果决定进入哪个分支节点，直到到达叶节点处，得到分类结果。这是一种基于if-then-else规则的有监督学习算法，决策树的这些规则通过训练得到，而不是人工制定的。

信息增益的公式

信息增益=信息熵-条件熵

其中信息熵：
其中 c_k表示集合D中属于第k类样本的样本子集。

条件熵：

信息增益：

信息增益率的公式

信息增益率：