点击上方卡片链接就可以进入专栏，专栏右上角有订阅选项，欢迎大家订阅～

前言

大家好，我是鬼仔，今天带来《机器学习高频面试题详解》专栏的第1.9节：决策树-结点生成算法。这是鬼仔第一次开设专栏，每篇文章鬼仔都会用心认真编写，希望能将每个知识点讲透、讲深，帮助同学们系统性地学习和掌握机器学习中的基础知识，希望大家能多多支持鬼仔的专栏～

目前这篇是试读，后续的文章需要订阅才能查看哦，专栏预计更新30+篇文章（只增不减），具体内容可以看专栏介绍，大家的支持是鬼仔更新的动力！

一、原理

1. ID3算法

ID3（Iterative Dichotomiser 3）算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树，相当于用极大似然法进行概率模型的选择。它在每一步选择当前最优的特征来划分数据，并递归地在子数据集上重复这个过程，最终生成一棵完整的决策树，用于对新数据进行分类。

具体的构建过程如下：从根结点开始，计算所有特征的信息增益，选择信息增益最大的特征作为该结点的特征，并根据该特征的不同取值分裂当前结点，建立子节点；递归地重复这个过程，直到所有特征都被考虑过或者数据集中的样本全部属于同一类别。

2. C4.5算法

ID3算法有着明显的不足，比如只能处理离散型的特征、信息增益准则的固有缺陷：对取值数目较多的属性有所偏好、缺失值处理的问和过拟合问题。C4.5算法是ID3算法的改进版本，针对以上缺点，作出了如下改进：

1）连续特征离散化

ID3算法无法处理连续型的特征，C4.5算法的做法是将连续的特征离散化。假设在样本集中，连续特征A有m个不同值，从小到大排列为，离散化的具体操作如下：

• 取相邻两个特征值的平均数，可得到个划分点，其中第i个划分点表示为：；
• 分别计算以这个划分点作为二元分类点时的信息增益率，选择信息增益率最大的点为该连续特征的最佳切分点。比如信息增益率最大的划分点为，则小于的值为类别1，大于的值为类别2，这样即可将连续特征转化为离散特征。

在C4.5算法中，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程，而离散特征则不可以。

2）采用信息增益率准则

从上一篇文章可知，信息增益作为标准容易偏向于取值较多的特征。为此，C4.5算法采用信息增益率准则来选择最优分裂结点。与信息增益相比，信息增益率引入了特征熵的概念（作为计算公式的分母项）。特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。

正所谓矫枉过正，信息增益率准则又不可避免地会对取值较少的特征有所偏好。所以，C4.5算法不是直接选择信息增益率最大的候选划分特征，而是先从候选特征中找出信息增益高于平均水平的特征，再从中选择信息增益率最高的。

3）利用概率权重方法处理样本缺失值

在机器学习中，缺失值问题可以通过几种方法来解决。一种常用的方法是使用代替值，例如使用数据集中该特征的平均值或中位数来代替缺失值。另一种方法是在建立决策树的过程中对缺失值进行特殊处理，例如分裂时不考虑包含缺失值的节点。

在C4.5算法中，还会利用概率权重方法处理样本缺失值，具体流程可参考下面的面试真题。

4）通过剪枝解决过拟合问题

过拟合的决策树的泛化能力很差，因此需要通过剪枝算法来缓和过拟合问题。剪