可以实现分类算法、回归算法，计算复杂度不高，对缺失值不太敏感，同时可以处理不相关特征；同时是集成学习算法Random Forest的基础算法；
1、ID3：解决分类问题
1.1、分裂节点：计算信息增益，值最大的为当前分裂特征
信息论中定义为互信息：，信息增益越大，当前节点该特征越适合做分裂特征
熵的理解：特征的取值越多，其信息熵越大
X代表特征，n为特征X的不同取值的数量，Pi是取第i个值的概率；
条件熵：在Y条件下，X的熵
信息增益：
1.2、ID3算法的不足
1.2.1、没有考虑过拟合问题
1.2.2、没有考虑缺失值
1.2.3、信息增益为分裂标准，容易偏向于取值较多的特征
1.2.4、没有考虑连续特征变量（但可通过连续特征离散化处理）
针对ID3的不足，出现了C4.5算法.
2、C4.5：解决分类问题
2.1、分裂节点：计算信息增益的增益率；即该特征的信息增益与特征熵的比值，值最大的为当前节点的分裂特征；
特征熵：
信息增益比：
样本特征A的特征值越多，则分母（特征熵）越大，分裂节点可以避免偏向特征值较多的特征。
B为样本集合，A为样本的特征，n为特征A的类别数，Bi为特征A第i个取值对应的样本数，|B|为样本数；
2.2、C4.5的优点：
2.2.1、采用信息增益比，解决了ID3信息增益偏向于取值较多的特征的问题；
2.2.2、考虑了ID3没有解决连续属性离散化问题
e.g.某样本中特征A为连续特征值，根据A的所有取值，从小到大排序，分别取出所有相邻两个值的均值，记做集合m，然后计算m中的每个值当做二元分类点的信息增益，选择信息增益最大的值为连续特征A的二元分类点。
2.2.3、缺失值的自动处理策略；
2.2.4、 C4.5引入了正则化系数进行初步剪枝；
2.3、C4.5的不足：
2.3.1、只能用于分类；
2.3.2、剪枝方法有优化空间；
2.3.3、生成的是多叉树，但使用二叉树会比多叉树效率更高；
2.3.4、选择了复杂度较高的熵来度量，计算比较耗时，且遇到连续值还需要进行排序；
CRAT树可实现分类和回归算法，在下一章节会详细讲解。
欢迎关注我的公众号！
