9 – 决策树的ID3和C4.5介绍一下 ”？
一些定义：决策树是一个非常常见并且优秀的机器学习算法，它易于理解、可解释性强，其可作为分类算法，也可用于回归模型。
解答：
ID3 算法是建立在奥卡姆剃刀（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树。其核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：
1） 初始化特征集合和数据集合；
2） 计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3） 更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4） 重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。
ID3的缺点：
1）ID3 没有剪枝策略，容易过拟合；
2）信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
3）只能用于处理离散分布的特征；
4）没有考虑缺失值。
C4.5 相对于 ID3 的缺点对应有以下改进方式：
1）引入悲观剪枝策略进行后剪枝；
2）引入信息增益率作为划分标准；
3）将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均4）数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作5）为该连续特征的二元离散分类点；
6）对于缺失值的处理可以分为两个子问题：
问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。
C4.5缺点
1）剪枝策略可以再优化；
2）C4.5 用的是多叉树，用二叉树效率更高；
3）C4.5 只能用于分类；
4）C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
5）C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。
参考链接：https://zhuanlan.zhihu.com/p/85731206
原文链接：https://blog.csdn.net/IT_Herven/article/details/120388193?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171851498816800184188889%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=171851498816800184188889&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~times_rank-12-120388193-null-null.nonecase&utm_term=AI%E9%9D%A2%E8%AF%95
