概述

决策树是一个无参、非线性、有监督的机器学习算法，它是一种基本的分类与回归方法。本文主要讨论用于分类的决策树。 决策树可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

• 其主要优点：1. 模型具有可读性；2.分类速度快。

• 学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型；预测时，对新的数据，利用决策树模型进行分类。

• 决策树学习包括三个步骤: 特征选择、决策树的生成和决策树的修剪。

• ID3、C4.5、CART都是决策树著名的算法。

1.1 决策树模型与学习

1.1.1 决策树的基本要素

分类决策树模型是一种描述对实例进行分类的树形结构。树形结构由结点和有向边组成。

• 内部结点（圆圈）：对应数据的一个特征（属性）。
• 叶节点（方框）：对应数据的一个类别。
• 有向边：结点到结点的每一条路径构建一条规则。

1.1.2 决策树的学习方式

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。

此方法生成的决策树可能对训练数据有很好的分类能力，但对未知数据未必有很好的拟合能力（过拟合现象）。所以我们需要对已经生成的决策树进行剪枝，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶节点，使其回退到父节点，甚至更高的结点，然后将父节点或更高的节点改为新的叶节点。

如果特征数据很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据最有用于分类的特征。

可以看出，在决策树学习算法中的三个步骤中，决策树的生成对应于模型的局部选择 ，而决策树的剪枝对应于模型的全局选择。

1.2 特征选择

特征选择的准则是 信息增益 或 信息增益比

为了便于说明，先给出熵与条件熵的定义：
熵表示随机变量不确定性的度量，熵越小随机变量的纯度越高。
条件熵表示给定随机变量X的条件下，随机变量Y不确定性的度量。
下图为熵的公式：

1.2.1 信息增益(ID3)

信息增益表示得知特征A的信息而使得类Y的信息的不确定性减少的程度,
即 信息增益越大, 特征A具有更强的分类能力：

1.2.2 信息增益率(C4.5)

有些特征取值数目比较多,可以使用信息增益率去选择。
同样 信息增益越大, 特征A具有更强的分类能力 ：

其中：

增益率准则对可取数目较少的属性有所偏好。
因此，C4.5算法使用先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的方法。

1.2.3 基尼系数(CART)

数据集D的基尼值如下公式所示：Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。
Gini(D)越小，数据集D的纯度越高。

属性a的基尼指数定义为：

2 决策树的生成

通常使用信息增益最大、信息增益率比最大、基尼指数最小作为特征选择的准则。
决策树的生成往往计算信息增益或其他指标，从根节点开始，递归的产生决策树。
这相当于用信息增益或其他准则不断地选取局部最优的特征，或将训练集分割为能够基本正确分类的子集。

3 决策树的剪枝

由于生成的决策树存在过拟合问题，需要对它进行剪枝，以简化学到的决策树。
决策树的剪枝，往往从已生成的树上剪掉一些叶节点或叶节点以上的子树，并其父节点或根节点作为新的叶节点，从而简化生成的决策树。

4 CART算法

既可以做分类、又可以做回归。只能形成二叉树。

5 写在最后——随机森林

• 决策树是传统机器学习方法，是单个分类器， 有性能提升的瓶颈和过拟合的问题。
• 因此集成多个分类器来预测性能的方法应运而成，就是集成学习（ensemble learning）。
• 随机森林算法就是 Bagging（并行）集成方法里最具有代表性的一个算法。

尽管有剪枝等等方法，一棵树的生成肯定还是不如多棵树，因此就有了随机森林，解决决策树泛化能力弱的缺点。（可以理解成三个臭皮匠顶过诸葛亮）

而同一批数据，用同样的算法只能产生一棵树，这时Bagging策略可以帮助我们产生不同的数据集。Bagging策略来源于bootstrap aggregation：

• 从样本集（假设样本集N个数据点）中重采样选出Nb个样本（有放回的采样，样本数据点个数仍然不变为N）；
• 在所有样本上，对这n个样本建立分类器（ID3\C4.5\CART\SVM\LOGISTIC），重复以上两步m次，获得m个分类器，最后根据这m个分类器的投票结果，决定数据属于哪一类。

随机森林在bagging的基础上更进一步：

1. 样本的随机：从样本集中用Bootstrap随机选取n个样本
2. 特征的随机：从所有属性中随机选取K个属性，选择最佳分割属性作为节点建立CART决策树（泛化的理解，这里面也可以是其他类型的分类器，比如SVM、Logistics）
3. 重复以上两步m次，即建立了m棵CART决策树
4. 这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类（投票机制有一票否决制、少数服从多数、加权多数）

关于调参：

1.如何选取K，可以考虑有N个属性，取K=根号N
2.最大深度（不超过8层）
3.棵数
4.最小分裂样本树
5.类别比例