姓名：王映中 学号：20181214025 学院：广研院
转自 https://blog.csdn.net/weixin_42327752/article/details/117806076
【嵌牛导读】以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使信息增益最大的属性（熵值变为最小），以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。
【嵌牛鼻子】ID3算法、C4.5算法
【嵌牛提问】如何实现ID3算法？
【嵌牛正文】
1 ID3算法
1.1 ID3算法思想
以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使信息增益最大的属性（熵值变为最小），以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0。
1.2 ID3算法流程
1.3 ID3不足之处
（1）没有考虑连续特征，比如长度、密度值（C4.5采用了特征离散）
（2）对于缺失值的情况没有考虑
（3）信息增益作为标准容易偏向于去取值较多的特征（C4.5 采用信息增益比改进）
（4）由于只有树的生成，容易出现过拟合
2 C4.5算法
2.1 C4.5算法思想
整体思路和ID3区别不大，只是在处理连续数据特征和采用信息增益比作为特征选取的参数。
2.2 二元分割（连续值特征离散化）
比如m个样本的连续特征A有m个，从小到大排列为a1,a2,…,am,则C4.5取相邻两样本值的中位数，一共取得m-1个划分点，其中第i个划分点Ti表示为：Ti=[a(i)+a(i+1)]/2。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为at,则小于at的值为类别1，大于at的值为类别2，这样我们就做到了连续特征的离散化。
2.3 C4.5不足之处
（1）由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。
（2）C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
