1. 三个步骤

决策树算法可以分为三个步骤：

  1. 特征选择
  2. 决策树生成
  3. 剪枝（防止过拟合）

在决策树生成阶段，构建节点分支时，目的是选择那些让分裂的子集尽可能“纯”的属性，选择属性的方法有：

  1. ID3（信息增益）
  2. C4.5（信息增益比）
  3. CART（基尼系数取代熵模型）

2. ID3

2.1 集合的熵

熵是衡量集合纯度的标准之一，它的计算公式如下：

\[Ent(D) = - \sum_{k=1}^{|D|} p_k \log p_k \tag{1}\]

其中\(p_k\)表示数据集\(D\)中第\(k\)类占比。熵越大说明集合越混乱，反之则说明集合比较“纯”。

2.2 信息增益

有了熵作为衡量集合纯度的标准，ID3使用信息增益（Information gain）来选择当前节点的属性。

信息增益：一个属性的信息增益就是由于这个属性分割样本而导致的熵降低量。

假设离散属性\(a\)有\(V\)个可能取值\(\{a_1, a_2, \cdots, a_V\}\)，样本集合\(D\)中，属性\(a\)上取值为\(a_v\)的样本标记为\(D_v\)，则属性\(a\)对应集合\(D\)的信息增益\(Gain(D, a)\)定义为：

\[Gain(D, a) = Ent(D) - \sum_{v=1}^V \frac{|D_v|}{|D|} Ent(D_v) \tag{2}\]

理解为属性\(a\)的信息使得样本集合不确定性减小的程度。如果某属性的信息增益更大，说明选择了这个属性进行划分后，集合的熵变小更多。

2.3 特点

  1. 无回溯且局部最优的；
  2. 没有剪枝过程，容易过拟合；（缺点）
  3. 只能处理离散分布的特征；（缺点）
  4. 没有考虑缺失值的处理；（缺点）
  5. 对可取数目较多的属性有偏好。例如，把样本编号作为属性，那么每个编号只有一个样本，纯度极高。（缺点）

3. C4.5

3.1 信息增益率

为了解决ID3的不足，C4.5算法提出用信息增益率（Gain ratio）来选择节点的属性，信息增益率是由信息增益\(Gain(D, a)\)和分裂信息度量\(IV(D, a)\)共同表示的：

\[Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(D, a)} \tag{3}\]

其中： \(IV(D, a) = - \sum_{v=1}^V \frac{|D_v|}{|D|} \log \frac{|D_v|}{|D|} \tag{4}\)

分裂信息用于衡量属性的广度和均匀度，从公式上看，实际上是各个属性样本占比的熵。分裂信息会阻碍模型选择均匀分布的属性。

例如上面的例子，把编号作为属性时，假设有\(n\)个样本被编号分成的\(n\)组，\(IV=- \sum_{v=1}^n \frac{1}{n} \log \frac{1}{n} = \log_2 n\)；而另一个属性把样本分成各一半，\(IV = -\sum_{v=1}^2 \frac{1}{2} \log \frac{1}{2} = 1\)；两个属性的信息增益相等时，两个属性的\(IV\)分别作为分母，显然第二个属性计算得到的信息增益比更大。

3.2 剪枝

树的节点数量决定一棵决策树的复杂度，剪枝能够一定程度抵抗过拟合，提高模型泛化性。

在节点划分之前判断是否需要继续扩展：预剪枝

  • 剩余样本的数量小于某个阈值时；
  • 所有特征都已经分裂；
  • 节点划分后准确率反而降低。

对已经生成完毕的决策树进行剪枝：后剪枝

  • 用递归的方式针对每一个非叶子节点进行评估，用一个最佳叶子节点代替这棵子树是否有益。如果剪枝后错误率有下降，那么该子树可以被替换。

3.3 缺失值处理

对于缺失值处理问题可以分成两个子问题：

  1. 如何对特征缺失的样本计算信息增益率？
  2. 应该把特征缺失的样本划分到哪个子集中？

对于问题一：C4.5对于具有缺失值的特征，用没有缺失的样本子集所占比重来折算。例如100个样本对特征\(A\)缺失了50个，那么对剩余的50个样本计算信息增益率后乘0.5，目的是体现缺失值的影响，尽可能不要选择具有缺失值的特征作为分裂节点。

对于问题二：C4.5将该样本分配权重并划分到所有子节点。如上面的例子，对特征\(A\)分裂后形成三个分支，分别具有10、10, 30个样本，那么将有缺失值的50个样本划分到三个分支中，但是他们的权重变成1/5、1/5和3/5，减少他们在后续计算信息增益比时的权重。

3.4 特点

  1. 对可选数目较少的属性有偏好；
  2. 在一些特定情况下，可能存在某个集合\(D\)的剩余属性中\(\vert D_v \vert\)非常接近\(\vert D \vert\)，这会导致分裂信息接近0,进而导致信息增益比非常大。这时候可以定义一些规则，例如先计算每个属性的增益，对于增益大于平均值的属性才用信息增益比来比较。
  3. 只能用于分类任务；（缺点）

4. CART

Classification And Regression Tree (CART)，即分类回归树算法。该算法与上述两种的最大不同是，它生成的数是二叉树，即将节点变成“是/否”的类型，这能够提升决策树的效率。

4.1 Gini

Gini指数也是衡量一个集合纯度的方法：

\[Gini(D) = 1 - \sum_{k=1}^K (\frac{|D_k|}{|D|})^2 \tag{5}\]

本质：从样本集合中随机取两个，它们不是同一类的概率。概率越小越纯。

所以，假设属性\(a\)将集合\(D\)划分为\(D_1\)和\(D_2\)，那么Gini指数为：

\[Gini(D, a) = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2) \tag{6}\]
  • 为什么选择Gini指数代替熵？ 因为Gini指数与熵非常接近。

Proof：
将\(f(x) = - \log x\)在\(x=1\)处进行一阶泰特展开：

\[f(x) = f(x_0) + f'(x_0)(x-x_0) = f(1) + f'(1)(x-1) = 1-x \tag{7}\]

所以：

\[Ent(D) = - \sum_{k=1}^K p_k \log p_k \approx \sum_{k=1}^K p_k(1-p_k) = 1 - \sum_{k=1}^K p_k^2 = Gini(D) \tag{8}\]

4.2 剪枝

CART采用“基于代价复杂度”的剪枝方法进行后剪枝，这种方法会生成一系列树，每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的，这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。这种方法需要使用一个单独的测试数据集来评估所有的树，根据它们在测试数据集的分类性能选出最佳的树。 摘自：Decision Tree-ID3、C4.5、CART

4.3 缺失值处理

对于缺失值的两个子问题（3.3）：

对于问题一：CART提出惩罚机制来反映缺失值的影响。例如一个特征在样本集合中有20%的记录是缺失的，那么这个特征在计算Gini指数时会进行20%的惩罚。目的是为了尽可能减少提早选择具有缺失值的特征作为分裂节点。这一点是与C4.5一样的。

对于问题二：CART采用的做法是“代理特征分裂”，这种方法比较复杂，而且计算量大，一般的机器学习框架下都不用这种方式进行处理。想详细了解过程的可以移步到参考链接中。

4.4 特点

  1. CART生成的树为二叉树，运算速度更快；
  2. 既能分类也能回归；
  3. 采用Gini系数作为分裂标准，减少对数运算；

5. 连续属性处理

连续属性是不可枚举的，所以不能依照上述算法进行分裂节点。二分法是将连续属性离散化的常用方法，具体做法如下：

给定训练集\(D\)和连续属性\(a\)，假设\(a\)在\(D\)上出现了\(n\)个不同取值，对这些值从小到大排序为\(\{a_1, a_2, \cdots, a_n\}\)，选择划分点：
\(T_a = \{\frac{a_i + a_{i+1}}{2} | 1 \leq i \leq n-1 \}\)
即把区间\([a_i, a_{i+1})\)的中点作为划分点。

6. 决策树特点

  1. 不需要做数据归一化；（优点）
  2. 能处理连续型、离散型数据；（优点）
  3. 训练最优决策树是完全NP问题，算法只能采用贪心策略，每一步都选择当前最优的特征进行分裂；（缺点）

Reference

Decision Tree-ID3、C4.5、CART
Decision tree